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