aboutsummaryrefslogtreecommitdiffhomepage
path: root/src/pathops/SkPathOpsCommon.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'src/pathops/SkPathOpsCommon.cpp')
-rw-r--r--src/pathops/SkPathOpsCommon.cpp158
1 files changed, 106 insertions, 52 deletions
diff --git a/src/pathops/SkPathOpsCommon.cpp b/src/pathops/SkPathOpsCommon.cpp
index c48a7eef68..f34148390c 100644
--- a/src/pathops/SkPathOpsCommon.cpp
+++ b/src/pathops/SkPathOpsCommon.cpp
@@ -111,75 +111,62 @@ SkOpSegment* FindUndone(SkTArray<SkOpContour*, true>& contourList, int* start, i
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 @@ SkOpSegment* FindChase(SkTDArray<SkOpSpan*>& chase, int& tIndex, int& endIndex)
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 @@ SkOpSegment* FindChase(SkTDArray<SkOpSpan*>& chase, int& tIndex, int& endIndex)
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 @@ static SkOpSegment* findSortableTop(const SkTArray<SkOpContour*, true>& contourL
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 @@ static SkOpSegment* findSortableTop(const SkTArray<SkOpContour*, true>& contourL
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 @@ SkOpSegment* FindSortableTop(const SkTArray<SkOpContour*, true>& contourList,
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 @@ SkOpSegment* FindSortableTop(const SkTArray<SkOpContour*, true>& contourList,
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 @@ SkOpSegment* FindSortableTop(const SkTArray<SkOpContour*, true>& contourList,
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 checkEnds(SkTArray<SkOpContour*, true>* contourList) {
}
}
+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 joinCoincidence(SkTArray<SkOpContour*, true>* contourList) {
}
}
+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 @@ void Assemble(const SkPathWriter& path, SkPathWriter* simple) {
#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 @@ void HandleCoincidence(SkTArray<SkOpContour*, true>* contourList, int total) {
#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;
}
generated by cgit v1.2.3 (git 2.39.1) at 2024-12-06 20:58:11 +0000