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
16SkOpContour* SkOpPtT::contour() const {
17    return segment()->contour();
18}
19
20SkOpGlobalState* SkOpPtT::globalState() const {
21    return contour()->globalState();
22}
23
24void SkOpPtT::init(SkOpSpanBase* span, double t, const SkPoint& pt, bool duplicate) {
25    fT = t;
26    fPt = pt;
27    fSpan = span;
28    fNext = this;
29    fDuplicatePt = duplicate;
30    fDeleted = false;
31    SkDEBUGCODE(fID = span->globalState()->nextPtTID());
32}
33
34bool SkOpPtT::onEnd() const {
35    const SkOpSpanBase* span = this->span();
36    if (span->ptT() != this) {
37        return false;
38    }
39    const SkOpSegment* segment = this->segment();
40    return span == segment->head() || span == segment->tail();
41}
42
43SkOpPtT* SkOpPtT::prev() {
44    SkOpPtT* result = this;
45    SkOpPtT* next = this;
46    while ((next = next->fNext) != this) {
47        result = next;
48    }
49    SkASSERT(result->fNext == this);
50    return result;
51}
52
53SkOpPtT* SkOpPtT::remove() {
54    SkOpPtT* prev = this;
55    do {
56        SkOpPtT* next = prev->fNext;
57        if (next == this) {
58            prev->removeNext(this);
59            SkASSERT(prev->fNext != prev);
60            fDeleted = true;
61            return prev;
62        }
63        prev = next;
64    } while (prev != this);
65    SkASSERT(0);
66    return NULL;
67}
68
69void SkOpPtT::removeNext(SkOpPtT* kept) {
70    SkASSERT(this->fNext);
71    SkOpPtT* next = this->fNext;
72    SkASSERT(this != next->fNext);
73    this->fNext = next->fNext;
74    SkOpSpanBase* span = next->span();
75    next->setDeleted();
76    if (span->ptT() == next) {
77        span->upCast()->detach(kept);
78    }
79}
80
81const SkOpSegment* SkOpPtT::segment() const {
82    return span()->segment();
83}
84
85SkOpSegment* SkOpPtT::segment() {
86    return span()->segment();
87}
88
89void SkOpSpanBase::align() {
90    if (this->fAligned) {
91        return;
92    }
93    SkASSERT(!zero_or_one(this->fPtT.fT));
94    SkASSERT(this->fPtT.next());
95    // if a linked pt/t pair has a t of zero or one, use it as the base for alignment
96    SkOpPtT* ptT = &this->fPtT, * stopPtT = ptT;
97    while ((ptT = ptT->next()) != stopPtT) {
98        if (zero_or_one(ptT->fT)) {
99            SkOpSegment* segment = ptT->segment();
100            SkASSERT(this->segment() != segment);
101            SkASSERT(segment->head()->ptT() == ptT || segment->tail()->ptT() == ptT);
102            if (ptT->fT) {
103                segment->tail()->alignEnd(1, segment->lastPt());
104            } else {
105                segment->head()->alignEnd(0, segment->pts()[0]);
106            }
107            return;
108        }
109    }
110    alignInner();
111    this->fAligned = true;
112}
113
114
115// FIXME: delete spans that collapse
116// delete segments that collapse
117// delete contours that collapse
118void SkOpSpanBase::alignEnd(double t, const SkPoint& pt) {
119    SkASSERT(zero_or_one(t));
120    SkOpSegment* segment = this->segment();
121    SkASSERT(t ? segment->lastPt() == pt : segment->pts()[0] == pt);
122    alignInner();
123    *segment->writablePt(!!t) = pt;
124    SkOpPtT* ptT = &this->fPtT;
125    SkASSERT(t == ptT->fT);
126    SkASSERT(pt == ptT->fPt);
127    SkOpPtT* test = ptT, * stopPtT = ptT;
128    while ((test = test->next()) != stopPtT) {
129        SkOpSegment* other = test->segment();
130        if (other == this->segment()) {
131            continue;
132        }
133        if (!zero_or_one(test->fT)) {
134            continue;
135        }
136        *other->writablePt(!!test->fT) = pt;
137    }
138    this->fAligned = true;
139}
140
141void SkOpSpanBase::alignInner() {
142    // force the spans to share points and t values
143    SkOpPtT* ptT = &this->fPtT, * stopPtT = ptT;
144    const SkPoint& pt = ptT->fPt;
145    do {
146        ptT->fPt = pt;
147        const SkOpSpanBase* span = ptT->span();
148        SkOpPtT* test = ptT;
149        do {
150            SkOpPtT* prev = test;
151            if ((test = test->next()) == stopPtT) {
152                break;
153            }
154            if (span == test->span() && !span->segment()->ptsDisjoint(*ptT, *test)) {
155                // omit aliases that alignment makes redundant
156                if ((!ptT->alias() || test->alias()) && (ptT->onEnd() || !test->onEnd())) {
157                    SkASSERT(test->alias());
158                    prev->removeNext(ptT);
159                    test = prev;
160                } else {
161                    SkASSERT(ptT->alias());
162                    stopPtT = ptT = ptT->remove();
163                    break;
164                }
165            }
166        } while (true);
167    } while ((ptT = ptT->next()) != stopPtT);
168}
169
170bool SkOpSpanBase::contains(const SkOpSpanBase* span) const {
171    const SkOpPtT* start = &fPtT;
172    const SkOpPtT* check = &span->fPtT;
173    SkASSERT(start != check);
174    const SkOpPtT* walk = start;
175    while ((walk = walk->next()) != start) {
176        if (walk == check) {
177            return true;
178        }
179    }
180    return false;
181}
182
183SkOpPtT* SkOpSpanBase::contains(const SkOpSegment* segment) {
184    SkOpPtT* start = &fPtT;
185    SkOpPtT* walk = start;
186    while ((walk = walk->next()) != start) {
187        if (walk->segment() == segment) {
188            return walk;
189        }
190    }
191    return NULL;
192}
193
194bool SkOpSpanBase::containsCoinEnd(const SkOpSegment* segment) const {
195    SkASSERT(this->segment() != segment);
196    const SkOpSpanBase* next = this;
197    while ((next = next->fCoinEnd) != this) {
198        if (next->segment() == segment) {
199            return true;
200        }
201    }
202    return false;
203}
204
205SkOpContour* SkOpSpanBase::contour() const {
206    return segment()->contour();
207}
208
209SkOpGlobalState* SkOpSpanBase::globalState() const {
210    return contour()->globalState();
211}
212
213void SkOpSpanBase::initBase(SkOpSegment* segment, SkOpSpan* prev, double t, const SkPoint& pt) {
214    fSegment = segment;
215    fPtT.init(this, t, pt, false);
216    fCoinEnd = this;
217    fFromAngle = NULL;
218    fPrev = prev;
219    fSpanAdds = 0;
220    fAligned = true;
221    fChased = false;
222    SkDEBUGCODE(fCount = 1);
223    SkDEBUGCODE(fID = globalState()->nextSpanID());
224}
225
226// this pair of spans share a common t value or point; merge them and eliminate duplicates
227// this does not compute the best t or pt value; this merely moves all data into a single list
228void SkOpSpanBase::merge(SkOpSpan* span) {
229    SkOpPtT* spanPtT = span->ptT();
230    SkASSERT(this->t() != spanPtT->fT);
231    SkASSERT(!zero_or_one(spanPtT->fT));
232    span->detach(this->ptT());
233    SkOpPtT* remainder = spanPtT->next();
234    ptT()->insert(spanPtT);
235    while (remainder != spanPtT) {
236        SkOpPtT* next = remainder->next();
237        SkOpPtT* compare = spanPtT->next();
238        while (compare != spanPtT) {
239            SkOpPtT* nextC = compare->next();
240            if (nextC->span() == remainder->span() && nextC->fT == remainder->fT) {
241                goto tryNextRemainder;
242            }
243            compare = nextC;
244        }
245        spanPtT->insert(remainder);
246tryNextRemainder:
247        remainder = next;
248    }
249    fSpanAdds += span->fSpanAdds;
250}
251
252int SkOpSpan::computeWindSum() {
253    SkOpGlobalState* globals = this->globalState();
254    SkOpContour* contourHead = globals->contourHead();
255    int windTry = 0;
256    while (!this->sortableTop(contourHead) && ++windTry < SkOpGlobalState::kMaxWindingTries) {
257        ;
258    }
259    return this->windSum();
260}
261
262bool SkOpSpan::containsCoincidence(const SkOpSegment* segment) const {
263    SkASSERT(this->segment() != segment);
264    const SkOpSpan* next = fCoincident;
265    do {
266        if (next->segment() == segment) {
267            return true;
268        }
269    } while ((next = next->fCoincident) != this);
270    return false;
271}
272
273void SkOpSpan::detach(SkOpPtT* kept) {
274    SkASSERT(!final());
275    SkOpSpan* prev = this->prev();
276    SkASSERT(prev);
277    SkOpSpanBase* next = this->next();
278    SkASSERT(next);
279    prev->setNext(next);
280    next->setPrev(prev);
281    this->segment()->detach(this);
282    this->globalState()->coincidence()->fixUp(this->ptT(), kept);
283    this->ptT()->setDeleted();
284}
285
286void SkOpSpan::init(SkOpSegment* segment, SkOpSpan* prev, double t, const SkPoint& pt) {
287    SkASSERT(t != 1);
288    initBase(segment, prev, t, pt);
289    fCoincident = this;
290    fToAngle = NULL;
291    fWindSum = fOppSum = SK_MinS32;
292    fWindValue = 1;
293    fOppValue = 0;
294    fTopTTry = 0;
295    fChased = fDone = false;
296    segment->bumpCount();
297}
298
299void SkOpSpan::setOppSum(int oppSum) {
300    SkASSERT(!final());
301    if (fOppSum != SK_MinS32 && fOppSum != oppSum) {
302        this->globalState()->setWindingFailed();
303        return;
304    }
305    SkASSERT(!DEBUG_LIMIT_WIND_SUM || abs(oppSum) <= DEBUG_LIMIT_WIND_SUM);
306    fOppSum = oppSum;
307}
308
309void SkOpSpan::setWindSum(int windSum) {
310    SkASSERT(!final());
311    if (fWindSum != SK_MinS32 && fWindSum != windSum) {
312        this->globalState()->setWindingFailed();
313        return;
314    }
315    SkASSERT(!DEBUG_LIMIT_WIND_SUM || abs(windSum) <= DEBUG_LIMIT_WIND_SUM);
316    fWindSum = windSum;
317}
318