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