fixup winding contours
Add AsWinding to convert SkPath with even odd fill to winding fill.
This basic implementation works for simple non-intersecting paths.
It may fail if contours in paths touch, specifically when the leftmost
point in a contour is shared with another contour.
The incomplete parts are marked with TODO in the code.
If this interface and implementation look promising, I will continue to
tackle the more difficult cases.
R=reed@google.com,bungeman@google.com
Bug: skia:7682
Change-Id: I479fba60072eb1391b451fcb819504245da2e2a9
Reviewed-on: https://skia-review.googlesource.com/147044
Commit-Queue: Cary Clark <caryclark@google.com>
Reviewed-by: Mike Reed <reed@google.com>
diff --git a/src/pathops/SkPathOpsAsWinding.cpp b/src/pathops/SkPathOpsAsWinding.cpp
new file mode 100644
index 0000000..7f173ee
--- /dev/null
+++ b/src/pathops/SkPathOpsAsWinding.cpp
@@ -0,0 +1,421 @@
+/*
+ * Copyright 2018 Google Inc.
+ *
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+#include "SkOpEdgeBuilder.h"
+#include "SkPathOpsCommon.h"
+#include "SkRect.h"
+#include <algorithm>
+#include <vector>
+
+using std::vector;
+
+struct Contour {
+ enum class Direction { // SkPath::Direction doesn't have 'none' state
+ kCCW = -1,
+ kNone,
+ kCW,
+ };
+
+ Contour(const SkRect& bounds, int lastStart, int verbStart)
+ : fBounds(bounds)
+ , fVerbStart(lastStart)
+ , fVerbEnd(verbStart) {
+ }
+
+ vector<Contour*> fChildren;
+ const SkRect fBounds;
+ SkPoint fMinXY{SK_ScalarMax, SK_ScalarMax};
+ const int fVerbStart;
+ const int fVerbEnd;
+ Direction fDirection{Direction::kNone};
+ bool fContained{false};
+ bool fReverse{false};
+};
+
+static const int kPtCount[] = { 1, 1, 2, 2, 3, 0 };
+static const int kPtIndex[] = { 0, 1, 1, 1, 1, 0 };
+
+static Contour::Direction to_direction(SkScalar dy) {
+ return dy > 0 ? Contour::Direction::kCCW : dy < 0 ? Contour::Direction::kCW :
+ Contour::Direction::kNone;
+}
+
+static int contains_edge(SkPoint pts[4], SkPath::Verb verb, SkScalar weight, const SkPoint& edge) {
+ SkRect bounds;
+ bounds.set(pts, kPtCount[verb] + 1);
+ if (bounds.fTop > edge.fY) {
+ return 0;
+ }
+ if (bounds.fBottom <= edge.fY) { // check to see if y is at line end to avoid double counting
+ return 0;
+ }
+ if (bounds.fLeft >= edge.fX) {
+ return 0;
+ }
+ int winding = 0;
+ double tVals[3];
+ Contour::Direction directions[3];
+ // must intersect horz ray with curve in case it intersects more than once
+ int count = (*CurveIntercept[verb * 2])(pts, weight, edge.fY, tVals);
+ SkASSERT(between(0, count, 3));
+ // remove results to the right of edge
+ for (int index = 0; index < count; ) {
+ SkScalar intersectX = (*CurvePointAtT[verb])(pts, weight, tVals[index]).fX;
+ if (intersectX < edge.fX) {
+ ++index;
+ continue;
+ }
+ if (intersectX > edge.fX) {
+ tVals[index] = tVals[--count];
+ continue;
+ }
+ // if intersect x equals edge x, we need to determine if pts is to the left or right of edge
+ if (pts[0].fX < edge.fX && pts[kPtCount[verb]].fX < edge.fX) {
+ ++index;
+ continue;
+ }
+ // TODO : other cases need discriminating. need op angle code to figure it out
+ // example: edge ends 45 degree diagonal going up. If pts is to the left of edge, keep.
+ // if pts is to the right of edge, discard. With code as is, can't distiguish the two cases.
+ if (intersectX < edge.fX) {
+ tVals[index] = tVals[--count];
+ continue;
+ }
+ }
+ // use first derivative to determine if intersection is contributing +1 or -1 to winding
+ for (int index = 0; index < count; ++index) {
+ directions[index] = to_direction((*CurveSlopeAtT[verb])(pts, weight, tVals[index]).fY);
+ }
+ for (int index = 0; index < count; ++index) {
+ // skip intersections that end at edge and go up
+ if (zero_or_one(tVals[index]) && Contour::Direction::kCCW != directions[index]) {
+ continue;
+ }
+ winding += (int) directions[index];
+ }
+ return winding; // note winding indicates containership, not contour direction
+}
+
+static SkScalar conic_weight(const SkPath::Iter& iter, SkPath::Verb verb) {
+ return SkPath::kConic_Verb == verb ? iter.conicWeight() : 1;
+}
+
+static SkPoint left_edge(SkPoint pts[4], SkPath::Verb verb, SkScalar weight,
+ Contour::Direction* direction) {
+ SkASSERT(SkPath::kLine_Verb <= verb && verb <= SkPath::kCubic_Verb);
+ SkPoint result;
+ double dy;
+ double t SK_INIT_TO_AVOID_WARNING;
+ int roots = 0;
+ if (SkPath::kLine_Verb == verb) {
+ result = pts[0].fX < pts[1].fX ? pts[0] : pts[1];
+ dy = pts[1].fY - pts[0].fY;
+ } else if (SkPath::kQuad_Verb == verb) {
+ SkDQuad quad;
+ quad.set(pts);
+ if (!quad.monotonicInX()) {
+ roots = SkDQuad::FindExtrema(&quad[0].fX, &t);
+ }
+ if (roots) {
+ result = quad.ptAtT(t).asSkPoint();
+ } else {
+ result = pts[0].fX < pts[2].fX ? pts[0] : pts[2];
+ t = pts[0].fX < pts[2].fX ? 0 : 1;
+ }
+ dy = quad.dxdyAtT(t).fY;
+ } else if (SkPath::kConic_Verb == verb) {
+ SkDConic conic;
+ conic.set(pts, weight);
+ if (!conic.monotonicInX()) {
+ roots = SkDConic::FindExtrema(&conic[0].fX, weight, &t);
+ }
+ if (roots) {
+ result = conic.ptAtT(t).asSkPoint();
+ } else {
+ result = pts[0].fX < pts[2].fX ? pts[0] : pts[2];
+ t = pts[0].fX < pts[2].fX ? 0 : 1;
+ }
+ dy = conic.dxdyAtT(t).fY;
+ } else {
+ SkASSERT(SkPath::kCubic_Verb == verb);
+ SkDCubic cubic;
+ cubic.set(pts);
+ if (!cubic.monotonicInX()) {
+ double tValues[2];
+ roots = SkDCubic::FindExtrema(&cubic[0].fX, tValues);
+ SkASSERT(roots <= 2);
+ for (int index = 0; index < roots; ++index) {
+ SkPoint temp = cubic.ptAtT(tValues[index]).asSkPoint();
+ if (0 == index || result.fX > temp.fX) {
+ result = temp;
+ t = tValues[index];
+ }
+ }
+ }
+ if (roots) {
+ result = cubic.ptAtT(t).asSkPoint();
+ } else {
+ result = pts[0].fX < pts[3].fX ? pts[0] : pts[3];
+ t = pts[0].fX < pts[3].fX ? 0 : 1;
+ }
+ dy = cubic.dxdyAtT(t).fY;
+ }
+ *direction = to_direction(dy);
+ return result;
+}
+
+class OpAsWinding {
+public:
+ enum class Edge {
+ kInitial,
+ kCompare,
+ };
+
+ OpAsWinding(const SkPath& path)
+ : fPath(path) {
+ }
+
+ void contourBounds(vector<Contour>* containers) {
+ SkRect bounds;
+ bounds.setEmpty();
+ SkPath::RawIter iter(fPath);
+ SkPoint pts[4];
+ SkPath::Verb verb;
+ int lastStart = 0;
+ int verbStart = 0;
+ do {
+ verb = iter.next(pts);
+ if (SkPath::kMove_Verb == verb) {
+ if (!bounds.isEmpty()) {
+ containers->emplace_back(bounds, lastStart, verbStart);
+ lastStart = verbStart;
+ }
+ bounds.setBounds(&pts[kPtIndex[verb]], kPtCount[verb]);
+ }
+ if (SkPath::kLine_Verb <= verb && verb <= SkPath::kCubic_Verb) {
+ SkRect verbBounds;
+ verbBounds.setBounds(&pts[kPtIndex[verb]], kPtCount[verb]);
+ bounds.joinPossiblyEmptyRect(verbBounds);
+ }
+ ++verbStart;
+ } while (SkPath::kDone_Verb != verb);
+ if (!bounds.isEmpty()) {
+ containers->emplace_back(bounds, lastStart, verbStart);
+ }
+ }
+
+ int nextEdge(Contour& contour, Edge edge) {
+ SkPath::Iter iter(fPath, true);
+ SkPoint pts[4];
+ SkPath::Verb verb;
+ int verbCount = -1;
+ int winding = 0;
+ do {
+ verb = iter.next(pts);
+ if (++verbCount < contour.fVerbStart) {
+ continue;
+ }
+ if (verbCount >= contour.fVerbEnd) {
+ continue;
+ }
+ if (SkPath::kLine_Verb > verb || verb > SkPath::kCubic_Verb) {
+ continue;
+ }
+ bool horizontal = true;
+ for (int index = 1; index <= kPtCount[verb]; ++index) {
+ if (pts[0].fY != pts[index].fY) {
+ horizontal = false;
+ break;
+ }
+ }
+ if (horizontal) {
+ continue;
+ }
+ if (edge == Edge::kCompare) {
+ winding += contains_edge(pts, verb, conic_weight(iter, verb), contour.fMinXY);
+ continue;
+ }
+ SkASSERT(edge == Edge::kInitial);
+ Contour::Direction direction;
+ SkPoint minXY = left_edge(pts, verb, conic_weight(iter, verb), &direction);
+ if (minXY.fX > contour.fMinXY.fX) {
+ continue;
+ }
+ if (minXY.fX == contour.fMinXY.fX) {
+ if (minXY.fY != contour.fMinXY.fY) {
+ continue;
+ }
+ if (direction == contour.fDirection) {
+ continue;
+ }
+ // incomplete: must sort edges to find the one most to left
+ SkDebugf("incomplete\n");
+ // TODO: add edges as opangle and sort
+ }
+ contour.fMinXY = minXY;
+ contour.fDirection = direction;
+ } while (SkPath::kDone_Verb != verb);
+ return winding;
+ }
+
+ void containerContains(Contour& contour, Contour& test) {
+ // find outside point on lesser contour
+ // arbitrarily, choose non-horizontal edge where point <= bounds left
+ // note that if leftmost point is control point, may need tight bounds
+ // to find edge with minimum-x
+ if (SK_ScalarMax == test.fMinXY.fX) {
+ this->nextEdge(test, Edge::kInitial);
+ }
+ // find all edges on greater equal or to the left of one on lesser
+ contour.fMinXY = test.fMinXY;
+ int winding = this->nextEdge(contour, Edge::kCompare);
+ // if edge is up, mark contour cw, otherwise, ccw
+ // sum of greater edges direction should be cw, 0, ccw
+ SkASSERT(-1 <= winding && winding <= 1);
+ test.fContained = winding != 0;
+ }
+
+ void inParent(Contour& contour, Contour& parent) {
+ // move contour into sibling list contained by parent
+ for (auto test : parent.fChildren) {
+ if (test->fBounds.contains(contour.fBounds)) {
+ inParent(contour, *test);
+ return;
+ }
+ }
+ // move parent's children into contour's children if contained by contour
+ for (auto iter = parent.fChildren.begin(); iter != parent.fChildren.end(); ) {
+ if (contour.fBounds.contains((*iter)->fBounds)) {
+ contour.fChildren.push_back(*iter);
+ iter = parent.fChildren.erase(iter);
+ continue;
+ }
+ ++iter;
+ }
+ parent.fChildren.push_back(&contour);
+ }
+
+ void checkContainerChildren(Contour* parent, Contour* child) {
+ for (auto grandChild : child->fChildren) {
+ checkContainerChildren(child, grandChild);
+ }
+ if (parent) {
+ containerContains(*parent, *child);
+ }
+ }
+
+ bool markReverse(Contour* parent, Contour* child) {
+ bool reversed = false;
+ for (auto grandChild : child->fChildren) {
+ reversed |= markReverse(grandChild->fContained ? child : parent, grandChild);
+ }
+ if (parent && parent->fDirection == child->fDirection) {
+ child->fReverse = true;
+ child->fDirection = (Contour::Direction) -(int) child->fDirection;
+ return true;
+ }
+ return reversed;
+ }
+
+ void reverseMarkedContours(vector<Contour>& contours, SkPath* result) {
+ SkPath::RawIter iter(fPath);
+ int verbCount = 0;
+ for (auto contour : contours) {
+ SkPath reverse;
+ SkPath* temp = contour.fReverse ? &reverse : result;
+ do {
+ SkPoint pts[4];
+ switch (iter.next(pts)) {
+ case SkPath::kMove_Verb:
+ temp->moveTo(pts[0]);
+ break;
+ case SkPath::kLine_Verb:
+ temp->lineTo(pts[1]);
+ break;
+ case SkPath::kQuad_Verb:
+ temp->quadTo(pts[1], pts[2]);
+ break;
+ case SkPath::kConic_Verb:
+ temp->conicTo(pts[1], pts[2], iter.conicWeight());
+ break;
+ case SkPath::kCubic_Verb:
+ temp->cubicTo(pts[1], pts[2], pts[3]);
+ break;
+ case SkPath::kClose_Verb:
+ temp->close();
+ break;
+ case SkPath::kDone_Verb:
+ break;
+ default:
+ SkASSERT(0);
+ }
+ } while (++verbCount < contour.fVerbEnd);
+ if (contour.fReverse) {
+ result->reverseAddPath(reverse);
+ }
+ }
+ }
+
+private:
+ const SkPath& fPath;
+};
+
+static bool set_result_path(SkPath* result, const SkPath& path, SkPath::FillType fillType) {
+ *result = path;
+ result->setFillType(fillType);
+ return true;
+}
+
+bool SK_API AsWinding(const SkPath& path, SkPath* result) {
+ if (!path.isFinite()) {
+ return false;
+ }
+ SkPath::FillType fillType = path.getFillType();
+ if (fillType == SkPath::kWinding_FillType
+ || fillType == SkPath::kInverseWinding_FillType ) {
+ return set_result_path(result, path, fillType);
+ }
+ fillType = path.isInverseFillType() ? SkPath::kInverseWinding_FillType :
+ SkPath::kWinding_FillType;
+ if (path.isEmpty() || path.isConvex()) {
+ return set_result_path(result, path, fillType);
+ }
+ // count contours
+ vector<Contour> contours; // one per contour
+ OpAsWinding winder(path);
+ winder.contourBounds(&contours);
+ if (contours.size() <= 1) {
+ return set_result_path(result, path, fillType);
+ }
+ // create contour bounding box tree
+ Contour sorted(SkRect(), 0, 0);
+ for (auto& contour : contours) {
+ winder.inParent(contour, sorted);
+ }
+ // if sorted has no grandchildren, no child has to fix its children's winding
+ if (std::all_of(sorted.fChildren.begin(), sorted.fChildren.end(),
+ [](const Contour* contour) -> bool { return !contour->fChildren.size(); } )) {
+ return set_result_path(result, path, fillType);
+ }
+ // starting with outermost and moving inward, see if one path contains another
+ for (auto contour : sorted.fChildren) {
+ winder.nextEdge(*contour, OpAsWinding::Edge::kInitial);
+ winder.checkContainerChildren(nullptr, contour);
+ }
+ // starting with outermost and moving inward, mark paths to reverse
+ bool reversed = false;
+ for (auto contour : sorted.fChildren) {
+ reversed |= winder.markReverse(nullptr, contour);
+ }
+ if (!reversed) {
+ return set_result_path(result, path, fillType);
+ }
+ SkPath temp;
+ temp.setFillType(fillType);
+ winder.reverseMarkedContours(contours, &temp);
+ result->swap(temp);
+ return true;
+}