1/*
2 * Copyright 2015 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 "SkOpSegment.h"
9#include "SkPathOpsTSect.h"
10
11bool SkOpCoincidence::extend(SkOpPtT* coinPtTStart, SkOpPtT* coinPtTEnd, SkOpPtT* oppPtTStart,
12        SkOpPtT* oppPtTEnd) {
13    // if there is an existing pair that overlaps the addition, extend it
14    SkCoincidentSpans* coinRec = fHead;
15    if (coinRec) {
16        do {
17            if (coinRec->fCoinPtTStart->segment() != coinPtTStart->segment()) {
18                continue;
19            }
20            if (coinRec->fOppPtTStart->segment() != oppPtTStart->segment()) {
21                continue;
22            }
23            if (coinRec->fCoinPtTStart->fT > coinPtTEnd->fT) {
24                continue;
25            }
26            if (coinRec->fCoinPtTEnd->fT < coinPtTStart->fT) {
27                continue;
28            }
29            if (coinRec->fCoinPtTStart->fT > coinPtTStart->fT) {
30                coinRec->fCoinPtTStart = coinPtTStart;
31                coinRec->fOppPtTStart = oppPtTStart;
32            }
33            if (coinRec->fCoinPtTEnd->fT < coinPtTEnd->fT) {
34                coinRec->fCoinPtTEnd = coinPtTEnd;
35                coinRec->fOppPtTEnd = oppPtTEnd;
36            }
37            return true;
38        } while ((coinRec = coinRec->fNext));
39    }
40    return false;
41}
42
43void SkOpCoincidence::add(SkOpPtT* coinPtTStart, SkOpPtT* coinPtTEnd, SkOpPtT* oppPtTStart,
44        SkOpPtT* oppPtTEnd, SkChunkAlloc* allocator) {
45    SkASSERT(coinPtTStart->fT < coinPtTEnd->fT);
46    bool flipped = oppPtTStart->fT > oppPtTEnd->fT;
47    SkCoincidentSpans* coinRec = SkOpTAllocator<SkCoincidentSpans>::Allocate(allocator);
48    coinRec->fNext = this->fHead;
49    coinRec->fCoinPtTStart = coinPtTStart;
50    coinRec->fCoinPtTEnd = coinPtTEnd;
51    coinRec->fOppPtTStart = oppPtTStart;
52    coinRec->fOppPtTEnd = oppPtTEnd;
53    coinRec->fFlipped = flipped;
54    this->fHead = coinRec;
55}
56
57static void t_range(const SkOpPtT* overS, const SkOpPtT* overE, double tStart, double tEnd,
58        const SkOpPtT* coinPtTStart, const SkOpPtT* coinPtTEnd, double* coinTs, double* coinTe) {
59    double denom = overE->fT - overS->fT;
60    double start = 0 < denom ? tStart : tEnd;
61    double end = 0 < denom ? tEnd : tStart;
62    double sRatio = (start - overS->fT) / denom;
63    double eRatio = (end - overS->fT) / denom;
64    *coinTs = coinPtTStart->fT + (coinPtTEnd->fT - coinPtTStart->fT) * sRatio;
65    *coinTe = coinPtTStart->fT + (coinPtTEnd->fT - coinPtTStart->fT) * eRatio;
66}
67
68bool SkOpCoincidence::addIfMissing(const SkOpPtT* over1s, const SkOpPtT* over1e,
69                      const SkOpPtT* over2s, const SkOpPtT* over2e, double tStart, double tEnd,
70        SkOpPtT* coinPtTStart, const SkOpPtT* coinPtTEnd,
71        SkOpPtT* oppPtTStart, const SkOpPtT* oppPtTEnd, SkChunkAlloc* allocator) {
72    double coinTs, coinTe, oppTs, oppTe;
73    t_range(over1s, over1e, tStart, tEnd, coinPtTStart, coinPtTEnd, &coinTs, &coinTe);
74    t_range(over2s, over2e, tStart, tEnd, oppPtTStart, oppPtTEnd, &oppTs, &oppTe);
75    SkOpSegment* coinSeg = coinPtTStart->segment();
76    SkOpSegment* oppSeg = oppPtTStart->segment();
77    SkASSERT(coinSeg != oppSeg);
78    SkCoincidentSpans* check = this->fHead;
79    do {
80        const SkOpSegment* checkCoinSeg = check->fCoinPtTStart->segment();
81        if (checkCoinSeg != coinSeg && checkCoinSeg != oppSeg) {
82            continue;
83        }
84        const SkOpSegment* checkOppSeg = check->fOppPtTStart->segment();
85        if (checkOppSeg != coinSeg && checkOppSeg != oppSeg) {
86            continue;
87        }
88        int cTs = coinTs;
89        int cTe = coinTe;
90        int oTs = oppTs;
91        int oTe = oppTe;
92        if (checkCoinSeg != coinSeg) {
93            SkASSERT(checkOppSeg != oppSeg);
94            SkTSwap(cTs, oTs);
95            SkTSwap(cTe, oTe);
96        }
97        int tweenCount = (int) between(check->fCoinPtTStart->fT, cTs, check->fCoinPtTEnd->fT)
98                       + (int) between(check->fCoinPtTStart->fT, cTe, check->fCoinPtTEnd->fT)
99                       + (int) between(check->fOppPtTStart->fT, oTs, check->fOppPtTEnd->fT)
100                       + (int) between(check->fOppPtTStart->fT, oTe, check->fOppPtTEnd->fT);
101//        SkASSERT(tweenCount == 0 || tweenCount == 4);
102        if (tweenCount) {
103            return true;
104        }
105    } while ((check = check->fNext));
106    if ((over1s->fT < over1e->fT) != (over2s->fT < over2e->fT)) {
107        SkTSwap(oppTs, oppTe);
108    }
109    if (coinTs > coinTe) {
110        SkTSwap(coinTs, coinTe);
111        SkTSwap(oppTs, oppTe);
112    }
113    SkOpPtT* cs = coinSeg->addMissing(coinTs, oppSeg, allocator);
114    SkOpPtT* ce = coinSeg->addMissing(coinTe, oppSeg, allocator);
115    if (cs == ce) {
116        return false;
117    }
118    SkOpPtT* os = oppSeg->addMissing(oppTs, coinSeg, allocator);
119    SkOpPtT* oe = oppSeg->addMissing(oppTe, coinSeg, allocator);
120    SkASSERT(os != oe);
121    cs->addOpp(os);
122    ce->addOpp(oe);
123    this->add(cs, ce, os, oe, allocator);
124    return true;
125}
126
127bool SkOpCoincidence::addMissing(SkChunkAlloc* allocator) {
128    SkCoincidentSpans* outer = this->fHead;
129    if (!outer) {
130        return true;
131    }
132    do {
133        SkCoincidentSpans* inner = outer;
134        while ((inner = inner->fNext)) {
135            double overS, overE;
136            if (this->overlap(outer->fCoinPtTStart, outer->fCoinPtTEnd,
137                    inner->fCoinPtTStart, inner->fCoinPtTEnd, &overS, &overE)) {
138                if (!this->addIfMissing(outer->fCoinPtTStart, outer->fCoinPtTEnd,
139                        inner->fCoinPtTStart, inner->fCoinPtTEnd, overS, overE,
140                        outer->fOppPtTStart, outer->fOppPtTEnd,
141                        inner->fOppPtTStart, inner->fOppPtTEnd, allocator)) {
142                    return false;
143                }
144            } else if (this->overlap(outer->fCoinPtTStart, outer->fCoinPtTEnd,
145                    inner->fOppPtTStart, inner->fOppPtTEnd, &overS, &overE)) {
146                if (!this->addIfMissing(outer->fCoinPtTStart, outer->fCoinPtTEnd,
147                        inner->fOppPtTStart, inner->fOppPtTEnd, overS, overE,
148                        outer->fOppPtTStart, outer->fOppPtTEnd,
149                        inner->fCoinPtTStart, inner->fCoinPtTEnd, allocator)) {
150                    return false;
151                }
152            } else if (this->overlap(outer->fOppPtTStart, outer->fOppPtTEnd,
153                    inner->fCoinPtTStart, inner->fCoinPtTEnd, &overS, &overE)) {
154                if (!this->addIfMissing(outer->fOppPtTStart, outer->fOppPtTEnd,
155                        inner->fCoinPtTStart, inner->fCoinPtTEnd, overS, overE,
156                        outer->fCoinPtTStart, outer->fCoinPtTEnd,
157                        inner->fOppPtTStart, inner->fOppPtTEnd, allocator)) {
158                    return false;
159                }
160            } else if (this->overlap(outer->fOppPtTStart, outer->fOppPtTEnd,
161                    inner->fOppPtTStart, inner->fOppPtTEnd, &overS, &overE)) {
162                if (!this->addIfMissing(outer->fOppPtTStart, outer->fOppPtTEnd,
163                        inner->fOppPtTStart, inner->fOppPtTEnd, overS, overE,
164                        outer->fCoinPtTStart, outer->fCoinPtTEnd,
165                        inner->fCoinPtTStart, inner->fCoinPtTEnd, allocator)) {
166                    return false;
167                }
168            }
169        }
170
171    } while ((outer = outer->fNext));
172    return true;
173}
174
175bool SkOpCoincidence::contains(SkOpPtT* coinPtTStart, SkOpPtT* coinPtTEnd, SkOpPtT* oppPtTStart,
176        SkOpPtT* oppPtTEnd, bool flipped) {
177    SkCoincidentSpans* coin = fHead;
178    if (!coin) {
179        return false;
180    }
181    do {
182        if (coin->fCoinPtTStart == coinPtTStart &&  coin->fCoinPtTEnd == coinPtTEnd
183                && coin->fOppPtTStart == oppPtTStart && coin->fOppPtTEnd == oppPtTEnd
184                && coin->fFlipped == flipped) {
185            return true;
186        }
187    } while ((coin = coin->fNext));
188    return false;
189}
190
191// walk span sets in parallel, moving winding from one to the other
192bool SkOpCoincidence::apply() {
193    SkCoincidentSpans* coin = fHead;
194    if (!coin) {
195        return true;
196    }
197    do {
198        SkOpSpan* start = coin->fCoinPtTStart->span()->upCast();
199        if (start->deleted()) {
200            continue;
201        }
202        SkOpSpanBase* end = coin->fCoinPtTEnd->span();
203        SkASSERT(start == start->starter(end));
204        bool flipped = coin->fFlipped;
205        SkOpSpan* oStart = (flipped ? coin->fOppPtTEnd : coin->fOppPtTStart)->span()->upCast();
206        if (oStart->deleted()) {
207            continue;
208        }
209        SkOpSpanBase* oEnd = (flipped ? coin->fOppPtTStart : coin->fOppPtTEnd)->span();
210        SkASSERT(oStart == oStart->starter(oEnd));
211        SkOpSegment* segment = start->segment();
212        SkOpSegment* oSegment = oStart->segment();
213        bool operandSwap = segment->operand() != oSegment->operand();
214        if (flipped) {
215            do {
216                SkOpSpanBase* oNext = oStart->next();
217                if (oNext == oEnd) {
218                    break;
219                }
220                oStart = oNext->upCast();
221            } while (true);
222        }
223        do {
224            int windValue = start->windValue();
225            int oppValue = start->oppValue();
226            int oWindValue = oStart->windValue();
227            int oOppValue = oStart->oppValue();
228            // winding values are added or subtracted depending on direction and wind type
229            // same or opposite values are summed depending on the operand value
230            int windDiff = operandSwap ? oOppValue : oWindValue;
231            int oWindDiff = operandSwap ? oppValue : windValue;
232            if (!flipped) {
233                windDiff = -windDiff;
234                oWindDiff = -oWindDiff;
235            }
236            if (windValue && (windValue > windDiff || (windValue == windDiff
237                    && oWindValue <= oWindDiff))) {
238                if (operandSwap) {
239                    SkTSwap(oWindValue, oOppValue);
240                }
241                if (flipped) {
242                    windValue -= oWindValue;
243                    oppValue -= oOppValue;
244                } else {
245                    windValue += oWindValue;
246                    oppValue += oOppValue;
247                }
248                if (segment->isXor()) {
249                    windValue &= 1;
250                }
251                if (segment->oppXor()) {
252                    oppValue &= 1;
253                }
254                oWindValue = oOppValue = 0;
255            } else {
256                if (operandSwap) {
257                    SkTSwap(windValue, oppValue);
258                }
259                if (flipped) {
260                    oWindValue -= windValue;
261                    oOppValue -= oppValue;
262                } else {
263                    oWindValue += windValue;
264                    oOppValue += oppValue;
265                }
266                if (oSegment->isXor()) {
267                    oWindValue &= 1;
268                }
269                if (oSegment->oppXor()) {
270                    oOppValue &= 1;
271                }
272                windValue = oppValue = 0;
273            }
274            start->setWindValue(windValue);
275            start->setOppValue(oppValue);
276            oStart->setWindValue(oWindValue);
277            oStart->setOppValue(oOppValue);
278            if (!windValue && !oppValue) {
279                segment->markDone(start);
280            }
281            if (!oWindValue && !oOppValue) {
282                oSegment->markDone(oStart);
283            }
284            SkOpSpanBase* next = start->next();
285            SkOpSpanBase* oNext = flipped ? oStart->prev() : oStart->next();
286            if (next == end) {
287                break;
288            }
289            start = next->upCast();
290            // if the opposite ran out too soon, just reuse the last span
291            if (!oNext || !oNext->upCastable()) {
292               oNext = oStart;
293            }
294            oStart = oNext->upCast();
295        } while (true);
296    } while ((coin = coin->fNext));
297    return true;
298}
299
300void SkOpCoincidence::detach(SkCoincidentSpans* remove) {
301    SkCoincidentSpans* coin = fHead;
302    SkCoincidentSpans* prev = NULL;
303    SkCoincidentSpans* next;
304    do {
305        next = coin->fNext;
306        if (coin == remove) {
307            if (prev) {
308                prev->fNext = next;
309            } else {
310                fHead = next;
311            }
312            break;
313        }
314        prev = coin;
315    } while ((coin = next));
316    SkASSERT(coin);
317}
318
319void SkOpCoincidence::expand() {
320    SkCoincidentSpans* coin = fHead;
321    if (!coin) {
322        return;
323    }
324    do {
325        SkOpSpan* start = coin->fCoinPtTStart->span()->upCast();
326        SkOpSpanBase* end = coin->fCoinPtTEnd->span();
327        SkOpSegment* segment = coin->fCoinPtTStart->segment();
328        SkOpSegment* oppSegment = coin->fOppPtTStart->segment();
329        SkOpSpan* prev = start->prev();
330        SkOpPtT* oppPtT;
331        if (prev && (oppPtT = prev->contains(oppSegment))) {
332            double midT = (prev->t() + start->t()) / 2;
333            if (segment->isClose(midT, oppSegment)) {
334                coin->fCoinPtTStart = prev->ptT();
335                coin->fOppPtTStart = oppPtT;
336            }
337        }
338        SkOpSpanBase* next = end->final() ? NULL : end->upCast()->next();
339        if (next && (oppPtT = next->contains(oppSegment))) {
340            double midT = (end->t() + next->t()) / 2;
341            if (segment->isClose(midT, oppSegment)) {
342                coin->fCoinPtTEnd = next->ptT();
343                coin->fOppPtTEnd = oppPtT;
344            }
345        }
346    } while ((coin = coin->fNext));
347}
348
349void SkOpCoincidence::fixUp(SkOpPtT* deleted, SkOpPtT* kept) {
350    SkCoincidentSpans* coin = fHead;
351    if (!coin) {
352        return;
353    }
354    do {
355        if (coin->fCoinPtTStart == deleted) {
356            if (coin->fCoinPtTEnd->span() == kept->span()) {
357                return this->detach(coin);
358            }
359            coin->fCoinPtTStart = kept;
360        }
361        if (coin->fCoinPtTEnd == deleted) {
362            if (coin->fCoinPtTStart->span() == kept->span()) {
363                return this->detach(coin);
364            }
365            coin->fCoinPtTEnd = kept;
366        }
367        if (coin->fOppPtTStart == deleted) {
368            if (coin->fOppPtTEnd->span() == kept->span()) {
369                return this->detach(coin);
370            }
371            coin->fOppPtTStart = kept;
372        }
373        if (coin->fOppPtTEnd == deleted) {
374            if (coin->fOppPtTStart->span() == kept->span()) {
375                return this->detach(coin);
376            }
377            coin->fOppPtTEnd = kept;
378        }
379    } while ((coin = coin->fNext));
380}
381
382void SkOpCoincidence::mark() {
383    SkCoincidentSpans* coin = fHead;
384    if (!coin) {
385        return;
386    }
387    do {
388        SkOpSpanBase* end = coin->fCoinPtTEnd->span();
389        SkOpSpanBase* oldEnd = end;
390        SkOpSpan* start = coin->fCoinPtTStart->span()->starter(&end);
391        SkOpSpanBase* oEnd = coin->fOppPtTEnd->span();
392        SkOpSpanBase* oOldEnd = oEnd;
393        SkOpSpanBase* oStart = coin->fOppPtTStart->span()->starter(&oEnd);
394        bool flipped = (end == oldEnd) != (oEnd == oOldEnd);
395        if (flipped) {
396            SkTSwap(oStart, oEnd);
397        }
398        SkOpSpanBase* next = start;
399        SkOpSpanBase* oNext = oStart;
400        // check to see if coincident span could be bigger
401
402        do {
403            next = next->upCast()->next();
404            oNext = flipped ? oNext->prev() : oNext->upCast()->next();
405            if (next == end || oNext == oEnd) {
406                break;
407            }
408            if (!next->containsCoinEnd(oNext)) {
409                next->insertCoinEnd(oNext);
410            }
411            SkOpSpan* nextSpan = next->upCast();
412            SkOpSpan* oNextSpan = oNext->upCast();
413            if (!nextSpan->containsCoincidence(oNextSpan)) {
414                nextSpan->insertCoincidence(oNextSpan);
415            }
416        } while (true);
417    } while ((coin = coin->fNext));
418}
419
420bool SkOpCoincidence::overlap(const SkOpPtT* coin1s, const SkOpPtT* coin1e,
421        const SkOpPtT* coin2s, const SkOpPtT* coin2e, double* overS, double* overE) const {
422    if (coin1s->segment() != coin2s->segment()) {
423        return false;
424    }
425    *overS = SkTMax(SkTMin(coin1s->fT, coin1e->fT), SkTMin(coin2s->fT, coin2e->fT));
426    *overE = SkTMin(SkTMax(coin1s->fT, coin1e->fT), SkTMax(coin2s->fT, coin2e->fT));
427    return *overS < *overE;
428}
429