HELLO·Android
系统源代码
IT资讯
技术文章
我的收藏
注册
登录
-
我收藏的文章
创建代码块
我的代码块
我的账号
Pie
|
9.0.0_r8
下载
查看原文件
收藏
根目录
external
skia
src
pathops
SkPathOpsTSect.h
/* * 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 "SkPathOpsBounds.h" #include "SkPathOpsRect.h" #include "SkIntersections.h" #include "SkTSort.h" #ifdef SK_DEBUG typedef uint8_t SkOpDebugBool; #else typedef bool SkOpDebugBool; #endif /* 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; }) // for testing only bool debugHasBounded(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
* 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; void 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); void 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); 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) { 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
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; SkDEBUGCODE(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; SkASSERT(down ? result > work.fStartT : result < work.fStartT); 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) { SkTSwap(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
::debugHasBounded(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) && 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 { SkDEBUGCODE(coinStart = first->fStartT); FAIL_IF(!oppFirst); 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) { SkTSwap(oppFirst, oppLast); SkTSwap(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) { SkTSwap(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