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