1/*
2 * Copyright 2012 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 "src/core/SkPointPriv.h"
8#include "src/pathops/SkOpCoincidence.h"
9#include "src/pathops/SkOpContour.h"
10#include "src/pathops/SkOpSegment.h"
11#include "src/pathops/SkPathWriter.h"
12
13#include <utility>
14
15/*
16After computing raw intersections, post process all segments to:
17- find small collections of points that can be collapsed to a single point
18- find missing intersections to resolve differences caused by different algorithms
19
20Consider segments containing tiny or small intervals. Consider coincident segments
21because coincidence finds intersections through distance measurement that non-coincident
22intersection tests cannot.
23 */
24
25#define F (false) // discard the edge
26#define T (true) // keep the edge
27
28static const bool gUnaryActiveEdge[2][2] = {
29// from=0 from=1
30// to=0,1 to=0,1
31 {F, T}, {T, F},
32};
33
34static const bool gActiveEdge[kXOR_SkPathOp + 1][2][2][2][2] = {
35// miFrom=0 miFrom=1
36// miTo=0 miTo=1 miTo=0 miTo=1
37// suFrom=0 1 suFrom=0 1 suFrom=0 1 suFrom=0 1
38// suTo=0,1 suTo=0,1 suTo=0,1 suTo=0,1 suTo=0,1 suTo=0,1 suTo=0,1 suTo=0,1
39 {{{{F, F}, {F, F}}, {{T, F}, {T, F}}}, {{{T, T}, {F, F}}, {{F, T}, {T, F}}}}, // mi - su
40 {{{{F, F}, {F, F}}, {{F, T}, {F, T}}}, {{{F, F}, {T, T}}, {{F, T}, {T, F}}}}, // mi & su
41 {{{{F, T}, {T, F}}, {{T, T}, {F, F}}}, {{{T, F}, {T, F}}, {{F, F}, {F, F}}}}, // mi | su
42 {{{{F, T}, {T, F}}, {{T, F}, {F, T}}}, {{{T, F}, {F, T}}, {{F, T}, {T, F}}}}, // mi ^ su
43};
44
45#undef F
46#undef T
47
48SkOpAngle* SkOpSegment::activeAngle(SkOpSpanBase* start, SkOpSpanBase** startPtr,
49 SkOpSpanBase** endPtr, bool* done) {
50 if (SkOpAngle* result = activeAngleInner(start, startPtr, endPtr, done)) {
51 return result;
52 }
53 if (SkOpAngle* result = activeAngleOther(start, startPtr, endPtr, done)) {
54 return result;
55 }
56 return nullptr;
57}
58
59SkOpAngle* SkOpSegment::activeAngleInner(SkOpSpanBase* start, SkOpSpanBase** startPtr,
60 SkOpSpanBase** endPtr, bool* done) {
61 SkOpSpan* upSpan = start->upCastable();
62 if (upSpan) {
63 if (upSpan->windValue() || upSpan->oppValue()) {
64 SkOpSpanBase* next = upSpan->next();
65 if (!*endPtr) {
66 *startPtr = start;
67 *endPtr = next;
68 }
69 if (!upSpan->done()) {
70 if (upSpan->windSum() != SK_MinS32) {
71 return spanToAngle(start, next);
72 }
73 *done = false;
74 }
75 } else {
76 SkASSERT(upSpan->done());
77 }
78 }
79 SkOpSpan* downSpan = start->prev();
80 // edge leading into junction
81 if (downSpan) {
82 if (downSpan->windValue() || downSpan->oppValue()) {
83 if (!*endPtr) {
84 *startPtr = start;
85 *endPtr = downSpan;
86 }
87 if (!downSpan->done()) {
88 if (downSpan->windSum() != SK_MinS32) {
89 return spanToAngle(start, downSpan);
90 }
91 *done = false;
92 }
93 } else {
94 SkASSERT(downSpan->done());
95 }
96 }
97 return nullptr;
98}
99
100SkOpAngle* SkOpSegment::activeAngleOther(SkOpSpanBase* start, SkOpSpanBase** startPtr,
101 SkOpSpanBase** endPtr, bool* done) {
102 SkOpPtT* oPtT = start->ptT()->next();
103 SkOpSegment* other = oPtT->segment();
104 SkOpSpanBase* oSpan = oPtT->span();
105 return other->activeAngleInner(oSpan, startPtr, endPtr, done);
106}
107
108bool SkOpSegment::activeOp(SkOpSpanBase* start, SkOpSpanBase* end, int xorMiMask, int xorSuMask,
109 SkPathOp op) {
110 int sumMiWinding = this->updateWinding(end, start);
111 int sumSuWinding = this->updateOppWinding(end, start);
112#if DEBUG_LIMIT_WIND_SUM
113 SkASSERT(abs(sumMiWinding) <= DEBUG_LIMIT_WIND_SUM);
114 SkASSERT(abs(sumSuWinding) <= DEBUG_LIMIT_WIND_SUM);
115#endif
116 if (this->operand()) {
117 using std::swap;
118 swap(sumMiWinding, sumSuWinding);
119 }
120 return this->activeOp(xorMiMask, xorSuMask, start, end, op, &sumMiWinding, &sumSuWinding);
121}
122
123bool SkOpSegment::activeOp(int xorMiMask, int xorSuMask, SkOpSpanBase* start, SkOpSpanBase* end,
124 SkPathOp op, int* sumMiWinding, int* sumSuWinding) {
125 int maxWinding, sumWinding, oppMaxWinding, oppSumWinding;
126 this->setUpWindings(start, end, sumMiWinding, sumSuWinding,
127 &maxWinding, &sumWinding, &oppMaxWinding, &oppSumWinding);
128 bool miFrom;
129 bool miTo;
130 bool suFrom;
131 bool suTo;
132 if (operand()) {
133 miFrom = (oppMaxWinding & xorMiMask) != 0;
134 miTo = (oppSumWinding & xorMiMask) != 0;
135 suFrom = (maxWinding & xorSuMask) != 0;
136 suTo = (sumWinding & xorSuMask) != 0;
137 } else {
138 miFrom = (maxWinding & xorMiMask) != 0;
139 miTo = (sumWinding & xorMiMask) != 0;
140 suFrom = (oppMaxWinding & xorSuMask) != 0;
141 suTo = (oppSumWinding & xorSuMask) != 0;
142 }
143 bool result = gActiveEdge[op][miFrom][miTo][suFrom][suTo];
144#if DEBUG_ACTIVE_OP
145 SkDebugf("%s id=%d t=%1.9g tEnd=%1.9g op=%s miFrom=%d miTo=%d suFrom=%d suTo=%d result=%d\n",
146 __FUNCTION__, debugID(), start->t(), end->t(),
147 SkPathOpsDebug::kPathOpStr[op], miFrom, miTo, suFrom, suTo, result);
148#endif
149 return result;
150}
151
152bool SkOpSegment::activeWinding(SkOpSpanBase* start, SkOpSpanBase* end) {
153 int sumWinding = updateWinding(end, start);
154 return activeWinding(start, end, &sumWinding);
155}
156
157bool SkOpSegment::activeWinding(SkOpSpanBase* start, SkOpSpanBase* end, int* sumWinding) {
158 int maxWinding;
159 setUpWinding(start, end, &maxWinding, sumWinding);
160 bool from = maxWinding != 0;
161 bool to = *sumWinding != 0;
162 bool result = gUnaryActiveEdge[from][to];
163 return result;
164}
165
166bool SkOpSegment::addCurveTo(const SkOpSpanBase* start, const SkOpSpanBase* end,
167 SkPathWriter* path) const {
168 const SkOpSpan* spanStart = start->starter(end);
169 FAIL_IF(spanStart->alreadyAdded());
170 const_cast<SkOpSpan*>(spanStart)->markAdded();
171 SkDCurveSweep curvePart;
172 start->segment()->subDivide(start, end, &curvePart.fCurve);
173 curvePart.setCurveHullSweep(fVerb);
174 SkPath::Verb verb = curvePart.isCurve() ? fVerb : SkPath::kLine_Verb;
175 path->deferredMove(start->ptT());
176 switch (verb) {
177 case SkPath::kLine_Verb:
178 FAIL_IF(!path->deferredLine(end->ptT()));
179 break;
180 case SkPath::kQuad_Verb:
181 path->quadTo(curvePart.fCurve.fQuad[1].asSkPoint(), end->ptT());
182 break;
183 case SkPath::kConic_Verb:
184 path->conicTo(curvePart.fCurve.fConic[1].asSkPoint(), end->ptT(),
185 curvePart.fCurve.fConic.fWeight);
186 break;
187 case SkPath::kCubic_Verb:
188 path->cubicTo(curvePart.fCurve.fCubic[1].asSkPoint(),
189 curvePart.fCurve.fCubic[2].asSkPoint(), end->ptT());
190 break;
191 default:
192 SkASSERT(0);
193 }
194 return true;
195}
196
197const SkOpPtT* SkOpSegment::existing(double t, const SkOpSegment* opp) const {
198 const SkOpSpanBase* test = &fHead;
199 const SkOpPtT* testPtT;
200 SkPoint pt = this->ptAtT(t);
201 do {
202 testPtT = test->ptT();
203 if (testPtT->fT == t) {
204 break;
205 }
206 if (!this->match(testPtT, this, t, pt)) {
207 if (t < testPtT->fT) {
208 return nullptr;
209 }
210 continue;
211 }
212 if (!opp) {
213 return testPtT;
214 }
215 const SkOpPtT* loop = testPtT->next();
216 while (loop != testPtT) {
217 if (loop->segment() == this && loop->fT == t && loop->fPt == pt) {
218 goto foundMatch;
219 }
220 loop = loop->next();
221 }
222 return nullptr;
223 } while ((test = test->upCast()->next()));
224foundMatch:
225 return opp && !test->contains(opp) ? nullptr : testPtT;
226}
227
228// break the span so that the coincident part does not change the angle of the remainder
229bool SkOpSegment::addExpanded(double newT, const SkOpSpanBase* test, bool* startOver) {
230 if (this->contains(newT)) {
231 return true;
232 }
233 this->globalState()->resetAllocatedOpSpan();
234 FAIL_IF(!between(0, newT, 1));
235 SkOpPtT* newPtT = this->addT(newT);
236 *startOver |= this->globalState()->allocatedOpSpan();
237 if (!newPtT) {
238 return false;
239 }
240 newPtT->fPt = this->ptAtT(newT);
241 SkOpPtT* oppPrev = test->ptT()->oppPrev(newPtT);
242 if (oppPrev) {
243 // const cast away to change linked list; pt/t values stays unchanged
244 SkOpSpanBase* writableTest = const_cast<SkOpSpanBase*>(test);
245 writableTest->mergeMatches(newPtT->span());
246 writableTest->ptT()->addOpp(newPtT, oppPrev);
247 writableTest->checkForCollapsedCoincidence();
248 }
249 return true;
250}
251
252// Please keep this in sync with debugAddT()
253SkOpPtT* SkOpSegment::addT(double t, const SkPoint& pt) {
254 debugValidate();
255 SkOpSpanBase* spanBase = &fHead;
256 do {
257 SkOpPtT* result = spanBase->ptT();
258 if (t == result->fT || (!zero_or_one(t) && this->match(result, this, t, pt))) {
259 spanBase->bumpSpanAdds();
260 return result;
261 }
262 if (t < result->fT) {
263 SkOpSpan* prev = result->span()->prev();
264 FAIL_WITH_NULL_IF(!prev);
265 // marks in global state that new op span has been allocated
266 SkOpSpan* span = this->insert(prev);
267 span->init(this, prev, t, pt);
268 this->debugValidate();
269#if DEBUG_ADD_T
270 SkDebugf("%s insert t=%1.9g segID=%d spanID=%d\n", __FUNCTION__, t,
271 span->segment()->debugID(), span->debugID());
272#endif
273 span->bumpSpanAdds();
274 return span->ptT();
275 }
276 FAIL_WITH_NULL_IF(spanBase == &fTail);
277 } while ((spanBase = spanBase->upCast()->next()));
278 SkASSERT(0);
279 return nullptr; // we never get here, but need this to satisfy compiler
280}
281
282SkOpPtT* SkOpSegment::addT(double t) {
283 return addT(t, this->ptAtT(t));
284}
285
286void SkOpSegment::calcAngles() {
287 bool activePrior = !fHead.isCanceled();
288 if (activePrior && !fHead.simple()) {
289 addStartSpan();
290 }
291 SkOpSpan* prior = &fHead;
292 SkOpSpanBase* spanBase = fHead.next();
293 while (spanBase != &fTail) {
294 if (activePrior) {
295 SkOpAngle* priorAngle = this->globalState()->allocator()->make<SkOpAngle>();
296 priorAngle->set(spanBase, prior);
297 spanBase->setFromAngle(priorAngle);
298 }
299 SkOpSpan* span = spanBase->upCast();
300 bool active = !span->isCanceled();
301 SkOpSpanBase* next = span->next();
302 if (active) {
303 SkOpAngle* angle = this->globalState()->allocator()->make<SkOpAngle>();
304 angle->set(span, next);
305 span->setToAngle(angle);
306 }
307 activePrior = active;
308 prior = span;
309 spanBase = next;
310 }
311 if (activePrior && !fTail.simple()) {
312 addEndSpan();
313 }
314}
315
316// Please keep this in sync with debugClearAll()
317void SkOpSegment::clearAll() {
318 SkOpSpan* span = &fHead;
319 do {
320 this->clearOne(span);
321 } while ((span = span->next()->upCastable()));
322 this->globalState()->coincidence()->release(this);
323}
324
325// Please keep this in sync with debugClearOne()
326void SkOpSegment::clearOne(SkOpSpan* span) {
327 span->setWindValue(0);
328 span->setOppValue(0);
329 this->markDone(span);
330}
331
332SkOpSpanBase::Collapsed SkOpSegment::collapsed(double s, double e) const {
333 const SkOpSpanBase* span = &fHead;
334 do {
335 SkOpSpanBase::Collapsed result = span->collapsed(s, e);
336 if (SkOpSpanBase::Collapsed::kNo != result) {
337 return result;
338 }
339 } while (span->upCastable() && (span = span->upCast()->next()));
340 return SkOpSpanBase::Collapsed::kNo;
341}
342
343bool SkOpSegment::ComputeOneSum(const SkOpAngle* baseAngle, SkOpAngle* nextAngle,
344 SkOpAngle::IncludeType includeType) {
345 SkOpSegment* baseSegment = baseAngle->segment();
346 int sumMiWinding = baseSegment->updateWindingReverse(baseAngle);
347 int sumSuWinding;
348 bool binary = includeType >= SkOpAngle::kBinarySingle;
349 if (binary) {
350 sumSuWinding = baseSegment->updateOppWindingReverse(baseAngle);
351 if (baseSegment->operand()) {
352 using std::swap;
353 swap(sumMiWinding, sumSuWinding);
354 }
355 }
356 SkOpSegment* nextSegment = nextAngle->segment();
357 int maxWinding, sumWinding;
358 SkOpSpanBase* last = nullptr;
359 if (binary) {
360 int oppMaxWinding, oppSumWinding;
361 nextSegment->setUpWindings(nextAngle->start(), nextAngle->end(), &sumMiWinding,
362 &sumSuWinding, &maxWinding, &sumWinding, &oppMaxWinding, &oppSumWinding);
363 if (!nextSegment->markAngle(maxWinding, sumWinding, oppMaxWinding, oppSumWinding,
364 nextAngle, &last)) {
365 return false;
366 }
367 } else {
368 nextSegment->setUpWindings(nextAngle->start(), nextAngle->end(), &sumMiWinding,
369 &maxWinding, &sumWinding);
370 if (!nextSegment->markAngle(maxWinding, sumWinding, nextAngle, &last)) {
371 return false;
372 }
373 }
374 nextAngle->setLastMarked(last);
375 return true;
376}
377
378bool SkOpSegment::ComputeOneSumReverse(SkOpAngle* baseAngle, SkOpAngle* nextAngle,
379 SkOpAngle::IncludeType includeType) {
380 SkOpSegment* baseSegment = baseAngle->segment();
381 int sumMiWinding = baseSegment->updateWinding(baseAngle);
382 int sumSuWinding;
383 bool binary = includeType >= SkOpAngle::kBinarySingle;
384 if (binary) {
385 sumSuWinding = baseSegment->updateOppWinding(baseAngle);
386 if (baseSegment->operand()) {
387 using std::swap;
388 swap(sumMiWinding, sumSuWinding);
389 }
390 }
391 SkOpSegment* nextSegment = nextAngle->segment();
392 int maxWinding, sumWinding;
393 SkOpSpanBase* last = nullptr;
394 if (binary) {
395 int oppMaxWinding, oppSumWinding;
396 nextSegment->setUpWindings(nextAngle->end(), nextAngle->start(), &sumMiWinding,
397 &sumSuWinding, &maxWinding, &sumWinding, &oppMaxWinding, &oppSumWinding);
398 if (!nextSegment->markAngle(maxWinding, sumWinding, oppMaxWinding, oppSumWinding,
399 nextAngle, &last)) {
400 return false;
401 }
402 } else {
403 nextSegment->setUpWindings(nextAngle->end(), nextAngle->start(), &sumMiWinding,
404 &maxWinding, &sumWinding);
405 if (!nextSegment->markAngle(maxWinding, sumWinding, nextAngle, &last)) {
406 return false;
407 }
408 }
409 nextAngle->setLastMarked(last);
410 return true;
411}
412
413// at this point, the span is already ordered, or unorderable
414int SkOpSegment::computeSum(SkOpSpanBase* start, SkOpSpanBase* end,
415 SkOpAngle::IncludeType includeType) {
416 SkASSERT(includeType != SkOpAngle::kUnaryXor);
417 SkOpAngle* firstAngle = this->spanToAngle(end, start);
418 if (nullptr == firstAngle || nullptr == firstAngle->next()) {
419 return SK_NaN32;
420 }
421 // if all angles have a computed winding,
422 // or if no adjacent angles are orderable,
423 // or if adjacent orderable angles have no computed winding,
424 // there's nothing to do
425 // if two orderable angles are adjacent, and both are next to orderable angles,
426 // and one has winding computed, transfer to the other
427 SkOpAngle* baseAngle = nullptr;
428 bool tryReverse = false;
429 // look for counterclockwise transfers
430 SkOpAngle* angle = firstAngle->previous();
431 SkOpAngle* next = angle->next();
432 firstAngle = next;
433 do {
434 SkOpAngle* prior = angle;
435 angle = next;
436 next = angle->next();
437 SkASSERT(prior->next() == angle);
438 SkASSERT(angle->next() == next);
439 if (prior->unorderable() || angle->unorderable() || next->unorderable()) {
440 baseAngle = nullptr;
441 continue;
442 }
443 int testWinding = angle->starter()->windSum();
444 if (SK_MinS32 != testWinding) {
445 baseAngle = angle;
446 tryReverse = true;
447 continue;
448 }
449 if (baseAngle) {
450 ComputeOneSum(baseAngle, angle, includeType);
451 baseAngle = SK_MinS32 != angle->starter()->windSum() ? angle : nullptr;
452 }
453 } while (next != firstAngle);
454 if (baseAngle && SK_MinS32 == firstAngle->starter()->windSum()) {
455 firstAngle = baseAngle;
456 tryReverse = true;
457 }
458 if (tryReverse) {
459 baseAngle = nullptr;
460 SkOpAngle* prior = firstAngle;
461 do {
462 angle = prior;
463 prior = angle->previous();
464 SkASSERT(prior->next() == angle);
465 next = angle->next();
466 if (prior->unorderable() || angle->unorderable() || next->unorderable()) {
467 baseAngle = nullptr;
468 continue;
469 }
470 int testWinding = angle->starter()->windSum();
471 if (SK_MinS32 != testWinding) {
472 baseAngle = angle;
473 continue;
474 }
475 if (baseAngle) {
476 ComputeOneSumReverse(baseAngle, angle, includeType);
477 baseAngle = SK_MinS32 != angle->starter()->windSum() ? angle : nullptr;
478 }
479 } while (prior != firstAngle);
480 }
481 return start->starter(end)->windSum();
482}
483
484bool SkOpSegment::contains(double newT) const {
485 const SkOpSpanBase* spanBase = &fHead;
486 do {
487 if (spanBase->ptT()->contains(this, newT)) {
488 return true;
489 }
490 if (spanBase == &fTail) {
491 break;
492 }
493 spanBase = spanBase->upCast()->next();
494 } while (true);
495 return false;
496}
497
498void SkOpSegment::release(const SkOpSpan* span) {
499 if (span->done()) {
500 --fDoneCount;
501 }
502 --fCount;
503 SkOPASSERT(fCount >= fDoneCount);
504}
505
506#if DEBUG_ANGLE
507// called only by debugCheckNearCoincidence
508double SkOpSegment::distSq(double t, const SkOpAngle* oppAngle) const {
509 SkDPoint testPt = this->dPtAtT(t);
510 SkDLine testPerp = {{ testPt, testPt }};
511 SkDVector slope = this->dSlopeAtT(t);
512 testPerp[1].fX += slope.fY;
513 testPerp[1].fY -= slope.fX;
514 SkIntersections i;
515 const SkOpSegment* oppSegment = oppAngle->segment();
516 (*CurveIntersectRay[oppSegment->verb()])(oppSegment->pts(), oppSegment->weight(), testPerp, &i);
517 double closestDistSq = SK_ScalarInfinity;
518 for (int index = 0; index < i.used(); ++index) {
519 if (!between(oppAngle->start()->t(), i[0][index], oppAngle->end()->t())) {
520 continue;
521 }
522 double testDistSq = testPt.distanceSquared(i.pt(index));
523 if (closestDistSq > testDistSq) {
524 closestDistSq = testDistSq;
525 }
526 }
527 return closestDistSq;
528}
529#endif
530
531/*
532 The M and S variable name parts stand for the operators.
533 Mi stands for Minuend (see wiki subtraction, analogous to difference)
534 Su stands for Subtrahend
535 The Opp variable name part designates that the value is for the Opposite operator.
536 Opposite values result from combining coincident spans.
537 */
538SkOpSegment* SkOpSegment::findNextOp(SkTDArray<SkOpSpanBase*>* chase, SkOpSpanBase** nextStart,
539 SkOpSpanBase** nextEnd, bool* unsortable, bool* simple,
540 SkPathOp op, int xorMiMask, int xorSuMask) {
541 SkOpSpanBase* start = *nextStart;
542 SkOpSpanBase* end = *nextEnd;
543 SkASSERT(start != end);
544 int step = start->step(end);
545 SkOpSegment* other = this->isSimple(nextStart, &step); // advances nextStart
546 if ((*simple = other)) {
547 // mark the smaller of startIndex, endIndex done, and all adjacent
548 // spans with the same T value (but not 'other' spans)
549#if DEBUG_WINDING
550 SkDebugf("%s simple\n", __FUNCTION__);
551#endif
552 SkOpSpan* startSpan = start->starter(end);
553 if (startSpan->done()) {
554 return nullptr;
555 }
556 markDone(startSpan);
557 *nextEnd = step > 0 ? (*nextStart)->upCast()->next() : (*nextStart)->prev();
558 return other;
559 }
560 SkOpSpanBase* endNear = step > 0 ? (*nextStart)->upCast()->next() : (*nextStart)->prev();
561 SkASSERT(endNear == end); // is this ever not end?
562 SkASSERT(endNear);
563 SkASSERT(start != endNear);
564 SkASSERT((start->t() < endNear->t()) ^ (step < 0));
565 // more than one viable candidate -- measure angles to find best
566 int calcWinding = computeSum(start, endNear, SkOpAngle::kBinaryOpp);
567 bool sortable = calcWinding != SK_NaN32;
568 if (!sortable) {
569 *unsortable = true;
570 markDone(start->starter(end));
571 return nullptr;
572 }
573 SkOpAngle* angle = this->spanToAngle(end, start);
574 if (angle->unorderable()) {
575 *unsortable = true;
576 markDone(start->starter(end));
577 return nullptr;
578 }
579#if DEBUG_SORT
580 SkDebugf("%s\n", __FUNCTION__);
581 angle->debugLoop();
582#endif
583 int sumMiWinding = updateWinding(end, start);
584 if (sumMiWinding == SK_MinS32) {
585 *unsortable = true;
586 markDone(start->starter(end));
587 return nullptr;
588 }
589 int sumSuWinding = updateOppWinding(end, start);
590 if (operand()) {
591 using std::swap;
592 swap(sumMiWinding, sumSuWinding);
593 }
594 SkOpAngle* nextAngle = angle->next();
595 const SkOpAngle* foundAngle = nullptr;
596 bool foundDone = false;
597 // iterate through the angle, and compute everyone's winding
598 SkOpSegment* nextSegment;
599 int activeCount = 0;
600 do {
601 nextSegment = nextAngle->segment();
602 bool activeAngle = nextSegment->activeOp(xorMiMask, xorSuMask, nextAngle->start(),
603 nextAngle->end(), op, &sumMiWinding, &sumSuWinding);
604 if (activeAngle) {
605 ++activeCount;
606 if (!foundAngle || (foundDone && activeCount & 1)) {
607 foundAngle = nextAngle;
608 foundDone = nextSegment->done(nextAngle);
609 }
610 }
611 if (nextSegment->done()) {
612 continue;
613 }
614 if (!activeAngle) {
615 (void) nextSegment->markAndChaseDone(nextAngle->start(), nextAngle->end(), nullptr);
616 }
617 SkOpSpanBase* last = nextAngle->lastMarked();
618 if (last) {
619 SkASSERT(!SkPathOpsDebug::ChaseContains(*chase, last));
620 *chase->append() = last;
621#if DEBUG_WINDING
622 SkDebugf("%s chase.append segment=%d span=%d", __FUNCTION__,
623 last->segment()->debugID(), last->debugID());
624 if (!last->final()) {
625 SkDebugf(" windSum=%d", last->upCast()->windSum());
626 }
627 SkDebugf("\n");
628#endif
629 }
630 } while ((nextAngle = nextAngle->next()) != angle);
631 start->segment()->markDone(start->starter(end));
632 if (!foundAngle) {
633 return nullptr;
634 }
635 *nextStart = foundAngle->start();
636 *nextEnd = foundAngle->end();
637 nextSegment = foundAngle->segment();
638#if DEBUG_WINDING
639 SkDebugf("%s from:[%d] to:[%d] start=%d end=%d\n",
640 __FUNCTION__, debugID(), nextSegment->debugID(), *nextStart, *nextEnd);
641 #endif
642 return nextSegment;
643}
644
645SkOpSegment* SkOpSegment::findNextWinding(SkTDArray<SkOpSpanBase*>* chase,
646 SkOpSpanBase** nextStart, SkOpSpanBase** nextEnd, bool* unsortable) {
647 SkOpSpanBase* start = *nextStart;
648 SkOpSpanBase* end = *nextEnd;
649 SkASSERT(start != end);
650 int step = start->step(end);
651 SkOpSegment* other = this->isSimple(nextStart, &step); // advances nextStart
652 if (other) {
653 // mark the smaller of startIndex, endIndex done, and all adjacent
654 // spans with the same T value (but not 'other' spans)
655#if DEBUG_WINDING
656 SkDebugf("%s simple\n", __FUNCTION__);
657#endif
658 SkOpSpan* startSpan = start->starter(end);
659 if (startSpan->done()) {
660 return nullptr;
661 }
662 markDone(startSpan);
663 *nextEnd = step > 0 ? (*nextStart)->upCast()->next() : (*nextStart)->prev();
664 return other;
665 }
666 SkOpSpanBase* endNear = step > 0 ? (*nextStart)->upCast()->next() : (*nextStart)->prev();
667 SkASSERT(endNear == end); // is this ever not end?
668 SkASSERT(endNear);
669 SkASSERT(start != endNear);
670 SkASSERT((start->t() < endNear->t()) ^ (step < 0));
671 // more than one viable candidate -- measure angles to find best
672 int calcWinding = computeSum(start, endNear, SkOpAngle::kUnaryWinding);
673 bool sortable = calcWinding != SK_NaN32;
674 if (!sortable) {
675 *unsortable = true;
676 markDone(start->starter(end));
677 return nullptr;
678 }
679 SkOpAngle* angle = this->spanToAngle(end, start);
680 if (angle->unorderable()) {
681 *unsortable = true;
682 markDone(start->starter(end));
683 return nullptr;
684 }
685#if DEBUG_SORT
686 SkDebugf("%s\n", __FUNCTION__);
687 angle->debugLoop();
688#endif
689 int sumWinding = updateWinding(end, start);
690 SkOpAngle* nextAngle = angle->next();
691 const SkOpAngle* foundAngle = nullptr;
692 bool foundDone = false;
693 // iterate through the angle, and compute everyone's winding
694 SkOpSegment* nextSegment;
695 int activeCount = 0;
696 do {
697 nextSegment = nextAngle->segment();
698 bool activeAngle = nextSegment->activeWinding(nextAngle->start(), nextAngle->end(),
699 &sumWinding);
700 if (activeAngle) {
701 ++activeCount;
702 if (!foundAngle || (foundDone && activeCount & 1)) {
703 foundAngle = nextAngle;
704 foundDone = nextSegment->done(nextAngle);
705 }
706 }
707 if (nextSegment->done()) {
708 continue;
709 }
710 if (!activeAngle) {
711 (void) nextSegment->markAndChaseDone(nextAngle->start(), nextAngle->end(), nullptr);
712 }
713 SkOpSpanBase* last = nextAngle->lastMarked();
714 if (last) {
715 SkASSERT(!SkPathOpsDebug::ChaseContains(*chase, last));
716 *chase->append() = last;
717#if DEBUG_WINDING
718 SkDebugf("%s chase.append segment=%d span=%d", __FUNCTION__,
719 last->segment()->debugID(), last->debugID());
720 if (!last->final()) {
721 SkDebugf(" windSum=%d", last->upCast()->windSum());
722 }
723 SkDebugf("\n");
724#endif
725 }
726 } while ((nextAngle = nextAngle->next()) != angle);
727 start->segment()->markDone(start->starter(end));
728 if (!foundAngle) {
729 return nullptr;
730 }
731 *nextStart = foundAngle->start();
732 *nextEnd = foundAngle->end();
733 nextSegment = foundAngle->segment();
734#if DEBUG_WINDING
735 SkDebugf("%s from:[%d] to:[%d] start=%d end=%d\n",
736 __FUNCTION__, debugID(), nextSegment->debugID(), *nextStart, *nextEnd);
737 #endif
738 return nextSegment;
739}
740
741SkOpSegment* SkOpSegment::findNextXor(SkOpSpanBase** nextStart, SkOpSpanBase** nextEnd,
742 bool* unsortable) {
743 SkOpSpanBase* start = *nextStart;
744 SkOpSpanBase* end = *nextEnd;
745 SkASSERT(start != end);
746 int step = start->step(end);
747 SkOpSegment* other = this->isSimple(nextStart, &step); // advances nextStart
748 if (other) {
749 // mark the smaller of startIndex, endIndex done, and all adjacent
750 // spans with the same T value (but not 'other' spans)
751#if DEBUG_WINDING
752 SkDebugf("%s simple\n", __FUNCTION__);
753#endif
754 SkOpSpan* startSpan = start->starter(end);
755 if (startSpan->done()) {
756 return nullptr;
757 }
758 markDone(startSpan);
759 *nextEnd = step > 0 ? (*nextStart)->upCast()->next() : (*nextStart)->prev();
760 return other;
761 }
762 SkDEBUGCODE(SkOpSpanBase* endNear = step > 0 ? (*nextStart)->upCast()->next() \
763 : (*nextStart)->prev());
764 SkASSERT(endNear == end); // is this ever not end?
765 SkASSERT(endNear);
766 SkASSERT(start != endNear);
767 SkASSERT((start->t() < endNear->t()) ^ (step < 0));
768 SkOpAngle* angle = this->spanToAngle(end, start);
769 if (!angle || angle->unorderable()) {
770 *unsortable = true;
771 markDone(start->starter(end));
772 return nullptr;
773 }
774#if DEBUG_SORT
775 SkDebugf("%s\n", __FUNCTION__);
776 angle->debugLoop();
777#endif
778 SkOpAngle* nextAngle = angle->next();
779 const SkOpAngle* foundAngle = nullptr;
780 bool foundDone = false;
781 // iterate through the angle, and compute everyone's winding
782 SkOpSegment* nextSegment;
783 int activeCount = 0;
784 do {
785 if (!nextAngle) {
786 return nullptr;
787 }
788 nextSegment = nextAngle->segment();
789 ++activeCount;
790 if (!foundAngle || (foundDone && activeCount & 1)) {
791 foundAngle = nextAngle;
792 if (!(foundDone = nextSegment->done(nextAngle))) {
793 break;
794 }
795 }
796 nextAngle = nextAngle->next();
797 } while (nextAngle != angle);
798 start->segment()->markDone(start->starter(end));
799 if (!foundAngle) {
800 return nullptr;
801 }
802 *nextStart = foundAngle->start();
803 *nextEnd = foundAngle->end();
804 nextSegment = foundAngle->segment();
805#if DEBUG_WINDING
806 SkDebugf("%s from:[%d] to:[%d] start=%d end=%d\n",
807 __FUNCTION__, debugID(), nextSegment->debugID(), *nextStart, *nextEnd);
808 #endif
809 return nextSegment;
810}
811
812SkOpGlobalState* SkOpSegment::globalState() const {
813 return contour()->globalState();
814}
815
816void SkOpSegment::init(SkPoint pts[], SkScalar weight, SkOpContour* contour, SkPath::Verb verb) {
817 fContour = contour;
818 fNext = nullptr;
819 fPts = pts;
820 fWeight = weight;
821 fVerb = verb;
822 fCount = 0;
823 fDoneCount = 0;
824 fVisited = false;
825 SkOpSpan* zeroSpan = &fHead;
826 zeroSpan->init(this, nullptr, 0, fPts[0]);
827 SkOpSpanBase* oneSpan = &fTail;
828 zeroSpan->setNext(oneSpan);
829 oneSpan->initBase(this, zeroSpan, 1, fPts[SkPathOpsVerbToPoints(fVerb)]);
830 SkDEBUGCODE(fID = globalState()->nextSegmentID());
831}
832
833bool SkOpSegment::isClose(double t, const SkOpSegment* opp) const {
834 SkDPoint cPt = this->dPtAtT(t);
835 SkDVector dxdy = (*CurveDSlopeAtT[this->verb()])(this->pts(), this->weight(), t);
836 SkDLine perp = {{ cPt, {cPt.fX + dxdy.fY, cPt.fY - dxdy.fX} }};
837 SkIntersections i;
838 (*CurveIntersectRay[opp->verb()])(opp->pts(), opp->weight(), perp, &i);
839 int used = i.used();
840 for (int index = 0; index < used; ++index) {
841 if (cPt.roughlyEqual(i.pt(index))) {
842 return true;
843 }
844 }
845 return false;
846}
847
848bool SkOpSegment::isXor() const {
849 return fContour->isXor();
850}
851
852void SkOpSegment::markAllDone() {
853 SkOpSpan* span = this->head();
854 do {
855 this->markDone(span);
856 } while ((span = span->next()->upCastable()));
857}
858
859 bool SkOpSegment::markAndChaseDone(SkOpSpanBase* start, SkOpSpanBase* end, SkOpSpanBase** found) {
860 int step = start->step(end);
861 SkOpSpan* minSpan = start->starter(end);
862 markDone(minSpan);
863 SkOpSpanBase* last = nullptr;
864 SkOpSegment* other = this;
865 SkOpSpan* priorDone = nullptr;
866 SkOpSpan* lastDone = nullptr;
867 int safetyNet = 100000;
868 while ((other = other->nextChase(&start, &step, &minSpan, &last))) {
869 if (!--safetyNet) {
870 return false;
871 }
872 if (other->done()) {
873 SkASSERT(!last);
874 break;
875 }
876 if (lastDone == minSpan || priorDone == minSpan) {
877 if (found) {
878 *found = nullptr;
879 }
880 return true;
881 }
882 other->markDone(minSpan);
883 priorDone = lastDone;
884 lastDone = minSpan;
885 }
886 if (found) {
887 *found = last;
888 }
889 return true;
890}
891
892bool SkOpSegment::markAndChaseWinding(SkOpSpanBase* start, SkOpSpanBase* end, int winding,
893 SkOpSpanBase** lastPtr) {
894 SkOpSpan* spanStart = start->starter(end);
895 int step = start->step(end);
896 bool success = markWinding(spanStart, winding);
897 SkOpSpanBase* last = nullptr;
898 SkOpSegment* other = this;
899 int safetyNet = 100000;
900 while ((other = other->nextChase(&start, &step, &spanStart, &last))) {
901 if (!--safetyNet) {
902 return false;
903 }
904 if (spanStart->windSum() != SK_MinS32) {
905// SkASSERT(spanStart->windSum() == winding); // FIXME: is this assert too aggressive?
906 SkASSERT(!last);
907 break;
908 }
909 (void) other->markWinding(spanStart, winding);
910 }
911 if (lastPtr) {
912 *lastPtr = last;
913 }
914 return success;
915}
916
917bool SkOpSegment::markAndChaseWinding(SkOpSpanBase* start, SkOpSpanBase* end,
918 int winding, int oppWinding, SkOpSpanBase** lastPtr) {
919 SkOpSpan* spanStart = start->starter(end);
920 int step = start->step(end);
921 bool success = markWinding(spanStart, winding, oppWinding);
922 SkOpSpanBase* last = nullptr;
923 SkOpSegment* other = this;
924 int safetyNet = 100000;
925 while ((other = other->nextChase(&start, &step, &spanStart, &last))) {
926 if (!--safetyNet) {
927 return false;
928 }
929 if (spanStart->windSum() != SK_MinS32) {
930 if (this->operand() == other->operand()) {
931 if (spanStart->windSum() != winding || spanStart->oppSum() != oppWinding) {
932 this->globalState()->setWindingFailed();
933 return true; // ... but let it succeed anyway
934 }
935 } else {
936 FAIL_IF(spanStart->windSum() != oppWinding);
937 FAIL_IF(spanStart->oppSum() != winding);
938 }
939 SkASSERT(!last);
940 break;
941 }
942 if (this->operand() == other->operand()) {
943 (void) other->markWinding(spanStart, winding, oppWinding);
944 } else {
945 (void) other->markWinding(spanStart, oppWinding, winding);
946 }
947 }
948 if (lastPtr) {
949 *lastPtr = last;
950 }
951 return success;
952}
953
954bool SkOpSegment::markAngle(int maxWinding, int sumWinding, const SkOpAngle* angle,
955 SkOpSpanBase** result) {
956 SkASSERT(angle->segment() == this);
957 if (UseInnerWinding(maxWinding, sumWinding)) {
958 maxWinding = sumWinding;
959 }
960 if (!markAndChaseWinding(angle->start(), angle->end(), maxWinding, result)) {
961 return false;
962 }
963#if DEBUG_WINDING
964 SkOpSpanBase* last = *result;
965 if (last) {
966 SkDebugf("%s last seg=%d span=%d", __FUNCTION__,
967 last->segment()->debugID(), last->debugID());
968 if (!last->final()) {
969 SkDebugf(" windSum=");
970 SkPathOpsDebug::WindingPrintf(last->upCast()->windSum());
971 }
972 SkDebugf("\n");
973 }
974#endif
975 return true;
976}
977
978bool SkOpSegment::markAngle(int maxWinding, int sumWinding, int oppMaxWinding,
979 int oppSumWinding, const SkOpAngle* angle, SkOpSpanBase** result) {
980 SkASSERT(angle->segment() == this);
981 if (UseInnerWinding(maxWinding, sumWinding)) {
982 maxWinding = sumWinding;
983 }
984 if (oppMaxWinding != oppSumWinding && UseInnerWinding(oppMaxWinding, oppSumWinding)) {
985 oppMaxWinding = oppSumWinding;
986 }
987 // caller doesn't require that this marks anything
988 if (!markAndChaseWinding(angle->start(), angle->end(), maxWinding, oppMaxWinding, result)) {
989 return false;
990 }
991#if DEBUG_WINDING
992 if (result) {
993 SkOpSpanBase* last = *result;
994 if (last) {
995 SkDebugf("%s last segment=%d span=%d", __FUNCTION__,
996 last->segment()->debugID(), last->debugID());
997 if (!last->final()) {
998 SkDebugf(" windSum=");
999 SkPathOpsDebug::WindingPrintf(last->upCast()->windSum());
1000 }
1001 SkDebugf(" \n");
1002 }
1003 }
1004#endif
1005 return true;
1006}
1007
1008void SkOpSegment::markDone(SkOpSpan* span) {
1009 SkASSERT(this == span->segment());
1010 if (span->done()) {
1011 return;
1012 }
1013#if DEBUG_MARK_DONE
1014 debugShowNewWinding(__FUNCTION__, span, span->windSum(), span->oppSum());
1015#endif
1016 span->setDone(true);
1017 ++fDoneCount;
1018 debugValidate();
1019}
1020
1021bool SkOpSegment::markWinding(SkOpSpan* span, int winding) {
1022 SkASSERT(this == span->segment());
1023 SkASSERT(winding);
1024 if (span->done()) {
1025 return false;
1026 }
1027#if DEBUG_MARK_DONE
1028 debugShowNewWinding(__FUNCTION__, span, winding);
1029#endif
1030 span->setWindSum(winding);
1031 debugValidate();
1032 return true;
1033}
1034
1035bool SkOpSegment::markWinding(SkOpSpan* span, int winding, int oppWinding) {
1036 SkASSERT(this == span->segment());
1037 SkASSERT(winding || oppWinding);
1038 if (span->done()) {
1039 return false;
1040 }
1041#if DEBUG_MARK_DONE
1042 debugShowNewWinding(__FUNCTION__, span, winding, oppWinding);
1043#endif
1044 span->setWindSum(winding);
1045 span->setOppSum(oppWinding);
1046 debugValidate();
1047 return true;
1048}
1049
1050bool SkOpSegment::match(const SkOpPtT* base, const SkOpSegment* testParent, double testT,
1051 const SkPoint& testPt) const {
1052 SkASSERT(this == base->segment());
1053 if (this == testParent) {
1054 if (precisely_equal(base->fT, testT)) {
1055 return true;
1056 }
1057 }
1058 if (!SkDPoint::ApproximatelyEqual(testPt, base->fPt)) {
1059 return false;
1060 }
1061 return this != testParent || !this->ptsDisjoint(base->fT, base->fPt, testT, testPt);
1062}
1063
1064static SkOpSegment* set_last(SkOpSpanBase** last, SkOpSpanBase* endSpan) {
1065 if (last) {
1066 *last = endSpan;
1067 }
1068 return nullptr;
1069}
1070
1071SkOpSegment* SkOpSegment::nextChase(SkOpSpanBase** startPtr, int* stepPtr, SkOpSpan** minPtr,
1072 SkOpSpanBase** last) const {
1073 SkOpSpanBase* origStart = *startPtr;
1074 int step = *stepPtr;
1075 SkOpSpanBase* endSpan = step > 0 ? origStart->upCast()->next() : origStart->prev();
1076 SkASSERT(endSpan);
1077 SkOpAngle* angle = step > 0 ? endSpan->fromAngle() : endSpan->upCast()->toAngle();
1078 SkOpSpanBase* foundSpan;
1079 SkOpSpanBase* otherEnd;
1080 SkOpSegment* other;
1081 if (angle == nullptr) {
1082 if (endSpan->t() != 0 && endSpan->t() != 1) {
1083 return nullptr;
1084 }
1085 SkOpPtT* otherPtT = endSpan->ptT()->next();
1086 other = otherPtT->segment();
1087 foundSpan = otherPtT->span();
1088 otherEnd = step > 0
1089 ? foundSpan->upCastable() ? foundSpan->upCast()->next() : nullptr
1090 : foundSpan->prev();
1091 } else {
1092 int loopCount = angle->loopCount();
1093 if (loopCount > 2) {
1094 return set_last(last, endSpan);
1095 }
1096 const SkOpAngle* next = angle->next();
1097 if (nullptr == next) {
1098 return nullptr;
1099 }
1100#if DEBUG_WINDING
1101 if (angle->debugSign() != next->debugSign() && !angle->segment()->contour()->isXor()
1102 && !next->segment()->contour()->isXor()) {
1103 SkDebugf("%s mismatched signs\n", __FUNCTION__);
1104 }
1105#endif
1106 other = next->segment();
1107 foundSpan = endSpan = next->start();
1108 otherEnd = next->end();
1109 }
1110 if (!otherEnd) {
1111 return nullptr;
1112 }
1113 int foundStep = foundSpan->step(otherEnd);
1114 if (*stepPtr != foundStep) {
1115 return set_last(last, endSpan);
1116 }
1117 SkASSERT(*startPtr);
1118// SkASSERT(otherEnd >= 0);
1119 SkOpSpan* origMin = step < 0 ? origStart->prev() : origStart->upCast();
1120 SkOpSpan* foundMin = foundSpan->starter(otherEnd);
1121 if (foundMin->windValue() != origMin->windValue()
1122 || foundMin->oppValue() != origMin->oppValue()) {
1123 return set_last(last, endSpan);
1124 }
1125 *startPtr = foundSpan;
1126 *stepPtr = foundStep;
1127 if (minPtr) {
1128 *minPtr = foundMin;
1129 }
1130 return other;
1131}
1132
1133// Please keep this in sync with DebugClearVisited()
1134void SkOpSegment::ClearVisited(SkOpSpanBase* span) {
1135 // reset visited flag back to false
1136 do {
1137 SkOpPtT* ptT = span->ptT(), * stopPtT = ptT;
1138 while ((ptT = ptT->next()) != stopPtT) {
1139 SkOpSegment* opp = ptT->segment();
1140 opp->resetVisited();
1141 }
1142 } while (!span->final() && (span = span->upCast()->next()));
1143}
1144
1145// Please keep this in sync with debugMissingCoincidence()
1146// look for pairs of undetected coincident curves
1147// assumes that segments going in have visited flag clear
1148// Even though pairs of curves correct detect coincident runs, a run may be missed
1149// if the coincidence is a product of multiple intersections. For instance, given
1150// curves A, B, and C:
1151// A-B intersect at a point 1; A-C and B-C intersect at point 2, so near
1152// the end of C that the intersection is replaced with the end of C.
1153// Even though A-B correctly do not detect an intersection at point 2,
1154// the resulting run from point 1 to point 2 is coincident on A and B.
1155bool SkOpSegment::missingCoincidence() {
1156 if (this->done()) {
1157 return false;
1158 }
1159 SkOpSpan* prior = nullptr;
1160 SkOpSpanBase* spanBase = &fHead;
1161 bool result = false;
1162 int safetyNet = 100000;
1163 do {
1164 SkOpPtT* ptT = spanBase->ptT(), * spanStopPtT = ptT;
1165 SkOPASSERT(ptT->span() == spanBase);
1166 while ((ptT = ptT->next()) != spanStopPtT) {
1167 if (!--safetyNet) {
1168 return false;
1169 }
1170 if (ptT->deleted()) {
1171 continue;
1172 }
1173 SkOpSegment* opp = ptT->span()->segment();
1174 if (opp->done()) {
1175 continue;
1176 }
1177 // when opp is encounted the 1st time, continue; on 2nd encounter, look for coincidence
1178 if (!opp->visited()) {
1179 continue;
1180 }
1181 if (spanBase == &fHead) {
1182 continue;
1183 }
1184 if (ptT->segment() == this) {
1185 continue;
1186 }
1187 SkOpSpan* span = spanBase->upCastable();
1188 // FIXME?: this assumes that if the opposite segment is coincident then no more
1189 // coincidence needs to be detected. This may not be true.
1190 if (span && span->containsCoincidence(opp)) {
1191 continue;
1192 }
1193 if (spanBase->containsCoinEnd(opp)) {
1194 continue;
1195 }
1196 SkOpPtT* priorPtT = nullptr, * priorStopPtT;
1197 // find prior span containing opp segment
1198 SkOpSegment* priorOpp = nullptr;
1199 SkOpSpan* priorTest = spanBase->prev();
1200 while (!priorOpp && priorTest) {
1201 priorStopPtT = priorPtT = priorTest->ptT();
1202 while ((priorPtT = priorPtT->next()) != priorStopPtT) {
1203 if (priorPtT->deleted()) {
1204 continue;
1205 }
1206 SkOpSegment* segment = priorPtT->span()->segment();
1207 if (segment == opp) {
1208 prior = priorTest;
1209 priorOpp = opp;
1210 break;
1211 }
1212 }
1213 priorTest = priorTest->prev();
1214 }
1215 if (!priorOpp) {
1216 continue;
1217 }
1218 if (priorPtT == ptT) {
1219 continue;
1220 }
1221 SkOpPtT* oppStart = prior->ptT();
1222 SkOpPtT* oppEnd = spanBase->ptT();
1223 bool swapped = priorPtT->fT > ptT->fT;
1224 if (swapped) {
1225 using std::swap;
1226 swap(priorPtT, ptT);
1227 swap(oppStart, oppEnd);
1228 }
1229 SkOpCoincidence* coincidences = this->globalState()->coincidence();
1230 SkOpPtT* rootPriorPtT = priorPtT->span()->ptT();
1231 SkOpPtT* rootPtT = ptT->span()->ptT();
1232 SkOpPtT* rootOppStart = oppStart->span()->ptT();
1233 SkOpPtT* rootOppEnd = oppEnd->span()->ptT();
1234 if (coincidences->contains(rootPriorPtT, rootPtT, rootOppStart, rootOppEnd)) {
1235 goto swapBack;
1236 }
1237 if (this->testForCoincidence(rootPriorPtT, rootPtT, prior, spanBase, opp)) {
1238 // mark coincidence
1239#if DEBUG_COINCIDENCE_VERBOSE
1240 SkDebugf("%s coinSpan=%d endSpan=%d oppSpan=%d oppEndSpan=%d\n", __FUNCTION__,
1241 rootPriorPtT->debugID(), rootPtT->debugID(), rootOppStart->debugID(),
1242 rootOppEnd->debugID());
1243#endif
1244 if (!coincidences->extend(rootPriorPtT, rootPtT, rootOppStart, rootOppEnd)) {
1245 coincidences->add(rootPriorPtT, rootPtT, rootOppStart, rootOppEnd);
1246 }
1247#if DEBUG_COINCIDENCE
1248 SkASSERT(coincidences->contains(rootPriorPtT, rootPtT, rootOppStart, rootOppEnd));
1249#endif
1250 result = true;
1251 }
1252 swapBack:
1253 if (swapped) {
1254 using std::swap;
1255 swap(priorPtT, ptT);
1256 }
1257 }
1258 } while ((spanBase = spanBase->final() ? nullptr : spanBase->upCast()->next()));
1259 ClearVisited(&fHead);
1260 return result;
1261}
1262
1263// please keep this in sync with debugMoveMultiples()
1264// if a span has more than one intersection, merge the other segments' span as needed
1265bool SkOpSegment::moveMultiples() {
1266 debugValidate();
1267 SkOpSpanBase* test = &fHead;
1268 do {
1269 int addCount = test->spanAddsCount();
1270// FAIL_IF(addCount < 1);
1271 if (addCount <= 1) {
1272 continue;
1273 }
1274 SkOpPtT* startPtT = test->ptT();
1275 SkOpPtT* testPtT = startPtT;
1276 int safetyHatch = 1000000;
1277 do { // iterate through all spans associated with start
1278 if (!--safetyHatch) {
1279 return false;
1280 }
1281 SkOpSpanBase* oppSpan = testPtT->span();
1282 if (oppSpan->spanAddsCount() == addCount) {
1283 continue;
1284 }
1285 if (oppSpan->deleted()) {
1286 continue;
1287 }
1288 SkOpSegment* oppSegment = oppSpan->segment();
1289 if (oppSegment == this) {
1290 continue;
1291 }
1292 // find range of spans to consider merging
1293 SkOpSpanBase* oppPrev = oppSpan;
1294 SkOpSpanBase* oppFirst = oppSpan;
1295 while ((oppPrev = oppPrev->prev())) {
1296 if (!roughly_equal(oppPrev->t(), oppSpan->t())) {
1297 break;
1298 }
1299 if (oppPrev->spanAddsCount() == addCount) {
1300 continue;
1301 }
1302 if (oppPrev->deleted()) {
1303 continue;
1304 }
1305 oppFirst = oppPrev;
1306 }
1307 SkOpSpanBase* oppNext = oppSpan;
1308 SkOpSpanBase* oppLast = oppSpan;
1309 while ((oppNext = oppNext->final() ? nullptr : oppNext->upCast()->next())) {
1310 if (!roughly_equal(oppNext->t(), oppSpan->t())) {
1311 break;
1312 }
1313 if (oppNext->spanAddsCount() == addCount) {
1314 continue;
1315 }
1316 if (oppNext->deleted()) {
1317 continue;
1318 }
1319 oppLast = oppNext;
1320 }
1321 if (oppFirst == oppLast) {
1322 continue;
1323 }
1324 SkOpSpanBase* oppTest = oppFirst;
1325 do {
1326 if (oppTest == oppSpan) {
1327 continue;
1328 }
1329 // check to see if the candidate meets specific criteria:
1330 // it contains spans of segments in test's loop but not including 'this'
1331 SkOpPtT* oppStartPtT = oppTest->ptT();
1332 SkOpPtT* oppPtT = oppStartPtT;
1333 while ((oppPtT = oppPtT->next()) != oppStartPtT) {
1334 SkOpSegment* oppPtTSegment = oppPtT->segment();
1335 if (oppPtTSegment == this) {
1336 goto tryNextSpan;
1337 }
1338 SkOpPtT* matchPtT = startPtT;
1339 do {
1340 if (matchPtT->segment() == oppPtTSegment) {
1341 goto foundMatch;
1342 }
1343 } while ((matchPtT = matchPtT->next()) != startPtT);
1344 goto tryNextSpan;
1345 foundMatch: // merge oppTest and oppSpan
1346 oppSegment->debugValidate();
1347 oppTest->mergeMatches(oppSpan);
1348 oppTest->addOpp(oppSpan);
1349 oppSegment->debugValidate();
1350 goto checkNextSpan;
1351 }
1352 tryNextSpan:
1353 ;
1354 } while (oppTest != oppLast && (oppTest = oppTest->upCast()->next()));
1355 } while ((testPtT = testPtT->next()) != startPtT);
1356checkNextSpan:
1357 ;
1358 } while ((test = test->final() ? nullptr : test->upCast()->next()));
1359 debugValidate();
1360 return true;
1361}
1362
1363// adjacent spans may have points close by
1364bool SkOpSegment::spansNearby(const SkOpSpanBase* refSpan, const SkOpSpanBase* checkSpan,
1365 bool* found) const {
1366 const SkOpPtT* refHead = refSpan->ptT();
1367 const SkOpPtT* checkHead = checkSpan->ptT();
1368// if the first pt pair from adjacent spans are far apart, assume that all are far enough apart
1369 if (!SkDPoint::WayRoughlyEqual(refHead->fPt, checkHead->fPt)) {
1370#if DEBUG_COINCIDENCE
1371 // verify that no combination of points are close
1372 const SkOpPtT* dBugRef = refHead;
1373 do {
1374 const SkOpPtT* dBugCheck = checkHead;
1375 do {
1376 SkOPASSERT(!SkDPoint::ApproximatelyEqual(dBugRef->fPt, dBugCheck->fPt));
1377 dBugCheck = dBugCheck->next();
1378 } while (dBugCheck != checkHead);
1379 dBugRef = dBugRef->next();
1380 } while (dBugRef != refHead);
1381#endif
1382 *found = false;
1383 return true;
1384 }
1385 // check only unique points
1386 SkScalar distSqBest = SK_ScalarMax;
1387 const SkOpPtT* refBest = nullptr;
1388 const SkOpPtT* checkBest = nullptr;
1389 const SkOpPtT* ref = refHead;
1390 do {
1391 if (ref->deleted()) {
1392 continue;
1393 }
1394 while (ref->ptAlreadySeen(refHead)) {
1395 ref = ref->next();
1396 if (ref == refHead) {
1397 goto doneCheckingDistance;
1398 }
1399 }
1400 const SkOpPtT* check = checkHead;
1401 const SkOpSegment* refSeg = ref->segment();
1402 int escapeHatch = 100000; // defend against infinite loops
1403 do {
1404 if (check->deleted()) {
1405 continue;
1406 }
1407 while (check->ptAlreadySeen(checkHead)) {
1408 check = check->next();
1409 if (check == checkHead) {
1410 goto nextRef;
1411 }
1412 }
1413 SkScalar distSq = SkPointPriv::DistanceToSqd(ref->fPt, check->fPt);
1414 if (distSqBest > distSq && (refSeg != check->segment()
1415 || !refSeg->ptsDisjoint(*ref, *check))) {
1416 distSqBest = distSq;
1417 refBest = ref;
1418 checkBest = check;
1419 }
1420 if (--escapeHatch <= 0) {
1421 return false;
1422 }
1423 } while ((check = check->next()) != checkHead);
1424 nextRef:
1425 ;
1426 } while ((ref = ref->next()) != refHead);
1427doneCheckingDistance:
1428 *found = checkBest && refBest->segment()->match(refBest, checkBest->segment(), checkBest->fT,
1429 checkBest->fPt);
1430 return true;
1431}
1432
1433// Please keep this function in sync with debugMoveNearby()
1434// Move nearby t values and pts so they all hang off the same span. Alignment happens later.
1435bool SkOpSegment::moveNearby() {
1436 debugValidate();
1437 // release undeleted spans pointing to this seg that are linked to the primary span
1438 SkOpSpanBase* spanBase = &fHead;
1439 int escapeHatch = 9999; // the largest count for a regular test is 50; for a fuzzer, 500
1440 do {
1441 SkOpPtT* ptT = spanBase->ptT();
1442 const SkOpPtT* headPtT = ptT;
1443 while ((ptT = ptT->next()) != headPtT) {
1444 if (!--escapeHatch) {
1445 return false;
1446 }
1447 SkOpSpanBase* test = ptT->span();
1448 if (ptT->segment() == this && !ptT->deleted() && test != spanBase
1449 && test->ptT() == ptT) {
1450 if (test->final()) {
1451 if (spanBase == &fHead) {
1452 this->clearAll();
1453 return true;
1454 }
1455 spanBase->upCast()->release(ptT);
1456 } else if (test->prev()) {
1457 test->upCast()->release(headPtT);
1458 }
1459 break;
1460 }
1461 }
1462 spanBase = spanBase->upCast()->next();
1463 } while (!spanBase->final());
1464 // This loop looks for adjacent spans which are near by
1465 spanBase = &fHead;
1466 do { // iterate through all spans associated with start
1467 SkOpSpanBase* test = spanBase->upCast()->next();
1468 bool found;
1469 if (!this->spansNearby(spanBase, test, &found)) {
1470 return false;
1471 }
1472 if (found) {
1473 if (test->final()) {
1474 if (spanBase->prev()) {
1475 test->merge(spanBase->upCast());
1476 } else {
1477 this->clearAll();
1478 return true;
1479 }
1480 } else {
1481 spanBase->merge(test->upCast());
1482 }
1483 }
1484 spanBase = test;
1485 } while (!spanBase->final());
1486 debugValidate();
1487 return true;
1488}
1489
1490bool SkOpSegment::operand() const {
1491 return fContour->operand();
1492}
1493
1494bool SkOpSegment::oppXor() const {
1495 return fContour->oppXor();
1496}
1497
1498bool SkOpSegment::ptsDisjoint(double t1, const SkPoint& pt1, double t2, const SkPoint& pt2) const {
1499 if (fVerb == SkPath::kLine_Verb) {
1500 return false;
1501 }
1502 // quads (and cubics) can loop back to nearly a line so that an opposite curve
1503 // hits in two places with very different t values.
1504 // OPTIMIZATION: curves could be preflighted so that, for example, something like
1505 // 'controls contained by ends' could avoid this check for common curves
1506 // 'ends are extremes in x or y' is cheaper to compute and real-world common
1507 // on the other hand, the below check is relatively inexpensive
1508 double midT = (t1 + t2) / 2;
1509 SkPoint midPt = this->ptAtT(midT);
1510 double seDistSq = std::max(SkPointPriv::DistanceToSqd(pt1, pt2) * 2, FLT_EPSILON * 2);
1511 return SkPointPriv::DistanceToSqd(midPt, pt1) > seDistSq ||
1512 SkPointPriv::DistanceToSqd(midPt, pt2) > seDistSq;
1513}
1514
1515void SkOpSegment::setUpWindings(SkOpSpanBase* start, SkOpSpanBase* end, int* sumMiWinding,
1516 int* maxWinding, int* sumWinding) {
1517 int deltaSum = SpanSign(start, end);
1518 *maxWinding = *sumMiWinding;
1519 *sumWinding = *sumMiWinding -= deltaSum;
1520 SkASSERT(!DEBUG_LIMIT_WIND_SUM || SkTAbs(*sumWinding) <= DEBUG_LIMIT_WIND_SUM);
1521}
1522
1523void SkOpSegment::setUpWindings(SkOpSpanBase* start, SkOpSpanBase* end, int* sumMiWinding,
1524 int* sumSuWinding, int* maxWinding, int* sumWinding, int* oppMaxWinding,
1525 int* oppSumWinding) {
1526 int deltaSum = SpanSign(start, end);
1527 int oppDeltaSum = OppSign(start, end);
1528 if (operand()) {
1529 *maxWinding = *sumSuWinding;
1530 *sumWinding = *sumSuWinding -= deltaSum;
1531 *oppMaxWinding = *sumMiWinding;
1532 *oppSumWinding = *sumMiWinding -= oppDeltaSum;
1533 } else {
1534 *maxWinding = *sumMiWinding;
1535 *sumWinding = *sumMiWinding -= deltaSum;
1536 *oppMaxWinding = *sumSuWinding;
1537 *oppSumWinding = *sumSuWinding -= oppDeltaSum;
1538 }
1539 SkASSERT(!DEBUG_LIMIT_WIND_SUM || SkTAbs(*sumWinding) <= DEBUG_LIMIT_WIND_SUM);
1540 SkASSERT(!DEBUG_LIMIT_WIND_SUM || SkTAbs(*oppSumWinding) <= DEBUG_LIMIT_WIND_SUM);
1541}
1542
1543bool SkOpSegment::sortAngles() {
1544 SkOpSpanBase* span = &this->fHead;
1545 do {
1546 SkOpAngle* fromAngle = span->fromAngle();
1547 SkOpAngle* toAngle = span->final() ? nullptr : span->upCast()->toAngle();
1548 if (!fromAngle && !toAngle) {
1549 continue;
1550 }
1551#if DEBUG_ANGLE
1552 bool wroteAfterHeader = false;
1553#endif
1554 SkOpAngle* baseAngle = fromAngle;
1555 if (fromAngle && toAngle) {
1556#if DEBUG_ANGLE
1557 SkDebugf("%s [%d] tStart=%1.9g [%d]\n", __FUNCTION__, debugID(), span->t(),
1558 span->debugID());
1559 wroteAfterHeader = true;
1560#endif
1561 FAIL_IF(!fromAngle->insert(toAngle));
1562 } else if (!fromAngle) {
1563 baseAngle = toAngle;
1564 }
1565 SkOpPtT* ptT = span->ptT(), * stopPtT = ptT;
1566 int safetyNet = 1000000;
1567 do {
1568 if (!--safetyNet) {
1569 return false;
1570 }
1571 SkOpSpanBase* oSpan = ptT->span();
1572 if (oSpan == span) {
1573 continue;
1574 }
1575 SkOpAngle* oAngle = oSpan->fromAngle();
1576 if (oAngle) {
1577#if DEBUG_ANGLE
1578 if (!wroteAfterHeader) {
1579 SkDebugf("%s [%d] tStart=%1.9g [%d]\n", __FUNCTION__, debugID(),
1580 span->t(), span->debugID());
1581 wroteAfterHeader = true;
1582 }
1583#endif
1584 if (!oAngle->loopContains(baseAngle)) {
1585 baseAngle->insert(oAngle);
1586 }
1587 }
1588 if (!oSpan->final()) {
1589 oAngle = oSpan->upCast()->toAngle();
1590 if (oAngle) {
1591#if DEBUG_ANGLE
1592 if (!wroteAfterHeader) {
1593 SkDebugf("%s [%d] tStart=%1.9g [%d]\n", __FUNCTION__, debugID(),
1594 span->t(), span->debugID());
1595 wroteAfterHeader = true;
1596 }
1597#endif
1598 if (!oAngle->loopContains(baseAngle)) {
1599 baseAngle->insert(oAngle);
1600 }
1601 }
1602 }
1603 } while ((ptT = ptT->next()) != stopPtT);
1604 if (baseAngle->loopCount() == 1) {
1605 span->setFromAngle(nullptr);
1606 if (toAngle) {
1607 span->upCast()->setToAngle(nullptr);
1608 }
1609 baseAngle = nullptr;
1610 }
1611#if DEBUG_SORT
1612 SkASSERT(!baseAngle || baseAngle->loopCount() > 1);
1613#endif
1614 } while (!span->final() && (span = span->upCast()->next()));
1615 return true;
1616}
1617
1618bool SkOpSegment::subDivide(const SkOpSpanBase* start, const SkOpSpanBase* end,
1619 SkDCurve* edge) const {
1620 SkASSERT(start != end);
1621 const SkOpPtT& startPtT = *start->ptT();
1622 const SkOpPtT& endPtT = *end->ptT();
1623 SkDEBUGCODE(edge->fVerb = fVerb);
1624 edge->fCubic[0].set(startPtT.fPt);
1625 int points = SkPathOpsVerbToPoints(fVerb);
1626 edge->fCubic[points].set(endPtT.fPt);
1627 if (fVerb == SkPath::kLine_Verb) {
1628 return false;
1629 }
1630 double startT = startPtT.fT;
1631 double endT = endPtT.fT;
1632 if ((startT == 0 || endT == 0) && (startT == 1 || endT == 1)) {
1633 // don't compute midpoints if we already have them
1634 if (fVerb == SkPath::kQuad_Verb) {
1635 edge->fLine[1].set(fPts[1]);
1636 return false;
1637 }
1638 if (fVerb == SkPath::kConic_Verb) {
1639 edge->fConic[1].set(fPts[1]);
1640 edge->fConic.fWeight = fWeight;
1641 return false;
1642 }
1643 SkASSERT(fVerb == SkPath::kCubic_Verb);
1644 if (startT == 0) {
1645 edge->fCubic[1].set(fPts[1]);
1646 edge->fCubic[2].set(fPts[2]);
1647 return false;
1648 }
1649 edge->fCubic[1].set(fPts[2]);
1650 edge->fCubic[2].set(fPts[1]);
1651 return false;
1652 }
1653 if (fVerb == SkPath::kQuad_Verb) {
1654 edge->fQuad[1] = SkDQuad::SubDivide(fPts, edge->fQuad[0], edge->fQuad[2], startT, endT);
1655 } else if (fVerb == SkPath::kConic_Verb) {
1656 edge->fConic[1] = SkDConic::SubDivide(fPts, fWeight, edge->fQuad[0], edge->fQuad[2],
1657 startT, endT, &edge->fConic.fWeight);
1658 } else {
1659 SkASSERT(fVerb == SkPath::kCubic_Verb);
1660 SkDCubic::SubDivide(fPts, edge->fCubic[0], edge->fCubic[3], startT, endT, &edge->fCubic[1]);
1661 }
1662 return true;
1663}
1664
1665bool SkOpSegment::testForCoincidence(const SkOpPtT* priorPtT, const SkOpPtT* ptT,
1666 const SkOpSpanBase* prior, const SkOpSpanBase* spanBase, const SkOpSegment* opp) const {
1667 // average t, find mid pt
1668 double midT = (prior->t() + spanBase->t()) / 2;
1669 SkPoint midPt = this->ptAtT(midT);
1670 bool coincident = true;
1671 // if the mid pt is not near either end pt, project perpendicular through opp seg
1672 if (!SkDPoint::ApproximatelyEqual(priorPtT->fPt, midPt)
1673 && !SkDPoint::ApproximatelyEqual(ptT->fPt, midPt)) {
1674 if (priorPtT->span() == ptT->span()) {
1675 return false;
1676 }
1677 coincident = false;
1678 SkIntersections i;
1679 SkDCurve curvePart;
1680 this->subDivide(prior, spanBase, &curvePart);
1681 SkDVector dxdy = (*CurveDDSlopeAtT[fVerb])(curvePart, 0.5f);
1682 SkDPoint partMidPt = (*CurveDDPointAtT[fVerb])(curvePart, 0.5f);
1683 SkDLine ray = {{{midPt.fX, midPt.fY}, {partMidPt.fX + dxdy.fY, partMidPt.fY - dxdy.fX}}};
1684 SkDCurve oppPart;
1685 opp->subDivide(priorPtT->span(), ptT->span(), &oppPart);
1686 (*CurveDIntersectRay[opp->verb()])(oppPart, ray, &i);
1687 // measure distance and see if it's small enough to denote coincidence
1688 for (int index = 0; index < i.used(); ++index) {
1689 if (!between(0, i[0][index], 1)) {
1690 continue;
1691 }
1692 SkDPoint oppPt = i.pt(index);
1693 if (oppPt.approximatelyDEqual(midPt)) {
1694 // the coincidence can occur at almost any angle
1695 coincident = true;
1696 }
1697 }
1698 }
1699 return coincident;
1700}
1701
1702SkOpSpan* SkOpSegment::undoneSpan() {
1703 SkOpSpan* span = &fHead;
1704 SkOpSpanBase* next;
1705 do {
1706 next = span->next();
1707 if (!span->done()) {
1708 return span;
1709 }
1710 } while (!next->final() && (span = next->upCast()));
1711 return nullptr;
1712}
1713
1714int SkOpSegment::updateOppWinding(const SkOpSpanBase* start, const SkOpSpanBase* end) const {
1715 const SkOpSpan* lesser = start->starter(end);
1716 int oppWinding = lesser->oppSum();
1717 int oppSpanWinding = SkOpSegment::OppSign(start, end);
1718 if (oppSpanWinding && UseInnerWinding(oppWinding - oppSpanWinding, oppWinding)
1719 && oppWinding != SK_MaxS32) {
1720 oppWinding -= oppSpanWinding;
1721 }
1722 return oppWinding;
1723}
1724
1725int SkOpSegment::updateOppWinding(const SkOpAngle* angle) const {
1726 const SkOpSpanBase* startSpan = angle->start();
1727 const SkOpSpanBase* endSpan = angle->end();
1728 return updateOppWinding(endSpan, startSpan);
1729}
1730
1731int SkOpSegment::updateOppWindingReverse(const SkOpAngle* angle) const {
1732 const SkOpSpanBase* startSpan = angle->start();
1733 const SkOpSpanBase* endSpan = angle->end();
1734 return updateOppWinding(startSpan, endSpan);
1735}
1736
1737int SkOpSegment::updateWinding(SkOpSpanBase* start, SkOpSpanBase* end) {
1738 SkOpSpan* lesser = start->starter(end);
1739 int winding = lesser->windSum();
1740 if (winding == SK_MinS32) {
1741 winding = lesser->computeWindSum();
1742 }
1743 if (winding == SK_MinS32) {
1744 return winding;
1745 }
1746 int spanWinding = SkOpSegment::SpanSign(start, end);
1747 if (winding && UseInnerWinding(winding - spanWinding, winding)
1748 && winding != SK_MaxS32) {
1749 winding -= spanWinding;
1750 }
1751 return winding;
1752}
1753
1754int SkOpSegment::updateWinding(SkOpAngle* angle) {
1755 SkOpSpanBase* startSpan = angle->start();
1756 SkOpSpanBase* endSpan = angle->end();
1757 return updateWinding(endSpan, startSpan);
1758}
1759
1760int SkOpSegment::updateWindingReverse(const SkOpAngle* angle) {
1761 SkOpSpanBase* startSpan = angle->start();
1762 SkOpSpanBase* endSpan = angle->end();
1763 return updateWinding(startSpan, endSpan);
1764}
1765
1766// OPTIMIZATION: does the following also work, and is it any faster?
1767// return outerWinding * innerWinding > 0
1768// || ((outerWinding + innerWinding < 0) ^ ((outerWinding - innerWinding) < 0)))
1769bool SkOpSegment::UseInnerWinding(int outerWinding, int innerWinding) {
1770 SkASSERT(outerWinding != SK_MaxS32);
1771 SkASSERT(innerWinding != SK_MaxS32);
1772 int absOut = SkTAbs(outerWinding);
1773 int absIn = SkTAbs(innerWinding);
1774 bool result = absOut == absIn ? outerWinding < 0 : absOut < absIn;
1775 return result;
1776}
1777
1778int SkOpSegment::windSum(const SkOpAngle* angle) const {
1779 const SkOpSpan* minSpan = angle->start()->starter(angle->end());
1780 return minSpan->windSum();
1781}
1782