shape ops work in progress
git-svn-id: http://skia.googlecode.com/svn/trunk@7758 2bbb7eff-a529-9590-31e7-b0007b416f81
diff --git a/experimental/Intersection/CubicBezierClip_Test.cpp b/experimental/Intersection/CubicBezierClip_Test.cpp
index 1a9092f..9133980 100644
--- a/experimental/Intersection/CubicBezierClip_Test.cpp
+++ b/experimental/Intersection/CubicBezierClip_Test.cpp
@@ -13,8 +13,10 @@
const Cubic& cubic1 = tests[index][0];
const Cubic& cubic2 = tests[index][1];
Cubic reduce1, reduce2;
- int order1 = reduceOrder(cubic1, reduce1, kReduceOrder_NoQuadraticsAllowed);
- int order2 = reduceOrder(cubic2, reduce2, kReduceOrder_NoQuadraticsAllowed);
+ int order1 = reduceOrder(cubic1, reduce1, kReduceOrder_NoQuadraticsAllowed,
+ kReduceOrder_TreatAsFill);
+ int order2 = reduceOrder(cubic2, reduce2, kReduceOrder_NoQuadraticsAllowed,
+ kReduceOrder_TreatAsFill);
if (order1 < 4) {
SkDebugf("%s [%d] cubic1 order=%d\n", __FUNCTION__, (int) index, order1);
}
diff --git a/experimental/Intersection/CubicConvexHull.cpp b/experimental/Intersection/CubicConvexHull.cpp
index 3be8c21..137b0d6 100644
--- a/experimental/Intersection/CubicConvexHull.cpp
+++ b/experimental/Intersection/CubicConvexHull.cpp
@@ -54,11 +54,11 @@
sub_divide(cubic1, minT1, maxT1, intersections.swapped() ? larger : smaller);
sub_divide(cubic2, minT2, maxT2, intersections.swapped() ? smaller : larger);
Cubic smallResult;
- if (reduceOrder(smaller, smallResult,
- kReduceOrder_NoQuadraticsAllowed) <= 2) {
+ if (reduceOrder(smaller, smallResult, kReduceOrder_NoQuadraticsAllowed,
+ kReduceOrder_TreatAsFill) <= 2) {
Cubic largeResult;
- if (reduceOrder(larger, largeResult,
- kReduceOrder_NoQuadraticsAllowed) <= 2) {
+ if (reduceOrder(larger, largeResult, kReduceOrder_NoQuadraticsAllowed,
+ kReduceOrder_TreatAsFill) <= 2) {
const _Line& smallLine = (const _Line&) smallResult;
const _Line& largeLine = (const _Line&) largeResult;
Intersections lineTs;
diff --git a/experimental/Intersection/CubicIntersection.cpp b/experimental/Intersection/CubicIntersection.cpp
index f25a046..02a39d6 100644
--- a/experimental/Intersection/CubicIntersection.cpp
+++ b/experimental/Intersection/CubicIntersection.cpp
@@ -17,6 +17,7 @@
#endif
#define DEBUG_QUAD_PART 0
+#define SWAP_TOP_DEBUG 0
static int quadPart(const Cubic& cubic, double tStart, double tEnd, Quadratic& simple) {
Cubic part;
@@ -25,7 +26,7 @@
demote_cubic_to_quad(part, quad);
// FIXME: should reduceOrder be looser in this use case if quartic is going to blow up on an
// extremely shallow quadratic?
- int order = reduceOrder(quad, simple);
+ int order = reduceOrder(quad, simple, kReduceOrder_TreatAsFill);
#if DEBUG_QUAD_PART
SkDebugf("%s cubic=(%1.17g,%1.17g %1.17g,%1.17g %1.17g,%1.17g %1.17g,%1.17g) t=(%1.17g,%1.17g)\n",
__FUNCTION__, cubic[0].x, cubic[0].y, cubic[1].x, cubic[1].y, cubic[2].x, cubic[2].y,
@@ -148,7 +149,9 @@
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
@@ -444,6 +447,25 @@
return result;
}
+const double CLOSE_ENOUGH = 0.001;
+
+static bool closeStart(const Cubic& cubic, int cubicIndex, Intersections& i, _Point& pt) {
+ if (i.fT[cubicIndex][0] != 0 || i.fT[cubicIndex][1] > CLOSE_ENOUGH) {
+ return false;
+ }
+ pt = xy_at_t(cubic, (i.fT[cubicIndex][0] + i.fT[cubicIndex][1]) / 2);
+ return true;
+}
+
+static bool closeEnd(const Cubic& cubic, int cubicIndex, Intersections& i, _Point& pt) {
+ int last = i.used() - 1;
+ if (i.fT[cubicIndex][last] != 1 || i.fT[cubicIndex][last - 1] < 1 - CLOSE_ENOUGH) {
+ return false;
+ }
+ pt = xy_at_t(cubic, (i.fT[cubicIndex][last] + i.fT[cubicIndex][last - 1]) / 2);
+ return true;
+}
+
bool intersect3(const Cubic& c1, const Cubic& c2, Intersections& i) {
bool result = intersect3(c1, 0, 1, c2, 0, 1, 1, i);
// FIXME: pass in cached bounds from caller
@@ -456,6 +478,21 @@
result |= intersectEnd(c2, false, c1, c1Bounds, i);
result |= intersectEnd(c2, true, c1, c1Bounds, i);
i.swap();
+ // If an end point and a second point very close to the end is returned, the second
+ // point may have been detected because the approximate quads
+ // intersected at the end and close to it. Verify that the second point is valid.
+ if (i.used() <= 1 || i.coincidentUsed()) {
+ return result;
+ }
+ _Point pt[2];
+ if (closeStart(c1, 0, i, pt[0]) && closeStart(c2, 1, i, pt[1])
+ && pt[0].approximatelyEqual(pt[1])) {
+ i.removeOne(1);
+ }
+ if (closeEnd(c1, 0, i, pt[0]) && closeEnd(c2, 1, i, pt[1])
+ && pt[0].approximatelyEqual(pt[1])) {
+ i.removeOne(i.used() - 2);
+ }
return result;
}
diff --git a/experimental/Intersection/CubicIntersection_Test.cpp b/experimental/Intersection/CubicIntersection_Test.cpp
index bdbf3de..9dea332 100644
--- a/experimental/Intersection/CubicIntersection_Test.cpp
+++ b/experimental/Intersection/CubicIntersection_Test.cpp
@@ -18,8 +18,10 @@
const Cubic& cubic1 = tests[index][0];
const Cubic& cubic2 = tests[index][1];
Cubic reduce1, reduce2;
- int order1 = reduceOrder(cubic1, reduce1, kReduceOrder_NoQuadraticsAllowed);
- int order2 = reduceOrder(cubic2, reduce2, kReduceOrder_NoQuadraticsAllowed);
+ int order1 = reduceOrder(cubic1, reduce1, kReduceOrder_NoQuadraticsAllowed,
+ kReduceOrder_TreatAsFill);
+ int order2 = reduceOrder(cubic2, reduce2, kReduceOrder_NoQuadraticsAllowed,
+ kReduceOrder_TreatAsFill);
if (order1 < 4) {
printf("%s [%d] cubic1 order=%d\n", __FUNCTION__, (int) index, order1);
continue;
@@ -131,6 +133,13 @@
const size_t testSetCount = sizeof(testSet) / sizeof(testSet[0]);
+static const Cubic newTestSet[] = {
+{{0,2},{0,1},{3,0},{1,0}},
+{{0,3},{0,1},{2,0},{1,0}},
+};
+
+const size_t newTestSetCount = sizeof(newTestSet) / sizeof(newTestSet[0]);
+
static void oneOff(const Cubic& cubic1, const Cubic& cubic2) {
SkTDArray<Quadratic> quads1;
cubic_to_quadratics(cubic1, calcPrecision(cubic1), quads1);
@@ -295,6 +304,16 @@
oneOff(12, 14);
}
+static void newOneOff(int outer, int inner) {
+ const Cubic& cubic1 = newTestSet[outer];
+ const Cubic& cubic2 = newTestSet[inner];
+ oneOff3(cubic1, cubic2);
+}
+
+void CubicIntersection_NewOneOffTest() {
+ newOneOff(0, 1);
+}
+
static void oneOffTests() {
for (size_t outer = 0; outer < testSetCount - 1; ++outer) {
for (size_t inner = outer + 1; inner < testSetCount; ++inner) {
@@ -522,11 +541,11 @@
}
void CubicIntersection_IntersectionFinder() {
- const Cubic& cubic1 = testSet[2];
- const Cubic& cubic2 = testSet[7];
+ const Cubic& cubic1 = newTestSet[0];
+ const Cubic& cubic2 = newTestSet[1];
- double t1Seed = 0.254;
- double t2Seed = 0.245;
+ double t1Seed = 0.99;
+ double t2Seed = 0.99;
double t1Step = 0.01;
double t2Step = 0.01;
_Point t1[3], t2[3];
diff --git a/experimental/Intersection/CubicReduceOrder.cpp b/experimental/Intersection/CubicReduceOrder.cpp
index bd1356a..f7c0c12 100644
--- a/experimental/Intersection/CubicReduceOrder.cpp
+++ b/experimental/Intersection/CubicReduceOrder.cpp
@@ -24,10 +24,13 @@
return 1;
}
-static int vertical_line(const Cubic& cubic, Cubic& reduction) {
+static int vertical_line(const Cubic& cubic, ReduceOrder_Styles reduceStyle, Cubic& reduction) {
double tValues[2];
reduction[0] = cubic[0];
reduction[1] = cubic[3];
+ if (reduceStyle == kReduceOrder_TreatAsFill) {
+ return 2;
+ }
int smaller = reduction[1].y > reduction[0].y;
int larger = smaller ^ 1;
int roots = findExtrema(cubic[0].y, cubic[1].y, cubic[2].y, cubic[3].y, tValues);
@@ -44,10 +47,13 @@
return 2;
}
-static int horizontal_line(const Cubic& cubic, Cubic& reduction) {
+static int horizontal_line(const Cubic& cubic, ReduceOrder_Styles reduceStyle, Cubic& reduction) {
double tValues[2];
reduction[0] = cubic[0];
reduction[1] = cubic[3];
+ if (reduceStyle == kReduceOrder_TreatAsFill) {
+ return 2;
+ }
int smaller = reduction[1].x > reduction[0].x;
int larger = smaller ^ 1;
int roots = findExtrema(cubic[0].x, cubic[1].x, cubic[2].x, cubic[3].x, tValues);
@@ -85,8 +91,8 @@
return 3;
}
-static int check_linear(const Cubic& cubic, Cubic& reduction,
- int minX, int maxX, int minY, int maxY) {
+static int check_linear(const Cubic& cubic, ReduceOrder_Styles reduceStyle,
+ int minX, int maxX, int minY, int maxY, Cubic& reduction) {
int startIndex = 0;
int endIndex = 3;
while (cubic[startIndex].approximatelyEqual(cubic[endIndex])) {
@@ -102,6 +108,9 @@
// four are colinear: return line formed by outside
reduction[0] = cubic[0];
reduction[1] = cubic[3];
+ if (reduceStyle == kReduceOrder_TreatAsFill) {
+ return 2;
+ }
int sameSide1;
int sameSide2;
bool useX = cubic[maxX].x - cubic[minX].x >= cubic[maxY].y - cubic[minY].y;
@@ -185,7 +194,8 @@
// note that three points in a line doesn't simplify a cubic
// look for approximation with single quadratic
// save approximation with multiple quadratics for later
-int reduceOrder(const Cubic& cubic, Cubic& reduction, ReduceOrder_Flags allowQuadratics) {
+int reduceOrder(const Cubic& cubic, Cubic& reduction, ReduceOrder_Quadratics allowQuadratics,
+ ReduceOrder_Styles reduceStyle) {
int index, minX, maxX, minY, maxY;
int minXSet, minYSet;
minX = maxX = minY = maxY = 0;
@@ -226,16 +236,17 @@
if (minYSet == 0xF) { // return 1 if all four are coincident
return coincident_line(cubic, reduction);
}
- return vertical_line(cubic, reduction);
+ return vertical_line(cubic, reduceStyle, reduction);
}
if (minYSet == 0xF) { // test for horizontal line
- return horizontal_line(cubic, reduction);
+ return horizontal_line(cubic, reduceStyle, reduction);
}
- int result = check_linear(cubic, reduction, minX, maxX, minY, maxY);
+ int result = check_linear(cubic, reduceStyle, minX, maxX, minY, maxY, reduction);
if (result) {
return result;
}
- if (allowQuadratics && (result = check_quadratic(cubic, reduction))) {
+ if (allowQuadratics == kReduceOrder_QuadraticsAllowed
+ && (result = check_quadratic(cubic, reduction))) {
return result;
}
memcpy(reduction, cubic, sizeof(Cubic));
diff --git a/experimental/Intersection/CubicReduceOrder_Test.cpp b/experimental/Intersection/CubicReduceOrder_Test.cpp
index 1011fab..79b3428 100644
--- a/experimental/Intersection/CubicReduceOrder_Test.cpp
+++ b/experimental/Intersection/CubicReduceOrder_Test.cpp
@@ -46,49 +46,56 @@
for (index = firstPointDegeneratesTest; index < pointDegenerates_count; ++index) {
const Cubic& cubic = pointDegenerates[index];
- order = reduceOrder(cubic, reduce, kReduceOrder_QuadraticsAllowed);
+ order = reduceOrder(cubic, reduce, kReduceOrder_QuadraticsAllowed,
+ kReduceOrder_TreatAsFill);
if (order != 1) {
SkDebugf("[%d] pointDegenerates order=%d\n", (int) index, order);
}
}
for (index = firstNotPointDegeneratesTest; index < notPointDegenerates_count; ++index) {
const Cubic& cubic = notPointDegenerates[index];
- order = reduceOrder(cubic, reduce, kReduceOrder_QuadraticsAllowed);
+ order = reduceOrder(cubic, reduce, kReduceOrder_QuadraticsAllowed,
+ kReduceOrder_TreatAsFill);
if (order == 1) {
SkDebugf("[%d] notPointDegenerates order=%d\n", (int) index, order);
}
}
for (index = firstLinesTest; index < lines_count; ++index) {
const Cubic& cubic = lines[index];
- order = reduceOrder(cubic, reduce, kReduceOrder_QuadraticsAllowed);
+ order = reduceOrder(cubic, reduce, kReduceOrder_QuadraticsAllowed,
+ kReduceOrder_TreatAsFill);
if (order != 2) {
SkDebugf("[%d] lines order=%d\n", (int) index, order);
}
}
for (index = firstNotLinesTest; index < notLines_count; ++index) {
const Cubic& cubic = notLines[index];
- order = reduceOrder(cubic, reduce, kReduceOrder_QuadraticsAllowed);
+ order = reduceOrder(cubic, reduce, kReduceOrder_QuadraticsAllowed,
+ kReduceOrder_TreatAsFill);
if (order == 2) {
SkDebugf("[%d] notLines order=%d\n", (int) index, order);
}
}
for (index = firstModEpsilonTest; index < modEpsilonLines_count; ++index) {
const Cubic& cubic = modEpsilonLines[index];
- order = reduceOrder(cubic, reduce, kReduceOrder_QuadraticsAllowed);
+ order = reduceOrder(cubic, reduce, kReduceOrder_QuadraticsAllowed,
+ kReduceOrder_TreatAsFill);
if (order == 2) {
SkDebugf("[%d] line mod by epsilon order=%d\n", (int) index, order);
}
}
for (index = firstLessEpsilonTest; index < lessEpsilonLines_count; ++index) {
const Cubic& cubic = lessEpsilonLines[index];
- order = reduceOrder(cubic, reduce, kReduceOrder_QuadraticsAllowed);
+ order = reduceOrder(cubic, reduce, kReduceOrder_QuadraticsAllowed,
+ kReduceOrder_TreatAsFill);
if (order != 2) {
SkDebugf("[%d] line less by epsilon/2 order=%d\n", (int) index, order);
}
}
for (index = firstNegEpsilonTest; index < negEpsilonLines_count; ++index) {
const Cubic& cubic = negEpsilonLines[index];
- order = reduceOrder(cubic, reduce, kReduceOrder_QuadraticsAllowed);
+ order = reduceOrder(cubic, reduce, kReduceOrder_QuadraticsAllowed,
+ kReduceOrder_TreatAsFill);
if (order != 2) {
SkDebugf("[%d] line neg by epsilon/2 order=%d\n", (int) index, order);
}
@@ -97,7 +104,8 @@
const Quadratic& quad = quadraticLines[index];
Cubic cubic;
quad_to_cubic(quad, cubic);
- order = reduceOrder(cubic, reduce, kReduceOrder_QuadraticsAllowed);
+ order = reduceOrder(cubic, reduce, kReduceOrder_QuadraticsAllowed,
+ kReduceOrder_TreatAsFill);
if (order != 2) {
SkDebugf("[%d] line quad order=%d\n", (int) index, order);
}
@@ -106,7 +114,8 @@
const Quadratic& quad = quadraticModEpsilonLines[index];
Cubic cubic;
quad_to_cubic(quad, cubic);
- order = reduceOrder(cubic, reduce, kReduceOrder_QuadraticsAllowed);
+ order = reduceOrder(cubic, reduce, kReduceOrder_QuadraticsAllowed,
+ kReduceOrder_TreatAsFill);
if (order != 3) {
SkDebugf("[%d] line mod quad order=%d\n", (int) index, order);
}
@@ -116,7 +125,8 @@
for (index = firstComputedLinesTest; index < lines_count; ++index) {
const Cubic& cubic = lines[index];
bool controlsInside = controls_inside(cubic);
- order = reduceOrder(cubic, reduce, kReduceOrder_QuadraticsAllowed);
+ order = reduceOrder(cubic, reduce, kReduceOrder_QuadraticsAllowed,
+ kReduceOrder_TreatAsFill);
if (reduce[0].x == reduce[1].x && reduce[0].y == reduce[1].y) {
SkDebugf("[%d] line computed ends match order=%d\n", (int) index, order);
}
diff --git a/experimental/Intersection/CubicToQuadratics.cpp b/experimental/Intersection/CubicToQuadratics.cpp
index dc4b51b..707cfd1 100644
--- a/experimental/Intersection/CubicToQuadratics.cpp
+++ b/experimental/Intersection/CubicToQuadratics.cpp
@@ -102,7 +102,7 @@
Quadratic q1;
demote_cubic_to_quad(part, q1);
Quadratic s1;
- int o1 = reduceOrder(q1, s1);
+ int o1 = reduceOrder(q1, s1, kReduceOrder_TreatAsFill);
if (order < o1) {
order = o1;
}
@@ -142,7 +142,8 @@
// it would still take the prechopped cubic for reduce order and find cubic inflections
void cubic_to_quadratics(const Cubic& cubic, double precision, SkTDArray<double>& ts) {
Cubic reduced;
- int order = reduceOrder(cubic, reduced, kReduceOrder_QuadraticsAllowed);
+ int order = reduceOrder(cubic, reduced, kReduceOrder_QuadraticsAllowed,
+ kReduceOrder_TreatAsFill);
if (order < 3) {
return;
}
@@ -152,11 +153,13 @@
CubicPair pair;
if (inflections == 1) {
chop_at(cubic, pair, inflectT[0]);
- int orderP1 = reduceOrder(pair.first(), reduced, kReduceOrder_NoQuadraticsAllowed);
+ int orderP1 = reduceOrder(pair.first(), reduced, kReduceOrder_NoQuadraticsAllowed,
+ kReduceOrder_TreatAsFill);
if (orderP1 < 2) {
--inflections;
} else {
- int orderP2 = reduceOrder(pair.second(), reduced, kReduceOrder_NoQuadraticsAllowed);
+ int orderP2 = reduceOrder(pair.second(), reduced, kReduceOrder_NoQuadraticsAllowed,
+ kReduceOrder_TreatAsFill);
if (orderP2 < 2) {
--inflections;
}
diff --git a/experimental/Intersection/CurveIntersection.h b/experimental/Intersection/CurveIntersection.h
index b67ea7e..555d7de 100644
--- a/experimental/Intersection/CurveIntersection.h
+++ b/experimental/Intersection/CurveIntersection.h
@@ -26,13 +26,18 @@
void tangent(const Quadratic& quad, double t, _Point& result);
// main functions
-enum ReduceOrder_Flags {
+enum ReduceOrder_Quadratics {
kReduceOrder_NoQuadraticsAllowed,
kReduceOrder_QuadraticsAllowed
};
-int reduceOrder(const Cubic& cubic, Cubic& reduction, ReduceOrder_Flags );
+enum ReduceOrder_Styles {
+ kReduceOrder_TreatAsStroke,
+ kReduceOrder_TreatAsFill
+};
+int reduceOrder(const Cubic& cubic, Cubic& reduction, ReduceOrder_Quadratics ,
+ ReduceOrder_Styles );
int reduceOrder(const _Line& line, _Line& reduction);
-int reduceOrder(const Quadratic& quad, Quadratic& reduction);
+int reduceOrder(const Quadratic& quad, Quadratic& reduction, ReduceOrder_Styles );
int horizontalIntersect(const Cubic& cubic, double y, double tRange[3]);
int horizontalIntersect(const Cubic& cubic, double left, double right, double y,
double tRange[3]);
diff --git a/experimental/Intersection/DataTypes.h b/experimental/Intersection/DataTypes.h
index c6b2486..ed3ec21 100644
--- a/experimental/Intersection/DataTypes.h
+++ b/experimental/Intersection/DataTypes.h
@@ -34,11 +34,13 @@
int UlpsDiff(float A, float B);
// FLT_EPSILON == 1.19209290E-07 == 1 / (2 ^ 23)
+// DBL_EPSILON == 2.22045e-16
const double FLT_EPSILON_CUBED = FLT_EPSILON * FLT_EPSILON * FLT_EPSILON;
const double FLT_EPSILON_HALF = FLT_EPSILON / 2;
const double FLT_EPSILON_SQUARED = FLT_EPSILON * FLT_EPSILON;
const double FLT_EPSILON_SQRT = sqrt(FLT_EPSILON);
const double FLT_EPSILON_INVERSE = 1 / FLT_EPSILON;
+const double DBL_EPSILON_ERR = DBL_EPSILON * 4; // tune -- allow a few bits of error
#ifdef SK_DEBUG
const double ROUGH_EPSILON = FLT_EPSILON * 16;
@@ -49,7 +51,7 @@
}
inline bool precisely_zero(double x) {
- return fabs(x) < DBL_EPSILON;
+ return fabs(x) < DBL_EPSILON_ERR;
}
inline bool approximately_zero(float x) {
@@ -105,6 +107,10 @@
#endif
}
+inline bool precisely_equal(double x, double y) {
+ return precisely_zero(x - y);
+}
+
inline bool approximately_equal_half(double x, double y) {
return approximately_zero_half(x - y);
}
@@ -134,7 +140,7 @@
}
inline bool precisely_greater_than_one(double x) {
- return x > 1 - DBL_EPSILON;
+ return x > 1 - DBL_EPSILON_ERR;
}
inline bool approximately_less_than_zero(double x) {
@@ -142,7 +148,7 @@
}
inline bool precisely_less_than_zero(double x) {
- return x < DBL_EPSILON;
+ return x < DBL_EPSILON_ERR;
}
inline bool approximately_negative(double x) {
@@ -150,7 +156,7 @@
}
inline bool precisely_negative(double x) {
- return x < DBL_EPSILON;
+ return x < DBL_EPSILON_ERR;
}
inline bool approximately_one_or_less(double x) {
diff --git a/experimental/Intersection/EdgeWalker.cpp b/experimental/Intersection/EdgeWalker.cpp
index 7bf400e..be3f57f 100644
--- a/experimental/Intersection/EdgeWalker.cpp
+++ b/experimental/Intersection/EdgeWalker.cpp
@@ -234,7 +234,7 @@
const Quadratic aQuad = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY},
{a[2].fX, a[2].fY}};
Quadratic dst;
- int order = reduceOrder(aQuad, dst);
+ int order = reduceOrder(aQuad, dst, kReduceOrder_TreatAsFill);
for (int index = 0; index < order; ++index) {
a[index].fX = SkDoubleToScalar(dst[index].x);
a[index].fY = SkDoubleToScalar(dst[index].y);
@@ -250,7 +250,7 @@
const Cubic aCubic = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY},
{a[2].fX, a[2].fY}, {a[3].fX, a[3].fY}};
Cubic dst;
- int order = reduceOrder(aCubic, dst, kReduceOrder_QuadraticsAllowed);
+ int order = reduceOrder(aCubic, dst, kReduceOrder_QuadraticsAllowed, kReduceOrder_TreatAsFill);
for (int index = 0; index < order; ++index) {
a[index].fX = SkDoubleToScalar(dst[index].x);
a[index].fY = SkDoubleToScalar(dst[index].y);
diff --git a/experimental/Intersection/Intersection_Tests.cpp b/experimental/Intersection/Intersection_Tests.cpp
index f7663e4..f55bab7 100644
--- a/experimental/Intersection/Intersection_Tests.cpp
+++ b/experimental/Intersection/Intersection_Tests.cpp
@@ -14,13 +14,16 @@
void Intersection_Tests() {
int testsRun = 0;
- SimplifyNew_Test();
+#if 0
+ QuadraticIntersection_IntersectionFinder();
QuadraticIntersection_OneOffTest();
- CubicsToQuadratics_OneOffTest();
CubicIntersection_IntersectionFinder();
+ CubicIntersection_NewOneOffTest();
+#endif
+ SimplifyNew_Test();
+ CubicsToQuadratics_OneOffTest();
CubicIntersection_OneOffTest();
CubicIntersection_OneOffTests();
- QuadraticIntersection_OneOffTest();
#if 0
parseSVG();
#endif
diff --git a/experimental/Intersection/Intersection_Tests.h b/experimental/Intersection/Intersection_Tests.h
index f647787..af658d9 100644
--- a/experimental/Intersection/Intersection_Tests.h
+++ b/experimental/Intersection/Intersection_Tests.h
@@ -12,6 +12,7 @@
void CubicBezierClip_Test();
void CubicCoincidence_Test();
void CubicIntersection_IntersectionFinder();
+void CubicIntersection_NewOneOffTest();
void CubicIntersection_OneOffTest();
void CubicIntersection_OneOffTests();
void CubicIntersection_Test();
@@ -30,6 +31,7 @@
void LineParameter_Test();
void LineQuadraticIntersection_Test();
void MiniSimplify_Test();
+void QuadraticIntersection_IntersectionFinder();
void QuadraticIntersection_OneOffTest();
void QuadraticIntersection_PointFinder();
void QuadLineIntersectThreaded_Test(int& );
diff --git a/experimental/Intersection/Intersections.cpp b/experimental/Intersection/Intersections.cpp
index 26fcc3f..3de45cb 100644
--- a/experimental/Intersection/Intersections.cpp
+++ b/experimental/Intersection/Intersections.cpp
@@ -122,16 +122,22 @@
|| startPt.approximatelyEqual(fPt[index])
|| endPt.approximatelyEqual(fPt[index]))) {
SkASSERT(fUsed > 0);
- int remaining = --fUsed - index;
- if (remaining > 0) {
- memmove(&fPt[index], &fPt[index - 1], sizeof(fPt[0]) * remaining);
- memmove(&fT[0][index], &fT[0][index - 1], sizeof(fT[0][0]) * remaining);
- memmove(&fT[1][index], &fT[1][index - 1], sizeof(fT[1][0]) * remaining);
- int coBit = fIsCoincident[0] & (1 << index);
- fIsCoincident[0] -= ((fIsCoincident[0] >> 1) & ~((1 << index) - 1)) + coBit;
- SkASSERT(!(coBit ^ (fIsCoincident[1] & (1 << index))));
- fIsCoincident[1] -= ((fIsCoincident[1] >> 1) & ~((1 << index) - 1)) + coBit;
- }
+ removeOne(index);
}
}
}
+
+void Intersections::removeOne(int index) {
+ int remaining = --fUsed - index;
+ if (remaining <= 0) {
+ return;
+ }
+ memmove(&fPt[index], &fPt[index + 1], sizeof(fPt[0]) * remaining);
+ memmove(&fT[0][index], &fT[0][index + 1], sizeof(fT[0][0]) * remaining);
+ memmove(&fT[1][index], &fT[1][index + 1], sizeof(fT[1][0]) * remaining);
+ SkASSERT(fIsCoincident[0] == 0);
+ int coBit = fIsCoincident[0] & (1 << index);
+ fIsCoincident[0] -= ((fIsCoincident[0] >> 1) & ~((1 << index) - 1)) + coBit;
+ SkASSERT(!(coBit ^ (fIsCoincident[1] & (1 << index))));
+ fIsCoincident[1] -= ((fIsCoincident[1] >> 1) & ~((1 << index) - 1)) + coBit;
+}
diff --git a/experimental/Intersection/Intersections.h b/experimental/Intersection/Intersections.h
index 449849c..33fc0ac 100644
--- a/experimental/Intersection/Intersections.h
+++ b/experimental/Intersection/Intersections.h
@@ -79,9 +79,11 @@
return fUsed > 0;
}
+ void removeOne(int index);
+
// leaves flip, swap alone
void reset() {
- fUsed = /* fUsed2 = fCoincidentUsed = */ 0;
+ fUsed = 0;
fUnsortable = false;
}
diff --git a/experimental/Intersection/LineCubicIntersection_Test.cpp b/experimental/Intersection/LineCubicIntersection_Test.cpp
index b81a87e..adf0112 100644
--- a/experimental/Intersection/LineCubicIntersection_Test.cpp
+++ b/experimental/Intersection/LineCubicIntersection_Test.cpp
@@ -27,7 +27,8 @@
const _Line& line = lineCubicTests[index].line;
Cubic reduce1;
_Line reduce2;
- int order1 = reduceOrder(cubic, reduce1, kReduceOrder_NoQuadraticsAllowed);
+ int order1 = reduceOrder(cubic, reduce1, kReduceOrder_NoQuadraticsAllowed,
+ kReduceOrder_TreatAsFill);
int order2 = reduceOrder(line, reduce2);
if (order1 < 4) {
printf("[%d] cubic order=%d\n", (int) index, order1);
diff --git a/experimental/Intersection/LineQuadraticIntersection_Test.cpp b/experimental/Intersection/LineQuadraticIntersection_Test.cpp
index 6c3986c..3e7e230 100644
--- a/experimental/Intersection/LineQuadraticIntersection_Test.cpp
+++ b/experimental/Intersection/LineQuadraticIntersection_Test.cpp
@@ -95,7 +95,7 @@
const _Line& line = lineQuadTests[index].line;
Quadratic reduce1;
_Line reduce2;
- int order1 = reduceOrder(quad, reduce1);
+ int order1 = reduceOrder(quad, reduce1, kReduceOrder_TreatAsFill);
int order2 = reduceOrder(line, reduce2);
if (order1 < 3) {
SkDebugf("%s [%d] quad order=%d\n", __FUNCTION__, (int) index, order1);
@@ -189,7 +189,7 @@
int cy = state.c >> 2;
Quadratic quad = {{ax, ay}, {bx, by}, {cx, cy}};
Quadratic reduced;
- int order = reduceOrder(quad, reduced);
+ int order = reduceOrder(quad, reduced, kReduceOrder_TreatAsFill);
if (order < 3) {
continue; // skip degenerates
}
diff --git a/experimental/Intersection/QuadraticBezierClip_Test.cpp b/experimental/Intersection/QuadraticBezierClip_Test.cpp
index 0d25faf..1579f98 100644
--- a/experimental/Intersection/QuadraticBezierClip_Test.cpp
+++ b/experimental/Intersection/QuadraticBezierClip_Test.cpp
@@ -47,8 +47,8 @@
const Quadratic& quad1 = quadraticTests[index][0];
const Quadratic& quad2 = quadraticTests[index][1];
Quadratic reduce1, reduce2;
- int order1 = reduceOrder(quad1, reduce1);
- int order2 = reduceOrder(quad2, reduce2);
+ int order1 = reduceOrder(quad1, reduce1, kReduceOrder_TreatAsFill);
+ int order2 = reduceOrder(quad2, reduce2, kReduceOrder_TreatAsFill);
if (order1 < 3) {
SkDebugf("%s [%d] quad1 order=%d\n", __FUNCTION__, (int)index, order1);
}
diff --git a/experimental/Intersection/QuadraticIntersection_Test.cpp b/experimental/Intersection/QuadraticIntersection_Test.cpp
index 8bddee2..4b8f254 100644
--- a/experimental/Intersection/QuadraticIntersection_Test.cpp
+++ b/experimental/Intersection/QuadraticIntersection_Test.cpp
@@ -20,8 +20,8 @@
const Quadratic& quad1 = quadraticTests[index][0];
const Quadratic& quad2 = quadraticTests[index][1];
Quadratic reduce1, reduce2;
- int order1 = reduceOrder(quad1, reduce1);
- int order2 = reduceOrder(quad2, reduce2);
+ int order1 = reduceOrder(quad1, reduce1, kReduceOrder_TreatAsFill);
+ int order2 = reduceOrder(quad2, reduce2, kReduceOrder_TreatAsFill);
if (order1 < 3) {
printf("[%d] quad1 order=%d\n", (int) index, order1);
}
@@ -54,6 +54,9 @@
}
static const Quadratic testSet[] = {
+ {{1.64451042,0.0942001592}, {1.53635465,0.00152863961}, {1,0}},
+ {{1.27672209,0.15}, {1.32143477,9.25185854e-17}, {1,0}},
+
{{0, 0}, {0.51851851851851849, 1.0185185185185186}, {1.2592592592592591, 1.9259259259259258}},
{{1.2592592592592593, 1.9259259259259265}, {0.51851851851851893, 1.0185185185185195}, {0, 0}},
@@ -293,3 +296,96 @@
hullIntersect(pointFinderTestSet[0], pointFinderTestSet[4]);
hullIntersect(pointFinderTestSet[0], pointFinderTestSet[6]);
}
+
+void QuadraticIntersection_IntersectionFinder() {
+ const Quadratic& quad1 = testSet[0];
+ const Quadratic& quad2 = testSet[1];
+
+ double t1Seed = 0.98;
+ double t2Seed = 0.97;
+ double t1Step = 0.05;
+ double t2Step = 0.05;
+ _Point t1[3], t2[3];
+ bool toggle = true;
+ do {
+ xy_at_t(quad1, t1Seed - t1Step, t1[0].x, t1[0].y);
+ xy_at_t(quad1, t1Seed, t1[1].x, t1[1].y);
+ xy_at_t(quad1, t1Seed + t1Step, t1[2].x, t1[2].y);
+ xy_at_t(quad2, t2Seed - t2Step, t2[0].x, t2[0].y);
+ xy_at_t(quad2, t2Seed, t2[1].x, t2[1].y);
+ xy_at_t(quad2, t2Seed + t2Step, t2[2].x, t2[2].y);
+ double dist[3][3];
+ dist[1][1] = t1[1].distance(t2[1]);
+ int best_i = 1, best_j = 1;
+ for (int i = 0; i < 3; ++i) {
+ for (int j = 0; j < 3; ++j) {
+ if (i == 1 && j == 1) {
+ continue;
+ }
+ dist[i][j] = t1[i].distance(t2[j]);
+ if (dist[best_i][best_j] > dist[i][j]) {
+ best_i = i;
+ best_j = j;
+ }
+ }
+ }
+ if (best_i == 0) {
+ t1Seed -= t1Step;
+ } else if (best_i == 2) {
+ t1Seed += t1Step;
+ }
+ if (best_j == 0) {
+ t2Seed -= t2Step;
+ } else if (best_j == 2) {
+ t2Seed += t2Step;
+ }
+ if (best_i == 1 && best_j == 1) {
+ if ((toggle ^= true)) {
+ t1Step /= 2;
+ } else {
+ t2Step /= 2;
+ }
+ }
+ } while (!t1[1].approximatelyEqual(t2[1]));
+ t1Step = t2Step = 0.1;
+ double t10 = t1Seed - t1Step * 2;
+ double t12 = t1Seed + t1Step * 2;
+ double t20 = t2Seed - t2Step * 2;
+ double t22 = t2Seed + t2Step * 2;
+ _Point test;
+ while (!approximately_zero(t1Step)) {
+ xy_at_t(quad1, t10, test.x, test.y);
+ t10 += t1[1].approximatelyEqual(test) ? -t1Step : t1Step;
+ t1Step /= 2;
+ }
+ t1Step = 0.1;
+ while (!approximately_zero(t1Step)) {
+ xy_at_t(quad1, t12, test.x, test.y);
+ t12 -= t1[1].approximatelyEqual(test) ? -t1Step : t1Step;
+ t1Step /= 2;
+ }
+ while (!approximately_zero(t2Step)) {
+ xy_at_t(quad2, t20, test.x, test.y);
+ t20 += t2[1].approximatelyEqual(test) ? -t2Step : t2Step;
+ t2Step /= 2;
+ }
+ t2Step = 0.1;
+ while (!approximately_zero(t2Step)) {
+ xy_at_t(quad2, t22, test.x, test.y);
+ t22 -= t2[1].approximatelyEqual(test) ? -t2Step : t2Step;
+ t2Step /= 2;
+ }
+ SkDebugf("%s t1=(%1.9g<%1.9g<%1.9g) t2=(%1.9g<%1.9g<%1.9g)\n", __FUNCTION__,
+ t10, t1Seed, t12, t20, t2Seed, t22);
+ _Point p10 = xy_at_t(quad1, t10);
+ _Point p1Seed = xy_at_t(quad1, t1Seed);
+ _Point p12 = xy_at_t(quad1, t12);
+ SkDebugf("%s p1=(%1.9g,%1.9g)<(%1.9g,%1.9g)<(%1.9g,%1.9g)\n", __FUNCTION__,
+ p10.x, p10.y, p1Seed.x, p1Seed.y, p12.x, p12.y);
+ _Point p20 = xy_at_t(quad2, t20);
+ _Point p2Seed = xy_at_t(quad2, t2Seed);
+ _Point p22 = xy_at_t(quad2, t22);
+ SkDebugf("%s p2=(%1.9g,%1.9g)<(%1.9g,%1.9g)<(%1.9g,%1.9g)\n", __FUNCTION__,
+ p20.x, p20.y, p2Seed.x, p2Seed.y, p22.x, p22.y);
+}
+
diff --git a/experimental/Intersection/QuadraticReduceOrder.cpp b/experimental/Intersection/QuadraticReduceOrder.cpp
index 700d4c5..27c7a29 100644
--- a/experimental/Intersection/QuadraticReduceOrder.cpp
+++ b/experimental/Intersection/QuadraticReduceOrder.cpp
@@ -21,10 +21,14 @@
return 1;
}
-static int vertical_line(const Quadratic& quad, Quadratic& reduction) {
+static int vertical_line(const Quadratic& quad, ReduceOrder_Styles reduceStyle,
+ Quadratic& reduction) {
double tValue;
reduction[0] = quad[0];
reduction[1] = quad[2];
+ if (reduceStyle == kReduceOrder_TreatAsFill) {
+ return 2;
+ }
int smaller = reduction[1].y > reduction[0].y;
int larger = smaller ^ 1;
if (findExtrema(quad[0].y, quad[1].y, quad[2].y, &tValue)) {
@@ -38,10 +42,14 @@
return 2;
}
-static int horizontal_line(const Quadratic& quad, Quadratic& reduction) {
+static int horizontal_line(const Quadratic& quad, ReduceOrder_Styles reduceStyle,
+ Quadratic& reduction) {
double tValue;
reduction[0] = quad[0];
reduction[1] = quad[2];
+ if (reduceStyle == kReduceOrder_TreatAsFill) {
+ return 2;
+ }
int smaller = reduction[1].x > reduction[0].x;
int larger = smaller ^ 1;
if (findExtrema(quad[0].x, quad[1].x, quad[2].x, &tValue)) {
@@ -55,8 +63,8 @@
return 2;
}
-static int check_linear(const Quadratic& quad, Quadratic& reduction,
- int minX, int maxX, int minY, int maxY) {
+static int check_linear(const Quadratic& quad, ReduceOrder_Styles reduceStyle,
+ int minX, int maxX, int minY, int maxY, Quadratic& reduction) {
int startIndex = 0;
int endIndex = 2;
while (quad[startIndex].approximatelyEqual(quad[endIndex])) {
@@ -72,6 +80,9 @@
// four are colinear: return line formed by outside
reduction[0] = quad[0];
reduction[1] = quad[2];
+ if (reduceStyle == kReduceOrder_TreatAsFill) {
+ return 2;
+ }
int sameSide;
bool useX = quad[maxX].x - quad[minX].x >= quad[maxY].y - quad[minY].y;
if (useX) {
@@ -128,7 +139,7 @@
// note that three points in a line doesn't simplify a cubic
// look for approximation with single quadratic
// save approximation with multiple quadratics for later
-int reduceOrder(const Quadratic& quad, Quadratic& reduction) {
+int reduceOrder(const Quadratic& quad, Quadratic& reduction, ReduceOrder_Styles reduceStyle) {
int index, minX, maxX, minY, maxY;
int minXSet, minYSet;
minX = maxX = minY = maxY = 0;
@@ -159,12 +170,12 @@
if (minYSet == 0x7) { // return 1 if all four are coincident
return coincident_line(quad, reduction);
}
- return vertical_line(quad, reduction);
+ return vertical_line(quad, reduceStyle, reduction);
}
if (minYSet == 0xF) { // test for horizontal line
- return horizontal_line(quad, reduction);
+ return horizontal_line(quad, reduceStyle, reduction);
}
- int result = check_linear(quad, reduction, minX, maxX, minY, maxY);
+ int result = check_linear(quad, reduceStyle, minX, maxX, minY, maxY, reduction);
if (result) {
return result;
}
diff --git a/experimental/Intersection/QuadraticReduceOrder_Test.cpp b/experimental/Intersection/QuadraticReduceOrder_Test.cpp
index abf8fa7..0c799c3 100644
--- a/experimental/Intersection/QuadraticReduceOrder_Test.cpp
+++ b/experimental/Intersection/QuadraticReduceOrder_Test.cpp
@@ -22,7 +22,7 @@
for (size_t index = 0; index < testSetCount; ++index) {
const Quadratic& quad = testSet[index];
Quadratic reduce;
- int order = reduceOrder(quad, reduce);
+ int order = reduceOrder(quad, reduce, kReduceOrder_TreatAsFill);
SkASSERT(order == 3);
}
}
@@ -47,14 +47,14 @@
for (index = firstQuadraticLineTest; index < quadraticLines_count; ++index) {
const Quadratic& quad = quadraticLines[index];
- order = reduceOrder(quad, reduce);
+ order = reduceOrder(quad, reduce, kReduceOrder_TreatAsFill);
if (order != 2) {
printf("[%d] line quad order=%d\n", (int) index, order);
}
}
for (index = firstQuadraticModLineTest; index < quadraticModEpsilonLines_count; ++index) {
const Quadratic& quad = quadraticModEpsilonLines[index];
- order = reduceOrder(quad, reduce);
+ order = reduceOrder(quad, reduce, kReduceOrder_TreatAsFill);
if (order != 3) {
printf("[%d] line mod quad order=%d\n", (int) index, order);
}
diff --git a/experimental/Intersection/QuadraticUtilities.cpp b/experimental/Intersection/QuadraticUtilities.cpp
index d33fda8..fa8acea 100644
--- a/experimental/Intersection/QuadraticUtilities.cpp
+++ b/experimental/Intersection/QuadraticUtilities.cpp
@@ -232,3 +232,13 @@
y = a * quad[0].y + b * quad[1].y + c * quad[2].y;
}
}
+
+_Point xy_at_t(const Quadratic& quad, double t) {
+ double one_t = 1 - t;
+ double a = one_t * one_t;
+ double b = 2 * one_t * t;
+ double c = t * t;
+ _Point 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;
+}
diff --git a/experimental/Intersection/QuadraticUtilities.h b/experimental/Intersection/QuadraticUtilities.h
index b507b5f..8308f38 100644
--- a/experimental/Intersection/QuadraticUtilities.h
+++ b/experimental/Intersection/QuadraticUtilities.h
@@ -38,5 +38,6 @@
void sub_divide(const Quadratic& src, double t1, double t2, Quadratic& dst);
_Point top(const Quadratic& , double startT, double endT);
void xy_at_t(const Quadratic& , double t, double& x, double& y);
+_Point xy_at_t(const Quadratic& , double t);
#endif
diff --git a/experimental/Intersection/Simplify.cpp b/experimental/Intersection/Simplify.cpp
index 0a75f2a..5cfc388 100644
--- a/experimental/Intersection/Simplify.cpp
+++ b/experimental/Intersection/Simplify.cpp
@@ -32,7 +32,7 @@
#define DEBUG_UNUSED 0 // set to expose unused functions
-#define FORCE_RELEASE 1 // set force release to 1 for multiple thread -- no debugging
+#define FORCE_RELEASE 0 // set force release to 1 for multiple thread -- no debugging
#if FORCE_RELEASE || defined SK_RELEASE
@@ -52,6 +52,7 @@
#define DEBUG_PATH_CONSTRUCTION 0
#define DEBUG_SHOW_WINDING 0
#define DEBUG_SORT 0
+#define DEBUG_SWAP_TOP 1
#define DEBUG_UNSORTABLE 0
#define DEBUG_WIND_BUMP 0
#define DEBUG_WINDING 0
@@ -75,6 +76,7 @@
#define DEBUG_PATH_CONSTRUCTION 1
#define DEBUG_SHOW_WINDING 0
#define DEBUG_SORT 1
+#define DEBUG_SWAP_TOP 1
#define DEBUG_UNSORTABLE 1
#define DEBUG_WIND_BUMP 0
#define DEBUG_WINDING 1
@@ -501,7 +503,7 @@
SkTDArray<SkPoint>& reducePts) {
MAKE_CONST_QUAD(aQuad, a);
Quadratic dst;
- int order = reduceOrder(aQuad, dst);
+ int order = reduceOrder(aQuad, dst, kReduceOrder_TreatAsFill);
if (order == 2) { // quad became line
for (int index = 0; index < order; ++index) {
SkPoint* pt = reducePts.append();
@@ -516,7 +518,7 @@
SkTDArray<SkPoint>& reducePts) {
MAKE_CONST_CUBIC(aCubic, a);
Cubic dst;
- int order = reduceOrder(aCubic, dst, kReduceOrder_QuadraticsAllowed);
+ int order = reduceOrder(aCubic, dst, kReduceOrder_QuadraticsAllowed, kReduceOrder_TreatAsFill);
if (order == 2 || order == 3) { // cubic became line or quad
for (int index = 0; index < order; ++index) {
SkPoint* pt = reducePts.append();
@@ -887,7 +889,7 @@
#if 1
const Span& thisSpan = (*fSpans)[index];
const Span& nextSpan = (*fSpans)[index + step];
- if (thisSpan.fTiny || thisSpan.fT == nextSpan.fT) {
+ if (thisSpan.fTiny || precisely_equal(thisSpan.fT, nextSpan.fT)) {
continue;
}
fUnsortable = step > 0 ? thisSpan.fUnsortableStart : nextSpan.fUnsortableEnd;
@@ -2820,9 +2822,17 @@
endIndex = angle->start();
} while (leftSegment->fTs[SkMin32(tIndex, endIndex)].fDone);
if (leftSegment->verb() >= SkPath::kQuad_Verb) {
- SkScalar dyE = leftSegment->dy(endIndex);
- SkScalar dyS = leftSegment->dy(tIndex);
- if (dyE < 0 && dyS > 0) {
+ SkPoint dxyE = leftSegment->dxdy(endIndex);
+ SkPoint dxyS = leftSegment->dxdy(tIndex);
+ double cross = dxyE.cross(dxyS);
+ #if DEBUG_SWAP_TOP
+ SkDebugf("%s dxyE=(%1.9g,%1.9g) dxyS=(%1.9g,%1.9g) cross=%1.9g\n", __FUNCTION__,
+ dxyE.fX, dxyE.fY, dxyS.fX, dxyS.fY, cross);
+ #endif
+ if (cross >= 1) {
+ #if DEBUG_SWAP_TOP
+ SkDebugf("%s swap\n", __FUNCTION__);
+ #endif
SkTSwap(tIndex, endIndex);
}
}
@@ -3972,6 +3982,11 @@
const Span* span = &fTs[i];
SkDebugf(") t=%1.9g (%1.9g,%1.9g)", fTs[i].fT,
xAtT(span), yAtT(span));
+ int iEnd = i + 1;
+ while (fTs[iEnd].fT < 1 && approximately_equal(fTs[i].fT, fTs[iEnd].fT)) {
+ ++iEnd;
+ }
+ SkDebugf(" tEnd=%1.9g", fTs[iEnd].fT);
const Segment* other = fTs[i].fOther;
SkDebugf(" other=%d otherT=%1.9g otherIndex=%d windSum=",
other->fID, fTs[i].fOtherT, fTs[i].fOtherIndex);
diff --git a/experimental/Intersection/SimplifyNew_Test.cpp b/experimental/Intersection/SimplifyNew_Test.cpp
index 08dda60..4c83be7 100644
--- a/experimental/Intersection/SimplifyNew_Test.cpp
+++ b/experimental/Intersection/SimplifyNew_Test.cpp
@@ -3767,12 +3767,82 @@
testShapeOp(path, pathB, kDifference_Op);
}
-static void (*firstTest)() = 0;
+static void cubicOp15d() {
+ SkPath path, pathB;
+ path.setFillType(SkPath::kWinding_FillType);
+ path.moveTo(0,1);
+ path.cubicTo(3,6, 2,0, 2,1);
+ path.close();
+ pathB.setFillType(SkPath::kWinding_FillType);
+ pathB.moveTo(0,2);
+ pathB.cubicTo(1,2, 1,0, 6,3);
+ pathB.close();
+ testShapeOp(path, pathB, kDifference_Op);
+}
+
+static void cubicOp16d() {
+ SkPath path, pathB;
+ path.setFillType(SkPath::kWinding_FillType);
+ path.moveTo(0,2);
+ path.cubicTo(0,1, 3,0, 1,0);
+ path.close();
+ pathB.setFillType(SkPath::kWinding_FillType);
+ pathB.moveTo(0,3);
+ pathB.cubicTo(0,1, 2,0, 1,0);
+ pathB.close();
+ testShapeOp(path, pathB, kDifference_Op);
+}
+
+static void cubicOp17d() {
+ SkPath path, pathB;
+ path.setFillType(SkPath::kWinding_FillType);
+ path.moveTo(0,2);
+ path.cubicTo(0,2, 4,0, 2,1);
+ path.close();
+ pathB.setFillType(SkPath::kWinding_FillType);
+ pathB.moveTo(0,4);
+ pathB.cubicTo(1,2, 2,0, 2,0);
+ pathB.close();
+ testShapeOp(path, pathB, kDifference_Op);
+}
+
+static void cubicOp18d() {
+ SkPath path, pathB;
+ path.setFillType(SkPath::kWinding_FillType);
+ path.moveTo(0,1);
+ path.cubicTo(3,5, 2,0, 2,1);
+ path.close();
+ pathB.setFillType(SkPath::kWinding_FillType);
+ pathB.moveTo(0,2);
+ pathB.cubicTo(1,2, 1,0, 5,3);
+ pathB.close();
+ testShapeOp(path, pathB, kDifference_Op);
+}
+
+static void cubicOp19i() {
+ SkPath path, pathB;
+ path.setFillType(SkPath::kWinding_FillType);
+ path.moveTo(0,2);
+ path.cubicTo(0,1, 2,1, 6,2);
+ path.close();
+ pathB.setFillType(SkPath::kWinding_FillType);
+ pathB.moveTo(1,2);
+ pathB.cubicTo(2,6, 2,0, 1,0);
+ pathB.close();
+ testShapeOp(path, pathB, kIntersect_Op);
+}
+
+static void (*firstTest)() = cubicOp19i;
static struct {
void (*fun)();
const char* str;
} tests[] = {
+ TEST(cubicOp19i),
+ TEST(cubicOp18d),
+ TEST(cubicOp17d),
+ TEST(cubicOp16d),
+ TEST(cubicOp15d),
TEST(cubicOp14d),
TEST(cubicOp13d),
TEST(cubicOp12d),
diff --git a/experimental/Intersection/as.htm b/experimental/Intersection/as.htm
index 43dceb4..2ed8015 100644
--- a/experimental/Intersection/as.htm
+++ b/experimental/Intersection/as.htm
@@ -2,166 +2,18 @@
<head>
<div style="height:0">
-<div id="quad56">
-debugShowActiveSpans id=1 (366.608826,151.196014 378.803101,136.674606 398.164948,136.674606) t=0.490456543 (380.294495,140.44487) other=7 otherT=0.578520747 otherIndex=3 windSum=? windValue=1
-debugShowActiveSpans id=2 (398.164948,136.674606 354.009216,208.816208) t=0 (398.164948,136.674606) other=1 otherT=1 otherIndex=4 windSum=? windValue=1
-debugShowActiveSpans id=3 (354.009216,208.816208 393.291473,102.232819) t=0 (354.009216,208.816208) other=2 otherT=1 otherIndex=1 windSum=? windValue=1
-debugShowActiveSpans id=3 (354.009216,208.816208 393.291473,102.232819) t=0.508945199 (374.00174,154.571106) other=6 otherT=0.598402499 otherIndex=1 windSum=? windValue=1
-debugShowActiveSpans id=3 (354.009216,208.816208 393.291473,102.232819) t=0.634079491 (378.917297,141.233871) other=7 otherT=0.536512741 otherIndex=1 windSum=-1 windValue=1
-debugShowActiveSpans id=5 (359.978058,136.581512 378.315979,136.581512 388.322723,149.613556) t=0.597488996 (378.917297,141.233856) other=7 otherT=0.536512973 otherIndex=2 windSum=? windValue=1
-debugShowActiveSpans id=6 (388.322723,149.613556 364.390686,157.898193) t=0 (388.322723,149.613556) other=5 otherT=1 otherIndex=4 windSum=? windValue=1
-debugShowActiveSpans id=6 (388.322723,149.613556 364.390686,157.898193) t=0.598402499 (374.00174,154.571106) other=3 otherT=0.508945199 otherIndex=1 windSum=? windValue=1
-debugShowActiveSpans id=7 (364.390686,157.898193 375.281769,136.674606 396.039917,136.674606) t=0 (364.390686,157.898193) other=6 otherT=1 otherIndex=2 windSum=? windValue=1
-debugShowActiveSpans id=7 (364.390686,157.898193 375.281769,136.674606 396.039917,136.674606) t=0.536512741 (378.917297,141.233871) other=3 otherT=0.634079491 otherIndex=2 windSum=? windValue=1
-debugShowActiveSpans id=7 (364.390686,157.898193 375.281769,136.674606 396.039917,136.674606) t=0.536512973 (378.917297,141.233856) other=5 otherT=0.597488996 otherIndex=3 windSum=-1 windValue=1
-</div>
-
-<div id="quad57c">
-debugShowActiveSpans id=1 (303.12088,141.299606 330.463562,217.659027) t=0.845414865 (326.236786,205.854996) other=13 otherT=0.999999913 otherIndex=3 windSum=? windValue=1
-debugShowActiveSpans id=2 (330.463562,217.659027 358.606506,141.299606) t=-0 (330.463562,217.659027) other=1 otherT=1 otherIndex=3 windSum=? windValue=1
-debugShowActiveSpans id=2 (330.463562,217.659027 358.606506,141.299606) t=0.154585135 (334.814056,205.854996) other=13 otherT=0.812241055 otherIndex=2 windSum=? windValue=1
-debugShowActiveSpans id=2 (330.463562,217.659027 358.606506,141.299606) t=0.283842806 (338.451721,195.984955) other=16 otherT=0.363593784 otherIndex=1 windSum=? windValue=1
-debugShowActiveSpans id=4 (362.874634,159.705902 335.665344,233.397751) t=0.379109438 (352.559326,187.643173) other=17 otherT=0.412818074 otherIndex=1 windSum=? windValue=1
-debugShowActiveSpans id=13 (371.919067,205.854996 326.236786,205.854996) t=0.812241055 (334.814056,205.854996) other=2 otherT=0.154585135 otherIndex=1 windSum=? windValue=1
-debugShowActiveSpans id=14 (326.236786,205.854996 329.104431,231.663818 351.512085,231.663818) t=0.962138429 (349.843323,231.626816) other=15 otherT=0.0583966647 otherIndex=1 windSum=1 windValue=1
-debugShowActiveSpans id=15 (351.512085,231.663818 322.935669,231.030273) t=0 (351.512085,231.663818) other=14 otherT=1 otherIndex=3 windSum=1 windValue=1
-debugShowActiveSpans id=16 (326.837006,195.984955 358.78125,195.984955) t=0 (326.837006,195.984955) other=18 otherT=1 otherIndex=1 windSum=? windValue=1
-debugShowActiveSpans id=16 (326.837006,195.984955 358.78125,195.984955) t=0.363593784 (338.451721,195.984955) other=2 otherT=0.283842806 otherIndex=2 windSum=? windValue=1
-debugShowActiveSpans id=16 (326.837006,195.984955 358.78125,195.984955) t=0.708806554 (349.479309,195.984955) other=4 otherT=0.492307539 otherIndex=3 windSum=? windValue=1
-debugShowActiveSpans id=17 (358.78125,195.984955 343.709442,175.778046) t=-0 (358.78125,195.984955) other=16 otherT=1 otherIndex=3 windSum=? windValue=1
-debugShowActiveSpans id=17 (358.78125,195.984955 343.709442,175.778046) t=0.412818074 (352.559326,187.643173) other=4 otherT=0.379109438 otherIndex=2 windSum=? windValue=1
-debugShowActiveSpans id=17 (358.78125,195.984955 343.709442,175.778046) t=0.902761903 (345.174988,177.74292) other=2 otherT=0.522739691 otherIndex=3 windSum=? windValue=1
-debugShowActiveSpans id=18 (343.709442,175.778046 328.570923,175.778046 326.837006,195.984955) t=0 (343.709442,175.778046) other=17 otherT=1 otherIndex=3 windSum=? windValue=1
-</div>
-
-<div id="quad57b">
-debugShowActiveSpans id=1 (303.12088,141.299606 330.463562,217.659027) t=0.845414865 (326.236786,205.854996) other=13 otherT=0.999999913 otherIndex=3 windSum=1 windValue=1
-debugShowActiveSpans id=2 (330.463562,217.659027 358.606506,141.299606) t=-0 (330.463562,217.659027) other=1 otherT=1 otherIndex=3 windSum=? windValue=1
-debugShowActiveSpans id=2 (330.463562,217.659027 358.606506,141.299606) t=0.154585135 (334.814056,205.854996) other=13 otherT=0.812241055 otherIndex=2 windSum=? windValue=1
-debugShowActiveSpans id=2 (330.463562,217.659027 358.606506,141.299606) t=0.283842806 (338.451721,195.984955) other=16 otherT=0.363593784 otherIndex=1 windSum=? windValue=1
-debugShowActiveSpans id=4 (362.874634,159.705902 335.665344,233.397751) t=0.379109438 (352.559326,187.643173) other=17 otherT=0.412818074 otherIndex=1 windSum=? windValue=1
-debugShowActiveSpans id=13 (371.919067,205.854996 326.236786,205.854996) t=0.812241055 (334.814056,205.854996) other=2 otherT=0.154585135 otherIndex=1 windSum=? windValue=1
-debugShowActiveSpans id=16 (326.837006,195.984955 358.78125,195.984955) t=0 (326.837006,195.984955) other=18 otherT=1 otherIndex=1 windSum=? windValue=1
-debugShowActiveSpans id=16 (326.837006,195.984955 358.78125,195.984955) t=0.363593784 (338.451721,195.984955) other=2 otherT=0.283842806 otherIndex=2 windSum=? windValue=1
-debugShowActiveSpans id=16 (326.837006,195.984955 358.78125,195.984955) t=0.708806554 (349.479309,195.984955) other=4 otherT=0.492307539 otherIndex=3 windSum=? windValue=1
-debugShowActiveSpans id=17 (358.78125,195.984955 343.709442,175.778046) t=-0 (358.78125,195.984955) other=16 otherT=1 otherIndex=3 windSum=? windValue=1
-debugShowActiveSpans id=17 (358.78125,195.984955 343.709442,175.778046) t=0.412818074 (352.559326,187.643173) other=4 otherT=0.379109438 otherIndex=2 windSum=? windValue=1
-debugShowActiveSpans id=17 (358.78125,195.984955 343.709442,175.778046) t=0.902761903 (345.174988,177.74292) other=2 otherT=0.522739691 otherIndex=3 windSum=? windValue=1
-debugShowActiveSpans id=18 (343.709442,175.778046 328.570923,175.778046 326.837006,195.984955) t=0 (343.709442,175.778046) other=17 otherT=1 otherIndex=3 windSum=? windValue=1
-</div>
-
-<div id="quad57a">
-debugShowActiveSpans id=2 (330.463562,217.659027 358.606506,141.299606) t=0.154585135 (334.814056,205.854996) other=13 otherT=0.812241055 otherIndex=2 windSum=-1 windValue=1
-debugShowActiveSpans id=2 (330.463562,217.659027 358.606506,141.299606) t=0.283842806 (338.451721,195.984955) other=16 otherT=0.363593784 otherIndex=1 windSum=? windValue=1
-debugShowActiveSpans id=4 (362.874634,159.705902 335.665344,233.397751) t=0.379109438 (352.559326,187.643173) other=17 otherT=0.412818074 otherIndex=1 windSum=? windValue=1
-debugShowActiveSpans id=16 (326.837006,195.984955 358.78125,195.984955) t=0 (326.837006,195.984955) other=18 otherT=1 otherIndex=1 windSum=? windValue=1
-debugShowActiveSpans id=16 (326.837006,195.984955 358.78125,195.984955) t=0.363593784 (338.451721,195.984955) other=2 otherT=0.283842806 otherIndex=2 windSum=? windValue=1
-debugShowActiveSpans id=16 (326.837006,195.984955 358.78125,195.984955) t=0.708806554 (349.479309,195.984955) other=4 otherT=0.492307539 otherIndex=3 windSum=? windValue=1
-debugShowActiveSpans id=17 (358.78125,195.984955 343.709442,175.778046) t=-0 (358.78125,195.984955) other=16 otherT=1 otherIndex=3 windSum=? windValue=1
-debugShowActiveSpans id=17 (358.78125,195.984955 343.709442,175.778046) t=0.412818074 (352.559326,187.643173) other=4 otherT=0.379109438 otherIndex=2 windSum=? windValue=1
-debugShowActiveSpans id=17 (358.78125,195.984955 343.709442,175.778046) t=0.902761903 (345.174988,177.74292) other=2 otherT=0.522739691 otherIndex=3 windSum=? windValue=1
-debugShowActiveSpans id=18 (343.709442,175.778046 328.570923,175.778046 326.837006,195.984955) t=0 (343.709442,175.778046) other=17 otherT=1 otherIndex=3 windSum=? windValue=1
-</div>
-
-<div id="quad58b">
-debugShowActiveSpans id=3 (303.12088,141.299606 330.463562,217.659027) t=0.845414865 (326.236786,205.854996) other=16 otherT=0.999999913 otherIndex=3 windSum=1 windValue=1
-debugShowActiveSpans id=4 (330.463562,217.659027 358.606506,141.299606) t=-0 (330.463562,217.659027) other=3 otherT=1 otherIndex=3 windSum=? windValue=1
-debugShowActiveSpans id=4 (330.463562,217.659027 358.606506,141.299606) t=0.154585135 (334.814056,205.854996) other=16 otherT=0.812241055 otherIndex=2 windSum=? windValue=1
-debugShowActiveSpans id=4 (330.463562,217.659027 358.606506,141.299606) t=0.283842806 (338.451721,195.984955) other=19 otherT=0.363593784 otherIndex=1 windSum=? windValue=1
-debugShowActiveSpans id=6 (362.874634,159.705902 335.665344,233.397751) t=0.287405665 (355.054535,180.885361) other=20 otherT=0.497256785 otherIndex=1 windSum=? windValue=1
-debugShowActiveSpans id=16 (371.919067,205.854996 326.236786,205.854996) t=0.812241055 (334.814056,205.854996) other=4 otherT=0.154585135 otherIndex=1 windSum=? windValue=1
-debugShowActiveSpans id=19 (326.837006,195.984955 358.78125,195.984955) t=0 (326.837006,195.984955) other=21 otherT=1 otherIndex=1 windSum=? windValue=1
-debugShowActiveSpans id=19 (326.837006,195.984955 358.78125,195.984955) t=0.363593784 (338.451721,195.984955) other=4 otherT=0.283842806 otherIndex=2 windSum=? windValue=1
-debugShowActiveSpans id=19 (326.837006,195.984955 358.78125,195.984955) t=0.708806554 (349.479309,195.984955) other=6 otherT=0.492307539 otherIndex=3 windSum=? windValue=1
-debugShowActiveSpans id=20 (358.78125,195.984955 358.78125,175.778046 343.709442,175.778046) t=0 (358.78125,195.984955) other=19 otherT=1 otherIndex=3 windSum=? windValue=1
-debugShowActiveSpans id=20 (358.78125,195.984955 358.78125,175.778046 343.709442,175.778046) t=0.497256785 (355.054535,180.885361) other=6 otherT=0.287405665 otherIndex=2 windSum=? windValue=1
-debugShowActiveSpans id=20 (358.78125,195.984955 358.78125,175.778046 343.709442,175.778046) t=0.925970638 (345.858368,175.888794) other=4 otherT=0.547021444 otherIndex=3 windSum=? windValue=1
-debugShowActiveSpans id=21 (343.709442,175.778046 328.570923,175.778046 326.837006,195.984955) t=0 (343.709442,175.778046) other=20 otherT=1 otherIndex=3 windSum=? windValue=1
-</div>
-
-<div id="quad58a">
-debugShowActiveSpans id=4 (330.463562,217.659027 358.606506,141.299606) t=0.154585135 (334.814056,205.854996) other=16 otherT=0.812241055 otherIndex=2 windSum=-1 windValue=1
-debugShowActiveSpans id=4 (330.463562,217.659027 358.606506,141.299606) t=0.283842806 (338.451721,195.984955) other=19 otherT=0.363593784 otherIndex=1 windSum=? windValue=1
-debugShowActiveSpans id=6 (362.874634,159.705902 335.665344,233.397751) t=0.287405665 (355.054535,180.885361) other=20 otherT=0.497256785 otherIndex=1 windSum=? windValue=1
-debugShowActiveSpans id=19 (326.837006,195.984955 358.78125,195.984955) t=0 (326.837006,195.984955) other=21 otherT=1 otherIndex=1 windSum=? windValue=1
-debugShowActiveSpans id=19 (326.837006,195.984955 358.78125,195.984955) t=0.363593784 (338.451721,195.984955) other=4 otherT=0.283842806 otherIndex=2 windSum=? windValue=1
-debugShowActiveSpans id=19 (326.837006,195.984955 358.78125,195.984955) t=0.708806554 (349.479309,195.984955) other=6 otherT=0.492307539 otherIndex=3 windSum=? windValue=1
-debugShowActiveSpans id=20 (358.78125,195.984955 358.78125,175.778046 343.709442,175.778046) t=0 (358.78125,195.984955) other=19 otherT=1 otherIndex=3 windSum=? windValue=1
-debugShowActiveSpans id=20 (358.78125,195.984955 358.78125,175.778046 343.709442,175.778046) t=0.497256785 (355.054535,180.885361) other=6 otherT=0.287405665 otherIndex=2 windSum=? windValue=1
-debugShowActiveSpans id=20 (358.78125,195.984955 358.78125,175.778046 343.709442,175.778046) t=0.925970638 (345.858368,175.888794) other=4 otherT=0.547021444 otherIndex=3 windSum=? windValue=1
-debugShowActiveSpans id=21 (343.709442,175.778046 328.570923,175.778046 326.837006,195.984955) t=0 (343.709442,175.778046) other=20 otherT=1 otherIndex=3 windSum=? windValue=1
-</div>
-
-<div id="quad59">
-debugShowQuadIntersection wtTs[0]=0 (369.863983,145.645813 382.380371,121.254936 406.236359,121.254936) (369.863983,145.645813) wnTs[0]=1 (406.236359,121.254936 409.445679,121.254936 412.975952,121.789818) (412.975952,121.789818)
-debugShowQuadLineIntersection wtTs[0]=1 (369.863983,145.645813 382.380371,121.254936 406.236359,121.254936) (406.236359,121.254936) wnTs[0]=0 (412.975952,121.789818 369.863983,145.645813) (412.975952,121.789818)
-debugShowQuadLineIntersection wtTs[0]=0 (406.236359,121.254936 409.445679,121.254936 412.975952,121.789818) (406.236359,121.254936) wnTs[0]=1 (412.975952,121.789818 369.863983,145.645813) (369.863983,145.645813)
-debugShowQuadIntersection no intersect (369.863983,145.645813 382.380371,121.254936 406.236359,121.254936) (369.970581,137.94342 383.98465,121.254936 406.235992,121.254936)
-debugShowQuadIntersection no intersect (369.863983,145.645813 382.380371,121.254936 406.236359,121.254936) (406.235992,121.254936 425.705902,121.254936 439.71994,137.087616)
-debugShowQuadLineIntersection wtTs[0]=0.934062756 (369.863983,145.645813 382.380371,121.254936 406.236359,121.254936) (403.139679,121.360977) wnTs[0]=0.17423 (439.71994,137.087616 369.970581,137.94342) (427.567535,137.236725)
-debugShowQuadIntersection wtTs[0]=9.61225644e-05 (406.236359,121.254936 409.445679,121.254936 412.975952,121.789818) (406.236969,121.254936) wnTs[0]=0.000495996 (406.235992,121.254936 425.705902,121.254936 439.71994,137.087616) (406.25531,121.254944)
-debugShowQuadLineIntersection no intersect (369.970581,137.94342 383.98465,121.254936 406.235992,121.254936) (412.975952,121.789818 369.863983,145.645813)
-debugShowQuadLineIntersection no intersect (406.235992,121.254936 425.705902,121.254936 439.71994,137.087616) (412.975952,121.789818 369.863983,145.645813)
-debugShowQuadIntersection wtTs[0]=0 (369.970581,137.94342 383.98465,121.254936 406.235992,121.254936) (369.970581,137.94342) wnTs[0]=1 (406.235992,121.254936 425.705902,121.254936 439.71994,137.087616) (439.71994,137.087616)
-debugShowQuadLineIntersection wtTs[0]=1 (369.970581,137.94342 383.98465,121.254936 406.235992,121.254936) (406.235992,121.254936) wnTs[0]=0 (439.71994,137.087616 369.970581,137.94342) (439.71994,137.087616)
-debugShowQuadLineIntersection wtTs[0]=0 (406.235992,121.254936 425.705902,121.254936 439.71994,137.087616) (406.235992,121.254936) wnTs[0]=1 (439.71994,137.087616 369.970581,137.94342) (369.970581,137.94342)
-</div>
-
-<div id="quad59b">
-debugShowActiveSpans id=1 (369.863983,145.645813 382.380371,121.254936 406.236359,121.254936) t=0 (369.863983,145.645813) other=3 otherT=1 otherIndex=2 windSum=? windValue=1
-debugShowActiveSpans id=1 (369.863983,145.645813 382.380371,121.254936 406.236359,121.254936) t=0.174229721 (374.569672,137.886993) other=6 otherT=0.934062756 otherIndex=2 windSum=? windValue=1
-debugShowActiveSpans id=2 (406.236359,121.254936 409.445679,121.254936 412.975952,121.789818) t=0 (406.236359,121.254936) other=1 otherT=1 otherIndex=2 windSum=? windValue=1
-debugShowActiveSpans id=2 (406.236359,121.254936 409.445679,121.254936 412.975952,121.789818) t=0.000495995847 (406.239532,121.254936) other=5 otherT=9.61225644e-05 otherIndex=1 windSum=? windValue=1
-debugShowActiveSpans id=3 (412.975952,121.789818 369.863983,145.645813) t=0 (412.975952,121.789818) other=2 otherT=1 otherIndex=2 windSum=? windValue=1
-debugShowActiveSpans id=3 (412.975952,121.789818 369.863983,145.645813) t=0.669864243 (384.096771,137.770096) other=6 otherT=0.797471908 otherIndex=1 windSum=? windValue=1
-debugShowActiveSpans id=4 (369.970581,137.94342 383.98465,121.254936 406.235992,121.254936) t=0 (369.970581,137.94342) other=6 otherT=1 otherIndex=3 windSum=? windValue=1
-debugShowActiveSpans id=5 (406.235992,121.254936 425.705902,121.254936 439.71994,137.087616) t=0 (406.235992,121.254936) other=4 otherT=1 otherIndex=1 windSum=? windValue=1
-debugShowActiveSpans id=5 (406.235992,121.254936 425.705902,121.254936 439.71994,137.087616) t=9.61225644e-05 (406.239746,121.254936) other=2 otherT=0.000495995847 otherIndex=1 windSum=? windValue=1
-debugShowActiveSpans id=6 (439.71994,137.087616 369.970581,137.94342) t=0 (439.71994,137.087616) other=5 otherT=1 otherIndex=2 windSum=? windValue=1
-debugShowActiveSpans id=6 (439.71994,137.087616 369.970581,137.94342) t=0.797471908 (384.096771,137.770096) other=3 otherT=0.669864243 otherIndex=1 windSum=? windValue=1
-debugShowActiveSpans id=6 (439.71994,137.087616 369.970581,137.94342) t=0.934062756 (374.569672,137.886993) other=1 otherT=0.174229721 otherIndex=1 windSum=? windValue=1
-</div>
-
-<div id="quad60">
-debugShowActiveSpans id=1 (360.416077,166.795715 370.126831,147.872162 388.635406,147.872162) t=0 (360.416077,166.795715) other=2 otherT=1 otherIndex=2 windSum=? windValue=1
-debugShowActiveSpans id=2 (388.635406,147.872162 360.416077,166.795715) t=0 (388.635406,147.872162) other=1 otherT=1 otherIndex=1 windSum=? windValue=1
-debugShowActiveSpans id=2 (388.635406,147.872162 360.416077,166.795715) t=0.00925761141 (388.374176,148.047348) other=4 otherT=0.883679938 otherIndex=1 windSum=? windValue=1
-debugShowActiveSpans id=3 (353.2948,194.351074 353.2948,173.767563 364.167572,160.819855) t=0 (353.2948,194.351074) other=5 otherT=1 otherIndex=1 windSum=? windValue=1
-debugShowActiveSpans id=4 (364.167572,160.819855 375.040314,147.872162 392.303894,147.872162) t=0 (364.167572,160.819855) other=3 otherT=1 otherIndex=1 windSum=? windValue=1
-debugShowActiveSpans id=4 (364.167572,160.819855 375.040314,147.872162 392.303894,147.872162) t=0.883679938 (388.374176,148.047348) other=2 otherT=0.00925761141 otherIndex=1 windSum=? windValue=1
-debugShowActiveSpans id=5 (392.303894,147.872162 353.2948,194.351074) t=0 (392.303894,147.872162) other=4 otherT=1 otherIndex=2 windSum=? windValue=1
-</div>
-
-<div id="quad61">
-debugShowActiveSpans id=1 (348.781738,123.864815 369.848602,123.864815) t=0 (348.781738,123.864815) other=4 otherT=1 otherIndex=4 windSum=? windValue=1
-debugShowActiveSpans id=2 (369.848602,123.864815 369.848602,145.680267) t=0 (369.848602,123.864815) other=1 otherT=1 otherIndex=1 windSum=? windValue=1
-debugShowActiveSpans id=3 (369.848602,145.680267 382.360413,121.298294 406.207703,121.298294) t=0 (369.848602,145.680267) other=2 otherT=1 otherIndex=1 windSum=? windValue=1
-debugShowActiveSpans id=3 (369.848602,145.680267 382.360413,121.298294 406.207703,121.298294) t=0.258355433 (377.070221,134.709274) other=6 otherT=0.8038997 otherIndex=1 windSum=? windValue=1
-debugShowActiveSpans id=3 (369.848602,145.680267 382.360413,121.298294 406.207703,121.298294) t=0.914354357 (402.206024,121.477142) other=4 otherT=0.0696842495 otherIndex=2 windSum=? windValue=1
-debugShowActiveSpans id=3 (369.848602,145.680267 382.360413,121.298294 406.207703,121.298294) t=0.999082394 (406.16394,121.298317) other=5 otherT=0.998890674 otherIndex=2 windSum=? windValue=1
-debugShowActiveSpans id=4 (406.207703,121.298294 348.781738,123.864815) t=1.0265934e-07 (406.207703,121.298294) other=5 otherT=0.999874327 otherIndex=3 windSum=? windValue=1
-debugShowActiveSpans id=4 (406.207703,121.298294 348.781738,123.864815) t=0.0696842495 (402.206024,121.477142) other=3 otherT=0.914354357 otherIndex=2 windSum=? windValue=1
-debugShowActiveSpans id=4 (406.207703,121.298294 348.781738,123.864815) t=0.0881931013 (401.143127,121.524643) other=5 otherT=0.883517581 otherIndex=1 windSum=? windValue=1
-debugShowActiveSpans id=5 (369.961151,137.980698 383.970093,121.298294 406.213287,121.298294) t=0 (369.961151,137.980698) other=6 otherT=1 otherIndex=2 windSum=? windValue=1
-debugShowActiveSpans id=5 (369.961151,137.980698 383.970093,121.298294 406.213287,121.298294) t=0.883517581 (401.143127,121.524643) other=4 otherT=0.0881931013 otherIndex=3 windSum=? windValue=1
-debugShowActiveSpans id=5 (369.961151,137.980698 383.970093,121.298294 406.213287,121.298294) t=0.998890674 (406.16394,121.298317) other=3 otherT=0.999082394 otherIndex=3 windSum=? windValue=1
-debugShowActiveSpans id=5 (369.961151,137.980698 383.970093,121.298294 406.213287,121.298294) t=0.999874327 (406.207703,121.298294) other=4 otherT=1.0265934e-07 otherIndex=1 windSum=? windValue=1
-debugShowActiveSpans id=6 (406.213287,121.298294 369.961151,137.980698) t=0 (406.213287,121.298294) other=5 otherT=1 otherIndex=4 windSum=? windValue=1
-debugShowActiveSpans id=6 (406.213287,121.298294 369.961151,137.980698) t=0.8038997 (377.070221,134.709274) other=3 otherT=0.258355433 otherIndex=1 windSum=? windValue=1
-</div>
-
-<div id="quad61b">
-debugShowQuadLineIntersection wtTs[0]=0.914354357 (369.848602,145.680267 382.360413,121.298294 406.207703,121.298294) (402.206024,121.477142) wtTs[1]=1 (406.207703,121.298294) wnTs[0]=0.0696842 (406.207703,121.298294 348.781738,123.864815) (402.206024,121.477142) wnTs[1]=0 (406.207703,121.298294)
-debugShowQuadIntersection wtTs[0]=0.999082394 (369.848602,145.680267 382.360413,121.298294 406.207703,121.298294) (406.16394,121.298317) wnTs[0]=0.998891 (369.961151,137.980698 383.970093,121.298294 406.213287,121.298294) (406.16394,121.298317)
-debugShowQuadLineIntersection wtTs[0]=0.258355433 (369.848602,145.680267 382.360413,121.298294 406.207703,121.298294) (377.070221,134.709274) wnTs[0]=0.8039 (406.213287,121.298294 369.961151,137.980698) (377.070221,134.709274)
-debugShowQuadLineIntersection wtTs[0]=0.883517581 (369.961151,137.980698 383.970093,121.298294 406.213287,121.298294) (401.143127,121.524643) wtTs[1]=0.999874327 (406.207703,121.298294) wnTs[0]=0.0881931 (406.207703,121.298294 348.781738,123.864815) (401.143127,121.524643) wnTs[1]=1.0265934e-07 (406.207703,121.298294)
-debugShowQuadLineIntersection wtTs[0]=0 (369.961151,137.980698 383.970093,121.298294 406.213287,121.298294) (369.961151,137.980698) wtTs[1]=1 (406.213287,121.298294) wnTs[0]=1 (406.213287,121.298294 369.961151,137.980698) (369.961151,137.980698) wnTs[1]=0 (406.213287,121.298294)
-</div>
-
-<div id="quad61c">
-debugShowActiveSpans id=3 (369.848602,145.680267 382.360413,121.298294 406.207703,121.298294) t=0.914354357 (402.206024,121.477142) other=4 otherT=0.0696842495 otherIndex=2 windSum=-1 windValue=1
-debugShowActiveSpans id=4 (406.207703,121.298294 348.781738,123.864815) t=1.0265934e-07 (406.207703,121.298294) other=5 otherT=0.999874327 otherIndex=3 windSum=-1 windValue=1
-debugShowActiveSpans id=5 (369.961151,137.980698 383.970093,121.298294 406.213287,121.298294) t=0.998890674 (406.16394,121.298317) other=3 otherT=0.999082394 otherIndex=3 windSum=-1 windValue=1
+<div id="cubicOp19i">
+debugShowActiveSpans id=3 (1,2 2,6 2,0 1,0) t=0 (1,2) tEnd=0.578464835 other=4 otherT=1 otherIndex=2 windSum=? windValue=1 oppValue=0
+debugShowActiveSpans id=3 (1,2 2,6 2,0 1,0) t=0.578464835 (1.73152983,2) tEnd=0.692069746 other=2 otherT=0.711411698 otherIndex=1 windSum=? windValue=1 oppValue=0
+debugShowActiveSpans id=3 (1,2 2,6 2,0 1,0) t=0.692069746 (1.63932765,1.25154662) tEnd=1 other=1 otherT=0.522705723 otherIndex=2 windSum=? windValue=1 oppValue=0
+debugShowActiveSpans id=4 (1,0 1,2) t=0 (1,0) tEnd=0.637627564 other=3 otherT=1 otherIndex=4 windSum=? windValue=1 oppValue=0
+debugShowActiveSpans id=4 (1,0 1,2) t=0.637627564 (1,1.27525508) tEnd=1 other=1 otherT=0.40824829 otherIndex=1 windSum=? windValue=1 oppValue=0
+debugShowActiveSpans id=1 (0,2 0,0.5 6,2) t=0 (0,2) tEnd=0.40824829 other=2 otherT=1 otherIndex=4 windSum=? windValue=1 oppValue=0
+debugShowActiveSpans id=1 (0,2 0,0.5 6,2) t=0.40824829 (1,1.27525508) tEnd=0.522705723 other=4 otherT=0.637627564 otherIndex=1 windSum=? windValue=1 oppValue=0
+debugShowActiveSpans id=1 (0,2 0,0.5 6,2) t=0.522705723 (1.63932765,1.25154662) tEnd=1 other=3 otherT=0.692069746 otherIndex=3 windSum=? windValue=1 oppValue=0
+debugShowActiveSpans id=2 (6,2 0,2) t=0 (6,2) tEnd=0.711411698 other=1 otherT=1 otherIndex=3 windSum=? windValue=1 oppValue=0
+debugShowActiveSpans id=2 (6,2 0,2) t=0.711411698 (1.73152983,2) tEnd=0.833333333 other=3 otherT=0.578464835 otherIndex=2 windSum=? windValue=1 oppValue=0
+debugShowActiveSpans id=2 (6,2 0,2) t=0.833333333 (1,2) tEnd=1 other=3 otherT=0 otherIndex=1 windSum=? windValue=1 oppValue=0
</div>
</div>
@@ -169,18 +21,7 @@
<script type="text/javascript">
var testDivs = [
- quad61,
- quad61b,
- quad61c,
- quad60,
- quad59b,
- quad59,
- quad58b,
- quad58a,
- quad57c,
- quad57b,
- quad57a,
- quad56,
+ cubicOp19i,
];
var decimal_places = 3; // make this 3 to show more precision
@@ -197,7 +38,7 @@
var srcLeft, srcTop;
var srcWidth, srcHeight;
var screenWidth, screenHeight;
-var drawnPts, drawnLines, drawnQuads, deferredLines, deferredQuads;
+var drawnPts, drawnLines, drawnQuads, drawnCubics, deferredLines, deferredQuads, deferredCubics;
var ptLabels = true;
var digit_mode = false;
@@ -216,31 +57,49 @@
var SPAN_L_T = 6;
var SPAN_L_TX = 7;
var SPAN_L_TY = 8;
-var SPAN_L_OTHER = 9;
-var SPAN_L_OTHERT = 10;
-var SPAN_L_OTHERI = 11;
-var SPAN_L_SUM = 12;
-var SPAN_L_VAL = 13;
+var SPAN_L_TEND = 9;
+var SPAN_L_OTHER = 10;
+var SPAN_L_OTHERT = 11;
+var SPAN_L_OTHERI = 12;
+var SPAN_L_SUM = 13;
+var SPAN_L_VAL = 14;
+var SPAN_L_OPP = 15;
var SPAN_X3 = 6;
var SPAN_Y3 = 7;
var SPAN_Q_T = 8;
var SPAN_Q_TX = 9;
var SPAN_Q_TY = 10;
-var SPAN_Q_OTHER = 11;
-var SPAN_Q_OTHERT = 12;
-var SPAN_Q_OTHERI = 13;
-var SPAN_Q_SUM = 14;
-var SPAN_Q_VAL = 15;
+var SPAN_Q_TEND = 11;
+var SPAN_Q_OTHER = 12;
+var SPAN_Q_OTHERT = 13;
+var SPAN_Q_OTHERI = 14;
+var SPAN_Q_SUM = 15;
+var SPAN_Q_VAL = 16;
+var SPAN_Q_OPP = 17;
+
+var SPAN_X4 = 8;
+var SPAN_Y4 = 9;
+var SPAN_C_T = 10;
+var SPAN_C_TX = 11;
+var SPAN_C_TY = 12;
+var SPAN_C_TEND = 13;
+var SPAN_C_OTHER = 14;
+var SPAN_C_OTHERT = 15;
+var SPAN_C_OTHERI = 16;
+var SPAN_C_SUM = 17;
+var SPAN_C_VAL = 18;
+var SPAN_C_OPP = 19;
var ACTIVE_LINE_SPAN = 1;
var ACTIVE_QUAD_SPAN = 2;
-var INTERSECT_QUAD_LINE = 3;
-var INTERSECT_QUAD_LINE_2 = 4;
-var INTERSECT_QUAD_LINE_NO = 5;
-var INTERSECT_QUAD = 6;
-var INTERSECT_QUAD_2 = 7;
-var INTERSECT_QUAD_NO = 8;
+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;
function strs_to_nums(strs) {
var result = [];
@@ -266,8 +125,9 @@
}
function parse_debugShowActiveSpans(test, title) {
- var re_quad = construct_regexp(" id=IDX (PT_VAL PT_VAL PT_VAL) t=T_VAL (PT_VAL) other=IDX otherT=T_VAL otherIndex=IDX windSum=OPT windValue=IDX");
- var re_line = construct_regexp(" id=IDX (PT_VAL PT_VAL) t=T_VAL (PT_VAL) other=IDX otherT=T_VAL otherIndex=IDX windSum=OPT windValue=IDX");
+ var re_cubic = construct_regexp(" id=IDX (PT_VAL PT_VAL PT_VAL PT_VAL) t=T_VAL (PT_VAL) tEnd=T_VAL other=IDX otherT=T_VAL otherIndex=IDX windSum=OPT windValue=IDX oppValue=IDX");
+ var re_quad = construct_regexp(" id=IDX (PT_VAL PT_VAL PT_VAL) t=T_VAL (PT_VAL) tEnd=T_VAL other=IDX otherT=T_VAL otherIndex=IDX windSum=OPT windValue=IDX oppValue=IDX");
+ var re_line = construct_regexp(" id=IDX (PT_VAL PT_VAL) t=T_VAL (PT_VAL) tEnd=T_VAL other=IDX otherT=T_VAL otherIndex=IDX windSum=OPT windValue=IDX oppValue=IDX");
var strs = test.split("debugShowActiveSpans");
if (strs.length == 1)
@@ -288,6 +148,11 @@
var quad = strs_to_nums(quadStrs);
spans.push(ACTIVE_QUAD_SPAN);
spans.push(quad);
+ } else if (re_cubic.test(str)) {
+ var cubicStrs = re_cubic.exec(str);
+ var cubic = strs_to_nums(cubicStrs);
+ spans.push(ACTIVE_CUBIC_SPAN);
+ spans.push(cubic);
}
}
if (spans.length >= 1) {
@@ -305,6 +170,7 @@
}
}
+// FIXME: add cubic support
function parse_intersections(test, title) {
var re_quad_line = construct_regexp(" wtTs[0]=T_VAL (PT_VAL PT_VAL PT_VAL) (PT_VAL) wnTs[0]=T_VAL (PT_VAL PT_VAL) (PT_VAL)");
var re_quad_line_2 = construct_regexp(" wtTs[0]=T_VAL (PT_VAL PT_VAL PT_VAL) (PT_VAL) wtTs[1]=T_VAL (PT_VAL) wnTs[0]=T_VAL (PT_VAL PT_VAL) (PT_VAL) wnTs[1]=T_VAL (PT_VAL)");
@@ -353,8 +219,10 @@
scanType = scan;
continue;
}
- if (scanType == ACTIVE_LINE_SPAN || scanType == ACTIVE_QUAD_SPAN) {
- var last = scanType == ACTIVE_QUAD_SPAN ? SPAN_X3 : SPAN_X2;
+ if (scanType == ACTIVE_LINE_SPAN || scanType == ACTIVE_QUAD_SPAN
+ || scanType == ACTIVE_CUBIC_SPAN) {
+ var last = scanType == ACTIVE_CUBIC_SPAN ? SPAN_X4
+ : scanType == ACTIVE_QUAD_SPAN ? SPAN_X3 : SPAN_X2;
for (var idx = SPAN_X1; idx <= last; idx += 2) {
xmin = Math.min(xmin, scan[idx]);
xmax = Math.max(xmax, scan[idx]);
@@ -453,6 +321,21 @@
deferredLines.push(y2);
}
+function drawLinePartial(x1, y1, x2, y2, t1, t2) {
+ var dx = x1 - x2;
+ var dy = y1 - y2;
+ var ax = x1 - t1 * dx;
+ var ay = y1 - t1 * dy;
+ var bx = x1 - t2 * dx;
+ var by = y1 - t2 * dy;
+ ctx.beginPath();
+ ctx.moveTo((ax - srcLeft) * scale,
+ (ay - srcTop) * scale);
+ ctx.lineTo((bx - srcLeft) * scale,
+ (by - srcTop) * scale);
+ ctx.stroke();
+}
+
function drawQuad(x1, y1, x2, y2, x3, y3, selected) {
for (var pts = 0; pts < drawnQuads.length; pts += 6) {
if (x1 == drawnQuads[pts] && y1 == drawnQuads[pts + 1]) {
@@ -490,7 +373,183 @@
deferredQuads.push(y3);
}
+function interp(A, B, t) {
+ return A + (B - A) * t;
+}
+
+function interp_quad_coords(x1, x2, x3, t)
+{
+ var ab = interp(x1, x2, t);
+ var bc = interp(x2, x3, t);
+ var abc = interp(ab, bc, t);
+ return abc;
+}
+
+function drawQuadPartial(x1, y1, x2, y2, x3, y3, t1, t2) {
+ var ax = interp_quad_coords(x1, x2, x3, t1);
+ var ay = interp_quad_coords(y1, y2, y3, t1);
+ var dx = interp_quad_coords(x1, x2, x3, (t1 + t2) / 2);
+ var dy = interp_quad_coords(y1, y2, y3, (t1 + t2) / 2);
+ var cx = interp_quad_coords(x1, x2, x3, t2);
+ var cy = interp_quad_coords(y1, y2, y3, t2);
+ var bx = 2*dx - (ax + cx)/2;
+ var by = 2*dy - (ay + cy)/2;
+ ctx.beginPath();
+ ctx.moveTo((ax - srcLeft) * scale,
+ (ay - srcTop) * scale);
+ ctx.quadraticCurveTo((bx - srcLeft) * scale,
+ (by - srcTop) * scale,
+ (cx - srcLeft) * scale,
+ (cy - srcTop) * scale);
+ ctx.stroke();
+}
+
+function drawCubic(x1, y1, x2, y2, x3, y3, x4, y4, selected) {
+ for (var pts = 0; pts < drawnCubics.length; pts += 8) {
+ if (x1 == drawnCubics[pts] && y1 == drawnCubics[pts + 1]) {
+ return;
+ }
+ if (x2 == drawnCubics[pts + 2] && x2 == drawnCubics[pts + 3]) {
+ return;
+ }
+ if (x2 == drawnCubics[pts + 4] && x2 == drawnCubics[pts + 5]) {
+ return;
+ }
+ if (x2 == drawnCubics[pts + 6] && x2 == drawnCubics[pts + 7]) {
+ return;
+ }
+ }
+ if (selected) {
+ drawnCubics.push(x1);
+ drawnCubics.push(y1);
+ drawnCubics.push(x2);
+ drawnCubics.push(y2);
+ drawnCubics.push(x3);
+ drawnCubics.push(y3);
+ drawnCubics.push(x4);
+ drawnCubics.push(y4);
+ ctx.beginPath();
+ ctx.moveTo((x1 - srcLeft) * scale,
+ (y1 - srcTop) * scale);
+ ctx.bezierCurveTo((x2 - srcLeft) * scale,
+ (y2 - srcTop) * scale,
+ (x3 - srcLeft) * scale,
+ (y3 - srcTop) * scale,
+ (x4 - srcLeft) * scale,
+ (y4 - srcTop) * scale);
+ ctx.stroke();
+ return;
+ }
+ deferredCubics.push(x1);
+ deferredCubics.push(y1);
+ deferredCubics.push(x2);
+ deferredCubics.push(y2);
+ deferredCubics.push(x3);
+ deferredCubics.push(y3);
+ deferredCubics.push(x4);
+ deferredCubics.push(y4);
+}
+
+function interp_cubic_coords(x1, x2, x3, x4, t)
+{
+ var ab = interp(x1, x2, t);
+ var bc = interp(x2, x3, t);
+ var cd = interp(x3, x4, t);
+ var abc = interp(ab, bc, t);
+ var bcd = interp(bc, cd, t);
+ var abcd = interp(abc, bcd, t);
+ return abcd;
+}
+
+function drawCubicPartial(x1, y1, x2, y2, x3, y3, x4, y4, t1, t2) {
+ var ax = interp_cubic_coords(x1, x2, x3, x4, t1);
+ var ay = interp_cubic_coords(y1, y2, y3, y4, t1);
+ var ex = interp_cubic_coords(x1, x2, x3, x4, (t1*2+t2)/3);
+ var ey = interp_cubic_coords(y1, y2, y3, y4, (t1*2+t2)/3);
+ var fx = interp_cubic_coords(x1, x2, x3, x4, (t1+t2*2)/3);
+ var fy = interp_cubic_coords(y1, y2, y3, y4, (t1+t2*2)/3);
+ var dx = interp_cubic_coords(x1, x2, x3, x4, t2);
+ var dy = interp_cubic_coords(y1, y2, y3, y4, t2);
+ var mx = ex * 27 - ax * 8 - dx;
+ var my = ey * 27 - ay * 8 - dy;
+ var nx = fx * 27 - ax - dx * 8;
+ var ny = fy * 27 - ay - dy * 8;
+ var bx = (mx * 2 - nx) / 18;
+ var by = (my * 2 - ny) / 18;
+ var cx = (nx * 2 - mx) / 18;
+ var cy = (ny * 2 - my) / 18;
+ ctx.beginPath();
+ ctx.moveTo((ax - srcLeft) * scale,
+ (ay - srcTop) * scale);
+ ctx.bezierCurveTo((bx - srcLeft) * scale,
+ (by - srcTop) * scale,
+ (cx - srcLeft) * scale,
+ (cy - srcTop) * scale,
+ (dx - srcLeft) * scale,
+ (dy - srcTop) * scale,
+ (ex - srcLeft) * scale,
+ (ey - srcTop) * scale);
+ ctx.stroke();
+}
+
+function drawPartial(test) {
+ ctx.lineWidth = 3;
+ ctx.strokeStyle = "rgba(0,0,255, 0.3)";
+ var scanType = -1;
+ var partIndex = 0;
+ for (var scansStr in test) {
+ var scans = parseInt(scansStr);
+ var scan = test[scans];
+ if (scanType == -1) {
+ scanType = scan;
+ continue;
+ }
+ partIndex++;
+ var hasId = scanType == ACTIVE_LINE_SPAN || scanType == ACTIVE_QUAD_SPAN
+ || scanType == ACTIVE_CUBIC_SPAN ? SPAN_ID : -1;
+ if (hasId < 0) {
+ continue;
+ }
+ var types = [scanType == ACTIVE_LINE_SPAN ? 0 : scanType == ACTIVE_QUAD_SPAN ? 1 : 2];
+ var x1 = scan[SPAN_X1];
+ var y1 = scan[SPAN_Y1];
+ var x2 = scan[SPAN_X2];
+ var y2 = scan[SPAN_Y2];
+ var x3, y3, x3, y4, t1, t2;
+ switch(scanType) {
+ case ACTIVE_LINE_SPAN:
+ t1 = scan[SPAN_L_T];
+ t2 = scan[SPAN_L_TEND];
+ drawLinePartial(x1, y1, x2, y2, t1, t2);
+ break;
+ case ACTIVE_QUAD_SPAN:
+ x3 = scan[SPAN_X3];
+ y3 = scan[SPAN_Y3];
+ t1 = scan[SPAN_Q_T];
+ t2 = scan[SPAN_Q_TEND];
+ drawQuadPartial(x1, y1, x2, y2, x3, y3, t1, t2);
+ break;
+ case ACTIVE_CUBIC_SPAN:
+ x3 = scan[SPAN_X3];
+ y3 = scan[SPAN_Y3];
+ x4 = scan[SPAN_X4];
+ y4 = scan[SPAN_Y4];
+ t1 = scan[SPAN_C_T];
+ t2 = scan[SPAN_C_TEND];
+ drawCubicPartial(x1, y1, x2, y2, x3, y3, x4, y4, t1, t2);
+ break;
+ }
+ scanType = -1;
+ }
+}
+
function drawDeferred() {
+ for (var pts = 0; pts < deferredCubics.length; pts += 8) {
+ drawCubic(deferredCubics[pts], deferredCubics[pts + 1],
+ deferredCubics[pts + 2], deferredCubics[pts + 3],
+ deferredCubics[pts + 4], deferredCubics[pts + 5],
+ deferredCubics[pts + 6], deferredCubics[pts + 7], true);
+ }
for (var pts = 0; pts < deferredQuads.length; pts += 6) {
drawQuad(deferredQuads[pts], deferredQuads[pts + 1],
deferredQuads[pts + 2], deferredQuads[pts + 3],
@@ -515,8 +574,10 @@
drawnPts = [];
drawnLines = [];
drawnQuads = [];
+ drawnCubics = [];
deferredLines = [];
deferredQuads = [];
+ deferredCubics = [];
var scanType = -1;
var partIndex = 0;
for (var scansStr in test) {
@@ -527,9 +588,10 @@
continue;
}
partIndex++;
- var hasId = scanType == ACTIVE_LINE_SPAN || scanType == ACTIVE_QUAD_SPAN ? SPAN_ID : -1;
+ var hasId = scanType == ACTIVE_LINE_SPAN || scanType == ACTIVE_QUAD_SPAN
+ || scanType == ACTIVE_CUBIC_SPAN ? SPAN_ID : -1;
if (hasId >= 0 && curId != scan[hasId]) {
- curId = hasId;
+ curId = scan[hasId];
firstIdx = lastIdx = partIndex;
index_tst++;
var nextIdx = lastIdx + 1;
@@ -549,9 +611,9 @@
scanType = -1;
continue;
}
- var types = [scanType == ACTIVE_LINE_SPAN ? 0 : 1];
+ var types = [scanType == ACTIVE_LINE_SPAN ? 0 : scanType == ACTIVE_QUAD_SPAN ? 1 : 2];
var pts = [];
- if (scanType == ACTIVE_LINE_SPAN || scanType == ACTIVE_QUAD_SPAN) {
+ if (scanType == ACTIVE_LINE_SPAN || scanType == ACTIVE_QUAD_SPAN || scanType == ACTIVE_CUBIC_SPAN) {
pts.push(SPAN_X1);
} else {
pts.push(scanType != INTERSECT_QUAD_NO && scanType != INTERSECT_QUAD_LINE_NO ? 2 : 1);
@@ -563,7 +625,11 @@
for (var typeIndex = 0; typeIndex < types.length; ++typeIndex) {
var type = types[typeIndex];
var index = pts[typeIndex];
- if (type == 1) {
+ if (type == 2) {
+ drawCubic(scan[index + 0], scan[index + 1], scan[index + 2], scan[index + 3],
+ scan[index + 4], scan[index + 5], scan[index + 6], scan[index + 7],
+ selected);
+ } else if (type == 1) {
drawQuad(scan[index + 0], scan[index + 1], scan[index + 2], scan[index + 3],
scan[index + 4], scan[index + 5], selected);
} else {
@@ -576,7 +642,7 @@
for (var typeIndex = 0; typeIndex < types.length; ++typeIndex) {
var type = types[typeIndex];
var index = pts[typeIndex];
- for (var idx = pts[typeIndex]; idx < (type == 1 ? pts[typeIndex] + 6 : pts[typeIndex] + 4); idx += 2) {
+ for (var idx = pts[typeIndex]; idx < pts[typeIndex] + (type + 1) * 2; idx += 2) {
var screenX = (scan[idx] - srcLeft) * scale;
var screenY = (scan[idx + 1] - srcTop) * scale;
debugText += screenX.toFixed(decimal_places) + ", ";
@@ -591,7 +657,7 @@
for (var typeIndex = 0; typeIndex < types.length; ++typeIndex) {
var type = types[typeIndex];
var index = pts[typeIndex];
- for (var idx = pts[typeIndex]; idx < (type == 1 ? pts[typeIndex] + 6 : pts[typeIndex] + 4); idx += 2) {
+ for (var idx = pts[typeIndex]; idx < pts[typeIndex] + (type + 1) * 2; idx += 2) {
drawPoint(scan[idx], scan[idx + 1]);
}
}
@@ -601,7 +667,9 @@
infoText += hasId >= 0 ? "id=" + scan[hasId] : partIndex;
}
if (intersect_mode && selected) {
- if (scanType == ACTIVE_QUAD_SPAN) {
+ if (scanType == ACTIVE_CUBIC_SPAN) {
+ infoText += " t=" + scan[SPAN_C_T];
+ } else if (scanType == ACTIVE_QUAD_SPAN) {
infoText += " t=" + scan[SPAN_Q_T];
} else if (scanType == ACTIVE_LINE_SPAN) {
infoText += " t=" + scan[SPAN_L_T];
@@ -623,7 +691,9 @@
}
if (intersect_mode && selected) {
ctx.fillStyle="rgba(50,100,200, 1.0)";
- if (scanType == ACTIVE_QUAD_SPAN) {
+ if (scanType == ACTIVE_CUBIC_SPAN) {
+ drawPoint(scan[SPAN_C_TX], scan[SPAN_C_TY]);
+ } else if (scanType == ACTIVE_QUAD_SPAN) {
drawPoint(scan[SPAN_Q_TX], scan[SPAN_Q_TY]);
} else if (scanType == ACTIVE_LINE_SPAN) {
drawPoint(scan[SPAN_L_TX], scan[SPAN_L_TY]);
@@ -638,6 +708,7 @@
scanType = -1;
}
drawDeferred();
+ drawPartial(test);
}
function drawTop() {
diff --git a/experimental/Intersection/op.htm b/experimental/Intersection/op.htm
index c3ae3c5..6d45854 100644
--- a/experimental/Intersection/op.htm
+++ b/experimental/Intersection/op.htm
@@ -3534,11 +3534,71 @@
pathB.close();
</div>
+<div id="cubicOp15d">
+ path.setFillType(SkPath::kWinding_FillType);
+ path.moveTo(0,1);
+ path.cubicTo(3,6, 2,0, 2,1);
+ path.close();
+ pathB.setFillType(SkPath::kWinding_FillType);
+ pathB.moveTo(0,2);
+ pathB.cubicTo(1,2, 1,0, 6,3);
+ pathB.close();
+</div>
+
+<div id="cubicOp16d">
+ path.setFillType(SkPath::kWinding_FillType);
+ path.moveTo(0,2);
+ path.cubicTo(0,1, 3,0, 1,0);
+ path.close();
+ pathB.setFillType(SkPath::kWinding_FillType);
+ pathB.moveTo(0,3);
+ pathB.cubicTo(0,1, 2,0, 1,0);
+ pathB.close();
+</div>
+
+<div id="cubicOp17d">
+ path.setFillType(SkPath::kWinding_FillType);
+ path.moveTo(0,2);
+ path.cubicTo(0,2, 4,0, 2,1);
+ path.close();
+ pathB.setFillType(SkPath::kWinding_FillType);
+ pathB.moveTo(0,4);
+ pathB.cubicTo(1,2, 2,0, 2,0);
+ pathB.close();
+</div>
+
+<div id="cubicOp18d">
+ path.setFillType(SkPath::kWinding_FillType);
+ path.moveTo(0,1);
+ path.cubicTo(3,5, 2,0, 2,1);
+ path.close();
+ pathB.setFillType(SkPath::kWinding_FillType);
+ pathB.moveTo(0,2);
+ pathB.cubicTo(1,2, 1,0, 5,3);
+ pathB.close();
+</div>
+
+<div id="cubicOp19i">
+ path.setFillType(SkPath::kWinding_FillType);
+ path.moveTo(0,2);
+ path.cubicTo(0,1, 2,1, 6,2);
+ path.close();
+ pathB.setFillType(SkPath::kWinding_FillType);
+ pathB.moveTo(1,2);
+ pathB.cubicTo(2,6, 2,0, 1,0);
+ pathB.close();
+</div>
+
</div>
<script type="text/javascript">
var testDivs = [
+ cubicOp19i,
+ cubicOp18d,
+ cubicOp17d,
+ cubicOp16d,
+ cubicOp15d,
cubicOp14d,
cubicOp13d,
cubicOp12d,
diff --git a/experimental/Intersection/qc.htm b/experimental/Intersection/qc.htm
index 861bdc0..f22921a 100644
--- a/experimental/Intersection/qc.htm
+++ b/experimental/Intersection/qc.htm
@@ -1977,11 +1977,34 @@
{{x = 0, y = 1}, {x = 1.9274705288631189e-19, y = 1.0000000000000002}, {x = 0.0017190297609673323, y = 0.99828097023903239}, {x = 0.0053709083094631276, y = 0.99505672974365911}}
</div>
+<div id="cubicOp16d">
+{{0,2},{0,1},{3,0},{1,0}},
+{{0,3},{0,1},{2,0},{1,0}},
+
+ {{0,2}, {0.0229970175,1.6585632}, {0.366509308,1.33437416}},
+ {{0.366509308,1.33437416}, {0.710021598,1.01018513}, {1.09808495,0.737739381}},
+ {{1.09808495,0.737739381}, {1.40607875,0.517813127}, {1.57937247,0.352342403}},
+ {{1.57937247,0.352342403}, {1.75266619,0.186871679}, {1.64451042,0.0942001592}},
+ {{1.64451042,0.0942001592}, {1.53635465,0.00152863961}, {1,0}},
+
+ {{0,3}, {0.0263932023,2.17082039}, {0.352786405,1.57082039}},
+ {{0.352786405,1.57082039}, {0.679179607,0.970820393}, {0.988854382,0.6}},
+ {{0.988854382,0.6}, {1.23200941,0.3}, {1.27672209,0.15}},
+ {{1.27672209,0.15}, {1.32143477,9.25185854e-17}, {1,0}},
+</div>
+
+<div id="quadOp16d">
+ {{1.64451042,0.0942001592}, {1.53635465,0.00152863961}, {1,0}},
+ {{1.27672209,0.15}, {1.32143477,9.25185854e-17}, {1,0}},
+</div>
+
</div>
<script type="text/javascript">
var testDivs = [
+ quadOp16d,
+ cubicOp16d,
cubicTest7,
cubicTest6,
cubicTest5,
@@ -2253,7 +2276,7 @@
var curveStrs = test.split("{{");
if (curveStrs.length == 1)
curveStrs = test.split("=(");
- var pattern = /[a-z$=]?-?\d+\.*\d*/g;
+ var pattern = /[a-z$=]?-?\d+\.*\d*e?-?\d*/g;
var curves = [];
for (var c in curveStrs) {
var curveStr = curveStrs[c];