shape ops work in progress
mostly working on cubic/cubic intersect
git-svn-id: http://skia.googlecode.com/svn/trunk@7266 2bbb7eff-a529-9590-31e7-b0007b416f81
diff --git a/experimental/Intersection/CubicIntersection_Test.cpp b/experimental/Intersection/CubicIntersection_Test.cpp
index 256529c..7d27bf4 100644
--- a/experimental/Intersection/CubicIntersection_Test.cpp
+++ b/experimental/Intersection/CubicIntersection_Test.cpp
@@ -56,3 +56,212 @@
}
}
}
+
+static void oneOff(const Cubic& cubic1, const Cubic& cubic2) {
+ SkTDArray<Quadratic> quads1;
+ cubic_to_quadratics(cubic1, calcPrecision(cubic1), 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");
+ SkTDArray<Quadratic> quads2;
+ cubic_to_quadratics(cubic2, calcPrecision(cubic2), quads2);
+ for (int index = 0; index < quads2.count(); ++index) {
+ const Quadratic& q = quads2[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");
+ Intersections intersections2;
+ intersect2(cubic1, cubic2, intersections2);
+ for (int pt = 0; pt < intersections2.used(); ++pt) {
+ double tt1 = intersections2.fT[0][pt];
+ double tx1, ty1;
+ xy_at_t(cubic1, tt1, tx1, ty1);
+ int pt2 = intersections2.fFlip ? intersections2.used() - pt - 1 : pt;
+ double tt2 = intersections2.fT[1][pt2];
+ double tx2, ty2;
+ xy_at_t(cubic2, tt2, tx2, ty2);
+ SkDebugf("%s t1=%1.9g (%1.9g, %1.9g) (%1.9g, %1.9g) t2=%1.9g\n", __FUNCTION__,
+ tt1, tx1, ty1, tx2, ty2, tt2);
+ }
+}
+
+static const Cubic testSet[] = {
+{{67.426548091427676, 37.993772624988935}, {23.483695892376684, 90.476863174921306}, {35.597065061143162, 79.872482633158796}, {75.38634169631932, 18.244890038969412}},
+{{61.336508189019057, 82.693132843213675}, {44.639380902349664, 54.074825790745592}, {16.815615499771951, 20.049704667203923}, {41.866884958868326, 56.735503699973002}},
+
+{{67.4265481, 37.9937726}, {23.4836959, 90.4768632}, {35.5970651, 79.8724826}, {75.3863417, 18.24489}},
+{{61.3365082, 82.6931328}, {44.6393809, 54.0748258}, {16.8156155, 20.0497047}, {41.866885, 56.7355037}},
+
+{{18.1312339, 31.6473732}, {95.5711034, 63.5350219}, {92.3283165, 62.0158945}, {18.5656052, 32.1268808}},
+{{97.402018, 35.7169972}, {33.1127443, 25.8935163}, {1.13970027, 54.9424981}, {56.4860195, 60.529264}},
+};
+
+const size_t testSetCount = sizeof(testSet) / sizeof(testSet[0]);
+
+void CubicIntersection_OneOffTest() {
+ for (size_t outer = 0; outer < testSetCount - 1; ++outer) {
+ SkDebugf("%s quads1[%d]\n", __FUNCTION__, outer);
+ const Cubic& cubic1 = testSet[outer];
+ for (size_t inner = outer + 1; inner < testSetCount; ++inner) {
+ SkDebugf("%s quads2[%d]\n", __FUNCTION__, inner);
+ const Cubic& cubic2 = testSet[inner];
+ oneOff(cubic1, cubic2);
+ }
+ }
+}
+
+#define DEBUG_CRASH 1
+
+class CubicChopper {
+public:
+
+// only finds one intersection
+CubicChopper(const Cubic& c1, const Cubic& c2)
+ : cubic1(c1)
+ , cubic2(c2)
+ , depth(0) {
+}
+
+bool intersect(double minT1, double maxT1, double minT2, double maxT2) {
+ Cubic sub1, sub2;
+ // FIXME: carry last subdivide and reduceOrder result with cubic
+ sub_divide(cubic1, minT1, maxT1, sub1);
+ sub_divide(cubic2, minT2, maxT2, sub2);
+ Intersections i;
+ intersect2(sub1, sub2, i);
+ if (i.used() == 0) {
+ return false;
+ }
+ double x1, y1, x2, y2;
+ t1 = minT1 + i.fT[0][0] * (maxT1 - minT1);
+ t2 = minT2 + i.fT[1][0] * (maxT2 - minT2);
+ xy_at_t(cubic1, t1, x1, y1);
+ xy_at_t(cubic2, t2, x2, y2);
+ if (AlmostEqualUlps(x1, x2) && AlmostEqualUlps(y1, y2)) {
+ return true;
+ }
+ double half1 = (minT1 + maxT1) / 2;
+ double half2 = (minT2 + maxT2) / 2;
+ ++depth;
+ bool result;
+ if (depth & 1) {
+ result = intersect(minT1, half1, minT2, maxT2) || intersect(half1, maxT1, minT2, maxT2)
+ || intersect(minT1, maxT1, minT2, half2) || intersect(minT1, maxT1, half2, maxT2);
+ } else {
+ result = intersect(minT1, maxT1, minT2, half2) || intersect(minT1, maxT1, half2, maxT2)
+ || intersect(minT1, half1, minT2, maxT2) || intersect(half1, maxT1, minT2, maxT2);
+ }
+ --depth;
+ return result;
+}
+
+const Cubic& cubic1;
+const Cubic& cubic2;
+double t1;
+double t2;
+int depth;
+};
+
+#define TRY_OLD 0 // old way fails on test == 1
+
+void CubicIntersection_RandTest() {
+ srand(0);
+ const int tests = 1000000; // 10000000;
+ double largestFactor = DBL_MAX;
+ for (int test = 0; test < tests; ++test) {
+ Cubic cubic1, cubic2;
+ for (int i = 0; i < 4; ++i) {
+ cubic1[i].x = (double) rand() / RAND_MAX * 100;
+ cubic1[i].y = (double) rand() / RAND_MAX * 100;
+ cubic2[i].x = (double) rand() / RAND_MAX * 100;
+ cubic2[i].y = (double) rand() / RAND_MAX * 100;
+ }
+ if (test == 2513) { // the pair crosses three times, but the quadratic approximation
+ continue; // only sees one -- should be OK to ignore the other two?
+ }
+ if (test == 12932) { // this exposes a weakness when one cubic touches the other but
+ continue; // does not touch the quad approximation. Captured in qc.htm as cubic15
+ }
+ #if DEBUG_CRASH
+ char str[1024];
+ sprintf(str, "{{%1.9g, %1.9g}, {%1.9g, %1.9g}, {%1.9g, %1.9g}, {%1.9g, %1.9g}},\n"
+ "{{%1.9g, %1.9g}, {%1.9g, %1.9g}, {%1.9g, %1.9g}, {%1.9g, %1.9g}},\n",
+ cubic1[0].x, cubic1[0].y, cubic1[1].x, cubic1[1].y, cubic1[2].x, cubic1[2].y,
+ cubic1[3].x, cubic1[3].y,
+ cubic2[0].x, cubic2[0].y, cubic2[1].x, cubic2[1].y, cubic2[2].x, cubic2[2].y,
+ cubic2[3].x, cubic2[3].y);
+ #endif
+ _Rect rect1, rect2;
+ rect1.setBounds(cubic1);
+ rect2.setBounds(cubic2);
+ bool boundsIntersect = rect1.left <= rect2.right && rect2.left <= rect2.right
+ && rect1.top <= rect2.bottom && rect2.top <= rect1.bottom;
+ Intersections i1, i2;
+ #if TRY_OLD
+ bool oldIntersects = intersect(cubic1, cubic2, i1);
+ #else
+ bool oldIntersects = false;
+ #endif
+ if (test == -1) {
+ SkDebugf("ready...\n");
+ }
+ bool newIntersects = intersect2(cubic1, cubic2, i2);
+ if (!boundsIntersect && (oldIntersects || newIntersects)) {
+ SkDebugf("%s %d unexpected intersection boundsIntersect=%d oldIntersects=%d"
+ " newIntersects=%d\n%s %s\n", __FUNCTION__, test, boundsIntersect,
+ oldIntersects, newIntersects, __FUNCTION__, str);
+ assert(0);
+ }
+ if (oldIntersects && !newIntersects) {
+ SkDebugf("%s %d missing intersection oldIntersects=%d newIntersects=%d\n%s %s\n",
+ __FUNCTION__, test, oldIntersects, newIntersects, __FUNCTION__, str);
+ assert(0);
+ }
+ if (!oldIntersects && !newIntersects) {
+ continue;
+ }
+ if (i2.used() > 1) {
+ continue;
+ // just look at single intercepts for simplicity
+ }
+ Intersections self1, self2; // self-intersect checks
+ if (intersect(cubic1, self1)) {
+ continue;
+ }
+ if (intersect(cubic2, self2)) {
+ continue;
+ }
+ // binary search for range necessary to enclose real intersection
+ CubicChopper c(cubic1, cubic2);
+ bool result = c.intersect(0, 1, 0, 1);
+ if (!result) {
+ // FIXME: a failure here probably means that a core routine used by CubicChopper is failing
+ continue;
+ }
+ double delta1 = fabs(c.t1 - i2.fT[0][0]);
+ double delta2 = fabs(c.t2 - i2.fT[1][0]);
+ double calc1 = calcPrecision(cubic1);
+ double calc2 = calcPrecision(cubic2);
+ double factor1 = calc1 / delta1;
+ double factor2 = calc2 / delta2;
+ SkDebugf("%s %d calc1=%1.9g delta1=%1.9g factor1=%1.9g calc2=%1.9g delta2=%1.9g"
+ " factor2=%1.9g\n", __FUNCTION__, test,
+ calc1, delta1, factor1, calc2, delta2, factor2);
+ if (factor1 < largestFactor) {
+ SkDebugf("WE HAVE A WINNER! %1.9g\n", factor1);
+ SkDebugf("%s\n", str);
+ oneOff(cubic1, cubic2);
+ largestFactor = factor1;
+ }
+ if (factor2 < largestFactor) {
+ SkDebugf("WE HAVE A WINNER! %1.9g\n", factor2);
+ SkDebugf("%s\n", str);
+ oneOff(cubic1, cubic2);
+ largestFactor = factor2;
+ }
+ }
+}