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 
extend(SkOpPtT * coinPtTStart,SkOpPtT * coinPtTEnd,SkOpPtT * oppPtTStart,SkOpPtT * oppPtTEnd)11 bool 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 
add(SkOpPtT * coinPtTStart,SkOpPtT * coinPtTEnd,SkOpPtT * oppPtTStart,SkOpPtT * oppPtTEnd,SkChunkAlloc * allocator)43 void 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 
t_range(const SkOpPtT * overS,const SkOpPtT * overE,double tStart,double tEnd,const SkOpPtT * coinPtTStart,const SkOpPtT * coinPtTEnd,double * coinTs,double * coinTe)57 static 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 
addIfMissing(const SkOpPtT * over1s,const SkOpPtT * over1e,const SkOpPtT * over2s,const SkOpPtT * over2e,double tStart,double tEnd,SkOpPtT * coinPtTStart,const SkOpPtT * coinPtTEnd,SkOpPtT * oppPtTStart,const SkOpPtT * oppPtTEnd,SkChunkAlloc * allocator)68 bool 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 
addMissing(SkChunkAlloc * allocator)127 bool 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 
contains(SkOpPtT * coinPtTStart,SkOpPtT * coinPtTEnd,SkOpPtT * oppPtTStart,SkOpPtT * oppPtTEnd,bool flipped)175 bool 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
apply()192 bool 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 
detach(SkCoincidentSpans * remove)300 void 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 
expand()319 void 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 
fixUp(SkOpPtT * deleted,SkOpPtT * kept)349 void 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 
mark()382 void 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 
overlap(const SkOpPtT * coin1s,const SkOpPtT * coin1e,const SkOpPtT * coin2s,const SkOpPtT * coin2e,double * overS,double * overE) const420 bool 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