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