save work in progress
git-svn-id: http://skia.googlecode.com/svn/trunk@3141 2bbb7eff-a529-9590-31e7-b0007b416f81
diff --git a/experimental/Intersection/EdgeWalker.cpp b/experimental/Intersection/EdgeWalker.cpp
new file mode 100644
index 0000000..bf090e7
--- /dev/null
+++ b/experimental/Intersection/EdgeWalker.cpp
@@ -0,0 +1,498 @@
+
+/*
+ * 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 "LineIntersection.h"
+#include "SkPath.h"
+#include "SkRect.h"
+#include "SkTArray.h"
+#include "SkTDArray.h"
+#include "TSearch.h"
+
+static int lineIntersect(const SkPoint a[2], const SkPoint b[2],
+ double aRange[2], double bRange[2]) {
+ _Line aLine = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}};
+ _Line bLine = {{b[0].fX, b[0].fY}, {b[1].fX, b[1].fY}};
+ return intersect(aLine, bLine, aRange, bRange);
+}
+
+static int lineIntersect(const SkPoint a[2], SkScalar y, double aRange[2]) {
+ _Line aLine = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}};
+ return horizontalIntersect(aLine, y, aRange);
+}
+
+// functions
+void contourBounds(const SkPath& path, SkTDArray<SkRect>& boundsArray);
+void simplify(const SkPath& path, bool asFill, SkPath& simple);
+/*
+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);
+ }
+ }
+}
+
+// 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;
+ }
+};
+
+struct Edge;
+
+struct Intercepts {
+ SkTDArray<double> fTs;
+};
+
+struct Edge {
+ bool operator<(const Edge& rh) const {
+ return fBounds.fTop == rh.fBounds.fTop
+ ? fBounds.fLeft < rh.fBounds.fLeft
+ : fBounds.fTop < rh.fBounds.fTop;
+ }
+
+ void add(double* ts, size_t count, int verbIndex) {
+ Intercepts& intercepts = fIntercepts[verbIndex];
+ // FIXME: in the pathological case where there is a ton of intercepts, binary search?
+ for (size_t index = 0; index < count; ++index) {
+ double t = ts[index];
+ size_t tCount = intercepts.fTs.count();
+ for (size_t idx2 = 0; idx2 < tCount; ++idx2) {
+ if (t <= intercepts.fTs[idx2]) {
+ if (t < intercepts.fTs[idx2]) {
+ *intercepts.fTs.insert(idx2) = t;
+ break;
+ }
+ }
+ }
+ if (tCount == 0 || t > intercepts.fTs[tCount - 1]) {
+ *intercepts.fTs.append() = t;
+ }
+ }
+ }
+
+ bool cached(const Edge* 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) {
+ SkPoint* ptPtr = fPts.begin();
+ SkPoint* ptLast = fPts.end();
+ if (ptPtr == ptLast) {
+ SkDebugf("empty edge\n");
+ 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;
+ }
+ fIntercepts.push_back_n(1);
+ fWinding = winding;
+ }
+
+ // temporary data : move this to a separate struct?
+ SkTDArray<const Edge*> fCached; // list of edges already intercepted
+ SkTArray<Intercepts> fIntercepts; // one per verb
+
+
+ // persistent data
+ SkTDArray<SkPoint> fPts;
+ SkTDArray<uint8_t> fVerbs;
+ Bounds fBounds;
+ signed char fWinding;
+};
+
+class EdgeBuilder {
+public:
+
+EdgeBuilder(const SkPath& path, bool ignoreHorizontal, SkTArray<Edge>& edges)
+ : fPath(path)
+ , fCurrentEdge(NULL)
+ , fEdges(edges)
+ , fIgnoreHorizontal(ignoreHorizontal)
+{
+ walk();
+}
+
+protected:
+
+void addEdge() {
+ fCurrentEdge->fPts.append(fPtCount - fPtOffset, &fPts[fPtOffset]);
+ fPtOffset = 1;
+ *fCurrentEdge->fVerbs.append() = fVerb;
+}
+
+int direction(int count) {
+ fPtCount = count;
+ fIgnorableHorizontal = fIgnoreHorizontal && isHorizontal();
+ if (fIgnorableHorizontal) {
+ return 0;
+ }
+ int last = count - 1;
+ return fPts[0].fY == fPts[last].fY
+ ? fPts[0].fX == fPts[last].fX ? 0 : fPts[0].fX > fPts[last].fX
+ ? 1 : -1 : fPts[0].fY > fPts[last].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() {
+ 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:
+ winding = 0;
+ startEdge();
+ continue;
+ case SkPath::kLine_Verb:
+ winding = direction(2);
+ break;
+ case SkPath::kQuad_Verb:
+ winding = direction(3);
+ break;
+ case SkPath::kCubic_Verb:
+ winding = direction(4);
+ break;
+ case SkPath::kClose_Verb:
+ if (fCurrentEdge->fVerbs.count()) {
+ fCurrentEdge->complete(fWinding);
+ }
+ continue;
+ default:
+ SkDEBUGFAIL("bad verb");
+ return;
+ }
+ if (fIgnorableHorizontal) {
+ continue;
+ }
+ if (fWinding + winding == 0) {
+ // FIXME: if prior verb or this verb is a horizontal line, reverse
+ // it instead of starting a new edge
+ fCurrentEdge->complete(fWinding);
+ startEdge();
+ }
+ fWinding = winding;
+ addEdge();
+ }
+ fCurrentEdge->complete(fWinding);
+}
+
+private:
+ const SkPath& fPath;
+ Edge* fCurrentEdge;
+ SkTArray<Edge>& fEdges;
+ SkPoint fPts[4];
+ SkPath::Verb fVerb;
+ int fPtCount;
+ int fPtOffset;
+ int8_t fWinding;
+ bool fIgnorableHorizontal;
+ bool fIgnoreHorizontal;
+};
+
+class WorkEdge {
+public:
+ WorkEdge(const Edge* edge) {
+ fVerbStart = edge->fVerbs.begin();
+ if ((fWinding = edge->fWinding) > 0) {
+ fPts = edge->fPts.begin();
+ fVerb = fVerbStart;
+ fVerbEnd = edge->fVerbs.end();
+ } else {
+ fPts = edge->fPts.end();
+ fVerb = edge->fVerbs.end();
+ fVerbEnd = fVerbStart;
+ next();
+ }
+ }
+
+ SkScalar bottom() const {
+ return fPts[fWinding > 0 ? verb() : 0].fY;
+ }
+
+ bool next() {
+ if (fWinding > 0) {
+ fPts += *fVerb;
+ return ++fVerb != fVerbEnd;
+ } else {
+ if (fVerb == fVerbEnd) {
+ return false;
+ }
+ fPts -= *--fVerb;
+ return true;
+ }
+ }
+
+ const SkPoint* points() const {
+ return fPts;
+ }
+
+ SkPath::Verb verb() const {
+ return (SkPath::Verb) *fVerb;
+ }
+
+ int verbIndex() const {
+ return fVerb - fVerbStart;
+ }
+
+protected:
+ const SkPoint* fPts;
+ const uint8_t* fVerb;
+ const uint8_t* fVerbEnd;
+ const uint8_t* fVerbStart;
+ int8_t fWinding;
+};
+
+struct ActiveEdge {
+ void init(const Edge* test) {
+ fEdge = test;
+ if (!fEdge->fIntercepts.count()) {
+ fBounds = test->fBounds;
+ fPtStart = 0;
+ fPtEnd = test->fPts.count();
+ fVerbStart = 0;
+ fVerbEnd = test->fVerbs.count();
+ fTStart = 0;
+ fTEnd = SK_Scalar1;
+ } else {
+ // FIXME: initialize from intercepts
+
+ }
+ }
+
+ const Edge* fEdge;
+ SkRect fBounds;
+ int fPtStart;
+ int fPtEnd;
+ int fVerbStart;
+ int fVerbEnd;
+ SkScalar fTStart;
+ SkScalar fTEnd;
+};
+
+void simplify(const SkPath& path, bool asFill, SkPath& simple) {
+ // 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<Edge> edges;
+ EdgeBuilder builder(path, asFill, edges);
+ size_t edgeCount = edges.count();
+ simple.reset();
+ if (edgeCount == 0) {
+ return;
+ }
+ // returns 1 for evenodd, -1 for winding, regardless of inverse-ness
+ int windingMask = (path.getFillType() & 1) ? 1 : -1;
+ SkTDArray<Edge*> edgeList;
+ for (size_t index = 0; index < edgeCount; ++index) {
+ *edgeList.append() = &edges[index];
+ }
+ Edge edgeSentinel;
+ edgeSentinel.fBounds.set(SK_ScalarMax, SK_ScalarMax, SK_ScalarMax, SK_ScalarMax);
+ *edgeList.append() = &edgeSentinel;
+ ++edgeCount;
+ QSort<Edge>(edgeList.begin(), edgeCount);
+ Edge** currentPtr = edgeList.begin();
+ Edge* current = *currentPtr;
+ SkScalar y = current->fBounds.fTop;
+ SkScalar bottom = current->fBounds.fBottom;
+ // walk the sorted edges from top to bottom, computing accumulated winding
+ do {
+ // find the list of edges that cross y
+ Edge** lastPtr = currentPtr; // find the edge below the bottom of the first set
+ Edge* last = *lastPtr;
+ while (lastPtr != edgeList.end()) {
+ if (bottom <= last->fBounds.fTop) {
+ break;
+ }
+ SkScalar lastTop = last->fBounds.fTop;
+ // 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 (lastTop > y) {
+ if (bottom > lastTop) {
+ bottom = lastTop;
+ break;
+ }
+ } else if (bottom > last->fBounds.fBottom) {
+ bottom = last->fBounds.fBottom;
+ }
+ last = *++lastPtr;
+ }
+ if (asFill && lastPtr - currentPtr <= 1) {
+ SkDebugf("expect 2 or more edges\n");
+ SkASSERT(0);
+ return;
+ }
+ // find any intersections in the range of active edges
+ Edge** testPtr = currentPtr;
+ Edge* test = *testPtr;
+ while (testPtr != lastPtr) {
+ if (test->fBounds.fBottom > bottom) {
+ WorkEdge wt(test);
+ do {
+ // FIXME: add all combinations of curve types
+ if (wt.verb() == SkPath::kLine_Verb) {
+ double wtTs[2];
+ int pts = lineIntersect(wt.points(), bottom, wtTs);
+ if (pts) {
+ test->add(wtTs, pts, wt.verbIndex());
+ }
+ }
+ } while (wt.next());
+ }
+ test = *++testPtr;
+ }
+ testPtr = currentPtr;
+ test = *testPtr;
+ while (testPtr != lastPtr - 1) {
+ Edge* next = *++testPtr;
+ // OPTIMIZATION: if test and next is inside the winding of outer
+ // edges such that intersecting them is irrelevent, skip them.
+ if (!test->cached(next)
+ && Bounds::Intersects(test->fBounds, next->fBounds)) {
+ WorkEdge wt(test);
+ WorkEdge wn(next);
+ do {
+ // FIXME: add all combinations of curve types
+ if (wt.verb() == SkPath::kLine_Verb && wn.verb() == SkPath::kLine_Verb) {
+ double wtTs[2], wnTs[2];
+ int pts = lineIntersect(wt.points(), wn.points(), wtTs, wnTs);
+ if (pts) {
+ test->add(wtTs, pts, wt.verbIndex());
+ next->add(wnTs, pts, wn.verbIndex());
+ }
+ }
+ } while (wt.bottom() <= wn.bottom() ? wt.next() : wn.next());
+ }
+ test = next;
+ }
+ // stitch edge and t range that satisfies operation
+ int winding = 0;
+ testPtr = currentPtr;
+ test = *testPtr;
+ while (testPtr != lastPtr - 1) {
+ int lastWinding = winding;
+ winding += test->fWinding;
+ if ((lastWinding & windingMask) == 0 || (winding & windingMask) == 0) {
+ // append pts, verbs, in front of or behind output
+ // a verb may have one or more inter-T value, but only break
+ // curve if curve at t changes winding inclusion
+ ;
+ }
+ test = *++testPtr;
+ }
+ y = bottom;
+ while ((*currentPtr)->fBounds.fBottom >= y) {
+ ++currentPtr;
+ }
+ } while (*currentPtr != &edgeSentinel);
+ // assemble output path from string of pts, verbs
+ ;
+}
+
+void testSimplify();
+
+void testSimplify() {
+ SkPath path, out;
+ path.setFillType(SkPath::kWinding_FillType);
+ path.addRect(10, 10, 30, 30);
+ path.addRect(20, 20, 40, 40);
+ simplify(path, true, out);
+ path = out;
+ path.addRect(30, 10, 40, 20);
+ path.addRect(10, 30, 20, 40);
+ simplify(path, true, out);
+ path = out;
+ path.addRect(10, 10, 40, 40, SkPath::kCCW_Direction);
+ simplify(path, true, out);
+ if (!out.isEmpty()) {
+ SkDebugf("expected empty\n");
+ }
+}