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