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, 3 insertions, 81 deletions

diff --git a/src/pathops/SkDLineIntersection.cpp b/src/pathops/SkDLineIntersection.cpp
index 8fc673f2fb..ed96b9c5d7 100644
--- a/src/pathops/SkDLineIntersection.cpp
+++ b/src/pathops/SkDLineIntersection.cpp
@@ -7,45 +7,6 @@
 #include "SkIntersections.h"
 #include "SkPathOpsLine.h"
 
-/* Determine the intersection point of two lines. This assumes the lines are not parallel,
-   and that that the lines are infinite.
-   From http://en.wikipedia.org/wiki/Line-line_intersection
- */
-SkDPoint SkIntersections::Line(const SkDLine& a, const SkDLine& b) {
-    double axLen = a[1].fX - a[0].fX;
-    double ayLen = a[1].fY - a[0].fY;
-    double bxLen = b[1].fX - b[0].fX;
-    double byLen = b[1].fY - b[0].fY;
-    double denom = byLen * axLen - ayLen * bxLen;
-    SkASSERT(denom);
-    double term1 = a[1].fX * a[0].fY - a[1].fY * a[0].fX;
-    double term2 = b[1].fX * b[0].fY - b[1].fY * b[0].fX;
-    SkDPoint p;
-    p.fX = (term1 * bxLen - axLen * term2) / denom;
-    p.fY = (term1 * byLen - ayLen * term2) / denom;
-    return p;
-}
-
-int SkIntersections::cleanUpCoincidence() {
-    do {
-        int last = fUsed - 1;
-        for (int index = 0; index < last; ++index) {
-            if (fT[0][index] == fT[0][index + 1]) {
-                removeOne(index + (int) (fT[1][index] == 0 || fT[1][index] == 1));
-                goto tryAgain;
-            }
-        }
-        for (int index = 0; index < last; ++index) {
-            if (fT[1][index] == fT[1][index + 1]) {
-                removeOne(index + (int) (fT[0][index] == 0 || fT[0][index] == 1));
-                goto tryAgain;
-            }
-        }
-        return fUsed;
-tryAgain: ;
-    } while (true);
-}
-
 void SkIntersections::cleanUpParallelLines(bool parallel) {
     while (fUsed > 2) {
         removeOne(1);
@@ -58,6 +19,9 @@ void SkIntersections::cleanUpParallelLines(bool parallel) {
             removeOne(endMatch);
         }
     }
+    if (fUsed == 2) {
+        fIsCoincident[0] = fIsCoincident[1] = 0x03;
+    }
 }
 
 void SkIntersections::computePoints(const SkDLine& line, int used) {
@@ -81,12 +45,6 @@ int SkIntersections::intersectRay(const SkDLine& a, const SkDLine& b) {
     SkDVector ab0 = a[0] - b[0];
     double numerA = ab0.fY * bLen.fX - bLen.fY * ab0.fX;
     double numerB = ab0.fY * aLen.fX - aLen.fY * ab0.fX;
-#if 0
-    if (!between(0, numerA, denom) || !between(0, numerB, denom)) {
-        fUsed = 0;
-        return 0;
-    }
-#endif
     numerA /= denom;
     numerB /= denom;
     int used;
@@ -190,7 +148,6 @@ int SkIntersections::intersect(const SkDLine& a, const SkDLine& b) {
                     }
                     SkASSERT(a[iA] != b[nearer]);
                     SkASSERT(iA == (bNearA[nearer] > 0.5));
-                    fNearlySame[iA] = true;
                     insertNear(iA, nearer, a[iA], b[nearer]);
                     aNearB[iA] = -1;
                     bNearA[nearer] = -1;
@@ -235,18 +192,6 @@ static double horizontal_intercept(const SkDLine& line, double y) {
      return SkPinT((y - line[0].fY) / (line[1].fY - line[0].fY));
 }
 
-int SkIntersections::horizontal(const SkDLine& line, double y) {
-    fMax = 2;
-    int horizontalType = horizontal_coincident(line, y);
-    if (horizontalType == 1) {
-        fT[0][0] = horizontal_intercept(line, y);
-    } else if (horizontalType == 2) {
-        fT[0][0] = 0;
-        fT[0][1] = 1;
-    }
-    return fUsed = horizontalType;
-}
-
 int SkIntersections::horizontal(const SkDLine& line, double left, double right,
                                 double y, bool flipped) {
     fMax = 3;  // clean up parallel at the end will limit the result to 2 at the most
@@ -323,18 +268,6 @@ static double vertical_intercept(const SkDLine& line, double x) {
     return SkPinT((x - line[0].fX) / (line[1].fX - line[0].fX));
 }
 
-int SkIntersections::vertical(const SkDLine& line, double x) {
-    fMax = 2;
-    int verticalType = vertical_coincident(line, x);
-    if (verticalType == 1) {
-        fT[0][0] = vertical_intercept(line, x);
-    } else if (verticalType == 2) {
-        fT[0][0] = 0;
-        fT[0][1] = 1;
-    }
-    return fUsed = verticalType;
-}
-
 int SkIntersections::vertical(const SkDLine& line, double top, double bottom,
                               double x, bool flipped) {
     fMax = 3;  // cleanup parallel lines will bring this back line
@@ -393,14 +326,3 @@ int SkIntersections::vertical(const SkDLine& line, double top, double bottom,
     return fUsed;
 }
 
-// from http://www.bryceboe.com/wordpress/wp-content/uploads/2006/10/intersect.py
-// 4 subs, 2 muls, 1 cmp
-static bool ccw(const SkDPoint& A, const SkDPoint& B, const SkDPoint& C) {
-    return (C.fY - A.fY) * (B.fX - A.fX) > (B.fY - A.fY) * (C.fX - A.fX);
-}
-
-// 16 subs, 8 muls, 6 cmps
-bool SkIntersections::Test(const SkDLine& a, const SkDLine& b) {
-    return ccw(a[0], b[0], b[1]) != ccw(a[1], b[0], b[1])
-            && ccw(a[0], a[1], b[0]) != ccw(a[0], a[1], b[1]);
-}