SkPathOpsCommon.cpp revision 08bc8488fa2ea2d2a17efb1443f0ec6579d5a3c8 
1/*
2 * Copyright 2012 Google Inc.
3 *
4 * Use of this source code is governed by a BSD-style license that can be
5 * found in the LICENSE file.
6 */
7#include "SkAddIntersections.h"
8#include "SkOpCoincidence.h"
9#include "SkOpEdgeBuilder.h"
10#include "SkPathOpsCommon.h"
11#include "SkPathWriter.h"
12#include "SkTSort.h"
13
14static int contourRangeCheckY(const SkTDArray<SkOpContour* >& contourList,
15        SkOpSegment** currentPtr, SkOpSpanBase** startPtr, SkOpSpanBase** endPtr,
16        double* bestHit, SkScalar* bestDx, bool* tryAgain, double* midPtr, bool opp) {
17    SkOpSpanBase* start = *startPtr;
18    SkOpSpanBase* end = *endPtr;
19    const double mid = *midPtr;
20    const SkOpSegment* current = *currentPtr;
21    double tAtMid = SkOpSegment::TAtMid(start, end, mid);
22    SkPoint basePt = current->ptAtT(tAtMid);
23    int contourCount = contourList.count();
24    SkScalar bestY = SK_ScalarMin;
25    SkOpSegment* bestSeg = NULL;
26    SkOpSpan* bestTSpan = NULL;
27    bool bestOpp;
28    bool hitSomething = false;
29    for (int cTest = 0; cTest < contourCount; ++cTest) {
30        SkOpContour* contour = contourList[cTest];
31        bool testOpp = contour->operand() ^ current->operand() ^ opp;
32        if (basePt.fY < contour->bounds().fTop) {
33            continue;
34        }
35        if (bestY > contour->bounds().fBottom) {
36            continue;
37        }
38        SkOpSegment* testSeg = contour->first();
39        SkASSERT(testSeg);
40        do {
41            SkScalar testY = bestY;
42            double testHit;
43            bool vertical;
44            SkOpSpan* testTSpan = testSeg->crossedSpanY(basePt, tAtMid, testOpp,
45                    testSeg == current, &testY, &testHit, &hitSomething, &vertical);
46            if (!testTSpan) {
47                if (vertical) {
48                    hitSomething = true;
49                    bestSeg = NULL;
50                    goto abortContours;  // vertical encountered, return and try different point
51                }
52                continue;
53            }
54            if (testSeg == current && SkOpSegment::BetweenTs(start, testHit, end)) {
55                double baseT = start->t();
56                double endT = end->t();
57                double newMid = (testHit - baseT) / (endT - baseT);
58#if DEBUG_WINDING
59                double midT = SkOpSegment::TAtMid(start, end, mid);
60                SkPoint midXY = current->ptAtT(midT);
61                double newMidT = SkOpSegment::TAtMid(start, end, newMid);
62                SkPoint newXY = current->ptAtT(newMidT);
63                SkDebugf("%s [%d] mid=%1.9g->%1.9g s=%1.9g (%1.9g,%1.9g) m=%1.9g (%1.9g,%1.9g)"
64                        " n=%1.9g (%1.9g,%1.9g) e=%1.9g (%1.9g,%1.9g)\n", __FUNCTION__,
65                        current->debugID(), mid, newMid,
66                        baseT, start->pt().fX, start->pt().fY,
67                        baseT + mid * (endT - baseT), midXY.fX, midXY.fY,
68                        baseT + newMid * (endT - baseT), newXY.fX, newXY.fY,
69                        endT, end->pt().fX, end->pt().fY);
70#endif
71                *midPtr = newMid * 2;  // calling loop with divide by 2 before continuing
72                return SK_MinS32;
73            }
74            bestSeg = testSeg;
75            *bestHit = testHit;
76            bestOpp = testOpp;
77            bestTSpan = testTSpan;
78            bestY = testY;
79        } while ((testSeg = testSeg->next()));
80    }
81abortContours:
82    int result;
83    if (!bestSeg) {
84        result = hitSomething ? SK_MinS32 : 0;
85    } else {
86        if (bestTSpan->windSum() == SK_MinS32) {
87            *currentPtr = bestSeg;
88            *startPtr = bestTSpan;
89            *endPtr = bestTSpan->next();
90            SkASSERT(*startPtr != *endPtr && *startPtr && *endPtr);
91            *tryAgain = true;
92            return 0;
93        }
94        result = bestSeg->windingAtT(*bestHit, bestTSpan, bestOpp, bestDx);
95        SkASSERT(result == SK_MinS32 || *bestDx);
96    }
97    double baseT = (*startPtr)->t();
98    double endT = (*endPtr)->t();
99    *bestHit = baseT + mid * (endT - baseT);
100    return result;
101}
102
103SkOpSegment* FindUndone(SkTDArray<SkOpContour* >& contourList, SkOpSpanBase** startPtr,
104         SkOpSpanBase** endPtr) {
105    int contourCount = contourList.count();
106    SkOpSegment* result;
107    for (int cIndex = 0; cIndex < contourCount; ++cIndex) {
108        SkOpContour* contour = contourList[cIndex];
109        result = contour->undoneSegment(startPtr, endPtr);
110        if (result) {
111            return result;
112        }
113    }
114    return NULL;
115}
116
117SkOpSegment* FindChase(SkTDArray<SkOpSpanBase*>* chase, SkOpSpanBase** startPtr,
118        SkOpSpanBase** endPtr) {
119    while (chase->count()) {
120        SkOpSpanBase* span;
121        chase->pop(&span);
122        SkOpSegment* segment = span->segment();
123        *startPtr = span->ptT()->next()->span();
124        bool sortable = true;
125        bool done = true;
126        *endPtr = NULL;
127        if (SkOpAngle* last = segment->activeAngle(*startPtr, startPtr, endPtr, &done,
128                &sortable)) {
129            if (last->unorderable()) {
130                continue;
131            }
132            *startPtr = last->start();
133            *endPtr = last->end();
134    #if TRY_ROTATE
135            *chase->insert(0) = span;
136    #else
137            *chase->append() = span;
138    #endif
139            return last->segment();
140        }
141        if (done) {
142            continue;
143        }
144        if (!sortable) {
145            continue;
146        }
147        // find first angle, initialize winding to computed wind sum
148        const SkOpAngle* angle = segment->spanToAngle(*startPtr, *endPtr);
149        if (!angle) {
150            continue;
151        }
152        const SkOpAngle* firstAngle = angle;
153        bool loop = false;
154        int winding = SK_MinS32;
155        do {
156            angle = angle->next();
157            if (angle == firstAngle && loop) {
158                break;    // if we get here, there's no winding, loop is unorderable
159            }
160            loop |= angle == firstAngle;
161            segment = angle->segment();
162            winding = segment->windSum(angle);
163        } while (winding == SK_MinS32);
164        if (winding == SK_MinS32) {
165            continue;
166        }
167        int sumWinding = segment->updateWindingReverse(angle);
168        SkOpSegment* first = NULL;
169        firstAngle = angle;
170        while ((angle = angle->next()) != firstAngle) {
171            segment = angle->segment();
172            SkOpSpanBase* start = angle->start();
173            SkOpSpanBase* end = angle->end();
174            int maxWinding;
175            segment->setUpWinding(start, end, &maxWinding, &sumWinding);
176            if (!segment->done(angle)) {
177                if (!first) {
178                    first = segment;
179                    *startPtr = start;
180                    *endPtr = end;
181                }
182                // OPTIMIZATION: should this also add to the chase?
183                (void) segment->markAngle(maxWinding, sumWinding, angle);
184            }
185        }
186        if (first) {
187       #if TRY_ROTATE
188            *chase->insert(0) = span;
189       #else
190            *chase->append() = span;
191       #endif
192            return first;
193        }
194    }
195    return NULL;
196}
197
198#if DEBUG_ACTIVE_SPANS
199void DebugShowActiveSpans(SkTDArray<SkOpContour* >& contourList) {
200    int index;
201    for (index = 0; index < contourList.count(); ++ index) {
202        contourList[index]->debugShowActiveSpans();
203    }
204}
205#endif
206
207static SkOpSegment* findTopSegment(const SkTDArray<SkOpContour* >& contourList,
208        bool firstPass, SkOpSpanBase** start, SkOpSpanBase** end, SkPoint* topLeft,
209        bool* unsortable, bool* done, SkChunkAlloc* allocator) {
210    SkOpSegment* result;
211    const SkOpSegment* lastTopStart = NULL;
212    SkOpSpanBase* lastStart = NULL, * lastEnd = NULL;
213    do {
214        SkPoint bestXY = {SK_ScalarMax, SK_ScalarMax};
215        int contourCount = contourList.count();
216        SkOpSegment* topStart = NULL;
217        *done = true;
218        for (int cIndex = 0; cIndex < contourCount; ++cIndex) {
219            SkOpContour* contour = contourList[cIndex];
220            if (contour->done()) {
221                continue;
222            }
223            const SkPathOpsBounds& bounds = contour->bounds();
224            if (bounds.fBottom < topLeft->fY) {
225                *done = false;
226                continue;
227            }
228            if (bounds.fBottom == topLeft->fY && bounds.fRight < topLeft->fX) {
229                *done = false;
230                continue;
231            }
232            contour->topSortableSegment(*topLeft, &bestXY, &topStart);
233            if (!contour->done()) {
234                *done = false;
235            }
236        }
237        if (!topStart) {
238            return NULL;
239        }
240        *topLeft = bestXY;
241        result = topStart->findTop(firstPass, start, end, unsortable, allocator);
242        if (!result) {
243            if (lastTopStart == topStart && lastStart == *start && lastEnd == *end) {
244                *done = true;
245                return NULL;
246            }
247            lastTopStart = topStart;
248            lastStart = *start;
249            lastEnd = *end;
250        }
251    } while (!result);
252    return result;
253}
254
255static int rightAngleWinding(const SkTDArray<SkOpContour* >& contourList,
256        SkOpSegment** currentPtr, SkOpSpanBase** start, SkOpSpanBase** end, double* tHit,
257        SkScalar* hitDx, bool* tryAgain, bool* onlyVertical, bool opp) {
258    double test = 0.9;
259    int contourWinding;
260    do {
261        contourWinding = contourRangeCheckY(contourList, currentPtr, start, end,
262                tHit, hitDx, tryAgain, &test, opp);
263        if (contourWinding != SK_MinS32 || *tryAgain) {
264            return contourWinding;
265        }
266        if (*currentPtr && (*currentPtr)->isVertical()) {
267            *onlyVertical = true;
268            return contourWinding;
269        }
270        test /= 2;
271    } while (!approximately_negative(test));
272    SkASSERT(0);  // FIXME: incomplete functionality
273    return contourWinding;
274}
275
276static void skipVertical(const SkTDArray<SkOpContour* >& contourList,
277        SkOpSegment** current, SkOpSpanBase** start, SkOpSpanBase** end) {
278    if (!(*current)->isVertical(*start, *end)) {
279        return;
280    }
281    int contourCount = contourList.count();
282    for (int cIndex = 0; cIndex < contourCount; ++cIndex) {
283        SkOpContour* contour = contourList[cIndex];
284        if (contour->done()) {
285            continue;
286        }
287        SkOpSegment* nonVertical = contour->nonVerticalSegment(start, end);
288        if (nonVertical) {
289            *current = nonVertical;
290            return;
291        }
292    }
293    return;
294}
295
296struct SortableTop2 {  // error if local in pre-C++11
297    SkOpSpanBase* fStart;
298    SkOpSpanBase* fEnd;
299};
300
301SkOpSegment* FindSortableTop(const SkTDArray<SkOpContour* >& contourList, bool firstPass,
302        SkOpAngle::IncludeType angleIncludeType, bool* firstContour, SkOpSpanBase** startPtr,
303        SkOpSpanBase** endPtr, SkPoint* topLeft, bool* unsortable, bool* done, bool* onlyVertical,
304        SkChunkAlloc* allocator) {
305    SkOpSegment* current = findTopSegment(contourList, firstPass, startPtr, endPtr, topLeft,
306            unsortable, done, allocator);
307    if (!current) {
308        return NULL;
309    }
310    SkOpSpanBase* start = *startPtr;
311    SkOpSpanBase* end = *endPtr;
312    SkASSERT(current == start->segment());
313    if (*firstContour) {
314        current->initWinding(start, end, angleIncludeType);
315        *firstContour = false;
316        return current;
317    }
318    SkOpSpan* minSpan = start->starter(end);
319    int sumWinding = minSpan->windSum();
320    if (sumWinding == SK_MinS32) {
321        SkOpSpanBase* iSpan = end;
322        SkOpSpanBase* oSpan = start;
323        do {
324            bool checkFrom = oSpan->t() < iSpan->t();
325            if ((checkFrom ? iSpan->fromAngle() : iSpan->upCast()->toAngle()) == NULL) {
326                if (!iSpan->addSimpleAngle(checkFrom, allocator)) {
327                    *unsortable = true;
328                    return NULL;
329                }
330            }
331            sumWinding = current->computeSum(oSpan, iSpan, angleIncludeType);
332            SkTSwap(iSpan, oSpan);
333        } while (sumWinding == SK_MinS32 && iSpan == start);
334    }
335    if (sumWinding != SK_MinS32 && sumWinding != SK_NaN32) {
336        return current;
337    }
338    int contourWinding;
339    int oppContourWinding = 0;
340    // the simple upward projection of the unresolved points hit unsortable angles
341    // shoot rays at right angles to the segment to find its winding, ignoring angle cases
342    bool tryAgain;
343    double tHit;
344    SkScalar hitDx = 0;
345    SkScalar hitOppDx = 0;
346    // keep track of subsequent returns to detect infinite loops
347    SkTDArray<SortableTop2> sortableTops;
348    do {
349        // if current is vertical, find another candidate which is not
350        // if only remaining candidates are vertical, then they can be marked done
351        SkASSERT(*startPtr != *endPtr && *startPtr && *endPtr);
352        SkASSERT(current == (*startPtr)->segment());
353        skipVertical(contourList, &current, startPtr, endPtr);
354        SkASSERT(current);  // FIXME: if null, all remaining are vertical
355        SkASSERT(*startPtr != *endPtr && *startPtr && *endPtr);
356        SkASSERT(current == (*startPtr)->segment());
357        tryAgain = false;
358        contourWinding = rightAngleWinding(contourList, &current, startPtr, endPtr, &tHit,
359                &hitDx, &tryAgain, onlyVertical, false);
360        SkASSERT(current == (*startPtr)->segment());
361        if (tryAgain) {
362            bool giveUp = false;
363            int count = sortableTops.count();
364            for (int index = 0; index < count; ++index) {
365                const SortableTop2& prev = sortableTops[index];
366                if (giveUp) {
367                    prev.fStart->segment()->markDone(prev.fStart->starter(prev.fEnd));
368                } else if (prev.fStart == *startPtr || prev.fEnd == *endPtr) {
369                    // remaining edges are non-vertical and cannot have their winding computed
370                    // mark them as done and return, and hope that assembly can fill the holes
371                    giveUp = true;
372                    index = -1;
373                }
374            }
375            if (giveUp) {
376                *done = true;
377                return NULL;
378            }
379        }
380        SortableTop2* sortableTop = sortableTops.append();
381        sortableTop->fStart = *startPtr;
382        sortableTop->fEnd = *endPtr;
383#if DEBUG_SORT
384        SkDebugf("%s current=%d index=%d endIndex=%d tHit=%1.9g hitDx=%1.9g try=%d vert=%d\n",
385                __FUNCTION__, current->debugID(), (*startPtr)->debugID(), (*endPtr)->debugID(),
386                tHit, hitDx, tryAgain, *onlyVertical);
387#endif
388        if (*onlyVertical) {
389            return current;
390        }
391        if (tryAgain) {
392            continue;
393        }
394        if (angleIncludeType < SkOpAngle::kBinarySingle) {
395            break;
396        }
397        oppContourWinding = rightAngleWinding(contourList, &current, startPtr, endPtr, &tHit,
398                &hitOppDx, &tryAgain, NULL, true);
399        SkASSERT(current == (*startPtr)->segment());
400    } while (tryAgain);
401    bool success = current->initWinding(*startPtr, *endPtr, tHit, contourWinding, hitDx,
402            oppContourWinding, hitOppDx);
403    if (current->done()) {
404        return NULL;
405    } else if (!success) {  // check if the span has a valid winding
406        SkOpSpan* minSpan = (*startPtr)->t() < (*endPtr)->t() ? (*startPtr)->upCast()
407            : (*endPtr)->upCast();
408        if (minSpan->windSum() == SK_MinS32) {
409            return NULL;
410        }
411    }
412    return current;
413}
414
415void MakeContourList(SkOpContour* contour, SkTDArray<SkOpContour* >& list,
416                     bool evenOdd, bool oppEvenOdd) {
417    do {
418        if (contour->count()) {
419            contour->setOppXor(contour->operand() ? evenOdd : oppEvenOdd);
420            *list.append() = contour;
421        }
422    } while ((contour = contour->next()));
423    if (list.count() < 2) {
424        return;
425    }
426    SkTQSort<SkOpContour>(list.begin(), list.end() - 1);
427}
428
429class DistanceLessThan {
430public:
431    DistanceLessThan(double* distances) : fDistances(distances) { }
432    double* fDistances;
433    bool operator()(const int one, const int two) {
434        return fDistances[one] < fDistances[two];
435    }
436};
437
438    /*
439        check start and end of each contour
440        if not the same, record them
441        match them up
442        connect closest
443        reassemble contour pieces into new path
444    */
445void Assemble(const SkPathWriter& path, SkPathWriter* simple) {
446    SkChunkAlloc allocator(4096);  // FIXME: constant-ize, tune
447    SkOpContour contour;
448    SkOpGlobalState globalState(NULL  SkDEBUGPARAMS(&contour));
449#if DEBUG_SHOW_TEST_NAME
450    SkDebugf("</div>\n");
451#endif
452#if DEBUG_PATH_CONSTRUCTION
453    SkDebugf("%s\n", __FUNCTION__);
454#endif
455    SkOpEdgeBuilder builder(path, &contour, &allocator, &globalState);
456    builder.finish(&allocator);
457    SkTDArray<const SkOpContour* > runs;  // indices of partial contours
458    const SkOpContour* eContour = builder.head();
459    do {
460        if (!eContour->count()) {
461            continue;
462        }
463        const SkPoint& eStart = eContour->start();
464        const SkPoint& eEnd = eContour->end();
465#if DEBUG_ASSEMBLE
466        SkDebugf("%s contour", __FUNCTION__);
467        if (!SkDPoint::ApproximatelyEqual(eStart, eEnd)) {
468            SkDebugf("[%d]", runs.count());
469        } else {
470            SkDebugf("   ");
471        }
472        SkDebugf(" start=(%1.9g,%1.9g) end=(%1.9g,%1.9g)\n",
473                eStart.fX, eStart.fY, eEnd.fX, eEnd.fY);
474#endif
475        if (SkDPoint::ApproximatelyEqual(eStart, eEnd)) {
476            eContour->toPath(simple);
477            continue;
478        }
479        *runs.append() = eContour;
480    } while ((eContour = eContour->next()));
481    int count = runs.count();
482    if (count == 0) {
483        return;
484    }
485    SkTDArray<int> sLink, eLink;
486    sLink.append(count);
487    eLink.append(count);
488    int rIndex, iIndex;
489    for (rIndex = 0; rIndex < count; ++rIndex) {
490        sLink[rIndex] = eLink[rIndex] = SK_MaxS32;
491    }
492    const int ends = count * 2;  // all starts and ends
493    const int entries = (ends - 1) * count;  // folded triangle : n * (n - 1) / 2
494    SkTDArray<double> distances;
495    distances.append(entries);
496    for (rIndex = 0; rIndex < ends - 1; ++rIndex) {
497        const SkOpContour* oContour = runs[rIndex >> 1];
498        const SkPoint& oPt = rIndex & 1 ? oContour->end() : oContour->start();
499        const int row = rIndex < count - 1 ? rIndex * ends : (ends - rIndex - 2)
500                * ends - rIndex - 1;
501        for (iIndex = rIndex + 1; iIndex < ends; ++iIndex) {
502            const SkOpContour* iContour = runs[iIndex >> 1];
503            const SkPoint& iPt = iIndex & 1 ? iContour->end() : iContour->start();
504            double dx = iPt.fX - oPt.fX;
505            double dy = iPt.fY - oPt.fY;
506            double dist = dx * dx + dy * dy;
507            distances[row + iIndex] = dist;  // oStart distance from iStart
508        }
509    }
510    SkTDArray<int> sortedDist;
511    sortedDist.append(entries);
512    for (rIndex = 0; rIndex < entries; ++rIndex) {
513        sortedDist[rIndex] = rIndex;
514    }
515    SkTQSort<int>(sortedDist.begin(), sortedDist.end() - 1, DistanceLessThan(distances.begin()));
516    int remaining = count;  // number of start/end pairs
517    for (rIndex = 0; rIndex < entries; ++rIndex) {
518        int pair = sortedDist[rIndex];
519        int row = pair / ends;
520        int col = pair - row * ends;
521        int thingOne = row < col ? row : ends - row - 2;
522        int ndxOne = thingOne >> 1;
523        bool endOne = thingOne & 1;
524        int* linkOne = endOne ? eLink.begin() : sLink.begin();
525        if (linkOne[ndxOne] != SK_MaxS32) {
526            continue;
527        }
528        int thingTwo = row < col ? col : ends - row + col - 1;
529        int ndxTwo = thingTwo >> 1;
530        bool endTwo = thingTwo & 1;
531        int* linkTwo = endTwo ? eLink.begin() : sLink.begin();
532        if (linkTwo[ndxTwo] != SK_MaxS32) {
533            continue;
534        }
535        SkASSERT(&linkOne[ndxOne] != &linkTwo[ndxTwo]);
536        bool flip = endOne == endTwo;
537        linkOne[ndxOne] = flip ? ~ndxTwo : ndxTwo;
538        linkTwo[ndxTwo] = flip ? ~ndxOne : ndxOne;
539        if (!--remaining) {
540            break;
541        }
542    }
543    SkASSERT(!remaining);
544#if DEBUG_ASSEMBLE
545    for (rIndex = 0; rIndex < count; ++rIndex) {
546        int s = sLink[rIndex];
547        int e = eLink[rIndex];
548        SkDebugf("%s %c%d <- s%d - e%d -> %c%d\n", __FUNCTION__, s < 0 ? 's' : 'e',
549                s < 0 ? ~s : s, rIndex, rIndex, e < 0 ? 'e' : 's', e < 0 ? ~e : e);
550    }
551#endif
552    rIndex = 0;
553    do {
554        bool forward = true;
555        bool first = true;
556        int sIndex = sLink[rIndex];
557        SkASSERT(sIndex != SK_MaxS32);
558        sLink[rIndex] = SK_MaxS32;
559        int eIndex;
560        if (sIndex < 0) {
561            eIndex = sLink[~sIndex];
562            sLink[~sIndex] = SK_MaxS32;
563        } else {
564            eIndex = eLink[sIndex];
565            eLink[sIndex] = SK_MaxS32;
566        }
567        SkASSERT(eIndex != SK_MaxS32);
568#if DEBUG_ASSEMBLE
569        SkDebugf("%s sIndex=%c%d eIndex=%c%d\n", __FUNCTION__, sIndex < 0 ? 's' : 'e',
570                    sIndex < 0 ? ~sIndex : sIndex, eIndex < 0 ? 's' : 'e',
571                    eIndex < 0 ? ~eIndex : eIndex);
572#endif
573        do {
574            const SkOpContour* contour = runs[rIndex];
575            if (first) {
576                first = false;
577                const SkPoint* startPtr = &contour->start();
578                simple->deferredMove(startPtr[0]);
579            }
580            if (forward) {
581                contour->toPartialForward(simple);
582            } else {
583                contour->toPartialBackward(simple);
584            }
585#if DEBUG_ASSEMBLE
586            SkDebugf("%s rIndex=%d eIndex=%s%d close=%d\n", __FUNCTION__, rIndex,
587                eIndex < 0 ? "~" : "", eIndex < 0 ? ~eIndex : eIndex,
588                sIndex == ((rIndex != eIndex) ^ forward ? eIndex : ~eIndex));
589#endif
590            if (sIndex == ((rIndex != eIndex) ^ forward ? eIndex : ~eIndex)) {
591                simple->close();
592                break;
593            }
594            if (forward) {
595                eIndex = eLink[rIndex];
596                SkASSERT(eIndex != SK_MaxS32);
597                eLink[rIndex] = SK_MaxS32;
598                if (eIndex >= 0) {
599                    SkASSERT(sLink[eIndex] == rIndex);
600                    sLink[eIndex] = SK_MaxS32;
601                } else {
602                    SkASSERT(eLink[~eIndex] == ~rIndex);
603                    eLink[~eIndex] = SK_MaxS32;
604                }
605            } else {
606                eIndex = sLink[rIndex];
607                SkASSERT(eIndex != SK_MaxS32);
608                sLink[rIndex] = SK_MaxS32;
609                if (eIndex >= 0) {
610                    SkASSERT(eLink[eIndex] == rIndex);
611                    eLink[eIndex] = SK_MaxS32;
612                } else {
613                    SkASSERT(sLink[~eIndex] == ~rIndex);
614                    sLink[~eIndex] = SK_MaxS32;
615                }
616            }
617            rIndex = eIndex;
618            if (rIndex < 0) {
619                forward ^= 1;
620                rIndex = ~rIndex;
621            }
622        } while (true);
623        for (rIndex = 0; rIndex < count; ++rIndex) {
624            if (sLink[rIndex] != SK_MaxS32) {
625                break;
626            }
627        }
628    } while (rIndex < count);
629#if DEBUG_ASSEMBLE
630    for (rIndex = 0; rIndex < count; ++rIndex) {
631       SkASSERT(sLink[rIndex] == SK_MaxS32);
632       SkASSERT(eLink[rIndex] == SK_MaxS32);
633    }
634#endif
635}
636
637static void align(SkTDArray<SkOpContour* >* contourList) {
638    int contourCount = (*contourList).count();
639    for (int cTest = 0; cTest < contourCount; ++cTest) {
640        SkOpContour* contour = (*contourList)[cTest];
641        contour->align();
642    }
643}
644
645static void calcAngles(SkTDArray<SkOpContour* >* contourList, SkChunkAlloc* allocator) {
646    int contourCount = (*contourList).count();
647    for (int cTest = 0; cTest < contourCount; ++cTest) {
648        SkOpContour* contour = (*contourList)[cTest];
649        contour->calcAngles(allocator);
650    }
651}
652
653static void missingCoincidence(SkTDArray<SkOpContour* >* contourList,
654        SkOpCoincidence* coincidence, SkChunkAlloc* allocator) {
655    int contourCount = (*contourList).count();
656    for (int cTest = 0; cTest < contourCount; ++cTest) {
657        SkOpContour* contour = (*contourList)[cTest];
658        contour->missingCoincidence(coincidence, allocator);
659    }
660}
661
662static void moveMultiples(SkTDArray<SkOpContour* >* contourList) {
663    int contourCount = (*contourList).count();
664    for (int cTest = 0; cTest < contourCount; ++cTest) {
665        SkOpContour* contour = (*contourList)[cTest];
666        contour->moveMultiples();
667    }
668}
669
670static void moveNearby(SkTDArray<SkOpContour* >* contourList) {
671    int contourCount = (*contourList).count();
672    for (int cTest = 0; cTest < contourCount; ++cTest) {
673        SkOpContour* contour = (*contourList)[cTest];
674        contour->moveNearby();
675    }
676}
677
678static void sortAngles(SkTDArray<SkOpContour* >* contourList) {
679    int contourCount = (*contourList).count();
680    for (int cTest = 0; cTest < contourCount; ++cTest) {
681        SkOpContour* contour = (*contourList)[cTest];
682        contour->sortAngles();
683    }
684}
685
686static void sortSegments(SkTDArray<SkOpContour* >* contourList) {
687    int contourCount = (*contourList).count();
688    for (int cTest = 0; cTest < contourCount; ++cTest) {
689        SkOpContour* contour = (*contourList)[cTest];
690        contour->sortSegments();
691    }
692}
693
694bool HandleCoincidence(SkTDArray<SkOpContour* >* contourList, SkOpCoincidence* coincidence,
695        SkChunkAlloc* allocator, SkOpGlobalState* globalState) {
696    // combine t values when multiple intersections occur on some segments but not others
697    moveMultiples(contourList);
698    // move t values and points together to eliminate small/tiny gaps
699    moveNearby(contourList);
700    align(contourList);  // give all span members common values
701#if DEBUG_VALIDATE
702    globalState->setPhase(SkOpGlobalState::kIntersecting);
703#endif
704    coincidence->addMissing(allocator);
705#if DEBUG_VALIDATE
706    globalState->setPhase(SkOpGlobalState::kWalking);
707#endif
708    coincidence->expand();  // check to see if, loosely, coincident ranges may be expanded
709    coincidence->mark();  // mark spans of coincident segments as coincident
710    missingCoincidence(contourList, coincidence, allocator);  // look for coincidence missed earlier
711    if (!coincidence->apply()) {  // adjust the winding value to account for coincident edges
712        return false;
713    }
714    sortSegments(contourList);
715    calcAngles(contourList, allocator);
716    sortAngles(contourList);
717    if (globalState->angleCoincidence()) {
718        missingCoincidence(contourList, coincidence, allocator);
719        if (!coincidence->apply()) {
720            return false;
721        }
722    }
723#if DEBUG_ACTIVE_SPANS
724    DebugShowActiveSpans(*contourList);
725#endif
726    return true;
727}
728