michael@0: /*
michael@0:  * Copyright 2012 Google Inc.
michael@0:  *
michael@0:  * Use of this source code is governed by a BSD-style license that can be
michael@0:  * found in the LICENSE file.
michael@0:  */
michael@0: #include "SkAddIntersections.h"
michael@0: #include "SkOpEdgeBuilder.h"
michael@0: #include "SkPathOpsCommon.h"
michael@0: #include "SkPathWriter.h"
michael@0: #include "SkTSort.h"
michael@0: 
michael@0: static int contourRangeCheckY(const SkTArray<SkOpContour*, true>& contourList, SkOpSegment** currentPtr,
michael@0:                               int* indexPtr, int* endIndexPtr, double* bestHit, SkScalar* bestDx,
michael@0:                               bool* tryAgain, double* midPtr, bool opp) {
michael@0:     const int index = *indexPtr;
michael@0:     const int endIndex = *endIndexPtr;
michael@0:     const double mid = *midPtr;
michael@0:     const SkOpSegment* current = *currentPtr;
michael@0:     double tAtMid = current->tAtMid(index, endIndex, mid);
michael@0:     SkPoint basePt = current->ptAtT(tAtMid);
michael@0:     int contourCount = contourList.count();
michael@0:     SkScalar bestY = SK_ScalarMin;
michael@0:     SkOpSegment* bestSeg = NULL;
michael@0:     int bestTIndex = 0;
michael@0:     bool bestOpp;
michael@0:     bool hitSomething = false;
michael@0:     for (int cTest = 0; cTest < contourCount; ++cTest) {
michael@0:         SkOpContour* contour = contourList[cTest];
michael@0:         bool testOpp = contour->operand() ^ current->operand() ^ opp;
michael@0:         if (basePt.fY < contour->bounds().fTop) {
michael@0:             continue;
michael@0:         }
michael@0:         if (bestY > contour->bounds().fBottom) {
michael@0:             continue;
michael@0:         }
michael@0:         int segmentCount = contour->segments().count();
michael@0:         for (int test = 0; test < segmentCount; ++test) {
michael@0:             SkOpSegment* testSeg = &contour->segments()[test];
michael@0:             SkScalar testY = bestY;
michael@0:             double testHit;
michael@0:             int testTIndex = testSeg->crossedSpanY(basePt, &testY, &testHit, &hitSomething, tAtMid,
michael@0:                     testOpp, testSeg == current);
michael@0:             if (testTIndex < 0) {
michael@0:                 if (testTIndex == SK_MinS32) {
michael@0:                     hitSomething = true;
michael@0:                     bestSeg = NULL;
michael@0:                     goto abortContours;  // vertical encountered, return and try different point
michael@0:                 }
michael@0:                 continue;
michael@0:             }
michael@0:             if (testSeg == current && current->betweenTs(index, testHit, endIndex)) {
michael@0:                 double baseT = current->t(index);
michael@0:                 double endT = current->t(endIndex);
michael@0:                 double newMid = (testHit - baseT) / (endT - baseT);
michael@0: #if DEBUG_WINDING
michael@0:                 double midT = current->tAtMid(index, endIndex, mid);
michael@0:                 SkPoint midXY = current->xyAtT(midT);
michael@0:                 double newMidT = current->tAtMid(index, endIndex, newMid);
michael@0:                 SkPoint newXY = current->xyAtT(newMidT);
michael@0:                 SkDebugf("%s [%d] mid=%1.9g->%1.9g s=%1.9g (%1.9g,%1.9g) m=%1.9g (%1.9g,%1.9g)"
michael@0:                         " n=%1.9g (%1.9g,%1.9g) e=%1.9g (%1.9g,%1.9g)\n", __FUNCTION__,
michael@0:                         current->debugID(), mid, newMid,
michael@0:                         baseT, current->xAtT(index), current->yAtT(index),
michael@0:                         baseT + mid * (endT - baseT), midXY.fX, midXY.fY,
michael@0:                         baseT + newMid * (endT - baseT), newXY.fX, newXY.fY,
michael@0:                         endT, current->xAtT(endIndex), current->yAtT(endIndex));
michael@0: #endif
michael@0:                 *midPtr = newMid * 2;  // calling loop with divide by 2 before continuing
michael@0:                 return SK_MinS32;
michael@0:             }
michael@0:             bestSeg = testSeg;
michael@0:             *bestHit = testHit;
michael@0:             bestOpp = testOpp;
michael@0:             bestTIndex = testTIndex;
michael@0:             bestY = testY;
michael@0:         }
michael@0:     }
michael@0: abortContours:
michael@0:     int result;
michael@0:     if (!bestSeg) {
michael@0:         result = hitSomething ? SK_MinS32 : 0;
michael@0:     } else {
michael@0:         if (bestSeg->windSum(bestTIndex) == SK_MinS32) {
michael@0:             *currentPtr = bestSeg;
michael@0:             *indexPtr = bestTIndex;
michael@0:             *endIndexPtr = bestSeg->nextSpan(bestTIndex, 1);
michael@0:             SkASSERT(*indexPtr != *endIndexPtr && *indexPtr >= 0 && *endIndexPtr >= 0);
michael@0:             *tryAgain = true;
michael@0:             return 0;
michael@0:         }
michael@0:         result = bestSeg->windingAtT(*bestHit, bestTIndex, bestOpp, bestDx);
michael@0:         SkASSERT(result == SK_MinS32 || *bestDx);
michael@0:     }
michael@0:     double baseT = current->t(index);
michael@0:     double endT = current->t(endIndex);
michael@0:     *bestHit = baseT + mid * (endT - baseT);
michael@0:     return result;
michael@0: }
michael@0: 
michael@0: SkOpSegment* FindUndone(SkTArray<SkOpContour*, true>& contourList, int* start, int* end) {
michael@0:     int contourCount = contourList.count();
michael@0:     SkOpSegment* result;
michael@0:     for (int cIndex = 0; cIndex < contourCount; ++cIndex) {
michael@0:         SkOpContour* contour = contourList[cIndex];
michael@0:         result = contour->undoneSegment(start, end);
michael@0:         if (result) {
michael@0:             return result;
michael@0:         }
michael@0:     }
michael@0:     return NULL;
michael@0: }
michael@0: 
michael@0: SkOpSegment* FindChase(SkTDArray<SkOpSpan*>& chase, int& tIndex, int& endIndex) {
michael@0:     while (chase.count()) {
michael@0:         SkOpSpan* span;
michael@0:         chase.pop(&span);
michael@0:         const SkOpSpan& backPtr = span->fOther->span(span->fOtherIndex);
michael@0:         SkOpSegment* segment = backPtr.fOther;
michael@0:         tIndex = backPtr.fOtherIndex;
michael@0:         SkSTArray<SkOpAngle::kStackBasedCount, SkOpAngle, true> angles;
michael@0:         int done = 0;
michael@0:         if (segment->activeAngle(tIndex, &done, &angles)) {
michael@0:             SkOpAngle* last = angles.end() - 1;
michael@0:             tIndex = last->start();
michael@0:             endIndex = last->end();
michael@0:    #if TRY_ROTATE
michael@0:             *chase.insert(0) = span;
michael@0:    #else
michael@0:             *chase.append() = span;
michael@0:    #endif
michael@0:             return last->segment();
michael@0:         }
michael@0:         if (done == angles.count()) {
michael@0:             continue;
michael@0:         }
michael@0:         SkSTArray<SkOpAngle::kStackBasedCount, SkOpAngle*, true> sorted;
michael@0:         bool sortable = SkOpSegment::SortAngles(angles, &sorted,
michael@0:                 SkOpSegment::kMayBeUnordered_SortAngleKind);
michael@0:         int angleCount = sorted.count();
michael@0: #if DEBUG_SORT
michael@0:         sorted[0]->segment()->debugShowSort(__FUNCTION__, sorted, 0, 0, 0, sortable);
michael@0: #endif
michael@0:         if (!sortable) {
michael@0:             continue;
michael@0:         }
michael@0:         // find first angle, initialize winding to computed fWindSum
michael@0:         int firstIndex = -1;
michael@0:         const SkOpAngle* angle;
michael@0:         int winding;
michael@0:         do {
michael@0:             angle = sorted[++firstIndex];
michael@0:             segment = angle->segment();
michael@0:             winding = segment->windSum(angle);
michael@0:         } while (winding == SK_MinS32);
michael@0:         int spanWinding = segment->spanSign(angle->start(), angle->end());
michael@0:     #if DEBUG_WINDING
michael@0:         SkDebugf("%s winding=%d spanWinding=%d\n",
michael@0:                 __FUNCTION__, winding, spanWinding);
michael@0:     #endif
michael@0:         // turn span winding into contour winding
michael@0:         if (spanWinding * winding < 0) {
michael@0:             winding += spanWinding;
michael@0:         }
michael@0:     #if DEBUG_SORT
michael@0:         segment->debugShowSort(__FUNCTION__, sorted, firstIndex, winding, 0, sortable);
michael@0:     #endif
michael@0:         // we care about first sign and whether wind sum indicates this
michael@0:         // edge is inside or outside. Maybe need to pass span winding
michael@0:         // or first winding or something into this function?
michael@0:         // advance to first undone angle, then return it and winding
michael@0:         // (to set whether edges are active or not)
michael@0:         int nextIndex = firstIndex + 1;
michael@0:         int lastIndex = firstIndex != 0 ? firstIndex : angleCount;
michael@0:         angle = sorted[firstIndex];
michael@0:         winding -= angle->segment()->spanSign(angle);
michael@0:         do {
michael@0:             SkASSERT(nextIndex != firstIndex);
michael@0:             if (nextIndex == angleCount) {
michael@0:                 nextIndex = 0;
michael@0:             }
michael@0:             angle = sorted[nextIndex];
michael@0:             segment = angle->segment();
michael@0:             int maxWinding = winding;
michael@0:             winding -= segment->spanSign(angle);
michael@0:     #if DEBUG_SORT
michael@0:             SkDebugf("%s id=%d maxWinding=%d winding=%d sign=%d\n", __FUNCTION__,
michael@0:                     segment->debugID(), maxWinding, winding, angle->sign());
michael@0:     #endif
michael@0:             tIndex = angle->start();
michael@0:             endIndex = angle->end();
michael@0:             int lesser = SkMin32(tIndex, endIndex);
michael@0:             const SkOpSpan& nextSpan = segment->span(lesser);
michael@0:             if (!nextSpan.fDone) {
michael@0:             // FIXME: this be wrong? assign startWinding if edge is in
michael@0:             // same direction. If the direction is opposite, winding to
michael@0:             // assign is flipped sign or +/- 1?
michael@0:                 if (SkOpSegment::UseInnerWinding(maxWinding, winding)) {
michael@0:                     maxWinding = winding;
michael@0:                 }
michael@0:                 segment->markAndChaseWinding(angle, maxWinding, 0);
michael@0:                 break;
michael@0:             }
michael@0:         } while (++nextIndex != lastIndex);
michael@0:         *chase.insert(0) = span;
michael@0:         return segment;
michael@0:     }
michael@0:     return NULL;
michael@0: }
michael@0: 
michael@0: #if DEBUG_ACTIVE_SPANS || DEBUG_ACTIVE_SPANS_FIRST_ONLY
michael@0: void DebugShowActiveSpans(SkTArray<SkOpContour*, true>& contourList) {
michael@0:     int index;
michael@0:     for (index = 0; index < contourList.count(); ++ index) {
michael@0:         contourList[index]->debugShowActiveSpans();
michael@0:     }
michael@0: }
michael@0: #endif
michael@0: 
michael@0: static SkOpSegment* findSortableTop(const SkTArray<SkOpContour*, true>& contourList,
michael@0:                                     int* index, int* endIndex, SkPoint* topLeft, bool* unsortable,
michael@0:                                     bool* done, bool onlySortable) {
michael@0:     SkOpSegment* result;
michael@0:     do {
michael@0:         SkPoint bestXY = {SK_ScalarMax, SK_ScalarMax};
michael@0:         int contourCount = contourList.count();
michael@0:         SkOpSegment* topStart = NULL;
michael@0:         *done = true;
michael@0:         for (int cIndex = 0; cIndex < contourCount; ++cIndex) {
michael@0:             SkOpContour* contour = contourList[cIndex];
michael@0:             if (contour->done()) {
michael@0:                 continue;
michael@0:             }
michael@0:             const SkPathOpsBounds& bounds = contour->bounds();
michael@0:             if (bounds.fBottom < topLeft->fY) {
michael@0:                 *done = false;
michael@0:                 continue;
michael@0:             }
michael@0:             if (bounds.fBottom == topLeft->fY && bounds.fRight < topLeft->fX) {
michael@0:                 *done = false;
michael@0:                 continue;
michael@0:             }
michael@0:             contour->topSortableSegment(*topLeft, &bestXY, &topStart);
michael@0:             if (!contour->done()) {
michael@0:                 *done = false;
michael@0:             }
michael@0:         }
michael@0:         if (!topStart) {
michael@0:             return NULL;
michael@0:         }
michael@0:         *topLeft = bestXY;
michael@0:         result = topStart->findTop(index, endIndex, unsortable, onlySortable);
michael@0:     } while (!result);
michael@0:     if (result) {
michael@0:         *unsortable = false;
michael@0:     }
michael@0:     return result;
michael@0: }
michael@0: 
michael@0: static int rightAngleWinding(const SkTArray<SkOpContour*, true>& contourList,
michael@0:                              SkOpSegment** current, int* index, int* endIndex, double* tHit,
michael@0:                              SkScalar* hitDx, bool* tryAgain, bool opp) {
michael@0:     double test = 0.9;
michael@0:     int contourWinding;
michael@0:     do {
michael@0:         contourWinding = contourRangeCheckY(contourList, current, index, endIndex, tHit, hitDx,
michael@0:                 tryAgain, &test, opp);
michael@0:         if (contourWinding != SK_MinS32 || *tryAgain) {
michael@0:             return contourWinding;
michael@0:         }
michael@0:         test /= 2;
michael@0:     } while (!approximately_negative(test));
michael@0:     SkASSERT(0);  // should be OK to comment out, but interested when this hits
michael@0:     return contourWinding;
michael@0: }
michael@0: 
michael@0: static void skipVertical(const SkTArray<SkOpContour*, true>& contourList,
michael@0:         SkOpSegment** current, int* index, int* endIndex) {
michael@0:     if (!(*current)->isVertical(*index, *endIndex)) {
michael@0:         return;
michael@0:     }
michael@0:     int contourCount = contourList.count();
michael@0:     for (int cIndex = 0; cIndex < contourCount; ++cIndex) {
michael@0:         SkOpContour* contour = contourList[cIndex];
michael@0:         if (contour->done()) {
michael@0:             continue;
michael@0:         }
michael@0:         *current = contour->nonVerticalSegment(index, endIndex);
michael@0:         if (*current) {
michael@0:             return;
michael@0:         }
michael@0:     }
michael@0: }
michael@0: 
michael@0: SkOpSegment* FindSortableTop(const SkTArray<SkOpContour*, true>& contourList,
michael@0:         SkOpAngle::IncludeType angleIncludeType, bool* firstContour, int* indexPtr,
michael@0:         int* endIndexPtr, SkPoint* topLeft, bool* unsortable, bool* done) {
michael@0:     SkOpSegment* current = findSortableTop(contourList, indexPtr, endIndexPtr, topLeft, unsortable,
michael@0:             done, true);
michael@0:     if (!current) {
michael@0:         return NULL;
michael@0:     }
michael@0:     const int index = *indexPtr;
michael@0:     const int endIndex = *endIndexPtr;
michael@0:     if (*firstContour) {
michael@0:         current->initWinding(index, endIndex);
michael@0:         *firstContour = false;
michael@0:         return current;
michael@0:     }
michael@0:     int minIndex = SkMin32(index, endIndex);
michael@0:     int sumWinding = current->windSum(minIndex);
michael@0:     if (sumWinding != SK_MinS32) {
michael@0:         return current;
michael@0:     }
michael@0:     SkASSERT(current->windSum(SkMin32(index, endIndex)) == SK_MinS32);
michael@0:     SkSTArray<SkOpAngle::kStackBasedCount, SkOpAngle, true> angles;
michael@0:     SkSTArray<SkOpAngle::kStackBasedCount, SkOpAngle*, true> sorted;
michael@0:     sumWinding = current->computeSum(index, endIndex, angleIncludeType, &angles, &sorted);
michael@0:     if (sumWinding != SK_MinS32 && sumWinding != SK_NaN32) {
michael@0:         return current;
michael@0:     }
michael@0:     int contourWinding;
michael@0:     int oppContourWinding = 0;
michael@0:     // the simple upward projection of the unresolved points hit unsortable angles
michael@0:     // shoot rays at right angles to the segment to find its winding, ignoring angle cases
michael@0:     bool tryAgain;
michael@0:     double tHit;
michael@0:     SkScalar hitDx = 0;
michael@0:     SkScalar hitOppDx = 0;
michael@0:     do {
michael@0:         // if current is vertical, find another candidate which is not
michael@0:         // if only remaining candidates are vertical, then they can be marked done
michael@0:         SkASSERT(*indexPtr != *endIndexPtr && *indexPtr >= 0 && *endIndexPtr >= 0);
michael@0:         skipVertical(contourList, &current, indexPtr, endIndexPtr);
michael@0: 
michael@0:         SkASSERT(*indexPtr != *endIndexPtr && *indexPtr >= 0 && *endIndexPtr >= 0);
michael@0:         tryAgain = false;
michael@0:         contourWinding = rightAngleWinding(contourList, &current, indexPtr, endIndexPtr, &tHit,
michael@0:                 &hitDx, &tryAgain, false);
michael@0:         if (tryAgain) {
michael@0:             continue;
michael@0:         }
michael@0:         if (angleIncludeType < SkOpAngle::kBinarySingle) {
michael@0:             break;
michael@0:         }
michael@0:         oppContourWinding = rightAngleWinding(contourList, &current, indexPtr, endIndexPtr, &tHit,
michael@0:                 &hitOppDx, &tryAgain, true);
michael@0:     } while (tryAgain);
michael@0:     current->initWinding(*indexPtr, *endIndexPtr, tHit, contourWinding, hitDx, oppContourWinding,
michael@0:             hitOppDx);
michael@0:     return current;
michael@0: }
michael@0: 
michael@0: static void checkEnds(SkTArray<SkOpContour*, true>* contourList) {
michael@0:     // it's hard to determine if the end of a cubic or conic nearly intersects another curve.
michael@0:     // instead, look to see if the connecting curve intersected at that same end.
michael@0:     int contourCount = (*contourList).count();
michael@0:     for (int cTest = 0; cTest < contourCount; ++cTest) {
michael@0:         SkOpContour* contour = (*contourList)[cTest];
michael@0:         contour->checkEnds();
michael@0:     }
michael@0: }
michael@0: 
michael@0: // A tiny interval may indicate an undiscovered coincidence. Find and fix.
michael@0: static void checkTiny(SkTArray<SkOpContour*, true>* contourList) {
michael@0:     int contourCount = (*contourList).count();
michael@0:     for (int cTest = 0; cTest < contourCount; ++cTest) {
michael@0:         SkOpContour* contour = (*contourList)[cTest];
michael@0:         contour->checkTiny();
michael@0:     }
michael@0: }
michael@0: 
michael@0: static void fixOtherTIndex(SkTArray<SkOpContour*, true>* contourList) {
michael@0:     int contourCount = (*contourList).count();
michael@0:     for (int cTest = 0; cTest < contourCount; ++cTest) {
michael@0:         SkOpContour* contour = (*contourList)[cTest];
michael@0:         contour->fixOtherTIndex();
michael@0:     }
michael@0: }
michael@0: 
michael@0: static void joinCoincidence(SkTArray<SkOpContour*, true>* contourList) {
michael@0:     int contourCount = (*contourList).count();
michael@0:     for (int cTest = 0; cTest < contourCount; ++cTest) {
michael@0:         SkOpContour* contour = (*contourList)[cTest];
michael@0:         contour->joinCoincidence();
michael@0:     }
michael@0: }
michael@0: 
michael@0: static void sortSegments(SkTArray<SkOpContour*, true>* contourList) {
michael@0:     int contourCount = (*contourList).count();
michael@0:     for (int cTest = 0; cTest < contourCount; ++cTest) {
michael@0:         SkOpContour* contour = (*contourList)[cTest];
michael@0:         contour->sortSegments();
michael@0:     }
michael@0: }
michael@0: 
michael@0: void MakeContourList(SkTArray<SkOpContour>& contours, SkTArray<SkOpContour*, true>& list,
michael@0:                      bool evenOdd, bool oppEvenOdd) {
michael@0:     int count = contours.count();
michael@0:     if (count == 0) {
michael@0:         return;
michael@0:     }
michael@0:     for (int index = 0; index < count; ++index) {
michael@0:         SkOpContour& contour = contours[index];
michael@0:         contour.setOppXor(contour.operand() ? evenOdd : oppEvenOdd);
michael@0:         list.push_back(&contour);
michael@0:     }
michael@0:     SkTQSort<SkOpContour>(list.begin(), list.end() - 1);
michael@0: }
michael@0: 
michael@0: class DistanceLessThan {
michael@0: public:
michael@0:     DistanceLessThan(double* distances) : fDistances(distances) { }
michael@0:     double* fDistances;
michael@0:     bool operator()(const int one, const int two) {
michael@0:         return fDistances[one] < fDistances[two];
michael@0:     }
michael@0: };
michael@0: 
michael@0:     /*
michael@0:         check start and end of each contour
michael@0:         if not the same, record them
michael@0:         match them up
michael@0:         connect closest
michael@0:         reassemble contour pieces into new path
michael@0:     */
michael@0: void Assemble(const SkPathWriter& path, SkPathWriter* simple) {
michael@0: #if DEBUG_PATH_CONSTRUCTION
michael@0:     SkDebugf("%s\n", __FUNCTION__);
michael@0: #endif
michael@0:     SkTArray<SkOpContour> contours;
michael@0:     SkOpEdgeBuilder builder(path, contours);
michael@0:     builder.finish();
michael@0:     int count = contours.count();
michael@0:     int outer;
michael@0:     SkTArray<int, true> runs(count);  // indices of partial contours
michael@0:     for (outer = 0; outer < count; ++outer) {
michael@0:         const SkOpContour& eContour = contours[outer];
michael@0:         const SkPoint& eStart = eContour.start();
michael@0:         const SkPoint& eEnd = eContour.end();
michael@0: #if DEBUG_ASSEMBLE
michael@0:         SkDebugf("%s contour", __FUNCTION__);
michael@0:         if (!SkDPoint::ApproximatelyEqual(eStart, eEnd)) {
michael@0:             SkDebugf("[%d]", runs.count());
michael@0:         } else {
michael@0:             SkDebugf("   ");
michael@0:         }
michael@0:         SkDebugf(" start=(%1.9g,%1.9g) end=(%1.9g,%1.9g)\n",
michael@0:                 eStart.fX, eStart.fY, eEnd.fX, eEnd.fY);
michael@0: #endif
michael@0:         if (SkDPoint::ApproximatelyEqual(eStart, eEnd)) {
michael@0:             eContour.toPath(simple);
michael@0:             continue;
michael@0:         }
michael@0:         runs.push_back(outer);
michael@0:     }
michael@0:     count = runs.count();
michael@0:     if (count == 0) {
michael@0:         return;
michael@0:     }
michael@0:     SkTArray<int, true> sLink, eLink;
michael@0:     sLink.push_back_n(count);
michael@0:     eLink.push_back_n(count);
michael@0:     int rIndex, iIndex;
michael@0:     for (rIndex = 0; rIndex < count; ++rIndex) {
michael@0:         sLink[rIndex] = eLink[rIndex] = SK_MaxS32;
michael@0:     }
michael@0:     const int ends = count * 2;  // all starts and ends
michael@0:     const int entries = (ends - 1) * count;  // folded triangle : n * (n - 1) / 2
michael@0:     SkTArray<double, true> distances;
michael@0:     distances.push_back_n(entries);
michael@0:     for (rIndex = 0; rIndex < ends - 1; ++rIndex) {
michael@0:         outer = runs[rIndex >> 1];
michael@0:         const SkOpContour& oContour = contours[outer];
michael@0:         const SkPoint& oPt = rIndex & 1 ? oContour.end() : oContour.start();
michael@0:         const int row = rIndex < count - 1 ? rIndex * ends : (ends - rIndex - 2)
michael@0:                 * ends - rIndex - 1;
michael@0:         for (iIndex = rIndex + 1; iIndex < ends; ++iIndex) {
michael@0:             int inner = runs[iIndex >> 1];
michael@0:             const SkOpContour& iContour = contours[inner];
michael@0:             const SkPoint& iPt = iIndex & 1 ? iContour.end() : iContour.start();
michael@0:             double dx = iPt.fX - oPt.fX;
michael@0:             double dy = iPt.fY - oPt.fY;
michael@0:             double dist = dx * dx + dy * dy;
michael@0:             distances[row + iIndex] = dist;  // oStart distance from iStart
michael@0:         }
michael@0:     }
michael@0:     SkTArray<int, true> sortedDist;
michael@0:     sortedDist.push_back_n(entries);
michael@0:     for (rIndex = 0; rIndex < entries; ++rIndex) {
michael@0:         sortedDist[rIndex] = rIndex;
michael@0:     }
michael@0:     SkTQSort<int>(sortedDist.begin(), sortedDist.end() - 1, DistanceLessThan(distances.begin()));
michael@0:     int remaining = count;  // number of start/end pairs
michael@0:     for (rIndex = 0; rIndex < entries; ++rIndex) {
michael@0:         int pair = sortedDist[rIndex];
michael@0:         int row = pair / ends;
michael@0:         int col = pair - row * ends;
michael@0:         int thingOne = row < col ? row : ends - row - 2;
michael@0:         int ndxOne = thingOne >> 1;
michael@0:         bool endOne = thingOne & 1;
michael@0:         int* linkOne = endOne ? eLink.begin() : sLink.begin();
michael@0:         if (linkOne[ndxOne] != SK_MaxS32) {
michael@0:             continue;
michael@0:         }
michael@0:         int thingTwo = row < col ? col : ends - row + col - 1;
michael@0:         int ndxTwo = thingTwo >> 1;
michael@0:         bool endTwo = thingTwo & 1;
michael@0:         int* linkTwo = endTwo ? eLink.begin() : sLink.begin();
michael@0:         if (linkTwo[ndxTwo] != SK_MaxS32) {
michael@0:             continue;
michael@0:         }
michael@0:         SkASSERT(&linkOne[ndxOne] != &linkTwo[ndxTwo]);
michael@0:         bool flip = endOne == endTwo;
michael@0:         linkOne[ndxOne] = flip ? ~ndxTwo : ndxTwo;
michael@0:         linkTwo[ndxTwo] = flip ? ~ndxOne : ndxOne;
michael@0:         if (!--remaining) {
michael@0:             break;
michael@0:         }
michael@0:     }
michael@0:     SkASSERT(!remaining);
michael@0: #if DEBUG_ASSEMBLE
michael@0:     for (rIndex = 0; rIndex < count; ++rIndex) {
michael@0:         int s = sLink[rIndex];
michael@0:         int e = eLink[rIndex];
michael@0:         SkDebugf("%s %c%d <- s%d - e%d -> %c%d\n", __FUNCTION__, s < 0 ? 's' : 'e',
michael@0:                 s < 0 ? ~s : s, rIndex, rIndex, e < 0 ? 'e' : 's', e < 0 ? ~e : e);
michael@0:     }
michael@0: #endif
michael@0:     rIndex = 0;
michael@0:     do {
michael@0:         bool forward = true;
michael@0:         bool first = true;
michael@0:         int sIndex = sLink[rIndex];
michael@0:         SkASSERT(sIndex != SK_MaxS32);
michael@0:         sLink[rIndex] = SK_MaxS32;
michael@0:         int eIndex;
michael@0:         if (sIndex < 0) {
michael@0:             eIndex = sLink[~sIndex];
michael@0:             sLink[~sIndex] = SK_MaxS32;
michael@0:         } else {
michael@0:             eIndex = eLink[sIndex];
michael@0:             eLink[sIndex] = SK_MaxS32;
michael@0:         }
michael@0:         SkASSERT(eIndex != SK_MaxS32);
michael@0: #if DEBUG_ASSEMBLE
michael@0:         SkDebugf("%s sIndex=%c%d eIndex=%c%d\n", __FUNCTION__, sIndex < 0 ? 's' : 'e',
michael@0:                     sIndex < 0 ? ~sIndex : sIndex, eIndex < 0 ? 's' : 'e',
michael@0:                     eIndex < 0 ? ~eIndex : eIndex);
michael@0: #endif
michael@0:         do {
michael@0:             outer = runs[rIndex];
michael@0:             const SkOpContour& contour = contours[outer];
michael@0:             if (first) {
michael@0:                 first = false;
michael@0:                 const SkPoint* startPtr = &contour.start();
michael@0:                 simple->deferredMove(startPtr[0]);
michael@0:             }
michael@0:             if (forward) {
michael@0:                 contour.toPartialForward(simple);
michael@0:             } else {
michael@0:                 contour.toPartialBackward(simple);
michael@0:             }
michael@0: #if DEBUG_ASSEMBLE
michael@0:             SkDebugf("%s rIndex=%d eIndex=%s%d close=%d\n", __FUNCTION__, rIndex,
michael@0:                 eIndex < 0 ? "~" : "", eIndex < 0 ? ~eIndex : eIndex,
michael@0:                 sIndex == ((rIndex != eIndex) ^ forward ? eIndex : ~eIndex));
michael@0: #endif
michael@0:             if (sIndex == ((rIndex != eIndex) ^ forward ? eIndex : ~eIndex)) {
michael@0:                 simple->close();
michael@0:                 break;
michael@0:             }
michael@0:             if (forward) {
michael@0:                 eIndex = eLink[rIndex];
michael@0:                 SkASSERT(eIndex != SK_MaxS32);
michael@0:                 eLink[rIndex] = SK_MaxS32;
michael@0:                 if (eIndex >= 0) {
michael@0:                     SkASSERT(sLink[eIndex] == rIndex);
michael@0:                     sLink[eIndex] = SK_MaxS32;
michael@0:                 } else {
michael@0:                     SkASSERT(eLink[~eIndex] == ~rIndex);
michael@0:                     eLink[~eIndex] = SK_MaxS32;
michael@0:                 }
michael@0:             } else {
michael@0:                 eIndex = sLink[rIndex];
michael@0:                 SkASSERT(eIndex != SK_MaxS32);
michael@0:                 sLink[rIndex] = SK_MaxS32;
michael@0:                 if (eIndex >= 0) {
michael@0:                     SkASSERT(eLink[eIndex] == rIndex);
michael@0:                     eLink[eIndex] = SK_MaxS32;
michael@0:                 } else {
michael@0:                     SkASSERT(sLink[~eIndex] == ~rIndex);
michael@0:                     sLink[~eIndex] = SK_MaxS32;
michael@0:                 }
michael@0:             }
michael@0:             rIndex = eIndex;
michael@0:             if (rIndex < 0) {
michael@0:                 forward ^= 1;
michael@0:                 rIndex = ~rIndex;
michael@0:             }
michael@0:         } while (true);
michael@0:         for (rIndex = 0; rIndex < count; ++rIndex) {
michael@0:             if (sLink[rIndex] != SK_MaxS32) {
michael@0:                 break;
michael@0:             }
michael@0:         }
michael@0:     } while (rIndex < count);
michael@0: #if DEBUG_ASSEMBLE
michael@0:     for (rIndex = 0; rIndex < count; ++rIndex) {
michael@0:        SkASSERT(sLink[rIndex] == SK_MaxS32);
michael@0:        SkASSERT(eLink[rIndex] == SK_MaxS32);
michael@0:     }
michael@0: #endif
michael@0: }
michael@0: 
michael@0: void HandleCoincidence(SkTArray<SkOpContour*, true>* contourList, int total) {
michael@0: #if DEBUG_SHOW_WINDING
michael@0:     SkOpContour::debugShowWindingValues(contourList);
michael@0: #endif
michael@0:     CoincidenceCheck(contourList, total);
michael@0: #if DEBUG_SHOW_WINDING
michael@0:     SkOpContour::debugShowWindingValues(contourList);
michael@0: #endif
michael@0:     fixOtherTIndex(contourList);
michael@0:     checkEnds(contourList);
michael@0:     checkTiny(contourList);
michael@0:     joinCoincidence(contourList);
michael@0:     sortSegments(contourList);
michael@0: #if DEBUG_ACTIVE_SPANS || DEBUG_ACTIVE_SPANS_FIRST_ONLY
michael@0:     DebugShowActiveSpans(*contourList);
michael@0: #endif
michael@0: }