path ops work in progress

src/pathops/SkOpSegment.cpp

 /*
  * Copyright 2012 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 "SkOpSegment.h"
 #include "SkPathWriter.h"
 #include "SkTSort.h"
@@ skipping 399 matching lines @@
 int SkOpSegment::addT(SkOpSegment* other, const SkPoint& pt, double newT, bool isNear) {
     if (precisely_zero(newT)) {
         newT = 0;
     } else if (precisely_equal(newT, 1)) {
         newT = 1;
     }
     // FIXME: in the pathological case where there is a ton of intercepts,
     //  binary search?
     int insertedAt = -1;
     size_t tCount = fTs.count();
+    const SkPoint& firstPt = fPts[0];
+    const SkPoint& lastPt = fPts[SkPathOpsVerbToPoints(fVerb)];
     for (size_t index = 0; index < tCount; ++index) {
         // OPTIMIZATION: if there are three or more identical Ts, then
         // the fourth and following could be further insertion-sorted so
         // that all the edges are clockwise or counterclockwise.
         // This could later limit segment tests to the two adjacent
         // neighbors, although it doesn't help with determining which
         // circular direction to go in.
-        if (newT < fTs[index].fT) {
+        const SkOpSpan& span = fTs[index];
+        if (newT < span.fT) {
             insertedAt = index;
             break;
         }
+        if (newT == span.fT) {
+            if (pt == span.fPt) {
+                insertedAt = index;
+                break;
+            }
+            if ((pt == firstPt && newT == 0) || (span.fPt == lastPt && newT == 1)) {
+                insertedAt = index;
+                break;
+            }
+        }
     }
     SkOpSpan* span;
     if (insertedAt >= 0) {
         span = fTs.insert(insertedAt);
     } else {
         insertedAt = tCount;
         span = fTs.append();
     }
     span->fT = newT;
     span->fOther = other;
@@ skipping 54 matching lines @@
         ++fDoneSpans;
         --less;
     }
     int more = 1;
     while (fTs.end() - &span[more - 1] > 1 && AlmostEqualUlps(span[more].fPt, span->fPt)) {
         if (span[more - 1].fDone) {
             break;
         }
         double tEndInterval = span[more].fT - newT;
         if (precisely_negative(tEndInterval)) {
+            if ((span->fTiny = span[more].fTiny)) {
+                span->fDone = true;
+                ++fDoneSpans;
+            }
             break;
         }
         if (fVerb == SkPath::kCubic_Verb) {
             double tMid = newT - tEndInterval / 2;
             SkDPoint midEndPt = dcubic_xy_at_t(fPts, tMid);
             if (!midEndPt.approximatelyEqual(xyAtT(span))) {
                 break;
             }
         }
         span[more - 1].fSmall = true;
@@ skipping 34 matching lines @@
               ^         ^                 <--|                           <--|
            startPt    endPt        test/oTest first pos      test/oTest final pos
 */
 void SkOpSegment::addTCancel(const SkPoint& startPt, const SkPoint& endPt, SkOpSegment* other) {
     bool binary = fOperand != other->fOperand;
     int index = 0;
     while (startPt != fTs[index].fPt) {
         SkASSERT(index < fTs.count());
         ++index;
     }
+    while (index > 0 && fTs[index].fT == fTs[index - 1].fT) {
+        --index;
+    }
     int oIndex = other->fTs.count();
     while (startPt != other->fTs[--oIndex].fPt) {  // look for startPt match
         SkASSERT(oIndex > 0);
     }
-    while (startPt == other->fTs[--oIndex].fPt) {  // look for first point beyond match
+    double oStartT = other->fTs[oIndex].fT;
+    // look for first point beyond match
+    while (startPt == other->fTs[--oIndex].fPt || oStartT == other->fTs[oIndex].fT) {
         SkASSERT(oIndex > 0);
     }
     SkOpSpan* test = &fTs[index];
     SkOpSpan* oTest = &other->fTs[oIndex];
     SkSTArray<kOutsideTrackedTCount, SkPoint, true> outsidePts;
     SkSTArray<kOutsideTrackedTCount, SkPoint, true> oOutsidePts;
     do {
         SkASSERT(test->fT < 1);
         SkASSERT(oTest->fT < 1);
         bool decrement = test->fWindValue && oTest->fWindValue;
         bool track = test->fWindValue || oTest->fWindValue;
         bool bigger = test->fWindValue >= oTest->fWindValue;
         const SkPoint& testPt = test->fPt;
+        double testT = test->fT;
         const SkPoint& oTestPt = oTest->fPt;
+        double oTestT = oTest->fT;
         do {
             if (decrement) {
                 if (binary && bigger) {
                     test->fOppValue--;
                 } else {
                     decrementSpan(test);
                 }
             } else if (track) {
                 TrackOutsidePair(&outsidePts, testPt, oTestPt);
             }
             SkASSERT(index < fTs.count() - 1);
             test = &fTs[++index];
-        } while (testPt == test->fPt);
+        } while (testPt == test->fPt || testT == test->fT);
         SkDEBUGCODE(int originalWindValue = oTest->fWindValue);
         do {
             SkASSERT(oTest->fT < 1);
             SkASSERT(originalWindValue == oTest->fWindValue);
             if (decrement) {
                 if (binary && !bigger) {
                     oTest->fOppValue--;
                 } else {
                     other->decrementSpan(oTest);
                 }
             } else if (track) {
                 TrackOutsidePair(&oOutsidePts, oTestPt, testPt);
             }
             if (!oIndex) {
                 break;
             }
             oTest = &other->fTs[--oIndex];
-        } while (oTestPt == oTest->fPt);
-        SkASSERT(endPt != test->fPt || oTestPt == endPt);
-    } while (endPt != test->fPt);
+        } while (oTestPt == oTest->fPt || oTestT == oTest->fT);
+    } while (endPt != test->fPt && test->fT < 1);
     // FIXME: determine if canceled edges need outside ts added
     int outCount = outsidePts.count();
     if (!done() && outCount) {
         addCancelOutsides(outsidePts[0], outsidePts[1], other);
         if (outCount > 2) {
             addCancelOutsides(outsidePts[outCount - 2], outsidePts[outCount - 1], other);
         }
     }
     if (!other->done() && oOutsidePts.count()) {
         other->addCancelOutsides(oOutsidePts[0], oOutsidePts[1], this);
@@ skipping 17 matching lines @@
         SkTSwap<int>(oWindValue, oOppValue);
     }
     SkOpSpan* const test = &fTs[index];
     SkOpSpan* end = test;
     const SkPoint& oStartPt = oTest.fPt;
     do {
         if (bumpSpan(end, oWindValue, oOppValue)) {
             TrackOutside(outsideTs, oStartPt);
         }
         end = &fTs[++index];
-    } while (end->fPt == test->fPt);
+    } while ((end->fPt == test->fPt || end->fT == test->fT) && end->fT < 1);
     *indexPtr = index;
 }
 
 bool SkOpSegment::bumpCoincident(SkOpSpan* test, bool bigger, bool binary) {
     if (bigger) {
         if (binary) {
             if (fOppXor) {
                 test->fOppValue ^= 1;
             } else {
                 test->fOppValue++;
@@ skipping 19 matching lines @@
 // may not have the same intermediate points. Compute the corresponding
 // intermediate T values (using this as the master, other as the follower)
 // and walk other conditionally -- hoping that it catches up in the end
 void SkOpSegment::bumpCoincidentOther(const SkOpSpan& test, int* oIndexPtr,
         SkTArray<SkPoint, true>* oOutsidePts) {
     int oIndex = *oIndexPtr;
     SkOpSpan* const oTest = &fTs[oIndex];
     SkOpSpan* oEnd = oTest;
     const SkPoint& startPt = test.fPt;
     const SkPoint& oStartPt = oTest->fPt;
-    if (oStartPt == oEnd->fPt) {
+    double oStartT = oTest->fT;
+    if (oStartPt == oEnd->fPt || oStartT == oEnd->fT) {
         TrackOutside(oOutsidePts, startPt);
     }
-    while (oStartPt == oEnd->fPt) {
+    while (oStartPt == oEnd->fPt || oStartT == oEnd->fT) {
         zeroSpan(oEnd);
         oEnd = &fTs[++oIndex];
     }
     *oIndexPtr = oIndex;
 }
 
 // FIXME: need to test this case:
 // contourA has two segments that are coincident
 // contourB has two segments that are coincident in the same place
 // each ends up with +2/0 pairs for winding count
 // since logic below doesn't transfer count (only increments/decrements) can this be
 // resolved to +4/0 ?
 
 // set spans from start to end to increment the greater by one and decrement
 // the lesser
-void SkOpSegment::addTCoincident(const SkPoint& startPt, const SkPoint& endPt,
+void SkOpSegment::addTCoincident(const SkPoint& startPt, const SkPoint& endPt, double endT,
         SkOpSegment* other) {
     bool binary = fOperand != other->fOperand;
     int index = 0;
     while (startPt != fTs[index].fPt) {
         SkASSERT(index < fTs.count());
         ++index;
     }
+    double startT = fTs[index].fT;
+    while (index > 0 && fTs[index - 1].fT == startT) {
+        --index;
+    }
     int oIndex = 0;
     while (startPt != other->fTs[oIndex].fPt) {
         SkASSERT(oIndex < other->fTs.count());
         ++oIndex;
     }
+    double oStartT = other->fTs[oIndex].fT;
+    while (oIndex > 0 && other->fTs[oIndex - 1].fT == oStartT) {
+        --oIndex;
+    }
     SkSTArray<kOutsideTrackedTCount, SkPoint, true> outsidePts;
     SkSTArray<kOutsideTrackedTCount, SkPoint, true> oOutsidePts;
     SkOpSpan* test = &fTs[index];
     const SkPoint* testPt = &test->fPt;
+    double testT = test->fT;
     SkOpSpan* oTest = &other->fTs[oIndex];
     const SkPoint* oTestPt = &oTest->fPt;
     SkASSERT(AlmostEqualUlps(*testPt, *oTestPt));
     do {
         SkASSERT(test->fT < 1);
         SkASSERT(oTest->fT < 1);
 #if 0
         if (test->fDone || oTest->fDone) {
 #else  // consolidate the winding count even if done
         if ((test->fWindValue == 0 && test->fOppValue == 0)
@@ skipping 19 matching lines @@
             if (!binary || test->fWindValue + oTest->fOppValue >= 0) {
                 bumpCoincidentThis(*oTest, binary, &index, &outsidePts);
                 other->bumpCoincidentOther(*test, &oIndex, &oOutsidePts);
             } else {
                 other->bumpCoincidentThis(*test, binary, &oIndex, &oOutsidePts);
                 bumpCoincidentOther(*oTest, &index, &outsidePts);
             }
         }
         test = &fTs[index];
         testPt = &test->fPt;
-        if (endPt == *testPt) {
+        testT = test->fT;
+        if (endPt == *testPt || endT == testT) {
             break;
         }
         oTest = &other->fTs[oIndex];
         oTestPt = &oTest->fPt;
         SkASSERT(AlmostEqualUlps(*testPt, *oTestPt));
     } while (endPt != *oTestPt);
+    if (endPt != *testPt && endT != testT) {  // in rare cases, one may have ended before the other
+        int lastWind = test[-1].fWindValue;
+        int lastOpp = test[-1].fOppValue;
+        bool zero = lastWind == 0 && lastOpp == 0;
+        do {
+            if (test->fWindValue || test->fOppValue) {
+                test->fWindValue = lastWind;
+                test->fOppValue = lastOpp;
+                if (zero) {
+                    test->fDone = true;
+                    ++fDoneSpans;
+                }
+            }
+            test = &fTs[++index];
+            testPt = &test->fPt;
+        } while (endPt != *testPt);
+   }
     int outCount = outsidePts.count();
     if (!done() && outCount) {
         addCoinOutsides(outsidePts[0], endPt, other);
     }
     if (!other->done() && oOutsidePts.count()) {
         other->addCoinOutsides(oOutsidePts[0], endPt, this);
     }
 }
 
 // FIXME: this doesn't prevent the same span from being added twice
@@ skipping 538 matching lines @@
         if (!span->fOppValue && !span->fDone) {
             span->fDone = true;
             ++fDoneSpans;
             return true;
         }
     }
     return false;
 }
 
 bool SkOpSegment::bumpSpan(SkOpSpan* span, int windDelta, int oppDelta) {
-    SkASSERT(!span->fDone || span->fTiny);
+    SkASSERT(!span->fDone || span->fTiny || span->fSmall);
     span->fWindValue += windDelta;
     SkASSERT(span->fWindValue >= 0);
     span->fOppValue += oppDelta;
     SkASSERT(span->fOppValue >= 0);
     if (fXor) {
         span->fWindValue &= 1;
     }
     if (fOppXor) {
         span->fOppValue &= 1;
     }
@@ skipping 38 matching lines @@
             ++tLast;
         }
         while (++tLast < count && t == fTs[tLast].fT)
             ;
         for (int peekIndex = peekStart; peekIndex <= peekLast; ++peekIndex) {
             if (peekIndex == span.fOtherIndex) {  // skip the other span pointed to by this span
                 continue;
             }
             const SkOpSpan& peekSpan = other->fTs[peekIndex];
             SkOpSegment* match = peekSpan.fOther;
+            if (match->done()) {
+                continue;  // if the edge has already been eaten (likely coincidence), ignore it
+            }
             const double matchT = peekSpan.fOtherT;
             // see if any of the spans match the other spans
             for (int tIndex = tStart + 1; tIndex < tLast; ++tIndex) {
                 const SkOpSpan& tSpan = fTs[tIndex];
                 if (tSpan.fOther == match) {
                     if (tSpan.fOtherT == matchT) {
-                        goto nextPeeker;
+                        goto nextPeekIndex;
                     }
                     double midT = (tSpan.fOtherT + matchT) / 2;
                     if (match->betweenPoints(midT, tSpan.fPt, peekSpan.fPt)) {
-                        goto nextPeeker;
+                        goto nextPeekIndex;
                     }
                 }
             }
             if (missingSpans.count() > 0) {
                 const MissingSpan& lastMissing = missingSpans.back();
                 if (lastMissing.fCommand == MissingSpan::kAddMissing
                         && lastMissing.fT == t
                         && lastMissing.fOther == match
                         && lastMissing.fOtherT == matchT) {
                     SkASSERT(lastMissing.fPt == peekSpan.fPt);
                     continue;
                 }
             }
 #if DEBUG_CHECK_ENDS
             SkDebugf("%s id=%d missing t=%1.9g other=%d otherT=%1.9g pt=(%1.9g,%1.9g)\n",
                     __FUNCTION__, fID, t, match->fID, matchT, peekSpan.fPt.fX, peekSpan.fPt.fY);
 #endif
             // this segment is missing a entry that the other contains
             // remember so we can add the missing one and recompute the indices
-            MissingSpan& missing = missingSpans.push_back();
-            SkDEBUGCODE(sk_bzero(&missing, sizeof(missing)));
-            missing.fCommand = MissingSpan::kAddMissing;
-            missing.fT = t;
-            missing.fOther = match;
-            missing.fOtherT = matchT;
-            missing.fPt = peekSpan.fPt;
+            {
+                MissingSpan& missing = missingSpans.push_back();
+                SkDEBUGCODE(sk_bzero(&missing, sizeof(missing)));
+                missing.fCommand = MissingSpan::kAddMissing;
+                missing.fT = t;
+                missing.fOther = match;
+                missing.fOtherT = matchT;
+                missing.fPt = peekSpan.fPt;
+            }
+            break;
+nextPeekIndex:
+            ;
         }
-nextPeeker:
-        ;
     }
     if (missingSpans.count() == 0) {
+        debugValidate();
         return;
     }
     // if one end is near the other point, look for a coincident span
     for (int index = 0; index < count; ++index) {
         const SkOpSpan& span = fTs[index];
         if (span.fT > 0) {
             break;
         }
         const SkOpSpan& otherSpan = span.fOther->span(span.fOtherIndex);
         if (span.fNear) {
@@ skipping 244 matching lines @@
         }
         return other;
     }
     // more than one viable candidate -- measure angles to find best
     SkSTArray<SkOpAngle::kStackBasedCount, SkOpAngle, true> angles;
     SkASSERT(startIndex - endIndex != 0);
     SkASSERT((startIndex - endIndex < 0) ^ (step < 0));
     SkSTArray<SkOpAngle::kStackBasedCount, SkOpAngle*, true> sorted;
     int calcWinding = computeSum(startIndex, end, SkOpAngle::kBinaryOpp, &angles, &sorted);
     bool sortable = calcWinding != SK_NaN32;
+    if (sortable && sorted.count() == 0) {
+        // if no edge has a computed winding sum, we can go no further
+        *unsortable = true;
+        return NULL;
+    }
     int angleCount = angles.count();
     int firstIndex = findStartingEdge(sorted, startIndex, end);
     SkASSERT(!sortable || firstIndex >= 0);
 #if DEBUG_SORT
     debugShowSort(__FUNCTION__, sorted, firstIndex, sortable);
 #endif
     if (!sortable) {
         *unsortable = true;
         return NULL;
     }
@@ skipping 494 matching lines @@
     int oppWindVal = oppValue(SkMin32(start, end));
     if (!oppWind) {
         oppWind = dx < 0 ? oppWindVal : -oppWindVal;
     } else if (hitOppDx * dx >= 0) {
         int oppSideWind = oppWind + (dx < 0 ? oppWindVal : -oppWindVal);
         if (abs(oppWind) < abs(oppSideWind)) {
             oppWind = oppSideWind;
         }
     }
     (void) markAndChaseWinding(start, end, winding, oppWind);
+    // OPTIMIZATION: the reverse mark and chase could skip the first marking
+    (void) markAndChaseWinding(end, start, winding, oppWind);
 }
 
 // OPTIMIZE: successive calls could start were the last leaves off
 // or calls could specialize to walk forwards or backwards
-bool SkOpSegment::isMissing(double startT) const {
+bool SkOpSegment::isMissing(double startT, const SkPoint& pt) const {
     size_t tCount = fTs.count();
     for (size_t index = 0; index < tCount; ++index) {
-        if (approximately_zero(startT - fTs[index].fT)) {
+        const SkOpSpan& span = fTs[index];
+        if (approximately_zero(startT - span.fT) && pt == span.fPt) {
             return false;
         }
     }
     return true;
 }
 
 bool SkOpSegment::isSimple(int end) const {
     int count = fTs.count();
     if (count == 2) {
         return true;
@@ skipping 120 matching lines @@
         maxWinding = sumWinding;
     }
     SkOpSpan* last;
     if (activeAngle) {
         last = markAndChaseWinding(angle, maxWinding);
     } else {
         last = markAndChaseDoneUnary(angle, maxWinding);
     }
 #if DEBUG_WINDING
     if (last) {
-        SkDebugf("%s last id=%d windSum=%d small=%d\n", __FUNCTION__,
-                last->fOther->fTs[last->fOtherIndex].fOther->debugID(), last->fWindSum,
-                last->fSmall);
+        SkDebugf("%s last id=%d windSum=", __FUNCTION__,
+                last->fOther->fTs[last->fOtherIndex].fOther->debugID());
+        SkPathOpsDebug::WindingPrintf(last->fWindSum);
+        SkDebugf(" small=%d\n", last->fSmall);
     }
 #endif
     return last;
 }
 
 SkOpSpan* SkOpSegment::markAngle(int maxWinding, int sumWinding, int oppMaxWinding,
                                  int oppSumWinding, bool activeAngle, const SkOpAngle* angle) {
     SkASSERT(angle->segment() == this);
     if (UseInnerWinding(maxWinding, sumWinding)) {
         maxWinding = sumWinding;
     }
     if (oppMaxWinding != oppSumWinding && UseInnerWinding(oppMaxWinding, oppSumWinding)) {
         oppMaxWinding = oppSumWinding;
     }
     SkOpSpan* last;
     if (activeAngle) {
         last = markAndChaseWinding(angle, maxWinding, oppMaxWinding);
     } else {
         last = markAndChaseDoneBinary(angle, maxWinding, oppMaxWinding);
     }
 #if DEBUG_WINDING
     if (last) {
-        SkDebugf("%s last id=%d windSum=%d small=%d\n", __FUNCTION__,
-                last->fOther->fTs[last->fOtherIndex].fOther->debugID(), last->fWindSum,
-                last->fSmall);
+        SkDebugf("%s last id=%d windSum=", __FUNCTION__,
+                last->fOther->fTs[last->fOtherIndex].fOther->debugID());
+        SkPathOpsDebug::WindingPrintf(last->fWindSum);
+        SkDebugf(" small=%d\n", last->fSmall);
     }
 #endif
     return last;
 }
 
 // FIXME: this should also mark spans with equal (x,y)
 // This may be called when the segment is already marked done. While this
 // wastes time, it shouldn't do any more than spin through the T spans.
 // OPTIMIZATION: abort on first done found (assuming that this code is
 // always called to mark segments done).
@@ skipping 91 matching lines @@
 #endif
     SkASSERT(span.fWindSum == SK_MinS32 || span.fWindSum == winding);
     SkASSERT(abs(winding) <= SkPathOpsDebug::gMaxWindSum);
     span.fWindSum = winding;
     return &span;
 }
 
 SkOpSpan* SkOpSegment::markOneWinding(const char* funName, int tIndex, int winding,
                                       int oppWinding) {
     SkOpSpan& span = fTs[tIndex];
-    if (span.fDone) {
+    if (span.fDone && !span.fSmall) {
         return NULL;
     }
 #if DEBUG_MARK_DONE
     debugShowNewWinding(funName, span, winding, oppWinding);
 #endif
     SkASSERT(span.fWindSum == SK_MinS32 || span.fWindSum == winding);
     SkASSERT(abs(winding) <= SkPathOpsDebug::gMaxWindSum);
     span.fWindSum = winding;
     SkASSERT(span.fOppSum == SK_MinS32 || span.fOppSum == oppWinding);
     SkASSERT(abs(oppWinding) <= SkPathOpsDebug::gMaxWindSum);
@@ skipping 622 matching lines @@
         }
     }
     SkASSERT(0);
     return 0;
 }
 
 void SkOpSegment::zeroSpan(SkOpSpan* span) {
     SkASSERT(span->fWindValue > 0 || span->fOppValue != 0);
     span->fWindValue = 0;
     span->fOppValue = 0;
+    if (span->fTiny || span->fSmall) {
+        return;
+    }
     SkASSERT(!span->fDone);
     span->fDone = true;
     ++fDoneSpans;
 }
 
 #if DEBUG_SWAP_TOP
 bool SkOpSegment::controlsContainedByEnds(int tStart, int tEnd) const {
     if (fVerb != SkPath::kCubic_Verb) {
         return false;
     }
     SkDCubic dst = SkDCubic::SubDivide(fPts, fTs[tStart].fT, fTs[tEnd].fT);
     return dst.controlsContainedByEnds();
 }
 #endif
 
 #if DEBUG_CONCIDENT
 // SkASSERT if pair has not already been added
 void SkOpSegment::debugAddTPair(double t, const SkOpSegment& other, double otherT) const {
     for (int i = 0; i < fTs.count(); ++i) {
         if (fTs[i].fT == t && fTs[i].fOther == &other && fTs[i].fOtherT == otherT) {
             return;
         }
     }
     SkASSERT(0);
 }
 #endif
 
 #if DEBUG_CONCIDENT
-void SkOpSegment::debugShowTs() const {
-    SkDebugf("%s id=%d", __FUNCTION__, fID);
+void SkOpSegment::debugShowTs(const char* prefix) const {
+    SkDebugf("%s %s id=%d", __FUNCTION__, prefix, fID);
     int lastWind = -1;
     int lastOpp = -1;
     double lastT = -1;
     int i;
     for (i = 0; i < fTs.count(); ++i) {
         bool change = lastT != fTs[i].fT || lastWind != fTs[i].fWindValue
                 || lastOpp != fTs[i].fOppValue;
         if (change && lastWind >= 0) {
             SkDebugf(" t=%1.3g %1.9g,%1.9g w=%d o=%d]",
                     lastT, xyAtT(i - 1).fX, xyAtT(i - 1).fY, lastWind, lastOpp);
@@ skipping 333 matching lines @@
 
 void SkOpSegment::dumpSpans() const {
     int count = this->count();
     for (int index = 0; index < count; ++index) {
         const SkOpSpan& span = this->span(index);
         SkDebugf("[%d] ", index);
         span.dump();
     }
 }
 #endif