Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(14)

Issues Search
    My Issues | Starred     Open | Closed | All

Unified Diff: src/pathops/SkPathOpsTSect.h

Issue 1037953004: add conics to path ops (Closed) Base URL: https://skia.googlesource.com/skia.git@master
Patch Set: turn off pathops specific debuggging Created 5 years, 8 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View side-by-side diff with in-line comments
Download patch
« no previous file with comments | « src/pathops/SkPathOpsTQuadSect.cpp ('k') | src/pathops/SkPathOpsTSect.cpp » ('j') | no next file with comments »
Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
Index: src/pathops/SkPathOpsTSect.h
diff --git a/src/pathops/SkPathOpsTSect.h b/src/pathops/SkPathOpsTSect.h
index 9d634333301e180c1121a28f2e4734b06cce362e..ffd69951d3f5fc5af6d9aa33dd1fe30e27929d6b 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, &sect2->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, &sect1->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, &sect2->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;
« no previous file with comments | « src/pathops/SkPathOpsTQuadSect.cpp ('k') | src/pathops/SkPathOpsTSect.cpp » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698