src/pathops/SkPathOpsAsWinding.cpp

/*
 * 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 "include/core/SkRect.h"
#include "src/pathops/SkOpEdgeBuilder.h"
#include "src/pathops/SkPathOpsCommon.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.
        tVals[index] = tVals[--count];
    }
    // 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
                // File a bug if this code path is triggered and AsWinding was
                // expected to succeed.
                SkDEBUGF("incomplete\n");
                // TODO: add edges as opangle and sort
            }
            contour.fMinXY = minXY;
            contour.fDirection = direction;
        } while (SkPath::kDone_Verb != verb);
        return winding;
    }

    bool 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
        test.fContained = winding != 0;
        return -1 <= winding && winding <= 1;
    }

    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);
    }

    bool checkContainerChildren(Contour* parent, Contour* child) {
        for (auto grandChild : child->fChildren) {
            if (!checkContainerChildren(child, grandChild)) {
                return false;
            }
        }
        if (parent) {
            if (!containerContains(*parent, *child)) {
                return false;
            }
        }
        return true;
    }

    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);
        if (!winder.checkContainerChildren(nullptr, contour)) {
            return false;
        }
    }
    // 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;
}