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