path ops -- rewrite angle sort

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 191 matching lines @@
     bool to = *sumWinding  != 0;
     bool result = gUnaryActiveEdge[from][to];
     return result;
 }
 
 void SkOpSegment::addAngle(SkTDArray<SkOpAngle>* anglesPtr, int start, int end) const {
     SkASSERT(start != end);
     SkOpAngle* angle = anglesPtr->append();
 #if DEBUG_ANGLE
     SkTDArray<SkOpAngle>& angles = *anglesPtr;
-    if (angles.count() > 1 && !fTs[start].fTiny) {
-        SkPoint angle0Pt = (*CurvePointAtT[SkPathOpsVerbToPoints(angles[0].verb())])(angles[0].pts(),
-                (*angles[0].spans())[angles[0].start()].fT);
-        SkPoint newPt = (*CurvePointAtT[SkPathOpsVerbToPoints(fVerb)])(fPts, fTs[start].fT);
-        bool match = AlmostEqualUlps(angle0Pt.fX, newPt.fX);
-        match &= AlmostEqualUlps(angle0Pt.fY, newPt.fY);
-        if (!match) {
-            SkDebugf("%s no match\n", __FUNCTION__);
-            SkASSERT(0);
+    if (angles.count() > 1) {
+        const SkOpSegment* aSeg = angles[0].segment();
+        int aStart = angles[0].start();
+        if (!aSeg->fTs[aStart].fTiny) {
+            const SkPoint& angle0Pt = aSeg->xyAtT(aStart);
+            SkDPoint newPt = (*CurveDPointAtT[SkPathOpsVerbToPoints(aSeg->fVerb)])(aSeg->fPts,
+                    aSeg->fTs[aStart].fT);
+#if ONE_OFF_DEBUG
+            SkDebugf("%s t1=%1.9g (%1.9g, %1.9g) (%1.9g, %1.9g)\n", __FUNCTION__,
+                    aSeg->fTs[aStart].fT, newPt.fX, newPt.fY, angle0Pt.fX, angle0Pt.fY);
+#endif
+            SkASSERT(newPt.approximatelyEqual(angle0Pt));
         }
     }
 #endif
-    angle->set(fPts, fVerb, this, start, end, fTs);
+    angle->set(this, start, end);
 }
 
 void SkOpSegment::addCancelOutsides(double tStart, double oStart, SkOpSegment* other, double oEnd) {
     int tIndex = -1;
     int tCount = fTs.count();
     int oIndex = -1;
     int oCount = other->fTs.count();
     do {
         ++tIndex;
     } while (!approximately_negative(tStart - fTs[tIndex].fT) && tIndex < tCount);
@@ skipping 611 matching lines @@
     other->addTwoAngles(next, oIndex, angles);
 }
 
 int SkOpSegment::computeSum(int startIndex, int endIndex, bool binary) {
     SkTDArray<SkOpAngle> 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)
     SkTDArray<SkOpAngle*> sorted;
-    bool sortable = SortAngles(angles, &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);
 #endif
     if (!sortable) {
         return SK_MinS32;
     }
     int angleCount = angles.count();
     const SkOpAngle* angle;
     const SkOpSegment* base;
     int winding;
@@ skipping 105 matching lines @@
         return bestTIndex;
     }
     if (fBounds.fLeft == fBounds.fRight) {
         // if vertical, and directly above test point, wait for another one
         return AlmostEqualUlps(basePt.fX, fBounds.fLeft) ? SK_MinS32 : bestTIndex;
     }
     // intersect ray starting at basePt with edge
     SkIntersections intersections;
     // OPTIMIZE: use specialty function that intersects ray with curve,
     // returning t values only for curve (we don't care about t on ray)
-    int pts = (intersections.*CurveVertical[SkPathOpsVerbToPoints(fVerb)])(fPts, top, bottom, basePt.fX, false);
+    int pts = (intersections.*CurveVertical[SkPathOpsVerbToPoints(fVerb)])
+            (fPts, top, bottom, basePt.fX, false);
     if (pts == 0 || (current && pts == 1)) {
         return bestTIndex;
     }
     if (current) {
         SkASSERT(pts > 1);
         int closestIdx = 0;
         double closest = fabs(intersections[0][0] - mid);
         for (int idx = 1; idx < pts; ++idx) {
             double test = fabs(intersections[0][idx] - mid);
             if (closest > test) {
@@ skipping 126 matching lines @@
         markDoneBinary(min);
         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))) {
+            return NULL;
+        }
         return other;
     }
     // more than one viable candidate -- measure angles to find best
     SkTDArray<SkOpAngle> angles;
     SkASSERT(startIndex - endIndex != 0);
     SkASSERT((startIndex - endIndex < 0) ^ (step < 0));
     addTwoAngles(startIndex, end, &angles);
     buildAngles(end, &angles, true);
     SkTDArray<SkOpAngle*> sorted;
-    bool sortable = SortAngles(angles, &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);
 #endif
     if (!sortable) {
         *unsortable = true;
         return NULL;
     }
@@ skipping 21 matching lines @@
         }
         const SkOpAngle* nextAngle = sorted[nextIndex];
         nextSegment = nextAngle->segment();
         int maxWinding, sumWinding, oppMaxWinding, oppSumWinding;
         bool activeAngle = nextSegment->activeOp(xorMiMask, xorSuMask, nextAngle->start(),
                 nextAngle->end(), op, &sumMiWinding, &sumSuWinding,
                 &maxWinding, &sumWinding, &oppMaxWinding, &oppSumWinding);
         if (activeAngle) {
             ++activeCount;
             if (!foundAngle || (foundDone && activeCount & 1)) {
-                if (nextSegment->tiny(nextAngle)) {
+                if (nextSegment->isTiny(nextAngle)) {
                     *unsortable = true;
                     return NULL;
                 }
                 foundAngle = nextAngle;
-                foundDone = nextSegment->done(nextAngle) && !nextSegment->tiny(nextAngle);
+                foundDone = nextSegment->done(nextAngle) && !nextSegment->isTiny(nextAngle);
             }
         }
         if (nextSegment->done()) {
             continue;
         }
         if (nextSegment->windSum(nextAngle) != SK_MinS32) {
             continue;
         }
         SkOpSpan* last = nextSegment->markAngle(maxWinding, sumWinding, oppMaxWinding,
                 oppSumWinding, activeAngle, nextAngle);
@@ skipping 54 matching lines @@
         SkASSERT(step < 0 ? *nextEnd >= 0 : *nextEnd < other->fTs.count());
         return other;
     }
     // more than one viable candidate -- measure angles to find best
     SkTDArray<SkOpAngle> angles;
     SkASSERT(startIndex - endIndex != 0);
     SkASSERT((startIndex - endIndex < 0) ^ (step < 0));
     addTwoAngles(startIndex, end, &angles);
     buildAngles(end, &angles, true);
     SkTDArray<SkOpAngle*> sorted;
-    bool sortable = SortAngles(angles, &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);
 #endif
     if (!sortable) {
         *unsortable = true;
         return NULL;
     }
@@ skipping 16 matching lines @@
             nextIndex = 0;
         }
         const SkOpAngle* nextAngle = sorted[nextIndex];
         nextSegment = nextAngle->segment();
         int maxWinding;
         bool activeAngle = nextSegment->activeWinding(nextAngle->start(), nextAngle->end(),
                 &maxWinding, &sumWinding);
         if (activeAngle) {
             ++activeCount;
             if (!foundAngle || (foundDone && activeCount & 1)) {
-                if (nextSegment->tiny(nextAngle)) {
+                if (nextSegment->isTiny(nextAngle)) {
                     *unsortable = true;
                     return NULL;
                 }
                 foundAngle = nextAngle;
                 foundDone = nextSegment->done(nextAngle);
             }
         }
         if (nextSegment->done()) {
             continue;
         }
@@ skipping 71 matching lines @@
         } while (true);
         SkASSERT(step < 0 ? *nextEnd >= 0 : *nextEnd < other->fTs.count());
         return other;
     }
     SkTDArray<SkOpAngle> angles;
     SkASSERT(startIndex - endIndex != 0);
     SkASSERT((startIndex - endIndex < 0) ^ (step < 0));
     addTwoAngles(startIndex, end, &angles);
     buildAngles(end, &angles, false);
     SkTDArray<SkOpAngle*> sorted;
-    bool sortable = SortAngles(angles, &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);
 #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);
 #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);
         if (nextIndex == angleCount) {
             nextIndex = 0;
         }
         const SkOpAngle* nextAngle = sorted[nextIndex];
         nextSegment = nextAngle->segment();
         ++activeCount;
         if (!foundAngle || (foundDone && activeCount & 1)) {
-            if (nextSegment->tiny(nextAngle)) {
+            if (nextSegment->isTiny(nextAngle)) {
                 *unsortable = true;
                 return NULL;
             }
             foundAngle = nextAngle;
             foundDone = nextSegment->done(nextAngle);
         }
         if (nextSegment->done()) {
             continue;
         }
     } while (++nextIndex != lastIndex);
@@ skipping 191 matching lines @@
         end = nextSpan(firstT, step);
         SkASSERT(end != -1);
     }
     // if the topmost T is not on end, or is three-way or more, find left
     // look for left-ness from tLeft to firstT (matching y of other)
     SkTDArray<SkOpAngle> angles;
     SkASSERT(firstT - end != 0);
     addTwoAngles(end, firstT, &angles);
     buildAngles(firstT, &angles, true);
     SkTDArray<SkOpAngle*> sorted;
-    bool sortable = SortAngles(angles, &sorted);
+    bool sortable = SortAngles(angles, &sorted, SkOpSegment::kMayBeUnordered_SortAngleKind);
     int first = SK_MaxS32;
     SkScalar top = SK_ScalarMax;
     int count = sorted.count();
     for (int index = 0; index < count; ++index) {
         const SkOpAngle* angle = sorted[index];
         SkOpSegment* next = angle->segment();
         SkPathOpsBounds bounds;
         next->subDivideBounds(angle->end(), angle->start(), &bounds);
         if (approximately_greater(top, bounds.fTop)) {
             top = bounds.fTop;
@@ skipping 432 matching lines @@
 #endif
     span.fOppSum = oppWinding;
     return &span;
 }
 
 // from http://stackoverflow.com/questions/1165647/how-to-determine-if-a-list-of-polygon-points-are-in-clockwise-order
 bool SkOpSegment::clockwise(int tStart, int tEnd) const {
     SkASSERT(fVerb != SkPath::kLine_Verb);
     SkPoint edge[4];
     subDivide(tStart, tEnd, edge);
-    double sum = (edge[0].fX - edge[SkPathOpsVerbToPoints(fVerb)].fX) * (edge[0].fY + edge[SkPathOpsVerbToPoints(fVerb)].fY);
+    int points = SkPathOpsVerbToPoints(fVerb);
+    double sum = (edge[0].fX - edge[points].fX) * (edge[0].fY + edge[points].fY);
     if (fVerb == SkPath::kCubic_Verb) {
         SkScalar lesser = SkTMin<SkScalar>(edge[0].fY, edge[3].fY);
         if (edge[1].fY < lesser && edge[2].fY < lesser) {
             SkDLine tangent1 = {{ {edge[0].fX, edge[0].fY}, {edge[1].fX, edge[1].fY} }};
             SkDLine tangent2 = {{ {edge[2].fX, edge[2].fY}, {edge[3].fX, edge[3].fY} }};
             if (SkIntersections::Test(tangent1, tangent2)) {
                 SkPoint topPt = cubic_top(fPts, fTs[tStart].fT, fTs[tEnd].fT);
                 sum += (topPt.fX - edge[0].fX) * (topPt.fY + edge[0].fY);
                 sum += (edge[3].fX - topPt.fX) * (edge[3].fY + topPt.fY);
                 return sum <= 0;
             }
         }
     }
-    for (int idx = 0; idx < SkPathOpsVerbToPoints(fVerb); ++idx){
+    for (int idx = 0; idx < points; ++idx){
         sum += (edge[idx + 1].fX - edge[idx].fX) * (edge[idx + 1].fY + edge[idx].fY);
     }
     return sum <= 0;
 }
 
 bool SkOpSegment::monotonicInY(int tStart, int tEnd) const {
     if (fVerb == SkPath::kLine_Verb) {
         return false;
     }
     if (fVerb == SkPath::kQuad_Verb) {
@@ skipping 218 matching lines @@
         *sumWinding = *sumMiWinding -= deltaSum;
         *oppMaxWinding = *sumSuWinding;
         *oppSumWinding = *sumSuWinding -= oppDeltaSum;
     }
 }
 
 // This marks all spans unsortable so that this info is available for early
 // exclusion in find top and others. This could be optimized to only mark
 // adjacent spans that unsortable. However, this makes it difficult to later
 // determine starting points for edge detection in find top and the like.
-bool SkOpSegment::SortAngles(const SkTDArray<SkOpAngle>& angles,
-                             SkTDArray<SkOpAngle*>* angleList) {
+bool SkOpSegment::SortAngles(const SkTDArray<SkOpAngle>& angles, SkTDArray<SkOpAngle*>* angleList,
+                             SortAngleKind orderKind) {
     bool sortable = true;
     int angleCount = angles.count();
     int angleIndex;
     angleList->setReserve(angleCount);
     for (angleIndex = 0; angleIndex < angleCount; ++angleIndex) {
         const SkOpAngle& angle = angles[angleIndex];
         *angleList->append() = const_cast<SkOpAngle*>(&angle);
-        sortable &= !angle.unsortable();
+#if DEBUG_ANGLE
+        (*(angleList->end() - 1))->setID(angleIndex);
+#endif
+        sortable &= !(angle.unsortable() || (orderKind == kMustBeOrdered_SortAngleKind
+                    && angle.unorderable()));
     }
     if (sortable) {
         SkTQSort<SkOpAngle>(angleList->begin(), angleList->end() - 1);
         for (angleIndex = 0; angleIndex < angleCount; ++angleIndex) {
-            if (angles[angleIndex].unsortable()) {
+            if (angles[angleIndex].unsortable() || (orderKind == kMustBeOrdered_SortAngleKind
+                        && angles[angleIndex].unorderable())) {
                 sortable = false;
                 break;
             }
         }
     }
     if (!sortable) {
         for (angleIndex = 0; angleIndex < angleCount; ++angleIndex) {
             const SkOpAngle& angle = angles[angleIndex];
             angle.segment()->markUnsortable(angle.start(), angle.end());
         }
     }
     return sortable;
 }
 
-void SkOpSegment::subDivide(int start, int end, SkPoint edge[4]) const {
+// return true if midpoints were computed
+bool SkOpSegment::subDivide(int start, int end, SkPoint edge[4]) const {
+    SkASSERT(start != end);
     edge[0] = fTs[start].fPt;
-    edge[SkPathOpsVerbToPoints(fVerb)] = fTs[end].fPt;
-    if (fVerb == SkPath::kQuad_Verb || fVerb == SkPath::kCubic_Verb) {
-        SkDPoint sub[2] = {{ edge[0].fX, edge[0].fY}, {edge[SkPathOpsVerbToPoints(fVerb)].fX, edge[SkPathOpsVerbToPoints(fVerb)].fY }};
+    int points = SkPathOpsVerbToPoints(fVerb);
+    edge[points] = fTs[end].fPt;
+    if (fVerb == SkPath::kLine_Verb) {
+        return false;
+    }
+    double startT = fTs[start].fT;
+    double endT = fTs[end].fT;
+    if ((startT == 0 || endT == 0) && (startT == 1 || endT == 1)) {
+        // don't compute midpoints if we already have them
         if (fVerb == SkPath::kQuad_Verb) {
-            edge[1] = SkDQuad::SubDivide(fPts, sub[0], sub[1], fTs[start].fT,
-                    fTs[end].fT).asSkPoint();
-        } else {
-            SkDCubic::SubDivide(fPts, sub[0], sub[1], fTs[start].fT, fTs[end].fT, sub);
-            edge[1] = sub[0].asSkPoint();
-            edge[2] = sub[1].asSkPoint();
+            edge[1] = fPts[1];
+            return false;
         }
+        SkASSERT(fVerb == SkPath::kCubic_Verb);
+        if (start < end) {
+            edge[1] = fPts[1];
+            edge[2] = fPts[2];
+            return false;
+        }
+        edge[1] = fPts[2];
+        edge[2] = fPts[1];
+        return false;
     }
+    const SkDPoint sub[2] = {{ edge[0].fX, edge[0].fY}, {edge[points].fX, edge[points].fY }};
+    if (fVerb == SkPath::kQuad_Verb) {
+        edge[1] = SkDQuad::SubDivide(fPts, sub[0], sub[1], startT, endT).asSkPoint();
+    } else {
+        SkASSERT(fVerb == SkPath::kCubic_Verb);
+        SkDPoint ctrl[2];
+        SkDCubic::SubDivide(fPts, sub[0], sub[1], startT, endT, ctrl);
+        edge[1] = ctrl[0].asSkPoint();
+        edge[2] = ctrl[1].asSkPoint();
+    }
+    return true;
+}
+
+// return true if midpoints were computed
+bool SkOpSegment::subDivide(int start, int end, SkDCubic* result) const {
+    SkASSERT(start != end);
+    (*result)[0].set(fTs[start].fPt);
+    int points = SkPathOpsVerbToPoints(fVerb);
+    (*result)[points].set(fTs[end].fPt);
+    if (fVerb == SkPath::kLine_Verb) {
+        return false;
+    }
+    double startT = fTs[start].fT;
+    double endT = fTs[end].fT;
+    if ((startT == 0 || endT == 0) && (startT == 1 || endT == 1)) {
+        // don't compute midpoints if we already have them
+        if (fVerb == SkPath::kQuad_Verb) {
+            (*result)[1].set(fPts[1]);
+            return false;
+        }
+        SkASSERT(fVerb == SkPath::kCubic_Verb);
+        if (start < end) {
+            (*result)[1].set(fPts[1]);
+            (*result)[2].set(fPts[2]);
+            return false;
+        }
+        (*result)[1].set(fPts[2]);
+        (*result)[2].set(fPts[1]);
+        return false;
+    }
+    if (fVerb == SkPath::kQuad_Verb) {
+        (*result)[1] = SkDQuad::SubDivide(fPts, (*result)[0], (*result)[2], startT, endT);
+    } else {
+        SkASSERT(fVerb == SkPath::kCubic_Verb);
+        SkDCubic::SubDivide(fPts, (*result)[0], (*result)[3], startT, endT, &(*result)[1]);
+    }
+    return true;
 }
 
 void SkOpSegment::subDivideBounds(int start, int end, SkPathOpsBounds* bounds) const {
     SkPoint edge[4];
     subDivide(start, end, edge);
     (bounds->*SetCurveBounds[SkPathOpsVerbToPoints(fVerb)])(edge);
 }
 
-bool SkOpSegment::tiny(const SkOpAngle* angle) const {
+bool SkOpSegment::isTiny(const SkOpAngle* angle) const {
     int start = angle->start();
     int end = angle->end();
     const SkOpSpan& mSpan = fTs[SkMin32(start, end)];
     return mSpan.fTiny;
 }
 
+bool SkOpSegment::isTiny(int index) const {
+    return fTs[index].fTiny;
+}
+
 void SkOpSegment::TrackOutside(SkTDArray<double>* outsideTs, double end, double start) {
     int outCount = outsideTs->count();
     if (outCount == 0 || !approximately_negative(end - (*outsideTs)[outCount - 2])) {
         *outsideTs->append() = end;
         *outsideTs->append() = start;
     }
 }
 
 void SkOpSegment::undoneSpan(int* start, int* end) {
     size_t tCount = fTs.count();
@@ skipping 323 matching lines @@
                 lastSum = windSum;
                 windSum -= segment.spanSign(&angle);
                 if (oppoSign) {
                     oppLastSum = oppWindSum;
                     oppWindSum -= oppoSign;
                 }
             }
         }
         SkDebugf("%s [%d] %s", __FUNCTION__, index,
                 angle.unsortable() ? "*** UNSORTABLE *** " : "");
-    #if COMPACT_DEBUG_SORT
-        SkDebugf("id=%d %s start=%d (%1.9g,%,1.9g) end=%d (%1.9g,%,1.9g)",
+    #if DEBUG_SORT_COMPACT
+        SkDebugf("id=%d %s start=%d (%1.9g,%1.9g) end=%d (%1.9g,%1.9g)",
                 segment.fID, kLVerbStr[SkPathOpsVerbToPoints(segment.fVerb)],
                 start, segment.xAtT(&sSpan), segment.yAtT(&sSpan), end,
                 segment.xAtT(&eSpan), segment.yAtT(&eSpan));
     #else
         switch (segment.fVerb) {
             case SkPath::kLine_Verb:
                 SkDebugf(LINE_DEBUG_STR, LINE_DEBUG_DATA(segment.fPts));
                 break;
             case SkPath::kQuad_Verb:
                 SkDebugf(QUAD_DEBUG_STR, QUAD_DEBUG_DATA(segment.fPts));
@@ skipping 70 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