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