diff options
Diffstat (limited to 'experimental/Intersection')
-rw-r--r-- | experimental/Intersection/DataTypes.cpp | 69 | ||||
-rw-r--r-- | experimental/Intersection/DataTypes.h | 14 | ||||
-rw-r--r-- | experimental/Intersection/EdgeWalker.cpp | 951 | ||||
-rw-r--r-- | experimental/Intersection/EdgeWalkerPolygons_Mismatches.cpp | 1614 | ||||
-rw-r--r-- | experimental/Intersection/EdgeWalkerPolygons_Mismatches.h | 9 | ||||
-rw-r--r-- | experimental/Intersection/EdgeWalkerPolygons_Test.cpp | 259 | ||||
-rw-r--r-- | experimental/Intersection/EdgeWalkerQuadralaterals_Test.cpp | 99 | ||||
-rw-r--r-- | experimental/Intersection/EdgeWalkerRectangles_Test.cpp | 13 | ||||
-rw-r--r-- | experimental/Intersection/EdgeWalker_Test.h | 7 | ||||
-rw-r--r-- | experimental/Intersection/EdgeWalker_TestUtility.cpp | 51 | ||||
-rw-r--r-- | experimental/Intersection/Intersection_Tests.cpp | 2 | ||||
-rw-r--r-- | experimental/Intersection/LineIntersection.cpp | 22 | ||||
-rw-r--r-- | experimental/Intersection/LineIntersection.h | 2 | ||||
-rw-r--r-- | experimental/Intersection/edge.xcodeproj/project.pbxproj | 10 |
14 files changed, 2870 insertions, 252 deletions
diff --git a/experimental/Intersection/DataTypes.cpp b/experimental/Intersection/DataTypes.cpp index 07e7548b1b..a68cb9a96a 100644 --- a/experimental/Intersection/DataTypes.cpp +++ b/experimental/Intersection/DataTypes.cpp @@ -1,5 +1,19 @@ #include "DataTypes.h" +#include <sys/types.h> +#include <stdlib.h> + +#ifdef __cplusplus +extern "C" { +#endif + +void *memcpy(void *, const void *, size_t); + +#ifdef __cplusplus +} +#endif + + const double PointEpsilon = 0.000001; const double SquaredEpsilon = PointEpsilon * PointEpsilon; @@ -111,3 +125,58 @@ void xy_at_t(const Quadratic& quad, double t, double& x, double& y) { y = a * quad[0].y + b * quad[1].y + c * quad[2].y; } } + + +// from http://randomascii.wordpress.com/2012/02/25/comparing-floating-point-numbers-2012-edition/ +union Float_t +{ + Float_t(float num = 0.0f) : f(num) {} + // Portable extraction of components. + bool Negative() const { return (i >> 31) != 0; } + int32_t RawMantissa() const { return i & ((1 << 23) - 1); } + int32_t RawExponent() const { return (i >> 23) & 0xFF; } + + int32_t i; + float f; +#ifdef _DEBUG + struct + { // Bitfields for exploration. Do not use in production code. + uint32_t mantissa : 23; + uint32_t exponent : 8; + uint32_t sign : 1; + } parts; +#endif +}; + +bool AlmostEqualUlps(float A, float B, int maxUlpsDiff) +{ + Float_t uA(A); + Float_t uB(B); + + // Different signs means they do not match. + if (uA.Negative() != uB.Negative()) + { + // Check for equality to make sure +0==-0 + return A == B; + } + + // Find the difference in ULPs. + int ulpsDiff = abs(uA.i - uB.i); + return ulpsDiff <= maxUlpsDiff; +} + +int UlpsDiff(float A, float B) +{ + Float_t uA(A); + Float_t uB(B); + + return abs(uA.i - uB.i); +} + +int FloatAsInt(float A) +{ + Float_t uA(A); + return uA.i; +} + + diff --git a/experimental/Intersection/DataTypes.h b/experimental/Intersection/DataTypes.h index 94373cd238..8b97cec0e0 100644 --- a/experimental/Intersection/DataTypes.h +++ b/experimental/Intersection/DataTypes.h @@ -1,6 +1,16 @@ #ifndef __DataTypes_h__ #define __DataTypes_h__ +#ifdef __cplusplus +extern "C" { +#endif + +extern double fabs( double ); + +#ifdef __cplusplus +} +#endif + extern const double PointEpsilon; extern const double SquaredEpsilon; @@ -123,4 +133,8 @@ void xy_at_t(const Cubic& , double t, double& x, double& y); void xy_at_t(const _Line& , double t, double& x, double& y); void xy_at_t(const Quadratic& , double t, double& x, double& y); +bool AlmostEqualUlps(float A, float B, int maxUlpsDiff); +int UlpsDiff(float A, float B); +int FloatAsInt(float A); + #endif // __DataTypes_h__ diff --git a/experimental/Intersection/EdgeWalker.cpp b/experimental/Intersection/EdgeWalker.cpp index 771e63960f..e33fd94681 100644 --- a/experimental/Intersection/EdgeWalker.cpp +++ b/experimental/Intersection/EdgeWalker.cpp @@ -14,9 +14,43 @@ #include "SkTDArray.h" #include "TSearch.h" +#if 0 // set to 1 for no debugging whatsoever static bool gShowDebugf = false; // FIXME: remove once debugging is complete -static bool gShowPath = false; -static bool gDebugLessThan = false; + +#define DEBUG_DUMP 0 +#define DEBUG_ADD 0 +#define DEBUG_ADD_INTERSECTING_TS 0 +#define DEBUG_ADD_BOTTOM_TS 0 +#define COMPARE_DOUBLE 0 +#define ASSERT_ON_ULPS 0 +#define DEBUG_ABOVE_BELOW 0 +#define DEBUG_ACTIVE_LESS_THAN 0 +#define DEBUG_SORT_HORIZONTAL 0 +#define DEBUG_OUT 0 +#define DEBUG_OUT_LESS_THAN 0 +#define DEBUG_ADJUST_COINCIDENT 0 +#else +static bool gShowDebugf = true; // FIXME: remove once debugging is complete + +#define DEBUG_DUMP 01 +#define DEBUG_ADD 01 +#define DEBUG_ADD_INTERSECTING_TS 0 +#define DEBUG_ADD_BOTTOM_TS 0 +#define COMPARE_DOUBLE 0 +#define ASSERT_ON_ULPS 0 +#define DEBUG_ABOVE_BELOW 01 +#define DEBUG_ACTIVE_LESS_THAN 0 +#define DEBUG_SORT_HORIZONTAL 01 +#define DEBUG_OUT 01 +#define DEBUG_OUT_LESS_THAN 0 +#define DEBUG_ADJUST_COINCIDENT 1 +#endif + +// FIXME: not wild about this -- min delta should be based on size of curve, not t +// #define MIN_T_DELTA 0.000001 +// not wild about this either -- for SkScalars backed by floats, would like to +// represent deltas in terms of number of significant matching bits +#define MIN_PT_DELTA 0.000001 static int LineIntersect(const SkPoint a[2], const SkPoint b[2], double aRange[2], double bRange[2]) { @@ -25,9 +59,10 @@ static int LineIntersect(const SkPoint a[2], const SkPoint b[2], return intersect(aLine, bLine, aRange, bRange); } -static int LineIntersect(const SkPoint a[2], SkScalar y, double aRange[2]) { +static int LineIntersect(const SkPoint a[2], SkScalar left, SkScalar right, + SkScalar y, double aRange[2]) { _Line aLine = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}}; - return horizontalIntersect(aLine, y, aRange); + return horizontalLineIntersect(aLine, left, right, y, aRange); } static void LineXYAtT(const SkPoint a[2], double t, SkPoint* out) { @@ -38,6 +73,22 @@ static void LineXYAtT(const SkPoint a[2], double t, SkPoint* out) { out->fY = SkDoubleToScalar(y); } +#if COMPARE_DOUBLE +static void LineXYAtT(const SkPoint a[2], double t, _Point* out) { + _Line aLine = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}}; + xy_at_t(aLine, t, out->x, out->y); +} +#endif + +#if 0 // unused for now +static SkScalar LineXAtT(const SkPoint a[2], double t) { + _Line aLine = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}}; + double x; + xy_at_t(aLine, t, x, *(double*) 0); + return SkDoubleToScalar(x); +} +#endif + static SkScalar LineYAtT(const SkPoint a[2], double t) { _Line aLine = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}}; double y; @@ -56,6 +107,13 @@ static void LineSubDivide(const SkPoint a[2], double startT, double endT, sub[1].fY = SkDoubleToScalar(dst[1].y); } +#if COMPARE_DOUBLE +static void LineSubDivide(const SkPoint a[2], double startT, double endT, + _Line& dst) { + _Line aLine = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}}; + sub_divide(aLine, startT, endT, dst); +} +#endif // functions void contourBounds(const SkPath& path, SkTDArray<SkRect>& boundsArray); @@ -125,6 +183,8 @@ static bool extendLine(const SkPoint line[2], const SkPoint& add) { return dx1 * dy2 == dx2 * dy1; } +// OPTIMIZATION: this should point to a list of input data rather than duplicating +// the line data here. This would reduce the need to assemble the results. struct OutEdge { bool operator<(const OutEdge& rh) const { const SkPoint& first = fPts[0]; @@ -135,7 +195,9 @@ struct OutEdge { } SkPoint fPts[4]; + int fID; // id of edge generating data uint8_t fVerb; // FIXME: not read from everywhere + bool fCloseCall; // edge is trimmable if not originally coincident }; class OutEdgeBuilder { @@ -144,11 +206,40 @@ public: : fFill(fill) { } - void addLine(const SkPoint line[2]) { + void addLine(const SkPoint line[2], int id, bool closeCall) { OutEdge& newEdge = fEdges.push_back(); newEdge.fPts[0] = line[0]; newEdge.fPts[1] = line[1]; newEdge.fVerb = SkPath::kLine_Verb; + newEdge.fID = id; + newEdge.fCloseCall = closeCall; + } + + bool trimLine(SkScalar y, int id) { + size_t count = fEdges.count(); + while (count-- != 0) { + OutEdge& edge = fEdges[count]; + if (edge.fID != id) { + continue; + } + if (edge.fCloseCall) { + return false; + } + SkASSERT(edge.fPts[0].fY <= y); + if (edge.fPts[1].fY <= y) { + continue; + } + edge.fPts[1].fX = edge.fPts[0].fX + (y - edge.fPts[0].fY) + * (edge.fPts[1].fX - edge.fPts[0].fX) + / (edge.fPts[1].fY - edge.fPts[0].fY); + edge.fPts[1].fY = y; + if (gShowDebugf) { + SkDebugf("%s edge=%d %1.9g,%1.9g\n", __FUNCTION__, id, + edge.fPts[1].fX, y); + } + return true; + } + return false; } void assemble(SkPath& simple) { @@ -238,6 +329,10 @@ public: if (edgeIndex == closeEdgeIndex || edgeIndex == 0) { if (lastLine[1] != firstPt) { simple.lineTo(lastLine[1].fX, lastLine[1].fY); + if (gShowDebugf) { + SkDebugf("%s lineTo last (%g, %g)\n", __FUNCTION__, + lastLine[1].fX, lastLine[1].fY); + } } simple.lineTo(firstPt.fX, firstPt.fY); simple.close(); @@ -267,19 +362,19 @@ public: int twoIndex = two < 0 ? 0 : twoEdge.fVerb; const SkPoint& startPt2 = twoEdge.fPts[twoIndex]; if (startPt1.fY != startPt2.fY) { - if (gDebugLessThan) { - SkDebugf("%s %d<%d (%g,%g) %s startPt1.fY < startPt2.fY\n", __FUNCTION__, - one, two, startPt1.fY, startPt2.fY, - startPt1.fY < startPt2.fY ? "true" : "false"); - } + #if DEBUG_OUT_LESS_THAN + SkDebugf("%s %d<%d (%g,%g) %s startPt1.fY < startPt2.fY\n", __FUNCTION__, + one, two, startPt1.fY, startPt2.fY, + startPt1.fY < startPt2.fY ? "true" : "false"); + #endif return startPt1.fY < startPt2.fY; } if (startPt1.fX != startPt2.fX) { - if (gDebugLessThan) { - SkDebugf("%s %d<%d (%g,%g) %s startPt1.fX < startPt2.fX\n", __FUNCTION__, - one, two, startPt1.fX, startPt2.fX, - startPt1.fX < startPt2.fX ? "true" : "false"); - } + #if DEBUG_OUT_LESS_THAN + SkDebugf("%s %d<%d (%g,%g) %s startPt1.fX < startPt2.fX\n", __FUNCTION__, + one, two, startPt1.fX, startPt2.fX, + startPt1.fX < startPt2.fX ? "true" : "false"); + #endif return startPt1.fX < startPt2.fX; } const SkPoint& endPt1 = oneEdge.fPts[oneIndex ^ oneEdge.fVerb]; @@ -288,25 +383,25 @@ public: SkScalar dy2 = startPt2.fY - endPt2.fY; SkScalar dy1y2 = dy1 * dy2; if (dy1y2 < 0) { // different signs - if (gDebugLessThan) { + #if DEBUG_OUT_LESS_THAN SkDebugf("%s %d<%d %s dy1 > 0\n", __FUNCTION__, one, two, dy1 > 0 ? "true" : "false"); - } + #endif return dy1 > 0; // one < two if one goes up and two goes down } if (dy1y2 == 0) { - if (gDebugLessThan) { - SkDebugf("%s %d<%d %s endPt1.fX < endPt2.fX\n", __FUNCTION__, - one, two, endPt1.fX < endPt2.fX ? "true" : "false"); - } + #if DEBUG_OUT_LESS_THAN + SkDebugf("%s %d<%d %s endPt1.fX < endPt2.fX\n", __FUNCTION__, + one, two, endPt1.fX < endPt2.fX ? "true" : "false"); + #endif return endPt1.fX < endPt2.fX; } SkScalar dx1y2 = (startPt1.fX - endPt1.fX) * dy2; SkScalar dx2y1 = (startPt2.fX - endPt2.fX) * dy1; - if (gDebugLessThan) { - SkDebugf("%s %d<%d %s dy2 < 0 ^ dx1y2 < dx2y1\n", __FUNCTION__, - one, two, dy2 < 0 ^ dx1y2 < dx2y1 ? "true" : "false"); - } + #if DEBUG_OUT_LESS_THAN + SkDebugf("%s %d<%d %s dy2 < 0 ^ dx1y2 < dx2y1\n", __FUNCTION__, + one, two, dy2 < 0 ^ dx1y2 < dx2y1 ? "true" : "false"); + #endif return dy2 > 0 ^ dx1y2 < dx2y1; } @@ -349,8 +444,19 @@ public: right.fPts[rightIndex < 0 ? 0 : right.fVerb]; pairUp = leftMatch == rightMatch; } else { + #if DEBUG_OUT + if (left.fPts[leftIndex < 0 ? 0 : left.fVerb].fY + != right.fPts[rightIndex < 0 ? 0 : right.fVerb].fY) { + *fMismatches.append() = leftIndex; + if (rightPtr == lastPtr) { + *fMismatches.append() = rightIndex; + } + pairUp = false; + } + #else SkASSERT(left.fPts[leftIndex < 0 ? 0 : left.fVerb].fY == right.fPts[rightIndex < 0 ? 0 : right.fVerb].fY); + #endif } if (pairUp) { if (leftIndex < 0) { @@ -367,6 +473,19 @@ public: } leftPtr = rightPtr; } +#if DEBUG_OUT + int* mismatch = fMismatches.begin(); + while (mismatch != fMismatches.end()) { + int leftIndex = *mismatch++; + int leftOutIndex = abs(leftIndex) - 1; + const OutEdge& left = fEdges[leftOutIndex]; + const SkPoint& leftPt = left.fPts[leftIndex < 0 ? 0 : left.fVerb]; + SkDebugf("%s left=%d %s (%1.9g,%1.9g)\n", + __FUNCTION__, left.fID, leftIndex < 0 ? "top" : "bot", + leftPt.fX, leftPt.fY); + } + SkASSERT(fMismatches.count() == 0); +#endif } protected: @@ -374,6 +493,9 @@ protected: SkTDArray<int> fTops; SkTDArray<int> fBottoms; bool fFill; +#if DEBUG_OUT + SkTDArray<int> fMismatches; +#endif }; // Bounds, unlike Rect, does not consider a vertical line to be empty. @@ -397,11 +519,51 @@ public: : fTopIntercepts(0) , fBottomIntercepts(0) { } + +#if DEBUG_DUMP + // FIXME: pass current verb as parameter + void dump(const SkPoint* pts) { + const char className[] = "Intercepts"; + const int tab = 8; + for (int i = 0; i < fTs.count(); ++i) { + SkPoint out; + LineXYAtT(pts, fTs[i], &out); + SkDebugf("%*s.fTs[%d]=%g (%g,%g)\n", tab + sizeof(className), + className, i, fTs[i], out.fX, out.fY); + } + SkDebugf("%*s.fTopIntercepts=%d\n", tab + sizeof(className), + className, fTopIntercepts); + SkDebugf("%*s.fBottomIntercepts=%d\n", tab + sizeof(className), + className, fBottomIntercepts); + } +#endif + SkTDArray<double> fTs; int fTopIntercepts; int fBottomIntercepts; }; +struct HorizontalEdge { + bool operator<(const HorizontalEdge& rh) const { + return fY == rh.fY ? fLeft == rh.fLeft ? fRight < rh.fRight + : fLeft < rh.fLeft : fY < rh.fY; + } + +#if DEBUG_DUMP + void dump() { + const char className[] = "HorizontalEdge"; + const int tab = 4; + SkDebugf("%*s.fLeft=%g\n", tab + sizeof(className), className, fLeft); + SkDebugf("%*s.fRight=%g\n", tab + sizeof(className), className, fRight); + SkDebugf("%*s.fY=%g\n", tab + sizeof(className), className, fY); + } +#endif + + SkScalar fLeft; + SkScalar fRight; + SkScalar fY; +}; + struct InEdge { bool operator<(const InEdge& rh) const { return fBounds.fTop == rh.fBounds.fTop @@ -409,9 +571,14 @@ struct InEdge { : fBounds.fTop < rh.fBounds.fTop; } - void add(double* ts, size_t count, ptrdiff_t verbIndex) { + // Avoid collapsing t values that are close to the same since + // we walk ts to describe consecutive intersections. Since a pair of ts can + // be nearly equal, any problems caused by this should be taken care + // of later. + int add(double* ts, size_t count, ptrdiff_t verbIndex) { // FIXME: in the pathological case where there is a ton of intercepts, binary search? bool foundIntercept = false; + int insertedAt = -1; Intercepts& intercepts = fIntercepts[verbIndex]; for (size_t index = 0; index < count; ++index) { double t = ts[index]; @@ -425,21 +592,27 @@ struct InEdge { } foundIntercept = true; size_t tCount = intercepts.fTs.count(); + double delta; for (size_t idx2 = 0; idx2 < tCount; ++idx2) { if (t <= intercepts.fTs[idx2]) { - double delta = intercepts.fTs[idx2] - t; + // FIXME: ? if (t < intercepts.fTs[idx2]) // failed + delta = intercepts.fTs[idx2] - t; if (delta > 0) { + insertedAt = idx2; *intercepts.fTs.insert(idx2) = t; } - fContainsIntercepts = true; - return; + goto nextPt; } } - if (tCount == 0 || t > intercepts.fTs[tCount - 1]) { + if (tCount == 0 || (delta = t - intercepts.fTs[tCount - 1]) > 0) { + insertedAt = tCount; *intercepts.fTs.append() = t; } + nextPt: + ; } fContainsIntercepts |= foundIntercept; + return insertedAt; } bool cached(const InEdge* edge) { @@ -458,7 +631,7 @@ struct InEdge { return false; } - void complete(signed char winding) { + void complete(signed char winding, int id) { SkPoint* ptPtr = fPts.begin(); SkPoint* ptLast = fPts.end(); if (ptPtr == ptLast) { @@ -486,7 +659,45 @@ struct InEdge { } } fContainsIntercepts = false; + fID = id; + } + +#if DEBUG_DUMP + void dump() { + int i; + const char className[] = "InEdge"; + const int tab = 4; + SkDebugf("InEdge %p (edge=%d)\n", this, fID); + for (i = 0; i < fCached.count(); ++i) { + SkDebugf("%*s.fCached[%d]=0x%08x\n", tab + sizeof(className), + className, i, fCached[i]); + } + uint8_t* verbs = fVerbs.begin(); + SkPoint* pts = fPts.begin(); + for (i = 0; i < fIntercepts.count(); ++i) { + SkDebugf("%*s.fIntercepts[%d]:\n", tab + sizeof(className), + className, i); + // FIXME: take current verb into consideration + fIntercepts[i].dump(pts); + pts += *verbs++; + } + for (i = 0; i < fPts.count(); ++i) { + SkDebugf("%*s.fPts[%d]=(%g,%g)\n", tab + sizeof(className), + className, i, fPts[i].fX, fPts[i].fY); + } + for (i = 0; i < fVerbs.count(); ++i) { + SkDebugf("%*s.fVerbs[%d]=%d\n", tab + sizeof(className), + className, i, fVerbs[i]); + } + SkDebugf("%*s.fBounds=(%g. %g, %g, %g)\n", tab + sizeof(className), + className, fBounds.fLeft, fBounds.fTop, + fBounds.fRight, fBounds.fBottom); + SkDebugf("%*s.fWinding=%d\n", tab + sizeof(className), className, + fWinding); + SkDebugf("%*s.fContainsIntercepts=%d\n", tab + sizeof(className), + className, fContainsIntercepts); } +#endif // temporary data : move this to a separate struct? SkTDArray<const InEdge*> fCached; // list of edges already intercepted @@ -496,6 +707,7 @@ struct InEdge { SkTDArray<SkPoint> fPts; SkTDArray<uint8_t> fVerbs; Bounds fBounds; + int fID; signed char fWinding; bool fContainsIntercepts; }; @@ -503,10 +715,13 @@ struct InEdge { class InEdgeBuilder { public: -InEdgeBuilder(const SkPath& path, bool ignoreHorizontal, SkTArray<InEdge>& edges) +InEdgeBuilder(const SkPath& path, bool ignoreHorizontal, SkTArray<InEdge>& edges, + SkTDArray<HorizontalEdge>& horizontalEdges) : fPath(path) , fCurrentEdge(NULL) , fEdges(edges) + , fID(0) + , fHorizontalEdges(horizontalEdges) , fIgnoreHorizontal(ignoreHorizontal) { walk(); @@ -523,7 +738,7 @@ void addEdge() { bool complete() { if (fCurrentEdge && fCurrentEdge->fVerbs.count()) { - fCurrentEdge->complete(fWinding); + fCurrentEdge->complete(fWinding, ++fID); fCurrentEdge = NULL; return true; } @@ -532,8 +747,7 @@ bool complete() { int direction(int count) { fPtCount = count; - fIgnorableHorizontal = fIgnoreHorizontal && isHorizontal(); - if (fIgnorableHorizontal) { + if (fIgnoreHorizontal && isHorizontal()) { return 0; } int last = count - 1; @@ -562,40 +776,22 @@ void startEdge() { void walk() { SkPath::Iter iter(fPath, true); - int winding; + int winding = 0; while ((fVerb = iter.next(fPts)) != SkPath::kDone_Verb) { switch (fVerb) { case SkPath::kMove_Verb: - if (gShowPath) { - SkDebugf("path.moveTo(%g, %g);\n", fPts[0].fX, fPts[0].fY); - } startEdge(); continue; case SkPath::kLine_Verb: - if (gShowPath) { - SkDebugf("path.lineTo(%g, %g);\n", fPts[1].fX, fPts[1].fY); - } winding = direction(2); break; case SkPath::kQuad_Verb: - if (gShowPath) { - SkDebugf("path.quadTo(%g, %g, %g, %g);\n", - fPts[1].fX, fPts[1].fY, fPts[2].fX, fPts[2].fY); - } winding = direction(3); break; case SkPath::kCubic_Verb: - if (gShowPath) { - SkDebugf("path.cubicTo(%g, %g, %g, %g);\n", - fPts[1].fX, fPts[1].fY, fPts[2].fX, fPts[2].fY, - fPts[3].fX, fPts[3].fY); - } winding = direction(4); break; case SkPath::kClose_Verb: - if (gShowPath) { - SkDebugf("path.close();\n"); - } SkASSERT(fCurrentEdge); complete(); continue; @@ -603,7 +799,15 @@ void walk() { SkDEBUGFAIL("bad verb"); return; } - if (fIgnorableHorizontal) { + if (winding == 0) { + HorizontalEdge* horizontalEdge = fHorizontalEdges.append(); + // FIXME: for degenerate quads and cubics, compute x extremes + horizontalEdge->fLeft = fPts[0].fX; + horizontalEdge->fRight = fPts[fVerb].fX; + horizontalEdge->fY = fPts[0].fY; + if (horizontalEdge->fLeft > horizontalEdge->fRight) { + SkTSwap<SkScalar>(horizontalEdge->fLeft, horizontalEdge->fRight); + } if (complete()) { startEdge(); } @@ -625,21 +829,19 @@ void walk() { fEdges.pop_back(); } } - if (gShowPath) { - SkDebugf("\n"); - } } private: const SkPath& fPath; InEdge* fCurrentEdge; SkTArray<InEdge>& fEdges; + SkTDArray<HorizontalEdge>& fHorizontalEdges; SkPoint fPts[4]; SkPath::Verb fVerb; int fPtCount; int fPtOffset; + int fID; int8_t fWinding; - bool fIgnorableHorizontal; bool fIgnoreHorizontal; }; @@ -689,7 +891,8 @@ struct WorkEdge { // OPTIMIZATION: Brian suggests that global sorting should be unnecessary, since // as active edges are introduced, only local sorting should be required -struct ActiveEdge { +class ActiveEdge { +public: // OPTIMIZATION: fold return statements into one bool operator<(const ActiveEdge& rh) const { if (rh.fAbove.fY - fAbove.fY > fBelow.fY - rh.fAbove.fY @@ -700,43 +903,109 @@ struct ActiveEdge { const SkPoint& check = rh.fBelow.fY <= fBelow.fY && fBelow != rh.fBelow ? rh.fBelow : rh.fAbove; - if (gDebugLessThan) { - SkDebugf("%s < %c %cthis (%d){%1.2g,%1.2g %1.2g,%1.2g}" - " < rh (%d){%1.2g,%1.2g %1.2g,%1.2g}\n", __FUNCTION__, - rh.fBelow.fY <= fBelow.fY && fBelow != rh.fBelow ? 'B' : 'A', - (check.fY - fAbove.fY) * (fBelow.fX - fAbove.fX) - < (fBelow.fY - fAbove.fY) * (check.fX - fAbove.fX) - ? ' ' : '!', - fIndex, fAbove.fX, fAbove.fY, fBelow.fX, fBelow.fY, - rh.fIndex, rh.fAbove.fX, rh.fAbove.fY, - rh.fBelow.fX, rh.fBelow.fY); - } + #if COMPARE_DOUBLE + SkASSERT(((check.fY - fAbove.fY) * (fBelow.fX - fAbove.fX) + < (fBelow.fY - fAbove.fY) * (check.fX - fAbove.fX)) + == ((check.fY - fDAbove.y) * (fDBelow.x - fDAbove.x) + < (fDBelow.y - fDAbove.y) * (check.fX - fDAbove.x))); + #endif + #if DEBUG_ACTIVE_LESS_THAN + SkDebugf("%s 1 %c %cthis (edge=%d) {%g,%g %g,%g}" + " < rh (edge=%d) {%g,%g %g,%g} upls=(%d)\n", __FUNCTION__, + rh.fBelow.fY <= fBelow.fY && fBelow != rh.fBelow ? 'B' : 'A', + (check.fY - fAbove.fY) * (fBelow.fX - fAbove.fX) + < (fBelow.fY - fAbove.fY) * (check.fX - fAbove.fX) ? ' ' + : '!', ID(), fAbove.fX, fAbove.fY, fBelow.fX, fBelow.fY, + rh.ID(), rh.fAbove.fX, rh.fAbove.fY, rh.fBelow.fX, rh.fBelow.fY, + UlpsDiff((check.fY - fAbove.fY) * (fBelow.fX - fAbove.fX), + (fBelow.fY - fAbove.fY) * (check.fX - fAbove.fX))); + #endif + #if ASSERT_ON_ULPS + int ulps = UlpsDiff((check.fY - fAbove.fY) * (fBelow.fX - fAbove.fX), + (fBelow.fY - fAbove.fY) * (check.fX - fAbove.fX)); + SkASSERT((unsigned) ulps == 0x80000000 || ulps == 0 || ulps > 32); + #endif return (check.fY - fAbove.fY) * (fBelow.fX - fAbove.fX) < (fBelow.fY - fAbove.fY) * (check.fX - fAbove.fX); } // FIXME: need to compute distance, not check for points equal const SkPoint& check = fBelow.fY <= rh.fBelow.fY && fBelow != rh.fBelow ? fBelow : fAbove; - if (gDebugLessThan) { - SkDebugf("%s > %c %cthis (%d){%1.2g,%1.2g %1.2g,%1.2g}" - " < rh (%d){%1.2g,%1.2g %1.2g,%1.2g}\n", __FUNCTION__, - fBelow.fY <= rh.fBelow.fY & fBelow != rh.fBelow ? 'B' : 'A', - (rh.fBelow.fY - rh.fAbove.fY) * (check.fX - rh.fAbove.fX) - < (check.fY - rh.fAbove.fY) * (rh.fBelow.fX - rh.fAbove.fX) - ? ' ' : '!', - fIndex, fAbove.fX, fAbove.fY, fBelow.fX, fBelow.fY, - rh.fIndex, rh.fAbove.fX, rh.fAbove.fY, - rh.fBelow.fX, rh.fBelow.fY); - } + #if COMPARE_DOUBLE + SkASSERT(((rh.fBelow.fY - rh.fAbove.fY) * (check.fX - rh.fAbove.fX) + < (check.fY - rh.fAbove.fY) * (rh.fBelow.fX - rh.fAbove.fX)) + == ((rh.fDBelow.y - rh.fDAbove.y) * (check.fX - rh.fDAbove.x) + < (check.fY - rh.fDAbove.y) * (rh.fDBelow.x - rh.fDAbove.x))); + #endif + #if DEBUG_ACTIVE_LESS_THAN + SkDebugf("%s 2 %c %cthis (edge=%d) {%g,%g %g,%g}" + " < rh (edge=%d) {%g,%g %g,%g} upls=(%d)\n", __FUNCTION__, + fBelow.fY <= rh.fBelow.fY & fBelow != rh.fBelow ? 'B' : 'A', + (rh.fBelow.fY - rh.fAbove.fY) * (check.fX - rh.fAbove.fX) + < (check.fY - rh.fAbove.fY) * (rh.fBelow.fX - rh.fAbove.fX) + ? ' ' : '!', ID(), fAbove.fX, fAbove.fY, fBelow.fX, fBelow.fY, + rh.ID(), rh.fAbove.fX, rh.fAbove.fY, rh.fBelow.fX, rh.fBelow.fY, + UlpsDiff((rh.fBelow.fY - rh.fAbove.fY) * (check.fX - rh.fAbove.fX), + (check.fY - rh.fAbove.fY) * (rh.fBelow.fX - rh.fAbove.fX))); + #endif + #if ASSERT_ON_ULPS + int ulps = UlpsDiff((rh.fBelow.fY - rh.fAbove.fY) * (check.fX - rh.fAbove.fX), + (check.fY - rh.fAbove.fY) * (rh.fBelow.fX - rh.fAbove.fX)); + SkASSERT((unsigned) ulps == 0x80000000 || ulps == 0 || ulps > 32); + #endif return (rh.fBelow.fY - rh.fAbove.fY) * (check.fX - rh.fAbove.fX) < (check.fY - rh.fAbove.fY) * (rh.fBelow.fX - rh.fAbove.fX); } + + // If a pair of edges are nearly coincident for some span, add a T in the + // edge so it can be shortened to match the other edge. Note that another + // approach is to trim the edge after it is added to the OutBuilder list -- + // FIXME: since this has no effect if the edge is already done (i.e., + // fYBottom >= y) maybe this can only be done by calling trimLine later. + void addTatYBelow(SkScalar y) { + if (fBelow.fY <= y || fYBottom >= y) { + return; + } + addTatYInner(y); + fFixBelow = true; + } + + void addTatYAbove(SkScalar y) { + if (fBelow.fY <= y) { + return; + } + addTatYInner(y); + } + + void addTatYInner(SkScalar y) { + double ts[2]; + SkScalar left = fWorkEdge.fPts[0].fX; + SkScalar right = fWorkEdge.fPts[1].fX; + if (left > right) { + SkTSwap(left, right); + } + int pts = LineIntersect(fWorkEdge.fPts, left, right, y, ts); + SkASSERT(pts == 1); + // An ActiveEdge or WorkEdge has no need to modify the T values computed + // in the InEdge, except in the following case. If a pair of edges are + // nearly coincident, this may not be detected when the edges are + // intersected. Later, when sorted, and this near-coincidence is found, + // an additional t value must be added, requiring the cast below. + InEdge* writable = const_cast<InEdge*>(fWorkEdge.fEdge); + int insertedAt = writable->add(ts, pts, fWorkEdge.verbIndex()); + if (insertedAt >= 0) { + if (insertedAt + 1 < fTIndex) { + SkASSERT(insertedAt + 2 == fTIndex); + --fTIndex; + } + } + } bool advanceT() { SkASSERT(fTIndex <= fTs->count()); return ++fTIndex <= fTs->count(); } - + bool advance() { // FIXME: flip sense of next bool result = fWorkEdge.advance(); @@ -766,6 +1035,23 @@ struct ActiveEdge { LineXYAtT(fWorkEdge.fPts, tAbove, &fAbove); double tBelow = t(fTIndex - ~add); LineXYAtT(fWorkEdge.fPts, tBelow, &fBelow); + SkASSERT(tAbove != tBelow); +// maybe the following is the right sort of thing to do, but it's fragile and +// it breaks testSimplifySkinnyTriangle4 +#if 0 + if (fAbove == fBelow && !add) { + tBelow = t(fTIndex - ~add + 1); + LineXYAtT(fWorkEdge.fPts, tBelow, &fBelow); + } +#endif + #if COMPARE_DOUBLE + LineXYAtT(fWorkEdge.fPts, tAbove, &fDAbove); + LineXYAtT(fWorkEdge.fPts, tBelow, &fDBelow); + #endif + #if DEBUG_ABOVE_BELOW + fTAbove = tAbove; + fTBelow = tBelow; + #endif break; } default: @@ -774,10 +1060,17 @@ struct ActiveEdge { } } - bool done(SkScalar y) { + bool done(SkScalar y) const { return fDone || fYBottom > y; } + void fixBelow() { + if (fFixBelow) { + LineXYAtT(fWorkEdge.fPts, nextT(), &fBelow); + fFixBelow = false; + } + } + void init(const InEdge* edge) { fWorkEdge.init(edge); initT(); @@ -802,7 +1095,9 @@ struct ActiveEdge { // t values, since the same t values could exist intersecting non-coincident // edges. bool isCoincidentWith(const ActiveEdge* edge, SkScalar y) const { - if (fAbove != edge->fAbove || fBelow != edge->fBelow) { + + if (!fAbove.equalsWithinTolerance(edge->fAbove, MIN_PT_DELTA) + || !fBelow.equalsWithinTolerance(edge->fBelow, MIN_PT_DELTA)) { return false; } uint8_t verb = fDone ? fWorkEdge.lastVerb() : fWorkEdge.verb(); @@ -822,6 +1117,19 @@ struct ActiveEdge { return false; } + // The shortest close call edge should be moved into a position where + // it contributes if the winding is transitioning to or from zero. + bool swapClose(const ActiveEdge* next, int prev, int wind, int mask) const { + if ((prev & mask) == 0 || (wind & mask) == 0) { + return next->fBelow.fY < fBelow.fY; + } + int nextWinding = wind + next->fWorkEdge.winding(); + if ((nextWinding & mask) == 0) { + return fBelow.fY < next->fBelow.fY; + } + return false; + } + bool swapCoincident(const ActiveEdge* edge, SkScalar bottom) const { if (fBelow.fY >= bottom || fDone || edge->fDone) { return false; @@ -841,8 +1149,32 @@ struct ActiveEdge { } return false; } + + bool tooCloseToCall(const ActiveEdge* edge) const { + int ulps; + // FIXME: don't compare points for equality + // OPTIMIZATION: refactor to make one call to UlpsDiff + if (edge->fAbove.fY - fAbove.fY > fBelow.fY - edge->fAbove.fY + && fBelow.fY < edge->fBelow.fY + || fAbove.fY - edge->fAbove.fY < edge->fBelow.fY - fAbove.fY + && edge->fBelow.fY < fBelow.fY) { + const SkPoint& check = edge->fBelow.fY <= fBelow.fY + && fBelow != edge->fBelow ? edge->fBelow : + edge->fAbove; + ulps = UlpsDiff((check.fY - fAbove.fY) * (fBelow.fX - fAbove.fX), + (fBelow.fY - fAbove.fY) * (check.fX - fAbove.fX)); + } else { + const SkPoint& check = fBelow.fY <= edge->fBelow.fY + && fBelow != edge->fBelow ? fBelow : fAbove; + ulps = UlpsDiff((edge->fBelow.fY - edge->fAbove.fY) + * (check.fX - edge->fAbove.fX), + (check.fY - edge->fAbove.fY) + * (edge->fBelow.fX - edge->fAbove.fX)); + } + return ulps >= 0 && ulps <= 32; + } - double nextT() { + double nextT() const { SkASSERT(fTIndex <= fTs->count()); return t(fTIndex + 1); } @@ -867,15 +1199,31 @@ struct ActiveEdge { return (*fTs)[tIndex - 1]; } + // FIXME: debugging only + int ID() { + return fWorkEdge.fEdge->fID; + } + +public: WorkEdge fWorkEdge; const SkTDArray<double>* fTs; SkPoint fAbove; SkPoint fBelow; +#if COMPARE_DOUBLE + _Point fDAbove; + _Point fDBelow; +#endif +#if DEBUG_ABOVE_BELOW + double fTAbove; + double fTBelow; +#endif SkScalar fYBottom; + int fCoincident; int fTIndex; - bool fSkip; + bool fSkip; // OPTIMIZATION: use bitfields? + bool fCloseCall; bool fDone; - int fIndex; // REMOVE: debugging only + bool fFixBelow; }; static void addToActive(SkTDArray<ActiveEdge>& activeEdges, const InEdge* edge) { @@ -892,32 +1240,49 @@ static void addToActive(SkTDArray<ActiveEdge>& activeEdges, const InEdge* edge) // Find any intersections in the range of active edges. A pair of edges, on // either side of another edge, may change the winding contribution for part of // the edge. -// OPTIMIZATION: Another approach would be to keep horizontal edges just for +// Keep horizontal edges just for // the purpose of computing when edges change their winding contribution, since // this is essentially computing the horizontal intersection. -static void addBottomT(InEdge** currentPtr, InEdge** lastPtr, SkScalar bottom) { - InEdge** testPtr = currentPtr; - InEdge* test = *testPtr; - while (testPtr != lastPtr) { - if (test->fBounds.fBottom > bottom) { - WorkEdge wt; - wt.init(test); +static void addBottomT(InEdge** currentPtr, InEdge** lastPtr, + HorizontalEdge** horizontal) { + InEdge** testPtr = currentPtr - 1; + HorizontalEdge* horzEdge = *horizontal; + SkScalar left = horzEdge->fLeft; + SkScalar bottom = horzEdge->fY; + while (++testPtr != lastPtr) { + InEdge* test = *testPtr; + if (test->fBounds.fBottom <= bottom || test->fBounds.fRight <= left) { + continue; + } + WorkEdge wt; + wt.init(test); + do { + HorizontalEdge** sorted = horizontal; + horzEdge = *sorted; do { - // OPTIMIZATION: if bottom intersection does not change - // the winding on either side of the split, don't intersect if (wt.verb() == SkPath::kLine_Verb) { double wtTs[2]; - int pts = LineIntersect(wt.fPts, bottom, wtTs); + int pts = LineIntersect(wt.fPts, horzEdge->fLeft, + horzEdge->fRight, horzEdge->fY, wtTs); if (pts) { +#if DEBUG_ADD_BOTTOM_TS + SkDebugf("%s y=%g wtTs[0]=%g (%g,%g, %g,%g)\n", __FUNCTION__, + horzEdge->fY, wtTs[0], wt.fPts[0].fX, wt.fPts[0].fY, + wt.fPts[1].fX, wt.fPts[1].fY); + if (pts == 2) { + SkDebugf("%s wtTs[1]=%g\n", __FUNCTION__, wtTs[1]); + } +#endif test->add(wtTs, pts, wt.verbIndex()); } } else { // FIXME: add all curve types SkASSERT(0); } - } while (wt.advance()); - } - test = *++testPtr; + horzEdge = *++sorted; + } while (horzEdge->fY == bottom + && horzEdge->fLeft <= test->fBounds.fRight); + } while (wt.advance()); } } @@ -943,6 +1308,27 @@ static void addIntersectingTs(InEdge** currentPtr, InEdge** lastPtr) { double wtTs[2], wnTs[2]; int pts = LineIntersect(wt.fPts, wn.fPts, wtTs, wnTs); if (pts) { +#if DEBUG_ADD_INTERSECTING_TS + SkPoint wtOutPt, wnOutPt; + LineXYAtT(wt.fPts, wtTs[0], &wtOutPt); + LineXYAtT(wn.fPts, wnTs[0], &wnOutPt); + SkDebugf("%s wtTs[0]=%g (%g,%g, %g,%g) (%g,%g) (%d,%d)\n", + __FUNCTION__, + wtTs[0], wt.fPts[0].fX, wt.fPts[0].fY, + wt.fPts[1].fX, wt.fPts[1].fY, wtOutPt.fX, wtOutPt.fY, + test->fID, next->fID); + if (pts == 2) { + SkDebugf("%s wtTs[1]=%g\n", __FUNCTION__, wtTs[1]); + } + SkDebugf("%s wnTs[0]=%g (%g,%g, %g,%g) (%g,%g) (%d,%d)\n", + __FUNCTION__, + wnTs[0], wn.fPts[0].fX, wn.fPts[0].fY, + wn.fPts[1].fX, wn.fPts[1].fY, wnOutPt.fX, wnOutPt.fY, + test->fID, next->fID); + if (pts == 2) { + SkDebugf("%s wnTs[1]=%g\n", __FUNCTION__, wnTs[1]); + } +#endif test->add(wtTs, pts, wt.verbIndex()); next->add(wnTs, pts, wn.verbIndex()); } @@ -955,20 +1341,22 @@ static void addIntersectingTs(InEdge** currentPtr, InEdge** lastPtr) { } } -static InEdge** advanceEdges(SkTDArray<ActiveEdge>& activeEdges, +static InEdge** advanceEdges(SkTDArray<ActiveEdge>* activeEdges, InEdge** currentPtr, InEdge** lastPtr, SkScalar y) { InEdge** testPtr = currentPtr - 1; while (++testPtr != lastPtr) { if ((*testPtr)->fBounds.fBottom > y) { continue; } - InEdge* test = *testPtr; - ActiveEdge* activePtr = activeEdges.begin() - 1; - ActiveEdge* lastActive = activeEdges.end(); - while (++activePtr != lastActive) { - if (activePtr->fWorkEdge.fEdge == test) { - activeEdges.remove(activePtr - activeEdges.begin()); - break; + if (activeEdges) { + InEdge* test = *testPtr; + ActiveEdge* activePtr = activeEdges->begin() - 1; + ActiveEdge* lastActive = activeEdges->end(); + while (++activePtr != lastActive) { + if (activePtr->fWorkEdge.fEdge == test) { + activeEdges->remove(activePtr - activeEdges->begin()); + break; + } } } if (testPtr == currentPtr) { @@ -978,9 +1366,17 @@ static InEdge** advanceEdges(SkTDArray<ActiveEdge>& activeEdges, return currentPtr; } +// OPTIMIZE: inline? +static HorizontalEdge** advanceHorizontal(HorizontalEdge** edge, SkScalar y) { + while ((*edge)->fY < y) { + ++edge; + } + return edge; +} + // compute bottom taking into account any intersected edges -static void computeInterceptBottom(SkTDArray<ActiveEdge>& activeEdges, - SkScalar y, SkScalar& bottom) { +static SkScalar computeInterceptBottom(SkTDArray<ActiveEdge>& activeEdges, + SkScalar y, SkScalar bottom) { ActiveEdge* activePtr = activeEdges.begin() - 1; ActiveEdge* lastActive = activeEdges.end(); while (++activePtr != lastActive) { @@ -1019,10 +1415,11 @@ static void computeInterceptBottom(SkTDArray<ActiveEdge>& activeEdges, } } while (wt.advance()); } + return bottom; } static SkScalar findBottom(InEdge** currentPtr, - InEdge** edgeListEnd, SkTDArray<ActiveEdge>& activeEdges, SkScalar y, + InEdge** edgeListEnd, SkTDArray<ActiveEdge>* activeEdges, SkScalar y, bool asFill, InEdge**& testPtr) { InEdge* current = *currentPtr; SkScalar bottom = current->fBounds.fBottom; @@ -1046,7 +1443,9 @@ static SkScalar findBottom(InEdge** currentPtr, if (bottom > testBottom) { bottom = testBottom; } - addToActive(activeEdges, test); + if (activeEdges) { + addToActive(*activeEdges, test); + } } test = *++testPtr; } @@ -1067,12 +1466,26 @@ static void makeEdgeList(SkTArray<InEdge>& edges, InEdge& edgeSentinel, QSort<InEdge>(edgeList.begin(), edgeList.end() - 1); } +static void makeHorizontalList(SkTDArray<HorizontalEdge>& edges, + HorizontalEdge& edgeSentinel, SkTDArray<HorizontalEdge*>& edgeList) { + size_t edgeCount = edges.count(); + if (edgeCount == 0) { + return; + } + for (size_t index = 0; index < edgeCount; ++index) { + *edgeList.append() = &edges[index]; + } + edgeSentinel.fLeft = edgeSentinel.fRight = edgeSentinel.fY = SK_ScalarMax; + *edgeList.append() = &edgeSentinel; + QSort<HorizontalEdge>(edgeList.begin(), edgeList.end() - 1); +} static void skipCoincidence(int lastWinding, int winding, int windingMask, ActiveEdge* activePtr, ActiveEdge* firstCoincident) { if (((lastWinding & windingMask) == 0) ^ (winding & windingMask) != 0) { return; } + // FIXME: ? shouldn't this be if (lastWinding & windingMask) ? if (lastWinding) { activePtr->fSkip = false; } else { @@ -1081,66 +1494,162 @@ static void skipCoincidence(int lastWinding, int winding, int windingMask, } static void sortHorizontal(SkTDArray<ActiveEdge>& activeEdges, - SkTDArray<ActiveEdge*>& edgeList, int windingMask, SkScalar y, - SkScalar bottom) { + SkTDArray<ActiveEdge*>& edgeList, SkScalar y) { + const int tab = 3; // FIXME: debugging only size_t edgeCount = activeEdges.count(); if (edgeCount == 0) { return; } +#if DEBUG_SORT_HORIZONTAL + SkDebugf("%s y=%1.9g\n", __FUNCTION__, y); +#endif size_t index; for (index = 0; index < edgeCount; ++index) { ActiveEdge& activeEdge = activeEdges[index]; - activeEdge.calcLeft(y); - activeEdge.fSkip = false; - activeEdge.fIndex = index; // REMOVE: debugging only + do { + activeEdge.calcLeft(y); + // skip segments that don't span y + if (activeEdge.fAbove != activeEdge.fBelow) { + break; + } + if (activeEdge.fDone) { +#if DEBUG_SORT_HORIZONTAL + SkDebugf("%*s edge=%d done\n", tab, "", activeEdge.ID()); +#endif + goto nextEdge; + } +#if DEBUG_SORT_HORIZONTAL + SkDebugf("%*s edge=%d above==below\n", tab, "", activeEdge.ID()); +#endif + } while (activeEdge.advanceT() || activeEdge.advance()); +#if DEBUG_SORT_HORIZONTAL + SkDebugf("%*s edge=%d above=(%1.9g,%1.9g) (%1.9g) below=(%1.9g,%1.9g)" + " (%1.9g)\n", tab, "", activeEdge.ID(), + activeEdge.fAbove.fX, activeEdge.fAbove.fY, activeEdge.fTAbove, + activeEdge.fBelow.fX, activeEdge.fBelow.fY, activeEdge.fTBelow); +#endif + activeEdge.fSkip = activeEdge.fCloseCall = activeEdge.fFixBelow = false; *edgeList.append() = &activeEdge; +nextEdge: + ; } QSort<ActiveEdge>(edgeList.begin(), edgeList.end() - 1); - // remove coincident edges - // OPTIMIZE: remove edges? This is tricky because the current logic expects - // the winding count to be maintained while skipping coincident edges. In - // addition to removing the coincident edges, the remaining edges would need - // to have a different winding value, possibly different per intercept span. - int lastWinding = 0; - bool lastSkipped = false; +} + +// remove coincident edges +// OPTIMIZE: remove edges? This is tricky because the current logic expects +// the winding count to be maintained while skipping coincident edges. In +// addition to removing the coincident edges, the remaining edges would need +// to have a different winding value, possibly different per intercept span. +static SkScalar adjustCoincident(SkTDArray<ActiveEdge*>& edgeList, + int windingMask, SkScalar y, SkScalar bottom, OutEdgeBuilder& outBuilder) +{ +#if DEBUG_ADJUST_COINCIDENT + SkDebugf("%s y=%1.9g bottom=%1.9g\n", __FUNCTION__, y, bottom); +#endif + size_t edgeCount = edgeList.count(); + if (edgeCount == 0) { + return bottom; + } ActiveEdge* activePtr = edgeList[0]; - ActiveEdge* firstCoincident = NULL; + size_t index; + bool foundCoincident = false; + int firstIndex = 0; + for (index = 1; index < edgeCount; ++index) { + ActiveEdge* nextPtr = edgeList[index]; + bool closeCall = false; + activePtr->fCoincident = firstIndex; + if (activePtr->isCoincidentWith(nextPtr, y) + || (closeCall = activePtr->tooCloseToCall(nextPtr))) { + activePtr->fSkip = nextPtr->fSkip = foundCoincident = true; + activePtr->fCloseCall = nextPtr->fCloseCall = closeCall; + } else { + firstIndex = index; + } + activePtr = nextPtr; + } + activePtr->fCoincident = firstIndex; + if (!foundCoincident) { + return bottom; + } int winding = 0; + activePtr = edgeList[0]; for (index = 1; index < edgeCount; ++index) { + int priorWinding = winding; winding += activePtr->fWorkEdge.winding(); ActiveEdge* nextPtr = edgeList[index]; - if (activePtr->isCoincidentWith(nextPtr, y)) { + if (activePtr->fCoincident == nextPtr->fCoincident) { // the coincident edges may not have been sorted above -- advance // the edges and resort if needed // OPTIMIZE: if sorting is done incrementally as new edges are added // and not all at once as is done here, fold this test into the // current less than test. - if (activePtr->swapCoincident(nextPtr, bottom)) { + if (activePtr->fCloseCall ? activePtr->swapClose(nextPtr, + priorWinding, winding, windingMask) + : activePtr->swapCoincident(nextPtr, bottom)) { winding -= activePtr->fWorkEdge.winding(); SkTSwap<ActiveEdge*>(edgeList[index - 1], edgeList[index]); SkTSwap<ActiveEdge*>(activePtr, nextPtr); winding += activePtr->fWorkEdge.winding(); } + } + activePtr = nextPtr; + } + int firstCoincidentWinding = 0; + ActiveEdge* firstCoincident = NULL; + winding = 0; + activePtr = edgeList[0]; + for (index = 1; index < edgeCount; ++index) { + int priorWinding = winding; + winding += activePtr->fWorkEdge.winding(); + ActiveEdge* nextPtr = edgeList[index]; + if (activePtr->fCoincident == nextPtr->fCoincident) { if (!firstCoincident) { firstCoincident = activePtr; + firstCoincidentWinding = priorWinding; + } + if (activePtr->fCloseCall) { + // If one of the edges has already been added to out as a non + // coincident edge, trim it back to the top of this span + if (outBuilder.trimLine(y, activePtr->ID())) { + activePtr->addTatYAbove(y); + activePtr->fYBottom = y; + } + if (outBuilder.trimLine(y, nextPtr->ID())) { + nextPtr->addTatYAbove(y); + nextPtr->fYBottom = y; + } + // add missing t values so edges can be the same length + SkScalar testY = activePtr->fBelow.fY; + nextPtr->addTatYBelow(testY); + if (bottom > testY && testY > y) { + bottom = testY; + } + testY = nextPtr->fBelow.fY; + activePtr->addTatYBelow(testY); + if (bottom > testY && testY > y) { + bottom = testY; + } } - activePtr->fSkip = nextPtr->fSkip = lastSkipped = true; - } else if (lastSkipped) { - skipCoincidence(lastWinding, winding, windingMask, activePtr, - firstCoincident); - lastSkipped = false; + } else if (firstCoincident) { + skipCoincidence(firstCoincidentWinding, winding, windingMask, + activePtr, firstCoincident); firstCoincident = NULL; } - if (!lastSkipped) { - lastWinding = winding; - } activePtr = nextPtr; } - if (lastSkipped) { + if (firstCoincident) { winding += activePtr->fWorkEdge.winding(); - skipCoincidence(lastWinding, winding, windingMask, activePtr, + skipCoincidence(firstCoincidentWinding, winding, windingMask, activePtr, firstCoincident); } + // fix up the bottom for close call edges. OPTIMIZATION: maybe this could + // be in the loop above, but moved here since loop above reads fBelow and + // it felt unsafe to write it in that loop + for (index = 0; index < edgeCount; ++index) { + (edgeList[index])->fixBelow(); + } + return bottom; } // stitch edge and t range that satisfies operation @@ -1149,24 +1658,52 @@ static void stitchEdge(SkTDArray<ActiveEdge*>& edgeList, SkScalar y, int winding = 0; ActiveEdge** activeHandle = edgeList.begin() - 1; ActiveEdge** lastActive = edgeList.end(); + const int tab = 7; // FIXME: debugging only if (gShowDebugf) { - SkDebugf("%s y=%g bottom=%g\n", __FUNCTION__, y, bottom); + SkDebugf("%s y=%1.9g bottom=%1.9g\n", __FUNCTION__, y, bottom); } while (++activeHandle != lastActive) { ActiveEdge* activePtr = *activeHandle; const WorkEdge& wt = activePtr->fWorkEdge; int lastWinding = winding; winding += wt.winding(); + if (gShowDebugf) { + SkDebugf("%*s edge=%d lastWinding=%d winding=%d skip=%d close=%d" +#if DEBUG_ABOVE_BELOW + " above=%1.9g below=%1.9g" +#endif + "\n", + tab-4, "", activePtr->ID(), lastWinding, + winding, activePtr->fSkip, activePtr->fCloseCall +#if DEBUG_ABOVE_BELOW + , activePtr->fTAbove, activePtr->fTBelow +#endif + ); + } if (activePtr->done(y)) { + if (activePtr->fCloseCall) { + // if the top has already advanced, trim the last edge add + // FIXME: not so simple + outBuilder.trimLine(y, activePtr->ID()); + activePtr->fYBottom = y; + } // FIXME: if this is successful, rewrite done to take bottom as well if (activePtr->fDone) { + if (gShowDebugf) { + SkDebugf("%*s activePtr->fDone\n", tab, ""); + } continue; } if (activePtr->fYBottom >= bottom) { + if (gShowDebugf) { + SkDebugf("%*s activePtr->fYBottom=%1.9g >= bottom\n", tab, "", + activePtr->fYBottom); + } continue; } if (0) { - SkDebugf("%s bot %g,%g\n", __FUNCTION__, activePtr->fYBottom, bottom); + SkDebugf("%s bot %1.9g,%1.9g\n", __FUNCTION__, activePtr->fYBottom, + bottom); } } int opener = (lastWinding & windingMask) == 0; @@ -1175,6 +1712,11 @@ static void stitchEdge(SkTDArray<ActiveEdge*>& edgeList, SkScalar y, bool inWinding = opener | closer; SkPoint clippedPts[2]; const SkPoint* clipped = NULL; + #if COMPARE_DOUBLE + _Line dPoints; + _Line clippedDPts; + const _Point* dClipped = NULL; + #endif uint8_t verb = wt.verb(); bool moreToDo, aboveBottom; do { @@ -1192,31 +1734,93 @@ static void stitchEdge(SkTDArray<ActiveEdge*>& edgeList, SkScalar y, // clipped[1].fY LineSubDivide(points, currentT, nextT, clippedPts); clipped = clippedPts; + #if COMPARE_DOUBLE + LineSubDivide(points, currentT, nextT, clippedDPts); + dClipped = clippedDPts; + #endif } else { clipped = points; + #if COMPARE_DOUBLE + dPoints[0].x = SkScalarToDouble(points[0].fX); + dPoints[0].y = SkScalarToDouble(points[1].fY); + dPoints[1].x = SkScalarToDouble(points[0].fX); + dPoints[1].y = SkScalarToDouble(points[1].fY); + dClipped = dPoints; + #endif } if (inWinding && !activePtr->fSkip) { if (gShowDebugf) { - SkDebugf("%s line %g,%g %g,%g\n", __FUNCTION__, + SkDebugf("%*s line %1.9g,%1.9g %1.9g,%1.9g edge=%d" + " v=%d t=(%1.9g,%1.9g)\n", tab, "", + clipped[0].fX, clipped[0].fY, + clipped[1].fX, clipped[1].fY, + activePtr->ID(), + activePtr->fWorkEdge.fVerb + - activePtr->fWorkEdge.fEdge->fVerbs.begin(), + currentT, nextT); + } + outBuilder.addLine(clipped, activePtr->fWorkEdge.fEdge->fID, + activePtr->fCloseCall); + } else { + if (gShowDebugf) { + SkDebugf("%*s skip %1.9g,%1.9g %1.9g,%1.9g" + " edge=%d v=%d t=(%1.9g,%1.9g)\n", tab, "", clipped[0].fX, clipped[0].fY, - clipped[1].fX, clipped[1].fY); + clipped[1].fX, clipped[1].fY, + activePtr->ID(), + activePtr->fWorkEdge.fVerb + - activePtr->fWorkEdge.fEdge->fVerbs.begin(), + currentT, nextT); } - outBuilder.addLine(clipped); } + // by advancing fAbove/fBelow, the next call to sortHorizontal + // will use these values if they're still valid instead of + // recomputing + #if COMPARE_DOUBLE + SkASSERT((clipped[1].fY > activePtr->fBelow.fY + && bottom >= activePtr->fBelow.fY) + == (dClipped[1].y > activePtr->fDBelow.y + && bottom >= activePtr->fDBelow.y)); + #endif if (clipped[1].fY > activePtr->fBelow.fY && bottom >= activePtr->fBelow.fY ) { activePtr->fAbove = activePtr->fBelow; activePtr->fBelow = clipped[1]; + #if COMPARE_DOUBLE + activePtr->fDAbove = activePtr->fDBelow; + activePtr->fDBelow = dClipped[1]; + #endif + #if DEBUG_ABOVE_BELOW + activePtr->fTAbove = activePtr->fTBelow; + activePtr->fTBelow = nextT; + #endif } - activePtr->fSkip = false; } else { // FIXME: add all curve types SkASSERT(0); } currentT = nextT; moreToDo = activePtr->advanceT(); - activePtr->fYBottom = clipped[verb].fY; - aboveBottom = activePtr->fYBottom < bottom; + activePtr->fYBottom = clipped[verb].fY; // was activePtr->fCloseCall ? bottom : + + // clearing the fSkip/fCloseCall bit here means that trailing edges + // fall out of sync, if one edge is long and another is a series of short pieces + // if fSkip/fCloseCall is set, need to recompute coincidence/too-close-to-call + // after advancing + // another approach would be to restrict bottom to smaller part of close call + // maybe this is already happening with coincidence when intersection is computed, + // and needs to be added to the close call computation as well + // this is hard to do because that the bottom is important is not known when + // the lines are intersected; only when the computation for edge sorting is done + // does the need for new bottoms become apparent. + // maybe this is good incentive to scrap the current sort and do an insertion + // sort that can take this into consideration when the x value is computed + + // FIXME: initialized in sortHorizontal, cleared here as well so + // that next edge is not skipped -- but should skipped edges ever + // continue? (probably not) + aboveBottom = clipped[verb].fY < bottom && !activePtr->fCloseCall; // TEST: added close call + activePtr->fSkip = activePtr->fCloseCall = false; } while (moreToDo & aboveBottom); } while ((moreToDo || activePtr->advance()) & aboveBottom); } @@ -1233,32 +1837,69 @@ void simplify(const SkPath& path, bool asFill, SkPath& simple) { // twice that have y extrema's on top) and detect crossings -- look for raw // bounds that cross over, then tight bounds that cross SkTArray<InEdge> edges; - InEdgeBuilder builder(path, asFill, edges); + SkTDArray<HorizontalEdge> horizontalEdges; + InEdgeBuilder builder(path, asFill, edges, horizontalEdges); SkTDArray<InEdge*> edgeList; InEdge edgeSentinel; makeEdgeList(edges, edgeSentinel, edgeList); + SkTDArray<HorizontalEdge*> horizontalList; + HorizontalEdge horizontalSentinel; + makeHorizontalList(horizontalEdges, horizontalSentinel, horizontalList); InEdge** currentPtr = edgeList.begin(); if (!currentPtr) { return; } + // find all intersections between edges +// beyond looking for horizontal intercepts, we need to know if any active edges +// intersect edges below 'bottom', but above the active edge segment. +// maybe it makes more sense to compute all intercepts before doing anything +// else, since the intercept list is long-lived, at least in the current design. + SkScalar y = (*currentPtr)->fBounds.fTop; + HorizontalEdge** currentHorizontal = horizontalList.begin(); + do { + InEdge** lastPtr = currentPtr; // find the edge below the bottom of the first set + SkScalar bottom = findBottom(currentPtr, edgeList.end(), + NULL, y, asFill, lastPtr); + if (lastPtr > currentPtr) { + if (currentHorizontal) { + if ((*currentHorizontal)->fY < SK_ScalarMax) { + addBottomT(currentPtr, lastPtr, currentHorizontal); + } + currentHorizontal = advanceHorizontal(currentHorizontal, bottom); + } + addIntersectingTs(currentPtr, lastPtr); + } + y = bottom; + currentPtr = advanceEdges(NULL, currentPtr, lastPtr, y); + } while (*currentPtr != &edgeSentinel); + +#if DEBUG_DUMP + InEdge** debugPtr = edgeList.begin(); + do { + (*debugPtr++)->dump(); + } while (*debugPtr != &edgeSentinel); +#endif + // walk the sorted edges from top to bottom, computing accumulated winding SkTDArray<ActiveEdge> activeEdges; OutEdgeBuilder outBuilder(asFill); - SkScalar y = (*currentPtr)->fBounds.fTop; + currentPtr = edgeList.begin(); + y = (*currentPtr)->fBounds.fTop; do { InEdge** lastPtr = currentPtr; // find the edge below the bottom of the first set SkScalar bottom = findBottom(currentPtr, edgeList.end(), - activeEdges, y, asFill, lastPtr); + &activeEdges, y, asFill, lastPtr); if (lastPtr > currentPtr) { - addBottomT(currentPtr, lastPtr, bottom); - addIntersectingTs(currentPtr, lastPtr); - computeInterceptBottom(activeEdges, y, bottom); + bottom = computeInterceptBottom(activeEdges, y, bottom); SkTDArray<ActiveEdge*> activeEdgeList; - sortHorizontal(activeEdges, activeEdgeList, windingMask, y, bottom); + sortHorizontal(activeEdges, activeEdgeList, y); + bottom = adjustCoincident(activeEdgeList, windingMask, y, bottom, + outBuilder); stitchEdge(activeEdgeList, y, bottom, windingMask, outBuilder); } y = bottom; - currentPtr = advanceEdges(activeEdges, currentPtr, lastPtr, y); + // OPTIMIZATION: as edges expire, InEdge allocations could be released + currentPtr = advanceEdges(&activeEdges, currentPtr, lastPtr, y); } while (*currentPtr != &edgeSentinel); // assemble output path from string of pts, verbs outBuilder.bridge(); diff --git a/experimental/Intersection/EdgeWalkerPolygons_Mismatches.cpp b/experimental/Intersection/EdgeWalkerPolygons_Mismatches.cpp new file mode 100644 index 0000000000..0054cfbd26 --- /dev/null +++ b/experimental/Intersection/EdgeWalkerPolygons_Mismatches.cpp @@ -0,0 +1,1614 @@ +#include "EdgeWalker_Test.h" +#include "Intersection_Tests.h" + +// edges that didn't match +struct misMatch { + SkPath::FillType fType; + int a, b, c, d, e, f, g, h; +} misMatches[] = { +/* +___________________________________|___________________________________ +_xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx__|_xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx__ +__xxxxxxxxxxxxxxxxxxxxxxxxxxxxxx___|__xxxxxxxxxxxxxxxxxxxxxxxxxxxxxx___ +__xxxxxxxxxxxxxxxxxxxxxxxxxxxx_____|__xxxxxxxxxxxxxxxxxxxxxxxxxxxx_____ +___xxxxxxxxxx__xxxxxxxxxxxxxx______|___xxxxxxxxxx__xxxxxxxxxxxxxx______ +___xxxxxxx______xxxxxxxxxxx________|___xxxxxxx______xxxxxxxxxxx________ +____xxx__________xxxxxxxxx_________|____xxx__________xxxxxxxxx_________ +____x_____________xxxxxxx__________|____x_____________xxxxxxx__________ +__xx_______________xxxx____________|__xxx______________xxxx____________ +___xx_______________xx_____________|___xx_______________xx_____________ +____________________x______________|____________________x______________ +______x____________xxx_____________|______x____________xxx_____________ +______xxx_________xxxxx____________|______xxx_________xxxxx____________ +_______xxxx_____xxxxxxxx___________|_______xxxx_____xxxxxxxx___________ +_______xxxxxx__xxxxxxxxx___________|_______xxxxxx__xxxxxxxxxx__________ +________xxxxx__xxxxxxxxxx__________|________xxxxx__xxxxxxxxxx__________ +________xxxx_____xxxxxxxxx_________|________xxxx_____xxxxxxxxx_________ +_________xxx_______xxxxxxxx________|_________xxx_______xxxxxxxx________ +_________xxx_________xxxxxxx_______|_________xxx_________xxxxxxx_______ +__________xx____________xxxxx______|__________xx____________xxxxx______ +__________xx______________xxxx_____|__________xx______________xxxx_____ +___________x________________xxx____|___________x________________xxx____ +___________x__________________xx___|___________x__________________xx___ +___________x____________________x__|___________x____________________x__ +___________________________________|___________________________________ +___________________________________|___________________________________ +*/ +{ SkPath::kWinding_FillType, 0, 3, 9, 13, 1, 2, 4, 15 }, +/* +___________________________________|___________________________________ +_xxxxxxxxxxx_________xxxxxxxxxxxx__|_xxxxxxxxxxx_________xxxxxxxxxxxx__ +__xxxxxxxxxxx______xxxxxxxxxxxxx___|__xxxxxxxxxxx______xxxxxxxxxxxxx___ +__xxxxxxxxxxxx__xxxxxxxxxxxxxx_____|__xxxxxxxxxxxx__xxxxxxxxxxxxxx_____ +___xxxxxxxxxx__xxxxxxxxxxxxxx______|___xxxxxxxxxx__xxxxxxxxxxxxxx______ +___xxxxxxx______xxxxxxxxxxx________|___xxxxxxx______xxxxxxxxxxx________ +____xxx__________xxxxxxxxx_________|____xxx__________xxxxxxxxx_________ +____x_____________xxxxxxx__________|____x_____________xxxxxxx__________ +__xx_______________xxxx____________|__xxx______________xxxx____________ +___xx_______________xx_____________|___xx_______________xx_____________ +____________________x______________|____________________x______________ +______x____________xxx_____________|______x____________xxx_____________ +______xxx_________xxxxx____________|______xxx_________xxxxx____________ +_______xxxx_____xxxxxxxx___________|_______xxxx_____xxxxxxxx___________ +_______xxxxxx__xxxxxxxxx___________|_______xxxxxx__xxxxxxxxxx__________ +________xxxxx__xxxxxxxxxx__________|________xxxxx__xxxxxxxxxx__________ +________xxxx_____xxxxxxxxx_________|________xxxx_____xxxxxxxxx_________ +_________xxx_______xxxxxxxx________|_________xxx_______xxxxxxxx________ +_________xxx_________xxxxxxx_______|_________xxx_________xxxxxxx_______ +__________xx____________xxxxx______|__________xx____________xxxxx______ +__________xx______________xxxx_____|__________xx______________xxxx_____ +___________x________________xxx____|___________x________________xxx____ +___________x__________________xx___|___________x__________________xx___ +___________x____________________x__|___________x____________________x__ +___________________________________|___________________________________ +___________________________________|___________________________________ +*/ +{ SkPath::kEvenOdd_FillType, 0, 3, 9, 13, 1, 2, 4, 15 }, +/* +___________________________________|___________________________________ +_x__________xxxxxxxxx______________|_x__________xxxxxxxxx______________ +__xxx________xxxxxx________________|__xxx________xxxxxx________________ +__xxxxxx______xx___________________|__xxxxxx______xx___________________ +___xxxxxxxx__xx____________________|___xxxxxxxx__xx____________________ +___xxxxxxx____xx___________________|___xxxxxxx____xx___________________ +____xxx_________x__________________|____xxx_________x__________________ +____x_____________x________________|____x_____________x________________ +__xx_______________xxx_____________|__xxx______________xxx_____________ +___xx_______________xx_____________|___xx_______________xx_____________ +____________________x______________|____________________x______________ +______x____________xxx_____________|______x____________xxx_____________ +______xxx_________xxxxx____________|______xxx_________xxxxx____________ +_______xxxx_____xxxxxxxx___________|_______xxxx_____xxxxxxxx___________ +_______xxxxxx__xxxxxxxxx___________|_______xxxxxx__xxxxxxxxxx__________ +________xxxxx__xxxxxxxxxx__________|________xxxxx__xxxxxxxxxx__________ +________xxxx_____xxxxxxxxx_________|________xxxx_____xxxxxxxxx_________ +_________xxx_______xxxxxxxx________|_________xxx_______xxxxxxxx________ +_________xxx_________xxxxxxx_______|_________xxx_________xxxxxxx_______ +__________xx____________xxxxx______|__________xx____________xxxxx______ +__________xx______________xxxx_____|__________xx______________xxxx_____ +___________x________________xxx____|___________x________________xxx____ +___________x__________________xx___|___________x__________________xx___ +___________x____________________x__|___________x____________________x__ +___________________________________|___________________________________ +___________________________________|___________________________________ +*/ +{ SkPath::kWinding_FillType, 0, 6, 9, 13, 1, 2, 4, 15 }, +/* +___________________________________|___________________________________ +_x__________xxxxxxxxx______________|_x__________xxxxxxxxx______________ +__xxx________xxxxxx________________|__xxx________xxxxxx________________ +__xxxxxx______xx___________________|__xxxxxx______xx___________________ +___xxxxxxxx__xx____________________|___xxxxxxxx__xx____________________ +___xxxxxxx____xx___________________|___xxxxxxx____xx___________________ +____xxx_________x__________________|____xxx_________x__________________ +____x_____________x________________|____x_____________x________________ +__xx_______________xxx_____________|__xxx______________xxx_____________ +___xx_______________xx_____________|___xx_______________xx_____________ +____________________x______________|____________________x______________ +______x____________xxx_____________|______x____________xxx_____________ +______xxx_________xxxxx____________|______xxx_________xxxxx____________ +_______xxxx_____xxxxxxxx___________|_______xxxx_____xxxxxxxx___________ +_______xxxxxx__xxxxxxxxx___________|_______xxxxxx__xxxxxxxxxx__________ +________xxxxx__xxxxxxxxxx__________|________xxxxx__xxxxxxxxxx__________ +________xxxx_____xxxxxxxxx_________|________xxxx_____xxxxxxxxx_________ +_________xxx_______xxxxxxxx________|_________xxx_______xxxxxxxx________ +_________xxx_________xxxxxxx_______|_________xxx_________xxxxxxx_______ +__________xx____________xxxxx______|__________xx____________xxxxx______ +__________xx______________xxxx_____|__________xx______________xxxx_____ +___________x________________xxx____|___________x________________xxx____ +___________x__________________xx___|___________x__________________xx___ +___________x____________________x__|___________x____________________x__ +___________________________________|___________________________________ +___________________________________|___________________________________ +*/ +{ SkPath::kEvenOdd_FillType, 0, 6, 9, 13, 1, 2, 4, 15 }, +/* +___________________________________|___________________________________ +_xx__________________x_____________|_xx__________________x_____________ +__xxxxx____________xx______________|__xxxxx____________xx______________ +__xxxxxxxxxx____xxxx_______________|__xxxxxxxxxx____xxxx_______________ +___xxxxxxxxxx___xxx________________|___xxxxxxxxxx___xxx________________ +___xxxxxxx_________x_______________|___xxxxxxx_________x_______________ +____xxx___________xxxxxx___________|____xxx___________xxxxxx___________ +____x____________xxxxxxxxxxx_______|____x____________xxxxxxxxxxx_______ +__xx____________xxxxxxxxxxxxxxxxx__|__xxx___________xxxxxxxxxxxxxxxxx__ +__xxx__________xxxxxxxxxxxxxxxx____|__xxx__________xxxxxxxxxxxxxxxx____ +___xx_________xxxxxxxxxxxx_________|___xx_________xxxxxxxxxxxx_________ +_____x_______xxxxxxxxx_____________|_____x_______xxxxxxxxx_____________ +____________xxxxxx_________________|____________xxxxxx_________________ +_______x___xxx_____________________|_______x___xxx_____________________ +_______xx__________________________|_______xx__________________________ +_____xxx_x_________________________|_____xxx_x_________________________ +_xxxxxxxxxxx_______________________|_xxxxxxxxxxx_______________________ +__xxxxx__xx________________________|__xxxxx__xx________________________ +____xx_____________________________|____xx_____________________________ +________xx_________________________|________xx_________________________ +_____x_xxx_________________________|_____x_xxx_________________________ +____x___xxx________________________|____x___xxx________________________ +___x_____xx________________________|___x_____xx________________________ +___________________________________|___________________________________ +___________________________________|___________________________________ +___________________________________|___________________________________ +*/ +{ SkPath::kWinding_FillType, 0, 7, 8, 13, 2, 4, 9, 12 }, +/* +___________________________________|___________________________________ +_xx__________________x_____________|_xx__________________x_____________ +__xxxxx____________xx______________|__xxxxx____________xx______________ +__xxxxxxxxxx____xxxx_______________|__xxxxxxxxxx____xxxx_______________ +___xxxxxxxxxx___xxx________________|___xxxxxxxxxx___xxx________________ +___xxxxxxx_________x_______________|___xxxxxxx_________x_______________ +____xxx___________xxxxxx___________|____xxx___________xxxxxx___________ +____x____________xxxxxxxxxxx_______|____x____________xxxxxxxxxxx_______ +__xx____________xxxxxxxxxxxxxxxxx__|__xxx___________xxxxxxxxxxxxxxxxx__ +__xxx__________xxxxxxxxxxxxxxxx____|__xxx__________xxxxxxxxxxxxxxxx____ +___xx_________xxxxxxxxxxxx_________|___xx_________xxxxxxxxxxxx_________ +_____x_______xxxxxxxxx_____________|_____x_______xxxxxxxxx_____________ +____________xxxxxx_________________|____________xxxxxx_________________ +_______x___xxx_____________________|_______x___xxx_____________________ +_______xx__________________________|_______xx__________________________ +_____xxx_x_________________________|_____xxx_x_________________________ +_xxxxxxxxxxx_______________________|_xxxxxxxxxxx_______________________ +__xxxxx__xx________________________|__xxxxx__xx________________________ +____xx_____________________________|____xx_____________________________ +________xx_________________________|________xx_________________________ +_____x_xxx_________________________|_____x_xxx_________________________ +____x___xxx________________________|____x___xxx________________________ +___x_____xx________________________|___x_____xx________________________ +___________________________________|___________________________________ +___________________________________|___________________________________ +___________________________________|___________________________________ +*/ +{ SkPath::kEvenOdd_FillType, 0, 7, 8, 13, 2, 4, 9, 12 }, +/* +___________________________________|___________________________________ +_x_________x_______________________|_x_________x_______________________ +__x_______xxx______________________|__x_______xxx______________________ +___x____xxxxxx_____________________|___x____xxxxxx_____________________ +____xx_xxxxxxxx____________________|____xx_xxxxxxxx____________________ +_____x_xxxxxxxxx___________________|_____x_xxxxxxxxx___________________ +____xx___xxxxxxxx__________________|____xx___xxxxxxxx__________________ +___xxxx___xxxxxxxx_________________|___xxxx___xxxxxxxx_________________ +_xxxxxxx___xxxxxxxx________________|_xxxxxxx____xxxxxxx________________ +__xxxxxxx____xxxxxxx_______________|__xxxxxxx____xxxxxxx_______________ +___xxxxxxx____xxxxxxx______________|___xxxxxxx____xxxxxxx______________ +_____xxxxxx_____xxxxxx_____________|_____xxxxxx_____xxxxxx_____________ +______xxxxxx_____xxxxxx____________|______xxxxxx_____xxxxxx____________ +________xxxxx______xxxxx___________|________xxxxx______xxxxx___________ +_________xxxxx______xxxx___________|_________xxxxx______xxxx___________ +__________xxxxx______xxxx__________|__________xxxxx______xxxx__________ +____________xxx________xxx_________|____________xxx________xxx_________ +_______________x___________xxxxx___|_______________x___________xxxxx___ +____________________________xxx____|____________________________xxx____ +__________________xx_______________|__________________xx_________x_____ +___________________xxxx_____xx_____|___________________xxxx_____xx_____ +____________________xxxxxx_xxxx____|____________________xxxxxx_xxxx____ +_____________________xxxx____xxx___|_____________________xxxx____xxx___ +______________________xx_______xx__|______________________xx_______xx__ +___________________________________|___________________________________ +___________________________________|___________________________________ +*/ +{ SkPath::kWinding_FillType, 0, 10, 11, 14, 1, 4, 9, 15 }, +/* +___________________________________|___________________________________ +_x_________x_______________________|_x_________x_______________________ +__x_______xxx______________________|__x_______xxx______________________ +___x____xxxxxx_____________________|___x____xxxxxx_____________________ +____xx_xxxxxxxx____________________|____xx_xxxxxxxx____________________ +_____x_xxxxxxxxx___________________|_____x_xxxxxxxxx___________________ +____xx___xxxxxxxx__________________|____xx___xxxxxxxx__________________ +___xxxx___xxxxxxxx_________________|___xxxx___xxxxxxxx_________________ +_xxxxxxx___xxxxxxxx________________|_xxxxxxx____xxxxxxx________________ +__xxxxxxx____xxxxxxx_______________|__xxxxxxx____xxxxxxx_______________ +___xxxxxxx____xxxxxxx______________|___xxxxxxx____xxxxxxx______________ +_____xxxxxx_____xxxxxx_____________|_____xxxxxx_____xxxxxx_____________ +______xxxxxx_____xxxxxx____________|______xxxxxx_____xxxxxx____________ +________xxxxx______xxxxx___________|________xxxxx______xxxxx___________ +_________xxxxx______xxxx___________|_________xxxxx______xxxx___________ +__________xxxxx______xxxx__________|__________xxxxx______xxxx__________ +____________xxx________xxx_________|____________xxx________xxx_________ +_______________x___________xxxxx___|_______________x___________xxxxx___ +____________________________xxx____|____________________________xxx____ +__________________xx_______________|__________________xx_________x_____ +___________________xxxx_____xx_____|___________________xxxx_____xx_____ +____________________xxxxxx_xxxx____|____________________xxxxxx_xxxx____ +_____________________xxxx____xxx___|_____________________xxxx____xxx___ +______________________xx_______xx__|______________________xx_______xx__ +___________________________________|___________________________________ +___________________________________|___________________________________ +*/ +{ SkPath::kEvenOdd_FillType, 0, 10, 11, 14, 1, 4, 9, 15 }, +/* +___________________________________|___________________________________ +_____________xxxxxxxxxxxxxxxxxxx___|_____________xxxxxxxxxxxxxxxxxxx___ +___________xx___xxxxxxxxxxx________|___________xx___xxxxxxxxxxx________ +___________xxx_____xxxx____________|___________xxx_____xxxx____________ +__________xxxxx____xxx_____________|__________xxxxx____xxx_____________ +__________xxxxx_xxxxxxxx___________|__________xxxxx_xxxxxxxxx__________ +_________xx______xxxxxxxxxx________|_________x_______xxxxxxxxxx________ +______xxx_________xxxxxxxxxxxx_____|______xxx_________xxxxxxxxxxxx_____ +__xxxxxx___________xxxxxxxxxxxxxx__|__xxxxxx___________xxxxxxxxxxxxxx__ +___xxxxx____________xxxxxxxxxxxx___|___xxxxx____________xxxxxxxxxxxx___ +_____xx______________xxxxxxxxx_____|_____xx______________xxxxxxxxx_____ +______________________xxxxxx_______|______________________xxxxxx_______ +_______xx______________xxx_________|_______xx______________xxx_________ +______xxxxx________________________|______xxxxx________________________ +______xxxxxxx_________xx___________|______xxxxxxx_________xxx__________ +_____xxxxxxxxxx____xxxxxx__________|_____xxxxxxxxxx____xxxxxx__________ +_____xxxxxxxxxxxxxxxxxxxxx_________|_____xxxxxxxxxxxxxxxxxxxxx_________ +____xxxxxxxxxxx____xxxxxxxx________|____xxxxxxxxxxx____xxxxxxxx________ +____xxxxxxxxx________xxxxxxx_______|____xxxxxxxxx________xxxxxxx_______ +___xxxxxxxx_____________xxxxx______|___xxxxxxxx_____________xxxxx______ +___xxxxxx_________________xxxx_____|___xxxxxx_________________xxxx_____ +__xxxxx_____________________xxx____|__xxxxx_____________________xxx____ +__xxx_________________________xx___|__xxx_________________________xx___ +_xx_____________________________x__|_xx_____________________________x__ +___________________________________|___________________________________ +___________________________________|___________________________________ +*/ +{ SkPath::kEvenOdd_FillType, 1, 1, 7, 12, 1, 3, 4, 15 }, +/* +___________________________________|___________________________________ +_xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx__|_xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx__ +__xxxxxxxxxxxxxxxxxxxxxxxxxxxxxx___|__xxxxxxxxxxxxxxxxxxxxxxxxxxxxxx___ +__xxxxxxxxxxxxxxxxxxxxxxxxxxxx_____|__xxxxxxxxxxxxxxxxxxxxxxxxxxxx_____ +___xxxxxxxxxx__xxxxxxxxxxxxxx______|___xxxxxxxxxx__xxxxxxxxxxxxxx______ +___xxxxxxx______xxxxxxxxxxx________|___xxxxxxx______xxxxxxxxxxx________ +____xxx__________xxxxxxxxx_________|____xxx__________xxxxxxxxx_________ +____x_____________xxxxxxx__________|____x_____________xxxxxxx__________ +__xx_______________xxxx____________|__xxx______________xxxx____________ +___xx_______________xx_____________|___xx_______________xx_____________ +____________________x______________|____________________x______________ +______x____________xxx_____________|______x____________xxx_____________ +______xxx_________xxxxx____________|______xxx_________xxxxx____________ +_______xxxx_____xxxxxxxx___________|_______xxxx_____xxxxxxxx___________ +_______xxxxxx__xxxxxxxxx___________|_______xxxxxx__xxxxxxxxxx__________ +________xxxxx__xxxxxxxxxx__________|________xxxxx__xxxxxxxxxx__________ +________xxxx_____xxxxxxxxx_________|________xxxx_____xxxxxxxxx_________ +_________xxx_______xxxxxxxx________|_________xxx_______xxxxxxxx________ +_________xxx_________xxxxxxx_______|_________xxx_________xxxxxxx_______ +__________xx____________xxxxx______|__________xx____________xxxxx______ +__________xx______________xxxx_____|__________xx______________xxxx_____ +___________x________________xxx____|___________x________________xxx____ +___________x__________________xx___|___________x__________________xx___ +___________x____________________x__|___________x____________________x__ +___________________________________|___________________________________ +___________________________________|___________________________________ +*/ +{ SkPath::kWinding_FillType, 1, 2, 4, 15, 0, 3, 9, 13 }, +/* +___________________________________|___________________________________ +_xxxxxxxxxxx_________xxxxxxxxxxxx__|_xxxxxxxxxxx_________xxxxxxxxxxxx__ +__xxxxxxxxxxx______xxxxxxxxxxxxx___|__xxxxxxxxxxx______xxxxxxxxxxxxx___ +__xxxxxxxxxxxx__xxxxxxxxxxxxxx_____|__xxxxxxxxxxxx__xxxxxxxxxxxxxx_____ +___xxxxxxxxxx__xxxxxxxxxxxxxx______|___xxxxxxxxxx__xxxxxxxxxxxxxx______ +___xxxxxxx______xxxxxxxxxxx________|___xxxxxxx______xxxxxxxxxxx________ +____xxx__________xxxxxxxxx_________|____xxx__________xxxxxxxxx_________ +____x_____________xxxxxxx__________|____x_____________xxxxxxx__________ +__xx_______________xxxx____________|__xxx______________xxxx____________ +___xx_______________xx_____________|___xx_______________xx_____________ +____________________x______________|____________________x______________ +______x____________xxx_____________|______x____________xxx_____________ +______xxx_________xxxxx____________|______xxx_________xxxxx____________ +_______xxxx_____xxxxxxxx___________|_______xxxx_____xxxxxxxx___________ +_______xxxxxx__xxxxxxxxx___________|_______xxxxxx__xxxxxxxxxx__________ +________xxxxx__xxxxxxxxxx__________|________xxxxx__xxxxxxxxxx__________ +________xxxx_____xxxxxxxxx_________|________xxxx_____xxxxxxxxx_________ +_________xxx_______xxxxxxxx________|_________xxx_______xxxxxxxx________ +_________xxx_________xxxxxxx_______|_________xxx_________xxxxxxx_______ +__________xx____________xxxxx______|__________xx____________xxxxx______ +__________xx______________xxxx_____|__________xx______________xxxx_____ +___________x________________xxx____|___________x________________xxx____ +___________x__________________xx___|___________x__________________xx___ +___________x____________________x__|___________x____________________x__ +___________________________________|___________________________________ +___________________________________|___________________________________ +*/ +{ SkPath::kEvenOdd_FillType, 1, 2, 4, 15, 0, 3, 9, 13 }, +/* +___________________________________|___________________________________ +_x__________xxxxxxxxx______________|_x__________xxxxxxxxx______________ +__xxx________xxxxxx________________|__xxx________xxxxxx________________ +__xxxxxx______xx___________________|__xxxxxx______xx___________________ +___xxxxxxxx__xx____________________|___xxxxxxxx__xx____________________ +___xxxxxxx____xx___________________|___xxxxxxx____xx___________________ +____xxx_________x__________________|____xxx_________x__________________ +____x_____________x________________|____x_____________x________________ +__xx_______________xxx_____________|__xxx______________xxx_____________ +___xx_______________xx_____________|___xx_______________xx_____________ +____________________x______________|____________________x______________ +______x____________xxx_____________|______x____________xxx_____________ +______xxx_________xxxxx____________|______xxx_________xxxxx____________ +_______xxxx_____xxxxxxxx___________|_______xxxx_____xxxxxxxx___________ +_______xxxxxx__xxxxxxxxx___________|_______xxxxxx__xxxxxxxxxx__________ +________xxxxx__xxxxxxxxxx__________|________xxxxx__xxxxxxxxxx__________ +________xxxx_____xxxxxxxxx_________|________xxxx_____xxxxxxxxx_________ +_________xxx_______xxxxxxxx________|_________xxx_______xxxxxxxx________ +_________xxx_________xxxxxxx_______|_________xxx_________xxxxxxx_______ +__________xx____________xxxxx______|__________xx____________xxxxx______ +__________xx______________xxxx_____|__________xx______________xxxx_____ +___________x________________xxx____|___________x________________xxx____ +___________x__________________xx___|___________x__________________xx___ +___________x____________________x__|___________x____________________x__ +___________________________________|___________________________________ +___________________________________|___________________________________ +*/ +{ SkPath::kWinding_FillType, 1, 2, 4, 15, 0, 6, 9, 13 }, +/* +___________________________________|___________________________________ +_x__________xxxxxxxxx______________|_x__________xxxxxxxxx______________ +__xxx________xxxxxx________________|__xxx________xxxxxx________________ +__xxxxxx______xx___________________|__xxxxxx______xx___________________ +___xxxxxxxx__xx____________________|___xxxxxxxx__xx____________________ +___xxxxxxx____xx___________________|___xxxxxxx____xx___________________ +____xxx_________x__________________|____xxx_________x__________________ +____x_____________x________________|____x_____________x________________ +__xx_______________xxx_____________|__xxx______________xxx_____________ +___xx_______________xx_____________|___xx_______________xx_____________ +____________________x______________|____________________x______________ +______x____________xxx_____________|______x____________xxx_____________ +______xxx_________xxxxx____________|______xxx_________xxxxx____________ +_______xxxx_____xxxxxxxx___________|_______xxxx_____xxxxxxxx___________ +_______xxxxxx__xxxxxxxxx___________|_______xxxxxx__xxxxxxxxxx__________ +________xxxxx__xxxxxxxxxx__________|________xxxxx__xxxxxxxxxx__________ +________xxxx_____xxxxxxxxx_________|________xxxx_____xxxxxxxxx_________ +_________xxx_______xxxxxxxx________|_________xxx_______xxxxxxxx________ +_________xxx_________xxxxxxx_______|_________xxx_________xxxxxxx_______ +__________xx____________xxxxx______|__________xx____________xxxxx______ +__________xx______________xxxx_____|__________xx______________xxxx_____ +___________x________________xxx____|___________x________________xxx____ +___________x__________________xx___|___________x__________________xx___ +___________x____________________x__|___________x____________________x__ +___________________________________|___________________________________ +___________________________________|___________________________________ +*/ +{ SkPath::kEvenOdd_FillType, 1, 2, 4, 15, 0, 6, 9, 13 }, +/* +___________________________________|___________________________________ +_______________________xxxxxxxxx___|_______________________xxxxxxxxx___ +___________xx____________xx________|___________xx____________xx________ +___________xxx_________xxx_________|___________xxx_________xxx_________ +__________xxxxx____xxxxxxxxx_______|__________xxxxx____xxxxxxxxx_______ +__________xxxxx_xxxxxxxxxxxxx______|__________xxxxx_xxxxxxxxxxxxx______ +_________xx______xxxxxxxxxxxxx_____|_________x_______xxxxxxxxxxxxx_____ +______xxx_________xxxxxxxxxxxxxx___|______xxx_________xxxxxxxxxxxxxx___ +__xxxxxx___________xxxxxxxxxxxxxx__|__xxxxxx___________xxxxxxxxxxxxxx__ +___xxxxx____________xxxxxxxxxxxx___|___xxxxx____________xxxxxxxxxxxx___ +_____xx______________xxxxxxxxx_____|_____xx______________xxxxxxxxx_____ +______________________xxxxxx_______|______________________xxxxxx_______ +_______xx______________xxx_________|_______xx______________xxx_________ +______xxxxx________________________|______xxxxx________________________ +______xxxxxxx_________xx___________|______xxxxxxx_________xxx__________ +_____xxxxxxxxxx____xxxxxx__________|_____xxxxxxxxxx____xxxxxx__________ +_____xxxxxxxxxxxxxxxxxxxxx_________|_____xxxxxxxxxxxxxxxxxxxxx_________ +____xxxxxxxxxxx____xxxxxxxx________|____xxxxxxxxxxx____xxxxxxxx________ +____xxxxxxxxx________xxxxxxx_______|____xxxxxxxxx________xxxxxxx_______ +___xxxxxxxx_____________xxxxx______|___xxxxxxxx_____________xxxxx______ +___xxxxxx_________________xxxx_____|___xxxxxx_________________xxxx_____ +__xxxxx_____________________xxx____|__xxxxx_____________________xxx____ +__xxx_________________________xx___|__xxx_________________________xx___ +_xx_____________________________x__|_xx_____________________________x__ +___________________________________|___________________________________ +___________________________________|___________________________________ +*/ +{ SkPath::kEvenOdd_FillType, 1, 2, 7, 12, 1, 3, 4, 15 }, +/* +___________________________________|___________________________________ +_____________xxxxxxxxxxxxxxxxxxx___|_____________xxxxxxxxxxxxxxxxxxx___ +___________xx___xxxxxxxxxxx________|___________xx___xxxxxxxxxxx________ +___________xxx_____xxxx____________|___________xxx_____xxxx____________ +__________xxxxx____xxx_____________|__________xxxxx____xxx_____________ +__________xxxxx_xxxxxxxx___________|__________xxxxx_xxxxxxxxx__________ +_________xx______xxxxxxxxxx________|_________x_______xxxxxxxxxx________ +______xxx_________xxxxxxxxxxxx_____|______xxx_________xxxxxxxxxxxx_____ +__xxxxxx___________xxxxxxxxxxxxxx__|__xxxxxx___________xxxxxxxxxxxxxx__ +___xxxxx____________xxxxxxxxxxxx___|___xxxxx____________xxxxxxxxxxxx___ +_____xx______________xxxxxxxxx_____|_____xx______________xxxxxxxxx_____ +______________________xxxxxx_______|______________________xxxxxx_______ +_______xx______________xxx_________|_______xx______________xxx_________ +______xxxxx________________________|______xxxxx________________________ +______xxxxxxx_________xx___________|______xxxxxxx_________xxx__________ +_____xxxxxxxxxx____xxxxxx__________|_____xxxxxxxxxx____xxxxxx__________ +_____xxxxxxxxxxxxxxxxxxxxx_________|_____xxxxxxxxxxxxxxxxxxxxx_________ +____xxxxxxxxxxx____xxxxxxxx________|____xxxxxxxxxxx____xxxxxxxx________ +____xxxxxxxxx________xxxxxxx_______|____xxxxxxxxx________xxxxxxx_______ +___xxxxxxxx_____________xxxxx______|___xxxxxxxx_____________xxxxx______ +___xxxxxx_________________xxxx_____|___xxxxxx_________________xxxx_____ +__xxxxx_____________________xxx____|__xxxxx_____________________xxx____ +__xxx_________________________xx___|__xxx_________________________xx___ +_xx_____________________________x__|_xx_____________________________x__ +___________________________________|___________________________________ +___________________________________|___________________________________ +*/ +{ SkPath::kEvenOdd_FillType, 1, 3, 4, 15, 1, 1, 7, 12 }, +/* +___________________________________|___________________________________ +_______________________xxxxxxxxx___|_______________________xxxxxxxxx___ +___________xx____________xx________|___________xx____________xx________ +___________xxx_________xxx_________|___________xxx_________xxx_________ +__________xxxxx____xxxxxxxxx_______|__________xxxxx____xxxxxxxxx_______ +__________xxxxx_xxxxxxxxxxxxx______|__________xxxxx_xxxxxxxxxxxxx______ +_________xx______xxxxxxxxxxxxx_____|_________x_______xxxxxxxxxxxxx_____ +______xxx_________xxxxxxxxxxxxxx___|______xxx_________xxxxxxxxxxxxxx___ +__xxxxxx___________xxxxxxxxxxxxxx__|__xxxxxx___________xxxxxxxxxxxxxx__ +___xxxxx____________xxxxxxxxxxxx___|___xxxxx____________xxxxxxxxxxxx___ +_____xx______________xxxxxxxxx_____|_____xx______________xxxxxxxxx_____ +______________________xxxxxx_______|______________________xxxxxx_______ +_______xx______________xxx_________|_______xx______________xxx_________ +______xxxxx________________________|______xxxxx________________________ +______xxxxxxx_________xx___________|______xxxxxxx_________xxx__________ +_____xxxxxxxxxx____xxxxxx__________|_____xxxxxxxxxx____xxxxxx__________ +_____xxxxxxxxxxxxxxxxxxxxx_________|_____xxxxxxxxxxxxxxxxxxxxx_________ +____xxxxxxxxxxx____xxxxxxxx________|____xxxxxxxxxxx____xxxxxxxx________ +____xxxxxxxxx________xxxxxxx_______|____xxxxxxxxx________xxxxxxx_______ +___xxxxxxxx_____________xxxxx______|___xxxxxxxx_____________xxxxx______ +___xxxxxx_________________xxxx_____|___xxxxxx_________________xxxx_____ +__xxxxx_____________________xxx____|__xxxxx_____________________xxx____ +__xxx_________________________xx___|__xxx_________________________xx___ +_xx_____________________________x__|_xx_____________________________x__ +___________________________________|___________________________________ +___________________________________|___________________________________ +*/ +{ SkPath::kEvenOdd_FillType, 1, 3, 4, 15, 1, 2, 7, 12 }, +/* +___________________________________|___________________________________ +________________________________xx_|________________________________xx_ +___________xx______________xxxxxxx_|___________xx______________xxxxxxx_ +___________xxx_________xxxxxxxxxxx_|___________xxx_________xxxxxxxxxxx_ +__________xxxxx____xxxxxxxxxxxxxxx_|__________xxxxx____xxxxxxxxxxxxxxx_ +__________xxxxx_xxxxxxxxxxxxxxxxxx_|__________xxxxx_xxxxxxxxxxxxxxxxxx_ +_________xx______xxxxxxxxxxxxxxxxx_|_________x_______xxxxxxxxxxxxxxxxx_ +______xxx_________xxxxxxxxxxxxxxxx_|______xxx_________xxxxxxxxxxxxxxxx_ +__xxxxxx___________xxxxxxxxxxxxxxx_|__xxxxxx___________xxxxxxxxxxxxxxx_ +___xxxxx____________xxxxxxxxxxxx___|___xxxxx____________xxxxxxxxxxxx___ +_____xx______________xxxxxxxxx_____|_____xx______________xxxxxxxxx_____ +______________________xxxxxx_______|______________________xxxxxx_______ +_______xx______________xxx_________|_______xx______________xxx_________ +______xxxxx________________________|______xxxxx________________________ +______xxxxxxx_________xx___________|______xxxxxxx_________xxx__________ +_____xxxxxxxxxx____xxxxxx__________|_____xxxxxxxxxx____xxxxxx__________ +_____xxxxxxxxxxxxxxxxxxxxx_________|_____xxxxxxxxxxxxxxxxxxxxx_________ +____xxxxxxxxxxx____xxxxxxxx________|____xxxxxxxxxxx____xxxxxxxx________ +____xxxxxxxxx________xxxxxxx_______|____xxxxxxxxx________xxxxxxx_______ +___xxxxxxxx_____________xxxxx______|___xxxxxxxx_____________xxxxx______ +___xxxxxx_________________xxxx_____|___xxxxxx_________________xxxx_____ +__xxxxx_____________________xxx____|__xxxxx_____________________xxx____ +__xxx_________________________xx___|__xxx_________________________xx___ +_xx_____________________________x__|_xx_____________________________x__ +___________________________________|___________________________________ +___________________________________|___________________________________ +*/ +{ SkPath::kEvenOdd_FillType, 1, 3, 4, 15, 1, 3, 7, 12 }, +/* +___________________________________|___________________________________ +_____________xxxxxxxxxxxxxxxxxxx___|_____________xxxxxxxxxxxxxxxxxxx___ +___________xx___xxxxxxxxxxx________|___________xx___xxxxxxxxxxx________ +___________xxx_____xxxx____________|___________xxx_____xxxx____________ +__________xxxxx____xxx_____________|__________xxxxx____xxx_____________ +__________xxxxx_xxxxxxxx___________|__________xxxxx_xxxxxxxxx__________ +_________xx______xxxxxxxxxx________|_________x_______xxxxxxxxxx________ +______xxx_________xxxxxxxxxxxx_____|______xxx_________xxxxxxxxxxxx_____ +__xxxxxx___________xxxxxxxxxxxxxx__|__xxxxxx___________xxxxxxxxxxxxxx__ +___xxxxx____________xxxxxxxxxxxx___|___xxxxx____________xxxxxxxxxxxx___ +_____xx______________xxxxxxxxx_____|_____xx______________xxxxxxxxx_____ +______________________xxxxxx_______|______________________xxxxxx_______ +_______xx______________xxx_________|_______xx______________xxx_________ +______xxxxx________________________|______xxxxx________________________ +______xxxxxxx_________xx___________|______xxxxxxx_________xxx__________ +_____xxxxxxxxxx____xxxxxx__________|_____xxxxxxxxxx____xxxxxx__________ +_____xxxxxxxxxxxxxxxxxxxxx_________|_____xxxxxxxxxxxxxxxxxxxxx_________ +____xxxxxxxxxxx____xxxxxxxx________|____xxxxxxxxxxx____xxxxxxxx________ +____xxxxxxxxx________xxxxxxx_______|____xxxxxxxxx________xxxxxxx_______ +___xxxxxxxx_____________xxxxx______|___xxxxxxxx_____________xxxxx______ +___xxxxxx_________________xxxx_____|___xxxxxx_________________xxxx_____ +__xxxxx_____________________xxx____|__xxxxx_____________________xxx____ +__xxx_________________________xx___|__xxx_________________________xx___ +_xx_____________________________x__|_xx_____________________________x__ +___________________________________|___________________________________ +___________________________________|___________________________________ +*/ +{ SkPath::kEvenOdd_FillType, 1, 3, 4, 15, 1, 7, 7, 12 }, +/* +___________________________________|___________________________________ +_____________xxxxxxxxxxxxxxxxxxx___|_____________xxxxxxxxxxxxxxxxxxx___ +___________xx___xxxxxxxxxxx________|___________xx___xxxxxxxxxxx________ +___________xxx_____xxxx____________|___________xxx_____xxxx____________ +__________xxxxx____xxx_____________|__________xxxxx____xxx_____________ +__________xxxxx_xxxxxxxx___________|__________xxxxx_xxxxxxxxx__________ +_________xx______xxxxxxxxxx________|_________x_______xxxxxxxxxx________ +______xxx_________xxxxxxxxxxxx_____|______xxx_________xxxxxxxxxxxx_____ +__xxxxxx___________xxxxxxxxxxxxxx__|__xxxxxx___________xxxxxxxxxxxxxx__ +___xxxxx____________xxxxxxxxxxxx___|___xxxxx____________xxxxxxxxxxxx___ +_____xx______________xxxxxxxxx_____|_____xx______________xxxxxxxxx_____ +______________________xxxxxx_______|______________________xxxxxx_______ +_______xx______________xxx_________|_______xx______________xxx_________ +______xxxxx________________________|______xxxxx________________________ +______xxxxxxx_________xx___________|______xxxxxxx_________xxx__________ +_____xxxxxxxxxx____xxxxxx__________|_____xxxxxxxxxx____xxxxxx__________ +_____xxxxxxxxxxxxxxxxxxxxx_________|_____xxxxxxxxxxxxxxxxxxxxx_________ +____xxxxxxxxxxx____xxxxxxxx________|____xxxxxxxxxxx____xxxxxxxx________ +____xxxxxxxxx________xxxxxxx_______|____xxxxxxxxx________xxxxxxx_______ +___xxxxxxxx_____________xxxxx______|___xxxxxxxx_____________xxxxx______ +___xxxxxx_________________xxxx_____|___xxxxxx_________________xxxx_____ +__xxxxx_____________________xxx____|__xxxxx_____________________xxx____ +__xxx_________________________xx___|__xxx_________________________xx___ +_xx_____________________________x__|_xx_____________________________x__ +___________________________________|___________________________________ +___________________________________|___________________________________ +*/ +{ SkPath::kEvenOdd_FillType, 1, 3, 4, 15, 1, 7, 12, 12 }, +/* +___________________________________|___________________________________ +________________________________xx_|________________________________xx_ +___________xx______________xxxxxxx_|___________xx______________xxxxxxx_ +___________xxx_________xxxxxxxxxxx_|___________xxx_________xxxxxxxxxxx_ +__________xxxxx____xxxxxxxxxxxxxxx_|__________xxxxx____xxxxxxxxxxxxxxx_ +__________xxxxx_xxxxxxxxxxxxxxxxxx_|__________xxxxx_xxxxxxxxxxxxxxxxxx_ +_________xx______xxxxxxxxxxxxxxxxx_|_________x_______xxxxxxxxxxxxxxxxx_ +______xxx_________xxxxxxxxxxxxxxxx_|______xxx_________xxxxxxxxxxxxxxxx_ +__xxxxxx___________xxxxxxxxxxxxxxx_|__xxxxxx___________xxxxxxxxxxxxxxx_ +___xxxxx____________xxxxxxxxxxxx___|___xxxxx____________xxxxxxxxxxxx___ +_____xx______________xxxxxxxxx_____|_____xx______________xxxxxxxxx_____ +______________________xxxxxx_______|______________________xxxxxx_______ +_______xx______________xxx_________|_______xx______________xxx_________ +______xxxxx________________________|______xxxxx________________________ +______xxxxxxx_________xx___________|______xxxxxxx_________xxx__________ +_____xxxxxxxxxx____xxxxxx__________|_____xxxxxxxxxx____xxxxxx__________ +_____xxxxxxxxxxxxxxxxxxxxx_________|_____xxxxxxxxxxxxxxxxxxxxx_________ +____xxxxxxxxxxx____xxxxxxxx________|____xxxxxxxxxxx____xxxxxxxx________ +____xxxxxxxxx________xxxxxxx_______|____xxxxxxxxx________xxxxxxx_______ +___xxxxxxxx_____________xxxxx______|___xxxxxxxx_____________xxxxx______ +___xxxxxx_________________xxxx_____|___xxxxxx_________________xxxx_____ +__xxxxx_____________________xxx____|__xxxxx_____________________xxx____ +__xxx_________________________xx___|__xxx_________________________xx___ +_xx_____________________________x__|_xx_____________________________x__ +___________________________________|___________________________________ +___________________________________|___________________________________ +*/ +{ SkPath::kEvenOdd_FillType, 1, 3, 7, 12, 1, 3, 4, 15 }, +/* +___________________________________|___________________________________ +____________xxxxxxxxxxxxxxxxxxxxx__|____________xxxxxxxxxxxxxxxxxxxxx__ +_____________xxxxxxxxxxxxxxxxxxx___|_____________xxxxxxxxxxxxxxxxxxx___ +______________xxxxxxxxx_xxxxxx_____|______________xxxxxxxxx_xxxxxx_____ +_______________xxxxxxxx_xxxxx______|_______________xxxxxxxx_xxxxx______ +________________xxxxxxx__xx________|________________xxxxxxx__xx________ +_________________xxxxxx__x_________|_________________xxxxxx__x_________ +__________________xxxxx__x_________|__________________xxxxx__x_________ +___________________xxxxxxx_________|___________________xxxxxxx_________ +____________________x_xxxxx________|____________________x_xxxxx________ +__________________xx_xxxxxx________|__________________xx_xxxxxx________ +_______________xxxx___xxxxxx_______|_______________xxxx___xxxxxx_______ +____________xxxxxx_____xxxxx_______|____________xxxxxx_____xxxxx_______ +_________xxxxxxx________xxxxx______|_________xxxxxxx________xxxxx______ +_______xxxxxxxx_________xxxxx______|_______xxxxxxxx__________xxxx______ +____xxxxxxxxx____________xxxxx_____|____xxxxxxxxx____________xxxxx_____ +_xxxxxxxxxxx______________xxxx_____|_xxxxxxxxxxx______________xxxx_____ +_____xxxxxx________________xxx_____|_____xxxxxx________________xxx_____ +____________________________xxx____|____________________________xxx____ +________xxxxx________________xx____|________xxxxx________________xx____ +______xxxxxxxxxxxx____________xx___|______xxxxxxxxxxxx____________xx___ +_____xxxxxxxxxxxxxxxxx_________x___|_____xxxxxxxxxxxxxxxxx_________x___ +____xxxxxxxxxxxxxxxxxxxxxx______x__|____xxxxxxxxxxxxxxxxxxxxxx______x__ +__xxxxxxxxxxxxxxxxxxxxxxxxxxxx_____|__xxxxxxxxxxxxxxxxxxxxxxxxxxxx_____ +___________________________________|___________________________________ +___________________________________|___________________________________ +*/ +{ SkPath::kEvenOdd_FillType, 1, 3, 12, 15, 2, 6, 8, 15 }, +/* +___________________________________|___________________________________ +_x_________x_______________________|_x_________x_______________________ +__x_______xxx______________________|__x_______xxx______________________ +___x____xxxxxx_____________________|___x____xxxxxx_____________________ +____xx_xxxxxxxx____________________|____xx_xxxxxxxx____________________ +_____x_xxxxxxxxx___________________|_____x_xxxxxxxxx___________________ +____xx___xxxxxxxx__________________|____xx___xxxxxxxx__________________ +___xxxx___xxxxxxxx_________________|___xxxx___xxxxxxxx_________________ +_xxxxxxx___xxxxxxxx________________|_xxxxxxx____xxxxxxx________________ +__xxxxxxx____xxxxxxx_______________|__xxxxxxx____xxxxxxx_______________ +___xxxxxxx____xxxxxxx______________|___xxxxxxx____xxxxxxx______________ +_____xxxxxx_____xxxxxx_____________|_____xxxxxx_____xxxxxx_____________ +______xxxxxx_____xxxxxx____________|______xxxxxx_____xxxxxx____________ +________xxxxx______xxxxx___________|________xxxxx______xxxxx___________ +_________xxxxx______xxxx___________|_________xxxxx______xxxx___________ +__________xxxxx______xxxx__________|__________xxxxx______xxxx__________ +____________xxx________xxx_________|____________xxx________xxx_________ +_______________x___________xxxxx___|_______________x___________xxxxx___ +____________________________xxx____|____________________________xxx____ +__________________xx_______________|__________________xx_________x_____ +___________________xxxx_____xx_____|___________________xxxx_____xx_____ +____________________xxxxxx_xxxx____|____________________xxxxxx_xxxx____ +_____________________xxxx____xxx___|_____________________xxxx____xxx___ +______________________xx_______xx__|______________________xx_______xx__ +___________________________________|___________________________________ +___________________________________|___________________________________ +*/ +{ SkPath::kWinding_FillType, 1, 4, 9, 15, 0, 10, 11, 14 }, +/* +___________________________________|___________________________________ +_x_________x_______________________|_x_________x_______________________ +__x_______xxx______________________|__x_______xxx______________________ +___x____xxxxxx_____________________|___x____xxxxxx_____________________ +____xx_xxxxxxxx____________________|____xx_xxxxxxxx____________________ +_____x_xxxxxxxxx___________________|_____x_xxxxxxxxx___________________ +____xx___xxxxxxxx__________________|____xx___xxxxxxxx__________________ +___xxxx___xxxxxxxx_________________|___xxxx___xxxxxxxx_________________ +_xxxxxxx___xxxxxxxx________________|_xxxxxxx____xxxxxxx________________ +__xxxxxxx____xxxxxxx_______________|__xxxxxxx____xxxxxxx_______________ +___xxxxxxx____xxxxxxx______________|___xxxxxxx____xxxxxxx______________ +_____xxxxxx_____xxxxxx_____________|_____xxxxxx_____xxxxxx_____________ +______xxxxxx_____xxxxxx____________|______xxxxxx_____xxxxxx____________ +________xxxxx______xxxxx___________|________xxxxx______xxxxx___________ +_________xxxxx______xxxx___________|_________xxxxx______xxxx___________ +__________xxxxx______xxxx__________|__________xxxxx______xxxx__________ +____________xxx________xxx_________|____________xxx________xxx_________ +_______________x___________xxxxx___|_______________x___________xxxxx___ +____________________________xxx____|____________________________xxx____ +__________________xx_______________|__________________xx_________x_____ +___________________xxxx_____xx_____|___________________xxxx_____xx_____ +____________________xxxxxx_xxxx____|____________________xxxxxx_xxxx____ +_____________________xxxx____xxx___|_____________________xxxx____xxx___ +______________________xx_______xx__|______________________xx_______xx__ +___________________________________|___________________________________ +___________________________________|___________________________________ +*/ +{ SkPath::kEvenOdd_FillType, 1, 4, 9, 15, 0, 10, 11, 14 }, +/* +___________________________________|___________________________________ +____________x__________xxxxxxxxxx__|____________x__________xxxxxxxxxx__ +_____________x_________xxxxxxxxx___|_____________x_________xxxxxxxxx___ +______________x_________xxxxxx_____|______________x_________xxxxxx_____ +_______________xx_______xxxxx______|_______________xx_______xxxxx______ +________________xx_______xx________|________________xx_______xx________ +_________________xxx_____x_________|_________________xxx_____x_________ +__________________xxx____x_________|__________________xxx____x_________ +___________________xxx_xxx_________|___________________xxx_xxx_________ +____________________x_xxxxx________|____________________x_xxxxx________ +__________________xx_xxxxxx________|__________________xx_xxxxxx________ +_______________xxxx___xxxxxx_______|_______________xxxx___xxxxxx_______ +____________xxxxxx_____xxxxx_______|____________xxxxxx_____xxxxx_______ +_________xxxxxxx________xxxxx______|_________xxxxxxx________xxxxx______ +_______xxxxxxxx_________xxxxx______|_______xxxxxxxx__________xxxx______ +____xxxxxxxxx____________xxxxx_____|____xxxxxxxxx____________xxxxx_____ +_xxxxxxxxxxx______________xxxx_____|_xxxxxxxxxxx______________xxxx_____ +_____xxxxxx________________xxx_____|_____xxxxxx________________xxx_____ +____________________________xxx____|____________________________xxx____ +________xxxxx________________xx____|________xxxxx________________xx____ +______xxxxxxxxxxxx____________xx___|______xxxxxxxxxxxx____________xx___ +_____xxxxxxxxxxxxxxxxx_________x___|_____xxxxxxxxxxxxxxxxx_________x___ +____xxxxxxxxxxxxxxxxxxxxxx______x__|____xxxxxxxxxxxxxxxxxxxxxx______x__ +__xxxxxxxxxxxxxxxxxxxxxxxxxxxx_____|__xxxxxxxxxxxxxxxxxxxxxxxxxxxx_____ +___________________________________|___________________________________ +___________________________________|___________________________________ +*/ +{ SkPath::kEvenOdd_FillType, 1, 6, 8, 15, 2, 3, 12, 15 }, +/* +___________________________________|___________________________________ +____________x________x_____________|____________x________x_____________ +_____________x_____xx______________|_____________x_____xx______________ +______________x_xxxx_______________|______________x_xxxx_______________ +_____________xx__xx________________|_____________xx__xx________________ +__________xxxxxx__x________________|__________xxxxxx__x________________ +_______xxxxxxxxxx_xx_______________|_______xxxxxxxxxx_xx_______________ +_____xxxxxxxxxxxx_xxx______________|_____xxxxxxxxxxxx_xxx______________ +__xxxxxxxxxxxxxx___xxx_____________|__xxxxxxxxxxxxxx___xxx_____________ +____xxxxxxxxxxx_____xx_____________|____xxxxxxxxxxx_____xx_____________ +________xxxxxx______x______________|________xxxxxx______x______________ +____________x______xxx_____________|____________x______xxx_____________ +____________xxxxx_xxxxx____________|____________xxxxx_xxxxx____________ +___________xxxxx_____xxx___________|___________xxxxx_____xxx___________ +__________xxxxx_________x__________|__________xxxxx____________________ +_________xxxx____________xxxx______|_________xxxx____________xxxx______ +________xxxx______________xxxxxxxx_|________xxxx______________xxxxxxxx_ +_______xxxxxxxx____________xxx_____|_______xxxxxxxx____________xxx_____ +______xxxxxxxxxxx________xxx_______|______xxxxxxxxxxx________xxx_______ +_____xxxxxxxxxxxxxxx_xxxxxxxx______|_____xxxxxxxxxxxxxxx_xxxxxxxx______ +_____xxxxxxxxxxxx______xxxxxxx_____|_____xxxxxxxxxxxx______xxxxxxx_____ +____xxxxxxxxx_____________xxxxx____|____xxxxxxxxx_____________xxxxx____ +___xxxxxx____________________xxx___|___xxxxxx____________________xxx___ +__xx___________________________xx__|__xx___________________________xx__ +___________________________________|___________________________________ +___________________________________|___________________________________ +*/ +{ SkPath::kWinding_FillType, 1, 6, 9, 15, 2, 4, 11, 12 }, +/* +___________________________________|___________________________________ +____________x________x_____________|____________x________x_____________ +_____________x_____xx______________|_____________x_____xx______________ +______________x_xxxx_______________|______________x_xxxx_______________ +_____________xx__xx________________|_____________xx__xx________________ +__________xxxxxx__x________________|__________xxxxxx__x________________ +_______xxxxxxxxxx_xx_______________|_______xxxxxxxxxx_xx_______________ +_____xxxxxxxxxxxx_xxx______________|_____xxxxxxxxxxxx_xxx______________ +__xxxxxxxxxxxxxx___xxx_____________|__xxxxxxxxxxxxxx___xxx_____________ +____xxxxxxxxxxx_____xx_____________|____xxxxxxxxxxx_____xx_____________ +________xxxxxx______x______________|________xxxxxx______x______________ +____________x______xxx_____________|____________x______xxx_____________ +____________xxxxx_xxxxx____________|____________xxxxx_xxxxx____________ +___________xxxxx_____xxx___________|___________xxxxx_____xxx___________ +__________xxxxx_________x__________|__________xxxxx____________________ +_________xxxx____________xxxx______|_________xxxx____________xxxx______ +________xxxx______________xxxxxxxx_|________xxxx______________xxxxxxxx_ +_______xxxxxxxx____________xxx_____|_______xxxxxxxx____________xxx_____ +______xxxxxxxxxxx________xxx_______|______xxxxxxxxxxx________xxx_______ +_____xxxxxxxxxxxxxxx_xxxxxxxx______|_____xxxxxxxxxxxxxxx_xxxxxxxx______ +_____xxxxxxxxxxxx______xxxxxxx_____|_____xxxxxxxxxxxx______xxxxxxx_____ +____xxxxxxxxx_____________xxxxx____|____xxxxxxxxx_____________xxxxx____ +___xxxxxx____________________xxx___|___xxxxxx____________________xxx___ +__xx___________________________xx__|__xx___________________________xx__ +___________________________________|___________________________________ +___________________________________|___________________________________ +*/ +{ SkPath::kEvenOdd_FillType, 1, 6, 9, 15, 2, 4, 11, 12 }, +/* +___________________________________|___________________________________ +_____________xxxxxxxxxxxxxxxxxxx___|_____________xxxxxxxxxxxxxxxxxxx___ +___________xx___xxxxxxxxxxx________|___________xx___xxxxxxxxxxx________ +___________xxx_____xxxx____________|___________xxx_____xxxx____________ +__________xxxxx____xxx_____________|__________xxxxx____xxx_____________ +__________xxxxx_xxxxxxxx___________|__________xxxxx_xxxxxxxxx__________ +_________xx______xxxxxxxxxx________|_________x_______xxxxxxxxxx________ +______xxx_________xxxxxxxxxxxx_____|______xxx_________xxxxxxxxxxxx_____ +__xxxxxx___________xxxxxxxxxxxxxx__|__xxxxxx___________xxxxxxxxxxxxxx__ +___xxxxx____________xxxxxxxxxxxx___|___xxxxx____________xxxxxxxxxxxx___ +_____xx______________xxxxxxxxx_____|_____xx______________xxxxxxxxx_____ +______________________xxxxxx_______|______________________xxxxxx_______ +_______xx______________xxx_________|_______xx______________xxx_________ +______xxxxx________________________|______xxxxx________________________ +______xxxxxxx_________xx___________|______xxxxxxx_________xxx__________ +_____xxxxxxxxxx____xxxxxx__________|_____xxxxxxxxxx____xxxxxx__________ +_____xxxxxxxxxxxxxxxxxxxxx_________|_____xxxxxxxxxxxxxxxxxxxxx_________ +____xxxxxxxxxxx____xxxxxxxx________|____xxxxxxxxxxx____xxxxxxxx________ +____xxxxxxxxx________xxxxxxx_______|____xxxxxxxxx________xxxxxxx_______ +___xxxxxxxx_____________xxxxx______|___xxxxxxxx_____________xxxxx______ +___xxxxxx_________________xxxx_____|___xxxxxx_________________xxxx_____ +__xxxxx_____________________xxx____|__xxxxx_____________________xxx____ +__xxx_________________________xx___|__xxx_________________________xx___ +_xx_____________________________x__|_xx_____________________________x__ +___________________________________|___________________________________ +___________________________________|___________________________________ +*/ +{ SkPath::kEvenOdd_FillType, 1, 7, 7, 12, 1, 3, 4, 15 }, +/* +___________________________________|___________________________________ +____________x____________________x_|____________x____________________x_ +_____________xxx_________________x_|_____________xxx_________________x_ +______________xxxxx_____________xx_|______________xxxxx_____________xx_ +_______________xxxxxxx__________xx_|_______________xxxxxxx__________xx_ +________________xxxxxxxx________xx_|________________xxxxxxxx________xx_ +_________________xxxxxxxxxx____xxx_|_________________xxxxxxxxxx____xxx_ +__________________xxxxxxxxxxxx_xxx_|__________________xxxxxxxxxxxx_xxx_ +___________________xxxxxxxxxxx___x_|___________________xxxxxxxxxxx___x_ +____________________xxxxxxxxxx_xxx_|____________________xxxxxxxxxx_xxx_ +_____________________xxxxx___xxxxx_|_____________________xxxxx___xxxxx_ +_____________________________xxxxx_|_____________________________xxxxx_ +__________________xxxxx_____xxxxxx_|__________________xxxxx_____xxxxxx_ +______________xxxxxxxxxx____xxxxxx_|______________xxxxxxxxxx____xxxxxx_ +__________xxxxxxxxxxxxxx___xxxxxxx_|__________xxxxxxxxxxxxxx___xxxxxxx_ +_____xxxxxxxxxxxxxxxxxxxx__xxxxxxx_|_____xxxxxxxxxxxxxxxxxxxx__xxxxxxx_ +_xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx_|_xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx_ +_____xxxxxxxxxxxxxxxxxxxxx_xxxxx___|_____xxxxxxxxxxxxxxxxxxxxx_xxxxx___ +_________xxxxxxxxxxxxxxxx___xxx____|_________xxxxxxxxxxxxxxxx___xxx____ +_____________xxxxxxxxxxxx__________|_____________xxxxxxxxxxxx____x_____ +__________________xxxxxxx___xx_____|__________________xxxxxxx___xx_____ +______________________xx___xxxx____|______________________xx___xxxx____ +________________________x_xxxxxx___|________________________x_xxxxxx___ +_______________________x______xxx__|_______________________x______xxx__ +___________________________________|___________________________________ +___________________________________|___________________________________ +*/ +{ SkPath::kEvenOdd_FillType, 1, 7, 8, 15, 3, 3, 11, 14 }, +/* +___________________________________|___________________________________ +____________x___________________x__|____________x___________________x__ +_____________xxx___________xxxxxx__|_____________xxx___________xxxxxx__ +______________xxxxx____xxxxxxxxx___|______________xxxxx____xxxxxxxxx___ +_______________xxxx___xxxxxxxxxx___|_______________xxxx___xxxxxxxxxx___ +_______________x________xxxxxxxx___|_______________x_________xxxxxxx___ +___________xxxxxx__________xxxx____|___________xxxxxx__________xxxx____ +______xxxxxxxxxxxx____________x____|______xxxxxxxxxxxx____________x____ +__xxxxxxxxxxxxxxxxx___________xxx__|__xxxxxxxxxxxxxxxxx___________xxx__ +____xxxxxxxxxxxxxxxx__________x____|____xxxxxxxxxxxxxxxx__________x____ +________xxxxxxxxxxxxx_____xxx______|________xxxxxxxxxxxxx_____xxx______ +____________xxxxxxxxxxxxxxxxx______|_____________xxxxxxxxxxxxxxxx______ +_________________xxxxxxxxxxx_______|_________________xxxxxxxxxxx_______ +______________xxxxxxxxxxxxxx_______|______________xxxxxxxxxxxxxx_______ +__________xxxxxxxxxxxxxx_xx________|__________xxxxxxxxxxxxxxxxx________ +_____xxxxxxxxxxxxxxxxxxxx__xx______|_____xxxxxxxxxxxxxxxxxxxx__xx______ +_xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx_|_xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx_ +_____xxxxxxxxxxxxxxxxxxxxx_xxxxx___|_____xxxxxxxxxxxxxxxxxxxxx_xxxxx___ +_________xxxxxxxxxxxxxxxx___xxx____|_________xxxxxxxxxxxxxxxx___xxx____ +_____________xxxxxxxxxxxx__________|_____________xxxxxxxxxxxx____x_____ +__________________xxxxxxx___xx_____|__________________xxxxxxx___xx_____ +______________________xx___xxxx____|______________________xx___xxxx____ +________________________x_xxxxxx___|________________________x_xxxxxx___ +_______________________x______xxx__|_______________________x______xxx__ +___________________________________|___________________________________ +___________________________________|___________________________________ +*/ +{ SkPath::kWinding_FillType, 1, 7, 8, 15, 3, 4, 11, 14 }, +/* +___________________________________|___________________________________ +____________x___________________x__|____________x___________________x__ +_____________xxx___________xxxxxx__|_____________xxx___________xxxxxx__ +______________xxxxx____xxxxxxxxx___|______________xxxxx____xxxxxxxxx___ +_______________xxxx___xxxxxxxxxx___|_______________xxxx___xxxxxxxxxx___ +_______________x________xxxxxxxx___|_______________x_________xxxxxxx___ +___________xxxxxx__________xxxx____|___________xxxxxx__________xxxx____ +______xxxxxxxxxxxx____________x____|______xxxxxxxxxxxx____________x____ +__xxxxxxxxxxxxxxxxx___________xxx__|__xxxxxxxxxxxxxxxxx___________xxx__ +____xxxxxxxxxxxxxxxx__________x____|____xxxxxxxxxxxxxxxx__________x____ +________xxxxxxxxxxxxx_____xxx______|________xxxxxxxxxxxxx_____xxx______ +____________xxxxxxxxxxxxxxxxx______|_____________xxxxxxxxxxxxxxxx______ +_________________x_____xxxxx_______|_________________x_____xxxxx_______ +______________xxxxxxx___xxxx_______|______________xxxxxxx___xxxx_______ +__________xxxxxxxxxxxxxx_xx________|__________xxxxxxxxxxxxxxxxx________ +_____xxxxxxxxxxxxxxxxxxxx__xx______|_____xxxxxxxxxxxxxxxxxxxx__xx______ +_xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx_|_xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx_ +_____xxxxxxxxxxxxxxxxxxxxx_xxxxx___|_____xxxxxxxxxxxxxxxxxxxxx_xxxxx___ +_________xxxxxxxxxxxxxxxx___xxx____|_________xxxxxxxxxxxxxxxx___xxx____ +_____________xxxxxxxxxxxx__________|_____________xxxxxxxxxxxx____x_____ +__________________xxxxxxx___xx_____|__________________xxxxxxx___xx_____ +______________________xx___xxxx____|______________________xx___xxxx____ +________________________x_xxxxxx___|________________________x_xxxxxx___ +_______________________x______xxx__|_______________________x______xxx__ +___________________________________|___________________________________ +___________________________________|___________________________________ +*/ +{ SkPath::kEvenOdd_FillType, 1, 7, 8, 15, 3, 4, 11, 14 }, +/* +___________________________________|___________________________________ +____________x______________________|____________x______________________ +_____________xxx________________x__|_____________xxx________________x__ +______________xxxxx___________xx___|______________xxxxx___________xx___ +_______________xxxxxxx_______xxx___|_______________xxxxxxx_______xxx___ +________________xxxxxxxx___xxxxx___|________________xxxxxxxxx__xxxxx___ +_________________xxxxxxxxx_xxxx____|_________________xxxxxxxxx_xxxx____ +__________________xxxxxxx_____x____|__________________xxxxxxx_____x____ +___________________xxxx_______xxx__|___________________xxxx_______xxx__ +____________________xxxx______x____|____________________xxxx______x____ +_____________________xxxx_xxx______|_____________________xxxx_xxx______ +___________________________xx______|___________________________xx______ +__________________xxxxx____________|__________________xxxxx____________ +______________xxxxxxxxxx____x______|______________xxxxxxxxxx____x______ +__________xxxxxxxxxxxxxx___xxxx____|__________xxxxxxxxxxxxxx___xxxx____ +_____xxxxxxxxxxxxxxxxxxxx__xxxxx___|_____xxxxxxxxxxxxxxxxxxxx__xxxxx___ +_xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx_|_xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx_ +_____xxxxxxxxxxxxxxxxxxxxx_xxxxx___|_____xxxxxxxxxxxxxxxxxxxxx_xxxxx___ +_________xxxxxxxxxxxxxxxx___xxx____|_________xxxxxxxxxxxxxxxx___xxx____ +_____________xxxxxxxxxxxx__________|_____________xxxxxxxxxxxx____x_____ +__________________xxxxxxx___xx_____|__________________xxxxxxx___xx_____ +______________________xx___xxxx____|______________________xx___xxxx____ +________________________x_xxxxxx___|________________________x_xxxxxx___ +_______________________x______xxx__|_______________________x______xxx__ +___________________________________|___________________________________ +___________________________________|___________________________________ +*/ +{ SkPath::kWinding_FillType, 1, 7, 8, 15, 3, 6, 11, 14 }, +/* +___________________________________|___________________________________ +____________x______________________|____________x______________________ +_____________xxx________________x__|_____________xxx________________x__ +______________xxxxx___________xx___|______________xxxxx___________xx___ +_______________xxxxxxx_______xxx___|_______________xxxxxxx_______xxx___ +________________xxxxxxxx___xxxxx___|________________xxxxxxxxx__xxxxx___ +_________________xxxxxxxxx_xxxx____|_________________xxxxxxxxx_xxxx____ +__________________xxxxxxx_____x____|__________________xxxxxxx_____x____ +___________________xxxx_______xxx__|___________________xxxx_______xxx__ +____________________xxxx______x____|____________________xxxx______x____ +_____________________xxxx_xxx______|_____________________xxxx_xxx______ +___________________________xx______|___________________________xx______ +__________________xxxxx____________|__________________xxxxx____________ +______________xxxxxxxxxx____x______|______________xxxxxxxxxx____x______ +__________xxxxxxxxxxxxxx___xxxx____|__________xxxxxxxxxxxxxx___xxxx____ +_____xxxxxxxxxxxxxxxxxxxx__xxxxx___|_____xxxxxxxxxxxxxxxxxxxx__xxxxx___ +_xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx_|_xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx_ +_____xxxxxxxxxxxxxxxxxxxxx_xxxxx___|_____xxxxxxxxxxxxxxxxxxxxx_xxxxx___ +_________xxxxxxxxxxxxxxxx___xxx____|_________xxxxxxxxxxxxxxxx___xxx____ +_____________xxxxxxxxxxxx__________|_____________xxxxxxxxxxxx____x_____ +__________________xxxxxxx___xx_____|__________________xxxxxxx___xx_____ +______________________xx___xxxx____|______________________xx___xxxx____ +________________________x_xxxxxx___|________________________x_xxxxxx___ +_______________________x______xxx__|_______________________x______xxx__ +___________________________________|___________________________________ +___________________________________|___________________________________ +*/ +{ SkPath::kEvenOdd_FillType, 1, 7, 8, 15, 3, 6, 11, 14 }, +/* +___________________________________|___________________________________ +____________x____________________x_|____________x____________________x_ +_____________xxx_________________x_|_____________xxx_________________x_ +______________xxxxx_____________xx_|______________xxxxx_____________xx_ +_______________xxxxxxx__________xx_|_______________xxxxxxx__________xx_ +________________xxxxxxxx________xx_|________________xxxxxxxx________xx_ +_________________xxxxxxxxxx____xxx_|_________________xxxxxxxxxx____xxx_ +__________________xxxxxxxxxxxx_xxx_|__________________xxxxxxxxxxxx_xxx_ +___________________xxxxxxxxxxx___x_|___________________xxxxxxxxxxx___x_ +____________________xxxxxxxxxx_xxx_|____________________xxxxxxxxxx_xxx_ +_____________________xxxxx___xxxxx_|_____________________xxxxx___xxxxx_ +_____________________________xxxxx_|_____________________________xxxxx_ +__________________xxxxx_____xxxxxx_|__________________xxxxx_____xxxxxx_ +______________xxxxxxxxxx____xxxxxx_|______________xxxxxxxxxx____xxxxxx_ +__________xxxxxxxxxxxxxx___xxxxxxx_|__________xxxxxxxxxxxxxx___xxxxxxx_ +_____xxxxxxxxxxxxxxxxxxxx__xxxxxxx_|_____xxxxxxxxxxxxxxxxxxxx__xxxxxxx_ +_xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx_|_xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx_ +_____xxxxxxxxxxxxxxxxxxxxx_xxxxx___|_____xxxxxxxxxxxxxxxxxxxxx_xxxxx___ +_________xxxxxxxxxxxxxxxx___xxx____|_________xxxxxxxxxxxxxxxx___xxx____ +_____________xxxxxxxxxxxx__________|_____________xxxxxxxxxxxx____x_____ +__________________xxxxxxx___xx_____|__________________xxxxxxx___xx_____ +______________________xx___xxxx____|______________________xx___xxxx____ +________________________x_xxxxxx___|________________________x_xxxxxx___ +_______________________x______xxx__|_______________________x______xxx__ +___________________________________|___________________________________ +___________________________________|___________________________________ +*/ +{ SkPath::kEvenOdd_FillType, 1, 7, 8, 15, 3, 7, 11, 14 }, +/* +___________________________________|___________________________________ +____________x______________________|____________x______________________ +_____________xxx___________________|_____________xxx___________________ +______________xxxxx________________|______________xxxxx________________ +_______________xxxxxxx_________x___|_______________xxxxxxx_________x___ +________________xxxxxxxx______xx___|________________xxxxxxxxx_____xx___ +_________________xxxxxxxxxx___x____|_________________xxxxxxxxxx___x____ +__________________xxxxxxxxxxx_x____|__________________xxxxxxxxxxx_x____ +___________________xxxxxxxxx__xxx__|___________________xxxxxxxxx__xxx__ +____________________xxxxxxxx__x____|____________________xxxxxxxx__x____ +_____________________xxxxx_xx______|_____________________xxxxx_xx______ +__________________________xxx______|__________________________xxx______ +__________________xxxxx___xx_______|__________________xxxxx___xx_______ +______________xxxxxxxxxx_xxx_______|______________xxxxxxxxxx_xxx_______ +__________xxxxxxxxxxxxxxxxx________|__________xxxxxxxxxxxxxxxxx________ +_____xxxxxxxxxxxxxxxxxxxxxx________|_____xxxxxxxxxxxxxxxxxxxxxx________ +_xxxxxxxxxxxxxxxxxxxxxxxxx_________|_xxxxxxxxxxxxxxxxxxxxxxxxx_________ +_____xxxxxxxxxxxxxxxxxxxxx_xxxxx___|_____xxxxxxxxxxxxxxxxxxxxx_xxxxx___ +_________xxxxxxxxxxxxxxxx___xxx____|_________xxxxxxxxxxxxxxxx___xxx____ +_____________xxxxxxxxxxxx__________|_____________xxxxxxxxxxxx____x_____ +__________________xxxxxxx___xx_____|__________________xxxxxxx___xx_____ +______________________xx___xxxx____|______________________xx___xxxx____ +________________________x_xxxxxx___|________________________x_xxxxxx___ +_______________________x______xxx__|_______________________x______xxx__ +___________________________________|___________________________________ +___________________________________|___________________________________ +*/ +{ SkPath::kWinding_FillType, 1, 7, 8, 15, 3, 10, 11, 14 }, +/* +___________________________________|___________________________________ +____________x______________________|____________x______________________ +_____________xxx___________________|_____________xxx___________________ +______________xxxxx________________|______________xxxxx________________ +_______________xxxxxxx_________x___|_______________xxxxxxx_________x___ +________________xxxxxxxx______xx___|________________xxxxxxxxx_____xx___ +_________________xxxxxxxxxx___x____|_________________xxxxxxxxxx___x____ +__________________xxxxxxxxxxx_x____|__________________xxxxxxxxxxx_x____ +___________________xxxxxxxxx__xxx__|___________________xxxxxxxxx__xxx__ +____________________xxxxxxxx__x____|____________________xxxxxxxx__x____ +_____________________xxxxx_xx______|_____________________xxxxx_xx______ +__________________________xxx______|__________________________xxx______ +__________________xxxxx___xx_______|__________________xxxxx___xx_______ +______________xxxxxxxxxx_xxx_______|______________xxxxxxxxxx_xxx_______ +__________xxxxxxxxxxxxxxxxx________|__________xxxxxxxxxxxxxx_xx________ +_____xxxxxxxxxxxxxxxxxx__xx________|_____xxxxxxxxxxxxxxxxxx__xx________ +_xxxxxxxxxxxxxxxxxxxxxx____________|_xxxxxxxxxxxxxxxxxxxxxx____________ +_____xxxxxxxxxxxxxxxxxxxxx_xxxxx___|_____xxxxxxxxxxxxxxxxxxxxx_xxxxx___ +_________xxxxxxxxxxxxxxxx___xxx____|_________xxxxxxxxxxxxxxxx___xxx____ +_____________xxxxxxxxxxxx__________|_____________xxxxxxxxxxxx____x_____ +__________________xxxxxxx___xx_____|__________________xxxxxxx___xx_____ +______________________xx___xxxx____|______________________xx___xxxx____ +________________________x_xxxxxx___|________________________x_xxxxxx___ +_______________________x______xxx__|_______________________x______xxx__ +___________________________________|___________________________________ +___________________________________|___________________________________ +*/ +{ SkPath::kEvenOdd_FillType, 1, 7, 8, 15, 3, 10, 11, 14 }, +/* +___________________________________|___________________________________ +____________x____________________x_|____________x____________________x_ +_____________xxx_________________x_|_____________xxx_________________x_ +______________xxxxx_____________xx_|______________xxxxx_____________xx_ +_______________xxxxxxx__________xx_|_______________xxxxxxx__________xx_ +________________xxxxxxxx________xx_|________________xxxxxxxx________xx_ +_________________xxxxxxxxxx____xxx_|_________________xxxxxxxxxx____xxx_ +__________________xxxxxxxxxxxx_xxx_|__________________xxxxxxxxxxxx_xxx_ +___________________xxxxxxxxxxx___x_|___________________xxxxxxxxxxx___x_ +____________________xxxxxxxxxx_xxx_|____________________xxxxxxxxxx_xxx_ +_____________________xxxxx___xxxxx_|_____________________xxxxx___xxxxx_ +_____________________________xxxxx_|_____________________________xxxxx_ +__________________xxxxx_____xxxxxx_|__________________xxxxx_____xxxxxx_ +______________xxxxxxxxxx____xxxxxx_|______________xxxxxxxxxx____xxxxxx_ +__________xxxxxxxxxxxxxx___xxxxxxx_|__________xxxxxxxxxxxxxx___xxxxxxx_ +_____xxxxxxxxxxxxxxxxxxxx__xxxxxxx_|_____xxxxxxxxxxxxxxxxxxxx__xxxxxxx_ +_xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx_|_xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx_ +_____xxxxxxxxxxxxxxxxxxxxx_xxxxx___|_____xxxxxxxxxxxxxxxxxxxxx_xxxxx___ +_________xxxxxxxxxxxxxxxx___xxx____|_________xxxxxxxxxxxxxxxx___xxx____ +_____________xxxxxxxxxxxx__________|_____________xxxxxxxxxxxx____x_____ +__________________xxxxxxx___xx_____|__________________xxxxxxx___xx_____ +______________________xx___xxxx____|______________________xx___xxxx____ +________________________x_xxxxxx___|________________________x_xxxxxx___ +_______________________x______xxx__|_______________________x______xxx__ +___________________________________|___________________________________ +___________________________________|___________________________________ +*/ +{ SkPath::kEvenOdd_FillType, 1, 7, 8, 15, 3, 11, 11, 14 }, +/* +___________________________________|___________________________________ +____________x____________________x_|____________x____________________x_ +_____________xxx_________________x_|_____________xxx_________________x_ +______________xxxxx_____________xx_|______________xxxxx_____________xx_ +_______________xxxxxxx__________xx_|_______________xxxxxxx__________xx_ +________________xxxxxxxx________xx_|________________xxxxxxxx________xx_ +_________________xxxxxxxxxx____xxx_|_________________xxxxxxxxxx____xxx_ +__________________xxxxxxxxxxxx_xxx_|__________________xxxxxxxxxxxx_xxx_ +___________________xxxxxxxxxxx___x_|___________________xxxxxxxxxxx___x_ +____________________xxxxxxxxxx_xxx_|____________________xxxxxxxxxx_xxx_ +_____________________xxxxx___xxxxx_|_____________________xxxxx___xxxxx_ +_____________________________xxxxx_|_____________________________xxxxx_ +__________________xxxxx_____xxxxxx_|__________________xxxxx_____xxxxxx_ +______________xxxxxxxxxx____xxxxxx_|______________xxxxxxxxxx____xxxxxx_ +__________xxxxxxxxxxxxxx___xxxxxxx_|__________xxxxxxxxxxxxxx___xxxxxxx_ +_____xxxxxxxxxxxxxxxxxxxx__xxxxxxx_|_____xxxxxxxxxxxxxxxxxxxx__xxxxxxx_ +_xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx_|_xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx_ +_____xxxxxxxxxxxxxxxxxxxxx_xxxxx___|_____xxxxxxxxxxxxxxxxxxxxx_xxxxx___ +_________xxxxxxxxxxxxxxxx___xxx____|_________xxxxxxxxxxxxxxxx___xxx____ +_____________xxxxxxxxxxxx__________|_____________xxxxxxxxxxxx____x_____ +__________________xxxxxxx___xx_____|__________________xxxxxxx___xx_____ +______________________xx___xxxx____|______________________xx___xxxx____ +________________________x_xxxxxx___|________________________x_xxxxxx___ +_______________________x______xxx__|_______________________x______xxx__ +___________________________________|___________________________________ +___________________________________|___________________________________ +*/ +{ SkPath::kEvenOdd_FillType, 1, 7, 8, 15, 3, 11, 14, 14 }, +/* +___________________________________|___________________________________ +_____________xxxxxxxxxxxxxxxxxxx___|_____________xxxxxxxxxxxxxxxxxxx___ +___________xx___xxxxxxxxxxx________|___________xx___xxxxxxxxxxx________ +___________xxx_____xxxx____________|___________xxx_____xxxx____________ +__________xxxxx____xxx_____________|__________xxxxx____xxx_____________ +__________xxxxx_xxxxxxxx___________|__________xxxxx_xxxxxxxxx__________ +_________xx______xxxxxxxxxx________|_________x_______xxxxxxxxxx________ +______xxx_________xxxxxxxxxxxx_____|______xxx_________xxxxxxxxxxxx_____ +__xxxxxx___________xxxxxxxxxxxxxx__|__xxxxxx___________xxxxxxxxxxxxxx__ +___xxxxx____________xxxxxxxxxxxx___|___xxxxx____________xxxxxxxxxxxx___ +_____xx______________xxxxxxxxx_____|_____xx______________xxxxxxxxx_____ +______________________xxxxxx_______|______________________xxxxxx_______ +_______xx______________xxx_________|_______xx______________xxx_________ +______xxxxx________________________|______xxxxx________________________ +______xxxxxxx_________xx___________|______xxxxxxx_________xxx__________ +_____xxxxxxxxxx____xxxxxx__________|_____xxxxxxxxxx____xxxxxx__________ +_____xxxxxxxxxxxxxxxxxxxxx_________|_____xxxxxxxxxxxxxxxxxxxxx_________ +____xxxxxxxxxxx____xxxxxxxx________|____xxxxxxxxxxx____xxxxxxxx________ +____xxxxxxxxx________xxxxxxx_______|____xxxxxxxxx________xxxxxxx_______ +___xxxxxxxx_____________xxxxx______|___xxxxxxxx_____________xxxxx______ +___xxxxxx_________________xxxx_____|___xxxxxx_________________xxxx_____ +__xxxxx_____________________xxx____|__xxxxx_____________________xxx____ +__xxx_________________________xx___|__xxx_________________________xx___ +_xx_____________________________x__|_xx_____________________________x__ +___________________________________|___________________________________ +___________________________________|___________________________________ +*/ +{ SkPath::kEvenOdd_FillType, 1, 7, 12, 12, 1, 3, 4, 15 }, +/* +___________________________________|___________________________________ +____________x__________xxxxxxxxxx__|____________x__________xxxxxxxxxx__ +_____________x_________xxxxxxxxx___|_____________x_________xxxxxxxxx___ +______________x_________xxxxxx_____|______________x_________xxxxxx_____ +_______________xx_______xxxxx______|_______________xx_______xxxxx______ +________________xx_______xx________|________________xx_______xx________ +_________________xxx_____x_________|_________________xxx_____x_________ +__________________xxx____x_________|__________________xxx____x_________ +___________________xxx_xxx_________|___________________xxx_xxx_________ +____________________x_xxxxx________|____________________x_xxxxx________ +__________________xx_xxxxxx________|__________________xx_xxxxxx________ +_______________xxxx___xxxxxx_______|_______________xxxx___xxxxxx_______ +____________xxxxxx_____xxxxx_______|____________xxxxxx_____xxxxx_______ +_________xxxxxxx________xxxxx______|_________xxxxxxx________xxxxx______ +_______xxxxxxxx_________xxxxx______|_______xxxxxxxx__________xxxx______ +____xxxxxxxxx____________xxxxx_____|____xxxxxxxxx____________xxxxx_____ +_xxxxxxxxxxx______________xxxx_____|_xxxxxxxxxxx______________xxxx_____ +_____xxxxxx________________xxx_____|_____xxxxxx________________xxx_____ +____________________________xxx____|____________________________xxx____ +________xxxxx________________xx____|________xxxxx________________xx____ +______xxxxxxxxxxxx____________xx___|______xxxxxxxxxxxx____________xx___ +_____xxxxxxxxxxxxxxxxx_________x___|_____xxxxxxxxxxxxxxxxx_________x___ +____xxxxxxxxxxxxxxxxxxxxxx______x__|____xxxxxxxxxxxxxxxxxxxxxx______x__ +__xxxxxxxxxxxxxxxxxxxxxxxxxxxx_____|__xxxxxxxxxxxxxxxxxxxxxxxxxxxx_____ +___________________________________|___________________________________ +___________________________________|___________________________________ +*/ +{ SkPath::kEvenOdd_FillType, 2, 3, 12, 15, 1, 6, 8, 15 }, +/* +___________________________________|___________________________________ +_xx__________________x_____________|_xx__________________x_____________ +__xxxxx____________xx______________|__xxxxx____________xx______________ +__xxxxxxxxxx____xxxx_______________|__xxxxxxxxxx____xxxx_______________ +___xxxxxxxxxx___xxx________________|___xxxxxxxxxx___xxx________________ +___xxxxxxx_________x_______________|___xxxxxxx_________x_______________ +____xxx___________xxxxxx___________|____xxx___________xxxxxx___________ +____x____________xxxxxxxxxxx_______|____x____________xxxxxxxxxxx_______ +__xx____________xxxxxxxxxxxxxxxxx__|__xxx___________xxxxxxxxxxxxxxxxx__ +__xxx__________xxxxxxxxxxxxxxxx____|__xxx__________xxxxxxxxxxxxxxxx____ +___xx_________xxxxxxxxxxxx_________|___xx_________xxxxxxxxxxxx_________ +_____x_______xxxxxxxxx_____________|_____x_______xxxxxxxxx_____________ +____________xxxxxx_________________|____________xxxxxx_________________ +_______x___xxx_____________________|_______x___xxx_____________________ +_______xx__________________________|_______xx__________________________ +_____xxx_x_________________________|_____xxx_x_________________________ +_xxxxxxxxxxx_______________________|_xxxxxxxxxxx_______________________ +__xxxxx__xx________________________|__xxxxx__xx________________________ +____xx_____________________________|____xx_____________________________ +________xx_________________________|________xx_________________________ +_____x_xxx_________________________|_____x_xxx_________________________ +____x___xxx________________________|____x___xxx________________________ +___x_____xx________________________|___x_____xx________________________ +___________________________________|___________________________________ +___________________________________|___________________________________ +___________________________________|___________________________________ +*/ +{ SkPath::kWinding_FillType, 2, 4, 9, 12, 0, 7, 8, 13 }, +/* +___________________________________|___________________________________ +_xx__________________x_____________|_xx__________________x_____________ +__xxxxx____________xx______________|__xxxxx____________xx______________ +__xxxxxxxxxx____xxxx_______________|__xxxxxxxxxx____xxxx_______________ +___xxxxxxxxxx___xxx________________|___xxxxxxxxxx___xxx________________ +___xxxxxxx_________x_______________|___xxxxxxx_________x_______________ +____xxx___________xxxxxx___________|____xxx___________xxxxxx___________ +____x____________xxxxxxxxxxx_______|____x____________xxxxxxxxxxx_______ +__xx____________xxxxxxxxxxxxxxxxx__|__xxx___________xxxxxxxxxxxxxxxxx__ +__xxx__________xxxxxxxxxxxxxxxx____|__xxx__________xxxxxxxxxxxxxxxx____ +___xx_________xxxxxxxxxxxx_________|___xx_________xxxxxxxxxxxx_________ +_____x_______xxxxxxxxx_____________|_____x_______xxxxxxxxx_____________ +____________xxxxxx_________________|____________xxxxxx_________________ +_______x___xxx_____________________|_______x___xxx_____________________ +_______xx__________________________|_______xx__________________________ +_____xxx_x_________________________|_____xxx_x_________________________ +_xxxxxxxxxxx_______________________|_xxxxxxxxxxx_______________________ +__xxxxx__xx________________________|__xxxxx__xx________________________ +____xx_____________________________|____xx_____________________________ +________xx_________________________|________xx_________________________ +_____x_xxx_________________________|_____x_xxx_________________________ +____x___xxx________________________|____x___xxx________________________ +___x_____xx________________________|___x_____xx________________________ +___________________________________|___________________________________ +___________________________________|___________________________________ +___________________________________|___________________________________ +*/ +{ SkPath::kEvenOdd_FillType, 2, 4, 9, 12, 0, 7, 8, 13 }, +/* +___________________________________|___________________________________ +____________x________x_____________|____________x________x_____________ +_____________x_____xx______________|_____________x_____xx______________ +______________x_xxxx_______________|______________x_xxxx_______________ +_____________xx__xx________________|_____________xx__xx________________ +__________xxxxxx__x________________|__________xxxxxx__x________________ +_______xxxxxxxxxx_xx_______________|_______xxxxxxxxxx_xx_______________ +_____xxxxxxxxxxxx_xxx______________|_____xxxxxxxxxxxx_xxx______________ +__xxxxxxxxxxxxxx___xxx_____________|__xxxxxxxxxxxxxx___xxx_____________ +____xxxxxxxxxxx_____xx_____________|____xxxxxxxxxxx_____xx_____________ +________xxxxxx______x______________|________xxxxxx______x______________ +____________x______xxx_____________|____________x______xxx_____________ +____________xxxxx_xxxxx____________|____________xxxxx_xxxxx____________ +___________xxxxx_____xxx___________|___________xxxxx_____xxx___________ +__________xxxxx_________x__________|__________xxxxx____________________ +_________xxxx____________xxxx______|_________xxxx____________xxxx______ +________xxxx______________xxxxxxxx_|________xxxx______________xxxxxxxx_ +_______xxxxxxxx____________xxx_____|_______xxxxxxxx____________xxx_____ +______xxxxxxxxxxx________xxx_______|______xxxxxxxxxxx________xxx_______ +_____xxxxxxxxxxxxxxx_xxxxxxxx______|_____xxxxxxxxxxxxxxx_xxxxxxxx______ +_____xxxxxxxxxxxx______xxxxxxx_____|_____xxxxxxxxxxxx______xxxxxxx_____ +____xxxxxxxxx_____________xxxxx____|____xxxxxxxxx_____________xxxxx____ +___xxxxxx____________________xxx___|___xxxxxx____________________xxx___ +__xx___________________________xx__|__xx___________________________xx__ +___________________________________|___________________________________ +___________________________________|___________________________________ +*/ +{ SkPath::kWinding_FillType, 2, 4, 11, 12, 1, 6, 9, 15 }, +/* +___________________________________|___________________________________ +____________x________x_____________|____________x________x_____________ +_____________x_____xx______________|_____________x_____xx______________ +______________x_xxxx_______________|______________x_xxxx_______________ +_____________xx__xx________________|_____________xx__xx________________ +__________xxxxxx__x________________|__________xxxxxx__x________________ +_______xxxxxxxxxx_xx_______________|_______xxxxxxxxxx_xx_______________ +_____xxxxxxxxxxxx_xxx______________|_____xxxxxxxxxxxx_xxx______________ +__xxxxxxxxxxxxxx___xxx_____________|__xxxxxxxxxxxxxx___xxx_____________ +____xxxxxxxxxxx_____xx_____________|____xxxxxxxxxxx_____xx_____________ +________xxxxxx______x______________|________xxxxxx______x______________ +____________x______xxx_____________|____________x______xxx_____________ +____________xxxxx_xxxxx____________|____________xxxxx_xxxxx____________ +___________xxxxx_____xxx___________|___________xxxxx_____xxx___________ +__________xxxxx_________x__________|__________xxxxx____________________ +_________xxxx____________xxxx______|_________xxxx____________xxxx______ +________xxxx______________xxxxxxxx_|________xxxx______________xxxxxxxx_ +_______xxxxxxxx____________xxx_____|_______xxxxxxxx____________xxx_____ +______xxxxxxxxxxx________xxx_______|______xxxxxxxxxxx________xxx_______ +_____xxxxxxxxxxxxxxx_xxxxxxxx______|_____xxxxxxxxxxxxxxx_xxxxxxxx______ +_____xxxxxxxxxxxx______xxxxxxx_____|_____xxxxxxxxxxxx______xxxxxxx_____ +____xxxxxxxxx_____________xxxxx____|____xxxxxxxxx_____________xxxxx____ +___xxxxxx____________________xxx___|___xxxxxx____________________xxx___ +__xx___________________________xx__|__xx___________________________xx__ +___________________________________|___________________________________ +___________________________________|___________________________________ +*/ +{ SkPath::kEvenOdd_FillType, 2, 4, 11, 12, 1, 6, 9, 15 }, +/* +___________________________________|___________________________________ +____________xxxxxxxxxxxxxxxxxxxxx__|____________xxxxxxxxxxxxxxxxxxxxx__ +_____________xxxxxxxxxxxxxxxxxxx___|_____________xxxxxxxxxxxxxxxxxxx___ +______________xxxxxxxxx_xxxxxx_____|______________xxxxxxxxx_xxxxxx_____ +_______________xxxxxxxx_xxxxx______|_______________xxxxxxxx_xxxxx______ +________________xxxxxxx__xx________|________________xxxxxxx__xx________ +_________________xxxxxx__x_________|_________________xxxxxx__x_________ +__________________xxxxx__x_________|__________________xxxxx__x_________ +___________________xxxxxxx_________|___________________xxxxxxx_________ +____________________x_xxxxx________|____________________x_xxxxx________ +__________________xx_xxxxxx________|__________________xx_xxxxxx________ +_______________xxxx___xxxxxx_______|_______________xxxx___xxxxxx_______ +____________xxxxxx_____xxxxx_______|____________xxxxxx_____xxxxx_______ +_________xxxxxxx________xxxxx______|_________xxxxxxx________xxxxx______ +_______xxxxxxxx_________xxxxx______|_______xxxxxxxx__________xxxx______ +____xxxxxxxxx____________xxxxx_____|____xxxxxxxxx____________xxxxx_____ +_xxxxxxxxxxx______________xxxx_____|_xxxxxxxxxxx______________xxxx_____ +_____xxxxxx________________xxx_____|_____xxxxxx________________xxx_____ +____________________________xxx____|____________________________xxx____ +________xxxxx________________xx____|________xxxxx________________xx____ +______xxxxxxxxxxxx____________xx___|______xxxxxxxxxxxx____________xx___ +_____xxxxxxxxxxxxxxxxx_________x___|_____xxxxxxxxxxxxxxxxx_________x___ +____xxxxxxxxxxxxxxxxxxxxxx______x__|____xxxxxxxxxxxxxxxxxxxxxx______x__ +__xxxxxxxxxxxxxxxxxxxxxxxxxxxx_____|__xxxxxxxxxxxxxxxxxxxxxxxxxxxx_____ +___________________________________|___________________________________ +___________________________________|___________________________________ +*/ +{ SkPath::kEvenOdd_FillType, 2, 6, 8, 15, 1, 3, 12, 15 }, +/* +___________________________________|___________________________________ +____________x____________________x_|____________x____________________x_ +_____________xxx_________________x_|_____________xxx_________________x_ +______________xxxxx_____________xx_|______________xxxxx_____________xx_ +_______________xxxxxxx__________xx_|_______________xxxxxxx__________xx_ +________________xxxxxxxx________xx_|________________xxxxxxxx________xx_ +_________________xxxxxxxxxx____xxx_|_________________xxxxxxxxxx____xxx_ +__________________xxxxxxxxxxxx_xxx_|__________________xxxxxxxxxxxx_xxx_ +___________________xxxxxxxxxxx___x_|___________________xxxxxxxxxxx___x_ +____________________xxxxxxxxxx_xxx_|____________________xxxxxxxxxx_xxx_ +_____________________xxxxx___xxxxx_|_____________________xxxxx___xxxxx_ +_____________________________xxxxx_|_____________________________xxxxx_ +__________________xxxxx_____xxxxxx_|__________________xxxxx_____xxxxxx_ +______________xxxxxxxxxx____xxxxxx_|______________xxxxxxxxxx____xxxxxx_ +__________xxxxxxxxxxxxxx___xxxxxxx_|__________xxxxxxxxxxxxxx___xxxxxxx_ +_____xxxxxxxxxxxxxxxxxxxx__xxxxxxx_|_____xxxxxxxxxxxxxxxxxxxx__xxxxxxx_ +_xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx_|_xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx_ +_____xxxxxxxxxxxxxxxxxxxxx_xxxxx___|_____xxxxxxxxxxxxxxxxxxxxx_xxxxx___ +_________xxxxxxxxxxxxxxxx___xxx____|_________xxxxxxxxxxxxxxxx___xxx____ +_____________xxxxxxxxxxxx__________|_____________xxxxxxxxxxxx____x_____ +__________________xxxxxxx___xx_____|__________________xxxxxxx___xx_____ +______________________xx___xxxx____|______________________xx___xxxx____ +________________________x_xxxxxx___|________________________x_xxxxxx___ +_______________________x______xxx__|_______________________x______xxx__ +___________________________________|___________________________________ +___________________________________|___________________________________ +*/ +{ SkPath::kEvenOdd_FillType, 3, 3, 11, 14, 1, 7, 8, 15 }, +/* +___________________________________|___________________________________ +____________x___________________x__|____________x___________________x__ +_____________xxx___________xxxxxx__|_____________xxx___________xxxxxx__ +______________xxxxx____xxxxxxxxx___|______________xxxxx____xxxxxxxxx___ +_______________xxxx___xxxxxxxxxx___|_______________xxxx___xxxxxxxxxx___ +_______________x________xxxxxxxx___|_______________x_________xxxxxxx___ +___________xxxxxx__________xxxx____|___________xxxxxx__________xxxx____ +______xxxxxxxxxxxx____________x____|______xxxxxxxxxxxx____________x____ +__xxxxxxxxxxxxxxxxx___________xxx__|__xxxxxxxxxxxxxxxxx___________xxx__ +____xxxxxxxxxxxxxxxx__________x____|____xxxxxxxxxxxxxxxx__________x____ +________xxxxxxxxxxxxx_____xxx______|________xxxxxxxxxxxxx_____xxx______ +____________xxxxxxxxxxxxxxxxx______|_____________xxxxxxxxxxxxxxxx______ +_________________xxxxxxxxxxx_______|_________________xxxxxxxxxxx_______ +______________xxxxxxxxxxxxxx_______|______________xxxxxxxxxxxxxx_______ +__________xxxxxxxxxxxxxx_xx________|__________xxxxxxxxxxxxxxxxx________ +_____xxxxxxxxxxxxxxxxxxxx__xx______|_____xxxxxxxxxxxxxxxxxxxx__xx______ +_xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx_|_xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx_ +_____xxxxxxxxxxxxxxxxxxxxx_xxxxx___|_____xxxxxxxxxxxxxxxxxxxxx_xxxxx___ +_________xxxxxxxxxxxxxxxx___xxx____|_________xxxxxxxxxxxxxxxx___xxx____ +_____________xxxxxxxxxxxx__________|_____________xxxxxxxxxxxx____x_____ +__________________xxxxxxx___xx_____|__________________xxxxxxx___xx_____ +______________________xx___xxxx____|______________________xx___xxxx____ +________________________x_xxxxxx___|________________________x_xxxxxx___ +_______________________x______xxx__|_______________________x______xxx__ +___________________________________|___________________________________ +___________________________________|___________________________________ +*/ +{ SkPath::kWinding_FillType, 3, 4, 11, 14, 1, 7, 8, 15 }, +/* +___________________________________|___________________________________ +____________x___________________x__|____________x___________________x__ +_____________xxx___________xxxxxx__|_____________xxx___________xxxxxx__ +______________xxxxx____xxxxxxxxx___|______________xxxxx____xxxxxxxxx___ +_______________xxxx___xxxxxxxxxx___|_______________xxxx___xxxxxxxxxx___ +_______________x________xxxxxxxx___|_______________x_________xxxxxxx___ +___________xxxxxx__________xxxx____|___________xxxxxx__________xxxx____ +______xxxxxxxxxxxx____________x____|______xxxxxxxxxxxx____________x____ +__xxxxxxxxxxxxxxxxx___________xxx__|__xxxxxxxxxxxxxxxxx___________xxx__ +____xxxxxxxxxxxxxxxx__________x____|____xxxxxxxxxxxxxxxx__________x____ +________xxxxxxxxxxxxx_____xxx______|________xxxxxxxxxxxxx_____xxx______ +____________xxxxxxxxxxxxxxxxx______|_____________xxxxxxxxxxxxxxxx______ +_________________x_____xxxxx_______|_________________x_____xxxxx_______ +______________xxxxxxx___xxxx_______|______________xxxxxxx___xxxx_______ +__________xxxxxxxxxxxxxx_xx________|__________xxxxxxxxxxxxxxxxx________ +_____xxxxxxxxxxxxxxxxxxxx__xx______|_____xxxxxxxxxxxxxxxxxxxx__xx______ +_xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx_|_xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx_ +_____xxxxxxxxxxxxxxxxxxxxx_xxxxx___|_____xxxxxxxxxxxxxxxxxxxxx_xxxxx___ +_________xxxxxxxxxxxxxxxx___xxx____|_________xxxxxxxxxxxxxxxx___xxx____ +_____________xxxxxxxxxxxx__________|_____________xxxxxxxxxxxx____x_____ +__________________xxxxxxx___xx_____|__________________xxxxxxx___xx_____ +______________________xx___xxxx____|______________________xx___xxxx____ +________________________x_xxxxxx___|________________________x_xxxxxx___ +_______________________x______xxx__|_______________________x______xxx__ +___________________________________|___________________________________ +___________________________________|___________________________________ +*/ +{ SkPath::kEvenOdd_FillType, 3, 4, 11, 14, 1, 7, 8, 15 }, +/* +___________________________________|___________________________________ +____________x______________________|____________x______________________ +_____________xxx________________x__|_____________xxx________________x__ +______________xxxxx___________xx___|______________xxxxx___________xx___ +_______________xxxxxxx_______xxx___|_______________xxxxxxx_______xxx___ +________________xxxxxxxx___xxxxx___|________________xxxxxxxxx__xxxxx___ +_________________xxxxxxxxx_xxxx____|_________________xxxxxxxxx_xxxx____ +__________________xxxxxxx_____x____|__________________xxxxxxx_____x____ +___________________xxxx_______xxx__|___________________xxxx_______xxx__ +____________________xxxx______x____|____________________xxxx______x____ +_____________________xxxx_xxx______|_____________________xxxx_xxx______ +___________________________xx______|___________________________xx______ +__________________xxxxx____________|__________________xxxxx____________ +______________xxxxxxxxxx____x______|______________xxxxxxxxxx____x______ +__________xxxxxxxxxxxxxx___xxxx____|__________xxxxxxxxxxxxxx___xxxx____ +_____xxxxxxxxxxxxxxxxxxxx__xxxxx___|_____xxxxxxxxxxxxxxxxxxxx__xxxxx___ +_xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx_|_xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx_ +_____xxxxxxxxxxxxxxxxxxxxx_xxxxx___|_____xxxxxxxxxxxxxxxxxxxxx_xxxxx___ +_________xxxxxxxxxxxxxxxx___xxx____|_________xxxxxxxxxxxxxxxx___xxx____ +_____________xxxxxxxxxxxx__________|_____________xxxxxxxxxxxx____x_____ +__________________xxxxxxx___xx_____|__________________xxxxxxx___xx_____ +______________________xx___xxxx____|______________________xx___xxxx____ +________________________x_xxxxxx___|________________________x_xxxxxx___ +_______________________x______xxx__|_______________________x______xxx__ +___________________________________|___________________________________ +___________________________________|___________________________________ +*/ +{ SkPath::kWinding_FillType, 3, 6, 11, 14, 1, 7, 8, 15 }, +/* +___________________________________|___________________________________ +____________x______________________|____________x______________________ +_____________xxx________________x__|_____________xxx________________x__ +______________xxxxx___________xx___|______________xxxxx___________xx___ +_______________xxxxxxx_______xxx___|_______________xxxxxxx_______xxx___ +________________xxxxxxxx___xxxxx___|________________xxxxxxxxx__xxxxx___ +_________________xxxxxxxxx_xxxx____|_________________xxxxxxxxx_xxxx____ +__________________xxxxxxx_____x____|__________________xxxxxxx_____x____ +___________________xxxx_______xxx__|___________________xxxx_______xxx__ +____________________xxxx______x____|____________________xxxx______x____ +_____________________xxxx_xxx______|_____________________xxxx_xxx______ +___________________________xx______|___________________________xx______ +__________________xxxxx____________|__________________xxxxx____________ +______________xxxxxxxxxx____x______|______________xxxxxxxxxx____x______ +__________xxxxxxxxxxxxxx___xxxx____|__________xxxxxxxxxxxxxx___xxxx____ +_____xxxxxxxxxxxxxxxxxxxx__xxxxx___|_____xxxxxxxxxxxxxxxxxxxx__xxxxx___ +_xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx_|_xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx_ +_____xxxxxxxxxxxxxxxxxxxxx_xxxxx___|_____xxxxxxxxxxxxxxxxxxxxx_xxxxx___ +_________xxxxxxxxxxxxxxxx___xxx____|_________xxxxxxxxxxxxxxxx___xxx____ +_____________xxxxxxxxxxxx__________|_____________xxxxxxxxxxxx____x_____ +__________________xxxxxxx___xx_____|__________________xxxxxxx___xx_____ +______________________xx___xxxx____|______________________xx___xxxx____ +________________________x_xxxxxx___|________________________x_xxxxxx___ +_______________________x______xxx__|_______________________x______xxx__ +___________________________________|___________________________________ +___________________________________|___________________________________ +*/ +{ SkPath::kEvenOdd_FillType, 3, 6, 11, 14, 1, 7, 8, 15 }, +/* +___________________________________|___________________________________ +____________x____________________x_|____________x____________________x_ +_____________xxx_________________x_|_____________xxx_________________x_ +______________xxxxx_____________xx_|______________xxxxx_____________xx_ +_______________xxxxxxx__________xx_|_______________xxxxxxx__________xx_ +________________xxxxxxxx________xx_|________________xxxxxxxx________xx_ +_________________xxxxxxxxxx____xxx_|_________________xxxxxxxxxx____xxx_ +__________________xxxxxxxxxxxx_xxx_|__________________xxxxxxxxxxxx_xxx_ +___________________xxxxxxxxxxx___x_|___________________xxxxxxxxxxx___x_ +____________________xxxxxxxxxx_xxx_|____________________xxxxxxxxxx_xxx_ +_____________________xxxxx___xxxxx_|_____________________xxxxx___xxxxx_ +_____________________________xxxxx_|_____________________________xxxxx_ +__________________xxxxx_____xxxxxx_|__________________xxxxx_____xxxxxx_ +______________xxxxxxxxxx____xxxxxx_|______________xxxxxxxxxx____xxxxxx_ +__________xxxxxxxxxxxxxx___xxxxxxx_|__________xxxxxxxxxxxxxx___xxxxxxx_ +_____xxxxxxxxxxxxxxxxxxxx__xxxxxxx_|_____xxxxxxxxxxxxxxxxxxxx__xxxxxxx_ +_xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx_|_xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx_ +_____xxxxxxxxxxxxxxxxxxxxx_xxxxx___|_____xxxxxxxxxxxxxxxxxxxxx_xxxxx___ +_________xxxxxxxxxxxxxxxx___xxx____|_________xxxxxxxxxxxxxxxx___xxx____ +_____________xxxxxxxxxxxx__________|_____________xxxxxxxxxxxx____x_____ +__________________xxxxxxx___xx_____|__________________xxxxxxx___xx_____ +______________________xx___xxxx____|______________________xx___xxxx____ +________________________x_xxxxxx___|________________________x_xxxxxx___ +_______________________x______xxx__|_______________________x______xxx__ +___________________________________|___________________________________ +___________________________________|___________________________________ +*/ +{ SkPath::kEvenOdd_FillType, 3, 7, 11, 14, 1, 7, 8, 15 }, +/* +___________________________________|___________________________________ +____________x______________________|____________x______________________ +_____________xxx___________________|_____________xxx___________________ +______________xxxxx________________|______________xxxxx________________ +_______________xxxxxxx_________x___|_______________xxxxxxx_________x___ +________________xxxxxxxx______xx___|________________xxxxxxxxx_____xx___ +_________________xxxxxxxxxx___x____|_________________xxxxxxxxxx___x____ +__________________xxxxxxxxxxx_x____|__________________xxxxxxxxxxx_x____ +___________________xxxxxxxxx__xxx__|___________________xxxxxxxxx__xxx__ +____________________xxxxxxxx__x____|____________________xxxxxxxx__x____ +_____________________xxxxx_xx______|_____________________xxxxx_xx______ +__________________________xxx______|__________________________xxx______ +__________________xxxxx___xx_______|__________________xxxxx___xx_______ +______________xxxxxxxxxx_xxx_______|______________xxxxxxxxxx_xxx_______ +__________xxxxxxxxxxxxxxxxx________|__________xxxxxxxxxxxxxxxxx________ +_____xxxxxxxxxxxxxxxxxxxxxx________|_____xxxxxxxxxxxxxxxxxxxxxx________ +_xxxxxxxxxxxxxxxxxxxxxxxxx_________|_xxxxxxxxxxxxxxxxxxxxxxxxx_________ +_____xxxxxxxxxxxxxxxxxxxxx_xxxxx___|_____xxxxxxxxxxxxxxxxxxxxx_xxxxx___ +_________xxxxxxxxxxxxxxxx___xxx____|_________xxxxxxxxxxxxxxxx___xxx____ +_____________xxxxxxxxxxxx__________|_____________xxxxxxxxxxxx____x_____ +__________________xxxxxxx___xx_____|__________________xxxxxxx___xx_____ +______________________xx___xxxx____|______________________xx___xxxx____ +________________________x_xxxxxx___|________________________x_xxxxxx___ +_______________________x______xxx__|_______________________x______xxx__ +___________________________________|___________________________________ +___________________________________|___________________________________ +*/ +{ SkPath::kWinding_FillType, 3, 10, 11, 14, 1, 7, 8, 15 }, +/* +___________________________________|___________________________________ +____________x______________________|____________x______________________ +_____________xxx___________________|_____________xxx___________________ +______________xxxxx________________|______________xxxxx________________ +_______________xxxxxxx_________x___|_______________xxxxxxx_________x___ +________________xxxxxxxx______xx___|________________xxxxxxxxx_____xx___ +_________________xxxxxxxxxx___x____|_________________xxxxxxxxxx___x____ +__________________xxxxxxxxxxx_x____|__________________xxxxxxxxxxx_x____ +___________________xxxxxxxxx__xxx__|___________________xxxxxxxxx__xxx__ +____________________xxxxxxxx__x____|____________________xxxxxxxx__x____ +_____________________xxxxx_xx______|_____________________xxxxx_xx______ +__________________________xxx______|__________________________xxx______ +__________________xxxxx___xx_______|__________________xxxxx___xx_______ +______________xxxxxxxxxx_xxx_______|______________xxxxxxxxxx_xxx_______ +__________xxxxxxxxxxxxxxxxx________|__________xxxxxxxxxxxxxx_xx________ +_____xxxxxxxxxxxxxxxxxx__xx________|_____xxxxxxxxxxxxxxxxxx__xx________ +_xxxxxxxxxxxxxxxxxxxxxx____________|_xxxxxxxxxxxxxxxxxxxxxx____________ +_____xxxxxxxxxxxxxxxxxxxxx_xxxxx___|_____xxxxxxxxxxxxxxxxxxxxx_xxxxx___ +_________xxxxxxxxxxxxxxxx___xxx____|_________xxxxxxxxxxxxxxxx___xxx____ +_____________xxxxxxxxxxxx__________|_____________xxxxxxxxxxxx____x_____ +__________________xxxxxxx___xx_____|__________________xxxxxxx___xx_____ +______________________xx___xxxx____|______________________xx___xxxx____ +________________________x_xxxxxx___|________________________x_xxxxxx___ +_______________________x______xxx__|_______________________x______xxx__ +___________________________________|___________________________________ +___________________________________|___________________________________ +*/ +{ SkPath::kEvenOdd_FillType, 3, 10, 11, 14, 1, 7, 8, 15 }, +/* +___________________________________|___________________________________ +____________x____________________x_|____________x____________________x_ +_____________xxx_________________x_|_____________xxx_________________x_ +______________xxxxx_____________xx_|______________xxxxx_____________xx_ +_______________xxxxxxx__________xx_|_______________xxxxxxx__________xx_ +________________xxxxxxxx________xx_|________________xxxxxxxx________xx_ +_________________xxxxxxxxxx____xxx_|_________________xxxxxxxxxx____xxx_ +__________________xxxxxxxxxxxx_xxx_|__________________xxxxxxxxxxxx_xxx_ +___________________xxxxxxxxxxx___x_|___________________xxxxxxxxxxx___x_ +____________________xxxxxxxxxx_xxx_|____________________xxxxxxxxxx_xxx_ +_____________________xxxxx___xxxxx_|_____________________xxxxx___xxxxx_ +_____________________________xxxxx_|_____________________________xxxxx_ +__________________xxxxx_____xxxxxx_|__________________xxxxx_____xxxxxx_ +______________xxxxxxxxxx____xxxxxx_|______________xxxxxxxxxx____xxxxxx_ +__________xxxxxxxxxxxxxx___xxxxxxx_|__________xxxxxxxxxxxxxx___xxxxxxx_ +_____xxxxxxxxxxxxxxxxxxxx__xxxxxxx_|_____xxxxxxxxxxxxxxxxxxxx__xxxxxxx_ +_xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx_|_xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx_ +_____xxxxxxxxxxxxxxxxxxxxx_xxxxx___|_____xxxxxxxxxxxxxxxxxxxxx_xxxxx___ +_________xxxxxxxxxxxxxxxx___xxx____|_________xxxxxxxxxxxxxxxx___xxx____ +_____________xxxxxxxxxxxx__________|_____________xxxxxxxxxxxx____x_____ +__________________xxxxxxx___xx_____|__________________xxxxxxx___xx_____ +______________________xx___xxxx____|______________________xx___xxxx____ +________________________x_xxxxxx___|________________________x_xxxxxx___ +_______________________x______xxx__|_______________________x______xxx__ +___________________________________|___________________________________ +___________________________________|___________________________________ +*/ +{ SkPath::kEvenOdd_FillType, 3, 11, 11, 14, 1, 7, 8, 15 }, +/* +___________________________________|___________________________________ +____________x____________________x_|____________x____________________x_ +_____________xxx_________________x_|_____________xxx_________________x_ +______________xxxxx_____________xx_|______________xxxxx_____________xx_ +_______________xxxxxxx__________xx_|_______________xxxxxxx__________xx_ +________________xxxxxxxx________xx_|________________xxxxxxxx________xx_ +_________________xxxxxxxxxx____xxx_|_________________xxxxxxxxxx____xxx_ +__________________xxxxxxxxxxxx_xxx_|__________________xxxxxxxxxxxx_xxx_ +___________________xxxxxxxxxxx___x_|___________________xxxxxxxxxxx___x_ +____________________xxxxxxxxxx_xxx_|____________________xxxxxxxxxx_xxx_ +_____________________xxxxx___xxxxx_|_____________________xxxxx___xxxxx_ +_____________________________xxxxx_|_____________________________xxxxx_ +__________________xxxxx_____xxxxxx_|__________________xxxxx_____xxxxxx_ +______________xxxxxxxxxx____xxxxxx_|______________xxxxxxxxxx____xxxxxx_ +__________xxxxxxxxxxxxxx___xxxxxxx_|__________xxxxxxxxxxxxxx___xxxxxxx_ +_____xxxxxxxxxxxxxxxxxxxx__xxxxxxx_|_____xxxxxxxxxxxxxxxxxxxx__xxxxxxx_ +_xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx_|_xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx_ +_____xxxxxxxxxxxxxxxxxxxxx_xxxxx___|_____xxxxxxxxxxxxxxxxxxxxx_xxxxx___ +_________xxxxxxxxxxxxxxxx___xxx____|_________xxxxxxxxxxxxxxxx___xxx____ +_____________xxxxxxxxxxxx__________|_____________xxxxxxxxxxxx____x_____ +__________________xxxxxxx___xx_____|__________________xxxxxxx___xx_____ +______________________xx___xxxx____|______________________xx___xxxx____ +________________________x_xxxxxx___|________________________x_xxxxxx___ +_______________________x______xxx__|_______________________x______xxx__ +___________________________________|___________________________________ +___________________________________|___________________________________ +*/ +{ SkPath::kEvenOdd_FillType, 3, 11, 14, 14, 1, 7, 8, 15 }, +}; + +size_t misMatchCount = sizeof(misMatches) / sizeof(misMatches[0]); + +void TestMismatches(); + +void TestMismatches() { + for (size_t index = 0; index < misMatchCount; ++index) { + const misMatch& miss = misMatches[index]; + int ax = miss.a & 0x03; + int ay = miss.a >> 2; + int bx = miss.b & 0x03; + int by = miss.b >> 2; + int cx = miss.c & 0x03; + int cy = miss.c >> 2; + int dx = miss.d & 0x03; + int dy = miss.d >> 2; + int ex = miss.e & 0x03; + int ey = miss.e >> 2; + int fx = miss.f & 0x03; + int fy = miss.f >> 2; + int gx = miss.g & 0x03; + int gy = miss.g >> 2; + int hx = miss.h & 0x03; + int hy = miss.h >> 2; + SkPath path, out; + path.setFillType(miss.fType); + path.moveTo(ax, ay); + path.lineTo(bx, by); + path.lineTo(cx, cy); + path.lineTo(dx, dy); + path.close(); + path.moveTo(ex, ey); + path.lineTo(fx, fy); + path.lineTo(gx, gy); + path.lineTo(hx, hy); + path.close(); + testSimplify(path, true, out); + } +} diff --git a/experimental/Intersection/EdgeWalkerPolygons_Mismatches.h b/experimental/Intersection/EdgeWalkerPolygons_Mismatches.h new file mode 100644 index 0000000000..d0381723aa --- /dev/null +++ b/experimental/Intersection/EdgeWalkerPolygons_Mismatches.h @@ -0,0 +1,9 @@ +/* + * EdgeWalkerPolygons_Mismatches.h + * edge + * + * Created by Cary Clark on 3/6/12. + * Copyright 2012 __MyCompanyName__. All rights reserved. + * + */ + diff --git a/experimental/Intersection/EdgeWalkerPolygons_Test.cpp b/experimental/Intersection/EdgeWalkerPolygons_Test.cpp index 07ce6c8f8a..9a740e996b 100644 --- a/experimental/Intersection/EdgeWalkerPolygons_Test.cpp +++ b/experimental/Intersection/EdgeWalkerPolygons_Test.cpp @@ -12,8 +12,8 @@ static void testSimplifyTriangle() { path.lineTo(10,30); // /_| path.lineTo(20,30); path.close(); - simplify(path, true, out); // expect |\/| - comparePaths(path, out); // |__| + testSimplify(path, true, out); // expect |\/| + // |__| } static void testSimplifyTriangle3() { @@ -26,8 +26,7 @@ static void testSimplifyTriangle3() { path.lineTo(1, 0); path.lineTo(3, 1); path.close(); - simplify(path, true, out); - comparePaths(path, out); + testSimplify(path, true, out); } static void testSimplifyTriangle4() { @@ -40,8 +39,7 @@ static void testSimplifyTriangle4() { path.lineTo(1, 0); path.lineTo(2, 1); path.close(); - simplify(path, true, out); - comparePaths(path, out); + testSimplify(path, true, out); } static void testSimplifyTriangle5() { @@ -54,8 +52,7 @@ static void testSimplifyTriangle5() { path.lineTo(1, 1); path.lineTo(2, 1); path.close(); - simplify(path, true, out); - comparePaths(path, out); + testSimplify(path, true, out); } static void testSimplifyTriangle6() { @@ -70,8 +67,7 @@ static void testSimplifyTriangle6() { path.lineTo(3, 1); path.lineTo(0, 0); path.close(); - simplify(path, true, out); - comparePaths(path, out); + testSimplify(path, true, out); } static void testSimplifyTriangle7() { @@ -86,8 +82,7 @@ static void testSimplifyTriangle7() { path.lineTo(0, 2); path.lineTo(0, 0); path.close(); - simplify(path, true, out); - comparePaths(path, out); + testSimplify(path, true, out); } static void testSimplifyTriangle8() { @@ -102,8 +97,7 @@ static void testSimplifyTriangle8() { path.lineTo(1, 3); path.lineTo(0, 1); path.close(); - simplify(path, true, out); - comparePaths(path, out); + testSimplify(path, true, out); } static void testSimplifyTriangle9() { @@ -118,8 +112,7 @@ static void testSimplifyTriangle9() { path.lineTo(2, 1); path.lineTo(0, 0); path.close(); - simplify(path, true, out); - comparePaths(path, out); + testSimplify(path, true, out); } static void testSimplifyTriangle10() { @@ -134,8 +127,7 @@ static void testSimplifyTriangle10() { path.lineTo(0, 1); path.lineTo(0, 0); path.close(); - simplify(path, true, out); - comparePaths(path, out); + testSimplify(path, true, out); } static void testSimplifyTriangle11() { @@ -150,8 +142,7 @@ static void testSimplifyTriangle11() { path.lineTo(2, 2); path.lineTo(0, 0); path.close(); - simplify(path, true, out); - comparePaths(path, out); + testSimplify(path, true, out); } static void testSimplifyTriangle12() { @@ -166,8 +157,7 @@ static void testSimplifyTriangle12() { path.lineTo(1, 1); path.lineTo(2, 0); path.close(); - simplify(path, true, out); - comparePaths(path, out); + testSimplify(path, true, out); } static void testSimplifyTriangle13() { @@ -182,8 +172,7 @@ static void testSimplifyTriangle13() { path.lineTo(1, 1); path.lineTo(3, 0); path.close(); - simplify(path, true, out); - comparePaths(path, out); + testSimplify(path, true, out); } static void testSimplifyTriangle14() { @@ -198,8 +187,7 @@ static void testSimplifyTriangle14() { path.lineTo(0, 1); path.lineTo(0, 0); path.close(); - simplify(path, true, out); - comparePaths(path, out); + testSimplify(path, true, out); } static void testSimplifyTriangle15() { @@ -213,8 +201,7 @@ static void testSimplifyTriangle15() { path.lineTo(0, 1); path.lineTo(2, 2); path.close(); - simplify(path, true, out); - comparePaths(path, out); + testSimplify(path, true, out); } static void testSimplifyTriangle16() { @@ -227,8 +214,7 @@ static void testSimplifyTriangle16() { path.lineTo(0, 1); path.lineTo(1, 3); path.close(); - simplify(path, true, out); - comparePaths(path, out); + testSimplify(path, true, out); } static void testSimplifyTriangle17() { @@ -241,8 +227,7 @@ static void testSimplifyTriangle17() { path.lineTo(1, 3); path.lineTo(0, 1); path.close(); - simplify(path, true, out); - comparePaths(path, out); + testSimplify(path, true, out); } static void testSimplifyTriangle18() { @@ -255,8 +240,7 @@ static void testSimplifyTriangle18() { path.lineTo(0, 1); path.lineTo(0, 3); path.close(); - simplify(path, true, out); - comparePaths(path, out); + testSimplify(path, true, out); } static void testSimplifyTriangle19() { @@ -270,8 +254,7 @@ static void testSimplifyTriangle19() { path.lineTo(1, 1); path.lineTo(2, 1); path.close(); - simplify(path, true, out); - comparePaths(path, out); + testSimplify(path, true, out); } static void testSimplifyTriangle20() { @@ -284,8 +267,7 @@ static void testSimplifyTriangle20() { path.lineTo(3, 2); path.lineTo(0, 3); path.close(); - simplify(path, true, out); - comparePaths(path, out); + testSimplify(path, true, out); } static void testSimplifyTriangle21() { @@ -298,8 +280,7 @@ static void testSimplifyTriangle21() { path.lineTo(2, 1); path.lineTo(0, 3); path.close(); - simplify(path, true, out); - comparePaths(path, out); + testSimplify(path, true, out); } static void testSimplifyDegenerateTriangle1() { @@ -312,8 +293,7 @@ static void testSimplifyDegenerateTriangle1() { path.lineTo(0, 0); path.lineTo(0, 0); path.close(); - simplify(path, true, out); - comparePaths(path, out); + testSimplify(path, true, out); } static void testSimplifyDegenerateTriangle2() { @@ -326,8 +306,7 @@ static void testSimplifyDegenerateTriangle2() { path.lineTo(2, 2); path.lineTo(3, 3); path.close(); - simplify(path, true, out); - comparePaths(path, out); + testSimplify(path, true, out); } static void testSimplifyWindingParallelogram() { @@ -343,9 +322,9 @@ static void testSimplifyWindingParallelogram() { path.lineTo(20,30); // /_/ path.lineTo(30,10); path.close(); - simplify(path, true, out); // expect _ - comparePaths(path, out); // / \ . -} // /___\ . + testSimplify(path, true, out); // expect _ + // / \ . +} // /___\ . static void testSimplifyXorParallelogram() { SkPath path, out; @@ -360,9 +339,8 @@ static void testSimplifyXorParallelogram() { path.lineTo(20,30); // /_/ path.lineTo(30,10); path.close(); - simplify(path, true, out); // expect _ - comparePaths(path, out); // \ / -} // + testSimplify(path, true, out); // expect _ +} // \ / static void testSimplifyTriangle2() { SkPath path, out; @@ -374,10 +352,9 @@ static void testSimplifyTriangle2() { path.moveTo(10,10); // triangle _ path.lineTo(20,10); // \ | path.lineTo(20,30); // \| - path.close(); // _ - simplify(path, true, out); // expect | | - comparePaths(path, out); // |_| -} + path.close(); // _ + testSimplify(path, true, out); // expect | | +} // |_| static void testSimplifyNondegenerate4x4Triangles() { char pathStr[1024]; @@ -433,11 +410,9 @@ static void testSimplifyNondegenerate4x4Triangles() { str += sprintf(str, " path.lineTo(%d, %d);\n", fx, fy); str += sprintf(str, " path.close();"); } - simplify(path, true, out); - comparePaths(path, out); + testSimplify(path, true, out); path.setFillType(SkPath::kEvenOdd_FillType); - simplify(path, true, out); - comparePaths(path, out); + testSimplify(path, true, out); } } } @@ -494,11 +469,9 @@ static void testSimplifyDegenerate4x4Triangles() { str += sprintf(str, " path.lineTo(%d, %d);\n", fx, fy); str += sprintf(str, " path.close();"); } - simplify(path, true, out); - comparePaths(path, out); + testSimplify(path, true, out); path.setFillType(SkPath::kEvenOdd_FillType); - simplify(path, true, out); - comparePaths(path, out); + testSimplify(path, true, out); } } } @@ -527,7 +500,165 @@ static void testPathTriangleRendering() { } } +static void testSimplifySkinnyTriangle1() { + for (int x = 1; x < 255; ++x) { + SkPath path, out; + path.moveTo((x * 101) % 10, 0); + path.lineTo((x * 91) % 10, 1000); + path.lineTo((x * 71) % 10, 2000); + path.lineTo((x * 51) % 10, 3000); + path.close(); + path.moveTo((x * 101) % 20, 0); + path.lineTo((x * 91) % 20, 1000); + path.lineTo((x * 71) % 20, 2000); + path.lineTo((x * 51) % 20, 3000); + path.close(); + path.moveTo((x * 101) % 30, 0); + path.lineTo((x * 91) % 30, 1000); + path.lineTo((x * 71) % 30, 2000); + path.lineTo((x * 51) % 30, 3000); + path.close(); + testSimplify(path, true, out); + } +} + +static void testSimplifySkinnyTriangle2() { + SkPath path, out; +#if 01 +path.moveTo(591.091064, 627.534851); +path.lineTo(541.088135, 560.707642); +path.lineTo(491.085175, 493.880310); +path.lineTo(441.082214, 427.053101); +//path.lineTo(591.091064, 627.534851); +path.close(); +#endif +path.moveTo(317.093445, 592.013306); +path.lineTo(366.316162, 542.986572); +path.lineTo(416.051514, 486.978577); +path.lineTo(465.786865, 430.970581); +//path.lineTo(317.093445, 592.013306); +path.close(); +#if 0 +path.moveTo(289.392517, 517.138489); +path.lineTo(249.886078, 508.598022); +path.lineTo(217.110916, 450.916443); +path.lineTo(196.621033, 394.917633); +//path.lineTo(289.392517, 517.138489); +path.close(); +#endif + testSimplify(path, true, out); +} + +static void testSimplifySkinnyTriangle3() { + SkPath path, out; + path.moveTo(591, 627.534851); + path.lineTo(541, 560.707642); + path.lineTo(491, 493.880310); + path.lineTo(441, 427.053101); + path.close(); + path.moveTo(317, 592.013306); + path.lineTo(366, 542.986572); + path.lineTo(416, 486.978577); + path.lineTo(465, 430.970581); + path.close(); + testSimplify(path, true, out); +} + +static void testSimplifySkinnyTriangle4() { + SkPath path, out; +path.moveTo(572.655212, 614.959961); +path.lineTo(524.618896, 549.339600); +path.lineTo(476.582581, 483.719269); +path.lineTo(428.546265, 418.098938); +path.lineTo(572.655212, 614.959961); +path.close(); +path.moveTo(312.166382, 583.723083); +path.lineTo(361.047791, 529.824219); +path.lineTo(409.929230, 475.925354); +path.lineTo(458.810669, 422.026520); +path.lineTo(312.166382, 583.723083); +path.close(); +path.moveTo(278.742737, 508.065643); +path.lineTo(241.475800, 493.465118); +path.lineTo(210.344177, 437.315125); +path.lineTo(197.019455, 383.794556); +path.lineTo(278.742737, 508.065643); +path.close(); + testSimplify(path, true, out); +} + +static void testSimplifySkinnyTriangle5() { + SkPath path, out; +path.moveTo(554.690613, 602.286072); +path.lineTo(508.590057, 537.906250); +path.lineTo(462.489441, 473.526520); +path.lineTo(416.388855, 409.146729); +path.lineTo(554.690613, 602.286072); +path.close(); +path.moveTo(307.216949, 575.189270); +path.lineTo(355.826965, 516.804688); +path.lineTo(403.815918, 464.990753); +path.lineTo(451.804871, 413.176819); +path.lineTo(307.216949, 575.189270); +path.close(); +path.moveTo(271.998901, 521.301025); +path.lineTo(234.619705, 499.687683); +path.lineTo(203.059692, 441.332336); +path.lineTo(195.994370, 386.856506); +path.lineTo(271.998901, 521.301025); +path.close(); + testSimplify(path, true, out); +} + + +static void testSimplifyTriangle22() { + SkPath path, out; + path.moveTo(0, 0); + path.lineTo(1, 0); + path.lineTo(0, 2); + path.close(); + path.moveTo(1, 0); + path.lineTo(0, 2); + path.lineTo(0, 1); + path.close(); + testSimplify(path, true, out); +} + +static void testSimplifyTriangle23() { + SkPath path, out; + path.moveTo(0, 0); + path.lineTo(0, 0); + path.lineTo(0, 0); + path.close(); + path.moveTo(0, 0); + path.lineTo(0, 1); + path.lineTo(1, 2); + path.close(); + testSimplify(path, true, out); +} + +static void testSimplifyTriangle24() { + SkPath path, out; + path.moveTo(0, 0); + path.lineTo(0, 0); + path.lineTo(0, 1); + path.close(); + path.moveTo(0, 0); + path.lineTo(1, 0); + path.lineTo(0, 1); + path.close(); + testSimplify(path, true, out); +} + static void (*simplifyTests[])() = { + testSimplifySkinnyTriangle5, + testSimplifySkinnyTriangle4, + testSimplifySkinnyTriangle3, + testSimplifySkinnyTriangle2, + testSimplifySkinnyTriangle1, + testSimplifyTriangle24, + testSimplifyTriangle23, + testSimplifyTriangle22, testSimplifyDegenerateTriangle2, testSimplifyDegenerateTriangle1, testSimplifyTriangle21, @@ -560,7 +691,7 @@ static void (*simplifyTests[])() = { static size_t simplifyTestsCount = sizeof(simplifyTests) / sizeof(simplifyTests[0]); -static void (*firstTest)() = 0; +static void (*firstTest)() = testSimplifySkinnyTriangle4; void SimplifyPolygonPaths_Test() { size_t index = 0; @@ -569,8 +700,10 @@ void SimplifyPolygonPaths_Test() { ++index; } } + bool firstTestComplete = false; for ( ; index < simplifyTestsCount; ++index) { (*simplifyTests[index])(); + firstTestComplete = true; } } diff --git a/experimental/Intersection/EdgeWalkerQuadralaterals_Test.cpp b/experimental/Intersection/EdgeWalkerQuadralaterals_Test.cpp index b22e1a392a..6cb24171a4 100644 --- a/experimental/Intersection/EdgeWalkerQuadralaterals_Test.cpp +++ b/experimental/Intersection/EdgeWalkerQuadralaterals_Test.cpp @@ -13,8 +13,82 @@ static void testSimplifyQuad1() { path.lineTo(1, 3); path.lineTo(1, 3); path.close(); - simplify(path, true, out); - comparePaths(path, out); + testSimplify(path, true, out); +} + +static void testSimplifyQuad2() { + SkPath path, out; + path.moveTo(0, 0); + path.lineTo(0, 0); + path.lineTo(0, 0); + path.lineTo(0, 2); + path.close(); + path.moveTo(0, 1); + path.lineTo(0, 1); + path.lineTo(1, 1); + path.lineTo(0, 2); + path.close(); + testSimplify(path, true, out); +} + +static void testSimplifyQuad3() { + SkPath path, out; + path.moveTo(0, 0); + path.lineTo(0, 0); + path.lineTo(1, 0); + path.lineTo(1, 2); + path.close(); + path.moveTo(0, 1); + path.lineTo(1, 1); + path.lineTo(2, 1); + path.lineTo(0, 2); + path.close(); + testSimplify(path, true, out); +} + +static void testSimplifyQuad4() { + SkPath path, out; + path.moveTo(0, 0); + path.lineTo(0, 0); + path.lineTo(1, 0); + path.lineTo(2, 2); + path.close(); + path.moveTo(0, 0); + path.lineTo(2, 1); + path.lineTo(3, 1); + path.lineTo(3, 3); + path.close(); + testSimplify(path, true, out); +} + +static void testSimplifyQuad5() { + SkPath path, out; + path.moveTo(0, 0); + path.lineTo(0, 0); + path.lineTo(1, 0); + path.lineTo(3, 2); + path.close(); + path.moveTo(0, 1); + path.lineTo(1, 1); + path.lineTo(2, 1); + path.lineTo(0, 2); + path.close(); + testSimplify(path, true, out); +} + +static void testSimplifyQuad6() { + SkPath path, out; + path.moveTo(0, 0); + path.lineTo(1, 0); + path.lineTo(1, 1); + path.lineTo(3, 3); + path.close(); + path.moveTo(1, 1); + path.lineTo(1, 1); + path.lineTo(1, 1); + path.lineTo(2, 2); + path.close(); + testSimplify(path, true, out); } static void testSimplify4x4Quadralaterals() { @@ -41,7 +115,7 @@ static void testSimplify4x4Quadralaterals() { for (int g = f ; g < 16; ++g) { int gx = g & 0x03; int gy = g >> 2; - for (int h = g ; g < 16; ++g) { + for (int h = g ; h < 16; ++h) { int hx = h & 0x03; int hy = h >> 2; SkPath path, out; @@ -56,7 +130,7 @@ static void testSimplify4x4Quadralaterals() { path.lineTo(gx, gy); path.lineTo(hx, hy); path.close(); - if (1) { + if (1) { // gdb: set print elements 400 char* str = pathStr; str += sprintf(str, " path.moveTo(%d, %d);\n", ax, ay); str += sprintf(str, " path.lineTo(%d, %d);\n", bx, by); @@ -69,11 +143,15 @@ static void testSimplify4x4Quadralaterals() { str += sprintf(str, " path.lineTo(%d, %d);\n", hx, hy); str += sprintf(str, " path.close();"); } - simplify(path, true, out); - comparePaths(path, out); + if (!testSimplify(path, true, out)) { + SkDebugf("*/\n{ SkPath::kWinding_FillType, %d, %d, %d, %d, %d, %d, %d, %d },\n/*\n", + a, b, c, d, e, f, g, h); + } path.setFillType(SkPath::kEvenOdd_FillType); - simplify(path, true, out); - comparePaths(path, out); + if (!testSimplify(path, true, out)) { + SkDebugf("*/\n{ SkPath::kEvenOdd_FillType, %d, %d, %d, %d, %d, %d, %d, %d },\n/*\n", + a, b, c, d, e, f, g, h); + } } } } @@ -87,6 +165,11 @@ static void testSimplify4x4Quadralaterals() { static void (*simplifyTests[])() = { + testSimplifyQuad6, + testSimplifyQuad5, + testSimplifyQuad4, + testSimplifyQuad3, + testSimplifyQuad2, testSimplifyQuad1, testSimplify4x4Quadralaterals, }; diff --git a/experimental/Intersection/EdgeWalkerRectangles_Test.cpp b/experimental/Intersection/EdgeWalkerRectangles_Test.cpp index a42a970789..8dc8627609 100644 --- a/experimental/Intersection/EdgeWalkerRectangles_Test.cpp +++ b/experimental/Intersection/EdgeWalkerRectangles_Test.cpp @@ -1,6 +1,15 @@ #include "EdgeWalker_Test.h" #include "Intersection_Tests.h" +static void testSimplifyCoincidentInner() { + SkPath path, out; + path.setFillType(SkPath::kWinding_FillType); + path.addRect(10, 10, 60, 60, SkPath::kCCW_Direction); + path.addRect(20, 20, 50, 50, SkPath::kCW_Direction); + path.addRect(20, 30, 40, 40, SkPath::kCW_Direction); + testSimplify(path, true, out); +} + static void testSimplifyCoincidentVertical() { SkPath path, out; path.setFillType(SkPath::kWinding_FillType); @@ -295,8 +304,7 @@ static void testSimplifyOverlap() { SkPath path, out; path.addRect(rect1, static_cast<SkPath::Direction>(dir)); path.addRect(rect2, static_cast<SkPath::Direction>(dir)); - simplify(path, true, out); - comparePaths(path, out); + testSimplify(path, true, out); } } } @@ -409,6 +417,7 @@ static void testSimplifyDegenerate1() { } static void (*simplifyTests[])() = { + testSimplifyCoincidentInner, testSimplifyOverlapTiny, testSimplifyDegenerate1, testSimplifyCorner, diff --git a/experimental/Intersection/EdgeWalker_Test.h b/experimental/Intersection/EdgeWalker_Test.h index 391100407e..c449d1a4d8 100644 --- a/experimental/Intersection/EdgeWalker_Test.h +++ b/experimental/Intersection/EdgeWalker_Test.h @@ -3,7 +3,10 @@ #include "SkPath.h" extern void contourBounds(const SkPath& path, SkTDArray<SkRect>& boundsArray); -extern void comparePaths(const SkPath& one, const SkPath& two); +extern bool comparePaths(const SkPath& one, const SkPath& two); extern void comparePathsTiny(const SkPath& one, const SkPath& two); +extern void drawAsciiPaths(const SkPath& one, const SkPath& two, + bool drawPaths); extern void simplify(const SkPath& path, bool asFill, SkPath& simple); - +extern void showPath(const SkPath& path, const char* str = NULL); +extern bool testSimplify(const SkPath& path, bool fill, SkPath& out); diff --git a/experimental/Intersection/EdgeWalker_TestUtility.cpp b/experimental/Intersection/EdgeWalker_TestUtility.cpp index eb1509e798..84ca87fce3 100644 --- a/experimental/Intersection/EdgeWalker_TestUtility.cpp +++ b/experimental/Intersection/EdgeWalker_TestUtility.cpp @@ -4,32 +4,31 @@ #include "SkCanvas.h" #include "SkPaint.h" -static bool gDrawLastAsciiPaths = true; +static bool gShowPath = false; +static bool gDrawLastAsciiPaths = false; static bool gDrawAllAsciiPaths = false; -static bool gShowPath = true; +static bool gShowAsciiPaths = false; +static bool gComparePathsAssert = false; -static void showPath(const char* str, const SkPath& path) { - if (!gShowPath) { - return; - } - SkDebugf("%s\n", str); +void showPath(const SkPath& path, const char* str) { + SkDebugf("%s\n", str ? "original:" : str); SkPath::Iter iter(path, true); uint8_t verb; SkPoint pts[4]; while ((verb = iter.next(pts)) != SkPath::kDone_Verb) { switch (verb) { case SkPath::kMove_Verb: - SkDebugf("path.moveTo(%g, %g);\n", pts[0].fX, pts[0].fY); + SkDebugf("path.moveTo(%3.6g, %3.6g);\n", pts[0].fX, pts[0].fY); continue; case SkPath::kLine_Verb: - SkDebugf("path.lineTo(%g, %g);\n", pts[1].fX, pts[1].fY); + SkDebugf("path.lineTo(%3.6g, %3.6g);\n", pts[1].fX, pts[1].fY); break; case SkPath::kQuad_Verb: - SkDebugf("path.quadTo(%g, %g, %g, %g);\n", + SkDebugf("path.quadTo(%3.6g, %3.6g, %3.6g, %3.6g);\n", pts[1].fX, pts[1].fY, pts[2].fX, pts[2].fY); break; case SkPath::kCubic_Verb: - SkDebugf("path.cubicTo(%g, %g, %g, %g);\n", + SkDebugf("path.cubicTo(%3.6g, %3.6g, %3.6g, %3.6g);\n", pts[1].fX, pts[1].fY, pts[2].fX, pts[2].fY, pts[3].fX, pts[3].fY); break; @@ -77,14 +76,14 @@ static bool pathsDrawTheSame(const SkPath& one, const SkPath& two) { return true; } -static void drawAsciiPaths(const SkPath& one, const SkPath& two, +void drawAsciiPaths(const SkPath& one, const SkPath& two, bool drawPaths) { if (!drawPaths) { return; } - if (0) { - showPath("one:", one); - showPath("two:", two); + if (gShowAsciiPaths) { + showPath(one, "one:"); + showPath(two, "two:"); } const SkRect& bounds1 = one.getBounds(); const SkRect& bounds2 = two.getBounds(); @@ -139,22 +138,25 @@ static bool scaledDrawTheSame(const SkPath& one, const SkPath& two, return false; } -void comparePaths(const SkPath& one, const SkPath& two) { +bool comparePaths(const SkPath& one, const SkPath& two) { if (pathsDrawTheSame(one, two)) { - return; + return true; } drawAsciiPaths(one, two, gDrawAllAsciiPaths); for (int x = 9; x <= 33; ++x) { if (scaledDrawTheSame(one, two, x, x - (x >> 2), gDrawAllAsciiPaths)) { - return; + return true; } } if (!gDrawAllAsciiPaths) { scaledDrawTheSame(one, two, 9, 7, gDrawLastAsciiPaths); } - showPath("original:", one); - showPath("simplified:", two); - SkASSERT(0); + if (gComparePathsAssert) { + showPath(one); + showPath(two, "simplified:"); + SkASSERT(0); + } + return false; } // doesn't work yet @@ -188,3 +190,10 @@ void comparePathsTiny(const SkPath& one, const SkPath& two) { } } +bool testSimplify(const SkPath& path, bool fill, SkPath& out) { + if (gShowPath) { + showPath(path); + } + simplify(path, fill, out); + return comparePaths(path, out); +} diff --git a/experimental/Intersection/Intersection_Tests.cpp b/experimental/Intersection/Intersection_Tests.cpp index 2a1620ee81..2cf960132f 100644 --- a/experimental/Intersection/Intersection_Tests.cpp +++ b/experimental/Intersection/Intersection_Tests.cpp @@ -17,8 +17,8 @@ void Intersection_Tests() { LineQuadraticIntersection_Test(); LineCubicIntersection_Test(); - SimplifyRectangularPaths_Test(); SimplifyPolygonPaths_Test(); + SimplifyRectangularPaths_Test(); SimplifyQuadralateralPaths_Test(); QuadraticCoincidence_Test(); diff --git a/experimental/Intersection/LineIntersection.cpp b/experimental/Intersection/LineIntersection.cpp index 4d80606945..f5128eab2d 100644 --- a/experimental/Intersection/LineIntersection.cpp +++ b/experimental/Intersection/LineIntersection.cpp @@ -100,6 +100,28 @@ int horizontalIntersect(const _Line& line, double y, double tRange[2]) { return 1; } +// OPTIMIZATION Given: dy = line[1].y - line[0].y +// and: xIntercept / (y - line[0].y) == (line[1].x - line[0].x) / dy +// then: xIntercept * dy == (line[1].x - line[0].x) * (y - line[0].y) +// Assuming that dy is always > 0, the line segment intercepts if: +// left * dy <= xIntercept * dy <= right * dy +// thus: left * dy <= (line[1].x - line[0].x) * (y - line[0].y) <= right * dy +// (clever as this is, it does not give us the t value, so may be useful only +// as a quick reject -- and maybe not then; it takes 3 muls, 3 adds, 2 cmps) +int horizontalLineIntersect(const _Line& line, double left, double right, + double y, double tRange[2]) { + int result = horizontalIntersect(line, y, tRange); + if (result != 1) { + return result; + } + // FIXME: this is incorrect if result == 2 + double xIntercept = line[0].x + tRange[0] * (line[1].x - line[0].x); + if (xIntercept > right || xIntercept < left) { + return 0; + } + return result; +} + // from http://www.bryceboe.com/wordpress/wp-content/uploads/2006/10/intersect.py // 4 subs, 2 muls, 1 cmp static bool ccw(const _Point& A, const _Point& B, const _Point& C) { diff --git a/experimental/Intersection/LineIntersection.h b/experimental/Intersection/LineIntersection.h index dfae7efde2..687b77d557 100644 --- a/experimental/Intersection/LineIntersection.h +++ b/experimental/Intersection/LineIntersection.h @@ -2,5 +2,7 @@ #include "DataTypes.h" int horizontalIntersect(const _Line& line, double y, double tRange[2]); +int horizontalLineIntersect(const _Line& line, double left, double right, + double y, double tRange[2]); int intersect(const _Line& a, const _Line& b, double aRange[2], double bRange[2]); bool testIntersect(const _Line& a, const _Line& b); diff --git a/experimental/Intersection/edge.xcodeproj/project.pbxproj b/experimental/Intersection/edge.xcodeproj/project.pbxproj index cf433c686d..1b520f199e 100644 --- a/experimental/Intersection/edge.xcodeproj/project.pbxproj +++ b/experimental/Intersection/edge.xcodeproj/project.pbxproj @@ -11,6 +11,7 @@ 8D11072B0486CEB800E47090 /* InfoPlist.strings in Resources */ = {isa = PBXBuildFile; fileRef = 089C165CFE840E0CC02AAC07 /* InfoPlist.strings */; }; FE3201C8144DCC68006DDA67 /* skia_mac.mm in Sources */ = {isa = PBXBuildFile; fileRef = FE3201C6144DCC68006DDA67 /* skia_mac.mm */; }; FE3201C9144DCC68006DDA67 /* SkOSWindow_Mac.mm in Sources */ = {isa = PBXBuildFile; fileRef = FE3201C7144DCC68006DDA67 /* SkOSWindow_Mac.mm */; }; + FE3DBAFE150E4A680006ADF4 /* junk.htm in Resources */ = {isa = PBXBuildFile; fileRef = FE3DBAFD150E4A680006ADF4 /* junk.htm */; }; FE7130A114CE0EEB0008E392 /* LineQuadraticIntersection.cpp in Sources */ = {isa = PBXBuildFile; fileRef = FE7130A014CE0EEB0008E392 /* LineQuadraticIntersection.cpp */; }; FE7131C414CF5A960008E392 /* LineQuadraticIntersection_Test.cpp in Sources */ = {isa = PBXBuildFile; fileRef = FE7131C314CF5A960008E392 /* LineQuadraticIntersection_Test.cpp */; }; FE7131EE14D03AED0008E392 /* LineCubicIntersection.cpp in Sources */ = {isa = PBXBuildFile; fileRef = FE7131ED14D03AED0008E392 /* LineCubicIntersection.cpp */; }; @@ -59,6 +60,7 @@ FECAA6E114BDDF2D00B35E2C /* QuadraticReduceOrder_Test.cpp in Sources */ = {isa = PBXBuildFile; fileRef = FECAA6E014BDDF2D00B35E2C /* QuadraticReduceOrder_Test.cpp */; }; FED53C391483CB9400F6359E /* Inline_Tests.cpp in Sources */ = {isa = PBXBuildFile; fileRef = FED53C381483CB9400F6359E /* Inline_Tests.cpp */; }; FED865F915056A79006F4508 /* EdgeWalkerQuadralaterals_Test.cpp in Sources */ = {isa = PBXBuildFile; fileRef = FED865F815056A79006F4508 /* EdgeWalkerQuadralaterals_Test.cpp */; }; + FED866D715066642006F4508 /* EdgeWalkerPolygons_Mismatches.cpp in Sources */ = {isa = PBXBuildFile; fileRef = FED866D615066642006F4508 /* EdgeWalkerPolygons_Mismatches.cpp */; }; FEED7245144DD2250059E97B /* SkEventNotifier.mm in Sources */ = {isa = PBXBuildFile; fileRef = FEED723E144DD2250059E97B /* SkEventNotifier.mm */; }; FEED7292144DD4610059E97B /* libexperimental.a in Frameworks */ = {isa = PBXBuildFile; fileRef = FEED726E144DD4050059E97B /* libexperimental.a */; }; FEED7293144DD4620059E97B /* libskgr.a in Frameworks */ = {isa = PBXBuildFile; fileRef = FEED7276144DD4140059E97B /* libskgr.a */; }; @@ -237,6 +239,8 @@ 8D1107320486CEB800E47090 /* edge.app */ = {isa = PBXFileReference; explicitFileType = wrapper.application; includeInIndex = 0; path = edge.app; sourceTree = BUILT_PRODUCTS_DIR; }; FE3201C6144DCC68006DDA67 /* skia_mac.mm */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.objcpp; name = skia_mac.mm; path = ../../src/utils/mac/skia_mac.mm; sourceTree = SOURCE_ROOT; }; FE3201C7144DCC68006DDA67 /* SkOSWindow_Mac.mm */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.objcpp; name = SkOSWindow_Mac.mm; path = ../../src/utils/mac/SkOSWindow_Mac.mm; sourceTree = SOURCE_ROOT; }; + FE3DB8C9150A48320006ADF4 /* junk.txt */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = text; path = junk.txt; sourceTree = "<group>"; }; + FE3DBAFD150E4A680006ADF4 /* junk.htm */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = text.html; name = junk.htm; path = ../../../../../junk.htm; sourceTree = SOURCE_ROOT; }; FE4FE7411492417500A12A34 /* IntersectionUtilities.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = IntersectionUtilities.cpp; sourceTree = "<group>"; }; FE7130A014CE0EEB0008E392 /* LineQuadraticIntersection.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = LineQuadraticIntersection.cpp; sourceTree = "<group>"; }; FE7131C314CF5A960008E392 /* LineQuadraticIntersection_Test.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = LineQuadraticIntersection_Test.cpp; sourceTree = "<group>"; }; @@ -301,6 +305,7 @@ FECAACA614BE1C6100B35E2C /* QuadraticParameterization_TestUtility.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = QuadraticParameterization_TestUtility.cpp; sourceTree = "<group>"; }; FED53C381483CB9400F6359E /* Inline_Tests.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = Inline_Tests.cpp; sourceTree = "<group>"; }; FED865F815056A79006F4508 /* EdgeWalkerQuadralaterals_Test.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = EdgeWalkerQuadralaterals_Test.cpp; sourceTree = "<group>"; }; + FED866D615066642006F4508 /* EdgeWalkerPolygons_Mismatches.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = EdgeWalkerPolygons_Mismatches.cpp; sourceTree = "<group>"; }; FEED723C144DD2250059E97B /* SampleApp.xib */ = {isa = PBXFileReference; lastKnownFileType = file.xib; name = SampleApp.xib; path = ../../src/utils/mac/SampleApp.xib; sourceTree = SOURCE_ROOT; }; FEED723D144DD2250059E97B /* SampleAppDelegate.mm */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.objcpp; name = SampleAppDelegate.mm; path = ../../src/utils/mac/SampleAppDelegate.mm; sourceTree = SOURCE_ROOT; }; FEED723E144DD2250059E97B /* SkEventNotifier.mm */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.objcpp; name = SkEventNotifier.mm; path = ../../src/utils/mac/SkEventNotifier.mm; sourceTree = SOURCE_ROOT; }; @@ -476,6 +481,8 @@ FE71354F14D305FD0008E392 /* ShapeOps */ = { isa = PBXGroup; children = ( + FE3DBAFD150E4A680006ADF4 /* junk.htm */, + FE3DB8C9150A48320006ADF4 /* junk.txt */, FE71358514D309E90008E392 /* EdgeWalker.cpp */, FE713C6114D9879B0008E392 /* TSearch.h */, ); @@ -539,6 +546,7 @@ FEED764B144F29BD0059E97B /* TestUtilities.cpp */, FE7413DB14F6926D00056D7B /* EdgeWalker_Test.h */, FED865F815056A79006F4508 /* EdgeWalkerQuadralaterals_Test.cpp */, + FED866D615066642006F4508 /* EdgeWalkerPolygons_Mismatches.cpp */, ); name = Tests; sourceTree = "<group>"; @@ -890,6 +898,7 @@ 8D11072B0486CEB800E47090 /* InfoPlist.strings in Resources */, 1DDD58160DA1D0A300B32029 /* MainMenu.xib in Resources */, FEED72B0144DD5710059E97B /* SampleApp.xib in Resources */, + FE3DBAFE150E4A680006ADF4 /* junk.htm in Resources */, ); runOnlyForDeploymentPostprocessing = 0; }; @@ -952,6 +961,7 @@ FE7413D414F6915A00056D7B /* EdgeWalkerPolygons_Test.cpp in Sources */, FE7413D814F691C200056D7B /* EdgeWalker_TestUtility.cpp in Sources */, FED865F915056A79006F4508 /* EdgeWalkerQuadralaterals_Test.cpp in Sources */, + FED866D715066642006F4508 /* EdgeWalkerPolygons_Mismatches.cpp in Sources */, ); runOnlyForDeploymentPostprocessing = 0; }; |