path ops -- fix skp bugs

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 432 matching lines @@
     SkOpSpan* span;
     if (insertedAt >= 0) {
         span = fTs.insert(insertedAt);
     } else {
         insertedAt = tCount;
         span = fTs.append();
     }
     span->fT = newT;
     span->fOther = other;
     span->fPt = pt;
+#if 0
+    // cubics, for instance, may not be exact enough to satisfy this check (e.g., cubicOp69d)
+    SkASSERT(approximately_equal(xyAtT(newT).fX, pt.fX)
+            && approximately_equal(xyAtT(newT).fY, pt.fY));
+#endif
     span->fWindSum = SK_MinS32;
     span->fOppSum = SK_MinS32;
     span->fWindValue = 1;
     span->fOppValue = 0;
     span->fTiny = false;
     span->fLoop = false;
     if ((span->fDone = newT == 1)) {
         ++fDoneSpans;
     }
     span->fUnsortableStart = false;
@@ skipping 63 matching lines @@
             }
         }
         ++fDoneSpans;
         ++more;
     }
     return insertedAt;
 }
 
 // set spans from start to end to decrement by one
 // note this walks other backwards
-// FIMXE: there's probably an edge case that can be constructed where
+// FIXME: there's probably an edge case that can be constructed where
 // two span in one segment are separated by float epsilon on one span but
 // not the other, if one segment is very small. For this
 // case the counts asserted below may or may not be enough to separate the
 // spans. Even if the counts work out, what if the spans aren't correctly
 // sorted? It feels better in such a case to match the span's other span
 // pointer since both coincident segments must contain the same spans.
+// FIXME? It seems that decrementing by one will fail for complex paths that
+// have three or more coincident edges. Shouldn't this subtract the difference
+// between the winding values?
 void SkOpSegment::addTCancel(double startT, double endT, SkOpSegment* other,
         double oStartT, double oEndT) {
     SkASSERT(!approximately_negative(endT - startT));
     SkASSERT(!approximately_negative(oEndT - oStartT));
     bool binary = fOperand != other->fOperand;
     int index = 0;
     while (!approximately_negative(startT - fTs[index].fT)) {
         ++index;
     }
     int oIndex = other->fTs.count();
     while (approximately_positive(other->fTs[--oIndex].fT - oEndT))
         ;
     double tRatio = (oEndT - oStartT) / (endT - startT);
     SkOpSpan* test = &fTs[index];
     SkOpSpan* oTest = &other->fTs[oIndex];
     SkTDArray<double> outsideTs;
     SkTDArray<double> oOutsideTs;
     do {
-        bool decrement = test->fWindValue && oTest->fWindValue && !binary;
+        bool decrement = test->fWindValue && oTest->fWindValue;
         bool track = test->fWindValue || oTest->fWindValue;
+        bool bigger = test->fWindValue >= oTest->fWindValue;
         double testT = test->fT;
         double oTestT = oTest->fT;
         SkOpSpan* span = test;
         do {
             if (decrement) {
-                decrementSpan(span);
+                if (binary && bigger) {
+                    span->fOppValue--;
+                } else {
+                    decrementSpan(span);
+                }
             } else if (track && span->fT < 1 && oTestT < 1) {
                 TrackOutside(&outsideTs, span->fT, oTestT);
             }
             span = &fTs[++index];
         } while (approximately_negative(span->fT - testT));
         SkOpSpan* oSpan = oTest;
         double otherTMatchStart = oEndT - (span->fT - startT) * tRatio;
         double otherTMatchEnd = oEndT - (test->fT - startT) * tRatio;
         SkDEBUGCODE(int originalWindValue = oSpan->fWindValue);
         while (approximately_negative(otherTMatchStart - oSpan->fT)
                 && !approximately_negative(otherTMatchEnd - oSpan->fT)) {
     #ifdef SK_DEBUG
             SkASSERT(originalWindValue == oSpan->fWindValue);
     #endif
             if (decrement) {
-                other->decrementSpan(oSpan);
+                if (binary && !bigger) {
+                    oSpan->fOppValue--;
+                } else {
+                    other->decrementSpan(oSpan);
+                }
             } else if (track && oSpan->fT < 1 && testT < 1) {
                 TrackOutside(&oOutsideTs, oSpan->fT, testT);
             }
             if (!oIndex) {
                 break;
             }
             oSpan = &other->fTs[--oIndex];
         }
         test = span;
         oTest = oSpan;
@@ skipping 156 matching lines @@
     int otherInsertedAt = other->addT(this, pt, otherT);
     addOtherT(insertedAt, otherT, otherInsertedAt);
     other->addOtherT(otherInsertedAt, t, insertedAt);
     matchWindingValue(insertedAt, t, borrowWind);
     other->matchWindingValue(otherInsertedAt, otherT, borrowWind);
 }
 
 void SkOpSegment::addTwoAngles(int start, int end, SkTDArray<SkOpAngle>* angles) const {
     // add edge leading into junction
     int min = SkMin32(end, start);
-    if (fTs[min].fWindValue > 0 || fTs[min].fOppValue > 0) {
+    if (fTs[min].fWindValue > 0 || fTs[min].fOppValue != 0) {
         addAngle(angles, end, start);
     }
     // add edge leading away from junction
     int step = SkSign32(end - start);
     int tIndex = nextExactSpan(end, step);
     min = SkMin32(end, tIndex);
-    if (tIndex >= 0 && (fTs[min].fWindValue > 0 || fTs[min].fOppValue > 0)) {
+    if (tIndex >= 0 && (fTs[min].fWindValue > 0 || fTs[min].fOppValue != 0)) {
         addAngle(angles, end, tIndex);
     }
 }
 
 int SkOpSegment::advanceCoincidentThis(const SkOpSpan* oTest, bool opp, int index) {
     SkOpSpan* const test = &fTs[index];
     SkOpSpan* end;
     do {
         end = &fTs[++index];
     } while (approximately_negative(end->fT - test->fT));
@@ skipping 126 matching lines @@
             }
         }
         if (segment->windSum(angle) == SK_MinS32) {
             if (opp) {
                 if (UseInnerWinding(oMaxWinding, oWinding)) {
                     oMaxWinding = oWinding;
                 }
                 if (oppoSign && UseInnerWinding(maxWinding, winding)) {
                     maxWinding = winding;
                 }
+#ifdef SK_DEBUG
+                SkASSERT(abs(maxWinding) <= gDebugMaxWindSum);
+                SkASSERT(abs(oMaxWinding) <= gDebugMaxWindSum);
+#endif
                 (void) segment->markAndChaseWinding(angle, oMaxWinding, maxWinding);
             } else {
                 if (UseInnerWinding(maxWinding, winding)) {
                     maxWinding = winding;
                 }
                 if (oppoSign && UseInnerWinding(oMaxWinding, oWinding)) {
                     oMaxWinding = oWinding;
                 }
+#ifdef SK_DEBUG
+                SkASSERT(abs(maxWinding) <= gDebugMaxWindSum);
+                SkASSERT(abs(binary ? oMaxWinding : 0) <= gDebugMaxWindSum);
+#endif
                 (void) segment->markAndChaseWinding(angle, maxWinding,
                         binary ? oMaxWinding : 0);
             }
         }
     } while (++nextIndex != lastIndex);
     int minIndex = SkMin32(startIndex, endIndex);
     return windSum(minIndex);
 }
 
 int SkOpSegment::crossedSpanY(const SkPoint& basePt, SkScalar* bestY, double* hitT,
@@ skipping 1301 matching lines @@
         *last = &fTs[end];
         return NULL;
     }
     const SkOpSpan& endSpan = fTs[end];
     SkOpSegment* other = endSpan.fOther;
     *index = endSpan.fOtherIndex;
     SkASSERT(*index >= 0);
     int otherEnd = other->nextExactSpan(*index, step);
     SkASSERT(otherEnd >= 0);
     *min = SkMin32(*index, otherEnd);
+    if (other->fTs[*min].fTiny) {
+        *last = NULL;
+        return NULL;
+    }
     return other;
 }
 
 // This has callers for two different situations: one establishes the end
 // of the current span, and one establishes the beginning of the next span
 // (thus the name). When this is looking for the end of the current span,
 // coincidence is found when the beginning Ts contain -step and the end
 // contains step. When it is looking for the beginning of the next, the
 // first Ts found can be ignored and the last Ts should contain -step.
 // OPTIMIZATION: probably should split into two functions
@@ skipping 228 matching lines @@
     for (int index = 0; index < count; ++index) {
         if (fTs[index].fT == t) {
             return fTs[index].fWindValue;
         }
     }
     SkASSERT(0);
     return 0;
 }
 
 void SkOpSegment::zeroSpan(SkOpSpan* span) {
-    SkASSERT(span->fWindValue > 0 || span->fOppValue > 0);
+    SkASSERT(span->fWindValue > 0 || span->fOppValue != 0);
     span->fWindValue = 0;
     span->fOppValue = 0;
     SkASSERT(!span->fDone);
     span->fDone = true;
     ++fDoneSpans;
 }
 
 #if DEBUG_SWAP_TOP
 bool SkOpSegment::controlsContainedByEnds(int tStart, int tEnd) const {
     if (fVerb != SkPath::kCubic_Verb) {
@@ skipping 47 matching lines @@
     if (fOperand) {
         SkDebugf(" operand");
     }
     if (done()) {
         SkDebugf(" done");
     }
     SkDebugf("\n");
 }
 #endif
 
-#if DEBUG_ACTIVE_SPANS
+#if DEBUG_ACTIVE_SPANS || DEBUG_ACTIVE_SPANS_FIRST_ONLY
 void SkOpSegment::debugShowActiveSpans() const {
     if (done()) {
         return;
     }
 #if DEBUG_ACTIVE_SPANS_SHORT_FORM
     int lastId = -1;
     double lastT = -1;
 #endif
     for (int i = 0; i < fTs.count(); ++i) {
         SkASSERT(&fTs[i] == &fTs[i].fOther->fTs[fTs[i].fOtherIndex].fOther->
                 fTs[fTs[i].fOther->fTs[fTs[i].fOtherIndex].fOtherIndex]);
         if (fTs[i].fDone) {
             continue;
         }
+        SkASSERT(i < fTs.count() - 1);
 #if DEBUG_ACTIVE_SPANS_SHORT_FORM
         if (lastId == fID && lastT == fTs[i].fT) {
             continue;
         }
         lastId = fID;
         lastT = fTs[i].fT;
 #endif
         SkDebugf("%s id=%d", __FUNCTION__, fID);
         SkDebugf(" (%1.9g,%1.9g", fPts[0].fX, fPts[0].fY);
         for (int vIndex = 1; vIndex <= fVerb; ++vIndex) {
@@ skipping 205 matching lines @@
         sum += fTs[i].fWindValue;
         slots[fTs[i].fOther->fID - 1] = as_digit(fTs[i].fWindValue);
         sum += fTs[i].fOppValue;
         slots[slotCount + fTs[i].fOther->fID - 1] = as_digit(fTs[i].fOppValue);
     }
     SkDebugf("%s id=%2d %.*s | %.*s\n", __FUNCTION__, fID, slotCount, slots.begin(), slotCount,
             slots.begin() + slotCount);
     return sum;
 }
 #endif