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

Issues Search
    My Issues | Starred     Open | Closed | All

Unified Diff: src/pathops/SkOpSegment.h

Issue 131103009: update pathops to circle sort (Closed) Base URL: https://skia.googlesource.com/skia.git@master
Patch Set: disable old test that still fails on linux 32 release Created 6 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/SkOpContour.cpp ('k') | src/pathops/SkOpSegment.cpp » ('j') | no next file with comments »
Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
Index: src/pathops/SkOpSegment.h
diff --git a/src/pathops/SkOpSegment.h b/src/pathops/SkOpSegment.h
index 79d83b1155fbd8728d3d0e986f78c270e97b74a8..54c1892d1bd881064d1c2332d55777eeba73e2bb 100644
--- a/src/pathops/SkOpSegment.h
+++ b/src/pathops/SkOpSegment.h
@@ -19,7 +19,7 @@ class SkPathWriter;
class SkOpSegment {
public:
SkOpSegment() {
-#ifdef SK_DEBUG
+#if defined(SK_DEBUG) || !FORCE_RELEASE
fID = ++SkPathOpsDebug::gSegmentID;
#endif
}
@@ -28,6 +28,12 @@ public:
return fBounds.fTop < rh.fBounds.fTop;
}
+ // FIXME: add some template or macro to avoid casting
+ SkOpAngle& angle(int index) {
+ const SkOpAngle& cAngle = (const_cast<const SkOpSegment*>(this))->angle(index);
+ return const_cast<SkOpAngle&>(cAngle);
+ }
+
const SkPathOpsBounds& bounds() const {
return fBounds;
}
@@ -42,6 +48,8 @@ public:
return count > 1 && fTs[0].fT == 0 && fTs[--count].fT == 1;
}
+ void constructLine(SkPoint shortLine[2]);
+
int count() const {
return fTs.count();
}
@@ -59,7 +67,6 @@ public:
return done(SkMin32(angle->start(), angle->end()));
}
- // used only by partial coincidence detection
SkDPoint dPtAtT(double mid) const {
return (*CurveDPointAtT[SkPathOpsVerbToPoints(fVerb)])(fPts, mid);
}
@@ -72,6 +79,14 @@ public:
return dxdy(index).fY;
}
+ bool hasSmall() const {
+ return fSmall;
+ }
+
+ bool hasTiny() const {
+ return fTiny;
+ }
+
bool intersected() const {
return fTs.count() > 0;
}
@@ -131,11 +146,12 @@ public:
return fTs[lesser].fOppValue;
}
- const SkOpSegment* other(int index) const {
- return fTs[index].fOther;
+#if DEBUG_VALIDATE
+ bool oppXor() const {
+ return fOppXor;
}
+#endif
- // was used only by right angle winding finding
SkPoint ptAtT(double mid) const {
return (*CurvePointAtT[SkPathOpsVerbToPoints(fVerb)])(fPts, mid);
}
@@ -160,11 +176,23 @@ public:
*sumWinding -= deltaSum;
}
- // OPTIMIZATION: mark as debugging only if used solely by tests
const SkOpSpan& span(int tIndex) const {
return fTs[tIndex];
}
+ const SkOpAngle* spanToAngle(int tStart, int tEnd) const {
+ SkASSERT(tStart != tEnd);
+ const SkOpSpan& span = fTs[tStart];
+ int index = tStart < tEnd ? span.fToAngleIndex : span.fFromAngleIndex;
+ return index >= 0 ? &angle(index) : NULL;
+ }
+
+ // FIXME: create some sort of macro or template that avoids casting
+ SkOpAngle* spanToAngle(int tStart, int tEnd) {
+ const SkOpAngle* cAngle = (const_cast<const SkOpSegment*>(this))->spanToAngle(tStart, tEnd);
+ return const_cast<SkOpAngle*>(cAngle);
+ }
+
// OPTIMIZATION: mark as debugging only if used solely by tests
const SkTDArray<SkOpSpan>& spans() const {
return fTs;
@@ -217,6 +245,12 @@ public:
}
#endif
+#if DEBUG_VALIDATE
+ bool _xor() const { // FIXME: used only by SkOpAngle::debugValidateLoop()
+ return fXor;
+ }
+#endif
+
const SkPoint& xyAtT(const SkOpSpan* span) const {
return span->fPt;
}
@@ -231,44 +265,56 @@ public:
}
#endif
- bool activeAngle(int index, int* done, SkTArray<SkOpAngle, true>* angles);
+ const SkOpAngle* activeAngle(int index, int* start, int* end, bool* done,
+ bool* sortable) const;
SkPoint activeLeftTop(bool onlySortable, int* firstT) const;
bool activeOp(int index, int endIndex, int xorMiMask, int xorSuMask, SkPathOp op);
bool activeWinding(int index, int endIndex);
void addCubic(const SkPoint pts[4], bool operand, bool evenOdd);
void addCurveTo(int start, int end, SkPathWriter* path, bool active) const;
+ void addEndSpan(int endIndex);
void addLine(const SkPoint pts[2], bool operand, bool evenOdd);
void addOtherT(int index, double otherT, int otherIndex);
void addQuad(const SkPoint pts[3], bool operand, bool evenOdd);
- int addSelfT(SkOpSegment* other, const SkPoint& pt, double newT);
+ void addSimpleAngle(int endIndex);
+ int addSelfT(const SkPoint& pt, double newT);
+ void addStartSpan(int endIndex);
int addT(SkOpSegment* other, const SkPoint& pt, double newT);
void addTCancel(const SkPoint& startPt, const SkPoint& endPt, SkOpSegment* other);
void addTCoincident(const SkPoint& startPt, const SkPoint& endPt, double endT,
- SkOpSegment* other);
- void addTPair(double t, SkOpSegment* other, double otherT, bool borrowWind, const SkPoint& pt);
+ SkOpSegment* other);
+ const SkOpSpan* addTPair(double t, SkOpSegment* other, double otherT, bool borrowWind,
+ const SkPoint& pt);
+ bool alignSpan(int index, double thisT, const SkPoint& thisPt);
+ void alignSpanState(int start, int end);
+ const SkOpAngle& angle(int index) const;
bool betweenTs(int lesser, double testT, int greater) const;
+ bool calcAngles();
+ void checkDuplicates();
void checkEnds();
+ void checkMultiples();
+ void checkSmall();
bool checkSmall(int index) const;
void checkTiny();
- int computeSum(int startIndex, int endIndex, SkOpAngle::IncludeType includeType,
- SkTArray<SkOpAngle, true>* angles, SkTArray<SkOpAngle*, true>* sorted);
+ int computeSum(int startIndex, int endIndex, SkOpAngle::IncludeType includeType);
int crossedSpanY(const SkPoint& basePt, SkScalar* bestY, double* hitT, bool* hitSomething,
double mid, bool opp, bool current) const;
bool findCoincidentMatch(const SkOpSpan* span, const SkOpSegment* other, int oStart, int oEnd,
int step, SkPoint* startPt, SkPoint* endPt, double* endT) const;
SkOpSegment* findNextOp(SkTDArray<SkOpSpan*>* chase, int* nextStart, int* nextEnd,
- bool* unsortable, SkPathOp op, const int xorMiMask,
- const int xorSuMask);
+ bool* unsortable, SkPathOp op, int xorMiMask, int xorSuMask);
SkOpSegment* findNextWinding(SkTDArray<SkOpSpan*>* chase, int* nextStart, int* nextEnd,
bool* unsortable);
SkOpSegment* findNextXor(int* nextStart, int* nextEnd, bool* unsortable);
+ int findExactT(double t, const SkOpSegment* ) const;
int findT(double t, const SkOpSegment* ) const;
- SkOpSegment* findTop(int* tIndex, int* endIndex, bool* unsortable, bool onlySortable);
+ SkOpSegment* findTop(int* tIndex, int* endIndex, bool* unsortable);
void fixOtherTIndex();
- void initWinding(int start, int end);
+ void initWinding(int start, int end, SkOpAngle::IncludeType angleIncludeType);
void initWinding(int start, int end, double tHit, int winding, SkScalar hitDx, int oppWind,
SkScalar hitOppDx);
bool isMissing(double startT, const SkPoint& pt) const;
+ bool isSmall(const SkOpAngle* angle) const;
bool isTiny(const SkOpAngle* angle) const;
bool joinCoincidence(SkOpSegment* other, double otherT, int step, bool cancel);
SkOpSpan* markAndChaseDoneBinary(int index, int endIndex);
@@ -283,44 +329,44 @@ public:
int nextSpan(int from, int step) const;
void setUpWindings(int index, int endIndex, int* sumMiWinding, int* sumSuWinding,
int* maxWinding, int* sumWinding, int* oppMaxWinding, int* oppSumWinding);
- enum SortAngleKind {
- kMustBeOrdered_SortAngleKind, // required for winding calc
- kMayBeUnordered_SortAngleKind // ok for find top
- };
- static bool SortAngles(const SkTArray<SkOpAngle, true>& angles, // FIXME: replace with
- SkTArray<SkOpAngle*, true>* angleList, // Sort Angles 2
- SortAngleKind );
- static bool SortAngles2(const SkTArray<SkOpAngle, true>& angles,
- SkTArray<SkOpAngle*, true>* angleList);
+ void sortAngles();
bool subDivide(int start, int end, SkPoint edge[4]) const;
bool subDivide(int start, int end, SkDCubic* result) const;
void undoneSpan(int* start, int* end);
int updateOppWindingReverse(const SkOpAngle* angle) const;
int updateWindingReverse(const SkOpAngle* angle) const;
static bool UseInnerWinding(int outerWinding, int innerWinding);
+ static bool UseInnerWindingReverse(int outerWinding, int innerWinding);
int windingAtT(double tHit, int tIndex, bool crossOpp, SkScalar* dx) const;
int windSum(const SkOpAngle* angle) const;
-
-#ifdef SK_DEBUG
+// available for testing only
+#if DEBUG_VALIDATE
+ bool debugContains(const SkOpAngle* ) const;
+#endif
+#if defined(SK_DEBUG) || !FORCE_RELEASE
int debugID() const {
return fID;
}
+#else
+ int debugID() const {
+ return -1;
+ }
#endif
#if DEBUG_ACTIVE_SPANS || DEBUG_ACTIVE_SPANS_FIRST_ONLY
void debugShowActiveSpans() const;
#endif
-#if DEBUG_SORT || DEBUG_SWAP_TOP
- void debugShowSort(const char* fun, const SkTArray<SkOpAngle*, true>& angles, int first,
- const int contourWinding, const int oppContourWinding, bool sortable) const;
- void debugShowSort(const char* fun, const SkTArray<SkOpAngle*, true>& angles, int first,
- bool sortable);
-#endif
#if DEBUG_CONCIDENT
void debugShowTs(const char* prefix) const;
#endif
#if DEBUG_SHOW_WINDING
int debugShowWindingValues(int slotCount, int ofInterest) const;
#endif
+ void debugValidate() const;
+ // available to testing only
+ void dumpAngles() const;
+ void dumpContour(int firstID, int lastID) const;
+ void dumpPts() const;
+ void dumpSpans() const;
private:
struct MissingSpan {
@@ -332,40 +378,55 @@ private:
SkPoint fPt;
};
- bool activeAngleOther(int index, int* done, SkTArray<SkOpAngle, true>* angles);
- bool activeAngleInner(int index, int* done, SkTArray<SkOpAngle, true>* angles);
+ const SkOpAngle* activeAngleInner(int index, int* start, int* end, bool* done,
+ bool* sortable) const;
+ const SkOpAngle* activeAngleOther(int index, int* start, int* end, bool* done,
+ bool* sortable) const;
bool activeOp(int xorMiMask, int xorSuMask, int index, int endIndex, SkPathOp op,
- int* sumMiWinding, int* sumSuWinding, int* maxWinding, int* sumWinding,
- int* oppMaxWinding, int* oppSumWinding);
- bool activeWinding(int index, int endIndex, int* maxWinding, int* sumWinding);
- void addAngle(SkTArray<SkOpAngle, true>* angles, int start, int end) const;
+ int* sumMiWinding, int* sumSuWinding);
+ bool activeWinding(int index, int endIndex, int* sumWinding);
void addCancelOutsides(const SkPoint& startPt, const SkPoint& endPt, SkOpSegment* other);
void addCoinOutsides(const SkPoint& startPt, const SkPoint& endPt, SkOpSegment* other);
+ int addSingletonAngleDown(int start, SkOpSegment** otherPtr);
+ int addSingletonAngleUp(int start, SkOpSegment** otherPtr);
+ SkOpAngle* addSingletonAngles(int start, int step);
void addTPair(double t, SkOpSegment* other, double otherT, bool borrowWind, const SkPoint& pt,
const SkPoint& oPt);
- void addTwoAngles(int start, int end, SkTArray<SkOpAngle, true>* angles) const;
bool betweenPoints(double midT, const SkPoint& pt1, const SkPoint& pt2) const;
- bool buildAngles(int index, SkTArray<SkOpAngle, true>* angles, bool includeOpp) const;
- void buildAnglesInner(int index, SkTArray<SkOpAngle, true>* angles) const;
void bumpCoincidentThis(const SkOpSpan& oTest, bool binary, int* index,
SkTArray<SkPoint, true>* outsideTs);
void bumpCoincidentOther(const SkOpSpan& oTest, int* index,
SkTArray<SkPoint, true>* outsideTs);
bool bumpSpan(SkOpSpan* span, int windDelta, int oppDelta);
+ bool calcLoopSpanCount(const SkOpSpan& thisSpan, int* smallCounts);
+ void checkLinks(const SkOpSpan* ,
+ SkTArray<MissingSpan, true>* missingSpans) const;
+ static void CheckOneLink(const SkOpSpan* test, const SkOpSpan* oSpan,
+ const SkOpSpan* oFirst, const SkOpSpan* oLast,
+ const SkOpSpan** missingPtr,
+ SkTArray<MissingSpan, true>* missingSpans);
+ int checkSetAngle(int tIndex) const;
+ void checkSmallCoincidence(const SkOpSpan& span, SkTArray<MissingSpan, true>* );
bool clockwise(int tStart, int tEnd) const;
static void ComputeOneSum(const SkOpAngle* baseAngle, SkOpAngle* nextAngle,
SkOpAngle::IncludeType );
static void ComputeOneSumReverse(const SkOpAngle* baseAngle, SkOpAngle* nextAngle,
SkOpAngle::IncludeType );
bool decrementSpan(SkOpSpan* span);
- int findStartingEdge(const SkTArray<SkOpAngle*, true>& sorted, int start, int end);
+ int findEndSpan(int endIndex) const;
+ int findStartSpan(int startIndex) const;
+ int firstActive(int tIndex) const;
+ const SkOpSpan& firstSpan(const SkOpSpan& thisSpan) const;
void init(const SkPoint pts[], SkPath::Verb verb, bool operand, bool evenOdd);
+ bool inLoop(const SkOpAngle* baseAngle, int spanCount, int* indexPtr) const;
bool isSimple(int end) const;
bool isTiny(int index) const;
+ const SkOpSpan& lastSpan(const SkOpSpan& thisSpan) const;
void matchWindingValue(int tIndex, double t, bool borrowWind);
SkOpSpan* markAndChaseDone(int index, int endIndex, int winding);
SkOpSpan* markAndChaseDoneBinary(const SkOpAngle* angle, int winding, int oppWinding);
- SkOpSpan* markAndChaseWinding(const SkOpAngle* angle, const int winding);
+ SkOpSpan* markAndChaseWinding(const SkOpAngle* angle, int winding);
+ SkOpSpan* markAndChaseWinding(int index, int endIndex, int winding);
SkOpSpan* markAndChaseWinding(int index, int endIndex, int winding, int oppWinding);
SkOpSpan* markAngle(int maxWinding, int sumWinding, const SkOpAngle* angle);
void markDoneBinary(int index, int winding, int oppWinding);
@@ -380,10 +441,21 @@ private:
void markWinding(int index, int winding, int oppWinding);
void markUnsortable(int start, int end);
bool monotonicInY(int tStart, int tEnd) const;
+
+ bool multipleEnds() const {
+ return fTs[count() - 2].fT == 1;
+ }
+
+ bool multipleStarts() const {
+ return fTs[1].fT == 0;
+ }
+
bool multipleSpans(int end) const;
SkOpSegment* nextChase(int* index, const int step, int* min, SkOpSpan** last);
int nextExactSpan(int from, int step) const;
bool serpentine(int tStart, int tEnd) const;
+ void setFromAngleIndex(int endIndex, int angleIndex);
+ void setToAngleIndex(int endIndex, int angleIndex);
void setUpWindings(int index, int endIndex, int* sumMiWinding,
int* maxWinding, int* sumWinding);
void subDivideBounds(int start, int end, SkPathOpsBounds* bounds) const;
@@ -395,7 +467,6 @@ private:
int updateWinding(int index, int endIndex) const;
int updateWinding(const SkOpAngle* angle) const;
int updateWindingReverse(int index, int endIndex) const;
- static bool UseInnerWindingReverse(int outerWinding, int innerWinding);
SkOpSpan* verifyOneWinding(const char* funName, int tIndex);
SkOpSpan* verifyOneWindingU(const char* funName, int tIndex);
@@ -412,8 +483,12 @@ private:
#if DEBUG_SWAP_TOP
bool controlsContainedByEnds(int tStart, int tEnd) const;
#endif
+ void debugAddAngle(int start, int end);
#if DEBUG_CONCIDENT
- void debugAddTPair(double t, const SkOpSegment& other, double otherT) const;
+ void debugAddTPair(double t, const SkOpSegment& other, double otherT) const;
+#endif
+#if DEBUG_ANGLE
+ void debugCheckPointsEqualish(int tStart, int tEnd) const;
#endif
#if DEBUG_MARK_DONE || DEBUG_UNSORTABLE
void debugShowNewWinding(const char* fun, const SkOpSpan& span, int winding);
@@ -424,27 +499,37 @@ private:
return value < 0 ? '?' : value <= 9 ? '0' + value : '+';
}
#endif
- void debugValidate() const;
-#ifdef SK_DEBUG
- void dumpPts() const;
+ // available to testing only
+ void debugConstruct();
+ void debugConstructCubic(SkPoint shortQuad[4]);
+ void debugConstructLine(SkPoint shortQuad[2]);
+ void debugConstructQuad(SkPoint shortQuad[3]);
+ void debugReset();
void dumpDPts() const;
- void dumpSpans() const;
-#endif
+ void dumpSpan(int index) const;
const SkPoint* fPts;
SkPathOpsBounds fBounds;
// FIXME: can't convert to SkTArray because it uses insert
- SkTDArray<SkOpSpan> fTs; // two or more (always includes t=0 t=1)
+ SkTDArray<SkOpSpan> fTs; // 2+ (always includes t=0 t=1) -- at least (number of spans) + 1
+// FIXME: replace both with bucket storage that allows direct immovable pointers to angles
+ SkTArray<SkOpAngle, true> fSingletonAngles; // 0 or 2 -- allocated for singletons
+ SkTArray<SkOpAngle, true> fAngles; // 0 or 2+ -- (number of non-zero spans) * 2
// OPTIMIZATION: could pack donespans, verb, operand, xor into 1 int-sized value
int fDoneSpans; // quick check that segment is finished
// OPTIMIZATION: force the following to be byte-sized
SkPath::Verb fVerb;
+ bool fLoop; // set if cubic intersects itself
bool fOperand;
bool fXor; // set if original contour had even-odd fill
bool fOppXor; // set if opposite operand had even-odd fill
-#ifdef SK_DEBUG
+ bool fSmall; // set if some span is small
+ bool fTiny; // set if some span is tiny
+#if defined(SK_DEBUG) || !FORCE_RELEASE
int fID;
#endif
+
+ friend class PathOpsSegmentTester;
};
#endif
« no previous file with comments | « src/pathops/SkOpContour.cpp ('k') | src/pathops/SkOpSegment.cpp » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698