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