diff options
19 files changed, 547 insertions, 369 deletions
diff --git a/experimental/Intersection/CubicIntersection.h b/experimental/Intersection/CubicIntersection.h deleted file mode 100644 index b918400d88..0000000000 --- a/experimental/Intersection/CubicIntersection.h +++ /dev/null @@ -1,40 +0,0 @@ -#ifndef CubicIntersection_DEFINE -#define CubicIntersection_DEFINE - -#include "DataTypes.h" - -class Intersections; - -// unit-testable utilities -bool bezier_clip(const Cubic& cubic1, const Cubic& cubic2, double& minT, double& maxT); -bool bezier_clip(const Quadratic& q1, const Quadratic& q2, double& minT, double& maxT); -void chop_at(const Cubic& src, CubicPair& dst, double t); -void chop_at(const Quadratic& src, QuadraticPair& dst, double t); -int convex_hull(const Cubic& cubic, char order[4]); -bool convex_x_hull(const Cubic& cubic, char connectTo0[2], char connectTo3[2]); -bool implicit_matches(const Cubic& cubic1, const Cubic& cubic2); -bool implicit_matches(const Quadratic& quad1, const Quadratic& quad2); -void sub_divide(const Cubic& src, double t1, double t2, Cubic& dst); -void sub_divide(const Quadratic& src, double t1, double t2, Quadratic& dst); -void tangent(const Cubic& cubic, double t, _Point& result); -void tangent(const Quadratic& cubic, double t, _Point& result); - -// utilities used only for unit testing -bool point_on_parameterized_curve(const Cubic& cubic, const _Point& point); -bool point_on_parameterized_curve(const Quadratic& quad, const _Point& point); - -// main functions -enum ReduceOrder_Flags { - kReduceOrder_NoQuadraticsAllowed, - kReduceOrder_QuadraticsAllowed -}; -int reduceOrder(const Cubic& cubic, Cubic& reduction, ReduceOrder_Flags ); -int reduceOrder(const _Line& line, _Line& reduction); -int reduceOrder(const Quadratic& quad, Quadratic& reduction); -//bool intersectStart(const Cubic& cubic1, const Cubic& cubic2, Intersections& ); -bool intersectStartT(const Cubic& cubic1, const Cubic& cubic2, Intersections& ); -bool intersectStart(const Cubic& cubic, const _Line& line, Intersections& ); -bool intersectStart(const Quadratic& q1, const Quadratic& q2, Intersections& ); -bool intersectStart(const Quadratic& quad, const _Line& line, Intersections& ); - -#endif diff --git a/experimental/Intersection/CurveIntersection.h b/experimental/Intersection/CurveIntersection.h index 88316fab7c..25c696c48d 100644 --- a/experimental/Intersection/CurveIntersection.h +++ b/experimental/Intersection/CurveIntersection.h @@ -31,6 +31,10 @@ int reduceOrder(const Cubic& cubic, Cubic& reduction, ReduceOrder_Flags ); int reduceOrder(const _Line& line, _Line& reduction); int reduceOrder(const Quadratic& quad, Quadratic& reduction); int horizontalIntersect(const Cubic& cubic, double y, double tRange[3]); +int horizontalIntersect(const Cubic& cubic, double left, double right, double y, + double tRange[3]); +int horizontalIntersect(const Quadratic& quad, double left, double right, + double y, double tRange[2]); bool intersect(const Cubic& cubic1, const Cubic& cubic2, Intersections& ); int intersect(const Cubic& cubic, const _Line& line, double cRange[3], double lRange[3]); bool intersect(const Quadratic& q1, const Quadratic& q2, Intersections& ); diff --git a/experimental/Intersection/EdgeWalker.cpp b/experimental/Intersection/EdgeWalker.cpp index 7f0ddffc01..70fa8e679c 100644 --- a/experimental/Intersection/EdgeWalker.cpp +++ b/experimental/Intersection/EdgeWalker.cpp @@ -16,7 +16,7 @@ #include "ShapeOps.h" #include "TSearch.h" -#if 01 // set to 1 for no debugging whatsoever +#if 0 // set to 1 for no debugging whatsoever const bool gShowDebugf = false; // FIXME: remove once debugging is complete #define DEBUG_DUMP 0 @@ -30,6 +30,7 @@ const bool gShowDebugf = false; // FIXME: remove once debugging is complete #define DEBUG_OUT_LESS_THAN 0 #define DEBUG_ADJUST_COINCIDENT 0 #define DEBUG_BOTTOM 0 +#define DEBUG_SPLIT 0 #else const bool gShowDebugf = true; // FIXME: remove once debugging is complete @@ -44,7 +45,8 @@ const bool gShowDebugf = true; // FIXME: remove once debugging is complete #define DEBUG_OUT 01 #define DEBUG_OUT_LESS_THAN 0 #define DEBUG_ADJUST_COINCIDENT 1 -#define DEBUG_BOTTOM 01 +#define DEBUG_BOTTOM 0 +#define DEBUG_SPLIT 1 #endif @@ -59,7 +61,8 @@ static int QuadLineIntersect(const SkPoint a[3], const SkPoint b[2], Intersections& intersections) { const Quadratic aQuad = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY}}; const _Line bLine = {{b[0].fX, b[0].fY}, {b[1].fX, b[1].fY}}; - return intersect(aQuad, bLine, intersections); + intersect(aQuad, bLine, intersections); + return intersections.fUsed; } static int CubicLineIntersect(const SkPoint a[2], const SkPoint b[3], @@ -67,15 +70,15 @@ static int CubicLineIntersect(const SkPoint a[2], const SkPoint b[3], const Cubic aCubic = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY}, {a[3].fX, a[3].fY}}; const _Line bLine = {{b[0].fX, b[0].fY}, {b[1].fX, b[1].fY}}; - intersections.fUsed = intersect(aCubic, bLine, intersections.fT[0], intersections.fT[1]); - return intersections.fUsed; + return intersect(aCubic, bLine, intersections.fT[0], intersections.fT[1]); } static int QuadIntersect(const SkPoint a[3], const SkPoint b[3], Intersections& intersections) { const Quadratic aQuad = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY}}; const Quadratic bQuad = {{b[0].fX, b[0].fY}, {b[1].fX, b[1].fY}, {b[2].fX, b[2].fY}}; - return intersect(aQuad, bQuad, intersections); + intersect(aQuad, bQuad, intersections); + return intersections.fUsed; } static int CubicIntersect(const SkPoint a[4], const SkPoint b[4], @@ -84,7 +87,8 @@ static int CubicIntersect(const SkPoint a[4], const SkPoint b[4], {a[3].fX, a[3].fY}}; const Cubic bCubic = {{b[0].fX, b[0].fY}, {b[1].fX, b[1].fY}, {b[2].fX, b[2].fY}, {b[3].fX, b[3].fY}}; - return intersect(aCubic, bCubic, intersections); + intersect(aCubic, bCubic, intersections); + return intersections.fUsed; } static int LineIntersect(const SkPoint a[2], SkScalar left, SkScalar right, @@ -93,6 +97,19 @@ static int LineIntersect(const SkPoint a[2], SkScalar left, SkScalar right, return horizontalLineIntersect(aLine, left, right, y, aRange); } +static int QuadIntersect(const SkPoint a[3], SkScalar left, SkScalar right, + SkScalar y, double aRange[3]) { + const Quadratic aQuad = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY}}; + return horizontalIntersect(aQuad, left, right, y, aRange); +} + +static int CubicIntersect(const SkPoint a[4], SkScalar left, SkScalar right, + SkScalar y, double aRange[4]) { + const Cubic aCubic = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY}, + {a[3].fX, a[3].fY}}; + return horizontalIntersect(aCubic, left, right, y, aRange); +} + static void LineXYAtT(const SkPoint a[2], double t, SkPoint* out) { const _Line line = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}}; double x, y; @@ -632,7 +649,25 @@ class Intercepts { public: Intercepts() : fTopIntercepts(0) - , fBottomIntercepts(0) { + , fBottomIntercepts(0) + , fExplicit(false) { + } + + Intercepts& operator=(const Intercepts& src) { + fTs = src.fTs; + fTopIntercepts = src.fTopIntercepts; + fBottomIntercepts = src.fBottomIntercepts; + } + + // OPTIMIZATION: remove this function if it's never called + double t(int tIndex) const { + if (tIndex == 0) { + return 0; + } + if (tIndex > fTs.count()) { + return 1; + } + return fTs[tIndex - 1]; } #if DEBUG_DUMP @@ -657,16 +692,18 @@ public: SkDebugf("%*s.fTs[%d]=%1.9g (%1.9g,%1.9g)\n", tab + sizeof(className), className, i, fTs[i], out.fX, out.fY); } - SkDebugf("%*s.fTopIntercepts=%d\n", tab + sizeof(className), + SkDebugf("%*s.fTopIntercepts=%u\n", tab + sizeof(className), className, fTopIntercepts); - SkDebugf("%*s.fBottomIntercepts=%d\n", tab + sizeof(className), + SkDebugf("%*s.fBottomIntercepts=%u\n", tab + sizeof(className), className, fBottomIntercepts); } #endif SkTDArray<double> fTs; - int fTopIntercepts; - int fBottomIntercepts; + unsigned char fTopIntercepts; // 0=init state 1=1 edge >1=multiple edges + unsigned char fBottomIntercepts; + bool fExplicit; // if set, suppress 0 and 1 + }; struct HorizontalEdge { @@ -709,13 +746,16 @@ struct InEdge { for (size_t index = 0; index < count; ++index) { double t = ts[index]; if (t <= 0) { + intercepts.fTopIntercepts <<= 1; fContainsIntercepts |= ++intercepts.fTopIntercepts > 1; continue; } if (t >= 1) { + intercepts.fBottomIntercepts <<= 1; fContainsIntercepts |= ++intercepts.fBottomIntercepts > 1; continue; } + fIntersected = true; foundIntercept = true; size_t tCount = intercepts.fTs.count(); double delta; @@ -740,6 +780,40 @@ struct InEdge { fContainsIntercepts |= foundIntercept; return insertedAt; } + + void addPartial(SkTArray<InEdge>& edges, int id, int ptStart, int ptEnd, + int verbStart, int verbEnd) { + InEdge* edge = edges.push_back_n(1); + int verbCount = verbEnd - verbStart; + edge->fIntercepts.push_back_n(verbCount); + uint8_t* verbs = &fVerbs[verbStart]; + for (int ceptIdx = 0; ceptIdx < verbCount; ++ceptIdx) { + edge->fIntercepts[ceptIdx] = fIntercepts[verbStart + ceptIdx]; + } + edge->fPts.append(ptEnd - ptStart, &fPts[ptStart]); + edge->fVerbs.append(verbCount, &fVerbs[verbStart]); + edge->setBounds(); + edge->fID = id + edges.count(); + edge->fWinding = fWinding; + edge->fContainsIntercepts = fContainsIntercepts; // FIXME: may not be correct -- but do we need to know? + } + + void addSplit(SkTArray<InEdge>& edges, int id, SkPoint* pts, uint8_t verb, + double* ts, int tCount, bool flipped) { + InEdge* edge = edges.push_back_n(1); + edge->fIntercepts.push_back_n(1); + edge->fIntercepts[0].fTs.append(tCount, ts); + edge->fIntercepts[0].fExplicit = true; + edge->fPts.append(verb, pts); + edge->fVerbs.append(1, &verb); + edge->setBounds(); + edge->fID = id + edges.count(); + edge->fWinding = fWinding; + edge->fContainsIntercepts = fContainsIntercepts; // FIXME: may not be correct -- but do we need to know? + if (flipped) { + flip(); + } + } bool cached(const InEdge* edge) { // FIXME: in the pathological case where there is a ton of edges, binary search? @@ -758,10 +832,44 @@ struct InEdge { } void complete(signed char winding, int id) { + setBounds(); + fIntercepts.push_back_n(fVerbs.count()); + if ((fWinding = winding) < 0) { // reverse verbs, pts, if bottom to top + flip(); + } + fContainsIntercepts = fIntersected = false; + fID = id; + } + + void flip() { + size_t index; + size_t last = fPts.count() - 1; + for (index = 0; index < last; ++index, --last) { + SkTSwap<SkPoint>(fPts[index], fPts[last]); + } + last = fVerbs.count() - 1; + for (index = 0; index < last; ++index, --last) { + SkTSwap<uint8_t>(fVerbs[index], fVerbs[last]); + } + } + + void reset() { + fCached.reset(); + fIntercepts.reset(); + fPts.reset(); + fVerbs.reset(); + fBounds.set(SK_ScalarMax, SK_ScalarMax, SK_ScalarMax, SK_ScalarMax); + fID = -1; + fWinding = 0; + fContainsIntercepts = false; + fIntersected = false; + } + + void setBounds() { SkPoint* ptPtr = fPts.begin(); SkPoint* ptLast = fPts.end(); if (ptPtr == ptLast) { - SkDebugf("empty edge\n"); + SkDebugf("%s empty edge\n", __FUNCTION__); SkASSERT(0); // FIXME: delete empty edge? return; @@ -772,20 +880,113 @@ struct InEdge { fBounds.growToInclude(ptPtr->fX, ptPtr->fY); ++ptPtr; } - fIntercepts.push_back_n(fVerbs.count()); - if ((fWinding = winding) < 0) { // reverse verbs, pts, if bottom to top - size_t index; - size_t last = fPts.count() - 1; - for (index = 0; index < last; ++index, --last) { - SkTSwap<SkPoint>(fPts[index], fPts[last]); + } + + void splitInflectionPts(SkTArray<InEdge>& edges, int idStart) { + if (!fIntersected) { + return; + } + uint8_t* verbs = fVerbs.begin(); + SkPoint* pts = fPts.begin(); + int lastVerb = 0; + int lastPt = 0; + uint8_t verb; + bool edgeSplit = false; + for (int ceptIdx = 0; ceptIdx < fIntercepts.count(); ++ceptIdx, pts += verb) { + Intercepts& intercepts = fIntercepts[ceptIdx]; + verb = *verbs++; + if (verb <= SkPath::kLine_Verb) { + continue; + } + size_t tCount = intercepts.fTs.count(); + if (!tCount) { + continue; + } + size_t tIndex = -1; + SkScalar y = pts[0].fY; + int lastSplit = 0; + int firstSplit = -1; + bool curveSplit = false; + while (++tIndex < tCount) { + double nextT = intercepts.fTs[tIndex]; + SkScalar nextY = verb == SkPath::kQuad_Verb + ? QuadYAtT(pts, nextT) : CubicYAtT(pts, nextT); + if (nextY < y) { + edgeSplit = curveSplit = true; + if (firstSplit < 0) { + firstSplit = tIndex; + int nextPt = pts - fPts.begin(); + int nextVerb = verbs - 1 - fVerbs.begin(); + if (lastVerb < nextVerb) { + addPartial(edges, idStart, lastPt, nextPt, + lastVerb, nextVerb); + #if DEBUG_SPLIT + SkDebugf("%s addPartial 1 edge=%d\n", __FUNCTION__, + fID); + #endif + } + lastPt = nextPt; + lastVerb = nextVerb; + } + } else { + if (firstSplit >= 0) { + if (lastSplit < firstSplit) { + addSplit(edges, idStart, pts, verb, + &intercepts.fTs[lastSplit], + firstSplit - lastSplit, false); + #if DEBUG_SPLIT + SkDebugf("%s addSplit 1 edge=%d tIndex=%d,%d\n", + __FUNCTION__, fID, lastSplit, firstSplit); + #endif + } + addSplit(edges, idStart, pts, verb, + &intercepts.fTs[firstSplit], + tIndex - firstSplit, true); + #if DEBUG_SPLIT + SkDebugf("%s addSplit 2 edge=%d tIndex=%d,%d flip\n", + __FUNCTION__, fID, firstSplit, tIndex); + #endif + lastSplit = tIndex; + firstSplit = -1; + } + } + y = nextY; + } + if (curveSplit) { + if (firstSplit < 0) { + firstSplit = lastSplit; + } else { + addSplit(edges, idStart, pts, verb, + &intercepts.fTs[lastSplit], firstSplit - lastSplit, + false); + #if DEBUG_SPLIT + SkDebugf("%s addSplit 3 edge=%d tIndex=%d,%d\n", __FUNCTION__, + fID, lastSplit, firstSplit); + #endif + } + addSplit(edges, idStart, pts, verb, + &intercepts.fTs[firstSplit], tIndex - firstSplit, + pts[verb].fY < y); + #if DEBUG_SPLIT + SkDebugf("%s addSplit 4 edge=%d tIndex=%d,%d %s\n", __FUNCTION__, + fID, firstSplit, tIndex, pts[verb].fY < y ? "flip" : ""); + #endif } - last = fVerbs.count() - 1; - for (index = 0; index < last; ++index, --last) { - SkTSwap<uint8_t>(fVerbs[index], fVerbs[last]); + } + // collapse remainder -- if there's nothing left, clear it somehow? + if (edgeSplit) { + int nextVerb = verbs - 1 - fVerbs.begin(); + if (lastVerb < nextVerb) { + int nextPt = pts - fPts.begin(); + addPartial(edges, idStart, lastPt, nextPt, + lastVerb, nextVerb); + #if DEBUG_SPLIT + SkDebugf("%s addPartial 2 edge=%d\n", __FUNCTION__, fID); + #endif } + // OPTIMIZATION: reuse the edge instead of marking it empty + reset(); } - fContainsIntercepts = false; - fID = id; } #if DEBUG_DUMP @@ -803,7 +1004,6 @@ struct InEdge { 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, (SkPath::Verb) *verbs); pts += *verbs++; } @@ -822,10 +1022,12 @@ struct InEdge { fWinding); SkDebugf("%*s.fContainsIntercepts=%d\n", tab + sizeof(className), className, fContainsIntercepts); + SkDebugf("%*s.fIntersected=%d\n", tab + sizeof(className), + className, fIntersected); } #endif - // temporary data : move this to a separate struct? + // FIXME: temporary data : move this to a separate struct? SkTDArray<const InEdge*> fCached; // list of edges already intercepted SkTArray<Intercepts> fIntercepts; // one per verb @@ -836,6 +1038,7 @@ struct InEdge { int fID; signed char fWinding; bool fContainsIntercepts; + bool fIntersected; }; class InEdgeBuilder { @@ -849,10 +1052,19 @@ InEdgeBuilder(const SkPath& path, bool ignoreHorizontal, SkTArray<InEdge>& edges , fID(0) , fHorizontalEdges(horizontalEdges) , fIgnoreHorizontal(ignoreHorizontal) + , fContainsCurves(false) { walk(); } +bool containsCurves() const { + return fContainsCurves; +} + +int nextID() { + return ++fID; +} + protected: void addEdge() { @@ -864,7 +1076,7 @@ void addEdge() { bool complete() { if (fCurrentEdge && fCurrentEdge->fVerbs.count()) { - fCurrentEdge->complete(fWinding, ++fID); + fCurrentEdge->complete(fWinding, nextID()); fCurrentEdge = NULL; return true; } @@ -913,9 +1125,11 @@ void walk() { break; case SkPath::kQuad_Verb: winding = direction(3); + fContainsCurves = true; break; case SkPath::kCubic_Verb: winding = direction(4); + fContainsCurves = true; break; case SkPath::kClose_Verb: SkASSERT(fCurrentEdge); @@ -969,6 +1183,7 @@ private: int fID; int8_t fWinding; bool fIgnoreHorizontal; + bool fContainsCurves; }; struct WorkEdge { @@ -1134,8 +1349,8 @@ public: } bool advanceT() { - SkASSERT(fTIndex <= fTs->count()); - return ++fTIndex <= fTs->count(); + SkASSERT(fTIndex <= fTs->count() - fExplicitTs); + return ++fTIndex <= fTs->count() - fExplicitTs; } bool advance() { @@ -1153,6 +1368,7 @@ public: SkASSERT(fWorkEdge.fEdge->fPts.begin() <= fWorkEdge.fPts); } while (fWorkEdge.fPts[0].fY >= y); initT(); + SkASSERT(!fExplicitTs); fTIndex = fTs->count() + 1; } @@ -1187,7 +1403,7 @@ public: // for the fTIndex, don't do it again // For identical x, this lets us know which edge is first. // If both edges have T values < 1, check x at next T (fXBelow). - int add = (fTIndex <= fTs->count()) - 1; + int add = (fTIndex <= fTs->count() - fExplicitTs) - 1; double tAbove = t(fTIndex + add); (*xyAtTFunc)(fWorkEdge.fPts, tAbove, &fAbove); double tBelow = t(fTIndex - ~add); @@ -1195,6 +1411,7 @@ public: SkASSERT(tAbove != tBelow); // FIXME: this can loop forever // need a break if we hit the end + // FIXME: in unit test, figure out how explicit Ts work as well while (fAbove.fY == fBelow.fY) { if (add < 0 || fTIndex == fTs->count()) { add -= 1; @@ -1249,7 +1466,8 @@ public: const Intercepts& intercepts = fWorkEdge.fEdge->fIntercepts.front(); SkASSERT(fWorkEdge.verbIndex() <= fWorkEdge.fEdge->fIntercepts.count()); const Intercepts* interceptPtr = &intercepts + fWorkEdge.verbIndex(); - fTs = &interceptPtr->fTs; + fTs = &interceptPtr->fTs; + fExplicitTs = interceptPtr->fExplicit; // the above is conceptually the same as // fTs = &fWorkEdge.fEdge->fIntercepts[fWorkEdge.verbIndex()].fTs; // but templated arrays don't allow returning a pointer to the end() element @@ -1379,23 +1597,21 @@ public: #endif return ulps >= 0 && ulps <= 32; } - + double nextT() const { - SkASSERT(fTIndex <= fTs->count()); + SkASSERT(fTIndex <= fTs->count() - fExplicitTs); return t(fTIndex + 1); } double t() const { - if (fTIndex == 0) { - return 0; - } - if (fTIndex > fTs->count()) { - return 1; - } - return (*fTs)[fTIndex - 1]; + return t(fTIndex); } double t(int tIndex) const { + if (fExplicitTs) { + SkASSERT(tIndex < fTs->count()); + return (*fTs)[tIndex]; + } if (tIndex == 0) { return 0; } @@ -1426,6 +1642,7 @@ public: bool fCloseCall; bool fDone; bool fFixBelow; + bool fExplicitTs; }; static void addToActive(SkTDArray<ActiveEdge>& activeEdges, const InEdge* edge) { @@ -1462,24 +1679,39 @@ static void addBottomT(InEdge** currentPtr, InEdge** lastPtr, HorizontalEdge** sorted = horizontal; horzEdge = *sorted; do { - if (wt.verb() == SkPath::kLine_Verb) { - double wtTs[2]; - int pts = LineIntersect(wt.fPts, horzEdge->fLeft, - horzEdge->fRight, horzEdge->fY, wtTs); - if (pts) { + double wtTs[4]; + int pts; + uint8_t verb = wt.verb(); + switch (verb) { + case SkPath::kLine_Verb: + pts = LineIntersect(wt.fPts, horzEdge->fLeft, + horzEdge->fRight, horzEdge->fY, wtTs); + break; + case SkPath::kQuad_Verb: + pts = QuadIntersect(wt.fPts, horzEdge->fLeft, + horzEdge->fRight, horzEdge->fY, wtTs); + break; + case SkPath::kCubic_Verb: + pts = CubicIntersect(wt.fPts, horzEdge->fLeft, + horzEdge->fRight, horzEdge->fY, wtTs); + break; + } + 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]); + for (int x = 0; x < pts; ++x) { + SkDebugf("%s y=%g wtTs[0]=%g (%g,%g", __FUNCTION__, + horzEdge->fY, wtTs[x], wt.fPts[0].fX, wt.fPts[0].fY); + for (int y = 0; y < verb; ++y) { + SkDebugf(" %g,%g", wt.fPts[y + 1].fX, wt.fPts[y + 1].fY)); } -#endif - test->add(wtTs, pts, wt.verbIndex()); + SkDebugf(")\n"); } - } else { - // FIXME: add all curve types - SkASSERT(0); + if (pts > verb) { + SkASSERT(0); // FIXME ? should this work? + SkDebugf("%s wtTs[1]=%g\n", __FUNCTION__, wtTs[1]); + } +#endif + test->add(wtTs, pts, wt.verbIndex()); } horzEdge = *++sorted; } while (horzEdge->fY == bottom @@ -1526,6 +1758,9 @@ static void addIntersectingTs(InEdge** currentPtr, InEdge** lastPtr) { InEdge** nextPtr = testPtr; do { InEdge* next = *++nextPtr; + // FIXME: this compares against the sentinel sometimes + // OPTIMIZATION: this may never be needed since this gets called + // in two passes now. Verify that double hits are appropriate. if (test->cached(next)) { continue; } @@ -1695,6 +1930,9 @@ static SkScalar computeInterceptBottom(SkTDArray<ActiveEdge>& activeEdges, } } while (wt.advance()); } +#if DEBUG_BOTTOM + SkDebugf("%s bottom=%1.9g\n", __FUNCTION__, bottom); +#endif return bottom; } @@ -1729,6 +1967,9 @@ static SkScalar findBottom(InEdge** currentPtr, } test = *++testPtr; } +#if DEBUG_BOTTOM + SkDebugf("%s %d bottom=%1.9g\n", __FUNCTION__, activeEdges ? 2 : 1, bottom); +#endif return bottom; } @@ -2095,7 +2336,7 @@ static void stitchEdge(SkTDArray<ActiveEdge*>& edgeList, SkScalar y, aboveBottom &= !activePtr->fCloseCall; } else { if (activePtr->fSkip || activePtr->fCloseCall) { - SkDebugf("== %1.9g\n", clippedPts[0].fY); + if (gShowDebugf) SkDebugf("== %1.9g\n", clippedPts[0].fY); } } } while (moreToDo & aboveBottom); @@ -2103,6 +2344,16 @@ static void stitchEdge(SkTDArray<ActiveEdge*>& edgeList, SkScalar y, } } +static void dumpEdgeList(const SkTDArray<InEdge*>& edgeList, + const InEdge& edgeSentinel) { +#if DEBUG_DUMP + InEdge** debugPtr = edgeList.begin(); + do { + (*debugPtr++)->dump(); + } while (*debugPtr != &edgeSentinel); +#endif +} + void simplify(const SkPath& path, bool asFill, SkPath& simple) { // returns 1 for evenodd, -1 for winding, regardless of inverse-ness int windingMask = (path.getFillType() & 1) ? 1 : -1; @@ -2149,14 +2400,24 @@ void simplify(const SkPath& path, bool asFill, SkPath& simple) { 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 - + // if a quadratic or cubic now has an intermediate T value, see if the Ts + // on either side cause the Y values to monotonically increase. If not, split + // the curve at the new T. + if (builder.containsCurves()) { + currentPtr = edgeList.begin(); + SkTArray<InEdge> splits; + do { + (*currentPtr)->splitInflectionPts(splits, builder.nextID()); + } while (*++currentPtr != &edgeSentinel); + if (splits.count()) { + edges.pop_back(); // pop the sentinel + for (int index = 0; index < splits.count(); ++index) { + edges.push_back(splits[index]); + } + makeEdgeList(edges, edgeSentinel, edgeList); + } + } + dumpEdgeList(edgeList, edgeSentinel); // walk the sorted edges from top to bottom, computing accumulated winding SkTDArray<ActiveEdge> activeEdges; OutEdgeBuilder outBuilder(asFill); @@ -2166,21 +2427,12 @@ void simplify(const SkPath& path, bool asFill, SkPath& simple) { InEdge** lastPtr = currentPtr; // find the edge below the bottom of the first set SkScalar bottom = findBottom(currentPtr, edgeList.end(), &activeEdges, y, asFill, lastPtr); -#if DEBUG_BOTTOM - SkDebugf("%s findBottom bottom=%1.9g\n", __FUNCTION__, bottom); -#endif if (lastPtr > currentPtr) { bottom = computeInterceptBottom(activeEdges, y, bottom); -#if DEBUG_BOTTOM - SkDebugf("%s computeInterceptBottom bottom=%1.9g\n", __FUNCTION__, bottom); -#endif SkTDArray<ActiveEdge*> activeEdgeList; sortHorizontal(activeEdges, activeEdgeList, y); bottom = adjustCoincident(activeEdgeList, windingMask, y, bottom, outBuilder); -#if DEBUG_BOTTOM - SkDebugf("%s adjustCoincident bottom=%1.9g\n", __FUNCTION__, bottom); -#endif stitchEdge(activeEdgeList, y, bottom, windingMask, asFill, outBuilder); } y = bottom; diff --git a/experimental/Intersection/EdgeWalkerPolygon4x4_Test.cpp b/experimental/Intersection/EdgeWalkerPolygon4x4_Test.cpp index 27ec5be90f..7054683c53 100755 --- a/experimental/Intersection/EdgeWalkerPolygon4x4_Test.cpp +++ b/experimental/Intersection/EdgeWalkerPolygon4x4_Test.cpp @@ -1,14 +1,24 @@ #include "EdgeWalker_Test.h" #include "Intersection_Tests.h" +#include "SkBitmap.h" +#include "SkCanvas.h" #include <assert.h> #include <pthread.h> - + struct State { + State() { + bitmap.setConfig(SkBitmap::kARGB_8888_Config, 150 * 2, 100); + bitmap.allocPixels(); + canvas = new SkCanvas(bitmap); + } + int a; int b; int c; int d; pthread_t threadID; + SkCanvas* canvas; + SkBitmap bitmap; bool abcIsATriangle; }; @@ -77,13 +87,13 @@ static void* testSimplify4x4QuadralateralsMain(void* data) str += sprintf(str, " path.lineTo(%d, %d);\n", hx, hy); str += sprintf(str, " path.close();"); } - if (!testSimplify(path, true, out)) { + if (!testSimplify(path, true, out, state.bitmap, state.canvas)) { SkDebugf("*/\n{ SkPath::kWinding_FillType, %d, %d, %d, %d," " %d, %d, %d, %d },\n/*\n", state.a, state.b, state.c, state.d, e, f, g, h); } path.setFillType(SkPath::kEvenOdd_FillType); - if (!testSimplify(path, true, out)) { + if (!testSimplify(path, true, out, state.bitmap, state.canvas)) { SkDebugf("*/\n{ SkPath::kEvenOdd_FillType, %d, %d, %d, %d," " %d, %d, %d, %d },\n/*\n", state.a, state.b, state.c, state.d, e, f, g, h); @@ -173,9 +183,9 @@ static void* testSimplify4x4NondegeneratesMain(void* data) { str += sprintf(str, " path.lineTo(%d, %d);\n", fx, fy); str += sprintf(str, " path.close();"); } - testSimplify(path, true, out); + testSimplify(path, true, out, state.bitmap, state.canvas); path.setFillType(SkPath::kEvenOdd_FillType); - testSimplify(path, true, out); + testSimplify(path, true, out, state.bitmap, state.canvas); } } } @@ -263,9 +273,9 @@ static void* testSimplify4x4DegeneratesMain(void* data) { str += sprintf(str, " path.lineTo(%d, %d);\n", fx, fy); str += sprintf(str, " path.close();"); } - testSimplify(path, true, out); + testSimplify(path, true, out, state.bitmap, state.canvas); path.setFillType(SkPath::kEvenOdd_FillType); - testSimplify(path, true, out); + testSimplify(path, true, out, state.bitmap, state.canvas); } } } diff --git a/experimental/Intersection/EdgeWalkerPolygons_Mismatches.cpp b/experimental/Intersection/EdgeWalkerPolygons_Mismatches.cpp index 0054cfbd26..09d6f9347e 100644 --- a/experimental/Intersection/EdgeWalkerPolygons_Mismatches.cpp +++ b/experimental/Intersection/EdgeWalkerPolygons_Mismatches.cpp @@ -1,5 +1,6 @@ #include "EdgeWalker_Test.h" #include "Intersection_Tests.h" +#include "SkBitmap.h" // edges that didn't match struct misMatch { @@ -1579,6 +1580,7 @@ size_t misMatchCount = sizeof(misMatches) / sizeof(misMatches[0]); void TestMismatches(); void TestMismatches() { + SkBitmap bitmap; for (size_t index = 0; index < misMatchCount; ++index) { const misMatch& miss = misMatches[index]; int ax = miss.a & 0x03; @@ -1609,6 +1611,6 @@ void TestMismatches() { path.lineTo(gx, gy); path.lineTo(hx, hy); path.close(); - testSimplify(path, true, out); + testSimplify(path, true, out, bitmap); } } diff --git a/experimental/Intersection/EdgeWalkerPolygons_Test.cpp b/experimental/Intersection/EdgeWalkerPolygons_Test.cpp index 7bf6452bee..f3455eec33 100644 --- a/experimental/Intersection/EdgeWalkerPolygons_Test.cpp +++ b/experimental/Intersection/EdgeWalkerPolygons_Test.cpp @@ -1,5 +1,8 @@ #include "EdgeWalker_Test.h" #include "Intersection_Tests.h" +#include "SkBitmap.h" + +static SkBitmap bitmap; static void testSimplifyTriangle() { SkPath path, out; @@ -12,7 +15,7 @@ static void testSimplifyTriangle() { path.lineTo(10,30); // /_| path.lineTo(20,30); path.close(); - testSimplify(path, true, out); // expect |\/| + testSimplify(path, true, out, bitmap); // expect |\/| // |__| } @@ -26,7 +29,7 @@ static void testSimplifyTriangle3() { path.lineTo(1, 0); path.lineTo(3, 1); path.close(); - testSimplify(path, true, out); + testSimplify(path, true, out, bitmap); } static void testSimplifyTriangle4() { @@ -39,7 +42,7 @@ static void testSimplifyTriangle4() { path.lineTo(1, 0); path.lineTo(2, 1); path.close(); - testSimplify(path, true, out); + testSimplify(path, true, out, bitmap); } static void testSimplifyTriangle5() { @@ -52,7 +55,7 @@ static void testSimplifyTriangle5() { path.lineTo(1, 1); path.lineTo(2, 1); path.close(); - testSimplify(path, true, out); + testSimplify(path, true, out, bitmap); } static void testSimplifyTriangle6() { @@ -67,7 +70,7 @@ static void testSimplifyTriangle6() { path.lineTo(3, 1); path.lineTo(0, 0); path.close(); - testSimplify(path, true, out); + testSimplify(path, true, out, bitmap); } static void testSimplifyTriangle7() { @@ -82,7 +85,7 @@ static void testSimplifyTriangle7() { path.lineTo(0, 2); path.lineTo(0, 0); path.close(); - testSimplify(path, true, out); + testSimplify(path, true, out, bitmap); } static void testSimplifyTriangle8() { @@ -97,7 +100,7 @@ static void testSimplifyTriangle8() { path.lineTo(1, 3); path.lineTo(0, 1); path.close(); - testSimplify(path, true, out); + testSimplify(path, true, out, bitmap); } static void testSimplifyTriangle9() { @@ -112,7 +115,7 @@ static void testSimplifyTriangle9() { path.lineTo(2, 1); path.lineTo(0, 0); path.close(); - testSimplify(path, true, out); + testSimplify(path, true, out, bitmap); } static void testSimplifyTriangle10() { @@ -127,7 +130,7 @@ static void testSimplifyTriangle10() { path.lineTo(0, 1); path.lineTo(0, 0); path.close(); - testSimplify(path, true, out); + testSimplify(path, true, out, bitmap); } static void testSimplifyTriangle11() { @@ -142,7 +145,7 @@ static void testSimplifyTriangle11() { path.lineTo(2, 2); path.lineTo(0, 0); path.close(); - testSimplify(path, true, out); + testSimplify(path, true, out, bitmap); } static void testSimplifyTriangle12() { @@ -157,7 +160,7 @@ static void testSimplifyTriangle12() { path.lineTo(1, 1); path.lineTo(2, 0); path.close(); - testSimplify(path, true, out); + testSimplify(path, true, out, bitmap); } static void testSimplifyTriangle13() { @@ -172,7 +175,7 @@ static void testSimplifyTriangle13() { path.lineTo(1, 1); path.lineTo(3, 0); path.close(); - testSimplify(path, true, out); + testSimplify(path, true, out, bitmap); } static void testSimplifyTriangle14() { @@ -187,7 +190,7 @@ static void testSimplifyTriangle14() { path.lineTo(0, 1); path.lineTo(0, 0); path.close(); - testSimplify(path, true, out); + testSimplify(path, true, out, bitmap); } static void testSimplifyTriangle15() { @@ -201,7 +204,7 @@ static void testSimplifyTriangle15() { path.lineTo(0, 1); path.lineTo(2, 2); path.close(); - testSimplify(path, true, out); + testSimplify(path, true, out, bitmap); } static void testSimplifyTriangle16() { @@ -214,7 +217,7 @@ static void testSimplifyTriangle16() { path.lineTo(0, 1); path.lineTo(1, 3); path.close(); - testSimplify(path, true, out); + testSimplify(path, true, out, bitmap); } static void testSimplifyTriangle17() { @@ -227,7 +230,7 @@ static void testSimplifyTriangle17() { path.lineTo(1, 3); path.lineTo(0, 1); path.close(); - testSimplify(path, true, out); + testSimplify(path, true, out, bitmap); } static void testSimplifyTriangle18() { @@ -240,7 +243,7 @@ static void testSimplifyTriangle18() { path.lineTo(0, 1); path.lineTo(0, 3); path.close(); - testSimplify(path, true, out); + testSimplify(path, true, out, bitmap); } static void testSimplifyTriangle19() { @@ -254,7 +257,7 @@ static void testSimplifyTriangle19() { path.lineTo(1, 1); path.lineTo(2, 1); path.close(); - testSimplify(path, true, out); + testSimplify(path, true, out, bitmap); } static void testSimplifyTriangle20() { @@ -267,7 +270,7 @@ static void testSimplifyTriangle20() { path.lineTo(3, 2); path.lineTo(0, 3); path.close(); - testSimplify(path, true, out); + testSimplify(path, true, out, bitmap); } static void testSimplifyTriangle21() { @@ -280,7 +283,7 @@ static void testSimplifyTriangle21() { path.lineTo(2, 1); path.lineTo(0, 3); path.close(); - testSimplify(path, true, out); + testSimplify(path, true, out, bitmap); } static void testSimplifyDegenerateTriangle1() { @@ -293,7 +296,7 @@ static void testSimplifyDegenerateTriangle1() { path.lineTo(0, 0); path.lineTo(0, 0); path.close(); - testSimplify(path, true, out); + testSimplify(path, true, out, bitmap); } static void testSimplifyDegenerateTriangle2() { @@ -306,7 +309,7 @@ static void testSimplifyDegenerateTriangle2() { path.lineTo(2, 2); path.lineTo(3, 3); path.close(); - testSimplify(path, true, out); + testSimplify(path, true, out, bitmap); } static void testSimplifyWindingParallelogram() { @@ -322,7 +325,7 @@ static void testSimplifyWindingParallelogram() { path.lineTo(20,30); // /_/ path.lineTo(30,10); path.close(); - testSimplify(path, true, out); // expect _ + testSimplify(path, true, out, bitmap); // expect _ // / \ . } // /___\ . @@ -339,7 +342,7 @@ static void testSimplifyXorParallelogram() { path.lineTo(20,30); // /_/ path.lineTo(30,10); path.close(); - testSimplify(path, true, out); // expect _ + testSimplify(path, true, out, bitmap); // expect _ } // \ / static void testSimplifyTriangle2() { @@ -353,9 +356,10 @@ static void testSimplifyTriangle2() { path.lineTo(20,10); // \ | path.lineTo(20,30); // \| path.close(); // _ - testSimplify(path, true, out); // expect | | + testSimplify(path, true, out, bitmap); // expect | | } // |_| +#if 0 static void testPathTriangleRendering() { SkPath one, two; one.moveTo(0, 0); @@ -375,10 +379,11 @@ static void testPathTriangleRendering() { two.reset(); } } +#endif static void simplify(const char* functionName, const SkPath& path, bool fill, SkPath& out) { - SkDebugf("%s\n", functionName); + if (false) SkDebugf("%s\n", functionName); simplify(path, fill, out); } @@ -525,7 +530,7 @@ static void testSimplifyTriangle22() { path.lineTo(0, 2); path.lineTo(0, 1); path.close(); - testSimplify(path, true, out); + testSimplify(path, true, out, bitmap); } static void testSimplifyTriangle23() { @@ -538,7 +543,7 @@ static void testSimplifyTriangle23() { path.lineTo(0, 1); path.lineTo(1, 2); path.close(); - testSimplify(path, true, out); + testSimplify(path, true, out, bitmap); } static void testSimplifyTriangle24() { @@ -551,7 +556,7 @@ static void testSimplifyTriangle24() { path.lineTo(1, 0); path.lineTo(0, 1); path.close(); - testSimplify(path, true, out); + testSimplify(path, true, out, bitmap); } static void testSimplifySkinnyTriangle7() { @@ -754,7 +759,7 @@ static void (*simplifyTests[])() = { testSimplifyTriangle2, testSimplifyWindingParallelogram, testSimplifyXorParallelogram, - testPathTriangleRendering, +// testPathTriangleRendering, }; static size_t simplifyTestsCount = sizeof(simplifyTests) / sizeof(simplifyTests[0]); @@ -772,7 +777,7 @@ void SimplifyPolygonPaths_Test() { for ( ; index < simplifyTestsCount; ++index) { (*simplifyTests[index])(); if (simplifyTests[index] == testSimplifySkinnyTriangle2) { - SkDebugf("%s last fast skinny test\n", __FUNCTION__); + if (false) SkDebugf("%s last fast skinny test\n", __FUNCTION__); } firstTestComplete = true; } diff --git a/experimental/Intersection/EdgeWalkerQuadralaterals_Test.cpp b/experimental/Intersection/EdgeWalkerQuadralaterals_Test.cpp index a87b37f31b..daf5af77f3 100644 --- a/experimental/Intersection/EdgeWalkerQuadralaterals_Test.cpp +++ b/experimental/Intersection/EdgeWalkerQuadralaterals_Test.cpp @@ -1,5 +1,8 @@ #include "EdgeWalker_Test.h" #include "Intersection_Tests.h" +#include "SkBitmap.h" + +static SkBitmap bitmap; static void testSimplifyQuad1() { SkPath path, out; @@ -13,7 +16,7 @@ static void testSimplifyQuad1() { path.lineTo(1, 3); path.lineTo(1, 3); path.close(); - testSimplify(path, true, out); + testSimplify(path, true, out, bitmap); } static void testSimplifyQuad2() { @@ -28,7 +31,7 @@ static void testSimplifyQuad2() { path.lineTo(1, 1); path.lineTo(0, 2); path.close(); - testSimplify(path, true, out); + testSimplify(path, true, out, bitmap); } static void testSimplifyQuad3() { @@ -43,7 +46,7 @@ static void testSimplifyQuad3() { path.lineTo(2, 1); path.lineTo(0, 2); path.close(); - testSimplify(path, true, out); + testSimplify(path, true, out, bitmap); } static void testSimplifyQuad4() { @@ -58,7 +61,7 @@ static void testSimplifyQuad4() { path.lineTo(3, 1); path.lineTo(3, 3); path.close(); - testSimplify(path, true, out); + testSimplify(path, true, out, bitmap); } static void testSimplifyQuad5() { @@ -73,7 +76,7 @@ static void testSimplifyQuad5() { path.lineTo(2, 1); path.lineTo(0, 2); path.close(); - testSimplify(path, true, out); + testSimplify(path, true, out, bitmap); } static void testSimplifyQuad6() { @@ -88,7 +91,7 @@ static void testSimplifyQuad6() { path.lineTo(1, 1); path.lineTo(2, 2); path.close(); - testSimplify(path, true, out); + testSimplify(path, true, out, bitmap); } static void (*simplifyTests[])() = { diff --git a/experimental/Intersection/EdgeWalkerQuadratics_Test.cpp b/experimental/Intersection/EdgeWalkerQuadratics_Test.cpp index ab4e39b637..584ecdabb3 100644 --- a/experimental/Intersection/EdgeWalkerQuadratics_Test.cpp +++ b/experimental/Intersection/EdgeWalkerQuadratics_Test.cpp @@ -1,5 +1,8 @@ #include "EdgeWalker_Test.h" #include "Intersection_Tests.h" +#include "SkBitmap.h" + +static SkBitmap bitmap; static void testSimplifyQuadratic1() { SkPath path, out; @@ -9,7 +12,7 @@ static void testSimplifyQuadratic1() { path.moveTo(1, 0); path.quadTo(0, 0, 0, 1); path.close(); - testSimplify(path, true, out); + testSimplify(path, true, out, bitmap); } static void testSimplifyQuadratic2() { @@ -20,8 +23,7 @@ static void testSimplifyQuadratic2() { path.moveTo(20, 0); path.quadTo(0, 0, 0, 20); path.close(); - testSimplify(path, true, out); - drawAsciiPaths(path, out, true); + testSimplify(path, true, out, bitmap); } static void testSimplifyQuadratic3() { @@ -32,11 +34,23 @@ static void testSimplifyQuadratic3() { path.moveTo(0, 20); path.quadTo(0, 0, 20, 0); path.close(); - testSimplify(path, true, out); + testSimplify(path, true, out, bitmap); +} + +static void testSimplifyQuadratic4() { + SkPath path, out; + path.moveTo(0, 20); + path.quadTo(20, 0, 40, 20); + path.close(); + path.moveTo(40, 10); + path.quadTo(20, 30, 0, 10); + path.close(); + testSimplify(path, true, out, bitmap); drawAsciiPaths(path, out, true); } static void (*simplifyTests[])() = { + testSimplifyQuadratic4, testSimplifyQuadratic3, testSimplifyQuadratic2, testSimplifyQuadratic1, diff --git a/experimental/Intersection/EdgeWalkerRectangles_Test.cpp b/experimental/Intersection/EdgeWalkerRectangles_Test.cpp index 8dc8627609..a5448e31b6 100644 --- a/experimental/Intersection/EdgeWalkerRectangles_Test.cpp +++ b/experimental/Intersection/EdgeWalkerRectangles_Test.cpp @@ -1,5 +1,8 @@ #include "EdgeWalker_Test.h" #include "Intersection_Tests.h" +#include "SkBitmap.h" + +static SkBitmap bitmap; static void testSimplifyCoincidentInner() { SkPath path, out; @@ -7,7 +10,7 @@ static void testSimplifyCoincidentInner() { 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); + testSimplify(path, true, out, bitmap); } static void testSimplifyCoincidentVertical() { @@ -304,7 +307,7 @@ static void testSimplifyOverlap() { SkPath path, out; path.addRect(rect1, static_cast<SkPath::Direction>(dir)); path.addRect(rect2, static_cast<SkPath::Direction>(dir)); - testSimplify(path, true, out); + testSimplify(path, true, out, bitmap); } } } diff --git a/experimental/Intersection/EdgeWalker_Test.h b/experimental/Intersection/EdgeWalker_Test.h index ac9743699a..1f644a7480 100644 --- a/experimental/Intersection/EdgeWalker_Test.h +++ b/experimental/Intersection/EdgeWalker_Test.h @@ -2,9 +2,13 @@ #include "ShapeOps.h" -extern bool comparePaths(const SkPath& one, const SkPath& two); +class SkBitmap; +class SkCanvas; + +//extern int comparePaths(const SkPath& one, const SkPath& two); extern void comparePathsTiny(const SkPath& one, const SkPath& two); extern bool drawAsciiPaths(const SkPath& one, const SkPath& two, bool drawPaths); extern void showPath(const SkPath& path, const char* str = NULL); -extern bool testSimplify(const SkPath& path, bool fill, SkPath& out); +extern bool testSimplify(const SkPath& path, bool fill, SkPath& out, + SkBitmap& bitmap, SkCanvas* canvas = 0); diff --git a/experimental/Intersection/EdgeWalker_TestUtility.cpp b/experimental/Intersection/EdgeWalker_TestUtility.cpp index 2cd01539ba..0b2fd06fbf 100644 --- a/experimental/Intersection/EdgeWalker_TestUtility.cpp +++ b/experimental/Intersection/EdgeWalker_TestUtility.cpp @@ -5,7 +5,7 @@ #include "SkPaint.h" static bool gShowPath = false; -static bool gComparePaths = false; +static bool gComparePaths = true; static bool gDrawLastAsciiPaths = true; static bool gDrawAllAsciiPaths = false; static bool gShowAsciiPaths = false; @@ -43,17 +43,27 @@ void showPath(const SkPath& path, const char* str) { } } -static bool pathsDrawTheSame(const SkPath& one, const SkPath& two) { +static int pathsDrawTheSame(const SkPath& one, const SkPath& two, + SkBitmap& bits, SkCanvas* c) { + SkCanvas* canvasPtr = c; + if (!c) { + canvasPtr = new SkCanvas(bits); + } const SkRect& bounds1 = one.getBounds(); const SkRect& bounds2 = two.getBounds(); SkRect larger = bounds1; larger.join(bounds2); - SkBitmap bits; int bitWidth = SkScalarCeil(larger.width()) + 2; int bitHeight = SkScalarCeil(larger.height()) + 2; - bits.setConfig(SkBitmap::kARGB_8888_Config, bitWidth * 2, bitHeight); - bits.allocPixels(); - SkCanvas canvas(bits); + if (bits.width() < bitWidth * 2 || bits.height() < bitHeight) { + if (bits.width() >= 200) { + SkDebugf("%s bitWidth=%d bitHeight=%d\n", __FUNCTION__, bitWidth, bitHeight); + } + bits.setConfig(SkBitmap::kARGB_8888_Config, bitWidth * 2, bitHeight); + bits.allocPixels(); + canvasPtr->setBitmapDevice(bits); + } + SkCanvas& canvas = *canvasPtr; canvas.drawColor(SK_ColorWHITE); SkPaint paint; canvas.save(); @@ -64,17 +74,21 @@ static bool pathsDrawTheSame(const SkPath& one, const SkPath& two) { canvas.translate(-bounds1.fLeft + 1 + bitWidth, -bounds1.fTop + 1); canvas.drawPath(two, paint); canvas.restore(); + int errors = 0; for (int y = 0; y < bitHeight; ++y) { uint32_t* addr1 = bits.getAddr32(0, y); uint32_t* addr2 = bits.getAddr32(bitWidth, y); for (int x = 0; x < bitWidth; ++x) { - if (addr1[x] != addr2[x]) { - return false; - break; - } + errors += addr1[x] != addr2[x]; } } - return true; + if (!c) { + delete canvasPtr; + } + return errors; +} + +void bitmapInit(SkBitmap& bits) { } bool drawAsciiPaths(const SkPath& one, const SkPath& two, @@ -130,8 +144,8 @@ bool drawAsciiPaths(const SkPath& one, const SkPath& two, return true; } -static bool scaledDrawTheSame(const SkPath& one, const SkPath& two, - int a, int b, bool drawPaths) { +static int scaledDrawTheSame(const SkPath& one, const SkPath& two, + int a, int b, bool drawPaths, SkBitmap& bitmap, SkCanvas* canvas) { SkMatrix scale; scale.reset(); float aScale = 1.21f; @@ -140,8 +154,9 @@ static bool scaledDrawTheSame(const SkPath& one, const SkPath& two, SkPath scaledOne, scaledTwo; one.transform(scale, &scaledOne); two.transform(scale, &scaledTwo); - if (pathsDrawTheSame(scaledOne, scaledTwo)) { - return true; + int errors = pathsDrawTheSame(scaledOne, scaledTwo, bitmap, canvas); + if (errors == 0) { + return 0; } while (!drawAsciiPaths(scaledOne, scaledTwo, drawPaths)) { scale.reset(); @@ -151,28 +166,36 @@ static bool scaledDrawTheSame(const SkPath& one, const SkPath& two, one.transform(scale, &scaledOne); two.transform(scale, &scaledTwo); } - return false; + return errors; } -bool comparePaths(const SkPath& one, const SkPath& two) { - if (pathsDrawTheSame(one, two)) { - return true; +static int comparePaths(const SkPath& one, const SkPath& two, SkBitmap& bitmap, + SkCanvas* canvas) { + int errors = pathsDrawTheSame(one, two, bitmap, canvas); + if (errors == 0) { + return 0; } drawAsciiPaths(one, two, gDrawAllAsciiPaths); for (int x = 9; x <= 33; ++x) { - if (scaledDrawTheSame(one, two, x, x - (x >> 2), gDrawAllAsciiPaths)) { - return true; + errors = scaledDrawTheSame(one, two, x, x - (x >> 2), gDrawAllAsciiPaths, + bitmap, canvas); + if (errors == 0) { + return 0; } } if (!gDrawAllAsciiPaths) { - scaledDrawTheSame(one, two, 9, 7, gDrawLastAsciiPaths); + errors = scaledDrawTheSame(one, two, 9, 7, false, bitmap, canvas); + if (errors > 4) { + scaledDrawTheSame(one, two, 9, 7, true, bitmap, canvas); + } } - if (gComparePathsAssert) { + if (errors > 0) SkDebugf("\n%s errors=%d\n", __FUNCTION__, errors); + if (errors > 4 && gComparePathsAssert) { showPath(one); showPath(two, "simplified:"); SkASSERT(0); } - return false; + return errors; } // doesn't work yet @@ -206,7 +229,8 @@ void comparePathsTiny(const SkPath& one, const SkPath& two) { } } -bool testSimplify(const SkPath& path, bool fill, SkPath& out) { +bool testSimplify(const SkPath& path, bool fill, SkPath& out, SkBitmap& bitmap, + SkCanvas* canvas) { if (gShowPath) { showPath(path); } @@ -214,5 +238,5 @@ bool testSimplify(const SkPath& path, bool fill, SkPath& out) { if (!gComparePaths) { return true; } - return comparePaths(path, out); + return comparePaths(path, out, bitmap, canvas) == 0; } diff --git a/experimental/Intersection/LineCubicIntersection.cpp b/experimental/Intersection/LineCubicIntersection.cpp index 500a91e053..8517b7e0f8 100644 --- a/experimental/Intersection/LineCubicIntersection.cpp +++ b/experimental/Intersection/LineCubicIntersection.cpp @@ -139,7 +139,25 @@ int horizontalIntersect(const Cubic& cubic, double y, double tRange[3]) { LineCubicIntersections c(cubic, *((_Line*) 0), tRange); return c.horizontalIntersect(y); } - + +int horizontalIntersect(const Cubic& cubic, double left, double right, double y, + double tRange[3]) { + LineCubicIntersections c(cubic, *((_Line*) 0), tRange); + int result = c.horizontalIntersect(y); + for (int index = 0; index < result; ) { + double x, y; + xy_at_t(cubic, tRange[index], x, y); + if (x < left || x > right) { + if (--result > index) { + tRange[index] = tRange[result]; + } + continue; + } + ++index; + } + return result; +} + int intersect(const Cubic& cubic, const _Line& line, double cRange[3], double lRange[3]) { LineCubicIntersections c(cubic, line, cRange); int roots; diff --git a/experimental/Intersection/LineQuadraticIntersection.cpp b/experimental/Intersection/LineQuadraticIntersection.cpp index 0d6477b085..737b76749d 100644 --- a/experimental/Intersection/LineQuadraticIntersection.cpp +++ b/experimental/Intersection/LineQuadraticIntersection.cpp @@ -131,6 +131,16 @@ bool intersect() { return roots > 0; } +int horizontalIntersect(double axisIntercept) { + double D = quad[2].y; // f + double E = quad[1].y; // e + double F = quad[0].y; // d + D += F - 2 * E; // D = d - 2*e + f + E -= F; // E = -(d - e) + F -= axisIntercept; + return quadraticRoots(D, E, F, intersections.fT[0]); +} + protected: double findLineT(double t) { @@ -156,7 +166,24 @@ Intersections& intersections; bool moreHorizontal; }; - + +int horizontalIntersect(const Quadratic& quad, double left, double right, + double y, double tRange[2]) { + Intersections i; + LineQuadraticIntersections q(quad, *((_Line*) 0), i); + int result = q.horizontalIntersect(y); + int tCount = 0; + for (int index = 0; index < result; ++index) { + double x, y; + xy_at_t(quad, i.fT[0][index], x, y); + if (x < left || x > right) { + continue; + } + tRange[tCount++] = i.fT[0][index]; + } + return tCount; +} + bool intersect(const Quadratic& quad, const _Line& line, Intersections& i) { LineQuadraticIntersections q(quad, line, i); return q.intersect(); diff --git a/experimental/Intersection/QuadraticIntersection.cpp b/experimental/Intersection/QuadraticIntersection.cpp index 634d083cbd..f8c43b5e5d 100644 --- a/experimental/Intersection/QuadraticIntersection.cpp +++ b/experimental/Intersection/QuadraticIntersection.cpp @@ -86,16 +86,22 @@ bool intersect(double minT1, double maxT1, double minT2, double maxT2) { double newMinT1 = interp(minT1, maxT1, minT); double newMaxT1 = interp(minT1, maxT1, maxT); split = (newMaxT1 - newMinT1 > (maxT1 - minT1) * tClipLimit) << 1; +#define VERBOSE 0 +#if VERBOSE printf("%s d=%d s=%d new1=(%g,%g) old1=(%g,%g) split=%d\n", __FUNCTION__, depth, splits, newMinT1, newMaxT1, minT1, maxT1, split); +#endif minT1 = newMinT1; maxT1 = newMaxT1; } else { double newMinT2 = interp(minT2, maxT2, minT); double newMaxT2 = interp(minT2, maxT2, maxT); split = newMaxT2 - newMinT2 > (maxT2 - minT2) * tClipLimit; +#define VERBOSE 0 +#if VERBOSE printf("%s d=%d s=%d new2=(%g,%g) old2=(%g,%g) split=%d\n", __FUNCTION__, depth, splits, newMinT2, newMaxT2, minT2, maxT2, split); +#endif minT2 = newMinT2; maxT2 = newMaxT2; } diff --git a/experimental/Intersection/ShapeOpsDemo-Info.plist b/experimental/Intersection/ShapeOpsDemo-Info.plist deleted file mode 100644 index 5dd4506c0e..0000000000 --- a/experimental/Intersection/ShapeOpsDemo-Info.plist +++ /dev/null @@ -1,32 +0,0 @@ -<?xml version="1.0" encoding="UTF-8"?> -<!DOCTYPE plist PUBLIC "-//Apple//DTD PLIST 1.0//EN" "http://www.apple.com/DTDs/PropertyList-1.0.dtd"> -<plist version="1.0"> -<dict> - <key>CFBundleDevelopmentRegion</key> - <string>English</string> - <key>CFBundleExecutable</key> - <string>${EXECUTABLE_NAME}</string> - <key>CFBundleIconFile</key> - <string></string> - <key>CFBundleIdentifier</key> - <string>com.googlecode.skia.${PRODUCT_NAME:rfc1034identifier}</string> - <key>CFBundleInfoDictionaryVersion</key> - <string>6.0</string> - <key>CFBundleName</key> - <string>${PRODUCT_NAME}</string> - <key>CFBundlePackageType</key> - <string>APPL</string> - <key>CFBundleShortVersionString</key> - <string>1.0</string> - <key>CFBundleSignature</key> - <string>????</string> - <key>CFBundleVersion</key> - <string>1</string> - <key>LSMinimumSystemVersion</key> - <string>${MACOSX_DEPLOYMENT_TARGET}</string> - <key>NSMainNibFile</key> - <string>ShapeOpsDemo</string> - <key>NSPrincipalClass</key> - <string>NSApplication</string> -</dict> -</plist> diff --git a/experimental/Intersection/ShapeOpsDemo.cpp b/experimental/Intersection/ShapeOpsDemo.cpp deleted file mode 100644 index a2690ea42a..0000000000 --- a/experimental/Intersection/ShapeOpsDemo.cpp +++ /dev/null @@ -1,110 +0,0 @@ -#include "EdgeWalker_Test.h" -#include "ShapeOps.h" -#include "SkApplication.h" -#include "SkCanvas.h" -#include "SkEvent.h" -#include "SkGraphics.h" -#include "SkPaint.h" - -SkCanvas* canvas = 0; -SkBitmap* bitmap; - -static bool test15(SkCanvas* canvas) { - // Three circles bounce inside a rectangle. The circles describe three, four - // or five points which in turn describe a polygon. The polygon points - // bounce inside the circles. The circles rotate and scale over time. The - // polygons are combined into a single path, simplified, and stroked. - static int step = 0; - const int circles = 3; - int scales[circles]; - int angles[circles]; - int locs[circles * 2]; - int pts[circles * 2 * 4]; - int c, p; - for (c = 0; c < circles; ++c) { - scales[c] = abs(10 - (step + c * 4) % 21); - angles[c] = (step + c * 6) % 600; - locs[c * 2] = abs(130 - (step + c * 9) % 261); - locs[c * 2 + 1] = abs(170 - (step + c * 11) % 341); - for (p = 0; p < 4; ++p) { - pts[c * 8 + p * 2] = abs(90 - ((step + c * 121 + p * 13) % 190)); - pts[c * 8 + p * 2 + 1] = abs(110 - ((step + c * 223 + p * 17) % 230)); - } - } - SkPath path, out; - for (c = 0; c < circles; ++c) { - for (p = 0; p < 4; ++p) { - SkScalar x = pts[c * 8 + p * 2]; - SkScalar y = pts[c * 8 + p * 2 + 1]; - x *= 3 + scales[c] / 10.0f; - y *= 3 + scales[c] / 10.0f; - SkScalar angle = angles[c] * 3.1415f * 2 / 600; - SkScalar temp = x * cos(angle) - y * sin(angle); - y = x * sin(angle) + y * cos(angle); - x = temp; - x += locs[c * 2] * 200 / 130.0f; - y += locs[c * 2 + 1] * 200 / 170.0f; - x += 50; - // y += 200; - if (p == 0) { - path.moveTo(x, y); - } else { - path.lineTo(x, y); - } - } - path.close(); - } - showPath(path, "original:"); - simplify(path, true, out); - showPath(out, "simplified:"); - SkPaint paint; - paint.setAntiAlias(true); - paint.setStyle(SkPaint::kStroke_Style); - paint.setStrokeWidth(3); - paint.setColor(0x3F007fbF); - canvas->drawPath(path, paint); - paint.setColor(0xFF60FF00); - paint.setStrokeWidth(1); - canvas->drawPath(out, paint); - ++step; - return true; -} - -static bool (*tests[])(SkCanvas* ) = { - test15, -}; - -static size_t testsCount = sizeof(tests) / sizeof(tests[0]); - -static bool (*firstTest)(SkCanvas*) = test15; - -extern "C" void* getPixels(bool* animate); -extern "C" void unlockPixels(); - -extern "C" void* getPixels(bool* animate) { - if (!canvas) { - canvas = new SkCanvas(); - bitmap = new SkBitmap(); - SkBitmap::Config config = SkBitmap::kARGB_8888_Config; - - bitmap->setConfig(config, 1100, 630); - bitmap->allocPixels(); - bitmap->setIsOpaque(true); - canvas->setBitmapDevice(*bitmap); - } - canvas->drawColor(SK_ColorWHITE); - size_t index = 0; - if (index == 0 && firstTest) { - while (index < testsCount && tests[index] != firstTest) { - ++index; - } - } - *animate = (tests[index])(canvas); - bitmap->lockPixels(); - return bitmap->getPixels(); -} - -extern "C" void unlockPixels() { - bitmap->unlockPixels(); -} - diff --git a/experimental/Intersection/edge-Info.plist b/experimental/Intersection/edge-Info.plist deleted file mode 100644 index f696cb233e..0000000000 --- a/experimental/Intersection/edge-Info.plist +++ /dev/null @@ -1,32 +0,0 @@ -<?xml version="1.0" encoding="UTF-8"?> -<!DOCTYPE plist PUBLIC "-//Apple//DTD PLIST 1.0//EN" "http://www.apple.com/DTDs/PropertyList-1.0.dtd"> -<plist version="1.0"> -<dict> - <key>CFBundleDevelopmentRegion</key> - <string>English</string> - <key>CFBundleExecutable</key> - <string>${EXECUTABLE_NAME}</string> - <key>CFBundleIconFile</key> - <string></string> - <key>CFBundleIdentifier</key> - <string>com.yourcompany.${PRODUCT_NAME:rfc1034identifier}</string> - <key>CFBundleInfoDictionaryVersion</key> - <string>6.0</string> - <key>CFBundleName</key> - <string>${PRODUCT_NAME}</string> - <key>CFBundlePackageType</key> - <string>APPL</string> - <key>CFBundleShortVersionString</key> - <string>1.0</string> - <key>CFBundleSignature</key> - <string>????</string> - <key>CFBundleVersion</key> - <string>1</string> - <key>LSMinimumSystemVersion</key> - <string>${MACOSX_DEPLOYMENT_TARGET}</string> - <key>NSMainNibFile</key> - <string>MainMenu</string> - <key>NSPrincipalClass</key> - <string>NSApplication</string> -</dict> -</plist> diff --git a/experimental/Intersection/thingsToDo.txt b/experimental/Intersection/thingsToDo.txt new file mode 100644 index 0000000000..a1d8ac01f2 --- /dev/null +++ b/experimental/Intersection/thingsToDo.txt @@ -0,0 +1,20 @@ +add unit test for quadratic horizontal intersection +add unit test for cubic horizontal intersection with left/right +add unit test for ActiveEdge::calcLeft (can currently loop forever) +does ActiveEdge::isCoincidentWith need to support quad, cubic? +figure out why variation in ActiveEdge::tooCloseToCall isn't better +why does 'lastPtr - 2' in addIntersectingTs break testSimplifyTriangle22? +add code to promote quad to cubic, or add quad/cubic intersection +figure out why testSimplifySkinnyTriangle13 fails + +for quadratics and cubics, once various T values are added, see if consecutive +Ts have ys that go up instead of down. If so, the edge needs to be broken. + +when splitting curves at inflection pts, should I retain the original curve +data and note that the first/last T are no longer 0/1 ? +I need to figure this out before I can proceed + +would it make sense to leave the InEdge alone, and add multiple copies of +ActiveEdge, pointing to the same InEdge, where the copy has only the subset +of Ts that need to be walked in reverse order? + diff --git a/gyp/shapeops_edge.gyp b/gyp/shapeops_edge.gyp index b5c9d16a3d..92007a0b64 100644 --- a/gyp/shapeops_edge.gyp +++ b/gyp/shapeops_edge.gyp @@ -66,7 +66,6 @@ '../experimental/Intersection/QuadraticUtilities.cpp', '../experimental/Intersection/RectUtilities.cpp', '../experimental/Intersection/TestUtilities.cpp', - '../experimental/Intersection/CubicIntersection.h', '../experimental/Intersection/CubicIntersection_TestData.h', '../experimental/Intersection/CubicUtilities.h', '../experimental/Intersection/CurveIntersection.h', @@ -87,6 +86,7 @@ '../experimental/Intersection/ShapeOps.h', '../experimental/Intersection/TestUtilities.h', '../experimental/Intersection/TSearch.h', + '../experimental/Intersection/thingsToDo.txt', ], 'dependencies': [ 'core.gyp:core', |