shape ops work in progress
this fixes quad/line intersection
git-svn-id: http://skia.googlecode.com/svn/trunk@5277 2bbb7eff-a529-9590-31e7-b0007b416f81
diff --git a/experimental/Intersection/CurveIntersection.h b/experimental/Intersection/CurveIntersection.h
index db227cf..7008516 100644
--- a/experimental/Intersection/CurveIntersection.h
+++ b/experimental/Intersection/CurveIntersection.h
@@ -46,7 +46,7 @@
bool intersect(const Cubic& cubic1, const Cubic& cubic2, Intersections& );
int intersect(const Cubic& cubic, const _Line& line, double cRange[3], double lRange[3]);
bool intersect(const Quadratic& q1, const Quadratic& q2, Intersections& );
-bool intersect(const Quadratic& quad, const _Line& line, Intersections& );
+int intersect(const Quadratic& quad, const _Line& line, Intersections& );
bool isLinear(const Quadratic& quad, int startIndex, int endIndex);
bool isLinear(const Cubic& cubic, int startIndex, int endIndex);
double leftMostT(const Cubic& , double startT, double endT);
diff --git a/experimental/Intersection/DataTypes.h b/experimental/Intersection/DataTypes.h
index 8c924af..f350567 100644
--- a/experimental/Intersection/DataTypes.h
+++ b/experimental/Intersection/DataTypes.h
@@ -99,10 +99,31 @@
return approximately_zero(x);
}
+inline bool approximately_greater_than_one(double x) {
+ return x > 1 - FLT_EPSILON;
+}
+
+inline bool approximately_less_than_zero(double x) {
+ return x < FLT_EPSILON;
+}
+
inline bool approximately_negative(double x) {
return x < FLT_EPSILON;
}
+inline bool approximately_one_or_less(double x) {
+ return x < 1 + FLT_EPSILON;
+}
+
+inline bool approximately_positive(double x) {
+ return x > -FLT_EPSILON;
+}
+
+inline bool approximately_zero_or_more(double x) {
+ return x > -FLT_EPSILON;
+}
+
+
#endif
struct _Point {
diff --git a/experimental/Intersection/EdgeWalker_TestUtility.cpp b/experimental/Intersection/EdgeWalker_TestUtility.cpp
index 4129ab4..aae7636 100644
--- a/experimental/Intersection/EdgeWalker_TestUtility.cpp
+++ b/experimental/Intersection/EdgeWalker_TestUtility.cpp
@@ -130,10 +130,10 @@
if (!c) {
delete canvasPtr;
}
- if (errors2 >= 2 || errors > 96) {
+ if (errors2 >= 3 || errors > 96) {
SkDebugf("%s errors2=%d errors=%d\n", __FUNCTION__, errors2, errors);
}
- if (errors2 >= 3 || errors > 192) {
+ if (errors2 >= 4 || errors > 192) {
drawAsciiPaths(scaledOne, scaledTwo, true);
}
error2x2 = errors2;
@@ -199,7 +199,7 @@
if (errors2x2 == 0) {
return 0;
}
- const int MAX_ERRORS = 4;
+ const int MAX_ERRORS = 5;
if (errors2x2 > MAX_ERRORS && gComparePathsAssert) {
SkDebugf("%s errors=%d\n", __FUNCTION__, errors);
showPath(one);
diff --git a/experimental/Intersection/Intersection_Tests.cpp b/experimental/Intersection/Intersection_Tests.cpp
index 100e32c..bdb8165 100644
--- a/experimental/Intersection/Intersection_Tests.cpp
+++ b/experimental/Intersection/Intersection_Tests.cpp
@@ -8,7 +8,7 @@
void Intersection_Tests() {
int testsRun = 0;
-// SimplifyAngle_Test();
+ // SimplifyAngle_Test();
SimplifyNew_Test();
Simplify4x4QuadraticsThreaded_Test(testsRun);
QuadLineIntersectThreaded_Test(testsRun);
diff --git a/experimental/Intersection/LineQuadraticIntersection.cpp b/experimental/Intersection/LineQuadraticIntersection.cpp
index f269b71..fc9c676 100644
--- a/experimental/Intersection/LineQuadraticIntersection.cpp
+++ b/experimental/Intersection/LineQuadraticIntersection.cpp
@@ -91,48 +91,41 @@
, intersections(i) {
}
-bool intersect() {
- double slope;
- double axisIntercept;
- moreHorizontal = implicitLine(line, slope, axisIntercept);
- double A = quad[2].x; // c
- double B = quad[1].x; // b
- double C = quad[0].x; // a
+int intersect() {
+/*
+ solve by rotating line+quad so line is horizontal, then finding the roots
+ set up matrix to rotate quad to x-axis
+ |cos(a) -sin(a)|
+ |sin(a) cos(a)|
+ note that cos(a) = A(djacent) / Hypoteneuse
+ sin(a) = O(pposite) / Hypoteneuse
+ since we are computing Ts, we can ignore hypoteneuse, the scale factor:
+ | A -O |
+ | O A |
+ A = line[1].x - line[0].x (adjacent side of the right triangle)
+ O = line[1].y - line[0].y (opposite side of the right triangle)
+ for each of the three points (e.g. n = 0 to 2)
+ quad[n].y' = (quad[n].y - line[0].y) * A - (quad[n].x - line[0].x) * O
+*/
+ double adj = line[1].x - line[0].x;
+ double opp = line[1].y - line[0].y;
+ double r[3];
+ for (int n = 0; n < 3; ++n) {
+ r[n] = (quad[n].y - line[0].y) * adj - (quad[n].x - line[0].x) * opp;
+ }
+ double A = r[2];
+ double B = r[1];
+ double C = r[0];
A += C - 2 * B; // A = a - 2*b + c
- B -= C; // B = -(a - b)
- double D = quad[2].y; // f
- double E = quad[1].y; // e
- double F = quad[0].y; // d
- D += F - 2 * E; // D = d - 2*e + f
- E -= F; // E = -(d - e)
- if (moreHorizontal) {
- A = A * slope - D;
- B = B * slope - E;
- C = C * slope - F + axisIntercept;
- } else {
- A = A - D * slope;
- B = B - E * slope;
- C = C - F * slope - axisIntercept;
- }
- double t[2];
- int roots = quadraticRoots(A, B, C, t);
- for (int x = 0; x < roots; ) {
- double lineT = findLineT(t[x]);
- if (lineT <= -FLT_EPSILON || lineT >= 1 + FLT_EPSILON) {
- if (x < --roots) {
- t[x] = t[roots];
- }
- continue;
+ B -= C; // B = -(b - c)
+ int roots = quadraticRoots(A, B, C, intersections.fT[0]);
+ for (int index = 0; index < roots; ) {
+ double lineT = findLineT(intersections.fT[0][index]);
+ if (lineIntersects(lineT, index, roots)) {
+ ++index;
}
- if (lineT < FLT_EPSILON) {
- lineT = 0;
- } else if (lineT > 1 - FLT_EPSILON) {
- lineT = 1;
- }
- intersections.add(t[x], lineT);
- ++x;
}
- return roots > 0;
+ return roots;
}
int horizontalIntersect(double axisIntercept) {
@@ -145,6 +138,19 @@
return quadraticRoots(D, E, F, intersections.fT[0]);
}
+int horizontalIntersect(double axisIntercept, double left, double right) {
+ int roots = horizontalIntersect(axisIntercept);
+ for (int index = 0; index < roots; ) {
+ double x;
+ xy_at_t(quad, intersections.fT[0][index], x, *(double*) NULL);
+ double lineT = (x - left) / (right - left);
+ if (lineIntersects(lineT, index, roots)) {
+ ++index;
+ }
+ }
+ return roots;
+}
+
int verticalIntersect(double axisIntercept) {
double D = quad[2].x; // f
double E = quad[1].x; // e
@@ -155,6 +161,19 @@
return quadraticRoots(D, E, F, intersections.fT[0]);
}
+int verticalIntersect(double axisIntercept, double top, double bottom) {
+ int roots = verticalIntersect(axisIntercept);
+ for (int index = 0; index < roots; ) {
+ double y;
+ xy_at_t(quad, intersections.fT[0][index], *(double*) NULL, y);
+ double lineT = (y - top) / (bottom - top);
+ if (lineIntersects(lineT, index, roots)) {
+ ++index;
+ }
+ }
+ return roots;
+}
+
protected:
double findLineT(double t) {
@@ -172,6 +191,22 @@
return (quadVal - lPtr[0]) / (lPtr[2] - lPtr[0]);
}
+bool lineIntersects(double lineT, const int x, int& roots) {
+ if (!approximately_zero_or_more(lineT) || !approximately_one_or_less(lineT)) {
+ if (x < --roots) {
+ intersections.fT[0][x] = intersections.fT[0][roots];
+ }
+ return false;
+ }
+ if (approximately_less_than_zero(lineT)) {
+ lineT = 0;
+ } else if (approximately_greater_than_one(lineT)) {
+ lineT = 1;
+ }
+ intersections.fT[1][x] = lineT;
+ return true;
+}
+
private:
const Quadratic& quad;
@@ -241,25 +276,7 @@
int horizontalIntersect(const Quadratic& quad, double left, double right, double y,
bool flipped, Intersections& intersections) {
LineQuadraticIntersections q(quad, *((_Line*) 0), intersections);
- int result = q.horizontalIntersect(y);
- for (int index = 0; index < result; ) {
- double x, y;
- xy_at_t(quad, intersections.fT[0][index], x, y);
- double lineT = (x - left) / (right - left);
- if (lineT <= -FLT_EPSILON || lineT >= 1 + FLT_EPSILON) {
- if (--result > index) {
- intersections.fT[0][index] = intersections.fT[0][result];
- }
- continue;
- }
- if (lineT < FLT_EPSILON) {
- lineT = 0;
- } else if (lineT > 1 - FLT_EPSILON) {
- lineT = 1;
- }
- intersections.fT[1][index] = lineT;
- ++index;
- }
+ int result = q.horizontalIntersect(y, left, right);
if (flipped) {
// OPTIMIZATION: instead of swapping, pass original line, use [1].x - [0].x
for (int index = 0; index < result; ++index) {
@@ -272,27 +289,9 @@
int verticalIntersect(const Quadratic& quad, double top, double bottom, double x,
bool flipped, Intersections& intersections) {
LineQuadraticIntersections q(quad, *((_Line*) 0), intersections);
- int result = q.verticalIntersect(x);
- for (int index = 0; index < result; ) {
- double x, y;
- xy_at_t(quad, intersections.fT[0][index], x, y);
- double lineT = (y - top) / (bottom - top);
- if (lineT <= -FLT_EPSILON || lineT >= 1 + FLT_EPSILON) {
- if (--result > index) {
- intersections.fT[0][index] = intersections.fT[0][result];
- }
- continue;
- }
- if (lineT < FLT_EPSILON) {
- lineT = 0;
- } else if (lineT > 1 - FLT_EPSILON) {
- lineT = 1;
- }
- intersections.fT[1][index] = lineT;
- ++index;
- }
+ int result = q.verticalIntersect(x, top, bottom);
if (flipped) {
- // OPTIMIZATION: instead of swapping, pass original line, use [1].x - [0].x
+ // OPTIMIZATION: instead of swapping, pass original line, use [1].y - [0].y
for (int index = 0; index < result; ++index) {
intersections.fT[1][index] = 1 - intersections.fT[1][index];
}
@@ -300,7 +299,7 @@
return result;
}
-bool intersect(const Quadratic& quad, const _Line& line, Intersections& i) {
+int intersect(const Quadratic& quad, const _Line& line, Intersections& i) {
LineQuadraticIntersections q(quad, line, i);
return q.intersect();
}
diff --git a/experimental/Intersection/Simplify.cpp b/experimental/Intersection/Simplify.cpp
index 5a026c8..103c534 100644
--- a/experimental/Intersection/Simplify.cpp
+++ b/experimental/Intersection/Simplify.cpp
@@ -25,9 +25,17 @@
int gDebugMaxWindValue = SK_MaxS32;
#endif
+#define HIGH_DEF_ANGLES 1
+
+#if HIGH_DEF_ANGLES
+typedef double AngleValue;
+#else
+typedef SkScalar AngleValue;
+#endif
+
#define DEBUG_UNUSED 0 // set to expose unused functions
-#if 0 // set to 1 for multiple thread -- no debugging
+#if 1 // set to 1 for multiple thread -- no debugging
const bool gRunTestsInOneThread = false;
@@ -51,11 +59,11 @@
#define DEBUG_ACTIVE_SPANS 1
#define DEBUG_ADD_INTERSECTING_TS 0
#define DEBUG_ADD_T_PAIR 0
-#define DEBUG_ANGLE 0
-#define DEBUG_CONCIDENT 0
+#define DEBUG_ANGLE 1
+#define DEBUG_CONCIDENT 1
#define DEBUG_CROSS 0
#define DEBUG_DUMP 1
-#define DEBUG_MARK_DONE 0
+#define DEBUG_MARK_DONE 1
#define DEBUG_PATH_CONSTRUCTION 1
#define DEBUG_SORT 1
#define DEBUG_WIND_BUMP 0
@@ -90,8 +98,7 @@
Intersections& intersections) {
const Quadratic aQuad = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY}};
const _Line bLine = {{b[0].fX, b[0].fY}, {b[1].fX, b[1].fY}};
- intersect(aQuad, bLine, intersections);
- return intersections.fUsed;
+ return intersect(aQuad, bLine, intersections);
}
static int CubicLineIntersect(const SkPoint a[2], const SkPoint b[3],
@@ -331,6 +338,46 @@
CubicSubDivide
};
+static void LineSubDivideHD(const SkPoint a[2], double startT, double endT,
+ _Point sub[]) {
+ const _Line aLine = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}};
+ _Line dst;
+ sub_divide(aLine, startT, endT, dst);
+ sub[0] = dst[0];
+ sub[1] = dst[1];
+}
+
+static void QuadSubDivideHD(const SkPoint a[3], double startT, double endT,
+ _Point sub[]) {
+ const Quadratic aQuad = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY},
+ {a[2].fX, a[2].fY}};
+ Quadratic dst;
+ sub_divide(aQuad, startT, endT, dst);
+ sub[0] = dst[0];
+ sub[1] = dst[1];
+ sub[2] = dst[2];
+}
+
+static void CubicSubDivideHD(const SkPoint a[4], double startT, double endT,
+ _Point sub[]) {
+ const Cubic aCubic = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY},
+ {a[2].fX, a[2].fY}, {a[3].fX, a[3].fY}};
+ Cubic dst;
+ sub_divide(aCubic, startT, endT, dst);
+ sub[0] = dst[0];
+ sub[1] = dst[1];
+ sub[2] = dst[2];
+ sub[3] = dst[3];
+}
+
+static void (* const SegmentSubDivideHD[])(const SkPoint [], double , double ,
+ _Point [] ) = {
+ NULL,
+ LineSubDivideHD,
+ QuadSubDivideHD,
+ CubicSubDivideHD
+};
+
#if DEBUG_UNUSED
static void QuadSubBounds(const SkPoint a[3], double startT, double endT,
SkRect& bounds) {
@@ -456,17 +503,17 @@
if (fDy == 0 && rh.fDy == 0 && fDx * rh.fDx < 0) {
return fDx < rh.fDx;
}
- SkScalar cmp = fDx * rh.fDy - rh.fDx * fDy;
+ AngleValue cmp = fDx * rh.fDy - rh.fDx * fDy;
if (!approximately_zero(cmp)) {
return cmp < 0;
}
- SkScalar dy = approximately_pin(fDy + fDDy);
- SkScalar rdy = approximately_pin(rh.fDy + rh.fDDy);
+ AngleValue dy = approximately_pin(fDy + fDDy);
+ AngleValue rdy = approximately_pin(rh.fDy + rh.fDDy);
if (dy * rdy < 0) {
return dy < 0;
}
- SkScalar dx = approximately_pin(fDx + fDDx);
- SkScalar rdx = approximately_pin(rh.fDx + rh.fDDx);
+ AngleValue dx = approximately_pin(fDx + fDDx);
+ AngleValue rdx = approximately_pin(rh.fDx + rh.fDDx);
if (dy == 0 && rdy == 0 && dx * rdx < 0) {
return dx < rdx;
}
@@ -502,7 +549,33 @@
bool isHorizontal() const {
return fDy == 0 && fDDy == 0 && fDDDy == 0;
}
+
+ // high precision version
+#if HIGH_DEF_ANGLES
+ void set(const SkPoint* orig, SkPath::Verb verb, const Segment* segment,
+ int start, int end, double startT, double endT) {
+ Cubic pts;
+ (*SegmentSubDivideHD[verb])(orig, startT, endT, pts);
+ fSegment = segment;
+ fStart = start;
+ fEnd = end;
+ fDx = approximately_pin(pts[1].x - pts[0].x); // b - a
+ fDy = approximately_pin(pts[1].y - pts[0].y);
+ if (verb == SkPath::kLine_Verb) {
+ fDDx = fDDy = fDDDx = fDDDy = 0;
+ return;
+ }
+ fDDx = approximately_pin(pts[2].x - pts[1].x - fDx); // a - 2b + c
+ fDDy = approximately_pin(pts[2].y - pts[1].y - fDy);
+ if (verb == SkPath::kQuad_Verb) {
+ fDDDx = fDDDy = 0;
+ return;
+ }
+ fDDDx = approximately_pin(pts[3].x + 3 * (pts[1].x - pts[2].x) - pts[0].x);
+ fDDDy = approximately_pin(pts[3].y + 3 * (pts[1].y - pts[2].y) - pts[0].y);
+ }
+#else
// since all angles share a point, this needs to know which point
// is the common origin, i.e., whether the center is at pts[0] or pts[verb]
// practically, this should only be called by addAngle
@@ -575,6 +648,7 @@
}
SkASSERT(0); // FIXME: add cubic case
}
+#endif
Segment* segment() const {
return const_cast<Segment*>(fSegment);
@@ -590,36 +664,42 @@
#if DEBUG_ANGLE
void debugShow(const SkPoint& a) const {
- SkDebugf(" d=(%1.9g,%1.9g) dd=(%1.9g,%1.9g) ddd=(%1.9g,%1.9g)",
+ SkDebugf(" d=(%1.9g,%1.9g) dd=(%1.9g,%1.9g) ddd=(%1.9g,%1.9g)\n",
fDx, fDy, fDDx, fDDy, fDDDx, fDDDy);
- SkPoint b, c, d;
- b.fX = a.fX + fDx; // add b - a
- b.fY = a.fY + fDy;
- c.fX = a.fX + 2 * fDx + fDDx; // add a + 2(b - a) to a - 2b + c
- c.fY = a.fY + 2 * fDy + fDDy;
+ AngleValue ax = (AngleValue) a.fX;
+ AngleValue ay = (AngleValue) a.fY;
+ AngleValue bx, by, cx, cy, dx, dy;
+ bx = ax + fDx; // add b - a
+ by = ay + fDy;
+ cx = ax + 2 * fDx + fDDx; // add a + 2(b - a) to a - 2b + c
+ cy = ay + 2 * fDy + fDDy;
if (fDDDx == 0 && fDDDy == 0) {
if (fDDx == 0 && fDDy == 0) {
- SkDebugf(" line=(%1.9g,%1.9g %1.9g,%1.9g)\n", a.fX, a.fY, b.fX, b.fY);
+ SkDebugf(
+" {SkPath::kLine_Verb, {{%1.9g, %1.9g}, {%1.9g, %1.9g} }},\n",
+ ax, ay, bx, by);
} else {
- SkDebugf(" quad=(%1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g)\n",
- a.fX, a.fY, b.fX, b.fY, c.fX, c.fY);
+ SkDebugf(
+" {SkPath::kQuad_Verb, {{%1.9g, %1.9g}, {%1.9g, %1.9g}, {%1.9g, %1.9g}}},\n",
+ ax, ay, bx, by, cx, cy);
}
} else {
- d.fX = fDDDx - a.fX - 3 * (c.fX - b.fX);
- d.fY = fDDDy - a.fY - 3 * (c.fY - b.fY);
- SkDebugf(" cubic=(%1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g)\n",
- a.fX, a.fY, b.fX, b.fY, c.fX, c.fY, d.fX, d.fY);
+ dx = fDDDx - ax - 3 * (cx - bx);
+ dy = fDDDy - ay - 3 * (cy - by);
+ SkDebugf(
+" {SkPath::kCubic_Verb, {{%1.9g, %1.9g}, {%1.9g, %1.9g}, {%1.9g, %1.9g}, {%1.9g, %1.9g}}},\n",
+ ax, ay, bx, by, cx, cy, dx, dy);
}
}
#endif
private:
- SkScalar fDx;
- SkScalar fDy;
- SkScalar fDDx;
- SkScalar fDDy;
- SkScalar fDDDx;
- SkScalar fDDDy;
+ AngleValue fDx;
+ AngleValue fDy;
+ AngleValue fDDx;
+ AngleValue fDDy;
+ AngleValue fDDDx;
+ AngleValue fDDDy;
const Segment* fSegment;
int fStart;
int fEnd;
@@ -726,7 +806,7 @@
}
double referenceT = fTs[index].fT;
int lesser = index;
- while (--lesser >= 0 && referenceT - fTs[lesser].fT < FLT_EPSILON) {
+ while (--lesser >= 0 && approximately_negative(referenceT - fTs[lesser].fT)) {
if (activeAngleOther(lesser, done, angles)) {
return true;
}
@@ -735,7 +815,7 @@
if (activeAngleOther(index, done, angles)) {
return true;
}
- } while (++index < fTs.count() && fTs[index].fT - referenceT < FLT_EPSILON);
+ } while (++index < fTs.count() && approximately_negative(fTs[index].fT - referenceT));
return false;
}
@@ -796,10 +876,14 @@
void addAngle(SkTDArray<Angle>& angles, int start, int end) const {
SkASSERT(start != end);
+ Angle* angle = angles.append();
+#if HIGH_DEF_ANGLES==0 // old way
SkPoint edge[4];
(*SegmentSubDivide[fVerb])(fPts, fTs[start].fT, fTs[end].fT, edge);
- Angle* angle = angles.append();
angle->set(edge, fVerb, this, start, end);
+#else // new way : compute temp edge in higher precision
+ angle->set(fPts, fVerb, this, start, end, fTs[start].fT, fTs[end].fT);
+#endif
}
void addCancelOutsides(double tStart, double oStart, Segment& other,
@@ -810,20 +894,20 @@
int oCount = other.fTs.count();
do {
++tIndex;
- } while (tStart - fTs[tIndex].fT >= FLT_EPSILON && tIndex < tCount);
+ } while (!approximately_negative(tStart - fTs[tIndex].fT) && tIndex < tCount);
int tIndexStart = tIndex;
do {
++oIndex;
- } while (oStart - other.fTs[oIndex].fT >= FLT_EPSILON && oIndex < oCount);
+ } while (!approximately_negative(oStart - other.fTs[oIndex].fT) && oIndex < oCount);
int oIndexStart = oIndex;
double nextT;
do {
nextT = fTs[++tIndex].fT;
- } while (nextT < 1 && nextT - tStart < FLT_EPSILON);
+ } while (nextT < 1 && approximately_negative(nextT - tStart));
double oNextT;
do {
oNextT = other.fTs[++oIndex].fT;
- } while (oNextT < 1 && oNextT - oStart < FLT_EPSILON);
+ } while (oNextT < 1 && approximately_negative(oNextT - oStart));
// at this point, spans before and after are at:
// fTs[tIndexStart - 1], fTs[tIndexStart], fTs[tIndex]
// if tIndexStart == 0, no prior span
@@ -885,10 +969,10 @@
double oStart = outsideTs[1];
do {
++tIndex;
- } while (tStart - fTs[tIndex].fT >= FLT_EPSILON);
+ } while (!approximately_negative(tStart - fTs[tIndex].fT));
do {
++oIndex;
- } while (oStart - other.fTs[oIndex].fT >= FLT_EPSILON);
+ } while (!approximately_negative(oStart - other.fTs[oIndex].fT));
if (tIndex > 0 || oIndex > 0) {
addTPair(tStart, other, oStart, false);
}
@@ -898,17 +982,17 @@
double nextT;
do {
nextT = fTs[++tIndex].fT;
- } while (nextT - tStart < FLT_EPSILON);
+ } while (approximately_negative(nextT - tStart));
tStart = nextT;
do {
nextT = other.fTs[++oIndex].fT;
- } while (nextT - oStart < FLT_EPSILON);
+ } while (approximately_negative(nextT - oStart));
oStart = nextT;
if (tStart == 1 && oStart == 1) {
break;
}
addTPair(tStart, other, oStart, false);
- } while (tStart < 1 && oStart < 1 && oEnd - oStart >= FLT_EPSILON);
+ } while (tStart < 1 && oStart < 1 && !approximately_negative(oEnd - oStart));
}
void addCubic(const SkPoint pts[4]) {
@@ -990,10 +1074,10 @@
int insertedAt = -1;
size_t tCount = fTs.count();
// FIXME: only do this pinning here (e.g. this is done also in quad/line intersect)
- if (newT < FLT_EPSILON) {
+ if (approximately_less_than_zero(newT)) {
newT = 0;
}
- if (newT > 1 - FLT_EPSILON) {
+ if (approximately_greater_than_one(newT)) {
newT = 1;
}
for (size_t index = 0; index < tCount; ++index) {
@@ -1037,14 +1121,14 @@
// pointer since both coincident segments must contain the same spans.
void addTCancel(double startT, double endT, Segment& other,
double oStartT, double oEndT) {
- SkASSERT(endT - startT >= FLT_EPSILON);
- SkASSERT(oEndT - oStartT >= FLT_EPSILON);
+ SkASSERT(!approximately_negative(endT - startT));
+ SkASSERT(!approximately_negative(oEndT - oStartT));
int index = 0;
- while (startT - fTs[index].fT >= FLT_EPSILON) {
+ while (!approximately_negative(startT - fTs[index].fT)) {
++index;
}
int oIndex = other.fTs.count();
- while (other.fTs[--oIndex].fT - oEndT > -FLT_EPSILON)
+ while (approximately_positive(other.fTs[--oIndex].fT - oEndT))
;
double tRatio = (oEndT - oStartT) / (endT - startT);
Span* test = &fTs[index];
@@ -1064,13 +1148,13 @@
TrackOutside(outsideTs, span->fT, oTestT);
}
span = &fTs[++index];
- } while (span->fT - testT < FLT_EPSILON);
+ } while (approximately_negative(span->fT - testT));
Span* oSpan = oTest;
double otherTMatchStart = oEndT - (span->fT - startT) * tRatio;
double otherTMatchEnd = oEndT - (test->fT - startT) * tRatio;
SkDEBUGCODE(int originalWindValue = oSpan->fWindValue);
- while (oSpan->fT > otherTMatchStart - FLT_EPSILON
- && otherTMatchEnd - FLT_EPSILON > oSpan->fT) {
+ while (approximately_negative(otherTMatchStart - oSpan->fT)
+ && !approximately_negative(otherTMatchEnd - oSpan->fT)) {
#ifdef SK_DEBUG
SkASSERT(originalWindValue == oSpan->fWindValue);
#endif
@@ -1086,8 +1170,8 @@
}
test = span;
oTest = oSpan;
- } while (test->fT < endT - FLT_EPSILON);
- SkASSERT(!oIndex || oTest->fT < oStartT + FLT_EPSILON);
+ } while (!approximately_negative(endT - test->fT));
+ SkASSERT(!oIndex || approximately_negative(oTest->fT - oStartT));
// FIXME: determine if canceled edges need outside ts added
if (!done() && outsideTs.count()) {
double tStart = outsideTs[0];
@@ -1111,14 +1195,14 @@
// the lesser
void addTCoincident(const int xorMask, double startT, double endT, Segment& other,
double oStartT, double oEndT) {
- SkASSERT(endT - startT >= FLT_EPSILON);
- SkASSERT(oEndT - oStartT >= FLT_EPSILON);
+ SkASSERT(!approximately_negative(endT - startT));
+ SkASSERT(!approximately_negative(oEndT - oStartT));
int index = 0;
- while (startT - fTs[index].fT >= FLT_EPSILON) {
+ while (!approximately_negative(startT - fTs[index].fT)) {
++index;
}
int oIndex = 0;
- while (oStartT - other.fTs[oIndex].fT >= FLT_EPSILON) {
+ while (!approximately_negative(oStartT - other.fTs[oIndex].fT)) {
++oIndex;
}
double tRatio = (oEndT - oStartT) / (endT - startT);
@@ -1155,14 +1239,14 @@
}
}
end = &fTs[++index];
- } while (end->fT - test->fT < FLT_EPSILON);
+ } while (approximately_negative(end->fT - test->fT));
// because of the order in which coincidences are resolved, this and other
// may not have the same intermediate points. Compute the corresponding
// intermediate T values (using this as the master, other as the follower)
// and walk other conditionally -- hoping that it catches up in the end
double otherTMatch = (test->fT - startT) * tRatio + oStartT;
Span* oEnd = oTest;
- while (oEnd->fT < oEndT - FLT_EPSILON && oEnd->fT - otherTMatch < FLT_EPSILON) {
+ while (!approximately_negative(oEndT - oEnd->fT) && approximately_negative(oEnd->fT - otherTMatch)) {
if (transfer) {
if (decrementThis) {
#ifdef SK_DEBUG
@@ -1182,9 +1266,9 @@
}
test = end;
oTest = oEnd;
- } while (test->fT < endT - FLT_EPSILON);
- SkASSERT(oTest->fT < oEndT + FLT_EPSILON);
- SkASSERT(oTest->fT > oEndT - FLT_EPSILON);
+ } while (!approximately_negative(endT - test->fT));
+ SkASSERT(approximately_negative(oTest->fT - oEndT));
+ SkASSERT(approximately_negative(oEndT - oTest->fT));
if (!done()) {
if (outsideTs.count()) {
addCoinOutsides(outsideTs, other, oEndT);
@@ -1204,10 +1288,10 @@
int tCount = fTs.count();
for (int tIndex = 0; tIndex < tCount; ++tIndex) {
const Span& span = fTs[tIndex];
- if (span.fT - t >= FLT_EPSILON) {
+ if (!approximately_negative(span.fT - t)) {
break;
}
- if (span.fT - t < FLT_EPSILON && span.fOther == &other && span.fOtherT == otherT) {
+ if (approximately_negative(span.fT - t) && span.fOther == &other && span.fOtherT == otherT) {
#if DEBUG_ADD_T_PAIR
SkDebugf("%s addTPair duplicate this=%d %1.9g other=%d %1.9g\n",
__FUNCTION__, fID, t, other.fID, otherT);
@@ -1247,12 +1331,12 @@
void buildAngles(int index, SkTDArray<Angle>& angles) const {
double referenceT = fTs[index].fT;
int lesser = index;
- while (--lesser >= 0 && referenceT - fTs[lesser].fT < FLT_EPSILON) {
+ while (--lesser >= 0 && approximately_negative(referenceT - fTs[lesser].fT)) {
buildAnglesInner(lesser, angles);
}
do {
buildAnglesInner(index, angles);
- } while (++index < fTs.count() && fTs[index].fT - referenceT < FLT_EPSILON);
+ } while (++index < fTs.count() && approximately_negative(fTs[index].fT - referenceT));
}
void buildAnglesInner(int index, SkTDArray<Angle>& angles) const {
@@ -1510,7 +1594,7 @@
nextEnd = nextStart;
do {
nextEnd += step;
- } while (fabs(startT - other->fTs[nextEnd].fT) < FLT_EPSILON);
+ } while (approximately_zero(startT - other->fTs[nextEnd].fT));
SkASSERT(step < 0 ? nextEnd >= 0 : nextEnd < other->fTs.count());
return other;
}
@@ -1673,8 +1757,8 @@
nextStart = endSpan->fOtherIndex;
double startT = other->fTs[nextStart].fT;
SkDEBUGCODE(bool firstLoop = true;)
- if ((startT < FLT_EPSILON && step < 0)
- || (startT > 1 - FLT_EPSILON && step > 0)) {
+ if ((approximately_less_than_zero(startT) && step < 0)
+ || (approximately_greater_than_one(startT) && step > 0)) {
step = -step;
SkDEBUGCODE(firstLoop = false;)
}
@@ -1682,7 +1766,7 @@
nextEnd = nextStart;
do {
nextEnd += step;
- } while (fabs(startT - other->fTs[nextEnd].fT) < FLT_EPSILON);
+ } while (approximately_zero(startT - other->fTs[nextEnd].fT));
if (other->fTs[SkMin32(nextStart, nextEnd)].fWindValue) {
break;
}
@@ -1825,7 +1909,7 @@
continue;
}
// FIXME: if moStartT, moEndT are initialized to NaN, can skip this test
- if (moStartT == moEndT) {
+ if (approximately_equal(moStartT, moEndT)) {
continue;
}
int toStart = -1;
@@ -1857,7 +1941,7 @@
if (toStart <= 0 || toEnd <= 0) {
continue;
}
- if (toStartT == toEndT) {
+ if (approximately_equal(toStartT, toEndT)) {
continue;
}
// test to see if the segment between there and here is linear
@@ -1866,14 +1950,10 @@
continue;
}
bool flipped = (moStart - moEnd) * (toStart - toEnd) < 1;
- double tStart = tOther->fTs[toStart].fT;
- double tEnd = tOther->fTs[toEnd].fT;
- double mStart = mOther->fTs[moStart].fT;
- double mEnd = mOther->fTs[moEnd].fT;
if (flipped) {
- mOther->addTCancel(mStart, mEnd, *tOther, tEnd, tStart);
+ mOther->addTCancel(moStartT, moEndT, *tOther, toEndT, toStartT);
} else {
- mOther->addTCoincident(xorMask, mStart, mEnd, *tOther, tStart, tEnd);
+ mOther->addTCoincident(xorMask, moStartT, moEndT, *tOther, toStartT, toEndT);
}
}
}
@@ -2032,7 +2112,7 @@
bool isMissing(double startT) const {
size_t tCount = fTs.count();
for (size_t index = 0; index < tCount; ++index) {
- if (fabs(startT - fTs[index].fT) < FLT_EPSILON) {
+ if (approximately_zero(startT - fTs[index].fT)) {
return false;
}
}
@@ -2045,11 +2125,11 @@
return true;
}
double t = fTs[end].fT;
- if (t < FLT_EPSILON) {
- return fTs[1].fT >= FLT_EPSILON;
+ if (approximately_less_than_zero(t)) {
+ return !approximately_less_than_zero(fTs[1].fT);
}
- if (t > 1 - FLT_EPSILON) {
- return fTs[count - 2].fT <= 1 - FLT_EPSILON;
+ if (approximately_greater_than_one(t)) {
+ return !approximately_greater_than_one(fTs[count - 2].fT);
}
return false;
}
@@ -2098,12 +2178,12 @@
SkASSERT(winding);
double referenceT = fTs[index].fT;
int lesser = index;
- while (--lesser >= 0 && referenceT - fTs[lesser].fT < FLT_EPSILON) {
+ while (--lesser >= 0 && approximately_negative(referenceT - fTs[lesser].fT)) {
markOneDone(__FUNCTION__, lesser, winding);
}
do {
markOneDone(__FUNCTION__, index, winding);
- } while (++index < fTs.count() && fTs[index].fT - referenceT < FLT_EPSILON);
+ } while (++index < fTs.count() && approximately_negative(fTs[index].fT - referenceT));
}
void markOneDone(const char* funName, int tIndex, int winding) {
@@ -2136,25 +2216,25 @@
SkASSERT(winding);
double referenceT = fTs[index].fT;
int lesser = index;
- while (--lesser >= 0 && referenceT - fTs[lesser].fT < FLT_EPSILON) {
+ while (--lesser >= 0 && approximately_negative(referenceT - fTs[lesser].fT)) {
markOneWinding(__FUNCTION__, lesser, winding);
}
do {
markOneWinding(__FUNCTION__, index, winding);
- } while (++index < fTs.count() && fTs[index].fT - referenceT < FLT_EPSILON);
+ } while (++index < fTs.count() && approximately_negative(fTs[index].fT - referenceT));
}
void matchWindingValue(int tIndex, double t, bool borrowWind) {
int nextDoorWind = SK_MaxS32;
if (tIndex > 0) {
const Span& below = fTs[tIndex - 1];
- if (t - below.fT < FLT_EPSILON) {
+ if (approximately_negative(t - below.fT)) {
nextDoorWind = below.fWindValue;
}
}
if (nextDoorWind == SK_MaxS32 && tIndex + 1 < fTs.count()) {
const Span& above = fTs[tIndex + 1];
- if (above.fT - t < FLT_EPSILON) {
+ if (approximately_negative(above.fT - t)) {
nextDoorWind = above.fWindValue;
}
}
@@ -2194,7 +2274,7 @@
int to = from;
while (step > 0 ? ++to < count : --to >= 0) {
const Span& span = fTs[to];
- if ((step > 0 ? span.fT - fromSpan.fT : fromSpan.fT - span.fT) < FLT_EPSILON) {
+ if (approximately_zero(span.fT - fromSpan.fT)) {
continue;
}
return to;
@@ -2239,7 +2319,7 @@
static void TrackOutside(SkTDArray<double>& outsideTs, double end,
double start) {
int outCount = outsideTs.count();
- if (outCount == 0 || end - outsideTs[outCount - 2] >= FLT_EPSILON) {
+ if (outCount == 0 || !approximately_negative(end - outsideTs[outCount - 2])) {
*outsideTs.append() = end;
*outsideTs.append() = start;
}
@@ -2256,7 +2336,7 @@
SkASSERT(index < tCount - 1);
start = index;
double startT = fTs[index].fT;
- while (fTs[++index].fT - startT < FLT_EPSILON)
+ while (approximately_negative(fTs[++index].fT - startT))
SkASSERT(index < tCount);
SkASSERT(index < tCount);
end = index;
@@ -2680,13 +2760,13 @@
if (startT > endT) {
SkTSwap<double>(startT, endT);
}
- SkASSERT(endT - startT >= FLT_EPSILON);
+ SkASSERT(!approximately_negative(endT - startT));
double oStartT = coincidence.fTs[1][0];
double oEndT = coincidence.fTs[1][1];
if (oStartT > oEndT) {
SkTSwap<double>(oStartT, oEndT);
}
- SkASSERT(oEndT - oStartT >= FLT_EPSILON);
+ SkASSERT(!approximately_negative(oEndT - oStartT));
if (thisOne.cancels(other)) {
// make sure startT and endT have t entries
if (startT > 0 || oEndT < 1
@@ -3415,7 +3495,7 @@
// angles to find the span closest to the ray -- even if there are just
// two spokes on the wheel.
const Angle* angle = NULL;
- if (fabs(tHit - test->t(tIndex)) < FLT_EPSILON) {
+ if (approximately_zero(tHit - test->t(tIndex))) {
SkTDArray<Angle> angles;
int end = test->nextSpan(tIndex, 1);
if (end < 0) {
diff --git a/experimental/Intersection/SimplifyAngle_Test.cpp b/experimental/Intersection/SimplifyAngle_Test.cpp
index 33b5fe2..1228a77 100644
--- a/experimental/Intersection/SimplifyAngle_Test.cpp
+++ b/experimental/Intersection/SimplifyAngle_Test.cpp
@@ -65,8 +65,16 @@
{SkPath::kMove_Verb }
};
+static const segment segmentTest2[] = {
+ {SkPath::kLine_Verb, {{1, 0}, {0, 0} }},
+ {SkPath::kQuad_Verb, {{1, 0}, {1.89897954f, 0.898979485f}, {2.39387703f, 1.59591794f}}},
+ {SkPath::kLine_Verb, {{1, 0}, {3, 2} }},
+ {SkPath::kMove_Verb }
+};
+
static const segment* segmentTests[] = {
- segmentTest1
+ segmentTest2,
+ segmentTest1,
};
static const size_t segmentTestCount = sizeof(segmentTests) / sizeof(segmentTests[0]);
@@ -78,19 +86,27 @@
int index = 0;
do {
int next = index + 1;
+ #if HIGH_DEF_ANGLES==0
if (testFlat) {
lesser.setFlat(segPtr[index].pts, segPtr[index].verb, 0, index, next);
} else {
lesser.set(segPtr[index].pts, segPtr[index].verb, 0, index, next);
}
+ #else
+ lesser.set(segPtr[index].pts, segPtr[index].verb, 0, index, next, 0, 1);
+ #endif
if (segPtr[next].verb == SkPath::kMove_Verb) {
break;
}
+ #if HIGH_DEF_ANGLES==0
if (testFlat) {
greater.setFlat(segPtr[next].pts, segPtr[next].verb, 0, index, next);
} else {
greater.set(segPtr[next].pts, segPtr[next].verb, 0, index, next);
}
+ #else
+ greater.set(segPtr[next].pts, segPtr[next].verb, 0, index, next, 0, 1);
+ #endif
bool result = lesser < greater;
SkASSERT(result);
index = next;
@@ -106,11 +122,15 @@
size_t x;
for (x = 0; x < lineCount; ++x) {
SimplifyAngleTest::Angle* angle = angles.append();
+ #if HIGH_DEF_ANGLES==0
if (testFlat) {
angle->setFlat(lines[x], SkPath::kLine_Verb, 0, x, x + 1);
} else {
angle->set(lines[x], SkPath::kLine_Verb, 0, x, x + 1);
}
+ #else
+ angle->set(lines[x], SkPath::kLine_Verb, 0, x, x + 1, 0, 1);
+ #endif
double arcTan = atan2(lines[x][0].fX - lines[x][1].fX,
lines[x][0].fY - lines[x][1].fY);
arcTans.push(arcTan);
@@ -157,12 +177,16 @@
size_t x;
for (x = 0; x < quadCount; ++x) {
SimplifyAngleTest::Angle* angle = angles.append();
+ #if HIGH_DEF_ANGLES==0
if (testFlat) {
angle->setFlat(quads[x], SkPath::kQuad_Verb, 0, x, x + 1);
} else {
angle->set(quads[x], SkPath::kQuad_Verb, 0, x, x + 1);
}
- }
+ #else
+ angle->set(quads[x], SkPath::kQuad_Verb, 0, x, x + 1, 0, 1);
+ #endif
+ }
for (x = 0; x < quadCount; ++x) {
angleList.push(&angles[x]);
}
@@ -183,11 +207,15 @@
SkTDArray<SimplifyAngleTest::Angle* > angleList;
for (size_t x = 0; x < cubicCount; ++x) {
SimplifyAngleTest::Angle* angle = angles.append();
+ #if HIGH_DEF_ANGLES==0
if (testFlat) {
angle->setFlat(cubics[x], SkPath::kCubic_Verb, 0, x, x + 1);
} else {
angle->set(cubics[x], SkPath::kCubic_Verb, 0, x, x + 1);
}
+ #else
+ angle->set(cubics[x], SkPath::kCubic_Verb, 0, x, x + 1, 0, 1);
+ #endif
angleList.push(angle);
}
QSort<SimplifyAngleTest::Angle>(angleList.begin(), angleList.end() - 1);
diff --git a/experimental/Intersection/SimplifyNew_Test.cpp b/experimental/Intersection/SimplifyNew_Test.cpp
index c862c27..799e78b 100644
--- a/experimental/Intersection/SimplifyNew_Test.cpp
+++ b/experimental/Intersection/SimplifyNew_Test.cpp
@@ -2472,12 +2472,55 @@
testSimplifyx(path);
}
-static void (*firstTest)() = testQuadratic14;
+static void testQuadratic15() {
+ SkPath path;
+ path.moveTo(0, 0);
+ path.quadTo(0, 0, 1, 0);
+ path.lineTo(1, 3);
+ path.close();
+ path.moveTo(1, 0);
+ path.lineTo(0, 1);
+ path.quadTo(1, 1, 0, 3);
+ path.close();
+ testSimplifyx(path);
+}
+
+static void testQuadratic17x() {
+ SkPath path;
+ path.setFillType(SkPath::kEvenOdd_FillType);
+ path.moveTo(0, 0);
+ path.quadTo(0, 0, 3, 1);
+ path.lineTo(0, 2);
+ path.close();
+ path.moveTo(0, 0);
+ path.lineTo(1, 0);
+ path.quadTo(3, 1, 0, 2);
+ path.close();
+ testSimplifyx(path);
+}
+
+static void testQuadratic18() {
+ SkPath path;
+ path.moveTo(0, 0);
+ path.quadTo(1, 0, 0, 1);
+ path.lineTo(0, 1);
+ path.close();
+ path.moveTo(0, 0);
+ path.lineTo(0, 0);
+ path.quadTo(1, 0, 1, 1);
+ path.close();
+ testSimplifyx(path);
+}
+
+static void (*firstTest)() = testQuadratic18;
static struct {
void (*fun)();
const char* str;
} tests[] = {
+ TEST(testQuadratic18),
+ TEST(testQuadratic17x),
+ TEST(testQuadratic15),
TEST(testQuadratic14),
TEST(testQuadratic9),
TEST(testQuadratic8),
diff --git a/experimental/Intersection/op.htm b/experimental/Intersection/op.htm
index b11b8f3..441bd16 100644
--- a/experimental/Intersection/op.htm
+++ b/experimental/Intersection/op.htm
@@ -1227,11 +1227,88 @@
path.close();
</div>
+<div id="testQuadratic15">
+ path.moveTo(0, 0);
+ path.quadTo(0, 0, 1, 0);
+ path.lineTo(1, 3);
+ path.close();
+ path.moveTo(1, 0);
+ path.lineTo(0, 1);
+ path.quadTo(1, 1, 0, 3);
+ path.close();
+</div>
+
+<div id="testQuadratic16a">
+path.moveTo(0, 0);
+path.quadTo(0, 0, 31, 0);
+path.lineTo(46.5, 31);
+path.lineTo(0, 0);
+path.close();
+path.moveTo(46.5, 15.5);
+path.lineTo(0, 31);
+path.quadTo(0, 31, 15.5, 31);
+path.lineTo(46.5, 15.5);
+path.close();
+</div>
+
+<div id="testQuadratic16b">
+path.moveTo(31, 20.6666679);
+path.lineTo(0, 0);
+path.lineTo(31, 0);
+path.lineTo(39.8571434, 17.7142868);
+path.lineTo(31, 20.6666679);
+path.close();
+path.moveTo(33.214283, 22.1428585);
+path.lineTo(15.5, 31);
+path.lineTo(0, 31);
+path.lineTo(31, 20.6666679);
+path.lineTo(33.214283, 22.1428585);
+path.close();
+path.moveTo(40.2999992, 18.6000004);
+path.lineTo(46.5, 31);
+path.lineTo(33.214283, 22.1428585);
+path.lineTo(40.2999992, 18.6000004);
+path.close();
+path.moveTo(39.8571434, 17.7142868);
+path.lineTo(46.5, 15.5);
+path.lineTo(40.2999992, 18.6000004);
+path.lineTo(39.8571434, 17.7142868);
+path.close();
+</div>
+
+<div id="testQuadratic17x">
+ path.setFillType(SkPath::kEvenOdd_FillType);
+ path.moveTo(0, 0);
+ path.quadTo(0, 0, 3, 1);
+ path.lineTo(0, 2);
+ path.close();
+ path.moveTo(0, 0);
+ path.lineTo(1, 0);
+ path.quadTo(3, 1, 0, 2);
+ path.close();
+</div>
+
+<div id="testQuadratic18">
+ path.moveTo(0, 0);
+ path.quadTo(1, 0, 0, 1);
+ path.lineTo(0, 1);
+ path.close();
+ path.moveTo(0, 0);
+ path.lineTo(0, 0);
+ path.quadTo(1, 0, 1, 1);
+ path.close();
+</div>
+
</div>
<script type="text/javascript">
var testDivs = [
+ testQuadratic18,
+ testQuadratic17x,
+ testQuadratic16b,
+ testQuadratic16a,
+ testQuadratic15,
testQuadratic14,
testQuadratic13b,
testQuadratic13a,