pathops version two

R=reed@google.com

marked 'no commit' to attempt to get trybots to run

TBR=reed@google.com

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

1 files changed, 232 insertions, 242 deletions

diff --git a/src/pathops/SkOpContour.h b/src/pathops/SkOpContour.h
index 7a1cc09247..be1f59f4bb 100644
--- a/src/pathops/SkOpContour.h
+++ b/src/pathops/SkOpContour.h
@@ -8,31 +8,16 @@
 #define SkOpContour_DEFINED
 
 #include "SkOpSegment.h"
-#include "SkTArray.h"
+#include "SkTDArray.h"
+#include "SkTSort.h"
 
-#if defined(SK_DEBUG) || !FORCE_RELEASE
-#include "SkThread.h"
-#endif
-
-class SkIntersections;
-class SkOpContour;
+class SkChunkAlloc;
 class SkPathWriter;
 
-struct SkCoincidence {
-    SkOpContour* fOther;
-    int fSegments[2];
-    double fTs[2][2];
-    SkPoint fPts[2][2];
-    int fNearly[2];
-};
-
 class SkOpContour {
 public:
     SkOpContour() {
         reset();
-#if defined(SK_DEBUG) || !FORCE_RELEASE
-        fID = sk_atomic_inc(&SkPathOpsDebug::gContourID);
-#endif
     }
 
     bool operator<(const SkOpContour& rh) const {
@@ -41,211 +26,255 @@ public:
                 : fBounds.fTop < rh.fBounds.fTop;
     }
 
-    bool addCoincident(int index, SkOpContour* other, int otherIndex,
-                       const SkIntersections& ts, bool swap);
-    void addCoincidentPoints();
+    void addCubic(SkPoint pts[4], SkChunkAlloc* allocator) {
+        appendSegment(allocator).addCubic(pts, this);
+    }
 
-    void addCross(const SkOpContour* crosser) {
-#ifdef DEBUG_CROSS
-        for (int index = 0; index < fCrosses.count(); ++index) {
-            SkASSERT(fCrosses[index] != crosser);
-        }
-#endif
-        fCrosses.push_back(crosser);
+    void addCurve(SkPath::Verb verb, const SkPoint pts[4], SkChunkAlloc* allocator);
+
+    void addLine(SkPoint pts[2], SkChunkAlloc* allocator) {
+        appendSegment(allocator).addLine(pts, this);
     }
 
-    void addCubic(const SkPoint pts[4]) {
-        fSegments.push_back().addCubic(pts, fOperand, fXor);
-        fContainsCurves = fContainsCubics = true;
+    void addQuad(SkPoint pts[3], SkChunkAlloc* allocator) {
+        appendSegment(allocator).addQuad(pts, this);
     }
 
-    int addLine(const SkPoint pts[2]) {
-        fSegments.push_back().addLine(pts, fOperand, fXor);
-        return fSegments.count();
+    void align() {
+        SkASSERT(fCount > 0);
+        SkOpSegment* segment = &fHead;
+        do {
+            segment->align();
+        } while ((segment = segment->next()));
     }
 
-    void addOtherT(int segIndex, int tIndex, double otherT, int otherIndex) {
-        fSegments[segIndex].addOtherT(tIndex, otherT, otherIndex);
+    SkOpSegment& appendSegment(SkChunkAlloc* allocator) {
+        SkOpSegment* result = fCount++
+                ? SkOpTAllocator<SkOpSegment>::Allocate(allocator) : &fHead;
+        result->setPrev(fTail);
+        if (fTail) {
+            fTail->setNext(result);
+        }
+        fTail = result;
+        return *result;
     }
 
-    bool addPartialCoincident(int index, SkOpContour* other, int otherIndex,
-                       const SkIntersections& ts, int ptIndex, bool swap);
+    SkOpContour* appendContour(SkChunkAlloc* allocator) {
+        SkOpContour* contour = SkOpTAllocator<SkOpContour>::New(allocator);
+        
+        SkOpContour* prev = this;
+        SkOpContour* next;
+        while ((next = prev->next())) {
+            prev = next;
+        }
+        prev->setNext(contour);
+        return contour;
+    }
+    
+    const SkPathOpsBounds& bounds() const {
+        return fBounds;
+    }
 
-    int addQuad(const SkPoint pts[3]) {
-        fSegments.push_back().addQuad(pts, fOperand, fXor);
-        fContainsCurves = true;
-        return fSegments.count();
+    void calcAngles(SkChunkAlloc* allocator) {
+        SkASSERT(fCount > 0);
+        SkOpSegment* segment = &fHead;
+        do {
+            segment->calcAngles(allocator);
+        } while ((segment = segment->next()));
     }
 
-    int addT(int segIndex, SkOpContour* other, int otherIndex, const SkPoint& pt, double newT) {
-        setContainsIntercepts();
-        return fSegments[segIndex].addT(&other->fSegments[otherIndex], pt, newT);
+    void complete() {
+        setBounds();
     }
 
-    int addSelfT(int segIndex, const SkPoint& pt, double newT) {
-        setContainsIntercepts();
-        return fSegments[segIndex].addSelfT(pt, newT);
+    int count() const {
+        return fCount;
     }
 
-    void align(const SkOpSegment::AlignedSpan& aligned, bool swap, SkCoincidence* coincidence);
-    void alignCoincidence(const SkOpSegment::AlignedSpan& aligned,
-            SkTArray<SkCoincidence, true>* coincidences);
+    int debugID() const {
+        return PATH_OPS_DEBUG_RELEASE(fID, -1);
+    }
 
-    void alignCoincidence(const SkOpSegment::AlignedSpan& aligned) {
-        alignCoincidence(aligned, &fCoincidences);
-        alignCoincidence(aligned, &fPartialCoincidences);
+    int debugIndent() const {
+        return PATH_OPS_DEBUG_RELEASE(fIndent, 0);
     }
 
-    void alignMultiples(SkTDArray<SkOpSegment::AlignedSpan>* aligned) {
-        int segmentCount = fSegments.count();
-        for (int sIndex = 0; sIndex < segmentCount; ++sIndex) {
-            SkOpSegment& segment = fSegments[sIndex];
-            if (segment.hasMultiples()) {
-                segment.alignMultiples(aligned);
-            }
-        }
+#if DEBUG_ACTIVE_SPANS
+    void debugShowActiveSpans() {
+        SkOpSegment* segment = &fHead;
+        do {
+            segment->debugShowActiveSpans();
+        } while ((segment = segment->next()));
     }
+#endif
 
-    void alignTPt(int segmentIndex, const SkOpContour* other, int otherIndex,
-                  bool swap, int tIndex, SkIntersections* ts, SkPoint* point) const;
+    const SkOpAngle* debugAngle(int id) const {
+        return PATH_OPS_DEBUG_RELEASE(globalState()->debugAngle(id), NULL);
+    }
 
-    const SkPathOpsBounds& bounds() const {
-        return fBounds;
+    SkOpContour* debugContour(int id) {
+        return PATH_OPS_DEBUG_RELEASE(globalState()->debugContour(id), NULL);
     }
 
-    bool calcAngles();
-    bool calcCoincidentWinding();
-    void calcPartialCoincidentWinding();
+    const SkOpPtT* debugPtT(int id) const {
+        return PATH_OPS_DEBUG_RELEASE(globalState()->debugPtT(id), NULL);
+    }
 
-    void checkDuplicates() {
-        int segmentCount = fSegments.count();
-        for (int sIndex = 0; sIndex < segmentCount; ++sIndex) {
-            SkOpSegment& segment = fSegments[sIndex];
-            if (segment.count() > 2) {
-                segment.checkDuplicates();
-            }
-        }
+    const SkOpSegment* debugSegment(int id) const {
+        return PATH_OPS_DEBUG_RELEASE(globalState()->debugSegment(id), NULL);
     }
 
-    bool checkEnds() {
-        if (!fContainsCurves) {
-            return true;
-        }
-        int segmentCount = fSegments.count();
-        for (int sIndex = 0; sIndex < segmentCount; ++sIndex) {
-            SkOpSegment* segment = &fSegments[sIndex];
-            if (segment->verb() == SkPath::kLine_Verb) {
-                continue;
-            }
-            if (segment->done()) {
-                continue;   // likely coincident, nothing to do
-            }
-            if (!segment->checkEnds()) {
-                return false;
-            }
-        }
-        return true;
+    const SkOpSpanBase* debugSpan(int id) const {
+        return PATH_OPS_DEBUG_RELEASE(globalState()->debugSpan(id), NULL);
     }
 
-    void checkMultiples() {
-        int segmentCount = fSegments.count();
-        for (int sIndex = 0; sIndex < segmentCount; ++sIndex) {
-            SkOpSegment& segment = fSegments[sIndex];
-            if (segment.count() > 2) {
-                segment.checkMultiples();
-                fMultiples |= segment.hasMultiples();
-            }
-        }
+    SkOpGlobalState* globalState() const {
+        return fState; 
     }
 
-    void checkSmall() {
-        int segmentCount = fSegments.count();
-        for (int sIndex = 0; sIndex < segmentCount; ++sIndex) {
-            SkOpSegment& segment = fSegments[sIndex];
-            // OPTIMIZATION : skip segments that are done?
-            if (segment.hasSmall()) {
-                segment.checkSmall();
-            }
-        }
+    void debugValidate() const {
+#if DEBUG_VALIDATE
+        const SkOpSegment* segment = &fHead;
+        const SkOpSegment* prior = NULL;
+        do {
+            segment->debugValidate();
+            SkASSERT(segment->prev() == prior);
+            prior = segment;
+        } while ((segment = segment->next()));
+        SkASSERT(prior == fTail);
+#endif
     }
 
-    // if same point has different T values, choose a common T
-    void checkTiny() {
-        int segmentCount = fSegments.count();
-        if (segmentCount <= 2) {
-            return;
-        }
-        for (int sIndex = 0; sIndex < segmentCount; ++sIndex) {
-            SkOpSegment& segment = fSegments[sIndex];
-            if (segment.hasTiny()) {
-                segment.checkTiny();
-            }
-        }
+    bool done() const {
+        return fDone;
     }
 
-    void complete() {
-        setBounds();
-        fContainsIntercepts = false;
+    void dump();
+    void dumpAll();
+    void dumpAngles() const;
+    void dumpPt(int ) const;
+    void dumpPts() const;
+    void dumpPtsX() const;
+    void dumpSegment(int ) const;
+    void dumpSegments(SkPathOp op) const;
+    void dumpSpan(int ) const;
+    void dumpSpans() const;
+
+    const SkPoint& end() const {
+        return fTail->pts()[SkPathOpsVerbToPoints(fTail->verb())];
     }
 
-    bool containsCubics() const {
-        return fContainsCubics;
+    SkOpSegment* first() {
+        SkASSERT(fCount > 0);
+        return &fHead;
     }
 
-    bool crosses(const SkOpContour* crosser) const {
-        for (int index = 0; index < fCrosses.count(); ++index) {
-            if (fCrosses[index] == crosser) {
-                return true;
-            }
-        }
-        return false;
+    const SkOpSegment* first() const {
+        SkASSERT(fCount > 0);
+        return &fHead;
     }
 
-    bool done() const {
-        return fDone;
+    void indentDump() {
+        PATH_OPS_DEBUG_CODE(fIndent += 2);
     }
 
-    const SkPoint& end() const {
-        const SkOpSegment& segment = fSegments.back();
-        return segment.pts()[SkPathOpsVerbToPoints(segment.verb())];
+    void init(SkOpGlobalState* globalState, bool operand, bool isXor) {
+        fState = globalState;
+        fOperand = operand;
+        fXor = isXor;
     }
 
-    void fixOtherTIndex() {
-        int segmentCount = fSegments.count();
-        for (int sIndex = 0; sIndex < segmentCount; ++sIndex) {
-            fSegments[sIndex].fixOtherTIndex();
-        }
+    bool isXor() const {
+        return fXor;
+    }
+
+    void missingCoincidence(SkOpCoincidence* coincidences, SkChunkAlloc* allocator) {
+        SkASSERT(fCount > 0);
+        SkOpSegment* segment = &fHead;
+        do {
+            if (fState->angleCoincidence()) {
+                segment->checkAngleCoin(coincidences, allocator);
+            } else {
+                segment->missingCoincidence(coincidences, allocator);
+            }
+        } while ((segment = segment->next()));
+    }
+
+    bool moveNearby() {
+        SkASSERT(fCount > 0);
+        SkOpSegment* segment = &fHead;
+        do {
+            if (!segment->moveNearby()) {
+                return false;
+            }
+        } while ((segment = segment->next()));
+        return true;
     }
 
-    bool hasMultiples() const {
-        return fMultiples;
+    SkOpContour* next() {
+        return fNext;
     }
 
-    void joinCoincidence() {
-        joinCoincidence(fCoincidences, false);
-        joinCoincidence(fPartialCoincidences, true);
+    const SkOpContour* next() const {
+        return fNext;
     }
 
-    SkOpSegment* nonVerticalSegment(int* start, int* end);
+    SkOpSegment* nonVerticalSegment(SkOpSpanBase** start, SkOpSpanBase** end);
 
     bool operand() const {
         return fOperand;
     }
 
-    void reset() {
-        fSegments.reset();
-        fBounds.set(SK_ScalarMax, SK_ScalarMax, SK_ScalarMax, SK_ScalarMax);
-        fContainsCurves = fContainsCubics = fContainsIntercepts = fDone = fMultiples = false;
+    bool oppXor() const {
+        return fOppXor;
+    }
+
+    void outdentDump() {
+        PATH_OPS_DEBUG_CODE(fIndent -= 2);
+    }
+
+    void remove(SkOpContour* contour) {
+        if (contour == this) {
+            SkASSERT(fCount == 0);
+            return;
+        }
+        SkASSERT(contour->fNext == NULL);
+        SkOpContour* prev = this;
+        SkOpContour* next;
+        while ((next = prev->next()) != contour) {
+            SkASSERT(next);
+            prev = next;
+        }
+        SkASSERT(prev);
+        prev->setNext(NULL);
     }
 
-    void resolveNearCoincidence();
+    void reset() {
+        fTail = NULL;
+        fNext = NULL;
+        fCount = 0;
+        fDone = false;
+        SkDEBUGCODE(fBounds.set(SK_ScalarMax, SK_ScalarMax, SK_ScalarMin, SK_ScalarMin));
+        SkDEBUGCODE(fFirstSorted = -1);
+        PATH_OPS_DEBUG_CODE(fIndent = 0);
+    }
+
+    void setBounds() {
+        SkASSERT(fCount > 0);
+        const SkOpSegment* segment = &fHead;
+        fBounds = segment->bounds();
+        while ((segment = segment->next())) {
+            fBounds.add(segment->bounds());
+        }
+    }
 
-    SkTArray<SkOpSegment>& segments() {
-        return fSegments;
+    void setGlobalState(SkOpGlobalState* state) {
+        fState = state;
     }
 
-    void setContainsIntercepts() {
-        fContainsIntercepts = true;
+    void setNext(SkOpContour* contour) {
+        SkASSERT(!fNext == !!contour);
+        fNext = contour;
     }
 
     void setOperand(bool isOp) {
@@ -254,107 +283,68 @@ public:
 
     void setOppXor(bool isOppXor) {
         fOppXor = isOppXor;
-        int segmentCount = fSegments.count();
-        for (int test = 0; test < segmentCount; ++test) {
-            fSegments[test].setOppXor(isOppXor);
-        }
     }
 
     void setXor(bool isXor) {
         fXor = isXor;
     }
 
-    void sortAngles();
-    void sortSegments();
-
-    const SkPoint& start() const {
-        return fSegments.front().pts()[0];
-    }
-
-    void toPath(SkPathWriter* path) const;
+    SkPath::Verb simplifyCubic(SkPoint pts[4]);
 
-    void toPartialBackward(SkPathWriter* path) const {
-        int segmentCount = fSegments.count();
-        for (int test = segmentCount - 1; test >= 0; --test) {
-            fSegments[test].addCurveTo(1, 0, path, true);
-        }
+    void sortAngles() {
+        SkASSERT(fCount > 0);
+        SkOpSegment* segment = &fHead;
+        do {
+            segment->sortAngles();
+        } while ((segment = segment->next()));
     }
 
-    void toPartialForward(SkPathWriter* path) const {
-        int segmentCount = fSegments.count();
-        for (int test = 0; test < segmentCount; ++test) {
-            fSegments[test].addCurveTo(0, 1, path, true);
-        }
+    void sortSegments() {
+        SkOpSegment* segment = &fHead;
+        do {
+            *fSortedSegments.append() = segment;
+        } while ((segment = segment->next()));
+        SkTQSort<SkOpSegment>(fSortedSegments.begin(), fSortedSegments.end() - 1);
+        fFirstSorted = 0;
     }
 
-    void topSortableSegment(const SkPoint& topLeft, SkPoint* bestXY, SkOpSegment** topStart);
-    SkOpSegment* undoneSegment(int* start, int* end);
-
-    int updateSegment(int index, const SkPoint* pts) {
-        SkOpSegment& segment = fSegments[index];
-        segment.updatePts(pts);
-        return SkPathOpsVerbToPoints(segment.verb()) + 1;
+    const SkPoint& start() const {
+        return fHead.pts()[0];
     }
 
-#if DEBUG_TEST
-    SkTArray<SkOpSegment>& debugSegments() {
-        return fSegments;
+    void toPartialBackward(SkPathWriter* path) const {
+        const SkOpSegment* segment = fTail;
+        do {
+            segment->addCurveTo(segment->tail(), segment->head(), path, true);
+        } while ((segment = segment->prev()));
     }
-#endif
 
-#if DEBUG_ACTIVE_SPANS || DEBUG_ACTIVE_SPANS_FIRST_ONLY
-    void debugShowActiveSpans() {
-        for (int index = 0; index < fSegments.count(); ++index) {
-            fSegments[index].debugShowActiveSpans();
-        }
+    void toPartialForward(SkPathWriter* path) const {
+        const SkOpSegment* segment = &fHead;
+        do {
+            segment->addCurveTo(segment->head(), segment->tail(), path, true);
+        } while ((segment = segment->next()));
     }
-#endif
-
-#if DEBUG_SHOW_WINDING
-    int debugShowWindingValues(int totalSegments, int ofInterest);
-    static void debugShowWindingValues(const SkTArray<SkOpContour*, true>& contourList);
-#endif
 
-    // available to test routines only
-    void dump() const;
-    void dumpAngles() const;
-    void dumpCoincidence(const SkCoincidence& ) const;
-    void dumpCoincidences() const;
-    void dumpPt(int ) const;
-    void dumpPts() const;
-    void dumpSpan(int ) const;
-    void dumpSpans() const;
+    void toPath(SkPathWriter* path) const;
+    void topSortableSegment(const SkPoint& topLeft, SkPoint* bestXY, SkOpSegment** topStart);
+    SkOpSegment* undoneSegment(SkOpSpanBase** startPtr, SkOpSpanBase** endPtr);
 
 private:
-    void alignPt(int index, SkPoint* point, int zeroPt) const;
-    int alignT(bool swap, int tIndex, SkIntersections* ts) const;
-    bool calcCommonCoincidentWinding(const SkCoincidence& );
-    void checkCoincidentPair(const SkCoincidence& oneCoin, int oneIdx,
-                             const SkCoincidence& twoCoin, int twoIdx, bool partial);
-    void joinCoincidence(const SkTArray<SkCoincidence, true>& , bool partial);
-    void setBounds();
-
-    SkTArray<SkOpSegment> fSegments;
-    SkTArray<SkOpSegment*, true> fSortedSegments;
-    int fFirstSorted;
-    SkTArray<SkCoincidence, true> fCoincidences;
-    SkTArray<SkCoincidence, true> fPartialCoincidences;
-    SkTArray<const SkOpContour*, true> fCrosses;
+    SkOpGlobalState* fState;
+    SkOpSegment fHead;
+    SkOpSegment* fTail;
+    SkOpContour* fNext;
+    SkTDArray<SkOpSegment*> fSortedSegments;  // set by find top segment
     SkPathOpsBounds fBounds;
-    bool fContainsIntercepts;  // FIXME: is this used by anybody?
-    bool fContainsCubics;
-    bool fContainsCurves;
-    bool fDone;
-    bool fMultiples;  // set if some segment has multiple identical intersections with other curves
+    int fCount;
+    int fFirstSorted;
+    bool fDone;  // set by find top segment
     bool fOperand;  // true for the second argument to a binary operator
-    bool fXor;
-    bool fOppXor;
-#if defined(SK_DEBUG) || !FORCE_RELEASE
-    int debugID() const { return fID; }
-    int fID;
-#else
-    int debugID() const { return -1; }
-#endif
+    bool fXor;  // set if original path had even-odd fill
+    bool fOppXor;  // set if opposite path had even-odd fill
+    PATH_OPS_DEBUG_CODE(int fID);
+    PATH_OPS_DEBUG_CODE(int fIndent);
 };
 
 #endif