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 SkDEBUGCODE(coinRec->fID = fDebugState->nextCoinID());
55
56 this->fHead = coinRec;
57 }
58
t_range(const SkOpPtT * overS,const SkOpPtT * overE,double tStart,double tEnd,const SkOpPtT * coinPtTStart,const SkOpPtT * coinPtTEnd,double * coinTs,double * coinTe)59 static void t_range(const SkOpPtT* overS, const SkOpPtT* overE, double tStart, double tEnd,
60 const SkOpPtT* coinPtTStart, const SkOpPtT* coinPtTEnd, double* coinTs, double* coinTe) {
61 double denom = overE->fT - overS->fT;
62 double start = 0 < denom ? tStart : tEnd;
63 double end = 0 < denom ? tEnd : tStart;
64 double sRatio = (start - overS->fT) / denom;
65 double eRatio = (end - overS->fT) / denom;
66 *coinTs = coinPtTStart->fT + (coinPtTEnd->fT - coinPtTStart->fT) * sRatio;
67 *coinTe = coinPtTStart->fT + (coinPtTEnd->fT - coinPtTStart->fT) * eRatio;
68 }
69
addExpanded(SkChunkAlloc * allocator PATH_OPS_DEBUG_VALIDATE_PARAMS (SkOpGlobalState * globalState))70 bool SkOpCoincidence::addExpanded(SkChunkAlloc* allocator
71 PATH_OPS_DEBUG_VALIDATE_PARAMS(SkOpGlobalState* globalState)) {
72 #if DEBUG_VALIDATE
73 globalState->setPhase(SkOpGlobalState::kIntersecting);
74 #endif
75 // for each coincident pair, match the spans
76 // if the spans don't match, add the mssing pt to the segment and loop it in the opposite span
77 SkCoincidentSpans* coin = this->fHead;
78 SkASSERT(coin);
79 do {
80 SkOpPtT* startPtT = coin->fCoinPtTStart;
81 SkOpPtT* oStartPtT = coin->fOppPtTStart;
82 SkASSERT(startPtT->contains(oStartPtT));
83 SkASSERT(coin->fCoinPtTEnd->contains(coin->fOppPtTEnd));
84 SkOpSpanBase* start = startPtT->span();
85 SkOpSpanBase* oStart = oStartPtT->span();
86 const SkOpSpanBase* end = coin->fCoinPtTEnd->span();
87 const SkOpSpanBase* oEnd = coin->fOppPtTEnd->span();
88 if (oEnd->deleted()) {
89 return false;
90 }
91 SkOpSpanBase* test = start->upCast()->next();
92 SkOpSpanBase* oTest = coin->fFlipped ? oStart->prev() : oStart->upCast()->next();
93 while (test != end || oTest != oEnd) {
94 if (!test->ptT()->contains(oTest->ptT())) {
95 // use t ranges to guess which one is missing
96 double startRange = coin->fCoinPtTEnd->fT - startPtT->fT;
97 if (!startRange) {
98 return false;
99 }
100 double startPart = (test->t() - startPtT->fT) / startRange;
101 double oStartRange = coin->fOppPtTEnd->fT - oStartPtT->fT;
102 if (!oStartRange) {
103 return false;
104 }
105 double oStartPart = (oTest->t() - oStartPtT->fT) / oStartRange;
106 if (startPart == oStartPart) {
107 return false;
108 }
109 SkOpPtT* newPt;
110 if (startPart < oStartPart) {
111 double newT = oStartPtT->fT + oStartRange * startPart;
112 newPt = oStart->segment()->addT(newT, SkOpSegment::kAllowAlias, allocator);
113 if (!newPt) {
114 return false;
115 }
116 newPt->fPt = test->pt();
117 test->ptT()->addOpp(newPt);
118 } else {
119 double newT = startPtT->fT + startRange * oStartPart;
120 newPt = start->segment()->addT(newT, SkOpSegment::kAllowAlias, allocator);
121 if (!newPt) {
122 return false;
123 }
124 newPt->fPt = oTest->pt();
125 oTest->ptT()->addOpp(newPt);
126 }
127 // start over
128 test = start;
129 oTest = oStart;
130 }
131 if (test != end) {
132 test = test->upCast()->next();
133 }
134 if (oTest != oEnd) {
135 oTest = coin->fFlipped ? oTest->prev() : oTest->upCast()->next();
136 }
137 }
138 } while ((coin = coin->fNext));
139 #if DEBUG_VALIDATE
140 globalState->setPhase(SkOpGlobalState::kWalking);
141 #endif
142 return true;
143 }
144
addIfMissing(const SkCoincidentSpans * outer,SkOpPtT * over1s,SkOpPtT * over1e,SkChunkAlloc * allocator)145 bool SkOpCoincidence::addIfMissing(const SkCoincidentSpans* outer, SkOpPtT* over1s,
146 SkOpPtT* over1e, SkChunkAlloc* allocator) {
147 SkCoincidentSpans* check = this->fTop;
148 do {
149 if (check->fCoinPtTStart->span() == over1s->span()
150 && check->fOppPtTStart->span() == outer->fOppPtTStart->span()) {
151 SkASSERT(check->fCoinPtTEnd->span() == over1e->span()
152 || !fDebugState->debugRunFail());
153 SkASSERT(check->fOppPtTEnd->span() == outer->fOppPtTEnd->span()
154 || !fDebugState->debugRunFail());
155 return false;
156 }
157 if (check->fCoinPtTStart->span() == outer->fCoinPtTStart->span()
158 && check->fOppPtTStart->span() == over1s->span()) {
159 SkASSERT(check->fCoinPtTEnd->span() == outer->fCoinPtTEnd->span()
160 || !fDebugState->debugRunFail());
161 SkASSERT(check->fOppPtTEnd->span() == over1e->span()
162 || !fDebugState->debugRunFail());
163 return false;
164 }
165 } while ((check = check->fNext));
166 this->add(outer->fCoinPtTStart, outer->fCoinPtTEnd, over1s, over1e, allocator);
167 #if 0
168 // FIXME: up to four flavors could be added -- do we need only one?
169 #endif
170 return true;
171 }
172
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)173 bool SkOpCoincidence::addIfMissing(const SkOpPtT* over1s, const SkOpPtT* over1e,
174 const SkOpPtT* over2s, const SkOpPtT* over2e, double tStart, double tEnd,
175 SkOpPtT* coinPtTStart, const SkOpPtT* coinPtTEnd,
176 SkOpPtT* oppPtTStart, const SkOpPtT* oppPtTEnd, SkChunkAlloc* allocator) {
177 double coinTs, coinTe, oppTs, oppTe;
178 t_range(over1s, over1e, tStart, tEnd, coinPtTStart, coinPtTEnd, &coinTs, &coinTe);
179 t_range(over2s, over2e, tStart, tEnd, oppPtTStart, oppPtTEnd, &oppTs, &oppTe);
180 SkOpSegment* coinSeg = coinPtTStart->segment();
181 SkOpSegment* oppSeg = oppPtTStart->segment();
182 SkASSERT(coinSeg != oppSeg);
183 SkCoincidentSpans* check = this->fTop;
184 do {
185 const SkOpSegment* checkCoinSeg = check->fCoinPtTStart->segment();
186 if (checkCoinSeg != coinSeg && checkCoinSeg != oppSeg) {
187 continue;
188 }
189 const SkOpSegment* checkOppSeg = check->fOppPtTStart->segment();
190 if (checkOppSeg != coinSeg && checkOppSeg != oppSeg) {
191 continue;
192 }
193 int cTs = coinTs;
194 int cTe = coinTe;
195 int oTs = oppTs;
196 int oTe = oppTe;
197 if (checkCoinSeg != coinSeg) {
198 SkASSERT(checkOppSeg != oppSeg);
199 SkTSwap(cTs, oTs);
200 SkTSwap(cTe, oTe);
201 }
202 int tweenCount = (int) between(check->fCoinPtTStart->fT, cTs, check->fCoinPtTEnd->fT)
203 + (int) between(check->fCoinPtTStart->fT, cTe, check->fCoinPtTEnd->fT)
204 + (int) between(check->fOppPtTStart->fT, oTs, check->fOppPtTEnd->fT)
205 + (int) between(check->fOppPtTStart->fT, oTe, check->fOppPtTEnd->fT);
206 // SkASSERT(tweenCount == 0 || tweenCount == 4);
207 if (tweenCount) {
208 return false;
209 }
210 } while ((check = check->fNext));
211 if ((over1s->fT < over1e->fT) != (over2s->fT < over2e->fT)) {
212 SkTSwap(oppTs, oppTe);
213 }
214 if (coinTs > coinTe) {
215 SkTSwap(coinTs, coinTe);
216 SkTSwap(oppTs, oppTe);
217 }
218 SkOpPtT* cs = coinSeg->addMissing(coinTs, oppSeg, allocator);
219 SkOpPtT* ce = coinSeg->addMissing(coinTe, oppSeg, allocator);
220 SkASSERT(cs != ce);
221 SkOpPtT* os = oppSeg->addMissing(oppTs, coinSeg, allocator);
222 SkOpPtT* oe = oppSeg->addMissing(oppTe, coinSeg, allocator);
223 // SkASSERT(os != oe);
224 cs->addOpp(os);
225 ce->addOpp(oe);
226 this->add(cs, ce, os, oe, allocator);
227 return true;
228 }
229
230 /* detects overlaps of different coincident runs on same segment */
231 /* does not detect overlaps for pairs without any segments in common */
addMissing(SkChunkAlloc * allocator)232 bool SkOpCoincidence::addMissing(SkChunkAlloc* allocator) {
233 SkCoincidentSpans* outer = fHead;
234 if (!outer) {
235 return true;
236 }
237 bool added = false;
238 fTop = outer;
239 fHead = nullptr;
240 do {
241 // addifmissing can modify the list that this is walking
242 // save head so that walker can iterate over old data unperturbed
243 // addifmissing adds to head freely then add saved head in the end
244 const SkOpSegment* outerCoin = outer->fCoinPtTStart->segment();
245 SkASSERT(outerCoin == outer->fCoinPtTEnd->segment());
246 const SkOpSegment* outerOpp = outer->fOppPtTStart->segment();
247 SkASSERT(outerOpp == outer->fOppPtTEnd->segment());
248 SkCoincidentSpans* inner = outer;
249 while ((inner = inner->fNext)) {
250 double overS, overE;
251 const SkOpSegment* innerCoin = inner->fCoinPtTStart->segment();
252 SkASSERT(innerCoin == inner->fCoinPtTEnd->segment());
253 const SkOpSegment* innerOpp = inner->fOppPtTStart->segment();
254 SkASSERT(innerOpp == inner->fOppPtTEnd->segment());
255 if (outerCoin == innerCoin
256 && this->overlap(outer->fCoinPtTStart, outer->fCoinPtTEnd,
257 inner->fCoinPtTStart, inner->fCoinPtTEnd, &overS, &overE)) {
258 added |= this->addIfMissing(outer->fCoinPtTStart, outer->fCoinPtTEnd,
259 inner->fCoinPtTStart, inner->fCoinPtTEnd, overS, overE,
260 outer->fOppPtTStart, outer->fOppPtTEnd,
261 inner->fOppPtTStart, inner->fOppPtTEnd, allocator);
262 } else if (outerCoin == innerOpp
263 && this->overlap(outer->fCoinPtTStart, outer->fCoinPtTEnd,
264 inner->fOppPtTStart, inner->fOppPtTEnd, &overS, &overE)) {
265 added |= this->addIfMissing(outer->fCoinPtTStart, outer->fCoinPtTEnd,
266 inner->fOppPtTStart, inner->fOppPtTEnd, overS, overE,
267 outer->fOppPtTStart, outer->fOppPtTEnd,
268 inner->fCoinPtTStart, inner->fCoinPtTEnd, allocator);
269 } else if (outerOpp == innerCoin
270 && this->overlap(outer->fOppPtTStart, outer->fOppPtTEnd,
271 inner->fCoinPtTStart, inner->fCoinPtTEnd, &overS, &overE)) {
272 added |= this->addIfMissing(outer->fOppPtTStart, outer->fOppPtTEnd,
273 inner->fCoinPtTStart, inner->fCoinPtTEnd, overS, overE,
274 outer->fCoinPtTStart, outer->fCoinPtTEnd,
275 inner->fOppPtTStart, inner->fOppPtTEnd, allocator);
276 } else if (outerOpp == innerOpp
277 && this->overlap(outer->fOppPtTStart, outer->fOppPtTEnd,
278 inner->fOppPtTStart, inner->fOppPtTEnd, &overS, &overE)) {
279 added |= this->addIfMissing(outer->fOppPtTStart, outer->fOppPtTEnd,
280 inner->fOppPtTStart, inner->fOppPtTEnd, overS, overE,
281 outer->fCoinPtTStart, outer->fCoinPtTEnd,
282 inner->fCoinPtTStart, inner->fCoinPtTEnd, allocator);
283 } else if (outerCoin != innerCoin) {
284 // check to see if outer span overlaps the inner span
285 // look for inner segment in pt-t list
286 // if present, and if t values are in coincident range
287 // add two pairs of new coincidence
288 SkOpPtT* testS = outer->fCoinPtTStart->contains(innerCoin);
289 SkOpPtT* testE = outer->fCoinPtTEnd->contains(innerCoin);
290 if (testS && testS->fT >= inner->fCoinPtTStart->fT
291 && testE && testE->fT <= inner->fCoinPtTEnd->fT
292 && this->testForCoincidence(outer, testS, testE)) {
293 added |= this->addIfMissing(outer, testS, testE, allocator);
294 } else {
295 testS = inner->fCoinPtTStart->contains(outerCoin);
296 testE = inner->fCoinPtTEnd->contains(outerCoin);
297 if (testS && testS->fT >= outer->fCoinPtTStart->fT
298 && testE && testE->fT <= outer->fCoinPtTEnd->fT
299 && this->testForCoincidence(inner, testS, testE)) {
300 added |= this->addIfMissing(inner, testS, testE, allocator);
301 }
302 }
303 }
304 #if 0 && DEBUG_COINCIDENCE
305 SkString miss;
306 miss.printf("addMissing inner=%d outer=%d", inner->debugID(), outer->debugID());
307 DEBUG_COINCIDENCE_HEALTH(fDebugState->contourHead(), miss.c_str());
308 #endif
309 }
310 } while ((outer = outer->fNext));
311 SkCoincidentSpans** headPtr = &fHead;
312 while (*headPtr) {
313 SkCoincidentSpans** headNext = &(*headPtr)->fNext;
314 if (*headNext) {
315 break;
316 }
317 headPtr = headNext;
318 }
319 *headPtr = fTop;
320 return added;
321 }
322
addOverlap(SkOpSegment * seg1,SkOpSegment * seg1o,SkOpSegment * seg2,SkOpSegment * seg2o,SkOpPtT * overS,SkOpPtT * overE,SkChunkAlloc * allocator)323 void SkOpCoincidence::addOverlap(SkOpSegment* seg1, SkOpSegment* seg1o, SkOpSegment* seg2,
324 SkOpSegment* seg2o, SkOpPtT* overS, SkOpPtT* overE, SkChunkAlloc* allocator) {
325 SkOpPtT* s1 = overS->find(seg1);
326 SkOpPtT* e1 = overE->find(seg1);
327 if (!s1->starter(e1)->span()->upCast()->windValue()) {
328 s1 = overS->find(seg1o);
329 e1 = overE->find(seg1o);
330 if (!s1->starter(e1)->span()->upCast()->windValue()) {
331 return;
332 }
333 }
334 SkOpPtT* s2 = overS->find(seg2);
335 SkOpPtT* e2 = overE->find(seg2);
336 if (!s2->starter(e2)->span()->upCast()->windValue()) {
337 s2 = overS->find(seg2o);
338 e2 = overE->find(seg2o);
339 if (!s2->starter(e2)->span()->upCast()->windValue()) {
340 return;
341 }
342 }
343 if (s1->segment() == s2->segment()) {
344 return;
345 }
346 if (s1->fT > e1->fT) {
347 SkTSwap(s1, e1);
348 SkTSwap(s2, e2);
349 }
350 this->add(s1, e1, s2, e2, allocator);
351 }
352
contains(const SkOpPtT * coinPtTStart,const SkOpPtT * coinPtTEnd,const SkOpPtT * oppPtTStart,const SkOpPtT * oppPtTEnd,bool flipped) const353 bool SkOpCoincidence::contains(const SkOpPtT* coinPtTStart, const SkOpPtT* coinPtTEnd,
354 const SkOpPtT* oppPtTStart, const SkOpPtT* oppPtTEnd, bool flipped) const {
355 const SkCoincidentSpans* coin = fHead;
356 if (!coin) {
357 return false;
358 }
359 do {
360 if (coin->fCoinPtTStart == coinPtTStart && coin->fCoinPtTEnd == coinPtTEnd
361 && coin->fOppPtTStart == oppPtTStart && coin->fOppPtTEnd == oppPtTEnd
362 && coin->fFlipped == flipped) {
363 return true;
364 }
365 } while ((coin = coin->fNext));
366 return false;
367 }
368
369 // walk span sets in parallel, moving winding from one to the other
apply()370 bool SkOpCoincidence::apply() {
371 SkCoincidentSpans* coin = fHead;
372 if (!coin) {
373 return true;
374 }
375 do {
376 SkOpSpan* start = coin->fCoinPtTStart->span()->upCast();
377 if (start->deleted()) {
378 continue;
379 }
380 SkOpSpanBase* end = coin->fCoinPtTEnd->span();
381 SkASSERT(start == start->starter(end));
382 bool flipped = coin->fFlipped;
383 SkOpSpan* oStart = (flipped ? coin->fOppPtTEnd : coin->fOppPtTStart)->span()->upCast();
384 if (oStart->deleted()) {
385 continue;
386 }
387 SkOpSpanBase* oEnd = (flipped ? coin->fOppPtTStart : coin->fOppPtTEnd)->span();
388 SkASSERT(oStart == oStart->starter(oEnd));
389 SkOpSegment* segment = start->segment();
390 SkOpSegment* oSegment = oStart->segment();
391 bool operandSwap = segment->operand() != oSegment->operand();
392 if (flipped) {
393 if (oEnd->deleted()) {
394 continue;
395 }
396 do {
397 SkOpSpanBase* oNext = oStart->next();
398 if (oNext == oEnd) {
399 break;
400 }
401 oStart = oNext->upCast();
402 } while (true);
403 }
404 do {
405 int windValue = start->windValue();
406 int oppValue = start->oppValue();
407 int oWindValue = oStart->windValue();
408 int oOppValue = oStart->oppValue();
409 // winding values are added or subtracted depending on direction and wind type
410 // same or opposite values are summed depending on the operand value
411 int windDiff = operandSwap ? oOppValue : oWindValue;
412 int oWindDiff = operandSwap ? oppValue : windValue;
413 if (!flipped) {
414 windDiff = -windDiff;
415 oWindDiff = -oWindDiff;
416 }
417 if (windValue && (windValue > windDiff || (windValue == windDiff
418 && oWindValue <= oWindDiff))) {
419 if (operandSwap) {
420 SkTSwap(oWindValue, oOppValue);
421 }
422 if (flipped) {
423 windValue -= oWindValue;
424 oppValue -= oOppValue;
425 } else {
426 windValue += oWindValue;
427 oppValue += oOppValue;
428 }
429 if (segment->isXor()) {
430 windValue &= 1;
431 }
432 if (segment->oppXor()) {
433 oppValue &= 1;
434 }
435 oWindValue = oOppValue = 0;
436 } else {
437 if (operandSwap) {
438 SkTSwap(windValue, oppValue);
439 }
440 if (flipped) {
441 oWindValue -= windValue;
442 oOppValue -= oppValue;
443 } else {
444 oWindValue += windValue;
445 oOppValue += oppValue;
446 }
447 if (oSegment->isXor()) {
448 oWindValue &= 1;
449 }
450 if (oSegment->oppXor()) {
451 oOppValue &= 1;
452 }
453 windValue = oppValue = 0;
454 }
455 start->setWindValue(windValue);
456 start->setOppValue(oppValue);
457 oStart->setWindValue(oWindValue);
458 oStart->setOppValue(oOppValue);
459 if (!windValue && !oppValue) {
460 segment->markDone(start);
461 }
462 if (!oWindValue && !oOppValue) {
463 oSegment->markDone(oStart);
464 }
465 SkOpSpanBase* next = start->next();
466 SkOpSpanBase* oNext = flipped ? oStart->prev() : oStart->next();
467 if (next == end) {
468 break;
469 }
470 if (!next->upCastable()) {
471 return false;
472 }
473 start = next->upCast();
474 // if the opposite ran out too soon, just reuse the last span
475 if (!oNext || !oNext->upCastable()) {
476 oNext = oStart;
477 }
478 oStart = oNext->upCast();
479 } while (true);
480 } while ((coin = coin->fNext));
481 return true;
482 }
483
detach(SkCoincidentSpans * remove)484 void SkOpCoincidence::detach(SkCoincidentSpans* remove) {
485 SkCoincidentSpans* coin = fHead;
486 SkCoincidentSpans* prev = nullptr;
487 SkCoincidentSpans* next;
488 do {
489 next = coin->fNext;
490 if (coin == remove) {
491 if (prev) {
492 prev->fNext = next;
493 } else {
494 fHead = next;
495 }
496 break;
497 }
498 prev = coin;
499 } while ((coin = next));
500 SkASSERT(coin);
501 }
502
expand()503 bool SkOpCoincidence::expand() {
504 SkCoincidentSpans* coin = fHead;
505 if (!coin) {
506 return false;
507 }
508 bool expanded = false;
509 do {
510 SkOpSpan* start = coin->fCoinPtTStart->span()->upCast();
511 SkOpSpanBase* end = coin->fCoinPtTEnd->span();
512 SkOpSegment* segment = coin->fCoinPtTStart->segment();
513 SkOpSegment* oppSegment = coin->fOppPtTStart->segment();
514 SkOpSpan* prev = start->prev();
515 SkOpPtT* oppPtT;
516 if (prev && (oppPtT = prev->contains(oppSegment))) {
517 double midT = (prev->t() + start->t()) / 2;
518 if (segment->isClose(midT, oppSegment)) {
519 coin->fCoinPtTStart = prev->ptT();
520 coin->fOppPtTStart = oppPtT;
521 expanded = true;
522 }
523 }
524 SkOpSpanBase* next = end->final() ? nullptr : end->upCast()->next();
525 if (next && (oppPtT = next->contains(oppSegment))) {
526 double midT = (end->t() + next->t()) / 2;
527 if (segment->isClose(midT, oppSegment)) {
528 coin->fCoinPtTEnd = next->ptT();
529 coin->fOppPtTEnd = oppPtT;
530 expanded = true;
531 }
532 }
533 } while ((coin = coin->fNext));
534 return expanded;
535 }
536
findOverlaps(SkOpCoincidence * overlaps,SkChunkAlloc * allocator) const537 void SkOpCoincidence::findOverlaps(SkOpCoincidence* overlaps, SkChunkAlloc* allocator) const {
538 overlaps->fHead = overlaps->fTop = nullptr;
539 SkDEBUGCODE_(overlaps->debugSetGlobalState(fDebugState));
540 SkCoincidentSpans* outer = fHead;
541 while (outer) {
542 SkOpSegment* outerCoin = outer->fCoinPtTStart->segment();
543 SkOpSegment* outerOpp = outer->fOppPtTStart->segment();
544 SkCoincidentSpans* inner = outer;
545 while ((inner = inner->fNext)) {
546 SkOpSegment* innerCoin = inner->fCoinPtTStart->segment();
547 if (outerCoin == innerCoin) {
548 continue; // both winners are the same segment, so there's no additional overlap
549 }
550 SkOpSegment* innerOpp = inner->fOppPtTStart->segment();
551 SkOpPtT* overlapS, * overlapE;
552 if ((outerOpp == innerCoin && SkOpPtT::Overlaps(outer->fOppPtTStart, outer->fOppPtTEnd,
553 inner->fCoinPtTStart, inner->fCoinPtTEnd, &overlapS, &overlapE))
554 || (outerCoin == innerOpp && SkOpPtT::Overlaps(outer->fCoinPtTStart,
555 outer->fCoinPtTEnd, inner->fOppPtTStart, inner->fOppPtTEnd,
556 &overlapS, &overlapE))
557 || (outerOpp == innerOpp && SkOpPtT::Overlaps(outer->fOppPtTStart,
558 outer->fOppPtTEnd, inner->fOppPtTStart, inner->fOppPtTEnd,
559 &overlapS, &overlapE))) {
560 overlaps->addOverlap(outerCoin, outerOpp, innerCoin, innerOpp,
561 overlapS, overlapE, allocator);
562 }
563 }
564 outer = outer->fNext;
565 }
566 }
567
fixAligned()568 void SkOpCoincidence::fixAligned() {
569 SkCoincidentSpans* coin = fHead;
570 if (!coin) {
571 return;
572 }
573 do {
574 if (coin->fCoinPtTStart->deleted()) {
575 coin->fCoinPtTStart = coin->fCoinPtTStart->doppelganger();
576 }
577 if (coin->fCoinPtTEnd->deleted()) {
578 coin->fCoinPtTEnd = coin->fCoinPtTEnd->doppelganger();
579 }
580 if (coin->fOppPtTStart->deleted()) {
581 coin->fOppPtTStart = coin->fOppPtTStart->doppelganger();
582 }
583 if (coin->fOppPtTEnd->deleted()) {
584 coin->fOppPtTEnd = coin->fOppPtTEnd->doppelganger();
585 }
586 } while ((coin = coin->fNext));
587 coin = fHead;
588 SkCoincidentSpans** priorPtr = &fHead;
589 do {
590 if (coin->fCoinPtTStart->collapsed(coin->fCoinPtTEnd)
591 || coin->fOppPtTStart->collapsed(coin->fOppPtTEnd)) {
592 *priorPtr = coin->fNext;
593 continue;
594 }
595 priorPtr = &coin->fNext;
596 } while ((coin = coin->fNext));
597 }
598
fixUp(SkOpPtT * deleted,SkOpPtT * kept)599 void SkOpCoincidence::fixUp(SkOpPtT* deleted, SkOpPtT* kept) {
600 SkCoincidentSpans* coin = fHead;
601 if (!coin) {
602 return;
603 }
604 do {
605 if (coin->fCoinPtTStart == deleted) {
606 if (coin->fCoinPtTEnd->span() == kept->span()) {
607 this->detach(coin);
608 continue;
609 }
610 coin->fCoinPtTStart = kept;
611 }
612 if (coin->fCoinPtTEnd == deleted) {
613 if (coin->fCoinPtTStart->span() == kept->span()) {
614 this->detach(coin);
615 continue;
616 }
617 coin->fCoinPtTEnd = kept;
618 }
619 if (coin->fOppPtTStart == deleted) {
620 if (coin->fOppPtTEnd->span() == kept->span()) {
621 this->detach(coin);
622 continue;
623 }
624 coin->fOppPtTStart = kept;
625 }
626 if (coin->fOppPtTEnd == deleted) {
627 if (coin->fOppPtTStart->span() == kept->span()) {
628 this->detach(coin);
629 continue;
630 }
631 coin->fOppPtTEnd = kept;
632 }
633 } while ((coin = coin->fNext));
634 }
635
636 /* this sets up the coincidence links in the segments when the coincidence crosses multiple spans */
mark()637 bool SkOpCoincidence::mark() {
638 SkCoincidentSpans* coin = fHead;
639 if (!coin) {
640 return true;
641 }
642 do {
643 SkOpSpanBase* end = coin->fCoinPtTEnd->span();
644 if (end->deleted()) {
645 return false;
646 }
647 SkOpSpanBase* oldEnd = end;
648 SkOpSpan* start = coin->fCoinPtTStart->span()->starter(&end);
649 SkOpSpanBase* oEnd = coin->fOppPtTEnd->span();
650 if (oEnd->deleted()) {
651 return false;
652 }
653 SkOpSpanBase* oOldEnd = oEnd;
654 SkOpSpanBase* oStart = coin->fOppPtTStart->span()->starter(&oEnd);
655 bool flipped = (end == oldEnd) != (oEnd == oOldEnd);
656 if (flipped) {
657 SkTSwap(oStart, oEnd);
658 }
659 SkOpSpanBase* next = start;
660 SkOpSpanBase* oNext = oStart;
661 do {
662 next = next->upCast()->next();
663 oNext = flipped ? oNext->prev() : oNext->upCast()->next();
664 if (next == end || oNext == oEnd) {
665 break;
666 }
667 if (!next->containsCoinEnd(oNext)) {
668 next->insertCoinEnd(oNext);
669 }
670 SkOpSpan* nextSpan = next->upCast();
671 SkOpSpan* oNextSpan = oNext->upCast();
672 if (!nextSpan->containsCoincidence(oNextSpan)) {
673 nextSpan->insertCoincidence(oNextSpan);
674 }
675 } while (true);
676 } while ((coin = coin->fNext));
677 return true;
678 }
679
overlap(const SkOpPtT * coin1s,const SkOpPtT * coin1e,const SkOpPtT * coin2s,const SkOpPtT * coin2e,double * overS,double * overE) const680 bool SkOpCoincidence::overlap(const SkOpPtT* coin1s, const SkOpPtT* coin1e,
681 const SkOpPtT* coin2s, const SkOpPtT* coin2e, double* overS, double* overE) const {
682 SkASSERT(coin1s->segment() == coin2s->segment());
683 *overS = SkTMax(SkTMin(coin1s->fT, coin1e->fT), SkTMin(coin2s->fT, coin2e->fT));
684 *overE = SkTMin(SkTMax(coin1s->fT, coin1e->fT), SkTMax(coin2s->fT, coin2e->fT));
685 return *overS < *overE;
686 }
687
testForCoincidence(const SkCoincidentSpans * outer,const SkOpPtT * testS,const SkOpPtT * testE) const688 bool SkOpCoincidence::testForCoincidence(const SkCoincidentSpans* outer, const SkOpPtT* testS,
689 const SkOpPtT* testE) const {
690 return testS->segment()->testForCoincidence(testS, testE, testS->span(),
691 testE->span(), outer->fCoinPtTStart->segment(), 120000); // FIXME: replace with tuned
692 }
693