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 PATH_OPS_DEBUG_RELEASE(contour()->globalState(), NULL);
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    PATH_OPS_DEBUG_CODE(fID = ++span->globalState()->fPtTID);
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::remove() {
44    SkOpPtT* prev = this;
45    do {
46        SkOpPtT* next = prev->fNext;
47        if (next == this) {
48            prev->removeNext(this);
49            fDeleted = true;
50            return prev;
51        }
52        prev = next;
53    } while (prev != this);
54    SkASSERT(0);
55    return NULL;
56}
57
58void SkOpPtT::removeNext(SkOpPtT* kept) {
59    SkASSERT(this->fNext);
60    SkOpPtT* next = this->fNext;
61    this->fNext = next->fNext;
62    SkOpSpanBase* span = next->span();
63    next->setDeleted();
64    if (span->ptT() == next) {
65        span->upCast()->detach(kept);
66    }
67}
68
69const SkOpSegment* SkOpPtT::segment() const {
70    return span()->segment();
71}
72
73SkOpSegment* SkOpPtT::segment() {
74    return span()->segment();
75}
76
77// find the starting or ending span with an existing loop of angles
78// OPTIMIZE? remove the spans pointing to windValue==0 here or earlier?
79// FIXME? assert that only one other span has a valid windValue or oppValue
80void SkOpSpanBase::addSimpleAngle(bool checkFrom, SkChunkAlloc* allocator) {
81    SkOpAngle* angle;
82    if (checkFrom) {
83        SkASSERT(this->final());
84        if (this->fromAngle()) {
85            SkASSERT(this->fromAngle()->loopCount() == 2);
86            return;
87        }
88        angle = this->segment()->addEndSpan(allocator);
89    } else {
90        SkASSERT(this->t() == 0);
91        SkOpSpan* span = this->upCast();
92        if (span->toAngle()) {
93            SkASSERT(span->toAngle()->loopCount() == 2);
94            SkASSERT(!span->fromAngle());
95            span->setFromAngle(span->toAngle()->next());
96            return;
97        }
98        angle = this->segment()->addStartSpan(allocator);
99    }
100    SkOpPtT* ptT = this->ptT();
101    SkOpSpanBase* oSpanBase;
102    SkOpSpan* oSpan;
103    SkOpSegment* other;
104    do {
105        ptT = ptT->next();
106        oSpanBase = ptT->span();
107        oSpan = oSpanBase->upCastable();
108        other = oSpanBase->segment();
109        if (oSpan && oSpan->windValue()) {
110            break;
111        }
112        if (oSpanBase->t() == 0) {
113            continue;
114        }
115        SkOpSpan* oFromSpan = oSpanBase->prev();
116        SkASSERT(oFromSpan->t() < 1);
117        if (oFromSpan->windValue()) {
118            break;
119        }
120    } while (ptT != this->ptT());
121    SkOpAngle* oAngle;
122    if (checkFrom) {
123        oAngle = other->addStartSpan(allocator);
124        SkASSERT(oSpan && !oSpan->final());
125        SkASSERT(oAngle == oSpan->toAngle());
126    } else {
127        oAngle = other->addEndSpan(allocator);
128        SkASSERT(oAngle == oSpanBase->fromAngle());
129    }
130    angle->insert(oAngle);
131}
132
133void SkOpSpanBase::align() {
134    if (this->fAligned) {
135        return;
136    }
137    SkASSERT(!zero_or_one(this->fPtT.fT));
138    SkASSERT(this->fPtT.next());
139    // if a linked pt/t pair has a t of zero or one, use it as the base for alignment
140    SkOpPtT* ptT = &this->fPtT, * stopPtT = ptT;
141    while ((ptT = ptT->next()) != stopPtT) {
142        if (zero_or_one(ptT->fT)) {
143            SkOpSegment* segment = ptT->segment();
144            SkASSERT(this->segment() != segment);
145            SkASSERT(segment->head()->ptT() == ptT || segment->tail()->ptT() == ptT);
146            if (ptT->fT) {
147                segment->tail()->alignEnd(1, segment->lastPt());
148            } else {
149                segment->head()->alignEnd(0, segment->pts()[0]);
150            }
151            return;
152        }
153    }
154    alignInner();
155    this->fAligned = true;
156}
157
158
159// FIXME: delete spans that collapse
160// delete segments that collapse
161// delete contours that collapse
162void SkOpSpanBase::alignEnd(double t, const SkPoint& pt) {
163    SkASSERT(zero_or_one(t));
164    SkOpSegment* segment = this->segment();
165    SkASSERT(t ? segment->lastPt() == pt : segment->pts()[0] == pt);
166    alignInner();
167    *segment->writablePt(!!t) = pt;
168    SkOpPtT* ptT = &this->fPtT;
169    SkASSERT(t == ptT->fT);
170    SkASSERT(pt == ptT->fPt);
171    SkOpPtT* test = ptT, * stopPtT = ptT;
172    while ((test = test->next()) != stopPtT) {
173        SkOpSegment* other = test->segment();
174        if (other == this->segment()) {
175            continue;
176        }
177        if (!zero_or_one(test->fT)) {
178            continue;
179        }
180        *other->writablePt(!!test->fT) = pt;
181    }
182    this->fAligned = true;
183}
184
185void SkOpSpanBase::alignInner() {
186    // force the spans to share points and t values
187    SkOpPtT* ptT = &this->fPtT, * stopPtT = ptT;
188    const SkPoint& pt = ptT->fPt;
189    do {
190        ptT->fPt = pt;
191        const SkOpSpanBase* span = ptT->span();
192        SkOpPtT* test = ptT;
193        do {
194            SkOpPtT* prev = test;
195            if ((test = test->next()) == stopPtT) {
196                break;
197            }
198            if (span == test->span() && !span->segment()->ptsDisjoint(*ptT, *test)) {
199                // omit aliases that alignment makes redundant
200                if ((!ptT->alias() || test->alias()) && (ptT->onEnd() || !test->onEnd())) {
201                    SkASSERT(test->alias());
202                    prev->removeNext(ptT);
203                    test = prev;
204                } else {
205                    SkASSERT(ptT->alias());
206                    stopPtT = ptT = ptT->remove();
207                    break;
208                }
209            }
210        } while (true);
211    } while ((ptT = ptT->next()) != stopPtT);
212}
213
214bool SkOpSpanBase::contains(const SkOpSpanBase* span) const {
215    const SkOpPtT* start = &fPtT;
216    const SkOpPtT* check = &span->fPtT;
217    SkASSERT(start != check);
218    const SkOpPtT* walk = start;
219    while ((walk = walk->next()) != start) {
220        if (walk == check) {
221            return true;
222        }
223    }
224    return false;
225}
226
227bool SkOpSpanBase::containsCoinEnd(const SkOpSegment* segment) const {
228    SkASSERT(this->segment() != segment);
229    const SkOpSpanBase* next = this;
230    while ((next = next->fCoinEnd) != this) {
231        if (next->segment() == segment) {
232            return true;
233        }
234    }
235    return false;
236}
237
238SkOpContour* SkOpSpanBase::contour() const {
239    return segment()->contour();
240}
241
242SkOpGlobalState* SkOpSpanBase::globalState() const {
243    return PATH_OPS_DEBUG_RELEASE(contour()->globalState(), NULL);
244}
245
246void SkOpSpanBase::initBase(SkOpSegment* segment, SkOpSpan* prev, double t, const SkPoint& pt) {
247    fSegment = segment;
248    fPtT.init(this, t, pt, false);
249    fCoinEnd = this;
250    fFromAngle = NULL;
251    fPrev = prev;
252    fAligned = true;
253    fChased = false;
254    PATH_OPS_DEBUG_CODE(fCount = 1);
255    PATH_OPS_DEBUG_CODE(fID = ++globalState()->fSpanID);
256}
257
258// this pair of spans share a common t value or point; merge them and eliminate duplicates
259// this does not compute the best t or pt value; this merely moves all data into a single list
260void SkOpSpanBase::merge(SkOpSpan* span) {
261    SkOpPtT* spanPtT = span->ptT();
262    SkASSERT(this->t() != spanPtT->fT);
263    SkASSERT(!zero_or_one(spanPtT->fT));
264    span->detach(this->ptT());
265    SkOpPtT* remainder = spanPtT->next();
266    ptT()->insert(spanPtT);
267    while (remainder != spanPtT) {
268        SkOpPtT* next = remainder->next();
269        SkOpPtT* compare = spanPtT->next();
270        while (compare != spanPtT) {
271            SkOpPtT* nextC = compare->next();
272            if (nextC->span() == remainder->span() && nextC->fT == remainder->fT) {
273                goto tryNextRemainder;
274            }
275            compare = nextC;
276        }
277        spanPtT->insert(remainder);
278tryNextRemainder:
279        remainder = next;
280    }
281}
282
283void SkOpSpanBase::mergeBaseAttributes(SkOpSpanBase* span) {
284    SkASSERT(!span->fChased);
285    SkASSERT(!span->fFromAngle);
286    if (this->upCastable() && span->upCastable()) {
287        this->upCast()->mergeAttributes(span->upCast());
288    }
289}
290
291void SkOpSpan::applyCoincidence(SkOpSpan* opp) {
292    SkASSERT(!final());
293    SkASSERT(0);  // incomplete
294}
295
296bool SkOpSpan::containsCoincidence(const SkOpSegment* segment) const {
297    SkASSERT(this->segment() != segment);
298    const SkOpSpan* next = this;
299    while ((next = next->fCoincident) != this) {
300        if (next->segment() == segment) {
301            return true;
302        }
303    }
304    return false;
305}
306
307void SkOpSpan::detach(SkOpPtT* kept) {
308    SkASSERT(!final());
309    SkOpSpan* prev = this->prev();
310    SkASSERT(prev);
311    SkOpSpanBase* next = this->next();
312    SkASSERT(next);
313    prev->setNext(next);
314    next->setPrev(prev);
315    this->segment()->detach(this);
316    if (this->coincident()) {
317        this->globalState()->fCoincidence->fixUp(this->ptT(), kept);
318    }
319    this->ptT()->setDeleted();
320}
321
322void SkOpSpan::init(SkOpSegment* segment, SkOpSpan* prev, double t, const SkPoint& pt) {
323    SkASSERT(t != 1);
324    initBase(segment, prev, t, pt);
325    fCoincident = this;
326    fToAngle = NULL;
327    fWindSum = fOppSum = SK_MinS32;
328    fWindValue = 1;
329    fOppValue = 0;
330    fChased = fDone = false;
331    segment->bumpCount();
332}
333
334void SkOpSpan::mergeAttributes(SkOpSpan* span) {
335    SkASSERT(!span->fToAngle);
336    if (span->fCoincident) {
337        this->insertCoincidence(span);
338    }
339}
340
341void SkOpCoincidence::add(SkOpPtT* coinPtTStart, SkOpPtT* coinPtTEnd, SkOpPtT* oppPtTStart,
342        SkOpPtT* oppPtTEnd, bool flipped, SkChunkAlloc* allocator) {
343    SkCoincidentSpans* coinRec = SkOpTAllocator<SkCoincidentSpans>::Allocate(allocator);
344    SkOpSpanBase* coinEnd = coinPtTEnd->span();
345    SkOpSpanBase* oppEnd = oppPtTEnd->span();
346    SkOpSpan* coinStart = coinPtTStart->span()->upCast();
347    SkASSERT(coinStart == coinStart->starter(coinEnd));
348    SkOpSpan* oppStart = (flipped ? oppPtTEnd : oppPtTStart)->span()->upCast();
349    SkASSERT(oppStart == oppStart->starter(oppEnd));
350    coinStart->insertCoincidence(oppStart);
351    coinEnd->insertCoinEnd(oppEnd);
352    coinRec->fNext = this->fHead;
353    coinRec->fCoinPtTStart = coinPtTStart;
354    coinRec->fCoinPtTEnd = coinPtTEnd;
355    coinRec->fOppPtTStart = oppPtTStart;
356    coinRec->fOppPtTEnd = oppPtTEnd;
357    coinRec->fFlipped = flipped;
358    this->fHead = coinRec;
359}
360
361bool SkOpCoincidence::contains(SkOpPtT* coinPtTStart, SkOpPtT* coinPtTEnd, SkOpPtT* oppPtTStart,
362        SkOpPtT* oppPtTEnd, bool flipped) {
363    SkCoincidentSpans* coin = fHead;
364    if (!coin) {
365        return false;
366    }
367    do {
368        if (coin->fCoinPtTStart == coinPtTStart &&  coin->fCoinPtTEnd == coinPtTEnd
369                && coin->fOppPtTStart == oppPtTStart && coin->fOppPtTEnd == oppPtTEnd
370                && coin->fFlipped == flipped) {
371            return true;
372        }
373    } while ((coin = coin->fNext));
374    return false;
375}
376
377// walk span sets in parallel, moving winding from one to the other
378void SkOpCoincidence::apply() {
379    SkCoincidentSpans* coin = fHead;
380    if (!coin) {
381        return;
382    }
383    do {
384        SkOpSpanBase* end = coin->fCoinPtTEnd->span();
385        SkOpSpan* start = coin->fCoinPtTStart->span()->upCast();
386        SkASSERT(start == start->starter(end));
387        bool flipped = coin->fFlipped;
388        SkOpSpanBase* oEnd = (flipped ? coin->fOppPtTStart : coin->fOppPtTEnd)->span();
389        SkOpSpan* oStart = (flipped ? coin->fOppPtTEnd : coin->fOppPtTStart)->span()->upCast();
390        SkASSERT(oStart == oStart->starter(oEnd));
391        SkOpSegment* segment = start->segment();
392        SkOpSegment* oSegment = oStart->segment();
393        bool operandSwap = segment->operand() != oSegment->operand();
394        if (flipped) {
395            do {
396                SkOpSpanBase* oNext = oStart->next();
397                if (oNext == oEnd) {
398                    break;
399                }
400                oStart = oNext->upCast();
401            } while (true);
402        }
403        bool isXor = segment->isXor();
404        bool oppXor = oSegment->isXor();
405        do {
406            int windValue = start->windValue();
407            int oWindValue = oStart->windValue();
408            int oppValue = start->oppValue();
409            int oOppValue = oStart->oppValue();
410            // winding values are added or subtracted depending on direction and wind type
411            // same or opposite values are summed depending on the operand value
412            if (windValue >= oWindValue) {
413                if (operandSwap) {
414                    SkTSwap(oWindValue, oOppValue);
415                }
416                if (flipped) {
417                    windValue -= oWindValue;
418                    oppValue -= oOppValue;
419                } else {
420                    windValue += oWindValue;
421                    oppValue += oOppValue;
422                }
423                if (isXor) {
424                    windValue &= 1;
425                }
426                if (oppXor) {
427                    oppValue &= 1;
428                }
429                oWindValue = oOppValue = 0;
430            } else {
431                if (operandSwap) {
432                    SkTSwap(windValue, oppValue);
433                }
434                if (flipped) {
435                    oWindValue -= windValue;
436                    oOppValue -= oppValue;
437                } else {
438                    oWindValue += windValue;
439                    oOppValue += oppValue;
440                }
441                if (isXor) {
442                    oOppValue &= 1;
443                }
444                if (oppXor) {
445                    oWindValue &= 1;
446                }
447                windValue = oppValue = 0;
448            }
449            start->setWindValue(windValue);
450            start->setOppValue(oppValue);
451            oStart->setWindValue(oWindValue);
452            oStart->setOppValue(oOppValue);
453            if (!windValue && !oppValue) {
454                segment->markDone(start);
455            }
456            if (!oWindValue && !oOppValue) {
457                oSegment->markDone(oStart);
458            }
459            SkOpSpanBase* next = start->next();
460            SkOpSpanBase* oNext = flipped ? oStart->prev() : oStart->next();
461            if (next == end) {
462                break;
463            }
464            start = next->upCast();
465            oStart = oNext->upCast();
466        } while (true);
467    } while ((coin = coin->fNext));
468}
469
470void SkOpCoincidence::mark() {
471    SkCoincidentSpans* coin = fHead;
472    if (!coin) {
473        return;
474    }
475    do {
476        SkOpSpanBase* end = coin->fCoinPtTEnd->span();
477        SkOpSpanBase* oldEnd = end;
478        SkOpSpan* start = coin->fCoinPtTStart->span()->starter(&end);
479        SkOpSpanBase* oEnd = coin->fOppPtTEnd->span();
480        SkOpSpanBase* oOldEnd = oEnd;
481        SkOpSpanBase* oStart = coin->fOppPtTStart->span()->starter(&oEnd);
482        bool flipped = (end == oldEnd) != (oEnd == oOldEnd);
483        if (flipped) {
484            SkTSwap(oStart, oEnd);
485        }
486        SkOpSpanBase* next = start;
487        SkOpSpanBase* oNext = oStart;
488        do {
489            next = next->upCast()->next();
490            oNext = flipped ? oNext->prev() : oNext->upCast()->next();
491            if (next == end) {
492                SkASSERT(oNext == oEnd);
493                break;
494            }
495            if (!next->containsCoinEnd(oNext)) {
496                next->insertCoinEnd(oNext);
497            }
498            SkOpSpan* nextSpan = next->upCast();
499            SkOpSpan* oNextSpan = oNext->upCast();
500            if (!nextSpan->containsCoincidence(oNextSpan)) {
501                nextSpan->insertCoincidence(oNextSpan);
502            }
503        } while (true);
504    } while ((coin = coin->fNext));
505}
506