SkPathOpsCommon.cpp revision 30b9fdd6a1d607bde20c793af65b5e2e8a1737ca 
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
14SkScalar ScaleFactor(const SkPath& path) {
15    static const SkScalar twoTo10 = 1024.f;
16    SkScalar largest = 0;
17    const SkScalar* oneBounds = &path.getBounds().fLeft;
18    for (int index = 0; index < 4; ++index) {
19        largest = SkTMax(largest, SkScalarAbs(oneBounds[index]));
20    }
21    SkScalar scale = twoTo10;
22    SkScalar next;
23    while ((next = scale * twoTo10) < largest) {
24        scale = next;
25    }
26    return scale == twoTo10 ? SK_Scalar1 : scale;
27}
28
29void ScalePath(const SkPath& path, SkScalar scale, SkPath* scaled) {
30    SkMatrix matrix;
31    matrix.setScale(scale, scale);
32    *scaled = path;
33    scaled->transform(matrix);
34}
35
36const SkOpAngle* AngleWinding(SkOpSpanBase* start, SkOpSpanBase* end, int* windingPtr,
37        bool* sortablePtr) {
38    // find first angle, initialize winding to computed fWindSum
39    SkOpSegment* segment = start->segment();
40    const SkOpAngle* angle = segment->spanToAngle(start, end);
41    if (!angle) {
42        *windingPtr = SK_MinS32;
43        return nullptr;
44    }
45    bool computeWinding = false;
46    const SkOpAngle* firstAngle = angle;
47    bool loop = false;
48    bool unorderable = false;
49    int winding = SK_MinS32;
50    do {
51        angle = angle->next();
52        if (!angle) {
53            return nullptr;
54        }
55        unorderable |= angle->unorderable();
56        if ((computeWinding = unorderable || (angle == firstAngle && loop))) {
57            break;    // if we get here, there's no winding, loop is unorderable
58        }
59        loop |= angle == firstAngle;
60        segment = angle->segment();
61        winding = segment->windSum(angle);
62    } while (winding == SK_MinS32);
63    // if the angle loop contains an unorderable span, the angle order may be useless
64    // directly compute the winding in this case for each span
65    if (computeWinding) {
66        firstAngle = angle;
67        winding = SK_MinS32;
68        do {
69            SkOpSpanBase* startSpan = angle->start();
70            SkOpSpanBase* endSpan = angle->end();
71            SkOpSpan* lesser = startSpan->starter(endSpan);
72            int testWinding = lesser->windSum();
73            if (testWinding == SK_MinS32) {
74                testWinding = lesser->computeWindSum();
75            }
76            if (testWinding != SK_MinS32) {
77                segment = angle->segment();
78                winding = testWinding;
79            }
80            angle = angle->next();
81        } while (angle != firstAngle);
82    }
83    *sortablePtr = !unorderable;
84    *windingPtr = winding;
85    return angle;
86}
87
88SkOpSegment* FindUndone(SkOpContourHead* contourList, SkOpSpanBase** startPtr,
89         SkOpSpanBase** endPtr) {
90    SkOpSegment* result;
91    SkOpContour* contour = contourList;
92    do {
93        result = contour->undoneSegment(startPtr, endPtr);
94        if (result) {
95            return result;
96        }
97    } while ((contour = contour->next()));
98    return nullptr;
99}
100
101SkOpSegment* FindChase(SkTDArray<SkOpSpanBase*>* chase, SkOpSpanBase** startPtr,
102        SkOpSpanBase** endPtr) {
103    while (chase->count()) {
104        SkOpSpanBase* span;
105        chase->pop(&span);
106        SkOpSegment* segment = span->segment();
107        *startPtr = span->ptT()->next()->span();
108        bool done = true;
109        *endPtr = nullptr;
110        if (SkOpAngle* last = segment->activeAngle(*startPtr, startPtr, endPtr, &done)) {
111            *startPtr = last->start();
112            *endPtr = last->end();
113    #if TRY_ROTATE
114            *chase->insert(0) = span;
115    #else
116            *chase->append() = span;
117    #endif
118            return last->segment();
119        }
120        if (done) {
121            continue;
122        }
123        // find first angle, initialize winding to computed wind sum
124        int winding;
125        bool sortable;
126        const SkOpAngle* angle = AngleWinding(*startPtr, *endPtr, &winding, &sortable);
127        if (!angle) {
128            return nullptr;
129        }
130        if (winding == SK_MinS32) {
131            continue;
132        }
133        int sumWinding SK_INIT_TO_AVOID_WARNING;
134        if (sortable) {
135            segment = angle->segment();
136            sumWinding = segment->updateWindingReverse(angle);
137        }
138        SkOpSegment* first = nullptr;
139        const SkOpAngle* firstAngle = angle;
140        while ((angle = angle->next()) != firstAngle) {
141            segment = angle->segment();
142            SkOpSpanBase* start = angle->start();
143            SkOpSpanBase* end = angle->end();
144            int maxWinding SK_INIT_TO_AVOID_WARNING;
145            if (sortable) {
146                segment->setUpWinding(start, end, &maxWinding, &sumWinding);
147            }
148            if (!segment->done(angle)) {
149                if (!first && (sortable || start->starter(end)->windSum() != SK_MinS32)) {
150                    first = segment;
151                    *startPtr = start;
152                    *endPtr = end;
153                }
154                // OPTIMIZATION: should this also add to the chase?
155                if (sortable) {
156                    (void) segment->markAngle(maxWinding, sumWinding, angle);
157                }
158            }
159        }
160        if (first) {
161       #if TRY_ROTATE
162            *chase->insert(0) = span;
163       #else
164            *chase->append() = span;
165       #endif
166            return first;
167        }
168    }
169    return nullptr;
170}
171
172bool SortContourList(SkOpContourHead** contourList, bool evenOdd, bool oppEvenOdd) {
173    SkTDArray<SkOpContour* > list;
174    SkOpContour* contour = *contourList;
175    do {
176        if (contour->count()) {
177            contour->setOppXor(contour->operand() ? evenOdd : oppEvenOdd);
178            *list.append() = contour;
179        }
180    } while ((contour = contour->next()));
181    int count = list.count();
182    if (!count) {
183        return false;
184    }
185    if (count > 1) {
186        SkTQSort<SkOpContour>(list.begin(), list.end() - 1);
187    }
188    contour = list[0];
189    SkOpContourHead* contourHead = static_cast<SkOpContourHead*>(contour);
190    contour->globalState()->setContourHead(contourHead);
191    *contourList = contourHead;
192    for (int index = 1; index < count; ++index) {
193        SkOpContour* next = list[index];
194        contour->setNext(next);
195        contour = next;
196    }
197    contour->setNext(nullptr);
198    return true;
199}
200
201class DistanceLessThan {
202public:
203    DistanceLessThan(double* distances) : fDistances(distances) { }
204    double* fDistances;
205    bool operator()(const int one, const int two) {
206        return fDistances[one] < fDistances[two];
207    }
208};
209
210    /*
211        check start and end of each contour
212        if not the same, record them
213        match them up
214        connect closest
215        reassemble contour pieces into new path
216    */
217void Assemble(const SkPathWriter& path, SkPathWriter* simple) {
218    SkChunkAlloc allocator(4096);  // FIXME: constant-ize, tune
219    SkOpContourHead contour;
220    SkOpGlobalState globalState(&contour, &allocator  SkDEBUGPARAMS(false)
221                                SkDEBUGPARAMS(nullptr));
222#if DEBUG_SHOW_TEST_NAME
223    SkDebugf("</div>\n");
224#endif
225#if DEBUG_PATH_CONSTRUCTION
226    SkDebugf("%s\n", __FUNCTION__);
227#endif
228    SkOpEdgeBuilder builder(path, &contour, &globalState);
229    builder.finish();
230    SkTDArray<const SkOpContour* > runs;  // indices of partial contours
231    const SkOpContour* eContour = builder.head();
232    do {
233        if (!eContour->count()) {
234            continue;
235        }
236        const SkPoint& eStart = eContour->start();
237        const SkPoint& eEnd = eContour->end();
238#if DEBUG_ASSEMBLE
239        SkDebugf("%s contour", __FUNCTION__);
240        if (!SkDPoint::ApproximatelyEqual(eStart, eEnd)) {
241            SkDebugf("[%d]", runs.count());
242        } else {
243            SkDebugf("   ");
244        }
245        SkDebugf(" start=(%1.9g,%1.9g) end=(%1.9g,%1.9g)\n",
246                eStart.fX, eStart.fY, eEnd.fX, eEnd.fY);
247#endif
248        if (SkDPoint::ApproximatelyEqual(eStart, eEnd)) {
249            eContour->toPath(simple);
250            continue;
251        }
252        *runs.append() = eContour;
253    } while ((eContour = eContour->next()));
254    int count = runs.count();
255    if (count == 0) {
256        return;
257    }
258    SkTDArray<int> sLink, eLink;
259    sLink.append(count);
260    eLink.append(count);
261    int rIndex, iIndex;
262    for (rIndex = 0; rIndex < count; ++rIndex) {
263        sLink[rIndex] = eLink[rIndex] = SK_MaxS32;
264    }
265    const int ends = count * 2;  // all starts and ends
266    const int entries = (ends - 1) * count;  // folded triangle : n * (n - 1) / 2
267    SkTDArray<double> distances;
268    distances.append(entries);
269    for (rIndex = 0; rIndex < ends - 1; ++rIndex) {
270        const SkOpContour* oContour = runs[rIndex >> 1];
271        const SkPoint& oPt = rIndex & 1 ? oContour->end() : oContour->start();
272        const int row = rIndex < count - 1 ? rIndex * ends : (ends - rIndex - 2)
273                * ends - rIndex - 1;
274        for (iIndex = rIndex + 1; iIndex < ends; ++iIndex) {
275            const SkOpContour* iContour = runs[iIndex >> 1];
276            const SkPoint& iPt = iIndex & 1 ? iContour->end() : iContour->start();
277            double dx = iPt.fX - oPt.fX;
278            double dy = iPt.fY - oPt.fY;
279            double dist = dx * dx + dy * dy;
280            distances[row + iIndex] = dist;  // oStart distance from iStart
281        }
282    }
283    SkTDArray<int> sortedDist;
284    sortedDist.append(entries);
285    for (rIndex = 0; rIndex < entries; ++rIndex) {
286        sortedDist[rIndex] = rIndex;
287    }
288    SkTQSort<int>(sortedDist.begin(), sortedDist.end() - 1, DistanceLessThan(distances.begin()));
289    int remaining = count;  // number of start/end pairs
290    for (rIndex = 0; rIndex < entries; ++rIndex) {
291        int pair = sortedDist[rIndex];
292        int row = pair / ends;
293        int col = pair - row * ends;
294        int thingOne = row < col ? row : ends - row - 2;
295        int ndxOne = thingOne >> 1;
296        bool endOne = thingOne & 1;
297        int* linkOne = endOne ? eLink.begin() : sLink.begin();
298        if (linkOne[ndxOne] != SK_MaxS32) {
299            continue;
300        }
301        int thingTwo = row < col ? col : ends - row + col - 1;
302        int ndxTwo = thingTwo >> 1;
303        bool endTwo = thingTwo & 1;
304        int* linkTwo = endTwo ? eLink.begin() : sLink.begin();
305        if (linkTwo[ndxTwo] != SK_MaxS32) {
306            continue;
307        }
308        SkASSERT(&linkOne[ndxOne] != &linkTwo[ndxTwo]);
309        bool flip = endOne == endTwo;
310        linkOne[ndxOne] = flip ? ~ndxTwo : ndxTwo;
311        linkTwo[ndxTwo] = flip ? ~ndxOne : ndxOne;
312        if (!--remaining) {
313            break;
314        }
315    }
316    SkASSERT(!remaining);
317#if DEBUG_ASSEMBLE
318    for (rIndex = 0; rIndex < count; ++rIndex) {
319        int s = sLink[rIndex];
320        int e = eLink[rIndex];
321        SkDebugf("%s %c%d <- s%d - e%d -> %c%d\n", __FUNCTION__, s < 0 ? 's' : 'e',
322                s < 0 ? ~s : s, rIndex, rIndex, e < 0 ? 'e' : 's', e < 0 ? ~e : e);
323    }
324#endif
325    rIndex = 0;
326    do {
327        bool forward = true;
328        bool first = true;
329        int sIndex = sLink[rIndex];
330        SkASSERT(sIndex != SK_MaxS32);
331        sLink[rIndex] = SK_MaxS32;
332        int eIndex;
333        if (sIndex < 0) {
334            eIndex = sLink[~sIndex];
335            sLink[~sIndex] = SK_MaxS32;
336        } else {
337            eIndex = eLink[sIndex];
338            eLink[sIndex] = SK_MaxS32;
339        }
340        SkASSERT(eIndex != SK_MaxS32);
341#if DEBUG_ASSEMBLE
342        SkDebugf("%s sIndex=%c%d eIndex=%c%d\n", __FUNCTION__, sIndex < 0 ? 's' : 'e',
343                    sIndex < 0 ? ~sIndex : sIndex, eIndex < 0 ? 's' : 'e',
344                    eIndex < 0 ? ~eIndex : eIndex);
345#endif
346        do {
347            const SkOpContour* contour = runs[rIndex];
348            if (first) {
349                first = false;
350                const SkPoint* startPtr = &contour->start();
351                simple->deferredMove(startPtr[0]);
352            }
353            if (forward) {
354                contour->toPartialForward(simple);
355            } else {
356                contour->toPartialBackward(simple);
357            }
358#if DEBUG_ASSEMBLE
359            SkDebugf("%s rIndex=%d eIndex=%s%d close=%d\n", __FUNCTION__, rIndex,
360                eIndex < 0 ? "~" : "", eIndex < 0 ? ~eIndex : eIndex,
361                sIndex == ((rIndex != eIndex) ^ forward ? eIndex : ~eIndex));
362#endif
363            if (sIndex == ((rIndex != eIndex) ^ forward ? eIndex : ~eIndex)) {
364                simple->close();
365                break;
366            }
367            if (forward) {
368                eIndex = eLink[rIndex];
369                SkASSERT(eIndex != SK_MaxS32);
370                eLink[rIndex] = SK_MaxS32;
371                if (eIndex >= 0) {
372                    SkASSERT(sLink[eIndex] == rIndex);
373                    sLink[eIndex] = SK_MaxS32;
374                } else {
375                    SkASSERT(eLink[~eIndex] == ~rIndex);
376                    eLink[~eIndex] = SK_MaxS32;
377                }
378            } else {
379                eIndex = sLink[rIndex];
380                SkASSERT(eIndex != SK_MaxS32);
381                sLink[rIndex] = SK_MaxS32;
382                if (eIndex >= 0) {
383                    SkASSERT(eLink[eIndex] == rIndex);
384                    eLink[eIndex] = SK_MaxS32;
385                } else {
386                    SkASSERT(sLink[~eIndex] == ~rIndex);
387                    sLink[~eIndex] = SK_MaxS32;
388                }
389            }
390            rIndex = eIndex;
391            if (rIndex < 0) {
392                forward ^= 1;
393                rIndex = ~rIndex;
394            }
395        } while (true);
396        for (rIndex = 0; rIndex < count; ++rIndex) {
397            if (sLink[rIndex] != SK_MaxS32) {
398                break;
399            }
400        }
401    } while (rIndex < count);
402#if DEBUG_ASSEMBLE
403    for (rIndex = 0; rIndex < count; ++rIndex) {
404       SkASSERT(sLink[rIndex] == SK_MaxS32);
405       SkASSERT(eLink[rIndex] == SK_MaxS32);
406    }
407#endif
408}
409
410static void calcAngles(SkOpContourHead* contourList) {
411    SkOpContour* contour = contourList;
412    do {
413        contour->calcAngles();
414    } while ((contour = contour->next()));
415}
416
417static bool missingCoincidence(SkOpContourHead* contourList) {
418    SkOpContour* contour = contourList;
419    bool result = false;
420    do {
421        result |= contour->missingCoincidence();
422    } while ((contour = contour->next()));
423    return result;
424}
425
426static bool moveMultiples(SkOpContourHead* contourList) {
427    SkOpContour* contour = contourList;
428    do {
429        if (!contour->moveMultiples()) {
430            return false;
431        }
432    } while ((contour = contour->next()));
433    return true;
434}
435
436static void moveNearby(SkOpContourHead* contourList) {
437    SkOpContour* contour = contourList;
438    do {
439        contour->moveNearby();
440    } while ((contour = contour->next()));
441}
442
443static void sortAngles(SkOpContourHead* contourList) {
444    SkOpContour* contour = contourList;
445    do {
446        contour->sortAngles();
447    } while ((contour = contour->next()));
448}
449
450bool HandleCoincidence(SkOpContourHead* contourList, SkOpCoincidence* coincidence) {
451    SkOpGlobalState* globalState = contourList->globalState();
452    DEBUG_COINCIDENCE_HEALTH(contourList, "start");
453#if DEBUG_VALIDATE
454    globalState->setPhase(SkOpGlobalState::kIntersecting);
455#endif
456
457    // match up points within the coincident runs
458    if (!coincidence->addExpanded()) {
459        return false;
460    }
461    DEBUG_COINCIDENCE_HEALTH(contourList, "addExpanded");
462#if DEBUG_VALIDATE
463    globalState->setPhase(SkOpGlobalState::kWalking);
464#endif
465    // combine t values when multiple intersections occur on some segments but not others
466    if (!moveMultiples(contourList)) {
467        return false;
468    }
469    DEBUG_COINCIDENCE_HEALTH(contourList, "moveMultiples");
470    // move t values and points together to eliminate small/tiny gaps
471    (void) moveNearby(contourList);
472    DEBUG_COINCIDENCE_HEALTH(contourList, "moveNearby");
473#if DEBUG_VALIDATE
474    globalState->setPhase(SkOpGlobalState::kIntersecting);
475#endif
476    // add coincidence formed by pairing on curve points and endpoints
477    coincidence->correctEnds();
478    if (!coincidence->addEndMovedSpans()) {
479        return false;
480    }
481    DEBUG_COINCIDENCE_HEALTH(contourList, "addEndMovedSpans");
482
483    const int SAFETY_COUNT = 100;  // FIXME: tune
484    int safetyHatch = SAFETY_COUNT;
485    // look for coincidence present in A-B and A-C but missing in B-C
486    while (coincidence->addMissing()) {
487        if (!--safetyHatch) {
488            SkASSERT(globalState->debugSkipAssert());
489            return false;
490        }
491        DEBUG_COINCIDENCE_HEALTH(contourList, "addMissing");
492        moveNearby(contourList);
493        DEBUG_COINCIDENCE_HEALTH(contourList, "moveNearby");
494    }
495    DEBUG_COINCIDENCE_HEALTH(contourList, "addMissing2");
496    // FIXME: only call this if addMissing modified something when returning false
497    moveNearby(contourList);
498    DEBUG_COINCIDENCE_HEALTH(contourList, "moveNearby2");
499    // check to see if, loosely, coincident ranges may be expanded
500    if (coincidence->expand()) {
501        DEBUG_COINCIDENCE_HEALTH(contourList, "expand1");
502        coincidence->addMissing();
503        DEBUG_COINCIDENCE_HEALTH(contourList, "addMissing2");
504        if (!coincidence->addExpanded()) {
505            return false;
506        }
507        DEBUG_COINCIDENCE_HEALTH(contourList, "addExpanded2");
508        if (!moveMultiples(contourList)) {
509            return false;
510        }
511        DEBUG_COINCIDENCE_HEALTH(contourList, "moveMultiples2");
512        moveNearby(contourList);
513    }
514#if DEBUG_VALIDATE
515    globalState->setPhase(SkOpGlobalState::kWalking);
516#endif
517    DEBUG_COINCIDENCE_HEALTH(contourList, "expand2");
518    // the expanded ranges may not align -- add the missing spans
519    if (!coincidence->addExpanded()) {
520        return false;
521    }
522    DEBUG_COINCIDENCE_HEALTH(contourList, "addExpanded3");
523    coincidence->correctEnds();
524    if (!coincidence->mark()) {  // mark spans of coincident segments as coincident
525        return false;
526    }
527    DEBUG_COINCIDENCE_HEALTH(contourList, "mark1");
528    // look for coincidence lines and curves undetected by intersection
529    if (missingCoincidence(contourList)) {
530#if DEBUG_VALIDATE
531        globalState->setPhase(SkOpGlobalState::kIntersecting);
532#endif
533        DEBUG_COINCIDENCE_HEALTH(contourList, "missingCoincidence1");
534        (void) coincidence->expand();
535        DEBUG_COINCIDENCE_HEALTH(contourList, "expand3");
536        if (!coincidence->addExpanded()) {
537            return false;
538        }
539#if DEBUG_VALIDATE
540        globalState->setPhase(SkOpGlobalState::kWalking);
541#endif
542        DEBUG_COINCIDENCE_HEALTH(contourList, "addExpanded3");
543        if (!coincidence->mark()) {
544            return false;
545        }
546    } else {
547        DEBUG_COINCIDENCE_HEALTH(contourList, "missingCoincidence2");
548        (void) coincidence->expand();
549    }
550    DEBUG_COINCIDENCE_HEALTH(contourList, "missingCoincidence3");
551
552    (void) coincidence->expand();
553
554#if 0  // under development
555    // coincident runs may cross two or more spans, but the opposite spans may be out of order
556    if (!coincidence->reorder()) {
557      return false;
558    }
559#endif
560    DEBUG_COINCIDENCE_HEALTH(contourList, "coincidence.reorder");
561    SkOpCoincidence overlaps(globalState);
562    do {
563        SkOpCoincidence* pairs = overlaps.isEmpty() ? coincidence : &overlaps;
564        if (!pairs->apply()) {  // adjust the winding value to account for coincident edges
565            return false;
566        }
567        DEBUG_COINCIDENCE_HEALTH(contourList, "pairs->apply");
568        // For each coincident pair that overlaps another, when the receivers (the 1st of the pair)
569        // are different, construct a new pair to resolve their mutual span
570        if (!pairs->findOverlaps(&overlaps)) {
571            return false;
572        }
573        DEBUG_COINCIDENCE_HEALTH(contourList, "pairs->findOverlaps");
574    } while (!overlaps.isEmpty());
575    calcAngles(contourList);
576    sortAngles(contourList);
577    if (globalState->angleCoincidence()) {
578        (void) missingCoincidence(contourList);
579        if (!coincidence->apply()) {
580            return false;
581        }
582    }
583#if DEBUG_COINCIDENCE_VERBOSE
584    coincidence->debugShowCoincidence();
585#endif
586#if DEBUG_COINCIDENCE
587    coincidence->debugValidate();
588#endif
589    SkPathOpsDebug::ShowActiveSpans(contourList);
590    return true;
591}
592