deal more consistently with unsortable edges

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 "SkOpCoincidence.h"
 #include "SkOpContour.h"
 #include "SkOpSegment.h"
 #include "SkPathWriter.h"
@@ skipping 25 matching lines @@
     {{{{F, F}, {F, F}}, {{T, F}, {T, F}}}, {{{T, T}, {F, F}}, {{F, T}, {T, F}}}},  // mi - su
     {{{{F, F}, {F, F}}, {{F, T}, {F, T}}}, {{{F, F}, {T, T}}, {{F, T}, {T, F}}}},  // mi & su
     {{{{F, T}, {T, F}}, {{T, T}, {F, F}}}, {{{T, F}, {T, F}}, {{F, F}, {F, F}}}},  // mi | su
     {{{{F, T}, {T, F}}, {{T, F}, {F, T}}}, {{{T, F}, {F, T}}, {{F, T}, {T, F}}}},  // mi ^ su
 };
 
 #undef F
 #undef T
 
 SkOpAngle* SkOpSegment::activeAngle(SkOpSpanBase* start, SkOpSpanBase** startPtr,
-        SkOpSpanBase** endPtr, bool* done, bool* sortable) {
-    if (SkOpAngle* result = activeAngleInner(start, startPtr, endPtr, done, sortable)) {
+        SkOpSpanBase** endPtr, bool* done) {
+    if (SkOpAngle* result = activeAngleInner(start, startPtr, endPtr, done)) {
         return result;
     }
-    if (SkOpAngle* result = activeAngleOther(start, startPtr, endPtr, done, sortable)) {
+    if (SkOpAngle* result = activeAngleOther(start, startPtr, endPtr, done)) {
         return result;
     }
     return NULL;
 }
 
 SkOpAngle* SkOpSegment::activeAngleInner(SkOpSpanBase* start, SkOpSpanBase** startPtr,
-        SkOpSpanBase** endPtr, bool* done, bool* sortable) {
+        SkOpSpanBase** endPtr, bool* done) {
     SkOpSpan* upSpan = start->upCastable();
     if (upSpan) {
         if (upSpan->windValue() || upSpan->oppValue()) {
             SkOpSpanBase* next = upSpan->next();
             if (!*endPtr) {
                 *startPtr = start;
                 *endPtr = next;
             }
             if (!upSpan->done()) {
                 if (upSpan->windSum() != SK_MinS32) {
@@ skipping 20 matching lines @@
                 *done = false;
             }
         } else {
             SkASSERT(downSpan->done());
         }
     }
     return NULL;
 }
 
 SkOpAngle* SkOpSegment::activeAngleOther(SkOpSpanBase* start, SkOpSpanBase** startPtr,
-        SkOpSpanBase** endPtr, bool* done, bool* sortable) {
+        SkOpSpanBase** endPtr, bool* done) {
     SkOpPtT* oPtT = start->ptT()->next();
     SkOpSegment* other = oPtT->segment();
     SkOpSpanBase* oSpan = oPtT->span();
-    return other->activeAngleInner(oSpan, startPtr, endPtr, done, sortable);
+    return other->activeAngleInner(oSpan, startPtr, endPtr, done);
 }
 
 bool SkOpSegment::activeOp(SkOpSpanBase* start, SkOpSpanBase* end, int xorMiMask, int xorSuMask,
         SkPathOp op) {
     int sumMiWinding = this->updateWinding(end, start);
     int sumSuWinding = this->updateOppWinding(end, start);
 #if DEBUG_LIMIT_WIND_SUM
     SkASSERT(abs(sumMiWinding) <= DEBUG_LIMIT_WIND_SUM);
     SkASSERT(abs(sumSuWinding) <= DEBUG_LIMIT_WIND_SUM);
 #endif
@@ skipping 191 matching lines @@
     }
     while ((span = span->upCast()->next())) {
         if (span == &fTail) {
             break;
         }
         span->align();
     }
     if (!span->aligned()) {
         span->alignEnd(1, fPts[SkPathOpsVerbToPoints(fVerb)]);
     }
+    if (this->collapsed()) {
+        SkOpSpan* span = &fHead;
+        do {
+            span->setWindValue(0);
+            span->setOppValue(0);
+            this->markDone(span);
+        } while ((span = span->next()->upCastable()));
+    }
     debugValidate();
 }
 
 void SkOpSegment::calcAngles(SkChunkAlloc* allocator) {
     bool activePrior = !fHead.isCanceled();
     if (activePrior && !fHead.simple()) {
         addStartSpan(allocator);
     }
     SkOpSpan* prior = &fHead;
     SkOpSpanBase* spanBase = fHead.next();
@@ skipping 32 matching lines @@
              break;
         }
         span = base->upCast();
         angle = span->toAngle();
         if (angle && angle->fCheckCoincidence) {
             angle->checkNearCoincidence();
         }
     } while ((base = span->next()));
 }
 
+bool SkOpSegment::collapsed() const {
+    return fVerb == SkPath::kLine_Verb && fHead.pt() == fTail.pt();
+}
+
 void SkOpSegment::ComputeOneSum(const SkOpAngle* baseAngle, SkOpAngle* nextAngle,
         SkOpAngle::IncludeType includeType) {
     SkOpSegment* baseSegment = baseAngle->segment();
     int sumMiWinding = baseSegment->updateWindingReverse(baseAngle);
     int sumSuWinding;
     bool binary = includeType >= SkOpAngle::kBinarySingle;
     if (binary) {
         sumSuWinding = baseSegment->updateOppWindingReverse(baseAngle);
         if (baseSegment->operand()) {
             SkTSwap<int>(sumMiWinding, sumSuWinding);
@@ skipping 695 matching lines @@
           return set_last(last, endSpan);
     }
     *startPtr = foundSpan;
     *stepPtr = foundStep;
     if (minPtr) {
         *minPtr = foundMin;
     }
     return other;
 }
 
-static void clear_visited(SkOpSpan* span) {
+static void clear_visited(SkOpSpanBase* span) {
     // reset visited flag back to false
     do {
         SkOpPtT* ptT = span->ptT(), * stopPtT = ptT;
         while ((ptT = ptT->next()) != stopPtT) {
             SkOpSegment* opp = ptT->segment();
             opp->resetVisited();
         }
-    } while ((span = span->next()->upCastable()));
+    } while (!span->final() && (span = span->upCast()->next()));
 }
 
 // look for pairs of undetected coincident curves
 // assumes that segments going in have visited flag clear
 // curve/curve intersection should now do a pretty good job of finding coincident runs so 
 // this may be only be necessary for line/curve pairs -- so skip unless this is a line and the
 // the opp is not a line
 void SkOpSegment::missingCoincidence(SkOpCoincidence* coincidences, SkChunkAlloc* allocator) {
     if (this->verb() != SkPath::kLine_Verb) {
         return;
     }
+    if (this->done()) {
+        return;
+    }
     SkOpSpan* prior = NULL;
-    SkOpSpan* span = &fHead;
+    SkOpSpanBase* spanBase = &fHead;
     do {
-        SkOpPtT* ptT = span->ptT(), * spanStopPtT = ptT;
-        SkASSERT(ptT->span() == span);
+        SkOpPtT* ptT = spanBase->ptT(), * spanStopPtT = ptT;
+        SkASSERT(ptT->span() == spanBase);
         while ((ptT = ptT->next()) != spanStopPtT) {
             SkOpSegment* opp = ptT->span()->segment();
-            if (!opp->setVisited()) {
-                continue;
-            }
             if (opp->verb() == SkPath::kLine_Verb) {
                 continue;
             }
-            if (span->containsCoincidence(opp)) { // FIXME: this assumes that if the opposite
-                                                  // segment is coincident then no more coincidence
-                                                  // needs to be detected. This may not be true. 
+            if (opp->done()) {
                 continue;
             }
-            if (span->containsCoinEnd(opp)) {
+            // when opp is encounted the 1st time, continue; on 2nd encounter, look for coincidence
+            if (!opp->visited()) {
+                continue;
+            }
+            if (spanBase == &fHead) {
+                continue;
+            }
+            SkOpSpan* span = spanBase->upCastable();
+            // FIXME?: this assumes that if the opposite segment is coincident then no more
+            // coincidence needs to be detected. This may not be true.
+            if (span && span->containsCoincidence(opp)) { 
+                continue;
+            }
+            if (spanBase->containsCoinEnd(opp)) {
                 continue;
             } 
-            // if already visited and visited again, check for coin
-            if (span == &fHead) {
-                continue;
-            }
             SkOpPtT* priorPtT = NULL, * priorStopPtT;
             // find prior span containing opp segment
             SkOpSegment* priorOpp = NULL;
-            prior = span;
-            while (!priorOpp && (prior = prior->prev())) {
-                priorStopPtT = priorPtT = prior->ptT();
+            SkOpSpan* priorTest = spanBase->prev();
+            while (!priorOpp && priorTest) {
+                priorStopPtT = priorPtT = priorTest->ptT();
                 while ((priorPtT = priorPtT->next()) != priorStopPtT) {
                     SkOpSegment* segment = priorPtT->span()->segment();
                     if (segment == opp) {
+                        prior = priorTest;
                         priorOpp = opp;
                         break;
                     }
                 }
+                priorTest = priorTest->prev();
             }
             if (!priorOpp) {
                 continue;
             }
             SkOpPtT* oppStart = prior->ptT();
-            SkOpPtT* oppEnd = span->ptT();
+            SkOpPtT* oppEnd = spanBase->ptT();
             bool swapped = priorPtT->fT > ptT->fT;
             if (swapped) {
                 SkTSwap(priorPtT, ptT);
                 SkTSwap(oppStart, oppEnd);
             }
             bool flipped = oppStart->fT > oppEnd->fT;
             bool coincident;
             if (coincidences->contains(priorPtT, ptT, oppStart, oppEnd, flipped)) {
                 goto swapBack;
             }
             {
                 // average t, find mid pt
-                double midT = (prior->t() + span->t()) / 2;
+                double midT = (prior->t() + spanBase->t()) / 2;
                 SkPoint midPt = this->ptAtT(midT);
                 coincident = true;
                 // if the mid pt is not near either end pt, project perpendicular through opp seg
                 if (!SkDPoint::ApproximatelyEqual(priorPtT->fPt, midPt)
                         && !SkDPoint::ApproximatelyEqual(ptT->fPt, midPt)) {
                     coincident = false;
                     SkIntersections i;
                     SkVector dxdy = (*CurveSlopeAtT[fVerb])(this->pts(), this->weight(), midT);
                     SkDLine ray = {{{midPt.fX, midPt.fY},
                             {midPt.fX + dxdy.fY, midPt.fY - dxdy.fX}}};
                     (*CurveIntersectRay[opp->verb()])(opp->pts(), opp->weight(), ray, &i);
                     // measure distance and see if it's small enough to denote coincidence
                     for (int index = 0; index < i.used(); ++index) {
                         SkDPoint oppPt = i.pt(index);
                         if (oppPt.approximatelyEqual(midPt)) {
                             SkVector oppDxdy = (*CurveSlopeAtT[opp->verb()])(opp->pts(),
                                     opp->weight(), i[index][0]);
                             oppDxdy.normalize();
                             dxdy.normalize();
                             SkScalar flatness = SkScalarAbs(dxdy.cross(oppDxdy) / FLT_EPSILON);
                             coincident |= flatness < 5000;  // FIXME: replace with tuned value
                         }
                     }
                 }
             }
             if (coincident) {
             // mark coincidence
-                coincidences->add(priorPtT, ptT, oppStart, oppEnd, allocator);
+                if (!coincidences->extend(priorPtT, ptT, oppStart, oppEnd)) {
+                    coincidences->add(priorPtT, ptT, oppStart, oppEnd, allocator);
+                }
                 clear_visited(&fHead);
-                missingCoincidence(coincidences, allocator);
                 return;
             }
     swapBack:
             if (swapped) {
                 SkTSwap(priorPtT, ptT);
             }
         }
-    } while ((span = span->next()->upCastable()));
+    } while ((spanBase = spanBase->final() ? NULL : spanBase->upCast()->next()));
     clear_visited(&fHead);
 }
 
 // if a span has more than one intersection, merge the other segments' span as needed
 void SkOpSegment::moveMultiples() {
     debugValidate();
     SkOpSpanBase* test = &fHead;
     do {
         int addCount = test->spanAddsCount();
         SkASSERT(addCount >= 1);
@@ skipping 397 matching lines @@
 int SkOpSegment::updateOppWindingReverse(const SkOpAngle* angle) const {
     const SkOpSpanBase* startSpan = angle->start();
     const SkOpSpanBase* endSpan = angle->end();
     return updateOppWinding(startSpan, endSpan);
 }
 
 int SkOpSegment::updateWinding(SkOpSpanBase* start, SkOpSpanBase* end) {
     SkOpSpan* lesser = start->starter(end);
     int winding = lesser->windSum();
     if (winding == SK_MinS32) {
-        SkOpGlobalState* globals = this->globalState();
-        SkOpContour* contourHead = globals->contourHead();
-        int windTry = 0;
-        while (!lesser->sortableTop(contourHead) && ++windTry < SkOpGlobalState::kMaxWindingTries) {
-            ;
-        }
-        winding = lesser->windSum();
+        winding = lesser->computeWindSum();
     }
     if (winding == SK_MinS32) {
         return winding;
     }
     int spanWinding = SkOpSegment::SpanSign(start, end);
     if (winding && UseInnerWinding(winding - spanWinding, winding)
             && winding != SK_MaxS32) {
         winding -= spanWinding;
     }
     return winding;
@@ skipping 20 matching lines @@
     int absOut = abs(outerWinding);
     int absIn = abs(innerWinding);
     bool result = absOut == absIn ? outerWinding < 0 : absOut < absIn;
     return result;
 }
 
 int SkOpSegment::windSum(const SkOpAngle* angle) const {
     const SkOpSpan* minSpan = angle->start()->starter(angle->end());
     return minSpan->windSum();
 }