path ops near exact
Modify line intersections to first
- match exact ends
- compute intersections
- match near ends
where the exact ends are preferred, then near matches, then
computed matches. This pulls matches towards existing end points
when possible, and keeps intersection distances consistent with
different line/line line/quad and line/cubic computations.
BUG=
Review URL: https://codereview.chromium.org/19183003
git-svn-id: http://skia.googlecode.com/svn/trunk@10073 2bbb7eff-a529-9590-31e7-b0007b416f81
diff --git a/src/pathops/SkDCubicIntersection.cpp b/src/pathops/SkDCubicIntersection.cpp
index 511879c..6e04970 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 @@
// 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 @@
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 f86a21c..dc80479 100644
--- a/src/pathops/SkDCubicLineIntersection.cpp
+++ b/src/pathops/SkDCubicLineIntersection.cpp
@@ -80,7 +80,12 @@
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 intersect() {
- addEndPoints();
+ addExactEndPoints();
double rootVals[3];
int roots = intersectRay(rootVals);
for (int index = 0; index < roots; ++index) {
@@ -113,6 +118,9 @@
intersections.insert(cubicT, lineT, pt);
}
}
+ if (fAllowNear) {
+ addNearEndPoints();
+ }
return intersections.used();
}
@@ -124,7 +132,7 @@
}
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 @@
intersections.insert(cubicT, lineT, pt);
}
}
+ if (fAllowNear) {
+ addNearHorizontalEndPoints(left, right, axisIntercept);
+ }
if (flipped) {
intersections.flip();
}
@@ -149,7 +160,7 @@
}
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 @@
intersections.insert(cubicT, lineT, pt);
}
}
+ if (fAllowNear) {
+ addNearVerticalEndPoints(top, bottom, axisIntercept);
+ }
if (flipped) {
intersections.flip();
}
@@ -168,67 +182,83 @@
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?
- 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]);
- }
+ double cubicT = (double) (cIndex >> 1);
+ intersections.insert(cubicT, lineT, cubic[cIndex]);
}
}
-void addHorizontalEndPoints(double left, double right, double y) {
+void addNearEndPoints() {
for (int cIndex = 0; cIndex < 4; cIndex += 3) {
- if (cubic[cIndex].fY != y) {
+ double cubicT = (double) (cIndex >> 1);
+ if (intersections.hasT(cubicT)) {
continue;
}
- if (cubic[cIndex].fX == left) {
- intersections.insert(cIndex >> 1, 0, cubic[cIndex]);
+ double lineT = line.nearPoint(cubic[cIndex]);
+ if (lineT < 0) {
+ continue;
}
- if (cubic[cIndex].fX == right) {
- intersections.insert(cIndex >> 1, 1, cubic[cIndex]);
- }
+ intersections.insert(cubicT, lineT, cubic[cIndex]);
}
}
-void addVerticalEndPoints(double top, double bottom, double x) {
+void addExactHorizontalEndPoints(double left, double right, double y) {
for (int cIndex = 0; cIndex < 4; cIndex += 3) {
- if (cubic[cIndex].fX != x) {
+ double lineT = SkDLine::ExactPointH(cubic[cIndex], left, right, y);
+ if (lineT < 0) {
continue;
}
- if (cubic[cIndex].fY == top) {
- intersections.insert(cIndex >> 1, 0, cubic[cIndex]);
- }
- if (cubic[cIndex].fY == bottom) {
- intersections.insert(cIndex >> 1, 1, 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;
+ }
+ 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 addExactVerticalEndPoints(double top, double bottom, double x) {
+ for (int cIndex = 0; cIndex < 4; cIndex += 3) {
+ double lineT = SkDLine::ExactPointV(cubic[cIndex], top, bottom, x);
+ if (lineT < 0) {
+ continue;
+ }
+ 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;
+ }
+ 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) {
SkDPoint xy = cubic.xyAtT(t);
double dx = line[1].fX - line[0].fX;
@@ -264,6 +294,7 @@
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::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 3b88b88..faa7c1d 100644
--- a/src/pathops/SkDLineIntersection.cpp
+++ b/src/pathops/SkDLineIntersection.cpp
@@ -75,47 +75,19 @@
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 @@
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(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
- for (int index = 0; index < result; ++index) {
- fT[1][index] = 1 - fT[1][index];
+ 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);
}
}
- return computePoints(line, result);
+ if (!fAllowNear && result != 2) {
+ return fUsed;
+ }
+ if ((t = line.nearPoint(leftPt)) >= 0) {
+ insert(t, (double) flipped, leftPt);
+ }
+ 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 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(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) {
- fT[1][index] = 1 - fT[1][index];
+ 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);
}
}
- return computePoints(line, result);
+ if (!fAllowNear && result != 2) {
+ return fUsed;
+ }
+ if ((t = line.nearPoint(topPt)) >= 0) {
+ insert(t, (double) flipped, topPt);
+ }
+ 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 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 54c8b49..124c7da 100644
--- a/src/pathops/SkDQuadIntersection.cpp
+++ b/src/pathops/SkDQuadIntersection.cpp
@@ -127,6 +127,7 @@
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 @@
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 98e3862..9df2dc2 100644
--- a/src/pathops/SkDQuadLineIntersection.cpp
+++ b/src/pathops/SkDQuadLineIntersection.cpp
@@ -92,7 +92,12 @@
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 @@
}
int intersect() {
- addEndPoints();
+ addExactEndPoints();
double rootVals[2];
int roots = intersectRay(rootVals);
for (int index = 0; index < roots; ++index) {
@@ -137,6 +142,9 @@
intersections->insert(quadT, lineT, pt);
}
}
+ if (fAllowNear) {
+ addNearEndPoints();
+ }
return intersections->used();
}
@@ -151,7 +159,7 @@
}
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 @@
intersections->insert(quadT, lineT, pt);
}
}
+ if (fAllowNear) {
+ addNearHorizontalEndPoints(left, right, axisIntercept);
+ }
if (flipped) {
intersections->flip();
}
@@ -179,7 +190,7 @@
}
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 @@
intersections->insert(quadT, lineT, pt);
}
}
+ if (fAllowNear) {
+ addNearVerticalEndPoints(top, bottom, axisIntercept);
+ }
if (flipped) {
intersections->flip();
}
@@ -198,73 +212,88 @@
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?
- 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]);
- }
+ double quadT = (double) (qIndex >> 1);
+ intersections->insert(quadT, lineT, quad[qIndex]);
}
}
- void addHorizontalEndPoints(double left, double right, double y) {
+ void addNearEndPoints() {
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 = line.nearPoint(quad[qIndex]);
+ if (lineT < 0) {
+ continue;
}
+ 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 addVerticalEndPoints(double top, double bottom, double x) {
+ void addNearHorizontalEndPoints(double left, double right, double y) {
for (int qIndex = 0; qIndex < 3; qIndex += 2) {
- if (!AlmostEqualUlps(quad[qIndex].fX, x)) {
+ double quadT = (double) (qIndex >> 1);
+ if (intersections->hasT(quadT)) {
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 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 addExactVerticalEndPoints(double top, double bottom, double x) {
+ for (int qIndex = 0; qIndex < 3; qIndex += 2) {
+ double lineT = SkDLine::ExactPointV(quad[qIndex], top, bottom, x);
+ if (lineT < 0) {
+ continue;
+ }
+ 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 @@
return dxT;
}
return fabs(dx) > fabs(dy) ? dxT : dyT;
-#endif
}
static bool PinTs(double* quadT, double* lineT) {
@@ -284,16 +312,8 @@
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 @@
const SkDQuad& quad;
const SkDLine& line;
SkIntersections* intersections;
+ bool fAllowNear;
};
// utility for pairs of coincident quads
@@ -355,6 +376,7 @@
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 af6cc08..fe23316 100644
--- a/src/pathops/SkIntersections.cpp
+++ b/src/pathops/SkIntersections.cpp
@@ -156,7 +156,7 @@
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 @@
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 @@
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 c0bb61f..de3d44c 100644
--- a/src/pathops/SkIntersections.h
+++ b/src/pathops/SkIntersections.h
@@ -45,6 +45,10 @@
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 @@
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 @@
}
}
- 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 @@
// leaves flip, swap alone
void reset() {
+ fAllowNear = true;
fUsed = 0;
}
@@ -204,7 +206,6 @@
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 @@
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 84f0eb1..456e6c0 100644
--- a/src/pathops/SkOpContour.h
+++ b/src/pathops/SkOpContour.h
@@ -90,6 +90,20 @@
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 8bd4cc2..5b20749 100644
--- a/src/pathops/SkOpSegment.cpp
+++ b/src/pathops/SkOpSegment.cpp
@@ -209,7 +209,7 @@
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 @@
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 3cbd29e..7e5e644 100644
--- a/src/pathops/SkOpSegment.h
+++ b/src/pathops/SkOpSegment.h
@@ -254,6 +254,7 @@
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 5a30c3a..9a92b00 100644
--- a/src/pathops/SkPathOpsCommon.cpp
+++ b/src/pathops/SkPathOpsCommon.cpp
@@ -344,6 +344,16 @@
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 569edb7..4ba4af2 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 5484147..05fe241 100644
--- a/src/pathops/SkPathOpsDebug.h
+++ b/src/pathops/SkPathOpsDebug.h
@@ -103,10 +103,10 @@
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 b7c91c9..47c0565 100644
--- a/src/pathops/SkPathOpsLine.cpp
+++ b/src/pathops/SkPathOpsLine.cpp
@@ -41,8 +41,99 @@
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 34bb658..c5ac7fd 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 0df4859..71efeee 100644
--- a/src/pathops/SkPathOpsOp.cpp
+++ b/src/pathops/SkPathOpsOp.cpp
@@ -299,6 +299,7 @@
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 3cbc28a..636e385 100644
--- a/src/pathops/SkPathOpsQuad.cpp
+++ b/src/pathops/SkPathOpsQuad.cpp
@@ -164,6 +164,7 @@
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 fd40c38..4887789 100644
--- a/src/pathops/SkPathOpsSimplify.cpp
+++ b/src/pathops/SkPathOpsSimplify.cpp
@@ -185,6 +185,7 @@
// 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 999e1b2..a076d15 100644
--- a/src/pathops/SkPathOpsTypes.cpp
+++ b/src/pathops/SkPathOpsTypes.cpp
@@ -16,8 +16,7 @@
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 @@
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 @@
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 20641d3..c988691 100644
--- a/src/pathops/SkPathOpsTypes.h
+++ b/src/pathops/SkPathOpsTypes.h
@@ -33,6 +33,11 @@
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 @@
return 1 << SKDSide(x);
}
+inline double SkPinT(double t) {
+ return precisely_less_than_zero(t) ? 0 : precisely_greater_than_one(t) ? 1 : t;
+}
+
#endif
diff --git a/tests/PathOpsCubicIntersectionTest.cpp b/tests/PathOpsCubicIntersectionTest.cpp
index e00ba16..db8e575 100644
--- a/tests/PathOpsCubicIntersectionTest.cpp
+++ b/tests/PathOpsCubicIntersectionTest.cpp
@@ -163,6 +163,39 @@
const size_t testSetCount = SK_ARRAY_COUNT(testSet);
static const SkDCubic newTestSet[] = {
+{{{1.0516976506771041, 2.9684399028541346 },
+ {1.0604363140895228, 2.9633503074444141 },
+ {1.0692548215065762, 2.9580354426587459 },
+ {1.0781560339512140, 2.9525043684031349 }}},
+
+{{{1.0523038101345104, 2.9523755204833737 },
+ {1.0607035288264237, 2.9580853881628375 },
+ {1.0690530472271964, 2.9633896794787749 },
+ {1.0773566568712512, 2.9682969775000219 }}},
+
+{{{1.0386522625066592, 2.9759024812329078 },
+ {1.0559713690392631, 2.9661782500838885 },
+ {1.0736041309019990, 2.9555348259177858 },
+ {1.0915734362784633, 2.9440446879826569 }}},
+
+{{{1.0396670794879301, 2.9435062123457261 },
+ {1.0565690546812769, 2.9557413250983462 },
+ {1.0732616463413533, 2.9663369676594282 },
+ {1.0897791867435489, 2.9753618045797472 }}},
+
+{{{0.8685656183311091, 3.0409266475785208 },
+ {0.99189542936395292, 3.0212163698184424 },
+ {1.1302108367493320, 2.9265646471747306 },
+ {1.2952305904872474, 2.7940808546473788 }}},
+
+{{{0.85437872843682727, 2.7536036928549055 },
+ {1.0045584590592620, 2.9493041024831705 },
+ {1.1336998329885613, 3.0248027987251747 },
+ {1.2593809752247314, 3.0152560315809107 }}},
+
+{{{0, 1}, {1, 6}, {1, 0}, {6, 2}}},
+{{{0, 1}, {2, 6}, {1, 0}, {6, 1}}},
+
{{{134,11414}, {131.990234375,11414}, {130.32666015625,11415.482421875}, {130.04275512695312,11417.4130859375}}},
{{{132,11419}, {130.89543151855469,11419}, {130,11418.1044921875}, {130,11417}}},
@@ -297,11 +330,6 @@
oneOff(reporter, cubic1, cubic2);
}
-static void oneOffTest(skiatest::Reporter* reporter) {
- newOneOff(reporter, 0, 1);
- oneOff(reporter, 14, 16);
-}
-
static void oneOffTests(skiatest::Reporter* reporter) {
for (size_t outer = 0; outer < testSetCount - 1; ++outer) {
for (size_t inner = outer + 1; inner < testSetCount; ++inner) {
@@ -515,8 +543,11 @@
}
}
+static void PathOpsCubicIntersectionOneOffTest(skiatest::Reporter* reporter) {
+ newOneOff(reporter, 6, 7);
+}
+
static void PathOpsCubicIntersectionTest(skiatest::Reporter* reporter) {
- oneOffTest(reporter);
oneOffTests(reporter);
cubicIntersectionSelfTest(reporter);
standardTestCases(reporter);
@@ -526,3 +557,5 @@
#include "TestClassDef.h"
DEFINE_TESTCLASS_SHORT(PathOpsCubicIntersectionTest)
+
+DEFINE_TESTCLASS_SHORT(PathOpsCubicIntersectionOneOffTest)
diff --git a/tests/PathOpsCubicLineIntersectionTest.cpp b/tests/PathOpsCubicLineIntersectionTest.cpp
index 29c04ae..245f8a6 100644
--- a/tests/PathOpsCubicLineIntersectionTest.cpp
+++ b/tests/PathOpsCubicLineIntersectionTest.cpp
@@ -14,6 +14,10 @@
SkDCubic cubic;
SkDLine line;
} lineCubicTests[] = {
+#if 0
+ {{{{258, 122}, {260.761414, 122}, { 263, 124.238579}, {263, 127}}},
+ {{{259.82843, 125.17157}, {261.535522, 123.46447}}}},
+#endif
{{{{1006.6951293945312,291}, {1023.263671875,291}, {1033.8402099609375,304.43145751953125},
{1030.318359375,321}}},
{{{979.30487060546875,561}, {1036.695068359375,291}}}},
@@ -67,7 +71,7 @@
}
}
-static void PathOpsCubicLineIntersectionTestOne(skiatest::Reporter* reporter) {
+static void PathOpsCubicLineIntersectionOneOffTest(skiatest::Reporter* reporter) {
int iIndex = 0;
testOne(reporter, iIndex);
const SkDCubic& cubic = lineCubicTests[iIndex].cubic;
@@ -95,4 +99,4 @@
#include "TestClassDef.h"
DEFINE_TESTCLASS_SHORT(PathOpsCubicLineIntersectionTest)
-DEFINE_TESTCLASS_SHORT(PathOpsCubicLineIntersectionTestOne)
+DEFINE_TESTCLASS_SHORT(PathOpsCubicLineIntersectionOneOffTest)
diff --git a/tests/PathOpsExtendedTest.cpp b/tests/PathOpsExtendedTest.cpp
index 7a7dcb3..93280d7 100644
--- a/tests/PathOpsExtendedTest.cpp
+++ b/tests/PathOpsExtendedTest.cpp
@@ -52,24 +52,54 @@
"kInverseEvenOdd_FillType"
};
+static void output_scalar(SkScalar num) {
+ if (num == (int) num) {
+ SkDebugf("%d", (int) num);
+ } else {
+ SkString str;
+ str.printf("%1.9g", num);
+ int width = str.size();
+ const char* cStr = str.c_str();
+ while (cStr[width - 1] == '0') {
+ --width;
+ }
+ str.resize(width);
+ SkDebugf("%sf", str.c_str());
+ }
+}
+
+static void output_points(const SkPoint* pts, int count) {
+ for (int index = 0; index < count; ++index) {
+ output_scalar(pts[index].fX);
+ SkDebugf(", ");
+ output_scalar(pts[index].fY);
+ if (index + 1 < count) {
+ SkDebugf(", ");
+ }
+ }
+ SkDebugf(");\n");
+}
+
static void showPathContours(SkPath::RawIter& 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);
+ SkDebugf(" %s.moveTo(", pathName);
+ output_points(&pts[0], 1);
continue;
case SkPath::kLine_Verb:
- SkDebugf(" %s.lineTo(%#1.9gf, %#1.9gf);\n", pathName, pts[1].fX, pts[1].fY);
+ SkDebugf(" %s.lineTo(", pathName);
+ output_points(&pts[1], 1);
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);
+ SkDebugf(" %s.quadTo(", pathName);
+ output_points(&pts[1], 2);
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);
+ SkDebugf(" %s.cubicTo(", pathName);
+ output_points(&pts[1], 3);
break;
case SkPath::kClose_Verb:
SkDebugf(" %s.close();\n", pathName);
@@ -116,24 +146,40 @@
SkPath::RawIter iter(path);
uint8_t verb;
SkPoint pts[4];
+ SkPoint firstPt, lastPt;
+ bool firstPtSet = false;
+ bool lastPtSet = true;
while ((verb = iter.next(pts)) != SkPath::kDone_Verb) {
switch (verb) {
case SkPath::kMove_Verb:
+ firstPt = pts[0];
+ firstPtSet = true;
continue;
case SkPath::kLine_Verb:
SkDebugf("{{%1.9g,%1.9g}, {%1.9g,%1.9g}},\n", pts[0].fX, pts[0].fY,
pts[1].fX, pts[1].fY);
+ lastPt = pts[1];
+ lastPtSet = true;
break;
case SkPath::kQuad_Verb:
SkDebugf("{{%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}},\n",
pts[0].fX, pts[0].fY, pts[1].fX, pts[1].fY, pts[2].fX, pts[2].fY);
+ lastPt = pts[2];
+ lastPtSet = true;
break;
case SkPath::kCubic_Verb:
SkDebugf("{{%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}},\n",
pts[0].fX, pts[0].fY, pts[1].fX, pts[1].fY, pts[2].fX, pts[2].fY,
pts[3].fX, pts[3].fY);
+ lastPt = pts[3];
+ lastPtSet = true;
break;
case SkPath::kClose_Verb:
+ if (firstPtSet && lastPtSet && firstPt != lastPt) {
+ SkDebugf("{{%1.9g,%1.9g}, {%1.9g,%1.9g}},\n", lastPt.fX, lastPt.fY,
+ firstPt.fX, firstPt.fY);
+ }
+ firstPtSet = lastPtSet = false;
break;
default:
SkDEBUGFAIL("bad verb");
@@ -521,6 +567,7 @@
const SkPathOp shapeOp, const char* testName) {
#if DEBUG_SHOW_TEST_NAME
if (testName == NULL) {
+ SkDebugf("\n");
showPathData(a);
showOp(shapeOp);
showPathData(b);
diff --git a/tests/PathOpsLineParametetersTest.cpp b/tests/PathOpsLineParametetersTest.cpp
index 3b223ae..c8f8be7 100644
--- a/tests/PathOpsLineParametetersTest.cpp
+++ b/tests/PathOpsLineParametetersTest.cpp
@@ -68,7 +68,7 @@
if (AlmostEqualUlps(fabs(normalizedDistance[inner]), answers[index][inner])) {
continue;
}
- SkDebugf("%s [%d,%d] normalizedDistance:%1.10g != answer:%g\n",
+ SkDebugf("%s [%d,%d] normalizedDistance:%1.9g != answer:%g\n",
__FUNCTION__, static_cast<int>(index), (int)inner,
normalizedDistance[inner], answers[index][inner]);
REPORTER_ASSERT(reporter, 0);
diff --git a/tests/PathOpsOpCubicThreadedTest.cpp b/tests/PathOpsOpCubicThreadedTest.cpp
index 3448ee9..0ccb89d 100644
--- a/tests/PathOpsOpCubicThreadedTest.cpp
+++ b/tests/PathOpsOpCubicThreadedTest.cpp
@@ -9,6 +9,9 @@
static void testOpCubicsMain(PathOpsThreadState* data)
{
+#if DEBUG_SHOW_TEST_NAME
+ strncpy(DEBUG_FILENAME_STRING, "", DEBUG_FILENAME_STRING_LENGTH);
+#endif
SkASSERT(data);
PathOpsThreadState& state = *data;
char pathStr[1024]; // gdb: set print elements 400
diff --git a/tests/PathOpsOpTest.cpp b/tests/PathOpsOpTest.cpp
index e06bc8f..098b386 100644
--- a/tests/PathOpsOpTest.cpp
+++ b/tests/PathOpsOpTest.cpp
@@ -1733,9 +1733,116 @@
#endif
}
+static void skpahrefs_com88(skiatest::Reporter* reporter) {
+ SkPath path;
+ path.setFillType(SkPath::kEvenOdd_FillType);
+ path.moveTo(1099.82886f, 7.17117119f);
+ path.lineTo(1099.12134f, 7.87867832f);
+ path.cubicTo(1099.66418f, 8.42157173f, 1100.00000f, 9.17157173f, 1100.00000f, 10.0000000f);
+ path.lineTo(1100.00000f, 28.0000000f);
+ path.cubicTo(1100.00000f, 29.6568546f, 1098.65686f, 31.0000000f, 1097.00000f, 31.0000000f);
+ path.lineTo(1088.00000f, 31.0000000f);
+ path.lineTo(1088.00000f, 32.0000000f);
+ path.lineTo(1097.00000f, 32.0000000f);
+ path.quadTo(1098.65686f, 32.0000000f, 1099.82886f, 30.8288002f);
+ path.quadTo(1101.00000f, 29.6568546f, 1101.00000f, 28.0000000f);
+ path.lineTo(1101.00000f, 10.0000000f);
+ path.quadTo(1101.00000f, 8.34314537f, 1099.82886f, 7.17119980f);
+ path.lineTo(1099.82886f, 7.17117119f);
+ path.close();
+ SkPath pathB;
+ pathB.setFillType(SkPath::kWinding_FillType);
+ pathB.moveTo(1101.00000f, 6.00000000f);
+ pathB.lineTo(1088.00000f, 6.00000000f);
+ pathB.lineTo(1088.00000f, 19.0000000f);
+ pathB.lineTo(1101.00000f, 32.0000000f);
+ testPathOp(reporter, path, pathB, kIntersect_PathOp);
+}
+
+static void skpahrefs_com29(skiatest::Reporter* reporter) {
+ SkPath path;
+ path.setFillType(SkPath::kEvenOdd_FillType);
+ path.moveTo(1037.17114f, 7.17119980f);
+ path.quadTo(1038.34314f, 6.00000000f, 1040.00000f, 6.00000000f);
+ path.lineTo(1074.00000f, 6.00000000f);
+ path.lineTo(1074.00000f, 32.0000000f);
+ path.lineTo(1040.00000f, 32.0000000f);
+ path.quadTo(1038.34314f, 32.0000000f, 1037.17114f, 30.8288002f);
+ path.quadTo(1036.00000f, 29.6568546f, 1036.00000f, 28.0000000f);
+ path.lineTo(1036.00000f, 10.0000000f);
+ path.quadTo(1036.00000f, 8.34314537f, 1037.17114f, 7.17119980f);
+ path.close();
+ path.moveTo(1037.00000f, 10.0000000f);
+ path.cubicTo(1037.00000f, 8.34314537f, 1038.34314f, 7.00000000f, 1040.00000f, 7.00000000f);
+ path.lineTo(1073.00000f, 7.00000000f);
+ path.lineTo(1073.00000f, 31.0000000f);
+ path.lineTo(1040.00000f, 31.0000000f);
+ path.cubicTo(1038.34314f, 31.0000000f, 1037.00000f, 29.6568546f, 1037.00000f, 28.0000000f);
+ path.lineTo(1037.00000f, 10.0000000f);
+ path.close();
+ SkPath pathB;
+ pathB.setFillType(SkPath::kWinding_FillType);
+ pathB.moveTo(1036.00000f, 32.0000000f);
+ pathB.lineTo(1049.00000f, 19.0000000f);
+ pathB.lineTo(1073.00000f, 31.0000000f);
+ pathB.lineTo(1074.00000f, 32.0000000f);
+ testPathOp(reporter, path, pathB, kIntersect_PathOp);
+}
+
+static void cubicOp85d(skiatest::Reporter* reporter) {
+ SkPath path;
+ path.setFillType(SkPath::kWinding_FillType);
+ path.moveTo(0,1);
+ path.cubicTo(1,6, 1,0, 6,2);
+ path.close();
+ SkPath pathB;
+ pathB.setFillType(SkPath::kWinding_FillType);
+ pathB.moveTo(0,1);
+ pathB.cubicTo(2,6, 1,0, 6,1);
+ pathB.close();
+ testPathOp(reporter, path, pathB, kDifference_PathOp);
+}
+
+#if 0 // FIXME
+// this fails because the pair of nearly coincident cubics intersect at the ends
+// but the line connected to one of the cubics at the same point does not intersect
+// the other
+static void skpkkiste_to98(skiatest::Reporter* reporter) {
+ SkPath path;
+ path.setFillType(SkPath::kEvenOdd_FillType);
+ path.moveTo(96, 122);
+ path.cubicTo(94.6192932f, 122, 93.3692932f, 122.559647f, 92.4644699f, 123.46447f);
+ path.lineTo(94.1715698f, 125.17157f);
+ path.cubicTo(94.8954315f, 124.447708f, 95.8954315f, 124, 97, 124);
+ path.lineTo(257, 124);
+ path.cubicTo(258.104553f, 124, 259.104584f, 124.447708f, 259.82843f, 125.17157f);
+ path.lineTo(261.535522f, 123.46447f);
+ path.cubicTo(260.630707f, 122.559647f, 259.380707f, 122, 258, 122);
+ path.lineTo(96, 122);
+ path.close();
+ SkPath pathB;
+ pathB.setFillType(SkPath::kWinding_FillType);
+ pathB.moveTo(258, 122);
+ pathB.cubicTo(260.761414f, 122, 263, 124.238579f, 263, 127);
+ pathB.lineTo(263, 284);
+ pathB.cubicTo(263, 286.761414f, 260.761414f, 289, 258, 289);
+ pathB.lineTo(96, 289);
+ pathB.cubicTo(93.2385788f, 289, 91, 286.761414f, 91, 284);
+ pathB.lineTo(91, 127);
+ pathB.cubicTo(91, 124.238579f, 93.2385788f, 122, 96, 122);
+ pathB.lineTo(258, 122);
+ pathB.close();
+ testPathOp(reporter, path, pathB, kIntersect_PathOp);
+}
+#endif
+
static void (*firstTest)(skiatest::Reporter* ) = 0;
static struct TestDesc tests[] = {
+// TEST(skpkkiste_to98),
+ TEST(skpahrefs_com29),
+ TEST(cubicOp85d),
+ TEST(skpahrefs_com88),
TEST(skphealth_com76),
TEST(skpancestry_com1),
TEST(skpbyte_com1),
diff --git a/tests/PathOpsQuadIntersectionTest.cpp b/tests/PathOpsQuadIntersectionTest.cpp
index 4bb0b34..c454b4d 100644
--- a/tests/PathOpsQuadIntersectionTest.cpp
+++ b/tests/PathOpsQuadIntersectionTest.cpp
@@ -50,6 +50,9 @@
}
static const SkDQuad testSet[] = {
+ {{{0.647069409,2.97691634}, {0.946860918,3.17625612}, {1.46875407,2.65105457}}},
+ {{{0,1}, {0.723699095,2.82756208}, {1.08907197,2.97497449}}},
+
{{{131.37418,11414.9825}, {130.28798,11415.9328}, {130.042755,11417.4131}}},
{{{130.585787,11418.4142}, {130.021447,11417.8498}, {130,11417}}},
@@ -264,7 +267,7 @@
}
}
-static void QuadraticIntersection_OneOffTest(skiatest::Reporter* reporter) {
+static void PathOpsQuadIntersectionOneOffTest(skiatest::Reporter* reporter) {
oneOffTest1(reporter, 0, 1);
}
@@ -471,10 +474,10 @@
standardTestCases(reporter);
if (false) QuadraticIntersection_IntersectionFinder();
if (false) QuadraticIntersection_PointFinder();
- if (false) QuadraticIntersection_OneOffTest(reporter);
}
#include "TestClassDef.h"
DEFINE_TESTCLASS_SHORT(PathOpsQuadIntersectionTest)
-DEFINE_TESTCLASS_SHORT(QuadraticIntersection_OneOffTest)
+
+DEFINE_TESTCLASS_SHORT(PathOpsQuadIntersectionOneOffTest)
diff --git a/tests/PathOpsQuadLineIntersectionTest.cpp b/tests/PathOpsQuadLineIntersectionTest.cpp
index 1615340..4227ee5 100644
--- a/tests/PathOpsQuadLineIntersectionTest.cpp
+++ b/tests/PathOpsQuadLineIntersectionTest.cpp
@@ -58,11 +58,13 @@
SkDQuad quad;
SkDLine line;
} oneOffs[] = {
+ {{{{1101, 10}, {1101, 8.3431453704833984}, {1099.828857421875, 7.1711997985839844}}},
+ {{{1099.828857421875,7.1711711883544922}, {1099.121337890625,7.8786783218383789}}}},
{{{{973, 507}, {973, 508.24264526367187}, {972.12158203125, 509.12161254882812}}},
{{{930, 467}, {973, 510}}}},
{{{{369.848602, 145.680267}, {382.360413, 121.298294}, {406.207703, 121.298294}}},
- {{{406.207703, 121.298294}, {348.781738, 123.864815}}}}
- };
+ {{{406.207703, 121.298294}, {348.781738, 123.864815}}}},
+};
static size_t oneOffs_count = SK_ARRAY_COUNT(oneOffs);
@@ -83,8 +85,11 @@
}
}
-static void PathOpsQuadLineIntersectionTest(skiatest::Reporter* reporter) {
+static void PathOpsQuadLineIntersectionTestOne(skiatest::Reporter* reporter) {
testOneOffs(reporter);
+}
+
+static void PathOpsQuadLineIntersectionTest(skiatest::Reporter* reporter) {
for (size_t index = 0; index < lineQuadTests_count; ++index) {
int iIndex = static_cast<int>(index);
const SkDQuad& quad = lineQuadTests[index].quad;
@@ -131,3 +136,5 @@
#include "TestClassDef.h"
DEFINE_TESTCLASS_SHORT(PathOpsQuadLineIntersectionTest)
+
+DEFINE_TESTCLASS_SHORT(PathOpsQuadLineIntersectionTestOne)
diff --git a/tests/PathOpsSkpClipTest.cpp b/tests/PathOpsSkpClipTest.cpp
index f46ad97..f9d33e1 100644
--- a/tests/PathOpsSkpClipTest.cpp
+++ b/tests/PathOpsSkpClipTest.cpp
@@ -88,7 +88,7 @@
SkDELETE(pic);
}
-const char skipBefore[] = "http___health_com.skp";
+const char skipBefore[] = "http___kkiste_to.skp";
static void PathOpsSkpClipTest(skiatest::Reporter* reporter) {
SkOSFile::Iter iter(pictDir, "skp");
@@ -138,7 +138,7 @@
testRunner.render();
}
-static void PathOpsSkpClipTestOne(skiatest::Reporter* reporter) {
+static void PathOpsSkpClipOneOffTest(skiatest::Reporter* reporter) {
SkString filename(skipBefore);
testOne(filename);
}
@@ -146,6 +146,6 @@
#include "TestClassDef.h"
DEFINE_TESTCLASS_SHORT(PathOpsSkpClipTest)
-DEFINE_TESTCLASS_SHORT(PathOpsSkpClipTestOne)
+DEFINE_TESTCLASS_SHORT(PathOpsSkpClipOneOffTest)
DEFINE_TESTCLASS_SHORT(PathOpsSkpClipThreadedTest)