/* * Copyright 2014 Google Inc. * * Use of this source code is governed by a BSD-style license that can be * found in the LICENSE file. */ #ifndef SkPathOpsTSect_DEFINED #define SkPathOpsTSect_DEFINED #include "SkArenaAlloc.h" #include "SkIntersections.h" #include "SkMacros.h" #include "SkPathOpsBounds.h" #include "SkPathOpsRect.h" #include "SkTSort.h" #include #ifdef SK_DEBUG typedef uint8_t SkOpDebugBool; #else typedef bool SkOpDebugBool; #endif static inline bool SkDoubleIsNaN(double x) { return x != x; } /* TCurve and OppCurve are one of { SkDQuadratic, SkDConic, SkDCubic } */ template class SkTCoincident { public: SkTCoincident() { this->init(); } void debugInit() { #ifdef SK_DEBUG this->fPerpPt.fX = this->fPerpPt.fY = SK_ScalarNaN; this->fPerpT = SK_ScalarNaN; this->fMatch = 0xFF; #endif } char dumpIsCoincidentStr() const; void dump() const; bool isMatch() const { SkASSERT(!!fMatch == fMatch); return SkToBool(fMatch); } void init() { fPerpT = -1; fMatch = false; fPerpPt.fX = fPerpPt.fY = SK_ScalarNaN; } void markCoincident() { if (!fMatch) { fPerpT = -1; } fMatch = true; } const SkDPoint& perpPt() const { return fPerpPt; } double perpT() const { return fPerpT; } void setPerp(const TCurve& c1, double t, const SkDPoint& cPt, const OppCurve& ); private: SkDPoint fPerpPt; double fPerpT; // perpendicular intersection on opposite curve SkOpDebugBool fMatch; }; template class SkTSect; template class SkTSpan; template struct SkTSpanBounded { SkTSpan* fBounded; SkTSpanBounded* fNext; }; /* Curve is either TCurve or SkDCubic */ template class SkTSpan { public: void addBounded(SkTSpan* , SkArenaAlloc* ); double closestBoundedT(const SkDPoint& pt) const; bool contains(double t) const; void debugInit() { TCurve dummy; dummy.debugInit(); init(dummy); initBounds(dummy); fCoinStart.init(); fCoinEnd.init(); } const SkTSect* debugOpp() const; #ifdef SK_DEBUG void debugSetGlobalState(SkOpGlobalState* state) { fDebugGlobalState = state; } #endif const SkTSpan* debugSpan(int ) const; const SkTSpan* debugT(double t) const; #ifdef SK_DEBUG bool debugIsBefore(const SkTSpan* span) const; #endif void dump() const; void dumpAll() const; void dumpBounded(int id) const; void dumpBounds() const; void dumpCoin() const; double endT() const { return fEndT; } SkTSpan* findOppSpan(const SkTSpan* opp) const; SkTSpan* findOppT(double t) const { SkTSpan* result = oppT(t); SkOPASSERT(result); return result; } SkDEBUGCODE(SkOpGlobalState* globalState() const { return fDebugGlobalState; }) bool hasOppT(double t) const { return SkToBool(oppT(t)); } int hullsIntersect(SkTSpan* span, bool* start, bool* oppStart); void init(const TCurve& ); bool initBounds(const TCurve& ); bool isBounded() const { return fBounded != nullptr; } bool linearsIntersect(SkTSpan* span); double linearT(const SkDPoint& ) const; void markCoincident() { fCoinStart.markCoincident(); fCoinEnd.markCoincident(); } const SkTSpan* next() const { return fNext; } bool onlyEndPointsInCommon(const SkTSpan* opp, bool* start, bool* oppStart, bool* ptsInCommon); const TCurve& part() const { return fPart; } bool removeAllBounded(); bool removeBounded(const SkTSpan* opp); void reset() { fBounded = nullptr; } void resetBounds(const TCurve& curve) { fIsLinear = fIsLine = false; initBounds(curve); } bool split(SkTSpan* work, SkArenaAlloc* heap) { return splitAt(work, (work->fStartT + work->fEndT) * 0.5, heap); } bool splitAt(SkTSpan* work, double t, SkArenaAlloc* heap); double startT() const { return fStartT; } private: // implementation is for testing only int debugID() const { return PATH_OPS_DEBUG_T_SECT_RELEASE(fID, -1); } void dumpID() const; int hullCheck(const SkTSpan* opp, bool* start, bool* oppStart); int linearIntersects(const OppCurve& ) const; SkTSpan* oppT(double t) const; void validate() const; void validateBounded() const; void validatePerpT(double oppT) const; void validatePerpPt(double t, const SkDPoint& ) const; TCurve fPart; SkTCoincident fCoinStart; SkTCoincident fCoinEnd; SkTSpanBounded* fBounded; SkTSpan* fPrev; SkTSpan* fNext; SkDRect fBounds; double fStartT; double fEndT; double fBoundsMax; SkOpDebugBool fCollapsed; SkOpDebugBool fHasPerp; SkOpDebugBool fIsLinear; SkOpDebugBool fIsLine; SkOpDebugBool fDeleted; SkDEBUGCODE(SkOpGlobalState* fDebugGlobalState); SkDEBUGCODE(SkTSect* fDebugSect); PATH_OPS_DEBUG_T_SECT_CODE(int fID); friend class SkTSect; friend class SkTSect; friend class SkTSpan; }; template class SkTSect { public: SkTSect(const TCurve& c SkDEBUGPARAMS(SkOpGlobalState* ) PATH_OPS_DEBUG_T_SECT_PARAMS(int id)); static void BinarySearch(SkTSect* sect1, SkTSect* sect2, SkIntersections* intersections); SkDEBUGCODE(SkOpGlobalState* globalState() { return fDebugGlobalState; }) bool hasBounded(const SkTSpan* ) const; const SkTSect* debugOpp() const { return SkDEBUGRELEASE(fOppSect, nullptr); } const SkTSpan* debugSpan(int id) const; const SkTSpan* debugT(double t) const; void dump() const; void dumpBoth(SkTSect* ) const; void dumpBounded(int id) const; void dumpBounds() const; void dumpCoin() const; void dumpCoinCurves() const; void dumpCurves() const; private: enum { kZeroS1Set = 1, kOneS1Set = 2, kZeroS2Set = 4, kOneS2Set = 8 }; SkTSpan* addFollowing(SkTSpan* prior); void addForPerp(SkTSpan* span, double t); SkTSpan* addOne(); SkTSpan* addSplitAt(SkTSpan* span, double t) { SkTSpan* result = this->addOne(); SkDEBUGCODE(result->debugSetGlobalState(this->globalState())); result->splitAt(span, t, &fHeap); result->initBounds(fCurve); span->initBounds(fCurve); return result; } bool binarySearchCoin(SkTSect* , double tStart, double tStep, double* t, double* oppT, SkTSpan** oppFirst); SkTSpan* boundsMax() const; bool coincidentCheck(SkTSect* sect2); void coincidentForce(SkTSect* sect2, double start1s, double start1e); bool coincidentHasT(double t); int collapsed() const; void computePerpendiculars(SkTSect* sect2, SkTSpan* first, SkTSpan* last); int countConsecutiveSpans(SkTSpan* first, SkTSpan** last) const; int debugID() const { return PATH_OPS_DEBUG_T_SECT_RELEASE(fID, -1); } bool deleteEmptySpans(); void dumpCommon(const SkTSpan* ) const; void dumpCommonCurves(const SkTSpan* ) const; static int EndsEqual(const SkTSect* sect1, const SkTSect* sect2, SkIntersections* ); bool extractCoincident(SkTSect* sect2, SkTSpan* first, SkTSpan* last, SkTSpan** result); SkTSpan* findCoincidentRun(SkTSpan* first, SkTSpan** lastPtr); int intersects(SkTSpan* span, SkTSect* opp, SkTSpan* oppSpan, int* oppResult); bool isParallel(const SkDLine& thisLine, const SkTSect* opp) const; int linesIntersect(SkTSpan* span, SkTSect* opp, SkTSpan* oppSpan, SkIntersections* ); bool markSpanGone(SkTSpan* span); bool matchedDirection(double t, const SkTSect* sect2, double t2) const; void matchedDirCheck(double t, const SkTSect* sect2, double t2, bool* calcMatched, bool* oppMatched) const; void mergeCoincidence(SkTSect* sect2); SkTSpan* prev(SkTSpan* ) const; bool removeByPerpendicular(SkTSect* opp); void recoverCollapsed(); bool removeCoincident(SkTSpan* span, bool isBetween); void removeAllBut(const SkTSpan* keep, SkTSpan* span, SkTSect* opp); bool removeSpan(SkTSpan* span); void removeSpanRange(SkTSpan* first, SkTSpan* last); bool removeSpans(SkTSpan* span, SkTSect* opp); void removedEndCheck(SkTSpan* span); void resetRemovedEnds() { fRemovedStartT = fRemovedEndT = false; } SkTSpan* spanAtT(double t, SkTSpan** priorSpan); SkTSpan* tail(); bool trim(SkTSpan* span, SkTSect* opp); bool unlinkSpan(SkTSpan* span); bool updateBounded(SkTSpan* first, SkTSpan* last, SkTSpan* oppFirst); void validate() const; void validateBounded() const; const TCurve& fCurve; SkArenaAlloc fHeap; SkTSpan* fHead; SkTSpan* fCoincident; SkTSpan* fDeleted; int fActiveCount; bool fRemovedStartT; bool fRemovedEndT; SkDEBUGCODE(SkOpGlobalState* fDebugGlobalState); SkDEBUGCODE(SkTSect* fOppSect); PATH_OPS_DEBUG_T_SECT_CODE(int fID); PATH_OPS_DEBUG_T_SECT_CODE(int fDebugCount); #if DEBUG_T_SECT int fDebugAllocatedCount; #endif friend class SkTSpan; friend class SkTSpan; friend class SkTSect; }; #define COINCIDENT_SPAN_COUNT 9 template void SkTCoincident::setPerp(const TCurve& c1, double t, const SkDPoint& cPt, const OppCurve& c2) { SkDVector dxdy = c1.dxdyAtT(t); SkDLine perp = {{ cPt, {cPt.fX + dxdy.fY, cPt.fY - dxdy.fX} }}; SkIntersections i SkDEBUGCODE((c1.globalState())); int used = i.intersectRay(c2, perp); // only keep closest if (used == 0 || used == 3) { this->init(); return; } fPerpT = i[0][0]; fPerpPt = i.pt(0); SkASSERT(used <= 2); if (used == 2) { double distSq = (fPerpPt - cPt).lengthSquared(); double dist2Sq = (i.pt(1) - cPt).lengthSquared(); if (dist2Sq < distSq) { fPerpT = i[0][1]; fPerpPt = i.pt(1); } } #if DEBUG_T_SECT SkDebugf("setPerp t=%1.9g cPt=(%1.9g,%1.9g) %s oppT=%1.9g fPerpPt=(%1.9g,%1.9g)\n", t, cPt.fX, cPt.fY, cPt.approximatelyEqual(fPerpPt) ? "==" : "!=", fPerpT, fPerpPt.fX, fPerpPt.fY); #endif fMatch = cPt.approximatelyEqual(fPerpPt); #if DEBUG_T_SECT if (fMatch) { SkDebugf(""); // allow setting breakpoint } #endif } template void SkTSpan::addBounded(SkTSpan* span, SkArenaAlloc* heap) { SkTSpanBounded* bounded = heap->make>(); bounded->fBounded = span; bounded->fNext = fBounded; fBounded = bounded; } template SkTSpan* SkTSect::addFollowing( SkTSpan* prior) { SkTSpan* result = this->addOne(); SkDEBUGCODE(result->debugSetGlobalState(this->globalState())); result->fStartT = prior ? prior->fEndT : 0; SkTSpan* next = prior ? prior->fNext : fHead; result->fEndT = next ? next->fStartT : 1; result->fPrev = prior; result->fNext = next; if (prior) { prior->fNext = result; } else { fHead = result; } if (next) { next->fPrev = result; } result->resetBounds(fCurve); // world may not be consistent to call validate here result->validate(); return result; } template void SkTSect::addForPerp(SkTSpan* span, double t) { if (!span->hasOppT(t)) { SkTSpan* priorSpan; SkTSpan* opp = this->spanAtT(t, &priorSpan); if (!opp) { opp = this->addFollowing(priorSpan); #if DEBUG_PERP SkDebugf("%s priorSpan=%d t=%1.9g opp=%d\n", __FUNCTION__, priorSpan ? priorSpan->debugID() : -1, t, opp->debugID()); #endif } #if DEBUG_PERP opp->dump(); SkDebugf("\n"); SkDebugf("%s addBounded span=%d opp=%d\n", __FUNCTION__, priorSpan ? priorSpan->debugID() : -1, opp->debugID()); #endif opp->addBounded(span, &fHeap); span->addBounded(opp, &fHeap); } this->validate(); #if DEBUG_T_SECT span->validatePerpT(t); #endif } template double SkTSpan::closestBoundedT(const SkDPoint& pt) const { double result = -1; double closest = DBL_MAX; const SkTSpanBounded* testBounded = fBounded; while (testBounded) { const SkTSpan* test = testBounded->fBounded; double startDist = test->fPart[0].distanceSquared(pt); if (closest > startDist) { closest = startDist; result = test->fStartT; } double endDist = test->fPart[OppCurve::kPointLast].distanceSquared(pt); if (closest > endDist) { closest = endDist; result = test->fEndT; } testBounded = testBounded->fNext; } SkASSERT(between(0, result, 1)); return result; } #ifdef SK_DEBUG template bool SkTSpan::debugIsBefore(const SkTSpan* span) const { const SkTSpan* work = this; do { if (span == work) { return true; } } while ((work = work->fNext)); return false; } #endif template bool SkTSpan::contains(double t) const { const SkTSpan* work = this; do { if (between(work->fStartT, t, work->fEndT)) { return true; } } while ((work = work->fNext)); return false; } template const SkTSect* SkTSpan::debugOpp() const { return SkDEBUGRELEASE(fDebugSect->debugOpp(), nullptr); } template SkTSpan* SkTSpan::findOppSpan( const SkTSpan* opp) const { SkTSpanBounded* bounded = fBounded; while (bounded) { SkTSpan* test = bounded->fBounded; if (opp == test) { return test; } bounded = bounded->fNext; } return nullptr; } // returns 0 if no hull intersection // 1 if hulls intersect // 2 if hulls only share a common endpoint // -1 if linear and further checking is required template int SkTSpan::hullCheck(const SkTSpan* opp, bool* start, bool* oppStart) { if (fIsLinear) { return -1; } bool ptsInCommon; if (onlyEndPointsInCommon(opp, start, oppStart, &ptsInCommon)) { SkASSERT(ptsInCommon); return 2; } bool linear; if (fPart.hullIntersects(opp->fPart, &linear)) { if (!linear) { // check set true if linear return 1; } fIsLinear = true; fIsLine = fPart.controlsInside(); return ptsInCommon ? 1 : -1; } else { // hull is not linear; check set true if intersected at the end points return ((int) ptsInCommon) << 1; // 0 or 2 } return 0; } // OPTIMIZE ? If at_most_end_pts_in_common detects that one quad is near linear, // use line intersection to guess a better split than 0.5 // OPTIMIZE Once at_most_end_pts_in_common detects linear, mark span so all future splits are linear template int SkTSpan::hullsIntersect(SkTSpan* opp, bool* start, bool* oppStart) { if (!fBounds.intersects(opp->fBounds)) { return 0; } int hullSect = this->hullCheck(opp, start, oppStart); if (hullSect >= 0) { return hullSect; } hullSect = opp->hullCheck(this, oppStart, start); if (hullSect >= 0) { return hullSect; } return -1; } template void SkTSpan::init(const TCurve& c) { fPrev = fNext = nullptr; fStartT = 0; fEndT = 1; fBounded = nullptr; resetBounds(c); } template bool SkTSpan::initBounds(const TCurve& c) { if (SkDoubleIsNaN(fStartT) || SkDoubleIsNaN(fEndT)) { return false; } fPart = c.subDivide(fStartT, fEndT); fBounds.setBounds(fPart); fCoinStart.init(); fCoinEnd.init(); fBoundsMax = SkTMax(fBounds.width(), fBounds.height()); fCollapsed = fPart.collapsed(); fHasPerp = false; fDeleted = false; #if DEBUG_T_SECT if (fCollapsed) { SkDebugf(""); // for convenient breakpoints } #endif return fBounds.valid(); } template bool SkTSpan::linearsIntersect(SkTSpan* span) { int result = this->linearIntersects(span->fPart); if (result <= 1) { return SkToBool(result); } SkASSERT(span->fIsLinear); result = span->linearIntersects(this->fPart); // SkASSERT(result <= 1); return SkToBool(result); } template double SkTSpan::linearT(const SkDPoint& pt) const { SkDVector len = fPart[TCurve::kPointLast] - fPart[0]; return fabs(len.fX) > fabs(len.fY) ? (pt.fX - fPart[0].fX) / len.fX : (pt.fY - fPart[0].fY) / len.fY; } template int SkTSpan::linearIntersects(const OppCurve& q2) const { // looks like q1 is near-linear int start = 0, end = TCurve::kPointLast; // the outside points are usually the extremes if (!fPart.controlsInside()) { double dist = 0; // if there's any question, compute distance to find best outsiders for (int outer = 0; outer < TCurve::kPointCount - 1; ++outer) { for (int inner = outer + 1; inner < TCurve::kPointCount; ++inner) { double test = (fPart[outer] - fPart[inner]).lengthSquared(); if (dist > test) { continue; } dist = test; start = outer; end = inner; } } } // see if q2 is on one side of the line formed by the extreme points double origX = fPart[start].fX; double origY = fPart[start].fY; double adj = fPart[end].fX - origX; double opp = fPart[end].fY - origY; double maxPart = SkTMax(fabs(adj), fabs(opp)); double sign = 0; // initialization to shut up warning in release build for (int n = 0; n < OppCurve::kPointCount; ++n) { double dx = q2[n].fY - origY; double dy = q2[n].fX - origX; double maxVal = SkTMax(maxPart, SkTMax(fabs(dx), fabs(dy))); double test = (q2[n].fY - origY) * adj - (q2[n].fX - origX) * opp; if (precisely_zero_when_compared_to(test, maxVal)) { return 1; } if (approximately_zero_when_compared_to(test, maxVal)) { return 3; } if (n == 0) { sign = test; continue; } if (test * sign < 0) { return 1; } } return 0; } template bool SkTSpan::onlyEndPointsInCommon(const SkTSpan* opp, bool* start, bool* oppStart, bool* ptsInCommon) { if (opp->fPart[0] == fPart[0]) { *start = *oppStart = true; } else if (opp->fPart[0] == fPart[TCurve::kPointLast]) { *start = false; *oppStart = true; } else if (opp->fPart[OppCurve::kPointLast] == fPart[0]) { *start = true; *oppStart = false; } else if (opp->fPart[OppCurve::kPointLast] == fPart[TCurve::kPointLast]) { *start = *oppStart = false; } else { *ptsInCommon = false; return false; } *ptsInCommon = true; const SkDPoint* otherPts[TCurve::kPointCount - 1], * oppOtherPts[OppCurve::kPointCount - 1]; int baseIndex = *start ? 0 : TCurve::kPointLast; fPart.otherPts(baseIndex, otherPts); opp->fPart.otherPts(*oppStart ? 0 : OppCurve::kPointLast, oppOtherPts); const SkDPoint& base = fPart[baseIndex]; for (int o1 = 0; o1 < (int) SK_ARRAY_COUNT(otherPts); ++o1) { SkDVector v1 = *otherPts[o1] - base; for (int o2 = 0; o2 < (int) SK_ARRAY_COUNT(oppOtherPts); ++o2) { SkDVector v2 = *oppOtherPts[o2] - base; if (v2.dot(v1) >= 0) { return false; } } } return true; } template SkTSpan* SkTSpan::oppT(double t) const { SkTSpanBounded* bounded = fBounded; while (bounded) { SkTSpan* test = bounded->fBounded; if (between(test->fStartT, t, test->fEndT)) { return test; } bounded = bounded->fNext; } return nullptr; } template bool SkTSpan::removeAllBounded() { bool deleteSpan = false; SkTSpanBounded* bounded = fBounded; while (bounded) { SkTSpan* opp = bounded->fBounded; deleteSpan |= opp->removeBounded(this); bounded = bounded->fNext; } return deleteSpan; } template bool SkTSpan::removeBounded(const SkTSpan* opp) { if (fHasPerp) { bool foundStart = false; bool foundEnd = false; SkTSpanBounded* bounded = fBounded; while (bounded) { SkTSpan* test = bounded->fBounded; if (opp != test) { foundStart |= between(test->fStartT, fCoinStart.perpT(), test->fEndT); foundEnd |= between(test->fStartT, fCoinEnd.perpT(), test->fEndT); } bounded = bounded->fNext; } if (!foundStart || !foundEnd) { fHasPerp = false; fCoinStart.init(); fCoinEnd.init(); } } SkTSpanBounded* bounded = fBounded; SkTSpanBounded* prev = nullptr; while (bounded) { SkTSpanBounded* boundedNext = bounded->fNext; if (opp == bounded->fBounded) { if (prev) { prev->fNext = boundedNext; return false; } else { fBounded = boundedNext; return fBounded == nullptr; } } prev = bounded; bounded = boundedNext; } SkOPASSERT(0); return false; } template bool SkTSpan::splitAt(SkTSpan* work, double t, SkArenaAlloc* heap) { fStartT = t; fEndT = work->fEndT; if (fStartT == fEndT) { fCollapsed = true; return false; } work->fEndT = t; if (work->fStartT == work->fEndT) { work->fCollapsed = true; return false; } fPrev = work; fNext = work->fNext; fIsLinear = work->fIsLinear; fIsLine = work->fIsLine; work->fNext = this; if (fNext) { fNext->fPrev = this; } this->validate(); SkTSpanBounded* bounded = work->fBounded; fBounded = nullptr; while (bounded) { this->addBounded(bounded->fBounded, heap); bounded = bounded->fNext; } bounded = fBounded; while (bounded) { bounded->fBounded->addBounded(this, heap); bounded = bounded->fNext; } return true; } template void SkTSpan::validate() const { #if DEBUG_VALIDATE SkASSERT(this != fPrev); SkASSERT(this != fNext); SkASSERT(fNext == nullptr || fNext != fPrev); SkASSERT(fNext == nullptr || this == fNext->fPrev); SkASSERT(fPrev == nullptr || this == fPrev->fNext); this->validateBounded(); #endif #if DEBUG_T_SECT SkASSERT(fBounds.width() || fBounds.height() || fCollapsed); SkASSERT(fBoundsMax == SkTMax(fBounds.width(), fBounds.height()) || fCollapsed == 0xFF); SkASSERT(0 <= fStartT); SkASSERT(fEndT <= 1); SkASSERT(fStartT <= fEndT); SkASSERT(fBounded || fCollapsed == 0xFF); if (fHasPerp) { if (fCoinStart.isMatch()) { validatePerpT(fCoinStart.perpT()); validatePerpPt(fCoinStart.perpT(), fCoinStart.perpPt()); } if (fCoinEnd.isMatch()) { validatePerpT(fCoinEnd.perpT()); validatePerpPt(fCoinEnd.perpT(), fCoinEnd.perpPt()); } } #endif } template void SkTSpan::validateBounded() const { #if DEBUG_VALIDATE const SkTSpanBounded* testBounded = fBounded; while (testBounded) { SkDEBUGCODE(const SkTSpan* overlap = testBounded->fBounded); SkASSERT(!overlap->fDeleted); #if DEBUG_T_SECT SkASSERT(((this->debugID() ^ overlap->debugID()) & 1) == 1); SkASSERT(overlap->findOppSpan(this)); #endif testBounded = testBounded->fNext; } #endif } template void SkTSpan::validatePerpT(double oppT) const { const SkTSpanBounded* testBounded = fBounded; while (testBounded) { const SkTSpan* overlap = testBounded->fBounded; if (precisely_between(overlap->fStartT, oppT, overlap->fEndT)) { return; } testBounded = testBounded->fNext; } SkASSERT(0); } template void SkTSpan::validatePerpPt(double t, const SkDPoint& pt) const { SkASSERT(fDebugSect->fOppSect->fCurve.ptAtT(t) == pt); } template SkTSect::SkTSect(const TCurve& c SkDEBUGPARAMS(SkOpGlobalState* debugGlobalState) PATH_OPS_DEBUG_T_SECT_PARAMS(int id)) : fCurve(c) , fHeap(sizeof(SkTSpan) * 4) , fCoincident(nullptr) , fDeleted(nullptr) , fActiveCount(0) SkDEBUGPARAMS(fDebugGlobalState(debugGlobalState)) PATH_OPS_DEBUG_T_SECT_PARAMS(fID(id)) PATH_OPS_DEBUG_T_SECT_PARAMS(fDebugCount(0)) PATH_OPS_DEBUG_T_SECT_PARAMS(fDebugAllocatedCount(0)) { this->resetRemovedEnds(); fHead = this->addOne(); SkDEBUGCODE(fHead->debugSetGlobalState(debugGlobalState)); fHead->init(c); } template SkTSpan* SkTSect::addOne() { SkTSpan* result; if (fDeleted) { result = fDeleted; fDeleted = result->fNext; } else { result = fHeap.make>(); #if DEBUG_T_SECT ++fDebugAllocatedCount; #endif } result->reset(); result->fHasPerp = false; result->fDeleted = false; ++fActiveCount; PATH_OPS_DEBUG_T_SECT_CODE(result->fID = fDebugCount++ * 2 + fID); SkDEBUGCODE(result->fDebugSect = this); #ifdef SK_DEBUG result->fPart.debugInit(); result->fCoinStart.debugInit(); result->fCoinEnd.debugInit(); result->fPrev = result->fNext = nullptr; result->fBounds.debugInit(); result->fStartT = result->fEndT = result->fBoundsMax = SK_ScalarNaN; result->fCollapsed = result->fIsLinear = result->fIsLine = 0xFF; #endif return result; } template bool SkTSect::binarySearchCoin(SkTSect* sect2, double tStart, double tStep, double* resultT, double* oppT, SkTSpan** oppFirst) { SkTSpan work; double result = work.fStartT = work.fEndT = tStart; SkDEBUGCODE(work.fDebugSect = this); SkDPoint last = fCurve.ptAtT(tStart); SkDPoint oppPt; bool flip = false; bool contained = false; bool down = tStep < 0; const OppCurve& opp = sect2->fCurve; do { tStep *= 0.5; work.fStartT += tStep; if (flip) { tStep = -tStep; flip = false; } work.initBounds(fCurve); if (work.fCollapsed) { return false; } if (last.approximatelyEqual(work.fPart[0])) { break; } last = work.fPart[0]; work.fCoinStart.setPerp(fCurve, work.fStartT, last, opp); if (work.fCoinStart.isMatch()) { #if DEBUG_T_SECT work.validatePerpPt(work.fCoinStart.perpT(), work.fCoinStart.perpPt()); #endif double oppTTest = work.fCoinStart.perpT(); if (sect2->fHead->contains(oppTTest)) { *oppT = oppTTest; oppPt = work.fCoinStart.perpPt(); contained = true; if (down ? result <= work.fStartT : result >= work.fStartT) { *oppFirst = nullptr; // signal caller to fail return false; } result = work.fStartT; continue; } } tStep = -tStep; flip = true; } while (true); if (!contained) { return false; } if (last.approximatelyEqual(fCurve[0])) { result = 0; } else if (last.approximatelyEqual(fCurve[TCurve::kPointLast])) { result = 1; } if (oppPt.approximatelyEqual(opp[0])) { *oppT = 0; } else if (oppPt.approximatelyEqual(opp[OppCurve::kPointLast])) { *oppT = 1; } *resultT = result; return true; } // OPTIMIZE ? keep a sorted list of sizes in the form of a doubly-linked list in quad span // so that each quad sect has a pointer to the largest, and can update it as spans // are split template SkTSpan* SkTSect::boundsMax() const { SkTSpan* test = fHead; SkTSpan* largest = fHead; bool lCollapsed = largest->fCollapsed; while ((test = test->fNext)) { bool tCollapsed = test->fCollapsed; if ((lCollapsed && !tCollapsed) || (lCollapsed == tCollapsed && largest->fBoundsMax < test->fBoundsMax)) { largest = test; lCollapsed = test->fCollapsed; } } return largest; } template bool SkTSect::coincidentCheck(SkTSect* sect2) { SkTSpan* first = fHead; if (!first) { return false; } SkTSpan* last, * next; do { int consecutive = this->countConsecutiveSpans(first, &last); next = last->fNext; if (consecutive < COINCIDENT_SPAN_COUNT) { continue; } this->validate(); sect2->validate(); this->computePerpendiculars(sect2, first, last); this->validate(); sect2->validate(); // check to see if a range of points are on the curve SkTSpan* coinStart = first; do { bool success = this->extractCoincident(sect2, coinStart, last, &coinStart); if (!success) { return false; } } while (coinStart && !last->fDeleted); if (!fHead || !sect2->fHead) { break; } if (!next || next->fDeleted) { break; } } while ((first = next)); return true; } template void SkTSect::coincidentForce(SkTSect* sect2, double start1s, double start1e) { SkTSpan* first = fHead; SkTSpan* last = this->tail(); SkTSpan* oppFirst = sect2->fHead; SkTSpan* oppLast = sect2->tail(); bool deleteEmptySpans = this->updateBounded(first, last, oppFirst); deleteEmptySpans |= sect2->updateBounded(oppFirst, oppLast, first); this->removeSpanRange(first, last); sect2->removeSpanRange(oppFirst, oppLast); first->fStartT = start1s; first->fEndT = start1e; first->resetBounds(fCurve); first->fCoinStart.setPerp(fCurve, start1s, fCurve[0], sect2->fCurve); first->fCoinEnd.setPerp(fCurve, start1e, fCurve[TCurve::kPointLast], sect2->fCurve); bool oppMatched = first->fCoinStart.perpT() < first->fCoinEnd.perpT(); double oppStartT = first->fCoinStart.perpT() == -1 ? 0 : SkTMax(0., first->fCoinStart.perpT()); double oppEndT = first->fCoinEnd.perpT() == -1 ? 1 : SkTMin(1., first->fCoinEnd.perpT()); if (!oppMatched) { using std::swap; swap(oppStartT, oppEndT); } oppFirst->fStartT = oppStartT; oppFirst->fEndT = oppEndT; oppFirst->resetBounds(sect2->fCurve); this->removeCoincident(first, false); sect2->removeCoincident(oppFirst, true); if (deleteEmptySpans) { this->deleteEmptySpans(); sect2->deleteEmptySpans(); } } template bool SkTSect::coincidentHasT(double t) { SkTSpan* test = fCoincident; while (test) { if (between(test->fStartT, t, test->fEndT)) { return true; } test = test->fNext; } return false; } template int SkTSect::collapsed() const { int result = 0; const SkTSpan* test = fHead; while (test) { if (test->fCollapsed) { ++result; } test = test->next(); } return result; } template void SkTSect::computePerpendiculars(SkTSect* sect2, SkTSpan* first, SkTSpan* last) { const OppCurve& opp = sect2->fCurve; SkTSpan* work = first; SkTSpan* prior = nullptr; do { if (!work->fHasPerp && !work->fCollapsed) { if (prior) { work->fCoinStart = prior->fCoinEnd; } else { work->fCoinStart.setPerp(fCurve, work->fStartT, work->fPart[0], opp); } if (work->fCoinStart.isMatch()) { double perpT = work->fCoinStart.perpT(); if (sect2->coincidentHasT(perpT)) { work->fCoinStart.init(); } else { sect2->addForPerp(work, perpT); } } work->fCoinEnd.setPerp(fCurve, work->fEndT, work->fPart[TCurve::kPointLast], opp); if (work->fCoinEnd.isMatch()) { double perpT = work->fCoinEnd.perpT(); if (sect2->coincidentHasT(perpT)) { work->fCoinEnd.init(); } else { sect2->addForPerp(work, perpT); } } work->fHasPerp = true; } if (work == last) { break; } prior = work; work = work->fNext; SkASSERT(work); } while (true); } template int SkTSect::countConsecutiveSpans(SkTSpan* first, SkTSpan** lastPtr) const { int consecutive = 1; SkTSpan* last = first; do { SkTSpan* next = last->fNext; if (!next) { break; } if (next->fStartT > last->fEndT) { break; } ++consecutive; last = next; } while (true); *lastPtr = last; return consecutive; } template bool SkTSect::hasBounded(const SkTSpan* span) const { const SkTSpan* test = fHead; if (!test) { return false; } do { if (test->findOppSpan(span)) { return true; } } while ((test = test->next())); return false; } template bool SkTSect::deleteEmptySpans() { SkTSpan* test; SkTSpan* next = fHead; int safetyHatch = 1000; while ((test = next)) { next = test->fNext; if (!test->fBounded) { if (!this->removeSpan(test)) { return false; } } if (--safetyHatch < 0) { return false; } } return true; } template bool SkTSect::extractCoincident( SkTSect* sect2, SkTSpan* first, SkTSpan* last, SkTSpan** result) { first = findCoincidentRun(first, &last); if (!first || !last) { *result = nullptr; return true; } // march outwards to find limit of coincidence from here to previous and next spans double startT = first->fStartT; double oppStartT SK_INIT_TO_AVOID_WARNING; double oppEndT SK_INIT_TO_AVOID_WARNING; SkTSpan* prev = first->fPrev; SkASSERT(first->fCoinStart.isMatch()); SkTSpan* oppFirst = first->findOppT(first->fCoinStart.perpT()); SkOPASSERT(last->fCoinEnd.isMatch()); bool oppMatched = first->fCoinStart.perpT() < first->fCoinEnd.perpT(); double coinStart; SkDEBUGCODE(double coinEnd); SkTSpan* cutFirst; if (prev && prev->fEndT == startT && this->binarySearchCoin(sect2, startT, prev->fStartT - startT, &coinStart, &oppStartT, &oppFirst) && prev->fStartT < coinStart && coinStart < startT && (cutFirst = prev->oppT(oppStartT))) { oppFirst = cutFirst; first = this->addSplitAt(prev, coinStart); first->markCoincident(); prev->fCoinEnd.markCoincident(); if (oppFirst->fStartT < oppStartT && oppStartT < oppFirst->fEndT) { SkTSpan* oppHalf = sect2->addSplitAt(oppFirst, oppStartT); if (oppMatched) { oppFirst->fCoinEnd.markCoincident(); oppHalf->markCoincident(); oppFirst = oppHalf; } else { oppFirst->markCoincident(); oppHalf->fCoinStart.markCoincident(); } } } else { if (!oppFirst) { return false; } SkDEBUGCODE(coinStart = first->fStartT); SkDEBUGCODE(oppStartT = oppMatched ? oppFirst->fStartT : oppFirst->fEndT); } // FIXME: incomplete : if we're not at the end, find end of coin SkTSpan* oppLast; SkOPASSERT(last->fCoinEnd.isMatch()); oppLast = last->findOppT(last->fCoinEnd.perpT()); SkDEBUGCODE(coinEnd = last->fEndT); #ifdef SK_DEBUG if (!this->globalState() || !this->globalState()->debugSkipAssert()) { oppEndT = oppMatched ? oppLast->fEndT : oppLast->fStartT; } #endif if (!oppMatched) { using std::swap; swap(oppFirst, oppLast); swap(oppStartT, oppEndT); } SkOPASSERT(oppStartT < oppEndT); SkASSERT(coinStart == first->fStartT); SkASSERT(coinEnd == last->fEndT); SkOPASSERT(oppStartT == oppFirst->fStartT); SkOPASSERT(oppEndT == oppLast->fEndT); if (!oppFirst) { *result = nullptr; return true; } if (!oppLast) { *result = nullptr; return true; } // reduce coincident runs to single entries this->validate(); sect2->validate(); bool deleteEmptySpans = this->updateBounded(first, last, oppFirst); deleteEmptySpans |= sect2->updateBounded(oppFirst, oppLast, first); this->removeSpanRange(first, last); sect2->removeSpanRange(oppFirst, oppLast); first->fEndT = last->fEndT; first->resetBounds(this->fCurve); first->fCoinStart.setPerp(fCurve, first->fStartT, first->fPart[0], sect2->fCurve); first->fCoinEnd.setPerp(fCurve, first->fEndT, first->fPart[TCurve::kPointLast], sect2->fCurve); oppStartT = first->fCoinStart.perpT(); oppEndT = first->fCoinEnd.perpT(); if (between(0, oppStartT, 1) && between(0, oppEndT, 1)) { if (!oppMatched) { using std::swap; swap(oppStartT, oppEndT); } oppFirst->fStartT = oppStartT; oppFirst->fEndT = oppEndT; oppFirst->resetBounds(sect2->fCurve); } this->validateBounded(); sect2->validateBounded(); last = first->fNext; if (!this->removeCoincident(first, false)) { return false; } if (!sect2->removeCoincident(oppFirst, true)) { return false; } if (deleteEmptySpans) { if (!this->deleteEmptySpans() || !sect2->deleteEmptySpans()) { *result = nullptr; return false; } } this->validate(); sect2->validate(); *result = last && !last->fDeleted && fHead && sect2->fHead ? last : nullptr; return true; } template SkTSpan* SkTSect::findCoincidentRun( SkTSpan* first, SkTSpan** lastPtr) { SkTSpan* work = first; SkTSpan* lastCandidate = nullptr; first = nullptr; // find the first fully coincident span do { if (work->fCoinStart.isMatch()) { #if DEBUG_T_SECT work->validatePerpT(work->fCoinStart.perpT()); work->validatePerpPt(work->fCoinStart.perpT(), work->fCoinStart.perpPt()); #endif SkOPASSERT(work->hasOppT(work->fCoinStart.perpT())); if (!work->fCoinEnd.isMatch()) { break; } lastCandidate = work; if (!first) { first = work; } } else if (first && work->fCollapsed) { *lastPtr = lastCandidate; return first; } else { lastCandidate = nullptr; SkOPASSERT(!first); } if (work == *lastPtr) { return first; } work = work->fNext; if (!work) { return nullptr; } } while (true); if (lastCandidate) { *lastPtr = lastCandidate; } return first; } template int SkTSect::intersects(SkTSpan* span, SkTSect* opp, SkTSpan* oppSpan, int* oppResult) { bool spanStart, oppStart; int hullResult = span->hullsIntersect(oppSpan, &spanStart, &oppStart); if (hullResult >= 0) { if (hullResult == 2) { // hulls have one point in common if (!span->fBounded || !span->fBounded->fNext) { SkASSERT(!span->fBounded || span->fBounded->fBounded == oppSpan); if (spanStart) { span->fEndT = span->fStartT; } else { span->fStartT = span->fEndT; } } else { hullResult = 1; } if (!oppSpan->fBounded || !oppSpan->fBounded->fNext) { SkASSERT(!oppSpan->fBounded || oppSpan->fBounded->fBounded == span); if (oppStart) { oppSpan->fEndT = oppSpan->fStartT; } else { oppSpan->fStartT = oppSpan->fEndT; } *oppResult = 2; } else { *oppResult = 1; } } else { *oppResult = 1; } return hullResult; } if (span->fIsLine && oppSpan->fIsLine) { SkIntersections i; int sects = this->linesIntersect(span, opp, oppSpan, &i); if (sects == 2) { return *oppResult = 1; } if (!sects) { return -1; } this->removedEndCheck(span); span->fStartT = span->fEndT = i[0][0]; opp->removedEndCheck(oppSpan); oppSpan->fStartT = oppSpan->fEndT = i[1][0]; return *oppResult = 2; } if (span->fIsLinear || oppSpan->fIsLinear) { return *oppResult = (int) span->linearsIntersect(oppSpan); } return *oppResult = 1; } template static bool is_parallel(const SkDLine& thisLine, const TCurve& opp) { if (!opp.IsConic()) { return false; // FIXME : breaks a lot of stuff now } int finds = 0; SkDLine thisPerp; thisPerp.fPts[0].fX = thisLine.fPts[1].fX + (thisLine.fPts[1].fY - thisLine.fPts[0].fY); thisPerp.fPts[0].fY = thisLine.fPts[1].fY + (thisLine.fPts[0].fX - thisLine.fPts[1].fX); thisPerp.fPts[1] = thisLine.fPts[1]; SkIntersections perpRayI; perpRayI.intersectRay(opp, thisPerp); for (int pIndex = 0; pIndex < perpRayI.used(); ++pIndex) { finds += perpRayI.pt(pIndex).approximatelyEqual(thisPerp.fPts[1]); } thisPerp.fPts[1].fX = thisLine.fPts[0].fX + (thisLine.fPts[1].fY - thisLine.fPts[0].fY); thisPerp.fPts[1].fY = thisLine.fPts[0].fY + (thisLine.fPts[0].fX - thisLine.fPts[1].fX); thisPerp.fPts[0] = thisLine.fPts[0]; perpRayI.intersectRay(opp, thisPerp); for (int pIndex = 0; pIndex < perpRayI.used(); ++pIndex) { finds += perpRayI.pt(pIndex).approximatelyEqual(thisPerp.fPts[0]); } return finds >= 2; } // while the intersection points are sufficiently far apart: // construct the tangent lines from the intersections // find the point where the tangent line intersects the opposite curve template int SkTSect::linesIntersect(SkTSpan* span, SkTSect* opp, SkTSpan* oppSpan, SkIntersections* i) { SkIntersections thisRayI SkDEBUGCODE((span->fDebugGlobalState)); SkIntersections oppRayI SkDEBUGCODE((span->fDebugGlobalState)); SkDLine thisLine = {{ span->fPart[0], span->fPart[TCurve::kPointLast] }}; SkDLine oppLine = {{ oppSpan->fPart[0], oppSpan->fPart[OppCurve::kPointLast] }}; int loopCount = 0; double bestDistSq = DBL_MAX; if (!thisRayI.intersectRay(opp->fCurve, thisLine)) { return 0; } if (!oppRayI.intersectRay(this->fCurve, oppLine)) { return 0; } // if the ends of each line intersect the opposite curve, the lines are coincident if (thisRayI.used() > 1) { int ptMatches = 0; for (int tIndex = 0; tIndex < thisRayI.used(); ++tIndex) { for (int lIndex = 0; lIndex < (int) SK_ARRAY_COUNT(thisLine.fPts); ++lIndex) { ptMatches += thisRayI.pt(tIndex).approximatelyEqual(thisLine.fPts[lIndex]); } } if (ptMatches == 2 || is_parallel(thisLine, opp->fCurve)) { return 2; } } if (oppRayI.used() > 1) { int ptMatches = 0; for (int oIndex = 0; oIndex < oppRayI.used(); ++oIndex) { for (int lIndex = 0; lIndex < (int) SK_ARRAY_COUNT(oppLine.fPts); ++lIndex) { ptMatches += oppRayI.pt(oIndex).approximatelyEqual(oppLine.fPts[lIndex]); } } if (ptMatches == 2|| is_parallel(oppLine, this->fCurve)) { return 2; } } do { // pick the closest pair of points double closest = DBL_MAX; int closeIndex SK_INIT_TO_AVOID_WARNING; int oppCloseIndex SK_INIT_TO_AVOID_WARNING; for (int index = 0; index < oppRayI.used(); ++index) { if (!roughly_between(span->fStartT, oppRayI[0][index], span->fEndT)) { continue; } for (int oIndex = 0; oIndex < thisRayI.used(); ++oIndex) { if (!roughly_between(oppSpan->fStartT, thisRayI[0][oIndex], oppSpan->fEndT)) { continue; } double distSq = thisRayI.pt(index).distanceSquared(oppRayI.pt(oIndex)); if (closest > distSq) { closest = distSq; closeIndex = index; oppCloseIndex = oIndex; } } } if (closest == DBL_MAX) { break; } const SkDPoint& oppIPt = thisRayI.pt(oppCloseIndex); const SkDPoint& iPt = oppRayI.pt(closeIndex); if (between(span->fStartT, oppRayI[0][closeIndex], span->fEndT) && between(oppSpan->fStartT, thisRayI[0][oppCloseIndex], oppSpan->fEndT) && oppIPt.approximatelyEqual(iPt)) { i->merge(oppRayI, closeIndex, thisRayI, oppCloseIndex); return i->used(); } double distSq = oppIPt.distanceSquared(iPt); if (bestDistSq < distSq || ++loopCount > 5) { return 0; } bestDistSq = distSq; double oppStart = oppRayI[0][closeIndex]; thisLine[0] = fCurve.ptAtT(oppStart); thisLine[1] = thisLine[0] + fCurve.dxdyAtT(oppStart); if (!thisRayI.intersectRay(opp->fCurve, thisLine)) { break; } double start = thisRayI[0][oppCloseIndex]; oppLine[0] = opp->fCurve.ptAtT(start); oppLine[1] = oppLine[0] + opp->fCurve.dxdyAtT(start); if (!oppRayI.intersectRay(this->fCurve, oppLine)) { break; } } while (true); // convergence may fail if the curves are nearly coincident SkTCoincident oCoinS, oCoinE; oCoinS.setPerp(opp->fCurve, oppSpan->fStartT, oppSpan->fPart[0], fCurve); oCoinE.setPerp(opp->fCurve, oppSpan->fEndT, oppSpan->fPart[OppCurve::kPointLast], fCurve); double tStart = oCoinS.perpT(); double tEnd = oCoinE.perpT(); bool swap = tStart > tEnd; if (swap) { using std::swap; swap(tStart, tEnd); } tStart = SkTMax(tStart, span->fStartT); tEnd = SkTMin(tEnd, span->fEndT); if (tStart > tEnd) { return 0; } SkDVector perpS, perpE; if (tStart == span->fStartT) { SkTCoincident coinS; coinS.setPerp(fCurve, span->fStartT, span->fPart[0], opp->fCurve); perpS = span->fPart[0] - coinS.perpPt(); } else if (swap) { perpS = oCoinE.perpPt() - oppSpan->fPart[OppCurve::kPointLast]; } else { perpS = oCoinS.perpPt() - oppSpan->fPart[0]; } if (tEnd == span->fEndT) { SkTCoincident coinE; coinE.setPerp(fCurve, span->fEndT, span->fPart[TCurve::kPointLast], opp->fCurve); perpE = span->fPart[TCurve::kPointLast] - coinE.perpPt(); } else if (swap) { perpE = oCoinS.perpPt() - oppSpan->fPart[0]; } else { perpE = oCoinE.perpPt() - oppSpan->fPart[OppCurve::kPointLast]; } if (perpS.dot(perpE) >= 0) { return 0; } SkTCoincident coinW; double workT = tStart; double tStep = tEnd - tStart; SkDPoint workPt; do { tStep *= 0.5; if (precisely_zero(tStep)) { return 0; } workT += tStep; workPt = fCurve.ptAtT(workT); coinW.setPerp(fCurve, workT, workPt, opp->fCurve); double perpT = coinW.perpT(); if (coinW.isMatch() ? !between(oppSpan->fStartT, perpT, oppSpan->fEndT) : perpT < 0) { continue; } SkDVector perpW = workPt - coinW.perpPt(); if ((perpS.dot(perpW) >= 0) == (tStep < 0)) { tStep = -tStep; } if (workPt.approximatelyEqual(coinW.perpPt())) { break; } } while (true); double oppTTest = coinW.perpT(); if (!opp->fHead->contains(oppTTest)) { return 0; } i->setMax(1); i->insert(workT, oppTTest, workPt); return 1; } template bool SkTSect::markSpanGone(SkTSpan* span) { if (--fActiveCount < 0) { return false; } span->fNext = fDeleted; fDeleted = span; SkOPASSERT(!span->fDeleted); span->fDeleted = true; return true; } template bool SkTSect::matchedDirection(double t, const SkTSect* sect2, double t2) const { SkDVector dxdy = this->fCurve.dxdyAtT(t); SkDVector dxdy2 = sect2->fCurve.dxdyAtT(t2); return dxdy.dot(dxdy2) >= 0; } template void SkTSect::matchedDirCheck(double t, const SkTSect* sect2, double t2, bool* calcMatched, bool* oppMatched) const { if (*calcMatched) { SkASSERT(*oppMatched == this->matchedDirection(t, sect2, t2)); } else { *oppMatched = this->matchedDirection(t, sect2, t2); *calcMatched = true; } } template void SkTSect::mergeCoincidence(SkTSect* sect2) { double smallLimit = 0; do { // find the smallest unprocessed span SkTSpan* smaller = nullptr; SkTSpan* test = fCoincident; do { if (!test) { return; } if (test->fStartT < smallLimit) { continue; } if (smaller && smaller->fEndT < test->fStartT) { continue; } smaller = test; } while ((test = test->fNext)); if (!smaller) { return; } smallLimit = smaller->fEndT; // find next larger span SkTSpan* prior = nullptr; SkTSpan* larger = nullptr; SkTSpan* largerPrior = nullptr; test = fCoincident; do { if (test->fStartT < smaller->fEndT) { continue; } SkOPASSERT(test->fStartT != smaller->fEndT); if (larger && larger->fStartT < test->fStartT) { continue; } largerPrior = prior; larger = test; } while ((prior = test), (test = test->fNext)); if (!larger) { continue; } // check middle t value to see if it is coincident as well double midT = (smaller->fEndT + larger->fStartT) / 2; SkDPoint midPt = fCurve.ptAtT(midT); SkTCoincident coin; coin.setPerp(fCurve, midT, midPt, sect2->fCurve); if (coin.isMatch()) { smaller->fEndT = larger->fEndT; smaller->fCoinEnd = larger->fCoinEnd; if (largerPrior) { largerPrior->fNext = larger->fNext; largerPrior->validate(); } else { fCoincident = larger->fNext; } } } while (true); } template SkTSpan* SkTSect::prev( SkTSpan* span) const { SkTSpan* result = nullptr; SkTSpan* test = fHead; while (span != test) { result = test; test = test->fNext; SkASSERT(test); } return result; } template void SkTSect::recoverCollapsed() { SkTSpan* deleted = fDeleted; while (deleted) { SkTSpan* delNext = deleted->fNext; if (deleted->fCollapsed) { SkTSpan** spanPtr = &fHead; while (*spanPtr && (*spanPtr)->fEndT <= deleted->fStartT) { spanPtr = &(*spanPtr)->fNext; } deleted->fNext = *spanPtr; *spanPtr = deleted; } deleted = delNext; } } template void SkTSect::removeAllBut(const SkTSpan* keep, SkTSpan* span, SkTSect* opp) { const SkTSpanBounded* testBounded = span->fBounded; while (testBounded) { SkTSpan* bounded = testBounded->fBounded; const SkTSpanBounded* next = testBounded->fNext; // may have been deleted when opp did 'remove all but' if (bounded != keep && !bounded->fDeleted) { SkAssertResult(SkDEBUGCODE(!) span->removeBounded(bounded)); if (bounded->removeBounded(span)) { opp->removeSpan(bounded); } } testBounded = next; } SkASSERT(!span->fDeleted); SkASSERT(span->findOppSpan(keep)); SkASSERT(keep->findOppSpan(span)); } template bool SkTSect::removeByPerpendicular(SkTSect* opp) { SkTSpan* test = fHead; SkTSpan* next; do { next = test->fNext; if (test->fCoinStart.perpT() < 0 || test->fCoinEnd.perpT() < 0) { continue; } SkDVector startV = test->fCoinStart.perpPt() - test->fPart[0]; SkDVector endV = test->fCoinEnd.perpPt() - test->fPart[TCurve::kPointLast]; #if DEBUG_T_SECT SkDebugf("%s startV=(%1.9g,%1.9g) endV=(%1.9g,%1.9g) dot=%1.9g\n", __FUNCTION__, startV.fX, startV.fY, endV.fX, endV.fY, startV.dot(endV)); #endif if (startV.dot(endV) <= 0) { continue; } if (!this->removeSpans(test, opp)) { return false; } } while ((test = next)); return true; } template bool SkTSect::removeCoincident(SkTSpan* span, bool isBetween) { if (!this->unlinkSpan(span)) { return false; } if (isBetween || between(0, span->fCoinStart.perpT(), 1)) { --fActiveCount; span->fNext = fCoincident; fCoincident = span; } else { this->markSpanGone(span); } return true; } template void SkTSect::removedEndCheck(SkTSpan* span) { if (!span->fStartT) { fRemovedStartT = true; } if (1 == span->fEndT) { fRemovedEndT = true; } } template bool SkTSect::removeSpan(SkTSpan* span) {\ this->removedEndCheck(span); if (!this->unlinkSpan(span)) { return false; } return this->markSpanGone(span); } template void SkTSect::removeSpanRange(SkTSpan* first, SkTSpan* last) { if (first == last) { return; } SkTSpan* span = first; SkASSERT(span); SkTSpan* final = last->fNext; SkTSpan* next = span->fNext; while ((span = next) && span != final) { next = span->fNext; this->markSpanGone(span); } if (final) { final->fPrev = first; } first->fNext = final; // world may not be ready for validation here first->validate(); } template bool SkTSect::removeSpans(SkTSpan* span, SkTSect* opp) { SkTSpanBounded* bounded = span->fBounded; while (bounded) { SkTSpan* spanBounded = bounded->fBounded; SkTSpanBounded* next = bounded->fNext; if (span->removeBounded(spanBounded)) { // shuffles last into position 0 this->removeSpan(span); } if (spanBounded->removeBounded(span)) { opp->removeSpan(spanBounded); } if (span->fDeleted && opp->hasBounded(span)) { return false; } bounded = next; } return true; } template SkTSpan* SkTSect::spanAtT(double t, SkTSpan** priorSpan) { SkTSpan* test = fHead; SkTSpan* prev = nullptr; while (test && test->fEndT < t) { prev = test; test = test->fNext; } *priorSpan = prev; return test && test->fStartT <= t ? test : nullptr; } template SkTSpan* SkTSect::tail() { SkTSpan* result = fHead; SkTSpan* next = fHead; while ((next = next->fNext)) { if (next->fEndT > result->fEndT) { result = next; } } return result; } /* Each span has a range of opposite spans it intersects. After the span is split in two, adjust the range to its new size */ template bool SkTSect::trim(SkTSpan* span, SkTSect* opp) { FAIL_IF(!span->initBounds(fCurve)); const SkTSpanBounded* testBounded = span->fBounded; while (testBounded) { SkTSpan* test = testBounded->fBounded; const SkTSpanBounded* next = testBounded->fNext; int oppSects, sects = this->intersects(span, opp, test, &oppSects); if (sects >= 1) { if (oppSects == 2) { test->initBounds(opp->fCurve); opp->removeAllBut(span, test, this); } if (sects == 2) { span->initBounds(fCurve); this->removeAllBut(test, span, opp); return true; } } else { if (span->removeBounded(test)) { this->removeSpan(span); } if (test->removeBounded(span)) { opp->removeSpan(test); } } testBounded = next; } return true; } template bool SkTSect::unlinkSpan(SkTSpan* span) { SkTSpan* prev = span->fPrev; SkTSpan* next = span->fNext; if (prev) { prev->fNext = next; if (next) { next->fPrev = prev; if (next->fStartT > next->fEndT) { return false; } // world may not be ready for validate here next->validate(); } } else { fHead = next; if (next) { next->fPrev = nullptr; } } return true; } template bool SkTSect::updateBounded(SkTSpan* first, SkTSpan* last, SkTSpan* oppFirst) { SkTSpan* test = first; const SkTSpan* final = last->next(); bool deleteSpan = false; do { deleteSpan |= test->removeAllBounded(); } while ((test = test->fNext) != final && test); first->fBounded = nullptr; first->addBounded(oppFirst, &fHeap); // cannot call validate until remove span range is called return deleteSpan; } template void SkTSect::validate() const { #if DEBUG_VALIDATE int count = 0; double last = 0; if (fHead) { const SkTSpan* span = fHead; SkASSERT(!span->fPrev); const SkTSpan* next; do { span->validate(); SkASSERT(span->fStartT >= last); last = span->fEndT; ++count; next = span->fNext; SkASSERT(next != span); } while ((span = next) != nullptr); } SkASSERT(count == fActiveCount); #endif #if DEBUG_T_SECT SkASSERT(fActiveCount <= fDebugAllocatedCount); int deletedCount = 0; const SkTSpan* deleted = fDeleted; while (deleted) { ++deletedCount; deleted = deleted->fNext; } const SkTSpan* coincident = fCoincident; while (coincident) { ++deletedCount; coincident = coincident->fNext; } SkASSERT(fActiveCount + deletedCount == fDebugAllocatedCount); #endif } template void SkTSect::validateBounded() const { #if DEBUG_VALIDATE if (!fHead) { return; } const SkTSpan* span = fHead; do { span->validateBounded(); } while ((span = span->fNext) != nullptr); #endif } template int SkTSect::EndsEqual(const SkTSect* sect1, const SkTSect* sect2, SkIntersections* intersections) { int zeroOneSet = 0; if (sect1->fCurve[0] == sect2->fCurve[0]) { zeroOneSet |= kZeroS1Set | kZeroS2Set; intersections->insert(0, 0, sect1->fCurve[0]); } if (sect1->fCurve[0] == sect2->fCurve[OppCurve::kPointLast]) { zeroOneSet |= kZeroS1Set | kOneS2Set; intersections->insert(0, 1, sect1->fCurve[0]); } if (sect1->fCurve[TCurve::kPointLast] == sect2->fCurve[0]) { zeroOneSet |= kOneS1Set | kZeroS2Set; intersections->insert(1, 0, sect1->fCurve[TCurve::kPointLast]); } if (sect1->fCurve[TCurve::kPointLast] == sect2->fCurve[OppCurve::kPointLast]) { zeroOneSet |= kOneS1Set | kOneS2Set; intersections->insert(1, 1, sect1->fCurve[TCurve::kPointLast]); } // check for zero if (!(zeroOneSet & (kZeroS1Set | kZeroS2Set)) && sect1->fCurve[0].approximatelyEqual(sect2->fCurve[0])) { zeroOneSet |= kZeroS1Set | kZeroS2Set; intersections->insertNear(0, 0, sect1->fCurve[0], sect2->fCurve[0]); } if (!(zeroOneSet & (kZeroS1Set | kOneS2Set)) && sect1->fCurve[0].approximatelyEqual(sect2->fCurve[OppCurve::kPointLast])) { zeroOneSet |= kZeroS1Set | kOneS2Set; intersections->insertNear(0, 1, sect1->fCurve[0], sect2->fCurve[OppCurve::kPointLast]); } // check for one if (!(zeroOneSet & (kOneS1Set | kZeroS2Set)) && sect1->fCurve[TCurve::kPointLast].approximatelyEqual(sect2->fCurve[0])) { zeroOneSet |= kOneS1Set | kZeroS2Set; intersections->insertNear(1, 0, sect1->fCurve[TCurve::kPointLast], sect2->fCurve[0]); } if (!(zeroOneSet & (kOneS1Set | kOneS2Set)) && sect1->fCurve[TCurve::kPointLast].approximatelyEqual(sect2->fCurve[ OppCurve::kPointLast])) { zeroOneSet |= kOneS1Set | kOneS2Set; intersections->insertNear(1, 1, sect1->fCurve[TCurve::kPointLast], sect2->fCurve[OppCurve::kPointLast]); } return zeroOneSet; } template struct SkClosestRecord { bool operator<(const SkClosestRecord& rh) const { return fClosest < rh.fClosest; } void addIntersection(SkIntersections* intersections) const { double r1t = fC1Index ? fC1Span->endT() : fC1Span->startT(); double r2t = fC2Index ? fC2Span->endT() : fC2Span->startT(); intersections->insert(r1t, r2t, fC1Span->part()[fC1Index]); } void findEnd(const SkTSpan* span1, const SkTSpan* span2, int c1Index, int c2Index) { const TCurve& c1 = span1->part(); const OppCurve& c2 = span2->part(); if (!c1[c1Index].approximatelyEqual(c2[c2Index])) { return; } double dist = c1[c1Index].distanceSquared(c2[c2Index]); if (fClosest < dist) { return; } fC1Span = span1; fC2Span = span2; fC1StartT = span1->startT(); fC1EndT = span1->endT(); fC2StartT = span2->startT(); fC2EndT = span2->endT(); fC1Index = c1Index; fC2Index = c2Index; fClosest = dist; } bool matesWith(const SkClosestRecord& mate SkDEBUGPARAMS(SkIntersections* i)) const { SkOPOBJASSERT(i, fC1Span == mate.fC1Span || fC1Span->endT() <= mate.fC1Span->startT() || mate.fC1Span->endT() <= fC1Span->startT()); SkOPOBJASSERT(i, fC2Span == mate.fC2Span || fC2Span->endT() <= mate.fC2Span->startT() || mate.fC2Span->endT() <= fC2Span->startT()); return fC1Span == mate.fC1Span || fC1Span->endT() == mate.fC1Span->startT() || fC1Span->startT() == mate.fC1Span->endT() || fC2Span == mate.fC2Span || fC2Span->endT() == mate.fC2Span->startT() || fC2Span->startT() == mate.fC2Span->endT(); } void merge(const SkClosestRecord& mate) { fC1Span = mate.fC1Span; fC2Span = mate.fC2Span; fClosest = mate.fClosest; fC1Index = mate.fC1Index; fC2Index = mate.fC2Index; } void reset() { fClosest = FLT_MAX; SkDEBUGCODE(fC1Span = nullptr); SkDEBUGCODE(fC2Span = nullptr); SkDEBUGCODE(fC1Index = fC2Index = -1); } void update(const SkClosestRecord& mate) { fC1StartT = SkTMin(fC1StartT, mate.fC1StartT); fC1EndT = SkTMax(fC1EndT, mate.fC1EndT); fC2StartT = SkTMin(fC2StartT, mate.fC2StartT); fC2EndT = SkTMax(fC2EndT, mate.fC2EndT); } const SkTSpan* fC1Span; const SkTSpan* fC2Span; double fC1StartT; double fC1EndT; double fC2StartT; double fC2EndT; double fClosest; int fC1Index; int fC2Index; }; template struct SkClosestSect { SkClosestSect() : fUsed(0) { fClosest.push_back().reset(); } bool find(const SkTSpan* span1, const SkTSpan* span2 SkDEBUGPARAMS(SkIntersections* i)) { SkClosestRecord* record = &fClosest[fUsed]; record->findEnd(span1, span2, 0, 0); record->findEnd(span1, span2, 0, OppCurve::kPointLast); record->findEnd(span1, span2, TCurve::kPointLast, 0); record->findEnd(span1, span2, TCurve::kPointLast, OppCurve::kPointLast); if (record->fClosest == FLT_MAX) { return false; } for (int index = 0; index < fUsed; ++index) { SkClosestRecord* test = &fClosest[index]; if (test->matesWith(*record SkDEBUGPARAMS(i))) { if (test->fClosest > record->fClosest) { test->merge(*record); } test->update(*record); record->reset(); return false; } } ++fUsed; fClosest.push_back().reset(); return true; } void finish(SkIntersections* intersections) const { SkSTArray*, true> closestPtrs; for (int index = 0; index < fUsed; ++index) { closestPtrs.push_back(&fClosest[index]); } SkTQSort >(closestPtrs.begin(), closestPtrs.end() - 1); for (int index = 0; index < fUsed; ++index) { const SkClosestRecord* test = closestPtrs[index]; test->addIntersection(intersections); } } // this is oversized so that an extra records can merge into final one SkSTArray, true> fClosest; int fUsed; }; // returns true if the rect is too small to consider template