SkOpSpan.cpp revision e7bb5b226662f01c91574b29f435acae71c76c46 
1/*
2 * Copyright 2014 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 "SkOpCoincidence.h"
8#include "SkOpContour.h"
9#include "SkOpSegment.h"
10#include "SkPathWriter.h"
11
12bool SkOpPtT::alias() const {
13    return this->span()->ptT() != this;
14}
15
16const SkOpPtT* SkOpPtT::active() const {
17    if (!fDeleted) {
18        return this;
19    }
20    const SkOpPtT* ptT = this;
21    const SkOpPtT* stopPtT = ptT;
22    while ((ptT = ptT->next()) != stopPtT) {
23        if (ptT->fSpan == fSpan && !ptT->fDeleted) {
24            return ptT;
25        }
26    }
27    SkASSERT(0);  // should never return deleted
28    return this;
29}
30
31bool SkOpPtT::collapsed(const SkOpPtT* check) const {
32    if (fPt != check->fPt) {
33        return false;
34    }
35    SkASSERT(this != check);
36    const SkOpSegment* segment = this->segment();
37    SkASSERT(segment == check->segment());
38    return segment->collapsed();
39}
40
41bool SkOpPtT::contains(const SkOpPtT* check) const {
42    SkOPASSERT(this != check);
43    const SkOpPtT* ptT = this;
44    const SkOpPtT* stopPtT = ptT;
45    while ((ptT = ptT->next()) != stopPtT) {
46        if (ptT == check) {
47            return true;
48        }
49    }
50    return false;
51}
52
53bool SkOpPtT::contains(const SkOpSegment* segment, const SkPoint& pt) const {
54    SkASSERT(this->segment() != segment);
55    const SkOpPtT* ptT = this;
56    const SkOpPtT* stopPtT = ptT;
57    while ((ptT = ptT->next()) != stopPtT) {
58        if (ptT->fPt == pt && ptT->segment() == segment) {
59            return true;
60        }
61    }
62    return false;
63}
64
65bool SkOpPtT::contains(const SkOpSegment* segment, double t) const {
66    const SkOpPtT* ptT = this;
67    const SkOpPtT* stopPtT = ptT;
68    while ((ptT = ptT->next()) != stopPtT) {
69        if (ptT->fT == t && ptT->segment() == segment) {
70            return true;
71        }
72    }
73    return false;
74}
75
76const SkOpPtT* SkOpPtT::contains(const SkOpSegment* check) const {
77    SkASSERT(this->segment() != check);
78    const SkOpPtT* ptT = this;
79    const SkOpPtT* stopPtT = ptT;
80    while ((ptT = ptT->next()) != stopPtT) {
81        if (ptT->segment() == check && !ptT->deleted()) {
82            return ptT;
83        }
84    }
85    return nullptr;
86}
87
88SkOpContour* SkOpPtT::contour() const {
89    return segment()->contour();
90}
91
92const SkOpPtT* SkOpPtT::find(const SkOpSegment* segment) const {
93    const SkOpPtT* ptT = this;
94    const SkOpPtT* stopPtT = ptT;
95    do {
96        if (ptT->segment() == segment && !ptT->deleted()) {
97            return ptT;
98        }
99        ptT = ptT->fNext;
100    } while (stopPtT != ptT);
101//    SkASSERT(0);
102    return nullptr;
103}
104
105SkOpGlobalState* SkOpPtT::globalState() const {
106    return contour()->globalState();
107}
108
109void SkOpPtT::init(SkOpSpanBase* span, double t, const SkPoint& pt, bool duplicate) {
110    fT = t;
111    fPt = pt;
112    fSpan = span;
113    fNext = this;
114    fDuplicatePt = duplicate;
115    fDeleted = false;
116    fCoincident = false;
117    SkDEBUGCODE(fID = span->globalState()->nextPtTID());
118}
119
120bool SkOpPtT::onEnd() const {
121    const SkOpSpanBase* span = this->span();
122    if (span->ptT() != this) {
123        return false;
124    }
125    const SkOpSegment* segment = this->segment();
126    return span == segment->head() || span == segment->tail();
127}
128
129bool SkOpPtT::ptAlreadySeen(const SkOpPtT* check) const {
130    while (this != check) {
131        if (this->fPt == check->fPt) {
132            return true;
133        }
134        check = check->fNext;
135    }
136    return false;
137}
138
139SkOpPtT* SkOpPtT::prev() {
140    SkOpPtT* result = this;
141    SkOpPtT* next = this;
142    while ((next = next->fNext) != this) {
143        result = next;
144    }
145    SkASSERT(result->fNext == this);
146    return result;
147}
148
149SkOpPtT* SkOpPtT::remove(const SkOpPtT* kept) {
150    SkOpPtT* prev = this;
151    do {
152        SkOpPtT* next = prev->fNext;
153        if (next == this) {
154            prev->removeNext(kept);
155            SkASSERT(prev->fNext != prev);
156            fDeleted = true;
157            return prev;
158        }
159        prev = next;
160    } while (prev != this);
161    SkASSERT(0);
162    return nullptr;
163}
164
165void SkOpPtT::removeNext(const SkOpPtT* kept) {
166    SkASSERT(this->fNext);
167    SkOpPtT* next = this->fNext;
168    SkASSERT(this != next->fNext);
169    this->fNext = next->fNext;
170    SkOpSpanBase* span = next->span();
171    SkOpCoincidence* coincidence = span->globalState()->coincidence();
172    if (coincidence) {
173        coincidence->fixUp(next, kept);
174    }
175    next->setDeleted();
176    if (span->ptT() == next) {
177        span->upCast()->release(kept);
178    }
179}
180
181const SkOpSegment* SkOpPtT::segment() const {
182    return span()->segment();
183}
184
185SkOpSegment* SkOpPtT::segment() {
186    return span()->segment();
187}
188
189void SkOpPtT::setDeleted() {
190    SkASSERT(this->span()->debugDeleted() || this->span()->ptT() != this);
191    SkOPASSERT(!fDeleted);
192    fDeleted = true;
193}
194
195void SkOpSpanBase::addOpp(SkOpSpanBase* opp) {
196    SkOpPtT* oppPrev = this->ptT()->oppPrev(opp->ptT());
197    if (!oppPrev) {
198        return;
199    }
200    this->mergeMatches(opp);
201    this->ptT()->addOpp(opp->ptT(), oppPrev);
202    this->checkForCollapsedCoincidence();
203}
204
205// Please keep this in sync with debugMergeContained()
206void SkOpSpanBase::mergeContained(const SkPathOpsBounds& bounds) {
207    // while adjacent spans' points are contained by the bounds, merge them
208    SkOpSpanBase* prev = this;
209    SkOpSegment* seg = this->segment();
210    while ((prev = prev->prev()) && bounds.contains(prev->pt()) && !seg->ptsDisjoint(prev, this)) {
211        this->mergeMatches(prev);
212        this->addOpp(prev);
213    }
214    SkOpSpanBase* next = this;
215    while (next->upCastable() && (next = next->upCast()->next())
216            && bounds.contains(next->pt()) && !seg->ptsDisjoint(this, next)) {
217        this->mergeMatches(next);
218        this->addOpp(next);
219    }
220#if DEBUG_COINCIDENCE
221    this->globalState()->coincidence()->debugValidate();
222#endif
223}
224
225bool SkOpSpanBase::collapsed(double s, double e) const {
226    const SkOpPtT* start = &fPtT;
227    const SkOpPtT* walk = start;
228    double min = walk->fT;
229    double max = min;
230    const SkOpSegment* segment = this->segment();
231    while ((walk = walk->next()) != start) {
232        if (walk->segment() != segment) {
233            continue;
234        }
235        min = SkTMin(min, walk->fT);
236        max = SkTMax(max, walk->fT);
237        if (between(min, s, max) && between(min, e, max)) {
238            return true;
239        }
240    }
241    return false;
242}
243
244bool SkOpSpanBase::contains(const SkOpSpanBase* span) const {
245    const SkOpPtT* start = &fPtT;
246    const SkOpPtT* check = &span->fPtT;
247    SkOPASSERT(start != check);
248    const SkOpPtT* walk = start;
249    while ((walk = walk->next()) != start) {
250        if (walk == check) {
251            return true;
252        }
253    }
254    return false;
255}
256
257const SkOpPtT* SkOpSpanBase::contains(const SkOpSegment* segment) const {
258    const SkOpPtT* start = &fPtT;
259    const SkOpPtT* walk = start;
260    while ((walk = walk->next()) != start) {
261        if (walk->deleted()) {
262            continue;
263        }
264        if (walk->segment() == segment && walk->span()->ptT() == walk) {
265            return walk;
266        }
267    }
268    return nullptr;
269}
270
271bool SkOpSpanBase::containsCoinEnd(const SkOpSegment* segment) const {
272    SkASSERT(this->segment() != segment);
273    const SkOpSpanBase* next = this;
274    while ((next = next->fCoinEnd) != this) {
275        if (next->segment() == segment) {
276            return true;
277        }
278    }
279    return false;
280}
281
282SkOpContour* SkOpSpanBase::contour() const {
283    return segment()->contour();
284}
285
286SkOpGlobalState* SkOpSpanBase::globalState() const {
287    return contour()->globalState();
288}
289
290void SkOpSpanBase::initBase(SkOpSegment* segment, SkOpSpan* prev, double t, const SkPoint& pt) {
291    fSegment = segment;
292    fPtT.init(this, t, pt, false);
293    fCoinEnd = this;
294    fFromAngle = nullptr;
295    fPrev = prev;
296    fSpanAdds = 0;
297    fAligned = true;
298    fChased = false;
299    SkDEBUGCODE(fCount = 1);
300    SkDEBUGCODE(fID = globalState()->nextSpanID());
301    SkDEBUGCODE(fDebugDeleted = false);
302}
303
304// this pair of spans share a common t value or point; merge them and eliminate duplicates
305// this does not compute the best t or pt value; this merely moves all data into a single list
306void SkOpSpanBase::merge(SkOpSpan* span) {
307    SkOpPtT* spanPtT = span->ptT();
308    SkASSERT(this->t() != spanPtT->fT);
309    SkASSERT(!zero_or_one(spanPtT->fT));
310    span->release(this->ptT());
311    if (this->contains(span)) {
312        SkOPASSERT(0);  // check to see if this ever happens -- should have been found earlier
313        return;  // merge is already in the ptT loop
314    }
315    SkOpPtT* remainder = spanPtT->next();
316    this->ptT()->insert(spanPtT);
317    while (remainder != spanPtT) {
318        SkOpPtT* next = remainder->next();
319        SkOpPtT* compare = spanPtT->next();
320        while (compare != spanPtT) {
321            SkOpPtT* nextC = compare->next();
322            if (nextC->span() == remainder->span() && nextC->fT == remainder->fT) {
323                goto tryNextRemainder;
324            }
325            compare = nextC;
326        }
327        spanPtT->insert(remainder);
328tryNextRemainder:
329        remainder = next;
330    }
331    fSpanAdds += span->fSpanAdds;
332}
333
334SkOpSpanBase* SkOpSpanBase::active() {
335    SkOpSpanBase* result = fPrev ? fPrev->next() : upCast()->next()->prev();
336    SkASSERT(this == result || fDebugDeleted);
337    return result;
338}
339
340// please keep in sync with debugCheckForCollapsedCoincidence()
341void SkOpSpanBase::checkForCollapsedCoincidence() {
342    SkOpCoincidence* coins = this->globalState()->coincidence();
343    if (coins->isEmpty()) {
344        return;
345    }
346// the insert above may have put both ends of a coincident run in the same span
347// for each coincident ptT in loop; see if its opposite in is also in the loop
348// this implementation is the motivation for marking that a ptT is referenced by a coincident span
349    SkOpPtT* head = this->ptT();
350    SkOpPtT* test = head;
351    do {
352        if (!test->coincident()) {
353            continue;
354        }
355        coins->markCollapsed(test);
356    } while ((test = test->next()) != head);
357    coins->releaseDeleted();
358}
359
360// please keep in sync with debugMergeMatches()
361// Look to see if pt-t linked list contains same segment more than once
362// if so, and if each pt-t is directly pointed to by spans in that segment,
363// merge them
364// keep the points, but remove spans so that the segment doesn't have 2 or more
365// spans pointing to the same pt-t loop at different loop elements
366void SkOpSpanBase::mergeMatches(SkOpSpanBase* opp) {
367    SkOpPtT* test = &fPtT;
368    SkOpPtT* testNext;
369    const SkOpPtT* stop = test;
370    do {
371        testNext = test->next();
372        if (test->deleted()) {
373            continue;
374        }
375        SkOpSpanBase* testBase = test->span();
376        SkASSERT(testBase->ptT() == test);
377        SkOpSegment* segment = test->segment();
378        if (segment->done()) {
379            continue;
380        }
381        SkOpPtT* inner = opp->ptT();
382        const SkOpPtT* innerStop = inner;
383        do {
384            if (inner->segment() != segment) {
385                continue;
386            }
387            if (inner->deleted()) {
388                continue;
389            }
390            SkOpSpanBase* innerBase = inner->span();
391            SkASSERT(innerBase->ptT() == inner);
392            // when the intersection is first detected, the span base is marked if there are
393            // more than one point in the intersection.
394            if (!zero_or_one(inner->fT)) {
395                innerBase->upCast()->release(test);
396            } else {
397                SkOPASSERT(inner->fT != test->fT);
398                if (!zero_or_one(test->fT)) {
399                    testBase->upCast()->release(inner);
400                } else {
401                    segment->markAllDone();  // mark segment as collapsed
402                    SkDEBUGCODE(testBase->debugSetDeleted());
403                    test->setDeleted();
404                    SkDEBUGCODE(innerBase->debugSetDeleted());
405                    inner->setDeleted();
406                }
407            }
408#ifdef SK_DEBUG   // assert if another undeleted entry points to segment
409            const SkOpPtT* debugInner = inner;
410            while ((debugInner = debugInner->next()) != innerStop) {
411                if (debugInner->segment() != segment) {
412                    continue;
413                }
414                if (debugInner->deleted()) {
415                    continue;
416                }
417                SkOPASSERT(0);
418            }
419#endif
420            break;
421        } while ((inner = inner->next()) != innerStop);
422    } while ((test = testNext) != stop);
423    this->checkForCollapsedCoincidence();
424}
425
426int SkOpSpan::computeWindSum() {
427    SkOpGlobalState* globals = this->globalState();
428    SkOpContour* contourHead = globals->contourHead();
429    int windTry = 0;
430    while (!this->sortableTop(contourHead) && ++windTry < SkOpGlobalState::kMaxWindingTries) {
431        ;
432    }
433    return this->windSum();
434}
435
436bool SkOpSpan::containsCoincidence(const SkOpSegment* segment) const {
437    SkASSERT(this->segment() != segment);
438    const SkOpSpan* next = fCoincident;
439    do {
440        if (next->segment() == segment) {
441            return true;
442        }
443    } while ((next = next->fCoincident) != this);
444    return false;
445}
446
447void SkOpSpan::init(SkOpSegment* segment, SkOpSpan* prev, double t, const SkPoint& pt) {
448    SkASSERT(t != 1);
449    initBase(segment, prev, t, pt);
450    fCoincident = this;
451    fToAngle = nullptr;
452    fWindSum = fOppSum = SK_MinS32;
453    fWindValue = 1;
454    fOppValue = 0;
455    fTopTTry = 0;
456    fChased = fDone = false;
457    segment->bumpCount();
458    fAlreadyAdded = false;
459}
460
461// Please keep this in sync with debugInsertCoincidence()
462bool SkOpSpan::insertCoincidence(const SkOpSegment* segment, bool flipped, bool ordered) {
463    if (this->containsCoincidence(segment)) {
464        return true;
465    }
466    SkOpPtT* next = &fPtT;
467    while ((next = next->next()) != &fPtT) {
468        if (next->segment() == segment) {
469            SkOpSpan* span;
470            SkOpSpanBase* base = next->span();
471            if (!ordered) {
472                const SkOpSpanBase* spanEnd = fNext->contains(segment)->span();
473                const SkOpPtT* start = base->ptT()->starter(spanEnd->ptT());
474                FAIL_IF(!start->span()->upCastable());
475                span = const_cast<SkOpSpan*>(start->span()->upCast());
476            } else if (flipped) {
477                span = base->prev();
478                FAIL_IF(!span);
479            } else {
480                FAIL_IF(!base->upCastable());
481                span = base->upCast();
482            }
483            this->insertCoincidence(span);
484            return true;
485        }
486    }
487#if DEBUG_COINCIDENCE
488    SkASSERT(0); // FIXME? if we get here, the span is missing its opposite segment...
489#endif
490    return true;
491}
492
493void SkOpSpan::release(const SkOpPtT* kept) {
494    SkDEBUGCODE(fDebugDeleted = true);
495    SkOPASSERT(kept->span() != this);
496    SkASSERT(!final());
497    SkOpSpan* prev = this->prev();
498    SkASSERT(prev);
499    SkOpSpanBase* next = this->next();
500    SkASSERT(next);
501    prev->setNext(next);
502    next->setPrev(prev);
503    this->segment()->release(this);
504    SkOpCoincidence* coincidence = this->globalState()->coincidence();
505    if (coincidence) {
506        coincidence->fixUp(this->ptT(), kept);
507    }
508    this->ptT()->setDeleted();
509    SkOpPtT* stopPtT = this->ptT();
510    SkOpPtT* testPtT = stopPtT;
511    const SkOpSpanBase* keptSpan = kept->span();
512    do {
513        if (this == testPtT->span()) {
514            testPtT->setSpan(keptSpan);
515        }
516    } while ((testPtT = testPtT->next()) != stopPtT);
517}
518
519void SkOpSpan::setOppSum(int oppSum) {
520    SkASSERT(!final());
521    if (fOppSum != SK_MinS32 && fOppSum != oppSum) {
522        this->globalState()->setWindingFailed();
523        return;
524    }
525    SkASSERT(!DEBUG_LIMIT_WIND_SUM || SkTAbs(oppSum) <= DEBUG_LIMIT_WIND_SUM);
526    fOppSum = oppSum;
527}
528
529void SkOpSpan::setWindSum(int windSum) {
530    SkASSERT(!final());
531    if (fWindSum != SK_MinS32 && fWindSum != windSum) {
532        this->globalState()->setWindingFailed();
533        return;
534    }
535    SkASSERT(!DEBUG_LIMIT_WIND_SUM || SkTAbs(windSum) <= DEBUG_LIMIT_WIND_SUM);
536    fWindSum = windSum;
537}
538