26#define COINCIDENT_SPAN_COUNT 9
33 int used = i.intersectRay(c2, perp);
35 if (used == 0 || used == 3) {
43 double distSq = (fPerpPt - cPt).lengthSquared();
44 double dist2Sq = (i.pt(1) - cPt).lengthSquared();
45 if (dist2Sq < distSq) {
51 SkDebugf(
"setPerp t=%1.9g cPt=(%1.9g,%1.9g) %s oppT=%1.9g fPerpPt=(%1.9g,%1.9g)\n",
66 bounded->
fNext = fBounded;
74 result->fStartT = prior ? prior->fEndT : 0;
93void SkTSect::addForPerp(
SkTSpan* span,
double t) {
94 if (!span->hasOppT(t)) {
96 SkTSpan* opp = this->spanAtT(t, &priorSpan);
98 opp = this->addFollowing(priorSpan);
100 SkDebugf(
"%s priorSpan=%d t=%1.9g opp=%d\n", __FUNCTION__, priorSpan ?
101 priorSpan->debugID() : -1, t, opp->debugID());
106 SkDebugf(
"%s addBounded span=%d opp=%d\n", __FUNCTION__, priorSpan ?
107 priorSpan->debugID() : -1, opp->debugID());
114 span->validatePerpT(t);
120 double closest = DBL_MAX;
122 while (testBounded) {
124 double startDist =
test->pointFirst().distanceSquared(pt);
125 if (closest > startDist) {
129 double endDist =
test->pointLast().distanceSquared(pt);
130 if (closest > endDist) {
134 testBounded = testBounded->
fNext;
142bool SkTSpan::debugIsBefore(
const SkTSpan* span)
const {
148 }
while ((work = work->fNext));
156 if (
between(work->fStartT, t, work->fEndT)) {
159 }
while ((work = work->fNext));
175 bounded = bounded->
fNext;
185int SkTSpan::hullCheck(
const SkTSpan* opp,
186 bool*
start,
bool* oppStart) {
202 return ptsInCommon ? 1 : -1;
205 return ((
int) ptsInCommon) << 1;
213 bool*
start,
bool* oppStart) {
217 int hullSect = this->hullCheck(opp,
start, oppStart);
221 hullSect = opp->hullCheck(
this, oppStart,
start);
229 fPrev = fNext =
nullptr;
244 fBoundsMax = std::max(fBounds.
width(), fBounds.
height());
253 return fBounds.
valid();
257 int result = this->linearIntersects(*span->fPart);
262 result = span->linearIntersects(*fPart);
269 return fabs(len.fX) > fabs(len.fY)
274int SkTSpan::linearIntersects(
const SkTCurve& q2)
const {
279 for (
int outer = 0; outer < this->
pointCount() - 1; ++outer) {
280 for (
int inner = outer + 1; inner < this->
pointCount(); ++inner) {
281 double test = ((*fPart)[outer] - (*fPart)[inner]).lengthSquared();
292 double origX = (*fPart)[
start].fX;
293 double origY = (*fPart)[
start].fY;
294 double adj = (*fPart)[
end].fX - origX;
295 double opp = (*fPart)[
end].fY - origY;
296 double maxPart = std::max(fabs(adj), fabs(opp));
299 double dx = q2[n].fY - origY;
300 double dy = q2[n].fX - origX;
301 double maxVal = std::max(maxPart, std::max(fabs(dx), fabs(dy)));
302 double test = (q2[n].fY - origY) * adj - (q2[n].fX - origX) * opp;
321 bool*
start,
bool* oppStart,
bool* ptsInCommon) {
322 if (opp->
pointFirst() == this->pointFirst()) {
323 *
start = *oppStart =
true;
324 }
else if (opp->
pointFirst() == this->pointLast()) {
327 }
else if (opp->
pointLast() == this->pointFirst()) {
330 }
else if (opp->
pointLast() == this->pointLast()) {
331 *
start = *oppStart =
false;
333 *ptsInCommon =
false;
337 const SkDPoint* otherPts[4], * oppOtherPts[4];
340 fPart->
otherPts(baseIndex, otherPts);
343 for (
int o1 = 0; o1 < this->
pointCount() - 1; ++o1) {
345 for (
int o2 = 0; o2 < opp->
pointCount() - 1; ++o2) {
347 if (
v2.dot(v1) >= 0) {
355SkTSpan* SkTSpan::oppT(
double t)
const {
362 bounded = bounded->
fNext;
368 bool deleteSpan =
false;
373 bounded = bounded->
fNext;
380 bool foundStart =
false;
381 bool foundEnd =
false;
389 bounded = bounded->
fNext;
391 if (!foundStart || !foundEnd) {
406 fBounded = boundedNext;
407 return fBounded ==
nullptr;
411 bounded = boundedNext;
420 if (fStartT == fEndT) {
425 if (work->fStartT == work->fEndT) {
426 work->fCollapsed =
true;
431 fIsLinear = work->fIsLinear;
432 fIsLine = work->fIsLine;
443 bounded = bounded->
fNext;
448 bounded = bounded->
fNext;
453void SkTSpan::validate()
const {
457 SkASSERT(fNext ==
nullptr || fNext != fPrev);
458 SkASSERT(fNext ==
nullptr ||
this == fNext->fPrev);
459 SkASSERT(fPrev ==
nullptr ||
this == fPrev->fNext);
460 this->validateBounded();
468 SkASSERT(fBounded || fCollapsed == 0xFF);
471 validatePerpT(fCoinStart.
perpT());
472 validatePerpPt(fCoinStart.
perpT(), fCoinStart.
perpPt());
475 validatePerpT(fCoinEnd.
perpT());
476 validatePerpPt(fCoinEnd.
perpT(), fCoinEnd.
perpPt());
482void SkTSpan::validateBounded()
const {
485 while (testBounded) {
489 SkASSERT(((this->debugID() ^ overlap->debugID()) & 1) == 1);
490 SkASSERT(overlap->findOppSpan(
this));
492 testBounded = testBounded->
fNext;
497void SkTSpan::validatePerpT(
double oppT)
const {
499 while (testBounded) {
504 testBounded = testBounded->
fNext;
509void SkTSpan::validatePerpPt(
double t,
const SkDPoint& pt)
const {
510 SkASSERT(fDebugSect->fOppSect->fCurve.ptAtT(t) == pt);
518 , fCoincident(nullptr)
527 this->resetRemovedEnds();
528 fHead = this->addOne();
529 SkDEBUGCODE(fHead->debugSetGlobalState(debugGlobalState));
541 ++fDebugAllocatedCount;
551 result->debugInit(fCurve, fHeap);
552 result->fCoinStart.debugInit();
553 result->fCoinEnd.debugInit();
555 result->fBounds.debugInit();
562bool SkTSect::binarySearchCoin(
SkTSect* sect2,
double tStart,
563 double tStep,
double* resultT,
double* oppT,
SkTSpan** oppFirst) {
565 double result = work.fStartT = work.fEndT = tStart;
570 bool contained =
false;
571 bool down = tStep < 0;
572 const SkTCurve& opp = sect2->fCurve;
575 work.fStartT += tStep;
581 if (work.fCollapsed) {
588 work.fCoinStart.
setPerp(fCurve, work.fStartT, last, opp);
589 if (work.fCoinStart.
isMatch()) {
591 work.validatePerpPt(work.fCoinStart.
perpT(), work.fCoinStart.
perpPt());
593 double oppTTest = work.fCoinStart.
perpT();
594 if (sect2->fHead->
contains(oppTTest)) {
596 oppPt = work.fCoinStart.
perpPt();
598 if (down ? result <= work.fStartT : result >= work.fStartT) {
633 bool lCollapsed = largest->fCollapsed;
634 int safetyNet = 10000;
640 bool tCollapsed =
test->fCollapsed;
641 if ((lCollapsed && !tCollapsed) || (lCollapsed == tCollapsed &&
642 largest->fBoundsMax <
test->fBoundsMax)) {
644 lCollapsed =
test->fCollapsed;
650bool SkTSect::coincidentCheck(
SkTSect* sect2) {
657 int consecutive = this->countConsecutiveSpans(first, &last);
664 this->computePerpendiculars(sect2, first, last);
670 bool success = this->extractCoincident(sect2, coinStart, last, &coinStart);
674 }
while (coinStart && !last->fDeleted);
675 if (!fHead || !sect2->fHead) {
681 }
while ((first =
next));
685void SkTSect::coincidentForce(
SkTSect* sect2,
686 double start1s,
double start1e) {
689 SkTSpan* oppFirst = sect2->fHead;
690 SkTSpan* oppLast = sect2->tail();
691 if (!last || !oppLast) {
694 bool deleteEmptySpans = this->updateBounded(first, last, oppFirst);
695 deleteEmptySpans |= sect2->updateBounded(oppFirst, oppLast, first);
696 this->removeSpanRange(first, last);
697 sect2->removeSpanRange(oppFirst, oppLast);
698 first->fStartT = start1s;
699 first->fEndT = start1e;
701 first->fCoinStart.
setPerp(fCurve, start1s, fCurve[0], sect2->fCurve);
702 first->fCoinEnd.
setPerp(fCurve, start1e, this->pointLast(), sect2->fCurve);
703 bool oppMatched = first->fCoinStart.
perpT() < first->fCoinEnd.
perpT();
704 double oppStartT = first->fCoinStart.
perpT() == -1 ? 0 : std::max(0., first->fCoinStart.
perpT());
705 double oppEndT = first->fCoinEnd.
perpT() == -1 ? 1 : std::min(1., first->fCoinEnd.
perpT());
708 swap(oppStartT, oppEndT);
710 oppFirst->fStartT = oppStartT;
711 oppFirst->fEndT = oppEndT;
713 this->removeCoincident(first,
false);
714 sect2->removeCoincident(oppFirst,
true);
715 if (deleteEmptySpans) {
716 this->deleteEmptySpans();
717 sect2->deleteEmptySpans();
721bool SkTSect::coincidentHasT(
double t) {
732int SkTSect::collapsed()
const {
736 if (
test->fCollapsed) {
744void SkTSect::computePerpendiculars(
SkTSect* sect2,
749 const SkTCurve& opp = sect2->fCurve;
753 if (!work->fHasPerp && !work->fCollapsed) {
755 work->fCoinStart = prior->fCoinEnd;
759 if (work->fCoinStart.
isMatch()) {
760 double perpT = work->fCoinStart.
perpT();
761 if (sect2->coincidentHasT(perpT)) {
762 work->fCoinStart.
init();
764 sect2->addForPerp(work, perpT);
768 if (work->fCoinEnd.
isMatch()) {
769 double perpT = work->fCoinEnd.
perpT();
770 if (sect2->coincidentHasT(perpT)) {
771 work->fCoinEnd.
init();
773 sect2->addForPerp(work, perpT);
776 work->fHasPerp =
true;
787int SkTSect::countConsecutiveSpans(
SkTSpan* first,
796 if (
next->fStartT > last->fEndT) {
806bool SkTSect::hasBounded(
const SkTSpan* span)
const {
812 if (
test->findOppSpan(span)) {
819bool SkTSect::deleteEmptySpans() {
822 int safetyHatch = 1000;
825 if (!
test->fBounded) {
826 if (!this->removeSpan(
test)) {
830 if (--safetyHatch < 0) {
837bool SkTSect::extractCoincident(
841 first = findCoincidentRun(first, &last);
842 if (!first || !last) {
847 double startT = first->fStartT;
854 bool oppMatched = first->fCoinStart.
perpT() < first->fCoinEnd.
perpT();
858 if (prev && prev->fEndT == startT
859 && this->binarySearchCoin(sect2, startT, prev->fStartT - startT, &coinStart,
860 &oppStartT, &oppFirst)
861 && prev->fStartT < coinStart && coinStart < startT
862 && (cutFirst = prev->oppT(oppStartT))) {
864 first = this->addSplitAt(prev, coinStart);
867 if (oppFirst->fStartT < oppStartT && oppStartT < oppFirst->fEndT) {
868 SkTSpan* oppHalf = sect2->addSplitAt(oppFirst, oppStartT);
883 SkDEBUGCODE(oppStartT = oppMatched ? oppFirst->fStartT : oppFirst->fEndT);
891 if (!this->globalState() || !this->globalState()->debugSkipAssert()) {
892 oppEndT = oppMatched ? oppLast->fEndT : oppLast->fStartT;
897 swap(oppFirst, oppLast);
898 swap(oppStartT, oppEndT);
901 SkASSERT(coinStart == first->fStartT);
916 bool deleteEmptySpans = this->updateBounded(first, last, oppFirst);
917 deleteEmptySpans |= sect2->updateBounded(oppFirst, oppLast, first);
918 this->removeSpanRange(first, last);
919 sect2->removeSpanRange(oppFirst, oppLast);
920 first->fEndT = last->fEndT;
922 first->fCoinStart.
setPerp(fCurve, first->fStartT, first->
pointFirst(), sect2->fCurve);
923 first->fCoinEnd.
setPerp(fCurve, first->fEndT, first->
pointLast(), sect2->fCurve);
924 oppStartT = first->fCoinStart.
perpT();
925 oppEndT = first->fCoinEnd.
perpT();
929 swap(oppStartT, oppEndT);
931 oppFirst->fStartT = oppStartT;
932 oppFirst->fEndT = oppEndT;
935 this->validateBounded();
936 sect2->validateBounded();
938 if (!this->removeCoincident(first,
false)) {
941 if (!sect2->removeCoincident(oppFirst,
true)) {
944 if (deleteEmptySpans) {
945 if (!this->deleteEmptySpans() || !sect2->deleteEmptySpans()) {
952 *
result = last && !last->fDeleted && fHead && sect2->fHead ? last :
nullptr;
956SkTSpan* SkTSect::findCoincidentRun(
959 SkTSpan* lastCandidate =
nullptr;
963 if (work->fCoinStart.
isMatch()) {
965 work->validatePerpT(work->fCoinStart.
perpT());
966 work->validatePerpPt(work->fCoinStart.
perpT(), work->fCoinStart.
perpPt());
969 if (!work->fCoinEnd.
isMatch()) {
972 lastCandidate = work;
976 }
else if (first && work->fCollapsed) {
977 *lastPtr = lastCandidate;
980 lastCandidate =
nullptr;
983 if (work == *lastPtr) {
992 *lastPtr = lastCandidate;
997int SkTSect::intersects(
SkTSpan* span,
999 SkTSpan* oppSpan,
int* oppResult) {
1000 bool spanStart, oppStart;
1001 int hullResult = span->
hullsIntersect(oppSpan, &spanStart, &oppStart);
1002 if (hullResult >= 0) {
1003 if (hullResult == 2) {
1004 if (!span->fBounded || !span->fBounded->
fNext) {
1007 span->fEndT = span->fStartT;
1009 span->fStartT = span->fEndT;
1014 if (!oppSpan->fBounded || !oppSpan->fBounded->
fNext) {
1015 if (oppSpan->fBounded && oppSpan->fBounded->
fBounded != span) {
1019 oppSpan->fEndT = oppSpan->fStartT;
1021 oppSpan->fStartT = oppSpan->fEndT;
1032 if (span->fIsLine && oppSpan->fIsLine) {
1034 int sects = this->linesIntersect(span, opp, oppSpan, &i);
1036 return *oppResult = 1;
1041 this->removedEndCheck(span);
1042 span->fStartT = span->fEndT = i[0][0];
1043 opp->removedEndCheck(oppSpan);
1044 oppSpan->fStartT = oppSpan->fEndT = i[1][0];
1045 return *oppResult = 2;
1047 if (span->fIsLinear || oppSpan->fIsLinear) {
1050 return *oppResult = 1;
1053template<
typename SkTCurve>
1062 thisPerp.
fPts[1] = thisLine.
fPts[1];
1065 for (
int pIndex = 0; pIndex < perpRayI.
used(); ++pIndex) {
1070 thisPerp.
fPts[0] = thisLine.
fPts[0];
1072 for (
int pIndex = 0; pIndex < perpRayI.
used(); ++pIndex) {
1082int SkTSect::linesIntersect(
SkTSpan* span,
1090 double bestDistSq = DBL_MAX;
1091 if (!thisRayI.intersectRay(opp->fCurve, thisLine)) {
1094 if (!oppRayI.intersectRay(this->fCurve, oppLine)) {
1098 if (thisRayI.used() > 1) {
1100 for (
int tIndex = 0; tIndex < thisRayI.used(); ++tIndex) {
1101 for (
int lIndex = 0; lIndex < (
int) std::size(thisLine.
fPts); ++lIndex) {
1105 if (ptMatches == 2 ||
is_parallel(thisLine, opp->fCurve)) {
1109 if (oppRayI.used() > 1) {
1111 for (
int oIndex = 0; oIndex < oppRayI.used(); ++oIndex) {
1112 for (
int lIndex = 0; lIndex < (
int) std::size(oppLine.
fPts); ++lIndex) {
1113 ptMatches += oppRayI.pt(oIndex).approximatelyEqual(oppLine.
fPts[lIndex]);
1116 if (ptMatches == 2||
is_parallel(oppLine, this->fCurve)) {
1122 double closest = DBL_MAX;
1125 for (
int index = 0; index < oppRayI.used(); ++index) {
1126 if (!
roughly_between(span->fStartT, oppRayI[0][index], span->fEndT)) {
1129 for (
int oIndex = 0; oIndex < thisRayI.used(); ++oIndex) {
1130 if (!
roughly_between(oppSpan->fStartT, thisRayI[0][oIndex], oppSpan->fEndT)) {
1133 double distSq = thisRayI.pt(index).distanceSquared(oppRayI.pt(oIndex));
1134 if (closest > distSq) {
1137 oppCloseIndex = oIndex;
1141 if (closest == DBL_MAX) {
1144 const SkDPoint& oppIPt = thisRayI.pt(oppCloseIndex);
1145 const SkDPoint& iPt = oppRayI.pt(closeIndex);
1146 if (
between(span->fStartT, oppRayI[0][closeIndex], span->fEndT)
1147 &&
between(oppSpan->fStartT, thisRayI[0][oppCloseIndex], oppSpan->fEndT)
1149 i->
merge(oppRayI, closeIndex, thisRayI, oppCloseIndex);
1153 if (bestDistSq < distSq || ++loopCount > 5) {
1156 bestDistSq = distSq;
1157 double oppStart = oppRayI[0][closeIndex];
1158 thisLine[0] = fCurve.
ptAtT(oppStart);
1159 thisLine[1] = thisLine[0] + fCurve.
dxdyAtT(oppStart);
1160 if (!thisRayI.intersectRay(opp->fCurve, thisLine)) {
1163 double start = thisRayI[0][oppCloseIndex];
1166 if (!oppRayI.intersectRay(this->fCurve, oppLine)) {
1174 double tStart = oCoinS.
perpT();
1175 double tEnd = oCoinE.
perpT();
1176 bool swap = tStart > tEnd;
1181 tStart = std::max(tStart, span->fStartT);
1182 tEnd = std::min(tEnd, span->fEndT);
1183 if (tStart > tEnd) {
1187 if (tStart == span->fStartT) {
1196 if (tEnd == span->fEndT) {
1205 if (perpS.
dot(perpE) >= 0) {
1209 double workT = tStart;
1210 double tStep = tEnd - tStart;
1218 workPt = fCurve.
ptAtT(workT);
1219 coinW.
setPerp(fCurve, workT, workPt, opp->fCurve);
1220 double perpT = coinW.
perpT();
1221 if (coinW.
isMatch() ? !
between(oppSpan->fStartT, perpT, oppSpan->fEndT) : perpT < 0) {
1225 if ((perpS.
dot(perpW) >= 0) == (tStep < 0)) {
1232 double oppTTest = coinW.
perpT();
1233 if (!opp->fHead->
contains(oppTTest)) {
1237 i->
insert(workT, oppTTest, workPt);
1241bool SkTSect::markSpanGone(
SkTSpan* span) {
1242 if (--fActiveCount < 0) {
1245 span->fNext = fDeleted;
1248 span->fDeleted =
true;
1252bool SkTSect::matchedDirection(
double t,
const SkTSect* sect2,
1256 return dxdy.
dot(dxdy2) >= 0;
1259void SkTSect::matchedDirCheck(
double t,
const SkTSect* sect2,
1260 double t2,
bool* calcMatched,
bool* oppMatched)
const {
1262 SkASSERT(*oppMatched == this->matchedDirection(t, sect2, t2));
1264 *oppMatched = this->matchedDirection(t, sect2, t2);
1265 *calcMatched =
true;
1269void SkTSect::mergeCoincidence(
SkTSect* sect2) {
1270 double smallLimit = 0;
1279 if (
test->fStartT < smallLimit) {
1282 if (smaller && smaller->fEndT <
test->fStartT) {
1290 smallLimit = smaller->fEndT;
1294 SkTSpan* largerPrior =
nullptr;
1297 if (
test->fStartT < smaller->fEndT) {
1301 if (larger && larger->fStartT <
test->fStartT) {
1304 largerPrior = prior;
1311 double midT = (smaller->fEndT + larger->fStartT) / 2;
1314 coin.
setPerp(fCurve, midT, midPt, sect2->fCurve);
1316 smaller->fEndT = larger->fEndT;
1317 smaller->fCoinEnd = larger->fCoinEnd;
1319 largerPrior->fNext = larger->fNext;
1320 largerPrior->validate();
1322 fCoincident = larger->fNext;
1332 while (span !=
test) {
1340void SkTSect::recoverCollapsed() {
1343 SkTSpan* delNext = deleted->fNext;
1344 if (deleted->fCollapsed) {
1346 while (*spanPtr && (*spanPtr)->fEndT <= deleted->fStartT) {
1347 spanPtr = &(*spanPtr)->fNext;
1349 deleted->fNext = *spanPtr;
1356void SkTSect::removeAllBut(
const SkTSpan* keep,
1359 while (testBounded) {
1363 if (bounded != keep && !bounded->fDeleted) {
1366 opp->removeSpan(bounded);
1376bool SkTSect::removeByPerpendicular(
SkTSect* opp) {
1381 if (
test->fCoinStart.perpT() < 0 ||
test->fCoinEnd.perpT() < 0) {
1387 SkDebugf(
"%s startV=(%1.9g,%1.9g) endV=(%1.9g,%1.9g) dot=%1.9g\n", __FUNCTION__,
1388 startV.
fX, startV.
fY, endV.
fX, endV.
fY, startV.
dot(endV));
1390 if (startV.
dot(endV) <= 0) {
1393 if (!this->removeSpans(
test, opp)) {
1400bool SkTSect::removeCoincident(
SkTSpan* span,
bool isBetween) {
1401 if (!this->unlinkSpan(span)) {
1404 if (isBetween ||
between(0, span->fCoinStart.
perpT(), 1)) {
1406 span->fNext = fCoincident;
1409 this->markSpanGone(span);
1414void SkTSect::removedEndCheck(
SkTSpan* span) {
1415 if (!span->fStartT) {
1416 fRemovedStartT =
true;
1418 if (1 == span->fEndT) {
1419 fRemovedEndT =
true;
1423bool SkTSect::removeSpan(
SkTSpan* span) {\
1424 this->removedEndCheck(span);
1425 if (!this->unlinkSpan(span)) {
1428 return this->markSpanGone(span);
1431void SkTSect::removeSpanRange(
SkTSpan* first,
1433 if (first == last) {
1440 while ((span =
next) && span !=
final) {
1442 this->markSpanGone(span);
1445 final->fPrev = first;
1447 first->fNext =
final;
1452bool SkTSect::removeSpans(
SkTSpan* span,
1459 this->removeSpan(span);
1462 opp->removeSpan(spanBounded);
1464 if (span->fDeleted && opp->hasBounded(span)) {
1472SkTSpan* SkTSect::spanAtT(
double t,
1487 int safetyNet = 100000;
1502bool SkTSect::trim(
SkTSpan* span,
1506 while (testBounded) {
1509 int oppSects, sects = this->intersects(span, opp,
test, &oppSects);
1511 if (oppSects == 2) {
1512 test->initBounds(opp->fCurve);
1513 opp->removeAllBut(span,
test,
this);
1517 this->removeAllBut(
test, span, opp);
1522 this->removeSpan(span);
1524 if (
test->removeBounded(span)) {
1525 opp->removeSpan(
test);
1533bool SkTSect::unlinkSpan(
SkTSpan* span) {
1549 next->fPrev =
nullptr;
1555bool SkTSect::updateBounded(
SkTSpan* first,
1559 bool deleteSpan =
false;
1561 deleteSpan |=
test->removeAllBounded();
1563 first->fBounded =
nullptr;
1569void SkTSect::validate()
const {
1584 }
while ((span =
next) !=
nullptr);
1589 SkASSERT(fActiveCount <= fDebugAllocatedCount);
1590 int deletedCount = 0;
1591 const SkTSpan* deleted = fDeleted;
1594 deleted = deleted->fNext;
1601 SkASSERT(fActiveCount + deletedCount == fDebugAllocatedCount);
1605void SkTSect::validateBounded()
const {
1612 span->validateBounded();
1613 }
while ((span = span->fNext) !=
nullptr);
1617int SkTSect::EndsEqual(
const SkTSect* sect1,
1620 if (sect1->fCurve[0] == sect2->fCurve[0]) {
1621 zeroOneSet |= kZeroS1Set | kZeroS2Set;
1622 intersections->
insert(0, 0, sect1->fCurve[0]);
1624 if (sect1->fCurve[0] == sect2->pointLast()) {
1625 zeroOneSet |= kZeroS1Set | kOneS2Set;
1626 intersections->
insert(0, 1, sect1->fCurve[0]);
1628 if (sect1->pointLast() == sect2->fCurve[0]) {
1629 zeroOneSet |= kOneS1Set | kZeroS2Set;
1630 intersections->
insert(1, 0, sect1->pointLast());
1632 if (sect1->pointLast() == sect2->pointLast()) {
1633 zeroOneSet |= kOneS1Set | kOneS2Set;
1634 intersections->
insert(1, 1, sect1->pointLast());
1637 if (!(zeroOneSet & (kZeroS1Set | kZeroS2Set))
1638 && sect1->fCurve[0].approximatelyEqual(sect2->fCurve[0])) {
1639 zeroOneSet |= kZeroS1Set | kZeroS2Set;
1640 intersections->
insertNear(0, 0, sect1->fCurve[0], sect2->fCurve[0]);
1642 if (!(zeroOneSet & (kZeroS1Set | kOneS2Set))
1643 && sect1->fCurve[0].approximatelyEqual(sect2->pointLast())) {
1644 zeroOneSet |= kZeroS1Set | kOneS2Set;
1645 intersections->
insertNear(0, 1, sect1->fCurve[0], sect2->pointLast());
1648 if (!(zeroOneSet & (kOneS1Set | kZeroS2Set))
1650 zeroOneSet |= kOneS1Set | kZeroS2Set;
1651 intersections->
insertNear(1, 0, sect1->pointLast(), sect2->fCurve[0]);
1653 if (!(zeroOneSet & (kOneS1Set | kOneS2Set))
1655 zeroOneSet |= kOneS1Set | kOneS2Set;
1656 intersections->
insertNear(1, 1, sect1->pointLast(), sect2->pointLast());
1673 int c1Index,
int c2Index) {
1676 if (!c1[c1Index].approximatelyEqual(c2[c2Index])) {
1679 double dist = c1[c1Index].distanceSquared(c2[c2Index]);
1748 record->
findEnd(span1, span2, 0, 0);
1755 for (
int index = 0; index <
fUsed; ++index) {
1759 test->merge(*record);
1761 test->update(*record);
1774 for (
int index = 0; index <
fUsed; ++index) {
1777 SkTQSort<const SkClosestRecord>(closestPtrs.
begin(), closestPtrs.
end());
1778 for (
int index = 0; index <
fUsed; ++index) {
1780 test->addIntersection(intersections);
1793#if DEBUG_T_SECT_DUMP > 1
1798 intersections->
reset();
1800 SkTSpan* span1 = sect1->fHead;
1801 SkTSpan* span2 = sect2->fHead;
1802 int oppSect, sect = sect1->intersects(span1, sect2, span2, &oppSect);
1807 if (sect == 2 && oppSect == 2) {
1808 (void) EndsEqual(sect1, sect2, intersections);
1813 const int kMaxCoinLoopCount = 8;
1814 int coinLoopCount = kMaxCoinLoopCount;
1819 SkTSpan* largest1 = sect1->boundsMax();
1826 SkTSpan* largest2 = sect2->boundsMax();
1828 if (!largest2 || (largest1 && (largest1->fBoundsMax > largest2->fBoundsMax
1829 || (!largest1->fCollapsed && largest2->fCollapsed)))) {
1833 if (largest1->fCollapsed) {
1836 sect1->resetRemovedEnds();
1837 sect2->resetRemovedEnds();
1839 SkTSpan* half1 = sect1->addOne();
1840 SkDEBUGCODE(half1->debugSetGlobalState(sect1->globalState()));
1841 if (!half1->
split(largest1, §1->fHeap)) {
1844 if (!sect1->trim(largest1, sect2)) {
1848 if (!sect1->trim(half1, sect2)) {
1853 if (largest2->fCollapsed) {
1856 sect1->resetRemovedEnds();
1857 sect2->resetRemovedEnds();
1859 SkTSpan* half2 = sect2->addOne();
1860 SkDEBUGCODE(half2->debugSetGlobalState(sect2->globalState()));
1861 if (!half2->split(largest2, §2->fHeap)) {
1864 if (!sect2->trim(largest2, sect1)) {
1868 if (!sect2->trim(half2, sect1)) {
1875#if DEBUG_T_SECT_LOOP_COUNT
1881 if (coinLoopCount == kMaxCoinLoopCount) {
1882 start1s = sect1->fHead->fStartT;
1883 start1e = sect1->tail()->fEndT;
1885 if (!sect1->coincidentCheck(sect2)) {
1890#if DEBUG_T_SECT_LOOP_COUNT
1893 if (!--coinLoopCount && sect1->fHead && sect2->fHead) {
1899 sect1->coincidentForce(sect2, start1s, start1e);
1906 if (!sect1->fHead) {
1909 sect1->computePerpendiculars(sect2, sect1->fHead, sect1->tail());
1910 if (!sect2->fHead) {
1913 sect2->computePerpendiculars(sect1, sect2->fHead, sect2->tail());
1914 if (!sect1->removeByPerpendicular(sect2)) {
1919#if DEBUG_T_SECT_LOOP_COUNT
1926#if DEBUG_T_SECT_DUMP
1929 if (!sect1->fHead || !sect2->fHead) {
1937 sect1->mergeCoincidence(sect2);
1951 double perpT =
coincident->fCoinStart.perpT();
1959 coincident->pointLast()) < 0) && index >= 0) {
1964 int zeroOneSet = EndsEqual(sect1, sect2, intersections);
1967 if (sect1->fRemovedStartT && !(zeroOneSet & kZeroS1Set)) {
1969 perp.
setPerp(sect1->fCurve, 0, sect1->fCurve[0], sect2->fCurve);
1974 if (sect1->fRemovedEndT && !(zeroOneSet & kOneS1Set)) {
1976 perp.
setPerp(sect1->fCurve, 1, sect1->pointLast(), sect2->fCurve);
1981 if (sect2->fRemovedStartT && !(zeroOneSet & kZeroS2Set)) {
1983 perp.
setPerp(sect2->fCurve, 0, sect2->fCurve[0], sect1->fCurve);
1988 if (sect2->fRemovedEndT && !(zeroOneSet & kOneS2Set)) {
1990 perp.
setPerp(sect2->fCurve, 1, sect2->pointLast(), sect1->fCurve);
1996 if (!sect1->fHead || !sect2->fHead) {
1999 sect1->recoverCollapsed();
2000 sect2->recoverCollapsed();
2001 SkTSpan* result1 = sect1->fHead;
2003 const SkTSpan* head1 = result1;
2005 const SkDPoint& start1 = sect1->fCurve[0];
2009 intersections->
insert(0, t, start1);
2013 const SkTSpan* head2 = sect2->fHead;
2015 const SkDPoint& start2 = sect2->fCurve[0];
2019 intersections->
insert(t, 0, start2);
2023 if (!(zeroOneSet & kOneS1Set)) {
2024 const SkTSpan* tail1 = sect1->tail();
2029 const SkDPoint& end1 = sect1->pointLast();
2033 intersections->
insert(1, t, end1);
2038 if (!(zeroOneSet & kOneS2Set)) {
2039 const SkTSpan* tail2 = sect2->tail();
2044 const SkDPoint& end2 = sect2->pointLast();
2048 intersections->
insert(t, 1, end2);
2055 while (result1 && result1->fCoinStart.
isMatch() && result1->fCoinEnd.
isMatch()) {
2056 result1 = result1->fNext;
2061 SkTSpan* result2 = sect2->fHead;
2064 result2 = result2->fNext;
2066 }
while ((result1 = result1->fNext));
2067 closest.
finish(intersections);
2069 int last = intersections->
used() - 1;
2070 for (
int index = 0; index < last; ) {
2075 double midT = ((*intersections)[0][index] + (*intersections)[0][index + 1]) / 2;
2079 perp.
setPerp(sect1->fCurve, midT, midPt, sect2->fCurve);
static bool coincident(const SkPoint &a, const SkPoint &b)
static float next(float f)
static float prev(float f)
#define SkAssertResult(cond)
void SK_SPI SkDebugf(const char format[],...) SK_PRINTF_LIKE(1
static bool between(SkScalar a, SkScalar b, SkScalar c)
#define SK_INIT_TO_AVOID_WARNING
#define SkDEBUGPARAMS(...)
#define SkDEBUGRELEASE(a, b)
#define PATH_OPS_DEBUG_T_SECT_PARAMS(...)
#define PATH_OPS_DEBUG_T_SECT_CODE(...)
#define COINCIDENT_SPAN_COUNT
static bool is_parallel(const SkDLine &thisLine, const SkTCurve &opp)
static bool SkDoubleIsNaN(double x)
bool approximately_less_than_zero(double x)
bool precisely_zero(double x)
bool roughly_between(double a, double b, double c)
bool approximately_greater_than_one(double x)
#define SkOPOBJASSERT(obj, cond)
bool precisely_between(double a, double b, double c)
bool precisely_zero_when_compared_to(double x, double y)
bool approximately_zero_when_compared_to(double x, double y)
static int sign(SkScalar x)
void swap(sk_sp< T > &a, sk_sp< T > &b)
static constexpr bool SkToBool(const T &x)
Type::kYUV Type::kRGBA() int(0.7 *637)
auto make(Ctor &&ctor) -> decltype(ctor(nullptr))
void merge(const SkIntersections &, int, const SkIntersections &, int)
int intersectRay(const SkDLine &, const SkDLine &)
int insert(double one, double two, const SkDPoint &pt)
int intersect(const SkDLine &, const SkDLine &)
void removeOne(int index)
const SkDPoint & pt(int index) const
void insertNear(double one, double two, const SkDPoint &pt1, const SkDPoint &pt2)
int insertCoincident(double one, double two, const SkDPoint &pt)
void debugBumpLoopCount(DebugLoop)
void setCoincident(int index)
bool isCoincident(int index)
void clearCoincidence(int index)
const SkDPoint & perpPt() const
void setPerp(const SkTCurve &c1, double t, const SkDPoint &cPt, const SkTCurve &)
virtual void otherPts(int oddMan, const SkDPoint *endPt[2]) const =0
virtual SkDPoint ptAtT(double t) const =0
virtual bool collapsed() const =0
virtual bool controlsInside() const =0
virtual int pointCount() const =0
virtual void subDivide(double t1, double t2, SkTCurve *curve) const =0
virtual bool hullIntersects(const SkDQuad &, bool *isLinear) const =0
virtual bool IsConic() const =0
virtual int maxIntersections() const =0
virtual SkDVector dxdyAtT(double t) const =0
virtual int pointLast() const =0
SkTSect(const SkTCurve &c SkDEBUGPARAMS(SkOpGlobalState *) PATH_OPS_DEBUG_T_SECT_PARAMS(int id))
static void BinarySearch(SkTSect *sect1, SkTSect *sect2, SkIntersections *intersections)
void dumpBoth(SkTSect *) const
bool initBounds(const SkTCurve &)
const SkTSect * debugOpp() const
int hullsIntersect(SkTSpan *span, bool *start, bool *oppStart)
bool contains(double t) const
const SkTSpan * next() const
void addBounded(SkTSpan *, SkArenaAlloc *)
const SkDPoint & pointLast() const
const SkDPoint & pointFirst() const
void init(const SkTCurve &)
SkTSpan * findOppT(double t) const
const SkTCurve & part() const
bool removeBounded(const SkTSpan *opp)
bool linearsIntersect(SkTSpan *span)
void resetBounds(const SkTCurve &curve)
bool split(SkTSpan *work, SkArenaAlloc *heap)
bool splitAt(SkTSpan *work, double t, SkArenaAlloc *heap)
double closestBoundedT(const SkDPoint &pt) const
SkTSpan * findOppSpan(const SkTSpan *opp) const
double linearT(const SkDPoint &) const
bool onlyEndPointsInCommon(const SkTSpan *opp, bool *start, bool *oppStart, bool *ptsInCommon)
skia_private::AutoTArray< sk_sp< SkImageFilter > > filters TypedMatrix matrix TypedMatrix matrix SkScalar dx
bool matesWith(const SkClosestRecord &mate SkDEBUGPARAMS(SkIntersections *i)) const
bool operator<(const SkClosestRecord &rh) const
void addIntersection(SkIntersections *intersections) const
void findEnd(const SkTSpan *span1, const SkTSpan *span2, int c1Index, int c2Index)
void update(const SkClosestRecord &mate)
void merge(const SkClosestRecord &mate)
bool find(const SkTSpan *span1, const SkTSpan *span2 SkDEBUGPARAMS(SkIntersections *i))
void finish(SkIntersections *intersections) const
STArray< SkDCubic::kMaxIntersections *2, SkClosestRecord, true > fClosest
static const int kMaxIntersections
double distanceSquared(const SkDPoint &a) const
bool approximatelyEqual(const SkDPoint &a) const
bool intersects(const SkDRect &r) const
void setBounds(const SkDConic &curve)
double dot(const SkDVector &a) const
static sk_sp< SkShader > linear(sk_sp< SkShader > shader)