/* * 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 #include 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 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* 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& 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 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; }