aboutsummaryrefslogtreecommitdiffhomepage
path: root/src/pathops
diff options
context:
space:
mode:
Diffstat (limited to 'src/pathops')
-rw-r--r--src/pathops/SkDCubicIntersection.cpp23
-rw-r--r--src/pathops/SkDCubicLineIntersection.cpp110
-rw-r--r--src/pathops/SkDLineIntersection.cpp258
-rw-r--r--src/pathops/SkDQuadIntersection.cpp2
-rw-r--r--src/pathops/SkDQuadLineIntersection.cpp128
-rw-r--r--src/pathops/SkIntersections.cpp17
-rw-r--r--src/pathops/SkIntersections.h20
-rw-r--r--src/pathops/SkOpContour.h14
-rw-r--r--src/pathops/SkOpSegment.cpp82
-rw-r--r--src/pathops/SkOpSegment.h1
-rw-r--r--src/pathops/SkPathOpsCommon.cpp10
-rw-r--r--src/pathops/SkPathOpsCommon.h1
-rw-r--r--src/pathops/SkPathOpsDebug.h8
-rw-r--r--src/pathops/SkPathOpsLine.cpp91
-rw-r--r--src/pathops/SkPathOpsLine.h17
-rw-r--r--src/pathops/SkPathOpsOp.cpp1
-rw-r--r--src/pathops/SkPathOpsQuad.cpp1
-rw-r--r--src/pathops/SkPathOpsSimplify.cpp1
-rw-r--r--src/pathops/SkPathOpsTypes.cpp21
-rw-r--r--src/pathops/SkPathOpsTypes.h9
20 files changed, 555 insertions, 260 deletions
diff --git a/src/pathops/SkDCubicIntersection.cpp b/src/pathops/SkDCubicIntersection.cpp
index 511879cd70..6e049708ac 100644
--- a/src/pathops/SkDCubicIntersection.cpp
+++ b/src/pathops/SkDCubicIntersection.cpp
@@ -15,11 +15,12 @@
#include "SkTSort.h"
#if ONE_OFF_DEBUG
-static const double tLimits1[2][2] = {{0.36, 0.37}, {0.63, 0.64}};
+static const double tLimits1[2][2] = {{0.388600450, 0.388600452}, {0.245852802, 0.245852804}};
static const double tLimits2[2][2] = {{-0.865211397, -0.865215212}, {-0.865207696, -0.865208078}};
#endif
-#define DEBUG_QUAD_PART 0
+#define DEBUG_QUAD_PART ONE_OFF_DEBUG && 1
+#define DEBUG_QUAD_PART_SHOW_SIMPLE DEBUG_QUAD_PART && 0
#define SWAP_TOP_DEBUG 0
static const int kCubicToQuadSubdivisionDepth = 8; // slots reserved for cubic to quads subdivision
@@ -31,25 +32,27 @@ static int quadPart(const SkDCubic& cubic, double tStart, double tEnd, SkReduceO
// extremely shallow quadratic?
int order = reducer->reduce(quad, SkReduceOrder::kFill_Style);
#if DEBUG_QUAD_PART
- SkDebugf("%s cubic=(%1.17g,%1.17g %1.17g,%1.17g %1.17g,%1.17g %1.17g,%1.17g)"
- " t=(%1.17g,%1.17g)\n", __FUNCTION__, cubic[0].fX, cubic[0].fY,
+ SkDebugf("%s cubic=(%1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g)"
+ " t=(%1.9g,%1.9g)\n", __FUNCTION__, cubic[0].fX, cubic[0].fY,
cubic[1].fX, cubic[1].fY, cubic[2].fX, cubic[2].fY,
cubic[3].fX, cubic[3].fY, tStart, tEnd);
- SkDebugf("%s part=(%1.17g,%1.17g %1.17g,%1.17g %1.17g,%1.17g %1.17g,%1.17g)"
- " quad=(%1.17g,%1.17g %1.17g,%1.17g %1.17g,%1.17g)\n", __FUNCTION__,
+ SkDebugf(" {{%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}},\n"
+ " {{%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}},\n",
part[0].fX, part[0].fY, part[1].fX, part[1].fY, part[2].fX, part[2].fY,
part[3].fX, part[3].fY, quad[0].fX, quad[0].fY,
quad[1].fX, quad[1].fY, quad[2].fX, quad[2].fY);
- SkDebugf("%s simple=(%1.17g,%1.17g", __FUNCTION__, reducer->fQuad[0].fX, reducer->fQuad[0].fY);
+#if DEBUG_QUAD_PART_SHOW_SIMPLE
+ SkDebugf("%s simple=(%1.9g,%1.9g", __FUNCTION__, reducer->fQuad[0].fX, reducer->fQuad[0].fY);
if (order > 1) {
- SkDebugf(" %1.17g,%1.17g", reducer->fQuad[1].fX, reducer->fQuad[1].fY);
+ SkDebugf(" %1.9g,%1.9g", reducer->fQuad[1].fX, reducer->fQuad[1].fY);
}
if (order > 2) {
- SkDebugf(" %1.17g,%1.17g", reducer->fQuad[2].fX, reducer->fQuad[2].fY);
+ SkDebugf(" %1.9g,%1.9g", reducer->fQuad[2].fX, reducer->fQuad[2].fY);
}
SkDebugf(")\n");
SkASSERT(order < 4 && order > 0);
#endif
+#endif
return order;
}
@@ -240,7 +243,7 @@ static void intersect(const SkDCubic& cubic1, double t1s, double t1e, const SkDC
i.used(), i.used() > 0 ? i[0][i.used() - 1] : -1);
#endif
}
- intersect(cubic1, c1Min, c1Max, cubic2, c2Min, c2Max, offset, i);
+ // intersect(cubic1, c1Min, c1Max, cubic2, c2Min, c2Max, offset, i);
// FIXME: if no intersection is found, either quadratics intersected where
// cubics did not, or the intersection was missed. In the former case, expect
// the quadratics to be nearly parallel at the point of intersection, and check
diff --git a/src/pathops/SkDCubicLineIntersection.cpp b/src/pathops/SkDCubicLineIntersection.cpp
index f86a21ccc1..dc80479f60 100644
--- a/src/pathops/SkDCubicLineIntersection.cpp
+++ b/src/pathops/SkDCubicLineIntersection.cpp
@@ -80,7 +80,12 @@ public:
LineCubicIntersections(const SkDCubic& c, const SkDLine& l, SkIntersections& i)
: cubic(c)
, line(l)
- , intersections(i) {
+ , intersections(i)
+ , fAllowNear(true) {
+}
+
+void allowNear(bool allow) {
+ fAllowNear = allow;
}
// see parallel routine in line quadratic intersections
@@ -97,7 +102,7 @@ int intersectRay(double roots[3]) {
}
int intersect() {
- addEndPoints();
+ addExactEndPoints();
double rootVals[3];
int roots = intersectRay(rootVals);
for (int index = 0; index < roots; ++index) {
@@ -113,6 +118,9 @@ int intersect() {
intersections.insert(cubicT, lineT, pt);
}
}
+ if (fAllowNear) {
+ addNearEndPoints();
+ }
return intersections.used();
}
@@ -124,7 +132,7 @@ int horizontalIntersect(double axisIntercept, double roots[3]) {
}
int horizontalIntersect(double axisIntercept, double left, double right, bool flipped) {
- addHorizontalEndPoints(left, right, axisIntercept);
+ addExactHorizontalEndPoints(left, right, axisIntercept);
double rootVals[3];
int roots = horizontalIntersect(axisIntercept, rootVals);
for (int index = 0; index < roots; ++index) {
@@ -135,6 +143,9 @@ int horizontalIntersect(double axisIntercept, double left, double right, bool fl
intersections.insert(cubicT, lineT, pt);
}
}
+ if (fAllowNear) {
+ addNearHorizontalEndPoints(left, right, axisIntercept);
+ }
if (flipped) {
intersections.flip();
}
@@ -149,7 +160,7 @@ int verticalIntersect(double axisIntercept, double roots[3]) {
}
int verticalIntersect(double axisIntercept, double top, double bottom, bool flipped) {
- addVerticalEndPoints(top, bottom, axisIntercept);
+ addExactVerticalEndPoints(top, bottom, axisIntercept);
double rootVals[3];
int roots = verticalIntersect(axisIntercept, rootVals);
for (int index = 0; index < roots; ++index) {
@@ -160,6 +171,9 @@ int verticalIntersect(double axisIntercept, double top, double bottom, bool flip
intersections.insert(cubicT, lineT, pt);
}
}
+ if (fAllowNear) {
+ addNearVerticalEndPoints(top, bottom, axisIntercept);
+ }
if (flipped) {
intersections.flip();
}
@@ -168,65 +182,81 @@ int verticalIntersect(double axisIntercept, double top, double bottom, bool flip
protected:
-void addEndPoints() {
+void addExactEndPoints() {
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) {
+ double lineT = line.exactPoint(cubic[cIndex]);
+ if (lineT < 0) {
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?
+ double cubicT = (double) (cIndex >> 1);
+ intersections.insert(cubicT, lineT, cubic[cIndex]);
+ }
+}
+
+void addNearEndPoints() {
+ for (int cIndex = 0; cIndex < 4; cIndex += 3) {
+ double cubicT = (double) (cIndex >> 1);
+ if (intersections.hasT(cubicT)) {
continue;
}
- double lineT = findLineT(cIndex >> 1);
- if (!between(0, lineT, 1)) {
+ double lineT = line.nearPoint(cubic[cIndex]);
+ if (lineT < 0) {
continue;
}
- SkDPoint linePt = line.xyAtT(lineT);
- if (linePt.approximatelyEqual(cubic[cIndex])) {
- intersections.insert(cIndex >> 1, lineT, cubic[cIndex]);
- }
+ intersections.insert(cubicT, lineT, cubic[cIndex]);
}
}
-void addHorizontalEndPoints(double left, double right, double y) {
+void addExactHorizontalEndPoints(double left, double right, double y) {
for (int cIndex = 0; cIndex < 4; cIndex += 3) {
- if (cubic[cIndex].fY != y) {
+ double lineT = SkDLine::ExactPointH(cubic[cIndex], left, right, y);
+ if (lineT < 0) {
continue;
}
- if (cubic[cIndex].fX == left) {
- intersections.insert(cIndex >> 1, 0, cubic[cIndex]);
+ double cubicT = (double) (cIndex >> 1);
+ intersections.insert(cubicT, lineT, cubic[cIndex]);
+ }
+}
+
+void addNearHorizontalEndPoints(double left, double right, double y) {
+ for (int cIndex = 0; cIndex < 4; cIndex += 3) {
+ double cubicT = (double) (cIndex >> 1);
+ if (intersections.hasT(cubicT)) {
+ continue;
}
- if (cubic[cIndex].fX == right) {
- intersections.insert(cIndex >> 1, 1, cubic[cIndex]);
+ double lineT = SkDLine::NearPointH(cubic[cIndex], left, right, y);
+ if (lineT < 0) {
+ continue;
}
+ intersections.insert(cubicT, lineT, cubic[cIndex]);
}
+ // FIXME: see if line end is nearly on cubic
}
-void addVerticalEndPoints(double top, double bottom, double x) {
+void addExactVerticalEndPoints(double top, double bottom, double x) {
for (int cIndex = 0; cIndex < 4; cIndex += 3) {
- if (cubic[cIndex].fX != x) {
+ double lineT = SkDLine::ExactPointV(cubic[cIndex], top, bottom, x);
+ if (lineT < 0) {
continue;
}
- if (cubic[cIndex].fY == top) {
- intersections.insert(cIndex >> 1, 0, cubic[cIndex]);
+ double cubicT = (double) (cIndex >> 1);
+ intersections.insert(cubicT, lineT, cubic[cIndex]);
+ }
+}
+
+void addNearVerticalEndPoints(double top, double bottom, double x) {
+ for (int cIndex = 0; cIndex < 4; cIndex += 3) {
+ double cubicT = (double) (cIndex >> 1);
+ if (intersections.hasT(cubicT)) {
+ continue;
}
- if (cubic[cIndex].fY == bottom) {
- intersections.insert(cIndex >> 1, 1, cubic[cIndex]);
+ double lineT = SkDLine::NearPointV(cubic[cIndex], top, bottom, x);
+ if (lineT < 0) {
+ continue;
}
+ intersections.insert(cubicT, lineT, cubic[cIndex]);
}
+ // FIXME: see if line end is nearly on cubic
}
double findLineT(double t) {
@@ -264,6 +294,7 @@ private:
const SkDCubic& cubic;
const SkDLine& line;
SkIntersections& intersections;
+bool fAllowNear;
};
int SkIntersections::horizontal(const SkDCubic& cubic, double left, double right, double y,
@@ -280,6 +311,7 @@ int SkIntersections::vertical(const SkDCubic& cubic, double top, double bottom,
int SkIntersections::intersect(const SkDCubic& cubic, const SkDLine& line) {
LineCubicIntersections c(cubic, line, *this);
+ c.allowNear(fAllowNear);
return c.intersect();
}
diff --git a/src/pathops/SkDLineIntersection.cpp b/src/pathops/SkDLineIntersection.cpp
index 3b88b88702..faa7c1d392 100644
--- a/src/pathops/SkDLineIntersection.cpp
+++ b/src/pathops/SkDLineIntersection.cpp
@@ -75,47 +75,19 @@ int SkIntersections::intersectRay(const SkDLine& a, const SkDLine& b) {
return computePoints(a, used);
}
-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;
+ if ((t = b.exactPoint(a[iA])) >= 0) {
+ insert(iA, t, a[iA]);
}
- insert(iA, t, a[iA]);
}
for (int iB = 0; iB < 2; ++iB) {
- if (!checkEndPoint(b[iB].fX, b[iB].fY, a, &t, -1)) {
- continue;
+ if ((t = a.exactPoint(b[iB])) >= 0) {
+ insert(t, iB, b[iB]);
}
- 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
@@ -131,166 +103,198 @@ int SkIntersections::intersect(const SkDLine& a, const SkDLine& b) {
byLen * axLen - ayLen * bxLen == 0 ( == denom )
*/
double denom = byLen * axLen - ayLen * bxLen;
- double ab0y = a[0].fY - b[0].fY;
- double ab0x = a[0].fX - b[0].fX;
- double numerA = ab0y * bxLen - byLen * ab0x;
- double numerB = ab0y * axLen - ayLen * ab0x;
- bool mayNotOverlap = (numerA < 0 && denom > numerA) || (numerA > 0 && denom < numerA)
- || (numerB < 0 && denom > numerB) || (numerB > 0 && denom < numerB);
- numerA /= denom;
- numerB /= denom;
- if ((!approximately_zero(denom) || (!approximately_zero_inverse(numerA)
- && !approximately_zero_inverse(numerB))) && !sk_double_isnan(numerA)
- && !sk_double_isnan(numerB)) {
- if (mayNotOverlap) {
- return 0;
+ if (0 != denom) {
+ double ab0y = a[0].fY - b[0].fY;
+ double ab0x = a[0].fX - b[0].fX;
+ double numerA = ab0y * bxLen - byLen * ab0x;
+ double numerB = ab0y * axLen - ayLen * ab0x;
+ if (between(0, numerA, denom) && between(0, numerB, denom)) {
+ fT[0][0] = numerA / denom;
+ fT[1][0] = numerB / denom;
+ return computePoints(a, 1);
}
- fT[0][0] = numerA;
- fT[1][0] = numerB;
- fPt[0] = a.xyAtT(numerA);
- return computePoints(a, 1);
}
- return 0;
+ if (fAllowNear || 0 == denom) {
+ for (int iA = 0; iA < 2; ++iA) {
+ if ((t = b.nearPoint(a[iA])) >= 0) {
+ insert(iA, t, a[iA]);
+ }
+ }
+ for (int iB = 0; iB < 2; ++iB) {
+ if ((t = a.nearPoint(b[iB])) >= 0) {
+ insert(t, iB, b[iB]);
+ }
+ }
+ }
+ return fUsed;
}
-int SkIntersections::horizontal(const SkDLine& line, double y) {
+static int horizontal_coincident(const SkDLine& line, double y) {
double min = line[0].fY;
double max = line[1].fY;
if (min > max) {
SkTSwap(min, max);
}
if (min > y || max < y) {
- return fUsed = 0;
+ return 0;
}
if (AlmostEqualUlps(min, max) && max - min < fabs(line[0].fX - line[1].fX)) {
- fT[0][0] = 0;
- fT[0][1] = 1;
- return fUsed = 2;
+ return 2;
}
- fT[0][0] = (y - line[0].fY) / (line[1].fY - line[0].fY);
- return fUsed = 1;
+ return 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;
+static double horizontal_intercept(const SkDLine& line, double y) {
+ return (y - line[0].fY) / (line[1].fY - line[0].fY);
+}
+
+int SkIntersections::horizontal(const SkDLine& line, double y) {
+ int horizontalType = horizontal_coincident(line, y);
+ if (horizontalType == 1) {
+ fT[0][0] = horizontal_intercept(line, y);
+ } else if (horizontalType == 2) {
+ fT[0][0] = 0;
+ fT[0][1] = 1;
}
- double t = (end.fX - left) / (right - left);
- SkASSERT(between(0, t, 1));
- *tPtr = flipped ? 1 - t : t;
- return true;
+ return fUsed = horizontalType;
}
int SkIntersections::horizontal(const SkDLine& line, double left, double right,
double y, bool flipped) {
// see if end points intersect the opposite line
double t;
- if (checkEndPoint(left, y, line, &t, true)) {
- insert(t, flipped, left, y);
+ const SkDPoint leftPt = { left, y };
+ if ((t = line.exactPoint(leftPt)) >= 0) {
+ insert(t, (double) flipped, leftPt);
}
if (left != right) {
- if (checkEndPoint(right, y, line, &t, true)) {
- insert(t, !flipped, right, y);
+ const SkDPoint rightPt = { right, y };
+ if ((t = line.exactPoint(rightPt)) >= 0) {
+ insert(t, (double) !flipped, rightPt);
}
for (int index = 0; index < 2; ++index) {
- if (!checkEndPointH(line[index], left, right, y, flipped, &t)) {
- continue;
+ if ((t = SkDLine::ExactPointH(line[index], left, right, y)) >= 0) {
+ insert((double) index, flipped ? 1 - t : t, line[index]);
}
- insert(index, t, line[index]);
}
}
- if (used() > 0) {
- SkASSERT(fUsed <= 2);
- return used(); // coincident lines are returned here
+ int result = horizontal_coincident(line, y);
+ if (result == 1 && fUsed == 0) {
+ fT[0][0] = horizontal_intercept(line, y);
+ double xIntercept = line[0].fX + fT[0][0] * (line[1].fX - line[0].fX);
+ if (between(left, xIntercept, right)) {
+ fT[1][0] = (xIntercept - left) / (right - left);
+ if (flipped) {
+ // 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];
+ }
+ }
+ return computePoints(line, result);
+ }
}
- int result = horizontal(line, y);
- if (!result) {
- return 0;
+ if (!fAllowNear && result != 2) {
+ return fUsed;
}
- 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;
+ if ((t = line.nearPoint(leftPt)) >= 0) {
+ insert(t, (double) flipped, leftPt);
}
- fT[1][0] = (xIntercept - left) / (right - left);
- if (flipped) {
- // 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];
+ if (left != right) {
+ const SkDPoint rightPt = { right, y };
+ if ((t = line.nearPoint(rightPt)) >= 0) {
+ insert(t, (double) !flipped, rightPt);
+ }
+ for (int index = 0; index < 2; ++index) {
+ if ((t = SkDLine::NearPointH(line[index], left, right, y)) >= 0) {
+ insert((double) index, flipped ? 1 - t : t, line[index]);
+ }
}
}
- return computePoints(line, result);
+ return fUsed;
}
-int SkIntersections::vertical(const SkDLine& line, double x) {
+static int vertical_coincident(const SkDLine& line, double x) {
double min = line[0].fX;
double max = line[1].fX;
if (min > max) {
SkTSwap(min, max);
}
if (!precisely_between(min, x, max)) {
- return fUsed = 0;
+ return 0;
}
if (AlmostEqualUlps(min, max)) {
- fT[0][0] = 0;
- fT[0][1] = 1;
- return fUsed = 2;
+ return 2;
}
- fT[0][0] = (x - line[0].fX) / (line[1].fX - line[0].fX);
- return fUsed = 1;
+ return 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;
+static double vertical_intercept(const SkDLine& line, double x) {
+ return (x - line[0].fX) / (line[1].fX - line[0].fX);
+}
+
+int SkIntersections::vertical(const SkDLine& line, double x) {
+ int verticalType = vertical_coincident(line, x);
+ if (verticalType == 1) {
+ fT[0][0] = vertical_intercept(line, x);
+ } else if (verticalType == 2) {
+ fT[0][0] = 0;
+ fT[0][1] = 1;
}
- double t = (end.fY - top) / (bottom - top);
- SkASSERT(between(0, t, 1));
- *tPtr = flipped ? 1 - t : t;
- return true;
+ return fUsed = verticalType;
}
int SkIntersections::vertical(const SkDLine& line, double top, double bottom,
- double x, bool flipped) {
+ 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);
+ SkDPoint topPt = { x, top };
+ if ((t = line.exactPoint(topPt)) >= 0) {
+ insert(t, (double) flipped, topPt);
}
if (top != bottom) {
- if (checkEndPoint(x, bottom,line, &t, false)) {
- insert(t, !flipped, x, bottom);
+ SkDPoint bottomPt = { x, bottom };
+ if ((t = line.exactPoint(bottomPt)) >= 0) {
+ insert(t, (double) !flipped, bottomPt);
}
for (int index = 0; index < 2; ++index) {
- if (!checkEndPointV(line[index], top, bottom, x, flipped, &t)) {
- continue;
+ if ((t = SkDLine::ExactPointV(line[index], top, bottom, x)) >= 0) {
+ insert((double) index, flipped ? 1 - t : t, line[index]);
}
- insert( index, t, line[index]);
}
}
- if (used() > 0) {
- SkASSERT(fUsed <= 2);
- return used(); // coincident lines are returned here
+ int result = vertical_coincident(line, x);
+ if (result == 1 && fUsed == 0) {
+ fT[0][0] = vertical_intercept(line, x);
+ double yIntercept = line[0].fY + fT[0][0] * (line[1].fY - line[0].fY);
+ if (between(top, yIntercept, bottom)) {
+ 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) {
+ fT[1][index] = 1 - fT[1][index];
+ }
+ }
+ return computePoints(line, result);
+ }
}
- int result = vertical(line, x);
- if (!result) {
- return 0;
+ if (!fAllowNear && result != 2) {
+ return fUsed;
}
- 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;
+ if ((t = line.nearPoint(topPt)) >= 0) {
+ insert(t, (double) flipped, topPt);
}
- 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) {
- fT[1][index] = 1 - fT[1][index];
+ if (top != bottom) {
+ SkDPoint bottomPt = { x, bottom };
+ if ((t = line.nearPoint(bottomPt)) >= 0) {
+ insert(t, (double) !flipped, bottomPt);
+ }
+ for (int index = 0; index < 2; ++index) {
+ if ((t = SkDLine::NearPointV(line[index], top, bottom, x)) >= 0) {
+ insert((double) index, flipped ? 1 - t : t, line[index]);
+ }
}
}
- return computePoints(line, result);
+ return fUsed;
}
// from http://www.bryceboe.com/wordpress/wp-content/uploads/2006/10/intersect.py
diff --git a/src/pathops/SkDQuadIntersection.cpp b/src/pathops/SkDQuadIntersection.cpp
index 54c8b4979b..124c7dab06 100644
--- a/src/pathops/SkDQuadIntersection.cpp
+++ b/src/pathops/SkDQuadIntersection.cpp
@@ -127,6 +127,7 @@ static bool add_intercept(const SkDQuad& q1, const SkDQuad& q2, double tMin, dou
line[0] -= dxdy;
line[1] += dxdy;
SkIntersections rootTs;
+ rootTs.allowNear(false);
int roots = rootTs.intersect(q1, line);
if (roots == 0) {
if (subDivide) {
@@ -154,6 +155,7 @@ static bool is_linear_inner(const SkDQuad& q1, double t1s, double t1e, const SkD
SkSTArray<kTestCount * 2, double, true> tsFound;
for (size_t index = 0; index < kTestCount; ++index) {
SkIntersections rootTs;
+ rootTs.allowNear(false);
int roots = rootTs.intersect(q2, *testLines[index]);
for (int idx2 = 0; idx2 < roots; ++idx2) {
double t = rootTs[0][idx2];
diff --git a/src/pathops/SkDQuadLineIntersection.cpp b/src/pathops/SkDQuadLineIntersection.cpp
index 98e38621e0..9df2dc248a 100644
--- a/src/pathops/SkDQuadLineIntersection.cpp
+++ b/src/pathops/SkDQuadLineIntersection.cpp
@@ -92,7 +92,12 @@ public:
LineQuadraticIntersections(const SkDQuad& q, const SkDLine& l, SkIntersections* i)
: quad(q)
, line(l)
- , intersections(i) {
+ , intersections(i)
+ , fAllowNear(true) {
+ }
+
+ void allowNear(bool allow) {
+ fAllowNear = allow;
}
int intersectRay(double roots[2]) {
@@ -126,7 +131,7 @@ public:
}
int intersect() {
- addEndPoints();
+ addExactEndPoints();
double rootVals[2];
int roots = intersectRay(rootVals);
for (int index = 0; index < roots; ++index) {
@@ -137,6 +142,9 @@ public:
intersections->insert(quadT, lineT, pt);
}
}
+ if (fAllowNear) {
+ addNearEndPoints();
+ }
return intersections->used();
}
@@ -151,7 +159,7 @@ public:
}
int horizontalIntersect(double axisIntercept, double left, double right, bool flipped) {
- addHorizontalEndPoints(left, right, axisIntercept);
+ addExactHorizontalEndPoints(left, right, axisIntercept);
double rootVals[2];
int roots = horizontalIntersect(axisIntercept, rootVals);
for (int index = 0; index < roots; ++index) {
@@ -162,6 +170,9 @@ public:
intersections->insert(quadT, lineT, pt);
}
}
+ if (fAllowNear) {
+ addNearHorizontalEndPoints(left, right, axisIntercept);
+ }
if (flipped) {
intersections->flip();
}
@@ -179,7 +190,7 @@ public:
}
int verticalIntersect(double axisIntercept, double top, double bottom, bool flipped) {
- addVerticalEndPoints(top, bottom, axisIntercept);
+ addExactVerticalEndPoints(top, bottom, axisIntercept);
double rootVals[2];
int roots = verticalIntersect(axisIntercept, rootVals);
for (int index = 0; index < roots; ++index) {
@@ -190,6 +201,9 @@ public:
intersections->insert(quadT, lineT, pt);
}
}
+ if (fAllowNear) {
+ addNearVerticalEndPoints(top, bottom, axisIntercept);
+ }
if (flipped) {
intersections->flip();
}
@@ -198,73 +212,88 @@ public:
protected:
// add endpoints first to get zero and one t values exactly
- void addEndPoints() {
+ void addExactEndPoints() {
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) {
+ double lineT = line.exactPoint(quad[qIndex]);
+ if (lineT < 0) {
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?
+ double quadT = (double) (qIndex >> 1);
+ intersections->insert(quadT, lineT, quad[qIndex]);
+ }
+ }
+
+ void addNearEndPoints() {
+ for (int qIndex = 0; qIndex < 3; qIndex += 2) {
+ double quadT = (double) (qIndex >> 1);
+ if (intersections->hasT(quadT)) {
continue;
}
- double lineT = findLineT(qIndex >> 1);
- if (!between(0, lineT, 1)) {
+ double lineT = line.nearPoint(quad[qIndex]);
+ if (lineT < 0) {
continue;
}
- SkDPoint linePt = line.xyAtT(lineT);
- if (linePt.approximatelyEqual(quad[qIndex])) {
- intersections->insert(qIndex >> 1, lineT, quad[qIndex]);
+ intersections->insert(quadT, lineT, quad[qIndex]);
+ }
+ // FIXME: see if line end is nearly on quad
+ }
+
+ void addExactHorizontalEndPoints(double left, double right, double y) {
+ for (int qIndex = 0; qIndex < 3; qIndex += 2) {
+ double lineT = SkDLine::ExactPointH(quad[qIndex], left, right, y);
+ if (lineT < 0) {
+ continue;
}
+ double quadT = (double) (qIndex >> 1);
+ intersections->insert(quadT, lineT, quad[qIndex]);
}
}
- void addHorizontalEndPoints(double left, double right, double y) {
+ void addNearHorizontalEndPoints(double left, double right, double y) {
for (int qIndex = 0; qIndex < 3; qIndex += 2) {
- if (!AlmostEqualUlps(quad[qIndex].fY, y)) {
+ double quadT = (double) (qIndex >> 1);
+ if (intersections->hasT(quadT)) {
continue;
}
- double x = quad[qIndex].fX;
- if (between(left, x, right)) {
- double t = (x - left) / (right - left);
- intersections->insert(qIndex >> 1, t, quad[qIndex]);
+ double lineT = SkDLine::NearPointH(quad[qIndex], left, right, y);
+ if (lineT < 0) {
+ continue;
}
+ intersections->insert(quadT, lineT, quad[qIndex]);
}
+ // FIXME: see if line end is nearly on quad
}
- void addVerticalEndPoints(double top, double bottom, double x) {
+ void addExactVerticalEndPoints(double top, double bottom, double x) {
for (int qIndex = 0; qIndex < 3; qIndex += 2) {
- if (!AlmostEqualUlps(quad[qIndex].fX, x)) {
+ double lineT = SkDLine::ExactPointV(quad[qIndex], top, bottom, x);
+ if (lineT < 0) {
continue;
}
- double y = quad[qIndex].fY;
- if (between(top, y, bottom)) {
- double t = (y - top) / (bottom - top);
- intersections->insert(qIndex >> 1, t, quad[qIndex]);
+ double quadT = (double) (qIndex >> 1);
+ intersections->insert(quadT, lineT, quad[qIndex]);
+ }
+ }
+
+ void addNearVerticalEndPoints(double top, double bottom, double x) {
+ for (int qIndex = 0; qIndex < 3; qIndex += 2) {
+ double quadT = (double) (qIndex >> 1);
+ if (intersections->hasT(quadT)) {
+ continue;
+ }
+ double lineT = SkDLine::NearPointV(quad[qIndex], top, bottom, x);
+ if (lineT < 0) {
+ continue;
}
+ intersections->insert(quadT, lineT, quad[qIndex]);
}
+ // FIXME: see if line end is nearly on quad
}
double findLineT(double t) {
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)) {
@@ -274,7 +303,6 @@ protected:
return dxT;
}
return fabs(dx) > fabs(dy) ? dxT : dyT;
-#endif
}
static bool PinTs(double* quadT, double* lineT) {
@@ -284,16 +312,8 @@ protected:
if (!approximately_zero_or_more(*lineT)) {
return false;
}
- if (precisely_less_than_zero(*quadT)) {
- *quadT = 0;
- } else if (precisely_greater_than_one(*quadT)) {
- *quadT = 1;
- }
- if (precisely_less_than_zero(*lineT)) {
- *lineT = 0;
- } else if (precisely_greater_than_one(*lineT)) {
- *lineT = 1;
- }
+ *quadT = SkPinT(*quadT);
+ *lineT = SkPinT(*lineT);
return true;
}
@@ -301,6 +321,7 @@ private:
const SkDQuad& quad;
const SkDLine& line;
SkIntersections* intersections;
+ bool fAllowNear;
};
// utility for pairs of coincident quads
@@ -355,6 +376,7 @@ int SkIntersections::vertical(const SkDQuad& quad, double top, double bottom, do
int SkIntersections::intersect(const SkDQuad& quad, const SkDLine& line) {
LineQuadraticIntersections q(quad, line, this);
+ q.allowNear(fAllowNear);
return q.intersect();
}
diff --git a/src/pathops/SkIntersections.cpp b/src/pathops/SkIntersections.cpp
index af6cc080ef..fe23316683 100644
--- a/src/pathops/SkIntersections.cpp
+++ b/src/pathops/SkIntersections.cpp
@@ -156,7 +156,7 @@ void SkIntersections::insertCoincidentPair(double s1, double e1, double s2, doub
insertCoincident(e1, e2, endPt);
}
-int SkIntersections::insert(double one, double two, double x, double y) {
+int SkIntersections::insert(double one, double two, const SkDPoint& pt) {
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;
@@ -166,15 +166,17 @@ int SkIntersections::insert(double one, double two, double x, double y) {
for (index = 0; index < fUsed; ++index) {
double oldOne = fT[0][index];
double oldTwo = fT[1][index];
- if (roughly_equal(oldOne, one) && roughly_equal(oldTwo, two)) {
+ if (one == oldOne && two == oldTwo) {
+ return -1;
+ }
+ if (more_roughly_equal(oldOne, one) && more_roughly_equal(oldTwo, two)) {
if ((precisely_zero(one) && !precisely_zero(oldOne))
|| (precisely_equal(one, 1) && !precisely_equal(oldOne, 1))
|| (precisely_zero(two) && !precisely_zero(oldTwo))
|| (precisely_equal(two, 1) && !precisely_equal(oldTwo, 1))) {
fT[0][index] = one;
fT[1][index] = two;
- fPt[index].fX = x;
- fPt[index].fY = y;
+ fPt[index] = pt;
}
return -1;
}
@@ -196,18 +198,13 @@ int SkIntersections::insert(double one, double two, double x, double y) {
fIsCoincident[0] += fIsCoincident[0] & ~((1 << index) - 1);
fIsCoincident[1] += fIsCoincident[1] & ~((1 << index) - 1);
}
- fPt[index].fX = x;
- fPt[index].fY = y;
+ fPt[index] = pt;
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;
diff --git a/src/pathops/SkIntersections.h b/src/pathops/SkIntersections.h
index c0bb61fef0..de3d44cd70 100644
--- a/src/pathops/SkIntersections.h
+++ b/src/pathops/SkIntersections.h
@@ -45,6 +45,10 @@ public:
SkDEBUGCODE(fDepth = i.fDepth);
}
+ void allowNear(bool nearAllowed) {
+ fAllowNear = nearAllowed;
+ }
+
int cubic(const SkPoint a[4]) {
SkDCubic cubic;
cubic.set(a);
@@ -88,6 +92,11 @@ public:
return intersect(cubic, quad);
}
+ bool hasT(double t) const {
+ SkASSERT(t == 0 || t == 1);
+ return fUsed > 0 && (t == 0 ? fT[0][0] == 0 : fT[0][fUsed - 1] == 1);
+ }
+
int insertSwap(double one, double two, const SkDPoint& pt) {
if (fSwap) {
return insert(two, one, pt);
@@ -96,14 +105,6 @@ 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;
}
@@ -166,6 +167,7 @@ public:
// leaves flip, swap alone
void reset() {
+ fAllowNear = true;
fUsed = 0;
}
@@ -204,7 +206,6 @@ 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,
@@ -248,6 +249,7 @@ private:
double fT[2][9];
uint16_t fIsCoincident[2]; // bit arrays, one bit set for each coincident T
unsigned char fUsed;
+ bool fAllowNear;
bool fSwap;
#ifdef SK_DEBUG
int fDepth;
diff --git a/src/pathops/SkOpContour.h b/src/pathops/SkOpContour.h
index 84f0eb10dd..456e6c0068 100644
--- a/src/pathops/SkOpContour.h
+++ b/src/pathops/SkOpContour.h
@@ -90,6 +90,20 @@ public:
void calcCoincidentWinding();
+ void checkEnds() {
+ if (!fContainsCurves) {
+ return;
+ }
+ int segmentCount = fSegments.count();
+ for (int sIndex = 0; sIndex < segmentCount; ++sIndex) {
+ SkOpSegment* segment = &fSegments[sIndex];
+ if (segment->verb() == SkPath::kLine_Verb) {
+ continue;
+ }
+ fSegments[sIndex].checkEnds();
+ }
+ }
+
void complete() {
setBounds();
fContainsIntercepts = false;
diff --git a/src/pathops/SkOpSegment.cpp b/src/pathops/SkOpSegment.cpp
index 8bd4cc275a..5b20749957 100644
--- a/src/pathops/SkOpSegment.cpp
+++ b/src/pathops/SkOpSegment.cpp
@@ -209,7 +209,7 @@ bool SkOpSegment::activeWinding(int index, int endIndex, int* maxWinding, int* s
void SkOpSegment::addAngle(SkTArray<SkOpAngle, true>* anglesPtr, int start, int end) const {
SkASSERT(start != end);
SkOpAngle& angle = anglesPtr->push_back();
-#if DEBUG_ANGLE
+#if 0 && DEBUG_ANGLE // computed pt and actual pt may differ by more than approx eq
SkTArray<SkOpAngle, true>& angles = *anglesPtr;
if (angles.count() > 1) {
const SkOpSegment* aSeg = angles[0].segment();
@@ -1080,6 +1080,86 @@ bool SkOpSegment::bumpSpan(SkOpSpan* span, int windDelta, int oppDelta) {
return false;
}
+// look to see if the curve end intersects an intermediary that intersects the other
+void SkOpSegment::checkEnds() {
+#if 1
+ return; // FIXME: suspect we will need the code below to make intersections consistent
+#else
+ SkTDArray<SkOpSpan> missingSpans;
+ int count = fTs.count();
+ for (int index = 0; index < count; ++index) {
+ const SkOpSpan& span = fTs[index];
+ const SkOpSegment* other = span.fOther;
+ const SkOpSpan* otherSpan = &other->fTs[span.fOtherIndex];
+ double otherT = otherSpan->fT;
+ if (otherT != 0 && otherT != 1) {
+ continue;
+ }
+ int peekStart = span.fOtherIndex;
+ while (peekStart > 0) {
+ const SkOpSpan* peeker = &other->fTs[peekStart - 1];
+ if (peeker->fT != otherT) {
+ break;
+ }
+ --peekStart;
+ }
+ int otherLast = other->fTs.count() - 1;
+ int peekLast = span.fOtherIndex;
+ while (peekLast < otherLast) {
+ const SkOpSpan* peeker = &other->fTs[peekLast + 1];
+ if (peeker->fT != otherT) {
+ break;
+ }
+ ++peekLast;
+ }
+ if (peekStart == peekLast) {
+ continue;
+ }
+ double t = span.fT;
+ int tStart = index;
+ while (tStart > 0 && t == fTs[tStart - 1].fT) {
+ --tStart;
+ }
+ int tLast = index;
+ int last = count - 1;
+ while (tLast < last && t == fTs[tLast + 1].fT) {
+ ++tLast;
+ }
+ for (int peekIndex = peekStart; peekIndex <= peekLast; ++peekIndex) {
+ if (peekIndex == span.fOtherIndex) {
+ continue;
+ }
+ const SkOpSpan& peekSpan = other->fTs[peekIndex];
+ SkOpSegment* match = peekSpan.fOther;
+ const double matchT = peekSpan.fOtherT;
+ for (int tIndex = tStart; tIndex <= tLast; ++tIndex) {
+ const SkOpSpan& tSpan = fTs[tIndex];
+ if (tSpan.fOther == match && tSpan.fOtherT == matchT) {
+ goto nextPeeker;
+ }
+ }
+ // this segment is missing a entry that the other contains
+ // remember so we can add the missing one and recompute the indices
+ SkOpSpan* missing = missingSpans.append();
+ missing->fT = t;
+ missing->fOther = match;
+ missing->fOtherT = matchT;
+ missing->fPt = peekSpan.fPt;
+ }
+nextPeeker:
+ ;
+ }
+ int missingCount = missingSpans.count();
+ for (int index = 0; index < missingCount; ++index) {
+ const SkOpSpan& missing = missingSpans[index];
+ addTPair(missing.fT, missing.fOther, missing.fOtherT, false, missing.fPt);
+ }
+ if (missingCount > 0) {
+ fixOtherTIndex();
+ }
+#endif
+}
+
bool SkOpSegment::equalPoints(int greaterTIndex, int lesserTIndex) {
SkASSERT(greaterTIndex >= lesserTIndex);
double greaterT = fTs[greaterTIndex].fT;
diff --git a/src/pathops/SkOpSegment.h b/src/pathops/SkOpSegment.h
index 3cbd29e77e..7e5e644f1d 100644
--- a/src/pathops/SkOpSegment.h
+++ b/src/pathops/SkOpSegment.h
@@ -254,6 +254,7 @@ public:
const SkPoint& oPt);
int addUnsortableT(SkOpSegment* other, bool start, const SkPoint& pt, double newT);
bool betweenTs(int lesser, double testT, int greater) const;
+ void checkEnds();
int computeSum(int startIndex, int endIndex, bool binary);
int crossedSpanY(const SkPoint& basePt, SkScalar* bestY, double* hitT, bool* hitSomething,
double mid, bool opp, bool current) const;
diff --git a/src/pathops/SkPathOpsCommon.cpp b/src/pathops/SkPathOpsCommon.cpp
index 5a30c3a98e..9a92b00acd 100644
--- a/src/pathops/SkPathOpsCommon.cpp
+++ b/src/pathops/SkPathOpsCommon.cpp
@@ -344,6 +344,16 @@ SkOpSegment* FindSortableTop(const SkTArray<SkOpContour*, true>& contourList, bo
return current;
}
+void CheckEnds(SkTArray<SkOpContour*, true>* contourList) {
+ // it's hard to determine if the end of a cubic or conic nearly intersects another curve.
+ // instead, look to see if the connecting curve intersected at that same end.
+ int contourCount = (*contourList).count();
+ for (int cTest = 0; cTest < contourCount; ++cTest) {
+ SkOpContour* contour = (*contourList)[cTest];
+ contour->checkEnds();
+ }
+}
+
void FixOtherTIndex(SkTArray<SkOpContour*, true>* contourList) {
int contourCount = (*contourList).count();
for (int cTest = 0; cTest < contourCount; ++cTest) {
diff --git a/src/pathops/SkPathOpsCommon.h b/src/pathops/SkPathOpsCommon.h
index 569edb7e32..4ba4af2300 100644
--- a/src/pathops/SkPathOpsCommon.h
+++ b/src/pathops/SkPathOpsCommon.h
@@ -13,6 +13,7 @@
class SkPathWriter;
void Assemble(const SkPathWriter& path, SkPathWriter* simple);
+void CheckEnds(SkTArray<SkOpContour*, true>* contourList);
// FIXME: find chase uses insert, so it can't be converted to SkTArray yet
SkOpSegment* FindChase(SkTDArray<SkOpSpan*>& chase, int& tIndex, int& endIndex);
SkOpSegment* FindSortableTop(const SkTArray<SkOpContour*, true>& contourList, bool* firstContour,
diff --git a/src/pathops/SkPathOpsDebug.h b/src/pathops/SkPathOpsDebug.h
index 5484147c3a..05fe241e0f 100644
--- a/src/pathops/SkPathOpsDebug.h
+++ b/src/pathops/SkPathOpsDebug.h
@@ -103,10 +103,10 @@ extern int gDebugMaxWindValue;
DEBUG_SORT_SINGLE | DEBUG_PATH_CONSTRUCTION)
#if DEBUG_AS_C_CODE
-#define CUBIC_DEBUG_STR "{{%1.17g,%1.17g}, {%1.17g,%1.17g}, {%1.17g,%1.17g}, {%1.17g,%1.17g}}"
-#define QUAD_DEBUG_STR "{{%1.17g,%1.17g}, {%1.17g,%1.17g}, {%1.17g,%1.17g}}"
-#define LINE_DEBUG_STR "{{%1.17g,%1.17g}, {%1.17g,%1.17g}}"
-#define PT_DEBUG_STR "{{%1.17g,%1.17g}}"
+#define CUBIC_DEBUG_STR "{{%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}}"
+#define QUAD_DEBUG_STR "{{%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}}"
+#define LINE_DEBUG_STR "{{%1.9g,%1.9g}, {%1.9g,%1.9g}}"
+#define PT_DEBUG_STR "{{%1.9g,%1.9g}}"
#else
#define CUBIC_DEBUG_STR "(%1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g)"
#define QUAD_DEBUG_STR "(%1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g)"
diff --git a/src/pathops/SkPathOpsLine.cpp b/src/pathops/SkPathOpsLine.cpp
index b7c91c991d..47c0565b69 100644
--- a/src/pathops/SkPathOpsLine.cpp
+++ b/src/pathops/SkPathOpsLine.cpp
@@ -41,8 +41,99 @@ double SkDLine::isLeft(const SkDPoint& pt) const {
return p0.cross(p2);
}
+// OPTIMIZE: assert if t is 0 or 1 (caller shouldn't pass only 0/1)
SkDPoint SkDLine::xyAtT(double t) const {
double one_t = 1 - t;
SkDPoint result = { one_t * fPts[0].fX + t * fPts[1].fX, one_t * fPts[0].fY + t * fPts[1].fY };
return result;
}
+
+double SkDLine::exactPoint(const SkDPoint& xy) const {
+ if (xy == fPts[0]) { // do cheapest test first
+ return 0;
+ }
+ if (xy == fPts[1]) {
+ return 1;
+ }
+ return -1;
+}
+
+double SkDLine::nearPoint(const SkDPoint& xy) const {
+ if (!AlmostBetweenUlps(fPts[0].fX, xy.fX, fPts[1].fX)
+ || !AlmostBetweenUlps(fPts[0].fY, xy.fY, fPts[1].fY)) {
+ return -1;
+ }
+ // project a perpendicular ray from the point to the line; find the T on the line
+ SkDVector len = fPts[1] - fPts[0]; // the x/y magnitudes of the line
+ double denom = len.fX * len.fX + len.fY * len.fY; // see DLine intersectRay
+ SkDVector ab0 = xy - fPts[0];
+ double numer = len.fX * ab0.fX + ab0.fY * len.fY;
+ if (!between(0, numer, denom)) {
+ return -1;
+ }
+ double t = numer / denom;
+ SkDPoint realPt = xyAtT(t);
+ SkDVector distU = xy - realPt;
+ double distSq = distU.fX * distU.fX + distU.fY * distU.fY;
+ double dist = sqrt(distSq); // OPTIMIZATION: can we compare against distSq instead ?
+ // find the ordinal in the original line with the largest unsigned exponent
+ double tiniest = SkTMin(SkTMin(SkTMin(fPts[0].fX, fPts[0].fY), fPts[1].fX), fPts[1].fY);
+ double largest = SkTMax(SkTMax(SkTMax(fPts[0].fX, fPts[0].fY), fPts[1].fX), fPts[1].fY);
+ largest = SkTMax(largest, -tiniest);
+ if (!AlmostEqualUlps(largest, largest + dist)) { // is the dist within ULPS tolerance?
+ return -1;
+ }
+ t = SkPinT(t);
+ SkASSERT(between(0, t, 1));
+ return t;
+}
+
+double SkDLine::ExactPointH(const SkDPoint& xy, double left, double right, double y) {
+ if (xy.fY == y) {
+ if (xy.fX == left) {
+ return 0;
+ }
+ if (xy.fX == right) {
+ return 1;
+ }
+ }
+ return -1;
+}
+
+double SkDLine::NearPointH(const SkDPoint& xy, double left, double right, double y) {
+ if (!AlmostEqualUlps(xy.fY, y)) {
+ return -1;
+ }
+ if (!AlmostBetweenUlps(left, xy.fX, right)) {
+ return -1;
+ }
+ double t = (xy.fX - left) / (right - left);
+ t = SkPinT(t);
+ SkASSERT(between(0, t, 1));
+ return t;
+}
+
+double SkDLine::ExactPointV(const SkDPoint& xy, double top, double bottom, double x) {
+ if (xy.fX == x) {
+ if (xy.fY == top) {
+ return 0;
+ }
+ if (xy.fY == bottom) {
+ return 1;
+ }
+ }
+ return -1;
+}
+
+double SkDLine::NearPointV(const SkDPoint& xy, double top, double bottom, double x) {
+ if (!AlmostEqualUlps(xy.fX, x)) {
+ return -1;
+ }
+ if (!AlmostBetweenUlps(top, xy.fY, bottom)) {
+ return -1;
+ }
+ double t = (xy.fY - top) / (bottom - top);
+ t = SkPinT(t);
+ SkASSERT(between(0, t, 1));
+ return t;
+}
diff --git a/src/pathops/SkPathOpsLine.h b/src/pathops/SkPathOpsLine.h
index 34bb6587d3..c5ac7fdb09 100644
--- a/src/pathops/SkPathOpsLine.h
+++ b/src/pathops/SkPathOpsLine.h
@@ -12,21 +12,28 @@
struct SkDLine {
SkDPoint fPts[2];
+ const SkDPoint& operator[](int n) const { SkASSERT(n >= 0 && n < 2); return fPts[n]; }
+ SkDPoint& operator[](int n) { SkASSERT(n >= 0 && n < 2); return fPts[n]; }
+
void set(const SkPoint pts[2]) {
fPts[0] = pts[0];
fPts[1] = pts[1];
}
- const SkDPoint& operator[](int n) const { SkASSERT(n >= 0 && n < 2); return fPts[n]; }
- SkDPoint& operator[](int n) { SkASSERT(n >= 0 && n < 2); return fPts[n]; }
-
- double isLeft(const SkDPoint& pt) const;
- SkDLine subDivide(double t1, double t2) const;
static SkDLine SubDivide(const SkPoint a[2], double t1, double t2) {
SkDLine line;
line.set(a);
return line.subDivide(t1, t2);
}
+
+ double exactPoint(const SkDPoint& xy) const;
+ static double ExactPointH(const SkDPoint& xy, double left, double right, double y);
+ static double ExactPointV(const SkDPoint& xy, double top, double bottom, double x);
+ double isLeft(const SkDPoint& pt) const;
+ double nearPoint(const SkDPoint& xy) const;
+ static double NearPointH(const SkDPoint& xy, double left, double right, double y);
+ static double NearPointV(const SkDPoint& xy, double top, double bottom, double x);
+ SkDLine subDivide(double t1, double t2) const;
SkDPoint xyAtT(double t) const;
private:
SkDVector tangent() const { return fPts[0] - fPts[1]; }
diff --git a/src/pathops/SkPathOpsOp.cpp b/src/pathops/SkPathOpsOp.cpp
index 0df4859cdf..71efeeea8c 100644
--- a/src/pathops/SkPathOpsOp.cpp
+++ b/src/pathops/SkPathOpsOp.cpp
@@ -299,6 +299,7 @@ bool Op(const SkPath& one, const SkPath& two, SkPathOp op, SkPath* result) {
SkOpContour::debugShowWindingValues(contourList);
#endif
FixOtherTIndex(&contourList);
+ CheckEnds(&contourList);
SortSegments(&contourList);
#if DEBUG_ACTIVE_SPANS || DEBUG_ACTIVE_SPANS_FIRST_ONLY
DebugShowActiveSpans(contourList);
diff --git a/src/pathops/SkPathOpsQuad.cpp b/src/pathops/SkPathOpsQuad.cpp
index 3cbc28abf4..636e3854fd 100644
--- a/src/pathops/SkPathOpsQuad.cpp
+++ b/src/pathops/SkPathOpsQuad.cpp
@@ -164,6 +164,7 @@ SkDVector SkDQuad::dxdyAtT(double t) const {
return result;
}
+// OPTIMIZE: assert if caller passes in t == 0 / t == 1 ?
SkDPoint SkDQuad::xyAtT(double t) const {
double one_t = 1 - t;
double a = one_t * one_t;
diff --git a/src/pathops/SkPathOpsSimplify.cpp b/src/pathops/SkPathOpsSimplify.cpp
index fd40c38503..488778904f 100644
--- a/src/pathops/SkPathOpsSimplify.cpp
+++ b/src/pathops/SkPathOpsSimplify.cpp
@@ -185,6 +185,7 @@ bool Simplify(const SkPath& path, SkPath* result) {
// eat through coincident edges
CoincidenceCheck(&contourList, 0);
FixOtherTIndex(&contourList);
+ CheckEnds(&contourList);
SortSegments(&contourList);
#if DEBUG_ACTIVE_SPANS || DEBUG_ACTIVE_SPANS_FIRST_ONLY
DebugShowActiveSpans(contourList);
diff --git a/src/pathops/SkPathOpsTypes.cpp b/src/pathops/SkPathOpsTypes.cpp
index 999e1b215d..a076d155f2 100644
--- a/src/pathops/SkPathOpsTypes.cpp
+++ b/src/pathops/SkPathOpsTypes.cpp
@@ -16,8 +16,7 @@ static bool equal_ulps(float A, float B, int epsilon) {
floatIntA.fFloat = A;
floatIntB.fFloat = B;
// Different signs means they do not match.
- if ((floatIntA.fSignBitInt < 0) != (floatIntB.fSignBitInt < 0))
- {
+ if ((floatIntA.fSignBitInt < 0) != (floatIntB.fSignBitInt < 0)) {
// Check for equality to make sure +0 == -0
return A == B;
}
@@ -26,6 +25,18 @@ static bool equal_ulps(float A, float B, int epsilon) {
return ulpsDiff <= epsilon;
}
+static bool less_ulps(float A, float B, int epsilon) {
+ SkFloatIntUnion floatIntA, floatIntB;
+ floatIntA.fFloat = A;
+ floatIntB.fFloat = B;
+ // Check different signs with float epsilon since we only care if they're both close to 0.
+ if ((floatIntA.fSignBitInt < 0) != (floatIntB.fSignBitInt < 0)) {
+ return A <= B + FLT_EPSILON * epsilon;
+ }
+ // Find the difference in ULPs.
+ return floatIntA.fSignBitInt <= floatIntB.fSignBitInt + epsilon;
+}
+
bool AlmostEqualUlps(float A, float B) {
const int UlpsEpsilon = 16;
return equal_ulps(A, B, UlpsEpsilon);
@@ -36,6 +47,12 @@ bool RoughlyEqualUlps(float A, float B) {
return equal_ulps(A, B, UlpsEpsilon);
}
+bool AlmostBetweenUlps(float a, float b, float c) {
+ const int UlpsEpsilon = 1;
+ return a <= c ? less_ulps(a, b, UlpsEpsilon) && less_ulps(b, c, UlpsEpsilon)
+ : less_ulps(b, a, UlpsEpsilon) && less_ulps(c, b, UlpsEpsilon);
+}
+
// cube root approximation using bit hack for 64-bit float
// adapted from Kahan's cbrt
static double cbrt_5d(double d) {
diff --git a/src/pathops/SkPathOpsTypes.h b/src/pathops/SkPathOpsTypes.h
index 20641d3345..c988691e26 100644
--- a/src/pathops/SkPathOpsTypes.h
+++ b/src/pathops/SkPathOpsTypes.h
@@ -33,6 +33,11 @@ inline bool RoughlyEqualUlps(double A, double B) {
return RoughlyEqualUlps(SkDoubleToScalar(A), SkDoubleToScalar(B));
}
+bool AlmostBetweenUlps(float a, float b, float c);
+inline bool AlmostBetweenUlps(double A, double B, double C) {
+ return AlmostBetweenUlps(SkDoubleToScalar(A), SkDoubleToScalar(B), SkDoubleToScalar(C));
+}
+
// FLT_EPSILON == 1.19209290E-07 == 1 / (2 ^ 23)
// DBL_EPSILON == 2.22045e-16
const double FLT_EPSILON_CUBED = FLT_EPSILON * FLT_EPSILON * FLT_EPSILON;
@@ -260,4 +265,8 @@ inline int SkDSideBit(double x) {
return 1 << SKDSide(x);
}
+inline double SkPinT(double t) {
+ return precisely_less_than_zero(t) ? 0 : precisely_greater_than_one(t) ? 1 : t;
+}
+
#endif
generated by cgit v1.2.3 (git 2.39.1) at 2024-07-02 03:35:42 +0000