aboutsummaryrefslogtreecommitdiffhomepage
path: root/experimental
diff options
context:
space:
mode:
Diffstat (limited to 'experimental')
-rwxr-xr-xexperimental/Intersection/EdgeWalkerPolygon4x4_Test.cpp36
-rw-r--r--experimental/Intersection/EdgeWalkerQuadratic4x4_Test.cpp12
-rw-r--r--experimental/Intersection/EdgeWalker_Test.h6
-rw-r--r--experimental/Intersection/EdgeWalker_TestUtility.cpp77
-rw-r--r--experimental/Intersection/Intersection_Tests.cpp14
-rw-r--r--experimental/Intersection/Intersection_Tests.h11
-rw-r--r--experimental/Intersection/LineCubicIntersection.cpp4
-rw-r--r--experimental/Intersection/LineQuadraticIntersection.cpp51
-rw-r--r--experimental/Intersection/LineQuadraticIntersection_Test.cpp118
-rw-r--r--experimental/Intersection/Simplify.cpp454
-rw-r--r--experimental/Intersection/SimplifyFindNext_Test.cpp8
-rw-r--r--experimental/Intersection/SimplifyNew_Test.cpp239
-rw-r--r--experimental/Intersection/SimplifyRect4x4_Test.cpp13
-rw-r--r--experimental/Intersection/op.htm195
14 files changed, 991 insertions, 247 deletions
diff --git a/experimental/Intersection/EdgeWalkerPolygon4x4_Test.cpp b/experimental/Intersection/EdgeWalkerPolygon4x4_Test.cpp
index e795cd0410..befac71c7c 100755
--- a/experimental/Intersection/EdgeWalkerPolygon4x4_Test.cpp
+++ b/experimental/Intersection/EdgeWalkerPolygon4x4_Test.cpp
@@ -53,15 +53,13 @@ static void* testSimplify4x4QuadralateralsMain(void* data)
str += sprintf(str, " path.lineTo(%d, %d);\n", hx, hy);
str += sprintf(str, " path.close();\n");
}
- outputProgress(state, pathStr);
- testSimplifyx(path, out, state, pathStr);
+ outputProgress(state, pathStr, SkPath::kWinding_FillType);
+ testSimplifyx(path, false, out, state, pathStr);
state.testsRun++;
- #if 0 // FIXME: enable once we have support for even/odd
path.setFillType(SkPath::kEvenOdd_FillType);
outputProgress(state, pathStr, SkPath::kEvenOdd_FillType);
testSimplifyx(path, true, out, state, pathStr);
state.testsRun++;
- #endif
}
}
}
@@ -70,7 +68,7 @@ static void* testSimplify4x4QuadralateralsMain(void* data)
return NULL;
}
-void Simplify4x4QuadralateralsThreaded_Test()
+void Simplify4x4QuadralateralsThreaded_Test(int& testsRun)
{
SkDebugf("%s\n", __FUNCTION__);
#ifdef SK_DEBUG
@@ -79,7 +77,7 @@ void Simplify4x4QuadralateralsThreaded_Test()
#endif
const char testStr[] = "testQuadralateral";
initializeTests(testStr, sizeof(testStr));
- int testsRun = 0;
+ int testsStart = testsRun;
for (int a = 0; a < 16; ++a) {
for (int b = a ; b < 16; ++b) {
for (int c = b ; c < 16; ++c) {
@@ -94,7 +92,7 @@ void Simplify4x4QuadralateralsThreaded_Test()
if (!gRunTestsInOneThread) SkDebugf("\n%d", a);
}
testsRun += waitForCompletion();
- SkDebugf("%s total tests run=%d\n", __FUNCTION__, testsRun);
+ SkDebugf("%s tests=%d total=%d\n", __FUNCTION__, testsRun - testsStart, testsRun);
}
@@ -146,15 +144,13 @@ static void* testSimplify4x4NondegeneratesMain(void* data) {
str += sprintf(str, " path.lineTo(%d, %d);\n", fx, fy);
str += sprintf(str, " path.close();\n");
}
- outputProgress(state, pathStr);
- testSimplifyx(path, out, state, pathStr);
+ outputProgress(state, pathStr, SkPath::kWinding_FillType);
+ testSimplifyx(path, false, out, state, pathStr);
state.testsRun++;
- #if 0 // FIXME: enable once we have support for even/odd
path.setFillType(SkPath::kEvenOdd_FillType);
outputProgress(state, pathStr, SkPath::kEvenOdd_FillType);
testSimplifyx(path, true, out, state, pathStr);
state.testsRun++;
- #endif
}
}
}
@@ -162,7 +158,7 @@ static void* testSimplify4x4NondegeneratesMain(void* data) {
return NULL;
}
-void SimplifyNondegenerate4x4TrianglesThreaded_Test() {
+void SimplifyNondegenerate4x4TrianglesThreaded_Test(int& testsRun) {
SkDebugf("%s\n", __FUNCTION__);
#ifdef SK_DEBUG
gDebugMaxWindSum = 2;
@@ -170,7 +166,7 @@ void SimplifyNondegenerate4x4TrianglesThreaded_Test() {
#endif
const char testStr[] = "testNondegenerate";
initializeTests(testStr, sizeof(testStr));
- int testsRun = 0;
+ int testsStart = testsRun;
for (int a = 0; a < 15; ++a) {
int ax = a & 0x03;
int ay = a >> 2;
@@ -194,7 +190,7 @@ void SimplifyNondegenerate4x4TrianglesThreaded_Test() {
if (!gRunTestsInOneThread) SkDebugf("\n%d", a);
}
testsRun += waitForCompletion();
- SkDebugf("%s total tests run=%d\n", __FUNCTION__, testsRun);
+ SkDebugf("%s tests=%d total=%d\n", __FUNCTION__, testsRun - testsStart, testsRun);
}
static void* testSimplify4x4DegeneratesMain(void* data) {
@@ -243,15 +239,13 @@ static void* testSimplify4x4DegeneratesMain(void* data) {
str += sprintf(str, " path.lineTo(%d, %d);\n", fx, fy);
str += sprintf(str, " path.close();\n");
}
- outputProgress(state, pathStr);
- testSimplifyx(path, out, state, pathStr);
+ outputProgress(state, pathStr, SkPath::kWinding_FillType);
+ testSimplifyx(path, false, out, state, pathStr);
state.testsRun++;
- #if 0 // FIXME: enable once we have support for even/odd
path.setFillType(SkPath::kEvenOdd_FillType);
outputProgress(state, pathStr, SkPath::kEvenOdd_FillType);
testSimplifyx(path, true, out, state, pathStr);
state.testsRun++;
- #endif
}
}
}
@@ -259,7 +253,7 @@ static void* testSimplify4x4DegeneratesMain(void* data) {
return NULL;
}
-void SimplifyDegenerate4x4TrianglesThreaded_Test() {
+void SimplifyDegenerate4x4TrianglesThreaded_Test(int& testsRun) {
SkDebugf("%s\n", __FUNCTION__);
#ifdef SK_DEBUG
gDebugMaxWindSum = 2;
@@ -267,7 +261,7 @@ void SimplifyDegenerate4x4TrianglesThreaded_Test() {
#endif
const char testStr[] = "testDegenerate";
initializeTests(testStr, sizeof(testStr));
- int testsRun = 0;
+ int testsStart = testsRun;
for (int a = 0; a < 16; ++a) {
int ax = a & 0x03;
int ay = a >> 2;
@@ -286,6 +280,6 @@ void SimplifyDegenerate4x4TrianglesThreaded_Test() {
if (!gRunTestsInOneThread) SkDebugf("\n%d", a);
}
testsRun += waitForCompletion();
- SkDebugf("%s total tests run=%d\n", __FUNCTION__, testsRun);
+ SkDebugf("%s tests=%d total=%d\n", __FUNCTION__, testsRun - testsStart, testsRun);
}
diff --git a/experimental/Intersection/EdgeWalkerQuadratic4x4_Test.cpp b/experimental/Intersection/EdgeWalkerQuadratic4x4_Test.cpp
index f7142495d9..1f5af8ec6c 100644
--- a/experimental/Intersection/EdgeWalkerQuadratic4x4_Test.cpp
+++ b/experimental/Intersection/EdgeWalkerQuadratic4x4_Test.cpp
@@ -53,15 +53,13 @@ static void* testSimplify4x4QuadraticsMain(void* data)
str += sprintf(str, " path.quadTo(%d, %d, %d, %d);\n", gx, gy, hx, hy);
str += sprintf(str, " path.close();\n");
}
- outputProgress(state, pathStr);
- testSimplifyx(path, out, state, pathStr);
+ outputProgress(state, pathStr, SkPath::kWinding_FillType);
+ testSimplifyx(path, false, out, state, pathStr);
state.testsRun++;
- #if 0 // FIXME: enable once we have support for even/odd
path.setFillType(SkPath::kEvenOdd_FillType);
outputProgress(state, pathStr, SkPath::kEvenOdd_FillType);
testSimplifyx(path, true, out, state, pathStr);
state.testsRun++;
- #endif
}
}
}
@@ -70,7 +68,7 @@ static void* testSimplify4x4QuadraticsMain(void* data)
return NULL;
}
-void Simplify4x4QuadraticsThreaded_Test()
+void Simplify4x4QuadraticsThreaded_Test(int& testsRun)
{
SkDebugf("%s\n", __FUNCTION__);
#ifdef SK_DEBUG
@@ -79,7 +77,7 @@ void Simplify4x4QuadraticsThreaded_Test()
#endif
const char testStr[] = "testQuadratic";
initializeTests(testStr, sizeof(testStr));
- int testsRun = 0;
+ int testsStart = testsRun;
for (int a = 0; a < 16; ++a) {
for (int b = a ; b < 16; ++b) {
for (int c = b ; c < 16; ++c) {
@@ -94,5 +92,5 @@ void Simplify4x4QuadraticsThreaded_Test()
if (!gRunTestsInOneThread) SkDebugf("\n%d", a);
}
testsRun += waitForCompletion();
- SkDebugf("%s total tests run=%d\n", __FUNCTION__, testsRun);
+ SkDebugf("%s tests=%d total=%d\n", __FUNCTION__, testsRun - testsStart, testsRun);
}
diff --git a/experimental/Intersection/EdgeWalker_Test.h b/experimental/Intersection/EdgeWalker_Test.h
index 229a94dae0..c86cefd9d1 100644
--- a/experimental/Intersection/EdgeWalker_Test.h
+++ b/experimental/Intersection/EdgeWalker_Test.h
@@ -16,7 +16,7 @@ extern bool drawAsciiPaths(const SkPath& one, const SkPath& two,
extern void showPath(const SkPath& path, const char* str = NULL);
extern bool testSimplify(const SkPath& path, bool fill, SkPath& out,
SkBitmap& bitmap, SkCanvas* canvas = 0);
-extern bool testSimplifyx(const SkPath& path, SkPath& out,
+extern bool testSimplifyx(SkPath& path, bool useXor, SkPath& out,
State4& state, const char* pathStr);
extern bool testSimplifyx(const SkPath& path);
@@ -44,7 +44,7 @@ struct State4 {
void createThread(State4* statePtr, void* (*test)(void* ));
int dispatchTest4(void* (*testFun)(void* ), int a, int b, int c, int d);
void initializeTests(const char* testName, size_t testNameSize);
-void outputProgress(const State4& state, const char* pathStr);
-void outputToStream(const State4& state, const char* pathStr, SkWStream& outFile);
+void outputProgress(const State4& state, const char* pathStr, SkPath::FillType );
+void outputToStream(const State4& state, const char* pathStr, SkPath::FillType, SkWStream& outFile);
bool runNextTestSet(State4& state);
int waitForCompletion();
diff --git a/experimental/Intersection/EdgeWalker_TestUtility.cpp b/experimental/Intersection/EdgeWalker_TestUtility.cpp
index 7baa17b055..0fb37b0840 100644
--- a/experimental/Intersection/EdgeWalker_TestUtility.cpp
+++ b/experimental/Intersection/EdgeWalker_TestUtility.cpp
@@ -22,11 +22,9 @@ static const char marker[] =
"<script type=\"text/javascript\">\n"
"\n"
"var testDivs = [\n";
-#if 0
-static const char filename[] = "../../experimental/Intersection/debugXX.txt";
-#else
-static const char filename[] = "/flash/debug/XX.txt";
-#endif
+
+static const char preferredFilename[] = "/flash/debug/XX.txt";
+static const char backupFilename[] = "../../experimental/Intersection/debugXX.txt";
static bool gShowPath = false;
static bool gComparePaths = true;
@@ -278,8 +276,10 @@ bool testSimplify(const SkPath& path, bool fill, SkPath& out, SkBitmap& bitmap,
return comparePaths(path, out, bitmap, canvas) == 0;
}
-bool testSimplifyx(const SkPath& path, SkPath& out, State4& state,
+bool testSimplifyx(SkPath& path, bool useXor, SkPath& out, State4& state,
const char* pathStr) {
+ SkPath::FillType fillType = useXor ? SkPath::kEvenOdd_FillType : SkPath::kWinding_FillType;
+ path.setFillType(fillType);
if (gShowPath) {
showPath(path);
}
@@ -292,7 +292,7 @@ bool testSimplifyx(const SkPath& path, SkPath& out, State4& state,
char temp[8192];
bzero(temp, sizeof(temp));
SkMemoryWStream stream(temp, sizeof(temp));
- outputToStream(state, pathStr, stream);
+ outputToStream(state, pathStr, fillType, stream);
SkDebugf(temp);
SkASSERT(0);
}
@@ -300,16 +300,14 @@ bool testSimplifyx(const SkPath& path, SkPath& out, State4& state,
}
bool testSimplifyx(const SkPath& path) {
- if (false) {
- showPath(path);
- }
SkPath out;
simplifyx(path, out);
- if (false) {
- return true;
- }
SkBitmap bitmap;
- return comparePaths(path, out, bitmap, 0) == 0;
+ int result = comparePaths(path, out, bitmap, 0);
+ if (result && gPathStrAssert) {
+ SkASSERT(0);
+ }
+ return result == 0;
}
const int maxThreadsAllocated = 64;
@@ -422,18 +420,26 @@ void initializeTests(const char* test, size_t testNameSize) {
}
}
}
+ const char* filename = preferredFilename;
+ SkFILEWStream preferredTest(filename);
+ if (!preferredTest.isValid()) {
+ filename = backupFilename;
+ SkFILEWStream backupTest(filename);
+ SkASSERT(backupTest.isValid());
+ }
for (int index = 0; index < maxThreads; ++index) {
State4* statePtr = &threadState[index];
strcpy(statePtr->filename, filename);
- SkASSERT(statePtr->filename[sizeof(filename) - 7] == 'X');
- SkASSERT(statePtr->filename[sizeof(filename) - 6] == 'X');
- statePtr->filename[sizeof(filename) - 7] = '0' + index / 10;
- statePtr->filename[sizeof(filename) - 6] = '0' + index % 10;
+ size_t len = strlen(filename);
+ SkASSERT(statePtr->filename[len - 6] == 'X');
+ SkASSERT(statePtr->filename[len - 5] == 'X');
+ statePtr->filename[len - 6] = '0' + index / 10;
+ statePtr->filename[len - 5] = '0' + index % 10;
}
threadIndex = 0;
}
-void outputProgress(const State4& state, const char* pathStr) {
+void outputProgress(const State4& state, const char* pathStr, SkPath::FillType pathFillType) {
if (gRunTestsInOneThread) {
SkDebugf("%s\n", pathStr);
} else {
@@ -442,33 +448,43 @@ void outputProgress(const State4& state, const char* pathStr) {
SkASSERT(0);
return;
}
- outputToStream(state, pathStr, outFile);
+ outputToStream(state, pathStr, pathFillType, outFile);
}
}
-void outputToStream(const State4& state, const char* pathStr, SkWStream& outFile) {
- outFile.writeText("<div id=\"");
+static void writeTestName(SkPath::FillType pathFillType, SkWStream& outFile) {
outFile.writeText(testName);
outFile.writeDecAsText(testNumber);
+ if (pathFillType == SkPath::kEvenOdd_FillType) {
+ outFile.writeText("x");
+ }
+}
+
+void outputToStream(const State4& state, const char* pathStr, SkPath::FillType pathFillType, SkWStream& outFile) {
+ outFile.writeText("<div id=\"");
+ writeTestName(pathFillType, outFile);
outFile.writeText("\">\n");
+ if (pathFillType == SkPath::kEvenOdd_FillType) {
+ outFile.writeText(" path.setFillType(SkPath::kEvenOdd_FillType);\n");
+ }
outFile.writeText(pathStr);
outFile.writeText("</div>\n\n");
outFile.writeText(marker);
outFile.writeText(" ");
- outFile.writeText(testName);
- outFile.writeDecAsText(testNumber);
+ writeTestName(pathFillType, outFile);
outFile.writeText(",\n\n\n");
outFile.writeText("static void ");
- outFile.writeText(testName);
- outFile.writeDecAsText(testNumber);
+ writeTestName(pathFillType, outFile);
outFile.writeText("() {\n SkPath path;\n");
+ if (pathFillType == SkPath::kEvenOdd_FillType) {
+ outFile.writeText(" path.setFillType(SkPath::kEvenOdd_FillType);\n");
+ }
outFile.writeText(pathStr);
outFile.writeText(" testSimplifyx(path);\n}\n\n");
outFile.writeText("static void (*firstTest)() = ");
- outFile.writeText(testName);
- outFile.writeDecAsText(testNumber);
+ writeTestName(pathFillType, outFile);
outFile.writeText(";\n\n");
outFile.writeText("static struct {\n");
@@ -476,8 +492,7 @@ void outputToStream(const State4& state, const char* pathStr, SkWStream& outFile
outFile.writeText(" const char* str;\n");
outFile.writeText("} tests[] = {\n");
outFile.writeText(" TEST(");
- outFile.writeText(testName);
- outFile.writeDecAsText(testNumber);
+ writeTestName(pathFillType, outFile);
outFile.writeText("),\n");
outFile.flush();
}
@@ -515,7 +530,7 @@ int waitForCompletion() {
--runningThreads;
SkDebugf("•");
State4::queue->last = true;
- State4* next;
+ State4* next = NULL;
for (index = 0; index < maxThreads; ++index) {
State4& test = threadState[index];
if (test.done && !test.last) {
diff --git a/experimental/Intersection/Intersection_Tests.cpp b/experimental/Intersection/Intersection_Tests.cpp
index 414b911a37..67885b39de 100644
--- a/experimental/Intersection/Intersection_Tests.cpp
+++ b/experimental/Intersection/Intersection_Tests.cpp
@@ -1,17 +1,21 @@
#include "CubicIntersection_TestData.h"
#include "Intersection_Tests.h"
+#include "SkTypes.h"
void cubecode_test(int test);
#define TEST_QUADS_FIRST 0
void Intersection_Tests() {
+ int testsRun = 0;
+ QuadLineIntersectThreaded_Test(testsRun);
SimplifyNew_Test();
- Simplify4x4QuadralateralsThreaded_Test();
- Simplify4x4QuadraticsThreaded_Test();
- Simplify4x4RectsThreaded_Test();
- SimplifyNondegenerate4x4TrianglesThreaded_Test();
- SimplifyDegenerate4x4TrianglesThreaded_Test();
+ Simplify4x4QuadraticsThreaded_Test(testsRun);
+ Simplify4x4RectsThreaded_Test(testsRun);
+ SimplifyNondegenerate4x4TrianglesThreaded_Test(testsRun);
+ SimplifyDegenerate4x4TrianglesThreaded_Test(testsRun);
+ Simplify4x4QuadralateralsThreaded_Test(testsRun);
+ SkDebugf("%s total testsRun=%d\n", __FUNCTION__, testsRun);
SimplifyFindNext_Test();
SimplifyFindTop_Test();
SimplifyAngle_Test();
diff --git a/experimental/Intersection/Intersection_Tests.h b/experimental/Intersection/Intersection_Tests.h
index 4873bf9845..4dcadefe25 100644
--- a/experimental/Intersection/Intersection_Tests.h
+++ b/experimental/Intersection/Intersection_Tests.h
@@ -18,18 +18,19 @@ void LineParameter_Test();
void LineQuadraticIntersection_Test();
void SimplifyAddIntersectingTs_Test();
void SimplifyAngle_Test();
-void SimplifyDegenerate4x4TrianglesThreaded_Test();
+void SimplifyDegenerate4x4TrianglesThreaded_Test(int& );
void SimplifyFindNext_Test();
void SimplifyFindTop_Test();
void SimplifyNew_Test();
-void SimplifyNondegenerate4x4TrianglesThreaded_Test();
+void SimplifyNondegenerate4x4TrianglesThreaded_Test(int& );
void SimplifyPolygonPaths_Test();
void SimplifyQuadralateralPaths_Test();
void SimplifyQuadraticPaths_Test();
-void Simplify4x4QuadralateralsThreaded_Test();
-void Simplify4x4QuadraticsThreaded_Test();
-void Simplify4x4RectsThreaded_Test();
+void Simplify4x4QuadralateralsThreaded_Test(int& );
+void Simplify4x4QuadraticsThreaded_Test(int& );
+void Simplify4x4RectsThreaded_Test(int& );
void SimplifyRectangularPaths_Test();
+void QuadLineIntersectThreaded_Test(int& );
void QuadraticBezierClip_Test();
void QuadraticCoincidence_Test();
void QuadraticIntersection_Test();
diff --git a/experimental/Intersection/LineCubicIntersection.cpp b/experimental/Intersection/LineCubicIntersection.cpp
index 6f2cf6c5e5..aaee2a1d38 100644
--- a/experimental/Intersection/LineCubicIntersection.cpp
+++ b/experimental/Intersection/LineCubicIntersection.cpp
@@ -178,7 +178,7 @@ int horizontalIntersect(const Cubic& cubic, double left, double right, double y,
}
continue;
}
- intersections.fT[0][index] = (x - left) / (right - left);
+ intersections.fT[1][index] = (x - left) / (right - left);
++index;
}
if (flipped) {
@@ -199,7 +199,7 @@ int verticalIntersect(const Cubic& cubic, double top, double bottom, double x,
xy_at_t(cubic, intersections.fT[0][index], x, y);
if (y < top || y > bottom) {
if (--result > index) {
- intersections.fT[0][index] = intersections.fT[0][result];
+ intersections.fT[1][index] = intersections.fT[0][result];
}
continue;
}
diff --git a/experimental/Intersection/LineQuadraticIntersection.cpp b/experimental/Intersection/LineQuadraticIntersection.cpp
index 1bc831b643..e2e712f1b3 100644
--- a/experimental/Intersection/LineQuadraticIntersection.cpp
+++ b/experimental/Intersection/LineQuadraticIntersection.cpp
@@ -128,6 +128,29 @@ bool intersect() {
for (int x = 0; x < roots; ++x) {
intersections.add(t[x], findLineT(t[x]));
}
+ // FIXME: quadratic root doesn't find t=0 or t=1, necessitating the hack below
+ if (roots == 0 || (roots == 1 && intersections.fT[0][0] >= FLT_EPSILON)) {
+ if (quad[0] == line[0]) {
+ intersections.fT[0][roots] = 0;
+ intersections.fT[1][roots++] = 0;
+ intersections.fUsed++;
+ } else if (quad[0] == line[1]) {
+ intersections.fT[0][roots] = 0;
+ intersections.fT[1][roots++] = 1;
+ intersections.fUsed++;
+ }
+ }
+ if (roots == 0 || (roots == 1 && intersections.fT[0][0] <= 1 - FLT_EPSILON)) {
+ if (quad[2] == line[1]) {
+ intersections.fT[0][roots] = 1;
+ intersections.fT[1][roots++] = 1;
+ intersections.fUsed++;
+ } else if (quad[2] == line[0]) {
+ intersections.fT[0][roots] = 1;
+ intersections.fT[1][roots++] = 0;
+ intersections.fUsed++;
+ }
+ }
return roots > 0;
}
@@ -138,7 +161,17 @@ int horizontalIntersect(double axisIntercept) {
D += F - 2 * E; // D = d - 2*e + f
E -= F; // E = -(d - e)
F -= axisIntercept;
- return quadraticRoots(D, E, F, intersections.fT[0]);
+ int roots = quadraticRoots(D, E, F, intersections.fT[0]);
+ // FIXME: ? quadraticRoots doesn't pick up intersections at 0, 1
+ if (roots < 2 && fabs(F) < FLT_EPSILON
+ && (roots == 0 || intersections.fT[0][0] >= FLT_EPSILON)) {
+ intersections.fT[0][roots++] = 0;
+ }
+ if (roots < 2 && fabs(quad[2].y - axisIntercept) < FLT_EPSILON
+ && (roots == 0 || intersections.fT[0][0] <= 1 - FLT_EPSILON)) {
+ intersections.fT[0][roots++] = 1;
+ }
+ return roots;
}
int verticalIntersect(double axisIntercept) {
@@ -148,7 +181,17 @@ int verticalIntersect(double axisIntercept) {
D += F - 2 * E; // D = d - 2*e + f
E -= F; // E = -(d - e)
F -= axisIntercept;
- return quadraticRoots(D, E, F, intersections.fT[0]);
+ int roots = quadraticRoots(D, E, F, intersections.fT[0]);
+ // FIXME: ? quadraticRoots doesn't pick up intersections at 0, 1
+ if (roots < 2 && fabs(F) < FLT_EPSILON
+ && (roots == 0 || intersections.fT[0][0] >= FLT_EPSILON)) {
+ intersections.fT[0][roots++] = 0;
+ }
+ if (roots < 2 && fabs(quad[2].x - axisIntercept) < FLT_EPSILON
+ && (roots == 0 || intersections.fT[0][0] <= 1 - FLT_EPSILON)) {
+ intersections.fT[0][roots++] = 1;
+ }
+ return roots;
}
protected:
@@ -247,7 +290,7 @@ int horizontalIntersect(const Quadratic& quad, double left, double right, double
}
continue;
}
- intersections.fT[0][index] = (x - left) / (right - left);
+ intersections.fT[1][index] = (x - left) / (right - left);
++index;
}
if (flipped) {
@@ -272,7 +315,7 @@ int verticalIntersect(const Quadratic& quad, double top, double bottom, double x
}
continue;
}
- intersections.fT[0][index] = (y - top) / (bottom - top);
+ intersections.fT[1][index] = (y - top) / (bottom - top);
++index;
}
if (flipped) {
diff --git a/experimental/Intersection/LineQuadraticIntersection_Test.cpp b/experimental/Intersection/LineQuadraticIntersection_Test.cpp
index 7551dc3df2..1161d2de29 100644
--- a/experimental/Intersection/LineQuadraticIntersection_Test.cpp
+++ b/experimental/Intersection/LineQuadraticIntersection_Test.cpp
@@ -1,5 +1,6 @@
#include "CurveIntersection.h"
#include "CurveUtilities.h"
+#include "EdgeWalker_Test.h"
#include "Intersection_Tests.h"
#include "Intersections.h"
#include "TestUtilities.h"
@@ -55,3 +56,120 @@ void LineQuadraticIntersection_Test() {
}
}
}
+
+static void testLineIntersect(State4& state, const Quadratic& quad, const _Line& line,
+ const double x, const double y) {
+ char pathStr[1024];
+ bzero(pathStr, sizeof(pathStr));
+ char* str = pathStr;
+ str += sprintf(str, " path.moveTo(%1.9g, %1.9g);\n", quad[0].x, quad[0].y);
+ str += sprintf(str, " path.quadTo(%1.9g, %1.9g, %1.9g, %1.9g);\n", quad[1].x, quad[1].y, quad[2].x, quad[2].y);
+ str += sprintf(str, " path.moveTo(%1.9g, %1.9g);\n", line[0].x, line[0].y);
+ str += sprintf(str, " path.lineTo(%1.9g, %1.9g);\n", line[1].x, line[1].y);
+
+ Intersections intersections;
+ int result;
+ bool flipped = false;
+ if (line[0].x == line[1].x) {
+ double top = line[0].y;
+ double bottom = line[1].y;
+ bool flipped = top > bottom;
+ if (flipped) {
+ SkTSwap<double>(top, bottom);
+ }
+ result = verticalIntersect(quad, top, bottom, line[0].x, flipped, intersections);
+ } else if (line[0].y == line[1].y) {
+ double left = line[0].x;
+ double right = line[1].x;
+ bool flipped = left > right;
+ if (flipped) {
+ SkTSwap<double>(left, right);
+ }
+ result = horizontalIntersect(quad, left, right, line[0].y, flipped, intersections);
+ } else {
+ intersect(quad, line, intersections);
+ result = intersections.fUsed;
+ }
+ bool found = false;
+ for (int index = 0; index < result; ++index) {
+ double quadT = intersections.fT[0][index];
+ double quadX, quadY;
+ xy_at_t(quad, quadT, quadX, quadY);
+ double lineT = intersections.fT[1][index];
+ if (flipped) {
+ lineT = 1 - lineT;
+ }
+ double lineX, lineY;
+ xy_at_t(line, lineT, lineX, lineY);
+ if (fabs(quadX - lineX) < FLT_EPSILON && fabs(quadY - lineY) < FLT_EPSILON
+ && fabs(x - lineX) < FLT_EPSILON && fabs(y - lineY) < FLT_EPSILON) {
+ found = true;
+ }
+ }
+ SkASSERT(found);
+ state.testsRun++;
+}
+
+
+// find a point on a quad by choosing a t from 0 to 1
+// create a vertical span above and below the point
+// verify that intersecting the vertical span and the quad returns t
+// verify that a vertical span starting at quad[0] intersects at t=0
+// verify that a vertical span starting at quad[2] intersects at t=1
+static void* testQuadLineIntersectMain(void* data)
+{
+ SkASSERT(data);
+ State4& state = *(State4*) data;
+ do {
+ int ax = state.a & 0x03;
+ int ay = state.a >> 2;
+ int bx = state.b & 0x03;
+ int by = state.b >> 2;
+ int cx = state.c & 0x03;
+ int cy = state.c >> 2;
+ Quadratic quad = {{ax, ay}, {bx, by}, {cx, cy}};
+ Quadratic reduced;
+ int order = reduceOrder(quad, reduced);
+ if (order < 3) {
+ continue; // skip degenerates
+ }
+ for (int tIndex = 0; tIndex <= 4; ++tIndex) {
+ double x, y;
+ xy_at_t(quad, tIndex / 4.0, x, y);
+ for (int h = -2; h <= 2; ++h) {
+ for (int v = -2; v <= 2; ++v) {
+ if (h == v && abs(h) != 1) {
+ continue;
+ }
+ _Line line = {{x - h, y - v}, {x, y}};
+ testLineIntersect(state, quad, line, x, y);
+ _Line line2 = {{x, y}, {x + h, y + v}};
+ testLineIntersect(state, quad, line2, x, y);
+ _Line line3 = {{x - h, y - v}, {x + h, y + v}};
+ testLineIntersect(state, quad, line3, x, y);
+ }
+ }
+ }
+ } while (runNextTestSet(state));
+ return NULL;
+}
+
+void QuadLineIntersectThreaded_Test(int& testsRun)
+{
+ SkDebugf("%s\n", __FUNCTION__);
+ const char testStr[] = "testQuadLineIntersect";
+ initializeTests(testStr, sizeof(testStr));
+ int testsStart = testsRun;
+ for (int a = 0; a < 16; ++a) {
+ for (int b = 0 ; b < 16; ++b) {
+ for (int c = 0 ; c < 16; ++c) {
+ testsRun += dispatchTest4(testQuadLineIntersectMain,
+ a, b, c, 0);
+ }
+ if (!gRunTestsInOneThread) SkDebugf(".");
+ }
+ if (!gRunTestsInOneThread) SkDebugf("%d", a);
+ }
+ testsRun += waitForCompletion();
+ SkDebugf("\n%s tests=%d total=%d\n", __FUNCTION__, testsRun - testsStart, testsRun);
+}
diff --git a/experimental/Intersection/Simplify.cpp b/experimental/Intersection/Simplify.cpp
index 9ffa33c734..eb6bda5457 100644
--- a/experimental/Intersection/Simplify.cpp
+++ b/experimental/Intersection/Simplify.cpp
@@ -48,12 +48,12 @@ const bool gRunTestsInOneThread = false;
const bool gRunTestsInOneThread = true;
#define DEBUG_ACTIVE_SPANS 1
-#define DEBUG_ADD_INTERSECTING_TS 0
-#define DEBUG_ADD_T_PAIR 1
+#define DEBUG_ADD_INTERSECTING_TS 1
+#define DEBUG_ADD_T_PAIR 0
#define DEBUG_CONCIDENT 1
#define DEBUG_CROSS 0
#define DEBUG_DUMP 1
-#define DEBUG_MARK_DONE 1
+#define DEBUG_MARK_DONE 0
#define DEBUG_PATH_CONSTRUCTION 1
#define DEBUG_SORT 1
#define DEBUG_WIND_BUMP 0
@@ -359,13 +359,12 @@ static SkPath::Verb QuadReduceOrder(const SkPoint a[3],
{a[2].fX, a[2].fY}};
Quadratic dst;
int order = reduceOrder(aQuad, dst);
- if (order == 3) {
- return SkPath::kQuad_Verb;
- }
- for (int index = 0; index < order; ++index) {
- SkPoint* pt = reducePts.append();
- pt->fX = SkDoubleToScalar(dst[index].x);
- pt->fY = SkDoubleToScalar(dst[index].y);
+ if (order == 2) { // quad became line
+ for (int index = 0; index < order; ++index) {
+ SkPoint* pt = reducePts.append();
+ pt->fX = SkDoubleToScalar(dst[index].x);
+ pt->fY = SkDoubleToScalar(dst[index].y);
+ }
}
return (SkPath::Verb) (order - 1);
}
@@ -376,13 +375,12 @@ static SkPath::Verb CubicReduceOrder(const SkPoint a[4],
{a[2].fX, a[2].fY}, {a[3].fX, a[3].fY}};
Cubic dst;
int order = reduceOrder(aCubic, dst, kReduceOrder_QuadraticsAllowed);
- if (order == 4) {
- return SkPath::kCubic_Verb;
- }
- for (int index = 0; index < order; ++index) {
- SkPoint* pt = reducePts.append();
- pt->fX = SkDoubleToScalar(dst[index].x);
- pt->fY = SkDoubleToScalar(dst[index].y);
+ if (order == 2 || order == 3) { // cubic became line or quad
+ for (int index = 0; index < order; ++index) {
+ SkPoint* pt = reducePts.append();
+ pt->fX = SkDoubleToScalar(dst[index].x);
+ pt->fY = SkDoubleToScalar(dst[index].y);
+ }
}
return (SkPath::Verb) (order - 1);
}
@@ -661,7 +659,7 @@ static bool useInnerWinding(int outerWinding, int innerWinding) {
bool result = absOut == absIn ? outerWinding < 0 : absOut < absIn;
if (outerWinding * innerWinding < 0) {
#if DEBUG_WINDING
- SkDebugf("%s *** outer=%d inner=%d result=%s\n", __FUNCTION__,
+ SkDebugf("%s outer=%d inner=%d result=%s\n", __FUNCTION__,
outerWinding, innerWinding, result ? "true" : "false");
#endif
}
@@ -1067,7 +1065,7 @@ public:
// set spans from start to end to increment the greater by one and decrement
// the lesser
- void addTCoincident(double startT, double endT, Segment& other,
+ void addTCoincident(const int xorMask, double startT, double endT, Segment& other,
double oStartT, double oEndT) {
SkASSERT(endT - startT >= FLT_EPSILON);
SkASSERT(oEndT - oStartT >= FLT_EPSILON);
@@ -1088,7 +1086,9 @@ public:
SkTDArray<double> oxOutsideTs;
do {
bool transfer = test->fWindValue && oTest->fWindValue;
- bool decrementOther = test->fWindValue >= oTest->fWindValue;
+ bool winding = xorMask < 0;
+ bool decrementThis = (test->fWindValue < oTest->fWindValue) & winding;
+ bool decrementOther = (test->fWindValue >= oTest->fWindValue) & winding;
Span* end = test;
double startT = end->fT;
int startIndex = index;
@@ -1118,7 +1118,7 @@ public:
Span* oEnd = oTest;
while (oEnd->fT < oEndT - FLT_EPSILON && oEnd->fT - otherTMatch < FLT_EPSILON) {
if (transfer) {
- if (!decrementOther) {
+ if (decrementThis) {
SkASSERT(abs(oEnd->fWindValue) < gDebugMaxWindValue);
++(oEnd->fWindValue);
} else if (other.decrementSpan(oEnd)) {
@@ -1271,7 +1271,7 @@ public:
int spanWinding = base->spanSign(angle);
bool inner = useInnerWinding(winding + spanWinding, winding);
#if DEBUG_WINDING
- SkDebugf("%s --- spanWinding=%d winding=%d sign=%d inner=%d result=%d\n", __FUNCTION__,
+ SkDebugf("%s spanWinding=%d winding=%d sign=%d inner=%d result=%d\n", __FUNCTION__,
spanWinding, winding, angle->sign(), inner,
inner ? winding + spanWinding : winding);
#endif
@@ -1316,7 +1316,9 @@ public:
SkPoint edge[4];
// OPTIMIZE: wrap this so that if start==0 end==fTCount-1 we can
// work with the original data directly
- (*SegmentSubDivide[fVerb])(fPts, fTs[start].fT, fTs[end].fT, edge);
+ double startT = fTs[start].fT;
+ double endT = fTs[end].fT;
+ (*SegmentSubDivide[fVerb])(fPts, startT, endT, edge);
// intersect ray starting at basePt with edge
Intersections intersections;
int pts = (*VSegmentIntersect[fVerb])(edge, top, bottom, basePt.fX,
@@ -1331,11 +1333,12 @@ public:
SkASSERT(pts == 1); // FIXME: more code required to disambiguate
SkPoint pt;
double foundT = intersections.fT[0][0];
- (*SegmentXYAtT[fVerb])(fPts, foundT, &pt);
+ double testT = startT + (endT - startT) * foundT;
+ (*SegmentXYAtT[fVerb])(fPts, testT, &pt);
if (bestY < pt.fY && pt.fY < basePt.fY) {
bestY = pt.fY;
bestT = foundT < 1 ? start : end;
- hitT = fTs[start].fT + (fTs[end].fT - fTs[start].fT) * foundT;
+ hitT = testT;
}
} while (fTs[end].fT != 1);
return bestT;
@@ -1421,10 +1424,10 @@ public:
// start is the index of the beginning T of this edge
// it is guaranteed to have an end which describes a non-zero length (?)
// winding -1 means ccw, 1 means cw
- // firstFind allows coincident edges to be treated differently
- Segment* findNext(SkTDArray<Span*>& chase, bool firstFind, bool active,
- const int startIndex, const int endIndex, int& nextStart,
- int& nextEnd, int& winding, int& spanWinding) {
+ Segment* findNextWinding(SkTDArray<Span*>& chase, bool active,
+ int& nextStart, int& nextEnd, int& winding, int& spanWinding) {
+ const int startIndex = nextStart;
+ const int endIndex = nextEnd;
int outerWinding = winding;
int innerWinding = winding + spanWinding;
#if DEBUG_WINDING
@@ -1476,90 +1479,71 @@ public:
#endif
SkASSERT(sorted[firstIndex]->segment() == this);
#if DEBUG_WINDING
- SkDebugf("%s sign=%d\n", __FUNCTION__, sorted[firstIndex]->sign());
+ SkDebugf("%s [%d] sign=%d\n", __FUNCTION__, firstIndex, sorted[firstIndex]->sign());
#endif
int sumWinding = winding - spanSign(sorted[firstIndex]);
int nextIndex = firstIndex + 1;
int lastIndex = firstIndex != 0 ? firstIndex : angleCount;
const Angle* foundAngle = NULL;
+ // FIXME: found done logic probably fails if there are more than 4
+ // sorted angles. It should bias towards the first and last undone
+ // edges -- but not sure that it won't choose a middle (incorrect)
+ // edge if one is undone
bool foundDone = false;
+ bool foundDone2 = false;
// iterate through the angle, and compute everyone's winding
- int toggleWinding = SK_MinS32;
- bool flipFound = false;
- int flipped = 1;
+ bool altFlipped = false;
+ bool foundFlipped = false;
+ int foundMax = SK_MinS32;
+ int foundSum = SK_MinS32;
Segment* nextSegment;
+ int lastNonZeroSum = winding;
do {
if (nextIndex == angleCount) {
nextIndex = 0;
}
const Angle* nextAngle = sorted[nextIndex];
int maxWinding = sumWinding;
+ if (sumWinding) {
+ lastNonZeroSum = sumWinding;
+ }
nextSegment = nextAngle->segment();
sumWinding -= nextSegment->spanSign(nextAngle);
+ altFlipped ^= lastNonZeroSum * sumWinding < 0; // flip if different signs
SkASSERT(abs(sumWinding) <= gDebugMaxWindSum);
#if DEBUG_WINDING
- SkDebugf("%s maxWinding=%d sumWinding=%d sign=%d\n", __FUNCTION__,
- maxWinding, sumWinding, nextAngle->sign());
- #endif
- if (maxWinding * sumWinding < 0) {
- flipFound ^= true;
- #if DEBUG_WINDING
- SkDebugf("%s flipFound=%d maxWinding=%d sumWinding=%d\n",
- __FUNCTION__, flipFound, maxWinding, sumWinding);
+ SkDebugf("%s [%d] maxWinding=%d sumWinding=%d sign=%d altFlipped=%d\n", __FUNCTION__,
+ nextIndex, maxWinding, sumWinding, nextAngle->sign(), altFlipped);
#endif
- }
- if (!sumWinding) {
+ if (!sumWinding) {
if (!active) {
markDone(SkMin32(startIndex, endIndex), outerWinding);
// FIXME: seems like a bug that this isn't calling userInnerWinding
nextSegment->markWinding(SkMin32(nextAngle->start(),
nextAngle->end()), maxWinding);
#if DEBUG_WINDING
- SkDebugf("%s inactive\n", __FUNCTION__);
+ SkDebugf("%s [%d] inactive\n", __FUNCTION__, nextIndex);
#endif
return NULL;
}
if (!foundAngle || foundDone) {
foundAngle = nextAngle;
foundDone = nextSegment->done(*nextAngle);
- if (flipFound || (maxWinding * outerWinding < 0)) {
- flipped = -flipped;
- #if DEBUG_WINDING
- SkDebugf("%s flipped=%d flipFound=%d maxWinding=%d"
- " outerWinding=%d\n", __FUNCTION__, flipped,
- flipFound, maxWinding, outerWinding);
- #endif
- }
+ foundFlipped = altFlipped;
+ foundMax = maxWinding;
}
continue;
}
- if (!maxWinding && !foundAngle) {
+ if (!maxWinding && (!foundAngle || foundDone2)) {
#if DEBUG_WINDING
- if (flipped > 0) {
- SkDebugf("%s sumWinding=%d * outerWinding=%d < 0 (%s)\n",
- __FUNCTION__, sumWinding, outerWinding,
- sumWinding * outerWinding < 0 ? "true" : "false");
+ if (foundAngle && foundDone2) {
+ SkDebugf("%s [%d] !foundAngle && foundDone2\n", __FUNCTION__, nextIndex);
}
#endif
- if (sumWinding * outerWinding < 0 && flipped > 0) {
- #if DEBUG_WINDING
- SkDebugf("%s toggleWinding=%d\n", __FUNCTION__, sumWinding);
- #endif
- toggleWinding = sumWinding;
- } else if (outerWinding != sumWinding) {
- #if DEBUG_WINDING
- SkDebugf("%s outerWinding=%d != sumWinding=%d winding=%d\n",
- __FUNCTION__, outerWinding, sumWinding, winding);
- #endif
- winding = sumWinding;
- }
foundAngle = nextAngle;
- if (flipFound) {
- flipped = -flipped;
- #if DEBUG_WINDING
- SkDebugf("%s flipped flipFound=%d\n", __FUNCTION__, flipFound);
- #endif
- }
+ foundDone2 = nextSegment->done(*nextAngle);
+ foundFlipped = altFlipped;
+ foundSum = sumWinding;
}
if (nextSegment->done()) {
continue;
@@ -1583,7 +1567,6 @@ public:
}
}
} while (++nextIndex != lastIndex);
- SkASSERT(sorted[firstIndex]->segment() == this);
markDone(SkMin32(startIndex, endIndex), outerWinding);
if (!foundAngle) {
return NULL;
@@ -1591,17 +1574,109 @@ public:
nextStart = foundAngle->start();
nextEnd = foundAngle->end();
nextSegment = foundAngle->segment();
+ int flipped = foundFlipped ? -1 : 1;
spanWinding = SkSign32(spanWinding) * flipped * nextSegment->windValue(
SkMin32(nextStart, nextEnd));
- if (toggleWinding != SK_MinS32) {
- winding = toggleWinding;
- spanWinding = -spanWinding;
+ if (winding) {
+ #if DEBUG_WINDING
+ SkDebugf("%s ---6 winding=%d foundSum=", __FUNCTION__, winding);
+ if (foundSum == SK_MinS32) {
+ SkDebugf("?");
+ } else {
+ SkDebugf("%d", foundSum);
+ }
+ SkDebugf(" foundMax=");
+ if (foundMax == SK_MinS32) {
+ SkDebugf("?");
+ } else {
+ SkDebugf("%d", foundMax);
+ }
+ SkDebugf("\n");
+ #endif
+ winding = foundSum;
}
#if DEBUG_WINDING
- SkDebugf("%s spanWinding=%d\n", __FUNCTION__, spanWinding);
+ SkDebugf("%s spanWinding=%d flipped=%d\n", __FUNCTION__, spanWinding, flipped);
#endif
return nextSegment;
}
+
+ Segment* findNextXor(int& nextStart, int& nextEnd) {
+ const int startIndex = nextStart;
+ const int endIndex = nextEnd;
+ SkASSERT(startIndex != endIndex);
+ int count = fTs.count();
+ SkASSERT(startIndex < endIndex ? startIndex < count - 1
+ : startIndex > 0);
+ int step = SkSign32(endIndex - startIndex);
+ int end = nextSpan(startIndex, step);
+ SkASSERT(end >= 0);
+ Span* endSpan = &fTs[end];
+ Segment* other;
+ markDone(SkMin32(startIndex, endIndex), 1);
+ if (isSimple(end)) {
+ #if DEBUG_WINDING
+ SkDebugf("%s simple\n", __FUNCTION__);
+ #endif
+ other = endSpan->fOther;
+ nextStart = endSpan->fOtherIndex;
+ double startT = other->fTs[nextStart].fT;
+ SkDEBUGCODE(bool firstLoop = true;)
+ if ((startT < FLT_EPSILON && step < 0)
+ || (startT > 1 - FLT_EPSILON && step > 0)) {
+ step = -step;
+ SkDEBUGCODE(firstLoop = false;)
+ }
+ do {
+ nextEnd = nextStart;
+ do {
+ nextEnd += step;
+ } while (fabs(startT - other->fTs[nextEnd].fT) < FLT_EPSILON);
+ if (other->fTs[SkMin32(nextStart, nextEnd)].fWindValue) {
+ break;
+ }
+ SkASSERT(firstLoop);
+ SkDEBUGCODE(firstLoop = false;)
+ step = -step;
+ } while (true);
+ SkASSERT(step < 0 ? nextEnd >= 0 : nextEnd < other->fTs.count());
+ return other;
+ }
+ SkTDArray<Angle> angles;
+ SkASSERT(startIndex - endIndex != 0);
+ SkASSERT((startIndex - endIndex < 0) ^ (step < 0));
+ addTwoAngles(startIndex, end, angles);
+ buildAngles(end, angles);
+ SkTDArray<Angle*> sorted;
+ sortAngles(angles, sorted);
+ int angleCount = angles.count();
+ int firstIndex = findStartingEdge(sorted, startIndex, end);
+ SkASSERT(firstIndex >= 0);
+ #if DEBUG_SORT
+ debugShowSort(sorted, firstIndex, 0);
+ #endif
+ SkASSERT(sorted[firstIndex]->segment() == this);
+ int nextIndex = firstIndex + 1;
+ int lastIndex = firstIndex != 0 ? firstIndex : angleCount;
+ const Angle* nextAngle;
+ Segment* nextSegment;
+ do {
+ if (nextIndex == angleCount) {
+ nextIndex = 0;
+ }
+ nextAngle = sorted[nextIndex];
+ nextSegment = nextAngle->segment();
+ if (!nextSegment->done(*nextAngle)) {
+ break;
+ }
+ if (++nextIndex == lastIndex) {
+ return NULL;
+ }
+ } while (true);
+ nextStart = nextAngle->start();
+ nextEnd = nextAngle->end();
+ return nextSegment;
+ }
int findStartingEdge(SkTDArray<Angle*>& sorted, int start, int end) {
int angleCount = sorted.count();
@@ -1947,70 +2022,51 @@ public:
// always called to mark segments done).
void markDone(int index, int winding) {
// SkASSERT(!done());
+ SkASSERT(winding);
double referenceT = fTs[index].fT;
int lesser = index;
while (--lesser >= 0 && referenceT - fTs[lesser].fT < FLT_EPSILON) {
- Span& span = fTs[lesser];
- if (span.fDone) {
- continue;
- }
- #if DEBUG_MARK_DONE
- debugShowNewWinding(__FUNCTION__, span, winding);
- #endif
- span.fDone = true;
- SkASSERT(span.fWindSum == SK_MinS32 || span.fWindSum == winding);
- SkASSERT(abs(winding) <= gDebugMaxWindSum);
- span.fWindSum = winding;
- fDoneSpans++;
+ markOneDone(__FUNCTION__, lesser, winding);
}
do {
- Span& span = fTs[index];
- // SkASSERT(!span.fDone);
- if (span.fDone) {
- continue;
- }
- #if DEBUG_MARK_DONE
- debugShowNewWinding(__FUNCTION__, span, winding);
- #endif
- span.fDone = true;
- SkASSERT(span.fWindSum == SK_MinS32 || span.fWindSum == winding);
- SkASSERT(abs(winding) <= gDebugMaxWindSum);
- span.fWindSum = winding;
- fDoneSpans++;
+ markOneDone(__FUNCTION__, index, winding);
} while (++index < fTs.count() && fTs[index].fT - referenceT < FLT_EPSILON);
}
+
+ void markOneDone(const char* funName, int tIndex, int winding) {
+ Span* span = markOneWinding(funName, tIndex, winding);
+ if (!span) {
+ return;
+ }
+ span->fDone = true;
+ fDoneSpans++;
+ }
+
+ Span* markOneWinding(const char* funName, int tIndex, int winding) {
+ Span& span = fTs[tIndex];
+ if (span.fDone) {
+ return NULL;
+ }
+ #if DEBUG_MARK_DONE
+ debugShowNewWinding(funName, span, winding);
+ #endif
+ SkASSERT(span.fWindSum == SK_MinS32 || span.fWindSum == winding);
+ SkASSERT(abs(winding) <= gDebugMaxWindSum);
+ span.fWindSum = winding;
+ return &span;
+ }
void markWinding(int index, int winding) {
// SkASSERT(!done());
+ SkASSERT(winding);
double referenceT = fTs[index].fT;
int lesser = index;
while (--lesser >= 0 && referenceT - fTs[lesser].fT < FLT_EPSILON) {
- Span& span = fTs[lesser];
- if (span.fDone) {
- continue;
- }
- // SkASSERT(span.fWindValue == 1 || winding == 0);
- #if DEBUG_MARK_DONE
- debugShowNewWinding(__FUNCTION__, span, winding);
- #endif
- SkASSERT(span.fWindSum == SK_MinS32 || span.fWindSum == winding);
- SkASSERT(abs(winding) <= gDebugMaxWindSum);
- span.fWindSum = winding;
+ markOneWinding(__FUNCTION__, lesser, winding);
}
do {
- Span& span = fTs[index];
- // SkASSERT(!span.fDone || span.fCoincident);
- if (span.fDone) {
- continue;
- }
- // SkASSERT(span.fWindValue == 1 || winding == 0);
- SkASSERT(span.fWindSum == SK_MinS32 || span.fWindSum == winding);
- #if DEBUG_MARK_DONE
- debugShowNewWinding(__FUNCTION__, span, winding);
- #endif
- SkASSERT(abs(winding) <= gDebugMaxWindSum);
- span.fWindSum = winding;
- } while (++index < fTs.count() && fTs[index].fT - referenceT < FLT_EPSILON);
+ markOneWinding(__FUNCTION__, index, winding);
+ } while (++index < fTs.count() && fTs[index].fT - referenceT < FLT_EPSILON);
}
void matchWindingValue(int tIndex, double t, bool borrowWind) {
@@ -2104,7 +2160,7 @@ public:
double t(int tIndex) const {
return fTs[tIndex].fT;
}
-
+
static void TrackOutside(SkTDArray<double>& outsideTs, double end,
double start) {
int outCount = outsideTs.count();
@@ -2113,6 +2169,23 @@ public:
*outsideTs.append() = start;
}
}
+
+ void undoneSpan(int& start, int& end) {
+ size_t tCount = fTs.count();
+ size_t index;
+ for (index = 0; index < tCount; ++index) {
+ if (!fTs[index].fDone) {
+ break;
+ }
+ }
+ SkASSERT(index < tCount - 1);
+ start = index;
+ double startT = fTs[index].fT;
+ while (fTs[++index].fT - startT < FLT_EPSILON)
+ SkASSERT(index < tCount);
+ SkASSERT(index < tCount);
+ end = index;
+ }
void updatePts(const SkPoint pts[]) {
fPts = pts;
@@ -2210,9 +2283,27 @@ public:
}
#endif
+#if DEBUG_WINDING
+ void debugShowSums() const {
+ SkDebugf("%s id=%d (%1.9g,%1.9g %1.9g,%1.9g)", __FUNCTION__, fID,
+ fPts[0].fX, fPts[0].fY, fPts[fVerb].fX, fPts[fVerb].fY);
+ for (int i = 0; i < fTs.count(); ++i) {
+ const Span& span = fTs[i];
+ SkDebugf(" [t=%1.3g %1.9g,%1.9g w=", span.fT, xAtT(&span), yAtT(&span));
+ if (span.fWindSum == SK_MinS32) {
+ SkDebugf("?");
+ } else {
+ SkDebugf("%d", span.fWindSum);
+ }
+ SkDebugf("]");
+ }
+ SkDebugf("\n");
+ }
+#endif
+
#if DEBUG_CONCIDENT
void debugShowTs() const {
- SkDebugf("%s %d", __FUNCTION__, fID);
+ 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);
@@ -2277,7 +2368,7 @@ public:
SkASSERT(angles.count() > 1);
int lastSum = contourWinding;
int windSum = lastSum - spanSign(angles[first]);
- SkDebugf("%s contourWinding=%d bump=%d\n", __FUNCTION__,
+ SkDebugf("%s contourWinding=%d sign=%d\n", __FUNCTION__,
contourWinding, spanSign(angles[first]));
int index = first;
bool firstTime = true;
@@ -2332,7 +2423,7 @@ private:
SkPath::Verb fVerb;
Bounds fBounds;
SkTDArray<Span> fTs; // two or more (always includes t=0 t=1)
- int fDoneSpans; // used for quick check that segment is finished
+ int fDoneSpans; // quick check that segment is finished
#if DEBUG_DUMP
int fID;
#endif
@@ -2491,7 +2582,7 @@ public:
fContainsCurves = fContainsIntercepts = false;
}
- void resolveCoincidence(int winding) {
+ void resolveCoincidence(int xorMask) {
int count = fCoincidences.count();
for (int index = 0; index < count; ++index) {
Coincidence& coincidence = fCoincidences[index];
@@ -2517,7 +2608,7 @@ public:
SkTSwap<double>(oStartT, oEndT);
}
SkASSERT(oEndT - oStartT >= FLT_EPSILON);
- if (winding > 0 || thisOne.cancels(other)) {
+ if (thisOne.cancels(other)) {
// make sure startT and endT have t entries
if (startT > 0 || oEndT < 1
|| thisOne.isMissing(startT) || other.isMissing(oEndT)) {
@@ -2537,7 +2628,7 @@ public:
|| thisOne.isMissing(endT) || other.isMissing(oEndT)) {
other.addTPair(oEndT, thisOne, endT, true);
}
- thisOne.addTCoincident(startT, endT, other, oStartT, oEndT);
+ thisOne.addTCoincident(xorMask, startT, endT, other, oStartT, oEndT);
}
#if DEBUG_CONCIDENT
thisOne.debugShowTs();
@@ -2590,6 +2681,19 @@ public:
return bestSegment;
}
+ Segment* undoneSegment(int& start, int& end) {
+ int segmentCount = fSegments.count();
+ for (int test = 0; test < segmentCount; ++test) {
+ Segment* testSegment = &fSegments[test];
+ if (testSegment->done()) {
+ continue;
+ }
+ testSegment->undoneSpan(start, end);
+ return testSegment;
+ }
+ return NULL;
+ }
+
int updateSegment(int index, const SkPoint* pts) {
Segment& segment = fSegments[index];
segment.updatePts(pts);
@@ -3170,15 +3274,15 @@ 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, int winding) {
+static void coincidenceCheck(SkTDArray<Contour*>& contourList, int xorMask) {
int contourCount = contourList.count();
for (int cIndex = 0; cIndex < contourCount; ++cIndex) {
Contour* contour = contourList[cIndex];
- contour->findTooCloseToCall(winding);
+ contour->findTooCloseToCall(xorMask);
}
for (int cIndex = 0; cIndex < contourCount; ++cIndex) {
Contour* contour = contourList[cIndex];
- contour->resolveCoincidence(winding);
+ contour->resolveCoincidence(xorMask);
}
}
@@ -3242,7 +3346,7 @@ static int innerContourCheck(SkTDArray<Contour*>& contourList,
SkASSERT(angles.count() > 0);
if (angles[0].segment()->yAtT(angles[0].start()) >= basePt.fY) {
#if DEBUG_SORT
- SkDebugf("%s *** early return\n", __FUNCTION__);
+ SkDebugf("%s early return\n", __FUNCTION__);
#endif
return 0;
}
@@ -3370,6 +3474,21 @@ static Segment* findTopContour(SkTDArray<Contour*>& contourList) {
return topStart;
}
+static Segment* findUndone(SkTDArray<Contour*>& contourList, int& start, int& end) {
+ int contourCount = contourList.count();
+ Segment* result;
+ for (int cIndex = 0; cIndex < contourCount; ++cIndex) {
+ Contour* contour = contourList[cIndex];
+ result = contour->undoneSegment(start, end);
+ if (result) {
+ return result;
+ }
+ }
+ return NULL;
+}
+
+
+
static Segment* findChase(SkTDArray<Span*>& chase, int& tIndex, int& endIndex,
int contourWinding) {
while (chase.count()) {
@@ -3479,7 +3598,7 @@ static bool windingIsActive(int winding, int spanWinding) {
// is an option, choose first edge that continues the inside.
// since we start with leftmost top edge, we'll traverse through a
// smaller angle counterclockwise to get to the next edge.
-static void bridge(SkTDArray<Contour*>& contourList, SkPath& simple) {
+static void bridgeWinding(SkTDArray<Contour*>& contourList, SkPath& simple) {
bool firstContour = true;
do {
Segment* topStart = findTopContour(contourList);
@@ -3511,7 +3630,7 @@ static void bridge(SkTDArray<Contour*>& contourList, SkPath& simple) {
contourWinding -= spanWinding;
}
#if DEBUG_WINDING
- SkDebugf("%s --- sumWinding=%d spanWinding=%d sign=%d inner=%d result=%d\n", __FUNCTION__,
+ SkDebugf("%s sumWinding=%d spanWinding=%d sign=%d inner=%d result=%d\n", __FUNCTION__,
sumWinding, spanWinding, SkSign32(index - endIndex),
inner, contourWinding);
#endif
@@ -3522,7 +3641,6 @@ static void bridge(SkTDArray<Contour*>& contourList, SkPath& simple) {
#endif
}
SkPoint lastPt;
- bool firstTime = true;
int winding = contourWinding;
int spanWinding = current->spanSign(index, endIndex);
// FIXME: needs work. While it works in limited situations, it does
@@ -3542,9 +3660,9 @@ static void bridge(SkTDArray<Contour*>& contourList, SkPath& simple) {
const SkPoint* firstPt = NULL;
do {
SkASSERT(!current->done());
- int nextStart, nextEnd;
- Segment* next = current->findNext(chaseArray,
- firstTime, active, index, endIndex,
+ int nextStart = index;
+ int nextEnd = endIndex;
+ Segment* next = current->findNextWinding(chaseArray, active,
nextStart, nextEnd, winding, spanWinding);
if (!next) {
break;
@@ -3556,7 +3674,6 @@ static void bridge(SkTDArray<Contour*>& contourList, SkPath& simple) {
current = next;
index = nextStart;
endIndex = nextEnd;
- firstTime = false;
} while (*firstPt != lastPt && (active || !current->done()));
if (firstPt && active) {
#if DEBUG_PATH_CONSTRUCTION
@@ -3576,7 +3693,7 @@ static void bridge(SkTDArray<Contour*>& contourList, SkPath& simple) {
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"
+ 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),
@@ -3591,6 +3708,37 @@ static void bridge(SkTDArray<Contour*>& contourList, SkPath& simple) {
} while (true);
}
+static void bridgeXor(SkTDArray<Contour*>& contourList, SkPath& simple) {
+ Segment* current;
+ int start, end;
+ while ((current = findUndone(contourList, start, end))) {
+ const SkPoint* firstPt = NULL;
+ SkPoint lastPt;
+ do {
+ SkASSERT(!current->done());
+ int nextStart = start;
+ int nextEnd = end;
+ Segment* next = current->findNextXor(nextStart, nextEnd);
+ if (!next) {
+ break;
+ }
+ if (!firstPt) {
+ firstPt = &current->addMoveTo(start, simple, true);
+ }
+ lastPt = current->addCurveTo(start, end, simple, true);
+ current = next;
+ start = nextStart;
+ end = nextEnd;
+ } while (*firstPt != lastPt);
+ if (firstPt) {
+ #if DEBUG_PATH_CONSTRUCTION
+ SkDebugf("%s close\n", __FUNCTION__);
+ #endif
+ simple.close();
+ }
+ }
+}
+
static void fixOtherTIndex(SkTDArray<Contour*>& contourList) {
int contourCount = contourList.count();
for (int cTest = 0; cTest < contourCount; ++cTest) {
@@ -3613,7 +3761,7 @@ static void makeContourList(SkTArray<Contour>& contours,
void simplifyx(const SkPath& path, SkPath& simple) {
// returns 1 for evenodd, -1 for winding, regardless of inverse-ness
- int winding = (path.getFillType() & 1) ? 1 : -1;
+ int xorMask = (path.getFillType() & 1) ? 1 : -1;
simple.reset();
simple.setFillType(SkPath::kEvenOdd_FillType);
@@ -3638,9 +3786,13 @@ void simplifyx(const SkPath& path, SkPath& simple) {
} while (addIntersectTs(current, next) && nextPtr != listEnd);
} while (currentPtr != listEnd);
// eat through coincident edges
- coincidenceCheck(contourList, winding);
+ coincidenceCheck(contourList, xorMask);
fixOtherTIndex(contourList);
// construct closed contours
- bridge(contourList, simple);
+ if (xorMask < 0) {
+ bridgeWinding(contourList, simple);
+ } else {
+ bridgeXor(contourList, simple);
+ }
}
diff --git a/experimental/Intersection/SimplifyFindNext_Test.cpp b/experimental/Intersection/SimplifyFindNext_Test.cpp
index 5fc6305294..7d33c11a6b 100644
--- a/experimental/Intersection/SimplifyFindNext_Test.cpp
+++ b/experimental/Intersection/SimplifyFindNext_Test.cpp
@@ -32,11 +32,11 @@ static const SimplifyFindNextTest::Segment* testCommon(
SimplifyFindNextTest::Segment& segment = contours[0].debugSegments()[0];
SkPoint pts[2];
pts[0] = segment.xyAtT(&segment.span(endIndex));
- int nextStart, nextEnd;
+ int nextStart = startIndex;
+ int nextEnd = endIndex;
SkTDArray<SimplifyFindNextTest::Span*> chaseArray;
- SimplifyFindNextTest::Segment* next = segment.findNext(chaseArray,
- true, true, startIndex, endIndex, nextStart, nextEnd,
- contourWinding, spanWinding);
+ SimplifyFindNextTest::Segment* next = segment.findNextWinding(chaseArray,
+ true, nextStart, nextEnd, contourWinding, spanWinding);
pts[1] = next->xyAtT(&next->span(nextStart));
SkASSERT(pts[0] == pts[1]);
return next;
diff --git a/experimental/Intersection/SimplifyNew_Test.cpp b/experimental/Intersection/SimplifyNew_Test.cpp
index 3d21908caa..b70865274a 100644
--- a/experimental/Intersection/SimplifyNew_Test.cpp
+++ b/experimental/Intersection/SimplifyNew_Test.cpp
@@ -961,13 +961,234 @@ static void testQuadralateral6() {
testSimplifyx(path);
}
-static void (*firstTest)() = 0;
+static void testFauxQuadralateral6() {
+ SkPath path;
+ path.moveTo(0, 0);
+ path.lineTo(1, 0);
+ path.lineTo(1, 1);
+ path.close();
+ path.moveTo(1, 0);
+ path.lineTo(2, 0);
+ path.lineTo(1 + 1.0f/3, 2.0f/3);
+ path.close();
+ path.moveTo(1 + 1.0f/3, 2.0f/3);
+ path.lineTo(0, 2);
+ path.lineTo(2, 2);
+ path.close();
+ testSimplifyx(path);
+}
+
+static void testFauxQuadralateral6a() {
+ SkPath path;
+ path.moveTo(0, 0);
+ path.lineTo(3, 0);
+ path.lineTo(3, 3);
+ path.close();
+ path.moveTo(3, 0);
+ path.lineTo(6, 0);
+ path.lineTo(4, 2);
+ path.close();
+ path.moveTo(4, 2);
+ path.lineTo(0, 6);
+ path.lineTo(6, 6);
+ path.close();
+ testSimplifyx(path);
+}
+
+static void testFauxQuadralateral6b() {
+ SkPath path;
+ path.moveTo(0, 0);
+ path.lineTo(3, 0);
+ path.lineTo(3, 3);
+ path.close();
+ path.moveTo(3, 0);
+ path.lineTo(6, 0);
+ path.lineTo(4, 2);
+ path.close();
+ path.moveTo(4, 2);
+ path.lineTo(6, 6);
+ path.lineTo(0, 6);
+ path.close();
+ testSimplifyx(path);
+}
+
+static void testFauxQuadralateral6c() {
+ SkPath path;
+ path.moveTo(0, 0);
+ path.lineTo(3, 3);
+ path.lineTo(3, 0);
+ path.close();
+ path.moveTo(3, 0);
+ path.lineTo(6, 0);
+ path.lineTo(4, 2);
+ path.close();
+ path.moveTo(4, 2);
+ path.lineTo(0, 6);
+ path.lineTo(6, 6);
+ path.close();
+ testSimplifyx(path);
+}
+
+static void testFauxQuadralateral6d() {
+ SkPath path;
+ path.moveTo(0, 0);
+ path.lineTo(3, 3);
+ path.lineTo(3, 0);
+ path.close();
+ path.moveTo(3, 0);
+ path.lineTo(6, 0);
+ path.lineTo(4, 2);
+ path.close();
+ path.moveTo(4, 2);
+ path.lineTo(6, 6);
+ path.lineTo(0, 6);
+ path.close();
+ testSimplifyx(path);
+}
+
+static void testQuadralateral6a() {
+ SkPath path;
+ path.moveTo(0, 0);
+ path.lineTo(0, 0);
+ path.lineTo(3, 0);
+ path.lineTo(3, 3);
+ path.close();
+ path.moveTo(3, 0);
+ path.lineTo(6, 0);
+ path.lineTo(0, 6);
+ path.lineTo(6, 6);
+ path.close();
+ testSimplifyx(path);
+}
+
+static void testQuadralateral7() {
+ SkPath path;
+ path.moveTo(0, 0);
+ path.lineTo(0, 0);
+ path.lineTo(1, 0);
+ path.lineTo(2, 1);
+ path.close();
+ path.moveTo(1, 0);
+ path.lineTo(1, 1);
+ path.lineTo(2, 2);
+ path.lineTo(1, 3);
+ path.close();
+ testSimplifyx(path);
+}
+
+static void testQuadralateral8() {
+ SkPath path;
+ path.moveTo(0, 0);
+ path.lineTo(3, 1);
+ path.lineTo(1, 3);
+ path.lineTo(3, 3);
+ path.close();
+ path.moveTo(2, 1);
+ path.lineTo(0, 2);
+ path.lineTo(3, 2);
+ path.lineTo(2, 3);
+ path.close();
+ testSimplifyx(path);
+}
+
+static void testQuadralateral9() {
+ SkPath path;
+ path.moveTo(0, 0);
+ path.lineTo(1, 0);
+ path.lineTo(1, 2);
+ path.lineTo(2, 2);
+ path.close();
+ path.moveTo(1, 1);
+ path.lineTo(2, 1);
+ path.lineTo(1, 3);
+ path.lineTo(2, 3);
+ path.close();
+ testSimplifyx(path);
+}
+
+static void testLine1x() {
+ SkPath path;
+ path.setFillType(SkPath::kEvenOdd_FillType);
+ path.addRect(0, 0, 12, 12, (SkPath::Direction) 0);
+ path.addRect(4, 0, 13, 13, (SkPath::Direction) 0);
+ testSimplifyx(path);
+}
+
+static void testLine2x() {
+ SkPath path;
+ path.setFillType(SkPath::kEvenOdd_FillType);
+ path.addRect(0, 20, 20, 20, (SkPath::Direction) 0);
+ path.addRect(0, 20, 12, 30, (SkPath::Direction) 0);
+ path.addRect(12, 0, 21, 21, (SkPath::Direction) 1);
+ testSimplifyx(path);
+}
+
+static void testLine3x() {
+ SkPath path;
+ path.setFillType(SkPath::kEvenOdd_FillType);
+ path.addRect(10, 30, 30, 30, (SkPath::Direction) 0);
+ path.addRect(18, 20, 30, 30, (SkPath::Direction) 1);
+ path.addRect(0, 32, 9, 36, (SkPath::Direction) 1);
+ testSimplifyx(path);
+}
+
+static void testLine4x() {
+ SkPath path;
+ path.setFillType(SkPath::kEvenOdd_FillType);
+ path.addRect(10, 30, 30, 30, (SkPath::Direction) 0);
+ path.addRect(24, 20, 36, 30, (SkPath::Direction) 1);
+ path.addRect(0, 32, 9, 36, (SkPath::Direction) 1);
+ testSimplifyx(path);
+}
+
+static void testQuadratic1() {
+ SkPath path;
+ path.moveTo(0, 0);
+ path.quadTo(0, 0, 0, 0);
+ path.lineTo(1, 0);
+ path.close();
+ path.moveTo(0, 0);
+ path.lineTo(0, 0);
+ path.quadTo(0, 0, 0, 0);
+ path.close();
+ testSimplifyx(path);
+}
+
+static void testQuadratic2() {
+ SkPath path;
+ path.moveTo(0, 0);
+ path.quadTo(0, 0, 0, 0);
+ path.lineTo(3, 0);
+ path.close();
+ path.moveTo(0, 0);
+ path.lineTo(0, 0);
+ path.quadTo(1, 0, 0, 1);
+ path.close();
+ testSimplifyx(path);
+}
+
+static void (*firstTest)() = testQuadratic2;
static struct {
void (*fun)();
const char* str;
} tests[] = {
+ TEST(testQuadratic2),
+ TEST(testQuadratic1),
+ TEST(testLine4x),
+ TEST(testLine3x),
+ TEST(testLine2x),
+ TEST(testLine1x),
+ TEST(testQuadralateral9),
+ TEST(testQuadralateral8),
+ TEST(testQuadralateral7),
TEST(testQuadralateral6),
+ TEST(testQuadralateral6a),
+ TEST(testFauxQuadralateral6d),
+ TEST(testFauxQuadralateral6c),
+ TEST(testFauxQuadralateral6b),
+ TEST(testFauxQuadralateral6a),
+ TEST(testFauxQuadralateral6),
TEST(testQuadralateral5),
TEST(testNondegenerate4),
TEST(testNondegenerate3),
@@ -1076,14 +1297,13 @@ static struct {
void (*fun)();
const char* str;
} subTests[] = {
- TEST(testLine68h),
- TEST(testLine68g),
- TEST(testLine68f),
- TEST(testLine68e),
- TEST(testLine68d),
- TEST(testLine68c),
- TEST(testLine68b),
- TEST(testLine68a),
+ TEST(testQuadralateral6),
+ TEST(testQuadralateral6a),
+ TEST(testFauxQuadralateral6d),
+ TEST(testFauxQuadralateral6c),
+ TEST(testFauxQuadralateral6b),
+ TEST(testFauxQuadralateral6a),
+ TEST(testFauxQuadralateral6),
};
static const size_t subTestCount = sizeof(subTests) / sizeof(subTests[0]);
@@ -1112,6 +1332,7 @@ void SimplifyNew_Test() {
while (index > 0 && tests[index].fun != firstTest) {
--index;
}
+ SkDebugf(" %s [%s]\n", __FUNCTION__, tests[index].str);
(*tests[index].fun)();
}
index = testCount - 1;
diff --git a/experimental/Intersection/SimplifyRect4x4_Test.cpp b/experimental/Intersection/SimplifyRect4x4_Test.cpp
index 6782d537ce..3768da988d 100644
--- a/experimental/Intersection/SimplifyRect4x4_Test.cpp
+++ b/experimental/Intersection/SimplifyRect4x4_Test.cpp
@@ -155,8 +155,11 @@ static void* testSimplify4x4RectsMain(void* data)
dYAlign = 5;
}
path.close();
- outputProgress(state, pathStr);
- testSimplifyx(path, out, state, pathStr);
+ outputProgress(state, pathStr, SkPath::kWinding_FillType);
+ testSimplifyx(path, false, out, state, pathStr);
+ state.testsRun++;
+ outputProgress(state, pathStr, SkPath::kEvenOdd_FillType);
+ testSimplifyx(path, true, out, state, pathStr);
state.testsRun++;
}
}
@@ -170,7 +173,7 @@ static void* testSimplify4x4RectsMain(void* data)
return NULL;
}
-void Simplify4x4RectsThreaded_Test()
+void Simplify4x4RectsThreaded_Test(int& testsRun)
{
SkDebugf("%s\n", __FUNCTION__);
#ifdef SK_DEBUG
@@ -179,7 +182,7 @@ void Simplify4x4RectsThreaded_Test()
#endif
const char testLineStr[] = "testLine";
initializeTests(testLineStr, sizeof(testLineStr));
- int testsRun = 0;
+ int testsStart = testsRun;
for (int a = 0; a < 8; ++a) { // outermost
for (int b = a ; b < 8; ++b) {
for (int c = b ; c < 8; ++c) {
@@ -193,6 +196,6 @@ void Simplify4x4RectsThreaded_Test()
if (!gRunTestsInOneThread) SkDebugf("\n%d", a);
}
testsRun += waitForCompletion();
- SkDebugf("%s total tests run=%d\n", __FUNCTION__, testsRun);
+ SkDebugf("%s tests=%d total=%d\n", __FUNCTION__, testsRun - testsStart, testsRun);
}
diff --git a/experimental/Intersection/op.htm b/experimental/Intersection/op.htm
index ce40130fd5..b844053365 100644
--- a/experimental/Intersection/op.htm
+++ b/experimental/Intersection/op.htm
@@ -862,11 +862,200 @@ path.close();
path.close();
</div>
+<div id="testFauxQuadralateral6">
+ path.moveTo(0, 0);
+ path.lineTo(1, 0);
+ path.lineTo(1, 1);
+ path.close();
+ path.moveTo(1, 0);
+ path.lineTo(2, 0);
+ path.lineTo(1.333, 0.667);
+ path.close();
+ path.moveTo(1.333, 0.667);
+ path.lineTo(0, 2);
+ path.lineTo(2, 2);
+ path.close();
+</div>
+
+<div id="testFauxQuadralateral6a">
+ path.moveTo(0, 0);
+ path.lineTo(3, 0);
+ path.lineTo(3, 3);
+ path.close();
+ path.moveTo(3, 0);
+ path.lineTo(6, 0);
+ path.lineTo(4, 2);
+ path.close();
+ path.moveTo(4, 2);
+ path.lineTo(0, 6);
+ path.lineTo(6, 6);
+ path.close();
+</div>
+
+<div id="testFauxQuadralateral6b">
+ path.moveTo(0, 0);
+ path.lineTo(3, 0);
+ path.lineTo(3, 3);
+ path.close();
+ path.moveTo(3, 0);
+ path.lineTo(6, 0);
+ path.lineTo(4, 2);
+ path.close();
+ path.moveTo(4, 2);
+ path.lineTo(6, 6);
+ path.lineTo(0, 6);
+ path.close();
+</div>
+
+<div id="testFauxQuadralateral6c">
+ path.moveTo(0, 0);
+ path.lineTo(3, 3);
+ path.lineTo(3, 0);
+ path.close();
+ path.moveTo(3, 0);
+ path.lineTo(6, 0);
+ path.lineTo(4, 2);
+ path.close();
+ path.moveTo(4, 2);
+ path.lineTo(0, 6);
+ path.lineTo(6, 6);
+ path.close();
+</div>
+
+<div id="testFauxQuadralateral6d">
+ path.moveTo(0, 0);
+ path.lineTo(3, 3);
+ path.lineTo(3, 0);
+ path.close();
+ path.moveTo(3, 0);
+ path.lineTo(6, 0);
+ path.lineTo(4, 2);
+ path.close();
+ path.moveTo(4, 2);
+ path.lineTo(6, 6);
+ path.lineTo(0, 6);
+</div>
+
+<div id="testQuadralateral6a">
+ path.moveTo(0, 0);
+ path.lineTo(0, 0);
+ path.lineTo(3, 0);
+ path.lineTo(3, 3);
+ path.close();
+ path.moveTo(3, 0);
+ path.lineTo(6, 0);
+ path.lineTo(0, 6);
+ path.lineTo(6, 6);
+</div>
+
+<div id="testQuadralateral7">
+ path.moveTo(0, 0);
+ path.lineTo(0, 0);
+ path.lineTo(1, 0);
+ path.lineTo(2, 1);
+ path.close();
+ path.moveTo(1, 0);
+ path.lineTo(1, 1);
+ path.lineTo(2, 2);
+ path.lineTo(1, 3);
+ path.close();
+</div>
+
+<div id="testQuadralateral8">
+ path.moveTo(0, 0);
+ path.lineTo(3, 1);
+ path.lineTo(1, 3);
+ path.lineTo(3, 3);
+ path.close();
+ path.moveTo(2, 1);
+ path.lineTo(0, 2);
+ path.lineTo(3, 2);
+ path.lineTo(2, 3);
+ path.close();
+</div>
+
+<div id="testQuadralateral9">
+ path.moveTo(0, 0);
+ path.lineTo(1, 0);
+ path.lineTo(1, 2);
+ path.lineTo(2, 2);
+ path.close();
+ path.moveTo(1, 1);
+ path.lineTo(2, 1);
+ path.lineTo(1, 3);
+ path.lineTo(2, 3);
+ path.close();
+</div>
+
+<div id="testLine1x">
+ path.setFillType(SkPath::kEvenOdd_FillType);
+ path.addRect(0, 0, 12, 12, (SkPath::Direction) 0);
+ path.addRect(4, 0, 13, 13, (SkPath::Direction) 0);
+</div>
+
+<div id="testLine2x">
+ path.setFillType(SkPath::kEvenOdd_FillType);
+ path.addRect(0, 20, 20, 20, (SkPath::Direction) 0);
+ path.addRect(0, 20, 12, 30, (SkPath::Direction) 0);
+ path.addRect(12, 0, 21, 21, (SkPath::Direction) 1);
+</div>
+
+<div id="testLine3x">
+ path.setFillType(SkPath::kEvenOdd_FillType);
+ path.addRect(10, 30, 30, 30, (SkPath::Direction) 0);
+ path.addRect(18, 20, 30, 30, (SkPath::Direction) 1);
+ path.addRect(0, 32, 9, 36, (SkPath::Direction) 1);
+</div>
+
+<div id="testLine4x">
+ path.setFillType(SkPath::kEvenOdd_FillType);
+ path.addRect(10, 30, 30, 30, (SkPath::Direction) 0);
+ path.addRect(24, 20, 36, 30, (SkPath::Direction) 1);
+ path.addRect(0, 32, 9, 36, (SkPath::Direction) 1);
+</div>
+
+<div id="testQuadratic1">
+ path.moveTo(0, 0);
+ path.quadTo(0, 0, 0, 0);
+ path.lineTo(1, 0);
+ path.close();
+ path.moveTo(0, 0);
+ path.lineTo(0, 0);
+ path.quadTo(0, 0, 0, 0);
+ path.close();
+</div>
+
+<div id="testQuadratic2">
+ path.moveTo(0, 0);
+ path.quadTo(0, 0, 0, 0);
+ path.lineTo(3, 0);
+ path.close();
+ path.moveTo(0, 0);
+ path.lineTo(0, 0);
+ path.quadTo(1, 0, 0, 1);
+ path.close();
+</div>
+
</div>
<script type="text/javascript">
var testDivs = [
+ testQuadratic2,
+ testQuadratic1,
+ testLine4x,
+ testLine3x,
+ testLine2x,
+ testLine1x,
+ testQuadralateral9,
+ testQuadralateral8,
+ testQuadralateral7,
+ testFauxQuadralateral6d,
+ testFauxQuadralateral6c,
+ testFauxQuadralateral6b,
+ testFauxQuadralateral6a,
+ testFauxQuadralateral6,
+ testQuadralateral6a,
testQuadralateral6,
testQuadralateral5,
testNondegenerate4,
@@ -976,6 +1165,7 @@ var decimal_places = 0; // make this 3 to show more precision
var tests = [];
var testTitles = [];
var testIndex = 0;
+var hasXor = false;
var ctx;
@@ -983,6 +1173,7 @@ function parse(test, title) {
var contours = [];
var contourStrs = test.split("path.close();");
var pattern = /-?\d+\.*\d*/g;
+ hasXor = test.split("kEvenOdd_FillType").length > 1;
for (var c in contourStrs) {
var contour = contourStrs[c];
var verbStrs = contour.split("path");
@@ -1022,6 +1213,7 @@ function parseRect(test, title) {
var contours = [];
var rectStrs = test.split("path.addRect");
var pattern = /-?\d+\.*\d*/g;
+ hasXor = test.split("kEvenOdd_FillType").length > 1;
for (var r in rectStrs) {
var rect = rectStrs[r];
var sideStrs = rect.match(pattern);
@@ -1176,6 +1368,9 @@ function draw(test, title, _at_x, _at_y, scale) {
}
ctx.closePath();
}
+ if (hasXor) {
+ ctx.fillType=xor; // how is this done?
+ }
ctx.stroke();
ctx.fillStyle="rgba(192,192,255, 0.3)";
ctx.fill();
generated by cgit v1.2.3 (git 2.39.1) at 2024-12-30 02:04:39 +0000