aboutsummaryrefslogtreecommitdiffhomepage
path: root/src/pathops
diff options
context:
space:
mode:
Diffstat (limited to 'src/pathops')
-rw-r--r--src/pathops/SkDCubicLineIntersection.cpp28
-rw-r--r--src/pathops/SkDLineIntersection.cpp242
-rw-r--r--src/pathops/SkDQuadLineIntersection.cpp55
-rw-r--r--src/pathops/SkIntersections.cpp43
-rw-r--r--src/pathops/SkIntersections.h11
-rw-r--r--src/pathops/SkOpAngle.cpp4
-rw-r--r--src/pathops/SkOpEdgeBuilder.cpp169
-rw-r--r--src/pathops/SkOpEdgeBuilder.h5
-rw-r--r--src/pathops/SkOpSegment.cpp27
-rw-r--r--src/pathops/SkOpSegment.h5
-rw-r--r--src/pathops/SkPathOpsCommon.cpp4
-rw-r--r--src/pathops/SkPathOpsDebug.cpp79
-rw-r--r--src/pathops/SkPathOpsDebug.h20
-rw-r--r--src/pathops/SkPathOpsOp.cpp15
-rw-r--r--src/pathops/SkPathOpsPoint.h10
-rw-r--r--src/pathops/SkPathOpsTypes.cpp16
-rw-r--r--src/pathops/SkPathOpsTypes.h5
-rw-r--r--src/pathops/SkReduceOrder.cpp12
-rw-r--r--src/pathops/SkReduceOrder.h4
19 files changed, 422 insertions, 332 deletions
diff --git a/src/pathops/SkDCubicLineIntersection.cpp b/src/pathops/SkDCubicLineIntersection.cpp
index 11876f8d73..418e107e41 100644
--- a/src/pathops/SkDCubicLineIntersection.cpp
+++ b/src/pathops/SkDCubicLineIntersection.cpp
@@ -105,6 +105,11 @@ int intersect() {
double lineT = findLineT(cubicT);
if (pinTs(&cubicT, &lineT)) {
SkDPoint pt = line.xyAtT(lineT);
+#if ONE_OFF_DEBUG
+ SkDPoint cPt = cubic.xyAtT(cubicT);
+ SkDebugf("%s pt=(%1.9g,%1.9g) cPt=(%1.9g,%1.9g)\n", __FUNCTION__, pt.fX, pt.fY,
+ cPt.fX, cPt.fY);
+#endif
intersections.insert(cubicT, lineT, pt);
}
}
@@ -165,11 +170,34 @@ protected:
void addEndPoints() {
for (int cIndex = 0; cIndex < 4; cIndex += 3) {
+ bool foundEnd = false;
for (int lIndex = 0; lIndex < 2; lIndex++) {
if (cubic[cIndex] == line[lIndex]) {
intersections.insert(cIndex >> 1, lIndex, line[lIndex]);
+ foundEnd = true;
}
}
+ // for the test case this was written for, the dist / error ratio was 170.6667
+ // it looks like the cubic stops short of touching the line, but this fixed it.
+ if (foundEnd) {
+ continue;
+ }
+ // See if the cubic end touches the line.
+ double dist = line.isLeft(cubic[cIndex]); // this distance isn't cartesian
+ SkDVector lineLen = line[1] - line[0]; // the x/y magnitudes of the line
+ // compute the ULPS of the larger of the x/y deltas
+ double larger = SkTMax(SkTAbs(lineLen.fX), SkTAbs(lineLen.fY));
+ if (!RoughlyEqualUlps(larger, larger + dist)) { // is the dist within ULPS tolerance?
+ continue;
+ }
+ double lineT = findLineT(cIndex >> 1);
+ if (!between(0, lineT, 1)) {
+ continue;
+ }
+ SkDPoint linePt = line.xyAtT(lineT);
+ if (linePt.approximatelyEqual(cubic[cIndex])) {
+ intersections.insert(cIndex >> 1, lineT, cubic[cIndex]);
+ }
}
}
diff --git a/src/pathops/SkDLineIntersection.cpp b/src/pathops/SkDLineIntersection.cpp
index 13c0dbbef4..3b88b88702 100644
--- a/src/pathops/SkDLineIntersection.cpp
+++ b/src/pathops/SkDLineIntersection.cpp
@@ -75,13 +75,51 @@ int SkIntersections::intersectRay(const SkDLine& a, const SkDLine& b) {
return computePoints(a, used);
}
-/*
- Determine the intersection point of two line segments
- Return FALSE if the lines don't intersect
- from: http://paulbourke.net/geometry/lineline2d/
- */
+static bool checkEndPoint(double x, double y, const SkDLine& l, double* tPtr, int useX) {
+ if (!between(l[0].fX, x, l[1].fX) || !between(l[0].fY, y, l[1].fY)) {
+ return false;
+ }
+ double xLen = l[1].fX - l[0].fX;
+ double yLen = l[1].fY - l[0].fY;
+ if (useX < 0) {
+ useX = SkTAbs(xLen) > SkTAbs(yLen);
+ }
+ // OPTIMIZATION: do between test before divide
+ double t = useX ? (x - l[0].fX) / xLen : (y - l[0].fY) / yLen;
+ if (!between(0, t, 1)) {
+ return false;
+ }
+ double opp = useX ? (1 - t) * l[0].fY + t * l[1].fY : (1 - t) * l[0].fX + t * l[1].fX;
+ if (!AlmostEqualUlps(opp, useX ? y : x)) {
+ return false;
+ }
+ *tPtr = t;
+ return true;
+}
+// note that this only works if both lines are neither horizontal nor vertical
int SkIntersections::intersect(const SkDLine& a, const SkDLine& b) {
+ // see if end points intersect the opposite line
+ double t;
+ for (int iA = 0; iA < 2; ++iA) {
+ if (!checkEndPoint(a[iA].fX, a[iA].fY, b, &t, -1)) {
+ continue;
+ }
+ insert(iA, t, a[iA]);
+ }
+ for (int iB = 0; iB < 2; ++iB) {
+ if (!checkEndPoint(b[iB].fX, b[iB].fY, a, &t, -1)) {
+ continue;
+ }
+ insert(t, iB, b[iB]);
+ }
+ if (used() > 0) {
+ SkASSERT(fUsed <= 2);
+ return used(); // coincident lines are returned here
+ }
+ /* Determine the intersection point of two line segments
+ Return FALSE if the lines don't intersect
+ from: http://paulbourke.net/geometry/lineline2d/ */
double axLen = a[1].fX - a[0].fX;
double ayLen = a[1].fY - a[0].fY;
double bxLen = b[1].fX - b[0].fX;
@@ -105,64 +143,14 @@ int SkIntersections::intersect(const SkDLine& a, const SkDLine& b) {
&& !approximately_zero_inverse(numerB))) && !sk_double_isnan(numerA)
&& !sk_double_isnan(numerB)) {
if (mayNotOverlap) {
- return fUsed = 0;
+ return 0;
}
fT[0][0] = numerA;
fT[1][0] = numerB;
fPt[0] = a.xyAtT(numerA);
return computePoints(a, 1);
}
- /* See if the axis intercepts match:
- ay - ax * ayLen / axLen == by - bx * ayLen / axLen
- axLen * (ay - ax * ayLen / axLen) == axLen * (by - bx * ayLen / axLen)
- axLen * ay - ax * ayLen == axLen * by - bx * ayLen
- */
- if (!AlmostEqualUlps(axLen * a[0].fY - ayLen * a[0].fX,
- axLen * b[0].fY - ayLen * b[0].fX)) {
- return fUsed = 0;
- }
- const double* aPtr;
- const double* bPtr;
- if (fabs(axLen) > fabs(ayLen) || fabs(bxLen) > fabs(byLen)) {
- aPtr = &a[0].fX;
- bPtr = &b[0].fX;
- } else {
- aPtr = &a[0].fY;
- bPtr = &b[0].fY;
- }
- double a0 = aPtr[0];
- double a1 = aPtr[2];
- double b0 = bPtr[0];
- double b1 = bPtr[2];
- // OPTIMIZATION: restructure to reject before the divide
- // e.g., if ((a0 - b0) * (a0 - a1) < 0 || abs(a0 - b0) > abs(a0 - a1))
- // (except efficient)
- double aDenom = a0 - a1;
- if (approximately_zero(aDenom)) {
- if (!between(b0, a0, b1)) {
- return fUsed = 0;
- }
- fT[0][0] = fT[0][1] = 0;
- } else {
- double at0 = (a0 - b0) / aDenom;
- double at1 = (a0 - b1) / aDenom;
- if ((at0 < 0 && at1 < 0) || (at0 > 1 && at1 > 1)) {
- return fUsed = 0;
- }
- fT[0][0] = SkTMax(SkTMin(at0, 1.0), 0.0);
- fT[0][1] = SkTMax(SkTMin(at1, 1.0), 0.0);
- }
- double bDenom = b0 - b1;
- if (approximately_zero(bDenom)) {
- fT[1][0] = fT[1][1] = 0;
- } else {
- int bIn = aDenom * bDenom < 0;
- fT[1][bIn] = SkTMax(SkTMin((b0 - a0) / bDenom, 1.0), 0.0);
- fT[1][!bIn] = SkTMax(SkTMin((b0 - a1) / bDenom, 1.0), 0.0);
- }
- bool second = fabs(fT[0][0] - fT[0][1]) > FLT_EPSILON;
- SkASSERT((fabs(fT[1][0] - fT[1][1]) <= FLT_EPSILON) ^ second);
- return computePoints(a, 1 + second);
+ return 0;
}
int SkIntersections::horizontal(const SkDLine& line, double y) {
@@ -174,7 +162,7 @@ int SkIntersections::horizontal(const SkDLine& line, double y) {
if (min > y || max < y) {
return fUsed = 0;
}
- if (AlmostEqualUlps(min, max)) {
+ if (AlmostEqualUlps(min, max) && max - min < fabs(line[0].fX - line[1].fX)) {
fT[0][0] = 0;
fT[0][1] = 1;
return fUsed = 2;
@@ -183,42 +171,51 @@ int SkIntersections::horizontal(const SkDLine& line, double y) {
return fUsed = 1;
}
+static bool checkEndPointH(const SkDPoint& end, double left, double right,
+ double y, bool flipped, double* tPtr) {
+ if (!between(left, end.fX, right) || !AlmostEqualUlps(y, end.fY)) {
+ return false;
+ }
+ double t = (end.fX - left) / (right - left);
+ SkASSERT(between(0, t, 1));
+ *tPtr = flipped ? 1 - t : t;
+ return true;
+}
+
int SkIntersections::horizontal(const SkDLine& line, double left, double right,
double y, bool flipped) {
- int result = horizontal(line, y);
- switch (result) {
- case 0:
- break;
- case 1: {
- double xIntercept = line[0].fX + fT[0][0] * (line[1].fX - line[0].fX);
- if (!precisely_between(left, xIntercept, right)) {
- return fUsed = 0;
- }
- fT[1][0] = (xIntercept - left) / (right - left);
- break;
+ // see if end points intersect the opposite line
+ double t;
+ if (checkEndPoint(left, y, line, &t, true)) {
+ insert(t, flipped, left, y);
+ }
+ if (left != right) {
+ if (checkEndPoint(right, y, line, &t, true)) {
+ insert(t, !flipped, right, y);
}
- case 2:
- double a0 = line[0].fX;
- double a1 = line[1].fX;
- double b0 = flipped ? right : left;
- double b1 = flipped ? left : right;
- // FIXME: share common code below
- double at0 = (a0 - b0) / (a0 - a1);
- double at1 = (a0 - b1) / (a0 - a1);
- if ((at0 < 0 && at1 < 0) || (at0 > 1 && at1 > 1)) {
- return fUsed = 0;
+ for (int index = 0; index < 2; ++index) {
+ if (!checkEndPointH(line[index], left, right, y, flipped, &t)) {
+ continue;
}
- fT[0][0] = SkTMax(SkTMin(at0, 1.0), 0.0);
- fT[0][1] = SkTMax(SkTMin(at1, 1.0), 0.0);
- int bIn = (a0 - a1) * (b0 - b1) < 0;
- fT[1][bIn] = SkTMax(SkTMin((b0 - a0) / (b0 - b1), 1.0), 0.0);
- fT[1][!bIn] = SkTMax(SkTMin((b0 - a1) / (b0 - b1), 1.0), 0.0);
- bool second = fabs(fT[0][0] - fT[0][1]) > FLT_EPSILON;
- SkASSERT((fabs(fT[1][0] - fT[1][1]) <= FLT_EPSILON) ^ second);
- return computePoints(line, 1 + second);
+ insert(index, t, line[index]);
+ }
+ }
+ if (used() > 0) {
+ SkASSERT(fUsed <= 2);
+ return used(); // coincident lines are returned here
+ }
+ int result = horizontal(line, y);
+ if (!result) {
+ return 0;
+ }
+ SkASSERT(result == 1);
+ double xIntercept = line[0].fX + fT[0][0] * (line[1].fX - line[0].fX);
+ if (!precisely_between(left, xIntercept, right)) {
+ return fUsed = 0;
}
+ fT[1][0] = (xIntercept - left) / (right - left);
if (flipped) {
- // OPTIMIZATION: instead of swapping, pass original line, use [1].fX - [0].fX
+ // OPTIMIZATION: ? instead of swapping, pass original line, use [1].fX - [0].fX
for (int index = 0; index < result; ++index) {
fT[1][index] = 1 - fT[1][index];
}
@@ -244,40 +241,49 @@ int SkIntersections::vertical(const SkDLine& line, double x) {
return fUsed = 1;
}
+static bool checkEndPointV(const SkDPoint& end, double top, double bottom,
+ double x, bool flipped, double* tPtr) {
+ if (!between(top, end.fY, bottom) || !AlmostEqualUlps(x, end.fX)) {
+ return false;
+ }
+ double t = (end.fY - top) / (bottom - top);
+ SkASSERT(between(0, t, 1));
+ *tPtr = flipped ? 1 - t : t;
+ return true;
+}
+
int SkIntersections::vertical(const SkDLine& line, double top, double bottom,
- double x, bool flipped) {
- int result = vertical(line, x);
- switch (result) {
- case 0:
- break;
- case 1: {
- double yIntercept = line[0].fY + fT[0][0] * (line[1].fY - line[0].fY);
- if (!precisely_between(top, yIntercept, bottom)) {
- return fUsed = 0;
- }
- fT[1][0] = (yIntercept - top) / (bottom - top);
- break;
+ double x, bool flipped) {
+ // see if end points intersect the opposite line
+ double t;
+ if (checkEndPoint(x, top, line, &t, false)) {
+ insert(t, flipped, x, top);
+ }
+ if (top != bottom) {
+ if (checkEndPoint(x, bottom,line, &t, false)) {
+ insert(t, !flipped, x, bottom);
}
- case 2:
- double a0 = line[0].fY;
- double a1 = line[1].fY;
- double b0 = flipped ? bottom : top;
- double b1 = flipped ? top : bottom;
- // FIXME: share common code above
- double at0 = (a0 - b0) / (a0 - a1);
- double at1 = (a0 - b1) / (a0 - a1);
- if ((at0 < 0 && at1 < 0) || (at0 > 1 && at1 > 1)) {
- return fUsed = 0;
+ for (int index = 0; index < 2; ++index) {
+ if (!checkEndPointV(line[index], top, bottom, x, flipped, &t)) {
+ continue;
}
- fT[0][0] = SkTMax(SkTMin(at0, 1.0), 0.0);
- fT[0][1] = SkTMax(SkTMin(at1, 1.0), 0.0);
- int bIn = (a0 - a1) * (b0 - b1) < 0;
- fT[1][bIn] = SkTMax(SkTMin((b0 - a0) / (b0 - b1), 1.0), 0.0);
- fT[1][!bIn] = SkTMax(SkTMin((b0 - a1) / (b0 - b1), 1.0), 0.0);
- bool second = fabs(fT[0][0] - fT[0][1]) > FLT_EPSILON;
- SkASSERT((fabs(fT[1][0] - fT[1][1]) <= FLT_EPSILON) ^ second);
- return computePoints(line, 1 + second);
+ insert( index, t, line[index]);
+ }
+ }
+ if (used() > 0) {
+ SkASSERT(fUsed <= 2);
+ return used(); // coincident lines are returned here
+ }
+ int result = vertical(line, x);
+ if (!result) {
+ return 0;
+ }
+ SkASSERT(result == 1);
+ double yIntercept = line[0].fY + fT[0][0] * (line[1].fY - line[0].fY);
+ if (!precisely_between(top, yIntercept, bottom)) {
+ return fUsed = 0;
}
+ fT[1][0] = (yIntercept - top) / (bottom - top);
if (flipped) {
// OPTIMIZATION: instead of swapping, pass original line, use [1].fY - [0].fY
for (int index = 0; index < result; ++index) {
diff --git a/src/pathops/SkDQuadLineIntersection.cpp b/src/pathops/SkDQuadLineIntersection.cpp
index afaa1552e4..216e31f285 100644
--- a/src/pathops/SkDQuadLineIntersection.cpp
+++ b/src/pathops/SkDQuadLineIntersection.cpp
@@ -200,38 +200,57 @@ protected:
// add endpoints first to get zero and one t values exactly
void addEndPoints() {
for (int qIndex = 0; qIndex < 3; qIndex += 2) {
+ bool foundEnd = false;
for (int lIndex = 0; lIndex < 2; lIndex++) {
if (quad[qIndex] == line[lIndex]) {
intersections->insert(qIndex >> 1, lIndex, line[lIndex]);
+ foundEnd = true;
}
}
+ if (foundEnd) {
+ continue;
+ }
+ // See if the quad end touches the line.
+ double dist = line.isLeft(quad[qIndex]); // this distance isn't cartesian
+ SkDVector lineLen = line[1] - line[0]; // the x/y magnitudes of the line
+ // compute the ULPS of the larger of the x/y deltas
+ double larger = SkTMax(SkTAbs(lineLen.fX), SkTAbs(lineLen.fY));
+ if (!RoughlyEqualUlps(larger, larger + dist)) { // is the dist within ULPS tolerance?
+ continue;
+ }
+ double lineT = findLineT(qIndex >> 1);
+ if (!between(0, lineT, 1)) {
+ continue;
+ }
+ SkDPoint linePt = line.xyAtT(lineT);
+ if (linePt.approximatelyEqual(quad[qIndex])) {
+ intersections->insert(qIndex >> 1, lineT, quad[qIndex]);
+ }
}
}
void addHorizontalEndPoints(double left, double right, double y) {
for (int qIndex = 0; qIndex < 3; qIndex += 2) {
- if (quad[qIndex].fY != y) {
+ if (!AlmostEqualUlps(quad[qIndex].fY, y)) {
continue;
}
- if (quad[qIndex].fX == left) {
- intersections->insert(qIndex >> 1, 0, quad[qIndex]);
- }
- if (quad[qIndex].fX == right) {
- intersections->insert(qIndex >> 1, 1, quad[qIndex]);
+ double x = quad[qIndex].fX;
+ if (between(left, x, right)) {
+ double t = (x - left) / (right - left);
+ intersections->insert(qIndex >> 1, t, quad[qIndex]);
}
}
}
void addVerticalEndPoints(double top, double bottom, double x) {
for (int qIndex = 0; qIndex < 3; qIndex += 2) {
- if (quad[qIndex].fX != x) {
+ if (!AlmostEqualUlps(quad[qIndex].fX, x)) {
continue;
}
- if (quad[qIndex].fY == top) {
- intersections->insert(qIndex >> 1, 0, quad[qIndex]);
- }
- if (quad[qIndex].fY == bottom) {
- intersections->insert(qIndex >> 1, 1, quad[qIndex]);
+ double y = quad[qIndex].fY;
+ if (between(top, y, bottom)) {
+ double t = (y - top) / (bottom - top);
+ intersections->insert(qIndex >> 1, t, quad[qIndex]);
}
}
}
@@ -240,10 +259,22 @@ protected:
SkDPoint xy = quad.xyAtT(t);
double dx = line[1].fX - line[0].fX;
double dy = line[1].fY - line[0].fY;
+#if 0
if (fabs(dx) > fabs(dy)) {
return (xy.fX - line[0].fX) / dx;
}
return (xy.fY - line[0].fY) / dy;
+#else
+ double dxT = (xy.fX - line[0].fX) / dx;
+ double dyT = (xy.fY - line[0].fY) / dy;
+ if (!between(FLT_EPSILON, dxT, 1 - FLT_EPSILON) && between(0, dyT, 1)) {
+ return dyT;
+ }
+ if (!between(FLT_EPSILON, dyT, 1 - FLT_EPSILON) && between(0, dxT, 1)) {
+ return dxT;
+ }
+ return fabs(dx) > fabs(dy) ? dxT : dyT;
+#endif
}
static bool PinTs(double* quadT, double* lineT) {
diff --git a/src/pathops/SkIntersections.cpp b/src/pathops/SkIntersections.cpp
index ace8474d1d..af6cc080ef 100644
--- a/src/pathops/SkIntersections.cpp
+++ b/src/pathops/SkIntersections.cpp
@@ -56,10 +56,31 @@ void SkIntersections::flip() {
void SkIntersections::insertCoincidentPair(double s1, double e1, double s2, double e2,
const SkDPoint& startPt, const SkDPoint& endPt) {
- if (fSwap) {
- remove(s2, e2, startPt, endPt);
- } else {
- remove(s1, e1, startPt, endPt);
+ SkASSERT(s1 < e1);
+ SkASSERT(s2 != e2);
+ if (coincidentUsed() != fUsed) { // if the curve is partially coincident, treat it as fully so
+ for (int index = fUsed - 1; index >= 0; --index) {
+ if (fIsCoincident[0] & (1 << index)) {
+ continue;
+ }
+ double nonCoinT = fT[0][index];
+ if (!between(s1, nonCoinT, e1)) {
+ if (s1 > nonCoinT) {
+ s1 = nonCoinT;
+ } else {
+ e1 = nonCoinT;
+ }
+ }
+ nonCoinT = fT[1][index];
+ if (!between(s2, nonCoinT, e2)) {
+ if ((s2 > nonCoinT) ^ (s2 > e2)) {
+ s2 = nonCoinT;
+ } else {
+ e2 = nonCoinT;
+ }
+ }
+ removeOne(index);
+ }
}
SkASSERT(coincidentUsed() == fUsed);
SkASSERT((coincidentUsed() & 1) != 1);
@@ -135,7 +156,7 @@ void SkIntersections::insertCoincidentPair(double s1, double e1, double s2, doub
insertCoincident(e1, e2, endPt);
}
-int SkIntersections::insert(double one, double two, const SkDPoint& pt) {
+int SkIntersections::insert(double one, double two, double x, double y) {
if (fIsCoincident[0] == 3 && between(fT[0][0], one, fT[0][1])) {
// For now, don't allow a mix of coincident and non-coincident intersections
return -1;
@@ -152,7 +173,8 @@ int SkIntersections::insert(double one, double two, const SkDPoint& pt) {
|| (precisely_equal(two, 1) && !precisely_equal(oldTwo, 1))) {
fT[0][index] = one;
fT[1][index] = two;
- fPt[index] = pt;
+ fPt[index].fX = x;
+ fPt[index].fY = y;
}
return -1;
}
@@ -174,13 +196,18 @@ int SkIntersections::insert(double one, double two, const SkDPoint& pt) {
fIsCoincident[0] += fIsCoincident[0] & ~((1 << index) - 1);
fIsCoincident[1] += fIsCoincident[1] & ~((1 << index) - 1);
}
- fPt[index] = pt;
+ fPt[index].fX = x;
+ fPt[index].fY = y;
fT[0][index] = one;
fT[1][index] = two;
++fUsed;
return index;
}
+int SkIntersections::insert(double one, double two, const SkDPoint& pt) {
+ return insert(one, two, pt.fX, pt.fY);
+}
+
void SkIntersections::insertCoincident(double one, double two, const SkDPoint& pt) {
int index = insertSwap(one, two, pt);
int bit = 1 << index;
@@ -209,6 +236,7 @@ void SkIntersections::quickRemoveOne(int index, int replace) {
}
}
+#if 0
void SkIntersections::remove(double one, double two, const SkDPoint& startPt,
const SkDPoint& endPt) {
for (int index = fUsed - 1; index >= 0; --index) {
@@ -220,6 +248,7 @@ void SkIntersections::remove(double one, double two, const SkDPoint& startPt,
}
}
}
+#endif
void SkIntersections::removeOne(int index) {
int remaining = --fUsed - index;
diff --git a/src/pathops/SkIntersections.h b/src/pathops/SkIntersections.h
index 23470d7884..c0bb61fef0 100644
--- a/src/pathops/SkIntersections.h
+++ b/src/pathops/SkIntersections.h
@@ -96,6 +96,14 @@ public:
}
}
+ int insertSwap(double one, double two, double x, double y) {
+ if (fSwap) {
+ return insert(two, one, x, y);
+ } else {
+ return insert(one, two, x, y);
+ }
+ }
+
bool isCoincident(int index) {
return (fIsCoincident[0] & 1 << index) != 0;
}
@@ -196,6 +204,7 @@ public:
int horizontal(const SkDCubic&, double left, double right, double y, double tRange[3]);
// FIXME : does not respect swap
int insert(double one, double two, const SkDPoint& pt);
+ int insert(double one, double two, double x, double y);
// start if index == 0 : end if index == 1
void insertCoincident(double one, double two, const SkDPoint& pt);
void insertCoincidentPair(double s1, double e1, double s2, double e2,
@@ -233,7 +242,7 @@ public:
private:
int computePoints(const SkDLine& line, int used);
// used by addCoincident to remove ordinary intersections in range
- void remove(double one, double two, const SkDPoint& startPt, const SkDPoint& endPt);
+ // void remove(double one, double two, const SkDPoint& startPt, const SkDPoint& endPt);
SkDPoint fPt[9];
double fT[2][9];
diff --git a/src/pathops/SkOpAngle.cpp b/src/pathops/SkOpAngle.cpp
index 0ac5a3da78..0dd0d65f79 100644
--- a/src/pathops/SkOpAngle.cpp
+++ b/src/pathops/SkOpAngle.cpp
@@ -22,7 +22,7 @@ static const int bugChar = strlen(funcName) + 1;
#if DEBUG_ANGLE
static bool CompareResult(SkString* bugOut, const char* append, bool compare) {
- bugOut->appendf(append);
+ bugOut->appendf("%s", append);
bugOut->writable_str()[bugChar] = "><"[compare];
SkDebugf("%s\n", bugOut->c_str());
return compare;
@@ -141,7 +141,7 @@ bool SkOpAngle::operator<(const SkOpAngle& rh) const { // this/lh: left-hand; r
}
}
if (fSide * rh.fSide == 0) {
- SkASSERT(fSide + rh.fSide != 0);
+ SkASSERT(fSide + rh.fSide != 0); // hitting this assert means coincidence was undetected
return COMPARE_RESULT("9 fSide * rh.fSide == 0 ...", fSide < rh.fSide);
}
// at this point, the initial tangent line is nearly coincident
diff --git a/src/pathops/SkOpEdgeBuilder.cpp b/src/pathops/SkOpEdgeBuilder.cpp
index d7f52752bf..5187b5f1e6 100644
--- a/src/pathops/SkOpEdgeBuilder.cpp
+++ b/src/pathops/SkOpEdgeBuilder.cpp
@@ -4,6 +4,7 @@
* Use of this source code is governed by a BSD-style license that can be
* found in the LICENSE file.
*/
+#include "SkGeometry.h"
#include "SkOpEdgeBuilder.h"
#include "SkReduceOrder.h"
@@ -37,70 +38,114 @@ bool SkOpEdgeBuilder::finish() {
if (fCurrentContour && !fCurrentContour->segments().count()) {
fContours.pop_back();
}
- // correct pointers in contours since fReducePts may have moved as it grew
- int cIndex = 0;
- int extraCount = fExtra.count();
- SkASSERT(extraCount == 0 || fExtra[0] == -1);
- int eIndex = 0;
- int rIndex = 0;
- while (++eIndex < extraCount) {
- int offset = fExtra[eIndex];
- if (offset < 0) {
- ++cIndex;
- continue;
+ return true;
+}
+
+void SkOpEdgeBuilder::closeContour(const SkPoint& curveEnd, const SkPoint& curveStart) {
+ if ((!AlmostEqualUlps(curveEnd.fX, curveStart.fX)
+ || !AlmostEqualUlps(curveEnd.fY, curveStart.fY))) {
+ fPathVerbs.push_back(SkPath::kLine_Verb);
+ fPathPts.push_back_n(1, &curveStart);
+ } else {
+ if (curveEnd.fX != curveStart.fX || curveEnd.fY != curveStart.fY) {
+ fPathPts[fPathPts.count() - 1] = curveStart;
+ } else {
+ fPathPts[fPathPts.count() - 1] = curveStart;
}
- fCurrentContour = &fContours[cIndex];
- rIndex += fCurrentContour->updateSegment(offset - 1,
- &fReducePts[rIndex]);
}
- fExtra.reset(); // we're done with this
- return true;
+ fPathVerbs.push_back(SkPath::kClose_Verb);
}
-// Note that copying the points here avoids copying the resulting path later.
-// To allow Op() to take one of the input paths as an output parameter, either the source data
-// must be copied (as implemented below) or the result must be copied.
-// OPTIMIZATION: This copies both sets of input points every time. If the input data was read
-// directly, the output path would only need to be copied if it was also one of the input paths.
int SkOpEdgeBuilder::preFetch() {
if (!fPath->isFinite()) {
fUnparseable = true;
return 0;
}
+ SkAutoConicToQuads quadder;
+ const SkScalar quadderTol = SK_Scalar1 / 16;
SkPath::RawIter iter(*fPath);
+ SkPoint curveStart;
+ SkPoint curve[4];
SkPoint pts[4];
SkPath::Verb verb;
+ bool lastCurve = false;
do {
verb = iter.next(pts);
- fPathVerbs.push_back(verb);
- if (verb == SkPath::kMove_Verb) {
- fPathPts.push_back(pts[0]);
- } else if (verb >= SkPath::kLine_Verb && verb <= SkPath::kCubic_Verb) {
- fPathPts.push_back_n(SkPathOpsVerbToPoints(verb), &pts[1]);
+ switch (verb) {
+ case SkPath::kMove_Verb:
+ if (!fAllowOpenContours && lastCurve) {
+ closeContour(curve[0], curveStart);
+ }
+ fPathVerbs.push_back(verb);
+ fPathPts.push_back(pts[0]);
+ curveStart = curve[0] = pts[0];
+ lastCurve = false;
+ continue;
+ case SkPath::kLine_Verb:
+ if (AlmostEqualUlps(curve[0].fX, pts[1].fX)
+ && AlmostEqualUlps(curve[0].fY, pts[1].fY)) {
+ continue; // skip degenerate points
+ }
+ break;
+ case SkPath::kQuad_Verb:
+ curve[1] = pts[1];
+ curve[2] = pts[2];
+ verb = SkReduceOrder::Quad(curve, pts);
+ if (verb == SkPath::kMove_Verb) {
+ continue; // skip degenerate points
+ }
+ break;
+ case SkPath::kConic_Verb: {
+ const SkPoint* quadPts = quadder.computeQuads(pts, iter.conicWeight(),
+ quadderTol);
+ const int nQuads = quadder.countQuads();
+ for (int i = 0; i < nQuads; ++i) {
+ fPathVerbs.push_back(SkPath::kQuad_Verb);
+ }
+ fPathPts.push_back_n(nQuads * 2, quadPts);
+ curve[0] = quadPts[nQuads * 2 - 1];
+ lastCurve = true;
+ }
+ continue;
+ case SkPath::kCubic_Verb:
+ curve[1] = pts[1];
+ curve[2] = pts[2];
+ curve[3] = pts[3];
+ verb = SkReduceOrder::Cubic(curve, pts);
+ if (verb == SkPath::kMove_Verb) {
+ continue; // skip degenerate points
+ }
+ break;
+ case SkPath::kClose_Verb:
+ closeContour(curve[0], curveStart);
+ lastCurve = false;
+ continue;
+ case SkPath::kDone_Verb:
+ continue;
}
+ fPathVerbs.push_back(verb);
+ int ptCount = SkPathOpsVerbToPoints(verb);
+ fPathPts.push_back_n(ptCount, &pts[1]);
+ curve[0] = pts[ptCount];
+ lastCurve = true;
} while (verb != SkPath::kDone_Verb);
+ if (!fAllowOpenContours && lastCurve) {
+ closeContour(curve[0], curveStart);
+ }
+ fPathVerbs.push_back(SkPath::kDone_Verb);
return fPathVerbs.count() - 1;
}
bool SkOpEdgeBuilder::close() {
- if (fFinalCurveStart && fFinalCurveEnd && *fFinalCurveStart != *fFinalCurveEnd) {
- fReducePts.push_back(*fFinalCurveStart);
- fReducePts.push_back(*fFinalCurveEnd);
- const SkPoint* lineStart = fReducePts.end() - 2;
- fExtra.push_back(fCurrentContour->addLine(lineStart));
- }
complete();
return true;
}
bool SkOpEdgeBuilder::walk() {
- SkPath::Verb reducedVerb;
uint8_t* verbPtr = fPathVerbs.begin();
uint8_t* endOfFirstHalf = &verbPtr[fSecondHalf];
- const SkPoint* pointsPtr = fPathPts.begin();
+ const SkPoint* pointsPtr = fPathPts.begin() - 1;
SkPath::Verb verb;
- fFinalCurveStart = NULL;
- fFinalCurveEnd = NULL;
while ((verb = (SkPath::Verb) *verbPtr) != SkPath::kDone_Verb) {
if (verbPtr == endOfFirstHalf) {
fOperand = true;
@@ -119,49 +164,18 @@ bool SkOpEdgeBuilder::walk() {
fCurrentContour = fContours.push_back_n(1);
fCurrentContour->setOperand(fOperand);
fCurrentContour->setXor(fXorMask[fOperand] == kEvenOdd_PathOpsMask);
- fExtra.push_back(-1); // start new contour
}
- fFinalCurveEnd = pointsPtr++;
+ pointsPtr += 1;
continue;
- case SkPath::kLine_Verb: {
- const SkPoint& lineEnd = pointsPtr[0];
- const SkPoint& lineStart = pointsPtr[-1];
- // skip degenerate points
- if (lineStart.fX != lineEnd.fX || lineStart.fY != lineEnd.fY) {
- fCurrentContour->addLine(&lineStart);
- }
- } break;
- case SkPath::kQuad_Verb: {
- const SkPoint* quadStart = &pointsPtr[-1];
- reducedVerb = SkReduceOrder::Quad(quadStart, &fReducePts);
- if (reducedVerb == 0) {
- break; // skip degenerate points
- }
- if (reducedVerb == SkPath::kLine_Verb) {
- const SkPoint* lineStart = fReducePts.end() - 2;
- fExtra.push_back(fCurrentContour->addLine(lineStart));
- break;
- }
- fCurrentContour->addQuad(quadStart);
- } break;
- case SkPath::kCubic_Verb: {
- const SkPoint* cubicStart = &pointsPtr[-1];
- reducedVerb = SkReduceOrder::Cubic(cubicStart, &fReducePts);
- if (reducedVerb == 0) {
- break; // skip degenerate points
- }
- if (reducedVerb == SkPath::kLine_Verb) {
- const SkPoint* lineStart = fReducePts.end() - 2;
- fExtra.push_back(fCurrentContour->addLine(lineStart));
- break;
- }
- if (reducedVerb == SkPath::kQuad_Verb) {
- const SkPoint* quadStart = fReducePts.end() - 3;
- fExtra.push_back(fCurrentContour->addQuad(quadStart));
- break;
- }
- fCurrentContour->addCubic(cubicStart);
- } break;
+ case SkPath::kLine_Verb:
+ fCurrentContour->addLine(pointsPtr);
+ break;
+ case SkPath::kQuad_Verb:
+ fCurrentContour->addQuad(pointsPtr);
+ break;
+ case SkPath::kCubic_Verb:
+ fCurrentContour->addCubic(pointsPtr);
+ break;
case SkPath::kClose_Verb:
SkASSERT(fCurrentContour);
if (!close()) {
@@ -172,7 +186,6 @@ bool SkOpEdgeBuilder::walk() {
SkDEBUGFAIL("bad verb");
return false;
}
- fFinalCurveStart = &pointsPtr[SkPathOpsVerbToPoints(verb) - 1];
pointsPtr += SkPathOpsVerbToPoints(verb);
SkASSERT(fCurrentContour);
}
diff --git a/src/pathops/SkOpEdgeBuilder.h b/src/pathops/SkOpEdgeBuilder.h
index 2a2bf034e4..df0795b0c8 100644
--- a/src/pathops/SkOpEdgeBuilder.h
+++ b/src/pathops/SkOpEdgeBuilder.h
@@ -43,6 +43,7 @@ public:
void init();
private:
+ void closeContour(const SkPoint& curveEnd, const SkPoint& curveStart);
bool close();
int preFetch();
bool walk();
@@ -52,11 +53,7 @@ private:
SkTArray<uint8_t, true> fPathVerbs;
SkOpContour* fCurrentContour;
SkTArray<SkOpContour>& fContours;
- SkTArray<SkPoint, true> fReducePts; // segments created on the fly
- SkTArray<int, true> fExtra; // -1 marks new contour, > 0 offsets into contour
SkPathOpsMask fXorMask[2];
- const SkPoint* fFinalCurveStart;
- const SkPoint* fFinalCurveEnd;
int fSecondHalf;
bool fOperand;
bool fAllowOpenContours;
diff --git a/src/pathops/SkOpSegment.cpp b/src/pathops/SkOpSegment.cpp
index 08f4f7eace..54e44904f4 100644
--- a/src/pathops/SkOpSegment.cpp
+++ b/src/pathops/SkOpSegment.cpp
@@ -861,7 +861,7 @@ int SkOpSegment::computeSum(int startIndex, int endIndex, bool binary) {
// FIXME?: Not sure if this sort must be ordered or if the relaxed ordering is OK ...
bool sortable = SortAngles(angles, &sorted, SkOpSegment::kMustBeOrdered_SortAngleKind);
#if DEBUG_SORT
- sorted[0]->segment()->debugShowSort(__FUNCTION__, sorted, 0, 0, 0);
+ sorted[0]->segment()->debugShowSort(__FUNCTION__, sorted, 0, 0, 0, sortable);
#endif
if (!sortable) {
return SK_MinS32;
@@ -896,7 +896,7 @@ int SkOpSegment::computeSum(int startIndex, int endIndex, bool binary) {
winding += spanWinding;
}
#if DEBUG_SORT
- base->debugShowSort(__FUNCTION__, sorted, firstIndex, winding, oWinding);
+ base->debugShowSort(__FUNCTION__, sorted, firstIndex, winding, oWinding, sortable);
#endif
int nextIndex = firstIndex + 1;
int lastIndex = firstIndex != 0 ? firstIndex : angleCount;
@@ -1134,6 +1134,7 @@ SkOpSegment* SkOpSegment::findNextOp(SkTDArray<SkOpSpan*>* chase, int* nextStart
while (precisely_zero(startT - other->fTs[*nextEnd].fT));
SkASSERT(step < 0 ? *nextEnd >= 0 : *nextEnd < other->fTs.count());
if (other->isTiny(SkMin32(*nextStart, *nextEnd))) {
+ *unsortable = true;
return NULL;
}
return other;
@@ -1150,7 +1151,7 @@ SkOpSegment* SkOpSegment::findNextOp(SkTDArray<SkOpSpan*>* chase, int* nextStart
int firstIndex = findStartingEdge(sorted, startIndex, end);
SkASSERT(firstIndex >= 0);
#if DEBUG_SORT
- debugShowSort(__FUNCTION__, sorted, firstIndex);
+ debugShowSort(__FUNCTION__, sorted, firstIndex, sortable);
#endif
if (!sortable) {
*unsortable = true;
@@ -1272,7 +1273,7 @@ SkOpSegment* SkOpSegment::findNextWinding(SkTDArray<SkOpSpan*>* chase, int* next
int firstIndex = findStartingEdge(sorted, startIndex, end);
SkASSERT(firstIndex >= 0);
#if DEBUG_SORT
- debugShowSort(__FUNCTION__, sorted, firstIndex);
+ debugShowSort(__FUNCTION__, sorted, firstIndex, sortable);
#endif
if (!sortable) {
*unsortable = true;
@@ -1400,7 +1401,8 @@ SkOpSegment* SkOpSegment::findNextXor(int* nextStart, int* nextEnd, bool* unsort
if (!sortable) {
*unsortable = true;
#if DEBUG_SORT
- debugShowSort(__FUNCTION__, sorted, findStartingEdge(sorted, startIndex, end), 0, 0);
+ debugShowSort(__FUNCTION__, sorted, findStartingEdge(sorted, startIndex, end), 0, 0,
+ sortable);
#endif
return NULL;
}
@@ -1408,7 +1410,7 @@ SkOpSegment* SkOpSegment::findNextXor(int* nextStart, int* nextEnd, bool* unsort
int firstIndex = findStartingEdge(sorted, startIndex, end);
SkASSERT(firstIndex >= 0);
#if DEBUG_SORT
- debugShowSort(__FUNCTION__, sorted, firstIndex, 0, 0);
+ debugShowSort(__FUNCTION__, sorted, firstIndex, 0, 0, sortable);
#endif
SkASSERT(sorted[firstIndex]->segment() == this);
int nextIndex = firstIndex + 1;
@@ -1654,7 +1656,7 @@ SkOpSegment* SkOpSegment::findTop(int* tIndexPtr, int* endIndexPtr, bool* unsort
}
SkASSERT(first < SK_MaxS32);
#if DEBUG_SORT // || DEBUG_SWAP_TOP
- sorted[first]->segment()->debugShowSort(__FUNCTION__, sorted, first, 0, 0);
+ sorted[first]->segment()->debugShowSort(__FUNCTION__, sorted, first, 0, 0, sortable);
#endif
if (onlySortable && !sortable) {
*unsortable = true;
@@ -2565,6 +2567,9 @@ int SkOpSegment::windingAtT(double tHit, int tIndex, bool crossOpp, SkScalar* dx
#endif
return SK_MinS32;
}
+ if (windVal < 0) { // reverse sign if opp contour traveled in reverse
+ *dx = -*dx;
+ }
if (winding * *dx > 0) { // if same signs, result is negative
winding += *dx > 0 ? -windVal : windVal;
}
@@ -2769,12 +2774,12 @@ void SkOpSegment::debugShowNewWinding(const char* fun, const SkOpSpan& span, int
#if DEBUG_SORT || DEBUG_SWAP_TOP
void SkOpSegment::debugShowSort(const char* fun, const SkTArray<SkOpAngle*, true>& angles,
int first, const int contourWinding,
- const int oppContourWinding) const {
+ const int oppContourWinding, bool sortable) const {
if (--gDebugSortCount < 0) {
return;
}
SkASSERT(angles[first]->segment() == this);
- SkASSERT(angles.count() > 1);
+ SkASSERT(!sortable || angles.count() > 1);
int lastSum = contourWinding;
int oppLastSum = oppContourWinding;
const SkOpAngle* firstAngle = angles[first];
@@ -2878,12 +2883,12 @@ void SkOpSegment::debugShowSort(const char* fun, const SkTArray<SkOpAngle*, true
}
void SkOpSegment::debugShowSort(const char* fun, const SkTArray<SkOpAngle*, true>& angles,
- int first) {
+ int first, bool sortable) {
const SkOpAngle* firstAngle = angles[first];
const SkOpSegment* segment = firstAngle->segment();
int winding = segment->updateWinding(firstAngle);
int oppWinding = segment->updateOppWinding(firstAngle);
- debugShowSort(fun, angles, first, winding, oppWinding);
+ debugShowSort(fun, angles, first, winding, oppWinding, sortable);
}
#endif
diff --git a/src/pathops/SkOpSegment.h b/src/pathops/SkOpSegment.h
index 94efcb53fe..3cbd29e77e 100644
--- a/src/pathops/SkOpSegment.h
+++ b/src/pathops/SkOpSegment.h
@@ -318,8 +318,9 @@ public:
#endif
#if DEBUG_SORT || DEBUG_SWAP_TOP
void debugShowSort(const char* fun, const SkTArray<SkOpAngle*, true>& angles, int first,
- const int contourWinding, const int oppContourWinding) const;
- void debugShowSort(const char* fun, const SkTArray<SkOpAngle*, true>& angles, int first);
+ const int contourWinding, const int oppContourWinding, bool sortable) const;
+ void debugShowSort(const char* fun, const SkTArray<SkOpAngle*, true>& angles, int first,
+ bool sortable);
#endif
#if DEBUG_CONCIDENT
void debugShowTs() const;
diff --git a/src/pathops/SkPathOpsCommon.cpp b/src/pathops/SkPathOpsCommon.cpp
index 0fa5ce0c92..5a30c3a98e 100644
--- a/src/pathops/SkPathOpsCommon.cpp
+++ b/src/pathops/SkPathOpsCommon.cpp
@@ -138,7 +138,7 @@ SkOpSegment* FindChase(SkTDArray<SkOpSpan*>& chase, int& tIndex, int& endIndex)
SkOpSegment::kMayBeUnordered_SortAngleKind);
int angleCount = sorted.count();
#if DEBUG_SORT
- sorted[0]->segment()->debugShowSort(__FUNCTION__, sorted, 0, 0, 0);
+ sorted[0]->segment()->debugShowSort(__FUNCTION__, sorted, 0, 0, 0, sortable);
#endif
if (!sortable) {
continue;
@@ -162,7 +162,7 @@ SkOpSegment* FindChase(SkTDArray<SkOpSpan*>& chase, int& tIndex, int& endIndex)
winding += spanWinding;
}
#if DEBUG_SORT
- segment->debugShowSort(__FUNCTION__, sorted, firstIndex, winding, 0);
+ segment->debugShowSort(__FUNCTION__, sorted, firstIndex, winding, 0, sortable);
#endif
// we care about first sign and whether wind sum indicates this
// edge is inside or outside. Maybe need to pass span winding
diff --git a/src/pathops/SkPathOpsDebug.cpp b/src/pathops/SkPathOpsDebug.cpp
index 6c8ca954f1..1071b52050 100644
--- a/src/pathops/SkPathOpsDebug.cpp
+++ b/src/pathops/SkPathOpsDebug.cpp
@@ -61,68 +61,29 @@ int gDebugSortCount;
const char* kPathOpStr[] = {"diff", "sect", "union", "xor"};
#endif
-#if DEBUG_SHOW_PATH
-static void showPathContours(SkPath::Iter& iter, const char* pathName) {
- uint8_t verb;
- SkPoint pts[4];
- while ((verb = iter.next(pts)) != SkPath::kDone_Verb) {
- switch (verb) {
- case SkPath::kMove_Verb:
- SkDebugf(" %s.moveTo(%#1.9gf, %#1.9gf);\n", pathName, pts[0].fX, pts[0].fY);
- continue;
- case SkPath::kLine_Verb:
- SkDebugf(" %s.lineTo(%#1.9gf, %#1.9gf);\n", pathName, pts[1].fX, pts[1].fY);
- break;
- case SkPath::kQuad_Verb:
- SkDebugf(" %s.quadTo(%#1.9gf, %#1.9gf, %#1.9gf, %#1.9gf);\n", pathName,
- pts[1].fX, pts[1].fY, pts[2].fX, pts[2].fY);
- break;
- case SkPath::kCubic_Verb:
- SkDebugf(" %s.cubicTo(%#1.9gf, %#1.9gf, %#1.9gf, %#1.9gf, %#1.9gf, %#1.9gf);\n",
- pathName, pts[1].fX, pts[1].fY, pts[2].fX, pts[2].fY, pts[3].fX, pts[3].fY);
- break;
- case SkPath::kClose_Verb:
- SkDebugf(" %s.close();\n", pathName);
- break;
- default:
- SkDEBUGFAIL("bad verb");
- return;
- }
- }
-}
-
-static const char* gFillTypeStr[] = {
- "kWinding_FillType",
- "kEvenOdd_FillType",
- "kInverseWinding_FillType",
- "kInverseEvenOdd_FillType"
-};
-
-
-void ShowFunctionHeader() {
- SkDebugf("\nstatic void test#(skiatest::Reporter* reporter) {\n");
+#if DEBUG_SHOW_TEST_NAME
+void* PathOpsDebugCreateNameStr() {
+ return SkNEW_ARRAY(char, DEBUG_FILENAME_STRING_LENGTH);
}
-void ShowPath(const SkPath& path, const char* pathName) {
- SkPath::Iter iter(path, true);
- SkPath::FillType fillType = path.getFillType();
- SkASSERT(fillType >= SkPath::kWinding_FillType && fillType <= SkPath::kInverseEvenOdd_FillType);
- SkDebugf(" SkPath %s;\n", pathName);
- SkDebugf(" %s.setFillType(SkPath::%s);\n", pathName, gFillTypeStr[fillType]);
- iter.setPath(path, true);
- showPathContours(iter, pathName);
+void PathOpsDebugDeleteNameStr(void* v) {
+ SkDELETE_ARRAY(reinterpret_cast<char* >(v));
}
-static const char* gOpStrs[] = {
- "kDifference_PathOp",
- "kIntersect_PathOp",
- "kUnion_PathOp",
- "kXor_PathOp",
- "kReverseDifference_PathOp",
-};
-
-void ShowOp(SkPathOp op, const char* pathOne, const char* pathTwo) {
- SkDebugf(" testPathOp(reporter, %s, %s, %s);\n", pathOne, pathTwo, gOpStrs[op]);
- SkDebugf("}\n");
+void DebugBumpTestName(char* test) {
+ char* num = test + strlen(test);
+ while (num[-1] >= '0' && num[-1] <= '9') {
+ --num;
+ }
+ if (num[0] == '\0') {
+ return;
+ }
+ int dec = atoi(num);
+ if (dec == 0) {
+ return;
+ }
+ ++dec;
+ SK_SNPRINTF(num, DEBUG_FILENAME_STRING_LENGTH - (num - test), "%d", dec);
}
#endif
+
diff --git a/src/pathops/SkPathOpsDebug.h b/src/pathops/SkPathOpsDebug.h
index cc1b8ead95..5484147c3a 100644
--- a/src/pathops/SkPathOpsDebug.h
+++ b/src/pathops/SkPathOpsDebug.h
@@ -56,7 +56,6 @@ extern int gDebugMaxWindValue;
#define DEBUG_FLOW 0
#define DEBUG_MARK_DONE 0
#define DEBUG_PATH_CONSTRUCTION 0
-#define DEBUG_SHOW_PATH 0
#define DEBUG_SHOW_TEST_NAME 0
#define DEBUG_SHOW_TEST_PROGRESS 0
#define DEBUG_SHOW_WINDING 0
@@ -86,7 +85,6 @@ extern int gDebugMaxWindValue;
#define DEBUG_FLOW 1
#define DEBUG_MARK_DONE 1
#define DEBUG_PATH_CONSTRUCTION 1
-#define DEBUG_SHOW_PATH 0
#define DEBUG_SHOW_TEST_NAME 1
#define DEBUG_SHOW_TEST_PROGRESS 1
#define DEBUG_SHOW_WINDING 0
@@ -141,14 +139,20 @@ void winding_printf(int winding);
extern const char* kPathOpStr[];
#endif
-#ifndef DEBUG_TEST
-#define DEBUG_TEST 0
+#if DEBUG_SHOW_TEST_NAME
+#include "SkTLS.h"
+
+extern void* PathOpsDebugCreateNameStr();
+extern void PathOpsDebugDeleteNameStr(void* v);
+#define DEBUG_FILENAME_STRING_LENGTH 64
+#define DEBUG_FILENAME_STRING \
+ (reinterpret_cast<char* >(SkTLS::Get(PathOpsDebugCreateNameStr, PathOpsDebugDeleteNameStr)))
+extern void DebugBumpTestName(char* );
+extern void DebugShowPath(const SkPath& one, const SkPath& two, SkPathOp op, const char* name);
#endif
-#if DEBUG_SHOW_PATH
-void ShowFunctionHeader();
-void ShowPath(const SkPath& path, const char* pathName);
-void ShowOp(SkPathOp op, const char* pathOne, const char* pathTwo);
+#ifndef DEBUG_TEST
+#define DEBUG_TEST 0
#endif
#endif
diff --git a/src/pathops/SkPathOpsOp.cpp b/src/pathops/SkPathOpsOp.cpp
index 7e1c772893..0df4859cdf 100644
--- a/src/pathops/SkPathOpsOp.cpp
+++ b/src/pathops/SkPathOpsOp.cpp
@@ -41,7 +41,7 @@ static SkOpSegment* findChaseOp(SkTDArray<SkOpSpan*>& chase, int& nextStart, int
SkOpSegment::kMayBeUnordered_SortAngleKind);
int angleCount = sorted.count();
#if DEBUG_SORT
- sorted[0]->segment()->debugShowSort(__FUNCTION__, sorted, 0);
+ sorted[0]->segment()->debugShowSort(__FUNCTION__, sorted, 0, sortable);
#endif
if (!sortable) {
continue;
@@ -54,7 +54,7 @@ static SkOpSegment* findChaseOp(SkTDArray<SkOpSpan*>& chase, int& nextStart, int
segment = angle->segment();
} while (segment->windSum(angle) == SK_MinS32);
#if DEBUG_SORT
- segment->debugShowSort(__FUNCTION__, sorted, firstIndex);
+ segment->debugShowSort(__FUNCTION__, sorted, firstIndex, sortable);
#endif
int sumMiWinding = segment->updateWindingReverse(angle);
int sumSuWinding = segment->updateOppWindingReverse(angle);
@@ -232,11 +232,12 @@ static const bool gOutInverse[kReverseDifference_PathOp + 1][2][2] = {
};
bool Op(const SkPath& one, const SkPath& two, SkPathOp op, SkPath* result) {
-#if DEBUG_SHOW_PATH
- ShowFunctionHeader();
- ShowPath(one, "path");
- ShowPath(two, "pathB");
- ShowOp(op, "path", "pathB");
+#if DEBUG_SHOW_TEST_NAME
+ char* debugName = DEBUG_FILENAME_STRING;
+ if (debugName && debugName[0]) {
+ DebugBumpTestName(debugName);
+ DebugShowPath(one, two, op, debugName);
+ }
#endif
op = gOpInverse[op][one.isInverseFillType()][two.isInverseFillType()];
SkPath::FillType fillType = gOutInverse[op][one.isInverseFillType()][two.isInverseFillType()]
diff --git a/src/pathops/SkPathOpsPoint.h b/src/pathops/SkPathOpsPoint.h
index 534154f199..ad959b6669 100644
--- a/src/pathops/SkPathOpsPoint.h
+++ b/src/pathops/SkPathOpsPoint.h
@@ -111,14 +111,8 @@ struct SkDPoint {
}
bool approximatelyEqual(const SkPoint& a) const {
- double denom = SkTMax(fabs(fX), SkTMax(fabs(fY),
- SkScalarToDouble(SkTMax(fabsf(a.fX), fabsf(a.fY)))));
- if (denom == 0) {
- return true;
- }
- double inv = 1 / denom;
- return approximately_equal_double(fX * inv, a.fX * inv)
- && approximately_equal_double(fY * inv, a.fY * inv);
+ return AlmostEqualUlps(SkDoubleToScalar(fX), a.fX)
+ && AlmostEqualUlps(SkDoubleToScalar(fY), a.fY);
}
bool approximatelyEqualHalf(const SkDPoint& a) const {
diff --git a/src/pathops/SkPathOpsTypes.cpp b/src/pathops/SkPathOpsTypes.cpp
index b071ca5371..999e1b215d 100644
--- a/src/pathops/SkPathOpsTypes.cpp
+++ b/src/pathops/SkPathOpsTypes.cpp
@@ -7,11 +7,11 @@
#include "SkFloatBits.h"
#include "SkPathOpsTypes.h"
-const int UlpsEpsilon = 16;
+
// from http://randomascii.wordpress.com/2012/02/25/comparing-floating-point-numbers-2012-edition/
// FIXME: move to SkFloatBits.h
-bool AlmostEqualUlps(float A, float B) {
+static bool equal_ulps(float A, float B, int epsilon) {
SkFloatIntUnion floatIntA, floatIntB;
floatIntA.fFloat = A;
floatIntB.fFloat = B;
@@ -23,7 +23,17 @@ bool AlmostEqualUlps(float A, float B) {
}
// Find the difference in ULPs.
int ulpsDiff = abs(floatIntA.fSignBitInt - floatIntB.fSignBitInt);
- return ulpsDiff <= UlpsEpsilon;
+ return ulpsDiff <= epsilon;
+}
+
+bool AlmostEqualUlps(float A, float B) {
+ const int UlpsEpsilon = 16;
+ return equal_ulps(A, B, UlpsEpsilon);
+}
+
+bool RoughlyEqualUlps(float A, float B) {
+ const int UlpsEpsilon = 256;
+ return equal_ulps(A, B, UlpsEpsilon);
}
// cube root approximation using bit hack for 64-bit float
diff --git a/src/pathops/SkPathOpsTypes.h b/src/pathops/SkPathOpsTypes.h
index 6ead79455c..20641d3345 100644
--- a/src/pathops/SkPathOpsTypes.h
+++ b/src/pathops/SkPathOpsTypes.h
@@ -28,6 +28,11 @@ inline bool AlmostEqualUlps(double A, double B) {
return AlmostEqualUlps(SkDoubleToScalar(A), SkDoubleToScalar(B));
}
+bool RoughlyEqualUlps(float A, float B);
+inline bool RoughlyEqualUlps(double A, double B) {
+ return RoughlyEqualUlps(SkDoubleToScalar(A), SkDoubleToScalar(B));
+}
+
// FLT_EPSILON == 1.19209290E-07 == 1 / (2 ^ 23)
// DBL_EPSILON == 2.22045e-16
const double FLT_EPSILON_CUBED = FLT_EPSILON * FLT_EPSILON * FLT_EPSILON;
diff --git a/src/pathops/SkReduceOrder.cpp b/src/pathops/SkReduceOrder.cpp
index ab85f3dd3e..3dfdc9daee 100644
--- a/src/pathops/SkReduceOrder.cpp
+++ b/src/pathops/SkReduceOrder.cpp
@@ -425,31 +425,27 @@ int SkReduceOrder::reduce(const SkDCubic& cubic, Quadratics allowQuadratics,
return 4;
}
-SkPath::Verb SkReduceOrder::Quad(const SkPoint a[3], SkTArray<SkPoint, true>* reducePts) {
+SkPath::Verb SkReduceOrder::Quad(const SkPoint a[3], SkPoint* reducePts) {
SkDQuad quad;
quad.set(a);
SkReduceOrder reducer;
int order = reducer.reduce(quad, kFill_Style);
if (order == 2) { // quad became line
for (int index = 0; index < order; ++index) {
- SkPoint& pt = reducePts->push_back();
- pt.fX = SkDoubleToScalar(reducer.fLine[index].fX);
- pt.fY = SkDoubleToScalar(reducer.fLine[index].fY);
+ *reducePts++ = reducer.fLine[index].asSkPoint();
}
}
return SkPathOpsPointsToVerb(order - 1);
}
-SkPath::Verb SkReduceOrder::Cubic(const SkPoint a[4], SkTArray<SkPoint, true>* reducePts) {
+SkPath::Verb SkReduceOrder::Cubic(const SkPoint a[4], SkPoint* reducePts) {
SkDCubic cubic;
cubic.set(a);
SkReduceOrder reducer;
int order = reducer.reduce(cubic, kAllow_Quadratics, kFill_Style);
if (order == 2 || order == 3) { // cubic became line or quad
for (int index = 0; index < order; ++index) {
- SkPoint& pt = reducePts->push_back();
- pt.fX = SkDoubleToScalar(reducer.fQuad[index].fX);
- pt.fY = SkDoubleToScalar(reducer.fQuad[index].fY);
+ *reducePts++ = reducer.fQuad[index].asSkPoint();
}
}
return SkPathOpsPointsToVerb(order - 1);
diff --git a/src/pathops/SkReduceOrder.h b/src/pathops/SkReduceOrder.h
index 82f8ffb143..c167951f8b 100644
--- a/src/pathops/SkReduceOrder.h
+++ b/src/pathops/SkReduceOrder.h
@@ -27,8 +27,8 @@ union SkReduceOrder {
int reduce(const SkDLine& line);
int reduce(const SkDQuad& quad, Style);
- static SkPath::Verb Cubic(const SkPoint pts[4], SkTArray<SkPoint, true>* reducePts);
- static SkPath::Verb Quad(const SkPoint pts[3], SkTArray<SkPoint, true>* reducePts);
+ static SkPath::Verb Cubic(const SkPoint pts[4], SkPoint* reducePts);
+ static SkPath::Verb Quad(const SkPoint pts[3], SkPoint* reducePts);
SkDLine fLine;
SkDQuad fQuad;
generated by cgit v1.2.3 (git 2.39.1) at 2024-11-27 17:16:54 +0000