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