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