xref: /aosp_15_r20/external/skia/src/pathops/SkPathOpsTSect.cpp (revision c8dee2aa9b3f27cf6c858bd81872bdeb2c07ed17) 
1 /*
2  * Copyright 2014 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 
8 #include "src/pathops/SkPathOpsTSect.h"
9 
10 #include "include/private/base/SkFloatingPoint.h"
11 #include "include/private/base/SkMacros.h"
12 #include "include/private/base/SkTArray.h"
13 #include "src/base/SkTSort.h"
14 #include "src/pathops/SkIntersections.h"
15 #include "src/pathops/SkPathOpsConic.h"
16 #include "src/pathops/SkPathOpsCubic.h"
17 #include "src/pathops/SkPathOpsLine.h"
18 #include "src/pathops/SkPathOpsQuad.h"
19 
20 #include <cfloat>
21 #include <algorithm>
22 #include <array>
23 #include <cmath>
24 
25 using namespace skia_private;
26 
27 #define COINCIDENT_SPAN_COUNT 9
28 
setPerp(const SkTCurve & c1,double t,const SkDPoint & cPt,const SkTCurve & c2)29 void SkTCoincident::setPerp(const SkTCurve& c1, double t,
30         const SkDPoint& cPt, const SkTCurve& c2) {
31     SkDVector dxdy = c1.dxdyAtT(t);
32     SkDLine perp = {{ cPt, {cPt.fX + dxdy.fY, cPt.fY - dxdy.fX} }};
33     SkIntersections i  SkDEBUGCODE((c1.globalState()));
34     int used = i.intersectRay(c2, perp);
35     // only keep closest
36     if (used == 0 || used == 3) {
37         this->init();
38         return;
39     }
40     fPerpT = i[0][0];
41     fPerpPt = i.pt(0);
42     SkASSERT(used <= 2);
43     if (used == 2) {
44         double distSq = (fPerpPt - cPt).lengthSquared();
45         double dist2Sq = (i.pt(1) - cPt).lengthSquared();
46         if (dist2Sq < distSq) {
47             fPerpT = i[0][1];
48             fPerpPt = i.pt(1);
49         }
50     }
51 #if DEBUG_T_SECT
52     SkDebugf("setPerp t=%1.9g cPt=(%1.9g,%1.9g) %s oppT=%1.9g fPerpPt=(%1.9g,%1.9g)\n",
53             t, cPt.fX, cPt.fY,
54             cPt.approximatelyEqual(fPerpPt) ? "==" : "!=", fPerpT, fPerpPt.fX, fPerpPt.fY);
55 #endif
56     fMatch = cPt.approximatelyEqual(fPerpPt);
57 #if DEBUG_T_SECT
58     if (fMatch) {
59         SkDebugf("%s", "");  // allow setting breakpoint
60     }
61 #endif
62 }
63 
addBounded(SkTSpan * span,SkArenaAlloc * heap)64 void SkTSpan::addBounded(SkTSpan* span, SkArenaAlloc* heap) {
65     SkTSpanBounded* bounded = heap->make<SkTSpanBounded>();
66     bounded->fBounded = span;
67     bounded->fNext = fBounded;
68     fBounded = bounded;
69 }
70 
addFollowing(SkTSpan * prior)71 SkTSpan* SkTSect::addFollowing(
72         SkTSpan* prior) {
73     SkTSpan* result = this->addOne();
74     SkDEBUGCODE(result->debugSetGlobalState(this->globalState()));
75     result->fStartT = prior ? prior->fEndT : 0;
76     SkTSpan* next = prior ? prior->fNext : fHead;
77     result->fEndT = next ? next->fStartT : 1;
78     result->fPrev = prior;
79     result->fNext = next;
80     if (prior) {
81         prior->fNext = result;
82     } else {
83         fHead = result;
84     }
85     if (next) {
86         next->fPrev = result;
87     }
88     result->resetBounds(fCurve);
89     // world may not be consistent to call validate here
90     result->validate();
91     return result;
92 }
93 
addForPerp(SkTSpan * span,double t)94 void SkTSect::addForPerp(SkTSpan* span, double t) {
95     if (!span->hasOppT(t)) {
96         SkTSpan* priorSpan;
97         SkTSpan* opp = this->spanAtT(t, &priorSpan);
98         if (!opp) {
99             opp = this->addFollowing(priorSpan);
100 #if DEBUG_PERP
101             SkDebugf("%s priorSpan=%d t=%1.9g opp=%d\n", __FUNCTION__, priorSpan ?
102                     priorSpan->debugID() : -1, t, opp->debugID());
103 #endif
104         }
105 #if DEBUG_PERP
106         opp->dump(); SkDebugf("\n");
107         SkDebugf("%s addBounded span=%d opp=%d\n", __FUNCTION__, priorSpan ?
108                 priorSpan->debugID() : -1, opp->debugID());
109 #endif
110         opp->addBounded(span, &fHeap);
111         span->addBounded(opp, &fHeap);
112     }
113     this->validate();
114 #if DEBUG_T_SECT
115     span->validatePerpT(t);
116 #endif
117 }
118 
closestBoundedT(const SkDPoint & pt) const119 double SkTSpan::closestBoundedT(const SkDPoint& pt) const {
120     double result = -1;
121     double closest = DBL_MAX;
122     const SkTSpanBounded* testBounded = fBounded;
123     while (testBounded) {
124         const SkTSpan* test = testBounded->fBounded;
125         double startDist = test->pointFirst().distanceSquared(pt);
126         if (closest > startDist) {
127             closest = startDist;
128             result = test->fStartT;
129         }
130         double endDist = test->pointLast().distanceSquared(pt);
131         if (closest > endDist) {
132             closest = endDist;
133             result = test->fEndT;
134         }
135         testBounded = testBounded->fNext;
136     }
137     SkASSERT(between(0, result, 1));
138     return result;
139 }
140 
141 #ifdef SK_DEBUG
142 
debugIsBefore(const SkTSpan * span) const143 bool SkTSpan::debugIsBefore(const SkTSpan* span) const {
144     const SkTSpan* work = this;
145     do {
146         if (span == work) {
147             return true;
148         }
149     } while ((work = work->fNext));
150     return false;
151 }
152 #endif
153 
contains(double t) const154 bool SkTSpan::contains(double t) const {
155     const SkTSpan* work = this;
156     do {
157         if (between(work->fStartT, t, work->fEndT)) {
158             return true;
159         }
160     } while ((work = work->fNext));
161     return false;
162 }
163 
debugOpp() const164 const SkTSect* SkTSpan::debugOpp() const {
165     return SkDEBUGRELEASE(fDebugSect->debugOpp(), nullptr);
166 }
167 
findOppSpan(const SkTSpan * opp) const168 SkTSpan* SkTSpan::findOppSpan(
169         const SkTSpan* opp) const {
170     SkTSpanBounded* bounded = fBounded;
171     while (bounded) {
172         SkTSpan* test = bounded->fBounded;
173         if (opp == test) {
174             return test;
175         }
176         bounded = bounded->fNext;
177     }
178     return nullptr;
179 }
180 
181 // returns 0 if no hull intersection
182 //         1 if hulls intersect
183 //         2 if hulls only share a common endpoint
184 //        -1 if linear and further checking is required
185 
hullCheck(const SkTSpan * opp,bool * start,bool * oppStart)186 int SkTSpan::hullCheck(const SkTSpan* opp,
187         bool* start, bool* oppStart) {
188     if (fIsLinear) {
189         return -1;
190     }
191     bool ptsInCommon;
192     if (onlyEndPointsInCommon(opp, start, oppStart, &ptsInCommon)) {
193         SkASSERT(ptsInCommon);
194         return 2;
195     }
196     bool linear;
197     if (fPart->hullIntersects(*opp->fPart, &linear)) {
198         if (!linear) {  // check set true if linear
199             return 1;
200         }
201         fIsLinear = true;
202         fIsLine = fPart->controlsInside();
203         return ptsInCommon ? 1 : -1;
204     }
205     // hull is not linear; check set true if intersected at the end points
206     return ((int) ptsInCommon) << 1;  // 0 or 2
207 }
208 
209 // OPTIMIZE ? If at_most_end_pts_in_common detects that one quad is near linear,
210 // use line intersection to guess a better split than 0.5
211 // OPTIMIZE Once at_most_end_pts_in_common detects linear, mark span so all future splits are linear
212 
hullsIntersect(SkTSpan * opp,bool * start,bool * oppStart)213 int SkTSpan::hullsIntersect(SkTSpan* opp,
214         bool* start, bool* oppStart) {
215     if (!fBounds.intersects(opp->fBounds)) {
216         return 0;
217     }
218     int hullSect = this->hullCheck(opp, start, oppStart);
219     if (hullSect >= 0) {
220         return hullSect;
221     }
222     hullSect = opp->hullCheck(this, oppStart, start);
223     if (hullSect >= 0) {
224         return hullSect;
225     }
226     return -1;
227 }
228 
init(const SkTCurve & c)229 void SkTSpan::init(const SkTCurve& c) {
230     fPrev = fNext = nullptr;
231     fStartT = 0;
232     fEndT = 1;
233     fBounded = nullptr;
234     resetBounds(c);
235 }
236 
initBounds(const SkTCurve & c)237 bool SkTSpan::initBounds(const SkTCurve& c) {
238     if (SkIsNaN(fStartT) || SkIsNaN(fEndT)) {
239         return false;
240     }
241     c.subDivide(fStartT, fEndT, fPart);
242     fBounds.setBounds(*fPart);
243     fCoinStart.init();
244     fCoinEnd.init();
245     fBoundsMax = std::max(fBounds.width(), fBounds.height());
246     fCollapsed = fPart->collapsed();
247     fHasPerp = false;
248     fDeleted = false;
249 #if DEBUG_T_SECT
250     if (fCollapsed) {
251         SkDebugf("%s", "");  // for convenient breakpoints
252     }
253 #endif
254     return fBounds.valid();
255 }
256 
linearsIntersect(SkTSpan * span)257 bool SkTSpan::linearsIntersect(SkTSpan* span) {
258     int result = this->linearIntersects(*span->fPart);
259     if (result <= 1) {
260         return SkToBool(result);
261     }
262     SkASSERT(span->fIsLinear);
263     result = span->linearIntersects(*fPart);
264 //    SkASSERT(result <= 1);
265     return SkToBool(result);
266 }
267 
linearT(const SkDPoint & pt) const268 double SkTSpan::linearT(const SkDPoint& pt) const {
269     SkDVector len = this->pointLast() - this->pointFirst();
270     return fabs(len.fX) > fabs(len.fY)
271             ? (pt.fX - this->pointFirst().fX) / len.fX
272             : (pt.fY - this->pointFirst().fY) / len.fY;
273 }
274 
linearIntersects(const SkTCurve & q2) const275 int SkTSpan::linearIntersects(const SkTCurve& q2) const {
276     // looks like q1 is near-linear
277     int start = 0, end = fPart->pointLast();  // the outside points are usually the extremes
278     if (!fPart->controlsInside()) {
279         double dist = 0;  // if there's any question, compute distance to find best outsiders
280         for (int outer = 0; outer < this->pointCount() - 1; ++outer) {
281             for (int inner = outer + 1; inner < this->pointCount(); ++inner) {
282                 double test = ((*fPart)[outer] - (*fPart)[inner]).lengthSquared();
283                 if (dist > test) {
284                     continue;
285                 }
286                 dist = test;
287                 start = outer;
288                 end = inner;
289             }
290         }
291     }
292     // see if q2 is on one side of the line formed by the extreme points
293     double origX = (*fPart)[start].fX;
294     double origY = (*fPart)[start].fY;
295     double adj = (*fPart)[end].fX - origX;
296     double opp = (*fPart)[end].fY - origY;
297     double maxPart = std::max(fabs(adj), fabs(opp));
298     double sign = 0;  // initialization to shut up warning in release build
299     for (int n = 0; n < q2.pointCount(); ++n) {
300         double dx = q2[n].fY - origY;
301         double dy = q2[n].fX - origX;
302         double maxVal = std::max(maxPart, std::max(fabs(dx), fabs(dy)));
303         double test = (q2[n].fY - origY) * adj - (q2[n].fX - origX) * opp;
304         if (precisely_zero_when_compared_to(test, maxVal)) {
305             return 1;
306         }
307         if (approximately_zero_when_compared_to(test, maxVal)) {
308             return 3;
309         }
310         if (n == 0) {
311             sign = test;
312             continue;
313         }
314         if (test * sign < 0) {
315             return 1;
316         }
317     }
318     return 0;
319 }
320 
onlyEndPointsInCommon(const SkTSpan * opp,bool * start,bool * oppStart,bool * ptsInCommon)321 bool SkTSpan::onlyEndPointsInCommon(const SkTSpan* opp,
322         bool* start, bool* oppStart, bool* ptsInCommon) {
323     if (opp->pointFirst() == this->pointFirst()) {
324         *start = *oppStart = true;
325     } else if (opp->pointFirst() == this->pointLast()) {
326         *start = false;
327         *oppStart = true;
328     } else if (opp->pointLast() == this->pointFirst()) {
329         *start = true;
330         *oppStart = false;
331     } else if (opp->pointLast() == this->pointLast()) {
332         *start = *oppStart = false;
333     } else {
334         *ptsInCommon = false;
335         return false;
336     }
337     *ptsInCommon = true;
338     const SkDPoint* otherPts[4], * oppOtherPts[4];
339 //  const SkDPoint* otherPts[this->pointCount() - 1], * oppOtherPts[opp->pointCount() - 1];
340     int baseIndex = *start ? 0 : fPart->pointLast();
341     fPart->otherPts(baseIndex, otherPts);
342     opp->fPart->otherPts(*oppStart ? 0 : opp->fPart->pointLast(), oppOtherPts);
343     const SkDPoint& base = (*fPart)[baseIndex];
344     for (int o1 = 0; o1 < this->pointCount() - 1; ++o1) {
345         SkDVector v1 = *otherPts[o1] - base;
346         for (int o2 = 0; o2 < opp->pointCount() - 1; ++o2) {
347             SkDVector v2 = *oppOtherPts[o2] - base;
348             if (v2.dot(v1) >= 0) {
349                 return false;
350             }
351         }
352     }
353     return true;
354 }
355 
oppT(double t) const356 SkTSpan* SkTSpan::oppT(double t) const {
357     SkTSpanBounded* bounded = fBounded;
358     while (bounded) {
359         SkTSpan* test = bounded->fBounded;
360         if (between(test->fStartT, t, test->fEndT)) {
361             return test;
362         }
363         bounded = bounded->fNext;
364     }
365     return nullptr;
366 }
367 
removeAllBounded()368 bool SkTSpan::removeAllBounded() {
369     bool deleteSpan = false;
370     SkTSpanBounded* bounded = fBounded;
371     while (bounded) {
372         SkTSpan* opp = bounded->fBounded;
373         deleteSpan |= opp->removeBounded(this);
374         bounded = bounded->fNext;
375     }
376     return deleteSpan;
377 }
378 
removeBounded(const SkTSpan * opp)379 bool SkTSpan::removeBounded(const SkTSpan* opp) {
380     if (fHasPerp) {
381         bool foundStart = false;
382         bool foundEnd = false;
383         SkTSpanBounded* bounded = fBounded;
384         while (bounded) {
385             SkTSpan* test = bounded->fBounded;
386             if (opp != test) {
387                 foundStart |= between(test->fStartT, fCoinStart.perpT(), test->fEndT);
388                 foundEnd |= between(test->fStartT, fCoinEnd.perpT(), test->fEndT);
389             }
390             bounded = bounded->fNext;
391         }
392         if (!foundStart || !foundEnd) {
393             fHasPerp = false;
394             fCoinStart.init();
395             fCoinEnd.init();
396         }
397     }
398     SkTSpanBounded* bounded = fBounded;
399     SkTSpanBounded* prev = nullptr;
400     while (bounded) {
401         SkTSpanBounded* boundedNext = bounded->fNext;
402         if (opp == bounded->fBounded) {
403             if (prev) {
404                 prev->fNext = boundedNext;
405                 return false;
406             } else {
407                 fBounded = boundedNext;
408                 return fBounded == nullptr;
409             }
410         }
411         prev = bounded;
412         bounded = boundedNext;
413     }
414     SkOPASSERT(0);
415     return false;
416 }
417 
splitAt(SkTSpan * work,double t,SkArenaAlloc * heap)418 bool SkTSpan::splitAt(SkTSpan* work, double t, SkArenaAlloc* heap) {
419     fStartT = t;
420     fEndT = work->fEndT;
421     if (fStartT == fEndT) {
422         fCollapsed = true;
423         return false;
424     }
425     work->fEndT = t;
426     if (work->fStartT == work->fEndT) {
427         work->fCollapsed = true;
428         return false;
429     }
430     fPrev = work;
431     fNext = work->fNext;
432     fIsLinear = work->fIsLinear;
433     fIsLine = work->fIsLine;
434 
435     work->fNext = this;
436     if (fNext) {
437         fNext->fPrev = this;
438     }
439     this->validate();
440     SkTSpanBounded* bounded = work->fBounded;
441     fBounded = nullptr;
442     while (bounded) {
443         this->addBounded(bounded->fBounded, heap);
444         bounded = bounded->fNext;
445     }
446     bounded = fBounded;
447     while (bounded) {
448         bounded->fBounded->addBounded(this, heap);
449         bounded = bounded->fNext;
450     }
451     return true;
452 }
453 
validate() const454 void SkTSpan::validate() const {
455 #if DEBUG_VALIDATE
456     SkASSERT(this != fPrev);
457     SkASSERT(this != fNext);
458     SkASSERT(fNext == nullptr || fNext != fPrev);
459     SkASSERT(fNext == nullptr || this == fNext->fPrev);
460     SkASSERT(fPrev == nullptr || this == fPrev->fNext);
461     this->validateBounded();
462 #endif
463 #if DEBUG_T_SECT
464     SkASSERT(fBounds.width() || fBounds.height() || fCollapsed);
465     SkASSERT(fBoundsMax == std::max(fBounds.width(), fBounds.height()) || fCollapsed == 0xFF);
466     SkASSERT(0 <= fStartT);
467     SkASSERT(fEndT <= 1);
468     SkASSERT(fStartT <= fEndT);
469     SkASSERT(fBounded || fCollapsed == 0xFF);
470     if (fHasPerp) {
471         if (fCoinStart.isMatch()) {
472             validatePerpT(fCoinStart.perpT());
473             validatePerpPt(fCoinStart.perpT(), fCoinStart.perpPt());
474         }
475         if (fCoinEnd.isMatch()) {
476             validatePerpT(fCoinEnd.perpT());
477             validatePerpPt(fCoinEnd.perpT(), fCoinEnd.perpPt());
478         }
479     }
480 #endif
481 }
482 
validateBounded() const483 void SkTSpan::validateBounded() const {
484 #if DEBUG_VALIDATE
485     const SkTSpanBounded* testBounded = fBounded;
486     while (testBounded) {
487         SkDEBUGCODE(const SkTSpan* overlap = testBounded->fBounded);
488         SkASSERT(!overlap->fDeleted);
489 #if DEBUG_T_SECT
490         SkASSERT(((this->debugID() ^ overlap->debugID()) & 1) == 1);
491         SkASSERT(overlap->findOppSpan(this));
492 #endif
493         testBounded = testBounded->fNext;
494     }
495 #endif
496 }
497 
validatePerpT(double oppT) const498 void SkTSpan::validatePerpT(double oppT) const {
499     const SkTSpanBounded* testBounded = fBounded;
500     while (testBounded) {
501         const SkTSpan* overlap = testBounded->fBounded;
502         if (precisely_between(overlap->fStartT, oppT, overlap->fEndT)) {
503             return;
504         }
505         testBounded = testBounded->fNext;
506     }
507     SkASSERT(0);
508 }
509 
validatePerpPt(double t,const SkDPoint & pt) const510 void SkTSpan::validatePerpPt(double t, const SkDPoint& pt) const {
511     SkASSERT(fDebugSect->fOppSect->fCurve.ptAtT(t) == pt);
512 }
513 
SkTSect(const SkTCurve & c SkDEBUGPARAMS (SkOpGlobalState * debugGlobalState)PATH_OPS_DEBUG_T_SECT_PARAMS (int id))514 SkTSect::SkTSect(const SkTCurve& c
515         SkDEBUGPARAMS(SkOpGlobalState* debugGlobalState)
516         PATH_OPS_DEBUG_T_SECT_PARAMS(int id))
517     : fCurve(c)
518     , fHeap(sizeof(SkTSpan) * 4)
519     , fCoincident(nullptr)
520     , fDeleted(nullptr)
521     , fActiveCount(0)
522     , fHung(false)
523     SkDEBUGPARAMS(fDebugGlobalState(debugGlobalState))
524     PATH_OPS_DEBUG_T_SECT_PARAMS(fID(id))
525     PATH_OPS_DEBUG_T_SECT_PARAMS(fDebugCount(0))
526     PATH_OPS_DEBUG_T_SECT_PARAMS(fDebugAllocatedCount(0))
527 {
528     this->resetRemovedEnds();
529     fHead = this->addOne();
530     SkDEBUGCODE(fHead->debugSetGlobalState(debugGlobalState));
531     fHead->init(c);
532 }
533 
addOne()534 SkTSpan* SkTSect::addOne() {
535     SkTSpan* result;
536     if (fDeleted) {
537         result = fDeleted;
538         fDeleted = result->fNext;
539     } else {
540         result = fHeap.make<SkTSpan>(fCurve, fHeap);
541 #if DEBUG_T_SECT
542         ++fDebugAllocatedCount;
543 #endif
544     }
545     result->reset();
546     result->fHasPerp = false;
547     result->fDeleted = false;
548     ++fActiveCount;
549     PATH_OPS_DEBUG_T_SECT_CODE(result->fID = fDebugCount++ * 2 + fID);
550     SkDEBUGCODE(result->fDebugSect = this);
551 #ifdef SK_DEBUG
552     result->debugInit(fCurve, fHeap);
553     result->fCoinStart.debugInit();
554     result->fCoinEnd.debugInit();
555     result->fPrev = result->fNext = nullptr;
556     result->fBounds.debugInit();
557     result->fStartT = result->fEndT = result->fBoundsMax = SK_ScalarNaN;
558     result->fCollapsed = result->fIsLinear = result->fIsLine = 0xFF;
559 #endif
560     return result;
561 }
562 
binarySearchCoin(SkTSect * sect2,double tStart,double tStep,double * resultT,double * oppT,SkTSpan ** oppFirst)563 bool SkTSect::binarySearchCoin(SkTSect* sect2, double tStart,
564         double tStep, double* resultT, double* oppT, SkTSpan** oppFirst) {
565     SkTSpan work(fCurve, fHeap);
566     double result = work.fStartT = work.fEndT = tStart;
567     SkDEBUGCODE(work.fDebugSect = this);
568     SkDPoint last = fCurve.ptAtT(tStart);
569     SkDPoint oppPt;
570     bool flip = false;
571     bool contained = false;
572     bool down = tStep < 0;
573     const SkTCurve& opp = sect2->fCurve;
574     do {
575         tStep *= 0.5;
576         work.fStartT += tStep;
577         if (flip) {
578             tStep = -tStep;
579             flip = false;
580         }
581         work.initBounds(fCurve);
582         if (work.fCollapsed) {
583             return false;
584         }
585         if (last.approximatelyEqual(work.pointFirst())) {
586             break;
587         }
588         last = work.pointFirst();
589         work.fCoinStart.setPerp(fCurve, work.fStartT, last, opp);
590         if (work.fCoinStart.isMatch()) {
591 #if DEBUG_T_SECT
592             work.validatePerpPt(work.fCoinStart.perpT(), work.fCoinStart.perpPt());
593 #endif
594             double oppTTest = work.fCoinStart.perpT();
595             if (sect2->fHead->contains(oppTTest)) {
596                 *oppT = oppTTest;
597                 oppPt = work.fCoinStart.perpPt();
598                 contained = true;
599                 if (down ? result <= work.fStartT : result >= work.fStartT) {
600                     *oppFirst = nullptr;    // signal caller to fail
601                     return false;
602                 }
603                 result = work.fStartT;
604                 continue;
605             }
606         }
607         tStep = -tStep;
608         flip = true;
609     } while (true);
610     if (!contained) {
611         return false;
612     }
613     if (last.approximatelyEqual(fCurve[0])) {
614         result = 0;
615     } else if (last.approximatelyEqual(this->pointLast())) {
616         result = 1;
617     }
618     if (oppPt.approximatelyEqual(opp[0])) {
619         *oppT = 0;
620     } else if (oppPt.approximatelyEqual(sect2->pointLast())) {
621         *oppT = 1;
622     }
623     *resultT = result;
624     return true;
625 }
626 
627 // OPTIMIZE ? keep a sorted list of sizes in the form of a doubly-linked list in quad span
628 //            so that each quad sect has a pointer to the largest, and can update it as spans
629 //            are split
630 
boundsMax()631 SkTSpan* SkTSect::boundsMax() {
632     SkTSpan* test = fHead;
633     SkTSpan* largest = fHead;
634     bool lCollapsed = largest->fCollapsed;
635     int safetyNet = 10000;
636     while ((test = test->fNext)) {
637         if (!--safetyNet) {
638             fHung = true;
639             return nullptr;
640         }
641         bool tCollapsed = test->fCollapsed;
642         if ((lCollapsed && !tCollapsed) || (lCollapsed == tCollapsed &&
643                 largest->fBoundsMax < test->fBoundsMax)) {
644             largest = test;
645             lCollapsed = test->fCollapsed;
646         }
647     }
648     return largest;
649 }
650 
coincidentCheck(SkTSect * sect2)651 bool SkTSect::coincidentCheck(SkTSect* sect2) {
652     SkTSpan* first = fHead;
653     if (!first) {
654         return false;
655     }
656     SkTSpan* last, * next;
657     do {
658         int consecutive = this->countConsecutiveSpans(first, &last);
659         next = last->fNext;
660         if (consecutive < COINCIDENT_SPAN_COUNT) {
661             continue;
662         }
663         this->validate();
664         sect2->validate();
665         this->computePerpendiculars(sect2, first, last);
666         this->validate();
667         sect2->validate();
668         // check to see if a range of points are on the curve
669         SkTSpan* coinStart = first;
670         do {
671             bool success = this->extractCoincident(sect2, coinStart, last, &coinStart);
672             if (!success) {
673                 return false;
674             }
675         } while (coinStart && !last->fDeleted);
676         if (!fHead || !sect2->fHead) {
677             break;
678         }
679         if (!next || next->fDeleted) {
680             break;
681         }
682     } while ((first = next));
683     return true;
684 }
685 
coincidentForce(SkTSect * sect2,double start1s,double start1e)686 void SkTSect::coincidentForce(SkTSect* sect2,
687         double start1s, double start1e) {
688     SkTSpan* first = fHead;
689     SkTSpan* last = this->tail();
690     SkTSpan* oppFirst = sect2->fHead;
691     SkTSpan* oppLast = sect2->tail();
692     if (!last || !oppLast) {
693         return;
694     }
695     bool deleteEmptySpans = this->updateBounded(first, last, oppFirst);
696     deleteEmptySpans |= sect2->updateBounded(oppFirst, oppLast, first);
697     this->removeSpanRange(first, last);
698     sect2->removeSpanRange(oppFirst, oppLast);
699     first->fStartT = start1s;
700     first->fEndT = start1e;
701     first->resetBounds(fCurve);
702     first->fCoinStart.setPerp(fCurve, start1s, fCurve[0], sect2->fCurve);
703     first->fCoinEnd.setPerp(fCurve, start1e, this->pointLast(), sect2->fCurve);
704     bool oppMatched = first->fCoinStart.perpT() < first->fCoinEnd.perpT();
705     double oppStartT = first->fCoinStart.perpT() == -1 ? 0 : std::max(0., first->fCoinStart.perpT());
706     double oppEndT = first->fCoinEnd.perpT() == -1 ? 1 : std::min(1., first->fCoinEnd.perpT());
707     if (!oppMatched) {
708         using std::swap;
709         swap(oppStartT, oppEndT);
710     }
711     oppFirst->fStartT = oppStartT;
712     oppFirst->fEndT = oppEndT;
713     oppFirst->resetBounds(sect2->fCurve);
714     this->removeCoincident(first, false);
715     sect2->removeCoincident(oppFirst, true);
716     if (deleteEmptySpans) {
717         this->deleteEmptySpans();
718         sect2->deleteEmptySpans();
719     }
720 }
721 
coincidentHasT(double t)722 bool SkTSect::coincidentHasT(double t) {
723     SkTSpan* test = fCoincident;
724     while (test) {
725         if (between(test->fStartT, t, test->fEndT)) {
726             return true;
727         }
728         test = test->fNext;
729     }
730     return false;
731 }
732 
collapsed() const733 int SkTSect::collapsed() const {
734     int result = 0;
735     const SkTSpan* test = fHead;
736     while (test) {
737         if (test->fCollapsed) {
738             ++result;
739         }
740         test = test->next();
741     }
742     return result;
743 }
744 
computePerpendiculars(SkTSect * sect2,SkTSpan * first,SkTSpan * last)745 void SkTSect::computePerpendiculars(SkTSect* sect2,
746         SkTSpan* first, SkTSpan* last) {
747     if (!last) {
748         return;
749     }
750     const SkTCurve& opp = sect2->fCurve;
751     SkTSpan* work = first;
752     SkTSpan* prior = nullptr;
753     do {
754         if (!work->fHasPerp && !work->fCollapsed) {
755             if (prior) {
756                 work->fCoinStart = prior->fCoinEnd;
757             } else {
758                 work->fCoinStart.setPerp(fCurve, work->fStartT, work->pointFirst(), opp);
759             }
760             if (work->fCoinStart.isMatch()) {
761                 double perpT = work->fCoinStart.perpT();
762                 if (sect2->coincidentHasT(perpT)) {
763                     work->fCoinStart.init();
764                 } else {
765                     sect2->addForPerp(work, perpT);
766                 }
767             }
768             work->fCoinEnd.setPerp(fCurve, work->fEndT, work->pointLast(), opp);
769             if (work->fCoinEnd.isMatch()) {
770                 double perpT = work->fCoinEnd.perpT();
771                 if (sect2->coincidentHasT(perpT)) {
772                     work->fCoinEnd.init();
773                 } else {
774                     sect2->addForPerp(work, perpT);
775                 }
776             }
777             work->fHasPerp = true;
778         }
779         if (work == last) {
780             break;
781         }
782         prior = work;
783         work = work->fNext;
784         SkASSERT(work);
785     } while (true);
786 }
787 
countConsecutiveSpans(SkTSpan * first,SkTSpan ** lastPtr) const788 int SkTSect::countConsecutiveSpans(SkTSpan* first,
789         SkTSpan** lastPtr) const {
790     int consecutive = 1;
791     SkTSpan* last = first;
792     do {
793         SkTSpan* next = last->fNext;
794         if (!next) {
795             break;
796         }
797         if (next->fStartT > last->fEndT) {
798             break;
799         }
800         ++consecutive;
801         last = next;
802     } while (true);
803     *lastPtr = last;
804     return consecutive;
805 }
806 
hasBounded(const SkTSpan * span) const807 bool SkTSect::hasBounded(const SkTSpan* span) const {
808     const SkTSpan* test = fHead;
809     if (!test) {
810         return false;
811     }
812     do {
813         if (test->findOppSpan(span)) {
814             return true;
815         }
816     } while ((test = test->next()));
817     return false;
818 }
819 
deleteEmptySpans()820 bool SkTSect::deleteEmptySpans() {
821     SkTSpan* test;
822     SkTSpan* next = fHead;
823     int safetyHatch = 1000;
824     while ((test = next)) {
825         next = test->fNext;
826         if (!test->fBounded) {
827             if (!this->removeSpan(test)) {
828                 return false;
829             }
830         }
831         if (--safetyHatch < 0) {
832             return false;
833         }
834     }
835     return true;
836 }
837 
extractCoincident(SkTSect * sect2,SkTSpan * first,SkTSpan * last,SkTSpan ** result)838 bool SkTSect::extractCoincident(
839         SkTSect* sect2,
840         SkTSpan* first, SkTSpan* last,
841         SkTSpan** result) {
842     first = findCoincidentRun(first, &last);
843     if (!first || !last) {
844         *result = nullptr;
845         return true;
846     }
847     // march outwards to find limit of coincidence from here to previous and next spans
848     double startT = first->fStartT;
849     double oppStartT SK_INIT_TO_AVOID_WARNING;
850     double oppEndT SK_INIT_TO_AVOID_WARNING;
851     SkTSpan* prev = first->fPrev;
852     SkASSERT(first->fCoinStart.isMatch());
853     SkTSpan* oppFirst = first->findOppT(first->fCoinStart.perpT());
854     SkOPASSERT(last->fCoinEnd.isMatch());
855     bool oppMatched = first->fCoinStart.perpT() < first->fCoinEnd.perpT();
856     double coinStart;
857     SkDEBUGCODE(double coinEnd);
858     SkTSpan* cutFirst;
859     if (prev && prev->fEndT == startT
860             && this->binarySearchCoin(sect2, startT, prev->fStartT - startT, &coinStart,
861                                       &oppStartT, &oppFirst)
862             && prev->fStartT < coinStart && coinStart < startT
863             && (cutFirst = prev->oppT(oppStartT))) {
864         oppFirst = cutFirst;
865         first = this->addSplitAt(prev, coinStart);
866         first->markCoincident();
867         prev->fCoinEnd.markCoincident();
868         if (oppFirst->fStartT < oppStartT && oppStartT < oppFirst->fEndT) {
869             SkTSpan* oppHalf = sect2->addSplitAt(oppFirst, oppStartT);
870             if (oppMatched) {
871                 oppFirst->fCoinEnd.markCoincident();
872                 oppHalf->markCoincident();
873                 oppFirst = oppHalf;
874             } else {
875                 oppFirst->markCoincident();
876                 oppHalf->fCoinStart.markCoincident();
877             }
878         }
879     } else {
880         if (!oppFirst) {
881             return false;
882         }
883         SkDEBUGCODE(coinStart = first->fStartT);
884         SkDEBUGCODE(oppStartT = oppMatched ? oppFirst->fStartT : oppFirst->fEndT);
885     }
886     // FIXME: incomplete : if we're not at the end, find end of coin
887     SkTSpan* oppLast;
888     SkOPASSERT(last->fCoinEnd.isMatch());
889     oppLast = last->findOppT(last->fCoinEnd.perpT());
890     SkDEBUGCODE(coinEnd = last->fEndT);
891 #ifdef SK_DEBUG
892     if (!this->globalState() || !this->globalState()->debugSkipAssert()) {
893         oppEndT = oppMatched ? oppLast->fEndT : oppLast->fStartT;
894     }
895 #endif
896     if (!oppMatched) {
897         using std::swap;
898         swap(oppFirst, oppLast);
899         swap(oppStartT, oppEndT);
900     }
901     SkOPASSERT(oppStartT < oppEndT);
902     SkASSERT(coinStart == first->fStartT);
903     SkASSERT(coinEnd == last->fEndT);
904     if (!oppFirst) {
905         *result = nullptr;
906         return true;
907     }
908     SkOPASSERT(oppStartT == oppFirst->fStartT);
909     if (!oppLast) {
910         *result = nullptr;
911         return true;
912     }
913     SkOPASSERT(oppEndT == oppLast->fEndT);
914     // reduce coincident runs to single entries
915     this->validate();
916     sect2->validate();
917     bool deleteEmptySpans = this->updateBounded(first, last, oppFirst);
918     deleteEmptySpans |= sect2->updateBounded(oppFirst, oppLast, first);
919     this->removeSpanRange(first, last);
920     sect2->removeSpanRange(oppFirst, oppLast);
921     first->fEndT = last->fEndT;
922     first->resetBounds(this->fCurve);
923     first->fCoinStart.setPerp(fCurve, first->fStartT, first->pointFirst(), sect2->fCurve);
924     first->fCoinEnd.setPerp(fCurve, first->fEndT, first->pointLast(), sect2->fCurve);
925     oppStartT = first->fCoinStart.perpT();
926     oppEndT = first->fCoinEnd.perpT();
927     if (between(0, oppStartT, 1) && between(0, oppEndT, 1)) {
928         if (!oppMatched) {
929             using std::swap;
930             swap(oppStartT, oppEndT);
931         }
932         oppFirst->fStartT = oppStartT;
933         oppFirst->fEndT = oppEndT;
934         oppFirst->resetBounds(sect2->fCurve);
935     }
936     this->validateBounded();
937     sect2->validateBounded();
938     last = first->fNext;
939     if (!this->removeCoincident(first, false)) {
940         return false;
941     }
942     if (!sect2->removeCoincident(oppFirst, true)) {
943         return false;
944     }
945     if (deleteEmptySpans) {
946         if (!this->deleteEmptySpans() || !sect2->deleteEmptySpans()) {
947             *result = nullptr;
948             return false;
949         }
950     }
951     this->validate();
952     sect2->validate();
953     *result = last && !last->fDeleted && fHead && sect2->fHead ? last : nullptr;
954     return true;
955 }
956 
findCoincidentRun(SkTSpan * first,SkTSpan ** lastPtr)957 SkTSpan* SkTSect::findCoincidentRun(
958         SkTSpan* first, SkTSpan** lastPtr) {
959     SkTSpan* work = first;
960     SkTSpan* lastCandidate = nullptr;
961     first = nullptr;
962     // find the first fully coincident span
963     do {
964         if (work->fCoinStart.isMatch()) {
965 #if DEBUG_T_SECT
966             work->validatePerpT(work->fCoinStart.perpT());
967             work->validatePerpPt(work->fCoinStart.perpT(), work->fCoinStart.perpPt());
968 #endif
969             SkOPASSERT(work->hasOppT(work->fCoinStart.perpT()));
970             if (!work->fCoinEnd.isMatch()) {
971                 break;
972             }
973             lastCandidate = work;
974             if (!first) {
975                 first = work;
976             }
977         } else if (first && work->fCollapsed) {
978             *lastPtr = lastCandidate;
979             return first;
980         } else {
981             lastCandidate = nullptr;
982             SkOPASSERT(!first);
983         }
984         if (work == *lastPtr) {
985             return first;
986         }
987         work = work->fNext;
988         if (!work) {
989             return nullptr;
990         }
991     } while (true);
992     if (lastCandidate) {
993         *lastPtr = lastCandidate;
994     }
995     return first;
996 }
997 
intersects(SkTSpan * span,SkTSect * opp,SkTSpan * oppSpan,int * oppResult)998 int SkTSect::intersects(SkTSpan* span,
999         SkTSect* opp,
1000         SkTSpan* oppSpan, int* oppResult) {
1001     bool spanStart, oppStart;
1002     int hullResult = span->hullsIntersect(oppSpan, &spanStart, &oppStart);
1003     if (hullResult >= 0) {
1004         if (hullResult == 2) {  // hulls have one point in common
1005             if (!span->fBounded || !span->fBounded->fNext) {
1006                 SkASSERT(!span->fBounded || span->fBounded->fBounded == oppSpan);
1007                 if (spanStart) {
1008                     span->fEndT = span->fStartT;
1009                 } else {
1010                     span->fStartT = span->fEndT;
1011                 }
1012             } else {
1013                 hullResult = 1;
1014             }
1015             if (!oppSpan->fBounded || !oppSpan->fBounded->fNext) {
1016                 if (oppSpan->fBounded && oppSpan->fBounded->fBounded != span) {
1017                     return 0;
1018                 }
1019                 if (oppStart) {
1020                     oppSpan->fEndT = oppSpan->fStartT;
1021                 } else {
1022                     oppSpan->fStartT = oppSpan->fEndT;
1023                 }
1024                 *oppResult = 2;
1025             } else {
1026                 *oppResult = 1;
1027             }
1028         } else {
1029             *oppResult = 1;
1030         }
1031         return hullResult;
1032     }
1033     if (span->fIsLine && oppSpan->fIsLine) {
1034         SkIntersections i;
1035         int sects = this->linesIntersect(span, opp, oppSpan, &i);
1036         if (sects == 2) {
1037             return *oppResult = 1;
1038         }
1039         if (!sects) {
1040             return -1;
1041         }
1042         this->removedEndCheck(span);
1043         span->fStartT = span->fEndT = i[0][0];
1044         opp->removedEndCheck(oppSpan);
1045         oppSpan->fStartT = oppSpan->fEndT = i[1][0];
1046         return *oppResult = 2;
1047     }
1048     if (span->fIsLinear || oppSpan->fIsLinear) {
1049         return *oppResult = (int) span->linearsIntersect(oppSpan);
1050     }
1051     return *oppResult = 1;
1052 }
1053 
1054 template<typename SkTCurve>
is_parallel(const SkDLine & thisLine,const SkTCurve & opp)1055 static bool is_parallel(const SkDLine& thisLine, const SkTCurve& opp) {
1056     if (!opp.IsConic()) {
1057         return false; // FIXME : breaks a lot of stuff now
1058     }
1059     int finds = 0;
1060     SkDLine thisPerp;
1061     thisPerp.fPts[0].fX = thisLine.fPts[1].fX + (thisLine.fPts[1].fY - thisLine.fPts[0].fY);
1062     thisPerp.fPts[0].fY = thisLine.fPts[1].fY + (thisLine.fPts[0].fX - thisLine.fPts[1].fX);
1063     thisPerp.fPts[1] = thisLine.fPts[1];
1064     SkIntersections perpRayI;
1065     perpRayI.intersectRay(opp, thisPerp);
1066     for (int pIndex = 0; pIndex < perpRayI.used(); ++pIndex) {
1067         finds += perpRayI.pt(pIndex).approximatelyEqual(thisPerp.fPts[1]);
1068     }
1069     thisPerp.fPts[1].fX = thisLine.fPts[0].fX + (thisLine.fPts[1].fY - thisLine.fPts[0].fY);
1070     thisPerp.fPts[1].fY = thisLine.fPts[0].fY + (thisLine.fPts[0].fX - thisLine.fPts[1].fX);
1071     thisPerp.fPts[0] = thisLine.fPts[0];
1072     perpRayI.intersectRay(opp, thisPerp);
1073     for (int pIndex = 0; pIndex < perpRayI.used(); ++pIndex) {
1074         finds += perpRayI.pt(pIndex).approximatelyEqual(thisPerp.fPts[0]);
1075     }
1076     return finds >= 2;
1077 }
1078 
1079 // while the intersection points are sufficiently far apart:
1080 // construct the tangent lines from the intersections
1081 // find the point where the tangent line intersects the opposite curve
1082 
linesIntersect(SkTSpan * span,SkTSect * opp,SkTSpan * oppSpan,SkIntersections * i)1083 int SkTSect::linesIntersect(SkTSpan* span,
1084         SkTSect* opp,
1085         SkTSpan* oppSpan, SkIntersections* i) {
1086     SkIntersections thisRayI  SkDEBUGCODE((span->fDebugGlobalState));
1087     SkIntersections oppRayI  SkDEBUGCODE((span->fDebugGlobalState));
1088     SkDLine thisLine = {{ span->pointFirst(), span->pointLast() }};
1089     SkDLine oppLine = {{ oppSpan->pointFirst(), oppSpan->pointLast() }};
1090     int loopCount = 0;
1091     double bestDistSq = DBL_MAX;
1092     if (!thisRayI.intersectRay(opp->fCurve, thisLine)) {
1093         return 0;
1094     }
1095     if (!oppRayI.intersectRay(this->fCurve, oppLine)) {
1096         return 0;
1097     }
1098     // if the ends of each line intersect the opposite curve, the lines are coincident
1099     if (thisRayI.used() > 1) {
1100         int ptMatches = 0;
1101         for (int tIndex = 0; tIndex < thisRayI.used(); ++tIndex) {
1102             for (int lIndex = 0; lIndex < (int) std::size(thisLine.fPts); ++lIndex) {
1103                 ptMatches += thisRayI.pt(tIndex).approximatelyEqual(thisLine.fPts[lIndex]);
1104             }
1105         }
1106         if (ptMatches == 2 || is_parallel(thisLine, opp->fCurve)) {
1107             return 2;
1108         }
1109     }
1110     if (oppRayI.used() > 1) {
1111         int ptMatches = 0;
1112         for (int oIndex = 0; oIndex < oppRayI.used(); ++oIndex) {
1113             for (int lIndex = 0; lIndex < (int) std::size(oppLine.fPts); ++lIndex) {
1114                 ptMatches += oppRayI.pt(oIndex).approximatelyEqual(oppLine.fPts[lIndex]);
1115             }
1116         }
1117         if (ptMatches == 2|| is_parallel(oppLine, this->fCurve)) {
1118             return 2;
1119         }
1120     }
1121     do {
1122         // pick the closest pair of points
1123         double closest = DBL_MAX;
1124         int closeIndex SK_INIT_TO_AVOID_WARNING;
1125         int oppCloseIndex SK_INIT_TO_AVOID_WARNING;
1126         for (int index = 0; index < oppRayI.used(); ++index) {
1127             if (!roughly_between(span->fStartT, oppRayI[0][index], span->fEndT)) {
1128                 continue;
1129             }
1130             for (int oIndex = 0; oIndex < thisRayI.used(); ++oIndex) {
1131                 if (!roughly_between(oppSpan->fStartT, thisRayI[0][oIndex], oppSpan->fEndT)) {
1132                     continue;
1133                 }
1134                 double distSq = thisRayI.pt(index).distanceSquared(oppRayI.pt(oIndex));
1135                 if (closest > distSq) {
1136                     closest = distSq;
1137                     closeIndex = index;
1138                     oppCloseIndex = oIndex;
1139                 }
1140             }
1141         }
1142         if (closest == DBL_MAX) {
1143             break;
1144         }
1145         const SkDPoint& oppIPt = thisRayI.pt(oppCloseIndex);
1146         const SkDPoint& iPt = oppRayI.pt(closeIndex);
1147         if (between(span->fStartT, oppRayI[0][closeIndex], span->fEndT)
1148                 && between(oppSpan->fStartT, thisRayI[0][oppCloseIndex], oppSpan->fEndT)
1149                 && oppIPt.approximatelyEqual(iPt)) {
1150             i->merge(oppRayI, closeIndex, thisRayI, oppCloseIndex);
1151             return i->used();
1152         }
1153         double distSq = oppIPt.distanceSquared(iPt);
1154         if (bestDistSq < distSq || ++loopCount > 5) {
1155             return 0;
1156         }
1157         bestDistSq = distSq;
1158         double oppStart = oppRayI[0][closeIndex];
1159         thisLine[0] = fCurve.ptAtT(oppStart);
1160         thisLine[1] = thisLine[0] + fCurve.dxdyAtT(oppStart);
1161         if (!thisRayI.intersectRay(opp->fCurve, thisLine)) {
1162             break;
1163         }
1164         double start = thisRayI[0][oppCloseIndex];
1165         oppLine[0] = opp->fCurve.ptAtT(start);
1166         oppLine[1] = oppLine[0] + opp->fCurve.dxdyAtT(start);
1167         if (!oppRayI.intersectRay(this->fCurve, oppLine)) {
1168             break;
1169         }
1170     } while (true);
1171     // convergence may fail if the curves are nearly coincident
1172     SkTCoincident oCoinS, oCoinE;
1173     oCoinS.setPerp(opp->fCurve, oppSpan->fStartT, oppSpan->pointFirst(), fCurve);
1174     oCoinE.setPerp(opp->fCurve, oppSpan->fEndT, oppSpan->pointLast(), fCurve);
1175     double tStart = oCoinS.perpT();
1176     double tEnd = oCoinE.perpT();
1177     bool swap = tStart > tEnd;
1178     if (swap) {
1179         using std::swap;
1180         swap(tStart, tEnd);
1181     }
1182     tStart = std::max(tStart, span->fStartT);
1183     tEnd = std::min(tEnd, span->fEndT);
1184     if (tStart > tEnd) {
1185         return 0;
1186     }
1187     SkDVector perpS, perpE;
1188     if (tStart == span->fStartT) {
1189         SkTCoincident coinS;
1190         coinS.setPerp(fCurve, span->fStartT, span->pointFirst(), opp->fCurve);
1191         perpS = span->pointFirst() - coinS.perpPt();
1192     } else if (swap) {
1193         perpS = oCoinE.perpPt() - oppSpan->pointLast();
1194     } else {
1195         perpS = oCoinS.perpPt() - oppSpan->pointFirst();
1196     }
1197     if (tEnd == span->fEndT) {
1198         SkTCoincident coinE;
1199         coinE.setPerp(fCurve, span->fEndT, span->pointLast(), opp->fCurve);
1200         perpE = span->pointLast() - coinE.perpPt();
1201     } else if (swap) {
1202         perpE = oCoinS.perpPt() - oppSpan->pointFirst();
1203     } else {
1204         perpE = oCoinE.perpPt() - oppSpan->pointLast();
1205     }
1206     if (perpS.dot(perpE) >= 0) {
1207         return 0;
1208     }
1209     SkTCoincident coinW;
1210     double workT = tStart;
1211     double tStep = tEnd - tStart;
1212     SkDPoint workPt;
1213     do {
1214         tStep *= 0.5;
1215         if (precisely_zero(tStep)) {
1216             return 0;
1217         }
1218         workT += tStep;
1219         workPt = fCurve.ptAtT(workT);
1220         coinW.setPerp(fCurve, workT, workPt, opp->fCurve);
1221         double perpT = coinW.perpT();
1222         if (coinW.isMatch() ? !between(oppSpan->fStartT, perpT, oppSpan->fEndT) : perpT < 0) {
1223             continue;
1224         }
1225         SkDVector perpW = workPt - coinW.perpPt();
1226         if ((perpS.dot(perpW) >= 0) == (tStep < 0)) {
1227             tStep = -tStep;
1228         }
1229         if (workPt.approximatelyEqual(coinW.perpPt())) {
1230             break;
1231         }
1232     } while (true);
1233     double oppTTest = coinW.perpT();
1234     if (!opp->fHead->contains(oppTTest)) {
1235         return 0;
1236     }
1237     i->setMax(1);
1238     i->insert(workT, oppTTest, workPt);
1239     return 1;
1240 }
1241 
markSpanGone(SkTSpan * span)1242 bool SkTSect::markSpanGone(SkTSpan* span) {
1243     if (--fActiveCount < 0) {
1244         return false;
1245     }
1246     span->fNext = fDeleted;
1247     fDeleted = span;
1248     SkOPASSERT(!span->fDeleted);
1249     span->fDeleted = true;
1250     return true;
1251 }
1252 
matchedDirection(double t,const SkTSect * sect2,double t2) const1253 bool SkTSect::matchedDirection(double t, const SkTSect* sect2,
1254         double t2) const {
1255     SkDVector dxdy = this->fCurve.dxdyAtT(t);
1256     SkDVector dxdy2 = sect2->fCurve.dxdyAtT(t2);
1257     return dxdy.dot(dxdy2) >= 0;
1258 }
1259 
matchedDirCheck(double t,const SkTSect * sect2,double t2,bool * calcMatched,bool * oppMatched) const1260 void SkTSect::matchedDirCheck(double t, const SkTSect* sect2,
1261         double t2, bool* calcMatched, bool* oppMatched) const {
1262     if (*calcMatched) {
1263         SkASSERT(*oppMatched == this->matchedDirection(t, sect2, t2));
1264     } else {
1265         *oppMatched = this->matchedDirection(t, sect2, t2);
1266         *calcMatched = true;
1267     }
1268 }
1269 
mergeCoincidence(SkTSect * sect2)1270 void SkTSect::mergeCoincidence(SkTSect* sect2) {
1271     double smallLimit = 0;
1272     do {
1273         // find the smallest unprocessed span
1274         SkTSpan* smaller = nullptr;
1275         SkTSpan* test = fCoincident;
1276         do {
1277             if (!test) {
1278                 return;
1279             }
1280             if (test->fStartT < smallLimit) {
1281                 continue;
1282             }
1283             if (smaller && smaller->fEndT < test->fStartT) {
1284                 continue;
1285             }
1286             smaller = test;
1287         } while ((test = test->fNext));
1288         if (!smaller) {
1289             return;
1290         }
1291         smallLimit = smaller->fEndT;
1292         // find next larger span
1293         SkTSpan* prior = nullptr;
1294         SkTSpan* larger = nullptr;
1295         SkTSpan* largerPrior = nullptr;
1296         test = fCoincident;
1297         do {
1298             if (test->fStartT < smaller->fEndT) {
1299                 continue;
1300             }
1301             SkOPASSERT(test->fStartT != smaller->fEndT);
1302             if (larger && larger->fStartT < test->fStartT) {
1303                 continue;
1304             }
1305             largerPrior = prior;
1306             larger = test;
1307         } while ((void) (prior = test), (test = test->fNext));
1308         if (!larger) {
1309             continue;
1310         }
1311         // check middle t value to see if it is coincident as well
1312         double midT = (smaller->fEndT + larger->fStartT) / 2;
1313         SkDPoint midPt = fCurve.ptAtT(midT);
1314         SkTCoincident coin;
1315         coin.setPerp(fCurve, midT, midPt, sect2->fCurve);
1316         if (coin.isMatch()) {
1317             smaller->fEndT = larger->fEndT;
1318             smaller->fCoinEnd = larger->fCoinEnd;
1319             if (largerPrior) {
1320                 largerPrior->fNext = larger->fNext;
1321                 largerPrior->validate();
1322             } else {
1323                 fCoincident = larger->fNext;
1324             }
1325         }
1326     } while (true);
1327 }
1328 
prev(SkTSpan * span) const1329 SkTSpan* SkTSect::prev(
1330         SkTSpan* span) const {
1331     SkTSpan* result = nullptr;
1332     SkTSpan* test = fHead;
1333     while (span != test) {
1334         result = test;
1335         test = test->fNext;
1336         SkASSERT(test);
1337     }
1338     return result;
1339 }
1340 
recoverCollapsed()1341 void SkTSect::recoverCollapsed() {
1342     SkTSpan* deleted = fDeleted;
1343     while (deleted) {
1344         SkTSpan* delNext = deleted->fNext;
1345         if (deleted->fCollapsed) {
1346             SkTSpan** spanPtr = &fHead;
1347             while (*spanPtr && (*spanPtr)->fEndT <= deleted->fStartT) {
1348                 spanPtr = &(*spanPtr)->fNext;
1349             }
1350             deleted->fNext = *spanPtr;
1351             *spanPtr = deleted;
1352         }
1353         deleted = delNext;
1354     }
1355 }
1356 
removeAllBut(const SkTSpan * keep,SkTSpan * span,SkTSect * opp)1357 void SkTSect::removeAllBut(const SkTSpan* keep,
1358         SkTSpan* span, SkTSect* opp) {
1359     const SkTSpanBounded* testBounded = span->fBounded;
1360     while (testBounded) {
1361         SkTSpan* bounded = testBounded->fBounded;
1362         const SkTSpanBounded* next = testBounded->fNext;
1363         // may have been deleted when opp did 'remove all but'
1364         if (bounded != keep && !bounded->fDeleted) {
1365             SkAssertResult(SkDEBUGCODE(!) span->removeBounded(bounded));
1366             if (bounded->removeBounded(span)) {
1367                 opp->removeSpan(bounded);
1368             }
1369         }
1370         testBounded = next;
1371     }
1372     SkASSERT(!span->fDeleted);
1373     SkASSERT(span->findOppSpan(keep));
1374     SkASSERT(keep->findOppSpan(span));
1375 }
1376 
removeByPerpendicular(SkTSect * opp)1377 bool SkTSect::removeByPerpendicular(SkTSect* opp) {
1378     SkTSpan* test = fHead;
1379     SkTSpan* next;
1380     do {
1381         next = test->fNext;
1382         if (test->fCoinStart.perpT() < 0 || test->fCoinEnd.perpT() < 0) {
1383             continue;
1384         }
1385         SkDVector startV = test->fCoinStart.perpPt() - test->pointFirst();
1386         SkDVector endV = test->fCoinEnd.perpPt() - test->pointLast();
1387 #if DEBUG_T_SECT
1388         SkDebugf("%s startV=(%1.9g,%1.9g) endV=(%1.9g,%1.9g) dot=%1.9g\n", __FUNCTION__,
1389                 startV.fX, startV.fY, endV.fX, endV.fY, startV.dot(endV));
1390 #endif
1391         if (startV.dot(endV) <= 0) {
1392             continue;
1393         }
1394         if (!this->removeSpans(test, opp)) {
1395             return false;
1396         }
1397     } while ((test = next));
1398     return true;
1399 }
1400 
removeCoincident(SkTSpan * span,bool isBetween)1401 bool SkTSect::removeCoincident(SkTSpan* span, bool isBetween) {
1402     if (!this->unlinkSpan(span)) {
1403         return false;
1404     }
1405     if (isBetween || between(0, span->fCoinStart.perpT(), 1)) {
1406         --fActiveCount;
1407         span->fNext = fCoincident;
1408         fCoincident = span;
1409     } else {
1410         this->markSpanGone(span);
1411     }
1412     return true;
1413 }
1414 
removedEndCheck(SkTSpan * span)1415 void SkTSect::removedEndCheck(SkTSpan* span) {
1416     if (!span->fStartT) {
1417         fRemovedStartT = true;
1418     }
1419     if (1 == span->fEndT) {
1420         fRemovedEndT = true;
1421     }
1422 }
1423 
removeSpan(SkTSpan * span)1424 bool SkTSect::removeSpan(SkTSpan* span) {\
1425     this->removedEndCheck(span);
1426     if (!this->unlinkSpan(span)) {
1427         return false;
1428     }
1429     return this->markSpanGone(span);
1430 }
1431 
removeSpanRange(SkTSpan * first,SkTSpan * last)1432 void SkTSect::removeSpanRange(SkTSpan* first,
1433         SkTSpan* last) {
1434     if (first == last) {
1435         return;
1436     }
1437     SkTSpan* span = first;
1438     SkASSERT(span);
1439     SkTSpan* final = last->fNext;
1440     SkTSpan* next = span->fNext;
1441     while ((span = next) && span != final) {
1442         next = span->fNext;
1443         this->markSpanGone(span);
1444     }
1445     if (final) {
1446         final->fPrev = first;
1447     }
1448     first->fNext = final;
1449     // world may not be ready for validation here
1450     first->validate();
1451 }
1452 
removeSpans(SkTSpan * span,SkTSect * opp)1453 bool SkTSect::removeSpans(SkTSpan* span,
1454         SkTSect* opp) {
1455     SkTSpanBounded* bounded = span->fBounded;
1456     while (bounded) {
1457         SkTSpan* spanBounded = bounded->fBounded;
1458         SkTSpanBounded* next = bounded->fNext;
1459         if (span->removeBounded(spanBounded)) {  // shuffles last into position 0
1460             this->removeSpan(span);
1461         }
1462         if (spanBounded->removeBounded(span)) {
1463             opp->removeSpan(spanBounded);
1464         }
1465         if (span->fDeleted && opp->hasBounded(span)) {
1466             return false;
1467         }
1468         bounded = next;
1469     }
1470     return true;
1471 }
1472 
spanAtT(double t,SkTSpan ** priorSpan)1473 SkTSpan* SkTSect::spanAtT(double t,
1474         SkTSpan** priorSpan) {
1475     SkTSpan* test = fHead;
1476     SkTSpan* prev = nullptr;
1477     while (test && test->fEndT < t) {
1478         prev = test;
1479         test = test->fNext;
1480     }
1481     *priorSpan = prev;
1482     return test && test->fStartT <= t ? test : nullptr;
1483 }
1484 
tail()1485 SkTSpan* SkTSect::tail() {
1486     SkTSpan* result = fHead;
1487     SkTSpan* next = fHead;
1488     int safetyNet = 100000;
1489     while ((next = next->fNext)) {
1490         if (!--safetyNet) {
1491             return nullptr;
1492         }
1493         if (next->fEndT > result->fEndT) {
1494             result = next;
1495         }
1496     }
1497     return result;
1498 }
1499 
1500 /* Each span has a range of opposite spans it intersects. After the span is split in two,
1501     adjust the range to its new size */
1502 
trim(SkTSpan * span,SkTSect * opp)1503 bool SkTSect::trim(SkTSpan* span,
1504         SkTSect* opp) {
1505     FAIL_IF(!span->initBounds(fCurve));
1506     const SkTSpanBounded* testBounded = span->fBounded;
1507     while (testBounded) {
1508         SkTSpan* test = testBounded->fBounded;
1509         const SkTSpanBounded* next = testBounded->fNext;
1510         int oppSects, sects = this->intersects(span, opp, test, &oppSects);
1511         if (sects >= 1) {
1512             if (oppSects == 2) {
1513                 test->initBounds(opp->fCurve);
1514                 opp->removeAllBut(span, test, this);
1515             }
1516             if (sects == 2) {
1517                 span->initBounds(fCurve);
1518                 this->removeAllBut(test, span, opp);
1519                 return true;
1520             }
1521         } else {
1522             if (span->removeBounded(test)) {
1523                 this->removeSpan(span);
1524             }
1525             if (test->removeBounded(span)) {
1526                 opp->removeSpan(test);
1527             }
1528         }
1529         testBounded = next;
1530     }
1531     return true;
1532 }
1533 
unlinkSpan(SkTSpan * span)1534 bool SkTSect::unlinkSpan(SkTSpan* span) {
1535     SkTSpan* prev = span->fPrev;
1536     SkTSpan* next = span->fNext;
1537     if (prev) {
1538         prev->fNext = next;
1539         if (next) {
1540             next->fPrev = prev;
1541             if (next->fStartT > next->fEndT) {
1542                 return false;
1543             }
1544             // world may not be ready for validate here
1545             next->validate();
1546         }
1547     } else {
1548         fHead = next;
1549         if (next) {
1550             next->fPrev = nullptr;
1551         }
1552     }
1553     return true;
1554 }
1555 
updateBounded(SkTSpan * first,SkTSpan * last,SkTSpan * oppFirst)1556 bool SkTSect::updateBounded(SkTSpan* first,
1557         SkTSpan* last, SkTSpan* oppFirst) {
1558     SkTSpan* test = first;
1559     const SkTSpan* final = last->next();
1560     bool deleteSpan = false;
1561     do {
1562         deleteSpan |= test->removeAllBounded();
1563     } while ((test = test->fNext) != final && test);
1564     first->fBounded = nullptr;
1565     first->addBounded(oppFirst, &fHeap);
1566     // cannot call validate until remove span range is called
1567     return deleteSpan;
1568 }
1569 
validate() const1570 void SkTSect::validate() const {
1571 #if DEBUG_VALIDATE
1572     int count = 0;
1573     double last = 0;
1574     if (fHead) {
1575         const SkTSpan* span = fHead;
1576         SkASSERT(!span->fPrev);
1577         const SkTSpan* next;
1578         do {
1579             span->validate();
1580             SkASSERT(span->fStartT >= last);
1581             last = span->fEndT;
1582             ++count;
1583             next = span->fNext;
1584             SkASSERT(next != span);
1585         } while ((span = next) != nullptr);
1586     }
1587     SkASSERT(count == fActiveCount);
1588 #endif
1589 #if DEBUG_T_SECT
1590     SkASSERT(fActiveCount <= fDebugAllocatedCount);
1591     int deletedCount = 0;
1592     const SkTSpan* deleted = fDeleted;
1593     while (deleted) {
1594         ++deletedCount;
1595         deleted = deleted->fNext;
1596     }
1597     const SkTSpan* coincident = fCoincident;
1598     while (coincident) {
1599         ++deletedCount;
1600         coincident = coincident->fNext;
1601     }
1602     SkASSERT(fActiveCount + deletedCount == fDebugAllocatedCount);
1603 #endif
1604 }
1605 
validateBounded() const1606 void SkTSect::validateBounded() const {
1607 #if DEBUG_VALIDATE
1608     if (!fHead) {
1609         return;
1610     }
1611     const SkTSpan* span = fHead;
1612     do {
1613         span->validateBounded();
1614     } while ((span = span->fNext) != nullptr);
1615 #endif
1616 }
1617 
EndsEqual(const SkTSect * sect1,const SkTSect * sect2,SkIntersections * intersections)1618 int SkTSect::EndsEqual(const SkTSect* sect1,
1619         const SkTSect* sect2, SkIntersections* intersections) {
1620     int zeroOneSet = 0;
1621     if (sect1->fCurve[0] == sect2->fCurve[0]) {
1622         zeroOneSet |= kZeroS1Set | kZeroS2Set;
1623         intersections->insert(0, 0, sect1->fCurve[0]);
1624     }
1625     if (sect1->fCurve[0] == sect2->pointLast()) {
1626         zeroOneSet |= kZeroS1Set | kOneS2Set;
1627         intersections->insert(0, 1, sect1->fCurve[0]);
1628     }
1629     if (sect1->pointLast() == sect2->fCurve[0]) {
1630         zeroOneSet |= kOneS1Set | kZeroS2Set;
1631         intersections->insert(1, 0, sect1->pointLast());
1632     }
1633     if (sect1->pointLast() == sect2->pointLast()) {
1634         zeroOneSet |= kOneS1Set | kOneS2Set;
1635             intersections->insert(1, 1, sect1->pointLast());
1636     }
1637     // check for zero
1638     if (!(zeroOneSet & (kZeroS1Set | kZeroS2Set))
1639             && sect1->fCurve[0].approximatelyEqual(sect2->fCurve[0])) {
1640         zeroOneSet |= kZeroS1Set | kZeroS2Set;
1641         intersections->insertNear(0, 0, sect1->fCurve[0], sect2->fCurve[0]);
1642     }
1643     if (!(zeroOneSet & (kZeroS1Set | kOneS2Set))
1644             && sect1->fCurve[0].approximatelyEqual(sect2->pointLast())) {
1645         zeroOneSet |= kZeroS1Set | kOneS2Set;
1646         intersections->insertNear(0, 1, sect1->fCurve[0], sect2->pointLast());
1647     }
1648     // check for one
1649     if (!(zeroOneSet & (kOneS1Set | kZeroS2Set))
1650             && sect1->pointLast().approximatelyEqual(sect2->fCurve[0])) {
1651         zeroOneSet |= kOneS1Set | kZeroS2Set;
1652         intersections->insertNear(1, 0, sect1->pointLast(), sect2->fCurve[0]);
1653     }
1654     if (!(zeroOneSet & (kOneS1Set | kOneS2Set))
1655             && sect1->pointLast().approximatelyEqual(sect2->pointLast())) {
1656         zeroOneSet |= kOneS1Set | kOneS2Set;
1657         intersections->insertNear(1, 1, sect1->pointLast(), sect2->pointLast());
1658     }
1659     return zeroOneSet;
1660 }
1661 
1662 struct SkClosestRecord {
operator <SkClosestRecord1663     bool operator<(const SkClosestRecord& rh) const {
1664         return fClosest < rh.fClosest;
1665     }
1666 
addIntersectionSkClosestRecord1667     void addIntersection(SkIntersections* intersections) const {
1668         double r1t = fC1Index ? fC1Span->endT() : fC1Span->startT();
1669         double r2t = fC2Index ? fC2Span->endT() : fC2Span->startT();
1670         intersections->insert(r1t, r2t, fC1Span->part()[fC1Index]);
1671     }
1672 
findEndSkClosestRecord1673     void findEnd(const SkTSpan* span1, const SkTSpan* span2,
1674             int c1Index, int c2Index) {
1675         const SkTCurve& c1 = span1->part();
1676         const SkTCurve& c2 = span2->part();
1677         if (!c1[c1Index].approximatelyEqual(c2[c2Index])) {
1678             return;
1679         }
1680         double dist = c1[c1Index].distanceSquared(c2[c2Index]);
1681         if (fClosest < dist) {
1682             return;
1683         }
1684         fC1Span = span1;
1685         fC2Span = span2;
1686         fC1StartT = span1->startT();
1687         fC1EndT = span1->endT();
1688         fC2StartT = span2->startT();
1689         fC2EndT = span2->endT();
1690         fC1Index = c1Index;
1691         fC2Index = c2Index;
1692         fClosest = dist;
1693     }
1694 
matesWithSkClosestRecord1695     bool matesWith(const SkClosestRecord& mate  SkDEBUGPARAMS(SkIntersections* i)) const {
1696         SkOPOBJASSERT(i, fC1Span == mate.fC1Span || fC1Span->endT() <= mate.fC1Span->startT()
1697                 || mate.fC1Span->endT() <= fC1Span->startT());
1698         SkOPOBJASSERT(i, fC2Span == mate.fC2Span || fC2Span->endT() <= mate.fC2Span->startT()
1699                 || mate.fC2Span->endT() <= fC2Span->startT());
1700         return fC1Span == mate.fC1Span || fC1Span->endT() == mate.fC1Span->startT()
1701                 || fC1Span->startT() == mate.fC1Span->endT()
1702                 || fC2Span == mate.fC2Span
1703                 || fC2Span->endT() == mate.fC2Span->startT()
1704                 || fC2Span->startT() == mate.fC2Span->endT();
1705     }
1706 
mergeSkClosestRecord1707     void merge(const SkClosestRecord& mate) {
1708         fC1Span = mate.fC1Span;
1709         fC2Span = mate.fC2Span;
1710         fClosest = mate.fClosest;
1711         fC1Index = mate.fC1Index;
1712         fC2Index = mate.fC2Index;
1713     }
1714 
resetSkClosestRecord1715     void reset() {
1716         fClosest = FLT_MAX;
1717         SkDEBUGCODE(fC1Span = nullptr);
1718         SkDEBUGCODE(fC2Span = nullptr);
1719         SkDEBUGCODE(fC1Index = fC2Index = -1);
1720     }
1721 
updateSkClosestRecord1722     void update(const SkClosestRecord& mate) {
1723         fC1StartT = std::min(fC1StartT, mate.fC1StartT);
1724         fC1EndT = std::max(fC1EndT, mate.fC1EndT);
1725         fC2StartT = std::min(fC2StartT, mate.fC2StartT);
1726         fC2EndT = std::max(fC2EndT, mate.fC2EndT);
1727     }
1728 
1729     const SkTSpan* fC1Span;
1730     const SkTSpan* fC2Span;
1731     double fC1StartT;
1732     double fC1EndT;
1733     double fC2StartT;
1734     double fC2EndT;
1735     double fClosest;
1736     int fC1Index;
1737     int fC2Index;
1738 };
1739 
1740 struct SkClosestSect {
SkClosestSectSkClosestSect1741     SkClosestSect()
1742         : fUsed(0) {
1743         fClosest.push_back().reset();
1744     }
1745 
findSkClosestSect1746     bool find(const SkTSpan* span1, const SkTSpan* span2
1747             SkDEBUGPARAMS(SkIntersections* i)) {
1748         SkClosestRecord* record = &fClosest[fUsed];
1749         record->findEnd(span1, span2, 0, 0);
1750         record->findEnd(span1, span2, 0, span2->part().pointLast());
1751         record->findEnd(span1, span2, span1->part().pointLast(), 0);
1752         record->findEnd(span1, span2, span1->part().pointLast(), span2->part().pointLast());
1753         if (record->fClosest == FLT_MAX) {
1754             return false;
1755         }
1756         for (int index = 0; index < fUsed; ++index) {
1757             SkClosestRecord* test = &fClosest[index];
1758             if (test->matesWith(*record  SkDEBUGPARAMS(i))) {
1759                 if (test->fClosest > record->fClosest) {
1760                     test->merge(*record);
1761                 }
1762                 test->update(*record);
1763                 record->reset();
1764                 return false;
1765             }
1766         }
1767         ++fUsed;
1768         fClosest.push_back().reset();
1769         return true;
1770     }
1771 
finishSkClosestSect1772     void finish(SkIntersections* intersections) const {
1773         STArray<SkDCubic::kMaxIntersections * 3,
1774                 const SkClosestRecord*, true> closestPtrs;
1775         for (int index = 0; index < fUsed; ++index) {
1776             closestPtrs.push_back(&fClosest[index]);
1777         }
1778         SkTQSort<const SkClosestRecord>(closestPtrs.begin(), closestPtrs.end());
1779         for (int index = 0; index < fUsed; ++index) {
1780             const SkClosestRecord* test = closestPtrs[index];
1781             test->addIntersection(intersections);
1782         }
1783     }
1784 
1785     // this is oversized so that an extra records can merge into final one
1786     STArray<SkDCubic::kMaxIntersections * 2, SkClosestRecord, true> fClosest;
1787     int fUsed;
1788 };
1789 
1790 // returns true if the rect is too small to consider
1791 
BinarySearch(SkTSect * sect1,SkTSect * sect2,SkIntersections * intersections)1792 void SkTSect::BinarySearch(SkTSect* sect1,
1793         SkTSect* sect2, SkIntersections* intersections) {
1794 #if DEBUG_T_SECT_DUMP > 1
1795     gDumpTSectNum = 0;
1796 #endif
1797     SkDEBUGCODE(sect1->fOppSect = sect2);
1798     SkDEBUGCODE(sect2->fOppSect = sect1);
1799     intersections->reset();
1800     intersections->setMax(sect1->fCurve.maxIntersections() + 4);  // give extra for slop
1801     SkTSpan* span1 = sect1->fHead;
1802     SkTSpan* span2 = sect2->fHead;
1803     int oppSect, sect = sect1->intersects(span1, sect2, span2, &oppSect);
1804 //    SkASSERT(between(0, sect, 2));
1805     if (!sect) {
1806         return;
1807     }
1808     if (sect == 2 && oppSect == 2) {
1809         (void) EndsEqual(sect1, sect2, intersections);
1810         return;
1811     }
1812     span1->addBounded(span2, &sect1->fHeap);
1813     span2->addBounded(span1, &sect2->fHeap);
1814     const int kMaxCoinLoopCount = 8;
1815     int coinLoopCount = kMaxCoinLoopCount;
1816     double start1s SK_INIT_TO_AVOID_WARNING;
1817     double start1e SK_INIT_TO_AVOID_WARNING;
1818     do {
1819         // find the largest bounds
1820         SkTSpan* largest1 = sect1->boundsMax();
1821         if (!largest1) {
1822             if (sect1->fHung) {
1823                 return;
1824             }
1825             break;
1826         }
1827         SkTSpan* largest2 = sect2->boundsMax();
1828         // split it
1829         if (!largest2 || (largest1 && (largest1->fBoundsMax > largest2->fBoundsMax
1830                 || (!largest1->fCollapsed && largest2->fCollapsed)))) {
1831             if (sect2->fHung) {
1832                 return;
1833             }
1834             if (largest1->fCollapsed) {
1835                 break;
1836             }
1837             sect1->resetRemovedEnds();
1838             sect2->resetRemovedEnds();
1839             // trim parts that don't intersect the opposite
1840             SkTSpan* half1 = sect1->addOne();
1841             SkDEBUGCODE(half1->debugSetGlobalState(sect1->globalState()));
1842             if (!half1->split(largest1, &sect1->fHeap)) {
1843                 break;
1844             }
1845             if (!sect1->trim(largest1, sect2)) {
1846                 SkOPOBJASSERT(intersections, 0);
1847                 return;
1848             }
1849             if (!sect1->trim(half1, sect2)) {
1850                 SkOPOBJASSERT(intersections, 0);
1851                 return;
1852             }
1853         } else {
1854             if (largest2->fCollapsed) {
1855                 break;
1856             }
1857             sect1->resetRemovedEnds();
1858             sect2->resetRemovedEnds();
1859             // trim parts that don't intersect the opposite
1860             SkTSpan* half2 = sect2->addOne();
1861             SkDEBUGCODE(half2->debugSetGlobalState(sect2->globalState()));
1862             if (!half2->split(largest2, &sect2->fHeap)) {
1863                 break;
1864             }
1865             if (!sect2->trim(largest2, sect1)) {
1866                 SkOPOBJASSERT(intersections, 0);
1867                 return;
1868             }
1869             if (!sect2->trim(half2, sect1)) {
1870                 SkOPOBJASSERT(intersections, 0);
1871                 return;
1872             }
1873         }
1874         sect1->validate();
1875         sect2->validate();
1876 #if DEBUG_T_SECT_LOOP_COUNT
1877         intersections->debugBumpLoopCount(SkIntersections::kIterations_DebugLoop);
1878 #endif
1879         // if there are 9 or more continuous spans on both sects, suspect coincidence
1880         if (sect1->fActiveCount >= COINCIDENT_SPAN_COUNT
1881                 && sect2->fActiveCount >= COINCIDENT_SPAN_COUNT) {
1882             if (coinLoopCount == kMaxCoinLoopCount) {
1883                 start1s = sect1->fHead->fStartT;
1884                 start1e = sect1->tail()->fEndT;
1885             }
1886             if (!sect1->coincidentCheck(sect2)) {
1887                 return;
1888             }
1889             sect1->validate();
1890             sect2->validate();
1891 #if DEBUG_T_SECT_LOOP_COUNT
1892             intersections->debugBumpLoopCount(SkIntersections::kCoinCheck_DebugLoop);
1893 #endif
1894             if (!--coinLoopCount && sect1->fHead && sect2->fHead) {
1895                 /* All known working cases resolve in two tries. Sadly, cubicConicTests[0]
1896                    gets stuck in a loop. It adds an extension to allow a coincident end
1897                    perpendicular to track its intersection in the opposite curve. However,
1898                    the bounding box of the extension does not intersect the original curve,
1899                    so the extension is discarded, only to be added again the next time around. */
1900                 sect1->coincidentForce(sect2, start1s, start1e);
1901                 sect1->validate();
1902                 sect2->validate();
1903             }
1904         }
1905         if (sect1->fActiveCount >= COINCIDENT_SPAN_COUNT
1906                 && sect2->fActiveCount >= COINCIDENT_SPAN_COUNT) {
1907             if (!sect1->fHead) {
1908                 return;
1909             }
1910             sect1->computePerpendiculars(sect2, sect1->fHead, sect1->tail());
1911             if (!sect2->fHead) {
1912                 return;
1913             }
1914             sect2->computePerpendiculars(sect1, sect2->fHead, sect2->tail());
1915             if (!sect1->removeByPerpendicular(sect2)) {
1916                 return;
1917             }
1918             sect1->validate();
1919             sect2->validate();
1920 #if DEBUG_T_SECT_LOOP_COUNT
1921             intersections->debugBumpLoopCount(SkIntersections::kComputePerp_DebugLoop);
1922 #endif
1923             if (sect1->collapsed() > sect1->fCurve.maxIntersections()) {
1924                 break;
1925             }
1926         }
1927 #if DEBUG_T_SECT_DUMP
1928         sect1->dumpBoth(sect2);
1929 #endif
1930         if (!sect1->fHead || !sect2->fHead) {
1931             break;
1932         }
1933     } while (true);
1934     SkTSpan* coincident = sect1->fCoincident;
1935     if (coincident) {
1936         // if there is more than one coincident span, check loosely to see if they should be joined
1937         if (coincident->fNext) {
1938             sect1->mergeCoincidence(sect2);
1939             coincident = sect1->fCoincident;
1940         }
1941         SkASSERT(sect2->fCoincident);  // courtesy check : coincidence only looks at sect 1
1942         do {
1943             if (!coincident) {
1944                 return;
1945             }
1946             if (!coincident->fCoinStart.isMatch()) {
1947                 continue;
1948             }
1949             if (!coincident->fCoinEnd.isMatch()) {
1950                 continue;
1951             }
1952             double perpT = coincident->fCoinStart.perpT();
1953             if (perpT < 0) {
1954                 return;
1955             }
1956             int index = intersections->insertCoincident(coincident->fStartT,
1957                     perpT, coincident->pointFirst());
1958             if ((intersections->insertCoincident(coincident->fEndT,
1959                     coincident->fCoinEnd.perpT(),
1960                     coincident->pointLast()) < 0) && index >= 0) {
1961                 intersections->clearCoincidence(index);
1962             }
1963         } while ((coincident = coincident->fNext));
1964     }
1965     int zeroOneSet = EndsEqual(sect1, sect2, intersections);
1966 //    if (!sect1->fHead || !sect2->fHead) {
1967         // if the final iteration contains an end (0 or 1),
1968         if (sect1->fRemovedStartT && !(zeroOneSet & kZeroS1Set)) {
1969             SkTCoincident perp;   // intersect perpendicular with opposite curve
1970             perp.setPerp(sect1->fCurve, 0, sect1->fCurve[0], sect2->fCurve);
1971             if (perp.isMatch()) {
1972                 intersections->insert(0, perp.perpT(), perp.perpPt());
1973             }
1974         }
1975         if (sect1->fRemovedEndT && !(zeroOneSet & kOneS1Set)) {
1976             SkTCoincident perp;
1977             perp.setPerp(sect1->fCurve, 1, sect1->pointLast(), sect2->fCurve);
1978             if (perp.isMatch()) {
1979                 intersections->insert(1, perp.perpT(), perp.perpPt());
1980             }
1981         }
1982         if (sect2->fRemovedStartT && !(zeroOneSet & kZeroS2Set)) {
1983             SkTCoincident perp;
1984             perp.setPerp(sect2->fCurve, 0, sect2->fCurve[0], sect1->fCurve);
1985             if (perp.isMatch()) {
1986                 intersections->insert(perp.perpT(), 0, perp.perpPt());
1987             }
1988         }
1989         if (sect2->fRemovedEndT && !(zeroOneSet & kOneS2Set)) {
1990             SkTCoincident perp;
1991             perp.setPerp(sect2->fCurve, 1, sect2->pointLast(), sect1->fCurve);
1992             if (perp.isMatch()) {
1993                 intersections->insert(perp.perpT(), 1, perp.perpPt());
1994             }
1995         }
1996 //    }
1997     if (!sect1->fHead || !sect2->fHead) {
1998         return;
1999     }
2000     sect1->recoverCollapsed();
2001     sect2->recoverCollapsed();
2002     SkTSpan* result1 = sect1->fHead;
2003     // check heads and tails for zero and ones and insert them if we haven't already done so
2004     const SkTSpan* head1 = result1;
2005     if (!(zeroOneSet & kZeroS1Set) && approximately_less_than_zero(head1->fStartT)) {
2006         const SkDPoint& start1 = sect1->fCurve[0];
2007         if (head1->isBounded()) {
2008             double t = head1->closestBoundedT(start1);
2009             if (sect2->fCurve.ptAtT(t).approximatelyEqual(start1)) {
2010                 intersections->insert(0, t, start1);
2011             }
2012         }
2013     }
2014     const SkTSpan* head2 = sect2->fHead;
2015     if (!(zeroOneSet & kZeroS2Set) && approximately_less_than_zero(head2->fStartT)) {
2016         const SkDPoint& start2 = sect2->fCurve[0];
2017         if (head2->isBounded()) {
2018             double t = head2->closestBoundedT(start2);
2019             if (sect1->fCurve.ptAtT(t).approximatelyEqual(start2)) {
2020                 intersections->insert(t, 0, start2);
2021             }
2022         }
2023     }
2024     if (!(zeroOneSet & kOneS1Set)) {
2025         const SkTSpan* tail1 = sect1->tail();
2026         if (!tail1) {
2027             return;
2028         }
2029         if (approximately_greater_than_one(tail1->fEndT)) {
2030             const SkDPoint& end1 = sect1->pointLast();
2031             if (tail1->isBounded()) {
2032                 double t = tail1->closestBoundedT(end1);
2033                 if (sect2->fCurve.ptAtT(t).approximatelyEqual(end1)) {
2034                     intersections->insert(1, t, end1);
2035                 }
2036             }
2037         }
2038     }
2039     if (!(zeroOneSet & kOneS2Set)) {
2040         const SkTSpan* tail2 = sect2->tail();
2041         if (!tail2) {
2042             return;
2043         }
2044         if (approximately_greater_than_one(tail2->fEndT)) {
2045             const SkDPoint& end2 = sect2->pointLast();
2046             if (tail2->isBounded()) {
2047                 double t = tail2->closestBoundedT(end2);
2048                 if (sect1->fCurve.ptAtT(t).approximatelyEqual(end2)) {
2049                     intersections->insert(t, 1, end2);
2050                 }
2051             }
2052         }
2053     }
2054     SkClosestSect closest;
2055     do {
2056         while (result1 && result1->fCoinStart.isMatch() && result1->fCoinEnd.isMatch()) {
2057             result1 = result1->fNext;
2058         }
2059         if (!result1) {
2060             break;
2061         }
2062         SkTSpan* result2 = sect2->fHead;
2063         while (result2) {
2064             closest.find(result1, result2  SkDEBUGPARAMS(intersections));
2065             result2 = result2->fNext;
2066         }
2067     } while ((result1 = result1->fNext));
2068     closest.finish(intersections);
2069     // if there is more than one intersection and it isn't already coincident, check
2070     int last = intersections->used() - 1;
2071     for (int index = 0; index < last; ) {
2072         if (intersections->isCoincident(index) && intersections->isCoincident(index + 1)) {
2073             ++index;
2074             continue;
2075         }
2076         double midT = ((*intersections)[0][index] + (*intersections)[0][index + 1]) / 2;
2077         SkDPoint midPt = sect1->fCurve.ptAtT(midT);
2078         // intersect perpendicular with opposite curve
2079         SkTCoincident perp;
2080         perp.setPerp(sect1->fCurve, midT, midPt, sect2->fCurve);
2081         if (!perp.isMatch()) {
2082             ++index;
2083             continue;
2084         }
2085         if (intersections->isCoincident(index)) {
2086             intersections->removeOne(index);
2087             --last;
2088         } else if (intersections->isCoincident(index + 1)) {
2089             intersections->removeOne(index + 1);
2090             --last;
2091         } else {
2092             intersections->setCoincident(index++);
2093         }
2094         intersections->setCoincident(index);
2095     }
2096     SkOPOBJASSERT(intersections, intersections->used() <= sect1->fCurve.maxIntersections());
2097 }
2098 
intersect(const SkDQuad & q1,const SkDQuad & q2)2099 int SkIntersections::intersect(const SkDQuad& q1, const SkDQuad& q2) {
2100     SkTQuad quad1(q1);
2101     SkTQuad quad2(q2);
2102     SkTSect sect1(quad1  SkDEBUGPARAMS(globalState())  PATH_OPS_DEBUG_T_SECT_PARAMS(1));
2103     SkTSect sect2(quad2  SkDEBUGPARAMS(globalState())  PATH_OPS_DEBUG_T_SECT_PARAMS(2));
2104     SkTSect::BinarySearch(&sect1, &sect2, this);
2105     return used();
2106 }
2107 
intersect(const SkDConic & c,const SkDQuad & q)2108 int SkIntersections::intersect(const SkDConic& c, const SkDQuad& q) {
2109     SkTConic conic(c);
2110     SkTQuad quad(q);
2111     SkTSect sect1(conic  SkDEBUGPARAMS(globalState())  PATH_OPS_DEBUG_T_SECT_PARAMS(1));
2112     SkTSect sect2(quad  SkDEBUGPARAMS(globalState())  PATH_OPS_DEBUG_T_SECT_PARAMS(2));
2113     SkTSect::BinarySearch(&sect1, &sect2, this);
2114     return used();
2115 }
2116 
intersect(const SkDConic & c1,const SkDConic & c2)2117 int SkIntersections::intersect(const SkDConic& c1, const SkDConic& c2) {
2118     SkTConic conic1(c1);
2119     SkTConic conic2(c2);
2120     SkTSect sect1(conic1  SkDEBUGPARAMS(globalState())  PATH_OPS_DEBUG_T_SECT_PARAMS(1));
2121     SkTSect sect2(conic2  SkDEBUGPARAMS(globalState())  PATH_OPS_DEBUG_T_SECT_PARAMS(2));
2122     SkTSect::BinarySearch(&sect1, &sect2, this);
2123     return used();
2124 }
2125 
intersect(const SkDCubic & c,const SkDQuad & q)2126 int SkIntersections::intersect(const SkDCubic& c, const SkDQuad& q) {
2127     SkTCubic cubic(c);
2128     SkTQuad quad(q);
2129     SkTSect sect1(cubic  SkDEBUGPARAMS(globalState())  PATH_OPS_DEBUG_T_SECT_PARAMS(1));
2130     SkTSect sect2(quad  SkDEBUGPARAMS(globalState())  PATH_OPS_DEBUG_T_SECT_PARAMS(2));
2131     SkTSect::BinarySearch(&sect1, &sect2, this);
2132     return used();
2133 }
2134 
intersect(const SkDCubic & cu,const SkDConic & co)2135 int SkIntersections::intersect(const SkDCubic& cu, const SkDConic& co) {
2136     SkTCubic cubic(cu);
2137     SkTConic conic(co);
2138     SkTSect sect1(cubic  SkDEBUGPARAMS(globalState())  PATH_OPS_DEBUG_T_SECT_PARAMS(1));
2139     SkTSect sect2(conic  SkDEBUGPARAMS(globalState())  PATH_OPS_DEBUG_T_SECT_PARAMS(2));
2140     SkTSect::BinarySearch(&sect1, &sect2, this);
2141     return used();
2142 
2143 }
2144 
intersect(const SkDCubic & c1,const SkDCubic & c2)2145 int SkIntersections::intersect(const SkDCubic& c1, const SkDCubic& c2) {
2146     SkTCubic cubic1(c1);
2147     SkTCubic cubic2(c2);
2148     SkTSect sect1(cubic1  SkDEBUGPARAMS(globalState())  PATH_OPS_DEBUG_T_SECT_PARAMS(1));
2149     SkTSect sect2(cubic2   SkDEBUGPARAMS(globalState())  PATH_OPS_DEBUG_T_SECT_PARAMS(2));
2150     SkTSect::BinarySearch(&sect1, &sect2, this);
2151     return used();
2152 }
2153