shape ops work in progress

cubic to quadratic experiment

git-svn-id: http://skia.googlecode.com/svn/trunk@7046 2bbb7eff-a529-9590-31e7-b0007b416f81

5 files changed, 156 insertions, 86 deletions

diff --git a/experimental/Intersection/CubicToQuadratics.cpp b/experimental/Intersection/CubicToQuadratics.cpp
index 7cea4d441c..424836c633 100644
--- a/experimental/Intersection/CubicToQuadratics.cpp
+++ b/experimental/Intersection/CubicToQuadratics.cpp
@@ -46,7 +46,7 @@ http://www.caffeineowl.com/graphics/2d/vectorial/cubic2quad01.html
 #include "CubicUtilities.h"
 #include "CurveIntersection.h"
 
-static double calcTDiv(const Cubic& cubic, double start) {
+static double calcTDiv(const Cubic& cubic, double precision, double start) {
     const double adjust = sqrt(3) / 36;
     Cubic sub;
     const Cubic* cPtr;
@@ -61,7 +61,7 @@ static double calcTDiv(const Cubic& cubic, double start) {
     double dx = c[3].x - 3 * (c[2].x - c[1].x) - c[0].x;
     double dy = c[3].y - 3 * (c[2].y - c[1].y) - c[0].y;
     double dist = sqrt(dx * dx + dy * dy);
-    double tDiv3 = FLT_EPSILON / (adjust * dist);
+    double tDiv3 = precision / (adjust * dist);
     return cube_root(tDiv3);
 }
 
@@ -72,7 +72,7 @@ static void demote(const Cubic& cubic, Quadratic& quad) {
     quad[2] = cubic[3];
 }
 
-int cubic_to_quadratics(const Cubic& cubic, SkTDArray<Quadratic>& quadratics) {
+int cubic_to_quadratics(const Cubic& cubic, double precision, SkTDArray<Quadratic>& quadratics) {
     quadratics.setCount(1); // FIXME: every place I have setCount(), I also want setReserve()
     Cubic reduced;
     int order = reduceOrder(cubic, reduced, kReduceOrder_QuadraticsAllowed);
@@ -80,10 +80,10 @@ int cubic_to_quadratics(const Cubic& cubic, SkTDArray<Quadratic>& quadratics) {
         memcpy(quadratics[0], reduced, order * sizeof(_Point));
         return order;
     }
-    double tDiv = calcTDiv(cubic, 0);
+    double tDiv = calcTDiv(cubic, precision, 0);
     if (approximately_greater_than_one(tDiv)) {
         demote(cubic, quadratics[0]);
-        return 2;
+        return 3;
     }
     if (tDiv >= 0.5) {
         CubicPair pair;
@@ -91,7 +91,7 @@ int cubic_to_quadratics(const Cubic& cubic, SkTDArray<Quadratic>& quadratics) {
         quadratics.setCount(2);
         demote(pair.first(), quadratics[0]);
         demote(pair.second(), quadratics[1]);
-        return 2;
+        return 3;
     }
     double start = 0;
     int index = -1;
@@ -99,17 +99,17 @@ int cubic_to_quadratics(const Cubic& cubic, SkTDArray<Quadratic>& quadratics) {
     // or if the control points are tangent to each other
     do {
         Cubic part;
-        sub_divide(part, start, tDiv, part);
+        sub_divide(cubic, start, tDiv, part);
         quadratics.append();
         demote(part, quadratics[++index]);
         if (tDiv == 1) {
             break;
         }
         start = tDiv;
-        tDiv = calcTDiv(cubic, start);
+        tDiv = calcTDiv(cubic, precision, start);
         if (tDiv > 1) {
             tDiv = 1;
         }
     } while (true);
-    return 2;
+    return 3;
 }
diff --git a/experimental/Intersection/CubicToQuadratics_Test.cpp b/experimental/Intersection/CubicToQuadratics_Test.cpp
index 61f6f7d11b..c4dc96a39e 100644
--- a/experimental/Intersection/CubicToQuadratics_Test.cpp
+++ b/experimental/Intersection/CubicToQuadratics_Test.cpp
@@ -4,8 +4,90 @@
 #include "QuadraticIntersection_TestData.h"
 #include "TestUtilities.h"
 
+static double calcPrecision(const Cubic& cubic) {
+    _Rect dRect;
+    dRect.setBounds(cubic);
+    double width = dRect.right - dRect.left;
+    double height = dRect.bottom - dRect.top;
+    return (width > height ? width : height) / 256;
+}
+
+static void test(const Cubic(& cubics)[], const char* name, int firstTest, size_t testCount) {
+    SkTDArray<Quadratic> quads;
+    for (size_t index = firstTest; index < testCount; ++index) {
+        const Cubic& cubic = cubics[index];
+        double precision = calcPrecision(cubic);
+        cubic_to_quadratics(cubic, precision, quads);
+        if (quads.count() != 1) {
+            printf("%s [%d] cubic to quadratics failed count=%d\n", name, (int) index,
+                    quads.count());
+        }
+    }
+}
+
+static void test(const Quadratic(& quadTests)[], const char* name, int firstTest, size_t testCount) {
+    SkTDArray<Quadratic> quads;
+    for (size_t index = firstTest; index < testCount; ++index) {
+        const Quadratic& quad = quadTests[index];
+        Cubic cubic;
+        quad_to_cubic(quad, cubic);
+        double precision = calcPrecision(cubic);
+        cubic_to_quadratics(cubic, precision, quads);
+        if (quads.count() != 1) {
+            printf("%s [%d] cubic to quadratics failed count=%d\n", name, (int) index,
+                    quads.count());
+        }
+    }
+}
+
+static void testC(const Cubic(& cubics)[], const char* name, int firstTest, size_t testCount) {
+    SkTDArray<Quadratic> quads;
+    // test if computed line end points are valid
+    for (size_t index = firstTest; index < testCount; ++index) {
+        const Cubic& cubic = cubics[index];
+        double precision = calcPrecision(cubic);
+        int order = cubic_to_quadratics(cubic, precision, quads);
+        assert(order != 4);
+        if (order < 3) {
+            continue;
+        }
+        if (!AlmostEqualUlps(cubic[0].x, quads[0][0].x)
+                || !AlmostEqualUlps(cubic[0].y, quads[0][0].y)) {
+            printf("[%d] unmatched start\n", (int) index);
+        }
+        int last = quads.count() - 1;
+        if (!AlmostEqualUlps(cubic[3].x, quads[last][2].x)
+                || !AlmostEqualUlps(cubic[3].y, quads[last][2].y)) {
+            printf("[%d] unmatched end\n", (int) index);
+        }
+    }
+}
+
+static void testC(const Cubic(& cubics)[][2], const char* name, int firstTest, size_t testCount) {
+    SkTDArray<Quadratic> quads;
+    for (size_t index = firstTest; index < testCount; ++index) {
+        for (int idx2 = 0; idx2 < 2; ++idx2) {
+            const Cubic& cubic = cubics[index][idx2];
+            double precision = calcPrecision(cubic);
+            int order = cubic_to_quadratics(cubic, precision, quads);
+            assert(order != 4);
+            if (order < 3) {
+                continue;
+            }
+            if (!AlmostEqualUlps(cubic[0].x, quads[0][0].x)
+                    || !AlmostEqualUlps(cubic[0].y, quads[0][0].y)) {
+                printf("[%d][%d] unmatched start\n", (int) index, idx2);
+            }
+            int last = quads.count() - 1;
+            if (!AlmostEqualUlps(cubic[3].x, quads[last][2].x)
+                    || !AlmostEqualUlps(cubic[3].y, quads[last][2].y)) {
+                printf("[%d][%d] unmatched end\n", (int) index, idx2);
+            }
+        }
+    }
+}
+
 void CubicToQuadratics_Test() {
-    size_t index;
     enum {
         RunAll,
         RunPointDegenerates,
@@ -18,6 +100,7 @@ void CubicToQuadratics_Test() {
         RunQuadraticLines,
         RunQuadraticModLines,
         RunComputedLines,
+        RunComputedTests,
         RunNone
     } run = RunAll;
     int firstTestIndex = 0;
@@ -35,85 +118,69 @@ void CubicToQuadratics_Test() {
     int firstQuadraticLineTest = run == RunAll ? 0 : run == RunQuadraticLines ? firstTestIndex : INT_MAX;
     int firstQuadraticModLineTest = run == RunAll ? 0 : run == RunQuadraticModLines ? firstTestIndex : INT_MAX;
     int firstComputedLinesTest = run == RunAll ? 0 : run == RunComputedLines ? firstTestIndex : INT_MAX;
-    SkTDArray<Quadratic> quads;
-    for (index = firstPointDegeneratesTest; index < pointDegenerates_count; ++index) {
-        const Cubic& cubic = pointDegenerates[index];
-        cubic_to_quadratics(cubic, quads);
-        if (quads.count() != 1) {
-            printf("[%d] pointDegenerates count=%d\n", (int) index, quads.count());
-        }
-    }
-    for (index = firstNotPointDegeneratesTest; index < notPointDegenerates_count; ++index) {
-        const Cubic& cubic = notPointDegenerates[index];
-        cubic_to_quadratics(cubic, quads);
-        if (quads.count() != 1) {
-            printf("[%d] notPointDegenerates count=%d\n", (int) index, quads.count());
-        }
-    }
-    for (index = firstLinesTest; index < lines_count; ++index) {
-        const Cubic& cubic = lines[index];
-        cubic_to_quadratics(cubic, quads);
-        if (quads.count() != 1) {
-            printf("[%d] lines count=%d\n", (int) index, quads.count());
-        }
-    }
-    for (index = firstNotLinesTest; index < notLines_count; ++index) {
-        const Cubic& cubic = notLines[index];
-        cubic_to_quadratics(cubic, quads);
-        if (quads.count() != 1) {
-            printf("[%d] notLines order=%d\n", (int) index, quads.count());
-        }
-    }
-    for (index = firstModEpsilonTest; index < modEpsilonLines_count; ++index) {
-        const Cubic& cubic = modEpsilonLines[index];
-        cubic_to_quadratics(cubic, quads);
-        if (quads.count() != 1) {
-            printf("[%d] line mod by epsilon order=%d\n", (int) index, quads.count());
-        }
-    }
-    for (index = firstLessEpsilonTest; index < lessEpsilonLines_count; ++index) {
-        const Cubic& cubic = lessEpsilonLines[index];
-        cubic_to_quadratics(cubic, quads);
-        if (quads.count() != 1) {
-            printf("[%d] line less by epsilon/2 order=%d\n", (int) index, quads.count());
-        }
-    }
-    for (index = firstNegEpsilonTest; index < negEpsilonLines_count; ++index) {
-        const Cubic& cubic = negEpsilonLines[index];
-        cubic_to_quadratics(cubic, quads);
-        if (quads.count() != 1) {
-            printf("[%d] line neg by epsilon/2 order=%d\n", (int) index, quads.count());
-        }
-    }
-    for (index = firstQuadraticLineTest; index < quadraticLines_count; ++index) {
-        const Quadratic& quad = quadraticLines[index];
-        Cubic cubic;
-        quad_to_cubic(quad, cubic);
-        cubic_to_quadratics(cubic, quads);
-        if (quads.count() != 1) {
-            printf("[%d] line quad order=%d\n", (int) index, quads.count());
-        }
+    int firstComputedCubicsTest = run == RunAll ? 0 : run == RunComputedTests ? firstTestIndex : INT_MAX;
+
+    test(pointDegenerates, "pointDegenerates", firstPointDegeneratesTest, pointDegenerates_count);
+    test(notPointDegenerates, "notPointDegenerates", firstNotPointDegeneratesTest, notPointDegenerates_count);
+    test(lines, "lines", firstLinesTest, lines_count);
+    test(notLines, "notLines", firstNotLinesTest, notLines_count);
+    test(modEpsilonLines, "modEpsilonLines", firstModEpsilonTest, modEpsilonLines_count);
+    test(lessEpsilonLines, "lessEpsilonLines", firstLessEpsilonTest, lessEpsilonLines_count);
+    test(negEpsilonLines, "negEpsilonLines", firstNegEpsilonTest, negEpsilonLines_count);
+    test(quadraticLines, "quadraticLines", firstQuadraticLineTest, quadraticLines_count);
+    test(quadraticModEpsilonLines, "quadraticModEpsilonLines", firstQuadraticModLineTest,
+            quadraticModEpsilonLines_count);
+    testC(lines, "computed lines", firstComputedLinesTest, lines_count);
+    testC(tests, "computed tests", firstComputedCubicsTest, tests_count);
+    printf("%s end\n", __FUNCTION__);
+}
+
+static Cubic locals[] = {
+ {{
+    60.776536520932126,
+    71.249307306133829
+  }, {
+    87.107894191103014, 
+    22.377669868235323
+  }, {
+    1.4974754310666936, 
+    68.069569937917208
+  }, {
+    45.261946574441133, 
+    17.536076632112298
+  }}
+};
+
+static size_t localsCount = sizeof(locals) / sizeof(locals[0]);
+
+void CubicsToQuadratics_RandTest() {
+    for (size_t x = 0; x < localsCount; ++x) {
+        const Cubic& cubic = locals[x];
+        SkTDArray<Quadratic> quads;
+        double precision = calcPrecision(cubic);
+        cubic_to_quadratics(cubic, precision, quads);
     }
-    for (index = firstQuadraticModLineTest; index < quadraticModEpsilonLines_count; ++index) {
-        const Quadratic& quad = quadraticModEpsilonLines[index];
+    srand(0);
+    const int arrayMax = 1000;
+    const int tests = 1000000;
+    int quadDist[arrayMax];
+    bzero(quadDist, sizeof(quadDist));
+    for (int x = 0; x < tests; ++x) {
         Cubic cubic;
-        quad_to_cubic(quad, cubic);
-        cubic_to_quadratics(cubic, quads);
-        if (quads.count() != 1) {
-            printf("[%d] line mod quad order=%d\n", (int) index, quads.count());
+        for (int i = 0; i < 4; ++i) {
+            cubic[i].x = (double) rand() / RAND_MAX * 100;
+            cubic[i].y = (double) rand() / RAND_MAX * 100;
         }
+        SkTDArray<Quadratic> quads;
+        double precision = calcPrecision(cubic);
+        cubic_to_quadratics(cubic, precision, quads);
+        assert(quads.count() < arrayMax);
+        quadDist[quads.count()]++;
     }
-
-    // test if computed line end points are valid
-    for (index = firstComputedLinesTest; index < lines_count; ++index) {
-        const Cubic& cubic = lines[index];
-        cubic_to_quadratics(cubic, quads);
-        if (cubic[0].x != quads[0][0].x && cubic[0].y != quads[0][0].y) {
-            printf("[%d] unmatched start\n", (int) index);
-        }
-        int last = quads.count() - 1;
-        if (cubic[3].x != quads[last][2].x && cubic[3].y != quads[last][2].y) {
-            printf("[%d] unmatched end\n", (int) index);
+    for (int x = 0; x < arrayMax; ++x) {
+        if (!quadDist[x]) {
+            continue;
         }
+        printf("%d 1.9%g%%\n", x, (double) quadDist[x] / tests * 100);
     }
 }
diff --git a/experimental/Intersection/CubicUtilities.h b/experimental/Intersection/CubicUtilities.h
index 2e345ea3ff..890ff00732 100644
--- a/experimental/Intersection/CubicUtilities.h
+++ b/experimental/Intersection/CubicUtilities.h
@@ -11,7 +11,8 @@
 #include "SkTDArray.h"
 
 double cube_root(double x);
-int cubic_to_quadratics(const Cubic& cubic, SkTDArray<Quadratic>& quadratics);
+int cubic_to_quadratics(const Cubic& cubic, double precision,
+        SkTDArray<Quadratic>& quadratics);
 void coefficients(const double* cubic, double& A, double& B, double& C, double& D);
 int cubicRoots(double A, double B, double C, double D, double t[3]);
 double derivativeAtT(const double* cubic, double t);
diff --git a/experimental/Intersection/Intersection_Tests.cpp b/experimental/Intersection/Intersection_Tests.cpp
index 67758f6216..6bad957f31 100644
--- a/experimental/Intersection/Intersection_Tests.cpp
+++ b/experimental/Intersection/Intersection_Tests.cpp
@@ -15,6 +15,7 @@ void cubecode_test(int test);
 void Intersection_Tests() {
     int testsRun = 0;
 
+    CubicsToQuadratics_RandTest();
     CubicToQuadratics_Test();
     SimplifyNew_Test();
     Simplify4x4RectsThreaded_Test(testsRun);
diff --git a/experimental/Intersection/Intersection_Tests.h b/experimental/Intersection/Intersection_Tests.h
index 682d7cdb84..7da4e097f5 100644
--- a/experimental/Intersection/Intersection_Tests.h
+++ b/experimental/Intersection/Intersection_Tests.h
@@ -16,6 +16,7 @@ void CubicCoincidence_Test();
 void CubicIntersection_Test();
 void CubicParameterization_Test();
 void CubicReduceOrder_Test();
+void CubicsToQuadratics_RandTest();
 void CubicToQuadratics_Test();
 void Inline_Tests();
 void Intersection_Tests();