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
11 // returns true if coincident span's start and end are the same
collapsed(const SkOpPtT * test) const12 bool SkCoincidentSpans::collapsed(const SkOpPtT* test) const {
13 return (fCoinPtTStart == test && fCoinPtTEnd->contains(test))
14 || (fCoinPtTEnd == test && fCoinPtTStart->contains(test))
15 || (fOppPtTStart == test && fOppPtTEnd->contains(test))
16 || (fOppPtTEnd == test && fOppPtTStart->contains(test));
17 }
18
19 // out of line since this function is referenced by address
coinPtTEnd() const20 const SkOpPtT* SkCoincidentSpans::coinPtTEnd() const {
21 return fCoinPtTEnd;
22 }
23
24 // out of line since this function is referenced by address
coinPtTStart() const25 const SkOpPtT* SkCoincidentSpans::coinPtTStart() const {
26 return fCoinPtTStart;
27 }
28
29 // sets the span's end to the ptT referenced by the previous-next
correctOneEnd(const SkOpPtT * (SkCoincidentSpans::* getEnd)()const,void (SkCoincidentSpans::* setEnd)(const SkOpPtT * ptT))30 void SkCoincidentSpans::correctOneEnd(
31 const SkOpPtT* (SkCoincidentSpans::* getEnd)() const,
32 void (SkCoincidentSpans::*setEnd)(const SkOpPtT* ptT) ) {
33 const SkOpPtT* origPtT = (this->*getEnd)();
34 const SkOpSpanBase* origSpan = origPtT->span();
35 const SkOpSpan* prev = origSpan->prev();
36 const SkOpPtT* testPtT = prev ? prev->next()->ptT()
37 : origSpan->upCast()->next()->prev()->ptT();
38 if (origPtT != testPtT) {
39 (this->*setEnd)(testPtT);
40 }
41 }
42
43 /* Please keep this in sync with debugCorrectEnds */
44 // FIXME: member pointers have fallen out of favor and can be replaced with
45 // an alternative approach.
46 // makes all span ends agree with the segment's spans that define them
correctEnds()47 void SkCoincidentSpans::correctEnds() {
48 this->correctOneEnd(&SkCoincidentSpans::coinPtTStart, &SkCoincidentSpans::setCoinPtTStart);
49 this->correctOneEnd(&SkCoincidentSpans::coinPtTEnd, &SkCoincidentSpans::setCoinPtTEnd);
50 this->correctOneEnd(&SkCoincidentSpans::oppPtTStart, &SkCoincidentSpans::setOppPtTStart);
51 this->correctOneEnd(&SkCoincidentSpans::oppPtTEnd, &SkCoincidentSpans::setOppPtTEnd);
52 }
53
54 /* Please keep this in sync with debugExpand */
55 // expand the range by checking adjacent spans for coincidence
expand()56 bool SkCoincidentSpans::expand() {
57 bool expanded = false;
58 const SkOpSegment* segment = coinPtTStart()->segment();
59 const SkOpSegment* oppSegment = oppPtTStart()->segment();
60 do {
61 const SkOpSpan* start = coinPtTStart()->span()->upCast();
62 const SkOpSpan* prev = start->prev();
63 const SkOpPtT* oppPtT;
64 if (!prev || !(oppPtT = prev->contains(oppSegment))) {
65 break;
66 }
67 double midT = (prev->t() + start->t()) / 2;
68 if (!segment->isClose(midT, oppSegment)) {
69 break;
70 }
71 setStarts(prev->ptT(), oppPtT);
72 expanded = true;
73 } while (true);
74 do {
75 const SkOpSpanBase* end = coinPtTEnd()->span();
76 SkOpSpanBase* next = end->final() ? nullptr : end->upCast()->next();
77 if (next && next->deleted()) {
78 break;
79 }
80 const SkOpPtT* oppPtT;
81 if (!next || !(oppPtT = next->contains(oppSegment))) {
82 break;
83 }
84 double midT = (end->t() + next->t()) / 2;
85 if (!segment->isClose(midT, oppSegment)) {
86 break;
87 }
88 setEnds(next->ptT(), oppPtT);
89 expanded = true;
90 } while (true);
91 return expanded;
92 }
93
94 // increase the range of this span
extend(const SkOpPtT * coinPtTStart,const SkOpPtT * coinPtTEnd,const SkOpPtT * oppPtTStart,const SkOpPtT * oppPtTEnd)95 bool SkCoincidentSpans::extend(const SkOpPtT* coinPtTStart, const SkOpPtT* coinPtTEnd,
96 const SkOpPtT* oppPtTStart, const SkOpPtT* oppPtTEnd) {
97 bool result = false;
98 if (fCoinPtTStart->fT > coinPtTStart->fT || (this->flipped()
99 ? fOppPtTStart->fT < oppPtTStart->fT : fOppPtTStart->fT > oppPtTStart->fT)) {
100 this->setStarts(coinPtTStart, oppPtTStart);
101 result = true;
102 }
103 if (fCoinPtTEnd->fT < coinPtTEnd->fT || (this->flipped()
104 ? fOppPtTEnd->fT > oppPtTEnd->fT : fOppPtTEnd->fT < oppPtTEnd->fT)) {
105 this->setEnds(coinPtTEnd, oppPtTEnd);
106 result = true;
107 }
108 return result;
109 }
110
111 // set the range of this span
set(SkCoincidentSpans * next,const SkOpPtT * coinPtTStart,const SkOpPtT * coinPtTEnd,const SkOpPtT * oppPtTStart,const SkOpPtT * oppPtTEnd)112 void SkCoincidentSpans::set(SkCoincidentSpans* next, const SkOpPtT* coinPtTStart,
113 const SkOpPtT* coinPtTEnd, const SkOpPtT* oppPtTStart, const SkOpPtT* oppPtTEnd) {
114 SkASSERT(SkOpCoincidence::Ordered(coinPtTStart, oppPtTStart));
115 fNext = next;
116 this->setStarts(coinPtTStart, oppPtTStart);
117 this->setEnds(coinPtTEnd, oppPtTEnd);
118 }
119
120 // returns true if both points are inside this
contains(const SkOpPtT * s,const SkOpPtT * e) const121 bool SkCoincidentSpans::contains(const SkOpPtT* s, const SkOpPtT* e) const {
122 if (s->fT > e->fT) {
123 SkTSwap(s, e);
124 }
125 if (s->segment() == fCoinPtTStart->segment()) {
126 return fCoinPtTStart->fT <= s->fT && e->fT <= fCoinPtTEnd->fT;
127 } else {
128 SkASSERT(s->segment() == fOppPtTStart->segment());
129 double oppTs = fOppPtTStart->fT;
130 double oppTe = fOppPtTEnd->fT;
131 if (oppTs > oppTe) {
132 SkTSwap(oppTs, oppTe);
133 }
134 return oppTs <= s->fT && e->fT <= oppTe;
135 }
136 }
137
138 // out of line since this function is referenced by address
oppPtTStart() const139 const SkOpPtT* SkCoincidentSpans::oppPtTStart() const {
140 return fOppPtTStart;
141 }
142
143 // out of line since this function is referenced by address
oppPtTEnd() const144 const SkOpPtT* SkCoincidentSpans::oppPtTEnd() const {
145 return fOppPtTEnd;
146 }
147
148 // A coincident span is unordered if the pairs of points in the main and opposite curves'
149 // t values do not ascend or descend. For instance, if a tightly arced quadratic is
150 // coincident with another curve, it may intersect it out of order.
ordered(bool * result) const151 bool SkCoincidentSpans::ordered(bool* result) const {
152 const SkOpSpanBase* start = this->coinPtTStart()->span();
153 const SkOpSpanBase* end = this->coinPtTEnd()->span();
154 const SkOpSpanBase* next = start->upCast()->next();
155 if (next == end) {
156 *result = true;
157 return true;
158 }
159 bool flipped = this->flipped();
160 const SkOpSegment* oppSeg = this->oppPtTStart()->segment();
161 double oppLastT = fOppPtTStart->fT;
162 do {
163 const SkOpPtT* opp = next->contains(oppSeg);
164 if (!opp) {
165 // SkOPOBJASSERT(start, 0); // may assert if coincident span isn't fully processed
166 return false;
167 }
168 if ((oppLastT > opp->fT) != flipped) {
169 *result = false;
170 return true;
171 }
172 oppLastT = opp->fT;
173 if (next == end) {
174 break;
175 }
176 if (!next->upCastable()) {
177 *result = false;
178 return true;
179 }
180 next = next->upCast()->next();
181 } while (true);
182 *result = true;
183 return true;
184 }
185
186 // if there is an existing pair that overlaps the addition, extend it
extend(const SkOpPtT * coinPtTStart,const SkOpPtT * coinPtTEnd,const SkOpPtT * oppPtTStart,const SkOpPtT * oppPtTEnd)187 bool SkOpCoincidence::extend(const SkOpPtT* coinPtTStart, const SkOpPtT* coinPtTEnd,
188 const SkOpPtT* oppPtTStart, const SkOpPtT* oppPtTEnd) {
189 SkCoincidentSpans* test = fHead;
190 if (!test) {
191 return false;
192 }
193 const SkOpSegment* coinSeg = coinPtTStart->segment();
194 const SkOpSegment* oppSeg = oppPtTStart->segment();
195 if (!Ordered(coinPtTStart, oppPtTStart)) {
196 SkTSwap(coinSeg, oppSeg);
197 SkTSwap(coinPtTStart, oppPtTStart);
198 SkTSwap(coinPtTEnd, oppPtTEnd);
199 if (coinPtTStart->fT > coinPtTEnd->fT) {
200 SkTSwap(coinPtTStart, coinPtTEnd);
201 SkTSwap(oppPtTStart, oppPtTEnd);
202 }
203 }
204 double oppMinT = SkTMin(oppPtTStart->fT, oppPtTEnd->fT);
205 SkDEBUGCODE(double oppMaxT = SkTMax(oppPtTStart->fT, oppPtTEnd->fT));
206 do {
207 if (coinSeg != test->coinPtTStart()->segment()) {
208 continue;
209 }
210 if (oppSeg != test->oppPtTStart()->segment()) {
211 continue;
212 }
213 double oTestMinT = SkTMin(test->oppPtTStart()->fT, test->oppPtTEnd()->fT);
214 double oTestMaxT = SkTMax(test->oppPtTStart()->fT, test->oppPtTEnd()->fT);
215 // if debug check triggers, caller failed to check if extended already exists
216 SkASSERT(test->coinPtTStart()->fT > coinPtTStart->fT
217 || coinPtTEnd->fT > test->coinPtTEnd()->fT
218 || oTestMinT > oppMinT || oppMaxT > oTestMaxT);
219 if ((test->coinPtTStart()->fT <= coinPtTEnd->fT
220 && coinPtTStart->fT <= test->coinPtTEnd()->fT)
221 || (oTestMinT <= oTestMaxT && oppMinT <= oTestMaxT)) {
222 test->extend(coinPtTStart, coinPtTEnd, oppPtTStart, oppPtTEnd);
223 return true;
224 }
225 } while ((test = test->next()));
226 return false;
227 }
228
229 // verifies that the coincidence hasn't already been added
DebugCheckAdd(const SkCoincidentSpans * check,const SkOpPtT * coinPtTStart,const SkOpPtT * coinPtTEnd,const SkOpPtT * oppPtTStart,const SkOpPtT * oppPtTEnd)230 static void DebugCheckAdd(const SkCoincidentSpans* check, const SkOpPtT* coinPtTStart,
231 const SkOpPtT* coinPtTEnd, const SkOpPtT* oppPtTStart, const SkOpPtT* oppPtTEnd) {
232 #if DEBUG_COINCIDENCE
233 while (check) {
234 SkASSERT(check->coinPtTStart() != coinPtTStart || check->coinPtTEnd() != coinPtTEnd
235 || check->oppPtTStart() != oppPtTStart || check->oppPtTEnd() != oppPtTEnd);
236 SkASSERT(check->coinPtTStart() != oppPtTStart || check->coinPtTEnd() != oppPtTEnd
237 || check->oppPtTStart() != coinPtTStart || check->oppPtTEnd() != coinPtTEnd);
238 check = check->next();
239 }
240 #endif
241 }
242
243 // adds a new coincident pair
add(SkOpPtT * coinPtTStart,SkOpPtT * coinPtTEnd,SkOpPtT * oppPtTStart,SkOpPtT * oppPtTEnd)244 void SkOpCoincidence::add(SkOpPtT* coinPtTStart, SkOpPtT* coinPtTEnd, SkOpPtT* oppPtTStart,
245 SkOpPtT* oppPtTEnd) {
246 // OPTIMIZE: caller should have already sorted
247 if (!Ordered(coinPtTStart, oppPtTStart)) {
248 if (oppPtTStart->fT < oppPtTEnd->fT) {
249 this->add(oppPtTStart, oppPtTEnd, coinPtTStart, coinPtTEnd);
250 } else {
251 this->add(oppPtTEnd, oppPtTStart, coinPtTEnd, coinPtTStart);
252 }
253 return;
254 }
255 SkASSERT(Ordered(coinPtTStart, oppPtTStart));
256 // choose the ptT at the front of the list to track
257 coinPtTStart = coinPtTStart->span()->ptT();
258 coinPtTEnd = coinPtTEnd->span()->ptT();
259 oppPtTStart = oppPtTStart->span()->ptT();
260 oppPtTEnd = oppPtTEnd->span()->ptT();
261 SkOPASSERT(coinPtTStart->fT < coinPtTEnd->fT);
262 SkOPASSERT(oppPtTStart->fT != oppPtTEnd->fT);
263 SkOPASSERT(!coinPtTStart->deleted());
264 SkOPASSERT(!coinPtTEnd->deleted());
265 SkOPASSERT(!oppPtTStart->deleted());
266 SkOPASSERT(!oppPtTEnd->deleted());
267 DebugCheckAdd(fHead, coinPtTStart, coinPtTEnd, oppPtTStart, oppPtTEnd);
268 DebugCheckAdd(fTop, coinPtTStart, coinPtTEnd, oppPtTStart, oppPtTEnd);
269 SkCoincidentSpans* coinRec = this->globalState()->allocator()->make<SkCoincidentSpans>();
270 coinRec->init(SkDEBUGCODE(fGlobalState));
271 coinRec->set(this->fHead, coinPtTStart, coinPtTEnd, oppPtTStart, oppPtTEnd);
272 fHead = coinRec;
273 }
274
275 // description below
addEndMovedSpans(const SkOpSpan * base,const SkOpSpanBase * testSpan)276 bool SkOpCoincidence::addEndMovedSpans(const SkOpSpan* base, const SkOpSpanBase* testSpan) {
277 const SkOpPtT* testPtT = testSpan->ptT();
278 const SkOpPtT* stopPtT = testPtT;
279 const SkOpSegment* baseSeg = base->segment();
280 int escapeHatch = 100000; // this is 100 times larger than the debugLoopLimit test
281 while ((testPtT = testPtT->next()) != stopPtT) {
282 if (--escapeHatch <= 0) {
283 return false; // if triggered (likely by a fuzz-generated test) too complex to succeed
284 }
285 const SkOpSegment* testSeg = testPtT->segment();
286 if (testPtT->deleted()) {
287 continue;
288 }
289 if (testSeg == baseSeg) {
290 continue;
291 }
292 if (testPtT->span()->ptT() != testPtT) {
293 continue;
294 }
295 if (this->contains(baseSeg, testSeg, testPtT->fT)) {
296 continue;
297 }
298 // intersect perp with base->ptT() with testPtT->segment()
299 SkDVector dxdy = baseSeg->dSlopeAtT(base->t());
300 const SkPoint& pt = base->pt();
301 SkDLine ray = {{{pt.fX, pt.fY}, {pt.fX + dxdy.fY, pt.fY - dxdy.fX}}};
302 SkIntersections i SkDEBUGCODE((this->globalState()));
303 (*CurveIntersectRay[testSeg->verb()])(testSeg->pts(), testSeg->weight(), ray, &i);
304 for (int index = 0; index < i.used(); ++index) {
305 double t = i[0][index];
306 if (!between(0, t, 1)) {
307 continue;
308 }
309 SkDPoint oppPt = i.pt(index);
310 if (!oppPt.approximatelyEqual(pt)) {
311 continue;
312 }
313 SkOpSegment* writableSeg = const_cast<SkOpSegment*>(testSeg);
314 SkOpPtT* oppStart = writableSeg->addT(t);
315 if (oppStart == testPtT) {
316 continue;
317 }
318 SkOpSpan* writableBase = const_cast<SkOpSpan*>(base);
319 oppStart->span()->addOpp(writableBase);
320 if (oppStart->deleted()) {
321 continue;
322 }
323 SkOpSegment* coinSeg = base->segment();
324 SkOpSegment* oppSeg = oppStart->segment();
325 double coinTs, coinTe, oppTs, oppTe;
326 if (Ordered(coinSeg, oppSeg)) {
327 coinTs = base->t();
328 coinTe = testSpan->t();
329 oppTs = oppStart->fT;
330 oppTe = testPtT->fT;
331 } else {
332 SkTSwap(coinSeg, oppSeg);
333 coinTs = oppStart->fT;
334 coinTe = testPtT->fT;
335 oppTs = base->t();
336 oppTe = testSpan->t();
337 }
338 if (coinTs > coinTe) {
339 SkTSwap(coinTs, coinTe);
340 SkTSwap(oppTs, oppTe);
341 }
342 bool added;
343 if (!this->addOrOverlap(coinSeg, oppSeg, coinTs, coinTe, oppTs, oppTe, &added)) {
344 return false;
345 }
346 }
347 }
348 return true;
349 }
350
351 // description below
addEndMovedSpans(const SkOpPtT * ptT)352 bool SkOpCoincidence::addEndMovedSpans(const SkOpPtT* ptT) {
353 FAIL_IF(!ptT->span()->upCastable());
354 const SkOpSpan* base = ptT->span()->upCast();
355 const SkOpSpan* prev = base->prev();
356 FAIL_IF(!prev);
357 if (!prev->isCanceled()) {
358 if (!this->addEndMovedSpans(base, base->prev())) {
359 return false;
360 }
361 }
362 if (!base->isCanceled()) {
363 if (!this->addEndMovedSpans(base, base->next())) {
364 return false;
365 }
366 }
367 return true;
368 }
369
370 /* If A is coincident with B and B includes an endpoint, and A's matching point
371 is not the endpoint (i.e., there's an implied line connecting B-end and A)
372 then assume that the same implied line may intersect another curve close to B.
373 Since we only care about coincidence that was undetected, look at the
374 ptT list on B-segment adjacent to the B-end/A ptT loop (not in the loop, but
375 next door) and see if the A matching point is close enough to form another
376 coincident pair. If so, check for a new coincident span between B-end/A ptT loop
377 and the adjacent ptT loop.
378 */
addEndMovedSpans(DEBUG_COIN_DECLARE_ONLY_PARAMS ())379 bool SkOpCoincidence::addEndMovedSpans(DEBUG_COIN_DECLARE_ONLY_PARAMS()) {
380 DEBUG_SET_PHASE();
381 SkCoincidentSpans* span = fHead;
382 if (!span) {
383 return true;
384 }
385 fTop = span;
386 fHead = nullptr;
387 do {
388 if (span->coinPtTStart()->fPt != span->oppPtTStart()->fPt) {
389 FAIL_IF(1 == span->coinPtTStart()->fT);
390 bool onEnd = span->coinPtTStart()->fT == 0;
391 bool oOnEnd = zero_or_one(span->oppPtTStart()->fT);
392 if (onEnd) {
393 if (!oOnEnd) { // if both are on end, any nearby intersect was already found
394 if (!this->addEndMovedSpans(span->oppPtTStart())) {
395 return false;
396 }
397 }
398 } else if (oOnEnd) {
399 if (!this->addEndMovedSpans(span->coinPtTStart())) {
400 return false;
401 }
402 }
403 }
404 if (span->coinPtTEnd()->fPt != span->oppPtTEnd()->fPt) {
405 bool onEnd = span->coinPtTEnd()->fT == 1;
406 bool oOnEnd = zero_or_one(span->oppPtTEnd()->fT);
407 if (onEnd) {
408 if (!oOnEnd) {
409 if (!this->addEndMovedSpans(span->oppPtTEnd())) {
410 return false;
411 }
412 }
413 } else if (oOnEnd) {
414 if (!this->addEndMovedSpans(span->coinPtTEnd())) {
415 return false;
416 }
417 }
418 }
419 } while ((span = span->next()));
420 this->restoreHead();
421 return true;
422 }
423
424 /* Please keep this in sync with debugAddExpanded */
425 // for each coincident pair, match the spans
426 // if the spans don't match, add the missing pt to the segment and loop it in the opposite span
addExpanded(DEBUG_COIN_DECLARE_ONLY_PARAMS ())427 bool SkOpCoincidence::addExpanded(DEBUG_COIN_DECLARE_ONLY_PARAMS()) {
428 DEBUG_SET_PHASE();
429 SkCoincidentSpans* coin = this->fHead;
430 if (!coin) {
431 return true;
432 }
433 do {
434 const SkOpPtT* startPtT = coin->coinPtTStart();
435 const SkOpPtT* oStartPtT = coin->oppPtTStart();
436 double priorT = startPtT->fT;
437 double oPriorT = oStartPtT->fT;
438 FAIL_IF(!startPtT->contains(oStartPtT));
439 SkOPASSERT(coin->coinPtTEnd()->contains(coin->oppPtTEnd()));
440 const SkOpSpanBase* start = startPtT->span();
441 const SkOpSpanBase* oStart = oStartPtT->span();
442 const SkOpSpanBase* end = coin->coinPtTEnd()->span();
443 const SkOpSpanBase* oEnd = coin->oppPtTEnd()->span();
444 FAIL_IF(oEnd->deleted());
445 FAIL_IF(!start->upCastable());
446 const SkOpSpanBase* test = start->upCast()->next();
447 FAIL_IF(!coin->flipped() && !oStart->upCastable());
448 const SkOpSpanBase* oTest = coin->flipped() ? oStart->prev() : oStart->upCast()->next();
449 FAIL_IF(!oTest);
450 SkOpSegment* seg = start->segment();
451 SkOpSegment* oSeg = oStart->segment();
452 while (test != end || oTest != oEnd) {
453 const SkOpPtT* containedOpp = test->ptT()->contains(oSeg);
454 const SkOpPtT* containedThis = oTest->ptT()->contains(seg);
455 if (!containedOpp || !containedThis) {
456 // choose the ends, or the first common pt-t list shared by both
457 double nextT, oNextT;
458 if (containedOpp) {
459 nextT = test->t();
460 oNextT = containedOpp->fT;
461 } else if (containedThis) {
462 nextT = containedThis->fT;
463 oNextT = oTest->t();
464 } else {
465 // iterate through until a pt-t list found that contains the other
466 const SkOpSpanBase* walk = test;
467 const SkOpPtT* walkOpp;
468 do {
469 FAIL_IF(!walk->upCastable());
470 walk = walk->upCast()->next();
471 } while (!(walkOpp = walk->ptT()->contains(oSeg))
472 && walk != coin->coinPtTEnd()->span());
473 FAIL_IF(!walkOpp);
474 nextT = walk->t();
475 oNextT = walkOpp->fT;
476 }
477 // use t ranges to guess which one is missing
478 double startRange = nextT - priorT;
479 FAIL_IF(!startRange);
480 double startPart = (test->t() - priorT) / startRange;
481 double oStartRange = oNextT - oPriorT;
482 FAIL_IF(!oStartRange);
483 double oStartPart = (oTest->t() - oPriorT) / oStartRange;
484 FAIL_IF(startPart == oStartPart);
485 bool addToOpp = !containedOpp && !containedThis ? startPart < oStartPart
486 : !!containedThis;
487 bool startOver = false;
488 bool success = addToOpp ? oSeg->addExpanded(
489 oPriorT + oStartRange * startPart, test, &startOver)
490 : seg->addExpanded(
491 priorT + startRange * oStartPart, oTest, &startOver);
492 FAIL_IF(!success);
493 if (startOver) {
494 test = start;
495 oTest = oStart;
496 }
497 end = coin->coinPtTEnd()->span();
498 oEnd = coin->oppPtTEnd()->span();
499 }
500 if (test != end) {
501 FAIL_IF(!test->upCastable());
502 priorT = test->t();
503 test = test->upCast()->next();
504 }
505 if (oTest != oEnd) {
506 oPriorT = oTest->t();
507 if (coin->flipped()) {
508 oTest = oTest->prev();
509 } else {
510 FAIL_IF(!oTest->upCastable());
511 oTest = oTest->upCast()->next();
512 }
513 FAIL_IF(!oTest);
514 }
515
516 }
517 } while ((coin = coin->next()));
518 return true;
519 }
520
521 // given a t span, map the same range on the coincident span
522 /*
523 the curves may not scale linearly, so interpolation may only happen within known points
524 remap over1s, over1e, cointPtTStart, coinPtTEnd to smallest range that captures over1s
525 then repeat to capture over1e
526 */
TRange(const SkOpPtT * overS,double t,const SkOpSegment * coinSeg SkDEBUGPARAMS (const SkOpPtT * overE))527 double SkOpCoincidence::TRange(const SkOpPtT* overS, double t,
528 const SkOpSegment* coinSeg SkDEBUGPARAMS(const SkOpPtT* overE)) {
529 const SkOpSpanBase* work = overS->span();
530 const SkOpPtT* foundStart = nullptr;
531 const SkOpPtT* foundEnd = nullptr;
532 const SkOpPtT* coinStart = nullptr;
533 const SkOpPtT* coinEnd = nullptr;
534 do {
535 const SkOpPtT* contained = work->contains(coinSeg);
536 if (!contained) {
537 if (work->final()) {
538 break;
539 }
540 continue;
541 }
542 if (work->t() <= t) {
543 coinStart = contained;
544 foundStart = work->ptT();
545 }
546 if (work->t() >= t) {
547 coinEnd = contained;
548 foundEnd = work->ptT();
549 break;
550 }
551 SkASSERT(work->ptT() != overE);
552 } while ((work = work->upCast()->next()));
553 if (!coinStart || !coinEnd) {
554 return 1;
555 }
556 // while overS->fT <=t and overS contains coinSeg
557 double denom = foundEnd->fT - foundStart->fT;
558 double sRatio = denom ? (t - foundStart->fT) / denom : 1;
559 return coinStart->fT + (coinEnd->fT - coinStart->fT) * sRatio;
560 }
561
562 // return true if span overlaps existing and needs to adjust the coincident list
checkOverlap(SkCoincidentSpans * check,const SkOpSegment * coinSeg,const SkOpSegment * oppSeg,double coinTs,double coinTe,double oppTs,double oppTe,SkTDArray<SkCoincidentSpans * > * overlaps) const563 bool SkOpCoincidence::checkOverlap(SkCoincidentSpans* check,
564 const SkOpSegment* coinSeg, const SkOpSegment* oppSeg,
565 double coinTs, double coinTe, double oppTs, double oppTe,
566 SkTDArray<SkCoincidentSpans*>* overlaps) const {
567 if (!Ordered(coinSeg, oppSeg)) {
568 if (oppTs < oppTe) {
569 return this->checkOverlap(check, oppSeg, coinSeg, oppTs, oppTe, coinTs, coinTe,
570 overlaps);
571 }
572 return this->checkOverlap(check, oppSeg, coinSeg, oppTe, oppTs, coinTe, coinTs, overlaps);
573 }
574 bool swapOpp = oppTs > oppTe;
575 if (swapOpp) {
576 SkTSwap(oppTs, oppTe);
577 }
578 do {
579 if (check->coinPtTStart()->segment() != coinSeg) {
580 continue;
581 }
582 if (check->oppPtTStart()->segment() != oppSeg) {
583 continue;
584 }
585 double checkTs = check->coinPtTStart()->fT;
586 double checkTe = check->coinPtTEnd()->fT;
587 bool coinOutside = coinTe < checkTs || coinTs > checkTe;
588 double oCheckTs = check->oppPtTStart()->fT;
589 double oCheckTe = check->oppPtTEnd()->fT;
590 if (swapOpp) {
591 if (oCheckTs <= oCheckTe) {
592 return false;
593 }
594 SkTSwap(oCheckTs, oCheckTe);
595 }
596 bool oppOutside = oppTe < oCheckTs || oppTs > oCheckTe;
597 if (coinOutside && oppOutside) {
598 continue;
599 }
600 bool coinInside = coinTe <= checkTe && coinTs >= checkTs;
601 bool oppInside = oppTe <= oCheckTe && oppTs >= oCheckTs;
602 if (coinInside && oppInside) { // already included, do nothing
603 return false;
604 }
605 *overlaps->append() = check; // partial overlap, extend existing entry
606 } while ((check = check->next()));
607 return true;
608 }
609
610 /* Please keep this in sync with debugAddIfMissing() */
611 // note that over1s, over1e, over2s, over2e are ordered
addIfMissing(const SkOpPtT * over1s,const SkOpPtT * over2s,double tStart,double tEnd,SkOpSegment * coinSeg,SkOpSegment * oppSeg,bool * added SkDEBUGPARAMS (const SkOpPtT * over1e)SkDEBUGPARAMS (const SkOpPtT * over2e))612 bool SkOpCoincidence::addIfMissing(const SkOpPtT* over1s, const SkOpPtT* over2s,
613 double tStart, double tEnd, SkOpSegment* coinSeg, SkOpSegment* oppSeg, bool* added
614 SkDEBUGPARAMS(const SkOpPtT* over1e) SkDEBUGPARAMS(const SkOpPtT* over2e)) {
615 SkASSERT(tStart < tEnd);
616 SkASSERT(over1s->fT < over1e->fT);
617 SkASSERT(between(over1s->fT, tStart, over1e->fT));
618 SkASSERT(between(over1s->fT, tEnd, over1e->fT));
619 SkASSERT(over2s->fT < over2e->fT);
620 SkASSERT(between(over2s->fT, tStart, over2e->fT));
621 SkASSERT(between(over2s->fT, tEnd, over2e->fT));
622 SkASSERT(over1s->segment() == over1e->segment());
623 SkASSERT(over2s->segment() == over2e->segment());
624 SkASSERT(over1s->segment() == over2s->segment());
625 SkASSERT(over1s->segment() != coinSeg);
626 SkASSERT(over1s->segment() != oppSeg);
627 SkASSERT(coinSeg != oppSeg);
628 double coinTs, coinTe, oppTs, oppTe;
629 coinTs = TRange(over1s, tStart, coinSeg SkDEBUGPARAMS(over1e));
630 coinTe = TRange(over1s, tEnd, coinSeg SkDEBUGPARAMS(over1e));
631 if (coinSeg->collapsed(coinTs, coinTe)) {
632 return true;
633 }
634 oppTs = TRange(over2s, tStart, oppSeg SkDEBUGPARAMS(over2e));
635 oppTe = TRange(over2s, tEnd, oppSeg SkDEBUGPARAMS(over2e));
636 if (oppSeg->collapsed(oppTs, oppTe)) {
637 return true;
638 }
639 if (coinTs > coinTe) {
640 SkTSwap(coinTs, coinTe);
641 SkTSwap(oppTs, oppTe);
642 }
643 return this->addOrOverlap(coinSeg, oppSeg, coinTs, coinTe, oppTs, oppTe, added);
644 }
645
646 /* Please keep this in sync with debugAddOrOverlap() */
647 // If this is called by addEndMovedSpans(), a returned false propogates out to an abort.
648 // If this is called by AddIfMissing(), a returned false indicates there was nothing to add
addOrOverlap(SkOpSegment * coinSeg,SkOpSegment * oppSeg,double coinTs,double coinTe,double oppTs,double oppTe,bool * added)649 bool SkOpCoincidence::addOrOverlap(SkOpSegment* coinSeg, SkOpSegment* oppSeg,
650 double coinTs, double coinTe, double oppTs, double oppTe, bool* added) {
651 SkTDArray<SkCoincidentSpans*> overlaps;
652 FAIL_IF(!fTop);
653 if (!this->checkOverlap(fTop, coinSeg, oppSeg, coinTs, coinTe, oppTs, oppTe, &overlaps)) {
654 return true;
655 }
656 if (fHead && !this->checkOverlap(fHead, coinSeg, oppSeg, coinTs,
657 coinTe, oppTs, oppTe, &overlaps)) {
658 return true;
659 }
660 SkCoincidentSpans* overlap = overlaps.count() ? overlaps[0] : nullptr;
661 for (int index = 1; index < overlaps.count(); ++index) { // combine overlaps before continuing
662 SkCoincidentSpans* test = overlaps[index];
663 if (overlap->coinPtTStart()->fT > test->coinPtTStart()->fT) {
664 overlap->setCoinPtTStart(test->coinPtTStart());
665 }
666 if (overlap->coinPtTEnd()->fT < test->coinPtTEnd()->fT) {
667 overlap->setCoinPtTEnd(test->coinPtTEnd());
668 }
669 if (overlap->flipped()
670 ? overlap->oppPtTStart()->fT < test->oppPtTStart()->fT
671 : overlap->oppPtTStart()->fT > test->oppPtTStart()->fT) {
672 overlap->setOppPtTStart(test->oppPtTStart());
673 }
674 if (overlap->flipped()
675 ? overlap->oppPtTEnd()->fT > test->oppPtTEnd()->fT
676 : overlap->oppPtTEnd()->fT < test->oppPtTEnd()->fT) {
677 overlap->setOppPtTEnd(test->oppPtTEnd());
678 }
679 if (!fHead || !this->release(fHead, test)) {
680 SkAssertResult(this->release(fTop, test));
681 }
682 }
683 const SkOpPtT* cs = coinSeg->existing(coinTs, oppSeg);
684 const SkOpPtT* ce = coinSeg->existing(coinTe, oppSeg);
685 if (overlap && cs && ce && overlap->contains(cs, ce)) {
686 return true;
687 }
688 FAIL_IF(cs == ce && cs);
689 const SkOpPtT* os = oppSeg->existing(oppTs, coinSeg);
690 const SkOpPtT* oe = oppSeg->existing(oppTe, coinSeg);
691 if (overlap && os && oe && overlap->contains(os, oe)) {
692 return true;
693 }
694 SkASSERT(!cs || !cs->deleted());
695 SkASSERT(!os || !os->deleted());
696 SkASSERT(!ce || !ce->deleted());
697 SkASSERT(!oe || !oe->deleted());
698 const SkOpPtT* csExisting = !cs ? coinSeg->existing(coinTs, nullptr) : nullptr;
699 const SkOpPtT* ceExisting = !ce ? coinSeg->existing(coinTe, nullptr) : nullptr;
700 FAIL_IF(csExisting && csExisting == ceExisting);
701 // FAIL_IF(csExisting && (csExisting == ce ||
702 // csExisting->contains(ceExisting ? ceExisting : ce)));
703 FAIL_IF(ceExisting && (ceExisting == cs ||
704 ceExisting->contains(csExisting ? csExisting : cs)));
705 const SkOpPtT* osExisting = !os ? oppSeg->existing(oppTs, nullptr) : nullptr;
706 const SkOpPtT* oeExisting = !oe ? oppSeg->existing(oppTe, nullptr) : nullptr;
707 FAIL_IF(osExisting && osExisting == oeExisting);
708 FAIL_IF(osExisting && (osExisting == oe ||
709 osExisting->contains(oeExisting ? oeExisting : oe)));
710 FAIL_IF(oeExisting && (oeExisting == os ||
711 oeExisting->contains(osExisting ? osExisting : os)));
712 // extra line in debug code
713 this->debugValidate();
714 if (!cs || !os) {
715 SkOpPtT* csWritable = cs ? const_cast<SkOpPtT*>(cs)
716 : coinSeg->addT(coinTs);
717 if (csWritable == ce) {
718 return true;
719 }
720 SkOpPtT* osWritable = os ? const_cast<SkOpPtT*>(os)
721 : oppSeg->addT(oppTs);
722 FAIL_IF(!csWritable || !osWritable);
723 csWritable->span()->addOpp(osWritable->span());
724 cs = csWritable;
725 os = osWritable->active();
726 FAIL_IF((ce && ce->deleted()) || (oe && oe->deleted()));
727 }
728 if (!ce || !oe) {
729 SkOpPtT* ceWritable = ce ? const_cast<SkOpPtT*>(ce)
730 : coinSeg->addT(coinTe);
731 SkOpPtT* oeWritable = oe ? const_cast<SkOpPtT*>(oe)
732 : oppSeg->addT(oppTe);
733 ceWritable->span()->addOpp(oeWritable->span());
734 ce = ceWritable;
735 oe = oeWritable;
736 }
737 this->debugValidate();
738 FAIL_IF(cs->deleted());
739 FAIL_IF(os->deleted());
740 FAIL_IF(ce->deleted());
741 FAIL_IF(oe->deleted());
742 FAIL_IF(cs->contains(ce) || os->contains(oe));
743 bool result = true;
744 if (overlap) {
745 if (overlap->coinPtTStart()->segment() == coinSeg) {
746 result = overlap->extend(cs, ce, os, oe);
747 } else {
748 if (os->fT > oe->fT) {
749 SkTSwap(cs, ce);
750 SkTSwap(os, oe);
751 }
752 result = overlap->extend(os, oe, cs, ce);
753 }
754 #if DEBUG_COINCIDENCE_VERBOSE
755 if (result) {
756 overlaps[0]->debugShow();
757 }
758 #endif
759 } else {
760 this->add(cs, ce, os, oe);
761 #if DEBUG_COINCIDENCE_VERBOSE
762 fHead->debugShow();
763 #endif
764 }
765 this->debugValidate();
766 if (result) {
767 *added = true;
768 }
769 return true;
770 }
771
772 // Please keep this in sync with debugAddMissing()
773 /* detects overlaps of different coincident runs on same segment */
774 /* does not detect overlaps for pairs without any segments in common */
775 // returns true if caller should loop again
addMissing(bool * added DEBUG_COIN_DECLARE_PARAMS ())776 bool SkOpCoincidence::addMissing(bool* added DEBUG_COIN_DECLARE_PARAMS()) {
777 SkCoincidentSpans* outer = fHead;
778 *added = false;
779 if (!outer) {
780 return true;
781 }
782 fTop = outer;
783 fHead = nullptr;
784 do {
785 // addifmissing can modify the list that this is walking
786 // save head so that walker can iterate over old data unperturbed
787 // addifmissing adds to head freely then add saved head in the end
788 const SkOpPtT* ocs = outer->coinPtTStart();
789 FAIL_IF(ocs->deleted());
790 const SkOpSegment* outerCoin = ocs->segment();
791 SkASSERT(!outerCoin->done()); // if it's done, should have already been removed from list
792 const SkOpPtT* oos = outer->oppPtTStart();
793 if (oos->deleted()) {
794 return true;
795 }
796 const SkOpSegment* outerOpp = oos->segment();
797 SkOPASSERT(!outerOpp->done());
798 SkOpSegment* outerCoinWritable = const_cast<SkOpSegment*>(outerCoin);
799 SkOpSegment* outerOppWritable = const_cast<SkOpSegment*>(outerOpp);
800 SkCoincidentSpans* inner = outer;
801 while ((inner = inner->next())) {
802 this->debugValidate();
803 double overS, overE;
804 const SkOpPtT* ics = inner->coinPtTStart();
805 FAIL_IF(ics->deleted());
806 const SkOpSegment* innerCoin = ics->segment();
807 FAIL_IF(innerCoin->done());
808 const SkOpPtT* ios = inner->oppPtTStart();
809 FAIL_IF(ios->deleted());
810 const SkOpSegment* innerOpp = ios->segment();
811 SkOPASSERT(!innerOpp->done());
812 SkOpSegment* innerCoinWritable = const_cast<SkOpSegment*>(innerCoin);
813 SkOpSegment* innerOppWritable = const_cast<SkOpSegment*>(innerOpp);
814 if (outerCoin == innerCoin) {
815 const SkOpPtT* oce = outer->coinPtTEnd();
816 if (oce->deleted()) {
817 return true;
818 }
819 const SkOpPtT* ice = inner->coinPtTEnd();
820 FAIL_IF(ice->deleted());
821 if (outerOpp != innerOpp && this->overlap(ocs, oce, ics, ice, &overS, &overE)) {
822 (void) this->addIfMissing(ocs->starter(oce), ics->starter(ice),
823 overS, overE, outerOppWritable, innerOppWritable, added
824 SkDEBUGPARAMS(ocs->debugEnder(oce))
825 SkDEBUGPARAMS(ics->debugEnder(ice)));
826 }
827 } else if (outerCoin == innerOpp) {
828 const SkOpPtT* oce = outer->coinPtTEnd();
829 SkASSERT(!oce->deleted());
830 const SkOpPtT* ioe = inner->oppPtTEnd();
831 SkASSERT(!ioe->deleted());
832 if (outerOpp != innerCoin && this->overlap(ocs, oce, ios, ioe, &overS, &overE)) {
833 (void) this->addIfMissing(ocs->starter(oce), ios->starter(ioe),
834 overS, overE, outerOppWritable, innerCoinWritable, added
835 SkDEBUGPARAMS(ocs->debugEnder(oce))
836 SkDEBUGPARAMS(ios->debugEnder(ioe)));
837 }
838 } else if (outerOpp == innerCoin) {
839 const SkOpPtT* ooe = outer->oppPtTEnd();
840 SkASSERT(!ooe->deleted());
841 const SkOpPtT* ice = inner->coinPtTEnd();
842 SkASSERT(!ice->deleted());
843 SkASSERT(outerCoin != innerOpp);
844 if (this->overlap(oos, ooe, ics, ice, &overS, &overE)) {
845 (void) this->addIfMissing(oos->starter(ooe), ics->starter(ice),
846 overS, overE, outerCoinWritable, innerOppWritable, added
847 SkDEBUGPARAMS(oos->debugEnder(ooe))
848 SkDEBUGPARAMS(ics->debugEnder(ice)));
849 }
850 } else if (outerOpp == innerOpp) {
851 const SkOpPtT* ooe = outer->oppPtTEnd();
852 SkASSERT(!ooe->deleted());
853 const SkOpPtT* ioe = inner->oppPtTEnd();
854 if (ioe->deleted()) {
855 return true;
856 }
857 SkASSERT(outerCoin != innerCoin);
858 if (this->overlap(oos, ooe, ios, ioe, &overS, &overE)) {
859 (void) this->addIfMissing(oos->starter(ooe), ios->starter(ioe),
860 overS, overE, outerCoinWritable, innerCoinWritable, added
861 SkDEBUGPARAMS(oos->debugEnder(ooe))
862 SkDEBUGPARAMS(ios->debugEnder(ioe)));
863 }
864 }
865 this->debugValidate();
866 }
867 } while ((outer = outer->next()));
868 this->restoreHead();
869 return true;
870 }
871
addOverlap(const SkOpSegment * seg1,const SkOpSegment * seg1o,const SkOpSegment * seg2,const SkOpSegment * seg2o,const SkOpPtT * overS,const SkOpPtT * overE)872 bool SkOpCoincidence::addOverlap(const SkOpSegment* seg1, const SkOpSegment* seg1o,
873 const SkOpSegment* seg2, const SkOpSegment* seg2o,
874 const SkOpPtT* overS, const SkOpPtT* overE) {
875 const SkOpPtT* s1 = overS->find(seg1);
876 const SkOpPtT* e1 = overE->find(seg1);
877 FAIL_IF(!s1);
878 FAIL_IF(!e1);
879 if (!s1->starter(e1)->span()->upCast()->windValue()) {
880 s1 = overS->find(seg1o);
881 e1 = overE->find(seg1o);
882 FAIL_IF(!s1);
883 FAIL_IF(!e1);
884 if (!s1->starter(e1)->span()->upCast()->windValue()) {
885 return true;
886 }
887 }
888 const SkOpPtT* s2 = overS->find(seg2);
889 const SkOpPtT* e2 = overE->find(seg2);
890 FAIL_IF(!s2);
891 FAIL_IF(!e2);
892 if (!s2->starter(e2)->span()->upCast()->windValue()) {
893 s2 = overS->find(seg2o);
894 e2 = overE->find(seg2o);
895 FAIL_IF(!s2);
896 FAIL_IF(!e2);
897 if (!s2->starter(e2)->span()->upCast()->windValue()) {
898 return true;
899 }
900 }
901 if (s1->segment() == s2->segment()) {
902 return true;
903 }
904 if (s1->fT > e1->fT) {
905 SkTSwap(s1, e1);
906 SkTSwap(s2, e2);
907 }
908 this->add(s1, e1, s2, e2);
909 return true;
910 }
911
contains(const SkOpSegment * seg,const SkOpSegment * opp,double oppT) const912 bool SkOpCoincidence::contains(const SkOpSegment* seg, const SkOpSegment* opp, double oppT) const {
913 if (this->contains(fHead, seg, opp, oppT)) {
914 return true;
915 }
916 if (this->contains(fTop, seg, opp, oppT)) {
917 return true;
918 }
919 return false;
920 }
921
contains(const SkCoincidentSpans * coin,const SkOpSegment * seg,const SkOpSegment * opp,double oppT) const922 bool SkOpCoincidence::contains(const SkCoincidentSpans* coin, const SkOpSegment* seg,
923 const SkOpSegment* opp, double oppT) const {
924 if (!coin) {
925 return false;
926 }
927 do {
928 if (coin->coinPtTStart()->segment() == seg && coin->oppPtTStart()->segment() == opp
929 && between(coin->oppPtTStart()->fT, oppT, coin->oppPtTEnd()->fT)) {
930 return true;
931 }
932 if (coin->oppPtTStart()->segment() == seg && coin->coinPtTStart()->segment() == opp
933 && between(coin->coinPtTStart()->fT, oppT, coin->coinPtTEnd()->fT)) {
934 return true;
935 }
936 } while ((coin = coin->next()));
937 return false;
938 }
939
contains(const SkOpPtT * coinPtTStart,const SkOpPtT * coinPtTEnd,const SkOpPtT * oppPtTStart,const SkOpPtT * oppPtTEnd) const940 bool SkOpCoincidence::contains(const SkOpPtT* coinPtTStart, const SkOpPtT* coinPtTEnd,
941 const SkOpPtT* oppPtTStart, const SkOpPtT* oppPtTEnd) const {
942 const SkCoincidentSpans* test = fHead;
943 if (!test) {
944 return false;
945 }
946 const SkOpSegment* coinSeg = coinPtTStart->segment();
947 const SkOpSegment* oppSeg = oppPtTStart->segment();
948 if (!Ordered(coinPtTStart, oppPtTStart)) {
949 SkTSwap(coinSeg, oppSeg);
950 SkTSwap(coinPtTStart, oppPtTStart);
951 SkTSwap(coinPtTEnd, oppPtTEnd);
952 if (coinPtTStart->fT > coinPtTEnd->fT) {
953 SkTSwap(coinPtTStart, coinPtTEnd);
954 SkTSwap(oppPtTStart, oppPtTEnd);
955 }
956 }
957 double oppMinT = SkTMin(oppPtTStart->fT, oppPtTEnd->fT);
958 double oppMaxT = SkTMax(oppPtTStart->fT, oppPtTEnd->fT);
959 do {
960 if (coinSeg != test->coinPtTStart()->segment()) {
961 continue;
962 }
963 if (coinPtTStart->fT < test->coinPtTStart()->fT) {
964 continue;
965 }
966 if (coinPtTEnd->fT > test->coinPtTEnd()->fT) {
967 continue;
968 }
969 if (oppSeg != test->oppPtTStart()->segment()) {
970 continue;
971 }
972 if (oppMinT < SkTMin(test->oppPtTStart()->fT, test->oppPtTEnd()->fT)) {
973 continue;
974 }
975 if (oppMaxT > SkTMax(test->oppPtTStart()->fT, test->oppPtTEnd()->fT)) {
976 continue;
977 }
978 return true;
979 } while ((test = test->next()));
980 return false;
981 }
982
correctEnds(DEBUG_COIN_DECLARE_ONLY_PARAMS ())983 void SkOpCoincidence::correctEnds(DEBUG_COIN_DECLARE_ONLY_PARAMS()) {
984 DEBUG_SET_PHASE();
985 SkCoincidentSpans* coin = fHead;
986 if (!coin) {
987 return;
988 }
989 do {
990 coin->correctEnds();
991 } while ((coin = coin->next()));
992 }
993
994 // walk span sets in parallel, moving winding from one to the other
apply(DEBUG_COIN_DECLARE_ONLY_PARAMS ())995 bool SkOpCoincidence::apply(DEBUG_COIN_DECLARE_ONLY_PARAMS()) {
996 DEBUG_SET_PHASE();
997 SkCoincidentSpans* coin = fHead;
998 if (!coin) {
999 return true;
1000 }
1001 do {
1002 SkOpSpanBase* startSpan = coin->coinPtTStartWritable()->span();
1003 FAIL_IF(!startSpan->upCastable());
1004 SkOpSpan* start = startSpan->upCast();
1005 if (start->deleted()) {
1006 continue;
1007 }
1008 const SkOpSpanBase* end = coin->coinPtTEnd()->span();
1009 SkASSERT(start == start->starter(end));
1010 bool flipped = coin->flipped();
1011 SkOpSpanBase* oStartBase = (flipped ? coin->oppPtTEndWritable()
1012 : coin->oppPtTStartWritable())->span();
1013 FAIL_IF(!oStartBase->upCastable());
1014 SkOpSpan* oStart = oStartBase->upCast();
1015 if (oStart->deleted()) {
1016 continue;
1017 }
1018 const SkOpSpanBase* oEnd = (flipped ? coin->oppPtTStart() : coin->oppPtTEnd())->span();
1019 SkASSERT(oStart == oStart->starter(oEnd));
1020 SkOpSegment* segment = start->segment();
1021 SkOpSegment* oSegment = oStart->segment();
1022 bool operandSwap = segment->operand() != oSegment->operand();
1023 if (flipped) {
1024 if (oEnd->deleted()) {
1025 continue;
1026 }
1027 do {
1028 SkOpSpanBase* oNext = oStart->next();
1029 if (oNext == oEnd) {
1030 break;
1031 }
1032 FAIL_IF(!oNext->upCastable());
1033 oStart = oNext->upCast();
1034 } while (true);
1035 }
1036 do {
1037 int windValue = start->windValue();
1038 int oppValue = start->oppValue();
1039 int oWindValue = oStart->windValue();
1040 int oOppValue = oStart->oppValue();
1041 // winding values are added or subtracted depending on direction and wind type
1042 // same or opposite values are summed depending on the operand value
1043 int windDiff = operandSwap ? oOppValue : oWindValue;
1044 int oWindDiff = operandSwap ? oppValue : windValue;
1045 if (!flipped) {
1046 windDiff = -windDiff;
1047 oWindDiff = -oWindDiff;
1048 }
1049 bool addToStart = windValue && (windValue > windDiff || (windValue == windDiff
1050 && oWindValue <= oWindDiff));
1051 if (addToStart ? start->done() : oStart->done()) {
1052 addToStart ^= true;
1053 }
1054 if (addToStart) {
1055 if (operandSwap) {
1056 SkTSwap(oWindValue, oOppValue);
1057 }
1058 if (flipped) {
1059 windValue -= oWindValue;
1060 oppValue -= oOppValue;
1061 } else {
1062 windValue += oWindValue;
1063 oppValue += oOppValue;
1064 }
1065 if (segment->isXor()) {
1066 windValue &= 1;
1067 }
1068 if (segment->oppXor()) {
1069 oppValue &= 1;
1070 }
1071 oWindValue = oOppValue = 0;
1072 } else {
1073 if (operandSwap) {
1074 SkTSwap(windValue, oppValue);
1075 }
1076 if (flipped) {
1077 oWindValue -= windValue;
1078 oOppValue -= oppValue;
1079 } else {
1080 oWindValue += windValue;
1081 oOppValue += oppValue;
1082 }
1083 if (oSegment->isXor()) {
1084 oWindValue &= 1;
1085 }
1086 if (oSegment->oppXor()) {
1087 oOppValue &= 1;
1088 }
1089 windValue = oppValue = 0;
1090 }
1091 #if 0 && DEBUG_COINCIDENCE
1092 SkDebugf("seg=%d span=%d windValue=%d oppValue=%d\n", segment->debugID(),
1093 start->debugID(), windValue, oppValue);
1094 SkDebugf("seg=%d span=%d windValue=%d oppValue=%d\n", oSegment->debugID(),
1095 oStart->debugID(), oWindValue, oOppValue);
1096 #endif
1097 start->setWindValue(windValue);
1098 start->setOppValue(oppValue);
1099 FAIL_IF(oWindValue == -1);
1100 oStart->setWindValue(oWindValue);
1101 oStart->setOppValue(oOppValue);
1102 if (!windValue && !oppValue) {
1103 segment->markDone(start);
1104 }
1105 if (!oWindValue && !oOppValue) {
1106 oSegment->markDone(oStart);
1107 }
1108 SkOpSpanBase* next = start->next();
1109 SkOpSpanBase* oNext = flipped ? oStart->prev() : oStart->next();
1110 if (next == end) {
1111 break;
1112 }
1113 FAIL_IF(!next->upCastable());
1114 start = next->upCast();
1115 // if the opposite ran out too soon, just reuse the last span
1116 if (!oNext || !oNext->upCastable()) {
1117 oNext = oStart;
1118 }
1119 oStart = oNext->upCast();
1120 } while (true);
1121 } while ((coin = coin->next()));
1122 return true;
1123 }
1124
1125 // Please keep this in sync with debugRelease()
release(SkCoincidentSpans * coin,SkCoincidentSpans * remove)1126 bool SkOpCoincidence::release(SkCoincidentSpans* coin, SkCoincidentSpans* remove) {
1127 SkCoincidentSpans* head = coin;
1128 SkCoincidentSpans* prev = nullptr;
1129 SkCoincidentSpans* next;
1130 do {
1131 next = coin->next();
1132 if (coin == remove) {
1133 if (prev) {
1134 prev->setNext(next);
1135 } else if (head == fHead) {
1136 fHead = next;
1137 } else {
1138 fTop = next;
1139 }
1140 break;
1141 }
1142 prev = coin;
1143 } while ((coin = next));
1144 return coin != nullptr;
1145 }
1146
releaseDeleted(SkCoincidentSpans * coin)1147 void SkOpCoincidence::releaseDeleted(SkCoincidentSpans* coin) {
1148 if (!coin) {
1149 return;
1150 }
1151 SkCoincidentSpans* head = coin;
1152 SkCoincidentSpans* prev = nullptr;
1153 SkCoincidentSpans* next;
1154 do {
1155 next = coin->next();
1156 if (coin->coinPtTStart()->deleted()) {
1157 SkOPASSERT(coin->flipped() ? coin->oppPtTEnd()->deleted() :
1158 coin->oppPtTStart()->deleted());
1159 if (prev) {
1160 prev->setNext(next);
1161 } else if (head == fHead) {
1162 fHead = next;
1163 } else {
1164 fTop = next;
1165 }
1166 } else {
1167 SkOPASSERT(coin->flipped() ? !coin->oppPtTEnd()->deleted() :
1168 !coin->oppPtTStart()->deleted());
1169 prev = coin;
1170 }
1171 } while ((coin = next));
1172 }
1173
releaseDeleted()1174 void SkOpCoincidence::releaseDeleted() {
1175 this->releaseDeleted(fHead);
1176 this->releaseDeleted(fTop);
1177 }
1178
restoreHead()1179 void SkOpCoincidence::restoreHead() {
1180 SkCoincidentSpans** headPtr = &fHead;
1181 while (*headPtr) {
1182 headPtr = (*headPtr)->nextPtr();
1183 }
1184 *headPtr = fTop;
1185 fTop = nullptr;
1186 // segments may have collapsed in the meantime; remove empty referenced segments
1187 headPtr = &fHead;
1188 while (*headPtr) {
1189 SkCoincidentSpans* test = *headPtr;
1190 if (test->coinPtTStart()->segment()->done() || test->oppPtTStart()->segment()->done()) {
1191 *headPtr = test->next();
1192 continue;
1193 }
1194 headPtr = (*headPtr)->nextPtr();
1195 }
1196 }
1197
1198 // Please keep this in sync with debugExpand()
1199 // expand the range by checking adjacent spans for coincidence
expand(DEBUG_COIN_DECLARE_ONLY_PARAMS ())1200 bool SkOpCoincidence::expand(DEBUG_COIN_DECLARE_ONLY_PARAMS()) {
1201 DEBUG_SET_PHASE();
1202 SkCoincidentSpans* coin = fHead;
1203 if (!coin) {
1204 return false;
1205 }
1206 bool expanded = false;
1207 do {
1208 if (coin->expand()) {
1209 // check to see if multiple spans expanded so they are now identical
1210 SkCoincidentSpans* test = fHead;
1211 do {
1212 if (coin == test) {
1213 continue;
1214 }
1215 if (coin->coinPtTStart() == test->coinPtTStart()
1216 && coin->oppPtTStart() == test->oppPtTStart()) {
1217 this->release(fHead, test);
1218 break;
1219 }
1220 } while ((test = test->next()));
1221 expanded = true;
1222 }
1223 } while ((coin = coin->next()));
1224 return expanded;
1225 }
1226
findOverlaps(SkOpCoincidence * overlaps DEBUG_COIN_DECLARE_PARAMS ()) const1227 bool SkOpCoincidence::findOverlaps(SkOpCoincidence* overlaps DEBUG_COIN_DECLARE_PARAMS()) const {
1228 DEBUG_SET_PHASE();
1229 overlaps->fHead = overlaps->fTop = nullptr;
1230 SkCoincidentSpans* outer = fHead;
1231 while (outer) {
1232 const SkOpSegment* outerCoin = outer->coinPtTStart()->segment();
1233 const SkOpSegment* outerOpp = outer->oppPtTStart()->segment();
1234 SkCoincidentSpans* inner = outer;
1235 while ((inner = inner->next())) {
1236 const SkOpSegment* innerCoin = inner->coinPtTStart()->segment();
1237 if (outerCoin == innerCoin) {
1238 continue; // both winners are the same segment, so there's no additional overlap
1239 }
1240 const SkOpSegment* innerOpp = inner->oppPtTStart()->segment();
1241 const SkOpPtT* overlapS;
1242 const SkOpPtT* overlapE;
1243 if ((outerOpp == innerCoin && SkOpPtT::Overlaps(outer->oppPtTStart(),
1244 outer->oppPtTEnd(),inner->coinPtTStart(), inner->coinPtTEnd(), &overlapS,
1245 &overlapE))
1246 || (outerCoin == innerOpp && SkOpPtT::Overlaps(outer->coinPtTStart(),
1247 outer->coinPtTEnd(), inner->oppPtTStart(), inner->oppPtTEnd(),
1248 &overlapS, &overlapE))
1249 || (outerOpp == innerOpp && SkOpPtT::Overlaps(outer->oppPtTStart(),
1250 outer->oppPtTEnd(), inner->oppPtTStart(), inner->oppPtTEnd(),
1251 &overlapS, &overlapE))) {
1252 if (!overlaps->addOverlap(outerCoin, outerOpp, innerCoin, innerOpp,
1253 overlapS, overlapE)) {
1254 return false;
1255 }
1256 }
1257 }
1258 outer = outer->next();
1259 }
1260 return true;
1261 }
1262
fixUp(SkOpPtT * deleted,const SkOpPtT * kept)1263 void SkOpCoincidence::fixUp(SkOpPtT* deleted, const SkOpPtT* kept) {
1264 SkOPASSERT(deleted != kept);
1265 if (fHead) {
1266 this->fixUp(fHead, deleted, kept);
1267 }
1268 if (fTop) {
1269 this->fixUp(fTop, deleted, kept);
1270 }
1271 }
1272
fixUp(SkCoincidentSpans * coin,SkOpPtT * deleted,const SkOpPtT * kept)1273 void SkOpCoincidence::fixUp(SkCoincidentSpans* coin, SkOpPtT* deleted, const SkOpPtT* kept) {
1274 SkCoincidentSpans* head = coin;
1275 do {
1276 if (coin->coinPtTStart() == deleted) {
1277 if (coin->coinPtTEnd()->span() == kept->span()) {
1278 this->release(head, coin);
1279 continue;
1280 }
1281 coin->setCoinPtTStart(kept);
1282 }
1283 if (coin->coinPtTEnd() == deleted) {
1284 if (coin->coinPtTStart()->span() == kept->span()) {
1285 this->release(head, coin);
1286 continue;
1287 }
1288 coin->setCoinPtTEnd(kept);
1289 }
1290 if (coin->oppPtTStart() == deleted) {
1291 if (coin->oppPtTEnd()->span() == kept->span()) {
1292 this->release(head, coin);
1293 continue;
1294 }
1295 coin->setOppPtTStart(kept);
1296 }
1297 if (coin->oppPtTEnd() == deleted) {
1298 if (coin->oppPtTStart()->span() == kept->span()) {
1299 this->release(head, coin);
1300 continue;
1301 }
1302 coin->setOppPtTEnd(kept);
1303 }
1304 } while ((coin = coin->next()));
1305 }
1306
1307 // Please keep this in sync with debugMark()
1308 /* this sets up the coincidence links in the segments when the coincidence crosses multiple spans */
mark(DEBUG_COIN_DECLARE_ONLY_PARAMS ())1309 bool SkOpCoincidence::mark(DEBUG_COIN_DECLARE_ONLY_PARAMS()) {
1310 DEBUG_SET_PHASE();
1311 SkCoincidentSpans* coin = fHead;
1312 if (!coin) {
1313 return true;
1314 }
1315 do {
1316 SkOpSpanBase* startBase = coin->coinPtTStartWritable()->span();
1317 FAIL_IF(!startBase->upCastable());
1318 SkOpSpan* start = startBase->upCast();
1319 FAIL_IF(start->deleted());
1320 SkOpSpanBase* end = coin->coinPtTEndWritable()->span();
1321 SkOPASSERT(!end->deleted());
1322 SkOpSpanBase* oStart = coin->oppPtTStartWritable()->span();
1323 SkOPASSERT(!oStart->deleted());
1324 SkOpSpanBase* oEnd = coin->oppPtTEndWritable()->span();
1325 SkASSERT(!oEnd->deleted());
1326 bool flipped = coin->flipped();
1327 if (flipped) {
1328 SkTSwap(oStart, oEnd);
1329 }
1330 /* coin and opp spans may not match up. Mark the ends, and then let the interior
1331 get marked as many times as the spans allow */
1332 FAIL_IF(!oStart->upCastable());
1333 start->insertCoincidence(oStart->upCast());
1334 end->insertCoinEnd(oEnd);
1335 const SkOpSegment* segment = start->segment();
1336 const SkOpSegment* oSegment = oStart->segment();
1337 SkOpSpanBase* next = start;
1338 SkOpSpanBase* oNext = oStart;
1339 bool ordered;
1340 FAIL_IF(!coin->ordered(&ordered));
1341 while ((next = next->upCast()->next()) != end) {
1342 FAIL_IF(!next->upCastable());
1343 FAIL_IF(!next->upCast()->insertCoincidence(oSegment, flipped, ordered));
1344 }
1345 while ((oNext = oNext->upCast()->next()) != oEnd) {
1346 FAIL_IF(!oNext->upCastable());
1347 FAIL_IF(!oNext->upCast()->insertCoincidence(segment, flipped, ordered));
1348 }
1349 } while ((coin = coin->next()));
1350 return true;
1351 }
1352
1353 // Please keep in sync with debugMarkCollapsed()
markCollapsed(SkCoincidentSpans * coin,SkOpPtT * test)1354 void SkOpCoincidence::markCollapsed(SkCoincidentSpans* coin, SkOpPtT* test) {
1355 SkCoincidentSpans* head = coin;
1356 while (coin) {
1357 if (coin->collapsed(test)) {
1358 if (zero_or_one(coin->coinPtTStart()->fT) && zero_or_one(coin->coinPtTEnd()->fT)) {
1359 coin->coinPtTStartWritable()->segment()->markAllDone();
1360 }
1361 if (zero_or_one(coin->oppPtTStart()->fT) && zero_or_one(coin->oppPtTEnd()->fT)) {
1362 coin->oppPtTStartWritable()->segment()->markAllDone();
1363 }
1364 this->release(head, coin);
1365 }
1366 coin = coin->next();
1367 }
1368 }
1369
1370 // Please keep in sync with debugMarkCollapsed()
markCollapsed(SkOpPtT * test)1371 void SkOpCoincidence::markCollapsed(SkOpPtT* test) {
1372 markCollapsed(fHead, test);
1373 markCollapsed(fTop, test);
1374 }
1375
Ordered(const SkOpSegment * coinSeg,const SkOpSegment * oppSeg)1376 bool SkOpCoincidence::Ordered(const SkOpSegment* coinSeg, const SkOpSegment* oppSeg) {
1377 if (coinSeg->verb() < oppSeg->verb()) {
1378 return true;
1379 }
1380 if (coinSeg->verb() > oppSeg->verb()) {
1381 return false;
1382 }
1383 int count = (SkPathOpsVerbToPoints(coinSeg->verb()) + 1) * 2;
1384 const SkScalar* cPt = &coinSeg->pts()[0].fX;
1385 const SkScalar* oPt = &oppSeg->pts()[0].fX;
1386 for (int index = 0; index < count; ++index) {
1387 if (*cPt < *oPt) {
1388 return true;
1389 }
1390 if (*cPt > *oPt) {
1391 return false;
1392 }
1393 ++cPt;
1394 ++oPt;
1395 }
1396 return true;
1397 }
1398
overlap(const SkOpPtT * coin1s,const SkOpPtT * coin1e,const SkOpPtT * coin2s,const SkOpPtT * coin2e,double * overS,double * overE) const1399 bool SkOpCoincidence::overlap(const SkOpPtT* coin1s, const SkOpPtT* coin1e,
1400 const SkOpPtT* coin2s, const SkOpPtT* coin2e, double* overS, double* overE) const {
1401 SkASSERT(coin1s->segment() == coin2s->segment());
1402 *overS = SkTMax(SkTMin(coin1s->fT, coin1e->fT), SkTMin(coin2s->fT, coin2e->fT));
1403 *overE = SkTMin(SkTMax(coin1s->fT, coin1e->fT), SkTMax(coin2s->fT, coin2e->fT));
1404 return *overS < *overE;
1405 }
1406
1407 // Commented-out lines keep this in sync with debugRelease()
release(const SkOpSegment * deleted)1408 void SkOpCoincidence::release(const SkOpSegment* deleted) {
1409 SkCoincidentSpans* coin = fHead;
1410 if (!coin) {
1411 return;
1412 }
1413 do {
1414 if (coin->coinPtTStart()->segment() == deleted
1415 || coin->coinPtTEnd()->segment() == deleted
1416 || coin->oppPtTStart()->segment() == deleted
1417 || coin->oppPtTEnd()->segment() == deleted) {
1418 this->release(fHead, coin);
1419 }
1420 } while ((coin = coin->next()));
1421 }
1422