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