diff options
21 files changed, 2002 insertions, 396 deletions
diff --git a/experimental/Intersection/CubicIntersection.cpp b/experimental/Intersection/CubicIntersection.cpp index fe146714a9..833ac273b0 100644 --- a/experimental/Intersection/CubicIntersection.cpp +++ b/experimental/Intersection/CubicIntersection.cpp @@ -356,6 +356,10 @@ static bool intersect3(const Cubic& cubic1, double t1s, double t1e, const Cubic& for (int i2 = 0; i2 <= ts2Count; ++i2) { const double tEnd2 = i2 < ts2Count ? ts2[i2] : 1; const double t2 = t2s + (t2e - t2s) * tEnd2; + if (cubic1 == cubic2 && t1Start >= t2Start) { + t2Start = t2; + continue; + } Quadratic s2; int o2 = quadPart(cubic2, t2Start, t2, s2); #if ONE_OFF_DEBUG @@ -392,10 +396,11 @@ static bool intersect3(const Cubic& cubic1, double t1s, double t1e, const Cubic& i.insertCoincidentPair(coStart[0], to1, coStart[1], to2, coPoint, p1); coStart[0] = -1; } - } else { + result = true; + } else if (cubic1 != cubic2 || !approximately_equal(to1, to2)) { i.insert(to1, to2, p1); + result = true; } - result = true; } else { double offset = precisionScale / 16; // FIME: const is arbitrary -- test & refine double c1Min = SkTMax(0., to1 - offset); @@ -520,44 +525,19 @@ int intersect(const Cubic& cubic, const Quadratic& quad, Intersections& i) { return i.used(); } -// FIXME: this needs to be recursive like intersect 3 -bool intersect(const Cubic& cubic, Intersections& i) { - SkTDArray<double> ts; - double precision = calcPrecision(cubic); - cubic_to_quadratics(cubic, precision, ts); - int tsCount = ts.count(); - if (tsCount == 1) { +/* http://www.ag.jku.at/compass/compasssample.pdf +( Self-Intersection Problems and Approximate Implicitization by Jan B. Thomassen +Centre of Mathematics for Applications, University of Oslo http://www.cma.uio.no janbth@math.uio.no +SINTEF Applied Mathematics http://www.sintef.no ) +describes a method to find the self intersection of a cubic by taking the gradient of the implicit +form dotted with the normal, and solving for the roots. My math foo is too poor to implement this.*/ + +int intersect(const Cubic& c, Intersections& i) { + // check to see if x or y end points are the extrema. Are other quick rejects possible? + if ((between(c[0].x, c[1].x, c[3].x) && between(c[0].x, c[2].x, c[3].x)) + || (between(c[0].y, c[1].y, c[3].y) && between(c[0].y, c[2].y, c[3].y))) { return false; } - double t1Start = 0; - Cubic part; - for (int idx = 0; idx < tsCount; ++idx) { - double t1 = ts[idx]; - Quadratic q1; - sub_divide(cubic, t1Start, t1, part); - demote_cubic_to_quad(part, q1); - double t2Start = t1; - for (int i2 = idx + 1; i2 <= tsCount; ++i2) { - const double t2 = i2 < tsCount ? ts[i2] : 1; - Quadratic q2; - sub_divide(cubic, t2Start, t2, part); - demote_cubic_to_quad(part, q2); - Intersections locals; - intersect2(q1, q2, locals); - for (int tIdx = 0; tIdx < locals.used(); ++tIdx) { - // discard intersections at cusp? (maximum curvature) - double t1sect = locals.fT[0][tIdx]; - double t2sect = locals.fT[1][tIdx]; - if (idx + 1 == i2 && t1sect == 1 && t2sect == 0) { - continue; - } - double to1 = t1Start + (t1 - t1Start) * t1sect; - double to2 = t2Start + (t2 - t2Start) * t2sect; - i.insert(to1, to2, locals.fPt[tIdx]); - } - t2Start = t2; - } - t1Start = t1; - } - return i.intersected(); + (void) intersect3(c, c, i); + return i.used(); } diff --git a/experimental/Intersection/CubicIntersection_Test.cpp b/experimental/Intersection/CubicIntersection_Test.cpp index fe5679fd17..b81abbb301 100644 --- a/experimental/Intersection/CubicIntersection_Test.cpp +++ b/experimental/Intersection/CubicIntersection_Test.cpp @@ -134,6 +134,9 @@ static const Cubic testSet[] = { const size_t testSetCount = sizeof(testSet) / sizeof(testSet[0]); static const Cubic newTestSet[] = { +{{0,1}, {3,6}, {1,0}, {5,2}}, +{{0,1}, {2,5}, {1,0}, {6,3}}, + {{1,2},{5,6},{1,0},{1,0}}, {{0,1},{0,1},{2,1},{6,5}}, @@ -550,8 +553,8 @@ void CubicIntersection_IntersectionFinder() { const Cubic& cubic1 = newTestSet[0]; const Cubic& cubic2 = newTestSet[1]; - double t1Seed = 0.599; - double t2Seed = 0.599; + double t1Seed = 0.633; + double t2Seed = 0.633; double t1Step = 0.1; double t2Step = 0.1; _Point t1[3], t2[3]; @@ -624,6 +627,7 @@ void CubicIntersection_IntersectionFinder() { t22 -= t2[1].approximatelyEqual(test) ? -t2Step : t2Step; t2Step /= 2; } +#if ONE_OFF_DEBUG 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(cubic1, t10); @@ -636,6 +640,7 @@ void CubicIntersection_IntersectionFinder() { _Point p22 = xy_at_t(cubic2, 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); +#endif } static void coincidentTest() { @@ -645,6 +650,37 @@ static void coincidentTest() { #endif } +void CubicIntersection_SelfTest() { + const Cubic selfSet[] = { + {{3.34,8.98}, {1.95,10.27}, {3.76,7.65}, {4.96,10.64}}, + {{3.13,2.74}, {1.08,4.62}, {3.71,0.94}, {2.01,3.81}}, + {{6.71,3.14}, {7.99,2.75}, {8.27,1.96}, {6.35,3.57}}, + {{12.81,7.27}, {7.22,6.98}, {12.49,8.97}, {11.42,6.18}}, + }; + size_t selfSetCount = sizeof(selfSet) / sizeof(selfSet[0]); + for (size_t index = 0; index < selfSetCount; ++index) { + const Cubic& cubic = selfSet[index]; + #if ONE_OFF_DEBUG + SkTDArray<Quadratic> quads1; + cubic_to_quadratics(cubic, calcPrecision(cubic), quads1); + for (int index = 0; index < quads1.count(); ++index) { + const Quadratic& q = quads1[index]; + SkDebugf(" {{%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}},\n", q[0].x, q[0].y, + q[1].x, q[1].y, q[2].x, q[2].y); + } + SkDebugf("\n"); + #endif + Intersections i; + int result = intersect(cubic, i); + SkASSERT(result == 1); + SkASSERT(i.used() == 1); + SkASSERT(!approximately_equal(i.fT[0][0], i.fT[1][0])); + _Point pt1 = xy_at_t(cubic, i.fT[0][0]); + _Point pt2 = xy_at_t(cubic, i.fT[1][0]); + SkASSERT(pt1.approximatelyEqual(pt2)); + } +} + void CubicIntersection_Test() { oneOffTests(); coincidentTest(); diff --git a/experimental/Intersection/CubicSubDivide.cpp b/experimental/Intersection/CubicSubDivide.cpp index b7cc127f0a..ee7057bbd8 100644 --- a/experimental/Intersection/CubicSubDivide.cpp +++ b/experimental/Intersection/CubicSubDivide.cpp @@ -83,6 +83,22 @@ void sub_divide(const Cubic& src, double t1, double t2, Cubic& dst) { /* cy = */ dst[2].y = (ny * 2 - my) / 18; } +void sub_divide(const Cubic& src, const _Point& a, const _Point& d, + double t1, double t2, _Point dst[2]) { + double ex = interp_cubic_coords(&src[0].x, (t1 * 2 + t2) / 3); + double ey = interp_cubic_coords(&src[0].y, (t1 * 2 + t2) / 3); + double fx = interp_cubic_coords(&src[0].x, (t1 + t2 * 2) / 3); + double fy = interp_cubic_coords(&src[0].y, (t1 + t2 * 2) / 3); + double mx = ex * 27 - a.x * 8 - d.x; + double my = ey * 27 - a.y * 8 - d.y; + double nx = fx * 27 - a.x - d.x * 8; + double ny = fy * 27 - a.y - d.y * 8; + /* bx = */ dst[0].x = (mx * 2 - nx) / 18; + /* by = */ dst[0].y = (my * 2 - ny) / 18; + /* cx = */ dst[1].x = (nx * 2 - mx) / 18; + /* cy = */ dst[1].y = (ny * 2 - my) / 18; +} + /* classic one t subdivision */ static void interp_cubic_coords(const double* src, double* dst, double t) { diff --git a/experimental/Intersection/CubicUtilities.h b/experimental/Intersection/CubicUtilities.h index abfb4338e0..3f52a94621 100644 --- a/experimental/Intersection/CubicUtilities.h +++ b/experimental/Intersection/CubicUtilities.h @@ -30,6 +30,7 @@ _Point dxdy_at_t(const Cubic& cubic, double t); int find_cubic_inflections(const Cubic& src, double tValues[]); bool rotate(const Cubic& cubic, int zero, int index, Cubic& rotPath); void sub_divide(const Cubic& src, double t1, double t2, Cubic& dst); +void sub_divide(const Cubic& , const _Point& a, const _Point& d, double t1, double t2, _Point [2]); _Point top(const Cubic& , double startT, double endT); void xy_at_t(const Cubic& , double t, double& x, double& y); _Point xy_at_t(const Cubic& , double t); diff --git a/experimental/Intersection/CurveIntersection.h b/experimental/Intersection/CurveIntersection.h index 555d7def36..d01bb7ddb8 100644 --- a/experimental/Intersection/CurveIntersection.h +++ b/experimental/Intersection/CurveIntersection.h @@ -54,7 +54,7 @@ bool intersect(const Cubic& cubic1, const Cubic& cubic2, Intersections& ); bool intersect2(const Cubic& cubic1, const Cubic& cubic2, Intersections& ); // like '2', but iterates on centers instead of possible edges bool intersect3(const Cubic& cubic1, const Cubic& cubic2, Intersections& ); -bool intersect(const Cubic& cubic, Intersections& i); // return true if cubic self-intersects +int intersect(const Cubic& cubic, Intersections& i); // return true if cubic self-intersects int intersect(const Cubic& cubic, const Quadratic& quad, Intersections& ); int intersect(const Cubic& cubic, const _Line& line, Intersections& ); int intersectRay(const Cubic& quad, const _Line& line, Intersections& i); diff --git a/experimental/Intersection/DataTypes.cpp b/experimental/Intersection/DataTypes.cpp index 698f497434..b76731c65d 100644 --- a/experimental/Intersection/DataTypes.cpp +++ b/experimental/Intersection/DataTypes.cpp @@ -83,4 +83,16 @@ void mathematica_ize(char* str, size_t bufferLen) { num = str[idx] >= '0' && str[idx] <= '9'; } } + +bool valid_wind(int wind) { + return wind > SK_MinS32 + 0xFFFF && wind < SK_MaxS32 - 0xFFFF; +} + +void winding_printf(int wind) { + if (wind == SK_MinS32) { + SkDebugf("?"); + } else { + SkDebugf("%d", wind); + } +} #endif diff --git a/experimental/Intersection/DataTypes.h b/experimental/Intersection/DataTypes.h index 8226f09bd2..3009c17ae0 100644 --- a/experimental/Intersection/DataTypes.h +++ b/experimental/Intersection/DataTypes.h @@ -249,6 +249,15 @@ struct _Point { return approximately_equal(x * inv, a.x * inv) && approximately_equal(y * inv, a.y * inv); } + bool approximatelyEqual(const SkPoint& a) const { + double denom = SkTMax(fabs(x), SkTMax(fabs(y), SkTMax(fabs(a.fX), fabs(a.fY)))); + if (denom == 0) { + return true; + } + double inv = 1 / denom; + return approximately_equal(x * inv, a.fX * inv) && approximately_equal(y * inv, a.fY * inv); + } + bool approximatelyEqualHalf(const _Point& a) const { double denom = SkTMax(fabs(x), SkTMax(fabs(y), SkTMax(fabs(a.x), fabs(a.y)))); if (denom == 0) { @@ -372,8 +381,11 @@ struct QuadraticPair { #define sk_double_isnan(a) sk_float_isnan(a) +// FIXME: move these to debugging file #if SK_DEBUG void mathematica_ize(char* str, size_t bufferSize); +bool valid_wind(int winding); +void winding_printf(int winding); #endif #endif // __DataTypes_h__ diff --git a/experimental/Intersection/Intersection_Tests.cpp b/experimental/Intersection/Intersection_Tests.cpp index 2db5d316fb..244f92f187 100644 --- a/experimental/Intersection/Intersection_Tests.cpp +++ b/experimental/Intersection/Intersection_Tests.cpp @@ -14,12 +14,13 @@ void parseSVG(); void Intersection_Tests() { int testsRun = 0; -#if 0 -#endif QuadraticIntersection_IntersectionFinder(); QuadraticIntersection_OneOffTest(); CubicIntersection_IntersectionFinder(); CubicIntersection_NewOneOffTest(); + CubicIntersection_SelfTest(); +#if 0 +#endif SimplifyNew_Test(); CubicsToQuadratics_OneOffTest(); CubicIntersection_OneOffTest(); diff --git a/experimental/Intersection/Intersection_Tests.h b/experimental/Intersection/Intersection_Tests.h index af658d9c45..333f245102 100644 --- a/experimental/Intersection/Intersection_Tests.h +++ b/experimental/Intersection/Intersection_Tests.h @@ -15,6 +15,7 @@ void CubicIntersection_IntersectionFinder(); void CubicIntersection_NewOneOffTest(); void CubicIntersection_OneOffTest(); void CubicIntersection_OneOffTests(); +void CubicIntersection_SelfTest(); void CubicIntersection_Test(); void CubicIntersection_RandTest(); void CubicIntersection_RandTestOld(); diff --git a/experimental/Intersection/QuadraticIntersection_Test.cpp b/experimental/Intersection/QuadraticIntersection_Test.cpp index d2be492742..e9b7d90bcb 100644 --- a/experimental/Intersection/QuadraticIntersection_Test.cpp +++ b/experimental/Intersection/QuadraticIntersection_Test.cpp @@ -54,6 +54,15 @@ static void standardTestCases() { } static const Quadratic testSet[] = { + {{1.80814127,2.41537795}, {2.23475077,2.05922313}, {3.16529668,1.98358763}}, + {{2.16505631,2.55782454}, {2.40541285,2.02193091}, {2.99836023,1.68247638}}, + +{{3, 1.875}, {3.375, 1.54296875}, {3.375, 1.421875}}, +{{3.375, 1.421875}, {3.3749999999999996, 1.3007812499999998}, {3, 2}}, + + {{3.34,8.98}, {2.83363281,9.4265625}, {2.83796875,9.363125}}, + {{2.83796875,9.363125}, {2.84230469,9.2996875}, {3.17875,9.1725}}, + {{2.7279999999999998, 3.024}, {2.5600000000000005, 2.5600000000000005}, {2.1520000000000001, 1.8560000000000001}}, {{0.66666666666666652, 1.1481481481481481}, {1.3333333333333326, 1.3333333333333335}, {2.6666666666666665, 2.1851851851851851}}, @@ -205,7 +214,6 @@ static void oneOffTest1(size_t outer, size_t inner) { void QuadraticIntersection_OneOffTest() { oneOffTest1(0, 1); - oneOffTest1(2, 3); } static void oneOffTests() { @@ -311,10 +319,10 @@ static void intersectionFinder(int test1, int test2) { const Quadratic& quad1 = testSet[test1]; const Quadratic& quad2 = testSet[test2]; - double t1Seed = 0.989; - double t2Seed = 0.800; - double t1Step = 0.01; - double t2Step = 0.01; + double t1Seed = 0.579; + double t2Seed = 0.469; + double t1Step = 0.1; + double t2Step = 0.1; _Point t1[3], t2[3]; bool toggle = true; do { @@ -385,6 +393,7 @@ static void intersectionFinder(int test1, int test2) { t22 -= t2[1].approximatelyEqual(test) ? -t2Step : t2Step; t2Step /= 2; } +#if ONE_OFF_DEBUG 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); @@ -397,9 +406,9 @@ static void intersectionFinder(int test1, int test2) { _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); +#endif } void QuadraticIntersection_IntersectionFinder() { intersectionFinder(0, 1); - intersectionFinder(2, 3); } diff --git a/experimental/Intersection/QuadraticSubDivide.cpp b/experimental/Intersection/QuadraticSubDivide.cpp index a889825a1a..2ced9e325a 100644 --- a/experimental/Intersection/QuadraticSubDivide.cpp +++ b/experimental/Intersection/QuadraticSubDivide.cpp @@ -50,6 +50,15 @@ void sub_divide(const Quadratic& src, double t1, double t2, Quadratic& dst) { /* by = */ dst[1].y = 2*dy - (ay + cy)/2; } +_Point sub_divide(const Quadratic& src, const _Point& a, const _Point& c, double t1, double t2) { + _Point b; + double dx = interp_quad_coords(&src[0].x, (t1 + t2) / 2); + double dy = interp_quad_coords(&src[0].y, (t1 + t2) / 2); + b.x = 2 * dx - (a.x + c.x) / 2; + b.y = 2 * dy - (a.y + c.y) / 2; + return b; +} + /* classic one t subdivision */ static void interp_quad_coords(const double* src, double* dst, double t) { diff --git a/experimental/Intersection/QuadraticUtilities.h b/experimental/Intersection/QuadraticUtilities.h index 74ab80972d..fe6bc68731 100644 --- a/experimental/Intersection/QuadraticUtilities.h +++ b/experimental/Intersection/QuadraticUtilities.h @@ -36,6 +36,7 @@ inline void set_abc(const double* quad, double& a, double& b, double& c) { int quadraticRootsReal(double A, double B, double C, double t[2]); int quadraticRootsValidT(const double A, const double B, const double C, double s[2]); void sub_divide(const Quadratic& src, double t1, double t2, Quadratic& dst); +_Point sub_divide(const Quadratic& src, const _Point& a, const _Point& c, double t1, double t2); void toCubic(const Quadratic& , Cubic& ); _Point top(const Quadratic& , double startT, double endT); void xy_at_t(const Quadratic& , double t, double& x, double& y); diff --git a/experimental/Intersection/QuarticRoot.cpp b/experimental/Intersection/QuarticRoot.cpp index ea786e4407..061098a598 100644 --- a/experimental/Intersection/QuarticRoot.cpp +++ b/experimental/Intersection/QuarticRoot.cpp @@ -45,6 +45,37 @@ int reducedQuarticRoots(const double t4, const double t3, const double t2, const SkDebugf("%s\n", str); #endif #endif +#if 0 && SK_DEBUG + bool t4Or = approximately_zero_when_compared_to(t4, t0) // 0 is one root + || approximately_zero_when_compared_to(t4, t1) + || approximately_zero_when_compared_to(t4, t2); + bool t4And = approximately_zero_when_compared_to(t4, t0) // 0 is one root + && approximately_zero_when_compared_to(t4, t1) + && approximately_zero_when_compared_to(t4, t2); + if (t4Or != t4And) { + SkDebugf("%s t4 or and\n", __FUNCTION__); + } + bool t3Or = approximately_zero_when_compared_to(t3, t0) + || approximately_zero_when_compared_to(t3, t1) + || approximately_zero_when_compared_to(t3, t2); + bool t3And = approximately_zero_when_compared_to(t3, t0) + && approximately_zero_when_compared_to(t3, t1) + && approximately_zero_when_compared_to(t3, t2); + if (t3Or != t3And) { + SkDebugf("%s t3 or and\n", __FUNCTION__); + } + bool t0Or = approximately_zero_when_compared_to(t0, t1) // 0 is one root + && approximately_zero_when_compared_to(t0, t2) + && approximately_zero_when_compared_to(t0, t3) + && approximately_zero_when_compared_to(t0, t4); + bool t0And = approximately_zero_when_compared_to(t0, t1) // 0 is one root + && approximately_zero_when_compared_to(t0, t2) + && approximately_zero_when_compared_to(t0, t3) + && approximately_zero_when_compared_to(t0, t4); + if (t0Or != t0And) { + SkDebugf("%s t0 or and\n", __FUNCTION__); + } +#endif if (approximately_zero_when_compared_to(t4, t0) // 0 is one root && approximately_zero_when_compared_to(t4, t1) && approximately_zero_when_compared_to(t4, t2)) { @@ -57,8 +88,8 @@ int reducedQuarticRoots(const double t4, const double t3, const double t2, const return cubicRootsReal(t3, t2, t1, t0, roots); } } - if (approximately_zero_when_compared_to(t0, t1) // 0 is one root - && approximately_zero_when_compared_to(t0, t2) + if ((approximately_zero_when_compared_to(t0, t1) || approximately_zero(t1))// 0 is one root + // && approximately_zero_when_compared_to(t0, t2) && approximately_zero_when_compared_to(t0, t3) && approximately_zero_when_compared_to(t0, t4)) { int num = cubicRootsReal(t4, t3, t2, t1, roots); diff --git a/experimental/Intersection/ShapeOps.cpp b/experimental/Intersection/ShapeOps.cpp index 57aedd6c96..bc390c72ea 100644 --- a/experimental/Intersection/ShapeOps.cpp +++ b/experimental/Intersection/ShapeOps.cpp @@ -215,6 +215,9 @@ static bool bridgeOp(SkTDArray<Contour*>& contourList, const ShapeOp op, void operate(const SkPath& one, const SkPath& two, ShapeOp op, SkPath& result) { +#if DEBUG_SORT + Op::gDebugSortCount = Op::gDebugSortCountDefault; +#endif result.reset(); result.setFillType(SkPath::kEvenOdd_FillType); // turn path into list of segments @@ -237,6 +240,9 @@ void operate(const SkPath& one, const SkPath& two, ShapeOp op, SkPath& result) { do { Op::Contour** nextPtr = currentPtr; Op::Contour* current = *currentPtr++; + if (current->containsCubics()) { + addSelfIntersectTs(current); + } Op::Contour* next; do { next = *nextPtr++; diff --git a/experimental/Intersection/Simplify.cpp b/experimental/Intersection/Simplify.cpp index 0db33fa77d..dfb36ff791 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 @@ -51,7 +51,7 @@ const bool gRunTestsInOneThread = false; #define DEBUG_MARK_DONE 0 #define DEBUG_PATH_CONSTRUCTION 0 #define DEBUG_SHOW_WINDING 0 -#define DEBUG_SORT 1 +#define DEBUG_SORT 0 #define DEBUG_SWAP_TOP 0 #define DEBUG_UNSORTABLE 0 #define DEBUG_WIND_BUMP 0 @@ -94,6 +94,11 @@ static int gContourID; static int gSegmentID; #endif +#if DEBUG_SORT +static int gDebugSortCountDefault = 3; // SK_MaxS32; +static int gDebugSortCount; +#endif + #if DEBUG_ACTIVE_OP static const char* kShapeOpStr[] = {"diff", "sect", "union", "xor"}; #endif @@ -165,6 +170,11 @@ static int CubicIntersect(const SkPoint a[4], const SkPoint b[4], Intersections& return intersections.fUsed; } +static int CubicIntersect(const SkPoint a[4], Intersections& intersections) { + MAKE_CONST_CUBIC(aCubic, a); + return intersect(aCubic, intersections); +} + static int HLineIntersect(const SkPoint a[2], SkScalar left, SkScalar right, SkScalar y, bool flipped, Intersections& intersections) { MAKE_CONST_LINE(aLine, a); @@ -1039,16 +1049,17 @@ struct Bounds : public SkRect { // return outerWinding * innerWinding > 0 // || ((outerWinding + innerWinding < 0) ^ ((outerWinding - innerWinding) < 0))) static bool useInnerWinding(int outerWinding, int innerWinding) { - // SkASSERT(outerWinding != innerWinding); + SkASSERT(outerWinding != SK_MaxS32); + SkASSERT(innerWinding != SK_MaxS32); int absOut = abs(outerWinding); int absIn = abs(innerWinding); bool result = absOut == absIn ? outerWinding < 0 : absOut < absIn; - if (outerWinding * innerWinding < 0) { #if 0 && DEBUG_WINDING + if (outerWinding * innerWinding < 0) { SkDebugf("%s outer=%d inner=%d result=%s\n", __FUNCTION__, outerWinding, innerWinding, result ? "true" : "false"); -#endif } +#endif return result; } @@ -1553,7 +1564,7 @@ public: ePtr = fPts; } else { // OPTIMIZE? if not active, skip remainder and return xy_at_t(end) - (*SegmentSubDivide[fVerb])(fPts, fTs[start].fT, fTs[end].fT, edge); + subDivide(start, end, edge); ePtr = edge; } if (active) { @@ -1682,9 +1693,19 @@ public: span->fUnsortableEnd = false; int less = -1; while (&span[less + 1] - fTs.begin() > 0 && !span[less].fDone - && !precisely_negative(newT - span[less].fT) - // && approximately_negative(newT - span[less].fT) && xyAtT(&span[less]) == xyAtT(span)) { + double tInterval = newT - span[less].fT; + if (precisely_negative(tInterval)) { + break; + } + if (fVerb == SkPath::kCubic_Verb) { + double tMid = newT - tInterval / 2; + _Point midPt; + CubicXYAtT(fPts, tMid, &midPt); + if (!midPt.approximatelyEqual(xyAtT(span))) { + break; + } + } span[less].fTiny = true; span[less].fDone = true; if (approximately_negative(newT - span[less].fT)) { @@ -1702,9 +1723,19 @@ public: } int more = 1; while (fTs.end() - &span[more - 1] > 1 && !span[more - 1].fDone - && !precisely_negative(span[more].fT - newT) - // && approximately_negative(span[more].fT - newT) && xyAtT(&span[more]) == xyAtT(span)) { + double tEndInterval = span[more].fT - newT; + if (precisely_negative(tEndInterval)) { + break; + } + if (fVerb == SkPath::kCubic_Verb) { + double tMid = newT - tEndInterval / 2; + _Point midEndPt; + CubicXYAtT(fPts, tMid, &midEndPt); + if (!midEndPt.approximatelyEqual(xyAtT(span))) { + break; + } + } span[more - 1].fTiny = true; span[more - 1].fDone = true; if (approximately_negative(span[more].fT - newT)) { @@ -2831,18 +2862,19 @@ public: SkPoint dxyE = leftSegment->dxdy(endIndex); SkPoint dxyS = leftSegment->dxdy(tIndex); double cross = dxyE.cross(dxyS); - bool bumpCheck = bumpsUp && xyE.fY < xyS.fY; + bool bumpCheck = bumpsUp && xyE.fY < xyS.fY && dxyE.fX < 0; #if DEBUG_SWAP_TOP SkDebugf("%s xyE=(%1.9g,%1.9g) xyS=(%1.9g,%1.9g)\n", __FUNCTION__, xyE.fX, xyE.fY, xyS.fX, xyS.fY); - SkDebugf("%s dxyE=(%1.9g,%1.9g) dxyS=(%1.9g,%1.9g) cross=%1.9g bump=%s\n", __FUNCTION__, - dxyE.fX, dxyE.fY, dxyS.fX, dxyS.fY, cross, bumpCheck ? "true" : "false"); - #endif + SkDebugf("%s dxyE=(%1.9g,%1.9g) dxyS=(%1.9g,%1.9g) cross=%1.9g bumpsUp=%s\n", + __FUNCTION__, + dxyE.fX, dxyE.fY, dxyS.fX, dxyS.fY, cross, bumpsUp ? "true" : "false"); if ((cross > 0) ^ bumpCheck) { leftSegment->bumpsUp(tIndex, endIndex); SkDebugf("%s cross bump disagree\n", __FUNCTION__); } - if (bumpCheck) { + #endif + if (cross > 0 || bumpCheck) { #if DEBUG_SWAP_TOP SkDebugf("%s swap\n", __FUNCTION__); #endif @@ -3313,7 +3345,7 @@ the same winding is shared by both. bool bumpsUp(int tStart, int tEnd) const { SkPoint edge[4]; - (*SegmentSubDivide[fVerb])(fPts, fTs[tStart].fT, fTs[tEnd].fT, edge); + subDivide(tStart, tEnd, edge); switch (fVerb) { case SkPath::kLine_Verb: SkASSERT(0); // shouldn't call in for lines @@ -3664,6 +3696,23 @@ the same winding is shared by both. #endif return result; } + + void subDivide(int start, int end, SkPoint edge[4]) const { + edge[0] = fTs[start].fPt; + edge[fVerb] = fTs[end].fPt; + if (fVerb == SkPath::kQuad_Verb || fVerb == SkPath::kCubic_Verb) { + _Point sub[2] = {{ edge[0].fX, edge[0].fY}, {edge[fVerb].fX, edge[fVerb].fY }}; + if (fVerb == SkPath::kQuad_Verb) { + MAKE_CONST_QUAD(aQuad, fPts); + edge[1] = sub_divide(aQuad, sub[0], sub[1], fTs[start].fT, fTs[end].fT).asSkPoint(); + } else { + MAKE_CONST_CUBIC(aCubic, fPts); + sub_divide(aCubic, sub[0], sub[1], fTs[start].fT, fTs[end].fT, sub); + edge[1] = sub[0].asSkPoint(); + edge[2] = sub[1].asSkPoint(); + } + } + } // OPTIMIZATION: mark as debugging only if used solely by tests double t(int tIndex) const { @@ -3841,6 +3890,7 @@ the same winding is shared by both. const SkPoint& xyAtT(const Span* span) const { if (SkScalarIsNaN(span->fPt.fX)) { + SkASSERT(0); // make sure this path is never used if (span->fT == 0) { span->fPt = fPts[0]; } else if (span->fT == 1) { @@ -4119,6 +4169,9 @@ the same winding is shared by both. #if DEBUG_SORT void debugShowSort(const char* fun, const SkTDArray<Angle*>& angles, int first, const int contourWinding, const int oppContourWinding) const { + if (--gDebugSortCount < 0) { + return; + } SkASSERT(angles[first]->segment() == this); SkASSERT(angles.count() > 1); int lastSum = contourWinding; @@ -4127,8 +4180,12 @@ the same winding is shared by both. int windSum = lastSum - spanSign(firstAngle); int oppoSign = oppSign(firstAngle); int oppWindSum = oppLastSum - oppoSign; - SkDebugf("%s %s contourWinding=%d oppContourWinding=%d sign=%d\n", fun, __FUNCTION__, - contourWinding, oppContourWinding, spanSign(angles[first])); + #define WIND_AS_STRING(x) char x##Str[12]; if (!valid_wind(x)) strcpy(x##Str, "?"); \ + else snprintf(x##Str, sizeof(x##Str), "%d", x) + WIND_AS_STRING(contourWinding); + WIND_AS_STRING(oppContourWinding); + SkDebugf("%s %s contourWinding=%s oppContourWinding=%s sign=%d\n", fun, __FUNCTION__, + contourWindingStr, oppContourWindingStr, spanSign(angles[first])); int index = first; bool firstTime = true; do { @@ -4165,13 +4222,7 @@ the same winding is shared by both. start, segment.xAtT(&sSpan), segment.yAtT(&sSpan), end, segment.xAtT(&eSpan), segment.yAtT(&eSpan), angle.sign(), mSpan.fWindValue); - start here; - // create an inline to replace this conditional - if (mSpan.fWindSum == SK_MinS32) { - SkDebugf("?"); - } else { - SkDebugf("%d", mSpan.fWindSum); - } + winding_printf(mSpan.fWindSum); int last, wind; if (opp) { last = oppLastSum; @@ -4180,12 +4231,19 @@ the same winding is shared by both. last = lastSum; wind = windSum; } + bool useInner = valid_wind(last) && valid_wind(wind) && useInnerWinding(last, wind); + WIND_AS_STRING(last); + WIND_AS_STRING(wind); + WIND_AS_STRING(lastSum); + WIND_AS_STRING(oppLastSum); + WIND_AS_STRING(windSum); + WIND_AS_STRING(oppWindSum); + #undef WIND_AS_STRING if (!oppoSign) { - SkDebugf(" %d->%d (max=%d)", last, wind, - useInnerWinding(last, wind) ? wind : last); + SkDebugf(" %s->%s (max=%s)", lastStr, windStr, useInner ? windStr : lastStr); } else { - SkDebugf(" %d->%d (%d->%d)", last, wind, opp ? lastSum : oppLastSum, - opp ? windSum : oppWindSum); + SkDebugf(" %s->%s (%s->%s)", lastStr, windStr, opp ? lastSumStr : oppLastSumStr, + opp ? windSumStr : oppWindSumStr); } SkDebugf(" done=%d tiny=%d opp=%d\n", mSpan.fDone, mSpan.fTiny, opp); #if false && DEBUG_ANGLE @@ -4307,7 +4365,7 @@ public: void addCubic(const SkPoint pts[4]) { fSegments.push_back().addCubic(pts, fOperand, fXor); - fContainsCurves = true; + fContainsCurves = fContainsCubics = true; } int addLine(const SkPoint pts[2]) { @@ -4326,7 +4384,7 @@ public: } int addT(int segIndex, double newT, Contour* other, int otherIndex, const SkPoint& pt) { - containsIntercepts(); + setContainsIntercepts(); return fSegments[segIndex].addT(newT, &other->fSegments[otherIndex], pt); } @@ -4343,9 +4401,9 @@ public: setBounds(); fContainsIntercepts = false; } - - void containsIntercepts() { - fContainsIntercepts = true; + + bool containsCubics() const { + return fContainsCubics; } bool crosses(const Contour* crosser) const { @@ -4405,7 +4463,7 @@ public: void reset() { fSegments.reset(); fBounds.set(SK_ScalarMax, SK_ScalarMax, SK_ScalarMax, SK_ScalarMax); - fContainsCurves = fContainsIntercepts = fDone = false; + fContainsCurves = fContainsCubics = fContainsIntercepts = fDone = false; } void resolveCoincidence(SkTDArray<Contour*>& contourList) { @@ -4591,6 +4649,10 @@ public: return fSegments; } + void setContainsIntercepts() { + fContainsIntercepts = true; + } + void setOperand(bool isOp) { fOperand = isOp; } @@ -4790,7 +4852,8 @@ private: SkTDArray<Coincidence> fCoincidences; SkTDArray<const Contour*> fCrosses; Bounds fBounds; - bool fContainsIntercepts; + bool fContainsIntercepts; // FIXME: is this used by anybody? + bool fContainsCubics; bool fContainsCurves; bool fDone; bool fOperand; // true for the second argument to a binary operator @@ -5135,27 +5198,42 @@ protected: }; #if DEBUG_ADD_INTERSECTING_TS + +#define DEBUG_AS_C_CODE 1 +#if DEBUG_AS_C_CODE +#define CUBIC_DEBUG_STR "{{%1.17g,%1.17g}, {%1.17g,%1.17g}, {%1.17g,%1.17g}, {%1.17g,%1.17g}}" +#define QUAD_DEBUG_STR "{{%1.17g,%1.17g}, {%1.17g,%1.17g}, {%1.17g,%1.17g}}" +#define LINE_DEBUG_STR "{{%1.17g,%1.17g}, {%1.17g,%1.17g}}" +#define PT_DEBUG_STR "{{%1.17g,%1.17g}}" +#else +#define CUBIC_DEBUG_STR "(%1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g)" +#define QUAD_DEBUG_STR "(%1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g)" +#define LINE_DEBUG_STR "(%1.9g,%1.9g %1.9g,%1.9g)" +#define PT_DEBUG_STR "(%1.9g,%1.9g)" +#endif +#define T_DEBUG_STR(t, n) #t "[" #n "]=%1.9g" +#define TX_DEBUG_STR(t) #t "[%d]=%1.9g" +#define CUBIC_DEBUG_DATA(c) c[0].fX, c[0].fY, c[1].fX, c[1].fY, c[2].fX, c[2].fY, c[3].fX, c[3].fY +#define QUAD_DEBUG_DATA(q) q[0].fX, q[0].fY, q[1].fX, q[1].fY, q[2].fX, q[2].fY +#define LINE_DEBUG_DATA(l) l[0].fX, l[0].fY, l[1].fX, l[1].fY +#define PT_DEBUG_DATA(i, n) i.fPt[n].x, i.fPt[n].y + static void debugShowLineIntersection(int pts, const Work& wt, const Work& wn, const Intersections& i) { SkASSERT(i.used() == pts); if (!pts) { - SkDebugf("%s no intersect (%1.9g,%1.9g %1.9g,%1.9g) (%1.9g,%1.9g %1.9g,%1.9g)\n", - __FUNCTION__, wt.pts()[0].fX, wt.pts()[0].fY, - wt.pts()[1].fX, wt.pts()[1].fY, wn.pts()[0].fX, wn.pts()[0].fY, - wn.pts()[1].fX, wn.pts()[1].fY); + SkDebugf("%s no intersect " LINE_DEBUG_STR " " LINE_DEBUG_STR "\n", + __FUNCTION__, LINE_DEBUG_DATA(wt.pts()), LINE_DEBUG_DATA(wn.pts())); return; } - SkDebugf("%s wtTs[0]=%1.9g (%1.9g,%1.9g %1.9g,%1.9g) (%1.9g,%1.9g)", - __FUNCTION__, - i.fT[0][0], wt.pts()[0].fX, wt.pts()[0].fY, - wt.pts()[1].fX, wt.pts()[1].fY, i.fPt[0].x, i.fPt[0].y); + SkDebugf("%s " T_DEBUG_STR(wtTs, 0) " " LINE_DEBUG_STR " " PT_DEBUG_STR, __FUNCTION__, + i.fT[0][0], LINE_DEBUG_DATA(wt.pts()), PT_DEBUG_DATA(i, 0)); if (pts == 2) { - SkDebugf(" wtTs[1]=%1.9g (%1.9g,%1.9g)", i.fT[0][1], i.fPt[1].x, i.fPt[1].y); + SkDebugf(" " T_DEBUG_STR(wtTs, 1) " " PT_DEBUG_STR, i.fT[0][1], PT_DEBUG_DATA(i, 1)); } - SkDebugf(" wnTs[0]=%g (%1.9g,%1.9g %1.9g,%1.9g)", i.fT[1][0], wn.pts()[0].fX, wn.pts()[0].fY, - wn.pts()[1].fX, wn.pts()[1].fY); + SkDebugf(" wnTs[0]=%g " LINE_DEBUG_STR, i.fT[1][0], LINE_DEBUG_DATA(wn.pts())); if (pts == 2) { - SkDebugf(" wnTs[1]=%1.9g", i.fT[1][1]); + SkDebugf(" " T_DEBUG_STR(wnTs, 1), i.fT[1][1]); } SkDebugf("\n"); } @@ -5164,25 +5242,18 @@ static void debugShowQuadLineIntersection(int pts, const Work& wt, const Work& wn, const Intersections& i) { SkASSERT(i.used() == pts); if (!pts) { - SkDebugf("%s no intersect (%1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g)" - " (%1.9g,%1.9g %1.9g,%1.9g)\n", - __FUNCTION__, wt.pts()[0].fX, wt.pts()[0].fY, - wt.pts()[1].fX, wt.pts()[1].fY, wt.pts()[2].fX, wt.pts()[2].fY, - wn.pts()[0].fX, wn.pts()[0].fY, wn.pts()[1].fX, wn.pts()[1].fY); + SkDebugf("%s no intersect " QUAD_DEBUG_STR " " LINE_DEBUG_STR "\n", + __FUNCTION__, QUAD_DEBUG_DATA(wt.pts()), LINE_DEBUG_DATA(wn.pts())); return; } - SkDebugf("%s wtTs[0]=%1.9g (%1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g) (%1.9g,%1.9g)", __FUNCTION__, - i.fT[0][0], wt.pts()[0].fX, wt.pts()[0].fY, - wt.pts()[1].fX, wt.pts()[1].fY, wt.pts()[2].fX, wt.pts()[2].fY, - i.fPt[0].x, i.fPt[0].y); - for (int index = 1; index < pts; ++index) { - SkDebugf(" wtTs[%d]=%1.9g (%1.9g,%1.9g)", index, i.fT[0][index], - i.fPt[index].x, i.fPt[index].y); + SkDebugf("%s " T_DEBUG_STR(wtTs, 0) " " QUAD_DEBUG_STR " " PT_DEBUG_STR, __FUNCTION__, + i.fT[0][0], QUAD_DEBUG_DATA(wt.pts()), PT_DEBUG_DATA(i, 0)); + for (int n = 1; n < pts; ++n) { + SkDebugf(" " TX_DEBUG_STR(wtTs) " " PT_DEBUG_STR, n, i.fT[0][n], PT_DEBUG_DATA(i, n)); } - SkDebugf(" wnTs[0]=%g (%1.9g,%1.9g %1.9g,%1.9g)", i.fT[1][0], wn.pts()[0].fX, wn.pts()[0].fY, - wn.pts()[1].fX, wn.pts()[1].fY); - for (int index = 1; index < pts; ++index) { - SkDebugf(" wnTs[%d]=%1.9g", index, i.fT[1][index]); + SkDebugf(" wnTs[0]=%g " LINE_DEBUG_STR, i.fT[1][0], LINE_DEBUG_DATA(wn.pts())); + for (int n = 1; n < pts; ++n) { + SkDebugf(" " TX_DEBUG_STR(wnTs), n, i.fT[1][n]); } SkDebugf("\n"); } @@ -5191,27 +5262,18 @@ static void debugShowQuadIntersection(int pts, const Work& wt, const Work& wn, const Intersections& i) { SkASSERT(i.used() == pts); if (!pts) { - SkDebugf("%s no intersect (%1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g)" - " (%1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g)\n", - __FUNCTION__, wt.pts()[0].fX, wt.pts()[0].fY, - wt.pts()[1].fX, wt.pts()[1].fY, wt.pts()[2].fX, wt.pts()[2].fY, - wn.pts()[0].fX, wn.pts()[0].fY, wn.pts()[1].fX, wn.pts()[1].fY, - wn.pts()[2].fX, wn.pts()[2].fY ); + SkDebugf("%s no intersect " QUAD_DEBUG_STR " " QUAD_DEBUG_STR "\n", + __FUNCTION__, QUAD_DEBUG_DATA(wt.pts()), QUAD_DEBUG_DATA(wn.pts())); return; } - SkDebugf("%s wtTs[0]=%1.9g (%1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g) (%1.9g,%1.9g)", __FUNCTION__, - i.fT[0][0], wt.pts()[0].fX, wt.pts()[0].fY, - wt.pts()[1].fX, wt.pts()[1].fY, wt.pts()[2].fX, wt.pts()[2].fY, - i.fPt[0].x, i.fPt[0].y); - for (int index = 1; index < pts; ++index) { - SkDebugf(" wtTs[%d]=%1.9g (%1.9g,%1.9g)", index, i.fT[0][index], i.fPt[index].x, - i.fPt[index].y); + SkDebugf("%s " T_DEBUG_STR(wtTs, 0) " " QUAD_DEBUG_STR " " PT_DEBUG_STR, __FUNCTION__, + i.fT[0][0], QUAD_DEBUG_DATA(wt.pts()), PT_DEBUG_DATA(i, 0)); + for (int n = 1; n < pts; ++n) { + SkDebugf(" " TX_DEBUG_STR(wtTs) " " PT_DEBUG_STR, n, i.fT[0][n], PT_DEBUG_DATA(i, n)); } - SkDebugf(" wnTs[0]=%g (%1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g)", - i.fT[1][0], wn.pts()[0].fX, wn.pts()[0].fY, - wn.pts()[1].fX, wn.pts()[1].fY, wn.pts()[2].fX, wn.pts()[2].fY); - for (int index = 1; index < pts; ++index) { - SkDebugf(" wnTs[%d]=%1.9g", index, i.fT[1][index]); + SkDebugf(" wnTs[0]=%g " QUAD_DEBUG_STR, i.fT[1][0], QUAD_DEBUG_DATA(wn.pts())); + for (int n = 1; n < pts; ++n) { + SkDebugf(" " TX_DEBUG_STR(wnTs), n, i.fT[1][n]); } SkDebugf("\n"); } @@ -5220,92 +5282,85 @@ static void debugShowCubicLineIntersection(int pts, const Work& wt, const Work& wn, const Intersections& i) { SkASSERT(i.used() == pts); if (!pts) { - SkDebugf("%s no intersect (%1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g)" - " (%1.9g,%1.9g %1.9g,%1.9g)\n", - __FUNCTION__, wt.pts()[0].fX, wt.pts()[0].fY, wt.pts()[1].fX, wt.pts()[1].fY, - wt.pts()[2].fX, wt.pts()[2].fY, wt.pts()[3].fX, wt.pts()[3].fY, - wn.pts()[0].fX, wn.pts()[0].fY, wn.pts()[1].fX, wn.pts()[1].fY); + SkDebugf("%s no intersect " CUBIC_DEBUG_STR " " LINE_DEBUG_STR "\n", + __FUNCTION__, CUBIC_DEBUG_DATA(wt.pts()), LINE_DEBUG_DATA(wn.pts())); return; } - SkDebugf("%s wtTs[0]=%1.9g (%1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g) (%1.9g,%1.9g)", - __FUNCTION__, - i.fT[0][0], wt.pts()[0].fX, wt.pts()[0].fY, wt.pts()[1].fX, wt.pts()[1].fY, - wt.pts()[2].fX, wt.pts()[2].fY, wt.pts()[3].fX, wt.pts()[3].fY, - i.fPt[0].x, i.fPt[0].y); - for (int index = 1; index < pts; ++index) { - SkDebugf(" wtTs[%d]=%1.9g (%1.9g,%1.9g)", index, i.fT[0][index], i.fPt[index].x, - i.fPt[index].y); + SkDebugf("%s " T_DEBUG_STR(wtTs, 0) " " CUBIC_DEBUG_STR " " PT_DEBUG_STR, __FUNCTION__, + i.fT[0][0], CUBIC_DEBUG_DATA(wt.pts()), PT_DEBUG_DATA(i, 0)); + for (int n = 1; n < pts; ++n) { + SkDebugf(" " TX_DEBUG_STR(wtTs) " " PT_DEBUG_STR, n, i.fT[0][n], PT_DEBUG_DATA(i, n)); } - SkDebugf(" wnTs[0]=%g (%1.9g,%1.9g %1.9g,%1.9g)", - i.fT[1][0], wn.pts()[0].fX, wn.pts()[0].fY, wn.pts()[1].fX, wn.pts()[1].fY); - for (int index = 1; index < pts; ++index) { - SkDebugf(" wnTs[%d]=%1.9g", index, i.fT[1][index]); + SkDebugf(" wnTs[0]=%g " LINE_DEBUG_STR, i.fT[1][0], LINE_DEBUG_DATA(wn.pts())); + for (int n = 1; n < pts; ++n) { + SkDebugf(" " TX_DEBUG_STR(wnTs), n, i.fT[1][n]); } SkDebugf("\n"); } -// FIXME: show more than two intersection points static void debugShowCubicQuadIntersection(int pts, const Work& wt, const Work& wn, const Intersections& i) { SkASSERT(i.used() == pts); if (!pts) { - SkDebugf("%s no intersect (%1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g)" - " (%1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g)\n", - __FUNCTION__, wt.pts()[0].fX, wt.pts()[0].fY, wt.pts()[1].fX, wt.pts()[1].fY, - wt.pts()[2].fX, wt.pts()[2].fY, wt.pts()[3].fX, wt.pts()[3].fY, - wn.pts()[0].fX, wn.pts()[0].fY, wn.pts()[1].fX, wn.pts()[1].fY, - wn.pts()[2].fX, wn.pts()[2].fY ); + SkDebugf("%s no intersect " CUBIC_DEBUG_STR " " QUAD_DEBUG_STR "\n", + __FUNCTION__, CUBIC_DEBUG_DATA(wt.pts()), QUAD_DEBUG_DATA(wn.pts())); return; } - SkDebugf("%s wtTs[0]=%1.9g (%1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g) (%1.9g,%1.9g)", - __FUNCTION__, - i.fT[0][0], wt.pts()[0].fX, wt.pts()[0].fY, wt.pts()[1].fX, wt.pts()[1].fY, - wt.pts()[2].fX, wt.pts()[2].fY, wt.pts()[3].fX, wt.pts()[3].fY, - i.fPt[0].x, i.fPt[0].y); - for (int index = 1; index < pts; ++index) { - SkDebugf(" wtTs[%d]=%1.9g (%1.9g,%1.9g)", index, i.fT[0][index], i.fPt[index].x, - i.fPt[index].y); - } - SkDebugf(" wnTs[0]=%g (%1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g)", - i.fT[1][0], wn.pts()[0].fX, wn.pts()[0].fY, wn.pts()[1].fX, wn.pts()[1].fY, - wn.pts()[2].fX, wn.pts()[2].fY); - for (int index = 1; index < pts; ++index) { - SkDebugf(" wnTs[%d]=%1.9g", index, i.fT[1][index]); + SkDebugf("%s " T_DEBUG_STR(wtTs, 0) " " CUBIC_DEBUG_STR " " PT_DEBUG_STR, __FUNCTION__, + i.fT[0][0], CUBIC_DEBUG_DATA(wt.pts()), PT_DEBUG_DATA(i, 0)); + for (int n = 1; n < pts; ++n) { + SkDebugf(" " TX_DEBUG_STR(wtTs) " " PT_DEBUG_STR, n, i.fT[0][n], PT_DEBUG_DATA(i, n)); + } + SkDebugf(" wnTs[0]=%g " QUAD_DEBUG_STR, i.fT[1][0], QUAD_DEBUG_DATA(wn.pts())); + for (int n = 1; n < pts; ++n) { + SkDebugf(" " TX_DEBUG_STR(wnTs), n, i.fT[1][n]); } SkDebugf("\n"); } -// FIXME: show more than two intersection points static void debugShowCubicIntersection(int pts, const Work& wt, const Work& wn, const Intersections& i) { SkASSERT(i.used() == pts); if (!pts) { - SkDebugf("%s no intersect (%1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g)" - " (%1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g)\n", - __FUNCTION__, wt.pts()[0].fX, wt.pts()[0].fY, wt.pts()[1].fX, wt.pts()[1].fY, - wt.pts()[2].fX, wt.pts()[2].fY, wt.pts()[3].fX, wt.pts()[3].fY, - wn.pts()[0].fX, wn.pts()[0].fY, wn.pts()[1].fX, wn.pts()[1].fY, - wn.pts()[2].fX, wn.pts()[2].fY, wn.pts()[3].fX, wn.pts()[3].fY ); + SkDebugf("%s no intersect " CUBIC_DEBUG_STR " " CUBIC_DEBUG_STR "\n", + __FUNCTION__, CUBIC_DEBUG_DATA(wt.pts()), CUBIC_DEBUG_DATA(wn.pts())); return; } - SkDebugf("%s wtTs[0]=%1.9g (%1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g) (%1.9g,%1.9g)", - __FUNCTION__, - i.fT[0][0], wt.pts()[0].fX, wt.pts()[0].fY, wt.pts()[1].fX, wt.pts()[1].fY, - wt.pts()[2].fX, wt.pts()[2].fY, wt.pts()[3].fX, wt.pts()[3].fY, - i.fPt[0].x, i.fPt[0].y); - for (int index = 1; index < pts; ++index) { - SkDebugf(" wtTs[%d]=%1.9g (%1.9g,%1.9g)", index, i.fT[0][index], i.fPt[index].x, - i.fPt[index].y); - } - SkDebugf(" wnTs[0]=%g (%1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g)", - i.fT[1][0], wn.pts()[0].fX, wn.pts()[0].fY, wn.pts()[1].fX, wn.pts()[1].fY, - wn.pts()[2].fX, wn.pts()[2].fY, wn.pts()[3].fX, wn.pts()[3].fY); - for (int index = 1; index < pts; ++index) { - SkDebugf(" wnTs[%d]=%1.9g", index, i.fT[0][index]); + SkDebugf("%s " T_DEBUG_STR(wtTs, 0) " " CUBIC_DEBUG_STR " " PT_DEBUG_STR, __FUNCTION__, + i.fT[0][0], CUBIC_DEBUG_DATA(wt.pts()), PT_DEBUG_DATA(i, 0)); + for (int n = 1; n < pts; ++n) { + SkDebugf(" " TX_DEBUG_STR(wtTs) " " PT_DEBUG_STR, n, i.fT[0][n], PT_DEBUG_DATA(i, n)); + } + SkDebugf(" wnTs[0]=%g " CUBIC_DEBUG_STR, i.fT[1][0], CUBIC_DEBUG_DATA(wn.pts())); + for (int n = 1; n < pts; ++n) { + SkDebugf(" " TX_DEBUG_STR(wnTs), n, i.fT[1][n]); + } + SkDebugf("\n"); +} + +static void debugShowCubicIntersection(int pts, const Work& wt, const Intersections& i) { + SkASSERT(i.used() == pts); + if (!pts) { + SkDebugf("%s no self intersect " CUBIC_DEBUG_STR "\n", __FUNCTION__, + CUBIC_DEBUG_DATA(wt.pts())); + return; } + SkDebugf("%s " T_DEBUG_STR(wtTs, 0) " " CUBIC_DEBUG_STR " " PT_DEBUG_STR, __FUNCTION__, + i.fT[0][0], CUBIC_DEBUG_DATA(wt.pts()), PT_DEBUG_DATA(i, 0)); + SkDebugf(" " T_DEBUG_STR(wtTs, 1), i.fT[1][0]); SkDebugf("\n"); } +#undef CUBIC_DEBUG_STR +#undef QUAD_DEBUG_STR +#undef LINE_DEBUG_STR +#undef PT_DEBUG_STR +#undef T_DEBUG_STR +#undef CUBIC_DEBUG_DATA +#undef QUAD_DEBUG_DATA +#undef LINE_DEBUG_DATA +#undef PT_DEBUG_DATA + #else static void debugShowLineIntersection(int , const Work& , const Work& , const Intersections& ) { } @@ -5326,6 +5381,9 @@ static void debugShowCubicQuadIntersection(int , const Work& , const Work& , static void debugShowCubicIntersection(int , const Work& , const Work& , const Intersections& ) { } + +static void debugShowCubicIntersection(int , const Work& , const Intersections& ) { +} #endif static bool addIntersectTs(Contour* test, Contour* next) { @@ -5565,6 +5623,30 @@ static bool addIntersectTs(Contour* test, Contour* next) { return true; } +static void addSelfIntersectTs(Contour* test) { + Work wt; + wt.init(test); + do { + if (wt.segmentType() != Work::kCubic_Segment) { + continue; + } + Intersections ts; + int pts = CubicIntersect(wt.pts(), ts); + debugShowCubicIntersection(pts, wt, ts); + if (!pts) { + continue; + } + SkASSERT(pts == 1); + SkASSERT(ts.fT[0][0] >= 0 && ts.fT[0][0] <= 1); + SkASSERT(ts.fT[1][0] >= 0 && ts.fT[1][0] <= 1); + SkPoint point = ts.fPt[0].asSkPoint(); + int testTAt = wt.addT(ts.fT[0][0], wt, point); + int nextTAt = wt.addT(ts.fT[1][0], wt, point); + wt.addOtherT(testTAt, ts.fT[1][0], nextTAt); + wt.addOtherT(nextTAt, ts.fT[0][0], testTAt); + } while (wt.advance()); +} + // resolve any coincident pairs found while intersecting, and // see if coincidence is formed by clipping non-concident segments static void coincidenceCheck(SkTDArray<Contour*>& contourList, int total) { @@ -6324,6 +6406,9 @@ static void assemble(const PathWrapper& path, PathWrapper& simple) { } void simplifyx(const SkPath& path, SkPath& result) { +#if DEBUG_SORT + gDebugSortCount = gDebugSortCountDefault; +#endif // returns 1 for evenodd, -1 for winding, regardless of inverse-ness result.reset(); result.setFillType(SkPath::kEvenOdd_FillType); @@ -6331,7 +6416,6 @@ void simplifyx(const SkPath& path, SkPath& result) { // turn path into list of segments SkTArray<Contour> contours; - // FIXME: add self-intersecting cubics' T values to segment EdgeBuilder builder(path, contours); builder.finish(); SkTDArray<Contour*> contourList; @@ -6345,6 +6429,9 @@ void simplifyx(const SkPath& path, SkPath& result) { do { Contour** nextPtr = currentPtr; Contour* current = *currentPtr++; + if (current->containsCubics()) { + addSelfIntersectTs(current); + } Contour* next; do { next = *nextPtr++; diff --git a/experimental/Intersection/SimplifyNew_Test.cpp b/experimental/Intersection/SimplifyNew_Test.cpp index 39cf5a8dac..0d49bb91a5 100644 --- a/experimental/Intersection/SimplifyNew_Test.cpp +++ b/experimental/Intersection/SimplifyNew_Test.cpp @@ -3897,12 +3897,278 @@ static void cubicOp24d() { testShapeOp(path, pathB, kDifference_Op); } -static void (*firstTest)() = 0; +static void testIntersect1() { + SkPath one, two; + one.addRect(0, 0, 6, 6, SkPath::kCW_Direction); + two.addRect(3, 3, 9, 9, SkPath::kCW_Direction); + testShapeOp(one, two, kIntersect_Op); +} + +static void testUnion1() { + SkPath one, two; + one.addRect(0, 0, 6, 6, SkPath::kCW_Direction); + two.addRect(3, 3, 9, 9, SkPath::kCW_Direction); + testShapeOp(one, two, kUnion_Op); +} + +static void testDiff1() { + SkPath one, two; + one.addRect(0, 0, 6, 6, SkPath::kCW_Direction); + two.addRect(3, 3, 9, 9, SkPath::kCW_Direction); + testShapeOp(one, two, kDifference_Op); +} + +static void testXor1() { + SkPath one, two; + one.addRect(0, 0, 6, 6, SkPath::kCW_Direction); + two.addRect(3, 3, 9, 9, SkPath::kCW_Direction); + testShapeOp(one, two, kXor_Op); +} + +static void testIntersect2() { + SkPath one, two; + one.addRect(0, 0, 6, 6, SkPath::kCW_Direction); + two.addRect(0, 3, 9, 9, SkPath::kCW_Direction); + testShapeOp(one, two, kIntersect_Op); +} + +static void testUnion2() { + SkPath one, two; + one.addRect(0, 0, 6, 6, SkPath::kCW_Direction); + two.addRect(0, 3, 9, 9, SkPath::kCW_Direction); + testShapeOp(one, two, kUnion_Op); +} + +static void testDiff2() { + SkPath one, two; + one.addRect(0, 0, 6, 6, SkPath::kCW_Direction); + two.addRect(0, 3, 9, 9, SkPath::kCW_Direction); + testShapeOp(one, two, kDifference_Op); +} + +static void testXor2() { + SkPath one, two; + one.addRect(0, 0, 6, 6, SkPath::kCW_Direction); + two.addRect(0, 3, 9, 9, SkPath::kCW_Direction); + testShapeOp(one, two, kXor_Op); +} + +static void testOp1d() { + SkPath path, pathB; + path.setFillType(SkPath::kWinding_FillType); + path.addRect(0, 0, 1, 1, SkPath::kCW_Direction); + path.addRect(0, 0, 2, 2, SkPath::kCW_Direction); + pathB.setFillType(SkPath::kWinding_FillType); + pathB.addRect(0, 0, 1, 1, SkPath::kCW_Direction); + pathB.addRect(0, 0, 1, 1, SkPath::kCW_Direction); + testShapeOp(path, pathB, kDifference_Op); +} + +static void testOp2d() { + SkPath path, pathB; + path.setFillType(SkPath::kWinding_FillType); + path.addRect(0, 0, 1, 1, SkPath::kCW_Direction); + path.addRect(0, 0, 2, 2, SkPath::kCW_Direction); + pathB.setFillType(SkPath::kEvenOdd_FillType); + pathB.addRect(0, 0, 1, 1, SkPath::kCW_Direction); + pathB.addRect(0, 0, 1, 1, SkPath::kCW_Direction); + testShapeOp(path, pathB, kDifference_Op); +} + +static void testOp3d() { + SkPath path, pathB; + path.setFillType(SkPath::kWinding_FillType); + path.addRect(0, 0, 1, 1, SkPath::kCW_Direction); + path.addRect(1, 1, 2, 2, SkPath::kCW_Direction); + pathB.setFillType(SkPath::kWinding_FillType); + pathB.addRect(0, 0, 1, 1, SkPath::kCW_Direction); + pathB.addRect(0, 0, 1, 1, SkPath::kCW_Direction); + testShapeOp(path, pathB, kDifference_Op); +} + +static void testOp1u() { + SkPath path, pathB; + path.setFillType(SkPath::kWinding_FillType); + path.addRect(0, 0, 1, 1, SkPath::kCW_Direction); + path.addRect(0, 0, 3, 3, SkPath::kCW_Direction); + pathB.setFillType(SkPath::kWinding_FillType); + pathB.addRect(0, 0, 1, 1, SkPath::kCW_Direction); + pathB.addRect(0, 0, 1, 1, SkPath::kCW_Direction); + testShapeOp(path, pathB, kUnion_Op); +} + +static void testOp4d() { + SkPath path, pathB; + path.setFillType(SkPath::kWinding_FillType); + path.addRect(0, 0, 1, 1, SkPath::kCW_Direction); + path.addRect(2, 2, 4, 4, SkPath::kCW_Direction); + pathB.setFillType(SkPath::kWinding_FillType); + pathB.addRect(0, 0, 1, 1, SkPath::kCW_Direction); + pathB.addRect(0, 0, 1, 1, SkPath::kCW_Direction); + testShapeOp(path, pathB, kDifference_Op); +} + +static void testOp5d() { + SkPath path, pathB; + path.setFillType(SkPath::kEvenOdd_FillType); + path.addRect(0, 0, 2, 2, SkPath::kCW_Direction); + path.addRect(0, 0, 3, 3, SkPath::kCW_Direction); + pathB.setFillType(SkPath::kEvenOdd_FillType); + pathB.addRect(0, 0, 1, 1, SkPath::kCW_Direction); + pathB.addRect(0, 0, 1, 1, SkPath::kCW_Direction); + testShapeOp(path, pathB, kDifference_Op); +} + +static void testOp6d() { + SkPath path, pathB; + path.setFillType(SkPath::kEvenOdd_FillType); + path.addRect(0, 0, 1, 1, SkPath::kCW_Direction); + path.addRect(0, 0, 3, 3, SkPath::kCW_Direction); + pathB.setFillType(SkPath::kWinding_FillType); + pathB.addRect(0, 0, 1, 1, SkPath::kCW_Direction); + pathB.addRect(0, 0, 1, 1, SkPath::kCW_Direction); + testShapeOp(path, pathB, kDifference_Op); +} + +static void testOp7d() { + SkPath path, pathB; + path.setFillType(SkPath::kEvenOdd_FillType); + path.addRect(0, 0, 2, 2, SkPath::kCW_Direction); + path.addRect(0, 0, 1, 1, SkPath::kCW_Direction); + pathB.setFillType(SkPath::kEvenOdd_FillType); + pathB.addRect(0, 0, 1, 1, SkPath::kCW_Direction); + pathB.addRect(0, 0, 1, 1, SkPath::kCW_Direction); + testShapeOp(path, pathB, kDifference_Op); +} + +static void testOp2u() { + SkPath path, pathB; + path.setFillType(SkPath::kEvenOdd_FillType); + path.addRect(0, 0, 2, 2, SkPath::kCW_Direction); + path.addRect(0, 0, 2, 2, SkPath::kCW_Direction); + pathB.setFillType(SkPath::kWinding_FillType); + pathB.addRect(0, 0, 3, 3, SkPath::kCW_Direction); + pathB.addRect(1, 1, 2, 2, SkPath::kCW_Direction); + testShapeOp(path, pathB, kUnion_Op); +} + +static void testOp8d() { + SkPath path, pathB; + path.addRect(0, 0, 640, 480); + pathB.moveTo(577330, 1971.72f); + pathB.cubicTo(10.7082f, -116.596f, 262.057f, 45.6468f, 294.694f, 1.96237f); + pathB.close(); + testShapeOp(path, pathB, kDifference_Op); +} +static void cubicOp25i() { + SkPath path, pathB; + path.setFillType(SkPath::kWinding_FillType); + path.moveTo(0,1); + path.cubicTo(2,4, 5,0, 3,2); + path.close(); + pathB.setFillType(SkPath::kWinding_FillType); + pathB.moveTo(0,5); + pathB.cubicTo(2,3, 1,0, 4,2); + pathB.close(); + testShapeOp(path, pathB, kIntersect_Op); +} + +static void cubicOp26d() { + SkPath path, pathB; + path.setFillType(SkPath::kWinding_FillType); + path.moveTo(0,1); + path.cubicTo(3,4, 4,0, 3,2); + path.close(); + pathB.setFillType(SkPath::kWinding_FillType); + pathB.moveTo(0,4); + pathB.cubicTo(2,3, 1,0, 4,3); + pathB.close(); + testShapeOp(path, pathB, kDifference_Op); +} + +static void cubicOp27d() { + SkPath path, pathB; + path.setFillType(SkPath::kWinding_FillType); + path.moveTo(0,1); + path.cubicTo(3,6, 1,0, 5,2); + path.close(); + pathB.setFillType(SkPath::kWinding_FillType); + pathB.moveTo(0,1); + pathB.cubicTo(2,5, 1,0, 6,3); + pathB.close(); + testShapeOp(path, pathB, kDifference_Op); +} + +static void cubicOp28u() { + SkPath path, pathB; + path.setFillType(SkPath::kWinding_FillType); + path.moveTo(0,1); + path.cubicTo(1,4, 6,0, 3,2); + path.close(); + pathB.setFillType(SkPath::kWinding_FillType); + pathB.moveTo(0,6); + pathB.cubicTo(2,3, 1,0, 4,1); + pathB.close(); + testShapeOp(path, pathB, kUnion_Op); +} + +static void cubicOp29d() { + SkPath path, pathB; + path.setFillType(SkPath::kWinding_FillType); + path.moveTo(0,1); + path.cubicTo(2,5, 6,0, 4,2); + path.close(); + pathB.setFillType(SkPath::kWinding_FillType); + pathB.moveTo(0,6); + pathB.cubicTo(2,4, 1,0, 5,2); + pathB.close(); + testShapeOp(path, pathB, kDifference_Op); +} + +static void cubicOp30d() { + SkPath path, pathB; + path.setFillType(SkPath::kWinding_FillType); + path.moveTo(0,1); + path.cubicTo(2,5, 6,0, 5,3); + path.close(); + pathB.setFillType(SkPath::kWinding_FillType); + pathB.moveTo(0,6); + pathB.cubicTo(3,5, 1,0, 5,2); + pathB.close(); + testShapeOp(path, pathB, kDifference_Op); +} + +static void (*firstTest)() = cubicOp30d; static struct { void (*fun)(); const char* str; } tests[] = { + TEST(cubicOp30d), + TEST(cubicOp29d), + TEST(cubicOp28u), + TEST(cubicOp27d), + TEST(cubicOp26d), + TEST(cubicOp25i), + TEST(testOp8d), + TEST(testDiff1), + TEST(testIntersect1), + TEST(testUnion1), + TEST(testXor1), + TEST(testDiff2), + TEST(testIntersect2), + TEST(testUnion2), + TEST(testXor2), + TEST(testOp1d), + TEST(testOp2d), + TEST(testOp3d), + TEST(testOp1u), + TEST(testOp4d), + TEST(testOp5d), + TEST(testOp6d), + TEST(testOp7d), + TEST(testOp2u), + TEST(cubicOp24d), TEST(cubicOp23d), TEST(cubicOp22d), @@ -4260,200 +4526,31 @@ static struct { static const size_t testCount = sizeof(tests) / sizeof(tests[0]); -static void testIntersect1() { - SkPath one, two; - one.addRect(0, 0, 6, 6, SkPath::kCW_Direction); - two.addRect(3, 3, 9, 9, SkPath::kCW_Direction); - testShapeOp(one, two, kIntersect_Op); -} - -static void testUnion1() { - SkPath one, two; - one.addRect(0, 0, 6, 6, SkPath::kCW_Direction); - two.addRect(3, 3, 9, 9, SkPath::kCW_Direction); - testShapeOp(one, two, kUnion_Op); -} - -static void testDiff1() { - SkPath one, two; - one.addRect(0, 0, 6, 6, SkPath::kCW_Direction); - two.addRect(3, 3, 9, 9, SkPath::kCW_Direction); - testShapeOp(one, two, kDifference_Op); -} - -static void testXor1() { - SkPath one, two; - one.addRect(0, 0, 6, 6, SkPath::kCW_Direction); - two.addRect(3, 3, 9, 9, SkPath::kCW_Direction); - testShapeOp(one, two, kXor_Op); -} - -static void testIntersect2() { - SkPath one, two; - one.addRect(0, 0, 6, 6, SkPath::kCW_Direction); - two.addRect(0, 3, 9, 9, SkPath::kCW_Direction); - testShapeOp(one, two, kIntersect_Op); -} - -static void testUnion2() { - SkPath one, two; - one.addRect(0, 0, 6, 6, SkPath::kCW_Direction); - two.addRect(0, 3, 9, 9, SkPath::kCW_Direction); - testShapeOp(one, two, kUnion_Op); -} - -static void testDiff2() { - SkPath one, two; - one.addRect(0, 0, 6, 6, SkPath::kCW_Direction); - two.addRect(0, 3, 9, 9, SkPath::kCW_Direction); - testShapeOp(one, two, kDifference_Op); -} - -static void testXor2() { - SkPath one, two; - one.addRect(0, 0, 6, 6, SkPath::kCW_Direction); - two.addRect(0, 3, 9, 9, SkPath::kCW_Direction); - testShapeOp(one, two, kXor_Op); -} - -static void testOp1d() { - SkPath path, pathB; - path.setFillType(SkPath::kWinding_FillType); - path.addRect(0, 0, 1, 1, SkPath::kCW_Direction); - path.addRect(0, 0, 2, 2, SkPath::kCW_Direction); - pathB.setFillType(SkPath::kWinding_FillType); - pathB.addRect(0, 0, 1, 1, SkPath::kCW_Direction); - pathB.addRect(0, 0, 1, 1, SkPath::kCW_Direction); - testShapeOp(path, pathB, kDifference_Op); -} - -static void testOp2d() { - SkPath path, pathB; - path.setFillType(SkPath::kWinding_FillType); - path.addRect(0, 0, 1, 1, SkPath::kCW_Direction); - path.addRect(0, 0, 2, 2, SkPath::kCW_Direction); - pathB.setFillType(SkPath::kEvenOdd_FillType); - pathB.addRect(0, 0, 1, 1, SkPath::kCW_Direction); - pathB.addRect(0, 0, 1, 1, SkPath::kCW_Direction); - testShapeOp(path, pathB, kDifference_Op); -} - -static void testOp3d() { - SkPath path, pathB; - path.setFillType(SkPath::kWinding_FillType); - path.addRect(0, 0, 1, 1, SkPath::kCW_Direction); - path.addRect(1, 1, 2, 2, SkPath::kCW_Direction); - pathB.setFillType(SkPath::kWinding_FillType); - pathB.addRect(0, 0, 1, 1, SkPath::kCW_Direction); - pathB.addRect(0, 0, 1, 1, SkPath::kCW_Direction); - testShapeOp(path, pathB, kDifference_Op); -} - -static void testOp1u() { - SkPath path, pathB; - path.setFillType(SkPath::kWinding_FillType); - path.addRect(0, 0, 1, 1, SkPath::kCW_Direction); - path.addRect(0, 0, 3, 3, SkPath::kCW_Direction); - pathB.setFillType(SkPath::kWinding_FillType); - pathB.addRect(0, 0, 1, 1, SkPath::kCW_Direction); - pathB.addRect(0, 0, 1, 1, SkPath::kCW_Direction); - testShapeOp(path, pathB, kUnion_Op); -} - -static void testOp4d() { - SkPath path, pathB; - path.setFillType(SkPath::kWinding_FillType); - path.addRect(0, 0, 1, 1, SkPath::kCW_Direction); - path.addRect(2, 2, 4, 4, SkPath::kCW_Direction); - pathB.setFillType(SkPath::kWinding_FillType); - pathB.addRect(0, 0, 1, 1, SkPath::kCW_Direction); - pathB.addRect(0, 0, 1, 1, SkPath::kCW_Direction); - testShapeOp(path, pathB, kDifference_Op); -} - -static void testOp5d() { - SkPath path, pathB; - path.setFillType(SkPath::kEvenOdd_FillType); - path.addRect(0, 0, 2, 2, SkPath::kCW_Direction); - path.addRect(0, 0, 3, 3, SkPath::kCW_Direction); - pathB.setFillType(SkPath::kEvenOdd_FillType); - pathB.addRect(0, 0, 1, 1, SkPath::kCW_Direction); - pathB.addRect(0, 0, 1, 1, SkPath::kCW_Direction); - testShapeOp(path, pathB, kDifference_Op); -} - -static void testOp6d() { - SkPath path, pathB; - path.setFillType(SkPath::kEvenOdd_FillType); - path.addRect(0, 0, 1, 1, SkPath::kCW_Direction); - path.addRect(0, 0, 3, 3, SkPath::kCW_Direction); - pathB.setFillType(SkPath::kWinding_FillType); - pathB.addRect(0, 0, 1, 1, SkPath::kCW_Direction); - pathB.addRect(0, 0, 1, 1, SkPath::kCW_Direction); - testShapeOp(path, pathB, kDifference_Op); -} - -static void testOp7d() { - SkPath path, pathB; - path.setFillType(SkPath::kEvenOdd_FillType); - path.addRect(0, 0, 2, 2, SkPath::kCW_Direction); - path.addRect(0, 0, 1, 1, SkPath::kCW_Direction); - pathB.setFillType(SkPath::kEvenOdd_FillType); - pathB.addRect(0, 0, 1, 1, SkPath::kCW_Direction); - pathB.addRect(0, 0, 1, 1, SkPath::kCW_Direction); - testShapeOp(path, pathB, kDifference_Op); -} - -static void testOp2u() { - SkPath path, pathB; - path.setFillType(SkPath::kEvenOdd_FillType); - path.addRect(0, 0, 2, 2, SkPath::kCW_Direction); - path.addRect(0, 0, 2, 2, SkPath::kCW_Direction); - pathB.setFillType(SkPath::kWinding_FillType); - pathB.addRect(0, 0, 3, 3, SkPath::kCW_Direction); - pathB.addRect(1, 1, 2, 2, SkPath::kCW_Direction); - testShapeOp(path, pathB, kUnion_Op); -} - -static void testOp8d() { - SkPath path, pathB; - path.addRect(0, 0, 640, 480); - pathB.moveTo(577330, 1971.72f); - pathB.cubicTo(10.7082f, -116.596f, 262.057f, 45.6468f, 294.694f, 1.96237f); - pathB.close(); - testShapeOp(path, pathB, kDifference_Op); -} static struct { void (*fun)(); const char* str; } subTests[] = { - TEST(testOp8d), - TEST(testDiff1), - TEST(testIntersect1), - TEST(testUnion1), - TEST(testXor1), - TEST(testDiff2), - TEST(testIntersect2), - TEST(testUnion2), - TEST(testXor2), - TEST(testOp1d), - TEST(testOp2d), - TEST(testOp3d), - TEST(testOp1u), - TEST(testOp4d), - TEST(testOp5d), - TEST(testOp6d), - TEST(testOp7d), - TEST(testOp2u), + TEST(cubicOp23d), + TEST(cubicOp24d), + TEST(cubicOp18d), + TEST(cubicOp15d), + TEST(cubicOp14d), + TEST(cubicOp13d), + TEST(cubicOp11d), + TEST(cubicOp9d), + TEST(cubicOp8d), + TEST(cubicOp7d), + TEST(cubicOp6d), + TEST(cubicOp5d), }; static const size_t subTestCount = sizeof(subTests) / sizeof(subTests[0]); -static void (*firstBinaryTest)() = 0; +static void (*firstSubTest)() = 0; static bool skipAll = false; -static bool runBinaryTestsFirst = false; +static bool runSubTestsFirst = false; static bool runReverse = true; static void (*stopTest)() = 0; @@ -4466,15 +4563,15 @@ void SimplifyNew_Test() { gDebugMaxWindValue = 4; size_t index; #endif - if (runBinaryTestsFirst && firstBinaryTest) { + if (runSubTestsFirst && firstSubTest) { index = subTestCount - 1; - while (index > 0 && subTests[index].fun != firstBinaryTest) { + while (index > 0 && subTests[index].fun != firstSubTest) { --index; } SkDebugf(" %s [%s]\n", __FUNCTION__, subTests[index].str); (*subTests[index].fun)(); } - if (runBinaryTestsFirst) { + if (runSubTestsFirst) { index = subTestCount - 1; do { SkDebugf(" %s [%s]\n", __FUNCTION__, subTests[index].str); @@ -4504,7 +4601,7 @@ void SimplifyNew_Test() { } index += runReverse ? -1 : 1; } while (true); - if (!runBinaryTestsFirst) { + if (!runSubTestsFirst) { index = subTestCount - 1; do { SkDebugf(" %s [%s]\n", __FUNCTION__, subTests[index].str); diff --git a/experimental/Intersection/as.htm b/experimental/Intersection/as.htm index 2ed8015be7..b5487668b6 100644 --- a/experimental/Intersection/as.htm +++ b/experimental/Intersection/as.htm @@ -2,6 +2,11 @@ <head> <div style="height:0"> +<div id="cubicOp25i"> +debugShowActiveSpans id=1 (0,1 2,4 5,0 3,2) t=0.466666667 (2.84355545,1.9478519) tEnd=0.605057566 other=2 otherT=0.0521481481 otherIndex=1 windSum=-1 windValue=1 oppValue=0 +debugShowActiveSpans id=2 (3,2 0,1) t=0.0521481481 (2.84355545,1.9478519) tEnd=0.377811276 other=1 otherT=0.466666667 otherIndex=2 windSum=1 windValue=1 oppValue=0 +</div> + <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 @@ -16,11 +21,32 @@ debugShowActiveSpans id=2 (6,2 0,2) t=0.711411698 (1.73152983,2) tEnd=0.83333333 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 id="cubicOp28u"> +debugShowActiveSpans id=3 (0,6 2,3 1,0 4,1) t=0 (0,6) tEnd=0.473902244 other=4 otherT=1 otherIndex=3 windSum=? windValue=1 oppValue=0 +debugShowActiveSpans id=3 (0,6 2,3 1,0 4,1) t=0.473902244 (1.5671773,2.16060209) tEnd=0.57224743 other=1 otherT=0.287206281 otherIndex=1 windSum=? windValue=1 oppValue=0 +debugShowActiveSpans id=3 (0,6 2,3 1,0 4,1) t=0.57224743 (1.79802597,1.59934199) tEnd=1 other=2 otherT=0.400657994 otherIndex=2 windSum=? windValue=1 oppValue=0 +debugShowActiveSpans id=4 (4,1 0,6) t=0 (4,1) tEnd=0.13678207 other=3 otherT=1 otherIndex=3 windSum=? windValue=1 oppValue=0 +debugShowActiveSpans id=4 (4,1 0,6) t=0.13678207 (3.4528718,1.68391037) tEnd=0.145041093 other=1 otherT=0.583645693 otherIndex=3 windSum=? windValue=1 oppValue=0 +debugShowActiveSpans id=4 (4,1 0,6) t=0.145041093 (3.41983557,1.72520542) tEnd=1 other=1 otherT=0.945703361 otherIndex=6 windSum=? windValue=1 oppValue=0 +debugShowActiveSpans id=1 (0,1 1,4 6,0 3,2) t=0 (0,1) tEnd=0.287206281 other=2 otherT=1 otherIndex=3 windSum=? windValue=1 oppValue=0 +debugShowActiveSpans id=1 (0,1 1,4 6,0 3,2) t=0.287206281 (1.5671773,2.16060209) tEnd=0.470588235 other=3 otherT=0.473902244 otherIndex=1 windSum=? windValue=1 oppValue=0 +debugShowActiveSpans id=1 (0,1 1,4 6,0 3,2) t=0.470588235 (2.81864452,1.93954813) tEnd=0.583645693 other=2 otherT=0.0604518624 otherIndex=1 windSum=? windValue=1 oppValue=0 +debugShowActiveSpans id=1 (0,1 1,4 6,0 3,2) t=0.583645693 (3.4528718,1.68391037) tEnd=0.614942976 other=4 otherT=0.13678207 otherIndex=1 windSum=? windValue=1 oppValue=0 +debugShowActiveSpans id=1 (0,1 1,4 6,0 3,2) t=0.614942976 (3.59216309,1.61630249) tEnd=0.916307024 other=1 otherT=0.916307024 otherIndex=5 windSum=? windValue=1 oppValue=0 +debugShowActiveSpans id=1 (0,1 1,4 6,0 3,2) t=0.916307024 (3.59216309,1.61630249) tEnd=0.945703361 other=1 otherT=0.614942976 otherIndex=4 windSum=? windValue=1 oppValue=0 +debugShowActiveSpans id=1 (0,1 1,4 6,0 3,2) t=0.945703361 (3.41983557,1.72520542) tEnd=1 other=4 otherT=0.145041093 otherIndex=2 windSum=? windValue=1 oppValue=0 +debugShowActiveSpans id=2 (3,2 0,1) t=0 (3,2) tEnd=0.0604518624 other=1 otherT=1 otherIndex=7 windSum=? windValue=1 oppValue=0 +debugShowActiveSpans id=2 (3,2 0,1) t=0.0604518624 (2.81864452,1.93954813) tEnd=0.400657994 other=1 otherT=0.470588235 otherIndex=2 windSum=? windValue=1 oppValue=0 +debugShowActiveSpans id=2 (3,2 0,1) t=0.400657994 (1.79802597,1.59934199) tEnd=1 other=3 otherT=0.57224743 otherIndex=2 windSum=? windValue=1 oppValue=0 +</div> + </div> <script type="text/javascript"> var testDivs = [ + cubicOp28u, + cubicOp25i, cubicOp19i, ]; diff --git a/experimental/Intersection/cd.htm b/experimental/Intersection/cd.htm new file mode 100644 index 0000000000..2e43022d7e --- /dev/null +++ b/experimental/Intersection/cd.htm @@ -0,0 +1,517 @@ +<html> +<head> +<div style="height:0"> + +<div id="test1"> +computeDelta c1=(0,1 1,6 1,0 2,0) t1=0.0166500365 scale1=1 c2=(0,1 0,2 1,0 6,1) t2=0.126935168 scale2=1 +cubicTangent t=0.0166500365 tangent=(-2.85263545,-12.6745554 2.95089079,15.1559166) pt=(0.0491276698 1.24068063) dxy=(2.90176312 13.915236) +cubicTangent t=0.126935168 tangent=(-0.852150487,0.242871519 0.961097194,2.2532568) pt=(0.0544733534 1.24806416) dxy=(0.90662384 1.00519264) +cubicDelta tangent=(-0.00039510851,-0.00189471984 0.0495227783,1.24257535) intersectLen=0.00193547772 tangentLen=14.2145708 scale=0.00390625 result=0.00404241153 +cubicDelta tangent=(0.00495057512,0.00548880522 0.0495227783,1.24257535) intersectLen=0.00739156118 tangentLen=1.35365395 scale=0.00390625 result=0.00936670107 +</div> + +<div id="test2"> +computeDelta c1=(0,1 0,2 1,0 6,1) t1=0.121215914 scale1=0.0187334021 c2=(0,1 1,6 1,0 2,0) t2=0.0167515231 scale2=0.00808482306 +cubicTangent t=0.121215914 tangent=(-0.810112087,0.159501524 0.908958243,2.32468734) pt=(0.0494230781 1.24209443) dxy=(0.859535165 1.08259291) +cubicTangent t=0.0167515231 tangent=(-2.85175241,-12.6666182 2.95059667,15.1508033) pt=(0.0494221303 1.24209251) dxy=(2.90117454 13.9087108) +cubicDelta tangent=(7.4284882e-07,9.35625319e-07 0.0494223352,1.2420935) intersectLen=1.19466276e-06 tangentLen=1.38231983 scale=7.31773521e-05 result=7.40415969e-05 +cubicDelta tangent=(-2.04951629e-07,-9.82572016e-07 0.0494223352,1.2420935) intersectLen=1.00371955e-06 tangentLen=14.2080628 scale=3.15813401e-05 result=3.16519844e-05 +</div> + +<div id="test3"> +computeDelta c1=(0,1 1,6 1,0 2,0) t1=0.0167458976 scale1=6.33039689e-05 c2=(0,1 0,2 1,0 6,1) t2=0.121141872 scale2=0.000148083194 +cubicTangent t=0.0167458976 tangent=(-2.85180136,-12.6670582 2.95061297,15.1510867) pt=(0.0494058095 1.24201427) dxy=(2.90120716 13.9090724) +cubicTangent t=0.121141872 tangent=(-0.809569955,0.158411583 0.908288874,2.32561689) pt=(0.0493594591 1.24201424) dxy=(0.858929414 1.08360265) +cubicDelta tangent=(-1.65436799e-05,-7.93143093e-05 0.0494223532,1.24209358) intersectLen=8.1021312e-05 tangentLen=14.2084235 scale=2.47281129e-07 result=5.94962466e-06 +cubicDelta tangent=(-6.28940702e-05,-7.93454971e-05 0.0494223532,1.24209358) intersectLen=0.000101249059 tangentLen=1.38273441 scale=5.78449976e-07 result=7.38022436e-05 +</div> + +</div> + +<script type="text/javascript"> + +var testDivs = [ + test3, + test2, + test1, +]; + +var scale, columns, rows, xStart, yStart; + +var ticks = 10; +var at_x = 13 + 0.5; +var at_y = 23 + 0.5; +var decimal_places = 3; +var tests = []; +var testTitles = []; +var testIndex = 0; +var ctx; +var minScale = 1; +var subscale = 1; +var curveT = -1; +var drawCubics = true; +var drawQuads = true; +var drawControlLines = true; +var drawT = true; + +var xmin, xmax, ymin, ymax; + +function strs_to_nums(strs) { + var result = []; + for (var idx in strs) { + var str = strs[idx]; + var num = parseFloat(str); + if (isNaN(num)) { + result.push(str); + } else { + result.push(num); + } + } + return result; +} + +function construct_regexp(pattern) { + var escape = pattern.replace(/[-/\\^$*+?.()|[\]{}]/g, '\\$&'); + escape = escape.replace(/PT_VAL/g, "(-?\\d+\\.?\\d*e?-?\\d*),(-?\\d+\\.?\\d*e?-?\\d*)"); + escape = escape.replace(/T_VAL/g, "(-?\\d+\\.?\\d*e?-?\\d*)"); + escape = escape.replace(/IDX/g, "(\\d+)"); + escape = escape.replace(/OPT/g, "(\\?|-?\\d+)"); + return new RegExp(escape, 'i'); +} + +var COMPUTE_DELTA = 1; +var CUBIC_TANGENT = 2; +var CUBIC_DATA = 3; + +var DELTA_C1_X1 = 1; +var DELTA_C1_Y1 = 2; +var DELTA_C1_X2 = 3; +var DELTA_C1_Y2 = 4; +var DELTA_C1_X3 = 5; +var DELTA_C1_Y3 = 6; +var DELTA_C1_X4 = 7; +var DELTA_C1_Y4 = 8; +var DELTA_T1 = 9; +var DELTA_SCALE1 = 10; +var DELTA_C2_X1 = 11; +var DELTA_C2_Y1 = 12; +var DELTA_C2_X2 = 13; +var DELTA_C2_Y2 = 14; +var DELTA_C2_X3 = 15; +var DELTA_C2_Y3 = 16; +var DELTA_C2_X4 = 17; +var DELTA_C2_Y4 = 18; +var DELTA_T2 = 19; +var DELTA_SCALE2 = 20; + +var TANGENT_T = 1; +var TANGENT_TANGENT_X1 = 2; +var TANGENT_TANGENT_Y1 = 3; +var TANGENT_TANGENT_X2 = 4; +var TANGENT_TANGENT_Y2 = 5; +var TANGENT_PT_X = 6; +var TANGENT_PT_Y = 7; +var TANGENT_DXY_X = 8; +var TANGENT_DXY_Y = 9; + +var CUBIC_TANGENT_X1 = 1; +var CUBIC_TANGENT_Y1 = 2; +var CUBIC_TANGENT_X2 = 3; +var CUBIC_TANGENT_Y2 = 4; +var CUBIC_INTERSECTION_LEN = 5; +var CUBIC_TANGENT_LEN = 6; +var CUBIC_SCALE = 7; +var CUBIC_RESULT = 8; + +function parse(test, title) { + var compute_delta = construct_regexp(" c1=(PT_VAL PT_VAL PT_VAL PT_VAL)" + + " t1=T_VAL scale1=T_VAL c2=(PT_VAL PT_VAL PT_VAL PT_VAL) t2=T_VAL scale2=T_VAL"); + var cubic_tangent = construct_regexp(" t=T_VAL tangent=(PT_VAL PT_VAL)" + + " pt=(T_VAL T_VAL) dxy=(T_VAL T_VAL)"); + var cubic_data = construct_regexp(" tangent=(PT_VAL PT_VAL)" + + " intersectLen=T_VAL tangentLen=T_VAL scale=T_VAL result=T_VAL"); + + var cStrs = test.split("computeDelta"); + var data = []; + for (var cs in cStrs) { + var str = cStrs[cs]; + if (str == "\n") { + continue; + } + var tStrs = str.split("cubicTangent"); + for (var ts in tStrs) { + str = tStrs[ts]; + if (str == "\n") { + continue; + } + var dStrs = str.split("cubicDelta"); + var dataStrs; + for (var ds in dStrs) { + str = dStrs[ds]; + if (str == "\n") { + continue; + } + var lineMatch, lineStrs; + if (compute_delta.test(str)) { + lineMatch = COMPUTE_DELTA; + lineStrs = compute_delta.exec(str); + } else if (cubic_tangent.test(str)) { + lineMatch = CUBIC_TANGENT; + lineStrs = cubic_tangent.exec(str); + } else if (cubic_data.test(str)) { + lineMatch = CUBIC_DATA; + lineStrs = cubic_data.exec(str); + } else { + continue; + } + var line = strs_to_nums(lineStrs); + data.push(lineMatch); + data.push(line); + } + } + } + if (data.length >= 1) { + tests.push(data); + testTitles.push(title); + } +} + +function init(test) { + var canvas = document.getElementById('canvas'); + if (!canvas.getContext) return; + canvas.width = window.innerWidth - at_x; + canvas.height = window.innerHeight - at_y; + ctx = canvas.getContext('2d'); + xmin = Infinity; + xmax = -Infinity; + ymin = Infinity; + ymax = -Infinity; + var scanType = -1; + for (var scansStr in test) { + var scans = parseInt(scansStr); + var scan = test[scans]; + if (scanType == -1) { + scanType = scan; + continue; + } + if (scanType == CUBIC_TANGENT) { + for (var idx = TANGENT_TANGENT_X1; idx < TANGENT_PT_X; idx += 2) { + xmin = Math.min(xmin, scan[idx]); + xmax = Math.max(xmax, scan[idx]); + ymin = Math.min(ymin, scan[idx + 1]); + ymax = Math.max(ymax, scan[idx + 1]); + } + } + scanType = -1; + } + var testW = xmax - xmin; + var testH = ymax - ymin; + subscale = 1; + if (testW > 1e10 || testH > 1e10) { + return; + } + while (testW * subscale < 0.1 && testH * subscale < 0.1) { + subscale *= 10; + } + while (testW * subscale > 10 && testH * subscale > 10) { + subscale /= 10; + } + calcFromScale(); +} + +function calcFromScale() { + xStart = Math.floor(xmin * subscale) / subscale; + yStart = Math.floor(ymin * subscale) / subscale; + var xEnd = Math.ceil(xmin * subscale) / subscale; + var yEnd = Math.ceil(ymin * subscale) / subscale; + var cCelsW = Math.floor(ctx.canvas.width / 10); + var cCelsH = Math.floor(ctx.canvas.height / 10); + var testW = xEnd - xStart; + var testH = yEnd - yStart; + var scaleWH = 1; + while (cCelsW > testW * scaleWH * 10 && cCelsH > testH * scaleWH * 10) { + scaleWH *= 10; + } + while (cCelsW * 10 < testW * scaleWH && cCelsH * 10 < testH * scaleWH) { + scaleWH /= 10; + } + + columns = Math.ceil(xmax * subscale) - Math.floor(xmin * subscale) + 1; + rows = Math.ceil(ymax * subscale) - Math.floor(ymin * subscale) + 1; + + var hscale = ctx.canvas.width / columns / ticks; + var vscale = ctx.canvas.height / rows / ticks; + minScale = Math.floor(Math.min(hscale, vscale)); + scale = minScale * subscale; +} + +function drawPoint(px, py, xoffset, yoffset, unit) { + var label = px.toFixed(decimal_places) + ", " + py.toFixed(decimal_places); + var _px = px * unit + xoffset; + var _py = py * unit + yoffset; + ctx.beginPath(); + ctx.arc(_px, _py, 3, 0, Math.PI*2, true); + ctx.closePath(); + ctx.fill(); + ctx.fillText(label, _px + 5, _py); +} + +function drawTPt(scan, cIdx, tIdx, xoffset, yoffset, unit) { + var t = scan[tIdx]; + var one_t = 1 - t; + var one_t2 = one_t * one_t; + var a = one_t2 * one_t; + var b = 3 * one_t2 * t; + var t2 = t * t; + var c = 3 * one_t * t2; + var d = t2 * t; + var x = a * scan[cIdx + 0] + b * scan[cIdx + 2] + c * scan[cIdx + 4] + d * scan[cIdx + 6]; + var y = a * scan[cIdx + 1] + b * scan[cIdx + 3] + c * scan[cIdx + 5] + d * scan[cIdx + 7]; + drawPoint(x, y, xoffset, yoffset, unit); +} + +function draw(test, title, scale) { + ctx.fillStyle = "rgba(0,0,0, 0.1)"; + ctx.font = "normal 50px Arial"; + ctx.fillText(title, 50, 50); + ctx.font = "normal 10px Arial"; + + var unit = scale * ticks; + ctx.lineWidth = 1; + var i; + for (i = 0; i <= rows * ticks; ++i) { + ctx.strokeStyle = (i % ticks) != 0 ? "rgb(200,200,200)" : "black"; + ctx.beginPath(); + ctx.moveTo(at_x + 0, at_y + i * minScale); + ctx.lineTo(at_x + ticks * columns * minScale, at_y + i * minScale); + ctx.stroke(); + } + for (i = 0; i <= columns * ticks; ++i) { + ctx.strokeStyle = (i % ticks) != 0 ? "rgb(200,200,200)" : "black"; + ctx.beginPath(); + ctx.moveTo(at_x + i * minScale, at_y + 0); + ctx.lineTo(at_x + i * minScale, at_y + ticks * rows * minScale); + ctx.stroke(); + } + + var xoffset = xStart * -unit + at_x; + var yoffset = yStart * -unit + at_y; + + ctx.fillStyle = "rgb(40,80,60)" + for (i = 0; i <= columns; i += 1) + { + num = xStart + i / subscale; + ctx.fillText(num.toFixed(decimal_places), xoffset + num * unit - 5, 10); + } + for (i = 0; i <= rows; i += 1) + { + num = yStart + i / subscale; + ctx.fillText(num.toFixed(decimal_places), 0, yoffset + num * unit + 0); + } + var scanType = -1; + var partIndex = 0; + for (var scans in test) { + var scan = test[scans]; + if (scanType == -1) { + scanType = scan; + continue; + } + partIndex++; + if (scanType == COMPUTE_DELTA) { + ctx.beginPath(); + ctx.moveTo(xoffset + scan[DELTA_C1_X1] * unit, yoffset + scan[DELTA_C1_Y1] * unit); + ctx.bezierCurveTo( + xoffset + scan[DELTA_C1_X2] * unit, yoffset + scan[DELTA_C1_Y2] * unit, + xoffset + scan[DELTA_C1_X3] * unit, yoffset + scan[DELTA_C1_Y3] * unit, + xoffset + scan[DELTA_C1_X4] * unit, yoffset + scan[DELTA_C1_Y4] * unit); + ctx.strokeStyle = "red"; // "rgba(0,0,0, 1.0)"; + ctx.stroke(); + ctx.beginPath(); + ctx.moveTo(xoffset + scan[DELTA_C2_X1] * unit, yoffset + scan[DELTA_C2_Y1] * unit); + ctx.bezierCurveTo( + xoffset + scan[DELTA_C2_X2] * unit, yoffset + scan[DELTA_C2_Y2] * unit, + xoffset + scan[DELTA_C2_X3] * unit, yoffset + scan[DELTA_C2_Y3] * unit, + xoffset + scan[DELTA_C2_X4] * unit, yoffset + scan[DELTA_C2_Y4] * unit); + ctx.strokeStyle = "blue"; // "rgba(0,0,0, 1.0)"; + ctx.stroke(); + } + if (scanType == COMPUTE_DELTA && drawControlLines) { + ctx.beginPath(); + ctx.moveTo(xoffset + scan[DELTA_C1_X1] * unit, yoffset + scan[DELTA_C1_Y1] * unit); + ctx.lineTo(xoffset + scan[DELTA_C1_X2] * unit, yoffset + scan[DELTA_C1_Y2] * unit); + ctx.lineTo(xoffset + scan[DELTA_C1_X3] * unit, yoffset + scan[DELTA_C1_Y3] * unit); + ctx.lineTo(xoffset + scan[DELTA_C1_X4] * unit, yoffset + scan[DELTA_C1_Y4] * unit); + ctx.strokeStyle = "rgba(0,0,0, 0.3)"; + ctx.stroke(); + ctx.beginPath(); + ctx.moveTo(xoffset + scan[DELTA_C2_X1] * unit, yoffset + scan[DELTA_C2_Y1] * unit); + ctx.lineTo(xoffset + scan[DELTA_C2_X2] * unit, yoffset + scan[DELTA_C2_Y2] * unit); + ctx.lineTo(xoffset + scan[DELTA_C2_X3] * unit, yoffset + scan[DELTA_C2_Y3] * unit); + ctx.lineTo(xoffset + scan[DELTA_C2_X4] * unit, yoffset + scan[DELTA_C2_Y4] * unit); + ctx.strokeStyle = "rgba(0,0,0, 0.3)"; + ctx.stroke(); + } + if (scanType == COMPUTE_DELTA && drawT) { + drawTPt(scan, DELTA_C1_X1, DELTA_T1, xoffset, yoffset, unit); + drawTPt(scan, DELTA_C2_X1, DELTA_T2, xoffset, yoffset, unit); + var num = "c1=" + scan[DELTA_T1].toFixed(decimal_places) + + " c2=" + scan[DELTA_T2].toFixed(decimal_places); + ctx.beginPath(); + ctx.rect(200,10,200,10); + ctx.fillStyle="white"; + ctx.fill(); + ctx.fillStyle="black"; + ctx.fillText(num, 230, 18); + } + if (scanType == CUBIC_TANGENT) { + ctx.beginPath(); + ctx.moveTo(xoffset + scan[TANGENT_TANGENT_X1] * unit, yoffset + scan[TANGENT_TANGENT_Y1] * unit); + ctx.lineTo(xoffset + scan[TANGENT_TANGENT_X2] * unit, yoffset + scan[TANGENT_TANGENT_Y2] * unit); + ctx.strokeStyle = partIndex > 2 ? "rgba(0,0,255, 0.7)" : "rgba(255,0,0, 0.7)"; + ctx.stroke(); + } + scanType = -1; + } +} + +function drawTop() { + init(tests[testIndex]); + redraw(); +} + +function redraw() { + ctx.beginPath(); + ctx.rect(0, 0, ctx.canvas.width, ctx.canvas.height); + ctx.fillStyle="white"; + ctx.fill(); + draw(tests[testIndex], testTitles[testIndex], scale); +} + +function doKeyPress(evt) { + var char = String.fromCharCode(evt.charCode); + switch (char) { + case 'c': + drawCubics ^= true; + redraw(); + break; + case 'd': + decimal_places++; + redraw(); + break; + case 'D': + decimal_places--; + if (decimal_places < 1) { + decimal_places = 1; + } + redraw(); + break; + case 'l': + drawControlLines ^= true; + redraw(); + break; + case 'N': + testIndex += 9; + case 'n': + if (++testIndex >= tests.length) + testIndex = 0; + mouseX = Infinity; + drawTop(); + break; + case 'P': + testIndex -= 9; + case 'p': + if (--testIndex < 0) + testIndex = tests.length - 1; + mouseX = Infinity; + drawTop(); + break; + case 'q': + drawQuads ^= true; + redraw(); + break; + case 't': + drawT ^= true; + redraw(); + break; + case 'x': + drawCubics ^= true; + drawQuads ^= true; + redraw(); + break; + case '-': + case '_': + subscale /= 2; + calcFromScale(); + redraw(); + break; + case '+': + case '=': + subscale *= 2; + calcFromScale(); + redraw(); + break; + } +} + +/* + var e = window.event; + var tgt = e.target || e.srcElement; + var min = tgt.offsetTop + Math.ceil(at_y); + var max = min + ticks * rows * minScale; + curveT = (e.clientY - min) / (max - min); + redraw(); +} +*/ + +function calcXY() { + var e = window.event; + var tgt = e.target || e.srcElement; + var left = tgt.offsetLeft; + var top = tgt.offsetTop; + var unit = scale * ticks; + mouseX = (e.clientX - left - Math.ceil(at_x) + 1) / unit + xStart; + mouseY = (e.clientY - top - Math.ceil(at_y)) / unit + yStart; +} + +function handleMouseOver() { + /* calcXY(); + var num = mouseX.toFixed(decimal_places) + ", " + mouseY.toFixed(decimal_places); + ctx.beginPath(); + ctx.rect(30,10,200,10); + ctx.fillStyle="white"; + ctx.fill(); + ctx.fillStyle="black"; + ctx.fillText(num, 30, 18); +*/ +} + +function start() { + for (i = 0; i < testDivs.length; ++i) { + var title = testDivs[i].id.toString(); + var str = testDivs[i].firstChild.data; + parse(str, title); + } + drawTop(); + window.addEventListener('keypress', doKeyPress, true); + window.onresize = function() { + drawTop(); + } +} + +function handleMouseClick() { + start(); +} + +function startx() { +} + +</script> +</head> + +<body onLoad="startx();"> +<canvas id="canvas" width="750" height="500" + onmousemove="handleMouseOver()" + onclick="handleMouseClick()" + ></canvas > +</body> +</html> diff --git a/experimental/Intersection/hg.htm b/experimental/Intersection/hg.htm new file mode 100644 index 0000000000..32f49a7446 --- /dev/null +++ b/experimental/Intersection/hg.htm @@ -0,0 +1,649 @@ +<html> +<head> +<div style="height:0"> + +<div id="cubic1"> +{{3.13,2.74}, {1.08,4.62}, {3.71,0.94}, {2.01,3.81}} +{{6.71,3.14}, {7.99,2.75}, {8.27,1.96}, {6.35,3.57}} +{{9.45,10.67}, {10.05,5.78}, {13.95,7.46}, {14.72,5.29}} +{{3.34,8.98}, {1.95,10.27}, {3.76,7.65}, {4.96,10.64}} +</div> + +</div> + +<script type="text/javascript"> + +var testDivs = [ + cubic1, +]; + +var scale, columns, rows, xStart, yStart; + +var ticks = 10; +var at_x = 13 + 0.5; +var at_y = 23 + 0.5; +var decimal_places = 3; +var tests = []; +var testTitles = []; +var testIndex = 0; +var ctx; +var minScale = 1; +var subscale = 1; +var curveT = -1; +var xmin, xmax, ymin, ymax; + +var mouseX, mouseY; +var mouseDown = false; + +var draw_deriviatives = false; +var draw_endpoints = true; +var draw_hodo = false; +var draw_hodo2 = false; +var draw_hodo_origin = true; +var draw_midpoint = false; +var draw_tangents = true; +var draw_sequence = true; + +function parse(test, title) { + var curveStrs = test.split("{{"); + if (curveStrs.length == 1) + curveStrs = test.split("=("); + var pattern = /[a-z$=]?-?\d+\.*\d*e?-?\d*/g; + var curves = []; + for (var c in curveStrs) { + var curveStr = curveStrs[c]; + var points = curveStr.match(pattern); + var pts = []; + for (var wd in points) { + var num = parseFloat(points[wd]); + if (isNaN(num)) continue; + pts.push(num); + } + if (pts.length > 2) + curves.push(pts); + } + if (curves.length >= 1) { + tests.push(curves); + testTitles.push(title); + } +} + +function init(test) { + var canvas = document.getElementById('canvas'); + if (!canvas.getContext) return; + canvas.width = window.innerWidth - 20; + canvas.height = window.innerHeight - 20; + ctx = canvas.getContext('2d'); + xmin = Infinity; + xmax = -Infinity; + ymin = Infinity; + ymax = -Infinity; + for (var curves in test) { + var curve = test[curves]; + var last = curve.length; + for (var idx = 0; idx < last; idx += 2) { + xmin = Math.min(xmin, curve[idx]); + xmax = Math.max(xmax, curve[idx]); + ymin = Math.min(ymin, curve[idx + 1]); + ymax = Math.max(ymax, curve[idx + 1]); + } + } + xmin -= 1; + var testW = xmax - xmin; + var testH = ymax - ymin; + subscale = 1; + while (testW * subscale < 0.1 && testH * subscale < 0.1) { + subscale *= 10; + } + while (testW * subscale > 10 && testH * subscale > 10) { + subscale /= 10; + } + calcFromScale(); +} + +function hodograph(cubic) { + var hodo = []; + hodo[0] = 3 * (cubic[2] - cubic[0]); + hodo[1] = 3 * (cubic[3] - cubic[1]); + hodo[2] = 3 * (cubic[4] - cubic[2]); + hodo[3] = 3 * (cubic[5] - cubic[3]); + hodo[4] = 3 * (cubic[6] - cubic[4]); + hodo[5] = 3 * (cubic[7] - cubic[5]); + return hodo; +} + +function hodograph2(cubic) { + var quad = hodograph(cubic); + var hodo = []; + hodo[0] = 2 * (quad[2] - quad[0]); + hodo[1] = 2 * (quad[3] - quad[1]); + hodo[2] = 2 * (quad[4] - quad[2]); + hodo[3] = 2 * (quad[5] - quad[3]); + return hodo; +} + +function quadraticRootsReal(A, B, C, s) { + if (A == 0) { + if (B == 0) { + s[0] = 0; + return C == 0; + } + s[0] = -C / B; + return 1; + } + /* normal form: x^2 + px + q = 0 */ + var p = B / (2 * A); + var q = C / A; + var p2 = p * p; + if (p2 < q) { + return 0; + } + var sqrt_D = 0; + if (p2 > q) { + sqrt_D = sqrt(p2 - q); + } + s[0] = sqrt_D - p; + s[1] = -sqrt_D - p; + return 1 + s[0] != s[1]; +} + +function add_valid_ts(s, realRoots, t) { + var foundRoots = 0; + for (var index = 0; index < realRoots; ++index) { + var tValue = s[index]; + if (tValue >= 0 && tValue <= 1) { + for (var idx2 = 0; idx2 < foundRoots; ++idx2) { + if (t[idx2] != tValue) { + t[foundRoots++] = tValue; + } + } + } + } + return foundRoots; +} + +function quadraticRootsValidT(a, b, c, t) { + var s = []; + var realRoots = quadraticRootsReal(A, B, C, s); + var foundRoots = add_valid_ts(s, realRoots, t); + return foundRoots != 0; +} + +function find_cubic_inflections(cubic, tValues) +{ + var Ax = src[2] - src[0]; + var Ay = src[3] - src[1]; + var Bx = src[4] - 2 * src[2] + src[0]; + var By = src[5] - 2 * src[3] + src[1]; + var Cx = src[6] + 3 * (src[2] - src[4]) - src[0]; + var Cy = src[7] + 3 * (src[3] - src[5]) - src[1]; + return quadraticRootsValidT(Bx * Cy - By * Cx, (Ax * Cy - Ay * Cx), + Ax * By - Ay * Bx, tValues); +} + +function dx_at_t(cubic, t) { + var one_t = 1 - t; + var a = cubic[0]; + var b = cubic[2]; + var c = cubic[4]; + var d = cubic[6]; + return 3 * ((b - a) * one_t * one_t + 2 * (c - b) * t * one_t + (d - c) * t * t); +} + +function dy_at_t(cubic, t) { + var one_t = 1 - t; + var a = cubic[1]; + var b = cubic[3]; + var c = cubic[5]; + var d = cubic[7]; + return 3 * ((b - a) * one_t * one_t + 2 * (c - b) * t * one_t + (d - c) * t * t); +} + +function x_at_t(cubic, t) { + var one_t = 1 - t; + var one_t2 = one_t * one_t; + var a = one_t2 * one_t; + var b = 3 * one_t2 * t; + var t2 = t * t; + var c = 3 * one_t * t2; + var d = t2 * t; + return a * cubic[0] + b * cubic[2] + c * cubic[4] + d * cubic[6]; +} + +function y_at_t(cubic, t) { + var one_t = 1 - t; + var one_t2 = one_t * one_t; + var a = one_t2 * one_t; + var b = 3 * one_t2 * t; + var t2 = t * t; + var c = 3 * one_t * t2; + var d = t2 * t; + return a * cubic[1] + b * cubic[3] + c * cubic[5] + d * cubic[7]; +} + +function calcFromScale() { + xStart = Math.floor(xmin * subscale) / subscale; + yStart = Math.floor(ymin * subscale) / subscale; + var xEnd = Math.ceil(xmin * subscale) / subscale; + var yEnd = Math.ceil(ymin * subscale) / subscale; + var cCelsW = Math.floor(ctx.canvas.width / 10); + var cCelsH = Math.floor(ctx.canvas.height / 10); + var testW = xEnd - xStart; + var testH = yEnd - yStart; + var scaleWH = 1; + while (cCelsW > testW * scaleWH * 10 && cCelsH > testH * scaleWH * 10) { + scaleWH *= 10; + } + while (cCelsW * 10 < testW * scaleWH && cCelsH * 10 < testH * scaleWH) { + scaleWH /= 10; + } + + columns = Math.ceil(xmax * subscale) - Math.floor(xmin * subscale) + 1; + rows = Math.ceil(ymax * subscale) - Math.floor(ymin * subscale) + 1; + + var hscale = ctx.canvas.width / columns / ticks; + var vscale = ctx.canvas.height / rows / ticks; + minScale = Math.floor(Math.min(hscale, vscale)); + scale = minScale * subscale; +} + +function drawLine(x1, y1, x2, y2) { + var unit = scale * ticks; + var xoffset = xStart * -unit + at_x; + var yoffset = yStart * -unit + at_y; + ctx.beginPath(); + ctx.moveTo(xoffset + x1 * unit, yoffset + y1 * unit); + ctx.lineTo(xoffset + x2 * unit, yoffset + y2 * unit); + ctx.stroke(); +} + +function drawPoint(px, py) { + var unit = scale * ticks; + var xoffset = xStart * -unit + at_x; + var yoffset = yStart * -unit + at_y; + var _px = px * unit + xoffset; + var _py = py * unit + yoffset; + ctx.beginPath(); + ctx.arc(_px, _py, 3, 0, Math.PI*2, true); + ctx.closePath(); + ctx.stroke(); +} + +function drawPointSolid(px, py) { + drawPoint(px, py); + ctx.fillStyle = "rgba(0,0,0, 0.4)"; + ctx.fill(); +} + +function drawLabel(num, px, py) { + ctx.beginPath(); + ctx.arc(px, py, 8, 0, Math.PI*2, true); + ctx.closePath(); + ctx.strokeStyle = "rgba(0,0,0, 0.4)"; + ctx.lineWidth = num == 0 || num == 3 ? 2 : 1; + ctx.stroke(); + ctx.fillStyle = "black"; + ctx.font = "normal 10px Arial"; + // ctx.rotate(0.001); + ctx.fillText(num, px - 2, py + 3); + // ctx.rotate(-0.001); +} + +function drawLabelX(ymin, num, loc) { + var unit = scale * ticks; + var xoffset = xStart * -unit + at_x; + var yoffset = yStart * -unit + at_y; + var px = loc * unit + xoffset; + var py = ymin * unit + yoffset - 20; + drawLabel(num, px, py); +} + +function drawLabelY(xmin, num, loc) { + var unit = scale * ticks; + var xoffset = xStart * -unit + at_x; + var yoffset = yStart * -unit + at_y; + var px = xmin * unit + xoffset - 20; + var py = loc * unit + yoffset; + drawLabel(num, px, py); +} + +function drawHodoOrigin(hx, hy, hMinX, hMinY, hMaxX, hMaxY) { + ctx.beginPath(); + ctx.moveTo(hx, hy - 100); + ctx.lineTo(hx, hy); + ctx.strokeStyle = hMinY < 0 ? "green" : "blue"; + ctx.stroke(); + ctx.beginPath(); + ctx.moveTo(hx, hy); + ctx.lineTo(hx, hy + 100); + ctx.strokeStyle = hMaxY > 0 ? "green" : "blue"; + ctx.stroke(); + ctx.beginPath(); + ctx.moveTo(hx - 100, hy); + ctx.lineTo(hx, hy); + ctx.strokeStyle = hMinX < 0 ? "green" : "blue"; + ctx.stroke(); + ctx.beginPath(); + ctx.moveTo(hx, hy); + ctx.lineTo(hx + 100, hy); + ctx.strokeStyle = hMaxX > 0 ? "green" : "blue"; + ctx.stroke(); +} + +function logCurves(test) { + for (curves in test) { + var curve = test[curves]; + if (curve.length != 8) { + continue; + } + var str = "{{"; + for (i = 0; i < 8; i += 2) { + str += curve[i].toFixed(2) + "," + curve[i + 1].toFixed(2); + if (i < 6) { + str += "}, {"; + } + } + str += "}}"; + console.log(str); + } +} + +function scalexy(x, y, mag) { + var length = Math.sqrt(x * x + y * y); + return mag / length; +} + +function drawArrow(x, y, dx, dy) { + var unit = scale * ticks; + var xoffset = xStart * -unit + at_x; + var yoffset = yStart * -unit + at_y; + var dscale = scalexy(dx, dy, 1); + dx *= dscale; + dy *= dscale; + ctx.beginPath(); + ctx.moveTo(xoffset + x * unit, yoffset + y * unit); + x += dx; + y += dy; + ctx.lineTo(xoffset + x * unit, yoffset + y * unit); + dx /= 10; + dy /= 10; + ctx.lineTo(xoffset + (x - dy) * unit, yoffset + (y + dx) * unit); + ctx.lineTo(xoffset + (x + dx * 2) * unit, yoffset + (y + dy * 2) * unit); + ctx.lineTo(xoffset + (x + dy) * unit, yoffset + (y - dx) * unit); + ctx.lineTo(xoffset + x * unit, yoffset + y * unit); + ctx.strokeStyle = "rgba(0,75,0, 0.4)"; + ctx.stroke(); +} + +function draw(test, title) { + ctx.fillStyle = "rgba(0,0,0, 0.1)"; + ctx.font = "normal 50px Arial"; + ctx.fillText(title, 50, 50); + ctx.font = "normal 10px Arial"; + var unit = scale * ticks; + // ctx.lineWidth = "1.001"; "0.999"; + var xoffset = xStart * -unit + at_x; + var yoffset = yStart * -unit + at_y; + + for (curves in test) { + var curve = test[curves]; + if (curve.length != 8) { + continue; + } + ctx.lineWidth = 1; + if (draw_tangents) { + ctx.strokeStyle = "rgba(0,0,255, 0.3)"; + drawLine(curve[0], curve[1], curve[2], curve[3]); + drawLine(curve[2], curve[3], curve[4], curve[5]); + drawLine(curve[4], curve[5], curve[6], curve[7]); + } + if (draw_deriviatives) { + var dx = dx_at_t(curve, 0); + var dy = dy_at_t(curve, 0); + drawArrow(curve[0], curve[1], dx, dy); + dx = dx_at_t(curve, 1); + dy = dy_at_t(curve, 1); + drawArrow(curve[6], curve[7], dx, dy); + if (draw_midpoint) { + var midX = x_at_t(curve, 0.5); + var midY = y_at_t(curve, 0.5); + dx = dx_at_t(curve, 0.5); + dy = dy_at_t(curve, 0.5); + drawArrow(midX, midY, dx, dy); + } + } + ctx.beginPath(); + ctx.moveTo(xoffset + curve[0] * unit, yoffset + curve[1] * unit); + ctx.bezierCurveTo( + xoffset + curve[2] * unit, yoffset + curve[3] * unit, + xoffset + curve[4] * unit, yoffset + curve[5] * unit, + xoffset + curve[6] * unit, yoffset + curve[7] * unit); + ctx.strokeStyle = "black"; + ctx.stroke(); + if (draw_endpoints) { + drawPoint(curve[0], curve[1]); + drawPoint(curve[2], curve[3]); + drawPoint(curve[4], curve[5]); + drawPoint(curve[6], curve[7]); + } + if (draw_midpoint) { + var midX = x_at_t(curve, 0.5); + var midY = y_at_t(curve, 0.5); + drawPointSolid(midX, midY); + } + if (draw_hodo) { + var hodo = hodograph(curve); + var hMinX = Math.min(0, hodo[0], hodo[2], hodo[4]); + var hMinY = Math.min(0, hodo[1], hodo[3], hodo[5]); + var hMaxX = Math.max(0, hodo[0], hodo[2], hodo[4]); + var hMaxY = Math.max(0, hodo[1], hodo[3], hodo[5]); + var hScaleX = hMaxX - hMinX > 0 ? ctx.canvas.width / (hMaxX - hMinX) : 1; + var hScaleY = hMaxY - hMinY > 0 ? ctx.canvas.height / (hMaxY - hMinY) : 1; + var hUnit = Math.min(hScaleX, hScaleY); + hUnit /= 2; + var hx = xoffset - hMinX * hUnit; + var hy = yoffset - hMinY * hUnit; + ctx.moveTo(hx + hodo[0] * hUnit, hy + hodo[1] * hUnit); + ctx.quadraticCurveTo( + hx + hodo[2] * hUnit, hy + hodo[3] * hUnit, + hx + hodo[4] * hUnit, hy + hodo[5] * hUnit); + ctx.strokeStyle = "red"; + ctx.stroke(); + if (draw_hodo_origin) { + drawHodoOrigin(hx, hy, hMinX, hMinY, hMaxX, hMaxY); + } + } + if (draw_hodo2) { + var hodo = hodograph2(curve); + var hMinX = Math.min(0, hodo[0], hodo[2]); + var hMinY = Math.min(0, hodo[1], hodo[3]); + var hMaxX = Math.max(0, hodo[0], hodo[2]); + var hMaxY = Math.max(0, hodo[1], hodo[3]); + var hScaleX = hMaxX - hMinX > 0 ? ctx.canvas.width / (hMaxX - hMinX) : 1; + var hScaleY = hMaxY - hMinY > 0 ? ctx.canvas.height / (hMaxY - hMinY) : 1; + var hUnit = Math.min(hScaleX, hScaleY); + hUnit /= 2; + var hx = xoffset - hMinX * hUnit; + var hy = yoffset - hMinY * hUnit; + ctx.moveTo(hx + hodo[0] * hUnit, hy + hodo[1] * hUnit); + ctx.lineTo(hx + hodo[2] * hUnit, hy + hodo[3] * hUnit); + ctx.strokeStyle = "red"; + ctx.stroke(); + drawHodoOrigin(hx, hy, hMinX, hMinY, hMaxX, hMaxY); + } + if (draw_sequence) { + var ymin = Math.min(curve[1], curve[3], curve[5], curve[7]); + for (var i = 0; i < 8; i+= 2) { + drawLabelX(ymin, i >> 1, curve[i]); + } + var xmin = Math.min(curve[0], curve[2], curve[4], curve[6]); + for (var i = 1; i < 8; i+= 2) { + drawLabelY(xmin, i >> 1, curve[i]); + } + } + } +} + +function drawTop() { + init(tests[testIndex]); + redraw(); +} + +function redraw() { + ctx.beginPath(); + ctx.rect(0, 0, ctx.canvas.width, ctx.canvas.height); + ctx.fillStyle="white"; + ctx.fill(); + draw(tests[testIndex], testTitles[testIndex]); +} + +function doKeyPress(evt) { + var char = String.fromCharCode(evt.charCode); + switch (char) { + case '2': + draw_hodo2 ^= true; + redraw(); + break; + case 'd': + draw_deriviatives ^= true; + redraw(); + break; + case 'e': + draw_endpoints ^= true; + redraw(); + break; + case 'h': + draw_hodo ^= true; + redraw(); + break; + case 'N': + testIndex += 9; + case 'n': + if (++testIndex >= tests.length) + testIndex = 0; + drawTop(); + break; + case 'l': + logCurves(tests[testIndex]); + break; + case 'm': + draw_midpoint ^= true; + redraw(); + break; + case 'o': + draw_hodo_origin ^= true; + redraw(); + break; + case 'P': + testIndex -= 9; + case 'p': + if (--testIndex < 0) + testIndex = tests.length - 1; + drawTop(); + break; + case 's': + draw_sequence ^= true; + redraw(); + break; + case 't': + draw_tangents ^= true; + redraw(); + break; + } +} + +function calcXY() { + var e = window.event; + var tgt = e.target || e.srcElement; + var left = tgt.offsetLeft; + var top = tgt.offsetTop; + var unit = scale * ticks; + mouseX = (e.clientX - left - Math.ceil(at_x) + 1) / unit + xStart; + mouseY = (e.clientY - top - Math.ceil(at_y)) / unit + yStart; +} + +var lastX, lastY; +var activeCurve = []; +var activePt; + +function handleMouseClick() { + calcXY(); +} + +function initDown() { + var unit = scale * ticks; + var xoffset = xStart * -unit + at_x; + var yoffset = yStart * -unit + at_y; + var test = tests[testIndex]; + var bestDistance = 1000000; + activePt = -1; + for (curves in test) { + var testCurve = test[curves]; + if (testCurve.length != 8) { + continue; + } + for (var i = 0; i < 8; i += 2) { + var testX = testCurve[i]; + var testY = testCurve[i + 1]; + var dx = testX - mouseX; + var dy = testY - mouseY; + var dist = dx * dx + dy * dy; + if (dist > bestDistance) { + continue; + } + activeCurve = testCurve; + activePt = i; + bestDistance = dist; + } + } + if (activePt >= 0) { + lastX = mouseX; + lastY = mouseY; + } +} + +function handleMouseOver() { + if (!mouseDown) { + activePt = -1; + return; + } + calcXY(); + if (activePt < 0) { + initDown(); + return; + } + var unit = scale * ticks; + var deltaX = (mouseX - lastX) /* / unit */; + var deltaY = (mouseY - lastY) /*/ unit */; + lastX = mouseX; + lastY = mouseY; + activeCurve[activePt] += deltaX; + activeCurve[activePt + 1] += deltaY; + redraw(); +} + +function start() { + for (i = 0; i < testDivs.length; ++i) { + var title = testDivs[i].id.toString(); + var str = testDivs[i].firstChild.data; + parse(str, title); + } + drawTop(); + window.addEventListener('keypress', doKeyPress, true); + window.onresize = function() { + drawTop(); + } +} + +</script> +</head> + +<body onLoad="start();"> +<canvas id="canvas" width="750" height="500" + onmousedown="mouseDown = true" + onmouseup="mouseDown = false" + onmousemove="handleMouseOver()" + onclick="handleMouseClick()" + ></canvas > +</body> +</html> diff --git a/experimental/Intersection/op.htm b/experimental/Intersection/op.htm index 21c315de67..466551b388 100644 --- a/experimental/Intersection/op.htm +++ b/experimental/Intersection/op.htm @@ -3644,34 +3644,106 @@ path.addRect(4, 13, 13, 16, SkPath::kCCW_Direction); pathB.close(); </div> +<div id="cubicOp25i"> + path.setFillType(SkPath::kWinding_FillType); + path.moveTo(0,1); + path.cubicTo(2,4, 5,0, 3,2); + path.close(); + pathB.setFillType(SkPath::kWinding_FillType); + pathB.moveTo(0,5); + pathB.cubicTo(2,3, 1,0, 4,2); + pathB.close(); +</div> + +<div id="cubicOp26d"> + path.setFillType(SkPath::kWinding_FillType); + path.moveTo(0,1); + path.cubicTo(3,4, 4,0, 3,2); + path.close(); + pathB.setFillType(SkPath::kWinding_FillType); + pathB.moveTo(0,4); + pathB.cubicTo(2,3, 1,0, 4,3); + pathB.close(); +</div> + +<div id="cubicOp27d"> + path.setFillType(SkPath::kWinding_FillType); + path.moveTo(0,1); + path.cubicTo(3,6, 1,0, 5,2); + path.close(); + pathB.setFillType(SkPath::kWinding_FillType); + pathB.moveTo(0,1); + pathB.cubicTo(2,5, 1,0, 6,3); + pathB.close(); +</div> + +<div id="cubicOp28u"> + path.setFillType(SkPath::kWinding_FillType); + path.moveTo(0,1); + path.cubicTo(1,4, 6,0, 3,2); + path.close(); + pathB.setFillType(SkPath::kWinding_FillType); + pathB.moveTo(0,6); + pathB.cubicTo(2,3, 1,0, 4,1); + pathB.close(); +</div> + +<div id="cubicOp29d"> + path.setFillType(SkPath::kWinding_FillType); + path.moveTo(0,1); + path.cubicTo(2,5, 6,0, 4,2); + path.close(); + pathB.setFillType(SkPath::kWinding_FillType); + pathB.moveTo(0,6); + pathB.cubicTo(2,4, 1,0, 5,2); + pathB.close(); +</div> + +<div id="cubicOp30d"> + path.setFillType(SkPath::kWinding_FillType); + path.moveTo(0,1); + path.cubicTo(2,5, 6,0, 5,3); + path.close(); + pathB.setFillType(SkPath::kWinding_FillType); + pathB.moveTo(0,6); + pathB.cubicTo(3,5, 1,0, 5,2); + pathB.close(); +</div> + </div> <script type="text/javascript"> var testDivs = [ + cubicOp30d, + cubicOp29d, + cubicOp28u, + cubicOp27d, + cubicOp26d, + cubicOp25i, cubicOp24d, cubicOp23d, - cubicOp22d, - cubicOp21d, - cubicOp20d, - cubicOp19i, cubicOp18d, - cubicOp17d, - cubicOp16d, cubicOp15d, cubicOp14d, cubicOp13d, - cubicOp12d, cubicOp11d, - cubicOp10d, - cubicOp1i, - lineOp9d, - quadOp9d, cubicOp9d, cubicOp8d, cubicOp7d, cubicOp6d, cubicOp5d, + cubicOp10d, + cubicOp22d, + cubicOp21d, + cubicOp20d, + cubicOp19i, + cubicOp17d, + cubicOp16d, + cubicOp12d, + cubicOp1i, + lineOp9d, + quadOp9d, cubicOp4d, cubicOp3d, cubicOp2d, diff --git a/experimental/Intersection/qc.htm b/experimental/Intersection/qc.htm index 0264b3ddb6..1d9cfa589b 100644 --- a/experimental/Intersection/qc.htm +++ b/experimental/Intersection/qc.htm @@ -2031,11 +2031,49 @@ quad=(1.20573276,0.813456177 1.2679289,0.830085346 1.33333333,0.851851852) {{0.666666667,1.14814815}, {1.33333333,1.33333333}, {2.66666667,2.18518519}}, </div> +<div id="cubicSelf1"> + {{3.34,8.98}, {1.95,10.27}, {3.76,7.65}, {4.96,10.64}}, + + {{3.34,8.98}, {2.83363281,9.4265625}, {2.83796875,9.363125}}, + {{2.83796875,9.363125}, {2.84230469,9.2996875}, {3.17875,9.1725}}, + {{3.17875,9.1725}, {3.51519531,9.0453125}, {4.00515625,9.300625}}, + {{4.00515625,9.300625}, {4.49511719,9.5559375}, {4.96,10.64}}, +</div> + +<div id="quadSelf1"> + {{3.34,8.98}, {2.83363281,9.4265625}, {2.83796875,9.363125}}, + {{2.83796875,9.363125}, {2.84230469,9.2996875}, {3.17875,9.1725}}, +</div> + +<div id="cubicOp27d"> +{{0,1}, {3,6}, {1,0}, {5,2}}, +{{0,1}, {2,5}, {1,0}, {6,3}}, + + {{0,1}, {1.11687388,2.858568}, {1.5151589,3.0010603}}, + {{1.5151589,3.0010603}, {1.91344391,3.14355261}, {2.16505631,2.55782454}}, + {{2.16505631,2.55782454}, {2.40541285,2.02193091}, {2.99836023,1.68247638}}, + {{2.99836023,1.68247638}, {3.5913076,1.34302184}, {5,2}}, + + {{0,1}, {0.691228423,2.3859516}, {1.0489054,2.56156367}}, + {{1.0489054,2.56156367}, {1.40658238,2.73717574}, {1.80814127,2.41537795}}, + {{1.80814127,2.41537795}, {2.23475077,2.05922313}, {3.16529668,1.98358763}}, + {{3.16529668,1.98358763}, {4.0958426,1.90795214}, {6,3}}, +</div> + +<div id="quadOp27d"> + {{1.80814127,2.41537795}, {2.23475077,2.05922313}, {3.16529668,1.98358763}}, + {{2.16505631,2.55782454}, {2.40541285,2.02193091}, {2.99836023,1.68247638}}, +</div> + </div> <script type="text/javascript"> var testDivs = [ + quadOp27d, + cubicOp27d, + quadSelf1, + cubicSelf1, quadOp21d, cubicOp21d, cubicOp20d, @@ -2306,6 +2344,7 @@ var curveT = -1; var drawCubics = true; var drawQuads = true; var drawControlLines = true; +var drawTangents = false; var xmin, xmax, ymin, ymax; function parse(test, title) { @@ -2477,7 +2516,7 @@ function draw(test, title, scale) { ctx.lineTo(xoffset + curve[4] * unit, yoffset + curve[5] * unit); if (curve.length == 8) ctx.lineTo(xoffset + curve[6] * unit, yoffset + curve[7] * unit); - ctx.lineTo(xoffset + curve[0] * unit, yoffset + curve[1] * unit); + // ctx.lineTo(xoffset + curve[0] * unit, yoffset + curve[1] * unit); ctx.stroke(); } if (curveT >= 0 && curveT <= 1) { @@ -2518,7 +2557,7 @@ function draw(test, title, scale) { ctx.fill(); ctx.fillStyle="black"; ctx.fillText(num, 230, 18); - if (curve.length == 8) { + if (drawTangents && curve.length == 8) { var one_t = 1 - t; var a = curve[0]; var b = curve[2]; @@ -2594,6 +2633,10 @@ function doKeyPress(evt) { drawQuads ^= true; redraw(); break; + case 't': + drawTangents ^= true; + redraw(); + break; case 'x': drawCubics ^= true; drawQuads ^= true; |