diff options
author | caryclark <caryclark@google.com> | 2015-04-20 08:31:59 -0700 |
---|---|---|
committer | Commit bot <commit-bot@chromium.org> | 2015-04-20 08:31:59 -0700 |
commit | 1049f1246e7be4ccb68001361efceb8933e6f81c (patch) | |
tree | 9c71ceb245856cbe2173913eaec3b0ebb490dd74 /src/pathops/SkPathOpsTSect.h | |
parent | 5c476fb2776639bdbf0e974dd38d1c5d4c4ff1aa (diff) |
Now, path ops natively intersect conics, quads, and cubics in any combination. There are still a class of cubic tests that fail and a handful of undiagnosed failures from skps and fuzz tests, but things are much better overall.
Extended tests (150M+) run to completion in release in about 6 minutes; the standard test suite exceeds 100K and finishes in a few seconds on desktops.
TBR=reed
BUG=skia:3588
Review URL: https://codereview.chromium.org/1037953004
Diffstat (limited to 'src/pathops/SkPathOpsTSect.h')
-rw-r--r-- | src/pathops/SkPathOpsTSect.h | 945 |
1 files changed, 546 insertions, 399 deletions
diff --git a/src/pathops/SkPathOpsTSect.h b/src/pathops/SkPathOpsTSect.h index 9d63433330..ffd69951d3 100644 --- a/src/pathops/SkPathOpsTSect.h +++ b/src/pathops/SkPathOpsTSect.h @@ -8,16 +8,15 @@ #include "SkChunkAlloc.h" #include "SkPathOpsBounds.h" #include "SkPathOpsRect.h" -#include "SkPathOpsQuad.h" #include "SkIntersections.h" #include "SkTSort.h" -/* TCurve is either SkDQuadratic or SkDCubic */ -template<typename TCurve> +/* TCurve and OppCurve are one of { SkDQuadratic, SkDConic, SkDCubic } */ +template<typename TCurve, typename OppCurve> class SkTCoincident { public: SkTCoincident() { - clear(); + this->clear(); } void clear() { @@ -25,12 +24,19 @@ public: fCoincident = false; } + void debugInit() { + this->clear(); + fPerpPt.fX = fPerpPt.fY = SK_ScalarNaN; + } + + void dump() const; + bool isCoincident() const { return fCoincident; } void init() { - clear(); + this->clear(); SkDEBUGCODE(fPerpPt.fX = fPerpPt.fY = SK_ScalarNaN); } @@ -49,7 +55,7 @@ public: return fPerpT; } - void setPerp(const TCurve& c1, double t, const SkDPoint& cPt, const TCurve& ); + void setPerp(const TCurve& c1, double t, const SkDPoint& cPt, const OppCurve& ); private: SkDPoint fPerpPt; @@ -57,40 +63,51 @@ private: bool fCoincident; }; -template<typename TCurve> class SkTSect; -template<typename TCurve> class SkTSpan; +template<typename TCurve, typename OppCurve> class SkTSect; +template<typename TCurve, typename OppCurve> class SkTSpan; -template<typename TCurve> +template<typename TCurve, typename OppCurve> struct SkTSpanBounded { - SkTSpan<TCurve>* fBounded; + SkTSpan<TCurve, OppCurve>* fBounded; SkTSpanBounded* fNext; }; /* Curve is either TCurve or SkDCubic */ -template<typename TCurve> +template<typename TCurve, typename OppCurve> class SkTSpan { public: - void addBounded(SkTSpan* , SkChunkAlloc* ); + void addBounded(SkTSpan<OppCurve, TCurve>* , SkChunkAlloc* ); double closestBoundedT(const SkDPoint& pt) const; bool contains(double t) const; - const SkTSect<TCurve>* debugOpp() const; + void debugInit() { + TCurve dummy; + dummy.debugInit(); + init(dummy); + initBounds(dummy); + fCoinStart.debugInit(); + fCoinEnd.debugInit(); + } + + const SkTSect<OppCurve, TCurve>* debugOpp() const; 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 dumpBounds(int id) const; + void dumpBounded(int id) const; + void dumpBounds() const; + void dumpCoin() const; double endT() const { return fEndT; } - SkTSpan* findOppSpan(const SkTSpan* opp) const; + SkTSpan<OppCurve, TCurve>* findOppSpan(const SkTSpan<OppCurve, TCurve>* opp) const; - SkTSpan* findOppT(double t) const { - SkTSpan* result = oppT(t); + SkTSpan<OppCurve, TCurve>* findOppT(double t) const { + SkTSpan<OppCurve, TCurve>* result = oppT(t); SkASSERT(result); return result; } @@ -99,7 +116,7 @@ public: return SkToBool(oppT(t)); } - int hullsIntersect(SkTSpan* span, bool* start, bool* oppStart); + int hullsIntersect(SkTSpan<OppCurve, TCurve>* span, bool* start, bool* oppStart); void init(const TCurve& ); void initBounds(const TCurve& ); @@ -107,7 +124,7 @@ public: return fBounded != NULL; } - bool linearsIntersect(SkTSpan* span); + bool linearsIntersect(SkTSpan<OppCurve, TCurve>* span); double linearT(const SkDPoint& ) const; void markCoincident() { @@ -119,14 +136,15 @@ public: return fNext; } - bool onlyEndPointsInCommon(const SkTSpan* opp, bool* start, bool* oppStart, bool* ptsInCommon); + bool onlyEndPointsInCommon(const SkTSpan<OppCurve, TCurve>* opp, bool* start, + bool* oppStart, bool* ptsInCommon); const TCurve& part() const { return fPart; } bool removeAllBounded(); - bool removeBounded(const SkTSpan* opp); + bool removeBounded(const SkTSpan<OppCurve, TCurve>* opp); void reset() { fBounded = NULL; @@ -156,9 +174,9 @@ private: void dumpID() const; - int hullCheck(const SkTSpan* opp, bool* start, bool* oppStart); - int linearIntersects(const TCurve& ) const; - SkTSpan* oppT(double t) const; + int hullCheck(const SkTSpan<OppCurve, TCurve>* opp, bool* start, bool* oppStart); + int linearIntersects(const OppCurve& ) const; + SkTSpan<OppCurve, TCurve>* oppT(double t) const; void validate() const; void validateBounded() const; @@ -166,9 +184,9 @@ private: void validatePerpPt(double t, const SkDPoint& ) const; TCurve fPart; - SkTCoincident<TCurve> fCoinStart; - SkTCoincident<TCurve> fCoinEnd; - SkTSpanBounded<TCurve>* fBounded; + SkTCoincident<TCurve, OppCurve> fCoinStart; + SkTCoincident<TCurve, OppCurve> fCoinEnd; + SkTSpanBounded<OppCurve, TCurve>* fBounded; SkTSpan* fPrev; SkTSpan* fNext; SkDRect fBounds; @@ -180,29 +198,33 @@ private: bool fIsLinear; bool fIsLine; bool fDeleted; - PATH_OPS_DEBUG_CODE(SkTSect<TCurve>* fDebugSect); + SkDEBUGCODE_(SkTSect<TCurve, OppCurve>* fDebugSect); PATH_OPS_DEBUG_T_SECT_CODE(int fID); - friend class SkTSect<TCurve>; + friend class SkTSect<TCurve, OppCurve>; + friend class SkTSect<OppCurve, TCurve>; + friend class SkTSpan<OppCurve, TCurve>; }; -template<typename TCurve> +template<typename TCurve, typename OppCurve> class SkTSect { public: SkTSect(const TCurve& c PATH_OPS_DEBUG_T_SECT_PARAMS(int id)); - static void BinarySearch(SkTSect* sect1, SkTSect* sect2, SkIntersections* intersections); + static void BinarySearch(SkTSect* sect1, SkTSect<OppCurve, TCurve>* sect2, + SkIntersections* intersections); // for testing only - bool debugHasBounded(const SkTSpan<TCurve>* ) const; + bool debugHasBounded(const SkTSpan<OppCurve, TCurve>* ) const; - const SkTSect* debugOpp() const { - return PATH_OPS_DEBUG_RELEASE(fOppSect, NULL); + const SkTSect<OppCurve, TCurve>* debugOpp() const { + return SkDEBUGRELEASE(fOppSect, NULL); } - const SkTSpan<TCurve>* debugSpan(int id) const; - const SkTSpan<TCurve>* debugT(double t) const; + const SkTSpan<TCurve, OppCurve>* debugSpan(int id) const; + const SkTSpan<TCurve, OppCurve>* debugT(double t) const; void dump() const; - void dumpBoth(SkTSect* ) const; - void dumpBounds(int id) const; + void dumpBoth(SkTSect<OppCurve, TCurve>* ) const; + void dumpBounded(int id) const; + void dumpBounds() const; void dumpCoin() const; void dumpCoinCurves() const; void dumpCurves() const; @@ -215,82 +237,92 @@ private: kOneS2Set = 8 }; - SkTSpan<TCurve>* addFollowing(SkTSpan<TCurve>* prior); - void addForPerp(SkTSpan<TCurve>* span, double t); - SkTSpan<TCurve>* addOne(); + SkTSpan<TCurve, OppCurve>* addFollowing(SkTSpan<TCurve, OppCurve>* prior); + void addForPerp(SkTSpan<OppCurve, TCurve>* span, double t); + SkTSpan<TCurve, OppCurve>* addOne(); - SkTSpan<TCurve>* addSplitAt(SkTSpan<TCurve>* span, double t) { - SkTSpan<TCurve>* result = this->addOne(); + SkTSpan<TCurve, OppCurve>* addSplitAt(SkTSpan<TCurve, OppCurve>* span, double t) { + SkTSpan<TCurve, OppCurve>* result = this->addOne(); 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<TCurve>* boundsMax() const; - void coincidentCheck(SkTSect* sect2); + bool binarySearchCoin(SkTSect<OppCurve, TCurve>* , double tStart, double tStep, double* t, + double* oppT); + SkTSpan<TCurve, OppCurve>* boundsMax() const; + void coincidentCheck(SkTSect<OppCurve, TCurve>* sect2); bool coincidentHasT(double t); - void computePerpendiculars(SkTSect* sect2, SkTSpan<TCurve>* first, SkTSpan<TCurve>* last); - int countConsecutiveSpans(SkTSpan<TCurve>* first, SkTSpan<TCurve>** last) const; + int collapsed() const; + void computePerpendiculars(SkTSect<OppCurve, TCurve>* sect2, SkTSpan<TCurve, OppCurve>* first, + SkTSpan<TCurve, OppCurve>* last); + int countConsecutiveSpans(SkTSpan<TCurve, OppCurve>* first, + SkTSpan<TCurve, OppCurve>** last) const; int debugID() const { return PATH_OPS_DEBUG_T_SECT_RELEASE(fID, -1); } void deleteEmptySpans(); - void dumpCommon(const SkTSpan<TCurve>* ) const; - void dumpCommonCurves(const SkTSpan<TCurve>* ) const; - static int EndsEqual(const SkTSect* sect1, const SkTSect* sect2, SkIntersections* ); - SkTSpan<TCurve>* extractCoincident(SkTSect* sect2, SkTSpan<TCurve>* first, - SkTSpan<TCurve>* last); - SkTSpan<TCurve>* findCoincidentRun(SkTSpan<TCurve>* first, SkTSpan<TCurve>** lastPtr, - const SkTSect* sect2); - int intersects(SkTSpan<TCurve>* span, const SkTSect* opp, - SkTSpan<TCurve>* oppSpan, int* oppResult) const; - int linesIntersect(const SkTSpan<TCurve>* span, const SkTSect* opp, - const SkTSpan<TCurve>* oppSpan, SkIntersections* ) const; - void markSpanGone(SkTSpan<TCurve>* span); - bool matchedDirection(double t, const SkTSect* sect2, double t2) const; - void matchedDirCheck(double t, const SkTSect* sect2, double t2, + void dumpCommon(const SkTSpan<TCurve, OppCurve>* ) const; + void dumpCommonCurves(const SkTSpan<TCurve, OppCurve>* ) const; + static int EndsEqual(const SkTSect* sect1, const SkTSect<OppCurve, TCurve>* sect2, + SkIntersections* ); + SkTSpan<TCurve, OppCurve>* extractCoincident(SkTSect<OppCurve, TCurve>* sect2, + SkTSpan<TCurve, OppCurve>* first, + SkTSpan<TCurve, OppCurve>* last); + SkTSpan<TCurve, OppCurve>* findCoincidentRun(SkTSpan<TCurve, OppCurve>* first, + SkTSpan<TCurve, OppCurve>** lastPtr); + int intersects(SkTSpan<TCurve, OppCurve>* span, SkTSect<OppCurve, TCurve>* opp, + SkTSpan<OppCurve, TCurve>* oppSpan, int* oppResult); + int linesIntersect(SkTSpan<TCurve, OppCurve>* span, SkTSect<OppCurve, TCurve>* opp, + SkTSpan<OppCurve, TCurve>* oppSpan, SkIntersections* ); + void markSpanGone(SkTSpan<TCurve, OppCurve>* span); + bool matchedDirection(double t, const SkTSect<OppCurve, TCurve>* sect2, double t2) const; + void matchedDirCheck(double t, const SkTSect<OppCurve, TCurve>* sect2, double t2, bool* calcMatched, bool* oppMatched) const; - void mergeCoincidence(SkTSect* sect2); - SkTSpan<TCurve>* prev(SkTSpan<TCurve>* ) const; - void removeByPerpendicular(SkTSect* opp); + void mergeCoincidence(SkTSect<OppCurve, TCurve>* sect2); + SkTSpan<TCurve, OppCurve>* prev(SkTSpan<TCurve, OppCurve>* ) const; + void removeByPerpendicular(SkTSect<OppCurve, TCurve>* opp); void recoverCollapsed(); - void removeCoincident(SkTSpan<TCurve>* span, bool isBetween); - void removeAllBut(const SkTSpan<TCurve>* keep, SkTSpan<TCurve>* span, SkTSect* opp); - void removeSpan(SkTSpan<TCurve>* span); - void removeSpanRange(SkTSpan<TCurve>* first, SkTSpan<TCurve>* last); - void removeSpans(SkTSpan<TCurve>* span, SkTSect* opp); - SkTSpan<TCurve>* spanAtT(double t, SkTSpan<TCurve>** priorSpan); - SkTSpan<TCurve>* tail(); - void trim(SkTSpan<TCurve>* span, SkTSect* opp); - void unlinkSpan(SkTSpan<TCurve>* span); - bool updateBounded(SkTSpan<TCurve>* first, SkTSpan<TCurve>* last, SkTSpan<TCurve>* oppFirst); + void removeCoincident(SkTSpan<TCurve, OppCurve>* span, bool isBetween); + void removeAllBut(const SkTSpan<OppCurve, TCurve>* keep, SkTSpan<TCurve, OppCurve>* span, + SkTSect<OppCurve, TCurve>* opp); + void removeSpan(SkTSpan<TCurve, OppCurve>* span); + void removeSpanRange(SkTSpan<TCurve, OppCurve>* first, SkTSpan<TCurve, OppCurve>* last); + void removeSpans(SkTSpan<TCurve, OppCurve>* span, SkTSect<OppCurve, TCurve>* opp); + SkTSpan<TCurve, OppCurve>* spanAtT(double t, SkTSpan<TCurve, OppCurve>** priorSpan); + SkTSpan<TCurve, OppCurve>* tail(); + void trim(SkTSpan<TCurve, OppCurve>* span, SkTSect<OppCurve, TCurve>* opp); + void unlinkSpan(SkTSpan<TCurve, OppCurve>* span); + bool updateBounded(SkTSpan<TCurve, OppCurve>* first, SkTSpan<TCurve, OppCurve>* last, + SkTSpan<OppCurve, TCurve>* oppFirst); void validate() const; void validateBounded() const; const TCurve& fCurve; SkChunkAlloc fHeap; - SkTSpan<TCurve>* fHead; - SkTSpan<TCurve>* fCoincident; - SkTSpan<TCurve>* fDeleted; + SkTSpan<TCurve, OppCurve>* fHead; + SkTSpan<TCurve, OppCurve>* fCoincident; + SkTSpan<TCurve, OppCurve>* fDeleted; int fActiveCount; - PATH_OPS_DEBUG_CODE(SkTSect* fOppSect); + SkDEBUGCODE_(SkTSect<OppCurve, TCurve>* 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<TCurve>; // only used by debug id + friend class SkTSpan<TCurve, OppCurve>; + friend class SkTSpan<OppCurve, TCurve>; + friend class SkTSect<OppCurve, TCurve>; }; #define COINCIDENT_SPAN_COUNT 9 -template<typename TCurve> -void SkTCoincident<TCurve>::setPerp(const TCurve& c1, double t, - const SkDPoint& cPt, const TCurve& c2) { +template<typename TCurve, typename OppCurve> +void SkTCoincident<TCurve, OppCurve>::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; @@ -312,8 +344,9 @@ void SkTCoincident<TCurve>::setPerp(const TCurve& c1, double t, } } #if DEBUG_T_SECT - SkDebugf("%s cPt=(%1.9g,%1.9g) %s fPerpPt=(%1.9g,%1.9g)\n", __FUNCTION__, cPt.fX, cPt.fY, - cPt.approximatelyEqual(fPerpPt) ? "==" : "!=", fPerpPt.fX, fPerpPt.fY); + 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 fCoincident = cPt.approximatelyEqual(fPerpPt); #if DEBUG_T_SECT @@ -323,20 +356,21 @@ void SkTCoincident<TCurve>::setPerp(const TCurve& c1, double t, #endif } -template<typename TCurve> -void SkTSpan<TCurve>::addBounded(SkTSpan* span, SkChunkAlloc* heap) { - SkTSpanBounded<TCurve>* bounded = SkNEW_PLACEMENT(heap->allocThrow( - sizeof(SkTSpanBounded<TCurve>)), SkTSpanBounded<TCurve>); +template<typename TCurve, typename OppCurve> +void SkTSpan<TCurve, OppCurve>::addBounded(SkTSpan<OppCurve, TCurve>* span, SkChunkAlloc* heap) { + SkTSpanBounded<OppCurve, TCurve>* bounded = SkNEW_PLACEMENT(heap->allocThrow( + sizeof(SkTSpanBounded<OppCurve, TCurve>)), (SkTSpanBounded<OppCurve, TCurve>)); bounded->fBounded = span; bounded->fNext = fBounded; fBounded = bounded; } -template<typename TCurve> -SkTSpan<TCurve>* SkTSect<TCurve>::addFollowing(SkTSpan<TCurve>* prior) { - SkTSpan<TCurve>* result = this->addOne(); +template<typename TCurve, typename OppCurve> +SkTSpan<TCurve, OppCurve>* SkTSect<TCurve, OppCurve>::addFollowing( + SkTSpan<TCurve, OppCurve>* prior) { + SkTSpan<TCurve, OppCurve>* result = this->addOne(); result->fStartT = prior ? prior->fEndT : 0; - SkTSpan<TCurve>* next = prior ? prior->fNext : fHead; + SkTSpan<TCurve, OppCurve>* next = prior ? prior->fNext : fHead; result->fEndT = next ? next->fStartT : 1; result->fPrev = prior; result->fNext = next; @@ -352,11 +386,11 @@ SkTSpan<TCurve>* SkTSect<TCurve>::addFollowing(SkTSpan<TCurve>* prior) { return result; } -template<typename TCurve> -void SkTSect<TCurve>::addForPerp(SkTSpan<TCurve>* span, double t) { +template<typename TCurve, typename OppCurve> +void SkTSect<TCurve, OppCurve>::addForPerp(SkTSpan<OppCurve, TCurve>* span, double t) { if (!span->hasOppT(t)) { - SkTSpan<TCurve>* priorSpan; - SkTSpan<TCurve>* opp = this->spanAtT(t, &priorSpan); + SkTSpan<TCurve, OppCurve>* priorSpan; + SkTSpan<TCurve, OppCurve>* opp = this->spanAtT(t, &priorSpan); if (!opp) { opp = this->addFollowing(priorSpan); #if DEBUG_PERP @@ -373,22 +407,24 @@ void SkTSect<TCurve>::addForPerp(SkTSpan<TCurve>* span, double t) { span->addBounded(opp, &fHeap); } this->validate(); +#if DEBUG_T_SECT span->validatePerpT(t); +#endif } -template<typename TCurve> -double SkTSpan<TCurve>::closestBoundedT(const SkDPoint& pt) const { +template<typename TCurve, typename OppCurve> +double SkTSpan<TCurve, OppCurve>::closestBoundedT(const SkDPoint& pt) const { double result = -1; double closest = FLT_MAX; - const SkTSpanBounded<TCurve>* testBounded = fBounded; + const SkTSpanBounded<OppCurve, TCurve>* testBounded = fBounded; while (testBounded) { - const SkTSpan* test = testBounded->fBounded; + const SkTSpan<OppCurve, TCurve>* test = testBounded->fBounded; double startDist = test->fPart[0].distanceSquared(pt); if (closest > startDist) { closest = startDist; result = test->fStartT; } - double endDist = test->fPart[TCurve::kPointLast].distanceSquared(pt); + double endDist = test->fPart[OppCurve::kPointLast].distanceSquared(pt); if (closest > endDist) { closest = endDist; result = test->fEndT; @@ -400,8 +436,8 @@ double SkTSpan<TCurve>::closestBoundedT(const SkDPoint& pt) const { } #ifdef SK_DEBUG -template<typename TCurve> -bool SkTSpan<TCurve>::debugIsBefore(const SkTSpan* span) const { +template<typename TCurve, typename OppCurve> +bool SkTSpan<TCurve, OppCurve>::debugIsBefore(const SkTSpan* span) const { const SkTSpan* work = this; do { if (span == work) { @@ -412,8 +448,8 @@ bool SkTSpan<TCurve>::debugIsBefore(const SkTSpan* span) const { } #endif -template<typename TCurve> -bool SkTSpan<TCurve>::contains(double t) const { +template<typename TCurve, typename OppCurve> +bool SkTSpan<TCurve, OppCurve>::contains(double t) const { const SkTSpan* work = this; do { if (between(work->fStartT, t, work->fEndT)) { @@ -423,16 +459,17 @@ bool SkTSpan<TCurve>::contains(double t) const { return false; } -template<typename TCurve> -const SkTSect<TCurve>* SkTSpan<TCurve>::debugOpp() const { - return PATH_OPS_DEBUG_RELEASE(fDebugSect->debugOpp(), NULL); +template<typename TCurve, typename OppCurve> +const SkTSect<OppCurve, TCurve>* SkTSpan<TCurve, OppCurve>::debugOpp() const { + return SkDEBUGRELEASE(fDebugSect->debugOpp(), NULL); } -template<typename TCurve> -SkTSpan<TCurve>* SkTSpan<TCurve>::findOppSpan(const SkTSpan* opp) const { - SkTSpanBounded<TCurve>* bounded = fBounded; +template<typename TCurve, typename OppCurve> +SkTSpan<OppCurve, TCurve>* SkTSpan<TCurve, OppCurve>::findOppSpan( + const SkTSpan<OppCurve, TCurve>* opp) const { + SkTSpanBounded<OppCurve, TCurve>* bounded = fBounded; while (bounded) { - SkTSpan* test = bounded->fBounded; + SkTSpan<OppCurve, TCurve>* test = bounded->fBounded; if (opp == test) { return test; } @@ -445,8 +482,9 @@ SkTSpan<TCurve>* SkTSpan<TCurve>::findOppSpan(const SkTSpan* opp) const { // 1 if hulls intersect // 2 if hulls only share a common endpoint // -1 if linear and further checking is required -template<typename TCurve> -int SkTSpan<TCurve>::hullCheck(const SkTSpan* opp, bool* start, bool* oppStart) { +template<typename TCurve, typename OppCurve> +int SkTSpan<TCurve, OppCurve>::hullCheck(const SkTSpan<OppCurve, TCurve>* opp, + bool* start, bool* oppStart) { if (fIsLinear) { return -1; } @@ -472,8 +510,9 @@ int SkTSpan<TCurve>::hullCheck(const SkTSpan* opp, bool* start, bool* oppStart) // 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<typename TCurve> -int SkTSpan<TCurve>::hullsIntersect(SkTSpan* opp, bool* start, bool* oppStart) { +template<typename TCurve, typename OppCurve> +int SkTSpan<TCurve, OppCurve>::hullsIntersect(SkTSpan<OppCurve, TCurve>* opp, + bool* start, bool* oppStart) { if (!fBounds.intersects(opp->fBounds)) { return 0; } @@ -488,8 +527,8 @@ int SkTSpan<TCurve>::hullsIntersect(SkTSpan* opp, bool* start, bool* oppStart) { return -1; } -template<typename TCurve> -void SkTSpan<TCurve>::init(const TCurve& c) { +template<typename TCurve, typename OppCurve> +void SkTSpan<TCurve, OppCurve>::init(const TCurve& c) { fPrev = fNext = NULL; fStartT = 0; fEndT = 1; @@ -497,8 +536,8 @@ void SkTSpan<TCurve>::init(const TCurve& c) { resetBounds(c); } -template<typename TCurve> -void SkTSpan<TCurve>::initBounds(const TCurve& c) { +template<typename TCurve, typename OppCurve> +void SkTSpan<TCurve, OppCurve>::initBounds(const TCurve& c) { fPart = c.subDivide(fStartT, fEndT); fBounds.setBounds(fPart); fCoinStart.init(); @@ -514,8 +553,8 @@ void SkTSpan<TCurve>::initBounds(const TCurve& c) { #endif } -template<typename TCurve> -bool SkTSpan<TCurve>::linearsIntersect(SkTSpan* span) { +template<typename TCurve, typename OppCurve> +bool SkTSpan<TCurve, OppCurve>::linearsIntersect(SkTSpan<OppCurve, TCurve>* span) { int result = this->linearIntersects(span->fPart); if (result <= 1) { return SkToBool(result); @@ -526,16 +565,16 @@ bool SkTSpan<TCurve>::linearsIntersect(SkTSpan* span) { return SkToBool(result); } -template<typename TCurve> -double SkTSpan<TCurve>::linearT(const SkDPoint& pt) const { +template<typename TCurve, typename OppCurve> +double SkTSpan<TCurve, OppCurve>::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<typename TCurve> -int SkTSpan<TCurve>::linearIntersects(const TCurve& q2) const { +template<typename TCurve, typename OppCurve> +int SkTSpan<TCurve, OppCurve>::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()) { @@ -559,7 +598,7 @@ int SkTSpan<TCurve>::linearIntersects(const TCurve& q2) const { 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 < TCurve::kPointCount; ++n) { + 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))); @@ -581,33 +620,33 @@ int SkTSpan<TCurve>::linearIntersects(const TCurve& q2) const { return 0; } -template<typename TCurve> -bool SkTSpan<TCurve>::onlyEndPointsInCommon(const SkTSpan* opp, bool* start, bool* oppStart, - bool* ptsInCommon) { +template<typename TCurve, typename OppCurve> +bool SkTSpan<TCurve, OppCurve>::onlyEndPointsInCommon(const SkTSpan<OppCurve, TCurve>* 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[TCurve::kPointLast] == fPart[0]) { + } else if (opp->fPart[OppCurve::kPointLast] == fPart[0]) { *start = true; *oppStart = false; - } else if (opp->fPart[TCurve::kPointLast] == fPart[TCurve::kPointLast]) { + } else if (opp->fPart[OppCurve::kPointLast] == fPart[TCurve::kPointLast]) { *start = *oppStart = false; } else { *ptsInCommon = false; return false; } *ptsInCommon = true; - const SkDPoint* o1Pts[TCurve::kPointCount - 1], * o2Pts[TCurve::kPointCount - 1]; + const SkDPoint* otherPts[TCurve::kPointCount - 1], * oppOtherPts[OppCurve::kPointCount - 1]; int baseIndex = *start ? 0 : TCurve::kPointLast; - fPart.otherPts(baseIndex, o1Pts); - opp->fPart.otherPts(*oppStart ? 0 : TCurve::kPointLast, o2Pts); + 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(o1Pts); ++o1) { - SkDVector v1 = *o1Pts[o1] - base; - for (int o2 = 0; o2 < (int) SK_ARRAY_COUNT(o2Pts); ++o2) { - SkDVector v2 = *o2Pts[o2] - base; + 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; } @@ -616,11 +655,11 @@ bool SkTSpan<TCurve>::onlyEndPointsInCommon(const SkTSpan* opp, bool* start, boo return true; } -template<typename TCurve> -SkTSpan<TCurve>* SkTSpan<TCurve>::oppT(double t) const { - SkTSpanBounded<TCurve>* bounded = fBounded; +template<typename TCurve, typename OppCurve> +SkTSpan<OppCurve, TCurve>* SkTSpan<TCurve, OppCurve>::oppT(double t) const { + SkTSpanBounded<OppCurve, TCurve>* bounded = fBounded; while (bounded) { - SkTSpan* test = bounded->fBounded; + SkTSpan<OppCurve, TCurve>* test = bounded->fBounded; if (between(test->fStartT, t, test->fEndT)) { return test; } @@ -629,26 +668,26 @@ SkTSpan<TCurve>* SkTSpan<TCurve>::oppT(double t) const { return NULL; } -template<typename TCurve> -bool SkTSpan<TCurve>::removeAllBounded() { +template<typename TCurve, typename OppCurve> +bool SkTSpan<TCurve, OppCurve>::removeAllBounded() { bool deleteSpan = false; - SkTSpanBounded<TCurve>* bounded = fBounded; + SkTSpanBounded<OppCurve, TCurve>* bounded = fBounded; while (bounded) { - SkTSpan* opp = bounded->fBounded; + SkTSpan<OppCurve, TCurve>* opp = bounded->fBounded; deleteSpan |= opp->removeBounded(this); bounded = bounded->fNext; } return deleteSpan; } -template<typename TCurve> -bool SkTSpan<TCurve>::removeBounded(const SkTSpan* opp) { +template<typename TCurve, typename OppCurve> +bool SkTSpan<TCurve, OppCurve>::removeBounded(const SkTSpan<OppCurve, TCurve>* opp) { if (fHasPerp) { bool foundStart = false; bool foundEnd = false; - SkTSpanBounded<TCurve>* bounded = fBounded; + SkTSpanBounded<OppCurve, TCurve>* bounded = fBounded; while (bounded) { - SkTSpan* test = bounded->fBounded; + SkTSpan<OppCurve, TCurve>* test = bounded->fBounded; if (opp != test) { foundStart |= between(test->fStartT, fCoinStart.perpT(), test->fEndT); foundEnd |= between(test->fStartT, fCoinEnd.perpT(), test->fEndT); @@ -661,10 +700,10 @@ bool SkTSpan<TCurve>::removeBounded(const SkTSpan* opp) { fCoinEnd.init(); } } - SkTSpanBounded<TCurve>* bounded = fBounded; - SkTSpanBounded<TCurve>* prev = NULL; + SkTSpanBounded<OppCurve, TCurve>* bounded = fBounded; + SkTSpanBounded<OppCurve, TCurve>* prev = NULL; while (bounded) { - SkTSpanBounded<TCurve>* boundedNext = bounded->fNext; + SkTSpanBounded<OppCurve, TCurve>* boundedNext = bounded->fNext; if (opp == bounded->fBounded) { if (prev) { prev->fNext = boundedNext; @@ -681,8 +720,8 @@ bool SkTSpan<TCurve>::removeBounded(const SkTSpan* opp) { return false; } -template<typename TCurve> -bool SkTSpan<TCurve>::splitAt(SkTSpan* work, double t, SkChunkAlloc* heap) { +template<typename TCurve, typename OppCurve> +bool SkTSpan<TCurve, OppCurve>::splitAt(SkTSpan* work, double t, SkChunkAlloc* heap) { fStartT = t; fEndT = work->fEndT; if (fStartT == fEndT) { @@ -703,7 +742,7 @@ bool SkTSpan<TCurve>::splitAt(SkTSpan* work, double t, SkChunkAlloc* heap) { if (fNext) { fNext->fPrev = this; } - SkTSpanBounded<TCurve>* bounded = work->fBounded; + SkTSpanBounded<OppCurve, TCurve>* bounded = work->fBounded; fBounded = NULL; while (bounded) { this->addBounded(bounded->fBounded, heap); @@ -717,8 +756,8 @@ bool SkTSpan<TCurve>::splitAt(SkTSpan* work, double t, SkChunkAlloc* heap) { return true; } -template<typename TCurve> -void SkTSpan<TCurve>::validate() const { +template<typename TCurve, typename OppCurve> +void SkTSpan<TCurve, OppCurve>::validate() const { #if DEBUG_T_SECT SkASSERT(fNext == NULL || fNext != fPrev); SkASSERT(fNext == NULL || this == fNext->fPrev); @@ -743,12 +782,12 @@ void SkTSpan<TCurve>::validate() const { #endif } -template<typename TCurve> -void SkTSpan<TCurve>::validateBounded() const { +template<typename TCurve, typename OppCurve> +void SkTSpan<TCurve, OppCurve>::validateBounded() const { #if DEBUG_VALIDATE - const SkTSpanBounded<TCurve>* testBounded = fBounded; + const SkTSpanBounded<OppCurve, TCurve>* testBounded = fBounded; while (testBounded) { - const SkTSpan* overlap = testBounded->fBounded; + SkDEBUGCODE_(const SkTSpan<OppCurve, TCurve>* overlap = testBounded->fBounded); SkASSERT(!overlap->fDeleted); SkASSERT(((this->debugID() ^ overlap->debugID()) & 1) == 1); SkASSERT(overlap->findOppSpan(this)); @@ -757,33 +796,29 @@ void SkTSpan<TCurve>::validateBounded() const { #endif } -template<typename TCurve> -void SkTSpan<TCurve>::validatePerpT(double oppT) const { -#if DEBUG_VALIDATE - const SkTSpanBounded<TCurve>* testBounded = fBounded; +template<typename TCurve, typename OppCurve> +void SkTSpan<TCurve, OppCurve>::validatePerpT(double oppT) const { + const SkTSpanBounded<OppCurve, TCurve>* testBounded = fBounded; while (testBounded) { - const SkTSpan* overlap = testBounded->fBounded; + const SkTSpan<OppCurve, TCurve>* overlap = testBounded->fBounded; if (between(overlap->fStartT, oppT, overlap->fEndT)) { return; } testBounded = testBounded->fNext; } SkASSERT(0); -#endif } -template<typename TCurve> -void SkTSpan<TCurve>::validatePerpPt(double t, const SkDPoint& pt) const { -#if DEBUG_T_SECT - PATH_OPS_DEBUG_CODE(SkASSERT(fDebugSect->fOppSect->fCurve.ptAtT(t) == pt)); -#endif +template<typename TCurve, typename OppCurve> +void SkTSpan<TCurve, OppCurve>::validatePerpPt(double t, const SkDPoint& pt) const { + SkASSERT(fDebugSect->fOppSect->fCurve.ptAtT(t) == pt); } -template<typename TCurve> -SkTSect<TCurve>::SkTSect(const TCurve& c PATH_OPS_DEBUG_T_SECT_PARAMS(int id)) +template<typename TCurve, typename OppCurve> +SkTSect<TCurve, OppCurve>::SkTSect(const TCurve& c PATH_OPS_DEBUG_T_SECT_PARAMS(int id)) : fCurve(c) - , fHeap(sizeof(SkTSpan<TCurve>) * 4) + , fHeap(sizeof(SkTSpan<TCurve, OppCurve>) * 4) , fCoincident(NULL) , fDeleted(NULL) , fActiveCount(0) @@ -795,15 +830,16 @@ SkTSect<TCurve>::SkTSect(const TCurve& c PATH_OPS_DEBUG_T_SECT_PARAMS(int id)) fHead->init(c); } -template<typename TCurve> -SkTSpan<TCurve>* SkTSect<TCurve>::addOne() { - SkTSpan<TCurve>* result; +template<typename TCurve, typename OppCurve> +SkTSpan<TCurve, OppCurve>* SkTSect<TCurve, OppCurve>::addOne() { + SkTSpan<TCurve, OppCurve>* result; if (fDeleted) { result = fDeleted; result->reset(); fDeleted = result->fNext; } else { - result = SkNEW_PLACEMENT(fHeap.allocThrow(sizeof(SkTSpan<TCurve>)), SkTSpan<TCurve>); + result = SkNEW_PLACEMENT(fHeap.allocThrow(sizeof(SkTSpan<TCurve, OppCurve>)), + (SkTSpan<TCurve, OppCurve>)); result->fBounded = NULL; #if DEBUG_T_SECT ++fDebugAllocatedCount; @@ -813,21 +849,21 @@ SkTSpan<TCurve>* SkTSect<TCurve>::addOne() { result->fDeleted = false; ++fActiveCount; PATH_OPS_DEBUG_T_SECT_CODE(result->fID = fDebugCount++ * 2 + fID); - PATH_OPS_DEBUG_CODE(result->fDebugSect = this); + SkDEBUGCODE(result->fDebugSect = this); return result; } -template<typename TCurve> -bool SkTSect<TCurve>::binarySearchCoin(SkTSect* sect2, double tStart, double tStep, - double* resultT, double* oppT) { - SkTSpan<TCurve> work; +template<typename TCurve, typename OppCurve> +bool SkTSect<TCurve, OppCurve>::binarySearchCoin(SkTSect<OppCurve, TCurve>* sect2, double tStart, + double tStep, double* resultT, double* oppT) { + SkTSpan<TCurve, OppCurve> work; double result = work.fStartT = work.fEndT = tStart; - PATH_OPS_DEBUG_CODE(work.fDebugSect = this); + SkDEBUGCODE(work.fDebugSect = this); SkDPoint last = fCurve.ptAtT(tStart); SkDPoint oppPt; bool flip = false; SkDEBUGCODE(bool down = tStep < 0); - const TCurve& opp = sect2->fCurve; + const OppCurve& opp = sect2->fCurve; do { tStep *= 0.5; work.fStartT += tStep; @@ -867,7 +903,7 @@ bool SkTSect<TCurve>::binarySearchCoin(SkTSect* sect2, double tStart, double tSt } if (oppPt.approximatelyEqual(opp[0])) { *oppT = 0; - } else if (oppPt.approximatelyEqual(opp[TCurve::kPointLast])) { + } else if (oppPt.approximatelyEqual(opp[OppCurve::kPointLast])) { *oppT = 1; } *resultT = result; @@ -877,25 +913,26 @@ bool SkTSect<TCurve>::binarySearchCoin(SkTSect* sect2, double tStart, double tSt // 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<typename TCurve> -SkTSpan<TCurve>* SkTSect<TCurve>::boundsMax() const { - SkTSpan<TCurve>* test = fHead; - SkTSpan<TCurve>* largest = fHead; +template<typename TCurve, typename OppCurve> +SkTSpan<TCurve, OppCurve>* SkTSect<TCurve, OppCurve>::boundsMax() const { + SkTSpan<TCurve, OppCurve>* test = fHead; + SkTSpan<TCurve, OppCurve>* 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<typename TCurve> -void SkTSect<TCurve>::coincidentCheck(SkTSect* sect2) { - SkTSpan<TCurve>* first = fHead; - SkTSpan<TCurve>* last, * next; +template<typename TCurve, typename OppCurve> +void SkTSect<TCurve, OppCurve>::coincidentCheck(SkTSect<OppCurve, TCurve>* sect2) { + SkTSpan<TCurve, OppCurve>* first = fHead; + SkTSpan<TCurve, OppCurve>* last, * next; do { int consecutive = this->countConsecutiveSpans(first, &last); next = last->fNext; @@ -908,16 +945,16 @@ void SkTSect<TCurve>::coincidentCheck(SkTSect* sect2) { this->validate(); sect2->validate(); // check to see if a range of points are on the curve - SkTSpan<TCurve>* coinStart = first; + SkTSpan<TCurve, OppCurve>* coinStart = first; do { coinStart = this->extractCoincident(sect2, coinStart, last); } while (coinStart && !last->fDeleted); } while ((first = next)); } -template<typename TCurve> -bool SkTSect<TCurve>::coincidentHasT(double t) { - SkTSpan<TCurve>* test = fCoincident; +template<typename TCurve, typename OppCurve> +bool SkTSect<TCurve, OppCurve>::coincidentHasT(double t) { + SkTSpan<TCurve, OppCurve>* test = fCoincident; while (test) { if (between(test->fStartT, t, test->fEndT)) { return true; @@ -927,12 +964,25 @@ bool SkTSect<TCurve>::coincidentHasT(double t) { return false; } -template<typename TCurve> -void SkTSect<TCurve>::computePerpendiculars(SkTSect* sect2, SkTSpan<TCurve>* first, - SkTSpan<TCurve>* last) { - const TCurve& opp = sect2->fCurve; - SkTSpan<TCurve>* work = first; - SkTSpan<TCurve>* prior = NULL; +template<typename TCurve, typename OppCurve> +int SkTSect<TCurve, OppCurve>::collapsed() const { + int result = 0; + const SkTSpan<TCurve, OppCurve>* test = fHead; + while (test) { + if (test->fCollapsed) { + ++result; + } + test = test->next(); + } + return result; +} + +template<typename TCurve, typename OppCurve> +void SkTSect<TCurve, OppCurve>::computePerpendiculars(SkTSect<OppCurve, TCurve>* sect2, + SkTSpan<TCurve, OppCurve>* first, SkTSpan<TCurve, OppCurve>* last) { + const OppCurve& opp = sect2->fCurve; + SkTSpan<TCurve, OppCurve>* work = first; + SkTSpan<TCurve, OppCurve>* prior = NULL; do { if (!work->fHasPerp && !work->fCollapsed) { if (prior) { @@ -968,13 +1018,13 @@ void SkTSect<TCurve>::computePerpendiculars(SkTSect* sect2, SkTSpan<TCurve>* fir } while (true); } -template<typename TCurve> -int SkTSect<TCurve>::countConsecutiveSpans(SkTSpan<TCurve>* first, - SkTSpan<TCurve>** lastPtr) const { +template<typename TCurve, typename OppCurve> +int SkTSect<TCurve, OppCurve>::countConsecutiveSpans(SkTSpan<TCurve, OppCurve>* first, + SkTSpan<TCurve, OppCurve>** lastPtr) const { int consecutive = 1; - SkTSpan<TCurve>* last = first; + SkTSpan<TCurve, OppCurve>* last = first; do { - SkTSpan<TCurve>* next = last->fNext; + SkTSpan<TCurve, OppCurve>* next = last->fNext; if (!next) { break; } @@ -988,9 +1038,9 @@ int SkTSect<TCurve>::countConsecutiveSpans(SkTSpan<TCurve>* first, return consecutive; } -template<typename TCurve> -bool SkTSect<TCurve>::debugHasBounded(const SkTSpan<TCurve>* span) const { - const SkTSpan<TCurve>* test = fHead; +template<typename TCurve, typename OppCurve> +bool SkTSect<TCurve, OppCurve>::debugHasBounded(const SkTSpan<OppCurve, TCurve>* span) const { + const SkTSpan<TCurve, OppCurve>* test = fHead; if (!test) { return false; } @@ -1002,10 +1052,10 @@ bool SkTSect<TCurve>::debugHasBounded(const SkTSpan<TCurve>* span) const { return false; } -template<typename TCurve> -void SkTSect<TCurve>::deleteEmptySpans() { - SkTSpan<TCurve>* test; - SkTSpan<TCurve>* next = fHead; +template<typename TCurve, typename OppCurve> +void SkTSect<TCurve, OppCurve>::deleteEmptySpans() { + SkTSpan<TCurve, OppCurve>* test; + SkTSpan<TCurve, OppCurve>* next = fHead; while ((test = next)) { next = test->fNext; if (!test->fBounded) { @@ -1014,10 +1064,11 @@ void SkTSect<TCurve>::deleteEmptySpans() { } } -template<typename TCurve> -SkTSpan<TCurve>* SkTSect<TCurve>::extractCoincident(SkTSect* sect2, SkTSpan<TCurve>* first, - SkTSpan<TCurve>* last) { - first = findCoincidentRun(first, &last, sect2); +template<typename TCurve, typename OppCurve> +SkTSpan<TCurve, OppCurve>* SkTSect<TCurve, OppCurve>::extractCoincident( + SkTSect<OppCurve, TCurve>* sect2, + SkTSpan<TCurve, OppCurve>* first, SkTSpan<TCurve, OppCurve>* last) { + first = findCoincidentRun(first, &last); if (!first) { return NULL; } @@ -1025,24 +1076,25 @@ SkTSpan<TCurve>* SkTSect<TCurve>::extractCoincident(SkTSect* sect2, SkTSpan<TCur double startT = first->fStartT; double oppStartT SK_INIT_TO_AVOID_WARNING; double oppEndT SK_INIT_TO_AVOID_WARNING; - SkTSpan<TCurve>* prev = first->fPrev; + SkTSpan<TCurve, OppCurve>* prev = first->fPrev; SkASSERT(first->fCoinStart.isCoincident()); - SkTSpan<TCurve>* oppFirst = first->findOppT(first->fCoinStart.perpT()); + SkTSpan<OppCurve, TCurve>* oppFirst = first->findOppT(first->fCoinStart.perpT()); SkASSERT(last->fCoinEnd.isCoincident()); bool oppMatched = first->fCoinStart.perpT() < first->fCoinEnd.perpT(); double coinStart; SkDEBUGCODE(double coinEnd); + SkTSpan<OppCurve, TCurve>* cutFirst; if (prev && prev->fEndT == startT && this->binarySearchCoin(sect2, startT, prev->fStartT - startT, &coinStart, &oppStartT) - && prev->fStartT < coinStart && coinStart < startT) { - oppFirst = prev->findOppT(oppStartT); // find opp start before splitting prev - SkASSERT(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<TCurve>* oppHalf = sect2->addSplitAt(oppFirst, oppStartT); + SkTSpan<OppCurve, TCurve>* oppHalf = sect2->addSplitAt(oppFirst, oppStartT); if (oppMatched) { oppFirst->fCoinEnd.markCoincident(); oppHalf->markCoincident(); @@ -1056,7 +1108,8 @@ SkTSpan<TCurve>* SkTSect<TCurve>::extractCoincident(SkTSect* sect2, SkTSpan<TCur SkDEBUGCODE(coinStart = first->fStartT); SkDEBUGCODE(oppStartT = oppMatched ? oppFirst->fStartT : oppFirst->fEndT); } - SkTSpan<TCurve>* oppLast; + // FIXME: incomplete : if we're not at the end, find end of coin + SkTSpan<OppCurve, TCurve>* oppLast; SkASSERT(last->fCoinEnd.isCoincident()); oppLast = last->findOppT(last->fCoinEnd.perpT()); SkDEBUGCODE(coinEnd = last->fEndT); @@ -1073,8 +1126,8 @@ SkTSpan<TCurve>* SkTSect<TCurve>::extractCoincident(SkTSect* sect2, SkTSpan<TCur // reduce coincident runs to single entries this->validate(); sect2->validate(); - bool deleteThisSpan = this->updateBounded(first, last, oppFirst); - bool deleteSect2Span = sect2->updateBounded(oppFirst, oppLast, first); + 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; @@ -1096,10 +1149,8 @@ SkTSpan<TCurve>* SkTSect<TCurve>::extractCoincident(SkTSect* sect2, SkTSpan<TCur last = first->fNext; this->removeCoincident(first, false); sect2->removeCoincident(oppFirst, true); - if (deleteThisSpan) { + if (deleteEmptySpans) { this->deleteEmptySpans(); - } - if (deleteSect2Span) { sect2->deleteEmptySpans(); } this->validate(); @@ -1107,17 +1158,19 @@ SkTSpan<TCurve>* SkTSect<TCurve>::extractCoincident(SkTSect* sect2, SkTSpan<TCur return last && !last->fDeleted ? last : NULL; } -template<typename TCurve> -SkTSpan<TCurve>* SkTSect<TCurve>::findCoincidentRun(SkTSpan<TCurve>* first, - SkTSpan<TCurve>** lastPtr, const SkTSect* sect2) { - SkTSpan<TCurve>* work = first; - SkTSpan<TCurve>* lastCandidate = NULL; +template<typename TCurve, typename OppCurve> +SkTSpan<TCurve, OppCurve>* SkTSect<TCurve, OppCurve>::findCoincidentRun( + SkTSpan<TCurve, OppCurve>* first, SkTSpan<TCurve, OppCurve>** lastPtr) { + SkTSpan<TCurve, OppCurve>* work = first; + SkTSpan<TCurve, OppCurve>* lastCandidate = NULL; first = NULL; // find the first fully coincident span do { if (work->fCoinStart.isCoincident()) { +#if DEBUG_T_SECT work->validatePerpT(work->fCoinStart.perpT()); work->validatePerpPt(work->fCoinStart.perpT(), work->fCoinStart.perpPt()); +#endif SkASSERT(work->hasOppT(work->fCoinStart.perpT())); if (!work->fCoinEnd.isCoincident()) { break; @@ -1126,6 +1179,9 @@ SkTSpan<TCurve>* SkTSect<TCurve>::findCoincidentRun(SkTSpan<TCurve>* first, if (!first) { first = work; } + } else if (first && work->fCollapsed) { + *lastPtr = lastCandidate; + return first; } else { lastCandidate = NULL; SkASSERT(!first); @@ -1142,9 +1198,10 @@ SkTSpan<TCurve>* SkTSect<TCurve>::findCoincidentRun(SkTSpan<TCurve>* first, return first; } -template<typename TCurve> -int SkTSect<TCurve>::intersects(SkTSpan<TCurve>* span, const SkTSect* opp, - SkTSpan<TCurve>* oppSpan, int* oppResult) const { +template<typename TCurve, typename OppCurve> +int SkTSect<TCurve, OppCurve>::intersects(SkTSpan<TCurve, OppCurve>* span, + SkTSect<OppCurve, TCurve>* opp, + SkTSpan<OppCurve, TCurve>* oppSpan, int* oppResult) { bool spanStart, oppStart; int hullResult = span->hullsIntersect(oppSpan, &spanStart, &oppStart); if (hullResult >= 0) { @@ -1194,21 +1251,22 @@ int SkTSect<TCurve>::intersects(SkTSpan<TCurve>* span, const SkTSect* opp, // 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<typename TCurve> -int SkTSect<TCurve>::linesIntersect(const SkTSpan<TCurve>* span, const SkTSect* opp, - const SkTSpan<TCurve>* oppSpan, SkIntersections* i) const { +template<typename TCurve, typename OppCurve> +int SkTSect<TCurve, OppCurve>::linesIntersect(SkTSpan<TCurve, OppCurve>* span, + SkTSect<OppCurve, TCurve>* opp, + SkTSpan<OppCurve, TCurve>* oppSpan, SkIntersections* i) { SkIntersections thisRayI, oppRayI; SkDLine thisLine = {{ span->fPart[0], span->fPart[TCurve::kPointLast] }}; - SkDLine oppLine = {{ oppSpan->fPart[0], oppSpan->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; + } do { - if (!thisRayI.intersectRay(opp->fCurve, thisLine)) { - return 0; - } - if (!oppRayI.intersectRay(this->fCurve, oppLine)) { - return 0; - } // pick the closest pair of points double closest = DBL_MAX; int closeIndex SK_INIT_TO_AVOID_WARNING; @@ -1230,7 +1288,7 @@ int SkTSect<TCurve>::linesIntersect(const SkTSpan<TCurve>* span, const SkTSect* } } if (closest == DBL_MAX) { - return 0; + break; } const SkDPoint& oppIPt = thisRayI.pt(oppCloseIndex); const SkDPoint& iPt = oppRayI.pt(closeIndex); @@ -1242,20 +1300,88 @@ int SkTSect<TCurve>::linesIntersect(const SkTSpan<TCurve>* span, const SkTSect* } double distSq = oppIPt.distanceSquared(iPt); if (bestDistSq < distSq || ++loopCount > 5) { - break; + return 0; } bestDistSq = distSq; - thisLine[0] = fCurve.ptAtT(oppRayI[0][closeIndex]); - thisLine[1] = thisLine[0] + fCurve.dxdyAtT(oppRayI[0][closeIndex]); - oppLine[0] = opp->fCurve.ptAtT(thisRayI[0][oppCloseIndex]); - oppLine[1] = oppLine[0] + opp->fCurve.dxdyAtT(thisRayI[0][oppCloseIndex]); + 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); - return false; + // convergence may fail if the curves are nearly coincident + SkTCoincident<OppCurve, TCurve> 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) { + SkTSwap(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<TCurve, OppCurve> 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<TCurve, OppCurve> 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<TCurve, OppCurve> 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); + SkDVector perpW = workPt - coinW.perpPt(); + if ((perpS.dot(perpW) >= 0) == (tStep < 0)) { + tStep = -tStep; + } + } while (!workPt.approximatelyEqual(coinW.perpPt())); + double oppTTest = coinW.perpT(); + if (!opp->fHead->contains(oppTTest)) { + return 0; + } + i->setMax(1); + i->insert(workT, oppTTest, workPt); + return 1; } -template<typename TCurve> -void SkTSect<TCurve>::markSpanGone(SkTSpan<TCurve>* span) { +template<typename TCurve, typename OppCurve> +void SkTSect<TCurve, OppCurve>::markSpanGone(SkTSpan<TCurve, OppCurve>* span) { --fActiveCount; span->fNext = fDeleted; fDeleted = span; @@ -1263,16 +1389,17 @@ void SkTSect<TCurve>::markSpanGone(SkTSpan<TCurve>* span) { span->fDeleted = true; } -template<typename TCurve> -bool SkTSect<TCurve>::matchedDirection(double t, const SkTSect* sect2, double t2) const { +template<typename TCurve, typename OppCurve> +bool SkTSect<TCurve, OppCurve>::matchedDirection(double t, const SkTSect<OppCurve, TCurve>* sect2, + double t2) const { SkDVector dxdy = this->fCurve.dxdyAtT(t); SkDVector dxdy2 = sect2->fCurve.dxdyAtT(t2); return dxdy.dot(dxdy2) >= 0; } -template<typename TCurve> -void SkTSect<TCurve>::matchedDirCheck(double t, const SkTSect* sect2, double t2, - bool* calcMatched, bool* oppMatched) const { +template<typename TCurve, typename OppCurve> +void SkTSect<TCurve, OppCurve>::matchedDirCheck(double t, const SkTSect<OppCurve, TCurve>* sect2, + double t2, bool* calcMatched, bool* oppMatched) const { if (*calcMatched) { SkASSERT(*oppMatched == this->matchedDirection(t, sect2, t2)); } else { @@ -1281,13 +1408,13 @@ void SkTSect<TCurve>::matchedDirCheck(double t, const SkTSect* sect2, double t2, } } -template<typename TCurve> -void SkTSect<TCurve>::mergeCoincidence(SkTSect* sect2) { +template<typename TCurve, typename OppCurve> +void SkTSect<TCurve, OppCurve>::mergeCoincidence(SkTSect<OppCurve, TCurve>* sect2) { double smallLimit = 0; do { // find the smallest unprocessed span - SkTSpan<TCurve>* smaller = NULL; - SkTSpan<TCurve>* test = fCoincident; + SkTSpan<TCurve, OppCurve>* smaller = NULL; + SkTSpan<TCurve, OppCurve>* test = fCoincident; do { if (test->fStartT < smallLimit) { continue; @@ -1302,9 +1429,9 @@ void SkTSect<TCurve>::mergeCoincidence(SkTSect* sect2) { } smallLimit = smaller->fEndT; // find next larger span - SkTSpan<TCurve>* prior = NULL; - SkTSpan<TCurve>* larger = NULL; - SkTSpan<TCurve>* largerPrior = NULL; + SkTSpan<TCurve, OppCurve>* prior = NULL; + SkTSpan<TCurve, OppCurve>* larger = NULL; + SkTSpan<TCurve, OppCurve>* largerPrior = NULL; test = fCoincident; do { if (test->fStartT < smaller->fEndT) { @@ -1323,7 +1450,7 @@ void SkTSect<TCurve>::mergeCoincidence(SkTSect* sect2) { // 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<TCurve> coin; + SkTCoincident<TCurve, OppCurve> coin; coin.setPerp(fCurve, midT, midPt, sect2->fCurve); if (coin.isCoincident()) { smaller->fEndT = larger->fEndT; @@ -1337,10 +1464,11 @@ void SkTSect<TCurve>::mergeCoincidence(SkTSect* sect2) { } while (true); } -template<typename TCurve> -SkTSpan<TCurve>* SkTSect<TCurve>::prev(SkTSpan<TCurve>* span) const { - SkTSpan<TCurve>* result = NULL; - SkTSpan<TCurve>* test = fHead; +template<typename TCurve, typename OppCurve> +SkTSpan<TCurve, OppCurve>* SkTSect<TCurve, OppCurve>::prev( + SkTSpan<TCurve, OppCurve>* span) const { + SkTSpan<TCurve, OppCurve>* result = NULL; + SkTSpan<TCurve, OppCurve>* test = fHead; while (span != test) { result = test; test = test->fNext; @@ -1349,13 +1477,13 @@ SkTSpan<TCurve>* SkTSect<TCurve>::prev(SkTSpan<TCurve>* span) const { return result; } -template<typename TCurve> -void SkTSect<TCurve>::recoverCollapsed() { - SkTSpan<TCurve>* deleted = fDeleted; +template<typename TCurve, typename OppCurve> +void SkTSect<TCurve, OppCurve>::recoverCollapsed() { + SkTSpan<TCurve, OppCurve>* deleted = fDeleted; while (deleted) { - SkTSpan<TCurve>* delNext = deleted->fNext; + SkTSpan<TCurve, OppCurve>* delNext = deleted->fNext; if (deleted->fCollapsed) { - SkTSpan<TCurve>** spanPtr = &fHead; + SkTSpan<TCurve, OppCurve>** spanPtr = &fHead; while (*spanPtr && (*spanPtr)->fEndT <= deleted->fStartT) { spanPtr = &(*spanPtr)->fNext; } @@ -1366,13 +1494,13 @@ void SkTSect<TCurve>::recoverCollapsed() { } } -template<typename TCurve> -void SkTSect<TCurve>::removeAllBut(const SkTSpan<TCurve>* keep, SkTSpan<TCurve>* span, - SkTSect* opp) { - const SkTSpanBounded<TCurve>* testBounded = span->fBounded; +template<typename TCurve, typename OppCurve> +void SkTSect<TCurve, OppCurve>::removeAllBut(const SkTSpan<OppCurve, TCurve>* keep, + SkTSpan<TCurve, OppCurve>* span, SkTSect<OppCurve, TCurve>* opp) { + const SkTSpanBounded<OppCurve, TCurve>* testBounded = span->fBounded; while (testBounded) { - SkTSpan<TCurve>* bounded = testBounded->fBounded; - const SkTSpanBounded<TCurve>* next = testBounded->fNext; + SkTSpan<OppCurve, TCurve>* bounded = testBounded->fBounded; + const SkTSpanBounded<OppCurve, TCurve>* next = testBounded->fNext; // may have been deleted when opp did 'remove all but' if (bounded != keep && !bounded->fDeleted) { SkAssertResult(SkDEBUGCODE(!) span->removeBounded(bounded)); @@ -1387,10 +1515,10 @@ void SkTSect<TCurve>::removeAllBut(const SkTSpan<TCurve>* keep, SkTSpan<TCurve>* SkASSERT(keep->findOppSpan(span)); } -template<typename TCurve> -void SkTSect<TCurve>::removeByPerpendicular(SkTSect<TCurve>* opp) { - SkTSpan<TCurve>* test = fHead; - SkTSpan<TCurve>* next; +template<typename TCurve, typename OppCurve> +void SkTSect<TCurve, OppCurve>::removeByPerpendicular(SkTSect<OppCurve, TCurve>* opp) { + SkTSpan<TCurve, OppCurve>* test = fHead; + SkTSpan<TCurve, OppCurve>* next; do { next = test->fNext; if (test->fCoinStart.perpT() < 0 || test->fCoinEnd.perpT() < 0) { @@ -1409,8 +1537,8 @@ void SkTSect<TCurve>::removeByPerpendicular(SkTSect<TCurve>* opp) { } while ((test = next)); } -template<typename TCurve> -void SkTSect<TCurve>::removeCoincident(SkTSpan<TCurve>* span, bool isBetween) { +template<typename TCurve, typename OppCurve> +void SkTSect<TCurve, OppCurve>::removeCoincident(SkTSpan<TCurve, OppCurve>* span, bool isBetween) { this->unlinkSpan(span); if (isBetween || between(0, span->fCoinStart.perpT(), 1)) { --fActiveCount; @@ -1421,21 +1549,22 @@ void SkTSect<TCurve>::removeCoincident(SkTSpan<TCurve>* span, bool isBetween) { } } -template<typename TCurve> -void SkTSect<TCurve>::removeSpan(SkTSpan<TCurve>* span) { +template<typename TCurve, typename OppCurve> +void SkTSect<TCurve, OppCurve>::removeSpan(SkTSpan<TCurve, OppCurve>* span) { this->unlinkSpan(span); this->markSpanGone(span); } -template<typename TCurve> -void SkTSect<TCurve>::removeSpanRange(SkTSpan<TCurve>* first, SkTSpan<TCurve>* last) { +template<typename TCurve, typename OppCurve> +void SkTSect<TCurve, OppCurve>::removeSpanRange(SkTSpan<TCurve, OppCurve>* first, + SkTSpan<TCurve, OppCurve>* last) { if (first == last) { return; } - SkTSpan<TCurve>* span = first; + SkTSpan<TCurve, OppCurve>* span = first; SkASSERT(span); - SkTSpan<TCurve>* final = last->fNext; - SkTSpan<TCurve>* next = span->fNext; + SkTSpan<TCurve, OppCurve>* final = last->fNext; + SkTSpan<TCurve, OppCurve>* next = span->fNext; while ((span = next) && span != final) { next = span->fNext; this->markSpanGone(span); @@ -1446,12 +1575,13 @@ void SkTSect<TCurve>::removeSpanRange(SkTSpan<TCurve>* first, SkTSpan<TCurve>* l first->fNext = final; } -template<typename TCurve> -void SkTSect<TCurve>::removeSpans(SkTSpan<TCurve>* span, SkTSect<TCurve>* opp) { - SkTSpanBounded<TCurve>* bounded = span->fBounded; +template<typename TCurve, typename OppCurve> +void SkTSect<TCurve, OppCurve>::removeSpans(SkTSpan<TCurve, OppCurve>* span, + SkTSect<OppCurve, TCurve>* opp) { + SkTSpanBounded<OppCurve, TCurve>* bounded = span->fBounded; while (bounded) { - SkTSpan<TCurve>* spanBounded = bounded->fBounded; - SkTSpanBounded<TCurve>* next = bounded->fNext; + SkTSpan<OppCurve, TCurve>* spanBounded = bounded->fBounded; + SkTSpanBounded<OppCurve, TCurve>* next = bounded->fNext; if (span->removeBounded(spanBounded)) { // shuffles last into position 0 this->removeSpan(span); } @@ -1463,10 +1593,11 @@ void SkTSect<TCurve>::removeSpans(SkTSpan<TCurve>* span, SkTSect<TCurve>* opp) { } } -template<typename TCurve> -SkTSpan<TCurve>* SkTSect<TCurve>::spanAtT(double t, SkTSpan<TCurve>** priorSpan) { - SkTSpan<TCurve>* test = fHead; - SkTSpan<TCurve>* prev = NULL; +template<typename TCurve, typename OppCurve> +SkTSpan<TCurve, OppCurve>* SkTSect<TCurve, OppCurve>::spanAtT(double t, + SkTSpan<TCurve, OppCurve>** priorSpan) { + SkTSpan<TCurve, OppCurve>* test = fHead; + SkTSpan<TCurve, OppCurve>* prev = NULL; while (test && test->fEndT < t) { prev = test; test = test->fNext; @@ -1475,10 +1606,10 @@ SkTSpan<TCurve>* SkTSect<TCurve>::spanAtT(double t, SkTSpan<TCurve>** priorSpan) return test && test->fStartT <= t ? test : NULL; } -template<typename TCurve> -SkTSpan<TCurve>* SkTSect<TCurve>::tail() { - SkTSpan<TCurve>* result = fHead; - SkTSpan<TCurve>* next = fHead; +template<typename TCurve, typename OppCurve> +SkTSpan<TCurve, OppCurve>* SkTSect<TCurve, OppCurve>::tail() { + SkTSpan<TCurve, OppCurve>* result = fHead; + SkTSpan<TCurve, OppCurve>* next = fHead; while ((next = next->fNext)) { if (next->fEndT > result->fEndT) { result = next; @@ -1489,13 +1620,14 @@ SkTSpan<TCurve>* SkTSect<TCurve>::tail() { /* 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<typename TCurve> -void SkTSect<TCurve>::trim(SkTSpan<TCurve>* span, SkTSect* opp) { +template<typename TCurve, typename OppCurve> +void SkTSect<TCurve, OppCurve>::trim(SkTSpan<TCurve, OppCurve>* span, + SkTSect<OppCurve, TCurve>* opp) { span->initBounds(fCurve); - const SkTSpanBounded<TCurve>* testBounded = span->fBounded; + const SkTSpanBounded<OppCurve, TCurve>* testBounded = span->fBounded; while (testBounded) { - SkTSpan<TCurve>* test = testBounded->fBounded; - const SkTSpanBounded<TCurve>* next = testBounded->fNext; + SkTSpan<OppCurve, TCurve>* test = testBounded->fBounded; + const SkTSpanBounded<OppCurve, TCurve>* next = testBounded->fNext; int oppSects, sects = this->intersects(span, opp, test, &oppSects); if (sects >= 1) { if (oppSects == 2) { @@ -1519,10 +1651,10 @@ void SkTSect<TCurve>::trim(SkTSpan<TCurve>* span, SkTSect* opp) { } } -template<typename TCurve> -void SkTSect<TCurve>::unlinkSpan(SkTSpan<TCurve>* span) { - SkTSpan<TCurve>* prev = span->fPrev; - SkTSpan<TCurve>* next = span->fNext; +template<typename TCurve, typename OppCurve> +void SkTSect<TCurve, OppCurve>::unlinkSpan(SkTSpan<TCurve, OppCurve>* span) { + SkTSpan<TCurve, OppCurve>* prev = span->fPrev; + SkTSpan<TCurve, OppCurve>* next = span->fNext; if (prev) { prev->fNext = next; if (next) { @@ -1536,11 +1668,11 @@ void SkTSect<TCurve>::unlinkSpan(SkTSpan<TCurve>* span) { } } -template<typename TCurve> -bool SkTSect<TCurve>::updateBounded(SkTSpan<TCurve>* first, SkTSpan<TCurve>* last, - SkTSpan<TCurve>* oppFirst) { - SkTSpan<TCurve>* test = first; - const SkTSpan<TCurve>* final = last->next(); +template<typename TCurve, typename OppCurve> +bool SkTSect<TCurve, OppCurve>::updateBounded(SkTSpan<TCurve, OppCurve>* first, + SkTSpan<TCurve, OppCurve>* last, SkTSpan<OppCurve, TCurve>* oppFirst) { + SkTSpan<TCurve, OppCurve>* test = first; + const SkTSpan<TCurve, OppCurve>* final = last->next(); bool deleteSpan = false; do { deleteSpan |= test->removeAllBounded(); @@ -1552,12 +1684,12 @@ bool SkTSect<TCurve>::updateBounded(SkTSpan<TCurve>* first, SkTSpan<TCurve>* las } -template<typename TCurve> -void SkTSect<TCurve>::validate() const { +template<typename TCurve, typename OppCurve> +void SkTSect<TCurve, OppCurve>::validate() const { #if DEBUG_T_SECT int count = 0; if (fHead) { - const SkTSpan<TCurve>* span = fHead; + const SkTSpan<TCurve, OppCurve>* span = fHead; SkASSERT(!span->fPrev); SkDEBUGCODE(double last = 0); do { @@ -1570,12 +1702,12 @@ void SkTSect<TCurve>::validate() const { SkASSERT(count == fActiveCount); SkASSERT(fActiveCount <= fDebugAllocatedCount); int deletedCount = 0; - const SkTSpan<TCurve>* deleted = fDeleted; + const SkTSpan<TCurve, OppCurve>* deleted = fDeleted; while (deleted) { ++deletedCount; deleted = deleted->fNext; } - const SkTSpan<TCurve>* coincident = fCoincident; + const SkTSpan<TCurve, OppCurve>* coincident = fCoincident; while (coincident) { ++deletedCount; coincident = coincident->fNext; @@ -1584,28 +1716,28 @@ void SkTSect<TCurve>::validate() const { #endif } -template<typename TCurve> -void SkTSect<TCurve>::validateBounded() const { +template<typename TCurve, typename OppCurve> +void SkTSect<TCurve, OppCurve>::validateBounded() const { #if DEBUG_T_SECT if (!fHead) { return; } - const SkTSpan<TCurve>* span = fHead; + const SkTSpan<TCurve, OppCurve>* span = fHead; do { span->validateBounded(); } while ((span = span->fNext) != NULL); #endif } -template<typename TCurve> -int SkTSect<TCurve>::EndsEqual(const SkTSect* sect1, const SkTSect* sect2, - SkIntersections* intersections) { +template<typename TCurve, typename OppCurve> +int SkTSect<TCurve, OppCurve>::EndsEqual(const SkTSect<TCurve, OppCurve>* sect1, + const SkTSect<OppCurve, TCurve>* 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[TCurve::kPointLast]) { + if (sect1->fCurve[0] == sect2->fCurve[OppCurve::kPointLast]) { zeroOneSet |= kZeroS1Set | kOneS2Set; intersections->insert(0, 1, sect1->fCurve[0]); } @@ -1613,7 +1745,7 @@ int SkTSect<TCurve>::EndsEqual(const SkTSect* sect1, const SkTSect* sect2, zeroOneSet |= kOneS1Set | kZeroS2Set; intersections->insert(1, 0, sect1->fCurve[TCurve::kPointLast]); } - if (sect1->fCurve[TCurve::kPointLast] == sect2->fCurve[TCurve::kPointLast]) { + if (sect1->fCurve[TCurve::kPointLast] == sect2->fCurve[OppCurve::kPointLast]) { zeroOneSet |= kOneS1Set | kOneS2Set; intersections->insert(1, 1, sect1->fCurve[TCurve::kPointLast]); } @@ -1624,9 +1756,9 @@ int SkTSect<TCurve>::EndsEqual(const SkTSect* sect1, const SkTSect* sect2, intersections->insertNear(0, 0, sect1->fCurve[0], sect2->fCurve[0]); } if (!(zeroOneSet & (kZeroS1Set | kOneS2Set)) - && sect1->fCurve[0].approximatelyEqual(sect2->fCurve[TCurve::kPointLast])) { + && sect1->fCurve[0].approximatelyEqual(sect2->fCurve[OppCurve::kPointLast])) { zeroOneSet |= kZeroS1Set | kOneS2Set; - intersections->insertNear(0, 1, sect1->fCurve[0], sect2->fCurve[TCurve::kPointLast]); + intersections->insertNear(0, 1, sect1->fCurve[0], sect2->fCurve[OppCurve::kPointLast]); } // check for one if (!(zeroOneSet & (kOneS1Set | kZeroS2Set)) @@ -1636,15 +1768,15 @@ int SkTSect<TCurve>::EndsEqual(const SkTSect* sect1, const SkTSect* sect2, } if (!(zeroOneSet & (kOneS1Set | kOneS2Set)) && sect1->fCurve[TCurve::kPointLast].approximatelyEqual(sect2->fCurve[ - TCurve::kPointLast])) { + OppCurve::kPointLast])) { zeroOneSet |= kOneS1Set | kOneS2Set; intersections->insertNear(1, 1, sect1->fCurve[TCurve::kPointLast], - sect2->fCurve[TCurve::kPointLast]); + sect2->fCurve[OppCurve::kPointLast]); } return zeroOneSet; } -template<typename TCurve> +template<typename TCurve, typename OppCurve> struct SkClosestRecord { bool operator<(const SkClosestRecord& rh) const { return fClosest < rh.fClosest; @@ -1656,10 +1788,10 @@ struct SkClosestRecord { intersections->insert(r1t, r2t, fC1Span->part()[fC1Index]); } - void findEnd(const SkTSpan<TCurve>* span1, const SkTSpan<TCurve>* span2, + void findEnd(const SkTSpan<TCurve, OppCurve>* span1, const SkTSpan<OppCurve, TCurve>* span2, int c1Index, int c2Index) { const TCurve& c1 = span1->part(); - const TCurve& c2 = span2->part(); + const OppCurve& c2 = span2->part(); if (!c1[c1Index].approximatelyEqual(c2[c2Index])) { return; } @@ -1700,7 +1832,8 @@ struct SkClosestRecord { void reset() { fClosest = FLT_MAX; - SkDEBUGCODE(fC1Span = fC2Span = NULL); + SkDEBUGCODE(fC1Span = NULL); + SkDEBUGCODE(fC2Span = NULL); SkDEBUGCODE(fC1Index = fC2Index = -1); } @@ -1711,8 +1844,8 @@ struct SkClosestRecord { fC2EndT = SkTMax(fC2EndT, mate.fC2EndT); } - const SkTSpan<TCurve>* fC1Span; - const SkTSpan<TCurve>* fC2Span; + const SkTSpan<TCurve, OppCurve>* fC1Span; + const SkTSpan<OppCurve, TCurve>* fC2Span; double fC1StartT; double fC1EndT; double fC2StartT; @@ -1722,24 +1855,24 @@ struct SkClosestRecord { int fC2Index; }; -template<typename TCurve> +template<typename TCurve, typename OppCurve> struct SkClosestSect { SkClosestSect() : fUsed(0) { fClosest.push_back().reset(); } - bool find(const SkTSpan<TCurve>* span1, const SkTSpan<TCurve>* span2) { - SkClosestRecord<TCurve>* record = &fClosest[fUsed]; + bool find(const SkTSpan<TCurve, OppCurve>* span1, const SkTSpan<OppCurve, TCurve>* span2) { + SkClosestRecord<TCurve, OppCurve>* record = &fClosest[fUsed]; record->findEnd(span1, span2, 0, 0); - record->findEnd(span1, span2, 0, TCurve::kPointLast); + record->findEnd(span1, span2, 0, OppCurve::kPointLast); record->findEnd(span1, span2, TCurve::kPointLast, 0); - record->findEnd(span1, span2, TCurve::kPointLast, TCurve::kPointLast); + record->findEnd(span1, span2, TCurve::kPointLast, OppCurve::kPointLast); if (record->fClosest == FLT_MAX) { return false; } for (int index = 0; index < fUsed; ++index) { - SkClosestRecord<TCurve>* test = &fClosest[index]; + SkClosestRecord<TCurve, OppCurve>* test = &fClosest[index]; if (test->matesWith(*record)) { if (test->fClosest > record->fClosest) { test->merge(*record); @@ -1755,34 +1888,37 @@ struct SkClosestSect { } void finish(SkIntersections* intersections) const { - SkSTArray<TCurve::kMaxIntersections * 2, const SkClosestRecord<TCurve>*, true> closestPtrs; + SkSTArray<TCurve::kMaxIntersections * 3, + const SkClosestRecord<TCurve, OppCurve>*, true> closestPtrs; for (int index = 0; index < fUsed; ++index) { closestPtrs.push_back(&fClosest[index]); } - SkTQSort<const SkClosestRecord<TCurve> >(closestPtrs.begin(), closestPtrs.end() - 1); + SkTQSort<const SkClosestRecord<TCurve, OppCurve> >(closestPtrs.begin(), closestPtrs.end() + - 1); for (int index = 0; index < fUsed; ++index) { - const SkClosestRecord<TCurve>* test = closestPtrs[index]; + const SkClosestRecord<TCurve, OppCurve>* test = closestPtrs[index]; test->addIntersection(intersections); } } // this is oversized so that an extra records can merge into final one - SkSTArray<TCurve::kMaxIntersections * 2, SkClosestRecord<TCurve>, true> fClosest; + SkSTArray<TCurve::kMaxIntersections * 2, SkClosestRecord<TCurve, OppCurve>, true> fClosest; int fUsed; }; // returns true if the rect is too small to consider -template<typename TCurve> -void SkTSect<TCurve>::BinarySearch(SkTSect* sect1, SkTSect* sect2, SkIntersections* intersections) { +template<typename TCurve, typename OppCurve> +void SkTSect<TCurve, OppCurve>::BinarySearch(SkTSect<TCurve, OppCurve>* sect1, + SkTSect<OppCurve, TCurve>* sect2, SkIntersections* intersections) { #if DEBUG_T_SECT_DUMP > 1 gDumpTSectNum = 0; #endif - PATH_OPS_DEBUG_CODE(sect1->fOppSect = sect2); - PATH_OPS_DEBUG_CODE(sect2->fOppSect = sect1); + SkDEBUGCODE(sect1->fOppSect = sect2); + SkDEBUGCODE(sect2->fOppSect = sect1); intersections->reset(); - intersections->setMax(TCurve::kMaxIntersections * 2); // give extra for slop - SkTSpan<TCurve>* span1 = sect1->fHead; - SkTSpan<TCurve>* span2 = sect2->fHead; + intersections->setMax(TCurve::kMaxIntersections * 3); // give extra for slop + SkTSpan<TCurve, OppCurve>* span1 = sect1->fHead; + SkTSpan<OppCurve, TCurve>* span2 = sect2->fHead; int oppSect, sect = sect1->intersects(span1, sect2, span2, &oppSect); // SkASSERT(between(0, sect, 2)); if (!sect) { @@ -1796,28 +1932,36 @@ void SkTSect<TCurve>::BinarySearch(SkTSect* sect1, SkTSect* sect2, SkIntersectio span2->addBounded(span1, §2->fHeap); do { // find the largest bounds - SkTSpan<TCurve>* largest1 = sect1->boundsMax(); + SkTSpan<TCurve, OppCurve>* largest1 = sect1->boundsMax(); if (!largest1) { break; } - SkTSpan<TCurve>* largest2 = sect2->boundsMax(); - bool split1 = !largest2 || (largest1 && (largest1->fBoundsMax > largest2->fBoundsMax - || (!largest1->fCollapsed && largest2->fCollapsed))); + SkTSpan<OppCurve, TCurve>* largest2 = sect2->boundsMax(); // split it - SkTSpan<TCurve>* half1 = split1 ? largest1 : largest2; - SkASSERT(half1); - if (half1->fCollapsed) { - break; - } - SkTSect* splitSect = split1 ? sect1 : sect2; - // trim parts that don't intersect the opposite - SkTSpan<TCurve>* half2 = splitSect->addOne(); - SkTSect* unsplitSect = split1 ? sect2 : sect1; - if (!half2->split(half1, &splitSect->fHeap)) { - break; + if (!largest2 || (largest1 && (largest1->fBoundsMax > largest2->fBoundsMax + || (!largest1->fCollapsed && largest2->fCollapsed)))) { + if (largest1->fCollapsed) { + break; + } + // trim parts that don't intersect the opposite + SkTSpan<TCurve, OppCurve>* half1 = sect1->addOne(); + if (!half1->split(largest1, §1->fHeap)) { + break; + } + sect1->trim(largest1, sect2); + sect1->trim(half1, sect2); + } else { + if (largest2->fCollapsed) { + break; + } + // trim parts that don't intersect the opposite + SkTSpan<OppCurve, TCurve>* half2 = sect2->addOne(); + if (!half2->split(largest2, §2->fHeap)) { + break; + } + sect2->trim(largest2, sect1); + sect2->trim(half2, sect1); } - splitSect->trim(half1, unsplitSect); - splitSect->trim(half2, unsplitSect); sect1->validate(); sect2->validate(); // if there are 9 or more continuous spans on both sects, suspect coincidence @@ -1834,6 +1978,9 @@ void SkTSect<TCurve>::BinarySearch(SkTSect* sect1, SkTSect* sect2, SkIntersectio sect1->removeByPerpendicular(sect2); sect1->validate(); sect2->validate(); + if (sect1->collapsed() > TCurve::kMaxIntersections) { + break; + } } #if DEBUG_T_SECT_DUMP sect1->dumpBoth(sect2); @@ -1842,7 +1989,7 @@ void SkTSect<TCurve>::BinarySearch(SkTSect* sect1, SkTSect* sect2, SkIntersectio break; } } while (true); - SkTSpan<TCurve>* coincident = sect1->fCoincident; + SkTSpan<TCurve, OppCurve>* coincident = sect1->fCoincident; if (coincident) { // if there is more than one coincident span, check loosely to see if they should be joined if (coincident->fNext) { @@ -1862,15 +2009,15 @@ void SkTSect<TCurve>::BinarySearch(SkTSect* sect1, SkTSect* sect2, SkIntersectio } } while ((coincident = coincident->fNext)); } + int zeroOneSet = EndsEqual(sect1, sect2, intersections); if (!sect1->fHead || !sect2->fHead) { return; } - int zeroOneSet = EndsEqual(sect1, sect2, intersections); sect1->recoverCollapsed(); sect2->recoverCollapsed(); - SkTSpan<TCurve>* result1 = sect1->fHead; + SkTSpan<TCurve, OppCurve>* result1 = sect1->fHead; // check heads and tails for zero and ones and insert them if we haven't already done so - const SkTSpan<TCurve>* head1 = result1; + const SkTSpan<TCurve, OppCurve>* head1 = result1; if (!(zeroOneSet & kZeroS1Set) && approximately_less_than_zero(head1->fStartT)) { const SkDPoint& start1 = sect1->fCurve[0]; if (head1->isBounded()) { @@ -1880,7 +2027,7 @@ void SkTSect<TCurve>::BinarySearch(SkTSect* sect1, SkTSect* sect2, SkIntersectio } } } - const SkTSpan<TCurve>* head2 = sect2->fHead; + const SkTSpan<OppCurve, TCurve>* head2 = sect2->fHead; if (!(zeroOneSet & kZeroS2Set) && approximately_less_than_zero(head2->fStartT)) { const SkDPoint& start2 = sect2->fCurve[0]; if (head2->isBounded()) { @@ -1890,7 +2037,7 @@ void SkTSect<TCurve>::BinarySearch(SkTSect* sect1, SkTSect* sect2, SkIntersectio } } } - const SkTSpan<TCurve>* tail1 = sect1->tail(); + const SkTSpan<TCurve, OppCurve>* tail1 = sect1->tail(); if (!(zeroOneSet & kOneS1Set) && approximately_greater_than_one(tail1->fEndT)) { const SkDPoint& end1 = sect1->fCurve[TCurve::kPointLast]; if (tail1->isBounded()) { @@ -1900,9 +2047,9 @@ void SkTSect<TCurve>::BinarySearch(SkTSect* sect1, SkTSect* sect2, SkIntersectio } } } - const SkTSpan<TCurve>* tail2 = sect2->tail(); + const SkTSpan<OppCurve, TCurve>* tail2 = sect2->tail(); if (!(zeroOneSet & kOneS2Set) && approximately_greater_than_one(tail2->fEndT)) { - const SkDPoint& end2 = sect2->fCurve[TCurve::kPointLast]; + const SkDPoint& end2 = sect2->fCurve[OppCurve::kPointLast]; if (tail2->isBounded()) { double t = tail2->closestBoundedT(end2); if (sect1->fCurve.ptAtT(t).approximatelyEqual(end2)) { @@ -1910,7 +2057,7 @@ void SkTSect<TCurve>::BinarySearch(SkTSect* sect1, SkTSect* sect2, SkIntersectio } } } - SkClosestSect<TCurve> closest; + SkClosestSect<TCurve, OppCurve> closest; do { while (result1 && result1->fCoinStart.isCoincident() && result1->fCoinEnd.isCoincident()) { result1 = result1->fNext; @@ -1918,7 +2065,7 @@ void SkTSect<TCurve>::BinarySearch(SkTSect* sect1, SkTSect* sect2, SkIntersectio if (!result1) { break; } - SkTSpan<TCurve>* result2 = sect2->fHead; + SkTSpan<OppCurve, TCurve>* result2 = sect2->fHead; bool found = false; while (result2) { found |= closest.find(result1, result2); @@ -1936,7 +2083,7 @@ void SkTSect<TCurve>::BinarySearch(SkTSect* sect1, SkTSect* sect2, SkIntersectio double midT = ((*intersections)[0][index] + (*intersections)[0][index + 1]) / 2; SkDPoint midPt = sect1->fCurve.ptAtT(midT); // intersect perpendicular with opposite curve - SkTCoincident<TCurve> perp; + SkTCoincident<TCurve, OppCurve> perp; perp.setPerp(sect1->fCurve, midT, midPt, sect2->fCurve); if (!perp.isCoincident()) { ++index; |