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 843 matching lines @@
 int SkOpSegment::computeSum(int startIndex, int endIndex, bool binary) {
     SkSTArray<SkOpAngle::kStackBasedCount, SkOpAngle, true> angles;
     addTwoAngles(startIndex, endIndex, &angles);
     buildAngles(endIndex, &angles, false);
     // OPTIMIZATION: check all angles to see if any have computed wind sum
     // before sorting (early exit if none)
     SkSTArray<SkOpAngle::kStackBasedCount, SkOpAngle*, true> sorted;
     // FIXME?: Not sure if this sort must be ordered or if the relaxed ordering is OK ...
     bool sortable = SortAngles(angles, &sorted, SkOpSegment::kMustBeOrdered_SortAngleKind);
 #if DEBUG_SORT
-    sorted[0]->segment()->debugShowSort(__FUNCTION__, sorted, 0, 0, 0);
+    sorted[0]->segment()->debugShowSort(__FUNCTION__, sorted, 0, 0, 0, sortable);
 #endif
     if (!sortable) {
         return SK_MinS32;
     }
     int angleCount = angles.count();
     const SkOpAngle* angle;
     const SkOpSegment* base;
     int winding;
     int oWinding;
     int firstIndex = 0;
@@ skipping 14 matching lines @@
     bool inner = UseInnerWinding(winding + spanWinding, winding);
 #if DEBUG_WINDING
     SkDebugf("%s spanWinding=%d winding=%d sign=%d inner=%d result=%d\n", __FUNCTION__,
         spanWinding, winding, angle->sign(), inner,
         inner ? winding + spanWinding : winding);
 #endif
     if (inner) {
         winding += spanWinding;
     }
 #if DEBUG_SORT
-    base->debugShowSort(__FUNCTION__, sorted, firstIndex, winding, oWinding);
+    base->debugShowSort(__FUNCTION__, sorted, firstIndex, winding, oWinding, sortable);
 #endif
     int nextIndex = firstIndex + 1;
     int lastIndex = firstIndex != 0 ? firstIndex : angleCount;
     winding -= base->spanSign(angle);
     oWinding -= base->oppSign(angle);
     do {
         if (nextIndex == angleCount) {
             nextIndex = 0;
         }
         angle = sorted[nextIndex];
@@ skipping 217 matching lines @@
         other = endSpan->fOther;
         *nextStart = endSpan->fOtherIndex;
         double startT = other->fTs[*nextStart].fT;
         *nextEnd = *nextStart;
         do {
             *nextEnd += step;
         }
         while (precisely_zero(startT - other->fTs[*nextEnd].fT));
         SkASSERT(step < 0 ? *nextEnd >= 0 : *nextEnd < other->fTs.count());
         if (other->isTiny(SkMin32(*nextStart, *nextEnd))) {
+            *unsortable = true;
             return NULL;
         }
         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));
     addTwoAngles(startIndex, end, &angles);
     buildAngles(end, &angles, true);
     SkSTArray<SkOpAngle::kStackBasedCount, SkOpAngle*, true> sorted;
     bool sortable = SortAngles(angles, &sorted, SkOpSegment::kMustBeOrdered_SortAngleKind);
     int angleCount = angles.count();
     int firstIndex = findStartingEdge(sorted, startIndex, end);
     SkASSERT(firstIndex >= 0);
 #if DEBUG_SORT
-    debugShowSort(__FUNCTION__, sorted, firstIndex);
+    debugShowSort(__FUNCTION__, sorted, firstIndex, sortable);
 #endif
     if (!sortable) {
         *unsortable = true;
         return NULL;
     }
     SkASSERT(sorted[firstIndex]->segment() == this);
 #if DEBUG_WINDING
     SkDebugf("%s firstIndex=[%d] sign=%d\n", __FUNCTION__, firstIndex,
             sorted[firstIndex]->sign());
 #endif
@@ skipping 101 matching lines @@
     SkASSERT(startIndex - endIndex != 0);
     SkASSERT((startIndex - endIndex < 0) ^ (step < 0));
     addTwoAngles(startIndex, end, &angles);
     buildAngles(end, &angles, true);
     SkSTArray<SkOpAngle::kStackBasedCount, SkOpAngle*, true> sorted;
     bool sortable = SortAngles(angles, &sorted, SkOpSegment::kMustBeOrdered_SortAngleKind);
     int angleCount = angles.count();
     int firstIndex = findStartingEdge(sorted, startIndex, end);
     SkASSERT(firstIndex >= 0);
 #if DEBUG_SORT
-    debugShowSort(__FUNCTION__, sorted, firstIndex);
+    debugShowSort(__FUNCTION__, sorted, firstIndex, sortable);
 #endif
     if (!sortable) {
         *unsortable = true;
         return NULL;
     }
     SkASSERT(sorted[firstIndex]->segment() == this);
 #if DEBUG_WINDING
     SkDebugf("%s firstIndex=[%d] sign=%d\n", __FUNCTION__, firstIndex,
             sorted[firstIndex]->sign());
 #endif
@@ skipping 107 matching lines @@
     SkSTArray<SkOpAngle::kStackBasedCount, SkOpAngle, true> angles;
     SkASSERT(startIndex - endIndex != 0);
     SkASSERT((startIndex - endIndex < 0) ^ (step < 0));
     addTwoAngles(startIndex, end, &angles);
     buildAngles(end, &angles, false);
     SkSTArray<SkOpAngle::kStackBasedCount, SkOpAngle*, true> sorted;
     bool sortable = SortAngles(angles, &sorted, SkOpSegment::kMustBeOrdered_SortAngleKind);
     if (!sortable) {
         *unsortable = true;
 #if DEBUG_SORT
-        debugShowSort(__FUNCTION__, sorted, findStartingEdge(sorted, startIndex, end), 0, 0);
+        debugShowSort(__FUNCTION__, sorted, findStartingEdge(sorted, startIndex, end), 0, 0,
+                sortable);
 #endif
         return NULL;
     }
     int angleCount = angles.count();
     int firstIndex = findStartingEdge(sorted, startIndex, end);
     SkASSERT(firstIndex >= 0);
 #if DEBUG_SORT
-    debugShowSort(__FUNCTION__, sorted, firstIndex, 0, 0);
+    debugShowSort(__FUNCTION__, sorted, firstIndex, 0, 0, sortable);
 #endif
     SkASSERT(sorted[firstIndex]->segment() == this);
     int nextIndex = firstIndex + 1;
     int lastIndex = firstIndex != 0 ? firstIndex : angleCount;
     const SkOpAngle* foundAngle = NULL;
     bool foundDone = false;
     SkOpSegment* nextSegment;
     int activeCount = 0;
     do {
         SkASSERT(nextIndex != firstIndex);
@@ skipping 225 matching lines @@
         SkOpSegment* next = angle->segment();
         SkPathOpsBounds bounds;
         next->subDivideBounds(angle->end(), angle->start(), &bounds);
         if (approximately_greater(top, bounds.fTop)) {
             top = bounds.fTop;
             first = index;
         }
     }
     SkASSERT(first < SK_MaxS32);
 #if DEBUG_SORT  // || DEBUG_SWAP_TOP
-    sorted[first]->segment()->debugShowSort(__FUNCTION__, sorted, first, 0, 0);
+    sorted[first]->segment()->debugShowSort(__FUNCTION__, sorted, first, 0, 0, sortable);
 #endif
     if (onlySortable && !sortable) {
         *unsortable = true;
         return NULL;
     }
     // skip edges that have already been processed
     firstT = first - 1;
     SkOpSegment* leftSegment;
     do {
         if (++firstT == count) {
@@ skipping 890 matching lines @@
     *dx = (*CurveSlopeAtT[SkPathOpsVerbToPoints(fVerb)])(fPts, tHit).fX;
     if (fVerb > SkPath::kLine_Verb && approximately_zero(*dx)) {
         *dx = fPts[2].fX - fPts[1].fX - *dx;
     }
     if (*dx == 0) {
 #if DEBUG_WINDING_AT_T
         SkDebugf(" dx=0 winding=SK_MinS32\n");
 #endif
         return SK_MinS32;
     }
+    if (windVal < 0) {  // reverse sign if opp contour traveled in reverse 
+            *dx = -*dx;
+    }
     if (winding * *dx > 0) {  // if same signs, result is negative
         winding += *dx > 0 ? -windVal : windVal;
     }
 #if DEBUG_WINDING_AT_T
     SkDebugf(" dx=%c winding=%d\n", *dx > 0 ? '+' : '-', winding);
 #endif
     return winding;
 }
 
 int SkOpSegment::windSum(const SkOpAngle* angle) const {
@@ skipping 184 matching lines @@
     } else {
         SkDebugf("%d", span.fWindSum);
     }
     SkDebugf(" windValue=%d\n", span.fWindValue);
 }
 #endif
 
 #if DEBUG_SORT || DEBUG_SWAP_TOP
 void SkOpSegment::debugShowSort(const char* fun, const SkTArray<SkOpAngle*, true>& angles,
                                 int first, const int contourWinding,
-                                const int oppContourWinding) const {
+                                const int oppContourWinding, bool sortable) const {
     if (--gDebugSortCount < 0) {
         return;
     }
     SkASSERT(angles[first]->segment() == this);
-    SkASSERT(angles.count() > 1);
+    SkASSERT(!sortable || angles.count() > 1);
     int lastSum = contourWinding;
     int oppLastSum = oppContourWinding;
     const SkOpAngle* firstAngle = angles[first];
     int windSum = lastSum - spanSign(firstAngle);
     int oppoSign = oppSign(firstAngle);
     int oppWindSum = oppLastSum - oppoSign;
     #define WIND_AS_STRING(x) char x##Str[12]; if (!valid_wind(x)) strcpy(x##Str, "?"); \
         else SK_SNPRINTF(x##Str, sizeof(x##Str), "%d", x)
     WIND_AS_STRING(contourWinding);
     WIND_AS_STRING(oppContourWinding);
@@ skipping 83 matching lines @@
         if (index == angles.count()) {
             index = 0;
         }
         if (firstTime) {
             firstTime = false;
         }
     } while (index != first);
 }
 
 void SkOpSegment::debugShowSort(const char* fun, const SkTArray<SkOpAngle*, true>& angles,
-                                int first) {
+                                int first, bool sortable) {
     const SkOpAngle* firstAngle = angles[first];
     const SkOpSegment* segment = firstAngle->segment();
     int winding = segment->updateWinding(firstAngle);
     int oppWinding = segment->updateOppWinding(firstAngle);
-    debugShowSort(fun, angles, first, winding, oppWinding);
+    debugShowSort(fun, angles, first, winding, oppWinding, sortable);
 }
 
 #endif
 
 #if DEBUG_SHOW_WINDING
 int SkOpSegment::debugShowWindingValues(int slotCount, int ofInterest) const {
     if (!(1 << fID & ofInterest)) {
         return 0;
     }
     int sum = 0;
     SkTArray<char, true> slots(slotCount * 2);
     memset(slots.begin(), ' ', slotCount * 2);
     for (int i = 0; i < fTs.count(); ++i) {
    //     if (!(1 << fTs[i].fOther->fID & ofInterest)) {
    //         continue;
    //     }
         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