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