diff options
Diffstat (limited to 'experimental')
27 files changed, 752 insertions, 288 deletions
diff --git a/experimental/Intersection/CubicBezierClip_Test.cpp b/experimental/Intersection/CubicBezierClip_Test.cpp index 1a9092fc9b..9133980f58 100644 --- a/experimental/Intersection/CubicBezierClip_Test.cpp +++ b/experimental/Intersection/CubicBezierClip_Test.cpp @@ -13,8 +13,10 @@ void CubicBezierClip_Test() { 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 3be8c21877..137b0d68d6 100644 --- a/experimental/Intersection/CubicConvexHull.cpp +++ b/experimental/Intersection/CubicConvexHull.cpp @@ -54,11 +54,11 @@ bool intersect(double minT1, double maxT1, double minT2, double maxT2) { 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 f25a046858..02a39d6d21 100644 --- a/experimental/Intersection/CubicIntersection.cpp +++ b/experimental/Intersection/CubicIntersection.cpp @@ -17,6 +17,7 @@ static const double tLimits[2][2] = {{0.516980827, 0.516981209}, {0.647714088, 0 #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 @@ static int quadPart(const Cubic& cubic, double tStart, double tEnd, Quadratic& s 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 @@ static bool doIntersect(const Cubic& cubic1, double t1s, double t1m, double t1e, 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 @@ bool intersect2(const Cubic& c1, const Cubic& c2, Intersections& i) { 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 @@ bool intersect3(const Cubic& c1, const Cubic& c2, Intersections& i) { 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 bdbf3de60f..9dea332441 100644 --- a/experimental/Intersection/CubicIntersection_Test.cpp +++ b/experimental/Intersection/CubicIntersection_Test.cpp @@ -18,8 +18,10 @@ static void standardTestCases() { 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 @@ static const Cubic testSet[] = { 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 @@ void CubicIntersection_OneOffTest() { 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_RandTest() { } 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 bd1356aada..f7c0c12d4c 100644 --- a/experimental/Intersection/CubicReduceOrder.cpp +++ b/experimental/Intersection/CubicReduceOrder.cpp @@ -24,10 +24,13 @@ static int coincident_line(const Cubic& cubic, Cubic& reduction) { 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 @@ static int vertical_line(const Cubic& cubic, Cubic& reduction) { 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 @@ static int check_quadratic(const Cubic& cubic, Cubic& reduction) { 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 @@ static int check_linear(const Cubic& cubic, Cubic& reduction, // 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 @@ http://kaba.hilvi.org // 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 @@ int reduceOrder(const Cubic& cubic, Cubic& reduction, ReduceOrder_Flags allowQua 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 1011fab9e9..79b34288d3 100644 --- a/experimental/Intersection/CubicReduceOrder_Test.cpp +++ b/experimental/Intersection/CubicReduceOrder_Test.cpp @@ -46,49 +46,56 @@ void CubicReduceOrder_Test() { 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 @@ void CubicReduceOrder_Test() { 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 @@ void CubicReduceOrder_Test() { 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 @@ void CubicReduceOrder_Test() { 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 dc4b51b2fd..707cfd10ba 100644 --- a/experimental/Intersection/CubicToQuadratics.cpp +++ b/experimental/Intersection/CubicToQuadratics.cpp @@ -102,7 +102,7 @@ int cubic_to_quadratics(const Cubic& cubic, double precision, SkTDArray<Quadrati 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 @@ static void addTs(const Cubic& cubic, double precision, double start, double end // 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 @@ void cubic_to_quadratics(const Cubic& cubic, double precision, SkTDArray<double> 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 b67ea7e4d2..555d7def36 100644 --- a/experimental/Intersection/CurveIntersection.h +++ b/experimental/Intersection/CurveIntersection.h @@ -26,13 +26,18 @@ void tangent(const _Line& line, _Point& result); 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 c6b24861e3..ed3ec218f6 100644 --- a/experimental/Intersection/DataTypes.h +++ b/experimental/Intersection/DataTypes.h @@ -34,11 +34,13 @@ inline bool AlmostEqualUlps(double A, double B) { return AlmostEqualUlps((float) 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 approximately_zero(double x) { } 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 @@ inline bool approximately_equal(double x, double y) { #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 approximately_greater_than_one(double x) { } 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 approximately_less_than_zero(double x) { } 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 approximately_negative(double x) { } 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 7bf400e4c7..be3f57fcdb 100644 --- a/experimental/Intersection/EdgeWalker.cpp +++ b/experimental/Intersection/EdgeWalker.cpp @@ -234,7 +234,7 @@ static SkPath::Verb QuadReduceOrder(SkPoint a[4]) { 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 @@ static SkPath::Verb CubicReduceOrder(SkPoint a[4]) { 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 f7663e4001..f55bab7764 100644 --- a/experimental/Intersection/Intersection_Tests.cpp +++ b/experimental/Intersection/Intersection_Tests.cpp @@ -14,13 +14,16 @@ void parseSVG(); 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 f647787e07..af658d9c45 100644 --- a/experimental/Intersection/Intersection_Tests.h +++ b/experimental/Intersection/Intersection_Tests.h @@ -12,6 +12,7 @@ void ConvexHull_X_Test(); 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 LineIntersection_Test(); 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 26fcc3f728..3de45cb4c7 100644 --- a/experimental/Intersection/Intersections.cpp +++ b/experimental/Intersection/Intersections.cpp @@ -122,16 +122,22 @@ void Intersections::remove(double one, double two, const _Point& startPt, const || 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 449849c143..33fc0ac82a 100644 --- a/experimental/Intersection/Intersections.h +++ b/experimental/Intersection/Intersections.h @@ -79,9 +79,11 @@ public: 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 b81a87e421..adf01122ac 100644 --- a/experimental/Intersection/LineCubicIntersection_Test.cpp +++ b/experimental/Intersection/LineCubicIntersection_Test.cpp @@ -27,7 +27,8 @@ void LineCubicIntersection_Test() { 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 6c3986c7b4..3e7e230ac9 100644 --- a/experimental/Intersection/LineQuadraticIntersection_Test.cpp +++ b/experimental/Intersection/LineQuadraticIntersection_Test.cpp @@ -95,7 +95,7 @@ void LineQuadraticIntersection_Test() { 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 @@ static void* testQuadLineIntersectMain(void* data) 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 0d25faf982..1579f98884 100644 --- a/experimental/Intersection/QuadraticBezierClip_Test.cpp +++ b/experimental/Intersection/QuadraticBezierClip_Test.cpp @@ -47,8 +47,8 @@ static void standardTestCases() { 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 8bddee2268..4b8f254bab 100644 --- a/experimental/Intersection/QuadraticIntersection_Test.cpp +++ b/experimental/Intersection/QuadraticIntersection_Test.cpp @@ -20,8 +20,8 @@ static void standardTestCases() { 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 void standardTestCases() { } 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 @@ void QuadraticIntersection_PointFinder() { 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 700d4c556e..27c7a29bf2 100644 --- a/experimental/Intersection/QuadraticReduceOrder.cpp +++ b/experimental/Intersection/QuadraticReduceOrder.cpp @@ -21,10 +21,14 @@ static int coincident_line(const Quadratic& quad, Quadratic& reduction) { 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 @@ static int vertical_line(const Quadratic& quad, Quadratic& reduction) { 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 @@ static int horizontal_line(const Quadratic& quad, Quadratic& reduction) { 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 @@ static int check_linear(const Quadratic& quad, Quadratic& reduction, // 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 @@ bool isLinear(const Quadratic& quad, int startIndex, int endIndex) { // 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 @@ int reduceOrder(const Quadratic& quad, Quadratic& reduction) { 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 abf8fa7dc6..0c799c3541 100644 --- a/experimental/Intersection/QuadraticReduceOrder_Test.cpp +++ b/experimental/Intersection/QuadraticReduceOrder_Test.cpp @@ -22,7 +22,7 @@ static void oneOffTest() { 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 @@ static void standardTestCases() { 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 d33fda8ae9..fa8acea622 100644 --- a/experimental/Intersection/QuadraticUtilities.cpp +++ b/experimental/Intersection/QuadraticUtilities.cpp @@ -232,3 +232,13 @@ void xy_at_t(const Quadratic& quad, double t, double& x, double& y) { 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 b507b5f464..8308f3878f 100644 --- a/experimental/Intersection/QuadraticUtilities.h +++ b/experimental/Intersection/QuadraticUtilities.h @@ -38,5 +38,6 @@ int quadraticRootsValidT(const double A, const double B, const double C, double 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 0a75f2a1e4..5cfc3884d0 100644 --- a/experimental/Intersection/Simplify.cpp +++ b/experimental/Intersection/Simplify.cpp @@ -32,7 +32,7 @@ int gDebugMaxWindValue = SK_MaxS32; #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 @@ const bool gRunTestsInOneThread = false; #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 @@ const bool gRunTestsInOneThread = true; #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 @@ static SkPath::Verb QuadReduceOrder(const SkPoint a[3], 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 @@ static SkPath::Verb CubicReduceOrder(const SkPoint a[4], 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 @@ public: #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 @@ public: 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 @@ the same winding is shared by both. 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 08dda602d8..4c83be7b6f 100644 --- a/experimental/Intersection/SimplifyNew_Test.cpp +++ b/experimental/Intersection/SimplifyNew_Test.cpp @@ -3767,12 +3767,82 @@ static void cubicOp14d() { 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 43dceb4757..2ed8015be7 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 @@ debugShowActiveSpans id=5 (369.961151,137.980698 383.970093,121.298294 406.21328 <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 mouseX, mouseY; 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_Y2 = 5; 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 construct_regexp(pattern) { } 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 @@ function parse_debugShowActiveSpans(test, title) { 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 @@ function filter_str_by(id, str, regex, array) { } } +// 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 @@ function init(test) { 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 @@ function drawLine(x1, y1, x2, y2, selected) { 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 @@ function drawQuad(x1, y1, x2, y2, x3, y3, selected) { 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 @@ function draw(test, title) { drawnPts = []; drawnLines = []; drawnQuads = []; + drawnCubics = []; deferredLines = []; deferredQuads = []; + deferredCubics = []; var scanType = -1; var partIndex = 0; for (var scansStr in test) { @@ -527,9 +588,10 @@ function draw(test, title) { 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 @@ function draw(test, title) { 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 @@ function draw(test, title) { 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 @@ function draw(test, title) { 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 @@ function draw(test, title) { 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 @@ function draw(test, title) { 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 @@ function draw(test, title) { } 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 @@ function draw(test, title) { scanType = -1; } drawDeferred(); + drawPartial(test); } function drawTop() { diff --git a/experimental/Intersection/op.htm b/experimental/Intersection/op.htm index c3ae3c52a5..6d45854767 100644 --- a/experimental/Intersection/op.htm +++ b/experimental/Intersection/op.htm @@ -3534,11 +3534,71 @@ path.addRect(4, 13, 13, 16, SkPath::kCCW_Direction); 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 861bdc09bd..f22921a7da 100644 --- a/experimental/Intersection/qc.htm +++ b/experimental/Intersection/qc.htm @@ -1977,11 +1977,34 @@ quad=(1.20573276,0.813456177 1.2679289,0.830085346 1.33333333,0.851851852) {{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 @@ function parse(test, title) { 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]; |