cumulative pathops patch

Replace the implicit curve intersection with a geometric curve intersection. The implicit intersection proved mathematically unstable and took a long time to zero in on an answer.

Use pointers instead of indices to refer to parts of curves. Indices required awkward renumbering.

Unify t and point values so that small intervals can be eliminated in one pass.

Break cubics up front to eliminate loops and cusps.

Make the Simplify and Op code more regular and eliminate arbitrary differences.

Add a builder that takes an array of paths and operators.

Delete unused code.

BUG=skia:3588
R=reed@google.com

Review URL: https://codereview.chromium.org/1037573004

1 files changed, 56 insertions, 32 deletions

diff --git a/src/pathops/SkDCubicLineIntersection.cpp b/src/pathops/SkDCubicLineIntersection.cpp
index 696c42e835..f5fe01503b 100644
--- a/src/pathops/SkDCubicLineIntersection.cpp
+++ b/src/pathops/SkDCubicLineIntersection.cpp
@@ -93,6 +93,29 @@ public:
         fAllowNear = allow;
     }
 
+    void checkCoincident() {
+        int last = fIntersections->used() - 1;
+        for (int index = 0; index < last; ) {
+            double cubicMidT = ((*fIntersections)[0][index] + (*fIntersections)[0][index + 1]) / 2;
+            SkDPoint cubicMidPt = fCubic.ptAtT(cubicMidT);
+            double t = fLine.nearPoint(cubicMidPt, NULL);
+            if (t < 0) {
+                ++index;
+                continue;
+            }
+            if (fIntersections->isCoincident(index)) {
+                fIntersections->removeOne(index);
+                --last;
+            } else if (fIntersections->isCoincident(index + 1)) {
+                fIntersections->removeOne(index + 1);
+                --last;
+            } else {
+                fIntersections->setCoincident(index++);
+            }
+            fIntersections->setCoincident(index);
+        }
+    }
+
     // see parallel routine in line quadratic intersections
     int intersectRay(double roots[3]) {
         double adj = fLine[1].fX - fLine[0].fX;
@@ -131,32 +154,11 @@ public:
             double cubicT = rootVals[index];
             double lineT = findLineT(cubicT);
             SkDPoint pt;
-            if (pinTs(&cubicT, &lineT, &pt, kPointUninitialized)) {
-    #if ONE_OFF_DEBUG
-                SkDPoint cPt = fCubic.ptAtT(cubicT);
-                SkDebugf("%s pt=(%1.9g,%1.9g) cPt=(%1.9g,%1.9g)\n", __FUNCTION__, pt.fX, pt.fY,
-                        cPt.fX, cPt.fY);
-    #endif
-                for (int inner = 0; inner < fIntersections->used(); ++inner) {
-                    if (fIntersections->pt(inner) != pt) {
-                        continue;
-                    }
-                    double existingCubicT = (*fIntersections)[0][inner];
-                    if (cubicT == existingCubicT) {
-                        goto skipInsert;
-                    }
-                    // check if midway on cubic is also same point. If so, discard this
-                    double cubicMidT = (existingCubicT + cubicT) / 2;
-                    SkDPoint cubicMidPt = fCubic.ptAtT(cubicMidT);
-                    if (cubicMidPt.approximatelyEqual(pt)) {
-                        goto skipInsert;
-                    }
-                }
+            if (pinTs(&cubicT, &lineT, &pt, kPointUninitialized) && uniqueAnswer(cubicT, pt)) {
                 fIntersections->insert(cubicT, lineT, pt);
-        skipInsert:
-                ;
             }
         }
+        checkCoincident();
         return fIntersections->used();
     }
 
@@ -186,20 +188,43 @@ public:
         int count = HorizontalIntersect(fCubic, axisIntercept, roots);
         for (int index = 0; index < count; ++index) {
             double cubicT = roots[index];
-            SkDPoint pt;
-            pt.fX = fCubic.ptAtT(cubicT).fX;
-            pt.fY = axisIntercept;
+            SkDPoint pt = { fCubic.ptAtT(cubicT).fX,  axisIntercept };
             double lineT = (pt.fX - left) / (right - left);
-            if (pinTs(&cubicT, &lineT, &pt, kPointInitialized)) {
+            if (pinTs(&cubicT, &lineT, &pt, kPointInitialized) && uniqueAnswer(cubicT, pt)) {
                 fIntersections->insert(cubicT, lineT, pt);
             }
         }
         if (flipped) {
             fIntersections->flip();
         }
+        checkCoincident();
         return fIntersections->used();
     }
 
+        bool uniqueAnswer(double cubicT, const SkDPoint& pt) {
+            for (int inner = 0; inner < fIntersections->used(); ++inner) {
+                if (fIntersections->pt(inner) != pt) {
+                    continue;
+                }
+                double existingCubicT = (*fIntersections)[0][inner];
+                if (cubicT == existingCubicT) {
+                    return false;
+                }
+                // check if midway on cubic is also same point. If so, discard this
+                double cubicMidT = (existingCubicT + cubicT) / 2;
+                SkDPoint cubicMidPt = fCubic.ptAtT(cubicMidT);
+                if (cubicMidPt.approximatelyEqual(pt)) {
+                    return false;
+                }
+            }
+#if ONE_OFF_DEBUG
+            SkDPoint cPt = fCubic.ptAtT(cubicT);
+            SkDebugf("%s pt=(%1.9g,%1.9g) cPt=(%1.9g,%1.9g)\n", __FUNCTION__, pt.fX, pt.fY,
+                    cPt.fX, cPt.fY);
+#endif
+            return true;
+        }
+
     static int VerticalIntersect(const SkDCubic& c, double axisIntercept, double roots[3]) {
         double A, B, C, D;
         SkDCubic::Coefficients(&c[0].fX, &A, &B, &C, &D);
@@ -226,17 +251,16 @@ public:
         int count = VerticalIntersect(fCubic, axisIntercept, roots);
         for (int index = 0; index < count; ++index) {
             double cubicT = roots[index];
-            SkDPoint pt;
-            pt.fX = axisIntercept;
-            pt.fY = fCubic.ptAtT(cubicT).fY;
+            SkDPoint pt = { axisIntercept, fCubic.ptAtT(cubicT).fY };
             double lineT = (pt.fY - top) / (bottom - top);
-            if (pinTs(&cubicT, &lineT, &pt, kPointInitialized)) {
+            if (pinTs(&cubicT, &lineT, &pt, kPointInitialized) && uniqueAnswer(cubicT, pt)) {
                 fIntersections->insert(cubicT, lineT, pt);
             }
         }
         if (flipped) {
             fIntersections->flip();
         }
+        checkCoincident();
         return fIntersections->used();
     }
 
@@ -342,7 +366,7 @@ public:
         double lT = *lineT = SkPinT(*lineT);
         SkDPoint lPt = fLine.ptAtT(lT);
         SkDPoint cPt = fCubic.ptAtT(cT);
-        if (!lPt.moreRoughlyEqual(cPt)) {
+        if (!lPt.roughlyEqual(cPt)) {
             return false;
         }
         // FIXME: if points are roughly equal but not approximately equal, need to do