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