shape ops work in progress
first cut at getting binary ops to work
(union/intersection/diff/xor)
git-svn-id: http://skia.googlecode.com/svn/trunk@6375 2bbb7eff-a529-9590-31e7-b0007b416f81
diff --git a/experimental/Intersection/ShapeOps.cpp b/experimental/Intersection/ShapeOps.cpp
index 669fa6d..dad482a 100644
--- a/experimental/Intersection/ShapeOps.cpp
+++ b/experimental/Intersection/ShapeOps.cpp
@@ -10,37 +10,146 @@
#include "Simplify.cpp"
-static bool windingIsActive(int winding, int spanWinding, int oppWinding,
- const ShapeOp op) {
- return winding * spanWinding <= 0 && abs(winding) <= abs(spanWinding)
- && (!winding || !spanWinding || winding == -spanWinding);
+// FIXME: this and find chase should be merge together, along with
+// other code that walks winding in angles
+// OPTIMIZATION: Probably, the walked winding should be rolled into the angle structure
+// so it isn't duplicated by walkers like this one
+static Segment* findChaseOp(SkTDArray<Span*>& chase, int& tIndex, int& endIndex) {
+ while (chase.count()) {
+ Span* span;
+ chase.pop(&span);
+ const Span& backPtr = span->fOther->span(span->fOtherIndex);
+ Segment* segment = backPtr.fOther;
+ tIndex = backPtr.fOtherIndex;
+ SkTDArray<Angle> angles;
+ int done = 0;
+ if (segment->activeAngle(tIndex, done, angles)) {
+ Angle* last = angles.end() - 1;
+ 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()) {
+ continue;
+ }
+ SkTDArray<Angle*> sorted;
+ bool sortable = Segment::SortAngles(angles, sorted);
+#if DEBUG_SORT
+ sorted[0]->segment()->debugShowSort(__FUNCTION__, sorted, 0, 0, 0);
+#endif
+ if (!sortable) {
+ continue;
+ }
+ // find first angle, initialize winding to computed fWindSum
+ int firstIndex = -1;
+ const Angle* angle;
+ int winding;
+ do {
+ angle = sorted[++firstIndex];
+ 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);
+ #endif
+ // turn span winding into contour winding
+ if (spanWinding * winding < 0) {
+ winding += spanWinding;
+ }
+ // 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 angleCount = sorted.count();
+ int lastIndex = firstIndex != 0 ? firstIndex : angleCount;
+ angle = sorted[firstIndex];
+ segment = angle->segment();
+ int oWinding = segment->oppSum(angle);
+ #if DEBUG_SORT
+ segment->debugShowSort(__FUNCTION__, sorted, firstIndex, winding, oWinding);
+ #endif
+ winding -= segment->spanSign(angle);
+ bool firstOperand = segment->operand();
+ do {
+ SkASSERT(nextIndex != firstIndex);
+ if (nextIndex == angleCount) {
+ nextIndex = 0;
+ }
+ angle = sorted[nextIndex];
+ segment = angle->segment();
+ int deltaSum = segment->spanSign(angle);
+ bool angleIsOp = segment->operand() ^ firstOperand;
+ int maxWinding;
+ if (angleIsOp) {
+ maxWinding = oWinding;
+ oWinding -= deltaSum;
+ } else {
+ maxWinding = winding;
+ winding -= deltaSum;
+ }
+ #if DEBUG_SORT
+ SkDebugf("%s id=%d maxWinding=%d winding=%d oWinding=%d sign=%d\n", __FUNCTION__,
+ segment->debugID(), maxWinding, winding, oWinding, angle->sign());
+ #endif
+ tIndex = angle->start();
+ endIndex = angle->end();
+ int lesser = SkMin32(tIndex, endIndex);
+ const Span& nextSpan = segment->span(lesser);
+ if (!nextSpan.fDone) {
+ if (angleIsOp) {
+ SkTSwap(winding, oWinding);
+ }
+ if (useInnerWinding(maxWinding, winding)) {
+ maxWinding = winding;
+ }
+ segment->markWinding(lesser, maxWinding, oWinding);
+ break;
+ }
+ } while (++nextIndex != lastIndex);
+ #if TRY_ROTATE
+ *chase.insert(0) = span;
+ #else
+ *chase.append() = span;
+ #endif
+ return segment;
+ }
+ return NULL;
}
-static void bridgeOp(SkTDArray<Contour*>& contourList, const ShapeOp op,
+static bool windingIsActive(int winding, int oppWinding, int spanWinding,
+ bool windingIsOp, ShapeOp op) {
+ bool active = windingIsActive(winding, spanWinding);
+ if (!active) {
+ return false;
+ }
+ bool opActive = oppWinding != 0;
+ return gOpLookup[op][opActive][windingIsOp];
+}
+
+static bool bridgeOp(SkTDArray<Contour*>& contourList, const ShapeOp op,
const int aXorMask, const int bXorMask, PathWrapper& simple) {
bool firstContour = true;
+ bool unsortable = false;
+ bool closable = true;
SkPoint topLeft = {SK_ScalarMin, SK_ScalarMin};
do {
-
-#if SORTABLE_CONTOURS // old way
- Segment* topStart = findTopContour(contourList);
- if (!topStart) {
- break;
- }
- // Start at the top. Above the top is outside, below is inside.
- // follow edges to intersection by changing the index by direction.
- int index, endIndex;
- Segment* current = topStart->findTop(index, endIndex);
-#else // new way: iterate while top is unsortable
int index, endIndex;
Segment* current = findSortableTop(contourList, index, endIndex, topLeft);
if (!current) {
break;
}
-#endif
- int contourWinding;
+ int contourWinding, oppContourWinding;
if (firstContour) {
- contourWinding = 0;
+ contourWinding = oppContourWinding = 0;
firstContour = false;
} else {
int sumWinding = current->windSum(SkMin32(index, endIndex));
@@ -50,9 +159,16 @@
}
if (sumWinding == SK_MinS32) {
contourWinding = innerContourCheck(contourList, current,
- index, endIndex);
+ index, endIndex, false);
+ oppContourWinding = innerContourCheck(contourList, current,
+ index, endIndex, true);
} else {
contourWinding = sumWinding;
+ oppContourWinding = 0;
+ SkASSERT(0);
+ // FIXME: need to get oppContourWinding by building sort wheel and
+ // retrieving sumWinding of uphill opposite span, calling inner contour check
+ // if need be
int spanWinding = current->spanSign(index, endIndex);
bool inner = useInnerWinding(sumWinding - spanWinding, sumWinding);
if (inner) {
@@ -69,79 +185,69 @@
SkDebugf("%s contourWinding=%d\n", __FUNCTION__, contourWinding);
#endif
}
- // SkPoint lastPt;
int winding = contourWinding;
+ int oppWinding = oppContourWinding;
int spanWinding = current->spanSign(index, endIndex);
- int oppWinding = current->oppSign(index, endIndex);
- bool active = windingIsActive(winding, spanWinding, oppWinding, op);
SkTDArray<Span*> chaseArray;
- bool unsortable = false;
do {
+ bool active = windingIsActive(winding, oppWinding, spanWinding,
+ current->operand(), op);
#if DEBUG_WINDING
- SkDebugf("%s active=%s winding=%d spanWinding=%d\n",
+ SkDebugf("%s active=%s winding=%d oppWinding=%d spanWinding=%d\n",
__FUNCTION__, active ? "true" : "false",
- winding, spanWinding);
+ winding, oppWinding, spanWinding);
#endif
- // const SkPoint* firstPt = NULL;
do {
- SkASSERT(!current->done());
+ #if DEBUG_ACTIVE_SPANS
+ if (!unsortable && current->done()) {
+ debugShowActiveSpans(contourList);
+ }
+ #endif
+ SkASSERT(unsortable || !current->done());
int nextStart = index;
int nextEnd = endIndex;
Segment* next = current->findNextOp(chaseArray, active,
- nextStart, nextEnd, winding, spanWinding, unsortable, op,
- aXorMask, bXorMask);
+ nextStart, nextEnd, winding, oppWinding, spanWinding,
+ unsortable, op, aXorMask, bXorMask);
if (!next) {
- // FIXME: if unsortable, allow partial paths to be later
- // assembled
SkASSERT(!unsortable);
- if (active && simple.hasMove()
+ if (active && !unsortable && simple.hasMove()
&& current->verb() != SkPath::kLine_Verb
&& !simple.isClosed()) {
- /* lastPt = */ current->addCurveTo(index, endIndex, simple, true);
+ current->addCurveTo(index, endIndex, simple, true);
SkASSERT(simple.isClosed());
}
break;
}
- // if (!firstPt) {
- // firstPt = ¤t->addMoveTo(index, simple, active);
- // }
- /* lastPt = */ current->addCurveTo(index, endIndex, simple, active);
+ current->addCurveTo(index, endIndex, simple, active);
current = next;
index = nextStart;
endIndex = nextEnd;
- } while (!simple.isClosed() && (active || !current->done()));
- if (simple.hasMove() && active) {
- #if DEBUG_PATH_CONSTRUCTION
- SkDebugf("%s close\n", __FUNCTION__);
- #endif
+ } while (!simple.isClosed()
+ && ((active && !unsortable) || !current->done()));
+ if (active) {
+ if (!simple.isClosed()) {
+ SkASSERT(unsortable);
+ int min = SkMin32(index, endIndex);
+ if (!current->done(min)) {
+ current->addCurveTo(index, endIndex, simple, true);
+ current->markDone(SkMin32(index, endIndex), winding ? winding : spanWinding);
+ }
+ closable = false;
+ }
simple.close();
}
- current = findChase(chaseArray, index, endIndex, contourWinding);
+ current = findChaseOp(chaseArray, index, endIndex);
#if DEBUG_ACTIVE_SPANS
debugShowActiveSpans(contourList);
#endif
if (!current) {
break;
}
- int lesser = SkMin32(index, endIndex);
- spanWinding = current->spanSign(index, endIndex);
- winding = current->windSum(lesser);
- bool inner = useInnerWinding(winding - spanWinding, winding);
- #if DEBUG_WINDING
- SkDebugf("%s id=%d t=%1.9g spanWinding=%d winding=%d sign=%d"
- " inner=%d result=%d\n",
- __FUNCTION__, current->debugID(), current->t(lesser),
- spanWinding, winding, SkSign32(index - endIndex),
- useInnerWinding(winding - spanWinding, winding),
- inner ? winding - spanWinding : winding);
- #endif
- if (inner) {
- winding -= spanWinding;
- }
- int oppWinding = current->oppSign(index, endIndex);
- active = windingIsActive(winding, spanWinding, oppWinding, op);
+ winding = updateWindings(current, index, endIndex, spanWinding, &oppWinding);
} while (true);
} while (true);
+ return closable;
}
} // end of Op namespace
@@ -177,6 +283,10 @@
// eat through coincident edges
coincidenceCheck(contourList);
fixOtherTIndex(contourList);
+ sortSegments(contourList);
+#if DEBUG_ACTIVE_SPANS
+ debugShowActiveSpans(contourList);
+#endif
// construct closed contours
Op::PathWrapper wrapper(result);
bridgeOp(contourList, op, aXorMask, bXorMask, wrapper);