diff options
author | caryclark@google.com <caryclark@google.com@2bbb7eff-a529-9590-31e7-b0007b416f81> | 2012-04-26 21:01:06 +0000 |
---|---|---|
committer | caryclark@google.com <caryclark@google.com@2bbb7eff-a529-9590-31e7-b0007b416f81> | 2012-04-26 21:01:06 +0000 |
commit | fa0588ff672564af1c235a63589573829035a60b (patch) | |
tree | e62a5152abd641fa2435951327ecfe3697ce3883 /experimental/Intersection/Simplify.cpp | |
parent | 8e124a2454543e17e69d5f383c1a63c3d034001a (diff) |
work in progress
in the middle of switching to sortless version
git-svn-id: http://skia.googlecode.com/svn/trunk@3768 2bbb7eff-a529-9590-31e7-b0007b416f81
Diffstat (limited to 'experimental/Intersection/Simplify.cpp')
-rw-r--r-- | experimental/Intersection/Simplify.cpp | 1213 |
1 files changed, 1213 insertions, 0 deletions
diff --git a/experimental/Intersection/Simplify.cpp b/experimental/Intersection/Simplify.cpp new file mode 100644 index 0000000000..5d7209a09d --- /dev/null +++ b/experimental/Intersection/Simplify.cpp @@ -0,0 +1,1213 @@ +/* + * 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 "CurveIntersection.h" +#include "Intersections.h" +#include "LineIntersection.h" +#include "SkPath.h" +#include "SkRect.h" +#include "SkTArray.h" +#include "SkTDArray.h" +#include "ShapeOps.h" +#include "TSearch.h" + +#undef SkASSERT +#define SkASSERT(cond) while (!(cond)) { sk_throw(); } + +// FIXME: remove once debugging is complete +#if 0 // set to 1 for no debugging whatsoever + +//const bool gxRunTestsInOneThread = false; + +#define DEBUG_ADD_INTERSECTING_TS 0 +#define DEBUG_BRIDGE 0 +#define DEBUG_DUMP 0 + +#else + +//const bool gRunTestsInOneThread = true; + +#define DEBUG_ADD_INTERSECTING_TS 1 +#define DEBUG_BRIDGE 1 +#define DEBUG_DUMP 1 + +#endif + +#if DEBUG_DUMP +static const char* kLVerbStr[] = {"", "line", "quad", "cubic"}; +static const char* kUVerbStr[] = {"", "Line", "Quad", "Cubic"}; +static int gContourID; +static int gSegmentID; +#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.fT[0], intersections.fT[1]); +} + +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.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}}; + intersect(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 HLineIntersect(const SkPoint a[2], SkScalar left, SkScalar right, + SkScalar y, bool flipped, Intersections& intersections) { + const _Line aLine = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}}; + return horizontalIntersect(aLine, left, right, y, flipped, intersections); +} + +static int VLineIntersect(const SkPoint a[2], SkScalar left, SkScalar right, + SkScalar y, bool flipped, Intersections& intersections) { + const _Line aLine = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}}; + return verticalIntersect(aLine, left, right, y, flipped, intersections); +} + +static int HQuadIntersect(const SkPoint a[3], SkScalar left, SkScalar right, + SkScalar y, bool flipped, Intersections& intersections) { + 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, flipped, intersections); +} + +static int VQuadIntersect(const SkPoint a[3], SkScalar left, SkScalar right, + SkScalar y, bool flipped, Intersections& intersections) { + const Quadratic aQuad = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY}}; + return verticalIntersect(aQuad, left, right, y, flipped, intersections); +} + +static int HCubicIntersect(const SkPoint a[4], SkScalar left, SkScalar right, + SkScalar y, bool flipped, 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}}; + return horizontalIntersect(aCubic, left, right, y, flipped, intersections); +} + +static int VCubicIntersect(const SkPoint a[4], SkScalar left, SkScalar right, + SkScalar y, bool flipped, 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}}; + return verticalIntersect(aCubic, left, right, y, flipped, intersections); +} + +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 void (* const SegmentXYAtT[])(const SkPoint [], double , SkPoint* ) = { + NULL, + LineXYAtT, + QuadXYAtT, + CubicXYAtT +}; + +static SkScalar LineXAtT(const SkPoint a[2], double t) { + const _Line aLine = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}}; + double x; + xy_at_t(aLine, t, x, *(double*) 0); + return SkDoubleToScalar(x); +} + +static SkScalar QuadXAtT(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 x; + xy_at_t(quad, t, x, *(double*) 0); + return SkDoubleToScalar(x); +} + +static SkScalar CubicXAtT(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 x; + xy_at_t(cubic, t, x, *(double*) 0); + return SkDoubleToScalar(x); +} + +static SkScalar (* const SegmentXAtT[])(const SkPoint [], double ) = { + NULL, + LineXAtT, + QuadXAtT, + CubicXAtT +}; + +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 SkScalar (* const SegmentYAtT[])(const SkPoint [], double ) = { + NULL, + LineYAtT, + QuadYAtT, + CubicYAtT +}; + +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(const SkPoint a[4], + SkTDArray<SkPoint>& reducePts) { + 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); + for (int index = 0; index < order; ++index) { + SkPoint* pt = reducePts.append(); + pt->fX = SkDoubleToScalar(dst[index].x); + pt->fY = SkDoubleToScalar(dst[index].y); + } + return (SkPath::Verb) (order - 1); +} + +static SkPath::Verb CubicReduceOrder(const SkPoint a[4], + SkTDArray<SkPoint>& reducePts) { + 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); + for (int index = 0; index < order; ++index) { + SkPoint* pt = reducePts.append(); + pt->fX = SkDoubleToScalar(dst[index].x); + pt->fY = SkDoubleToScalar(dst[index].y); + } + return (SkPath::Verb) (order - 1); +} + +static SkScalar LineLeftMost(const SkPoint a[2], double startT, double endT) { + const _Line aLine = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}}; + double x[2]; + xy_at_t(aLine, startT, x[0], *(double*) 0); + xy_at_t(aLine, endT, x[0], *(double*) 0); + return startT < endT ? startT : endT; +} + +static SkScalar QuadLeftMost(const SkPoint a[3], double startT, double endT) { + const Quadratic aQuad = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, + {a[2].fX, a[2].fY}}; + return leftMostT(aQuad, startT, endT); +} + +static SkScalar CubicLeftMost(const SkPoint a[4], double startT, double endT) { + 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 leftMostT(aCubic, startT, endT); +} + +static SkScalar (* const SegmentLeftMost[])(const SkPoint [], double , double) = { + NULL, + LineLeftMost, + QuadLeftMost, + CubicLeftMost +}; + +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); +} + +// 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); + } + + void setCubicBounds(const SkPoint a[4]) { + _Rect dRect; + 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}}; + dRect.setBounds(cubic); + set(dRect.left, dRect.top, dRect.right, dRect.bottom); + } + + void setQuadBounds(const SkPoint a[3]) { + const Quadratic quad = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, + {a[2].fX, a[2].fY}}; + _Rect dRect; + dRect.setBounds(quad); + set(dRect.left, dRect.top, dRect.right, dRect.bottom); + } +}; + +class Segment; + +struct TEntry { + double fT; + const Segment* fOther; + double fOtherT; + bool fCoincident; +}; + +class Segment { +public: + Segment() { +#if DEBUG_DUMP + fID = ++gSegmentID; +#endif + } + + int addT(double newT, const Segment& other) { + // FIXME: in the pathological case where there is a ton of intercepts, + // binary search? + int insertedAt = -1; + TEntry* entry; + size_t tCount = fTs.count(); + double delta; + for (size_t idx2 = 0; idx2 < tCount; ++idx2) { + if (newT <= fTs[idx2].fT) { + insertedAt = idx2; + entry = fTs.insert(idx2); + goto finish; + } + } + insertedAt = tCount; + entry = fTs.append(); +finish: + entry->fT = newT; + entry->fOther = &other; + return insertedAt; + } + + bool addCubic(const SkPoint pts[4]) { + fPts = pts; + fVerb = SkPath::kCubic_Verb; + fBounds.setCubicBounds(pts); + } + + bool addLine(const SkPoint pts[2]) { + fPts = pts; + fVerb = SkPath::kLine_Verb; + fBounds.set(pts, 2); + } + + // add 2 to edge or out of range values to get T extremes + void addOtherT(int index, double other, bool coincident) { + fTs[index].fOtherT = other; + fTs[index].fCoincident = coincident; + } + + bool addQuad(const SkPoint pts[3]) { + fPts = pts; + fVerb = SkPath::kQuad_Verb; + fBounds.setQuadBounds(pts); + } + + const Bounds& bounds() const { + return fBounds; + } + + int findByT(double t, const Segment* match) const { + // OPTIMIZATION: bsearch if count is honkin huge + int count = fTs.count(); + for (int index = 0; index < count; ++index) { + const TEntry& entry = fTs[index]; + if (t == entry.fT && match == entry.fOther) { + return index; + } + } + SkASSERT(0); // should never get here + return -1; + } + + int findLefty(int tIndex, const SkPoint& base) const { + int bestTIndex; + SkPoint test; + SkScalar bestX = DBL_MAX; + int testTIndex = tIndex; + while (--testTIndex >= 0) { + xyAtT(testTIndex, &test); + if (test != base) { + continue; + } + bestX = test.fX; + bestTIndex = testTIndex; + break; + } + int count = fTs.count(); + testTIndex = tIndex; + while (++testTIndex < count) { + xyAtT(testTIndex, &test); + if (test == base) { + continue; + } + return bestX > test.fX ? testTIndex : bestTIndex; + } + return -1; + } + + const Segment* findTop(int& tIndex) const { + // iterate through T intersections and return topmost + // topmost tangent from y-min to first pt is closer to horizontal + int firstT = 0; + int lastT = 0; + SkScalar topY = fPts[0].fY; + int count = fTs.count(); + int index; + for (index = 1; index < count; ++index) { + const TEntry& entry = fTs[index]; + double t = entry.fT; + SkScalar yIntercept = (*SegmentYAtT[fVerb])(fPts, t); + if (topY > yIntercept) { + topY = yIntercept; + firstT = lastT = index; + } else if (topY == yIntercept) { + lastT = index; + } + } + // if a pair of segments go down, choose the higher endpoint + if (firstT == lastT && (firstT == 0 || firstT == count - 1)) { + tIndex = firstT; + return this; + } + // if the topmost T is not on end, or is three-way or more, find left + SkPoint leftBase; + xyAtT(firstT, &leftBase); + int tLeft = findLefty(firstT, leftBase); + SkASSERT(tLeft > 0); + const Segment* leftSegment = this; + SkScalar left = leftMost(firstT, tLeft); + for (index = firstT; index <= lastT; ++index) { + const Segment* other = fTs[index].fOther; + double otherT = fTs[index].fOtherT; + int otherTIndex = other->findByT(otherT, this); + // pick companionT closest (but not too close) on either side + int otherTLeft = other->findLefty(otherTIndex, leftBase); + if (otherTLeft < 0) { + continue; + } + SkScalar otherMost = other->leftMost(otherTIndex, otherTLeft); + if (otherMost < left) { + leftSegment = other; + } + } + return leftSegment; + } + + bool intersected() const { + return fTs.count() > 0; + } + + bool isHorizontal() const { + return fBounds.fTop == fBounds.fBottom; + } + + bool isVertical() const { + return fBounds.fLeft == fBounds.fRight; + } + + SkScalar leftMost(int start, int end) const { + return (*SegmentLeftMost[fVerb])(fPts, fTs[start].fT, fTs[end].fT); + } + + const SkPoint* pts() const { + return fPts; + } + + void reset() { + fPts = NULL; + fVerb = (SkPath::Verb) -1; + fBounds.set(SK_ScalarMax, SK_ScalarMax, SK_ScalarMax, SK_ScalarMax); + fTs.reset(); + } + + // OPTIMIZATION: remove this function if it's never called + double t(int tIndex) const { + return fTs[tIndex].fT; + } + + SkPath::Verb verb() const { + return fVerb; + } + + SkScalar xAtT(double t) const { + return (*SegmentXAtT[fVerb])(fPts, t); + } + + void xyAtT(double t, SkPoint* pt) const { + (*SegmentXYAtT[fVerb])(fPts, t, pt); + } + +#if DEBUG_DUMP + void dump() const { + const char className[] = "Segment"; + const int tab = 4; + for (int i = 0; i < fTs.count(); ++i) { + SkPoint out; + (*SegmentXYAtT[fVerb])(fPts, t(i), &out); + SkDebugf("%*s [%d] %s.fTs[%d]=%1.9g (%1.9g,%1.9g) other=%d" + " otherT=%1.9g coincident=%d\n", + tab + sizeof(className), className, fID, + kLVerbStr[fVerb], i, fTs[i].fT, out.fX, out.fY, + fTs[i].fOther->fID, fTs[i].fOtherT, fTs[i].fCoincident); + } + SkDebugf("%*s [%d] fBounds=(l:%1.9g, t:%1.9g r:%1.9g, b:%1.9g)\n", + tab + sizeof(className), className, fID, + fBounds.fLeft, fBounds.fTop, fBounds.fRight, fBounds.fBottom); + } +#endif + +private: + const SkPoint* fPts; + SkPath::Verb fVerb; + Bounds fBounds; + SkTDArray<TEntry> fTs; +#if DEBUG_DUMP + int fID; +#endif +}; + +class Contour { +public: + Contour() { + reset(); +#if DEBUG_DUMP + fID = ++gContourID; +#endif + } + + bool operator<(const Contour& rh) const { + return fBounds.fTop == rh.fBounds.fTop + ? fBounds.fLeft < rh.fBounds.fLeft + : fBounds.fTop < rh.fBounds.fTop; + } + + void addCubic(const SkPoint pts[4]) { + fSegments.push_back().addCubic(pts); + fContainsCurves = true; + } + void addLine(const SkPoint pts[2]) { + fSegments.push_back().addLine(pts); + } + + void addQuad(const SkPoint pts[3]) { + fSegments.push_back().addQuad(pts); + fContainsCurves = true; + } + + const Bounds& bounds() const { + return fBounds; + } + + void complete() { + setBounds(); + fContainsIntercepts = false; + } + + void containsIntercepts() { + fContainsIntercepts = true; + } + + void reset() { + fSegments.reset(); + fBounds.set(SK_ScalarMax, SK_ScalarMax, SK_ScalarMax, SK_ScalarMax); + fContainsCurves = fContainsIntercepts = false; + } + + Segment& topSegment() { + return fSegments[fTopSegment]; + } + +#if DEBUG_DUMP + void dump() { + int i; + const char className[] = "Contour"; + const int tab = 4; + SkDebugf("%s %p (contour=%d)\n", className, this, fID); + for (i = 0; i < fSegments.count(); ++i) { + SkDebugf("%*s.fSegments[%d]:\n", tab + sizeof(className), + className, i); + fSegments[i].dump(); + } + SkDebugf("%*s.fBounds=(l:%1.9g, t:%1.9g r:%1.9g, b:%1.9g)\n", + tab + sizeof(className), className, + fBounds.fLeft, fBounds.fTop, + fBounds.fRight, fBounds.fBottom); + SkDebugf("%*s.fTopSegment=%d\n", tab + sizeof(className), className, + fTopSegment); + SkDebugf("%*s.fContainsIntercepts=%d\n", tab + sizeof(className), + className, fContainsIntercepts); + SkDebugf("%*s.fContainsCurves=%d\n", tab + sizeof(className), + className, fContainsCurves); + } +#endif + +protected: + void setBounds() { + int count = fSegments.count(); + if (count == 0) { + SkDebugf("%s empty contour\n", __FUNCTION__); + SkASSERT(0); + // FIXME: delete empty contour? + return; + } + fTopSegment = 0; + fBounds = fSegments.front().bounds(); + SkScalar top = fBounds.fTop; + for (int index = 1; index < count; ++index) { + fBounds.growToInclude(fSegments[index].bounds()); + if (top > fBounds.fTop) { + fTopSegment = index; + top = fBounds.fTop; + } + } + } + +public: + SkTArray<Segment> fSegments; // not worth accessor functions? + +private: + Bounds fBounds; + int fTopSegment; + bool fContainsIntercepts; + bool fContainsCurves; +#if DEBUG_DUMP + int fID; +#endif +}; + +class EdgeBuilder { +public: + +EdgeBuilder(const SkPath& path, SkTArray<Contour>& contours) + : fPath(path) + , fCurrentContour(NULL) + , fContours(contours) +{ +#if DEBUG_DUMP + gContourID = 0; + gSegmentID = 0; +#endif + walk(); +} + +protected: + +void complete() { + if (fCurrentContour && fCurrentContour->fSegments.count()) { + fCurrentContour->complete(); + fCurrentContour = NULL; + } +} + +void startContour() { + if (!fCurrentContour) { + fCurrentContour = fContours.push_back_n(1); + } +} + +void walk() { + // FIXME:remove once we can access path pts directly + SkPath::RawIter iter(fPath); // FIXME: access path directly when allowed + SkPoint pts[4]; + SkPath::Verb verb; + do { + verb = iter.next(pts); + *fPathVerbs.append() = verb; + if (verb == SkPath::kMove_Verb) { + *fPathPts.append() = pts[0]; + } else if (verb >= SkPath::kLine_Verb && verb <= SkPath::kCubic_Verb) { + fPathPts.append(verb, &pts[1]); + } + } while (verb != SkPath::kDone_Verb); + // FIXME: end of section to remove once path pts are accessed directly + + SkPath::Verb reducedVerb; + uint8_t* verbPtr = fPathVerbs.begin(); + const SkPoint* pointsPtr = fPathPts.begin(); + while ((verb = (SkPath::Verb) *verbPtr++) != SkPath::kDone_Verb) { + switch (verb) { + case SkPath::kMove_Verb: + complete(); + startContour(); + pointsPtr += 1; + continue; + case SkPath::kLine_Verb: + // skip degenerate points + if (pointsPtr[-1].fX != pointsPtr[0].fX + || pointsPtr[-1].fY != pointsPtr[0].fY) { + fCurrentContour->addLine(&pointsPtr[-1]); + } + break; + case SkPath::kQuad_Verb: + reducedVerb = QuadReduceOrder(&pointsPtr[-1], fReducePts); + if (reducedVerb == 0) { + break; // skip degenerate points + } + if (reducedVerb == 1) { + fCurrentContour->addLine(fReducePts.end() - 2); + break; + } + fCurrentContour->addQuad(&pointsPtr[-1]); + break; + case SkPath::kCubic_Verb: + reducedVerb = CubicReduceOrder(&pointsPtr[-1], fReducePts); + if (reducedVerb == 0) { + break; // skip degenerate points + } + if (reducedVerb == 1) { + fCurrentContour->addLine(fReducePts.end() - 2); + break; + } + if (reducedVerb == 2) { + fCurrentContour->addQuad(fReducePts.end() - 3); + break; + } + fCurrentContour->addCubic(&pointsPtr[-1]); + break; + case SkPath::kClose_Verb: + SkASSERT(fCurrentContour); + complete(); + continue; + default: + SkDEBUGFAIL("bad verb"); + return; + } + pointsPtr += verb; + SkASSERT(fCurrentContour); + } + complete(); + if (fCurrentContour && !fCurrentContour->fSegments.count()) { + fContours.pop_back(); + } +} + +private: + const SkPath& fPath; + SkTDArray<SkPoint> fPathPts; // FIXME: point directly to path pts instead + SkTDArray<uint8_t> fPathVerbs; // FIXME: remove + Contour* fCurrentContour; + SkTArray<Contour>& fContours; + SkTDArray<SkPoint> fReducePts; // segments created on the fly +}; + +class Work { +public: + enum SegmentType { + kHorizontalLine_Segment = -1, + kVerticalLine_Segment = 0, + kLine_Segment = SkPath::kLine_Verb, + kQuad_Segment = SkPath::kQuad_Verb, + kCubic_Segment = SkPath::kCubic_Verb, + }; + + void addOtherT(int index, double other, bool coincident) { + fContour->fSegments[fIndex].addOtherT(index, other, coincident); + } + + // 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. + // On the edge or out of range values are negative; add 2 to get end + int addT(double newT, const Work& other) { + fContour->containsIntercepts(); + return fContour->fSegments[fIndex].addT(newT, + other.fContour->fSegments[other.fIndex]); + } + + bool advance() { + return ++fIndex < fLast; + } + + SkScalar bottom() const { + return bounds().fBottom; + } + + const Bounds& bounds() const { + return fContour->fSegments[fIndex].bounds(); + } + + const SkPoint* cubic() const { + return fCubic; + } + + void init(Contour* contour) { + fContour = contour; + fIndex = 0; + fLast = contour->fSegments.count(); + } + + SkScalar left() const { + return bounds().fLeft; + } + + void promoteToCubic() { + fCubic[0] = pts()[0]; + fCubic[2] = pts()[1]; + fCubic[3] = pts()[2]; + fCubic[1].fX = (fCubic[0].fX + fCubic[2].fX * 2) / 3; + fCubic[1].fY = (fCubic[0].fY + fCubic[2].fY * 2) / 3; + fCubic[2].fX = (fCubic[3].fX + fCubic[2].fX * 2) / 3; + fCubic[2].fY = (fCubic[3].fY + fCubic[2].fY * 2) / 3; + } + + const SkPoint* pts() const { + return fContour->fSegments[fIndex].pts(); + } + + SkScalar right() const { + return bounds().fRight; + } + + ptrdiff_t segmentIndex() const { + return fIndex; + } + + SegmentType segmentType() const { + const Segment& segment = fContour->fSegments[fIndex]; + SegmentType type = (SegmentType) segment.verb(); + if (type != kLine_Segment) { + return type; + } + if (segment.isHorizontal()) { + return kHorizontalLine_Segment; + } + if (segment.isVertical()) { + return kVerticalLine_Segment; + } + return kLine_Segment; + } + + bool startAfter(const Work& after) { + fIndex = after.fIndex; + return advance(); + } + + SkScalar top() const { + return bounds().fTop; + } + + SkPath::Verb verb() const { + return fContour->fSegments[fIndex].verb(); + } + + SkScalar x() const { + return bounds().fLeft; + } + + bool xFlipped() const { + return x() != pts()[0].fX; + } + + SkScalar y() const { + return bounds().fTop; + } + + bool yFlipped() const { + return y() != pts()[0].fX; + } + +protected: + Contour* fContour; + SkPoint fCubic[4]; + int fIndex; + int fLast; +}; + +static void debugShowLineIntersection(int pts, const Work& wt, + const Work& wn, const double wtTs[2], const double wnTs[2]) { +#if DEBUG_ADD_INTERSECTING_TS + if (!pts) { + return; + } + SkPoint wtOutPt, wnOutPt; + LineXYAtT(wt.pts(), wtTs[0], &wtOutPt); + LineXYAtT(wn.pts(), wnTs[0], &wnOutPt); + SkDebugf("%s wtTs[0]=%g (%g,%g, %g,%g) (%g,%g)\n", + __FUNCTION__, + wtTs[0], wt.pts()[0].fX, wt.pts()[0].fY, + wt.pts()[1].fX, wt.pts()[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.pts()[0].fX, wn.pts()[0].fY, + wn.pts()[1].fX, wn.pts()[1].fY, wnOutPt.fX, wnOutPt.fY); + if (pts == 2) { + SkDebugf("%s wnTs[1]=%g\n", __FUNCTION__, wnTs[1]); + } +#endif +} + +static bool addIntersectingTs(Contour* test, Contour* next) { + if (test != next) { + if (test->bounds().fBottom < next->bounds().fTop) { + return false; + } + if (!Bounds::Intersects(test->bounds(), next->bounds())) { + return true; + } + } + Work wt, wn; + wt.init(test); + wn.init(next); + do { + if (test == next && !wn.startAfter(wt)) { + continue; + } + do { + if (!Bounds::Intersects(wt.bounds(), wn.bounds())) { + continue; + } + int pts; + Intersections ts; + bool swap = false; + switch (wt.segmentType()) { + case Work::kHorizontalLine_Segment: + swap = true; + switch (wn.segmentType()) { + case Work::kHorizontalLine_Segment: + case Work::kVerticalLine_Segment: + case Work::kLine_Segment: { + pts = HLineIntersect(wn.pts(), wt.left(), + wt.right(), wt.y(), wt.xFlipped(), ts); + break; + } + case Work::kQuad_Segment: { + pts = HQuadIntersect(wn.pts(), wt.left(), + wt.right(), wt.y(), wt.xFlipped(), ts); + break; + } + case Work::kCubic_Segment: { + pts = HCubicIntersect(wn.pts(), wt.left(), + wt.right(), wt.y(), wt.xFlipped(), ts); + break; + } + default: + SkASSERT(0); + } + break; + case Work::kVerticalLine_Segment: + swap = true; + switch (wn.segmentType()) { + case Work::kHorizontalLine_Segment: + case Work::kVerticalLine_Segment: + case Work::kLine_Segment: { + pts = VLineIntersect(wn.pts(), wt.top(), + wt.bottom(), wt.x(), wt.yFlipped(), ts); + break; + } + case Work::kQuad_Segment: { + pts = VQuadIntersect(wn.pts(), wt.top(), + wt.bottom(), wt.x(), wt.yFlipped(), ts); + break; + } + case Work::kCubic_Segment: { + pts = VCubicIntersect(wn.pts(), wt.top(), + wt.bottom(), wt.x(), wt.yFlipped(), ts); + break; + } + default: + SkASSERT(0); + } + break; + case Work::kLine_Segment: + switch (wn.segmentType()) { + case Work::kHorizontalLine_Segment: + pts = HLineIntersect(wt.pts(), wn.left(), + wn.right(), wn.y(), wn.xFlipped(), ts); + break; + case Work::kVerticalLine_Segment: + pts = VLineIntersect(wt.pts(), wn.top(), + wn.bottom(), wn.x(), wn.yFlipped(), ts); + break; + case Work::kLine_Segment: { + pts = LineIntersect(wt.pts(), wn.pts(), ts); + debugShowLineIntersection(pts, wt, wn, + ts.fT[1], ts.fT[0]); + break; + } + case Work::kQuad_Segment: { + swap = true; + pts = QuadLineIntersect(wn.pts(), wt.pts(), ts); + break; + } + case Work::kCubic_Segment: { + swap = true; + pts = CubicLineIntersect(wn.pts(), wt.pts(), ts); + break; + } + default: + SkASSERT(0); + } + break; + case Work::kQuad_Segment: + switch (wn.segmentType()) { + case Work::kHorizontalLine_Segment: + pts = HQuadIntersect(wt.pts(), wn.left(), + wn.right(), wn.y(), wn.xFlipped(), ts); + break; + case Work::kVerticalLine_Segment: + pts = VQuadIntersect(wt.pts(), wn.top(), + wn.bottom(), wn.x(), wn.yFlipped(), ts); + break; + case Work::kLine_Segment: { + pts = QuadLineIntersect(wt.pts(), wn.pts(), ts); + break; + } + case Work::kQuad_Segment: { + pts = QuadIntersect(wt.pts(), wn.pts(), ts); + break; + } + case Work::kCubic_Segment: { + wt.promoteToCubic(); + pts = CubicIntersect(wt.cubic(), wn.pts(), ts); + break; + } + default: + SkASSERT(0); + } + break; + case Work::kCubic_Segment: + switch (wn.segmentType()) { + case Work::kHorizontalLine_Segment: + pts = HCubicIntersect(wt.pts(), wn.left(), + wn.right(), wn.y(), wn.xFlipped(), ts); + break; + case Work::kVerticalLine_Segment: + pts = VCubicIntersect(wt.pts(), wn.top(), + wn.bottom(), wn.x(), wn.yFlipped(), ts); + break; + case Work::kLine_Segment: { + pts = CubicLineIntersect(wt.pts(), wn.pts(), ts); + break; + } + case Work::kQuad_Segment: { + wn.promoteToCubic(); + pts = CubicIntersect(wt.pts(), wn.cubic(), ts); + break; + } + case Work::kCubic_Segment: { + pts = CubicIntersect(wt.pts(), wn.pts(), ts); + break; + } + default: + SkASSERT(0); + } + break; + default: + SkASSERT(0); + } + // in addition to recording T values, record matching segment + bool coincident = pts == 2 && wn.segmentType() <= Work::kLine_Segment + && wt.segmentType() <= Work::kLine_Segment; + for (int pt = 0; pt < pts; ++pt) { + SkASSERT(ts.fT[0][pt] >= 0 && ts.fT[0][pt] <= 1); + SkASSERT(ts.fT[1][pt] >= 0 && ts.fT[1][pt] <= 1); + int testTAt = wt.addT(ts.fT[swap][pt], wn); + int nextTAt = wn.addT(ts.fT[!swap][pt], wt); + wt.addOtherT(testTAt, ts.fT[!swap][pt], coincident); + wn.addOtherT(nextTAt, ts.fT[swap][pt], coincident); + } + } while (wn.advance()); + } while (wt.advance()); + return true; +} + +// Each segment may have an inside or an outside. Segments contained within +// winding may have insides on either side, and form a contour that should be +// ignored. Segments that are coincident with opposing direction segments may +// have outsides on either side, and should also disappear. +// 'Normal' segments will have one inside and one outside. Subsequent connections +// when winding should follow the intersection direction. If more than one edge +// is an option, choose first edge that continues the inside. + +static void bridge(SkTDArray<Contour*>& contourList) { + // Start at the top. Above the top is outside, below is inside. + Contour* topContour = contourList[0]; + Segment& topStart = topContour->topSegment(); + int index; + const Segment* topSegment = topStart.findTop(index); + start here ; + // find span + // handle coincident + // mark neighbors winding coverage + // output span + // mark span as processed + +} + +static void makeContourList(SkTArray<Contour>& contours, Contour& sentinel, + SkTDArray<Contour*>& list) { + size_t count = contours.count(); + if (count == 0) { + return; + } + for (size_t index = 0; index < count; ++index) { + *list.append() = &contours[index]; + } + *list.append() = &sentinel; + QSort<Contour>(list.begin(), list.end() - 1); +} + +void simplifyx(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 segments + SkTArray<Contour> contours; + // FIXME: add self-intersecting cubics' T values to segment + EdgeBuilder builder(path, contours); + SkTDArray<Contour*> contourList; + Contour sentinel; + sentinel.reset(); + makeContourList(contours, sentinel, contourList); + Contour** currentPtr = contourList.begin(); + if (!currentPtr) { + return; + } + // find all intersections between segments + do { + Contour** nextPtr = currentPtr; + Contour* current = *currentPtr++; + Contour* next; + do { + next = *nextPtr++; + } while (next != &sentinel && addIntersectingTs(current, next)); + } while (*currentPtr != &sentinel); + // construct closed contours + bridge(contourList); +} + |