shape ops work in progress
git-svn-id: http://skia.googlecode.com/svn/trunk@7898 2bbb7eff-a529-9590-31e7-b0007b416f81
diff --git a/experimental/Intersection/CubicIntersection.cpp b/experimental/Intersection/CubicIntersection.cpp
index 0a82866..f7b66d5 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.772784538, 0.77278492}, {0.999111748, 0.999112129}};
+static const double tLimits[2][2] = {{0.134, 0.145}, {0.134, 0.136}};
#endif
#define DEBUG_QUAD_PART 0
@@ -66,217 +66,6 @@
}
}
-static double distanceFromEnd(double t) {
- return t > 0.5 ? 1 - t : t;
-}
-
-// OPTIMIZATION: this used to try to guess the value for delta, and that may still be worthwhile
-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 / gPrecisionUnit;
- if (dt1 < dt2) {
- if (t1 == dt1) {
- s1 = SkTMax(s1 - delta, 0.);
- } else {
- e1 = SkTMin(e1 + delta, 1.);
- }
- } else {
- if (t2 == dt2) {
- s2 = SkTMax(s2 - delta, 0.);
- } else {
- e2 = SkTMin(e2 + delta, 1.);
- }
- }
-}
-
-static bool doIntersect(const Cubic& cubic1, double t1s, double t1m, double t1e,
- const Cubic& cubic2, double t2s, double t2m, double t2e, Intersections& i) {
- bool result = false;
- i.upDepth();
- // divide the quadratics at the new t value and try again
- double p1s = t1s;
- double p1e = t1m;
- for (int p1 = 0; p1 < 2; ++p1) {
- Quadratic s1a;
- int o1a = quadPart(cubic1, p1s, p1e, s1a);
- double p2s = t2s;
- double p2e = t2m;
- for (int p2 = 0; p2 < 2; ++p2) {
- Quadratic s2a;
- int o2a = quadPart(cubic2, p2s, p2e, s2a);
- Intersections locals;
- #if ONE_OFF_DEBUG
- if (tLimits[0][0] >= p1s && tLimits[0][1] <= p1e
- && tLimits[1][0] >= p2s && tLimits[1][1] <= p2e) {
- SkDebugf("t1=(%1.9g,%1.9g) o1=%d t2=(%1.9g,%1.9g) o2=%d\n",
- p1s, p1e, o1a, p2s, p2e, o2a);
- if (o1a == 2) {
- SkDebugf("{{%1.9g,%1.9g}, {%1.9g,%1.9g}},\n",
- s1a[0].x, s1a[0].y, s1a[1].x, s1a[1].y);
- } else {
- SkDebugf("{{%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}},\n",
- s1a[0].x, s1a[0].y, s1a[1].x, s1a[1].y, s1a[2].x, s1a[2].y);
- }
- if (o2a == 2) {
- SkDebugf("{{%1.9g,%1.9g}, {%1.9g,%1.9g}},\n",
- s2a[0].x, s2a[0].y, s2a[1].x, s2a[1].y);
- } else {
- SkDebugf("{{%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}},\n",
- s2a[0].x, s2a[0].y, s2a[1].x, s2a[1].y, s2a[2].x, s2a[2].y);
- }
- Intersections xlocals;
- intersectWithOrder(s1a, o1a, s2a, o2a, xlocals);
- SkDebugf("xlocals.fUsed=%d depth=%d\n", xlocals.used(), i.depth());
- }
- #endif
- intersectWithOrder(s1a, o1a, s2a, o2a, locals);
- for (int tIdx = 0; tIdx < locals.used(); ++tIdx) {
- double to1 = p1s + (p1e - p1s) * locals.fT[0][tIdx];
- double to2 = p2s + (p2e - p2s) * locals.fT[1][tIdx];
- // if the computed t is not sufficiently precise, iterate
- _Point p1, p2;
- xy_at_t(cubic1, to1, p1.x, p1.y);
- xy_at_t(cubic2, to2, p2.x, p2.y);
- #if ONE_OFF_DEBUG
- SkDebugf("to1=%1.9g p1=(%1.9g,%1.9g) to2=%1.9g p2=(%1.9g,%1.9g) d=%1.9g\n",
- to1, p1.x, p1.y, to2, p2.x, p2.y, p1.distance(p2));
-
- #endif
- if (p1.approximatelyEqualHalf(p2)) {
- i.insertSwap(to1, to2, p1);
- result = true;
- } else {
- result = doIntersect(cubic1, p1s, to1, p1e, cubic2, p2s, to2, p2e, i);
- if (!result && p1.approximatelyEqual(p2)) {
- i.insertSwap(to1, to2, p1);
- #if SWAP_TOP_DEBUG
- SkDebugf("!!!\n");
- #endif
- result = true;
- } else
- // if both cubics curve in the same direction, the quadratic intersection
- // may mark a range that does not contain the cubic intersection. If no
- // intersection is found, look again including the t distance of the
- // of the quadratic intersection nearest a quadratic end (which in turn is
- // nearest the actual cubic)
- if (!result) {
- double b1s = p1s;
- double b1e = p1e;
- double b2s = p2s;
- double b2e = p2e;
- bumpForRetry(locals.fT[0][tIdx], locals.fT[1][tIdx], b1s, b1e, b2s, b2e);
- result = doIntersect(cubic1, b1s, to1, b1e, cubic2, b2s, to2, b2e, i);
- }
- }
- }
- p2s = p2e;
- p2e = t2e;
- }
- p1s = p1e;
- p1e = t1e;
- }
- i.downDepth();
- return result;
-}
-
-// this flavor approximates the cubics with quads to find the intersecting ts
-// OPTIMIZE: if this strategy proves successful, the quad approximations, or the ts used
-// to create the approximations, could be stored in the cubic segment
-// FIXME: this strategy needs to intersect the convex hull on either end with the opposite to
-// account for inset quadratics that cause the endpoint intersection to avoid detection
-// the segments can be very short -- the length of the maximum quadratic error (precision)
-static bool intersect2(const Cubic& cubic1, double t1s, double t1e, const Cubic& cubic2,
- double t2s, double t2e, double precisionScale, Intersections& i) {
- Cubic c1, c2;
- sub_divide(cubic1, t1s, t1e, c1);
- sub_divide(cubic2, t2s, t2e, c2);
- SkTDArray<double> ts1;
- cubic_to_quadratics(c1, calcPrecision(c1) * precisionScale, ts1);
- SkTDArray<double> ts2;
- cubic_to_quadratics(c2, calcPrecision(c2) * precisionScale, ts2);
- double t1Start = t1s;
- int ts1Count = ts1.count();
- for (int i1 = 0; i1 <= ts1Count; ++i1) {
- const double tEnd1 = i1 < ts1Count ? ts1[i1] : 1;
- const double t1 = t1s + (t1e - t1s) * tEnd1;
- Quadratic s1;
- int o1 = quadPart(cubic1, t1Start, t1, s1);
- double t2Start = t2s;
- int ts2Count = ts2.count();
- for (int i2 = 0; i2 <= ts2Count; ++i2) {
- const double tEnd2 = i2 < ts2Count ? ts2[i2] : 1;
- const double t2 = t2s + (t2e - t2s) * tEnd2;
- Quadratic s2;
- int o2 = quadPart(cubic2, t2Start, t2, s2);
- #if ONE_OFF_DEBUG
- if (tLimits[0][0] >= t1Start && tLimits[0][1] <= t1
- && tLimits[1][0] >= t2Start && tLimits[1][1] <= t2) {
- Cubic cSub1, cSub2;
- sub_divide(cubic1, t1Start, tEnd1, cSub1);
- sub_divide(cubic2, t2Start, tEnd2, cSub2);
- SkDebugf("t1=(%1.9g,%1.9g) t2=(%1.9g,%1.9g)\n",
- t1Start, t1, t2Start, t2);
- Intersections xlocals;
- intersectWithOrder(s1, o1, s2, o2, xlocals);
- SkDebugf("xlocals.fUsed=%d\n", xlocals.used());
- }
- #endif
- Intersections locals;
- intersectWithOrder(s1, o1, s2, o2, locals);
-
- for (int tIdx = 0; tIdx < locals.used(); ++tIdx) {
- double to1 = t1Start + (t1 - t1Start) * locals.fT[0][tIdx];
- double to2 = t2Start + (t2 - t2Start) * locals.fT[1][tIdx];
- // if the computed t is not sufficiently precise, iterate
- _Point p1, p2;
- xy_at_t(cubic1, to1, p1.x, p1.y);
- xy_at_t(cubic2, to2, p2.x, p2.y);
- if (p1.approximatelyEqual(p2)) {
- i.insert(to1, to2, p1);
- } else {
- #if ONE_OFF_DEBUG
- if (tLimits[0][0] >= t1Start && tLimits[0][1] <= t1
- && tLimits[1][0] >= t2Start && tLimits[1][1] <= t2) {
- SkDebugf("t1=(%1.9g,%1.9g) t2=(%1.9g,%1.9g)\n",
- t1Start, t1, t2Start, t2);
- }
- #endif
- bool found = doIntersect(cubic1, t1Start, to1, t1, cubic2, t2Start, to2, t2, i);
- if (!found) {
- double b1s = t1Start;
- double b1e = t1;
- double b2s = t2Start;
- double b2e = t2;
- bumpForRetry(locals.fT[0][tIdx], locals.fT[1][tIdx], b1s, b1e, b2s, b2e);
- doIntersect(cubic1, b1s, to1, b1e, cubic2, b2s, to2, b2e, i);
- }
- }
- }
- int coincidentCount = locals.coincidentUsed();
- if (coincidentCount) {
- // FIXME: one day, we'll probably need to allow coincident + non-coincident pts
- SkASSERT(coincidentCount == locals.used());
- SkASSERT(coincidentCount == 2);
- double coTs[2][2];
- for (int tIdx = 0; tIdx < coincidentCount; ++tIdx) {
- if (locals.fIsCoincident[0] & (1 << tIdx)) {
- coTs[0][tIdx] = t1Start + (t1 - t1Start) * locals.fT[0][tIdx];
- }
- if (locals.fIsCoincident[1] & (1 << tIdx)) {
- coTs[1][tIdx] = t2Start + (t2 - t2Start) * locals.fT[1][tIdx];
- }
- }
- i.insertCoincidentPair(coTs[0][0], coTs[0][1], coTs[1][0], coTs[1][1],
- locals.fPt[0], locals.fPt[1]);
- }
- t2Start = t2;
- }
- t1Start = t1;
- }
- return i.intersected();
-}
-
// 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,
@@ -325,7 +114,8 @@
intersectWithOrder(s1, o1, s2, o2, locals);
double coStart[2] = { -1 };
_Point coPoint;
- for (int tIdx = 0; tIdx < locals.used(); ++tIdx) {
+ int tCount = locals.used();
+ for (int tIdx = 0; tIdx < tCount; ++tIdx) {
double to1 = t1Start + (t1 - t1Start) * locals.fT[0][tIdx];
double to2 = t2Start + (t2 - t2Start) * locals.fT[1][tIdx];
// if the computed t is not sufficiently precise, iterate
@@ -353,39 +143,32 @@
}
} else {
double offset = precisionScale / 16; // FIME: const is arbitrary -- test & refine
- double c1Min = SkTMax(0., to1 - offset);
- double c1Max = SkTMin(1., to1 + offset);
- double c2Min = SkTMax(0., to2 - offset);
- double c2Max = SkTMin(1., to2 + offset);
- bool found = intersect3(cubic1, c1Min, c1Max, cubic2, c2Min, c2Max, offset, i);
- if (false && !found) {
- // either offset was overagressive or cubics didn't really intersect
- // if they didn't intersect, then quad tangents ought to be nearly parallel
- offset = precisionScale / 2; // try much less agressive offset
- c1Min = SkTMax(0., to1 - offset);
- c1Max = SkTMin(1., to1 + offset);
- c2Min = SkTMax(0., to2 - offset);
- c2Max = SkTMin(1., to2 + offset);
- found = intersect3(cubic1, c1Min, c1Max, cubic2, c2Min, c2Max, offset, i);
- if (found) {
- SkDebugf("%s *** over-aggressive? offset=%1.9g depth=%d\n", __FUNCTION__,
- offset, i.depth());
- }
- // try parallel measure
- _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)) {
- SkDebugf("%s *** near-miss? shallow=%1.9g depth=%d\n", __FUNCTION__,
- offset, i.depth());
- }
- #endif
- if (i.depth() == 1 && shallow < 0.6) {
- SkDebugf("%s !!! near-miss? shallow=%1.9g depth=%d\n", __FUNCTION__,
- offset, i.depth());
- }
+ double c1Bottom = tIdx == 0 ? 0 :
+ (t1Start + (t1 - t1Start) * locals.fT[0][tIdx - 1] + to1) / 2;
+ double c1Min = SkTMax(c1Bottom, to1 - offset);
+ double c1Top = tIdx == tCount - 1 ? 1 :
+ (t1Start + (t1 - t1Start) * locals.fT[0][tIdx + 1] + to1) / 2;
+ double c1Max = SkTMin(c1Top, to1 + offset);
+ double c2Bottom = tIdx == 0 ? to2 :
+ (t2Start + (t2 - t2Start) * locals.fT[1][tIdx - 1] + to2) / 2;
+ double c2Top = tIdx == tCount - 1 ? to2 :
+ (t2Start + (t2 - t2Start) * locals.fT[1][tIdx + 1] + to2) / 2;
+ if (c2Bottom > c2Top) {
+ SkTSwap(c2Bottom, c2Top);
}
+ if (c2Bottom == to2) {
+ c2Bottom = 0;
+ }
+ if (c2Top == to2) {
+ c2Top = 1;
+ }
+ double c2Min = SkTMax(c2Bottom, to2 - offset);
+ double c2Max = SkTMin(c2Top, to2 + offset);
+ intersect3(cubic1, c1Min, c1Max, cubic2, c2Min, c2Max, offset, i);
+ // TODO: if no intersection is found, either quadratics intersected where
+ // cubics did not, or the intersection was missed. In the former case, expect
+ // the quadratics to be nearly parallel at the point of intersection, and check
+ // for that.
}
}
SkASSERT(coStart[0] == -1);
@@ -440,25 +223,6 @@
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
-// quadratic curve fitting.
-bool intersect2(const Cubic& c1, const Cubic& c2, Intersections& i) {
- bool result = intersect2(c1, 0, 1, c2, 0, 1, 1, i);
- // FIXME: pass in cached bounds from caller
- _Rect c1Bounds, c2Bounds;
- c1Bounds.setBounds(c1); // OPTIMIZE use setRawBounds ?
- c2Bounds.setBounds(c2);
- result |= intersectEnd(c1, false, c2, c2Bounds, i);
- result |= intersectEnd(c1, true, c2, c2Bounds, i);
- i.swap();
- result |= intersectEnd(c2, false, c1, c1Bounds, i);
- result |= intersectEnd(c2, true, c1, c1Bounds, i);
- i.swap();
- return result;
-}
-
const double CLOSE_ENOUGH = 0.001;
static bool closeStart(const Cubic& cubic, int cubicIndex, Intersections& i, _Point& pt) {
diff --git a/experimental/Intersection/CubicIntersection_Test.cpp b/experimental/Intersection/CubicIntersection_Test.cpp
index 358afcf..20c7671 100644
--- a/experimental/Intersection/CubicIntersection_Test.cpp
+++ b/experimental/Intersection/CubicIntersection_Test.cpp
@@ -134,7 +134,10 @@
const size_t testSetCount = sizeof(testSet) / sizeof(testSet[0]);
static const Cubic newTestSet[] = {
-{{0,1}, {2,5}, {6,0}, {5,3}},
+{{0,1}, {3,5}, {2,1}, {3,1}},
+{{1,2}, {1,3}, {1,0}, {5,3}},
+
+{{0,1}, {2,5}, {6,0}, {5,3}},
{{0,6}, {3,5}, {1,0}, {5,2}},
{{0,1}, {3,6}, {1,0}, {5,2}},
@@ -152,6 +155,7 @@
const size_t newTestSetCount = sizeof(newTestSet) / sizeof(newTestSet[0]);
+#if 0
static void oneOff(const Cubic& cubic1, const Cubic& cubic2) {
SkTDArray<Quadratic> quads1;
cubic_to_quadratics(cubic1, calcPrecision(cubic1), quads1);
@@ -224,7 +228,7 @@
tt2 = intersections3.fT[1][pt2];
xy_at_t(cubic2, tt2, xy2.x, xy2.y);
#if ONE_OFF_DEBUG
- SkDebugf("%s t3=%1.9g (%1.9g, %1.9g) (%1.9g, %1.9g) (%1.9g, %1.9g) t2=%1.9g\n",
+ SkDebugf("%s t1=%1.9g (%1.9g, %1.9g) (%1.9g, %1.9g) (%1.9g, %1.9g) t2=%1.9g\n",
__FUNCTION__, tt1, xy1.x, xy1.y, intersections3.fPt[pt1].x,
intersections3.fPt[pt1].y, xy2.x, xy2.y, tt2);
#endif
@@ -233,6 +237,7 @@
}
}
}
+#endif
static void oneOff3(const Cubic& cubic1, const Cubic& cubic2) {
SkTDArray<Quadratic> quads1;
@@ -270,7 +275,7 @@
tt2 = intersections3.fT[1][pt2];
xy_at_t(cubic2, tt2, xy2.x, xy2.y);
#if ONE_OFF_DEBUG
- SkDebugf("%s t3=%1.9g (%1.9g, %1.9g) (%1.9g, %1.9g) (%1.9g, %1.9g) t2=%1.9g\n",
+ SkDebugf("%s t1=%1.9g (%1.9g, %1.9g) (%1.9g, %1.9g) (%1.9g, %1.9g) t2=%1.9g\n",
__FUNCTION__, tt1, xy1.x, xy1.y, intersections3.fPt[pt3].x,
intersections3.fPt[pt3].y, xy2.x, xy2.y, tt2);
#endif
@@ -278,6 +283,7 @@
}
}
+#if 0
static int fails[][2] = { {0, 23}, // fails in intersect2 recursing
{2, 7}, // answers differ, but neither is correct ('3' is closer)
{3, 26}, // fails in intersect2 recursing
@@ -293,10 +299,12 @@
};
static int failCount = sizeof(fails) / sizeof(fails[0]);
+#endif
static void oneOff(int outer, int inner) {
const Cubic& cubic1 = testSet[outer];
const Cubic& cubic2 = testSet[inner];
+#if 0
bool failing = false;
for (int i = 0; i < failCount; ++i) {
if ((fails[i][0] == outer && fails[i][1] == inner)
@@ -308,8 +316,9 @@
if (!failing) {
oneOff(cubic1, cubic2);
} else {
+#endif
oneOff3(cubic1, cubic2);
- }
+// }
}
void CubicIntersection_OneOffTest() {
@@ -324,6 +333,7 @@
void CubicIntersection_NewOneOffTest() {
newOneOff(0, 1);
+ newOneOff(1, 0);
}
static void oneOffTests() {
@@ -356,7 +366,7 @@
sub_divide(cubic1, minT1, maxT1, sub1);
sub_divide(cubic2, minT2, maxT2, sub2);
Intersections i;
- intersect2(sub1, sub2, i);
+ intersect3(sub1, sub2, i);
if (i.used() == 0) {
return false;
}
@@ -433,7 +443,7 @@
if (test == -1) {
SkDebugf("ready...\n");
}
- bool newIntersects = intersect2(cubic1, cubic2, i2);
+ bool newIntersects = intersect3(cubic1, cubic2, i2);
if (!boundsIntersect && (oldIntersects || newIntersects)) {
#if DEBUG_CRASH
SkDebugf("%s %d unexpected intersection boundsIntersect=%d oldIntersects=%d"
@@ -484,7 +494,7 @@
#if DEBUG_CRASH
SkDebugf("%s\n", str);
#endif
- oneOff(cubic1, cubic2);
+ oneOff3(cubic1, cubic2);
largestFactor = factor1;
}
if (factor2 < largestFactor) {
@@ -492,7 +502,7 @@
#if DEBUG_CRASH
SkDebugf("%s\n", str);
#endif
- oneOff(cubic1, cubic2);
+ oneOff3(cubic1, cubic2);
largestFactor = factor2;
}
}
@@ -527,7 +537,7 @@
SkDebugf("ready...\n");
}
Intersections intersections2;
- bool newIntersects = intersect2(cubic1, cubic2, intersections2);
+ bool newIntersects = intersect3(cubic1, cubic2, intersections2);
if (!boundsIntersect && newIntersects) {
#if DEBUG_CRASH
SkDebugf("%s %d unexpected intersection boundsIntersect=%d "
@@ -556,10 +566,10 @@
const Cubic& cubic1 = newTestSet[0];
const Cubic& cubic2 = newTestSet[1];
- double t1Seed = 0.77;
- double t2Seed = 0.99;
+ double t1Seed = 0.134792061;
+ double t2Seed = 0.134792094;
double t1Step = 0.1;
- double t2Step = 0.01;
+ double t2Step = 0.1;
_Point t1[3], t2[3];
bool toggle = true;
do {
diff --git a/experimental/Intersection/CubicUtilities.cpp b/experimental/Intersection/CubicUtilities.cpp
index 1de2ef7..56f1e45 100644
--- a/experimental/Intersection/CubicUtilities.cpp
+++ b/experimental/Intersection/CubicUtilities.cpp
@@ -113,7 +113,7 @@
bzero(str, sizeof(str));
sprintf(str, "Solve[%1.19g x^3 + %1.19g x^2 + %1.19g x + %1.19g == 0, x]", A, B, C, D);
mathematica_ize(str, sizeof(str));
-#if ONE_OFF_DEBUG
+#if ONE_OFF_DEBUG && ONE_OFF_DEBUG_MATHEMATICA
SkDebugf("%s\n", str);
#endif
#endif
diff --git a/experimental/Intersection/CurveIntersection.h b/experimental/Intersection/CurveIntersection.h
index d01bb7d..cbcda76 100644
--- a/experimental/Intersection/CurveIntersection.h
+++ b/experimental/Intersection/CurveIntersection.h
@@ -51,7 +51,7 @@
double y, bool flipped, Intersections& );
bool intersect(const Cubic& cubic1, const Cubic& cubic2, Intersections& );
// the following flavor uses quadratic approximation instead of convex hulls
-bool intersect2(const Cubic& cubic1, const Cubic& cubic2, Intersections& );
+//bool intersect2(const Cubic& cubic1, const Cubic& cubic2, Intersections& );
// like '2', but iterates on centers instead of possible edges
bool intersect3(const Cubic& cubic1, const Cubic& cubic2, Intersections& );
int intersect(const Cubic& cubic, Intersections& i); // return true if cubic self-intersects
diff --git a/experimental/Intersection/DataTypes.h b/experimental/Intersection/DataTypes.h
index 4b682ff..166ba81 100644
--- a/experimental/Intersection/DataTypes.h
+++ b/experimental/Intersection/DataTypes.h
@@ -13,6 +13,7 @@
#include "SkPoint.h"
#define ONE_OFF_DEBUG 0
+#define ONE_OFF_DEBUG_MATHEMATICA 1
// FIXME: move these into SkTypes.h
template <typename T> inline T SkTMax(T a, T b) {
diff --git a/experimental/Intersection/EdgeWalker_TestUtility.cpp b/experimental/Intersection/EdgeWalker_TestUtility.cpp
index 8afc09f..9f4aafc 100644
--- a/experimental/Intersection/EdgeWalker_TestUtility.cpp
+++ b/experimental/Intersection/EdgeWalker_TestUtility.cpp
@@ -265,7 +265,8 @@
showPath(a, "minuend:");
SkDebugf("op: %s\n", opStrs[shapeOp]);
showPath(b, "subtrahend:");
- showPath(scaledOne, "region:", scale);
+ // the region often isn't very helpful since it approximates curves with a lot of line-tos
+ if (0) showPath(scaledOne, "region:", scale);
showPath(two, "op result:");
drawAsciiPaths(scaledOne, scaledTwo, true);
}
diff --git a/experimental/Intersection/Intersection_Tests.cpp b/experimental/Intersection/Intersection_Tests.cpp
index 244f92f..9e5237c 100644
--- a/experimental/Intersection/Intersection_Tests.cpp
+++ b/experimental/Intersection/Intersection_Tests.cpp
@@ -14,11 +14,11 @@
void Intersection_Tests() {
int testsRun = 0;
+ CubicIntersection_SelfTest();
QuadraticIntersection_IntersectionFinder();
QuadraticIntersection_OneOffTest();
CubicIntersection_IntersectionFinder();
CubicIntersection_NewOneOffTest();
- CubicIntersection_SelfTest();
#if 0
#endif
SimplifyNew_Test();
diff --git a/experimental/Intersection/QuadraticIntersection_Test.cpp b/experimental/Intersection/QuadraticIntersection_Test.cpp
index 46cf20a..35fda3a 100644
--- a/experimental/Intersection/QuadraticIntersection_Test.cpp
+++ b/experimental/Intersection/QuadraticIntersection_Test.cpp
@@ -54,6 +54,9 @@
}
static const Quadratic testSet[] = {
+ {{1,2}, {0.984375,2.3359375}, {1.0625,2.15625}},
+ {{0,1}, {0.983539095,2.30041152}, {1.47325103,2.61316872}},
+
{{4.09011926,2.20971038}, {4.74608133,1.9335932}, {5.02469918,2.00694987}},
{{2.79472921,1.73568666}, {3.36246373,1.21251209}, {5,2}},
diff --git a/experimental/Intersection/QuarticRoot.cpp b/experimental/Intersection/QuarticRoot.cpp
index 061098a..039a2c7 100644
--- a/experimental/Intersection/QuarticRoot.cpp
+++ b/experimental/Intersection/QuarticRoot.cpp
@@ -41,7 +41,7 @@
sprintf(str, "Solve[%1.19g x^4 + %1.19g x^3 + %1.19g x^2 + %1.19g x + %1.19g == 0, x]",
t4, t3, t2, t1, t0);
mathematica_ize(str, sizeof(str));
-#if ONE_OFF_DEBUG
+#if ONE_OFF_DEBUG && ONE_OFF_DEBUG_MATHEMATICA
SkDebugf("%s\n", str);
#endif
#endif
diff --git a/experimental/Intersection/ShapeOps.cpp b/experimental/Intersection/ShapeOps.cpp
index f1792a8..7c7a205 100644
--- a/experimental/Intersection/ShapeOps.cpp
+++ b/experimental/Intersection/ShapeOps.cpp
@@ -134,8 +134,6 @@
bool firstContour = true;
bool unsortable = false;
bool topUnsortable = false;
- bool firstRetry = false;
- bool closable = true;
SkPoint topLeft = {SK_ScalarMin, SK_ScalarMin};
do {
int index, endIndex;
@@ -145,8 +143,7 @@
if (!current) {
if (topUnsortable || !done) {
topUnsortable = false;
- SkASSERT(!firstRetry);
- firstRetry = true;
+ SkASSERT(topLeft.fX != SK_ScalarMin && topLeft.fY != SK_ScalarMin);
topLeft.fX = topLeft.fY = SK_ScalarMin;
continue;
}
@@ -155,7 +152,6 @@
SkTDArray<Span*> chaseArray;
do {
if (current->activeOp(index, endIndex, xorMask, xorOpMask, op)) {
- bool active = true;
do {
#if DEBUG_ACTIVE_SPANS
if (!unsortable && current->done()) {
@@ -168,34 +164,37 @@
Segment* next = current->findNextOp(chaseArray, nextStart, nextEnd,
unsortable, op, xorMask, xorOpMask);
if (!next) {
- // SkASSERT(!unsortable);
if (!unsortable && simple.hasMove()
&& current->verb() != SkPath::kLine_Verb
&& !simple.isClosed()) {
current->addCurveTo(index, endIndex, simple, true);
SkASSERT(simple.isClosed());
}
- active = false;
break;
}
+ #if DEBUG_FLOW
+ SkDebugf("%s current id=%d from=(%1.9g,%1.9g) to=(%1.9g,%1.9g)\n", __FUNCTION__,
+ current->debugID(), current->xyAtT(index).fX, current->xyAtT(index).fY,
+ current->xyAtT(endIndex).fX, current->xyAtT(endIndex).fY);
+ #endif
current->addCurveTo(index, endIndex, simple, true);
current = next;
index = nextStart;
endIndex = nextEnd;
- } while (!simple.isClosed() && ((!unsortable) || !current->done()));
- if (active && !simple.isClosed()) {
+ } while (!simple.isClosed() && ((!unsortable)
+ || !current->done(SkMin32(index, endIndex))));
+ if (current->activeWinding(index, endIndex) && !simple.isClosed()) {
SkASSERT(unsortable);
int min = SkMin32(index, endIndex);
if (!current->done(min)) {
current->addCurveTo(index, endIndex, simple, true);
current->markDoneBinary(min);
}
- closable = false;
}
simple.close();
} else {
Span* last = current->markAndChaseDoneBinary(index, endIndex);
- if (last) {
+ if (last && !last->fLoop) {
*chaseArray.append() = last;
}
}
@@ -208,7 +207,7 @@
}
} while (true);
} while (true);
- return closable;
+ return simple.someAssemblyRequired();
}
} // end of Op namespace
diff --git a/experimental/Intersection/Simplify.cpp b/experimental/Intersection/Simplify.cpp
index e269ffd..47ce8f4 100644
--- a/experimental/Intersection/Simplify.cpp
+++ b/experimental/Intersection/Simplify.cpp
@@ -69,7 +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_AS_C_CODE 1
#define DEBUG_ASSEMBLE 1
#define DEBUG_CONCIDENT 1
#define DEBUG_CROSS 0
@@ -97,7 +97,7 @@
#endif
#if DEBUG_SORT
-static int gDebugSortCountDefault = 3; // SK_MaxS32;
+static int gDebugSortCountDefault = SK_MaxS32;
static int gDebugSortCount;
#endif
@@ -649,6 +649,7 @@
bool fUnsortableStart; // set when start is part of an unsortable pair
bool fUnsortableEnd; // set when end is part of an unsortable pair
bool fTiny; // if set, span may still be considered once for edge following
+ bool fLoop; // set when a cubic loops back to this point
};
// sorting angles
@@ -862,12 +863,10 @@
Quadratic& quad = (Quadratic&)fCurvePart;
QuadSubDivideHD(fPts, startT, endT, quad);
fTangent1.quadEndPoints(quad, 0, 1);
- #if 1 // FIXME: try enabling this and see if a) it's called and b) does it break anything
if (dx() == 0 && dy() == 0) {
// SkDebugf("*** %s quad is line\n", __FUNCTION__);
fTangent1.quadEndPoints(quad);
}
- #endif
fSide = -fTangent1.pointDistance(fCurvePart[2]); // not normalized -- compare sign only
} break;
case SkPath::kCubic_Verb: {
@@ -877,12 +876,10 @@
if (dx() == 0 && dy() == 0) {
fTangent1.cubicEndPoints(fCurvePart, 0, 2);
nextC = 3;
- #if 1 // FIXME: try enabling this and see if a) it's called and b) does it break anything
if (dx() == 0 && dy() == 0) {
- SkDebugf("*** %s cubic is line\n", __FUNCTION__);
+ // SkDebugf("*** %s cubic is line\n", __FUNCTION__);
fTangent1.cubicEndPoints(fCurvePart, 0, 3);
}
- #endif
}
fSide = -fTangent1.pointDistance(fCurvePart[nextC]); // compare sign only
if (nextC == 2 && approximately_zero(fSide)) {
@@ -1686,6 +1683,7 @@
span->fWindValue = 1;
span->fOppValue = 0;
span->fTiny = false;
+ span->fLoop = false;
if ((span->fDone = newT == 1)) {
++fDoneSpans;
}
@@ -1881,6 +1879,13 @@
other.addCancelOutsides(tStart, oStart, *this, endT);
}
}
+
+ int addSelfT(Segment* other, const SkPoint& pt, double& newT) {
+ int result = addT(other, pt, newT);
+ Span* span = &fTs[result];
+ span->fLoop = true;
+ return result;
+ }
int addUnsortableT(Segment* other, bool start, const SkPoint& pt, double& newT) {
int result = addT(other, pt, newT);
@@ -2435,6 +2440,7 @@
bool foundDone = false;
// iterate through the angle, and compute everyone's winding
Segment* nextSegment;
+ int activeCount = 0;
do {
SkASSERT(nextIndex != firstIndex);
if (nextIndex == angleCount) {
@@ -2446,9 +2452,16 @@
bool activeAngle = nextSegment->activeOp(xorMiMask, xorSuMask, nextAngle->start(),
nextAngle->end(), op, sumMiWinding, sumSuWinding,
maxWinding, sumWinding, oppMaxWinding, oppSumWinding);
- if (activeAngle && (!foundAngle || foundDone)) {
- foundAngle = nextAngle;
- foundDone = nextSegment->done(nextAngle) && !nextSegment->tiny(nextAngle);
+ if (activeAngle) {
+ ++activeCount;
+ if (!foundAngle || (foundDone && activeCount & 1)) {
+ if (nextSegment->tiny(nextAngle)) {
+ unsortable = true;
+ return NULL;
+ }
+ foundAngle = nextAngle;
+ foundDone = nextSegment->done(nextAngle) && !nextSegment->tiny(nextAngle);
+ }
}
if (nextSegment->done()) {
continue;
@@ -2909,6 +2922,10 @@
SkVector dxyS = leftSegment->dxdy(tIndex);
double cross = dxyE.cross(dxyS);
bool bumpCheck = bumpsUp && xyE.fY < xyS.fY && dxyE.fX < 0;
+ if (xyE == xyS){
+ SkDebugf("%s ignore loops\n", __FUNCTION__);
+ cross = 0;
+ }
#if DEBUG_SWAP_TOP
SkDebugf("%s xyE=(%1.9g,%1.9g) xyS=(%1.9g,%1.9g)\n", __FUNCTION__,
xyE.fX, xyE.fY, xyS.fX, xyS.fY);
@@ -3195,7 +3212,7 @@
Segment* other = this;
while ((other = other->nextChase(index, step, min, last))) {
if (other->fTs[min].fWindSum != SK_MinS32) {
- SkASSERT(other->fTs[min].fWindSum == winding);
+ SkASSERT(other->fTs[min].fWindSum == winding || other->fTs[min].fLoop);
return NULL;
}
other->markWinding(min, winding, oppWinding);
@@ -4442,6 +4459,11 @@
return fSegments[segIndex].addT(&other->fSegments[otherIndex], pt, newT);
}
+ int addSelfT(int segIndex, Contour* other, int otherIndex, const SkPoint& pt, double& newT) {
+ setContainsIntercepts();
+ return fSegments[segIndex].addSelfT(&other->fSegments[otherIndex], pt, newT);
+ }
+
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);
@@ -5133,6 +5155,10 @@
int addT(const Work& other, const SkPoint& pt, double& newT) {
return fContour->addT(fIndex, other.fContour, other.fIndex, pt, newT);
}
+
+ int addSelfT(const Work& other, const SkPoint& pt, double& newT) {
+ return fContour->addSelfT(fIndex, other.fContour, other.fIndex, pt, newT);
+ }
int addUnsortableT(const Work& other, bool start, const SkPoint& pt, double& newT) {
return fContour->addUnsortableT(fIndex, other.fContour, other.fIndex, start, pt, newT);
@@ -5694,7 +5720,7 @@
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(wt, point, ts.fT[0][0]);
+ int testTAt = wt.addSelfT(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);
@@ -6157,7 +6183,7 @@
simple.close();
} else {
Span* last = current->markAndChaseDoneUnary(index, endIndex);
- if (last) {
+ if (last && !last->fLoop) {
*chaseArray.append() = last;
}
}
diff --git a/experimental/Intersection/SimplifyAngle_Test.cpp b/experimental/Intersection/SimplifyAngle_Test.cpp
index 9b25851..e83a52f 100644
--- a/experimental/Intersection/SimplifyAngle_Test.cpp
+++ b/experimental/Intersection/SimplifyAngle_Test.cpp
@@ -230,10 +230,19 @@
{SkPath::kMove_Verb }
};
+static const segmentWithT oneOffTest4[] = {
+ {SkPath::kCubic_Verb, {{1,2}, {1,3}, {1,0}, {5,3}}, {0.134792, 0}},
+ {SkPath::kCubic_Verb, {{0,1}, {3,5}, {2,1}, {3,1}}, {0.134792094, 0}},
+ {SkPath::kCubic_Verb, {{0,1}, {3,5}, {2,1}, {3,1}}, {0.134792094, 0.551812363}},
+ {SkPath::kCubic_Verb, {{1,2}, {1,3}, {1,0}, {5,3}}, {0.134792, 0.333333333}},
+ {SkPath::kMove_Verb }
+};
+
static const segmentWithT* oneOffTests[] = {
oneOffTest1,
oneOffTest2,
oneOffTest3,
+ oneOffTest4,
};
static const size_t oneOffTestCount = sizeof(oneOffTests) / sizeof(oneOffTests[0]);
@@ -259,6 +268,49 @@
SkDebugf("%s finished\n", __FUNCTION__);
}
+#if 0 // seems too complicated for this to be useful (didn't finish writing/debugging this)
+// this (trys to) take a pair of curves, construct segments/spans, and verify that they sort correctly
+static void oneOffTestNew() {
+ const segmentWithT* segPtr = oneOffTest4;
+ SimplifyAngleTest::Segment segOne, segTwo;
+ segOne.init(segPtr[0].pts, segPtr[0].verb, false, false);
+ segTwo.init(segPtr[1].pts, segPtr[1].verb, false, false);
+ int index = 0;
+ do {
+ int next = index + 1;
+ if (segPtr[index].verb == SkPath::kMove_Verb) {
+ break;
+ }
+ SkPoint sub[4];
+ (*SegmentSubDivide[segPtr[index].verb])(segPtr[index].pts, segPtr[index].ts[0],
+ segPtr[index].ts[1], sub);
+ if (memcmp(segPtr[index].pts, segPtr[0].pts, sizeof(SkPoint) * (segPtr[index].verb + 1) == 0) {
+ segOne.addT(&segTwo, sub[0], segPtr[index].ts[0]);
+ segOne.addT(&segTwo, sub[segPtr[index].verb], segPtr[index].ts[1]);
+ } else {
+ segTwo.addT(&segOne, sub[0], segPtr[index].ts[0]);
+ segTwo.addT(&v, sub[segPtr[index].verb], segPtr[index].ts[1]);
+ }
+ } while (true);
+ SimplifyAngleTest::Angle lesser, greater;
+ do {
+ int next = index + 1;
+ if (segPtr[next].verb == SkPath::kMove_Verb) {
+ break;
+ }
+ SkPoint one[4], two[4];
+ bool use1 = memcmp(segPtr[index].pts, segPtr[0].pts, sizeof(SkPoint) * (segPtr[index].verb + 1) == 0;
+ lesser.set(segPtr[index].pts, segPtr[index].verb, use1 ? &segOne : &segTwo, index, next, dummy);
+ use1 = memcmp(segPtr[next].pts, segPtr[0].pts, sizeof(SkPoint) * (segPtr[next].verb + 1) == 0;
+ greater.set(segPtr[next].pts, segPtr[next].verb, use1 ? &segOne : &segTwo, index, next, dummy);
+ bool result = lesser < greater;
+ SkASSERT(result);
+ index = next;
+ } while (true);
+ SkDebugf("%s finished\n", __FUNCTION__);
+}
+#endif
+
static void (*tests[])(bool) = {
oneOffTest,
testSegments,
diff --git a/experimental/Intersection/SimplifyNew_Test.cpp b/experimental/Intersection/SimplifyNew_Test.cpp
index ffba8dc..145b856 100644
--- a/experimental/Intersection/SimplifyNew_Test.cpp
+++ b/experimental/Intersection/SimplifyNew_Test.cpp
@@ -4164,6 +4164,19 @@
testShapeOp(path, pathB, kUnion_Op);
}
+static void cubicOp31x() {
+ 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, kXor_Op);
+}
+
static void testCubic2() {
SkPath path;
path.moveTo(0,2);
@@ -4175,15 +4188,72 @@
testSimplifyx(path);
}
-static void (*firstTest)() = 0;
+static void cubicOp32d() {
+ SkPath path, pathB;
+ path.setFillType(SkPath::kWinding_FillType);
+ path.moveTo(0,1);
+ path.cubicTo(1,2, 6,0, 3,1);
+ path.close();
+ pathB.setFillType(SkPath::kWinding_FillType);
+ pathB.moveTo(0,6);
+ pathB.cubicTo(1,3, 1,0, 2,1);
+ pathB.close();
+ testShapeOp(path, pathB, kDifference_Op);
+}
+
+static void cubicOp33i() {
+ SkPath path, pathB;
+ path.setFillType(SkPath::kWinding_FillType);
+ path.moveTo(0,1);
+ path.cubicTo(1,2, 6,0, 3,1);
+ path.close();
+ pathB.setFillType(SkPath::kWinding_FillType);
+ pathB.moveTo(0,6);
+ pathB.cubicTo(1,3, 1,0, 2,1);
+ pathB.close();
+ testShapeOp(path, pathB, kIntersect_Op);
+}
+
+static void cubicOp34d() {
+ SkPath path, pathB;
+ path.setFillType(SkPath::kWinding_FillType);
+ path.moveTo(0,1);
+ path.cubicTo(3,5, 2,1, 3,1);
+ path.close();
+ pathB.setFillType(SkPath::kWinding_FillType);
+ pathB.moveTo(1,2);
+ pathB.cubicTo(1,3, 1,0, 5,3);
+ pathB.close();
+ testShapeOp(path, pathB, kDifference_Op);
+}
+
+static void cubicOp35d() {
+ SkPath path, pathB;
+ path.setFillType(SkPath::kWinding_FillType);
+ path.moveTo(0,1);
+ path.cubicTo(1,5, 2,1, 4,0);
+ path.close();
+ pathB.setFillType(SkPath::kWinding_FillType);
+ pathB.moveTo(1,2);
+ pathB.cubicTo(0,4, 1,0, 5,1);
+ pathB.close();
+ testShapeOp(path, pathB, kDifference_Op);
+}
+
+static void (*firstTest)() = cubicOp35d;
static struct {
void (*fun)();
const char* str;
} tests[] = {
- TEST(testCubic2),
- TEST(cubicOp31u),
+ TEST(cubicOp35d),
+ TEST(cubicOp34d),
+ TEST(cubicOp33i),
+ TEST(cubicOp32d),
TEST(cubicOp31d),
+ TEST(testCubic2),
+ TEST(cubicOp31x),
+ TEST(cubicOp31u),
TEST(cubicOp30d),
TEST(cubicOp29d),
TEST(cubicOp28u),
@@ -4591,7 +4661,7 @@
static bool skipAll = false;
static bool runSubTestsFirst = false;
-static bool runReverse = false;
+static bool runReverse = true;
static void (*stopTest)() = 0;
void SimplifyNew_Test() {
diff --git a/experimental/Intersection/as.htm b/experimental/Intersection/as.htm
index 93845cb..c8a50bb 100644
--- a/experimental/Intersection/as.htm
+++ b/experimental/Intersection/as.htm
@@ -60,11 +60,177 @@
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="cubicOp35d">
+ SimplifyNew_Test [cubicOp35d]
+debugShowCubicIntersection no self intersect {{0,1}, {1,5}, {2,1}, {4,0}}
+debugShowCubicLineIntersection wtTs[0]=0 {{0,1}, {1,5}, {2,1}, {4,0}} {{0,1}} wtTs[1]=1 {{4,0}} wnTs[0]=1 {{4,0}, {0,1}} wnTs[1]=0
+debugShowCubicIntersection wtTs[0]=0.210357794 {{0,1}, {1,5}, {2,1}, {4,0}} {{0.64038179843233178,2.5646764769093426}} wtTs[1]=0.788675135 {{2.8565880156561105,0.93208711896642604}} wnTs[0]=0.223476 {{1,2}, {0,4}, {1,0}, {5,1}} wnTs[1]=0.788675135
+debugShowCubicLineIntersection wtTs[0]=0.646900486 {{0,1}, {1,5}, {2,1}, {4,0}} {{2.2114165293341985,1.6971458676664504}} wnTs[0]=0.697146 {{5,1}, {1,2}}
+debugShowCubicLineIntersection no intersect {{1,2}, {0,4}, {1,0}, {5,1}} {{4,0}, {0,1}}
+debugShowLineIntersection no intersect {{4,0}, {0,1}} {{5,1}, {1,2}}
+debugShowCubicIntersection wtTs[0]=0.002763735 {{1,2}, {0,4}, {1,0}, {5,1}} {{0.9917546455060533,2.0164451540317003}} wtTs[1]=0.461521979
+debugShowCubicLineIntersection wtTs[0]=0 {{1,2}, {0,4}, {1,0}, {5,1}} {{1,2}} wtTs[1]=0.466666667 {{1.0082962962962965,1.9979259259259259}} wtTs[2]=1 {{5,1}} wnTs[0]=1 {{5,1}, {1,2}} wnTs[1]=0.997925926 wnTs[2]=0
+debugShowActiveSpans id=1 (0,1 1,5 2,1 4,0) t=0 (0,1) tEnd=0.210357794 other=2 otherT=1 otherIndex=1 windSum=? windValue=1 oppValue=0
+debugShowActiveSpans id=1 (0,1 1,5 2,1 4,0) t=0.210357794 (0.640381813,2.56467652) tEnd=0.646900486 other=3 otherT=0.223476406 otherIndex=2 windSum=? windValue=1 oppValue=0
+debugShowActiveSpans id=1 (0,1 1,5 2,1 4,0) t=0.646900486 (2.21141648,1.69714582) tEnd=0.788675135 other=4 otherT=0.697145868 otherIndex=1 windSum=? windValue=1 oppValue=0
+debugShowActiveSpans id=1 (0,1 1,5 2,1 4,0) t=0.788675135 (2.85658813,0.932087123) tEnd=1 other=3 otherT=0.788675135 otherIndex=5 windSum=? windValue=1 oppValue=0
+debugShowActiveSpans id=2 (4,0 0,1) t=0 (4,0) tEnd=1 other=1 otherT=1 otherIndex=4 windSum=? windValue=1 oppValue=0
+debugShowActiveSpans id=3 (1,2 0,4 1,0 5,1) t=0 (1,2) tEnd=0.002763735 other=4 otherT=1 otherIndex=3 windSum=? windValue=1 oppValue=0
+debugShowActiveSpans id=3 (1,2 0,4 1,0 5,1) t=0.002763735 (0.991754651,2.01644516) tEnd=0.223476406 other=3 otherT=0.461521979 otherIndex=3 windSum=? windValue=1 oppValue=0
+debugShowActiveSpans id=3 (1,2 0,4 1,0 5,1) t=0.223476406 (0.640381813,2.56467652) tEnd=0.461521979 other=1 otherT=0.210357794 otherIndex=1 windSum=? windValue=1 oppValue=0
+debugShowActiveSpans id=3 (1,2 0,4 1,0 5,1) t=0.461521979 (0.991754651,2.01644516) tEnd=0.466666667 other=3 otherT=0.002763735 otherIndex=1 windSum=? windValue=1 oppValue=0
+debugShowActiveSpans id=3 (1,2 0,4 1,0 5,1) t=0.466666667 (1.00829625,1.99792588) tEnd=0.788675135 other=4 otherT=0.997925926 otherIndex=2 windSum=? windValue=1 oppValue=0
+debugShowActiveSpans id=3 (1,2 0,4 1,0 5,1) t=0.788675135 (2.85658813,0.932087123) tEnd=1 other=1 otherT=0.788675135 otherIndex=3 windSum=? windValue=1 oppValue=0
+debugShowActiveSpans id=4 (5,1 1,2) t=0 (5,1) tEnd=0.697145868 other=3 otherT=1 otherIndex=6 windSum=? windValue=1 oppValue=0
+debugShowActiveSpans id=4 (5,1 1,2) t=0.697145868 (2.21141648,1.69714582) tEnd=0.997925926 other=1 otherT=0.646900486 otherIndex=2 windSum=? windValue=1 oppValue=0
+debugShowActiveSpans id=4 (5,1 1,2) t=0.997925926 (1.00829625,1.99792588) tEnd=1 other=3 otherT=0.466666667 otherIndex=4 windSum=? windValue=1 oppValue=0
+findTop debugShowSort contourWinding=0 oppContourWinding=0 sign=-1
+debugShowSort [0] id=2 line start=0 (4,0) end=1 (0,1) sign=-1 windValue=1 windSum=? 0->1 (max=1) done=0 tiny=0 opp=0
+debugShowSort [1] id=1 cubic start=4 (4,0) end=3 (2.85658813,0.932087123) sign=1 windValue=1 windSum=? 1->0 (max=1) done=0 tiny=0 opp=0
+markWinding id=2 (4,0 0,1) t=0 [0] (4,0) newWindSum=1 newOppSum=0 oppSum=? windSum=? windValue=1
+markWinding id=1 (0,1 1,5 2,1 4,0) t=0.788675135 [3] (2.85658813,0.932087123) newWindSum=1 newOppSum=0 oppSum=? windSum=? windValue=1
+markWinding id=2 (4,0 0,1) t=0 [0] (4,0) newWindSum=1 newOppSum=0 oppSum=0 windSum=1 windValue=1
+markWinding id=1 (0,1 1,5 2,1 4,0) t=0 [0] (0,1) newWindSum=1 newOppSum=0 oppSum=? windSum=? windValue=1
+activeOp op=diff miFrom=1 miTo=0 suFrom=0 suTo=0 result=1
+findNextOp simple
+markDoneBinary id=2 (4,0 0,1) t=0 [0] (4,0) newWindSum=1 newOppSum=0 oppSum=0 windSum=1 windValue=1
+bridgeOp current id=2 from=(0,1) to=(4,0)
+findNextOp debugShowSort contourWinding=0 oppContourWinding=0 sign=-1
+debugShowSort [1] id=1 cubic start=3 (2.85658813,0.932087123) end=4 (4,0) sign=-1 windValue=1 windSum=1 0->1 (max=1) done=0 tiny=0 opp=0
+debugShowSort [2] id=3 cubic start=5 (2.85658813,0.932087123) end=4 (1.00829625,1.99792588) sign=1 windValue=1 windSum=? 0->-1 (max=-1) done=0 tiny=0 opp=1
+debugShowSort [3] id=1 cubic start=3 (2.85658813,0.932087123) end=2 (2.21141648,1.69714582) sign=1 windValue=1 windSum=? 1->0 (max=1) done=0 tiny=0 opp=0
+debugShowSort [0] id=3 cubic start=5 (2.85658813,0.932087123) end=6 (5,1) sign=-1 windValue=1 windSum=? -1->0 (max=-1) done=0 tiny=0 opp=1
+findNextOp firstIndex=[1] sign=-1
+activeOp op=diff miFrom=1 miTo=1 suFrom=0 suTo=1 result=1
+markWinding id=3 (1,2 0,4 1,0 5,1) t=0.466666667 [4] (1.00829625,1.99792588) newWindSum=-1 newOppSum=1 oppSum=? windSum=? windValue=1
+findNextOp chase.append id=3
+activeOp op=diff miFrom=1 miTo=0 suFrom=1 suTo=1 result=0
+markDoneBinary id=1 (0,1 1,5 2,1 4,0) t=0.646900486 [2] (2.21141648,1.69714582) newWindSum=1 newOppSum=-1 oppSum=? windSum=? windValue=1
+findNextOp chase.append id=1
+activeOp op=diff miFrom=0 miTo=0 suFrom=1 suTo=0 result=0
+markDoneBinary id=3 (1,2 0,4 1,0 5,1) t=0.788675135 [5] (2.85658813,0.932087123) newWindSum=-1 newOppSum=0 oppSum=? windSum=? windValue=1
+markDoneBinary id=4 (5,1 1,2) t=0 [0] (5,1) newWindSum=-1 newOppSum=0 oppSum=? windSum=? windValue=1
+findNextOp chase.append id=4
+markDoneBinary id=1 (0,1 1,5 2,1 4,0) t=0.788675135 [3] (2.85658813,0.932087123) newWindSum=1 newOppSum=0 oppSum=0 windSum=1 windValue=1
+findNextOp from:[1] to:[3] start=5 end=4
+bridgeOp current id=1 from=(4,0) to=(2.85658813,0.932087123)
+path.moveTo(0,1);
+path.lineTo(4,0);
+path.cubicTo(3.57735038,0.211324871, 3.1993587,0.556624353, 2.85658813,0.932087123);
+findNextOp debugShowSort contourWinding=-1 oppContourWinding=1 sign=-1
+debugShowSort [1] id=3 cubic start=4 (1.00829625,1.99792588) end=5 (2.85658813,0.932087123) sign=-1 windValue=1 windSum=-1 -1->0 (max=-1) done=0 tiny=0 opp=0
+debugShowSort [2] id=4 line start=2 (1.00829625,1.99792588) end=3 (1,2) sign=-1 windValue=1 windSum=? 0->1 (max=1) done=0 tiny=0 opp=0
+debugShowSort [3] id=3 cubic start=4 (1.00829625,1.99792588) end=3 (0.991754651,2.01644516) sign=1 windValue=1 windSum=? 1->0 (max=1) done=0 tiny=0 opp=0
+debugShowSort [0] id=4 line start=2 (1.00829625,1.99792588) end=1 (2.21141648,1.69714582) sign=1 windValue=1 windSum=? 0->-1 (max=-1) done=0 tiny=0 opp=0
+findNextOp firstIndex=[1] sign=-1
+activeOp op=diff miFrom=1 miTo=1 suFrom=0 suTo=1 result=1
+markWinding id=4 (5,1 1,2) t=0.997925926 [2] (1.00829625,1.99792588) newWindSum=1 newOppSum=1 oppSum=? windSum=? windValue=1
+markWinding id=3 (1,2 0,4 1,0 5,1) t=0 [0] (1,2) newWindSum=1 newOppSum=1 oppSum=? windSum=? windValue=1
+findNextOp chase.append id=3
+activeOp op=diff miFrom=1 miTo=1 suFrom=1 suTo=0 result=1
+markWinding id=3 (1,2 0,4 1,0 5,1) t=0.461521979 [3] (0.991754651,2.01644516) newWindSum=1 newOppSum=1 oppSum=? windSum=? windValue=1
+findNextOp chase.append id=3
+activeOp op=diff miFrom=1 miTo=1 suFrom=0 suTo=1 result=1
+markWinding id=4 (5,1 1,2) t=0.697145868 [1] (2.21141648,1.69714582) newWindSum=-1 newOppSum=1 oppSum=? windSum=? windValue=1
+findNextOp chase.append id=4
+markDoneBinary id=3 (1,2 0,4 1,0 5,1) t=0.466666667 [4] (1.00829625,1.99792588) newWindSum=-1 newOppSum=1 oppSum=1 windSum=-1 windValue=1
+findNextOp from:[3] to:[4] start=2 end=3
+bridgeOp current id=3 from=(2.85658813,0.932087123) to=(1.00829625,1.99792588)
+path.cubicTo(1.96246409,1.13237906, 1.35749662,1.61008465, 1.00829625,1.99792588);
+findNextOp simple
+markDoneBinary id=4 (5,1 1,2) t=0.997925926 [2] (1.00829625,1.99792588) newWindSum=1 newOppSum=1 oppSum=1 windSum=1 windValue=1
+bridgeOp current id=4 from=(1.00829625,1.99792588) to=(1,2)
+Program received signal: “EXC_BAD_ACCESS”.
+findNextOp debugShowSort contourWinding=1 oppContourWinding=1 sign=1
+debugShowSort [1] id=3 cubic start=1 (0.991754651,2.01644516) end=0 (1,2) sign=1 windValue=1 windSum=1 1->0 (max=1) done=0 tiny=0 opp=0
+debugShowSort [2] id=3 cubic start=3 (0.991754651,2.01644516) end=2 (0.640381813,2.56467652) sign=1 windValue=1 windSum=? 0->-1 (max=-1) done=0 tiny=0 opp=0
+debugShowSort [3] id=3 cubic start=1 (0.991754651,2.01644516) end=2 (0.640381813,2.56467652) sign=-1 windValue=1 windSum=? -1->0 (max=-1) done=0 tiny=0 opp=0
+debugShowSort [0] id=3 cubic start=3 (0.991754651,2.01644516) end=4 (1.00829625,1.99792588) sign=-1 windValue=1 windSum=1 0->1 (max=1) done=0 tiny=0 opp=0
+findNextOp firstIndex=[1] sign=1
+activeOp op=diff miFrom=1 miTo=1 suFrom=0 suTo=1 result=1
+markWinding id=3 (1,2 0,4 1,0 5,1) t=0.223476406 [2] (0.640381813,2.56467652) newWindSum=-1 newOppSum=1 oppSum=? windSum=? windValue=1
+findNextOp chase.append id=3
+activeOp op=diff miFrom=1 miTo=1 suFrom=1 suTo=0 result=1
+markWinding id=3 (1,2 0,4 1,0 5,1) t=0.002763735 [1] (0.991754651,2.01644516) newWindSum=-1 newOppSum=1 oppSum=? windSum=? windValue=1
+findNextOp chase.append id=3
+activeOp op=diff miFrom=1 miTo=1 suFrom=0 suTo=1 result=1
+markDoneBinary id=3 (1,2 0,4 1,0 5,1) t=0 [0] (1,2) newWindSum=1 newOppSum=1 oppSum=1 windSum=1 windValue=1
+findNextOp from:[3] to:[3] start=3 end=2
+bridgeOp current id=3 from=(1,2) to=(0.991754651,2.01644516)
+path.lineTo(1,2);
+path.cubicTo(0.997236252,2.0055275, 0.994487822,2.01100922, 0.991754651,2.01644516);
+findNextOp debugShowSort contourWinding=-1 oppContourWinding=1 sign=-1
+debugShowSort [0] id=3 cubic start=2 (0.640381813,2.56467652) end=3 (0.991754651,2.01644516) sign=-1 windValue=1 windSum=-1 -1->0 (max=-1) done=0 tiny=0 opp=0
+debugShowSort [1] id=1 cubic start=1 (0.640381813,2.56467652) end=0 (0,1) sign=1 windValue=1 windSum=1 1->0 (max=1) done=0 tiny=0 opp=1
+debugShowSort [2] id=3 cubic start=2 (0.640381813,2.56467652) end=1 (0.991754651,2.01644516) sign=1 windValue=1 windSum=-1 0->-1 (max=-1) done=0 tiny=0 opp=0
+debugShowSort [3] id=1 cubic start=1 (0.640381813,2.56467652) end=2 (2.21141648,1.69714582) sign=-1 windValue=1 windSum=? 0->1 (max=1) done=0 tiny=0 opp=1
+findNextOp firstIndex=[0] sign=-1
+activeOp op=diff miFrom=1 miTo=0 suFrom=0 suTo=0 result=1
+activeOp op=diff miFrom=0 miTo=0 suFrom=0 suTo=1 result=0
+activeOp op=diff miFrom=0 miTo=1 suFrom=1 suTo=1 result=0
+markDoneBinary id=1 (0,1 1,5 2,1 4,0) t=0.210357794 [1] (0.640381813,2.56467652) newWindSum=1 newOppSum=-1 oppSum=? windSum=? windValue=1
+findNextOp chase.append id=1
+markDoneBinary id=3 (1,2 0,4 1,0 5,1) t=0.223476406 [2] (0.640381813,2.56467652) newWindSum=-1 newOppSum=1 oppSum=1 windSum=-1 windValue=1
+findNextOp from:[3] to:[1] start=1 end=0
+bridgeOp current id=3 from=(0.991754651,2.01644516) to=(0.640381813,2.56467652)
+path.cubicTo(0.739642859,2.30096555, 0.627014875,2.53316927, 0.640381813,2.56467652);
+findNextOp simple
+markDoneBinary id=1 (0,1 1,5 2,1 4,0) t=0 [0] (0,1) newWindSum=1 newOppSum=0 oppSum=0 windSum=1 windValue=1
+bridgeOp current id=1 from=(0.640381813,2.56467652) to=(0,1)
+path.cubicTo(0.42071557,2.32885909, 0.2103578,1.84143114, 0,1);
+path.close();
+debugShowActiveSpans id=3 (1,2 0,4 1,0 5,1) t=0.002763735 (0.991754651,2.01644516) tEnd=0.223476406 other=3 otherT=0.461521979 otherIndex=3 windSum=-1 windValue=1 oppValue=0
+debugShowActiveSpans id=3 (1,2 0,4 1,0 5,1) t=0.461521979 (0.991754651,2.01644516) tEnd=0.466666667 other=3 otherT=0.002763735 otherIndex=1 windSum=1 windValue=1 oppValue=0
+debugShowActiveSpans id=4 (5,1 1,2) t=0.697145868 (2.21141648,1.69714582) tEnd=0.997925926 other=1 otherT=0.646900486 otherIndex=2 windSum=-1 windValue=1 oppValue=0
+activeOp op=diff miFrom=1 miTo=1 suFrom=1 suTo=0 result=1
+findNextOp debugShowSort contourWinding=0 oppContourWinding=1 sign=1
+debugShowSort [0] id=4 line start=2 (1.00829625,1.99792588) end=1 (2.21141648,1.69714582) sign=1 windValue=1 windSum=-1 0->-1 (max=-1) done=0 tiny=0 opp=0
+debugShowSort [1] id=3 cubic start=4 (1.00829625,1.99792588) end=5 (2.85658813,0.932087123) sign=-1 windValue=1 windSum=-1 -1->0 (max=-1) done=1 tiny=0 opp=0
+debugShowSort [2] id=4 line start=2 (1.00829625,1.99792588) end=3 (1,2) sign=-1 windValue=1 windSum=1 0->1 (max=1) done=1 tiny=0 opp=0
+debugShowSort [3] id=3 cubic start=4 (1.00829625,1.99792588) end=3 (0.991754651,2.01644516) sign=1 windValue=1 windSum=1 1->0 (max=1) done=0 tiny=0 opp=0
+findNextOp firstIndex=[0] sign=1
+activeOp op=diff miFrom=1 miTo=1 suFrom=1 suTo=0 result=1
+activeOp op=diff miFrom=1 miTo=1 suFrom=0 suTo=1 result=1
+activeOp op=diff miFrom=1 miTo=1 suFrom=1 suTo=0 result=1
+markDoneBinary id=4 (5,1 1,2) t=0.697145868 [1] (2.21141648,1.69714582) newWindSum=-1 newOppSum=1 oppSum=1 windSum=-1 windValue=1
+findNextOp from:[4] to:[3] start=4 end=3
+bridgeOp current id=4 from=(2.21141648,1.69714582) to=(1.00829625,1.99792588)
+findNextOp debugShowSort contourWinding=0 oppContourWinding=1 sign=-1
+debugShowSort [0] id=3 cubic start=3 (0.991754651,2.01644516) end=4 (1.00829625,1.99792588) sign=-1 windValue=1 windSum=1 0->1 (max=1) done=0 tiny=0 opp=0
+debugShowSort [1] id=3 cubic start=1 (0.991754651,2.01644516) end=0 (1,2) sign=1 windValue=1 windSum=1 1->0 (max=1) done=1 tiny=0 opp=0
+debugShowSort [2] id=3 cubic start=3 (0.991754651,2.01644516) end=2 (0.640381813,2.56467652) sign=1 windValue=1 windSum=-1 0->-1 (max=-1) done=1 tiny=0 opp=0
+debugShowSort [3] id=3 cubic start=1 (0.991754651,2.01644516) end=2 (0.640381813,2.56467652) sign=-1 windValue=1 windSum=-1 -1->0 (max=-1) done=0 tiny=0 opp=0
+findNextOp firstIndex=[0] sign=-1
+activeOp op=diff miFrom=1 miTo=1 suFrom=1 suTo=0 result=1
+activeOp op=diff miFrom=1 miTo=1 suFrom=0 suTo=1 result=1
+activeOp op=diff miFrom=1 miTo=1 suFrom=1 suTo=0 result=1
+markDoneBinary id=3 (1,2 0,4 1,0 5,1) t=0.461521979 [3] (0.991754651,2.01644516) newWindSum=1 newOppSum=1 oppSum=1 windSum=1 windValue=1
+findNextOp from:[3] to:[3] start=1 end=2
+bridgeOp current id=3 from=(1.00829625,1.99792588) to=(0.991754651,2.01644516)
+path.moveTo(2.21141648,1.69714582);
+path.lineTo(1.00829625,1.99792588);
+path.cubicTo(1.00271726,2.0041225, 0.99720329,2.01029587, 0.991754651,2.01644516);
+findNextOp debugShowSort contourWinding=0 oppContourWinding=1 sign=1
+debugShowSort [2] id=3 cubic start=2 (0.640381813,2.56467652) end=1 (0.991754651,2.01644516) sign=1 windValue=1 windSum=-1 0->-1 (max=-1) done=0 tiny=0 opp=0
+debugShowSort [3] id=1 cubic start=1 (0.640381813,2.56467652) end=2 (2.21141648,1.69714582) sign=-1 windValue=1 windSum=1 1->2 (max=2) done=1 tiny=0 opp=1
+debugShowSort [0] id=3 cubic start=2 (0.640381813,2.56467652) end=3 (0.991754651,2.01644516) sign=-1 windValue=1 windSum=-1 -1->0 (max=-1) done=1 tiny=0 opp=0
+debugShowSort [1] id=1 cubic start=1 (0.640381813,2.56467652) end=0 (0,1) sign=1 windValue=1 windSum=1 2->1 (max=2) done=1 tiny=0 opp=1
+findNextOp firstIndex=[2] sign=1
+activeOp op=diff miFrom=1 miTo=1 suFrom=1 suTo=1 result=0
+activeOp op=diff miFrom=1 miTo=1 suFrom=1 suTo=0 result=1
+activeOp op=diff miFrom=1 miTo=1 suFrom=0 suTo=0 result=0
+markDoneBinary id=3 (1,2 0,4 1,0 5,1) t=0.002763735 [1] (0.991754651,2.01644516) newWindSum=-1 newOppSum=1 oppSum=1 windSum=-1 windValue=1
+findNextOp from:[3] to:[3] start=2 end=3
+bridgeOp current id=3 from=(0.991754651,2.01644516) to=(0.640381813,2.56467652)
+path.cubicTo(0.773483634,2.45056915, 0.652775407,2.59388947, 0.640381813,2.56467652);
+</div>
+
</div>
<script type="text/javascript">
var testDivs = [
+ cubicOp35d,
cubicOp31da,
cubicOp31d,
cubicOp28u,
@@ -140,14 +306,48 @@
var SPAN_C_OPP = 19;
var ACTIVE_LINE_SPAN = 1;
-var ACTIVE_QUAD_SPAN = 2;
-var ACTIVE_CUBIC_SPAN = 3;
-var INTERSECT_QUAD_LINE = 4;
-var INTERSECT_QUAD_LINE_2 = 5;
-var INTERSECT_QUAD_LINE_NO = 6;
-var INTERSECT_QUAD = 7;
-var INTERSECT_QUAD_2 = 8;
-var INTERSECT_QUAD_NO = 9;
+var ACTIVE_QUAD_SPAN = ACTIVE_LINE_SPAN + 1;
+var ACTIVE_CUBIC_SPAN = ACTIVE_QUAD_SPAN + 1;
+
+var PATH_MOVETO = ACTIVE_CUBIC_SPAN + 1;
+var PATH_LINETO = PATH_MOVETO + 1;
+var PATH_QUADTO = PATH_LINETO + 1;
+var PATH_CUBICTO = PATH_QUADTO + 1;
+var PATH_CLOSE = PATH_CUBICTO + 1;
+
+var INTERSECT_LINE = PATH_CLOSE + 1;
+var INTERSECT_LINE_2 = INTERSECT_LINE + 1;
+var INTERSECT_LINE_NO = INTERSECT_LINE_2 + 1;
+var INTERSECT_QUAD_LINE = INTERSECT_LINE_NO + 1;
+var INTERSECT_QUAD_LINE_2 = INTERSECT_QUAD_LINE + 1;
+var INTERSECT_QUAD_LINE_NO = INTERSECT_QUAD_LINE_2 + 1;
+var INTERSECT_QUAD = INTERSECT_QUAD_LINE_NO + 1;
+var INTERSECT_QUAD_2 = INTERSECT_QUAD + 1;
+var INTERSECT_QUAD_NO = INTERSECT_QUAD_2 + 1;
+var INTERSECT_SELF_CUBIC = INTERSECT_QUAD_NO + 1;
+var INTERSECT_SELF_CUBIC_NO = INTERSECT_SELF_CUBIC + 1;
+var INTERSECT_CUBIC_LINE = INTERSECT_SELF_CUBIC_NO + 1;
+var INTERSECT_CUBIC_LINE_2 = INTERSECT_CUBIC_LINE + 1;
+var INTERSECT_CUBIC_LINE_3 = INTERSECT_CUBIC_LINE_2 + 1;
+var INTERSECT_CUBIC_LINE_NO = INTERSECT_CUBIC_LINE_3 + 1;
+// FIXME: add cubic/quad
+var INTERSECT_CUBIC = INTERSECT_CUBIC_LINE_NO + 1;
+var INTERSECT_CUBIC_2 = INTERSECT_CUBIC + 1;
+var INTERSECT_CUBIC_3 = INTERSECT_CUBIC_2 + 1;
+var INTERSECT_CUBIC_4 = INTERSECT_CUBIC_3 + 1;
+// FIXME: add cubic 5- 9
+var INTERSECT_CUBIC_NO = INTERSECT_CUBIC_4 + 1;
+
+var SORT_LINE = INTERSECT_CUBIC_NO + 1;
+var SORT_QUAD = SORT_LINE + 1;
+var SORT_CUBIC = SORT_QUAD + 1;
+
+var REC_TYPE_UNKNOWN = -1;
+var REC_TYPE_PATH = 0;
+var REC_TYPE_SECT = 1;
+var REC_TYPE_ACTIVE = 2;
+var REC_TYPE_ADD = 3;
+var REC_TYPE_SORT = 4;
function strs_to_nums(strs) {
var result = [];
@@ -215,7 +415,9 @@
var result = strs_to_nums(strs);
array.push(id);
array.push(result);
+ return true;
}
+ return false;
}
// FIXME: add cubic support
@@ -249,6 +451,150 @@
}
}
+function construct_regexp2(pattern) {
+ var escape = pattern.replace(/[-/\\^$*+?.()|[\]{}]/g, '\\$&');
+ escape = escape.replace(/CUBIC_VAL/g, "\\(P_VAL P_VAL P_VAL P_VAL\\)");
+ escape = escape.replace(/QUAD_VAL/g, "\\(P_VAL P_VAL P_VAL\\)");
+ escape = escape.replace(/LINE_VAL/g, "\\(P_VAL P_VAL\\)");
+ escape = escape.replace(/PT_VAL/g, "\\(P_VAL\\)");
+ escape = escape.replace(/P_VAL/g, "(\\d+\\.?\\d*),(\\d+\\.?\\d*)");
+ escape = escape.replace(/T_VAL/g, "(\\d+\\.?\\d*e?-?\\d*)");
+ escape = escape.replace(/IDX/g, "(\\d+)");
+ escape = escape.replace(/NUM/g, "(-?\\d+)");
+ escape = escape.replace(/OPT/g, "(\\?|-?\\d+)");
+ return new RegExp(escape, 'i');
+}
+
+function construct_regexp2c(pattern) {
+ var escape = pattern.replace(/[-/\\^$*+?.()|[\]{}]/g, '\\$&');
+ escape = escape.replace(/CUBIC_VAL/g, "\\{\\{P_VAL\\}, \\{P_VAL\\}, \\{P_VAL\\}, \\{P_VAL\\}\\}");
+ escape = escape.replace(/QUAD_VAL/g, "\\{\\{P_VAL\\}, \\{P_VAL\\}, \\{P_VAL\\}\\}");
+ escape = escape.replace(/LINE_VAL/g, "\\{\\{P_VAL\\}, \\{P_VAL\\}\\}");
+ escape = escape.replace(/PT_VAL/g, "\\{\\{P_VAL\\}\\}");
+ escape = escape.replace(/P_VAL/g, "(\\d+\\.?\\d*),(\\d+\\.?\\d*)");
+ escape = escape.replace(/T_VAL/g, "(\\d+\\.?\\d*e?-?\\d*)");
+ escape = escape.replace(/IDX/g, "(\\d+)");
+ escape = escape.replace(/NUM/g, "(-?\\d+)");
+ escape = escape.replace(/OPT/g, "(\\?|-?\\d+)");
+ return new RegExp(escape, 'i');
+}
+
+function match_regexp(str, lineNo, array, id, pattern) {
+ var regex = construct_regexp2(pattern);
+ if (filter_str_by(id, str, regex, array)) {
+ return true;
+ }
+ regex = construct_regexp2c(pattern);
+ return filter_str_by(id, str, regex, array);
+}
+
+function parse_all(test, title) {
+ var lines = test.match(/[^\r\n]+/g);
+ var records = []; // a rec can be the original paths, a set of intersections, a set of active spans, a sort, or a path add
+ var record = [];
+ var recType = REC_TYPE_UNKNOWN;
+ for (var lineNo in lines) {
+ var line = lines[lineNo];
+ var type = line.lastIndexOf("debugShowSort", 0) === 0 ? REC_TYPE_SORT
+ : line.lastIndexOf("debugShowActiveSpans", 0) === 0 ? REC_TYPE_ACTIVE
+ : line.lastIndexOf("debugShow", 0) === 0 ? REC_TYPE_SECT
+ : line.lastIndexOf("path.", 0) === 0 ? REC_TYPE_ADD
+ : line.lastIndexOf("{{", 0) === 0 ? REC_TYPE_PATH
+ : REC_TYPE_UNKNOWN;
+ if (recType != type) {
+ if (recType != REC_TYPE_UNKNOWN) {
+ records.push(recType);
+ records.push(lineNo);
+ records.push(record);
+ }
+ record = [];
+ recType = type;
+ }
+ var found = false;
+ switch (recType) {
+ case REC_TYPE_ACTIVE:
+ found = match_regexp(line, lineNo, record, ACTIVE_LINE_SPAN, "debugShowActiveSpans" +
+" id=IDX LINE_VAL t=T_VAL PT_VAL tEnd=T_VAL other=IDX otherT=T_VAL otherIndex=IDX windSum=OPT windValue=IDX oppValue=IDX"
+ ) || match_regexp(line, lineNo, record, ACTIVE_QUAD_SPAN, "debugShowActiveSpans" +
+" id=IDX QUAD_VAL t=T_VAL PT_VAL tEnd=T_VAL other=IDX otherT=T_VAL otherIndex=IDX windSum=OPT windValue=IDX oppValue=IDX"
+ ) || match_regexp(line, lineNo, record, ACTIVE_CUBIC_SPAN, "debugShowActiveSpans" +
+" id=IDX CUBIC_VAL t=T_VAL PT_VAL tEnd=T_VAL other=IDX otherT=T_VAL otherIndex=IDX windSum=OPT windValue=IDX oppValue=IDX"
+ );
+ break;
+ case REC_TYPE_ADD:
+ found = match_regexp(line, lineNo, record, PATH_MOVETO, "path.moveToPT_VAL;"
+ ) || match_regexp(line, lineNo, record, PATH_LINETO, "path.lineTo(P_VAL);"
+ ) || match_regexp(line, lineNo, record, PATH_QUADTO, "path.quadTo(P_VAL, P_VAL);"
+ ) || match_regexp(line, lineNo, record, PATH_CUBICTO, "path.cubicTo(P_VAL, P_VAL, P_VAL);"
+ ) || match_regexp(line, lineNo, record, PATH_CLOSE, "path.close();"
+ );
+ break;
+ case REC_TYPE_SECT:
+ found = match_regexp(line, lineNo, record, INTERSECT_LINE, "debugShowLineIntersection" +
+" wtTs[0]=T_VAL LINE_VAL PT_VAL wnTs[0]=T_VAL LINE_VAL"
+ ) || match_regexp(line, lineNo, record, INTERSECT_LINE_2, "debugShowLineIntersection" +
+" wtTs[0]=T_VAL LINE_VAL PT_VAL wtTs[1]=T_VAL PT_VAL wnTs[0]=T_VAL LINE_VAL wnTs[1]=T_VAL"
+ ) || match_regexp(line, lineNo, record, INTERSECT_LINE_NO, "debugShowLineIntersection" +
+" no intersect LINE_VAL LINE_VAL"
+ ) || match_regexp(line, lineNo, record, INTERSECT_QUAD_LINE, "debugShowQuadLineIntersection" +
+" wtTs[0]=T_VAL QUAD_VAL PT_VAL wnTs[0]=T_VAL LINE_VAL"
+ ) || match_regexp(line, lineNo, record, INTERSECT_QUAD_LINE_2, "debugShowQuadLineIntersection" +
+" wtTs[0]=T_VAL QUAD_VAL PT_VAL wtTs[1]=T_VAL PT_VAL wnTs[0]=T_VAL LINE_VAL wnTs[1]=T_VAL"
+ ) || match_regexp(line, lineNo, record, INTERSECT_QUAD_LINE_NO, "debugShowQuadLineIntersection" +
+" no intersect QUAD_VAL LINE_VAL"
+ ) || match_regexp(line, lineNo, record, INTERSECT_QUAD, "debugShowQuadIntersection" +
+" wtTs[0]=T_VAL QUAD_VAL PT_VAL wnTs[0]=T_VAL QUAD_VAL"
+ ) || match_regexp(line, lineNo, record, INTERSECT_QUAD_2, "debugShowQuadIntersection" +
+" wtTs[0]=T_VAL QUAD_VAL PT_VAL wtTs[1]=T_VAL wnTs[0]=T_VAL QUAD_VAL wnTs[1]=T_VAL"
+ ) || match_regexp(line, lineNo, record, INTERSECT_QUAD_NO, "debugShowQuadIntersection" +
+" no intersect QUAD_VAL QUAD_VAL"
+ ) || match_regexp(line, lineNo, record, INTERSECT_SELF_CUBIC, "debugShowCubicIntersection" +
+" wtTs[0]=T_VAL CUBIC_VAL PT_VAL wtTs[1]=T_VAL"
+ ) || match_regexp(line, lineNo, record, INTERSECT_SELF_CUBIC_NO, "debugShowCubicIntersection" +
+" no self intersect CUBIC_VAL"
+ ) || match_regexp(line, lineNo, record, INTERSECT_CUBIC_LINE, "debugShowCubicLineIntersection" +
+" wtTs[0]=T_VAL CUBIC_VAL PT_VAL wnTs[0]=T_VAL LINE_VAL"
+ ) || match_regexp(line, lineNo, record, INTERSECT_CUBIC_LINE_2, "debugShowCubicLineIntersection" +
+" wtTs[0]=T_VAL CUBIC_VAL PT_VAL wtTs[1]=T_VAL PT_VAL wnTs[0]=T_VAL LINE_VAL wnTs[1]=T_VAL"
+ ) || match_regexp(line, lineNo, record, INTERSECT_CUBIC_LINE_3, "debugShowCubicLineIntersection" +
+" wtTs[0]=T_VAL CUBIC_VAL PT_VAL wtTs[1]=T_VAL PT_VAL wtTs[2]=T_VAL PT_VAL wnTs[0]=T_VAL LINE_VAL wnTs[1]=T_VAL wnTs[2]=T_VAL"
+ ) || match_regexp(line, lineNo, record, INTERSECT_CUBIC_LINE_NO, "debugShowCubicLineIntersection" +
+" no intersect CUBIC_VAL LINE_VAL"
+ ) || match_regexp(line, lineNo, record, INTERSECT_CUBIC, "debugShowCubicIntersection" +
+" wtTs[0]=T_VAL CUBIC_VAL PT_VAL wnTs[0]=T_VAL CUBIC_VAL"
+ ) || match_regexp(line, lineNo, record, INTERSECT_CUBIC_2, "debugShowCubicIntersection" +
+" wtTs[0]=T_VAL CUBIC_VAL PT_VAL wtTs[1]=T_VAL PT_VAL wnTs[0]=T_VAL CUBIC_VAL wnTs[1]=T_VAL"
+ ) || match_regexp(line, lineNo, record, INTERSECT_CUBIC_3, "debugShowCubicIntersection" +
+" wtTs[0]=T_VAL CUBIC_VAL PT_VAL wtTs[1]=T_VAL PT_VAL wtTs[2]=T_VAL PT_VAL wnTs[0]=T_VAL CUBIC_VAL wnTs[1]=T_VAL wnTs[2]=T_VAL"
+ ) || match_regexp(line, lineNo, record, INTERSECT_CUBIC_4, "debugShowCubicIntersection" +
+" wtTs[0]=T_VAL CUBIC_VAL PT_VAL wtTs[1]=T_VAL PT_VAL wtTs[2]=T_VAL PT_VAL wtTs[3]=T_VAL PT_VAL wnTs[0]=T_VAL CUBIC_VAL wnTs[1]=T_VAL wnTs[2]=T_VAL wnTs[3]=T_VAL"
+ ) || match_regexp(line, lineNo, record, INTERSECT_CUBIC_NO, "debugShowCubicIntersection" +
+" no intersect CUBIC_VAL CUBIC_VAL"
+ );
+ break;
+ case REC_TYPE_SORT:
+ found = match_regexp(line, lineNo, record, SORT_LINE, "debugShowSort" +
+" [IDX] id=IDX line start=IDX PT_VAL end=IDX PT_VAL sign=NUM windValue=IDX windSum=OPT NUM->NUM (max=NUM) done=IDX tiny=IDX opp=IDX"
+ ) || match_regexp(line, lineNo, record, SORT_QUAD, "debugShowSort" +
+" [IDX] id=IDX quad start=IDX PT_VAL end=IDX PT_VAL sign=NUM windValue=IDX windSum=OPT NUM->NUM (max=NUM) done=IDX tiny=IDX opp=IDX"
+ ) || match_regexp(line, lineNo, record, SORT_CUBIC, "debugShowSort" +
+" [IDX] id=IDX cubic start=IDX PT_VAL end=IDX PT_VAL sign=NUM windValue=IDX windSum=OPT NUM->NUM (max=NUM) done=IDX tiny=IDX opp=IDX"
+ );
+ break;
+ case REC_TYPE_UNKNOWN:
+ found = true;
+ break;
+ }
+ if (!found) {
+ console.log(line + " [" + lineNo + "] of type " + type + " not found");
+ }
+ }
+ if (records.length >= 1) {
+ tests.push(records);
+ testTitles.push(title);
+ }
+}
+
function init(test) {
var canvas = document.getElementById('canvas');
if (!canvas.getContext) return;
@@ -902,6 +1248,7 @@
for (i = 0; i < testDivs.length; ++i) {
var title = testDivs[i].id.toString();
var str = testDivs[i].firstChild.data;
+ parse_all(str, title);
parse_debugShowActiveSpans(str, title);
parse_intersections(str, title);
}
diff --git a/experimental/Intersection/op.htm b/experimental/Intersection/op.htm
index 199a9df..267fbec 100644
--- a/experimental/Intersection/op.htm
+++ b/experimental/Intersection/op.htm
@@ -3721,11 +3721,59 @@
pathB.close();
</div>
+<div id="cubicOp32d">
+ path.setFillType(SkPath::kWinding_FillType);
+ path.moveTo(0,1);
+ path.cubicTo(1,2, 6,0, 3,1);
+ path.close();
+ pathB.setFillType(SkPath::kWinding_FillType);
+ pathB.moveTo(0,6);
+ pathB.cubicTo(1,3, 1,0, 2,1);
+ pathB.close();
+</div>
+
+<div id="cubicOp33i">
+ path.setFillType(SkPath::kWinding_FillType);
+ path.moveTo(0,1);
+ path.cubicTo(1,2, 6,0, 3,1);
+ path.close();
+ pathB.setFillType(SkPath::kWinding_FillType);
+ pathB.moveTo(0,6);
+ pathB.cubicTo(1,3, 1,0, 2,1);
+ pathB.close();
+</div>
+
+<div id="cubicOp34d">
+ path.setFillType(SkPath::kWinding_FillType);
+ path.moveTo(0,1);
+ path.cubicTo(3,5, 2,1, 3,1);
+ path.close();
+ pathB.setFillType(SkPath::kWinding_FillType);
+ pathB.moveTo(1,2);
+ pathB.cubicTo(1,3, 1,0, 5,3);
+ pathB.close();
+</div>
+
+<div id="cubicOp35d">
+ path.setFillType(SkPath::kWinding_FillType);
+ path.moveTo(0,1);
+ path.cubicTo(1,5, 2,1, 4,0);
+ path.close();
+ pathB.setFillType(SkPath::kWinding_FillType);
+ pathB.moveTo(1,2);
+ pathB.cubicTo(0,4, 1,0, 5,1);
+ pathB.close();
+</div>
+
</div>
<script type="text/javascript">
var testDivs = [
+ cubicOp35d,
+ cubicOp34d,
+ cubicOp33i,
+ cubicOp32d,
cubicOp31d,
cubicOp30d,
cubicOp29d,
@@ -4267,11 +4315,11 @@
calcXY();
var num = mouseX.toFixed(3) + ", " + mouseY.toFixed(3);
ctx.beginPath();
- ctx.rect(300,100,200,10);
+ ctx.rect(300,0,72,9);
ctx.fillStyle="white";
ctx.fill();
ctx.fillStyle="black";
- ctx.fillText(num, 300, 108);
+ ctx.fillText(num, 300, 7);
}
function handleMouseClick() {
diff --git a/experimental/Intersection/qc.htm b/experimental/Intersection/qc.htm
index db77fa4..e3075d1 100644
--- a/experimental/Intersection/qc.htm
+++ b/experimental/Intersection/qc.htm
@@ -2086,11 +2086,48 @@
{{2.79472921,1.73568666}, {3.36246373,1.21251209}, {5,2}},
</div>
+<div id="cubicOp34d">
+{{x = 1.0097960937999808, y = 2.2108396209439607}, {x = 1, y = 2.1969085233712229}, {x = 1, y = 2.1347920612232207}, {x = 1, y = 2}}
+{{x = 1.0097960937999808, y = 2.2108396209439607}, {x = 1.0242251996917398, y = 2.2313593593386498}, {x = 1.0599075827658746, y = 2.1473377437648784}, {x = 1.1481481481481481, y = 2.0370370370370372}}
+{{x = 1.0097960958786989, y = 2.2108396260650962}, {x = 0.73607693096853644, y = 1.9329854848088734}, {x = 0.40437628284615079, y = 1.5391683771282005}, {x = 0, y = 1}}
+{{x = 1.0097960958786989, y = 2.2108396260650962}, {x = 1.8566294376993437, y = 3.0704657726520206}, {x = 2.1484860084122528, y = 2.8201383770234716}, {x = 2.320499529631658, y = 2.3301248824079162}}
+</div>
+
+<div id="cubicOp34da">
+{{x = 1.0097960937999808, y = 2.2108396209439607}, {x = 1, y = 2.1969085233712229}, {x = 1, y = 2.1347920612232207}, {x = 1, y = 2}}
+{{x = 1.0097960937999808, y = 2.2108396209439607}, {x = 1.0242251996917398, y = 2.2313593593386498}, {x = 1.0599075827658746, y = 2.1473377437648784}, {x = 1.1481481481481481, y = 2.0370370370370372}}
+</div>
+
+<div id="cubicOp34db">
+{{1,2}, {1,3}, {1,0}, {5,3}},
+{{0,1}, {3,5}, {2,1}, {3,1}},
+
+ {{1,2}, {0.984375,2.3359375}, {1.0625,2.15625}},
+ {{1.0625,2.15625}, {1.140625,1.9765625}, {1.5,1.75}},
+ {{1.5,1.75}, {1.859375,1.5234375}, {2.6875,1.71875}},
+ {{2.6875,1.71875}, {3.515625,1.9140625}, {5,3}},
+
+ {{0,1}, {0.983539095,2.30041152}, {1.47325103,2.61316872}},
+ {{1.47325103,2.61316872}, {1.96296296,2.92592593}, {2.1563786,2.64609053}},
+ {{2.1563786,2.64609053}, {2.34979424,2.36625514}, {2.44444444,1.88888889}},
+ {{2.44444444,1.88888889}, {2.52083333,1.54166667}, {2.63888889,1.27777778}},
+ {{2.63888889,1.27777778}, {2.75694444,1.01388889}, {3,1}},
+</div>
+
+<div id="quadOp34d">
+ {{1,2}, {0.984375,2.3359375}, {1.0625,2.15625}},
+ {{0,1}, {0.983539095,2.30041152}, {1.47325103,2.61316872}},
+</div>
+
</div>
<script type="text/javascript">
var testDivs = [
+ quadOp34d,
+ cubicOp34db,
+ cubicOp34d,
+ cubicOp34da,
quadOp30d,
cubicOp30d,
quadOp27d,