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