aboutsummaryrefslogtreecommitdiffhomepage
diff options
context:
space:
mode:
authorGravatar caryclark@google.com <caryclark@google.com@2bbb7eff-a529-9590-31e7-b0007b416f81>2013-02-22 21:50:07 +0000
committerGravatar caryclark@google.com <caryclark@google.com@2bbb7eff-a529-9590-31e7-b0007b416f81>2013-02-22 21:50:07 +0000
commitc83c70e911a38aea03db4af8dd9841d0d77bd129 (patch)
treec957cfecc8e073f178dc13aae8a16d9bd3653e8c
parentf8d7d2731318cdf510ab68e6b3f5ec68ab22c8e2 (diff)
shape ops work in progress
git-svn-id: http://skia.googlecode.com/svn/trunk@7836 2bbb7eff-a529-9590-31e7-b0007b416f81
Diffstat
-rw-r--r--experimental/Intersection/CubicIntersection.cpp60
-rw-r--r--experimental/Intersection/CubicIntersection_Test.cpp40
-rw-r--r--experimental/Intersection/CubicSubDivide.cpp16
-rw-r--r--experimental/Intersection/CubicUtilities.h1
-rw-r--r--experimental/Intersection/CurveIntersection.h2
-rw-r--r--experimental/Intersection/DataTypes.cpp12
-rw-r--r--experimental/Intersection/DataTypes.h12
-rw-r--r--experimental/Intersection/Intersection_Tests.cpp5
-rw-r--r--experimental/Intersection/Intersection_Tests.h1
-rw-r--r--experimental/Intersection/QuadraticIntersection_Test.cpp21
-rw-r--r--experimental/Intersection/QuadraticSubDivide.cpp9
-rw-r--r--experimental/Intersection/QuadraticUtilities.h1
-rw-r--r--experimental/Intersection/QuarticRoot.cpp35
-rw-r--r--experimental/Intersection/ShapeOps.cpp6
-rw-r--r--experimental/Intersection/Simplify.cpp371
-rw-r--r--experimental/Intersection/SimplifyNew_Test.cpp473
-rw-r--r--experimental/Intersection/as.htm26
-rw-r--r--experimental/Intersection/cd.htm517
-rw-r--r--experimental/Intersection/hg.htm649
-rw-r--r--experimental/Intersection/op.htm94
-rw-r--r--experimental/Intersection/qc.htm47
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;
generated by cgit v1.2.3 (git 2.39.1) at 2024-11-27 23:47:31 +0000