Mike R: please sanity check SkPostConfig.h
Mike K: please sanity check Test.cpp and skia_test.cpp
Feel free to look at the rest, but I don't expect any in depth review of path ops innards.
Path Ops first iteration used QuickSort to order segments radiating from an intersection to compute the winding rule.
This revision uses a circular sort instead. Breaking out the circular sort into its own long-lived structure (SkOpAngle) allows doing less work and provides a home for caching additional sorting data.
The circle sort is more stable than the former sort, has a robust ordering and fewer exceptions. It finds unsortable ordering less often. It is less reliant on the initial curve tangent, using convex hulls instead whenever it can.
Additional debug validation makes sure that the computed structures are self-consistent. A new visualization tool helps verify that the angle ordering is correct.
The 70+M tests pass with this change on Windows, Mac, Linux 32 and Linux 64 in debug and release.
R=mtklein@google.com, reed@google.com
Author: caryclark@google.com
Review URL: https://codereview.chromium.org/131103009
git-svn-id: http://skia.googlecode.com/svn/trunk@14183 2bbb7eff-a529-9590-31e7-b0007b416f81
diff --git a/src/pathops/SkPathOpsCommon.cpp b/src/pathops/SkPathOpsCommon.cpp
index c48a7ee..f341483 100644
--- a/src/pathops/SkPathOpsCommon.cpp
+++ b/src/pathops/SkPathOpsCommon.cpp
@@ -111,75 +111,62 @@
return NULL;
}
-SkOpSegment* FindChase(SkTDArray<SkOpSpan*>& chase, int& tIndex, int& endIndex) {
- while (chase.count()) {
+SkOpSegment* FindChase(SkTDArray<SkOpSpan*>* chase, int* tIndex, int* endIndex) {
+ while (chase->count()) {
SkOpSpan* span;
- chase.pop(&span);
+ chase->pop(&span);
const SkOpSpan& backPtr = span->fOther->span(span->fOtherIndex);
SkOpSegment* segment = backPtr.fOther;
- tIndex = backPtr.fOtherIndex;
- SkSTArray<SkOpAngle::kStackBasedCount, SkOpAngle, true> angles;
- int done = 0;
- if (segment->activeAngle(tIndex, &done, &angles)) {
- SkOpAngle* last = angles.end() - 1;
- tIndex = last->start();
- endIndex = last->end();
- #if TRY_ROTATE
- *chase.insert(0) = span;
- #else
- *chase.append() = span;
- #endif
+ *tIndex = backPtr.fOtherIndex;
+ bool sortable = true;
+ bool done = true;
+ *endIndex = -1;
+ if (const SkOpAngle* last = segment->activeAngle(*tIndex, tIndex, endIndex, &done,
+ &sortable)) {
+ *tIndex = last->start();
+ *endIndex = last->end();
+ #if TRY_ROTATE
+ *chase->insert(0) = span;
+ #else
+ *chase->append() = span;
+ #endif
return last->segment();
}
- if (done == angles.count()) {
+ if (done) {
continue;
}
- SkSTArray<SkOpAngle::kStackBasedCount, SkOpAngle*, true> sorted;
- bool sortable = SkOpSegment::SortAngles(angles, &sorted,
- SkOpSegment::kMayBeUnordered_SortAngleKind);
- int angleCount = sorted.count();
-#if DEBUG_SORT
- sorted[0]->segment()->debugShowSort(__FUNCTION__, sorted, 0, 0, 0, sortable);
-#endif
if (!sortable) {
continue;
}
// find first angle, initialize winding to computed fWindSum
- int firstIndex = -1;
- const SkOpAngle* angle;
+ const SkOpAngle* angle = segment->spanToAngle(*tIndex, *endIndex);
+ const SkOpAngle* firstAngle;
+ SkDEBUGCODE(firstAngle = angle);
+ SkDEBUGCODE(bool loop = false);
int winding;
do {
- angle = sorted[++firstIndex];
+ angle = angle->next();
+ SkASSERT(angle != firstAngle || !loop);
+ SkDEBUGCODE(loop |= angle == firstAngle);
segment = angle->segment();
winding = segment->windSum(angle);
} while (winding == SK_MinS32);
int spanWinding = segment->spanSign(angle->start(), angle->end());
#if DEBUG_WINDING
- SkDebugf("%s winding=%d spanWinding=%d\n",
- __FUNCTION__, winding, spanWinding);
+ SkDebugf("%s winding=%d spanWinding=%d\n", __FUNCTION__, winding, spanWinding);
#endif
// turn span winding into contour winding
if (spanWinding * winding < 0) {
winding += spanWinding;
}
- #if DEBUG_SORT
- segment->debugShowSort(__FUNCTION__, sorted, firstIndex, winding, 0, sortable);
- #endif
// we care about first sign and whether wind sum indicates this
// edge is inside or outside. Maybe need to pass span winding
// or first winding or something into this function?
// advance to first undone angle, then return it and winding
// (to set whether edges are active or not)
- int nextIndex = firstIndex + 1;
- int lastIndex = firstIndex != 0 ? firstIndex : angleCount;
- angle = sorted[firstIndex];
- winding -= angle->segment()->spanSign(angle);
- do {
- SkASSERT(nextIndex != firstIndex);
- if (nextIndex == angleCount) {
- nextIndex = 0;
- }
- angle = sorted[nextIndex];
+ firstAngle = angle;
+ winding -= firstAngle->segment()->spanSign(firstAngle);
+ while ((angle = angle->next()) != firstAngle) {
segment = angle->segment();
int maxWinding = winding;
winding -= segment->spanSign(angle);
@@ -187,9 +174,9 @@
SkDebugf("%s id=%d maxWinding=%d winding=%d sign=%d\n", __FUNCTION__,
segment->debugID(), maxWinding, winding, angle->sign());
#endif
- tIndex = angle->start();
- endIndex = angle->end();
- int lesser = SkMin32(tIndex, endIndex);
+ *tIndex = angle->start();
+ *endIndex = angle->end();
+ int lesser = SkMin32(*tIndex, *endIndex);
const SkOpSpan& nextSpan = segment->span(lesser);
if (!nextSpan.fDone) {
// FIXME: this be wrong? assign startWinding if edge is in
@@ -201,8 +188,8 @@
segment->markAndChaseWinding(angle, maxWinding, 0);
break;
}
- } while (++nextIndex != lastIndex);
- *chase.insert(0) = span;
+ }
+ *chase->insert(0) = span;
return segment;
}
return NULL;
@@ -221,6 +208,8 @@
int* index, int* endIndex, SkPoint* topLeft, bool* unsortable,
bool* done, bool onlySortable) {
SkOpSegment* result;
+ const SkOpSegment* lastTopStart = NULL;
+ int lastIndex = -1, lastEndIndex = -1;
do {
SkPoint bestXY = {SK_ScalarMax, SK_ScalarMax};
int contourCount = contourList.count();
@@ -249,7 +238,16 @@
return NULL;
}
*topLeft = bestXY;
- result = topStart->findTop(index, endIndex, unsortable, onlySortable);
+ result = topStart->findTop(index, endIndex, unsortable);
+ if (!result) {
+ if (lastTopStart == topStart && lastIndex == *index && lastEndIndex == *endIndex) {
+ *done = true;
+ return NULL;
+ }
+ lastTopStart = topStart;
+ lastIndex = *index;
+ lastEndIndex = *endIndex;
+ }
} while (!result);
if (result) {
*unsortable = false;
@@ -303,7 +301,7 @@
const int index = *indexPtr;
const int endIndex = *endIndexPtr;
if (*firstContour) {
- current->initWinding(index, endIndex);
+ current->initWinding(index, endIndex, angleIncludeType);
*firstContour = false;
return current;
}
@@ -313,9 +311,11 @@
return current;
}
SkASSERT(current->windSum(SkMin32(index, endIndex)) == SK_MinS32);
- SkSTArray<SkOpAngle::kStackBasedCount, SkOpAngle, true> angles;
- SkSTArray<SkOpAngle::kStackBasedCount, SkOpAngle*, true> sorted;
- sumWinding = current->computeSum(index, endIndex, angleIncludeType, &angles, &sorted);
+ const SkOpSpan& span = current->span(endIndex);
+ if ((index < endIndex ? span.fFromAngleIndex : span.fToAngleIndex) < 0) {
+ current->addSimpleAngle(endIndex);
+ }
+ sumWinding = current->computeSum(index, endIndex, angleIncludeType);
if (sumWinding != SK_MinS32 && sumWinding != SK_NaN32) {
return current;
}
@@ -351,6 +351,25 @@
return current;
}
+static bool calcAngles(SkTArray<SkOpContour*, true>* contourList) {
+ int contourCount = (*contourList).count();
+ for (int cTest = 0; cTest < contourCount; ++cTest) {
+ SkOpContour* contour = (*contourList)[cTest];
+ if (!contour->calcAngles()) {
+ return false;
+ }
+ }
+ return true;
+}
+
+static void checkDuplicates(SkTArray<SkOpContour*, true>* contourList) {
+ int contourCount = (*contourList).count();
+ for (int cTest = 0; cTest < contourCount; ++cTest) {
+ SkOpContour* contour = (*contourList)[cTest];
+ contour->checkDuplicates();
+ }
+}
+
static void checkEnds(SkTArray<SkOpContour*, true>* contourList) {
// it's hard to determine if the end of a cubic or conic nearly intersects another curve.
// instead, look to see if the connecting curve intersected at that same end.
@@ -361,6 +380,25 @@
}
}
+static void checkMultiples(SkTArray<SkOpContour*, true>* contourList) {
+ // it's hard to determine if the end of a cubic or conic nearly intersects another curve.
+ // instead, look to see if the connecting curve intersected at that same end.
+ int contourCount = (*contourList).count();
+ for (int cTest = 0; cTest < contourCount; ++cTest) {
+ SkOpContour* contour = (*contourList)[cTest];
+ contour->checkMultiples();
+ }
+}
+
+// A small interval of a pair of curves may collapse to lines for each, triggering coincidence
+static void checkSmall(SkTArray<SkOpContour*, true>* contourList) {
+ int contourCount = (*contourList).count();
+ for (int cTest = 0; cTest < contourCount; ++cTest) {
+ SkOpContour* contour = (*contourList)[cTest];
+ contour->checkSmall();
+ }
+}
+
// A tiny interval may indicate an undiscovered coincidence. Find and fix.
static void checkTiny(SkTArray<SkOpContour*, true>* contourList) {
int contourCount = (*contourList).count();
@@ -386,6 +424,14 @@
}
}
+static void sortAngles(SkTArray<SkOpContour*, true>* contourList) {
+ int contourCount = (*contourList).count();
+ for (int cTest = 0; cTest < contourCount; ++cTest) {
+ SkOpContour* contour = (*contourList)[cTest];
+ contour->sortAngles();
+ }
+}
+
static void sortSegments(SkTArray<SkOpContour*, true>* contourList) {
int contourCount = (*contourList).count();
for (int cTest = 0; cTest < contourCount; ++cTest) {
@@ -613,7 +659,7 @@
#endif
}
-void HandleCoincidence(SkTArray<SkOpContour*, true>* contourList, int total) {
+bool HandleCoincidence(SkTArray<SkOpContour*, true>* contourList, int total) {
#if DEBUG_SHOW_WINDING
SkOpContour::debugShowWindingValues(contourList);
#endif
@@ -623,10 +669,18 @@
#endif
fixOtherTIndex(contourList);
checkEnds(contourList);
+ checkMultiples(contourList);
+ checkDuplicates(contourList);
checkTiny(contourList);
+ checkSmall(contourList);
joinCoincidence(contourList);
sortSegments(contourList);
+ if (!calcAngles(contourList)) {
+ return false;
+ }
+ sortAngles(contourList);
#if DEBUG_ACTIVE_SPANS || DEBUG_ACTIVE_SPANS_FIRST_ONLY
DebugShowActiveSpans(*contourList);
#endif
+ return true;
}