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