shape ops work in progress
git-svn-id: http://skia.googlecode.com/svn/trunk@7864 2bbb7eff-a529-9590-31e7-b0007b416f81
diff --git a/experimental/Intersection/CubicIntersection.cpp b/experimental/Intersection/CubicIntersection.cpp
index 833ac27..bf8ea46 100644
--- a/experimental/Intersection/CubicIntersection.cpp
+++ b/experimental/Intersection/CubicIntersection.cpp
@@ -14,7 +14,7 @@
#include "QuadraticUtilities.h"
#if ONE_OFF_DEBUG
-static const double tLimits[2][2] = {{0.599274754, 0.599275135}, {0.599274754, 0.599275135}};
+static const double tLimits[2][2] = {{0.772784538, 0.77278492}, {0.999111748, 0.999112129}};
#endif
#define DEBUG_QUAD_PART 0
@@ -74,7 +74,7 @@
static void bumpForRetry(double t1, double t2, double& s1, double& e1, double& s2, double& e2) {
double dt1 = distanceFromEnd(t1);
double dt2 = distanceFromEnd(t2);
- double delta = 1.0 / precisionUnit;
+ double delta = 1.0 / gPrecisionUnit;
if (dt1 < dt2) {
if (t1 == dt1) {
s1 = SkTMax(s1 - delta, 0.);
@@ -277,60 +277,6 @@
return i.intersected();
}
-static bool intersectEnd(const Cubic& cubic1, bool start, const Cubic& cubic2, const _Rect& bounds2,
- Intersections& i) {
- _Line line1;
- line1[1] = cubic1[start ? 0 : 3];
- if (line1[1].approximatelyEqual(cubic2[0]) || line1[1].approximatelyEqual(cubic2[3])) {
- return false;
- }
- line1[0] = line1[1];
- _Point dxy1 = line1[0] - cubic1[start ? 1 : 2];
- if (dxy1.approximatelyZero()) {
- dxy1 = line1[0] - cubic1[start ? 2 : 1];
- }
- dxy1 /= precisionUnit;
- line1[1] += dxy1;
- _Rect line1Bounds;
- line1Bounds.setBounds(line1);
- if (!bounds2.intersects(line1Bounds)) {
- return false;
- }
- _Line line2;
- line2[0] = line2[1] = line1[0];
- _Point dxy2 = line2[0] - cubic1[start ? 3 : 0];
- SkASSERT(!dxy2.approximatelyZero());
- dxy2 /= precisionUnit;
- line2[1] += dxy2;
-#if 0 // this is so close to the first bounds test it isn't worth the short circuit test
- _Rect line2Bounds;
- line2Bounds.setBounds(line2);
- if (!bounds2.intersects(line2Bounds)) {
- return false;
- }
-#endif
- Intersections local1;
- if (!intersect(cubic2, line1, local1)) {
- return false;
- }
- Intersections local2;
- if (!intersect(cubic2, line2, local2)) {
- return false;
- }
- double tMin, tMax;
- tMin = tMax = local1.fT[0][0];
- for (int index = 1; index < local1.fUsed; ++index) {
- tMin = SkTMin(tMin, local1.fT[0][index]);
- tMax = SkTMax(tMax, local1.fT[0][index]);
- }
- for (int index = 1; index < local2.fUsed; ++index) {
- tMin = SkTMin(tMin, local2.fT[0][index]);
- tMax = SkTMax(tMax, local2.fT[0][index]);
- }
- return intersect2(cubic1, start ? 0 : 1, start ? 1.0 / precisionUnit : 1 - 1.0 / precisionUnit,
- cubic2, tMin, tMax, 1, i);
-}
-
// this flavor centers potential intersections recursively. In contrast, '2' may inadvertently
// chase intersections near quadratic ends, requiring odd hacks to find them.
static bool intersect3(const Cubic& cubic1, double t1s, double t1e, const Cubic& cubic2,
@@ -398,7 +344,11 @@
}
result = true;
} else if (cubic1 != cubic2 || !approximately_equal(to1, to2)) {
- i.insert(to1, to2, p1);
+ if (i.swapped()) { // FIXME: insert should respect swap
+ i.insert(to2, to1, p1);
+ } else {
+ i.insert(to1, to2, p1);
+ }
result = true;
}
} else {
@@ -422,8 +372,8 @@
offset, i.depth());
}
// try parallel measure
- _Point d1 = dxdy_at_t(cubic1, to1);
- _Point d2 = dxdy_at_t(cubic2, to2);
+ _Vector d1 = dxdy_at_t(cubic1, to1);
+ _Vector d2 = dxdy_at_t(cubic2, to2);
double shallow = d1.cross(d2);
#if 1 || ONE_OFF_DEBUG // not sure this is worth debugging
if (!approximately_zero(shallow)) {
@@ -447,6 +397,49 @@
return result;
}
+// intersect the end of the cubic with the other. Try lines from the end to control and opposite
+// end to determine range of t on opposite cubic.
+static bool intersectEnd(const Cubic& cubic1, bool start, const Cubic& cubic2, const _Rect& bounds2,
+ Intersections& i) {
+ _Line line;
+ int t1Index = start ? 0 : 3;
+ line[0] = cubic1[t1Index];
+ // don't bother if the two cubics are connnected
+ if (line[0].approximatelyEqual(cubic2[0]) || line[0].approximatelyEqual(cubic2[3])) {
+ return false;
+ }
+ double tMin = 1, tMax = 0;
+ for (int index = 0; index < 4; ++index) {
+ if (index == t1Index) {
+ continue;
+ }
+ _Vector dxy1 = cubic1[index] - line[0];
+ dxy1 /= gPrecisionUnit;
+ line[1] = line[0] + dxy1;
+ _Rect lineBounds;
+ lineBounds.setBounds(line);
+ if (!bounds2.intersects(lineBounds)) {
+ continue;
+ }
+ Intersections local;
+ if (!intersect(cubic2, line, local)) {
+ continue;
+ }
+ for (int index = 0; index < local.fUsed; ++index) {
+ tMin = SkTMin(tMin, local.fT[0][index]);
+ tMax = SkTMax(tMax, local.fT[0][index]);
+ }
+ }
+ if (tMin > tMax) {
+ return false;
+ }
+ double tMin1 = start ? 0 : 1 - 1.0 / gPrecisionUnit;
+ double tMax1 = start ? 1.0 / gPrecisionUnit : 1;
+ double tMin2 = SkTMax(tMin - 1.0 / gPrecisionUnit, 0.0);
+ double tMax2 = SkTMin(tMax + 1.0 / gPrecisionUnit, 1.0);
+ return intersect3(cubic1, tMin1, tMax1, cubic2, tMin2, tMax2, 1, i);
+}
+
// FIXME: add intersection of convex hull on cubics' ends with the opposite cubic. The hull line
// segments can be constructed to be only as long as the calculated precision suggests. If the hull
// line segments intersect the cubic, then use the intersections to construct a subdivision for
diff --git a/experimental/Intersection/CubicIntersection_Test.cpp b/experimental/Intersection/CubicIntersection_Test.cpp
index 53d33cf..e45d543 100644
--- a/experimental/Intersection/CubicIntersection_Test.cpp
+++ b/experimental/Intersection/CubicIntersection_Test.cpp
@@ -134,6 +134,9 @@
const size_t testSetCount = sizeof(testSet) / sizeof(testSet[0]);
static const Cubic newTestSet[] = {
+{{0,1}, {2,5}, {6,0}, {5,3}},
+{{0,6}, {3,5}, {1,0}, {5,2}},
+
{{0,1}, {3,6}, {1,0}, {5,2}},
{{0,1}, {2,5}, {1,0}, {6,3}},
@@ -553,10 +556,10 @@
const Cubic& cubic1 = newTestSet[0];
const Cubic& cubic2 = newTestSet[1];
- double t1Seed = 0.633;
- double t2Seed = 0.633;
+ double t1Seed = 0.77;
+ double t2Seed = 0.99;
double t1Step = 0.1;
- double t2Step = 0.1;
+ double t2Step = 0.01;
_Point t1[3], t2[3];
bool toggle = true;
do {
diff --git a/experimental/Intersection/CubicUtilities.cpp b/experimental/Intersection/CubicUtilities.cpp
index 11d4e6c..b27accf 100644
--- a/experimental/Intersection/CubicUtilities.cpp
+++ b/experimental/Intersection/CubicUtilities.cpp
@@ -8,7 +8,7 @@
#include "Extrema.h"
#include "QuadraticUtilities.h"
-const int precisionUnit = 256; // FIXME: arbitrary -- should try different values in test framework
+const int gPrecisionUnit = 256; // FIXME: arbitrary -- should try different values in test framework
// FIXME: cache keep the bounds and/or precision with the caller?
double calcPrecision(const Cubic& cubic) {
@@ -16,7 +16,7 @@
dRect.setBounds(cubic); // OPTIMIZATION: just use setRawBounds ?
double width = dRect.right - dRect.left;
double height = dRect.bottom - dRect.top;
- return (width > height ? width : height) / precisionUnit;
+ return (width > height ? width : height) / gPrecisionUnit;
}
#if SK_DEBUG
@@ -236,13 +236,8 @@
}
// OPTIMIZE? compute t^2, t(1-t), and (1-t)^2 and pass them to another version of derivative at t?
-void dxdy_at_t(const Cubic& cubic, double t, _Point& dxdy) {
- dxdy.x = derivativeAtT(&cubic[0].x, t);
- dxdy.y = derivativeAtT(&cubic[0].y, t);
-}
-
-_Point dxdy_at_t(const Cubic& cubic, double t) {
- _Point result = { derivativeAtT(&cubic[0].x, t), derivativeAtT(&cubic[0].y, t) };
+_Vector dxdy_at_t(const Cubic& cubic, double t) {
+ _Vector result = { derivativeAtT(&cubic[0].x, t), derivativeAtT(&cubic[0].y, t) };
return result;
}
@@ -306,6 +301,17 @@
return topPt;
}
+// OPTIMIZE: avoid computing the unused half
+void xy_at_t(const Cubic& cubic, double t, double& x, double& y) {
+ _Point xy = xy_at_t(cubic, t);
+ if (&x) {
+ x = xy.x;
+ }
+ if (&y) {
+ y = xy.y;
+ }
+}
+
_Point xy_at_t(const Cubic& cubic, double t) {
double one_t = 1 - t;
double one_t2 = one_t * one_t;
@@ -319,13 +325,3 @@
return result;
}
-
-void xy_at_t(const Cubic& cubic, double t, double& x, double& y) {
- _Point xy = xy_at_t(cubic, t);
- if (&x) {
- x = xy.x;
- }
- if (&y) {
- y = xy.y;
- }
-}
diff --git a/experimental/Intersection/CubicUtilities.h b/experimental/Intersection/CubicUtilities.h
index 3f52a94..646fb74 100644
--- a/experimental/Intersection/CubicUtilities.h
+++ b/experimental/Intersection/CubicUtilities.h
@@ -25,8 +25,8 @@
void demote_cubic_to_quad(const Cubic& cubic, Quadratic& quad);
double dx_at_t(const Cubic& , double t);
double dy_at_t(const Cubic& , double t);
-void dxdy_at_t(const Cubic& , double t, _Point& y);
-_Point dxdy_at_t(const Cubic& cubic, double t);
+//void dxdy_at_t(const Cubic& , double t, _Point& y);
+_Vector dxdy_at_t(const Cubic& cubic, double t);
int find_cubic_inflections(const Cubic& src, double tValues[]);
bool rotate(const Cubic& cubic, int zero, int index, Cubic& rotPath);
void sub_divide(const Cubic& src, double t1, double t2, Cubic& dst);
@@ -35,6 +35,6 @@
void xy_at_t(const Cubic& , double t, double& x, double& y);
_Point xy_at_t(const Cubic& , double t);
-extern const int precisionUnit;
+extern const int gPrecisionUnit;
#endif
diff --git a/experimental/Intersection/DataTypes.cpp b/experimental/Intersection/DataTypes.cpp
index b76731c..a4a3039 100644
--- a/experimental/Intersection/DataTypes.cpp
+++ b/experimental/Intersection/DataTypes.cpp
@@ -16,6 +16,16 @@
const int UlpsEpsilon = 16;
+_Vector operator-(const _Point& a, const _Point& b) {
+ _Vector v = {a.x - b.x, a.y - b.y};
+ return v;
+}
+
+_Point operator+(const _Point& a, const _Vector& b) {
+ _Point v = {a.x + b.x, a.y + b.y};
+ return v;
+}
+
// from http://randomascii.wordpress.com/2012/02/25/comparing-floating-point-numbers-2012-edition/
union Float_t
{
diff --git a/experimental/Intersection/DataTypes.h b/experimental/Intersection/DataTypes.h
index 3009c17..4b682ff 100644
--- a/experimental/Intersection/DataTypes.h
+++ b/experimental/Intersection/DataTypes.h
@@ -200,21 +200,20 @@
}
#endif
-struct _Point {
+struct _Point;
+
+struct _Vector {
double x;
double y;
- friend _Point operator-(const _Point& a, const _Point& b) {
- _Point v = {a.x - b.x, a.y - b.y};
- return v;
- }
+ friend _Point operator+(const _Point& a, const _Vector& b);
- void operator+=(const _Point& v) {
+ void operator+=(const _Vector& v) {
x += v.x;
y += v.y;
}
- void operator-=(const _Point& v) {
+ void operator-=(const _Vector& v) {
x -= v.x;
y -= v.y;
}
@@ -229,6 +228,44 @@
y *= s;
}
+ double cross(const _Vector& a) const {
+ return x * a.y - y * a.x;
+ }
+
+ double dot(const _Vector& a) const {
+ return x * a.x + y * a.y;
+ }
+
+ double length() const {
+ return sqrt(lengthSquared());
+ }
+
+ double lengthSquared() const {
+ return x * x + y * y;
+ }
+
+ SkVector asSkVector() const {
+ SkVector v = {SkDoubleToScalar(x), SkDoubleToScalar(y)};
+ return v;
+ }
+};
+
+struct _Point {
+ double x;
+ double y;
+
+ friend _Vector operator-(const _Point& a, const _Point& b);
+
+ void operator+=(const _Vector& v) {
+ x += v.x;
+ y += v.y;
+ }
+
+ void operator-=(const _Vector& v) {
+ x -= v.x;
+ y -= v.y;
+ }
+
friend bool operator==(const _Point& a, const _Point& b) {
return a.x == b.x && a.y == b.y;
}
@@ -277,32 +314,16 @@
return pt;
}
- double cross(const _Point& a) const {
- return x * a.y - y * a.x;
- }
-
double distance(const _Point& a) const {
- _Point temp = *this - a;
+ _Vector temp = *this - a;
return temp.length();
}
double distanceSquared(const _Point& a) const {
- _Point temp = *this - a;
+ _Vector temp = *this - a;
return temp.lengthSquared();
}
- double dot(const _Point& a) const {
- return x * a.x + y * a.y;
- }
-
- double length() const {
- return sqrt(lengthSquared());
- }
-
- double lengthSquared() const {
- return x * x + y * y;
- }
-
double roughlyEqual(const _Point& a) const {
return roughly_equal(a.y, y) && roughly_equal(a.x, x);
}
diff --git a/experimental/Intersection/Intersections.h b/experimental/Intersection/Intersections.h
index 9a35a7d..fc4c26c 100644
--- a/experimental/Intersection/Intersections.h
+++ b/experimental/Intersection/Intersections.h
@@ -54,6 +54,7 @@
}
}
+ // FIXME : does not respect swap
int insert(double one, double two, const _Point& pt);
// start if index == 0 : end if index == 1
diff --git a/experimental/Intersection/LineUtilities.cpp b/experimental/Intersection/LineUtilities.cpp
index 186fa9b..53319c4 100644
--- a/experimental/Intersection/LineUtilities.cpp
+++ b/experimental/Intersection/LineUtilities.cpp
@@ -59,8 +59,8 @@
// See: the January 2001 Algorithm on Area of Triangles
// return (float) ((P1.x - P0.x)*(P2.y - P0.y) - (P2.x - P0.x)*(P1.y - P0.y));
double is_left(const _Line& line, const _Point& pt) {
- _Point P0 = line[1] - line[0];
- _Point P2 = pt - line[0];
+ _Vector P0 = line[1] - line[0];
+ _Vector P2 = pt - line[0];
return P0.cross(P2);
}
diff --git a/experimental/Intersection/QuadraticImplicit.cpp b/experimental/Intersection/QuadraticImplicit.cpp
index a13e39b..ed6244e 100644
--- a/experimental/Intersection/QuadraticImplicit.cpp
+++ b/experimental/Intersection/QuadraticImplicit.cpp
@@ -130,12 +130,9 @@
xy_at_t(q2, tMid, mid.x, mid.y);
_Line line;
line[0] = line[1] = mid;
- _Point dxdy;
- dxdy_at_t(q2, tMid, dxdy);
- line[0].x -= dxdy.x;
- line[0].y -= dxdy.y;
- line[1].x += dxdy.x;
- line[1].y += dxdy.y;
+ _Vector dxdy = dxdy_at_t(q2, tMid);
+ line[0] -= dxdy;
+ line[1] += dxdy;
Intersections rootTs;
int roots = intersect(q1, line, rootTs);
if (roots == 0) {
@@ -186,7 +183,6 @@
return true;
}
double tMin, tMax;
- _Point dxy1, dxy2;
if (tCount == 1) {
tMin = tMax = tsFound[0];
} else if (tCount > 1) {
@@ -206,11 +202,12 @@
tMax = t2e;
}
int split = 0;
+ _Vector dxy1, dxy2;
if (tMin != tMax || tCount > 2) {
- dxdy_at_t(q2, tMin, dxy2);
+ dxy2 = dxdy_at_t(q2, tMin);
for (int index = 1; index < tCount; ++index) {
dxy1 = dxy2;
- dxdy_at_t(q2, tsFound[index], dxy2);
+ dxy2 = dxdy_at_t(q2, tsFound[index]);
double dot = dxy1.dot(dxy2);
if (dot < 0) {
split = index - 1;
@@ -244,10 +241,8 @@
}
static double flatMeasure(const Quadratic& q) {
- _Point mid = q[1];
- mid -= q[0];
- _Point dxy = q[2];
- dxy -= q[0];
+ _Vector mid = q[1] - q[0];
+ _Vector dxy = q[2] - q[0];
double length = dxy.length(); // OPTIMIZE: get rid of sqrt
return fabs(mid.cross(dxy) / length);
}
diff --git a/experimental/Intersection/QuadraticIntersection_Test.cpp b/experimental/Intersection/QuadraticIntersection_Test.cpp
index e9b7d90..46cf20a 100644
--- a/experimental/Intersection/QuadraticIntersection_Test.cpp
+++ b/experimental/Intersection/QuadraticIntersection_Test.cpp
@@ -54,6 +54,9 @@
}
static const Quadratic testSet[] = {
+ {{4.09011926,2.20971038}, {4.74608133,1.9335932}, {5.02469918,2.00694987}},
+ {{2.79472921,1.73568666}, {3.36246373,1.21251209}, {5,2}},
+
{{1.80814127,2.41537795}, {2.23475077,2.05922313}, {3.16529668,1.98358763}},
{{2.16505631,2.55782454}, {2.40541285,2.02193091}, {2.99836023,1.68247638}},
@@ -319,10 +322,10 @@
const Quadratic& quad1 = testSet[test1];
const Quadratic& quad2 = testSet[test2];
- double t1Seed = 0.579;
- double t2Seed = 0.469;
+ double t1Seed = 0.966;
+ double t2Seed = 0.99;
double t1Step = 0.1;
- double t2Step = 0.1;
+ double t2Step = 0.01;
_Point t1[3], t2[3];
bool toggle = true;
do {
diff --git a/experimental/Intersection/QuadraticUtilities.cpp b/experimental/Intersection/QuadraticUtilities.cpp
index 7133e2e..cba722b 100644
--- a/experimental/Intersection/QuadraticUtilities.cpp
+++ b/experimental/Intersection/QuadraticUtilities.cpp
@@ -11,11 +11,11 @@
// from http://blog.gludion.com/2009/08/distance-to-quadratic-bezier-curve.html
double nearestT(const Quadratic& quad, const _Point& pt) {
- _Point pos = quad[0] - pt;
+ _Vector pos = quad[0] - pt;
// search points P of bezier curve with PM.(dP / dt) = 0
// a calculus leads to a 3d degree equation :
- _Point A = quad[1] - quad[0];
- _Point B = quad[2] - quad[1];
+ _Vector A = quad[1] - quad[0];
+ _Vector B = quad[2] - quad[1];
B -= A;
double a = B.dot(B);
double b = 3 * A.dot(B);
@@ -222,12 +222,13 @@
return derivativeAtT(&quad[0].y, t);
}
-void dxdy_at_t(const Quadratic& quad, double t, _Point& dxy) {
+_Vector dxdy_at_t(const Quadratic& quad, double t) {
double a = t - 1;
double b = 1 - 2 * t;
double c = t;
- dxy.x = a * quad[0].x + b * quad[1].x + c * quad[2].x;
- dxy.y = a * quad[0].y + b * quad[1].y + c * quad[2].y;
+ _Vector result = { a * quad[0].x + b * quad[1].x + c * quad[2].x,
+ a * quad[0].y + b * quad[1].y + c * quad[2].y };
+ return result;
}
void xy_at_t(const Quadratic& quad, double t, double& x, double& y) {
diff --git a/experimental/Intersection/QuadraticUtilities.h b/experimental/Intersection/QuadraticUtilities.h
index fe6bc68..8ec9037 100644
--- a/experimental/Intersection/QuadraticUtilities.h
+++ b/experimental/Intersection/QuadraticUtilities.h
@@ -14,7 +14,9 @@
void chop_at(const Quadratic& src, QuadraticPair& dst, double t);
double dx_at_t(const Quadratic& , double t);
double dy_at_t(const Quadratic& , double t);
-void dxdy_at_t(const Quadratic& , double t, _Point& xy);
+//void dxdy_at_t(const Quadratic& , double t, _Point& xy);
+_Vector dxdy_at_t(const Quadratic& , double t);
+
double nearestT(const Quadratic& , const _Point& );
bool point_in_hull(const Quadratic& , const _Point& );
diff --git a/experimental/Intersection/ShapeOps.cpp b/experimental/Intersection/ShapeOps.cpp
index bc390c7..f1792a8 100644
--- a/experimental/Intersection/ShapeOps.cpp
+++ b/experimental/Intersection/ShapeOps.cpp
@@ -168,7 +168,7 @@
Segment* next = current->findNextOp(chaseArray, nextStart, nextEnd,
unsortable, op, xorMask, xorOpMask);
if (!next) {
- SkASSERT(!unsortable);
+ // SkASSERT(!unsortable);
if (!unsortable && simple.hasMove()
&& current->verb() != SkPath::kLine_Verb
&& !simple.isClosed()) {
diff --git a/experimental/Intersection/Simplify.cpp b/experimental/Intersection/Simplify.cpp
index f4d8875..ea4c9bf 100644
--- a/experimental/Intersection/Simplify.cpp
+++ b/experimental/Intersection/Simplify.cpp
@@ -44,6 +44,7 @@
#define DEBUG_ADD_INTERSECTING_TS 0
#define DEBUG_ADD_T_PAIR 0
#define DEBUG_ANGLE 0
+#define DEBUG_AS_C_CODE 1
#define DEBUG_ASSEMBLE 0
#define DEBUG_CONCIDENT 0
#define DEBUG_CROSS 0
@@ -68,6 +69,7 @@
#define DEBUG_ADD_INTERSECTING_TS 1
#define DEBUG_ADD_T_PAIR 1
#define DEBUG_ANGLE 1
+#define DEBUG_AS_C_CODE 0
#define DEBUG_ASSEMBLE 1
#define DEBUG_CONCIDENT 1
#define DEBUG_CROSS 0
@@ -382,25 +384,23 @@
CubicDYAtT
};
-static SkPoint LineDXDYAtT(const SkPoint a[2], double ) {
+static SkVector LineDXDYAtT(const SkPoint a[2], double ) {
return a[1] - a[0];
}
-static SkPoint QuadDXDYAtT(const SkPoint a[3], double t) {
+static SkVector QuadDXDYAtT(const SkPoint a[3], double t) {
MAKE_CONST_QUAD(quad, a);
- _Point pt;
- dxdy_at_t(quad, t, pt);
- return pt.asSkPoint();
+ _Vector v = dxdy_at_t(quad, t);
+ return v.asSkVector();
}
-static SkPoint CubicDXDYAtT(const SkPoint a[4], double t) {
+static SkVector CubicDXDYAtT(const SkPoint a[4], double t) {
MAKE_CONST_CUBIC(cubic, a);
- _Point pt;
- dxdy_at_t(cubic, t, pt);
- return pt.asSkPoint();
+ _Vector v = dxdy_at_t(cubic, t);
+ return v.asSkVector();
}
-static SkPoint (* const SegmentDXDYAtT[])(const SkPoint [], double ) = {
+static SkVector (* const SegmentDXDYAtT[])(const SkPoint [], double ) = {
NULL,
LineDXDYAtT,
QuadDXDYAtT,
@@ -1646,7 +1646,7 @@
// resolve overlapping ts when considering coincidence later
// add non-coincident intersection. Resulting edges are sorted in T.
- int addT(double newT, Segment* other, const SkPoint& pt) {
+ int addT(Segment* other, const SkPoint& pt, double& newT) {
// FIXME: in the pathological case where there is a ton of intercepts,
// binary search?
int insertedAt = -1;
@@ -1692,8 +1692,11 @@
span->fUnsortableStart = false;
span->fUnsortableEnd = false;
int less = -1;
- while (&span[less + 1] - fTs.begin() > 0 && !span[less].fDone
- && xyAtT(&span[less]) == xyAtT(span)) {
+ while (&span[less + 1] - fTs.begin() > 0 && xyAtT(&span[less]) == xyAtT(span)) {
+#if 1
+ if (span[less].fDone) {
+ break;
+ }
double tInterval = newT - span[less].fT;
if (precisely_negative(tInterval)) {
break;
@@ -1719,11 +1722,34 @@
}
}
++fDoneSpans;
+#else
+ double tInterval = newT - span[less].fT;
+ if (precisely_negative(tInterval)) {
+ break;
+ }
+ if (fVerb == SkPath::kCubic_Verb) {
+ double tMid = newT - tInterval / 2;
+ _Point midPt;
+ CubicXYAtT(fPts, tMid, &midPt);
+ if (!midPt.approximatelyEqual(xyAtT(span))) {
+ break;
+ }
+ }
+ SkASSERT(span[less].fDone == span->fDone);
+ if (span[less].fT == 0) {
+ span->fT = newT = 0;
+ } else {
+ setSpanT(less, newT);
+ }
+#endif
--less;
}
int more = 1;
- while (fTs.end() - &span[more - 1] > 1 && !span[more - 1].fDone
- && xyAtT(&span[more]) == xyAtT(span)) {
+ while (fTs.end() - &span[more - 1] > 1 && xyAtT(&span[more]) == xyAtT(span)) {
+#if 1
+ if (span[more - 1].fDone) {
+ break;
+ }
double tEndInterval = span[more].fT - newT;
if (precisely_negative(tEndInterval)) {
break;
@@ -1749,6 +1775,26 @@
}
}
++fDoneSpans;
+#else
+ double tEndInterval = span[more].fT - newT;
+ if (precisely_negative(tEndInterval)) {
+ break;
+ }
+ if (fVerb == SkPath::kCubic_Verb) {
+ double tMid = newT - tEndInterval / 2;
+ _Point midEndPt;
+ CubicXYAtT(fPts, tMid, &midEndPt);
+ if (!midEndPt.approximatelyEqual(xyAtT(span))) {
+ break;
+ }
+ }
+ SkASSERT(span[more - 1].fDone == span[more].fDone);
+ if (newT == 0) {
+ setSpanT(more, 0);
+ } else {
+ span->fT = newT = span[more].fT;
+ }
+#endif
++more;
}
return insertedAt;
@@ -1836,8 +1882,8 @@
}
}
- int addUnsortableT(double newT, Segment* other, bool start, const SkPoint& pt) {
- int result = addT(newT, other, pt);
+ int addUnsortableT(Segment* other, bool start, const SkPoint& pt, double& newT) {
+ int result = addT(other, pt, newT);
Span* span = &fTs[result];
if (start) {
if (result > 0) {
@@ -1961,8 +2007,8 @@
SkDebugf("%s addTPair this=%d %1.9g other=%d %1.9g\n",
__FUNCTION__, fID, t, other.fID, otherT);
#endif
- int insertedAt = addT(t, &other, pt);
- int otherInsertedAt = other.addT(otherT, this, pt);
+ int insertedAt = addT(&other, pt, t);
+ int otherInsertedAt = other.addT(this, pt, otherT);
addOtherT(insertedAt, otherT, otherInsertedAt);
other.addOtherT(otherInsertedAt, t, insertedAt);
matchWindingValue(insertedAt, t, borrowWind);
@@ -2292,7 +2338,7 @@
return done(SkMin32(angle->start(), angle->end()));
}
- SkPoint dxdy(int index) const {
+ SkVector dxdy(int index) const {
return (*SegmentDXDYAtT[fVerb])(fPts, fTs[index].fT);
}
@@ -2859,8 +2905,8 @@
bool bumpsUp = leftSegment->bumpsUp(tIndex, endIndex);
SkPoint xyE = leftSegment->xyAtT(endIndex);
SkPoint xyS = leftSegment->xyAtT(tIndex);
- SkPoint dxyE = leftSegment->dxdy(endIndex);
- SkPoint dxyS = leftSegment->dxdy(tIndex);
+ SkVector dxyE = leftSegment->dxdy(endIndex);
+ SkVector dxyS = leftSegment->dxdy(tIndex);
double cross = dxyE.cross(dxyS);
bool bumpCheck = bumpsUp && xyE.fY < xyS.fY && dxyE.fX < 0;
#if DEBUG_SWAP_TOP
@@ -3622,6 +3668,12 @@
void setOppXor(bool isOppXor) {
fOppXor = isOppXor;
}
+
+ void setSpanT(int index, double t) {
+ Span& span = fTs[index];
+ span.fT = t;
+ span.fOther->fTs[span.fOtherIndex].fOtherT = t;
+ }
void setUpWinding(int index, int endIndex, int& maxWinding, int& sumWinding) {
int deltaSum = spanSign(index, endIndex);
@@ -4049,6 +4101,8 @@
double lastT = -1;
#endif
for (int i = 0; i < fTs.count(); ++i) {
+ SkASSERT(&fTs[i] == &fTs[i].fOther->fTs[fTs[i].fOtherIndex].fOther->
+ fTs[fTs[i].fOther->fTs[fTs[i].fOtherIndex].fOtherIndex]);
if (fTs[i].fDone) {
continue;
}
@@ -4383,14 +4437,14 @@
return fSegments.count();
}
- int addT(int segIndex, double newT, Contour* other, int otherIndex, const SkPoint& pt) {
+ int addT(int segIndex, Contour* other, int otherIndex, const SkPoint& pt, double& newT) {
setContainsIntercepts();
- return fSegments[segIndex].addT(newT, &other->fSegments[otherIndex], pt);
+ return fSegments[segIndex].addT(&other->fSegments[otherIndex], pt, newT);
}
- int addUnsortableT(int segIndex, double newT, Contour* other, int otherIndex, bool start,
- const SkPoint& pt) {
- return fSegments[segIndex].addUnsortableT(newT, &other->fSegments[otherIndex], start, pt);
+ int addUnsortableT(int segIndex, Contour* other, int otherIndex, bool start,
+ const SkPoint& pt, double& newT) {
+ return fSegments[segIndex].addUnsortableT(&other->fSegments[otherIndex], start, pt, newT);
}
const Bounds& bounds() const {
@@ -4559,7 +4613,8 @@
double endT = coincidence.fTs[0][1];
bool cancelers;
if ((cancelers = startT > endT)) {
- SkTSwap<double>(startT, endT);
+ SkTSwap(startT, endT);
+ SkTSwap(coincidence.fPts[0], coincidence.fPts[1]);
}
SkASSERT(!approximately_negative(endT - startT));
double oStartT = coincidence.fTs[1][0];
@@ -5075,12 +5130,12 @@
// be nearly equal, any problems caused by this should be taken care
// of later.
// On the edge or out of range values are negative; add 2 to get end
- int addT(double newT, const Work& other, const SkPoint& pt) {
- return fContour->addT(fIndex, newT, other.fContour, other.fIndex, pt);
+ int addT(const Work& other, const SkPoint& pt, double& newT) {
+ return fContour->addT(fIndex, other.fContour, other.fIndex, pt, newT);
}
- int addUnsortableT(double newT, const Work& other, bool start, const SkPoint& pt) {
- return fContour->addUnsortableT(fIndex, newT, other.fContour, other.fIndex, start, pt);
+ int addUnsortableT(const Work& other, bool start, const SkPoint& pt, double& newT) {
+ return fContour->addUnsortableT(fIndex, other.fContour, other.fIndex, start, pt, newT);
}
bool advance() {
@@ -5199,7 +5254,6 @@
#if DEBUG_ADD_INTERSECTING_TS
-#define DEBUG_AS_C_CODE 1
#if DEBUG_AS_C_CODE
#define CUBIC_DEBUG_STR "{{%1.17g,%1.17g}, {%1.17g,%1.17g}, {%1.17g,%1.17g}, {%1.17g,%1.17g}}"
#define QUAD_DEBUG_STR "{{%1.17g,%1.17g}, {%1.17g,%1.17g}, {%1.17g,%1.17g}}"
@@ -5586,9 +5640,9 @@
// FIXME: if unsortable, the other points to the original. This logic is
// untested downstream.
SkPoint point = ts.fPt[pt].asSkPoint();
- int testTAt = wt.addUnsortableT(ts.fT[swap][pt], wt, start, point);
+ int testTAt = wt.addUnsortableT(wt, start, point, ts.fT[swap][pt]);
wt.addOtherT(testTAt, ts.fT[swap][pt], testTAt);
- testTAt = wn.addUnsortableT(ts.fT[!swap][pt], wn, start ^ ts.fFlip, point);
+ testTAt = wn.addUnsortableT(wn, start ^ ts.fFlip, point, ts.fT[!swap][pt]);
wn.addOtherT(testTAt, ts.fT[!swap][pt], testTAt);
start ^= true;
}
@@ -5613,8 +5667,8 @@
SkASSERT(ts.fT[0][pt] >= 0 && ts.fT[0][pt] <= 1);
SkASSERT(ts.fT[1][pt] >= 0 && ts.fT[1][pt] <= 1);
SkPoint point = ts.fPt[pt].asSkPoint();
- int testTAt = wt.addT(ts.fT[swap][pt], wn, point);
- int nextTAt = wn.addT(ts.fT[!swap][pt], wt, point);
+ int testTAt = wt.addT(wn, point, ts.fT[swap][pt]);
+ int nextTAt = wn.addT(wt, point, ts.fT[!swap][pt]);
wt.addOtherT(testTAt, ts.fT[!swap][pt ^ ts.fFlip], nextTAt);
wn.addOtherT(nextTAt, ts.fT[swap][pt ^ ts.fFlip], testTAt);
}
@@ -5640,8 +5694,8 @@
SkASSERT(ts.fT[0][0] >= 0 && ts.fT[0][0] <= 1);
SkASSERT(ts.fT[1][0] >= 0 && ts.fT[1][0] <= 1);
SkPoint point = ts.fPt[0].asSkPoint();
- int testTAt = wt.addT(ts.fT[0][0], wt, point);
- int nextTAt = wt.addT(ts.fT[1][0], wt, point);
+ int testTAt = wt.addT(wt, point, ts.fT[0][0]);
+ int nextTAt = wt.addT(wt, point, ts.fT[1][0]);
wt.addOtherT(testTAt, ts.fT[1][0], nextTAt);
wt.addOtherT(nextTAt, ts.fT[0][0], testTAt);
} while (wt.advance());
diff --git a/experimental/Intersection/SimplifyNew_Test.cpp b/experimental/Intersection/SimplifyNew_Test.cpp
index 0d49bb9..ffba8dc 100644
--- a/experimental/Intersection/SimplifyNew_Test.cpp
+++ b/experimental/Intersection/SimplifyNew_Test.cpp
@@ -4138,12 +4138,52 @@
testShapeOp(path, pathB, kDifference_Op);
}
-static void (*firstTest)() = cubicOp30d;
+static void cubicOp31d() {
+ SkPath path, pathB;
+ path.setFillType(SkPath::kWinding_FillType);
+ path.moveTo(0,2);
+ path.cubicTo(0,3, 2,1, 4,0);
+ path.close();
+ pathB.setFillType(SkPath::kWinding_FillType);
+ pathB.moveTo(1,2);
+ pathB.cubicTo(0,4, 2,0, 3,0);
+ pathB.close();
+ testShapeOp(path, pathB, kDifference_Op);
+}
+
+static void cubicOp31u() {
+ SkPath path, pathB;
+ path.setFillType(SkPath::kWinding_FillType);
+ path.moveTo(0,2);
+ path.cubicTo(0,3, 2,1, 4,0);
+ path.close();
+ pathB.setFillType(SkPath::kWinding_FillType);
+ pathB.moveTo(1,2);
+ pathB.cubicTo(0,4, 2,0, 3,0);
+ pathB.close();
+ testShapeOp(path, pathB, kUnion_Op);
+}
+
+static void testCubic2() {
+ SkPath path;
+ path.moveTo(0,2);
+ path.cubicTo(0,3, 2,1, 4,0);
+ path.close();
+ path.moveTo(1,2);
+ path.cubicTo(0,4, 2,0, 3,0);
+ path.close();
+ testSimplifyx(path);
+}
+
+static void (*firstTest)() = 0;
static struct {
void (*fun)();
const char* str;
} tests[] = {
+ TEST(testCubic2),
+ TEST(cubicOp31u),
+ TEST(cubicOp31d),
TEST(cubicOp30d),
TEST(cubicOp29d),
TEST(cubicOp28u),
@@ -4551,7 +4591,7 @@
static bool skipAll = false;
static bool runSubTestsFirst = false;
-static bool runReverse = true;
+static bool runReverse = false;
static void (*stopTest)() = 0;
void SimplifyNew_Test() {
diff --git a/experimental/Intersection/TriangleUtilities.cpp b/experimental/Intersection/TriangleUtilities.cpp
index 38915d4..9889368 100644
--- a/experimental/Intersection/TriangleUtilities.cpp
+++ b/experimental/Intersection/TriangleUtilities.cpp
@@ -10,9 +10,9 @@
// http://www.blackpawn.com/texts/pointinpoly/default.html
bool pointInTriangle(const Triangle& triangle, const _Point& pt) {
// Compute vectors
- _Point v0 = triangle[2] - triangle[0];
- _Point v1 = triangle[1] - triangle[0];
- _Point v2 = pt - triangle[0];
+ _Vector v0 = triangle[2] - triangle[0];
+ _Vector v1 = triangle[1] - triangle[0];
+ _Vector v2 = pt - triangle[0];
// Compute dot products
double dot00 = v0.dot(v0);
diff --git a/experimental/Intersection/as.htm b/experimental/Intersection/as.htm
index b548766..93845cb 100644
--- a/experimental/Intersection/as.htm
+++ b/experimental/Intersection/as.htm
@@ -40,11 +40,33 @@
debugShowActiveSpans id=2 (3,2 0,1) t=0.400657994 (1.79802597,1.59934199) tEnd=1 other=3 otherT=0.57224743 otherIndex=2 windSum=? windValue=1 oppValue=0
</div>
+<div id="cubicOp31d">
+debugShowActiveSpans id=1 (0,2 0,3 2,1 4,0) t=0 (0,2) tEnd=0.5 other=2 otherT=1 otherIndex=3 windSum=1 windValue=1 oppValue=0
+debugShowActiveSpans id=1 (0,2 0,3 2,1 4,0) t=0.5 (1.25,1.75) tEnd=1 other=4 otherT=0.875 otherIndex=2 windSum=1 windValue=1 oppValue=0
+debugShowActiveSpans id=2 (4,0 0,2) t=0 (4,0) tEnd=0.5 other=1 otherT=1 otherIndex=3 windSum=1 windValue=1 oppValue=0
+debugShowActiveSpans id=2 (4,0 0,2) t=0.586298186 (1.65480721,1.17259634) tEnd=1 other=3 otherT=0.622399169 otherIndex=3 windSum=1 windValue=1 oppValue=0
+debugShowActiveSpans id=3 (1,2 0,4 2,0 3,0) t=0 (1,2) tEnd=0.5 other=4 otherT=1 otherIndex=4 windSum=? windValue=1 oppValue=0
+debugShowActiveSpans id=3 (1,2 0,4 2,0 3,0) t=0.500000008 (1.25,1.75) tEnd=0.622399169 other=1 otherT=0.5 otherIndex=1 windSum=-1 windValue=1 oppValue=0
+debugShowActiveSpans id=4 (3,0 1,2) t=0.5 (2,1) tEnd=0.875 other=2 otherT=0.5 otherIndex=1 windSum=-1 windValue=1 oppValue=0
+debugShowActiveSpans id=4 (3,0 1,2) t=0.875 (1.25,1.75) tEnd=1 other=1 otherT=0.5 otherIndex=2 windSum=? windValue=1 oppValue=0
+</div>
+
+<div id="cubicOp31da">
+debugShowActiveSpans id=1 (0,2 0,3 2,1 4,0) t=0 (0,2) tEnd=0.5 other=2 otherT=1 otherIndex=3 windSum=1 windValue=1 oppValue=0
+debugShowActiveSpans id=1 (0,2 0,3 2,1 4,0) t=0.5 (1.25,1.75) tEnd=1 other=4 otherT=0.875 otherIndex=2 windSum=1 windValue=1 oppValue=0
+debugShowActiveSpans id=3 (1,2 0,4 2,0 3,0) t=0 (1,2) tEnd=0.5 other=4 otherT=1 otherIndex=4 windSum=? windValue=1 oppValue=0
+debugShowActiveSpans id=3 (1,2 0,4 2,0 3,0) t=0.500000008 (1.25,1.75) tEnd=0.622399169 other=1 otherT=0.5 otherIndex=1 windSum=-1 windValue=1 oppValue=0
+debugShowActiveSpans id=4 (3,0 1,2) t=0.5 (2,1) tEnd=0.875 other=2 otherT=0.5 otherIndex=1 windSum=-1 windValue=1 oppValue=0
+debugShowActiveSpans id=4 (3,0 1,2) t=0.875 (1.25,1.75) tEnd=1 other=1 otherT=0.5 otherIndex=2 windSum=? windValue=1 oppValue=0
+</div>
+
</div>
<script type="text/javascript">
var testDivs = [
+ cubicOp31da,
+ cubicOp31d,
cubicOp28u,
cubicOp25i,
cubicOp19i,
diff --git a/experimental/Intersection/op.htm b/experimental/Intersection/op.htm
index 466551b..199a9df 100644
--- a/experimental/Intersection/op.htm
+++ b/experimental/Intersection/op.htm
@@ -3710,11 +3710,23 @@
pathB.close();
</div>
+<div id="cubicOp31d">
+ path.setFillType(SkPath::kWinding_FillType);
+ path.moveTo(0,2);
+ path.cubicTo(0,3, 2,1, 4,0);
+ path.close();
+ pathB.setFillType(SkPath::kWinding_FillType);
+ pathB.moveTo(1,2);
+ pathB.cubicTo(0,4, 2,0, 3,0);
+ pathB.close();
+</div>
+
</div>
<script type="text/javascript">
var testDivs = [
+ cubicOp31d,
cubicOp30d,
cubicOp29d,
cubicOp28u,
diff --git a/experimental/Intersection/qc.htm b/experimental/Intersection/qc.htm
index 1d9cfa5..db77fa4 100644
--- a/experimental/Intersection/qc.htm
+++ b/experimental/Intersection/qc.htm
@@ -2065,11 +2065,34 @@
{{2.16505631,2.55782454}, {2.40541285,2.02193091}, {2.99836023,1.68247638}},
</div>
+<div id="cubicOp30d">
+{{0,1}, {2,5}, {6,0}, {5,3}},
+{{0,6}, {3,5}, {1,0}, {5,2}},
+
+ {{0,1}, {0.585028897,2.1161006}, {1.31572211,2.42528354}},
+ {{1.31572211,2.42528354}, {2.04641532,2.73446648}, {2.77656625,2.5918049}},
+ {{2.77656625,2.5918049}, {3.50671719,2.44914333}, {4.09011926,2.20971038}},
+ {{4.09011926,2.20971038}, {4.74608133,1.9335932}, {5.02469918,2.00694987}},
+ {{5.02469918,2.00694987}, {5.30331702,2.08030653}, {5,3}},
+
+ {{0,6}, {0.946962644,5.64705935}, {1.35765232,4.89865813}},
+ {{1.35765232,4.89865813}, {1.768342,4.1502569}, {1.97833659,3.34197296}},
+ {{1.97833659,3.34197296}, {2.2269947,2.25886123}, {2.79472921,1.73568666}},
+ {{2.79472921,1.73568666}, {3.36246373,1.21251209}, {5,2}},
+</div>
+
+<div id="quadOp30d">
+ {{4.09011926,2.20971038}, {4.74608133,1.9335932}, {5.02469918,2.00694987}},
+ {{2.79472921,1.73568666}, {3.36246373,1.21251209}, {5,2}},
+</div>
+
</div>
<script type="text/javascript">
var testDivs = [
+ quadOp30d,
+ cubicOp30d,
quadOp27d,
cubicOp27d,
quadSelf1,
@@ -2345,6 +2368,7 @@
var drawQuads = true;
var drawControlLines = true;
var drawTangents = false;
+var drawGrid = true;
var xmin, xmax, ymin, ymax;
function parse(test, title) {
@@ -2448,35 +2472,38 @@
var unit = scale * ticks;
ctx.lineWidth = 1;
- var i;
- for (i = 0; i <= rows * ticks; ++i) {
- ctx.strokeStyle = (i % ticks) != 0 ? "rgb(200,200,200)" : "black";
- ctx.beginPath();
- ctx.moveTo(at_x + 0, at_y + i * minScale);
- ctx.lineTo(at_x + ticks * columns * minScale, at_y + i * minScale);
- ctx.stroke();
+ if (drawGrid) {
+ var i;
+ for (i = 0; i <= rows * ticks; ++i) {
+ ctx.strokeStyle = (i % ticks) != 0 ? "rgb(200,200,200)" : "black";
+ ctx.beginPath();
+ ctx.moveTo(at_x + 0, at_y + i * minScale);
+ ctx.lineTo(at_x + ticks * columns * minScale, at_y + i * minScale);
+ ctx.stroke();
+ }
+ for (i = 0; i <= columns * ticks; ++i) {
+ ctx.strokeStyle = (i % ticks) != 0 ? "rgb(200,200,200)" : "black";
+ ctx.beginPath();
+ ctx.moveTo(at_x + i * minScale, at_y + 0);
+ ctx.lineTo(at_x + i * minScale, at_y + ticks * rows * minScale);
+ ctx.stroke();
+ }
}
- for (i = 0; i <= columns * ticks; ++i) {
- ctx.strokeStyle = (i % ticks) != 0 ? "rgb(200,200,200)" : "black";
- ctx.beginPath();
- ctx.moveTo(at_x + i * minScale, at_y + 0);
- ctx.lineTo(at_x + i * minScale, at_y + ticks * rows * minScale);
- ctx.stroke();
- }
-
var xoffset = xStart * -unit + at_x;
var yoffset = yStart * -unit + at_y;
- ctx.fillStyle = "rgb(40,80,60)"
- for (i = 0; i <= columns; i += 1)
- {
- num = xStart + i / subscale;
- ctx.fillText(num.toFixed(decimal_places), xoffset + num * unit - 5, 10);
- }
- for (i = 0; i <= rows; i += 1)
- {
- num = yStart + i / subscale;
- ctx.fillText(num.toFixed(decimal_places), 0, yoffset + num * unit + 0);
+ ctx.fillStyle = "rgb(40,80,60)"
+ if (drawGrid) {
+ for (i = 0; i <= columns; i += 1)
+ {
+ num = xStart + i / subscale;
+ ctx.fillText(num.toFixed(decimal_places), xoffset + num * unit - 5, 10);
+ }
+ for (i = 0; i <= rows; i += 1)
+ {
+ num = yStart + i / subscale;
+ ctx.fillText(num.toFixed(decimal_places), 0, yoffset + num * unit + 0);
+ }
}
var curves, pts;
for (curves in test) {
@@ -2609,6 +2636,10 @@
}
redraw();
break;
+ case 'g':
+ drawGrid ^= true;
+ redraw();
+ break;
case 'l':
drawControlLines ^= true;
redraw();