123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427 |
- /*
- * 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;
- }
|