blob: 7f173eed6d74e7e4126f02c02d654a4d4ac0608d [file] [log] [blame]
/*
* 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;
}