aboutsummaryrefslogtreecommitdiffhomepage
diff options
context:
space:
mode:
authorGravatar caryclark@google.com <caryclark@google.com@2bbb7eff-a529-9590-31e7-b0007b416f81>2012-11-14 21:14:56 +0000
committerGravatar caryclark@google.com <caryclark@google.com@2bbb7eff-a529-9590-31e7-b0007b416f81>2012-11-14 21:14:56 +0000
commit57cff8dbdfb32b3fea426519a4fdc05f13be69d9 (patch)
tree45721a1469731bc8a82b5516d00fb8df3489124e
parent459e6623f1c014136f2a8df34c4af80f994eccf0 (diff)
shape ops work in progress
binary ops work for simple coincident case git-svn-id: http://skia.googlecode.com/svn/trunk@6422 2bbb7eff-a529-9590-31e7-b0007b416f81
-rw-r--r--experimental/Intersection/ShapeOps.cpp36
-rw-r--r--experimental/Intersection/Simplify.cpp299
-rw-r--r--experimental/Intersection/SimplifyNew_Test.cpp100
3 files changed, 288 insertions, 147 deletions
diff --git a/experimental/Intersection/ShapeOps.cpp b/experimental/Intersection/ShapeOps.cpp
index 5356ca6bb6..fa29ab769c 100644
--- a/experimental/Intersection/ShapeOps.cpp
+++ b/experimental/Intersection/ShapeOps.cpp
@@ -78,6 +78,7 @@ static Segment* findChaseOp(SkTDArray<Span*>& chase, int& tIndex, int& endIndex)
segment->debugShowSort(__FUNCTION__, sorted, firstIndex, winding, oWinding);
#endif
winding -= segment->spanSign(angle);
+ oWinding -= segment->oppSign(angle);
bool firstOperand = segment->operand();
do {
SkASSERT(nextIndex != firstIndex);
@@ -87,14 +88,17 @@ static Segment* findChaseOp(SkTDArray<Span*>& chase, int& tIndex, int& endIndex)
angle = sorted[nextIndex];
segment = angle->segment();
int deltaSum = segment->spanSign(angle);
+ int deltaOppSum = segment->oppSign(angle);
bool angleIsOp = segment->operand() ^ firstOperand;
int maxWinding;
if (angleIsOp) {
maxWinding = oWinding;
oWinding -= deltaSum;
+ winding -= deltaOppSum;
} else {
maxWinding = winding;
winding -= deltaSum;
+ oWinding -= deltaOppSum;
}
#if DEBUG_SORT
SkDebugf("%s id=%d maxWinding=%d winding=%d oWinding=%d sign=%d\n", __FUNCTION__,
@@ -125,16 +129,31 @@ static Segment* findChaseOp(SkTDArray<Span*>& chase, int& tIndex, int& endIndex)
return NULL;
}
-static bool windingIsActive(int winding, int oppWinding, int spanWinding,
+static bool windingIsActive(int winding, int oppWinding, int spanWinding, int oppSpanWinding,
bool windingIsOp, ShapeOp op) {
bool active = windingIsActive(winding, spanWinding);
if (!active) {
return false;
}
+ if (oppSpanWinding && windingIsActive(oppWinding, oppSpanWinding)) {
+ return op == kIntersect_Op || op == kUnion_Op;
+ }
bool opActive = oppWinding != 0;
return gOpLookup[op][opActive][windingIsOp];
}
+static int updateWindings(const Segment* current, int index, int endIndex,
+ int& spanWinding, int& oppWinding, int& oppSpanWinding) {
+ int winding = updateWindings(current, index, endIndex, spanWinding);
+ int lesser = SkMin32(index, endIndex);
+ oppWinding = current->oppSum(lesser);
+ oppSpanWinding = current->oppSign(index, endIndex);
+ if (oppSpanWinding && useInnerWinding(oppWinding - oppSpanWinding, oppWinding)) {
+ oppWinding -= oppSpanWinding;
+ }
+ return winding;
+}
+
static bool bridgeOp(SkTDArray<Contour*>& contourList, const ShapeOp op,
const int aXorMask, const int bXorMask, PathWrapper& simple) {
bool firstContour = true;
@@ -188,14 +207,15 @@ static bool bridgeOp(SkTDArray<Contour*>& contourList, const ShapeOp op,
int winding = contourWinding;
int oppWinding = oppContourWinding;
int spanWinding = current->spanSign(index, endIndex);
+ int oppSpanWinding = current->oppSign(index, endIndex);
SkTDArray<Span*> chaseArray;
do {
- bool active = windingIsActive(winding, oppWinding, spanWinding,
+ bool active = windingIsActive(winding, oppWinding, spanWinding, oppSpanWinding,
current->operand(), op);
#if DEBUG_WINDING
- SkDebugf("%s active=%s winding=%d oppWinding=%d spanWinding=%d\n",
+ SkDebugf("%s active=%s winding=%d oppWinding=%d spanWinding=%d oppSpanWinding=%d\n",
__FUNCTION__, active ? "true" : "false",
- winding, oppWinding, spanWinding);
+ winding, oppWinding, spanWinding, oppSpanWinding);
#endif
do {
#if DEBUG_ACTIVE_SPANS
@@ -207,7 +227,7 @@ static bool bridgeOp(SkTDArray<Contour*>& contourList, const ShapeOp op,
int nextStart = index;
int nextEnd = endIndex;
Segment* next = current->findNextOp(chaseArray, active,
- nextStart, nextEnd, winding, oppWinding, spanWinding,
+ nextStart, nextEnd, winding, oppWinding, spanWinding, oppSpanWinding,
unsortable, op, aXorMask, bXorMask);
if (!next) {
SkASSERT(!unsortable);
@@ -244,7 +264,8 @@ static bool bridgeOp(SkTDArray<Contour*>& contourList, const ShapeOp op,
if (!current) {
break;
}
- winding = updateWindings(current, index, endIndex, spanWinding, &oppWinding);
+ winding = updateWindings(current, index, endIndex, spanWinding, oppWinding,
+ oppSpanWinding);
} while (true);
} while (true);
return closable;
@@ -281,7 +302,8 @@ void operate(const SkPath& one, const SkPath& two, ShapeOp op, SkPath& result) {
} while (addIntersectTs(current, next) && nextPtr != listEnd);
} while (currentPtr != listEnd);
// eat through coincident edges
- coincidenceCheck(contourList);
+ coincidenceCheck(contourList, (aXorMask == kEvenOdd_Mask)
+ ^ (bXorMask == kEvenOdd_Mask));
fixOtherTIndex(contourList);
sortSegments(contourList);
#if DEBUG_ACTIVE_SPANS
diff --git a/experimental/Intersection/Simplify.cpp b/experimental/Intersection/Simplify.cpp
index 42610291e6..80c3566028 100644
--- a/experimental/Intersection/Simplify.cpp
+++ b/experimental/Intersection/Simplify.cpp
@@ -482,6 +482,7 @@ struct Span {
int fWindSum; // accumulated from contours surrounding this one.
int fOppSum; // for binary operators: the opposite winding sum
int fWindValue; // 0 == canceled; 1 == normal; >1 == coincident
+ int fOppValue; // normally 0 -- when binary coincident edges combine, opp value goes here
bool fDone; // if set, this span to next higher T has been processed
bool fUnsortableStart; // set when start is part of an unsortable pair
bool fUnsortableEnd; // set when end is part of an unsortable pair
@@ -837,7 +838,10 @@ static const bool gOpLookup[][2][2] = {
{{true , true }, {true , true }}, // a ^ b
};
-static bool activeOp(bool angleIsOp, int otherNonZero, ShapeOp op) {
+static bool activeOp(bool angleIsOp, int otherNonZero, int otherCoin, ShapeOp op) {
+ if (otherNonZero != otherCoin) {
+ return op == kIntersect_Op || op == kUnion_Op;
+ }
return gOpLookup[op][otherNonZero][angleIsOp];
}
@@ -1334,6 +1338,7 @@ public:
span->fWindSum = SK_MinS32;
span->fOppSum = SK_MinS32;
span->fWindValue = 1;
+ span->fOppValue = 0;
span->fTiny = false;
if ((span->fDone = newT == 1)) {
++fDoneSpans;
@@ -1460,14 +1465,105 @@ public:
other.addCancelOutsides(tStart, oStart, *this, endT);
}
}
+
+ int bumpCoincidentThis(const Span* oTest, const bool transfer, const bool decrementThis,
+ const bool thisXor, const bool opp, int index, SkTDArray<double>& outsideTs,
+ SkTDArray<double>& xOutsideTs)
+ {
+ Span* const test = &fTs[index];
+ Span* end = test;
+ const int startIndex = index;
+ const double oStartT = oTest->fT;
+ do {
+ if (transfer) {
+ if (!decrementThis & !thisXor & !opp) {
+ #ifdef SK_DEBUG
+ SkASSERT(abs(end->fWindValue) < gDebugMaxWindValue);
+ #endif
+ ++(end->fWindValue);
+ } else if (decrementSpan(end)) {
+ TrackOutside(outsideTs, end->fT, oStartT);
+ }
+ } else if (opp) {
+ if (decrementThis) {
+ if (decrementSpan(end)) {
+ TrackOutside(outsideTs, end->fT, oStartT);
+ }
+ } else {
+ end->fOppValue += oTest->fWindValue;
+ }
+ } else if (oTest->fWindValue) {
+ SkASSERT(decrementThis);
+ if (startIndex > 0 && fTs[startIndex - 1].fWindValue) {
+ TrackOutside(xOutsideTs, end->fT, oStartT);
+ }
+ }
+ end = &fTs[++index];
+ } while (approximately_negative(end->fT - test->fT));
+ return index;
+ }
+
+ // because of the order in which coincidences are resolved, this and other
+ // may not have the same intermediate points. Compute the corresponding
+ // intermediate T values (using this as the master, other as the follower)
+ // and walk other conditionally -- hoping that it catches up in the end
+ int bumpCoincidentOther(const Span* test, const bool transfer, const bool decrementThis,
+ const bool otherXor, const bool opp, const double tRatio, const double oEndT,
+ int& oIndex, SkTDArray<double>& oOutsideTs)
+ {
+ Span* const oTest = &fTs[oIndex];
+ Span* oEnd = oTest;
+ const double startT = test->fT;
+ const int oStartIndex = oIndex;
+ const double oStartT = oTest->fT;
+ double otherTMatch = (test->fT - startT) * tRatio + oStartT;
+ while (!approximately_negative(oEndT - oEnd->fT)
+ && approximately_negative(oEnd->fT - otherTMatch)) {
+ if (transfer) {
+ if (decrementThis & !otherXor & !opp) {
+ #ifdef SK_DEBUG
+ SkASSERT(abs(oEnd->fWindValue) < gDebugMaxWindValue);
+ #endif
+ ++(oEnd->fWindValue);
+ } else if (decrementSpan(oEnd)) {
+ TrackOutside(oOutsideTs, oEnd->fT, startT);
+ }
+ } else if (opp) {
+ if (decrementThis) {
+ oEnd->fOppValue += test->fWindValue;
+ } else {
+ if (decrementSpan(oEnd)) {
+ TrackOutside(oOutsideTs, oEnd->fT, startT);
+ }
+ }
+ } else if (test->fWindValue) {
+ SkASSERT(decrementThis);
+ if (oStartIndex > 0 && fTs[oStartIndex - 1].fWindValue) {
+ SkASSERT(0); // track for later?
+ }
+ }
+ oEnd = &fTs[++oIndex];
+ }
+ return oIndex;
+ }
+
+ // FIXME: need to test this case:
+ // contourA has two segments that are coincident
+ // contourB has two segments that are coincident in the same place
+ // each ends up with +2/0 pairs for winding count
+ // since logic below doesn't transfer count (only increments/decrements) can this be
+ // resolved to +4/0 ?
// set spans from start to end to increment the greater by one and decrement
// the lesser
- void addTCoincident(bool isXor, double startT, double endT,
+ void addTCoincident(bool thisXor, bool otherXor, double startT, double endT,
Segment& other, double oStartT, double oEndT) {
SkASSERT(!approximately_negative(endT - startT));
SkASSERT(!approximately_negative(oEndT - oStartT));
- isXor |= fOperand != other.fOperand;
+ bool opp = fOperand ^ other.fOperand;
+ if (!opp) {
+ otherXor = thisXor;
+ }
int index = 0;
while (!approximately_negative(startT - fTs[index].fT)) {
++index;
@@ -1482,61 +1578,22 @@ public:
SkTDArray<double> outsideTs;
SkTDArray<double> xOutsideTs;
SkTDArray<double> oOutsideTs;
- SkTDArray<double> oxOutsideTs;
do {
- bool transfer = test->fWindValue && oTest->fWindValue;
- bool decrementThis = (test->fWindValue < oTest->fWindValue) & !isXor;
- bool decrementOther = (test->fWindValue >= oTest->fWindValue) & !isXor;
- Span* end = test;
- double startT = end->fT;
- int startIndex = index;
- double oStartT = oTest->fT;
- int oStartIndex = oIndex;
- do {
- if (transfer) {
- if (decrementOther) {
- #ifdef SK_DEBUG
- SkASSERT(abs(end->fWindValue) < gDebugMaxWindValue);
- #endif
- ++(end->fWindValue);
- } else if (decrementSpan(end)) {
- TrackOutside(outsideTs, end->fT, oStartT);
- }
- } else if (oTest->fWindValue) {
- SkASSERT(!decrementOther);
- if (startIndex > 0 && fTs[startIndex - 1].fWindValue) {
- TrackOutside(xOutsideTs, end->fT, oStartT);
- }
- }
- end = &fTs[++index];
- } while (approximately_negative(end->fT - test->fT));
- // because of the order in which coincidences are resolved, this and other
- // may not have the same intermediate points. Compute the corresponding
- // intermediate T values (using this as the master, other as the follower)
- // and walk other conditionally -- hoping that it catches up in the end
- double otherTMatch = (test->fT - startT) * tRatio + oStartT;
- Span* oEnd = oTest;
- while (!approximately_negative(oEndT - oEnd->fT)
- && approximately_negative(oEnd->fT - otherTMatch)) {
- if (transfer) {
- if (decrementThis) {
- #ifdef SK_DEBUG
- SkASSERT(abs(oEnd->fWindValue) < gDebugMaxWindValue);
- #endif
- ++(oEnd->fWindValue);
- } else if (other.decrementSpan(oEnd)) {
- TrackOutside(oOutsideTs, oEnd->fT, startT);
- }
- } else if (test->fWindValue) {
- SkASSERT(!decrementOther);
- if (oStartIndex > 0 && other.fTs[oStartIndex - 1].fWindValue) {
- SkASSERT(0); // track for later?
- }
- }
- oEnd = &other.fTs[++oIndex];
+ bool transfer = test->fWindValue && oTest->fWindValue && !opp;
+ bool decrementThis = test->fWindValue < oTest->fWindValue;
+ if (decrementThis) {
+ oIndex = other.bumpCoincidentOther(test, transfer, decrementThis, otherXor, opp,
+ tRatio, oEndT, oIndex, oOutsideTs);
+ index = bumpCoincidentThis(oTest, transfer, decrementThis, thisXor, opp,
+ index, outsideTs, xOutsideTs);
+ } else {
+ index = bumpCoincidentThis(oTest, transfer, decrementThis, thisXor, opp,
+ index, outsideTs, xOutsideTs);
+ oIndex = other.bumpCoincidentOther(test, transfer, decrementThis, otherXor, opp,
+ tRatio, oEndT, oIndex, oOutsideTs);
}
- test = end;
- oTest = oEnd;
+ test = &fTs[index];
+ oTest = &other.fTs[oIndex];
} while (!approximately_negative(endT - test->fT));
SkASSERT(approximately_negative(oTest->fT - oEndT));
SkASSERT(approximately_negative(oEndT - oTest->fT));
@@ -1811,7 +1868,7 @@ public:
Segment* findNextOp(SkTDArray<Span*>& chase, bool active,
int& nextStart, int& nextEnd, int& winding, int& oppWinding,
- int& spanWinding, bool& unsortable, ShapeOp op,
+ int& spanWinding, int& oppSpanWinding, bool& unsortable, ShapeOp op,
const int aXorMask, const int bXorMask) {
const int startIndex = nextStart;
const int endIndex = nextEnd;
@@ -1824,6 +1881,13 @@ public:
if (useInnerWinding(outerWinding, innerWinding)) {
outerWinding = innerWinding;
}
+ int outerOppWinding = oppWinding;
+ if (oppSpanWinding) {
+ int innerOppWinding = oppWinding + oppSpanWinding;
+ if (useInnerWinding(oppWinding, innerOppWinding)) {
+ outerOppWinding = innerOppWinding;
+ }
+ }
SkASSERT(startIndex != endIndex);
int count = fTs.count();
SkASSERT(startIndex < endIndex ? startIndex < count - 1
@@ -1839,7 +1903,7 @@ public:
#if DEBUG_WINDING
SkDebugf("%s simple\n", __FUNCTION__);
#endif
- markDone(SkMin32(startIndex, endIndex), outerWinding, oppWinding);
+ markDone(SkMin32(startIndex, endIndex), outerWinding, outerOppWinding);
other = endSpan->fOther;
nextStart = endSpan->fOtherIndex;
double startT = other->fTs[nextStart].fT;
@@ -1871,16 +1935,21 @@ public:
}
SkASSERT(sorted[firstIndex]->segment() == this);
#if DEBUG_WINDING
- SkDebugf("%s [%d] sign=%d\n", __FUNCTION__, firstIndex, sorted[firstIndex]->sign());
+ SkDebugf("%s firstIndex=[%d] sign=%d\n", __FUNCTION__, firstIndex,
+ sorted[firstIndex]->sign());
#endif
int aSumWinding = winding;
int bSumWinding = oppWinding;
bool angleIsOp = sorted[firstIndex]->segment()->operand() ^ operand();
- int angleSpan = spanSign(sorted[firstIndex]);
+ const Angle* firstAngle = sorted[firstIndex];
+ int angleSpan = spanSign(firstAngle);
+ int oppoSign = oppSign(firstAngle);
if (angleIsOp) {
bSumWinding -= angleSpan;
+ aSumWinding -= oppoSign;
} else {
aSumWinding -= angleSpan;
+ bSumWinding -= oppoSign;
}
int nextIndex = firstIndex + 1;
int lastIndex = firstIndex != 0 ? firstIndex : angleCount;
@@ -1913,8 +1982,9 @@ public:
bool nextTiny = nextSegment->tiny(*nextAngle);
angleIsOp = nextSegment->operand() ^ operand();
int deltaSum = nextSegment->spanSign(nextAngle);
+ int oppDeltaSum = nextSegment->oppSign(nextAngle);
int maxWinding, xorMask, sumWinding;
- bool otherNonZero, altFlipped;
+ bool otherNonZero, altFlipped, otherCoin;
if (angleIsOp) {
maxWinding = bSumWinding;
if (bSumWinding) {
@@ -1926,6 +1996,8 @@ public:
xorMask = bXorMask;
bAltFlipped ^= bLastNonZeroSum * bSumWinding < 0; // flip if different signs
altFlipped = bAltFlipped;
+ aSumWinding -= oppDeltaSum;
+ otherCoin = aSumWinding & aXorMask;
} else {
maxWinding = aSumWinding;
if (aSumWinding) {
@@ -1937,12 +2009,14 @@ public:
xorMask = aXorMask;
aAltFlipped ^= aLastNonZeroSum * aSumWinding < 0; // flip if different signs
altFlipped = aAltFlipped;
+ bSumWinding -= oppDeltaSum;
+ otherCoin = bSumWinding & bXorMask;
}
- bool opIsActive = activeOp(nextSegment->operand(), otherNonZero, op);
+ bool opIsActive = activeOp(nextSegment->operand(), otherNonZero, otherCoin, op);
int oWinding = angleIsOp ? aSumWinding : bSumWinding;
if (!(sumWinding & xorMask)) {
if (!active) {
- markAndChaseDone(startIndex, endIndex, outerWinding, oppWinding);
+ markAndChaseDone(startIndex, endIndex, outerWinding, outerOppWinding);
nextSegment->markAndChaseWinding(nextAngle, maxWinding, oWinding);
#if DEBUG_WINDING
SkDebugf("%s [%d] inactive\n", __FUNCTION__, nextIndex);
@@ -1994,7 +2068,7 @@ public:
}
}
} while (++nextIndex != lastIndex);
- markDone(SkMin32(startIndex, endIndex), outerWinding, oppWinding);
+ markDone(SkMin32(startIndex, endIndex), outerWinding, outerOppWinding);
if (!foundAngle) {
return NULL;
}
@@ -2005,14 +2079,17 @@ public:
nextEnd = foundAngle->end();
nextSegment = foundAngle->segment();
int flipped = foundFlipped ? -1 : 1;
- spanWinding = SkSign32(spanWinding) * flipped * nextSegment->windValue(
- SkMin32(nextStart, nextEnd));
+ int minStartEnd = SkMin32(nextStart, nextEnd);
+ spanWinding = SkSign32(spanWinding) * flipped * nextSegment->windValue(minStartEnd);
+ oppSpanWinding = SkSign32(oppSpanWinding) * flipped * nextSegment->oppValue(minStartEnd);
+
#if DEBUG_WINDING
SkDebugf("%s foundFlipped=%d spanWinding=%d oldSpanSign=%d spanSign=%d\n",
__FUNCTION__, foundFlipped, spanWinding, oldSpanSign,
nextSegment->spanSign(foundAngle));
- SkDebugf("%s foundOpp=%d oppWinding=%d foundOppWinding=%d winding=%d foundSum=",
- __FUNCTION__, foundOpp, oppWinding, foundOppWinding, winding);
+ SkDebugf("%s foundOpp=%d oppWinding=%d oppSpanWinding=%d foundOppWinding=%d winding=%d"
+ " foundSum=", __FUNCTION__, foundOpp, oppWinding, oppSpanWinding, foundOppWinding,
+ winding);
if (foundSum == SK_MinS32) {
SkDebugf("?");
} else {
@@ -2026,6 +2103,7 @@ public:
SkASSERT(foundSum != SK_MinS32);
winding = foundSum;
spanWinding = nextSegment->spanSign(foundAngle);
+ oppSpanWinding = nextSegment->oppSign(foundAngle);
}
}
return nextSegment;
@@ -2333,7 +2411,7 @@ public:
}
// FIXME: this is tricky code; needs its own unit test
- void findTooCloseToCall(bool isXor) {
+ void findTooCloseToCall(bool thisXor, bool otherXor) {
int count = fTs.count();
if (count < 3) { // require t=0, x, 1 at minimum
return;
@@ -2459,7 +2537,8 @@ public:
// FIXME: this is bogus for multiple ops
// the xorMask needs to be accumulated from the union of the two
// edges -- which means that the segment must have its own copy of the mask
- mOther->addTCoincident(isXor, moStartT, moEndT, *tOther, toStartT, toEndT);
+ mOther->addTCoincident(thisXor, otherXor,
+ moStartT, moEndT, *tOther, toStartT, toEndT);
}
}
}
@@ -2965,6 +3044,20 @@ public:
return fOperand;
}
+ int oppSign(const Angle* angle) const {
+ SkASSERT(angle->segment() == this);
+ return oppSign(angle->start(), angle->end());
+ }
+
+ int oppSign(int startIndex, int endIndex) const {
+ int result = startIndex < endIndex ? -fTs[startIndex].fOppValue
+ : fTs[endIndex].fOppValue;
+#if DEBUG_WIND_BUMP
+ SkDebugf("%s oppSign=%d\n", __FUNCTION__, result);
+#endif
+ return result;
+ }
+
int oppSum(int tIndex) const {
return fTs[tIndex].fOppSum;
}
@@ -2974,6 +3067,10 @@ public:
return fTs[lesser].fOppSum;
}
+ int oppValue(int tIndex) const {
+ return fTs[tIndex].fOppValue;
+ }
+
const SkPoint* pts() const {
return fPts;
}
@@ -3320,8 +3417,10 @@ public:
SkASSERT(angles.count() > 1);
int lastSum = contourWinding;
int oppLastSum = oppContourWinding;
- int windSum = lastSum - spanSign(angles[first]);
- int oppWindSum = oppLastSum;
+ const Angle* firstAngle = angles[first];
+ int windSum = lastSum - spanSign(firstAngle);
+ int oppoSign = oppSign(firstAngle);
+ int oppWindSum = oppLastSum - oppoSign;
SkDebugf("%s %s contourWinding=%d oppContourWinding=%d sign=%d\n", fun, __FUNCTION__,
contourWinding, oppContourWinding, spanSign(angles[first]));
int index = first;
@@ -3336,12 +3435,21 @@ public:
const Span& mSpan = segment.fTs[SkMin32(start, end)];
bool opp = segment.fOperand ^ fOperand;
if (!firstTime) {
+ oppoSign = segment.oppSign(&angle);
if (opp) {
oppLastSum = oppWindSum;
oppWindSum -= segment.spanSign(&angle);
+ if (oppoSign) {
+ lastSum = windSum;
+ windSum -= oppoSign;
+ }
} else {
lastSum = windSum;
windSum -= segment.spanSign(&angle);
+ if (oppoSign) {
+ oppLastSum = oppWindSum;
+ oppWindSum -= oppoSign;
+ }
}
}
SkDebugf("%s [%d] %sid=%d %s start=%d (%1.9g,%,1.9g) end=%d (%1.9g,%,1.9g)"
@@ -3364,8 +3472,13 @@ public:
last = lastSum;
wind = windSum;
}
- SkDebugf(" winding: %d->%d (max=%d) ", last, wind,
- useInnerWinding(last, wind) ? wind : last);
+ if (!oppoSign) {
+ SkDebugf(" %d->%d (max=%d)", last, wind,
+ useInnerWinding(last, wind) ? wind : last);
+ } else {
+ SkDebugf(" %d->%d (%d->%d)", last, wind, opp ? lastSum : oppLastSum,
+ opp ? windSum : oppWindSum);
+ }
SkDebugf(" done=%d tiny=%d opp=%d\n", mSpan.fDone, mSpan.fTiny, opp);
#if false && DEBUG_ANGLE
angle.debugShow(segment.xyAtT(&sSpan));
@@ -3415,7 +3528,6 @@ struct Coincidence {
Contour* fContours[2];
int fSegments[2];
double fTs[2][2];
- bool fXor;
};
class Contour {
@@ -3436,7 +3548,7 @@ public:
void addCoincident(int index, Contour* other, int otherIndex,
const Intersections& ts, bool swap) {
Coincidence& coincidence = *fCoincidences.append();
- coincidence.fContours[0] = this;
+ coincidence.fContours[0] = this; // FIXME: no need to store
coincidence.fContours[1] = other;
coincidence.fSegments[0] = index;
coincidence.fSegments[1] = otherIndex;
@@ -3454,7 +3566,6 @@ public:
coincidence.fTs[!swap][0] = ts.fCoincidentT[1][0];
coincidence.fTs[!swap][1] = ts.fCoincidentT[1][1];
}
- coincidence.fXor = fOperand == other->fOperand ? fXor : true;
}
void addCross(const Contour* crosser) {
@@ -3559,10 +3670,11 @@ public:
return segment.pts()[segment.verb()];
}
- void findTooCloseToCall() {
+ void findTooCloseToCall(bool otherXor) {
int segmentCount = fSegments.count();
+ otherXor ^= fXor;
for (int sIndex = 0; sIndex < segmentCount; ++sIndex) {
- fSegments[sIndex].findTooCloseToCall(fXor);
+ fSegments[sIndex].findTooCloseToCall(fXor, otherXor);
}
}
@@ -3601,22 +3713,22 @@ public:
#endif
double startT = coincidence.fTs[0][0];
double endT = coincidence.fTs[0][1];
- bool opposite = false;
+ bool cancelers = false;
if (startT > endT) {
SkTSwap<double>(startT, endT);
- opposite ^= true;
+ cancelers ^= true; // FIXME: just assign true
}
SkASSERT(!approximately_negative(endT - startT));
double oStartT = coincidence.fTs[1][0];
double oEndT = coincidence.fTs[1][1];
if (oStartT > oEndT) {
SkTSwap<double>(oStartT, oEndT);
- opposite ^= true;
+ cancelers ^= true;
}
SkASSERT(!approximately_negative(oEndT - oStartT));
- if (opposite) {
- // make sure startT and endT have t entries
- SkASSERT(opposite);
+ bool opp = thisContour->fOperand ^ otherContour->fOperand;
+ if (cancelers && !opp) {
+ // make sure startT and endT have t entries
if (startT > 0 || oEndT < 1
|| thisOne.isMissing(startT) || other.isMissing(oEndT)) {
thisOne.addTPair(startT, other, oEndT, true);
@@ -3635,7 +3747,8 @@ public:
|| thisOne.isMissing(endT) || other.isMissing(oEndT)) {
other.addTPair(oEndT, thisOne, endT, true);
}
- thisOne.addTCoincident(coincidence.fXor, startT, endT, other, oStartT, oEndT);
+ thisOne.addTCoincident(thisContour->fXor, otherContour->fXor,
+ startT, endT, other, oStartT, oEndT);
}
#if DEBUG_CONCIDENT
thisOne.debugShowTs();
@@ -4502,7 +4615,7 @@ static bool addIntersectTs(Contour* test, Contour* next) {
// resolve any coincident pairs found while intersecting, and
// see if coincidence is formed by clipping non-concident segments
-static void coincidenceCheck(SkTDArray<Contour*>& contourList) {
+static void coincidenceCheck(SkTDArray<Contour*>& contourList, bool otherXor) {
int contourCount = contourList.count();
for (int cIndex = 0; cIndex < contourCount; ++cIndex) {
Contour* contour = contourList[cIndex];
@@ -4510,7 +4623,7 @@ static void coincidenceCheck(SkTDArray<Contour*>& contourList) {
}
for (int cIndex = 0; cIndex < contourCount; ++cIndex) {
Contour* contour = contourList[cIndex];
- contour->findTooCloseToCall();
+ contour->findTooCloseToCall(otherXor);
}
}
@@ -4828,8 +4941,7 @@ static Segment* findSortableTop(SkTDArray<Contour*>& contourList, int& index,
return result;
}
-static int updateWindings(const Segment* current, int index, int endIndex,
- int& spanWinding, int* oppWinding) {
+static int updateWindings(const Segment* current, int index, int endIndex, int& spanWinding) {
int lesser = SkMin32(index, endIndex);
spanWinding = current->spanSign(index, endIndex);
int winding = current->windSum(lesser);
@@ -4845,9 +4957,6 @@ static int updateWindings(const Segment* current, int index, int endIndex,
if (inner) {
winding -= spanWinding;
}
- if (oppWinding) {
- *oppWinding = current->oppSum(lesser);
- }
return winding;
}
@@ -4961,7 +5070,7 @@ static bool bridgeWinding(SkTDArray<Contour*>& contourList, PathWrapper& simple)
if (!current) {
break;
}
- winding = updateWindings(current, index, endIndex, spanWinding, NULL);
+ winding = updateWindings(current, index, endIndex, spanWinding);
} while (true);
} while (true);
return closable;
@@ -5234,7 +5343,7 @@ void simplifyx(const SkPath& path, SkPath& result) {
} while (addIntersectTs(current, next) && nextPtr != listEnd);
} while (currentPtr != listEnd);
// eat through coincident edges
- coincidenceCheck(contourList);
+ coincidenceCheck(contourList, false);
fixOtherTIndex(contourList);
sortSegments(contourList);
#if DEBUG_ACTIVE_SPANS
diff --git a/experimental/Intersection/SimplifyNew_Test.cpp b/experimental/Intersection/SimplifyNew_Test.cpp
index 6a805415c6..f190ec13e6 100644
--- a/experimental/Intersection/SimplifyNew_Test.cpp
+++ b/experimental/Intersection/SimplifyNew_Test.cpp
@@ -2552,62 +2552,58 @@ static void testQuadratic21() {
}
static void testIntersect1() {
- SkPath one, two, result;
- one.addRect(0, 0, 6, 6, (SkPath::Direction) 0);
- two.addRect(3, 3, 9, 9, (SkPath::Direction) 0);
- operate(one, two, kIntersect_Op, result);
- SkASSERT(result.countPoints() == 5);
- SkASSERT(result.countVerbs() == 6); // move, 4 lines, close
- SkRect bounds = result.getBounds();
- SkASSERT(bounds.fLeft == 3);
- SkASSERT(bounds.fTop == 3);
- SkASSERT(bounds.fRight == 6);
- SkASSERT(bounds.fBottom == 6);
+ SkPath one, two;
+ one.addRect(0, 0, 6, 6, SkPath::kCW_Direction);
+ two.addRect(3, 3, 9, 9, SkPath::kCW_Direction);
testShapeOp(one, two, kIntersect_Op);
}
static void testUnion1() {
- SkPath one, two, result;
- one.addRect(0, 0, 6, 6, (SkPath::Direction) 0);
- two.addRect(3, 3, 9, 9, (SkPath::Direction) 0);
- operate(one, two, kUnion_Op, result);
- SkASSERT(result.countPoints() == 9);
- SkASSERT(result.countVerbs() == 10); // move, 8 lines, close
- SkRect bounds = result.getBounds();
- SkASSERT(bounds.fLeft == 0);
- SkASSERT(bounds.fTop == 0);
- SkASSERT(bounds.fRight == 9);
- SkASSERT(bounds.fBottom == 9);
+ SkPath one, two;
+ one.addRect(0, 0, 6, 6, SkPath::kCW_Direction);
+ two.addRect(3, 3, 9, 9, SkPath::kCW_Direction);
testShapeOp(one, two, kUnion_Op);
}
static void testDiff1() {
- SkPath one, two, result;
- one.addRect(0, 0, 6, 6, (SkPath::Direction) 0);
- two.addRect(3, 3, 9, 9, (SkPath::Direction) 0);
- operate(one, two, kDifference_Op, result);
- SkASSERT(result.countPoints() == 7);
- SkASSERT(result.countVerbs() == 8); // move, 6 lines, close
- SkRect bounds = result.getBounds();
- SkASSERT(bounds.fLeft == 0);
- SkASSERT(bounds.fTop == 0);
- SkASSERT(bounds.fRight == 6);
- SkASSERT(bounds.fBottom == 6);
+ SkPath one, two;
+ one.addRect(0, 0, 6, 6, SkPath::kCW_Direction);
+ two.addRect(3, 3, 9, 9, SkPath::kCW_Direction);
testShapeOp(one, two, kDifference_Op);
}
static void testXor1() {
- SkPath one, two, result;
- one.addRect(0, 0, 6, 6, (SkPath::Direction) 0);
- two.addRect(3, 3, 9, 9, (SkPath::Direction) 0);
- operate(one, two, kXor_Op, result);
- SkASSERT(result.countPoints() == 14);
- SkASSERT(result.countVerbs() == 16); // move, 6 lines, close, move, 6 lines, close
- SkRect bounds = result.getBounds();
- SkASSERT(bounds.fLeft == 0);
- SkASSERT(bounds.fTop == 0);
- SkASSERT(bounds.fRight == 9);
- SkASSERT(bounds.fBottom == 9);
+ SkPath one, two;
+ one.addRect(0, 0, 6, 6, SkPath::kCW_Direction);
+ two.addRect(3, 3, 9, 9, SkPath::kCW_Direction);
+ testShapeOp(one, two, kXor_Op);
+}
+
+static void testIntersect2() {
+ SkPath one, two;
+ one.addRect(0, 0, 6, 6, SkPath::kCW_Direction);
+ two.addRect(0, 3, 9, 9, SkPath::kCW_Direction);
+ testShapeOp(one, two, kIntersect_Op);
+}
+
+static void testUnion2() {
+ SkPath one, two;
+ one.addRect(0, 0, 6, 6, SkPath::kCW_Direction);
+ two.addRect(0, 3, 9, 9, SkPath::kCW_Direction);
+ testShapeOp(one, two, kUnion_Op);
+}
+
+static void testDiff2() {
+ SkPath one, two;
+ one.addRect(0, 0, 6, 6, SkPath::kCW_Direction);
+ two.addRect(0, 3, 9, 9, SkPath::kCW_Direction);
+ testShapeOp(one, two, kDifference_Op);
+}
+
+static void testXor2() {
+ SkPath one, two;
+ one.addRect(0, 0, 6, 6, SkPath::kCW_Direction);
+ two.addRect(0, 3, 9, 9, SkPath::kCW_Direction);
testShapeOp(one, two, kXor_Op);
}
@@ -3215,14 +3211,20 @@ static struct {
void (*fun)();
const char* str;
} subTests[] = {
- TEST(testXor1),
TEST(testDiff1),
TEST(testIntersect1),
TEST(testUnion1),
+ TEST(testXor1),
+ TEST(testDiff2),
+ TEST(testIntersect2),
+ TEST(testUnion2),
+ TEST(testXor2),
};
static const size_t subTestCount = sizeof(subTests) / sizeof(subTests[0]);
+static void (*firstBinaryTest)() = testUnion2;
+
static bool skipAll = false;
static bool runBinaryTestsFirst = true;
static bool runReverse = false;
@@ -3236,6 +3238,14 @@ void SimplifyNew_Test() {
gDebugMaxWindValue = 4;
size_t index;
#endif
+ if (firstBinaryTest) {
+ index = subTestCount - 1;
+ while (index > 0 && subTests[index].fun != firstBinaryTest) {
+ --index;
+ }
+ SkDebugf(" %s [%s]\n", __FUNCTION__, subTests[index].str);
+ (*subTests[index].fun)();
+ }
if (runBinaryTestsFirst) {
index = subTestCount - 1;
do {