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