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>

1 files changed, 421 insertions, 0 deletions

diff --git a/src/pathops/SkPathOpsAsWinding.cpp b/src/pathops/SkPathOpsAsWinding.cpp
new file mode 100644
index 0000000000..7f173eed6d
--- /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;
+}