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, 27 insertions, 8 deletions

diff --git a/src/pathops/SkPathOpsQuad.h b/src/pathops/SkPathOpsQuad.h
index 932c5fbe75..81638cf0bc 100644
--- a/src/pathops/SkPathOpsQuad.h
+++ b/src/pathops/SkPathOpsQuad.h
@@ -17,43 +17,61 @@ struct SkDQuadPair {
 };
 
 struct SkDQuad {
-    SkDPoint fPts[3];
+    static const int kPointCount = 3;
+    static const int kPointLast = kPointCount - 1;
+    static const int kMaxIntersections = 4;
+
+    SkDPoint fPts[kPointCount];
+
+    bool collapsed() const {
+        return fPts[0].approximatelyEqual(fPts[1]) && fPts[0].approximatelyEqual(fPts[2]);
+    }
+
+    bool controlsInside() const {
+        SkDVector v01 = fPts[0] - fPts[1];
+        SkDVector v02 = fPts[0] - fPts[2];
+        SkDVector v12 = fPts[1] - fPts[2];
+        return v02.dot(v01) > 0 && v02.dot(v12) > 0;
+    }
 
     SkDQuad flip() const {
         SkDQuad result = {{fPts[2], fPts[1], fPts[0]}};
         return result;
     }
 
-    void set(const SkPoint pts[3]) {
+    static bool IsCubic() { return false; }
+
+    void set(const SkPoint pts[kPointCount]) {
         fPts[0] = pts[0];
         fPts[1] = pts[1];
         fPts[2] = pts[2];
     }
 
-    const SkDPoint& operator[](int n) const { SkASSERT(n >= 0 && n < 3); return fPts[n]; }
-    SkDPoint& operator[](int n) { SkASSERT(n >= 0 && n < 3); return fPts[n]; }
+    const SkDPoint& operator[](int n) const { SkASSERT(n >= 0 && n < kPointCount); return fPts[n]; }
+    SkDPoint& operator[](int n) { SkASSERT(n >= 0 && n < kPointCount); return fPts[n]; }
 
     static int AddValidTs(double s[], int realRoots, double* t);
     void align(int endIndex, SkDPoint* dstPt) const;
     SkDQuadPair chopAt(double t) const;
     SkDVector dxdyAtT(double t) const;
     static int FindExtrema(double a, double b, double c, double tValue[1]);
+    bool hullIntersects(const SkDQuad& , bool* isLinear) const;
     bool isLinear(int startIndex, int endIndex) const;
     bool monotonicInY() const;
     double nearestT(const SkDPoint&) const;
-    bool pointInHull(const SkDPoint&) const;
+    void otherPts(int oddMan, const SkDPoint* endPt[2]) const;
     SkDPoint ptAtT(double t) const;
     static int RootsReal(double A, double B, double C, double t[2]);
     static int RootsValidT(const double A, const double B, const double C, double s[2]);
     static void SetABC(const double* quad, double* a, double* b, double* c);
     SkDQuad subDivide(double t1, double t2) const;
-    static SkDQuad SubDivide(const SkPoint a[3], double t1, double t2) {
+    static SkDQuad SubDivide(const SkPoint a[kPointCount], double t1, double t2) {
         SkDQuad quad;
         quad.set(a);
         return quad.subDivide(t1, t2);
     }
     SkDPoint subDivide(const SkDPoint& a, const SkDPoint& c, double t1, double t2) const;
-    static SkDPoint SubDivide(const SkPoint pts[3], const SkDPoint& a, const SkDPoint& c,
+    static SkDPoint SubDivide(const SkPoint pts[kPointCount], const SkDPoint& a, const SkDPoint& c,
                               double t1, double t2) {
         SkDQuad quad;
         quad.set(pts);
@@ -64,7 +82,8 @@ struct SkDQuad {
 
     // utilities callable by the user from the debugger when the implementation code is linked in
     void dump() const;
-    void dumpComma(const char*) const;
+    void dumpID(int id) const;
+    void dumpInner() const;
 
 private:
 //  static double Tangent(const double* quadratic, double t);  // uncalled