shape ops work in progress
overhaul coincident handling
git-svn-id: http://skia.googlecode.com/svn/trunk@6695 2bbb7eff-a529-9590-31e7-b0007b416f81
diff --git a/experimental/Intersection/EdgeWalker_Test.h b/experimental/Intersection/EdgeWalker_Test.h
index d5c38cf..205051e 100644
--- a/experimental/Intersection/EdgeWalker_Test.h
+++ b/experimental/Intersection/EdgeWalker_Test.h
@@ -13,6 +13,8 @@
//extern int comparePaths(const SkPath& one, const SkPath& two);
extern int comparePaths(const SkPath& one, const SkPath& two, SkBitmap& bitmap);
+extern int comparePaths(const SkPath& one, const SkPath& two, SkBitmap& bitmap,
+ const SkPath& a, const SkPath& b, const ShapeOp shapeOp);
extern void comparePathsTiny(const SkPath& one, const SkPath& two);
extern bool drawAsciiPaths(const SkPath& one, const SkPath& two,
bool drawPaths);
diff --git a/experimental/Intersection/EdgeWalker_TestUtility.cpp b/experimental/Intersection/EdgeWalker_TestUtility.cpp
index e3ea52e..5489a8b 100644
--- a/experimental/Intersection/EdgeWalker_TestUtility.cpp
+++ b/experimental/Intersection/EdgeWalker_TestUtility.cpp
@@ -29,25 +29,133 @@
"\n"
"var testDivs = [\n";
+static const char* opStrs[] = {
+ "kDifference_Op",
+ "kIntersect_Op",
+ "kUnion_Op",
+ "kXor_Op",
+};
+
+static const char* opSuffixes[] = {
+ "d",
+ "i",
+ "u",
+ "x",
+};
+
static const char preferredFilename[] = "/flash/debug/XX.txt";
static const char backupFilename[] = "../../experimental/Intersection/debugXX.txt";
static bool gShowPath = false;
static bool gComparePaths = true;
-//static bool gDrawLastAsciiPaths = true;
-//static bool gDrawAllAsciiPaths = false;
static bool gShowOutputProgress = false;
-static bool gShowAsciiPaths = true;
-static bool gComparePathsAssert = false;
+static bool gComparePathsAssert = true;
static bool gPathStrAssert = true;
static bool gUsePhysicalFiles = false;
-void showPath(const SkPath& path, const char* str) {
- SkDebugf("%s\n", !str ? "original:" : str);
- SkPath::Iter iter(path, true);
+static bool isRectContour(SkPath::Iter& iter, SkRect& rect, SkPath::Direction& direction) {
+ int corners = 0;
+ SkPoint first, last;
+ first.set(0, 0);
+ last.set(0, 0);
+ int firstDirection = 0;
+ int lastDirection = 0;
+ int nextDirection = 0;
+ bool closedOrMoved = false;
+ bool autoClose = false;
+ rect.setEmpty();
+ uint8_t verb;
+ SkPoint data[4];
+ SkTDArray<SkPoint> sides;
+ bool empty = true;
+ while ((verb = iter.next(data)) != SkPath::kDone_Verb && !autoClose) {
+ empty = false;
+ SkPoint* pts = &data[1];
+ switch (verb) {
+ case SkPath::kClose_Verb:
+ pts = &last;
+ autoClose = true;
+ case SkPath::kLine_Verb: {
+ SkScalar left = last.fX;
+ SkScalar top = last.fY;
+ SkScalar right = pts->fX;
+ SkScalar bottom = pts->fY;
+ *sides.append() = *pts;
+ ++pts;
+ if (left != right && top != bottom) {
+ return false; // diagonal
+ }
+ if (left == right && top == bottom) {
+ break; // single point on side OK
+ }
+ nextDirection = (left != right) << 0 |
+ (left < right || top < bottom) << 1;
+ if (0 == corners) {
+ firstDirection = nextDirection;
+ first = last;
+ last = pts[-1];
+ corners = 1;
+ closedOrMoved = false;
+ break;
+ }
+ if (closedOrMoved) {
+ return false; // closed followed by a line
+ }
+ if (autoClose && nextDirection == firstDirection) {
+ break; // colinear with first
+ }
+ closedOrMoved = autoClose;
+ if (lastDirection != nextDirection) {
+ if (++corners > 4) {
+ return false; // too many direction changes
+ }
+ }
+ last = pts[-1];
+ if (lastDirection == nextDirection) {
+ break; // colinear segment
+ }
+ // Possible values for corners are 2, 3, and 4.
+ // When corners == 3, nextDirection opposes firstDirection.
+ // Otherwise, nextDirection at corner 2 opposes corner 4.
+ int turn = firstDirection ^ (corners - 1);
+ int directionCycle = 3 == corners ? 0 : nextDirection ^ turn;
+ if ((directionCycle ^ turn) != nextDirection) {
+ return false; // direction didn't follow cycle
+ }
+ break;
+ }
+ case SkPath::kQuad_Verb:
+ case SkPath::kCubic_Verb:
+ return false; // quadratic, cubic not allowed
+ case SkPath::kMove_Verb:
+ last = *pts++;
+ *sides.append() = last;
+ closedOrMoved = true;
+ break;
+ }
+ lastDirection = nextDirection;
+ }
+ // Success if 4 corners and first point equals last
+ bool result = 4 == corners && (first == last || autoClose);
+ if (result) {
+ direction = firstDirection == (lastDirection + 1 & 3) ? SkPath::kCCW_Direction
+ : SkPath::kCW_Direction;
+ rect.set(&sides[0], sides.count());
+ } else {
+ rect.setEmpty();
+ }
+ return !empty;
+}
+
+static void showPathContour(SkPath::Iter& iter, bool skip) {
uint8_t verb;
SkPoint pts[4];
while ((verb = iter.next(pts)) != SkPath::kDone_Verb) {
+ if (skip) {
+ if (verb == SkPath::kClose_Verb) {
+ return;
+ }
+ }
switch (verb) {
case SkPath::kMove_Verb:
SkDebugf("path.moveTo(%1.9g, %1.9g);\n", pts[0].fX, pts[0].fY);
@@ -66,7 +174,7 @@
break;
case SkPath::kClose_Verb:
SkDebugf("path.close();\n");
- continue;
+ return;
default:
SkDEBUGFAIL("bad verb");
return;
@@ -74,8 +182,32 @@
}
}
-static int pathsDrawTheSame(const SkPath& one, const SkPath& two,
- SkBitmap& bits, int& error2x2) {
+void showPath(const SkPath& path, const char* str) {
+ SkDebugf("%s\n", !str ? "original:" : str);
+ SkPath::Iter iter(path, true);
+ SkTDArray<SkRect> rects;
+ SkTDArray<SkPath::Direction> directions;
+ SkRect rect;
+ SkPath::Direction direction;
+ while (isRectContour(iter, rect, direction)) {
+ *rects.append() = rect;
+ *directions.append() = direction;
+ }
+ iter.setPath(path, true);
+ for (int contour = 0; contour < rects.count(); ++contour) {
+ const SkRect& rect = rects[contour];
+ bool useRect = !rect.isEmpty();
+ showPathContour(iter, useRect);
+ if (useRect) {
+ SkDebugf("path.addRect(%1.9g, %1.9g, %1.9g, %1.9g, %s);\n", rect.fLeft, rect.fTop,
+ rect.fRight, rect.fBottom, directions[contour] == SkPath::kCCW_Direction
+ ? "SkPath::kCCW_Direction" : "SkPath::kCW_Direction");
+ }
+ }
+}
+
+static int pathsDrawTheSame(const SkPath& one, const SkPath& two,
+ SkBitmap& bits, SkPath& scaledOne, SkPath& scaledTwo, int& error2x2) {
const int bitWidth = 64;
const int bitHeight = 64;
if (bits.width() == 0) {
@@ -98,7 +230,6 @@
SkMatrix scale;
scale.reset();
scale.preScale(hScale, vScale);
- SkPath scaledOne, scaledTwo;
one.transform(scale, &scaledOne);
two.transform(scale, &scaledTwo);
const SkRect& bounds1 = scaledOne.getBounds();
@@ -134,9 +265,6 @@
if (errors2 >= 6 || errors > 160) {
SkDebugf("%s errors2=%d errors=%d\n", __FUNCTION__, errors2, errors);
}
- if (errors2 >= 7) {
- drawAsciiPaths(scaledOne, scaledTwo, true);
- }
error2x2 = errors2;
return errors;
}
@@ -145,10 +273,6 @@
if (!drawPaths) {
return true;
}
- if (gShowAsciiPaths) {
- showPath(one, "one:");
- showPath(two, "two:");
- }
const SkRect& bounds1 = one.getBounds();
const SkRect& bounds2 = two.getBounds();
SkRect larger = bounds1;
@@ -193,17 +317,58 @@
return true;
}
+static void showSimplifiedPath(const SkPath& one, const SkPath& two,
+ const SkPath& scaledOne, const SkPath& scaledTwo) {
+ showPath(one, "original:");
+ showPath(two, "simplified:");
+ drawAsciiPaths(scaledOne, scaledTwo, true);
+}
+
int comparePaths(const SkPath& one, const SkPath& two, SkBitmap& bitmap) {
int errors2x2;
- int errors = pathsDrawTheSame(one, two, bitmap, errors2x2);
+ SkPath scaledOne, scaledTwo;
+ int errors = pathsDrawTheSame(one, two, bitmap, scaledOne, scaledTwo, errors2x2);
if (errors2x2 == 0) {
return 0;
}
const int MAX_ERRORS = 8;
+ if (errors2x2 == MAX_ERRORS || errors2x2 == MAX_ERRORS - 1) {
+ showSimplifiedPath(one, two, scaledOne, scaledTwo);
+ }
if (errors2x2 > MAX_ERRORS && gComparePathsAssert) {
SkDebugf("%s errors=%d\n", __FUNCTION__, errors);
- showPath(one);
- showPath(two, "simplified:");
+ showSimplifiedPath(one, two, scaledOne, scaledTwo);
+ SkASSERT(0);
+ }
+ return errors2x2 > MAX_ERRORS ? errors2x2 : 0;
+}
+
+static void showShapeOpPath(const SkPath& one, const SkPath& two, const SkPath& a, const SkPath& b,
+ const SkPath& scaledOne, const SkPath& scaledTwo, const ShapeOp shapeOp) {
+ SkASSERT((unsigned) shapeOp < sizeof(opStrs) / sizeof(opStrs[0]));
+ showPath(a, "minuend:");
+ SkDebugf("op: %s\n", opStrs[shapeOp]);
+ showPath(b, "subtrahend:");
+ showPath(one, "region:");
+ showPath(two, "op result:");
+ drawAsciiPaths(scaledOne, scaledTwo, true);
+}
+
+int comparePaths(const SkPath& one, const SkPath& two, SkBitmap& bitmap,
+ const SkPath& a, const SkPath& b, const ShapeOp shapeOp) {
+ int errors2x2;
+ SkPath scaledOne, scaledTwo;
+ int errors = pathsDrawTheSame(one, two, bitmap, scaledOne, scaledTwo, errors2x2);
+ if (errors2x2 == 0) {
+ return 0;
+ }
+ const int MAX_ERRORS = 8;
+ if (errors2x2 == MAX_ERRORS || errors2x2 == MAX_ERRORS - 1) {
+ showShapeOpPath(one, two, a, b, scaledOne, scaledTwo, shapeOp);
+ }
+ if (errors2x2 > MAX_ERRORS && gComparePathsAssert) {
+ SkDebugf("%s errors=%d\n", __FUNCTION__, errors);
+ showShapeOpPath(one, two, a, b, scaledOne, scaledTwo, shapeOp);
SkASSERT(0);
}
return errors2x2 > MAX_ERRORS ? errors2x2 : 0;
@@ -304,7 +469,7 @@
rgnOut.op(rgnA, rgnB, (SkRegion::Op) shapeOp);
rgnOut.getBoundaryPath(&pathOut);
SkBitmap bitmap;
- int result = comparePaths(pathOut, out, bitmap);
+ int result = comparePaths(pathOut, out, bitmap, a, b, shapeOp);
if (result && gPathStrAssert) {
SkASSERT(0);
}
@@ -467,20 +632,6 @@
outputToStream(state, pathStr, pathPrefix, nameSuffix, testFunction, outRam);
}
-static const char* opStrs[] = {
- "kDifference_Op",
- "kIntersect_Op",
- "kUnion_Op",
- "kXor_Op",
-};
-
-static const char* opSuffixes[] = {
- "d",
- "i",
- "u",
- "x",
-};
-
void outputProgress(const State4& state, const char* pathStr, ShapeOp op) {
SkString testFunc("testShapeOp(path, pathB, ");
testFunc += opStrs[op];
diff --git a/experimental/Intersection/ShapeOpRect4x4_Test.cpp b/experimental/Intersection/ShapeOpRect4x4_Test.cpp
index d228a33..69b567f 100644
--- a/experimental/Intersection/ShapeOpRect4x4_Test.cpp
+++ b/experimental/Intersection/ShapeOpRect4x4_Test.cpp
@@ -27,12 +27,14 @@
for (int c = 0 ; c < 6; ++c) {
for (int d = c + 1 ; d < 7; ++d) {
for (int op = 0 ; op < kShapeOp_Count; ++op) {
- for (int e = 0 ; e <= SkPath::kEvenOdd_FillType; ++e) {
- for (int f = 0 ; f <= SkPath::kEvenOdd_FillType; ++f) {
+ for (int e = SkPath::kWinding_FillType ; e <= SkPath::kEvenOdd_FillType; ++e) {
+ for (int f = SkPath::kWinding_FillType ; f <= SkPath::kEvenOdd_FillType; ++f) {
SkPath pathA, pathB;
char* str = pathStr;
pathA.setFillType((SkPath::FillType) e);
- str += sprintf(str, " path.setFillType((SkPath::FillType) %d);\n", e);
+ str += sprintf(str, " path.setFillType(SkPath::k%s_FillType);\n",
+ e == SkPath::kWinding_FillType ? "Winding" : e == SkPath::kEvenOdd_FillType
+ ? "EvenOdd" : "?UNDEFINED");
pathA.addRect(state.a, state.a, state.b, state.b, SkPath::kCW_Direction);
str += sprintf(str, " path.addRect(%d, %d, %d, %d,"
" SkPath::kCW_Direction);\n", state.a, state.a, state.b, state.b);
@@ -41,7 +43,9 @@
" SkPath::kCW_Direction);\n", state.c, state.c, state.d, state.d);
pathA.close();
pathB.setFillType((SkPath::FillType) f);
- str += sprintf(str, " pathB.setFillType((SkPath::FillType) %d);\n", f);
+ str += sprintf(str, " pathB.setFillType(SkPath::k%s_FillType);\n",
+ f == SkPath::kWinding_FillType ? "Winding" : f == SkPath::kEvenOdd_FillType
+ ? "EvenOdd" : "?UNDEFINED");
pathB.addRect(a, a, b, b, SkPath::kCW_Direction);
str += sprintf(str, " pathB.addRect(%d, %d, %d, %d,"
" SkPath::kCW_Direction);\n", a, a, b, b);
diff --git a/experimental/Intersection/ShapeOps.cpp b/experimental/Intersection/ShapeOps.cpp
index cecfbff..1231ea3 100644
--- a/experimental/Intersection/ShapeOps.cpp
+++ b/experimental/Intersection/ShapeOps.cpp
@@ -232,7 +232,8 @@
builder.finish();
const int xorOpMask = builder.xorMask();
SkTDArray<Op::Contour*> contourList;
- makeContourList(contours, contourList);
+ makeContourList(contours, contourList, xorMask == kEvenOdd_Mask,
+ xorOpMask == kEvenOdd_Mask);
Op::Contour** currentPtr = contourList.begin();
if (!currentPtr) {
return;
@@ -257,8 +258,7 @@
#if DEBUG_SHOW_WINDING
Op::Contour::debugShowWindingValues(contourList);
#endif
- coincidenceCheck(contourList, (xorMask == kEvenOdd_Mask)
- ^ (xorOpMask == kEvenOdd_Mask), total);
+ coincidenceCheck(contourList, total);
#if DEBUG_SHOW_WINDING
Op::Contour::debugShowWindingValues(contourList);
#endif
diff --git a/experimental/Intersection/Simplify.cpp b/experimental/Intersection/Simplify.cpp
index c52ff5f..81fe79b 100644
--- a/experimental/Intersection/Simplify.cpp
+++ b/experimental/Intersection/Simplify.cpp
@@ -29,13 +29,14 @@
#define TRY_ROTATE 1
#define DEBUG_UNUSED 0 // set to expose unused functions
-#define FORCE_RELEASE 1 // set force release to 1 for multiple thread -- no debugging
+#define FORCE_RELEASE 0 // set force release to 1 for multiple thread -- no debugging
#if FORCE_RELEASE || defined SK_RELEASE
const bool gRunTestsInOneThread = false;
#define DEBUG_ACTIVE_SPANS 0
+#define DEBUG_ACTIVE_SPANS_SHORT_FORM 0
#define DEBUG_ADD_INTERSECTING_TS 0
#define DEBUG_ADD_T_PAIR 0
#define DEBUG_ANGLE 0
@@ -53,6 +54,7 @@
const bool gRunTestsInOneThread = true;
#define DEBUG_ACTIVE_SPANS 1
+#define DEBUG_ACTIVE_SPANS_SHORT_FORM 1
#define DEBUG_ADD_INTERSECTING_TS 1
#define DEBUG_ADD_T_PAIR 1
#define DEBUG_ANGLE 1
@@ -792,7 +794,7 @@
void add(const Bounds& toAdd) {
add(toAdd.fLeft, toAdd.fTop, toAdd.fRight, toAdd.fBottom);
}
-
+
bool isEmpty() {
return fLeft > fRight || fTop > fBottom
|| (fLeft == fRight && fTop == fBottom)
@@ -999,7 +1001,7 @@
return fBounds.fTop < rh.fBounds.fTop;
}
- bool activeAngle(int index, int& done, SkTDArray<Angle>& angles) const {
+ bool activeAngle(int index, int& done, SkTDArray<Angle>& angles) {
if (activeAngleInner(index, done, angles)) {
return true;
}
@@ -1018,37 +1020,43 @@
return false;
}
- bool activeAngleOther(int index, int& done, SkTDArray<Angle>& angles) const {
+ bool activeAngleOther(int index, int& done, SkTDArray<Angle>& angles) {
Span* span = &fTs[index];
Segment* other = span->fOther;
int oIndex = span->fOtherIndex;
return other->activeAngleInner(oIndex, done, angles);
}
- bool activeAngleInner(int index, int& done, SkTDArray<Angle>& angles) const {
+ bool activeAngleInner(int index, int& done, SkTDArray<Angle>& angles) {
int next = nextExactSpan(index, 1);
if (next > 0) {
- const Span& upSpan = fTs[index];
- if (upSpan.fWindValue) {
+ Span& upSpan = fTs[index];
+ if (upSpan.fWindValue || upSpan.fOppValue) {
addAngle(angles, index, next);
if (upSpan.fDone || upSpan.fUnsortableEnd) {
done++;
} else if (upSpan.fWindSum != SK_MinS32) {
return true;
}
+ } else if (!upSpan.fDone) {
+ upSpan.fDone = true;
+ fDoneSpans++;
}
}
int prev = nextExactSpan(index, -1);
// edge leading into junction
if (prev >= 0) {
- const Span& downSpan = fTs[prev];
- if (downSpan.fWindValue) {
+ Span& downSpan = fTs[prev];
+ if (downSpan.fWindValue || downSpan.fOppValue) {
addAngle(angles, index, prev);
if (downSpan.fDone) {
done++;
} else if (downSpan.fWindSum != SK_MinS32) {
return true;
}
+ } else if (!downSpan.fDone) {
+ downSpan.fDone = true;
+ fDoneSpans++;
}
}
return false;
@@ -1112,8 +1120,21 @@
}
int oppCoin = oppSign(index, endIndex) & oppMask;
if (oppCoin) {
- return op == kIntersect_Op || op == kUnion_Op
- || (oppSumWinding & oppMask && oppMaxWinding & oppMask);
+ bool oppCrossZero = !(oppSumWinding & oppMask) || !(oppMaxWinding & oppMask);
+ bool outside = !(oppSumWinding & oppMask) ^ !(sumWinding & mask);
+ switch (op) {
+ case kIntersect_Op:
+ return !oppCrossZero | !outside;
+ case kUnion_Op:
+ return oppCrossZero & !outside;
+ case kDifference_Op:
+ return oppCrossZero ? outside : operand();
+ case kXor_Op:
+ return !oppCrossZero;
+ default:
+ SkASSERT(0);
+ }
+
}
bool oppNonZero = oppMaxWinding & oppMask;
return isActiveOp(operand(), oppNonZero, op);
@@ -1222,7 +1243,7 @@
do {
++oIndex;
} while (!approximately_negative(oStart - other.fTs[oIndex].fT));
- if (tIndex > 0 || oIndex > 0) {
+ if (tIndex > 0 || oIndex > 0 || fOperand != other.fOperand) {
addTPair(tStart, other, oStart, false);
}
tStart = fTs[tIndex].fT;
@@ -1237,15 +1258,15 @@
nextT = other.fTs[++oIndex].fT;
} while (approximately_negative(nextT - oStart));
oStart = nextT;
- if (tStart == 1 && oStart == 1) {
+ if (tStart == 1 && oStart == 1 && fOperand == other.fOperand) {
break;
}
addTPair(tStart, other, oStart, false);
} while (tStart < 1 && oStart < 1 && !approximately_negative(oEnd - oStart));
}
- void addCubic(const SkPoint pts[4], bool operand) {
- init(pts, SkPath::kCubic_Verb, operand);
+ void addCubic(const SkPoint pts[4], bool operand, bool evenOdd) {
+ init(pts, SkPath::kCubic_Verb, operand, evenOdd);
fBounds.setCubicBounds(pts);
}
@@ -1298,8 +1319,8 @@
// return ePtr[fVerb];
}
- void addLine(const SkPoint pts[2], bool operand) {
- init(pts, SkPath::kLine_Verb, operand);
+ void addLine(const SkPoint pts[2], bool operand, bool evenOdd) {
+ init(pts, SkPath::kLine_Verb, operand, evenOdd);
fBounds.set(pts, 2);
}
@@ -1327,8 +1348,8 @@
span.fOtherIndex = otherIndex;
}
- void addQuad(const SkPoint pts[3], bool operand) {
- init(pts, SkPath::kQuad_Verb, operand);
+ void addQuad(const SkPoint pts[3], bool operand, bool evenOdd) {
+ init(pts, SkPath::kQuad_Verb, operand, evenOdd);
fBounds.setQuadBounds(pts);
}
@@ -1505,44 +1526,19 @@
}
}
- int bumpCoincidentThis(const Span* oTest, const bool transfer, const bool decrementThis,
- const bool thisXor, const int oXorMask, const bool opp, int index,
- SkTDArray<double>& outsideTs, SkTDArray<double>& xOutsideTs)
- {
+ int bumpCoincidentThis(const Span* oTest, bool opp, int index,
+ SkTDArray<double>& outsideTs) {
+ int oWindValue = oTest->fWindValue;
+ int oOppValue = oTest->fOppValue;
+ if (opp) {
+ SkTSwap<int>(oWindValue, oOppValue);
+ }
Span* const test = &fTs[index];
Span* end = test;
- const int startIndex = index;
const double oStartT = oTest->fT;
do {
- if (transfer) {
- if (opp) {
- if (decrementThis) {
- zeroSpan(end, oStartT);
- TrackOutside(outsideTs, end->fT, oStartT);
- } else {
- end->fWindValue += oTest->fOppValue;
- end->fOppValue = (end->fOppValue + oTest->fWindValue) & oXorMask;
- if (thisXor) {
- SkASSERT(end->fWindValue);
- if (!(end->fWindValue & 1)) {
- zeroSpan(end, oStartT);
- TrackOutside(outsideTs, end->fT, oStartT);
- }
- }
- }
- } else if (!decrementThis & !thisXor) {
- #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(decrementThis);
- if (startIndex > 0 && fTs[startIndex - 1].fWindValue) {
- TrackOutside(xOutsideTs, end->fT, oStartT);
- }
+ if (bumpSpan(end, oWindValue, oOppValue)) {
+ TrackOutside(outsideTs, end->fT, oStartT);
}
end = &fTs[++index];
} while (approximately_negative(end->fT - test->fT));
@@ -1553,48 +1549,16 @@
// 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 int xorMask, const bool opp, const double tRatio,
- const double oEndT, int& oIndex, SkTDArray<double>& oOutsideTs)
- {
+ int bumpCoincidentOther(const Span* test, 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 (opp) {
- if (decrementThis) {
- oEnd->fWindValue += test->fOppValue;
- oEnd->fOppValue = (oEnd->fOppValue + test->fWindValue) & xorMask;
- if (otherXor) {
- SkASSERT(oEnd->fWindValue);
- if (!(oEnd->fWindValue & 1)) {
- zeroSpan(oEnd, startT);
- TrackOutside(oOutsideTs, oEnd->fT, startT);
- }
- }
- } else {
- zeroSpan(oEnd, startT);
- TrackOutside(oOutsideTs, oEnd->fT, startT);
- }
- } else if (decrementThis & !otherXor) {
- #ifdef SK_DEBUG
- SkASSERT(abs(oEnd->fWindValue) < gDebugMaxWindValue);
- #endif
- ++(oEnd->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?
- }
- }
+ && approximately_negative(oEnd->fT - oStartT)) {
+ zeroSpan(oEnd);
+ TrackOutside(oOutsideTs, oEnd->fT, startT);
oEnd = &fTs[++oIndex];
}
return oIndex;
@@ -1609,14 +1573,10 @@
// set spans from start to end to increment the greater by one and decrement
// the lesser
- void addTCoincident(bool thisXor, bool otherXor, double startT, double endT,
- Segment& other, double oStartT, double oEndT) {
+ void addTCoincident(double startT, double endT, Segment& other, double oStartT, double oEndT) {
SkASSERT(!approximately_negative(endT - startT));
SkASSERT(!approximately_negative(oEndT - oStartT));
bool opp = fOperand ^ other.fOperand;
- if (!opp) {
- otherXor = thisXor;
- }
int index = 0;
while (!approximately_negative(startT - fTs[index].fT)) {
++index;
@@ -1625,41 +1585,21 @@
while (!approximately_negative(oStartT - other.fTs[oIndex].fT)) {
++oIndex;
}
- double tRatio = (oEndT - oStartT) / (endT - startT);
Span* test = &fTs[index];
Span* oTest = &other.fTs[oIndex];
SkTDArray<double> outsideTs;
- SkTDArray<double> xOutsideTs;
SkTDArray<double> oOutsideTs;
- int xorMask = thisXor ? 1 : -1;
- int oXorMask = otherXor ? 1 : -1;
do {
- bool transfer = test->fWindValue && oTest->fWindValue;
- bool decrementThis = test->fWindValue < oTest->fWindValue ||
- (test->fWindValue == oTest->fWindValue && thisXor);
- if (decrementThis) {
- oIndex = other.bumpCoincidentOther(test, transfer, decrementThis, otherXor, xorMask,
- opp, tRatio, oEndT, oIndex, oOutsideTs);
- index = bumpCoincidentThis(oTest, transfer, decrementThis, thisXor, oXorMask, opp,
- index, outsideTs, xOutsideTs);
- } else {
- index = bumpCoincidentThis(oTest, transfer, decrementThis, thisXor, oXorMask, opp,
- index, outsideTs, xOutsideTs);
- oIndex = other.bumpCoincidentOther(test, transfer, decrementThis, otherXor, xorMask,
- opp, tRatio, oEndT, oIndex, oOutsideTs);
- }
+ // if either span has an opposite value and the operands don't match, resolve first
+ index = bumpCoincidentThis(oTest, opp, index, outsideTs);
+ oIndex = other.bumpCoincidentOther(test, oEndT, oIndex, oOutsideTs);
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));
- if (!done()) {
- if (outsideTs.count()) {
- addCoinOutsides(outsideTs, other, oEndT);
- }
- if (xOutsideTs.count()) {
- addCoinOutsides(xOutsideTs, other, oEndT);
- }
+ if (!done() && outsideTs.count()) {
+ addCoinOutsides(outsideTs, other, oEndT);
}
if (!other.done() && oOutsideTs.count()) {
other.addCoinOutsides(oOutsideTs, *this, endT);
@@ -1698,13 +1638,15 @@
void addTwoAngles(int start, int end, SkTDArray<Angle>& angles) const {
// add edge leading into junction
- if (fTs[SkMin32(end, start)].fWindValue > 0) {
+ int min = SkMin32(end, start);
+ if (fTs[min].fWindValue > 0 || fTs[min].fOppValue > 0) {
addAngle(angles, end, start);
}
// add edge leading away from junction
int step = SkSign32(end - start);
int tIndex = nextExactSpan(end, step);
- if (tIndex >= 0 && fTs[SkMin32(end, tIndex)].fWindValue > 0) {
+ min = SkMin32(end, tIndex);
+ if (tIndex >= 0 && (fTs[min].fWindValue > 0 || fTs[min].fOppValue > 0)) {
addAngle(angles, end, tIndex);
}
}
@@ -1828,7 +1770,7 @@
if (oppoSign && useInnerWinding(maxWinding, winding)) {
maxWinding = winding;
}
- segment->markAndChaseWinding(angle, oMaxWinding, maxWinding);
+ (void) segment->markAndChaseWinding(angle, oMaxWinding, maxWinding);
} else {
if (useInnerWinding(maxWinding, winding)) {
maxWinding = winding;
@@ -1836,7 +1778,7 @@
if (oppoSign && useInnerWinding(oMaxWinding, oWinding)) {
oMaxWinding = oWinding;
}
- segment->markAndChaseWinding(angle, maxWinding, binary ? oMaxWinding : 0);
+ (void) segment->markAndChaseWinding(angle, maxWinding, binary ? oMaxWinding : 0);
}
}
} while (++nextIndex != lastIndex);
@@ -1931,13 +1873,31 @@
return false;
}
- bool decrementSpan(Span* span) {
+ void decrementSpan(Span* span) {
SkASSERT(span->fWindValue > 0);
if (--(span->fWindValue) == 0) {
- if (!span->fDone) {
+ if (!span->fOppValue && !span->fDone) {
span->fDone = true;
++fDoneSpans;
}
+ }
+ }
+
+ bool bumpSpan(Span* span, int windDelta, int oppDelta) {
+ SkASSERT(!span->fDone);
+ span->fWindValue += windDelta;
+ SkASSERT(span->fWindValue >= 0);
+ span->fOppValue += oppDelta;
+ SkASSERT(span->fOppValue >= 0);
+ if (fXor) {
+ span->fWindValue &= 1;
+ }
+ if (fOppXor) {
+ span->fOppValue &= 1;
+ }
+ if (!span->fWindValue && !span->fOppValue) {
+ span->fDone = true;
+ ++fDoneSpans;
return true;
}
return false;
@@ -2380,7 +2340,7 @@
}
// FIXME: this is tricky code; needs its own unit test
- void findTooCloseToCall(bool thisXor, bool otherXor) {
+ void findTooCloseToCall() {
int count = fTs.count();
if (count < 3) { // require t=0, x, 1 at minimum
return;
@@ -2503,11 +2463,7 @@
if (flipped) {
mOther->addTCancel(moStartT, moEndT, *tOther, toEndT, toStartT);
} else {
- // 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(thisXor, otherXor,
- moStartT, moEndT, *tOther, toStartT, toEndT);
+ mOther->addTCoincident(moStartT, moEndT, *tOther, toStartT, toEndT);
}
}
}
@@ -2609,96 +2565,11 @@
}
}
}
-
- // OPTIMIZATION: uses tail recursion. Unwise?
- Span* innerChaseDone(int index, int step, int winding) {
- int end = nextExactSpan(index, step);
- SkASSERT(end >= 0);
- if (multipleSpans(end)) {
- return &fTs[end];
- }
- const Span& endSpan = fTs[end];
- Segment* other = endSpan.fOther;
- index = endSpan.fOtherIndex;
- int otherEnd = other->nextExactSpan(index, step);
- Span* last = other->innerChaseDone(index, step, winding);
- other->markDone(SkMin32(index, otherEnd), winding);
- return last;
- }
-
- Span* innerChaseDoneBinary(int index, int step, int winding, int oppWinding) {
- int end = nextExactSpan(index, step);
- SkASSERT(end >= 0);
- if (multipleSpans(end)) {
- return &fTs[end];
- }
- const Span& endSpan = fTs[end];
- Segment* other = endSpan.fOther;
- index = endSpan.fOtherIndex;
- int otherEnd = other->nextExactSpan(index, step);
- Span* last = other->innerChaseDoneBinary(index, step, winding, oppWinding);
- other->markDoneBinary(SkMin32(index, otherEnd), winding, oppWinding);
- return last;
- }
-
- Span* innerChaseDoneBinary(int index, int step) {
- int end = nextExactSpan(index, step);
- SkASSERT(end >= 0);
- if (multipleSpans(end)) {
- return &fTs[end];
- }
- const Span& endSpan = fTs[end];
- Segment* other = endSpan.fOther;
- index = endSpan.fOtherIndex;
- int otherEnd = other->nextExactSpan(index, step);
- Span* last = other->innerChaseDoneBinary(index, step);
- other->markDoneBinary(SkMin32(index, otherEnd));
- return last;
- }
-
- Span* innerChaseWinding(int index, int step, int winding) {
- int end = nextExactSpan(index, step);
- SkASSERT(end >= 0);
- if (multipleSpans(end)) {
- return &fTs[end];
- }
- const Span& endSpan = fTs[end];
- Segment* other = endSpan.fOther;
- index = endSpan.fOtherIndex;
- int otherEnd = other->nextExactSpan(index, step);
- int min = SkMin32(index, otherEnd);
- if (other->fTs[min].fWindSum != SK_MinS32) {
- SkASSERT(other->fTs[min].fWindSum == winding);
- return NULL;
- }
- Span* last = other->innerChaseWinding(index, step, winding);
- other->markWinding(min, winding);
- return last;
- }
-
- Span* innerChaseWinding(int index, int step, int winding, int oppWinding) {
- int end = nextExactSpan(index, step);
- SkASSERT(end >= 0);
- if (multipleSpans(end)) {
- return &fTs[end];
- }
- const Span& endSpan = fTs[end];
- Segment* other = endSpan.fOther;
- index = endSpan.fOtherIndex;
- int otherEnd = other->nextExactSpan(index, step);
- int min = SkMin32(index, otherEnd);
- if (other->fTs[min].fWindSum != SK_MinS32) {
- SkASSERT(other->fTs[min].fWindSum == winding);
- return NULL;
- }
- Span* last = other->innerChaseWinding(index, step, winding, oppWinding);
- other->markWinding(min, winding, oppWinding);
- return last;
- }
-
- void init(const SkPoint pts[], SkPath::Verb verb, bool operand) {
+
+ void init(const SkPoint pts[], SkPath::Verb verb, bool operand, bool evenOdd) {
fDoneSpans = 0;
fOperand = operand;
+ fXor = evenOdd;
fPts = pts;
fVerb = verb;
}
@@ -2712,7 +2583,7 @@
if (local * oppWinding >= 0) {
oppWinding += local;
}
- markAndChaseWinding(start, end, winding, oppWinding);
+ (void) markAndChaseWinding(start, end, winding, oppWinding);
}
bool intersected() const {
@@ -2790,8 +2661,13 @@
Span* markAndChaseDone(int index, int endIndex, int winding) {
int step = SkSign32(endIndex - index);
- Span* last = innerChaseDone(index, step, winding);
- markDone(SkMin32(index, endIndex), winding);
+ int min = SkMin32(index, endIndex);
+ markDone(min, winding);
+ Span* last;
+ Segment* other = this;
+ while ((other = other->nextChase(index, step, min, last))) {
+ other->markDone(min, winding);
+ }
return last;
}
@@ -2799,33 +2675,59 @@
int index = angle->start();
int endIndex = angle->end();
int step = SkSign32(endIndex - index);
- Span* last = innerChaseDoneBinary(index, step, winding, oppWinding);
- markDoneBinary(SkMin32(index, endIndex), winding, oppWinding);
+ int min = SkMin32(index, endIndex);
+ markDoneBinary(min, winding, oppWinding);
+ Span* last;
+ Segment* other = this;
+ while ((other = other->nextChase(index, step, min, last))) {
+ other->markDoneBinary(min, winding, oppWinding);
+ }
return last;
}
Span* markAndChaseDoneBinary(int index, int endIndex) {
int step = SkSign32(endIndex - index);
- Span* last = innerChaseDoneBinary(index, step);
- markDoneBinary(SkMin32(index, endIndex));
+ int min = SkMin32(index, endIndex);
+ markDoneBinary(min);
+ Span* last;
+ Segment* other = this;
+ while ((other = other->nextChase(index, step, min, last))) {
+ other->markDoneBinary(min);
+ }
return last;
}
- Span* markAndChaseWinding(const Angle* angle, int winding) {
+ Span* markAndChaseWinding(const Angle* angle, const int winding) {
int index = angle->start();
int endIndex = angle->end();
+ int step = SkSign32(endIndex - index);
int min = SkMin32(index, endIndex);
- int step = SkSign32(endIndex - index);
- Span* last = innerChaseWinding(index, step, winding);
markWinding(min, winding);
+ Span* last;
+ Segment* other = this;
+ while ((other = other->nextChase(index, step, min, last))) {
+ if (other->fTs[min].fWindSum != SK_MinS32) {
+ SkASSERT(other->fTs[min].fWindSum == winding);
+ return NULL;
+ }
+ other->markWinding(min, winding);
+ }
return last;
}
Span* markAndChaseWinding(int index, int endIndex, int winding, int oppWinding) {
int min = SkMin32(index, endIndex);
int step = SkSign32(endIndex - index);
- Span* last = innerChaseWinding(index, step, winding, oppWinding);
markWinding(min, winding, oppWinding);
+ Span* last;
+ Segment* other = this;
+ while ((other = other->nextChase(index, step, min, last))) {
+ if (other->fTs[min].fWindSum != SK_MinS32) {
+ SkASSERT(other->fTs[min].fWindSum == winding);
+ return NULL;
+ }
+ other->markWinding(min, winding, oppWinding);
+ }
return last;
}
@@ -3005,7 +2907,7 @@
void markWinding(int index, int winding, int oppWinding) {
// SkASSERT(!done());
- SkASSERT(winding);
+ SkASSERT(winding || oppWinding);
double referenceT = fTs[index].fT;
int lesser = index;
while (--lesser >= 0 && precisely_negative(referenceT - fTs[lesser].fT)) {
@@ -3042,7 +2944,7 @@
Span& newSpan = fTs[tIndex];
newSpan.fWindValue = nextDoorWind;
newSpan.fOppValue = nextOppWind;
- if (!nextDoorWind && !newSpan.fDone) {
+ if (!nextDoorWind && !nextOppWind && !newSpan.fDone) {
newSpan.fDone = true;
++fDoneSpans;
}
@@ -3058,6 +2960,21 @@
return end > 0 && end < fTs.count() - 1;
}
+ Segment* nextChase(int& index, const int step, int& min, Span*& last) const {
+ int end = nextExactSpan(index, step);
+ SkASSERT(end >= 0);
+ if (multipleSpans(end)) {
+ last = &fTs[end];
+ return NULL;
+ }
+ const Span& endSpan = fTs[end];
+ Segment* other = endSpan.fOther;
+ index = endSpan.fOtherIndex;
+ int otherEnd = other->nextExactSpan(index, step);
+ min = SkMin32(index, otherEnd);
+ return other;
+ }
+
// This has callers for two different situations: one establishes the end
// of the current span, and one establishes the beginning of the next span
// (thus the name). When this is looking for the end of the current span,
@@ -3134,11 +3051,15 @@
}
void reset() {
- init(NULL, (SkPath::Verb) -1, false);
+ init(NULL, (SkPath::Verb) -1, false, false);
fBounds.set(SK_ScalarMax, SK_ScalarMax, SK_ScalarMax, SK_ScalarMax);
fTs.reset();
}
+ void setOppXor(bool isOppXor) {
+ fOppXor = isOppXor;
+ }
+
void setUpWindings(int index, int endIndex, int& sumMiWinding, int& sumSuWinding,
int& maxWinding, int& sumWinding, int& oppMaxWinding, int& oppSumWinding) {
int deltaSum = spanSign(index, endIndex);
@@ -3227,7 +3148,7 @@
*outsideTs.append() = start;
}
}
-
+
void undoneSpan(int& start, int& end) {
size_t tCount = fTs.count();
size_t index;
@@ -3352,21 +3273,35 @@
return xyAtT(span).fY;
}
- void zeroSpan(Span* span, double otherT) {
- SkASSERT(span->fWindValue > 0);
+ void zeroCoincidentOpp(Span* oTest, int index) {
+ Span* const test = &fTs[index];
+ Span* end = test;
+ do {
+ end->fOppValue = 0;
+ end = &fTs[++index];
+ } while (approximately_negative(end->fT - test->fT));
+ }
+
+ void zeroCoincidentOther(Span* test, const double tRatio, const double oEndT, int oIndex) {
+ Span* const oTest = &fTs[oIndex];
+ Span* oEnd = oTest;
+ const double startT = test->fT;
+ const double oStartT = oTest->fT;
+ double otherTMatch = (test->fT - startT) * tRatio + oStartT;
+ while (!approximately_negative(oEndT - oEnd->fT)
+ && approximately_negative(oEnd->fT - otherTMatch)) {
+ oEnd->fOppValue = 0;
+ oEnd = &fTs[++oIndex];
+ }
+ }
+
+ void zeroSpan(Span* span) {
+ SkASSERT(span->fWindValue > 0 || span->fOppValue > 0);
span->fWindValue = 0;
- if (!span->fDone) {
- span->fDone = true;
- ++fDoneSpans;
- }
- int oppValue = span->fOppValue;
- if (!oppValue) {
- return;
- }
span->fOppValue = 0;
- Segment* other = span->fOther;
- Span& oSpan = other->fTs[span->fOtherIndex];
- SkASSERT(0);
+ SkASSERT(!span->fDone);
+ span->fDone = true;
+ ++fDoneSpans;
}
#if DEBUG_DUMP
@@ -3427,9 +3362,36 @@
#if DEBUG_CONCIDENT
void debugShowTs() const {
SkDebugf("%s id=%d", __FUNCTION__, fID);
- for (int i = 0; i < fTs.count(); ++i) {
- SkDebugf(" [o=%d t=%1.3g %1.9g,%1.9g w=%d]", fTs[i].fOther->fID,
- fTs[i].fT, xAtT(&fTs[i]), yAtT(&fTs[i]), fTs[i].fWindValue);
+ int lastWind = -1;
+ int lastOpp = -1;
+ double lastT = -1;
+ int i;
+ for (i = 0; i < fTs.count(); ++i) {
+ bool change = lastT != fTs[i].fT || lastWind != fTs[i].fWindValue
+ || lastOpp != fTs[i].fOppValue;
+ if (change && lastWind >= 0) {
+ SkDebugf(" t=%1.3g %1.9g,%1.9g w=%d o=%d]",
+ lastT, xyAtT(i - 1).fX, xyAtT(i - 1).fY, lastWind, lastOpp);
+ }
+ if (change) {
+ SkDebugf(" [o=%d", fTs[i].fOther->fID);
+ lastWind = fTs[i].fWindValue;
+ lastOpp = fTs[i].fOppValue;
+ lastT = fTs[i].fT;
+ } else {
+ SkDebugf(",%d", fTs[i].fOther->fID);
+ }
+ }
+ if (i <= 0) {
+ return;
+ }
+ SkDebugf(" t=%1.3g %1.9g,%1.9g w=%d o=%d]",
+ lastT, xyAtT(i - 1).fX, xyAtT(i - 1).fY, lastWind, lastOpp);
+ if (fOperand) {
+ SkDebugf(" operand");
+ }
+ if (done()) {
+ SkDebugf(" done");
}
SkDebugf("\n");
}
@@ -3440,10 +3402,21 @@
if (done()) {
return;
}
+#if DEBUG_ACTIVE_SPANS_SHORT_FORM
+ int lastId = -1;
+ double lastT = -1;
+#endif
for (int i = 0; i < fTs.count(); ++i) {
if (fTs[i].fDone) {
continue;
}
+#if DEBUG_ACTIVE_SPANS_SHORT_FORM
+ if (lastId == fID && lastT == fTs[i].fT) {
+ continue;
+ }
+ lastId = fID;
+ lastT = fTs[i].fT;
+#endif
SkDebugf("%s id=%d", __FUNCTION__, fID);
SkDebugf(" (%1.9g,%1.9g", fPts[0].fX, fPts[0].fY);
for (int vIndex = 1; vIndex <= fVerb; ++vIndex) {
@@ -3460,7 +3433,7 @@
} else {
SkDebugf("%d", fTs[i].fWindSum);
}
- SkDebugf(" windValue=%d\n", fTs[i].fWindValue);
+ SkDebugf(" windValue=%d oppValue=%d\n", fTs[i].fWindValue, fTs[i].fOppValue);
}
}
@@ -3687,11 +3660,15 @@
private:
const SkPoint* fPts;
- SkPath::Verb fVerb;
Bounds fBounds;
SkTDArray<Span> fTs; // two or more (always includes t=0 t=1)
+ // 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 fOperand;
+ bool fXor; // set if original contour had even-odd fill
+ bool fOppXor; // set if opposite operand had even-odd fill
#if DEBUG_DUMP
int fID;
#endif
@@ -3753,12 +3730,12 @@
}
void addCubic(const SkPoint pts[4]) {
- fSegments.push_back().addCubic(pts, fOperand);
+ fSegments.push_back().addCubic(pts, fOperand, fXor);
fContainsCurves = true;
}
int addLine(const SkPoint pts[2]) {
- fSegments.push_back().addLine(pts, fOperand);
+ fSegments.push_back().addLine(pts, fOperand, fXor);
return fSegments.count();
}
@@ -3767,7 +3744,7 @@
}
int addQuad(const SkPoint pts[3]) {
- fSegments.push_back().addQuad(pts, fOperand);
+ fSegments.push_back().addQuad(pts, fOperand, fXor);
fContainsCurves = true;
return fSegments.count();
}
@@ -3845,11 +3822,10 @@
return segment.pts()[segment.verb()];
}
- void findTooCloseToCall(bool otherXor) {
+ void findTooCloseToCall() {
int segmentCount = fSegments.count();
- otherXor ^= fXor;
for (int sIndex = 0; sIndex < segmentCount; ++sIndex) {
- fSegments[sIndex].findTooCloseToCall(fXor, otherXor);
+ fSegments[sIndex].findTooCloseToCall();
}
}
@@ -3874,13 +3850,18 @@
int count = fCoincidences.count();
for (int index = 0; index < count; ++index) {
Coincidence& coincidence = fCoincidences[index];
- Contour* thisContour = coincidence.fContours[0];
- SkASSERT(thisContour == this);
- Contour* otherContour = coincidence.fContours[1];
+ SkASSERT(coincidence.fContours[0] == this);
int thisIndex = coincidence.fSegments[0];
+ Segment& thisOne = fSegments[thisIndex];
+ if (thisOne.done()) {
+ continue;
+ }
+ Contour* otherContour = coincidence.fContours[1];
int otherIndex = coincidence.fSegments[1];
- Segment& thisOne = thisContour->fSegments[thisIndex];
Segment& other = otherContour->fSegments[otherIndex];
+ if (other.done()) {
+ continue;
+ }
#if DEBUG_CONCIDENT
thisOne.debugShowTs();
other.debugShowTs();
@@ -3900,7 +3881,7 @@
cancelers ^= true;
}
SkASSERT(!approximately_negative(oEndT - oStartT));
- bool opp = thisContour->fOperand ^ otherContour->fOperand;
+ bool opp = fOperand ^ otherContour->fOperand;
if (cancelers && !opp) {
// make sure startT and endT have t entries
if (startT > 0 || oEndT < 1
@@ -3921,8 +3902,7 @@
|| thisOne.isMissing(endT) || other.isMissing(oEndT)) {
other.addTPair(oEndT, thisOne, endT, true);
}
- thisOne.addTCoincident(thisContour->fXor, otherContour->fXor,
- startT, endT, other, oStartT, oEndT);
+ thisOne.addTCoincident(startT, endT, other, oStartT, oEndT);
}
#if DEBUG_CONCIDENT
thisOne.debugShowTs();
@@ -3941,6 +3921,14 @@
void setOperand(bool isOp) {
fOperand = isOp;
}
+
+ void setOppXor(bool isOppXor) {
+ fOppXor = isOppXor;
+ int segmentCount = fSegments.count();
+ for (int test = 0; test < segmentCount; ++test) {
+ fSegments[test].setOppXor(isOppXor);
+ }
+ }
void setXor(bool isXor) {
fXor = isXor;
@@ -4174,6 +4162,7 @@
bool fContainsCurves;
bool fOperand; // true for the second argument to a binary operator
bool fXor;
+ bool fOppXor;
#if DEBUG_DUMP
int fID;
#endif
@@ -4820,7 +4809,7 @@
// resolve any coincident pairs found while intersecting, and
// see if coincidence is formed by clipping non-concident segments
-static void coincidenceCheck(SkTDArray<Contour*>& contourList, bool otherXor, int total) {
+static void coincidenceCheck(SkTDArray<Contour*>& contourList, int total) {
int contourCount = contourList.count();
for (int cIndex = 0; cIndex < contourCount; ++cIndex) {
Contour* contour = contourList[cIndex];
@@ -4828,7 +4817,7 @@
}
for (int cIndex = 0; cIndex < contourCount; ++cIndex) {
Contour* contour = contourList[cIndex];
- contour->findTooCloseToCall(otherXor);
+ contour->findTooCloseToCall();
}
}
@@ -5333,14 +5322,16 @@
}
}
-static void makeContourList(SkTArray<Contour>& contours,
- SkTDArray<Contour*>& list) {
+static void makeContourList(SkTArray<Contour>& contours, SkTDArray<Contour*>& list,
+ bool evenOdd, bool oppEvenOdd) {
int count = contours.count();
if (count == 0) {
return;
}
for (int index = 0; index < count; ++index) {
- *list.append() = &contours[index];
+ Contour& contour = contours[index];
+ contour.setOppXor(contour.operand() ? evenOdd : oppEvenOdd);
+ *list.append() = &contour;
}
QSort<Contour>(list.begin(), list.end() - 1);
}
@@ -5532,7 +5523,7 @@
EdgeBuilder builder(path, contours);
builder.finish();
SkTDArray<Contour*> contourList;
- makeContourList(contours, contourList);
+ makeContourList(contours, contourList, false, false);
Contour** currentPtr = contourList.begin();
if (!currentPtr) {
return;
@@ -5548,7 +5539,7 @@
} while (addIntersectTs(current, next) && nextPtr != listEnd);
} while (currentPtr != listEnd);
// eat through coincident edges
- coincidenceCheck(contourList, false, 0);
+ coincidenceCheck(contourList, 0);
fixOtherTIndex(contourList);
sortSegments(contourList);
#if DEBUG_ACTIVE_SPANS
diff --git a/experimental/Intersection/SimplifyFindNext_Test.cpp b/experimental/Intersection/SimplifyFindNext_Test.cpp
index b6f5d1e..b01b951 100644
--- a/experimental/Intersection/SimplifyFindNext_Test.cpp
+++ b/experimental/Intersection/SimplifyFindNext_Test.cpp
@@ -21,7 +21,7 @@
int contourWinding, int spanWinding, int startIndex, int endIndex,
SkTArray<SimplifyFindNextTest::Contour>& contours) {
SkTDArray<SimplifyFindNextTest::Contour*> contourList;
- makeContourList(contours, contourList);
+ makeContourList(contours, contourList, false, false);
addIntersectTs(contourList[0], contourList[0]);
if (contours.count() > 1) {
SkASSERT(contours.count() == 2);
diff --git a/experimental/Intersection/SimplifyFindTop_Test.cpp b/experimental/Intersection/SimplifyFindTop_Test.cpp
index 0c30b2e..3abcee1 100644
--- a/experimental/Intersection/SimplifyFindTop_Test.cpp
+++ b/experimental/Intersection/SimplifyFindTop_Test.cpp
@@ -19,7 +19,7 @@
SkTArray<SimplifyFindTopTest::Contour>& contours,
int& index, int& end) {
SkTDArray<SimplifyFindTopTest::Contour*> contourList;
- makeContourList(contours, contourList);
+ makeContourList(contours, contourList, false, false);
addIntersectTs(contourList[0], contourList[0]);
if (contours.count() > 1) {
SkASSERT(contours.count() == 2);
diff --git a/experimental/Intersection/SimplifyNew_Test.cpp b/experimental/Intersection/SimplifyNew_Test.cpp
index 2affc05..dfdc75e 100644
--- a/experimental/Intersection/SimplifyNew_Test.cpp
+++ b/experimental/Intersection/SimplifyNew_Test.cpp
@@ -2561,95 +2561,6 @@
testSimplifyx(path);
}
-static void testIntersect1() {
- 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;
- 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;
- 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;
- 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);
-}
-
-static void testOp1d() {
- SkPath path, pathB;
- path.setFillType((SkPath::FillType) 0);
- path.addRect(0, 0, 1, 1, SkPath::kCW_Direction);
- path.addRect(0, 0, 2, 2, SkPath::kCW_Direction);
- pathB.setFillType((SkPath::FillType) 0);
- pathB.addRect(0, 0, 1, 1, SkPath::kCW_Direction);
- pathB.addRect(0, 0, 1, 1, SkPath::kCW_Direction);
- testShapeOp(path, pathB, kDifference_Op);
-}
-
-static void testOp2d() {
- SkPath path, pathB;
- path.setFillType((SkPath::FillType) 0);
- path.addRect(0, 0, 1, 1, SkPath::kCW_Direction);
- path.addRect(0, 0, 2, 2, SkPath::kCW_Direction);
- pathB.setFillType((SkPath::FillType) 1);
- pathB.addRect(0, 0, 1, 1, SkPath::kCW_Direction);
- pathB.addRect(0, 0, 1, 1, SkPath::kCW_Direction);
- testShapeOp(path, pathB, kDifference_Op);
-}
-
-static void testOp3d() {
- SkPath path, pathB;
- path.setFillType((SkPath::FillType) 0);
- path.addRect(0, 0, 1, 1, SkPath::kCW_Direction);
- path.addRect(1, 1, 2, 2, SkPath::kCW_Direction);
- pathB.setFillType((SkPath::FillType) 0);
- pathB.addRect(0, 0, 1, 1, SkPath::kCW_Direction);
- pathB.addRect(0, 0, 1, 1, SkPath::kCW_Direction);
- testShapeOp(path, pathB, kDifference_Op);
-}
-
static void testQuadratic22() {
SkPath path;
path.moveTo(0, 0);
@@ -3249,6 +3160,150 @@
TEST(testLine1),
};
+static void testIntersect1() {
+ 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;
+ 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;
+ 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;
+ 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);
+}
+
+static void testOp1d() {
+ SkPath path, pathB;
+ path.setFillType(SkPath::kWinding_FillType);
+ path.addRect(0, 0, 1, 1, SkPath::kCW_Direction);
+ path.addRect(0, 0, 2, 2, SkPath::kCW_Direction);
+ pathB.setFillType(SkPath::kWinding_FillType);
+ pathB.addRect(0, 0, 1, 1, SkPath::kCW_Direction);
+ pathB.addRect(0, 0, 1, 1, SkPath::kCW_Direction);
+ testShapeOp(path, pathB, kDifference_Op);
+}
+
+static void testOp2d() {
+ SkPath path, pathB;
+ path.setFillType(SkPath::kWinding_FillType);
+ path.addRect(0, 0, 1, 1, SkPath::kCW_Direction);
+ path.addRect(0, 0, 2, 2, SkPath::kCW_Direction);
+ pathB.setFillType(SkPath::kEvenOdd_FillType);
+ pathB.addRect(0, 0, 1, 1, SkPath::kCW_Direction);
+ pathB.addRect(0, 0, 1, 1, SkPath::kCW_Direction);
+ testShapeOp(path, pathB, kDifference_Op);
+}
+
+static void testOp3d() {
+ SkPath path, pathB;
+ path.setFillType(SkPath::kWinding_FillType);
+ path.addRect(0, 0, 1, 1, SkPath::kCW_Direction);
+ path.addRect(1, 1, 2, 2, SkPath::kCW_Direction);
+ pathB.setFillType(SkPath::kWinding_FillType);
+ pathB.addRect(0, 0, 1, 1, SkPath::kCW_Direction);
+ pathB.addRect(0, 0, 1, 1, SkPath::kCW_Direction);
+ testShapeOp(path, pathB, kDifference_Op);
+}
+
+static void testOp1u() {
+ SkPath path, pathB;
+ path.setFillType(SkPath::kWinding_FillType);
+ path.addRect(0, 0, 1, 1, SkPath::kCW_Direction);
+ path.addRect(0, 0, 3, 3, SkPath::kCW_Direction);
+ pathB.setFillType(SkPath::kWinding_FillType);
+ pathB.addRect(0, 0, 1, 1, SkPath::kCW_Direction);
+ pathB.addRect(0, 0, 1, 1, SkPath::kCW_Direction);
+ testShapeOp(path, pathB, kUnion_Op);
+}
+
+static void testOp4d() {
+ SkPath path, pathB;
+ path.setFillType(SkPath::kWinding_FillType);
+ path.addRect(0, 0, 1, 1, SkPath::kCW_Direction);
+ path.addRect(2, 2, 4, 4, SkPath::kCW_Direction);
+ pathB.setFillType(SkPath::kWinding_FillType);
+ pathB.addRect(0, 0, 1, 1, SkPath::kCW_Direction);
+ pathB.addRect(0, 0, 1, 1, SkPath::kCW_Direction);
+ testShapeOp(path, pathB, kDifference_Op);
+}
+
+static void testOp5d() {
+ SkPath path, pathB;
+ path.setFillType(SkPath::kEvenOdd_FillType);
+ path.addRect(0, 0, 2, 2, SkPath::kCW_Direction);
+ path.addRect(0, 0, 3, 3, SkPath::kCW_Direction);
+ pathB.setFillType(SkPath::kEvenOdd_FillType);
+ pathB.addRect(0, 0, 1, 1, SkPath::kCW_Direction);
+ pathB.addRect(0, 0, 1, 1, SkPath::kCW_Direction);
+ testShapeOp(path, pathB, kDifference_Op);
+}
+
+static void testOp6d() {
+ SkPath path, pathB;
+ path.setFillType(SkPath::kEvenOdd_FillType);
+ path.addRect(0, 0, 1, 1, SkPath::kCW_Direction);
+ path.addRect(0, 0, 3, 3, SkPath::kCW_Direction);
+ pathB.setFillType(SkPath::kWinding_FillType);
+ pathB.addRect(0, 0, 1, 1, SkPath::kCW_Direction);
+ pathB.addRect(0, 0, 1, 1, SkPath::kCW_Direction);
+ testShapeOp(path, pathB, kDifference_Op);
+}
+
+static void testOp7d() {
+ SkPath path, pathB;
+ path.setFillType(SkPath::kEvenOdd_FillType);
+ path.addRect(0, 0, 2, 2, SkPath::kCW_Direction);
+ path.addRect(0, 0, 1, 1, SkPath::kCW_Direction);
+ pathB.setFillType(SkPath::kEvenOdd_FillType);
+ pathB.addRect(0, 0, 1, 1, SkPath::kCW_Direction);
+ pathB.addRect(0, 0, 1, 1, SkPath::kCW_Direction);
+ testShapeOp(path, pathB, kDifference_Op);
+}
+
static const size_t testCount = sizeof(tests) / sizeof(tests[0]);
static struct {
@@ -3266,11 +3321,16 @@
TEST(testOp1d),
TEST(testOp2d),
TEST(testOp3d),
+ TEST(testOp1u),
+ TEST(testOp4d),
+ TEST(testOp5d),
+ TEST(testOp6d),
+ TEST(testOp7d),
};
static const size_t subTestCount = sizeof(subTests) / sizeof(subTests[0]);
-static void (*firstBinaryTest)() = testOp1d;
+static void (*firstBinaryTest)() = 0;
static bool skipAll = false;
static bool runBinaryTestsFirst = true;