diff options
author | caryclark@google.com <caryclark@google.com@2bbb7eff-a529-9590-31e7-b0007b416f81> | 2012-08-20 12:43:57 +0000 |
---|---|---|
committer | caryclark@google.com <caryclark@google.com@2bbb7eff-a529-9590-31e7-b0007b416f81> | 2012-08-20 12:43:57 +0000 |
commit | 24bec79d6f3d71ff97b50db72461a3892bd4f6b5 (patch) | |
tree | d7e6fa1fc0a739f2361d24641b7105c0abfba806 | |
parent | 8ccfa55adbfa41670bc67d13bb4a6dcf97b9e6c0 (diff) |
shape ops work in progress
major milestone: 35.8M tests pass
(all rect/triangle/quadralateral)
git-svn-id: http://skia.googlecode.com/svn/trunk@5166 2bbb7eff-a529-9590-31e7-b0007b416f81
-rwxr-xr-x | experimental/Intersection/EdgeWalkerPolygon4x4_Test.cpp | 36 | ||||
-rw-r--r-- | experimental/Intersection/EdgeWalkerQuadratic4x4_Test.cpp | 12 | ||||
-rw-r--r-- | experimental/Intersection/EdgeWalker_Test.h | 6 | ||||
-rw-r--r-- | experimental/Intersection/EdgeWalker_TestUtility.cpp | 77 | ||||
-rw-r--r-- | experimental/Intersection/Intersection_Tests.cpp | 14 | ||||
-rw-r--r-- | experimental/Intersection/Intersection_Tests.h | 11 | ||||
-rw-r--r-- | experimental/Intersection/LineCubicIntersection.cpp | 4 | ||||
-rw-r--r-- | experimental/Intersection/LineQuadraticIntersection.cpp | 51 | ||||
-rw-r--r-- | experimental/Intersection/LineQuadraticIntersection_Test.cpp | 118 | ||||
-rw-r--r-- | experimental/Intersection/Simplify.cpp | 454 | ||||
-rw-r--r-- | experimental/Intersection/SimplifyFindNext_Test.cpp | 8 | ||||
-rw-r--r-- | experimental/Intersection/SimplifyNew_Test.cpp | 239 | ||||
-rw-r--r-- | experimental/Intersection/SimplifyRect4x4_Test.cpp | 13 | ||||
-rw-r--r-- | experimental/Intersection/op.htm | 195 |
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 = ¤t->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(); |