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, 19 insertions, 72 deletions

diff --git a/src/pathops/SkIntersectionHelper.h b/src/pathops/SkIntersectionHelper.h
index 3569c934de..c633fd02df 100644
--- a/src/pathops/SkIntersectionHelper.h
+++ b/src/pathops/SkIntersectionHelper.h
@@ -5,6 +5,7 @@
  * found in the LICENSE file.
  */
 #include "SkOpContour.h"
+#include "SkOpSegment.h"
 #include "SkPath.h"
 
 #ifdef SK_DEBUG
@@ -21,42 +22,9 @@ public:
         kCubic_Segment = SkPath::kCubic_Verb,
     };
 
-    bool addCoincident(SkIntersectionHelper& other, const SkIntersections& ts, bool swap) {
-        return fContour->addCoincident(fIndex, other.fContour, other.fIndex, ts, swap);
-    }
-
-    // FIXME: does it make sense to write otherIndex now if we're going to
-    // fix it up later?
-    void addOtherT(int index, double otherT, int otherIndex) {
-        fContour->addOtherT(fIndex, index, otherT, otherIndex);
-    }
-
-    bool addPartialCoincident(SkIntersectionHelper& other, const SkIntersections& ts, int index,
-            bool swap) {
-        return fContour->addPartialCoincident(fIndex, other.fContour, other.fIndex, ts, index,
-                swap);
-    }
-
-    // Avoid collapsing t values that are close to the same since
-    // we walk ts to describe consecutive intersections. Since a pair of ts can
-    // be nearly equal, any problems caused by this should be taken care
-    // of later.
-    // On the edge or out of range values are negative; add 2 to get end
-    int addT(const SkIntersectionHelper& other, const SkPoint& pt, double newT) {
-        return fContour->addT(fIndex, other.fContour, other.fIndex, pt, newT);
-    }
-
-    int addSelfT(const SkPoint& pt, double newT) {
-        return fContour->addSelfT(fIndex, pt, newT);
-    }
-
     bool advance() {
-        return ++fIndex < fLast;
-    }
-
-    void alignTPt(SkIntersectionHelper& other, bool swap, int index,
-            SkIntersections* ts, SkPoint* point) {
-        fContour->alignTPt(fIndex, other.fContour, other.fIndex, swap, index, ts, point);
+        fSegment = fSegment->next();
+        return fSegment != NULL;
     }
 
     SkScalar bottom() const {
@@ -64,30 +32,15 @@ public:
     }
 
     const SkPathOpsBounds& bounds() const {
-        return fContour->segments()[fIndex].bounds();
+        return fSegment->bounds();
     }
 
-    void init(SkOpContour* contour) {
-        fContour = contour;
-        fIndex = 0;
-        fLast = contour->segments().count();
-    }
-
-    bool isAdjacent(const SkIntersectionHelper& next) {
-        return fContour == next.fContour && fIndex + 1 == next.fIndex;
+    SkOpContour* contour() const {
+        return fSegment->contour();
     }
 
-    bool isFirstLast(const SkIntersectionHelper& next) {
-        return fContour == next.fContour && fIndex == 0
-                && next.fIndex == fLast - 1;
-    }
-
-    bool isPartial(double t1, double t2, const SkDPoint& pt1, const SkDPoint& pt2) const {
-        const SkOpSegment& segment = fContour->segments()[fIndex];
-        double mid = (t1 + t2) / 2;
-        SkDPoint midPtByT = segment.dPtAtT(mid);
-        SkDPoint midPtByAvg = SkDPoint::Mid(pt1, pt2);
-        return midPtByT.approximatelyPEqual(midPtByAvg);
+    void init(SkOpContour* contour) {
+        fSegment = contour->first();
     }
 
     SkScalar left() const {
@@ -95,41 +48,40 @@ public:
     }
 
     const SkPoint* pts() const {
-        return fContour->segments()[fIndex].pts();
+        return fSegment->pts();
     }
 
     SkScalar right() const {
         return bounds().fRight;
     }
 
+    SkOpSegment* segment() const {
+        return fSegment;
+    }
+
     SegmentType segmentType() const {
-        const SkOpSegment& segment = fContour->segments()[fIndex];
-        SegmentType type = (SegmentType) segment.verb();
+        SegmentType type = (SegmentType) fSegment->verb();
         if (type != kLine_Segment) {
             return type;
         }
-        if (segment.isHorizontal()) {
+        if (fSegment->isHorizontal()) {
             return kHorizontalLine_Segment;
         }
-        if (segment.isVertical()) {
+        if (fSegment->isVertical()) {
             return kVerticalLine_Segment;
         }
         return kLine_Segment;
     }
 
     bool startAfter(const SkIntersectionHelper& after) {
-        fIndex = after.fIndex;
-        return advance();
+        fSegment = after.fSegment->next();
+        return fSegment != NULL;
     }
 
     SkScalar top() const {
         return bounds().fTop;
     }
 
-    SkPath::Verb verb() const {
-        return fContour->segments()[fIndex].verb();
-    }
-
     SkScalar x() const {
         return bounds().fLeft;
     }
@@ -147,10 +99,5 @@ public:
     }
 
 private:
-    // utility callable by the user from the debugger when the implementation code is linked in
-    void dump() const;
-
-    SkOpContour* fContour;
-    int fIndex;
-    int fLast;
+    SkOpSegment* fSegment;
 };