diff options
Diffstat (limited to 'experimental/Intersection/EdgeWalker.cpp')
-rw-r--r-- | experimental/Intersection/EdgeWalker.cpp | 2705 |
1 files changed, 0 insertions, 2705 deletions
diff --git a/experimental/Intersection/EdgeWalker.cpp b/experimental/Intersection/EdgeWalker.cpp deleted file mode 100644 index be3f57fcdb..0000000000 --- a/experimental/Intersection/EdgeWalker.cpp +++ /dev/null @@ -1,2705 +0,0 @@ -/* - * Copyright 2012 Google Inc. - * - * Use of this source code is governed by a BSD-style license that can be - * found in the LICENSE file. - */ - -#include "Simplify.h" - -#undef SkASSERT -#define SkASSERT(cond) while (!(cond)) { sk_throw(); } - -// FIXME: remove once debugging is complete -#if 01 // set to 1 for no debugging whatsoever - -//const bool gRunTestsInOneThread = false; - -#define DEBUG_ACTIVE_LESS_THAN 0 -#define DEBUG_ADD 0 -#define DEBUG_ADD_BOTTOM_TS 0 -#define DEBUG_ADD_INTERSECTING_TS 0 -#define DEBUG_ADJUST_COINCIDENT 0 -#define DEBUG_ASSEMBLE 0 -#define DEBUG_BOTTOM 0 -#define DEBUG_BRIDGE 0 -#define DEBUG_DUMP 0 -#define DEBUG_SORT_HORIZONTAL 0 -#define DEBUG_OUT 0 -#define DEBUG_OUT_LESS_THAN 0 -#define DEBUG_SPLIT 0 -#define DEBUG_STITCH_EDGE 0 -#define DEBUG_TRIM_LINE 0 - -#else - -//const bool gRunTestsInOneThread = true; - -#define DEBUG_ACTIVE_LESS_THAN 0 -#define DEBUG_ADD 01 -#define DEBUG_ADD_BOTTOM_TS 0 -#define DEBUG_ADD_INTERSECTING_TS 0 -#define DEBUG_ADJUST_COINCIDENT 1 -#define DEBUG_ASSEMBLE 1 -#define DEBUG_BOTTOM 0 -#define DEBUG_BRIDGE 1 -#define DEBUG_DUMP 1 -#define DEBUG_SORT_HORIZONTAL 01 -#define DEBUG_OUT 01 -#define DEBUG_OUT_LESS_THAN 0 -#define DEBUG_SPLIT 1 -#define DEBUG_STITCH_EDGE 1 -#define DEBUG_TRIM_LINE 1 - -#endif - -#if DEBUG_ASSEMBLE || DEBUG_BRIDGE -static const char* kLVerbStr[] = {"", "line", "quad", "cubic"}; -#endif -#if DEBUG_STITCH_EDGE -static const char* kUVerbStr[] = {"", "Line", "Quad", "Cubic"}; -#endif - -static int LineIntersect(const SkPoint a[2], const SkPoint b[2], - Intersections& intersections) { - const _Line aLine = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}}; - const _Line bLine = {{b[0].fX, b[0].fY}, {b[1].fX, b[1].fY}}; - return intersect(aLine, bLine, intersections); -} - -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}}; - intersect(aQuad, bLine, intersections); - return intersections.fUsed; -} - -static int CubicLineIntersect(const SkPoint a[2], const SkPoint b[3], - Intersections& intersections) { - 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}}; - return intersect(aCubic, bLine, intersections); -} - -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}}; - intersect2(aQuad, bQuad, intersections); - return intersections.fUsed; -} - -static int CubicIntersect(const SkPoint a[4], const SkPoint b[4], - Intersections& intersections) { - 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 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}}; - intersect(aCubic, bCubic, intersections); - return intersections.fUsed; -} - -static int LineIntersect(const SkPoint a[2], SkScalar left, SkScalar right, - SkScalar y, double aRange[2]) { - const _Line aLine = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}}; - 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; - xy_at_t(line, t, x, y); - out->fX = SkDoubleToScalar(x); - out->fY = SkDoubleToScalar(y); -} - -static void QuadXYAtT(const SkPoint a[3], double t, SkPoint* out) { - const Quadratic quad = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY}}; - double x, y; - xy_at_t(quad, t, x, y); - out->fX = SkDoubleToScalar(x); - out->fY = SkDoubleToScalar(y); -} - -static void CubicXYAtT(const SkPoint a[4], double t, SkPoint* out) { - const Cubic cubic = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY}, - {a[3].fX, a[3].fY}}; - double x, y; - xy_at_t(cubic, t, x, y); - out->fX = SkDoubleToScalar(x); - out->fY = SkDoubleToScalar(y); -} - -static SkScalar LineYAtT(const SkPoint a[2], double t) { - const _Line aLine = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}}; - double y; - xy_at_t(aLine, t, *(double*) 0, y); - return SkDoubleToScalar(y); -} - -static SkScalar QuadYAtT(const SkPoint a[3], double t) { - const Quadratic quad = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY}}; - double y; - xy_at_t(quad, t, *(double*) 0, y); - return SkDoubleToScalar(y); -} - -static SkScalar CubicYAtT(const SkPoint a[4], double t) { - const Cubic cubic = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY}, - {a[3].fX, a[3].fY}}; - double y; - xy_at_t(cubic, t, *(double*) 0, y); - return SkDoubleToScalar(y); -} - -static void LineSubDivide(const SkPoint a[2], double startT, double endT, - SkPoint sub[2]) { - const _Line aLine = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}}; - _Line dst; - sub_divide(aLine, startT, endT, dst); - sub[0].fX = SkDoubleToScalar(dst[0].x); - sub[0].fY = SkDoubleToScalar(dst[0].y); - sub[1].fX = SkDoubleToScalar(dst[1].x); - sub[1].fY = SkDoubleToScalar(dst[1].y); -} - -static void QuadSubDivide(const SkPoint a[3], double startT, double endT, - SkPoint sub[3]) { - const Quadratic aQuad = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, - {a[2].fX, a[2].fY}}; - Quadratic dst; - sub_divide(aQuad, startT, endT, dst); - sub[0].fX = SkDoubleToScalar(dst[0].x); - sub[0].fY = SkDoubleToScalar(dst[0].y); - sub[1].fX = SkDoubleToScalar(dst[1].x); - sub[1].fY = SkDoubleToScalar(dst[1].y); - sub[2].fX = SkDoubleToScalar(dst[2].x); - sub[2].fY = SkDoubleToScalar(dst[2].y); -} - -static void CubicSubDivide(const SkPoint a[4], double startT, double endT, - SkPoint sub[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}}; - Cubic dst; - sub_divide(aCubic, startT, endT, dst); - sub[0].fX = SkDoubleToScalar(dst[0].x); - sub[0].fY = SkDoubleToScalar(dst[0].y); - sub[1].fX = SkDoubleToScalar(dst[1].x); - sub[1].fY = SkDoubleToScalar(dst[1].y); - sub[2].fX = SkDoubleToScalar(dst[2].x); - sub[2].fY = SkDoubleToScalar(dst[2].y); - sub[3].fX = SkDoubleToScalar(dst[3].x); - sub[3].fY = SkDoubleToScalar(dst[3].y); -} - -static void QuadSubBounds(const SkPoint a[3], double startT, double endT, - SkRect& bounds) { - SkPoint dst[3]; - QuadSubDivide(a, startT, endT, dst); - bounds.fLeft = bounds.fRight = dst[0].fX; - bounds.fTop = bounds.fBottom = dst[0].fY; - for (int index = 1; index < 3; ++index) { - bounds.growToInclude(dst[index].fX, dst[index].fY); - } -} - -static void CubicSubBounds(const SkPoint a[4], double startT, double endT, - SkRect& bounds) { - SkPoint dst[4]; - CubicSubDivide(a, startT, endT, dst); - bounds.fLeft = bounds.fRight = dst[0].fX; - bounds.fTop = bounds.fBottom = dst[0].fY; - for (int index = 1; index < 4; ++index) { - bounds.growToInclude(dst[index].fX, dst[index].fY); - } -} - -static SkPath::Verb QuadReduceOrder(SkPoint a[4]) { - const Quadratic aQuad = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, - {a[2].fX, a[2].fY}}; - Quadratic dst; - int order = reduceOrder(aQuad, dst, kReduceOrder_TreatAsFill); - for (int index = 0; index < order; ++index) { - a[index].fX = SkDoubleToScalar(dst[index].x); - a[index].fY = SkDoubleToScalar(dst[index].y); - } - if (order == 1) { // FIXME: allow returning points, caller should discard - a[1] = a[0]; - return (SkPath::Verb) order; - } - return (SkPath::Verb) (order - 1); -} - -static SkPath::Verb CubicReduceOrder(SkPoint a[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}}; - Cubic dst; - int order = reduceOrder(aCubic, dst, kReduceOrder_QuadraticsAllowed, kReduceOrder_TreatAsFill); - for (int index = 0; index < order; ++index) { - a[index].fX = SkDoubleToScalar(dst[index].x); - a[index].fY = SkDoubleToScalar(dst[index].y); - } - if (order == 1) { // FIXME: allow returning points, caller should discard - a[1] = a[0]; - return (SkPath::Verb) order; - } - return (SkPath::Verb) (order - 1); -} - -static bool IsCoincident(const SkPoint a[2], const SkPoint& above, - const SkPoint& below) { - const _Line aLine = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}}; - const _Line bLine = {{above.fX, above.fY}, {below.fX, below.fY}}; - return implicit_matches_ulps(aLine, bLine, 32); -} - -/* -list of edges -bounds for edge -sort -active T - -if a contour's bounds is outside of the active area, no need to create edges -*/ - -/* given one or more paths, - find the bounds of each contour, select the active contours - for each active contour, compute a set of edges - each edge corresponds to one or more lines and curves - leave edges unbroken as long as possible - when breaking edges, compute the t at the break but leave the control points alone - - */ - -void contourBounds(const SkPath& path, SkTDArray<SkRect>& boundsArray) { - SkPath::Iter iter(path, false); - SkPoint pts[4]; - SkPath::Verb verb; - SkRect bounds; - bounds.setEmpty(); - int count = 0; - while ((verb = iter.next(pts)) != SkPath::kDone_Verb) { - switch (verb) { - case SkPath::kMove_Verb: - if (!bounds.isEmpty()) { - *boundsArray.append() = bounds; - } - bounds.set(pts[0].fX, pts[0].fY, pts[0].fX, pts[0].fY); - count = 0; - break; - case SkPath::kLine_Verb: - count = 1; - break; - case SkPath::kQuad_Verb: - count = 2; - break; - case SkPath::kCubic_Verb: - count = 3; - break; - case SkPath::kClose_Verb: - count = 0; - break; - default: - SkDEBUGFAIL("bad verb"); - return; - } - for (int i = 1; i <= count; ++i) { - bounds.growToInclude(pts[i].fX, pts[i].fY); - } - } -} - -static bool extendLine(const SkPoint line[2], const SkPoint& add) { - // FIXME: allow this to extend lines that have slopes that are nearly equal - SkScalar dx1 = line[1].fX - line[0].fX; - SkScalar dy1 = line[1].fY - line[0].fY; - SkScalar dx2 = add.fX - line[0].fX; - SkScalar dy2 = add.fY - line[0].fY; - 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]; - const SkPoint& rhFirst = rh.fPts[0]; - return first.fY == rhFirst.fY - ? first.fX < rhFirst.fX - : first.fY < rhFirst.fY; - } - - 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 { -public: - OutEdgeBuilder(bool fill) - : fFill(fill) { - } - - void addCurve(const SkPoint line[4], SkPath::Verb verb, int id, - bool closeCall) { - OutEdge& newEdge = fEdges.push_back(); - memcpy(newEdge.fPts, line, (verb + 1) * sizeof(SkPoint)); - newEdge.fVerb = 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 DEBUG_TRIM_LINE - SkDebugf("%s edge=%d %1.9g,%1.9g\n", __FUNCTION__, id, - edge.fPts[1].fX, y); -#endif - return true; - } - return false; - } - - void assemble(SkPath& simple) { - size_t listCount = fEdges.count(); - if (listCount == 0) { - return; - } - do { - size_t listIndex = 0; - int advance = 1; - while (listIndex < listCount && fTops[listIndex] == 0) { - ++listIndex; - } - if (listIndex >= listCount) { - break; - } - int closeEdgeIndex = -listIndex - 1; - // the curve is deferred and not added right away because the - // following edge may extend the first curve. - SkPoint firstPt, lastCurve[4]; - uint8_t lastVerb; -#if DEBUG_ASSEMBLE - int firstIndex, lastIndex; - const int tab = 8; -#endif - bool doMove = true; - int edgeIndex; - do { - SkPoint* ptArray = fEdges[listIndex].fPts; - uint8_t verb = fEdges[listIndex].fVerb; - SkPoint* curve[4]; - if (advance < 0) { - curve[0] = &ptArray[verb]; - if (verb == SkPath::kCubic_Verb) { - curve[1] = &ptArray[2]; - curve[2] = &ptArray[1]; - } - curve[verb] = &ptArray[0]; - } else { - curve[0] = &ptArray[0]; - if (verb == SkPath::kCubic_Verb) { - curve[1] = &ptArray[1]; - curve[2] = &ptArray[2]; - } - curve[verb] = &ptArray[verb]; - } - if (verb == SkPath::kQuad_Verb) { - curve[1] = &ptArray[1]; - } - if (doMove) { - firstPt = *curve[0]; - simple.moveTo(curve[0]->fX, curve[0]->fY); -#if DEBUG_ASSEMBLE - SkDebugf("%s %d moveTo (%g,%g)\n", __FUNCTION__, - listIndex + 1, curve[0]->fX, curve[0]->fY); - firstIndex = listIndex; -#endif - for (int index = 0; index <= verb; ++index) { - lastCurve[index] = *curve[index]; - } - doMove = false; - } else { - bool gap = lastCurve[lastVerb] != *curve[0]; - if (gap || lastVerb != SkPath::kLine_Verb) { // output the accumulated curve before the gap - // FIXME: see comment in bridge -- this probably - // conceals errors - SkASSERT(fFill && UlpsDiff(lastCurve[lastVerb].fY, - curve[0]->fY) <= 10); - switch (lastVerb) { - case SkPath::kLine_Verb: - simple.lineTo(lastCurve[1].fX, lastCurve[1].fY); - break; - case SkPath::kQuad_Verb: - simple.quadTo(lastCurve[1].fX, lastCurve[1].fY, - lastCurve[2].fX, lastCurve[2].fY); - break; - case SkPath::kCubic_Verb: - simple.cubicTo(lastCurve[1].fX, lastCurve[1].fY, - lastCurve[2].fX, lastCurve[2].fY, - lastCurve[3].fX, lastCurve[3].fY); - break; - } -#if DEBUG_ASSEMBLE - SkDebugf("%*s %d %sTo (%g,%g)\n", tab, "", lastIndex + 1, - kLVerbStr[lastVerb], lastCurve[lastVerb].fX, - lastCurve[lastVerb].fY); -#endif - } - int firstCopy = 1; - if (gap || (lastVerb == SkPath::kLine_Verb - && (verb != SkPath::kLine_Verb - || !extendLine(lastCurve, *curve[verb])))) { - // FIXME: see comment in bridge -- this probably - // conceals errors - SkASSERT(lastCurve[lastVerb] == *curve[0] || - (fFill && UlpsDiff(lastCurve[lastVerb].fY, - curve[0]->fY) <= 10)); - simple.lineTo(curve[0]->fX, curve[0]->fY); -#if DEBUG_ASSEMBLE - SkDebugf("%*s %d gap lineTo (%g,%g)\n", tab, "", - lastIndex + 1, curve[0]->fX, curve[0]->fY); -#endif - firstCopy = 0; - } else if (lastVerb != SkPath::kLine_Verb) { - firstCopy = 0; - } - for (int index = firstCopy; index <= verb; ++index) { - lastCurve[index] = *curve[index]; - } - } - lastVerb = verb; -#if DEBUG_ASSEMBLE - lastIndex = listIndex; -#endif - if (advance < 0) { - edgeIndex = fTops[listIndex]; - fTops[listIndex] = 0; - } else { - edgeIndex = fBottoms[listIndex]; - fBottoms[listIndex] = 0; - } - if (edgeIndex) { - listIndex = abs(edgeIndex) - 1; - if (edgeIndex < 0) { - fTops[listIndex] = 0; - } else { - fBottoms[listIndex] = 0; - } - } - if (edgeIndex == closeEdgeIndex || edgeIndex == 0) { - switch (lastVerb) { - case SkPath::kLine_Verb: - simple.lineTo(lastCurve[1].fX, lastCurve[1].fY); - break; - case SkPath::kQuad_Verb: - simple.quadTo(lastCurve[1].fX, lastCurve[1].fY, - lastCurve[2].fX, lastCurve[2].fY); - break; - case SkPath::kCubic_Verb: - simple.cubicTo(lastCurve[1].fX, lastCurve[1].fY, - lastCurve[2].fX, lastCurve[2].fY, - lastCurve[3].fX, lastCurve[3].fY); - break; - } -#if DEBUG_ASSEMBLE - SkDebugf("%*s %d %sTo last (%g, %g)\n", tab, "", - lastIndex + 1, kLVerbStr[lastVerb], - lastCurve[lastVerb].fX, lastCurve[lastVerb].fY); -#endif - if (lastCurve[lastVerb] != firstPt) { - simple.lineTo(firstPt.fX, firstPt.fY); -#if DEBUG_ASSEMBLE - SkDebugf("%*s %d final line (%g, %g)\n", tab, "", - firstIndex + 1, firstPt.fX, firstPt.fY); -#endif - } - simple.close(); -#if DEBUG_ASSEMBLE - SkDebugf("%*s close\n", tab, ""); -#endif - break; - } - // if this and next edge go different directions -#if DEBUG_ASSEMBLE - SkDebugf("%*s advance=%d edgeIndex=%d flip=%s\n", tab, "", - advance, edgeIndex, advance > 0 ^ edgeIndex < 0 ? - "true" : "false"); -#endif - if (advance > 0 ^ edgeIndex < 0) { - advance = -advance; - } - } while (edgeIndex); - } while (true); - } - - // sort points by y, then x - // if x/y is identical, sort bottoms before tops - // if identical and both tops/bottoms, sort by angle - static bool lessThan(SkTArray<OutEdge>& edges, const int one, - const int two) { - const OutEdge& oneEdge = edges[abs(one) - 1]; - int oneIndex = one < 0 ? 0 : oneEdge.fVerb; - const SkPoint& startPt1 = oneEdge.fPts[oneIndex]; - const OutEdge& twoEdge = edges[abs(two) - 1]; - int twoIndex = two < 0 ? 0 : twoEdge.fVerb; - const SkPoint& startPt2 = twoEdge.fPts[twoIndex]; - if (startPt1.fY != startPt2.fY) { - #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 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]; - const SkPoint& endPt2 = twoEdge.fPts[twoIndex ^ twoEdge.fVerb]; - SkScalar dy1 = startPt1.fY - endPt1.fY; - SkScalar dy2 = startPt2.fY - endPt2.fY; - SkScalar dy1y2 = dy1 * dy2; - if (dy1y2 < 0) { // different signs - #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 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 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; - } - - // Sort the indices of paired points and then create more indices so - // assemble() can find the next edge and connect the top or bottom - void bridge() { - size_t index; - size_t count = fEdges.count(); - if (!count) { - return; - } - SkASSERT(!fFill || count > 1); - fTops.setCount(count); - sk_bzero(fTops.begin(), sizeof(fTops[0]) * count); - fBottoms.setCount(count); - sk_bzero(fBottoms.begin(), sizeof(fBottoms[0]) * count); - SkTDArray<int> order; - for (index = 1; index <= count; ++index) { - *order.append() = -index; - } - for (index = 1; index <= count; ++index) { - *order.append() = index; - } - QSort<SkTArray<OutEdge>, int>(fEdges, order.begin(), order.end() - 1, lessThan); - int* lastPtr = order.end() - 1; - int* leftPtr = order.begin(); - while (leftPtr < lastPtr) { - int leftIndex = *leftPtr; - int leftOutIndex = abs(leftIndex) - 1; - const OutEdge& left = fEdges[leftOutIndex]; - int* rightPtr = leftPtr + 1; - int rightIndex = *rightPtr; - int rightOutIndex = abs(rightIndex) - 1; - const OutEdge& right = fEdges[rightOutIndex]; - bool pairUp = fFill; - if (!pairUp) { - const SkPoint& leftMatch = - left.fPts[leftIndex < 0 ? 0 : left.fVerb]; - const SkPoint& rightMatch = - right.fPts[rightIndex < 0 ? 0 : right.fVerb]; - pairUp = leftMatch == rightMatch; - } else { - #if DEBUG_OUT - // FIXME : not happy that error in low bit is allowed - // this probably conceals error elsewhere - if (UlpsDiff(left.fPts[leftIndex < 0 ? 0 : left.fVerb].fY, - right.fPts[rightIndex < 0 ? 0 : right.fVerb].fY) > 1) { - *fMismatches.append() = leftIndex; - if (rightPtr == lastPtr) { - *fMismatches.append() = rightIndex; - } - pairUp = false; - } - #else - SkASSERT(UlpsDiff(left.fPts[leftIndex < 0 ? 0 : left.fVerb].fY, - right.fPts[rightIndex < 0 ? 0 : right.fVerb].fY) <= 10); - #endif - } - if (pairUp) { - if (leftIndex < 0) { - fTops[leftOutIndex] = rightIndex; - } else { - fBottoms[leftOutIndex] = rightIndex; - } - if (rightIndex < 0) { - fTops[rightOutIndex] = leftIndex; - } else { - fBottoms[rightOutIndex] = leftIndex; - } - ++rightPtr; - } - 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 -#if DEBUG_BRIDGE - for (index = 0; index < count; ++index) { - const OutEdge& edge = fEdges[index]; - uint8_t verb = edge.fVerb; - SkDebugf("%s %d edge=%d %s (%1.9g,%1.9g) (%1.9g,%1.9g)\n", - index == 0 ? __FUNCTION__ : " ", - index + 1, edge.fID, kLVerbStr[verb], edge.fPts[0].fX, - edge.fPts[0].fY, edge.fPts[verb].fX, edge.fPts[verb].fY); - } - for (index = 0; index < count; ++index) { - SkDebugf(" top of % 2d connects to %s of % 2d\n", index + 1, - fTops[index] < 0 ? "top " : "bottom", abs(fTops[index])); - SkDebugf(" bottom of % 2d connects to %s of % 2d\n", index + 1, - fBottoms[index] < 0 ? "top " : "bottom", abs(fBottoms[index])); - } -#endif - } - -protected: - SkTArray<OutEdge> fEdges; - 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. -struct Bounds : public SkRect { - static bool Intersects(const Bounds& a, const Bounds& b) { - return a.fLeft <= b.fRight && b.fLeft <= a.fRight && - a.fTop <= b.fBottom && b.fTop <= a.fBottom; - } - - bool isEmpty() { - return fLeft > fRight || fTop > fBottom - || (fLeft == fRight && fTop == fBottom) - || isnan(fLeft) || isnan(fRight) - || isnan(fTop) || isnan(fBottom); - } -}; - -class Intercepts { -public: - Intercepts() - : fTopIntercepts(0) - , fBottomIntercepts(0) - , fExplicit(false) { - } - - Intercepts& operator=(const Intercepts& src) { - fTs = src.fTs; - fTopIntercepts = src.fTopIntercepts; - fBottomIntercepts = src.fBottomIntercepts; - return *this; - } - - // 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 - void dump(const SkPoint* pts, SkPath::Verb verb) { - const char className[] = "Intercepts"; - const int tab = 8; - for (int i = 0; i < fTs.count(); ++i) { - SkPoint out; - switch (verb) { - case SkPath::kLine_Verb: - LineXYAtT(pts, fTs[i], &out); - break; - case SkPath::kQuad_Verb: - QuadXYAtT(pts, fTs[i], &out); - break; - case SkPath::kCubic_Verb: - CubicXYAtT(pts, fTs[i], &out); - break; - default: - SkASSERT(0); - } - 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=%u\n", tab + sizeof(className), - className, fTopIntercepts); - SkDebugf("%*s.fBottomIntercepts=%u\n", tab + sizeof(className), - className, fBottomIntercepts); - SkDebugf("%*s.fExplicit=%d\n", tab + sizeof(className), - className, fExplicit); - } -#endif - - SkTDArray<double> fTs; - 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 { - 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=%1.9g\n", tab + sizeof(className), className, fLeft); - SkDebugf("%*s.fRight=%1.9g\n", tab + sizeof(className), className, fRight); - SkDebugf("%*s.fY=%1.9g\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 - ? fBounds.fLeft < rh.fBounds.fLeft - : fBounds.fTop < rh.fBounds.fTop; - } - - // 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]; - 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; - for (size_t idx2 = 0; idx2 < tCount; ++idx2) { - if (t <= intercepts.fTs[idx2]) { - // FIXME: ? if (t < intercepts.fTs[idx2]) // failed - delta = intercepts.fTs[idx2] - t; - if (delta > 0) { - insertedAt = idx2; - *intercepts.fTs.insert(idx2) = t; - } - goto nextPt; - } - } - if (tCount == 0 || (delta = t - intercepts.fTs[tCount - 1]) > 0) { - insertedAt = tCount; - *intercepts.fTs.append() = t; - } - nextPt: - ; - } - fContainsIntercepts |= foundIntercept; - return insertedAt; - } - - void addPartial(SkTArray<InEdge>& edges, 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->fWinding = fWinding; - edge->fContainsIntercepts = fContainsIntercepts; // FIXME: may not be correct -- but do we need to know? - } - - void addSplit(SkTArray<InEdge>& edges, SkPoint* pts, uint8_t verb, - Intercepts& intercepts, int firstT, int lastT, bool flipped) { - InEdge* edge = edges.push_back_n(1); - edge->fIntercepts.push_back_n(1); - if (firstT == 0) { - *edge->fIntercepts[0].fTs.append() = 0; - } else { - *edge->fIntercepts[0].fTs.append() = intercepts.fTs[firstT - 1]; - } - bool add1 = lastT == intercepts.fTs.count(); - edge->fIntercepts[0].fTs.append(lastT - firstT, &intercepts.fTs[firstT]); - if (add1) { - *edge->fIntercepts[0].fTs.append() = 1; - } - edge->fIntercepts[0].fExplicit = true; - edge->fPts.append(verb + 1, pts); - edge->fVerbs.append(1, &verb); - // FIXME: bounds could be better for partial Ts - edge->setSubBounds(); - edge->fContainsIntercepts = fContainsIntercepts; // FIXME: may not be correct -- but do we need to know? - if (flipped) { - edge->flipTs(); - edge->fWinding = -fWinding; - } else { - edge->fWinding = fWinding; - } - } - - bool cached(const InEdge* edge) { - // FIXME: in the pathological case where there is a ton of edges, binary search? - size_t count = fCached.count(); - for (size_t index = 0; index < count; ++index) { - if (edge == fCached[index]) { - return true; - } - if (edge < fCached[index]) { - *fCached.insert(index) = edge; - return false; - } - } - *fCached.append() = edge; - return false; - } - - void complete(signed char winding) { - setBounds(); - fIntercepts.push_back_n(fVerbs.count()); - if ((fWinding = winding) < 0) { // reverse verbs, pts, if bottom to top - flip(); - } - fContainsIntercepts = fIntersected = false; - } - - 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 flipTs() { - SkASSERT(fIntercepts.count() == 1); - Intercepts& intercepts = fIntercepts[0]; - SkASSERT(intercepts.fExplicit); - SkTDArray<double>& ts = intercepts.fTs; - size_t index; - size_t last = ts.count() - 1; - for (index = 0; index < last; ++index, --last) { - SkTSwap<double>(ts[index], ts[last]); - } - } - - void reset() { - fCached.reset(); - fIntercepts.reset(); - fPts.reset(); - fVerbs.reset(); - fBounds.set(SK_ScalarMax, SK_ScalarMax, SK_ScalarMax, SK_ScalarMax); - fWinding = 0; - fContainsIntercepts = false; - fIntersected = false; - } - - void setBounds() { - SkPoint* ptPtr = fPts.begin(); - SkPoint* ptLast = fPts.end(); - if (ptPtr == ptLast) { - SkDebugf("%s empty edge\n", __FUNCTION__); - SkASSERT(0); - // FIXME: delete empty edge? - return; - } - fBounds.set(ptPtr->fX, ptPtr->fY, ptPtr->fX, ptPtr->fY); - ++ptPtr; - while (ptPtr != ptLast) { - fBounds.growToInclude(ptPtr->fX, ptPtr->fY); - ++ptPtr; - } - } - - // recompute bounds based on subrange of T values - void setSubBounds() { - SkASSERT(fIntercepts.count() == 1); - Intercepts& intercepts = fIntercepts[0]; - SkASSERT(intercepts.fExplicit); - SkASSERT(fVerbs.count() == 1); - SkTDArray<double>& ts = intercepts.fTs; - if (fVerbs[0] == SkPath::kQuad_Verb) { - SkASSERT(fPts.count() == 3); - QuadSubBounds(fPts.begin(), ts[0], ts[ts.count() - 1], fBounds); - } else { - SkASSERT(fVerbs[0] == SkPath::kCubic_Verb); - SkASSERT(fPts.count() == 4); - CubicSubBounds(fPts.begin(), ts[0], ts[ts.count() - 1], fBounds); - } - } - - void splitInflectionPts(SkTArray<InEdge>& edges) { - 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 = (size_t) -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, lastPt, nextPt, lastVerb, nextVerb); - #if DEBUG_SPLIT - SkDebugf("%s addPartial 1\n", __FUNCTION__); - #endif - } - lastPt = nextPt; - lastVerb = nextVerb; - } - } else { - if (firstSplit >= 0) { - if (lastSplit < firstSplit) { - addSplit(edges, pts, verb, intercepts, - lastSplit, firstSplit, false); - #if DEBUG_SPLIT - SkDebugf("%s addSplit 1 tIndex=%d,%d\n", - __FUNCTION__, lastSplit, firstSplit); - #endif - } - addSplit(edges, pts, verb, intercepts, - firstSplit, tIndex, true); - #if DEBUG_SPLIT - SkDebugf("%s addSplit 2 tIndex=%d,%d flip\n", - __FUNCTION__, firstSplit, tIndex); - #endif - lastSplit = tIndex; - firstSplit = -1; - } - } - y = nextY; - } - if (curveSplit) { - if (firstSplit < 0) { - firstSplit = lastSplit; - } else { - addSplit(edges, pts, verb, intercepts, lastSplit, - firstSplit, false); - #if DEBUG_SPLIT - SkDebugf("%s addSplit 3 tIndex=%d,%d\n", __FUNCTION__, - lastSplit, firstSplit); - #endif - } - addSplit(edges, pts, verb, intercepts, firstSplit, - tIndex, pts[verb].fY < y); - #if DEBUG_SPLIT - SkDebugf("%s addSplit 4 tIndex=%d,%d %s\n", __FUNCTION__, - firstSplit, tIndex, pts[verb].fY < y ? "flip" : ""); - #endif - } - } - // 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, lastPt, nextPt, lastVerb, nextVerb); - #if DEBUG_SPLIT - SkDebugf("%s addPartial 2\n", __FUNCTION__); - #endif - } - // OPTIMIZATION: reuse the edge instead of marking it empty - reset(); - } - } - -#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); - fIntercepts[i].dump(pts, (SkPath::Verb) *verbs); - pts += *verbs++; - } - for (i = 0; i < fPts.count(); ++i) { - SkDebugf("%*s.fPts[%d]=(%1.9g,%1.9g)\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=(%1.9g, %1.9g, %1.9g, %1.9g)\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); - SkDebugf("%*s.fIntersected=%d\n", tab + sizeof(className), - className, fIntersected); - } -#endif - - // FIXME: temporary data : move this to a separate struct? - SkTDArray<const InEdge*> fCached; // list of edges already intercepted - SkTArray<Intercepts> fIntercepts; // one per verb - - // persistent data - SkTDArray<SkPoint> fPts; - SkTDArray<uint8_t> fVerbs; - Bounds fBounds; - int fID; - signed char fWinding; - bool fContainsIntercepts; - bool fIntersected; -}; - -class InEdgeBuilder { -public: - -InEdgeBuilder(const SkPath& path, bool ignoreHorizontal, SkTArray<InEdge>& edges, - SkTDArray<HorizontalEdge>& horizontalEdges) - : fPath(path) - , fCurrentEdge(NULL) - , fEdges(edges) - , fHorizontalEdges(horizontalEdges) - , fIgnoreHorizontal(ignoreHorizontal) - , fContainsCurves(false) -{ - walk(); -} - -bool containsCurves() const { - return fContainsCurves; -} - -protected: - -void addEdge() { - SkASSERT(fCurrentEdge); - fCurrentEdge->fPts.append(fPtCount - fPtOffset, &fPts[fPtOffset]); - fPtOffset = 1; - *fCurrentEdge->fVerbs.append() = fVerb; -} - -bool complete() { - if (fCurrentEdge && fCurrentEdge->fVerbs.count()) { - fCurrentEdge->complete(fWinding); - fCurrentEdge = NULL; - return true; - } - return false; -} - -int direction(SkPath::Verb verb) { - fPtCount = verb + 1; - if (fIgnoreHorizontal && isHorizontal()) { - return 0; - } - return fPts[0].fY == fPts[verb].fY - ? fPts[0].fX == fPts[verb].fX ? 0 : fPts[0].fX < fPts[verb].fX - ? 1 : -1 : fPts[0].fY < fPts[verb].fY ? 1 : -1; -} - -bool isHorizontal() { - SkScalar y = fPts[0].fY; - for (int i = 1; i < fPtCount; ++i) { - if (fPts[i].fY != y) { - return false; - } - } - return true; -} - -void startEdge() { - if (!fCurrentEdge) { - fCurrentEdge = fEdges.push_back_n(1); - } - fWinding = 0; - fPtOffset = 0; -} - -void walk() { - SkPath::Iter iter(fPath, true); - int winding = 0; - while ((fVerb = iter.next(fPts)) != SkPath::kDone_Verb) { - switch (fVerb) { - case SkPath::kMove_Verb: - startEdge(); - continue; - case SkPath::kLine_Verb: - winding = direction(SkPath::kLine_Verb); - break; - case SkPath::kQuad_Verb: - fVerb = QuadReduceOrder(fPts); - winding = direction(fVerb); - fContainsCurves |= fVerb == SkPath::kQuad_Verb; - break; - case SkPath::kCubic_Verb: - fVerb = CubicReduceOrder(fPts); - winding = direction(fVerb); - fContainsCurves |= fVerb >= SkPath::kQuad_Verb; - break; - case SkPath::kClose_Verb: - SkASSERT(fCurrentEdge); - complete(); - continue; - default: - SkDEBUGFAIL("bad verb"); - return; - } - 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(); - } - continue; - } - if (fWinding + winding == 0) { - // FIXME: if prior verb or this verb is a horizontal line, reverse - // it instead of starting a new edge - SkASSERT(fCurrentEdge); - if (complete()) { - startEdge(); - } - } - fWinding = winding; - addEdge(); - } - if (!complete()) { - if (fCurrentEdge) { - fEdges.pop_back(); - } - } -} - -private: - const SkPath& fPath; - InEdge* fCurrentEdge; - SkTArray<InEdge>& fEdges; - SkTDArray<HorizontalEdge>& fHorizontalEdges; - SkPoint fPts[4]; - SkPath::Verb fVerb; - int fPtCount; - int fPtOffset; - int8_t fWinding; - bool fIgnoreHorizontal; - bool fContainsCurves; -}; - -struct WorkEdge { - SkScalar bottom() const { - return fPts[verb()].fY; - } - - void init(const InEdge* edge) { - fEdge = edge; - fPts = edge->fPts.begin(); - fVerb = edge->fVerbs.begin(); - } - - bool advance() { - SkASSERT(fVerb < fEdge->fVerbs.end()); - fPts += *fVerb++; - return fVerb != fEdge->fVerbs.end(); - } - - const SkPoint* lastPoints() const { - SkASSERT(fPts >= fEdge->fPts.begin() + lastVerb()); - return &fPts[-lastVerb()]; - } - - SkPath::Verb lastVerb() const { - SkASSERT(fVerb > fEdge->fVerbs.begin()); - return (SkPath::Verb) fVerb[-1]; - } - - const SkPoint* points() const { - return fPts; - } - - SkPath::Verb verb() const { - return (SkPath::Verb) *fVerb; - } - - ptrdiff_t verbIndex() const { - return fVerb - fEdge->fVerbs.begin(); - } - - int winding() const { - return fEdge->fWinding; - } - - const InEdge* fEdge; - const SkPoint* fPts; - const uint8_t* fVerb; -}; - -// always constructed with SkTDArray because new edges are inserted -// this may be a inappropriate optimization, suggesting that a separate array of -// ActiveEdge* may be faster to insert and search - -// OPTIMIZATION: Brian suggests that global sorting should be unnecessary, since -// as active edges are introduced, only local sorting should be required -class ActiveEdge { -public: - // this logic must be kept in sync with tooCloseToCall - // callers expect this to only read fAbove, fTangent - bool operator<(const ActiveEdge& rh) const { - if (fVerb == rh.fVerb) { - // FIXME: don't know what to do if verb is quad, cubic - return abCompare(fAbove, fBelow, rh.fAbove, rh.fBelow); - } - // figure out which is quad, line - // if cached data says line did not intersect quad, use top/bottom - if (fVerb != SkPath::kLine_Verb ? noIntersect(rh) : rh.noIntersect(*this)) { - return abCompare(fAbove, fBelow, rh.fAbove, rh.fBelow); - } - // use whichever of top/tangent tangent/bottom overlaps more - // with line top/bot - // assumes quad/cubic can already be upconverted to cubic/cubic - const SkPoint* line[2]; - const SkPoint* curve[4]; - if (fVerb != SkPath::kLine_Verb) { - line[0] = &rh.fAbove; - line[1] = &rh.fBelow; - curve[0] = &fAbove; - curve[1] = &fTangent; - curve[2] = &fBelow; - } else { - line[0] = &fAbove; - line[1] = &fBelow; - curve[0] = &rh.fAbove; - curve[1] = &rh.fTangent; - curve[2] = &rh.fBelow; - } - // FIXME: code has been abandoned, incomplete.... - return false; - } - - bool abCompare(const SkPoint& a1, const SkPoint& a2, const SkPoint& b1, - const SkPoint& b2) const { - double topD = a1.fX - b1.fX; - if (b1.fY < a1.fY) { - topD = (b2.fY - b1.fY) * topD - (a1.fY - b1.fY) * (b2.fX - b1.fX); - } else if (b1.fY > a1.fY) { - topD = (a2.fY - a1.fY) * topD + (b1.fY - a1.fY) * (a2.fX - a1.fX); - } - double botD = a2.fX - b2.fX; - if (b2.fY > a2.fY) { - botD = (b2.fY - b1.fY) * botD - (a2.fY - b2.fY) * (b2.fX - b1.fX); - } else if (b2.fY < a2.fY) { - botD = (a2.fY - a1.fY) * botD + (b2.fY - a2.fY) * (a2.fX - a1.fX); - } - // return sign of greater absolute value - return (fabs(topD) > fabs(botD) ? topD : botD) < 0; - } - - // 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) { - if (fWorkEdge.fPts[0].fY > y) { - backup(y); - } - SkScalar left = fWorkEdge.fPts[0].fX; - SkScalar right = fWorkEdge.fPts[1].fX; - if (left > right) { - SkTSwap(left, right); - } - double ts[2]; - SkASSERT(fWorkEdge.fVerb[0] == SkPath::kLine_Verb); - 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 DEBUG_ADJUST_COINCIDENT - SkDebugf("%s edge=%d y=%1.9g t=%1.9g\n", __FUNCTION__, ID(), y, ts[0]); - #endif - if (insertedAt >= 0) { - if (insertedAt + 1 < fTIndex) { - SkASSERT(insertedAt + 2 == fTIndex); - --fTIndex; - } - } - } - - bool advanceT() { - SkASSERT(fTIndex <= fTs->count() - fExplicitTs); - return ++fTIndex <= fTs->count() - fExplicitTs; - } - - bool advance() { - // FIXME: flip sense of next - bool result = fWorkEdge.advance(); - fDone = !result; - initT(); - return result; - } - - void backup(SkScalar y) { - do { - SkASSERT(fWorkEdge.fEdge->fVerbs.begin() < fWorkEdge.fVerb); - fWorkEdge.fPts -= *--fWorkEdge.fVerb; - SkASSERT(fWorkEdge.fEdge->fPts.begin() <= fWorkEdge.fPts); - } while (fWorkEdge.fPts[0].fY >= y); - initT(); - SkASSERT(!fExplicitTs); - fTIndex = fTs->count() + 1; - } - - void calcAboveBelow(double tAbove, double tBelow) { - fVerb = fWorkEdge.verb(); - switch (fVerb) { - case SkPath::kLine_Verb: - LineXYAtT(fWorkEdge.fPts, tAbove, &fAbove); - LineXYAtT(fWorkEdge.fPts, tBelow, &fTangent); - fBelow = fTangent; - break; - case SkPath::kQuad_Verb: - // FIXME: put array in struct to avoid copy? - SkPoint quad[3]; - QuadSubDivide(fWorkEdge.fPts, tAbove, tBelow, quad); - fAbove = quad[0]; - fTangent = quad[0] != quad[1] ? quad[1] : quad[2]; - fBelow = quad[2]; - break; - case SkPath::kCubic_Verb: - SkPoint cubic[3]; - CubicSubDivide(fWorkEdge.fPts, tAbove, tBelow, cubic); - fAbove = cubic[0]; - // FIXME: can't see how quad logic for how tangent is used - // extends to cubic - fTangent = cubic[0] != cubic[1] ? cubic[1] - : cubic[0] != cubic[2] ? cubic[2] : cubic[3]; - fBelow = cubic[3]; - break; - default: - SkASSERT(0); - } - } - - void calcLeft(SkScalar y) { - // OPTIMIZE: put a kDone_Verb at the end of the verb list? - if (fDone || fBelow.fY > y) { - return; // nothing to do; use last - } - calcLeft(); - if (fAbove.fY == fBelow.fY) { - SkDebugf("%s edge=%d fAbove.fY != fBelow.fY %1.9g\n", __FUNCTION__, - ID(), fAbove.fY); - } - } - - void calcLeft() { - int add = (fTIndex <= fTs->count() - fExplicitTs) - 1; - double tAbove = t(fTIndex + add); - double tBelow = t(fTIndex - ~add); - // OPTIMIZATION: if fAbove, fBelow have already been computed - // for the fTIndex, don't do it again - calcAboveBelow(tAbove, tBelow); - // For identical x, this lets us know which edge is first. - // If both edges have T values < 1, check x at next T (fBelow). - 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; - SkASSERT(fTIndex + add >= 0); - tAbove = t(fTIndex + add); - } else { - add += 1; - SkASSERT(fTIndex - ~add <= fTs->count() + 1); - tBelow = t(fTIndex - ~add); - } - calcAboveBelow(tAbove, tBelow); - } - fTAbove = tAbove; - fTBelow = tBelow; - } - - bool done(SkScalar bottom) const { - return fDone || fYBottom >= bottom; - } - - void fixBelow() { - if (fFixBelow) { - fTBelow = nextT(); - calcAboveBelow(fTAbove, fTBelow); - fFixBelow = false; - } - } - - void init(const InEdge* edge) { - fWorkEdge.init(edge); - fDone = false; - initT(); - fBelow.fY = SK_ScalarMin; - fYBottom = SK_ScalarMin; - } - - void initT() { - const Intercepts& intercepts = fWorkEdge.fEdge->fIntercepts.front(); - SkASSERT(fWorkEdge.verbIndex() <= fWorkEdge.fEdge->fIntercepts.count()); - const Intercepts* interceptPtr = &intercepts + fWorkEdge.verbIndex(); - 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 - fTIndex = 0; - if (!fDone) { - fVerb = fWorkEdge.verb(); - } - SkASSERT(fVerb > SkPath::kMove_Verb); - } - - // OPTIMIZATION: record if two edges are coincident when the are intersected - // It's unclear how to do this -- seems more complicated than recording the - // t values, since the same t values could exist intersecting non-coincident - // edges. - bool isCoincidentWith(const ActiveEdge* edge) const { - if (fAbove != edge->fAbove || fBelow != edge->fBelow) { - return false; - } - if (fVerb != edge->fVerb) { - return false; - } - switch (fVerb) { - case SkPath::kLine_Verb: - return true; - default: - // FIXME: add support for quads, cubics - SkASSERT(0); - return false; - } - return false; - } - - bool isUnordered(const ActiveEdge* edge) const { - return fAbove == edge->fAbove && fBelow == edge->fBelow; - } - -// SkPath::Verb lastVerb() const { -// return fDone ? fWorkEdge.lastVerb() : fWorkEdge.verb(); -// } - - const SkPoint* lastPoints() const { - return fDone ? fWorkEdge.lastPoints() : fWorkEdge.points(); - } - - bool noIntersect(const ActiveEdge& ) const { - // incomplete - 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 DEBUG_ADJUST_COINCIDENT - SkDebugf("%s edge=%d (%g) next=%d (%g) prev=%d wind=%d nextWind=%d\n", - __FUNCTION__, ID(), fBelow.fY, next->ID(), next->fBelow.fY, - prev, wind, wind + next->fWorkEdge.winding()); -#endif - 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; - } - ActiveEdge thisWork = *this; - ActiveEdge edgeWork = *edge; - while ((thisWork.advanceT() || thisWork.advance()) - && (edgeWork.advanceT() || edgeWork.advance())) { - thisWork.calcLeft(); - edgeWork.calcLeft(); - if (thisWork < edgeWork) { - return false; - } - if (edgeWork < thisWork) { - return true; - } - } - return false; - } - - bool swapUnordered(const ActiveEdge* edge, SkScalar /* bottom */) const { - SkASSERT(fVerb != SkPath::kLine_Verb - || edge->fVerb != SkPath::kLine_Verb); - if (fDone || edge->fDone) { - return false; - } - ActiveEdge thisWork, edgeWork; - extractAboveBelow(thisWork); - edge->extractAboveBelow(edgeWork); - return edgeWork < thisWork; - } - - bool tooCloseToCall(const ActiveEdge* edge) const { - int ulps; - double t1, t2, b1, b2; - // This logic must be kept in sync with operator < - if (edge->fAbove.fY < fAbove.fY) { - t1 = (edge->fTangent.fY - edge->fAbove.fY) * (fAbove.fX - edge->fAbove.fX); - t2 = (fAbove.fY - edge->fAbove.fY) * (edge->fTangent.fX - edge->fAbove.fX); - } else if (edge->fAbove.fY > fAbove.fY) { - t1 = (fTangent.fY - fAbove.fY) * (fAbove.fX - edge->fAbove.fX); - t2 = (fAbove.fY - edge->fAbove.fY) * (fTangent.fX - fAbove.fX); - } else { - t1 = fAbove.fX; - t2 = edge->fAbove.fX; - } - if (edge->fTangent.fY > fTangent.fY) { - b1 = (edge->fTangent.fY - edge->fAbove.fY) * (fTangent.fX - edge->fTangent.fX); - b2 = (fTangent.fY - edge->fTangent.fY) * (edge->fTangent.fX - edge->fAbove.fX); - } else if (edge->fTangent.fY < fTangent.fY) { - b1 = (fTangent.fY - fAbove.fY) * (fTangent.fX - edge->fTangent.fX); - b2 = (fTangent.fY - edge->fTangent.fY) * (fTangent.fX - fAbove.fX); - } else { - b1 = fTangent.fX; - b2 = edge->fTangent.fX; - } - if (fabs(t1 - t2) > fabs(b1 - b2)) { - ulps = UlpsDiff((float) t1, (float) t2); - } else { - ulps = UlpsDiff((float) b1, (float) b2); - } -#if DEBUG_ADJUST_COINCIDENT - SkDebugf("%s this=%d edge=%d ulps=%d\n", __FUNCTION__, ID(), edge->ID(), - ulps); -#endif - if (ulps < 0 || ulps > 32) { - return false; - } - if (fVerb == SkPath::kLine_Verb && edge->fVerb == SkPath::kLine_Verb) { - return true; - } - if (fVerb != SkPath::kLine_Verb && edge->fVerb != SkPath::kLine_Verb) { - return false; - } - - double ts[2]; - bool isLine = true; - bool curveQuad = true; - if (fVerb == SkPath::kCubic_Verb) { - ts[0] = (fTAbove * 2 + fTBelow) / 3; - ts[1] = (fTAbove + fTBelow * 2) / 3; - curveQuad = isLine = false; - } else if (edge->fVerb == SkPath::kCubic_Verb) { - ts[0] = (edge->fTAbove * 2 + edge->fTBelow) / 3; - ts[1] = (edge->fTAbove + edge->fTBelow * 2) / 3; - curveQuad = false; - } else if (fVerb == SkPath::kQuad_Verb) { - ts[0] = fTAbove; - ts[1] = (fTAbove + fTBelow) / 2; - isLine = false; - } else { - SkASSERT(edge->fVerb == SkPath::kQuad_Verb); - ts[0] = edge->fTAbove; - ts[1] = (edge->fTAbove + edge->fTBelow) / 2; - } - const SkPoint* curvePts = isLine ? edge->lastPoints() : lastPoints(); - const ActiveEdge* lineEdge = isLine ? this : edge; - SkPoint curveSample[2]; - for (int index = 0; index < 2; ++index) { - if (curveQuad) { - QuadXYAtT(curvePts, ts[index], &curveSample[index]); - } else { - CubicXYAtT(curvePts, ts[index], &curveSample[index]); - } - } - return IsCoincident(curveSample, lineEdge->fAbove, lineEdge->fBelow); - } - - double nextT() const { - SkASSERT(fTIndex <= fTs->count() - fExplicitTs); - return t(fTIndex + 1); - } - - double t() const { - return t(fTIndex); - } - - double t(int tIndex) const { - if (fExplicitTs) { - SkASSERT(tIndex < fTs->count()); - return (*fTs)[tIndex]; - } - if (tIndex == 0) { - return 0; - } - if (tIndex > fTs->count()) { - return 1; - } - return (*fTs)[tIndex - 1]; - } - - // FIXME: debugging only - int ID() const { - return fWorkEdge.fEdge->fID; - } - -private: - // utility used only by swapUnordered - void extractAboveBelow(ActiveEdge& extracted) const { - SkPoint curve[4]; - switch (fVerb) { - case SkPath::kLine_Verb: - extracted.fAbove = fAbove; - extracted.fTangent = fTangent; - return; - case SkPath::kQuad_Verb: - QuadSubDivide(lastPoints(), fTAbove, fTBelow, curve); - break; - case SkPath::kCubic_Verb: - CubicSubDivide(lastPoints(), fTAbove, fTBelow, curve); - break; - default: - SkASSERT(0); - } - extracted.fAbove = curve[0]; - extracted.fTangent = curve[1]; - } - -public: - WorkEdge fWorkEdge; - const SkTDArray<double>* fTs; - SkPoint fAbove; - SkPoint fTangent; - SkPoint fBelow; - double fTAbove; // OPTIMIZATION: only required if edge has quads or cubics - double fTBelow; - SkScalar fYBottom; - int fCoincident; - int fTIndex; - SkPath::Verb fVerb; - bool fSkip; // OPTIMIZATION: use bitfields? - bool fCloseCall; - bool fDone; - bool fFixBelow; - bool fExplicitTs; -}; - -static void addToActive(SkTDArray<ActiveEdge>& activeEdges, const InEdge* edge) { - size_t count = activeEdges.count(); - for (size_t index = 0; index < count; ++index) { - if (edge == activeEdges[index].fWorkEdge.fEdge) { - return; - } - } - ActiveEdge* active = activeEdges.append(); - active->init(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. -// 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, - 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 { - 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 - 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)); - } - SkDebugf(")\n"); - } - 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 - && horzEdge->fLeft <= test->fBounds.fRight); - } while (wt.advance()); - } -} - -#if DEBUG_ADD_INTERSECTING_TS -static void debugShowLineIntersection(int pts, const WorkEdge& wt, - const WorkEdge& wn, const double wtTs[2], const double wnTs[2]) { - if (!pts) { - return; - } - 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)\n", - __FUNCTION__, - wtTs[0], wt.fPts[0].fX, wt.fPts[0].fY, - wt.fPts[1].fX, wt.fPts[1].fY, wtOutPt.fX, wtOutPt.fY); - if (pts == 2) { - SkDebugf("%s wtTs[1]=%g\n", __FUNCTION__, wtTs[1]); - } - SkDebugf("%s wnTs[0]=%g (%g,%g, %g,%g) (%g,%g)\n", - __FUNCTION__, - wnTs[0], wn.fPts[0].fX, wn.fPts[0].fY, - wn.fPts[1].fX, wn.fPts[1].fY, wnOutPt.fX, wnOutPt.fY); - if (pts == 2) { - SkDebugf("%s wnTs[1]=%g\n", __FUNCTION__, wnTs[1]); - } -} -#else -static void debugShowLineIntersection(int , const WorkEdge& , - const WorkEdge& , const double [2], const double [2]) { -} -#endif - -static void addIntersectingTs(InEdge** currentPtr, InEdge** lastPtr) { - InEdge** testPtr = currentPtr - 1; - // FIXME: lastPtr should be past the point of interest, so - // test below should be lastPtr - 2 - // that breaks testSimplifyTriangle22, so further investigation is needed - while (++testPtr != lastPtr - 1) { - InEdge* test = *testPtr; - 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; - } - if (!Bounds::Intersects(test->fBounds, next->fBounds)) { - continue; - } - WorkEdge wt, wn; - wt.init(test); - wn.init(next); - do { - int pts; - Intersections ts; - bool swap = false; - switch (wt.verb()) { - case SkPath::kLine_Verb: - switch (wn.verb()) { - case SkPath::kLine_Verb: { - pts = LineIntersect(wt.fPts, wn.fPts, ts); - debugShowLineIntersection(pts, wt, wn, - ts.fT[0], ts.fT[1]); - break; - } - case SkPath::kQuad_Verb: { - swap = true; - pts = QuadLineIntersect(wn.fPts, wt.fPts, ts); - break; - } - case SkPath::kCubic_Verb: { - swap = true; - pts = CubicLineIntersect(wn.fPts, wt.fPts, ts); - break; - } - default: - SkASSERT(0); - } - break; - case SkPath::kQuad_Verb: - switch (wn.verb()) { - case SkPath::kLine_Verb: { - pts = QuadLineIntersect(wt.fPts, wn.fPts, ts); - break; - } - case SkPath::kQuad_Verb: { - pts = QuadIntersect(wt.fPts, wn.fPts, ts); - break; - } - case SkPath::kCubic_Verb: { - // FIXME: promote quad to cubic - pts = CubicIntersect(wt.fPts, wn.fPts, ts); - break; - } - default: - SkASSERT(0); - } - break; - case SkPath::kCubic_Verb: - switch (wn.verb()) { - case SkPath::kLine_Verb: { - pts = CubicLineIntersect(wt.fPts, wn.fPts, ts); - break; - } - case SkPath::kQuad_Verb: { - // FIXME: promote quad to cubic - pts = CubicIntersect(wt.fPts, wn.fPts, ts); - break; - } - case SkPath::kCubic_Verb: { - pts = CubicIntersect(wt.fPts, wn.fPts, ts); - break; - } - default: - SkASSERT(0); - } - break; - default: - SkASSERT(0); - } - test->add(ts.fT[swap], pts, wt.verbIndex()); - next->add(ts.fT[!swap], pts, wn.verbIndex()); - } while (wt.bottom() <= wn.bottom() ? wt.advance() : wn.advance()); - } while (nextPtr != lastPtr); - } -} - -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; - } - 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) { - ++currentPtr; - } - } - 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 SkScalar computeInterceptBottom(SkTDArray<ActiveEdge>& activeEdges, - SkScalar y, SkScalar bottom) { - ActiveEdge* activePtr = activeEdges.begin() - 1; - ActiveEdge* lastActive = activeEdges.end(); - while (++activePtr != lastActive) { - const InEdge* test = activePtr->fWorkEdge.fEdge; - if (!test->fContainsIntercepts) { - continue; - } - WorkEdge wt; - wt.init(test); - do { - const Intercepts& intercepts = test->fIntercepts[wt.verbIndex()]; - if (intercepts.fTopIntercepts > 1) { - SkScalar yTop = wt.fPts[0].fY; - if (yTop > y && bottom > yTop) { - bottom = yTop; - } - } - if (intercepts.fBottomIntercepts > 1) { - SkScalar yBottom = wt.fPts[wt.verb()].fY; - if (yBottom > y && bottom > yBottom) { - bottom = yBottom; - } - } - const SkTDArray<double>& fTs = intercepts.fTs; - size_t count = fTs.count(); - for (size_t index = 0; index < count; ++index) { - SkScalar yIntercept; - switch (wt.verb()) { - case SkPath::kLine_Verb: { - yIntercept = LineYAtT(wt.fPts, fTs[index]); - break; - } - case SkPath::kQuad_Verb: { - yIntercept = QuadYAtT(wt.fPts, fTs[index]); - break; - } - case SkPath::kCubic_Verb: { - yIntercept = CubicYAtT(wt.fPts, fTs[index]); - break; - } - default: - SkASSERT(0); // should never get here - } - if (yIntercept > y && bottom > yIntercept) { - bottom = yIntercept; - } - } - } while (wt.advance()); - } -#if DEBUG_BOTTOM - SkDebugf("%s bottom=%1.9g\n", __FUNCTION__, bottom); -#endif - return bottom; -} - -static SkScalar findBottom(InEdge** currentPtr, - InEdge** edgeListEnd, SkTDArray<ActiveEdge>* activeEdges, SkScalar y, - bool /*asFill*/, InEdge**& testPtr) { - InEdge* current = *currentPtr; - SkScalar bottom = current->fBounds.fBottom; - - // find the list of edges that cross y - InEdge* test = *testPtr; - while (testPtr != edgeListEnd) { - SkScalar testTop = test->fBounds.fTop; - if (bottom <= testTop) { - break; - } - SkScalar testBottom = test->fBounds.fBottom; - // OPTIMIZATION: Shortening the bottom is only interesting when filling - // and when the edge is to the left of a longer edge. If it's a framing - // edge, or part of the right, it won't effect the longer edges. - if (testTop > y) { - bottom = testTop; - break; - } - if (y < testBottom) { - if (bottom > testBottom) { - bottom = testBottom; - } - if (activeEdges) { - addToActive(*activeEdges, test); - } - } - test = *++testPtr; - } -#if DEBUG_BOTTOM - SkDebugf("%s %d bottom=%1.9g\n", __FUNCTION__, activeEdges ? 2 : 1, bottom); -#endif - return bottom; -} - -static void makeEdgeList(SkTArray<InEdge>& edges, InEdge& edgeSentinel, - SkTDArray<InEdge*>& edgeList) { - size_t edgeCount = edges.count(); - if (edgeCount == 0) { - return; - } - int id = 0; - for (size_t index = 0; index < edgeCount; ++index) { - InEdge& edge = edges[index]; - if (!edge.fWinding) { - continue; - } - edge.fID = ++id; - *edgeList.append() = &edge; - } - *edgeList.append() = &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) { -#if DEBUG_ADJUST_COINCIDENT - SkDebugf("%s edge=%d 1 set skip=false\n", __FUNCTION__, activePtr->ID()); -#endif - activePtr->fSkip = false; - } else { -#if DEBUG_ADJUST_COINCIDENT - SkDebugf("%s edge=%d 2 set skip=false\n", __FUNCTION__, firstCoincident->ID()); -#endif - firstCoincident->fSkip = false; - } -} - -static void sortHorizontal(SkTDArray<ActiveEdge>& activeEdges, - SkTDArray<ActiveEdge*>& edgeList, SkScalar y) { - size_t edgeCount = activeEdges.count(); - if (edgeCount == 0) { - return; - } -#if DEBUG_SORT_HORIZONTAL - const int tab = 3; // FIXME: debugging only - SkDebugf("%s y=%1.9g\n", __FUNCTION__, y); -#endif - size_t index; - for (index = 0; index < edgeCount; ++index) { - ActiveEdge& activeEdge = activeEdges[index]; - 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. -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, * nextPtr = edgeList[0]; - size_t index; - bool foundCoincident = false; - size_t firstIndex = 0; - for (index = 1; index < edgeCount; ++index) { - activePtr = nextPtr; - nextPtr = edgeList[index]; - if (firstIndex != index - 1 && activePtr->fVerb > SkPath::kLine_Verb - && nextPtr->fVerb == SkPath::kLine_Verb - && activePtr->isUnordered(nextPtr)) { - // swap the line with the curve - // back up to the previous edge and retest - SkTSwap<ActiveEdge*>(edgeList[index - 1], edgeList[index]); - SkASSERT(index > 1); - index -= 2; - nextPtr = edgeList[index]; - continue; - } - bool closeCall = false; - activePtr->fCoincident = firstIndex; - if (activePtr->isCoincidentWith(nextPtr) - || (closeCall = activePtr->tooCloseToCall(nextPtr))) { - activePtr->fSkip = nextPtr->fSkip = foundCoincident = true; - activePtr->fCloseCall = nextPtr->fCloseCall = closeCall; - } else if (activePtr->isUnordered(nextPtr)) { - foundCoincident = true; - } else { - firstIndex = index; - } - } - nextPtr->fCoincident = firstIndex; - if (!foundCoincident) { - return bottom; - } - int winding = 0; - nextPtr = edgeList[0]; - for (index = 1; index < edgeCount; ++index) { - int priorWinding = winding; - winding += activePtr->fWorkEdge.winding(); - activePtr = nextPtr; - nextPtr = edgeList[index]; - SkASSERT(activePtr == edgeList[index - 1]); - SkASSERT(nextPtr == edgeList[index]); - if (activePtr->fCoincident != nextPtr->fCoincident) { - continue; - } - // 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. - while ((!activePtr->fSkip || !nextPtr->fSkip) - && activePtr->fCoincident == nextPtr->fCoincident) { - if (activePtr->swapUnordered(nextPtr, bottom)) { - winding -= activePtr->fWorkEdge.winding(); - SkASSERT(activePtr == edgeList[index - 1]); - SkASSERT(nextPtr == edgeList[index]); - SkTSwap<ActiveEdge*>(edgeList[index - 1], edgeList[index]); - if (--index == 0) { - winding += activePtr->fWorkEdge.winding(); - break; - } - // back up one - activePtr = edgeList[index - 1]; - continue; - } - SkASSERT(activePtr == edgeList[index - 1]); - SkASSERT(nextPtr == edgeList[index]); - break; - } - if (activePtr->fSkip && nextPtr->fSkip) { - if (activePtr->fCloseCall ? activePtr->swapClose(nextPtr, - priorWinding, winding, windingMask) - : activePtr->swapCoincident(nextPtr, bottom)) { - winding -= activePtr->fWorkEdge.winding(); - SkASSERT(activePtr == edgeList[index - 1]); - SkASSERT(nextPtr == edgeList[index]); - SkTSwap<ActiveEdge*>(edgeList[index - 1], edgeList[index]); - SkTSwap<ActiveEdge*>(activePtr, nextPtr); - winding += activePtr->fWorkEdge.winding(); - SkASSERT(activePtr == edgeList[index - 1]); - SkASSERT(nextPtr == edgeList[index]); - } - } - } - int firstCoincidentWinding = 0; - ActiveEdge* firstCoincident = NULL; - winding = 0; - activePtr = edgeList[0]; - for (index = 1; index < edgeCount; ++index) { - int priorWinding = winding; - winding += activePtr->fWorkEdge.winding(); - nextPtr = edgeList[index]; - if (activePtr->fSkip && nextPtr->fSkip - && 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); - #if DEBUG_ADJUST_COINCIDENT - SkDebugf("%s 1 edge=%d y=%1.9g (was fYBottom=%1.9g)\n", - __FUNCTION__, activePtr->ID(), y, activePtr->fYBottom); - #endif - activePtr->fYBottom = y; - } - if (outBuilder.trimLine(y, nextPtr->ID())) { - nextPtr->addTatYAbove(y); - #if DEBUG_ADJUST_COINCIDENT - SkDebugf("%s 2 edge=%d y=%1.9g (was fYBottom=%1.9g)\n", - __FUNCTION__, nextPtr->ID(), y, nextPtr->fYBottom); - #endif - 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) { - #if DEBUG_ADJUST_COINCIDENT - SkDebugf("%s 3 edge=%d bottom=%1.9g (was bottom=%1.9g)\n", - __FUNCTION__, activePtr->ID(), testY, bottom); - #endif - bottom = testY; - } - testY = nextPtr->fBelow.fY; - activePtr->addTatYBelow(testY); - if (bottom > testY && testY > y) { - #if DEBUG_ADJUST_COINCIDENT - SkDebugf("%s 4 edge=%d bottom=%1.9g (was bottom=%1.9g)\n", - __FUNCTION__, nextPtr->ID(), testY, bottom); - #endif - bottom = testY; - } - } - } else if (firstCoincident) { - skipCoincidence(firstCoincidentWinding, winding, windingMask, - activePtr, firstCoincident); - firstCoincident = NULL; - } - activePtr = nextPtr; - } - if (firstCoincident) { - winding += activePtr->fWorkEdge.winding(); - 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 -static void stitchEdge(SkTDArray<ActiveEdge*>& edgeList, SkScalar -#if DEBUG_STITCH_EDGE -y -#endif -, - SkScalar bottom, int windingMask, bool fill, OutEdgeBuilder& outBuilder) { - int winding = 0; - ActiveEdge** activeHandle = edgeList.begin() - 1; - ActiveEdge** lastActive = edgeList.end(); -#if DEBUG_STITCH_EDGE - const int tab = 7; // FIXME: debugging only - SkDebugf("%s y=%1.9g bottom=%1.9g\n", __FUNCTION__, y, bottom); -#endif - while (++activeHandle != lastActive) { - ActiveEdge* activePtr = *activeHandle; - const WorkEdge& wt = activePtr->fWorkEdge; - int lastWinding = winding; - winding += wt.winding(); -#if DEBUG_STITCH_EDGE - SkDebugf("%*s edge=%d lastWinding=%d winding=%d skip=%d close=%d" - " above=%1.9g below=%1.9g\n", - tab-4, "", activePtr->ID(), lastWinding, - winding, activePtr->fSkip, activePtr->fCloseCall, - activePtr->fTAbove, activePtr->fTBelow); -#endif - if (activePtr->done(bottom)) { -#if DEBUG_STITCH_EDGE - SkDebugf("%*s fDone=%d || fYBottom=%1.9g >= bottom\n", tab, "", - activePtr->fDone, activePtr->fYBottom); -#endif - continue; - } - int opener = (lastWinding & windingMask) == 0; - bool closer = (winding & windingMask) == 0; - SkASSERT(!opener | !closer); - bool inWinding = opener | closer; - SkPoint clippedPts[4]; - const SkPoint* clipped = NULL; - bool moreToDo, aboveBottom; - do { - double currentT = activePtr->t(); - const SkPoint* points = wt.fPts; - double nextT; - SkPath::Verb verb = activePtr->fVerb; - do { - nextT = activePtr->nextT(); - // FIXME: obtuse: want efficient way to say - // !currentT && currentT != 1 || !nextT && nextT != 1 - if (currentT * nextT != 0 || currentT + nextT != 1) { - // OPTIMIZATION: if !inWinding, we only need - // clipped[1].fY - switch (verb) { - case SkPath::kLine_Verb: - LineSubDivide(points, currentT, nextT, clippedPts); - break; - case SkPath::kQuad_Verb: - QuadSubDivide(points, currentT, nextT, clippedPts); - break; - case SkPath::kCubic_Verb: - CubicSubDivide(points, currentT, nextT, clippedPts); - break; - default: - SkASSERT(0); - break; - } - clipped = clippedPts; - } else { - clipped = points; - } - if (inWinding && !activePtr->fSkip && (fill ? clipped[0].fY - != clipped[verb].fY : clipped[0] != clipped[verb])) { -#if DEBUG_STITCH_EDGE - SkDebugf("%*s add%s %1.9g,%1.9g %1.9g,%1.9g edge=%d" - " v=%d t=(%1.9g,%1.9g)\n", tab, "", - kUVerbStr[verb], clipped[0].fX, clipped[0].fY, - clipped[verb].fX, clipped[verb].fY, - activePtr->ID(), - activePtr->fWorkEdge.fVerb - - activePtr->fWorkEdge.fEdge->fVerbs.begin(), - currentT, nextT); -#endif - outBuilder.addCurve(clipped, (SkPath::Verb) verb, - activePtr->fWorkEdge.fEdge->fID, - activePtr->fCloseCall); - } else { -#if DEBUG_STITCH_EDGE - SkDebugf("%*s skip%s %1.9g,%1.9g %1.9g,%1.9g" - " edge=%d v=%d t=(%1.9g,%1.9g)\n", tab, "", - kUVerbStr[verb], clipped[0].fX, clipped[0].fY, - clipped[verb].fX, clipped[verb].fY, - activePtr->ID(), - activePtr->fWorkEdge.fVerb - - activePtr->fWorkEdge.fEdge->fVerbs.begin(), - currentT, nextT); -#endif - } - // by advancing fAbove/fBelow, the next call to sortHorizontal - // will use these values if they're still valid instead of - // recomputing - if (clipped[verb].fY > activePtr->fBelow.fY - && bottom >= activePtr->fBelow.fY - && verb == SkPath::kLine_Verb) { - activePtr->fAbove = activePtr->fBelow; - activePtr->fBelow = activePtr->fTangent = clipped[verb]; - activePtr->fTAbove = activePtr->fTBelow < 1 - ? activePtr->fTBelow : 0; - activePtr->fTBelow = nextT; - } - currentT = nextT; - moreToDo = activePtr->advanceT(); - 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; - if (clipped[0].fY != clipped[verb].fY) { - activePtr->fSkip = false; - activePtr->fCloseCall = false; - aboveBottom &= !activePtr->fCloseCall; - } -#if DEBUG_STITCH_EDGE - else { - if (activePtr->fSkip || activePtr->fCloseCall) { - SkDebugf("%s skip or close == %1.9g\n", __FUNCTION__, - clippedPts[0].fY); - } - } -#endif - } while (moreToDo & aboveBottom); - } while ((moreToDo || activePtr->advance()) & aboveBottom); - } -} - -#if DEBUG_DUMP -static void dumpEdgeList(const SkTDArray<InEdge*>& edgeList, - const InEdge& edgeSentinel) { - InEdge** debugPtr = edgeList.begin(); - do { - (*debugPtr++)->dump(); - } while (*debugPtr != &edgeSentinel); -} -#else -static void dumpEdgeList(const SkTDArray<InEdge*>& , - const InEdge& ) { -} -#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; - simple.reset(); - simple.setFillType(SkPath::kEvenOdd_FillType); - // turn path into list of edges increasing in y - // if an edge is a quad or a cubic with a y extrema, note it, but leave it - // unbroken. Once we have a list, sort it, then walk the list (walk edges - // 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; - SkTDArray<HorizontalEdge> horizontalEdges; - InEdgeBuilder builder(path, asFill, edges, horizontalEdges); - SkTDArray<InEdge*> edgeList; - InEdge edgeSentinel; - edgeSentinel.reset(); - 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 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. - - // try an alternate approach which does not split curves or stitch edges - // (may still need adjustCoincident, though) - // the idea is to output non-intersecting contours, then figure out their - // respective winding contribution - // each contour will need to know whether it is CW or CCW, and then whether - // a ray from that contour hits any a contour that contains it. The ray can - // move to the left and then arbitrarily move up or down (as long as it never - // moves to the right) to find a reference sibling contour or containing - // contour. If the contour is part of an intersection, the companion contour - // that is part of the intersection can determine the containership. - if (builder.containsCurves()) { - currentPtr = edgeList.begin(); - SkTArray<InEdge> splits; - do { - (*currentPtr)->splitInflectionPts(splits); - } while (*++currentPtr != &edgeSentinel); - if (splits.count()) { - for (int index = 0; index < splits.count(); ++index) { - edges.push_back(splits[index]); - } - edgeList.reset(); - makeEdgeList(edges, edgeSentinel, edgeList); - } - } - dumpEdgeList(edgeList, edgeSentinel); - // walk the sorted edges from top to bottom, computing accumulated winding - SkTDArray<ActiveEdge> activeEdges; - OutEdgeBuilder outBuilder(asFill); - 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); - if (lastPtr > currentPtr) { - bottom = computeInterceptBottom(activeEdges, y, bottom); - SkTDArray<ActiveEdge*> activeEdgeList; - sortHorizontal(activeEdges, activeEdgeList, y); - bottom = adjustCoincident(activeEdgeList, windingMask, y, bottom, - outBuilder); - stitchEdge(activeEdgeList, y, bottom, windingMask, asFill, outBuilder); - } - y = bottom; - // 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(); - outBuilder.assemble(simple); -} |