Add implementation of path ops

src/pathops/SkOpContour.cpp

Index: src/pathops/SkOpContour.cpp
===================================================================
--- src/pathops/SkOpContour.cpp	(revision 0)
+++ src/pathops/SkOpContour.cpp	(revision 0)
@@ -0,0 +1,355 @@
+/*
+* Copyright 2013 Google Inc.
+*
+* Use of this source code is governed by a BSD-style license that can be
+* found in the LICENSE file.
+*/
+#include "SkIntersections.h"
+#include "SkOpContour.h"
+#include "SkPathWriter.h"
+#include "TSearch.h"
+
+void SkOpContour::addCoincident(int index, SkOpContour* other, int otherIndex,
+        const SkIntersections& ts, bool swap) {
+    SkCoincidence& coincidence = *fCoincidences.append();
+    coincidence.fContours[0] = this; // FIXME: no need to store
+    coincidence.fContours[1] = other;
+    coincidence.fSegments[0] = index;
+    coincidence.fSegments[1] = otherIndex;
+    coincidence.fTs[swap][0] = ts[0][0];
+    coincidence.fTs[swap][1] = ts[0][1];
+    coincidence.fTs[!swap][0] = ts[1][0];
+    coincidence.fTs[!swap][1] = ts[1][1];
+    coincidence.fPts[0] = ts.pt(0).asSkPoint();
+    coincidence.fPts[1] = ts.pt(1).asSkPoint();
+}
+
+SkOpSegment* SkOpContour::nonVerticalSegment(int& start, int& end) {
+    int segmentCount = fSortedSegments.count();
+    SkASSERT(segmentCount > 0);
+    for (int sortedIndex = fFirstSorted; sortedIndex < segmentCount; ++sortedIndex) {
+        SkOpSegment* testSegment = fSortedSegments[sortedIndex];
+        if (testSegment->done()) {
+            continue;
+        }
+        start = end = 0;
+        while (testSegment->nextCandidate(start, end)) {
+            if (!testSegment->isVertical(start, end)) {
+                return testSegment;
+            }
+        }
+    }
+    return NULL;
+}
+
+void SkOpContour::resolveCoincidence(SkTDArray<SkOpContour*>& contourList) {
+    int count = fCoincidences.count();
+    for (int index = 0; index < count; ++index) {
+        SkCoincidence& coincidence = fCoincidences[index];
+        SkASSERT(coincidence.fContours[0] == this);
+        int thisIndex = coincidence.fSegments[0];
+        SkOpSegment& thisOne = fSegments[thisIndex];
+        SkOpContour* otherContour = coincidence.fContours[1];
+        int otherIndex = coincidence.fSegments[1];
+        SkOpSegment& other = otherContour->fSegments[otherIndex];
+        if ((thisOne.done() || other.done()) && thisOne.complete() && other.complete()) {
+            continue;
+        }
+    #if DEBUG_CONCIDENT
+        thisOne.debugShowTs();
+        other.debugShowTs();
+    #endif
+        double startT = coincidence.fTs[0][0];
+        double endT = coincidence.fTs[0][1];
+        bool cancelers = false;
+        if (startT > endT) {
+            SkTSwap<double>(startT, endT);
+            cancelers ^= true; // FIXME: just assign true
+        }
+        SkASSERT(!approximately_negative(endT - startT));
+        double oStartT = coincidence.fTs[1][0];
+        double oEndT = coincidence.fTs[1][1];
+        if (oStartT > oEndT) {
+            SkTSwap<double>(oStartT, oEndT);
+            cancelers ^= true;
+        }
+        SkASSERT(!approximately_negative(oEndT - oStartT));
+        bool opp = fOperand ^ otherContour->fOperand;
+        if (cancelers && !opp) {
+            // make sure startT and endT have t entries
+            if (startT > 0 || oEndT < 1
+                    || thisOne.isMissing(startT) || other.isMissing(oEndT)) {
+                thisOne.addTPair(startT, other, oEndT, true, coincidence.fPts[0]);
+            }
+            if (oStartT > 0 || endT < 1
+                    || thisOne.isMissing(endT) || other.isMissing(oStartT)) {
+                other.addTPair(oStartT, thisOne, endT, true, coincidence.fPts[1]);
+            }
+            if (!thisOne.done() && !other.done()) {
+                thisOne.addTCancel(startT, endT, other, oStartT, oEndT);
+            }
+        } else {
+            if (startT > 0 || oStartT > 0
+                    || thisOne.isMissing(startT) || other.isMissing(oStartT)) {
+                thisOne.addTPair(startT, other, oStartT, true, coincidence.fPts[0]);
+            }
+            if (endT < 1 || oEndT < 1
+                    || thisOne.isMissing(endT) || other.isMissing(oEndT)) {
+                other.addTPair(oEndT, thisOne, endT, true, coincidence.fPts[1]);
+            }
+            if (!thisOne.done() && !other.done()) {
+                thisOne.addTCoincident(startT, endT, other, oStartT, oEndT);
+            }
+        }
+    #if DEBUG_CONCIDENT
+        thisOne.debugShowTs();
+        other.debugShowTs();
+    #endif
+    #if DEBUG_SHOW_WINDING
+        debugShowWindingValues(contourList);
+    #endif
+    }
+}
+
+// first pass, add missing T values
+// second pass, determine winding values of overlaps
+void SkOpContour::addCoincidentPoints() {
+    int count = fCoincidences.count();
+    for (int index = 0; index < count; ++index) {
+        SkCoincidence& coincidence = fCoincidences[index];
+        SkASSERT(coincidence.fContours[0] == this);
+        int thisIndex = coincidence.fSegments[0];
+        SkOpSegment& thisOne = fSegments[thisIndex];
+        SkOpContour* otherContour = coincidence.fContours[1];
+        int otherIndex = coincidence.fSegments[1];
+        SkOpSegment& other = otherContour->fSegments[otherIndex];
+        if ((thisOne.done() || other.done()) && thisOne.complete() && other.complete()) {
+            // OPTIMIZATION: remove from array
+            continue;
+        }
+    #if DEBUG_CONCIDENT
+        thisOne.debugShowTs();
+        other.debugShowTs();
+    #endif
+        double startT = coincidence.fTs[0][0];
+        double endT = coincidence.fTs[0][1];
+        bool cancelers;
+        if ((cancelers = startT > endT)) {
+            SkTSwap(startT, endT);
+            SkTSwap(coincidence.fPts[0], coincidence.fPts[1]);
+        }
+        SkASSERT(!approximately_negative(endT - startT));
+        double oStartT = coincidence.fTs[1][0];
+        double oEndT = coincidence.fTs[1][1];
+        if (oStartT > oEndT) {
+            SkTSwap<double>(oStartT, oEndT);
+            cancelers ^= true;
+        }
+        SkASSERT(!approximately_negative(oEndT - oStartT));
+        bool opp = fOperand ^ otherContour->fOperand;
+        if (cancelers && !opp) {
+            // make sure startT and endT have t entries
+            if (startT > 0 || oEndT < 1
+                    || thisOne.isMissing(startT) || other.isMissing(oEndT)) {
+                thisOne.addTPair(startT, other, oEndT, true, coincidence.fPts[0]);
+            }
+            if (oStartT > 0 || endT < 1
+                    || thisOne.isMissing(endT) || other.isMissing(oStartT)) {
+                other.addTPair(oStartT, thisOne, endT, true, coincidence.fPts[1]);
+            }
+        } else {
+            if (startT > 0 || oStartT > 0
+                    || thisOne.isMissing(startT) || other.isMissing(oStartT)) {
+                thisOne.addTPair(startT, other, oStartT, true, coincidence.fPts[0]);
+            }
+            if (endT < 1 || oEndT < 1
+                    || thisOne.isMissing(endT) || other.isMissing(oEndT)) {
+                other.addTPair(oEndT, thisOne, endT, true, coincidence.fPts[1]);
+            }
+        }
+    #if DEBUG_CONCIDENT
+        thisOne.debugShowTs();
+        other.debugShowTs();
+    #endif
+    }
+}
+
+void SkOpContour::calcCoincidentWinding() {
+    int count = fCoincidences.count();
+    for (int index = 0; index < count; ++index) {
+        SkCoincidence& coincidence = fCoincidences[index];
+        SkASSERT(coincidence.fContours[0] == this);
+        int thisIndex = coincidence.fSegments[0];
+        SkOpSegment& thisOne = fSegments[thisIndex];
+        if (thisOne.done()) {
+            continue;
+        }
+        SkOpContour* otherContour = coincidence.fContours[1];
+        int otherIndex = coincidence.fSegments[1];
+        SkOpSegment& other = otherContour->fSegments[otherIndex];
+        if (other.done()) {
+            continue;
+        }
+        double startT = coincidence.fTs[0][0];
+        double endT = coincidence.fTs[0][1];
+        bool cancelers;
+        if ((cancelers = startT > endT)) {
+            SkTSwap<double>(startT, endT);
+        }
+        SkASSERT(!approximately_negative(endT - startT));
+        double oStartT = coincidence.fTs[1][0];
+        double oEndT = coincidence.fTs[1][1];
+        if (oStartT > oEndT) {
+            SkTSwap<double>(oStartT, oEndT);
+            cancelers ^= true;
+        }
+        SkASSERT(!approximately_negative(oEndT - oStartT));
+        bool opp = fOperand ^ otherContour->fOperand;
+        if (cancelers && !opp) {
+            // make sure startT and endT have t entries
+            if (!thisOne.done() && !other.done()) {
+                thisOne.addTCancel(startT, endT, other, oStartT, oEndT);
+            }
+        } else {
+            if (!thisOne.done() && !other.done()) {
+                thisOne.addTCoincident(startT, endT, other, oStartT, oEndT);
+            }
+        }
+    #if DEBUG_CONCIDENT
+        thisOne.debugShowTs();
+        other.debugShowTs();
+    #endif
+    }
+}
+
+void SkOpContour::sortSegments() {
+    int segmentCount = fSegments.count();
+    fSortedSegments.setReserve(segmentCount);
+    for (int test = 0; test < segmentCount; ++test) {
+        *fSortedSegments.append() = &fSegments[test];
+    }
+    QSort<SkOpSegment>(fSortedSegments.begin(), fSortedSegments.end() - 1);
+    fFirstSorted = 0;
+}
+
+void SkOpContour::toPath(SkPathWriter& path) const {
+    int segmentCount = fSegments.count();
+    const SkPoint& pt = fSegments.front().pts()[0];
+    path.deferredMove(pt);
+    for (int test = 0; test < segmentCount; ++test) {
+        fSegments[test].addCurveTo(0, 1, path, true);
+    }
+    path.close();
+}
+
+void SkOpContour::topSortableSegment(const SkPoint& topLeft, SkPoint& bestXY, SkOpSegment*& topStart) {
+    int segmentCount = fSortedSegments.count();
+    SkASSERT(segmentCount > 0);
+    int sortedIndex = fFirstSorted;
+    fDone = true; // may be cleared below
+    for ( ; sortedIndex < segmentCount; ++sortedIndex) {
+        SkOpSegment* testSegment = fSortedSegments[sortedIndex];
+        if (testSegment->done()) {
+            if (sortedIndex == fFirstSorted) {
+                ++fFirstSorted;
+            }
+            continue;
+        }
+        fDone = false;
+        SkPoint testXY = testSegment->activeLeftTop(true, NULL);
+        if (topStart) {
+            if (testXY.fY < topLeft.fY) {
+                continue;
+            }
+            if (testXY.fY == topLeft.fY && testXY.fX < topLeft.fX) {
+                continue;
+            }
+            if (bestXY.fY < testXY.fY) {
+                continue;
+            }
+            if (bestXY.fY == testXY.fY && bestXY.fX < testXY.fX) {
+                continue;
+            }
+        }
+        topStart = testSegment;
+        bestXY = testXY;
+    }
+}
+
+SkOpSegment* SkOpContour::undoneSegment(int& start, int& end) {
+    int segmentCount = fSegments.count();
+    for (int test = 0; test < segmentCount; ++test) {
+        SkOpSegment* testSegment = &fSegments[test];
+        if (testSegment->done()) {
+            continue;
+        }
+        testSegment->undoneSpan(start, end);
+        return testSegment;
+    }
+    return NULL;
+}
+
+#if DEBUG_DUMP
+void SkOpContour::dump() {
+    int i;
+    const char className[] = "SkOpContour";
+    const int tab = 4;
+    SkDebugf("%s %p (contour=%d)\n", className, this, fID);
+    for (i = 0; i < fSegments.count(); ++i) {
+        SkDebugf("%*s.fSegments[%d]:\n", tab + sizeof(className),
+                className, i);
+        fSegments[i].dump();
+    }
+    SkDebugf("%*s.fBounds=(l:%1.9g, t:%1.9g r:%1.9g, b:%1.9g)\n",
+            tab + sizeof(className), className,
+            fBounds.fLeft, fBounds.fTop,
+            fBounds.fRight, fBounds.fBottom);
+    SkDebugf("%*s.fContainsIntercepts=%d\n", tab + sizeof(className),
+            className, fContainsIntercepts);
+    SkDebugf("%*s.fContainsCurves=%d\n", tab + sizeof(className),
+            className, fContainsCurves);
+}
+#endif
+
+#if DEBUG_SHOW_WINDING
+int SkOpContour::debugShowWindingValues(int totalSegments, int ofInterest) {
+    int count = fSegments.count();
+    int sum = 0;
+    for (int index = 0; index < count; ++index) {
+        sum += fSegments[index].debugShowWindingValues(totalSegments, ofInterest);
+    }
+//      SkDebugf("%s sum=%d\n", __FUNCTION__, sum);
+    return sum;
+}
+
+static void SkOpContour::debugShowWindingValues(SkTDArray<SkOpContour*>& contourList) {
+//     int ofInterest = 1 << 1 | 1 << 5 | 1 << 9 | 1 << 13;
+//    int ofInterest = 1 << 4 | 1 << 8 | 1 << 12 | 1 << 16;
+    int ofInterest = 1 << 5 | 1 << 8;
+    int total = 0;
+    int index;
+    for (index = 0; index < contourList.count(); ++index) {
+        total += contourList[index]->segments().count();
+    }
+    int sum = 0;
+    for (index = 0; index < contourList.count(); ++index) {
+        sum += contourList[index]->debugShowWindingValues(total, ofInterest);
+    }
+//       SkDebugf("%s total=%d\n", __FUNCTION__, sum);
+}
+#endif
+
+void SkOpContour::setBounds() {
+    int count = fSegments.count();
+    if (count == 0) {
+        SkDebugf("%s empty contour\n", __FUNCTION__);
+        SkASSERT(0);
+        // FIXME: delete empty contour?
+        return;
+    }
+    fBounds = fSegments.front().bounds();
+    for (int index = 1; index < count; ++index) {
+        fBounds.add(fSegments[index].bounds());
+    }
+}
+