shape ops work in progress
git-svn-id: http://skia.googlecode.com/svn/trunk@7738 2bbb7eff-a529-9590-31e7-b0007b416f81
diff --git a/experimental/Intersection/CubicBounds.cpp b/experimental/Intersection/CubicBounds.cpp
index c7ca49a..7fd9fef 100644
--- a/experimental/Intersection/CubicBounds.cpp
+++ b/experimental/Intersection/CubicBounds.cpp
@@ -10,15 +10,13 @@
static int isBoundedByEndPoints(double a, double b, double c, double d)
{
- return (a <= b && a <= c && b <= d && c <= d)
- || (a >= b && a >= c && b >= d && c >= d);
+ return between(a, b, d) && between(a, c, d);
}
double leftMostT(const Cubic& cubic, double startT, double endT) {
double leftTs[2];
_Point pt[2];
- int results = findExtrema(cubic[0].x, cubic[1].x, cubic[2].x, cubic[3].x,
- leftTs);
+ int results = findExtrema(cubic[0].x, cubic[1].x, cubic[2].x, cubic[3].x, leftTs);
int best = -1;
for (int index = 0; index < results; ++index) {
if (startT > leftTs[index] || leftTs[index] > endT) {
@@ -48,12 +46,10 @@
double tValues[4];
int roots = 0;
if (!isBoundedByEndPoints(cubic[0].x, cubic[1].x, cubic[2].x, cubic[3].x)) {
- roots = findExtrema(cubic[0].x, cubic[1].x, cubic[2].x,
- cubic[3].x, tValues);
+ roots = findExtrema(cubic[0].x, cubic[1].x, cubic[2].x, cubic[3].x, tValues);
}
if (!isBoundedByEndPoints(cubic[0].y, cubic[1].y, cubic[2].y, cubic[3].y)) {
- roots += findExtrema(cubic[0].y, cubic[1].y, cubic[2].y,
- cubic[3].y, &tValues[roots]);
+ roots += findExtrema(cubic[0].y, cubic[1].y, cubic[2].y, cubic[3].y, &tValues[roots]);
}
for (int x = 0; x < roots; ++x) {
_Point result;
diff --git a/experimental/Intersection/CubicConvexHull.cpp b/experimental/Intersection/CubicConvexHull.cpp
new file mode 100644
index 0000000..3be8c21
--- /dev/null
+++ b/experimental/Intersection/CubicConvexHull.cpp
@@ -0,0 +1,165 @@
+/*
+ * Copyright 2012 Google Inc.
+ *
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+
+#include "CubicUtilities.h"
+#include "CurveIntersection.h"
+#include "Intersections.h"
+#include "IntersectionUtilities.h"
+#include "LineIntersection.h"
+
+static const double tClipLimit = 0.8; // http://cagd.cs.byu.edu/~tom/papers/bezclip.pdf see Multiple intersections
+
+class CubicIntersections : public Intersections {
+public:
+
+CubicIntersections(const Cubic& c1, const Cubic& c2, Intersections& i)
+ : cubic1(c1)
+ , cubic2(c2)
+ , intersections(i)
+ , depth(0)
+ , splits(0) {
+}
+
+bool intersect() {
+ double minT1, minT2, maxT1, maxT2;
+ if (!bezier_clip(cubic2, cubic1, minT1, maxT1)) {
+ return false;
+ }
+ if (!bezier_clip(cubic1, cubic2, minT2, maxT2)) {
+ return false;
+ }
+ int split;
+ if (maxT1 - minT1 < maxT2 - minT2) {
+ intersections.swap();
+ minT2 = 0;
+ maxT2 = 1;
+ split = maxT1 - minT1 > tClipLimit;
+ } else {
+ minT1 = 0;
+ maxT1 = 1;
+ split = (maxT2 - minT2 > tClipLimit) << 1;
+ }
+ return chop(minT1, maxT1, minT2, maxT2, split);
+}
+
+protected:
+
+bool intersect(double minT1, double maxT1, double minT2, double maxT2) {
+ Cubic smaller, larger;
+ // FIXME: carry last subdivide and reduceOrder result with cubic
+ sub_divide(cubic1, minT1, maxT1, intersections.swapped() ? larger : smaller);
+ sub_divide(cubic2, minT2, maxT2, intersections.swapped() ? smaller : larger);
+ Cubic smallResult;
+ if (reduceOrder(smaller, smallResult,
+ kReduceOrder_NoQuadraticsAllowed) <= 2) {
+ Cubic largeResult;
+ if (reduceOrder(larger, largeResult,
+ kReduceOrder_NoQuadraticsAllowed) <= 2) {
+ const _Line& smallLine = (const _Line&) smallResult;
+ const _Line& largeLine = (const _Line&) largeResult;
+ Intersections lineTs;
+ // FIXME: this doesn't detect or deal with coincident lines
+ if (!::intersect(smallLine, largeLine, lineTs)) {
+ return false;
+ }
+ if (intersections.swapped()) {
+ lineTs.fT[0][0] = interp(minT2, maxT2, lineTs.fT[0][0]);
+ lineTs.fT[1][0] = interp(minT1, maxT1, lineTs.fT[1][0]);
+ } else {
+ lineTs.fT[0][0] = interp(minT1, maxT1, lineTs.fT[0][0]);
+ lineTs.fT[1][0] = interp(minT2, maxT2, lineTs.fT[1][0]);
+ }
+ _Point pt;
+ xy_at_t(cubic1, lineTs.fT[0][0], pt.x, pt.y);
+ intersections.insert(lineTs.fT[0][0], lineTs.fT[1][0], pt);
+ return true;
+ }
+ }
+ double minT, maxT;
+ if (!bezier_clip(smaller, larger, minT, maxT)) {
+ if (minT == maxT) {
+ if (intersections.swapped()) {
+ minT1 = (minT1 + maxT1) / 2;
+ minT2 = interp(minT2, maxT2, minT);
+ } else {
+ minT1 = interp(minT1, maxT1, minT);
+ minT2 = (minT2 + maxT2) / 2;
+ }
+ _Point pt;
+ xy_at_t(cubic1, minT1, pt.x, pt.y);
+ intersections.insert(minT1, minT2, pt);
+ return true;
+ }
+ return false;
+ }
+
+ int split;
+ if (intersections.swapped()) {
+ double newMinT1 = interp(minT1, maxT1, minT);
+ double newMaxT1 = interp(minT1, maxT1, maxT);
+ split = (newMaxT1 - newMinT1 > (maxT1 - minT1) * tClipLimit) << 1;
+#define VERBOSE 0
+#if VERBOSE
+ printf("%s d=%d s=%d new1=(%g,%g) old1=(%g,%g) split=%d\n",
+ __FUNCTION__, depth, splits, newMinT1, newMaxT1, minT1, maxT1,
+ split);
+#endif
+ minT1 = newMinT1;
+ maxT1 = newMaxT1;
+ } else {
+ double newMinT2 = interp(minT2, maxT2, minT);
+ double newMaxT2 = interp(minT2, maxT2, maxT);
+ split = newMaxT2 - newMinT2 > (maxT2 - minT2) * tClipLimit;
+#if VERBOSE
+ printf("%s d=%d s=%d new2=(%g,%g) old2=(%g,%g) split=%d\n",
+ __FUNCTION__, depth, splits, newMinT2, newMaxT2, minT2, maxT2,
+ split);
+#endif
+ minT2 = newMinT2;
+ maxT2 = newMaxT2;
+ }
+ return chop(minT1, maxT1, minT2, maxT2, split);
+}
+
+bool chop(double minT1, double maxT1, double minT2, double maxT2, int split) {
+ ++depth;
+ intersections.swap();
+ if (split) {
+ ++splits;
+ if (split & 2) {
+ double middle1 = (maxT1 + minT1) / 2;
+ intersect(minT1, middle1, minT2, maxT2);
+ intersect(middle1, maxT1, minT2, maxT2);
+ } else {
+ double middle2 = (maxT2 + minT2) / 2;
+ intersect(minT1, maxT1, minT2, middle2);
+ intersect(minT1, maxT1, middle2, maxT2);
+ }
+ --splits;
+ intersections.swap();
+ --depth;
+ return intersections.intersected();
+ }
+ bool result = intersect(minT1, maxT1, minT2, maxT2);
+ intersections.swap();
+ --depth;
+ return result;
+}
+
+private:
+
+const Cubic& cubic1;
+const Cubic& cubic2;
+Intersections& intersections;
+int depth;
+int splits;
+};
+
+bool intersect(const Cubic& c1, const Cubic& c2, Intersections& i) {
+ CubicIntersections c(c1, c2, i);
+ return c.intersect();
+}
diff --git a/experimental/Intersection/CubicIntersection.cpp b/experimental/Intersection/CubicIntersection.cpp
index 6e88eff..02310a3 100644
--- a/experimental/Intersection/CubicIntersection.cpp
+++ b/experimental/Intersection/CubicIntersection.cpp
@@ -12,243 +12,12 @@
#include "LineIntersection.h"
#include "LineUtilities.h"
-#define DEBUG_COMPUTE_DELTA 1
-#define COMPUTE_DELTA 0
+#if ONE_OFF_DEBUG
+static const double tLimits[2][2] = {{0.516980827, 0.516981209}, {0.647714088, 0.64771447}};
+#endif
+
#define DEBUG_QUAD_PART 0
-static const double tClipLimit = 0.8; // http://cagd.cs.byu.edu/~tom/papers/bezclip.pdf see Multiple intersections
-
-class CubicIntersections : public Intersections {
-public:
-
-CubicIntersections(const Cubic& c1, const Cubic& c2, Intersections& i)
- : cubic1(c1)
- , cubic2(c2)
- , intersections(i)
- , depth(0)
- , splits(0) {
-}
-
-bool intersect() {
- double minT1, minT2, maxT1, maxT2;
- if (!bezier_clip(cubic2, cubic1, minT1, maxT1)) {
- return false;
- }
- if (!bezier_clip(cubic1, cubic2, minT2, maxT2)) {
- return false;
- }
- int split;
- if (maxT1 - minT1 < maxT2 - minT2) {
- intersections.swap();
- minT2 = 0;
- maxT2 = 1;
- split = maxT1 - minT1 > tClipLimit;
- } else {
- minT1 = 0;
- maxT1 = 1;
- split = (maxT2 - minT2 > tClipLimit) << 1;
- }
- return chop(minT1, maxT1, minT2, maxT2, split);
-}
-
-protected:
-
-bool intersect(double minT1, double maxT1, double minT2, double maxT2) {
- Cubic smaller, larger;
- // FIXME: carry last subdivide and reduceOrder result with cubic
- sub_divide(cubic1, minT1, maxT1, intersections.swapped() ? larger : smaller);
- sub_divide(cubic2, minT2, maxT2, intersections.swapped() ? smaller : larger);
- Cubic smallResult;
- if (reduceOrder(smaller, smallResult,
- kReduceOrder_NoQuadraticsAllowed) <= 2) {
- Cubic largeResult;
- if (reduceOrder(larger, largeResult,
- kReduceOrder_NoQuadraticsAllowed) <= 2) {
- const _Line& smallLine = (const _Line&) smallResult;
- const _Line& largeLine = (const _Line&) largeResult;
- double smallT[2];
- double largeT[2];
- // FIXME: this doesn't detect or deal with coincident lines
- if (!::intersect(smallLine, largeLine, smallT, largeT)) {
- return false;
- }
- if (intersections.swapped()) {
- smallT[0] = interp(minT2, maxT2, smallT[0]);
- largeT[0] = interp(minT1, maxT1, largeT[0]);
- } else {
- smallT[0] = interp(minT1, maxT1, smallT[0]);
- largeT[0] = interp(minT2, maxT2, largeT[0]);
- }
- intersections.add(smallT[0], largeT[0]);
- return true;
- }
- }
- double minT, maxT;
- if (!bezier_clip(smaller, larger, minT, maxT)) {
- if (minT == maxT) {
- if (intersections.swapped()) {
- minT1 = (minT1 + maxT1) / 2;
- minT2 = interp(minT2, maxT2, minT);
- } else {
- minT1 = interp(minT1, maxT1, minT);
- minT2 = (minT2 + maxT2) / 2;
- }
- intersections.add(minT1, minT2);
- return true;
- }
- return false;
- }
-
- int split;
- if (intersections.swapped()) {
- double newMinT1 = interp(minT1, maxT1, minT);
- double newMaxT1 = interp(minT1, maxT1, maxT);
- split = (newMaxT1 - newMinT1 > (maxT1 - minT1) * tClipLimit) << 1;
-#define VERBOSE 0
-#if VERBOSE
- printf("%s d=%d s=%d new1=(%g,%g) old1=(%g,%g) split=%d\n",
- __FUNCTION__, depth, splits, newMinT1, newMaxT1, minT1, maxT1,
- split);
-#endif
- minT1 = newMinT1;
- maxT1 = newMaxT1;
- } else {
- double newMinT2 = interp(minT2, maxT2, minT);
- double newMaxT2 = interp(minT2, maxT2, maxT);
- split = newMaxT2 - newMinT2 > (maxT2 - minT2) * tClipLimit;
-#if VERBOSE
- printf("%s d=%d s=%d new2=(%g,%g) old2=(%g,%g) split=%d\n",
- __FUNCTION__, depth, splits, newMinT2, newMaxT2, minT2, maxT2,
- split);
-#endif
- minT2 = newMinT2;
- maxT2 = newMaxT2;
- }
- return chop(minT1, maxT1, minT2, maxT2, split);
-}
-
-bool chop(double minT1, double maxT1, double minT2, double maxT2, int split) {
- ++depth;
- intersections.swap();
- if (split) {
- ++splits;
- if (split & 2) {
- double middle1 = (maxT1 + minT1) / 2;
- intersect(minT1, middle1, minT2, maxT2);
- intersect(middle1, maxT1, minT2, maxT2);
- } else {
- double middle2 = (maxT2 + minT2) / 2;
- intersect(minT1, maxT1, minT2, middle2);
- intersect(minT1, maxT1, middle2, maxT2);
- }
- --splits;
- intersections.swap();
- --depth;
- return intersections.intersected();
- }
- bool result = intersect(minT1, maxT1, minT2, maxT2);
- intersections.swap();
- --depth;
- return result;
-}
-
-private:
-
-const Cubic& cubic1;
-const Cubic& cubic2;
-Intersections& intersections;
-int depth;
-int splits;
-};
-
-bool intersect(const Cubic& c1, const Cubic& c2, Intersections& i) {
- CubicIntersections c(c1, c2, i);
- return c.intersect();
-}
-
-#if COMPUTE_DELTA
-static void cubicTangent(const Cubic& cubic, double t, _Line& tangent, _Point& pt, _Point& dxy) {
- xy_at_t(cubic, t, tangent[0].x, tangent[0].y);
- pt = tangent[1] = tangent[0];
- dxdy_at_t(cubic, t, dxy);
- if (dxy.approximatelyZero()) {
- if (approximately_zero(t)) {
- SkASSERT(cubic[0].approximatelyEqual(cubic[1]));
- dxy = cubic[2];
- dxy -= cubic[0];
- } else {
- SkASSERT(approximately_equal(t, 1));
- SkASSERT(cubic[3].approximatelyEqual(cubic[2]));
- dxy = cubic[3];
- dxy -= cubic[1];
- }
- SkASSERT(!dxy.approximatelyZero());
- }
- tangent[0] -= dxy;
- tangent[1] += dxy;
-#if DEBUG_COMPUTE_DELTA
- SkDebugf("%s t=%1.9g tangent=(%1.9g,%1.9g %1.9g,%1.9g)"
- " pt=(%1.9g %1.9g) dxy=(%1.9g %1.9g)\n", __FUNCTION__, t,
- tangent[0].x, tangent[0].y, tangent[1].x, tangent[1].y, pt.x, pt.y,
- dxy.x, dxy.y);
-#endif
-}
-#endif
-
-#if COMPUTE_DELTA
-static double cubicDelta(const _Point& dxy, _Line& tangent, double scale) {
- double tangentLen = dxy.length();
- tangent[0] -= tangent[1];
- double intersectLen = tangent[0].length();
- double result = intersectLen / tangentLen + scale;
-#if DEBUG_COMPUTE_DELTA
- SkDebugf("%s tangent=(%1.9g,%1.9g %1.9g,%1.9g) intersectLen=%1.9g tangentLen=%1.9g scale=%1.9g"
- " result=%1.9g\n", __FUNCTION__, tangent[0].x, tangent[0].y, tangent[1].x, tangent[1].y,
- intersectLen, tangentLen, scale, result);
-#endif
- return result;
-}
-#endif
-
-#if COMPUTE_DELTA
-// FIXME: after testing, make this static
-static void computeDelta(const Cubic& c1, double t1, double scale1, const Cubic& c2, double t2,
- double scale2, double& delta1, double& delta2) {
-#if DEBUG_COMPUTE_DELTA
- SkDebugf("%s c1=(%1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g) t1=%1.9g scale1=%1.9g"
- " c2=(%1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g) t2=%1.9g scale2=%1.9g\n",
- __FUNCTION__,
- c1[0].x, c1[0].y, c1[1].x, c1[1].y, c1[2].x, c1[2].y, c1[3].x, c1[3].y, t1, scale1,
- c2[0].x, c2[0].y, c2[1].x, c2[1].y, c2[2].x, c2[2].y, c2[3].x, c2[3].y, t2, scale2);
-#endif
- _Line tangent1, tangent2, line1, line2;
- _Point dxy1, dxy2;
- cubicTangent(c1, t1, line1, tangent1[0], dxy1);
- cubicTangent(c2, t2, line2, tangent2[0], dxy2);
- double range1[2], range2[2];
- int found = intersect(line1, line2, range1, range2);
- if (found == 0) {
- range1[0] = 0.5;
- } else {
- SkASSERT(found == 1);
- }
- xy_at_t(line1, range1[0], tangent1[1].x, tangent1[1].y);
-#if SK_DEBUG
- if (found == 1) {
- xy_at_t(line2, range2[0], tangent2[1].x, tangent2[1].y);
- SkASSERT(tangent2[1].approximatelyEqual(tangent1[1]));
- }
-#endif
- tangent2[1] = tangent1[1];
- delta1 = cubicDelta(dxy1, tangent1, scale1 / precisionUnit);
- delta2 = cubicDelta(dxy2, tangent2, scale2 / precisionUnit);
-}
-
-#if SK_DEBUG
-int debugDepth;
-#endif
-#endif
-
static int quadPart(const Cubic& cubic, double tStart, double tEnd, Quadratic& simple) {
Cubic part;
sub_divide(cubic, tStart, tEnd, part);
@@ -283,7 +52,7 @@
if (order1 == 3 && order2 == 3) {
intersect2(simple1, simple2, i);
} else if (order1 <= 2 && order2 <= 2) {
- i.fUsed = intersect((const _Line&) simple1, (const _Line&) simple2, i.fT[0], i.fT[1]);
+ intersect((const _Line&) simple1, (const _Line&) simple2, i);
} else if (order1 == 3 && order2 <= 2) {
intersect(simple1, (const _Line&) simple2, i);
} else {
@@ -335,9 +104,9 @@
Quadratic s2a;
int o2a = quadPart(cubic2, p2s, p2e, s2a);
Intersections locals;
- #if 0 && SK_DEBUG
- if (0.497026154 >= p1s && 0.497026535 <= p1e
- && 0.710440575 >= p2s && 0.710440956 <= p2e) {
+ #if ONE_OFF_DEBUG
+ if (tLimits[0][0] >= p1s && tLimits[0][1] <= p1e
+ && tLimits[1][0] >= p2s && tLimits[1][1] <= p2e) {
SkDebugf("t1=(%1.9g,%1.9g) o1=%d t2=(%1.9g,%1.9g) o2=%d\n",
p1s, p1e, o1a, p2s, p2e, o2a);
if (o1a == 2) {
@@ -356,7 +125,7 @@
}
Intersections xlocals;
intersectWithOrder(s1a, o1a, s2a, o2a, xlocals);
- SkDebugf("xlocals.fUsed=%d\n", xlocals.used());
+ SkDebugf("xlocals.fUsed=%d depth=%d\n", xlocals.used(), i.depth());
}
#endif
intersectWithOrder(s1a, o1a, s2a, o2a, locals);
@@ -367,16 +136,21 @@
_Point p1, p2;
xy_at_t(cubic1, to1, p1.x, p1.y);
xy_at_t(cubic2, to2, p2.x, p2.y);
- #if 0 && SK_DEBUG
+ #if ONE_OFF_DEBUG
SkDebugf("to1=%1.9g p1=(%1.9g,%1.9g) to2=%1.9g p2=(%1.9g,%1.9g) d=%1.9g\n",
to1, p1.x, p1.y, to2, p2.x, p2.y, p1.distance(p2));
#endif
- if (p1.approximatelyEqual(p2)) {
- i.insert(i.swapped() ? to2 : to1, i.swapped() ? to1 : to2);
+ if (p1.approximatelyEqualHalf(p2)) {
+ i.insertSwap(to1, to2, p1);
result = true;
} else {
result = doIntersect(cubic1, p1s, to1, p1e, cubic2, p2s, to2, p2e, i);
+ if (!result && p1.approximatelyEqual(p2)) {
+ i.insertSwap(to1, to2, p1);
+ SkDebugf("!!!\n");
+ result = true;
+ } else
// if both cubics curve in the same direction, the quadratic intersection
// may mark a range that does not contain the cubic intersection. If no
// intersection is found, look again including the t distance of the
@@ -431,9 +205,9 @@
const double t2 = t2s + (t2e - t2s) * tEnd2;
Quadratic s2;
int o2 = quadPart(cubic2, t2Start, t2, s2);
- #if 0 && SK_DEBUG
- if (0.497026154 >= t1Start && 0.497026535 <= t1
- && 0.710440575 + 0.0004 >= t2Start && 0.710440956 <= t2) {
+ #if ONE_OFF_DEBUG
+ if (tLimits[0][0] >= t1Start && tLimits[0][1] <= t1
+ && tLimits[1][0] >= t2Start && tLimits[1][1] <= t2) {
Cubic cSub1, cSub2;
sub_divide(cubic1, t1Start, tEnd1, cSub1);
sub_divide(cubic2, t2Start, tEnd2, cSub2);
@@ -455,31 +229,11 @@
xy_at_t(cubic1, to1, p1.x, p1.y);
xy_at_t(cubic2, to2, p2.x, p2.y);
if (p1.approximatelyEqual(p2)) {
- i.insert(i.swapped() ? to2 : to1, i.swapped() ? to1 : to2);
+ i.insert(to1, to2, p1);
} else {
- #if COMPUTE_DELTA
- double dt1, dt2;
- computeDelta(cubic1, to1, (t1e - t1s), cubic2, to2, (t2e - t2s), dt1, dt2);
- double scale = precisionScale;
- if (dt1 > 0.125 || dt2 > 0.125) {
- scale /= 2;
- SkDebugf("%s scale=%1.9g\n", __FUNCTION__, scale);
- }
-#if SK_DEBUG
- ++debugDepth;
- SkASSERT(debugDepth < 10);
-#endif
- i.swap();
- intersect2(cubic2, SkTMax(to2 - dt2, 0.), SkTMin(to2 + dt2, 1.),
- cubic1, SkTMax(to1 - dt1, 0.), SkTMin(to1 + dt1, 1.), scale, i);
- i.swap();
-#if SK_DEBUG
- --debugDepth;
-#endif
- #else
- #if 0 && SK_DEBUG
- if (0.497026154 >= t1Start && 0.497026535 <= t1
- && 0.710440575 >= t2Start && 0.710440956 <= t2) {
+ #if ONE_OFF_DEBUG
+ if (tLimits[0][0] >= t1Start && tLimits[0][1] <= t1
+ && tLimits[1][0] >= t2Start && tLimits[1][1] <= t2) {
SkDebugf("t1=(%1.9g,%1.9g) t2=(%1.9g,%1.9g)\n",
t1Start, t1, t2Start, t2);
}
@@ -493,17 +247,24 @@
bumpForRetry(locals.fT[0][tIdx], locals.fT[1][tIdx], b1s, b1e, b2s, b2e);
doIntersect(cubic1, b1s, to1, b1e, cubic2, b2s, to2, b2e, i);
}
- #endif
}
}
- if (locals.coincidentUsed()) {
- SkASSERT(locals.coincidentUsed() == 2);
+ int coincidentCount = locals.coincidentUsed();
+ if (coincidentCount) {
+ // FIXME: one day, we'll probably need to allow coincident + non-coincident pts
+ SkASSERT(coincidentCount == locals.used());
+ SkASSERT(coincidentCount == 2);
double coTs[2][2];
- for (int tIdx = 0; tIdx < locals.coincidentUsed(); ++tIdx) {
- coTs[0][tIdx] = t1Start + (t1 - t1Start) * locals.fCoincidentT[0][tIdx];
- coTs[1][tIdx] = t2Start + (t2 - t2Start) * locals.fCoincidentT[1][tIdx];
+ for (int tIdx = 0; tIdx < coincidentCount; ++tIdx) {
+ if (locals.fIsCoincident[0] & (1 << tIdx)) {
+ coTs[0][tIdx] = t1Start + (t1 - t1Start) * locals.fT[0][tIdx];
+ }
+ if (locals.fIsCoincident[1] & (1 << tIdx)) {
+ coTs[1][tIdx] = t2Start + (t2 - t2Start) * locals.fT[1][tIdx];
+ }
}
- i.addCoincident(coTs[0][0], coTs[0][1], coTs[1][0], coTs[1][1]);
+ i.insertCoincidentPair(coTs[0][0], coTs[0][1], coTs[1][0], coTs[1][1],
+ locals.fPt[0], locals.fPt[1]);
}
t2Start = t2;
}
@@ -562,21 +323,113 @@
tMin = SkTMin(tMin, local2.fT[0][index]);
tMax = SkTMax(tMax, local2.fT[0][index]);
}
-#if SK_DEBUG && COMPUTE_DELTA
- debugDepth = 0;
-#endif
return intersect2(cubic1, start ? 0 : 1, start ? 1.0 / precisionUnit : 1 - 1.0 / precisionUnit,
cubic2, tMin, tMax, 1, i);
}
+// this flavor centers potential intersections recursively. In contrast, '2' may inadvertently
+// chase intersections near quadratic ends, requiring odd hacks to find them.
+static bool intersect3(const Cubic& cubic1, double t1s, double t1e, const Cubic& cubic2,
+ double t2s, double t2e, double precisionScale, Intersections& i) {
+ i.upDepth();
+ bool result = false;
+ Cubic c1, c2;
+ sub_divide(cubic1, t1s, t1e, c1);
+ sub_divide(cubic2, t2s, t2e, c2);
+ SkTDArray<double> ts1;
+ cubic_to_quadratics(c1, calcPrecision(c1) * precisionScale, ts1);
+ SkTDArray<double> ts2;
+ cubic_to_quadratics(c2, calcPrecision(c2) * precisionScale, ts2);
+ double t1Start = t1s;
+ int ts1Count = ts1.count();
+ for (int i1 = 0; i1 <= ts1Count; ++i1) {
+ const double tEnd1 = i1 < ts1Count ? ts1[i1] : 1;
+ const double t1 = t1s + (t1e - t1s) * tEnd1;
+ Quadratic s1;
+ int o1 = quadPart(cubic1, t1Start, t1, s1);
+ double t2Start = t2s;
+ int ts2Count = ts2.count();
+ for (int i2 = 0; i2 <= ts2Count; ++i2) {
+ const double tEnd2 = i2 < ts2Count ? ts2[i2] : 1;
+ const double t2 = t2s + (t2e - t2s) * tEnd2;
+ Quadratic s2;
+ int o2 = quadPart(cubic2, t2Start, t2, s2);
+ Intersections locals;
+ intersectWithOrder(s1, o1, s2, o2, locals);
+ double coStart[2] = { -1 };
+ _Point coPoint;
+ for (int tIdx = 0; tIdx < locals.used(); ++tIdx) {
+ double to1 = t1Start + (t1 - t1Start) * locals.fT[0][tIdx];
+ double to2 = t2Start + (t2 - t2Start) * locals.fT[1][tIdx];
+ // if the computed t is not sufficiently precise, iterate
+ _Point p1, p2;
+ xy_at_t(cubic1, to1, p1.x, p1.y);
+ xy_at_t(cubic2, to2, p2.x, p2.y);
+ if (p1.approximatelyEqual(p2)) {
+ if (locals.fIsCoincident[0] & 1 << tIdx) {
+ if (coStart[0] < 0) {
+ coStart[0] = to1;
+ coStart[1] = to2;
+ coPoint = p1;
+ } else {
+ i.insertCoincidentPair(coStart[0], to1, coStart[1], to2, coPoint, p1);
+ coStart[0] = -1;
+ }
+ } else {
+ i.insert(to1, to2, p1);
+ }
+ result = true;
+ } else {
+ double offset = precisionScale / 16; // FIME: const is arbitrary -- test & refine
+ double c1Min = SkTMax(0., to1 - offset);
+ double c1Max = SkTMin(1., to1 + offset);
+ double c2Min = SkTMax(0., to2 - offset);
+ double c2Max = SkTMin(1., to2 + offset);
+ bool found = intersect3(cubic1, c1Min, c1Max, cubic2, c2Min, c2Max, offset, i);
+ if (false && !found) {
+ // either offset was overagressive or cubics didn't really intersect
+ // if they didn't intersect, then quad tangents ought to be nearly parallel
+ offset = precisionScale / 2; // try much less agressive offset
+ c1Min = SkTMax(0., to1 - offset);
+ c1Max = SkTMin(1., to1 + offset);
+ c2Min = SkTMax(0., to2 - offset);
+ c2Max = SkTMin(1., to2 + offset);
+ found = intersect3(cubic1, c1Min, c1Max, cubic2, c2Min, c2Max, offset, i);
+ if (found) {
+ SkDebugf("%s *** over-aggressive? offset=%1.9g depth=%d\n", __FUNCTION__,
+ offset, i.depth());
+ }
+ // try parallel measure
+ _Point d1 = dxdy_at_t(cubic1, to1);
+ _Point d2 = dxdy_at_t(cubic2, to2);
+ double shallow = d1.cross(d2);
+ #if 1 || ONE_OFF_DEBUG // not sure this is worth debugging
+ if (!approximately_zero(shallow)) {
+ SkDebugf("%s *** near-miss? shallow=%1.9g depth=%d\n", __FUNCTION__,
+ offset, i.depth());
+ }
+ #endif
+ if (i.depth() == 1 && shallow < 0.6) {
+ SkDebugf("%s !!! near-miss? shallow=%1.9g depth=%d\n", __FUNCTION__,
+ offset, i.depth());
+ }
+ }
+ }
+ }
+ SkASSERT(coStart[0] == -1);
+ t2Start = t2;
+ }
+ t1Start = t1;
+ }
+ i.downDepth();
+ return result;
+}
+
// FIXME: add intersection of convex hull on cubics' ends with the opposite cubic. The hull line
// segments can be constructed to be only as long as the calculated precision suggests. If the hull
// line segments intersect the cubic, then use the intersections to construct a subdivision for
// quadratic curve fitting.
bool intersect2(const Cubic& c1, const Cubic& c2, Intersections& i) {
-#if SK_DEBUG && COMPUTE_DELTA
- debugDepth = 0;
-#endif
bool result = intersect2(c1, 0, 1, c2, 0, 1, 1, i);
// FIXME: pass in cached bounds from caller
_Rect c1Bounds, c2Bounds;
@@ -591,6 +444,21 @@
return result;
}
+bool intersect3(const Cubic& c1, const Cubic& c2, Intersections& i) {
+ bool result = intersect3(c1, 0, 1, c2, 0, 1, 1, i);
+ // FIXME: pass in cached bounds from caller
+ _Rect c1Bounds, c2Bounds;
+ c1Bounds.setBounds(c1); // OPTIMIZE use setRawBounds ?
+ c2Bounds.setBounds(c2);
+ result |= intersectEnd(c1, false, c2, c2Bounds, i);
+ result |= intersectEnd(c1, true, c2, c2Bounds, i);
+ i.swap();
+ result |= intersectEnd(c2, false, c1, c1Bounds, i);
+ result |= intersectEnd(c2, true, c1, c1Bounds, i);
+ i.swap();
+ return result;
+}
+
int intersect(const Cubic& cubic, const Quadratic& quad, Intersections& i) {
SkTDArray<double> ts;
double precision = calcPrecision(cubic);
@@ -607,9 +475,7 @@
intersect2(q1, quad, locals);
for (int tIdx = 0; tIdx < locals.used(); ++tIdx) {
double globalT = tStart + (t - tStart) * locals.fT[0][tIdx];
- i.insertOne(globalT, 0);
- globalT = locals.fT[1][tIdx];
- i.insertOne(globalT, 1);
+ i.insert(globalT, locals.fT[1][tIdx], locals.fPt[tIdx]);
}
tStart = t;
}
@@ -648,7 +514,7 @@
}
double to1 = t1Start + (t1 - t1Start) * t1sect;
double to2 = t2Start + (t2 - t2Start) * t2sect;
- i.insert(to1, to2);
+ i.insert(to1, to2, locals.fPt[tIdx]);
}
t2Start = t2;
}
diff --git a/experimental/Intersection/CubicIntersection_Test.cpp b/experimental/Intersection/CubicIntersection_Test.cpp
index ae52a25..381881c 100644
--- a/experimental/Intersection/CubicIntersection_Test.cpp
+++ b/experimental/Intersection/CubicIntersection_Test.cpp
@@ -13,7 +13,7 @@
const int firstCubicIntersectionTest = 9;
-void CubicIntersection_Test() {
+static void standardTestCases() {
for (size_t index = firstCubicIntersectionTest; index < tests_count; ++index) {
const Cubic& cubic1 = tests[index][0];
const Cubic& cubic2 = tests[index][1];
@@ -57,60 +57,22 @@
}
}
-#define ONE_OFF_DEBUG 0
-
-static void oneOff(const Cubic& cubic1, const Cubic& cubic2) {
- SkTDArray<Quadratic> quads1;
- cubic_to_quadratics(cubic1, calcPrecision(cubic1), quads1);
-#if ONE_OFF_DEBUG
- for (int index = 0; index < quads1.count(); ++index) {
- const Quadratic& q = quads1[index];
- SkDebugf(" {{%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}},\n", q[0].x, q[0].y,
- q[1].x, q[1].y, q[2].x, q[2].y);
- }
- SkDebugf("\n");
-#endif
- SkTDArray<Quadratic> quads2;
- cubic_to_quadratics(cubic2, calcPrecision(cubic2), quads2);
-#if ONE_OFF_DEBUG
- for (int index = 0; index < quads2.count(); ++index) {
- const Quadratic& q = quads2[index];
- SkDebugf(" {{%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}},\n", q[0].x, q[0].y,
- q[1].x, q[1].y, q[2].x, q[2].y);
- }
- SkDebugf("\n");
-#endif
- Intersections intersections2;
- intersect2(cubic1, cubic2, intersections2);
- for (int pt = 0; pt < intersections2.used(); ++pt) {
- double tt1 = intersections2.fT[0][pt];
- _Point xy1, xy2;
- xy_at_t(cubic1, tt1, xy1.x, xy1.y);
- int pt2 = intersections2.fFlip ? intersections2.used() - pt - 1 : pt;
- double tt2 = intersections2.fT[1][pt2];
- xy_at_t(cubic2, tt2, xy2.x, xy2.y);
-#if ONE_OFF_DEBUG
- SkDebugf("%s t1=%1.9g (%1.9g, %1.9g) (%1.9g, %1.9g) t2=%1.9g\n", __FUNCTION__,
- tt1, xy1.x, xy1.y, xy2.x, xy2.y, tt2);
-#endif
- SkASSERT(xy1.approximatelyEqual(xy2));
- }
- for (int pt = 0; pt < intersections2.coincidentUsed(); ++pt) {
- double tt1 = intersections2.fCoincidentT[0][pt];
- _Point xy1, xy2;
- xy_at_t(cubic1, tt1, xy1.x, xy1.y);
- int pt2 = intersections2.fFlip ? intersections2.used() - pt - 1 : pt;
- double tt2 = intersections2.fCoincidentT[1][pt2];
- xy_at_t(cubic2, tt2, xy2.x, xy2.y);
-#if ONE_OFF_DEBUG
- SkDebugf("%s t1=%1.9g (%1.9g, %1.9g) (%1.9g, %1.9g) t2=%1.9g\n", __FUNCTION__,
- tt1, xy1.x, xy1.y, xy2.x, xy2.y, tt2);
-#endif
- SkASSERT(xy1.approximatelyEqual(xy2));
- }
-}
-
static const Cubic testSet[] = {
+{{0,1}, {4,5}, {1,0}, {5,3}},
+{{0,1}, {3,5}, {1,0}, {5,4}},
+
+{{0, 1}, {1, 6}, {1, 0}, {1, 0}},
+{{0, 1}, {0, 1}, {1, 0}, {6, 1}},
+
+{{0,1}, {3,4}, {1,0}, {5,1}},
+{{0,1}, {1,5}, {1,0}, {4,3}},
+
+{{0,1}, {1,2}, {1,0}, {6,1}},
+{{0,1}, {1,6}, {1,0}, {2,1}},
+
+{{0,1}, {0,5}, {1,0}, {4,0}},
+{{0,1}, {0,4}, {1,0}, {5,0}},
+
{{0,1}, {3,4}, {1,0}, {3,0}},
{{0,1}, {0,3}, {1,0}, {4,3}},
@@ -169,22 +131,182 @@
const size_t testSetCount = sizeof(testSet) / sizeof(testSet[0]);
-void CubicIntersection_OneOffTest() {
- for (size_t outer = 0; outer < testSetCount - 1; ++outer) {
+static void oneOff(const Cubic& cubic1, const Cubic& cubic2) {
+ SkTDArray<Quadratic> quads1;
+ cubic_to_quadratics(cubic1, calcPrecision(cubic1), quads1);
#if ONE_OFF_DEBUG
- SkDebugf("%s quads1[%d]\n", __FUNCTION__, outer);
+ for (int index = 0; index < quads1.count(); ++index) {
+ const Quadratic& q = quads1[index];
+ SkDebugf(" {{%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}},\n", q[0].x, q[0].y,
+ q[1].x, q[1].y, q[2].x, q[2].y);
+ }
+ SkDebugf("\n");
#endif
- const Cubic& cubic1 = testSet[outer];
- for (size_t inner = outer + 1; inner < testSetCount; ++inner) {
+ SkTDArray<Quadratic> quads2;
+ cubic_to_quadratics(cubic2, calcPrecision(cubic2), quads2);
#if ONE_OFF_DEBUG
- SkDebugf("%s quads2[%d]\n", __FUNCTION__, inner);
+ for (int index = 0; index < quads2.count(); ++index) {
+ const Quadratic& q = quads2[index];
+ SkDebugf(" {{%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}},\n", q[0].x, q[0].y,
+ q[1].x, q[1].y, q[2].x, q[2].y);
+ }
+ SkDebugf("\n");
#endif
- const Cubic& cubic2 = testSet[inner];
- oneOff(cubic1, cubic2);
+ Intersections intersections2, intersections3;
+ intersect2(cubic1, cubic2, intersections2);
+ intersect3(cubic1, cubic2, intersections3);
+ int pt1, pt2, pt3;
+ bool found;
+ double tt1, tt2, last = -1;
+ _Point xy1, xy2;
+ for (pt1 = 0; pt1 < intersections2.used(); ++pt1) {
+ tt1 = intersections2.fT[0][pt1];
+ SkASSERT(!approximately_equal(last, tt1));
+ last = tt1;
+ xy_at_t(cubic1, tt1, xy1.x, xy1.y);
+ pt2 = intersections2.fFlip ? intersections2.used() - pt1 - 1 : pt1;
+ tt2 = intersections2.fT[1][pt2];
+ xy_at_t(cubic2, tt2, xy2.x, xy2.y);
+#if ONE_OFF_DEBUG
+ SkDebugf("%s t1=%1.9g (%1.9g, %1.9g) (%1.9g, %1.9g) (%1.9g, %1.9g) t2=%1.9g\n",
+ __FUNCTION__, tt1, xy1.x, xy1.y, intersections2.fPt[pt1].x,
+ intersections2.fPt[pt1].y, xy2.x, xy2.y, tt2);
+#endif
+ SkASSERT(xy1.approximatelyEqual(xy2));
+#if SK_DEBUG
+ found = false;
+ for (pt3 = 0; pt3 < intersections3.used(); ++pt3) {
+ if (roughly_equal(tt1, intersections3.fT[0][pt3])) {
+ found = true;
+ break;
+ }
+ }
+ SkASSERT(found);
+#endif
+ }
+ last = -1;
+ for (pt3 = 0; pt3 < intersections3.used(); ++pt3) {
+ found = false;
+ double tt3 = intersections3.fT[0][pt3];
+ SkASSERT(!approximately_equal(last, tt3));
+ last = tt3;
+ for (pt1 = 0; pt1 < intersections2.used(); ++pt1) {
+ if (approximately_equal(tt3, intersections2.fT[0][pt1])) {
+ found = true;
+ break;
+ }
+ }
+ if (!found) {
+ tt1 = intersections3.fT[0][pt3];
+ xy_at_t(cubic1, tt1, xy1.x, xy1.y);
+ pt2 = intersections3.fFlip ? intersections3.used() - pt3 - 1 : pt3;
+ tt2 = intersections3.fT[1][pt2];
+ xy_at_t(cubic2, tt2, xy2.x, xy2.y);
+ #if ONE_OFF_DEBUG
+ SkDebugf("%s t3=%1.9g (%1.9g, %1.9g) (%1.9g, %1.9g) (%1.9g, %1.9g) t2=%1.9g\n",
+ __FUNCTION__, tt1, xy1.x, xy1.y, intersections3.fPt[pt1].x,
+ intersections3.fPt[pt1].y, xy2.x, xy2.y, tt2);
+ #endif
+ SkASSERT(xy1.approximatelyEqual(xy2));
+ SkDebugf("%s missing in intersect2\n", __FUNCTION__);
}
}
}
+static void oneOff3(const Cubic& cubic1, const Cubic& cubic2) {
+ SkTDArray<Quadratic> quads1;
+ cubic_to_quadratics(cubic1, calcPrecision(cubic1), quads1);
+#if ONE_OFF_DEBUG
+ for (int index = 0; index < quads1.count(); ++index) {
+ const Quadratic& q = quads1[index];
+ SkDebugf(" {{%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}},\n", q[0].x, q[0].y,
+ q[1].x, q[1].y, q[2].x, q[2].y);
+ }
+ SkDebugf("\n");
+#endif
+ SkTDArray<Quadratic> quads2;
+ cubic_to_quadratics(cubic2, calcPrecision(cubic2), quads2);
+#if ONE_OFF_DEBUG
+ for (int index = 0; index < quads2.count(); ++index) {
+ const Quadratic& q = quads2[index];
+ SkDebugf(" {{%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}},\n", q[0].x, q[0].y,
+ q[1].x, q[1].y, q[2].x, q[2].y);
+ }
+ SkDebugf("\n");
+#endif
+ Intersections intersections3;
+ intersect3(cubic1, cubic2, intersections3);
+ int pt2, pt3;
+ double tt1, tt2, last = -1;
+ _Point xy1, xy2;
+ for (pt3 = 0; pt3 < intersections3.used(); ++pt3) {
+ double tt3 = intersections3.fT[0][pt3];
+ SkASSERT(!approximately_equal(last, tt3));
+ last = tt3;
+ tt1 = intersections3.fT[0][pt3];
+ xy_at_t(cubic1, tt1, xy1.x, xy1.y);
+ pt2 = intersections3.fFlip ? intersections3.used() - pt3 - 1 : pt3;
+ tt2 = intersections3.fT[1][pt2];
+ xy_at_t(cubic2, tt2, xy2.x, xy2.y);
+#if ONE_OFF_DEBUG
+ SkDebugf("%s t3=%1.9g (%1.9g, %1.9g) (%1.9g, %1.9g) (%1.9g, %1.9g) t2=%1.9g\n",
+ __FUNCTION__, tt1, xy1.x, xy1.y, intersections3.fPt[pt3].x,
+ intersections3.fPt[pt3].y, xy2.x, xy2.y, tt2);
+#endif
+ SkASSERT(xy1.approximatelyEqual(xy2));
+ }
+}
+
+static int fails[][2] = { {0, 23}, // fails in intersect2 recursing
+ {2, 7}, // answers differ, but neither is correct ('3' is closer)
+ {3, 26}, // fails in intersect2 recursing
+ {4, 9}, // fails in intersect2 recursing
+ {4, 10}, // fails in intersect2 recursing
+ {10, 17}, // fails in intersect2 recursing
+ {12, 14}, // loops indefinitely
+ {12, 21}, // fails in intersect2 recursing
+ {13, 21}, // fails in intersect2 recursing
+ {14, 21}, // fails in intersect2 recursing
+ {17, 25}, // fails in intersect2 recursing
+ {23, 25}, // fails in intersect2 recursing
+};
+
+static int failCount = sizeof(fails) / sizeof(fails[0]);
+
+static void oneOff(int outer, int inner) {
+ const Cubic& cubic1 = testSet[outer];
+ const Cubic& cubic2 = testSet[inner];
+ bool failing = false;
+ for (int i = 0; i < failCount; ++i) {
+ if ((fails[i][0] == outer && fails[i][1] == inner)
+ || (fails[i][1] == outer && fails[i][0] == inner)) {
+ failing = true;
+ break;
+ }
+ }
+ if (!failing) {
+ oneOff(cubic1, cubic2);
+ } else {
+ oneOff3(cubic1, cubic2);
+ }
+}
+
+void CubicIntersection_OneOffTest() {
+ oneOff(12, 14);
+}
+
+static void oneOffTests() {
+ for (size_t outer = 0; outer < testSetCount - 1; ++outer) {
+ for (size_t inner = outer + 1; inner < testSetCount; ++inner) {
+ oneOff(outer, inner);
+ }
+ }
+}
+
+void CubicIntersection_OneOffTests() {
+ oneOffTests();
+}
+
#define DEBUG_CRASH 0
class CubicChopper {
@@ -400,12 +522,13 @@
}
void CubicIntersection_IntersectionFinder() {
- Cubic cubic1 = {{0,1}, {3,4}, {1,0}, {3,0}};
- Cubic cubic2 = {{0,1}, {0,3}, {1,0}, {4,3}};
- double t1Seed = 0.496;
- double t2Seed = 0.711;
- double t1Step = 0.1;
- double t2Step = 0.1;
+ const Cubic& cubic1 = testSet[2];
+ const Cubic& cubic2 = testSet[7];
+
+ double t1Seed = 0.254;
+ double t2Seed = 0.245;
+ double t1Step = 0.01;
+ double t2Step = 0.01;
_Point t1[3], t2[3];
bool toggle = true;
do {
@@ -478,12 +601,27 @@
}
SkDebugf("%s t1=(%1.9g<%1.9g<%1.9g) t2=(%1.9g<%1.9g<%1.9g)\n", __FUNCTION__,
t10, t1Seed, t12, t20, t2Seed, t22);
+ _Point p10 = xy_at_t(cubic1, t10);
+ _Point p1Seed = xy_at_t(cubic1, t1Seed);
+ _Point p12 = xy_at_t(cubic1, t12);
+ SkDebugf("%s p1=(%1.9g,%1.9g)<(%1.9g,%1.9g)<(%1.9g,%1.9g)\n", __FUNCTION__,
+ p10.x, p10.y, p1Seed.x, p1Seed.y, p12.x, p12.y);
+ _Point p20 = xy_at_t(cubic2, t20);
+ _Point p2Seed = xy_at_t(cubic2, t2Seed);
+ _Point p22 = xy_at_t(cubic2, t22);
+ SkDebugf("%s p2=(%1.9g,%1.9g)<(%1.9g,%1.9g)<(%1.9g,%1.9g)\n", __FUNCTION__,
+ p20.x, p20.y, p2Seed.x, p2Seed.y, p22.x, p22.y);
}
+static void coincidentTest() {
#if 0
-void CubicIntersection_CoincidentTest() {
Cubic cubic1 = {{0, 1}, {0, 2}, {1, 0}, {1, 0}};
Cubic cubic2 = {{0, 1}, {0, 2}, {1, 0}, {6, 1}};
-
-}
#endif
+}
+
+void CubicIntersection_Test() {
+ oneOffTests();
+ coincidentTest();
+ standardTestCases();
+}
diff --git a/experimental/Intersection/CubicReduceOrder.cpp b/experimental/Intersection/CubicReduceOrder.cpp
index 29920ab..bd1356a 100644
--- a/experimental/Intersection/CubicReduceOrder.cpp
+++ b/experimental/Intersection/CubicReduceOrder.cpp
@@ -205,10 +205,20 @@
}
}
for (index = 0; index < 4; ++index) {
- if (AlmostEqualUlps(cubic[index].x, cubic[minX].x)) {
+ double cx = cubic[index].x;
+ double cy = cubic[index].y;
+ double denom = SkTMax(fabs(cx), SkTMax(fabs(cy),
+ SkTMax(fabs(cubic[minX].x), fabs(cubic[minY].y))));
+ if (denom == 0) {
+ minXSet |= 1 << index;
+ minYSet |= 1 << index;
+ continue;
+ }
+ double inv = 1 / denom;
+ if (approximately_equal_half(cx * inv, cubic[minX].x * inv)) {
minXSet |= 1 << index;
}
- if (AlmostEqualUlps(cubic[index].y, cubic[minY].y)) {
+ if (approximately_equal_half(cy * inv, cubic[minY].y * inv)) {
minYSet |= 1 << index;
}
}
diff --git a/experimental/Intersection/CubicToQuadratics.cpp b/experimental/Intersection/CubicToQuadratics.cpp
index 66288b4..dc4b51b 100644
--- a/experimental/Intersection/CubicToQuadratics.cpp
+++ b/experimental/Intersection/CubicToQuadratics.cpp
@@ -149,11 +149,23 @@
double inflectT[2];
int inflections = find_cubic_inflections(cubic, inflectT);
SkASSERT(inflections <= 2);
+ CubicPair pair;
+ if (inflections == 1) {
+ chop_at(cubic, pair, inflectT[0]);
+ int orderP1 = reduceOrder(pair.first(), reduced, kReduceOrder_NoQuadraticsAllowed);
+ if (orderP1 < 2) {
+ --inflections;
+ } else {
+ int orderP2 = reduceOrder(pair.second(), reduced, kReduceOrder_NoQuadraticsAllowed);
+ if (orderP2 < 2) {
+ --inflections;
+ }
+ }
+ }
if (inflections == 0 && addSimpleTs(cubic, precision, ts)) {
return;
}
if (inflections == 1) {
- CubicPair pair;
chop_at(cubic, pair, inflectT[0]);
addTs(pair.first(), precision, 0, inflectT[0], ts);
addTs(pair.second(), precision, inflectT[0], 1, ts);
diff --git a/experimental/Intersection/CubicToQuadratics_Test.cpp b/experimental/Intersection/CubicToQuadratics_Test.cpp
index 9688164..b7e1252 100644
--- a/experimental/Intersection/CubicToQuadratics_Test.cpp
+++ b/experimental/Intersection/CubicToQuadratics_Test.cpp
@@ -129,6 +129,9 @@
}
static Cubic locals[] = {
+{{0, 1}, {1.9274705288631189e-19, 1.0000000000000002}, {0.0017190297609673323, 0.99828097023903239},
+ {0.0053709083094631276, 0.99505672974365911}},
+
{{14.5975863, 41.632436}, {16.3518929, 26.2639684}, {18.5165519, 7.68775139}, {8.03767257, 89.1628526}},
{{69.7292014, 38.6877352}, {24.7648688, 23.1501713}, {84.9283191, 90.2588441}, {80.392774, 61.3533852}},
{{
@@ -152,20 +155,31 @@
#define TEST_AVERAGE_END_POINTS 0 // must take const off to test
extern const bool AVERAGE_END_POINTS;
-void CubicsToQuadratics_RandTest() {
+static void oneOff(size_t x) {
+ const Cubic& cubic = locals[x];
+ const SkPoint skcubic[4] = {{(float) cubic[0].x, (float) cubic[0].y},
+ {(float) cubic[1].x, (float) cubic[1].y}, {(float) cubic[2].x, (float) cubic[2].y},
+ {(float) cubic[3].x, (float) cubic[3].y}};
+ SkScalar skinflect[2];
+ int skin = SkFindCubicInflections(skcubic, skinflect);
+ SkDebugf("%s %d %1.9g\n", __FUNCTION__, skin, skinflect[0]);
+ SkTDArray<Quadratic> quads;
+ double precision = calcPrecision(cubic);
+ (void) cubic_to_quadratics(cubic, precision, quads);
+ SkDebugf("%s quads=%d\n", __FUNCTION__, quads.count());
+}
+
+void CubicsToQuadratics_OneOffTests() {
for (size_t x = 0; x < localsCount; ++x) {
- const Cubic& cubic = locals[x];
- const SkPoint skcubic[4] = {{(float) cubic[0].x, (float) cubic[0].y},
- {(float) cubic[1].x, (float) cubic[1].y}, {(float) cubic[2].x, (float) cubic[2].y},
- {(float) cubic[3].x, (float) cubic[3].y}};
- SkScalar skinflect[2];
- int skin = SkFindCubicInflections(skcubic, skinflect);
- SkDebugf("%s %d %1.9g\n", __FUNCTION__, skin, skinflect[0]);
- SkTDArray<Quadratic> quads;
- double precision = calcPrecision(cubic);
- (void) cubic_to_quadratics(cubic, precision, quads);
- SkDebugf("%s quads=%d\n", __FUNCTION__, quads.count());
+ oneOff(x);
}
+}
+
+void CubicsToQuadratics_OneOffTest() {
+ oneOff(0);
+}
+
+void CubicsToQuadratics_RandTest() {
srand(0);
const int arrayMax = 8;
const int sampleMax = 10;
diff --git a/experimental/Intersection/CubicUtilities.cpp b/experimental/Intersection/CubicUtilities.cpp
index 78be8df..0c7f2c1 100644
--- a/experimental/Intersection/CubicUtilities.cpp
+++ b/experimental/Intersection/CubicUtilities.cpp
@@ -5,6 +5,7 @@
* found in the LICENSE file.
*/
#include "CubicUtilities.h"
+#include "Extrema.h"
#include "QuadraticUtilities.h"
const int precisionUnit = 256; // FIXME: arbitrary -- should try different values in test framework
@@ -112,7 +113,8 @@
bzero(str, sizeof(str));
sprintf(str, "Solve[%1.19g x^3 + %1.19g x^2 + %1.19g x + %1.19g == 0, x]", A, B, C, D);
#endif
- if (approximately_zero_when_compared_to(A, B)
+ if (approximately_zero(A)
+ && approximately_zero_when_compared_to(A, B)
&& approximately_zero_when_compared_to(A, C)
&& approximately_zero_when_compared_to(A, D)) { // we're just a quadratic
return quadraticRootsReal(B, C, D, s);
@@ -235,6 +237,11 @@
dxdy.y = derivativeAtT(&cubic[0].y, t);
}
+_Point dxdy_at_t(const Cubic& cubic, double t) {
+ _Point result = { derivativeAtT(&cubic[0].x, t), derivativeAtT(&cubic[0].y, t) };
+ return result;
+}
+
int find_cubic_inflections(const Cubic& src, double tValues[])
{
double Ax = src[1].x - src[0].x;
@@ -273,7 +280,29 @@
}
#endif
-void xy_at_t(const Cubic& cubic, double t, double& x, double& y) {
+_Point top(const Cubic& cubic, double startT, double endT) {
+ Cubic sub;
+ sub_divide(cubic, startT, endT, sub);
+ _Point topPt = sub[0];
+ if (topPt.y > sub[3].y || (topPt.y == sub[3].y && topPt.x > sub[3].x)) {
+ topPt = sub[3];
+ }
+ double extremeTs[2];
+ if (!between(sub[0].y, sub[1].y, sub[3].y) && !between(sub[0].y, sub[2].y, sub[3].y)) {
+ int roots = findExtrema(sub[0].y, sub[1].y, sub[2].y, sub[3].y, extremeTs);
+ for (int index = 0; index < roots; ++index) {
+ _Point mid;
+ double t = startT + (endT - startT) * extremeTs[index];
+ xy_at_t(cubic, t, mid.x, mid.y);
+ if (topPt.y > mid.y || (topPt.y == mid.y && topPt.x > mid.x)) {
+ topPt = mid;
+ }
+ }
+ }
+ return topPt;
+}
+
+_Point xy_at_t(const Cubic& cubic, double t) {
double one_t = 1 - t;
double one_t2 = one_t * one_t;
double a = one_t2 * one_t;
@@ -281,10 +310,19 @@
double t2 = t * t;
double c = 3 * one_t * t2;
double d = t2 * t;
+ _Point result = {a * cubic[0].x + b * cubic[1].x + c * cubic[2].x + d * cubic[3].x,
+ a * cubic[0].y + b * cubic[1].y + c * cubic[2].y + d * cubic[3].y};
+ return result;
+}
+
+
+void xy_at_t(const Cubic& cubic, double t, double& x, double& y) {
+ _Point xy = xy_at_t(cubic, t);
if (&x) {
- x = a * cubic[0].x + b * cubic[1].x + c * cubic[2].x + d * cubic[3].x;
+ x = xy.x;
}
if (&y) {
- y = a * cubic[0].y + b * cubic[1].y + c * cubic[2].y + d * cubic[3].y;
+ y = xy.y;
}
}
+
diff --git a/experimental/Intersection/CubicUtilities.h b/experimental/Intersection/CubicUtilities.h
index f3c8e64..abfb433 100644
--- a/experimental/Intersection/CubicUtilities.h
+++ b/experimental/Intersection/CubicUtilities.h
@@ -26,10 +26,13 @@
double dx_at_t(const Cubic& , double t);
double dy_at_t(const Cubic& , double t);
void dxdy_at_t(const Cubic& , double t, _Point& y);
+_Point dxdy_at_t(const Cubic& cubic, double t);
int find_cubic_inflections(const Cubic& src, double tValues[]);
bool rotate(const Cubic& cubic, int zero, int index, Cubic& rotPath);
void sub_divide(const Cubic& src, double t1, double t2, Cubic& dst);
+_Point top(const Cubic& , double startT, double endT);
void xy_at_t(const Cubic& , double t, double& x, double& y);
+_Point xy_at_t(const Cubic& , double t);
extern const int precisionUnit;
diff --git a/experimental/Intersection/CurveIntersection.h b/experimental/Intersection/CurveIntersection.h
index 34cd6fb..b67ea7e 100644
--- a/experimental/Intersection/CurveIntersection.h
+++ b/experimental/Intersection/CurveIntersection.h
@@ -47,6 +47,8 @@
bool intersect(const Cubic& cubic1, const Cubic& cubic2, Intersections& );
// the following flavor uses quadratic approximation instead of convex hulls
bool intersect2(const Cubic& cubic1, const Cubic& cubic2, Intersections& );
+// like '2', but iterates on centers instead of possible edges
+bool intersect3(const Cubic& cubic1, const Cubic& cubic2, Intersections& );
bool intersect(const Cubic& cubic, Intersections& i); // return true if cubic self-intersects
int intersect(const Cubic& cubic, const Quadratic& quad, Intersections& );
int intersect(const Cubic& cubic, const _Line& line, Intersections& );
diff --git a/experimental/Intersection/DataTypes.h b/experimental/Intersection/DataTypes.h
index 026d497..09c4378 100644
--- a/experimental/Intersection/DataTypes.h
+++ b/experimental/Intersection/DataTypes.h
@@ -10,7 +10,9 @@
#include <float.h> // for FLT_EPSILON
#include <math.h> // for fabs, sqrt
-#include "SkTypes.h"
+#include "SkPoint.h"
+
+#define ONE_OFF_DEBUG 0
// FIXME: move these into SkTypes.h
template <typename T> inline T SkTMax(T a, T b) {
@@ -33,22 +35,24 @@
// FLT_EPSILON == 1.19209290E-07 == 1 / (2 ^ 23)
const double FLT_EPSILON_CUBED = FLT_EPSILON * FLT_EPSILON * FLT_EPSILON;
+const double FLT_EPSILON_HALF = FLT_EPSILON / 2;
const double FLT_EPSILON_SQUARED = FLT_EPSILON * FLT_EPSILON;
const double FLT_EPSILON_SQRT = sqrt(FLT_EPSILON);
const double FLT_EPSILON_INVERSE = 1 / FLT_EPSILON;
-inline bool approximately_zero(double x) {
+#ifdef SK_DEBUG
+const double ROUGH_EPSILON = FLT_EPSILON * 16;
+#endif
+inline bool approximately_zero(double x) {
return fabs(x) < FLT_EPSILON;
}
inline bool precisely_zero(double x) {
-
return fabs(x) < DBL_EPSILON;
}
inline bool approximately_zero(float x) {
-
return fabs(x) < FLT_EPSILON;
}
@@ -56,6 +60,10 @@
return fabs(x) < FLT_EPSILON_CUBED;
}
+inline bool approximately_zero_half(double x) {
+ return fabs(x) < FLT_EPSILON_HALF;
+}
+
inline bool approximately_zero_squared(double x) {
return fabs(x) < FLT_EPSILON_SQUARED;
}
@@ -97,6 +105,10 @@
#endif
}
+inline bool approximately_equal_half(double x, double y) {
+ return approximately_zero_half(x - y);
+}
+
inline bool approximately_equal_squared(double x, double y) {
return approximately_equal(x, y);
}
@@ -168,6 +180,12 @@
return (a - b) * (c - b) <= 0;
}
+#ifdef SK_DEBUG
+inline bool roughly_equal(double x, double y) {
+ return fabs(x - y) < ROUGH_EPSILON;
+}
+#endif
+
struct _Point {
double x;
double y;
@@ -209,22 +227,32 @@
// return approximately_equal(a.y, y) && approximately_equal(a.x, x);
// because that will not take the magnitude of the values
bool approximatelyEqual(const _Point& a) const {
-#if 0
- return AlmostEqualUlps((float) x, (float) a.x)
- && AlmostEqualUlps((float) y, (float) a.y);
-#else
double denom = SkTMax(fabs(x), SkTMax(fabs(y), SkTMax(fabs(a.x), fabs(a.y))));
if (denom == 0) {
return true;
}
double inv = 1 / denom;
return approximately_equal(x * inv, a.x * inv) && approximately_equal(y * inv, a.y * inv);
-#endif
+ }
+
+ bool approximatelyEqualHalf(const _Point& a) const {
+ double denom = SkTMax(fabs(x), SkTMax(fabs(y), SkTMax(fabs(a.x), fabs(a.y))));
+ if (denom == 0) {
+ return true;
+ }
+ double inv = 1 / denom;
+ return approximately_equal_half(x * inv, a.x * inv)
+ && approximately_equal_half(y * inv, a.y * inv);
}
bool approximatelyZero() const {
return approximately_zero(x) && approximately_zero(y);
}
+
+ SkPoint asSkPoint() const {
+ SkPoint pt = {SkDoubleToScalar(x), SkDoubleToScalar(y)};
+ return pt;
+ }
double cross(const _Point& a) const {
return x * a.y - y * a.x;
diff --git a/experimental/Intersection/EdgeWalker.cpp b/experimental/Intersection/EdgeWalker.cpp
index 79334b4..7bf400e 100644
--- a/experimental/Intersection/EdgeWalker.cpp
+++ b/experimental/Intersection/EdgeWalker.cpp
@@ -64,7 +64,7 @@
Intersections& intersections) {
const _Line aLine = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}};
const _Line bLine = {{b[0].fX, b[0].fY}, {b[1].fX, b[1].fY}};
- return intersect(aLine, bLine, intersections.fT[0], intersections.fT[1]);
+ return intersect(aLine, bLine, intersections);
}
static int QuadLineIntersect(const SkPoint a[3], const SkPoint b[2],
@@ -87,7 +87,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 Quadratic bQuad = {{b[0].fX, b[0].fY}, {b[1].fX, b[1].fY}, {b[2].fX, b[2].fY}};
- intersect(aQuad, bQuad, intersections);
+ intersect2(aQuad, bQuad, intersections);
return intersections.fUsed;
}
diff --git a/experimental/Intersection/EdgeWalker_Test.h b/experimental/Intersection/EdgeWalker_Test.h
index 8799b35..d5c38cf 100644
--- a/experimental/Intersection/EdgeWalker_Test.h
+++ b/experimental/Intersection/EdgeWalker_Test.h
@@ -13,9 +13,6 @@
//extern int comparePaths(const SkPath& one, const SkPath& two);
extern int comparePaths(const SkPath& one, const SkPath& two, SkBitmap& bitmap);
-extern int comparePaths(const SkPath& one, const SkPath& scaledOne, const SkPath& two,
- const SkPath& scaledTwo, SkBitmap& bitmap,
- const SkPath& a, const SkPath& b, const ShapeOp shapeOp);
extern void comparePathsTiny(const SkPath& one, const SkPath& two);
extern bool drawAsciiPaths(const SkPath& one, const SkPath& two,
bool drawPaths);
diff --git a/experimental/Intersection/EdgeWalker_TestUtility.cpp b/experimental/Intersection/EdgeWalker_TestUtility.cpp
index cc95a0a..00d7011 100644
--- a/experimental/Intersection/EdgeWalker_TestUtility.cpp
+++ b/experimental/Intersection/EdgeWalker_TestUtility.cpp
@@ -8,6 +8,7 @@
#include "Intersection_Tests.h"
#include "SkBitmap.h"
#include "SkCanvas.h"
+#include "SkMatrix.h"
#include "SkPaint.h"
#include "SkStream.h"
@@ -103,8 +104,17 @@
showPathContour(iter);
}
- const int bitWidth = 64;
- const int bitHeight = 64;
+static void showPath(const SkPath& path, const char* str, const SkMatrix& scale) {
+ SkPath scaled;
+ SkMatrix inverse;
+ bool success = scale.invert(&inverse);
+ if (!success) SkASSERT(0);
+ path.transform(inverse, &scaled);
+ showPath(scaled, str);
+}
+
+const int bitWidth = 64;
+const int bitHeight = 64;
static void scaleMatrix(const SkPath& one, const SkPath& two, SkMatrix& scale) {
SkRect larger = one.getBounds();
@@ -249,19 +259,21 @@
}
static void showShapeOpPath(const SkPath& one, const SkPath& two, const SkPath& a, const SkPath& b,
- const SkPath& scaledOne, const SkPath& scaledTwo, const ShapeOp shapeOp) {
+ const SkPath& scaledOne, const SkPath& scaledTwo, const ShapeOp shapeOp,
+ const SkMatrix& scale) {
SkASSERT((unsigned) shapeOp < sizeof(opStrs) / sizeof(opStrs[0]));
showPath(a, "minuend:");
SkDebugf("op: %s\n", opStrs[shapeOp]);
showPath(b, "subtrahend:");
- showPath(one, "region:");
+ showPath(scaledOne, "region:", scale);
showPath(two, "op result:");
drawAsciiPaths(scaledOne, scaledTwo, true);
}
-int comparePaths(const SkPath& one, const SkPath& scaledOne, const SkPath& two,
+static int comparePaths(const SkPath& one, const SkPath& scaledOne, const SkPath& two,
const SkPath& scaledTwo,
- SkBitmap& bitmap, const SkPath& a, const SkPath& b, const ShapeOp shapeOp) {
+ SkBitmap& bitmap, const SkPath& a, const SkPath& b, const ShapeOp shapeOp,
+ const SkMatrix& scale) {
int errors2x2;
int errors = pathsDrawTheSame(bitmap, scaledOne, scaledTwo, errors2x2);
if (errors2x2 == 0) {
@@ -269,11 +281,11 @@
}
const int MAX_ERRORS = 8;
if (errors2x2 == MAX_ERRORS || errors2x2 == MAX_ERRORS - 1) {
- showShapeOpPath(one, two, a, b, scaledOne, scaledTwo, shapeOp);
+ showShapeOpPath(one, two, a, b, scaledOne, scaledTwo, shapeOp, scale);
}
if (errors2x2 > MAX_ERRORS && gComparePathsAssert) {
SkDebugf("%s errors=%d\n", __FUNCTION__, errors);
- showShapeOpPath(one, two, a, b, scaledOne, scaledTwo, shapeOp);
+ showShapeOpPath(one, two, a, b, scaledOne, scaledTwo, shapeOp, scale);
SkASSERT(0);
}
return errors2x2 > MAX_ERRORS ? errors2x2 : 0;
@@ -390,7 +402,7 @@
SkPath scaledOut;
scaledOut.addPath(out, scale);
scaledOut.setFillType(out.getFillType());
- int result = comparePaths(pathOut, scaledPathOut, out, scaledOut, bitmap, a, b, shapeOp);
+ int result = comparePaths(pathOut, scaledPathOut, out, scaledOut, bitmap, a, b, shapeOp, scale);
if (result && gPathStrAssert) {
SkASSERT(0);
}
diff --git a/experimental/Intersection/Intersection_Tests.cpp b/experimental/Intersection/Intersection_Tests.cpp
index e828184..f7663e4 100644
--- a/experimental/Intersection/Intersection_Tests.cpp
+++ b/experimental/Intersection/Intersection_Tests.cpp
@@ -14,14 +14,17 @@
void Intersection_Tests() {
int testsRun = 0;
+ SimplifyNew_Test();
QuadraticIntersection_OneOffTest();
+ CubicsToQuadratics_OneOffTest();
CubicIntersection_IntersectionFinder();
CubicIntersection_OneOffTest();
+ CubicIntersection_OneOffTests();
+ QuadraticIntersection_OneOffTest();
#if 0
parseSVG();
#endif
- SimplifyNew_Test();
- QuadraticIntersection_PointFinder();
+// QuadraticIntersection_PointFinder();
ShapeOps4x4CubicsThreaded_Test(testsRun);
CubicToQuadratics_Test();
QuadraticIntersection_Test();
@@ -62,7 +65,7 @@
SimplifyRectangularPaths_Test();
SimplifyQuadralateralPaths_Test();
- ActiveEdge_Test();
+ // ActiveEdge_Test();
QuadraticCoincidence_Test();
QuadraticIntersection_Test();
diff --git a/experimental/Intersection/Intersection_Tests.h b/experimental/Intersection/Intersection_Tests.h
index 20aa80b..f647787 100644
--- a/experimental/Intersection/Intersection_Tests.h
+++ b/experimental/Intersection/Intersection_Tests.h
@@ -13,11 +13,14 @@
void CubicCoincidence_Test();
void CubicIntersection_IntersectionFinder();
void CubicIntersection_OneOffTest();
+void CubicIntersection_OneOffTests();
void CubicIntersection_Test();
void CubicIntersection_RandTest();
void CubicIntersection_RandTestOld();
void CubicParameterization_Test();
void CubicReduceOrder_Test();
+void CubicsToQuadratics_OneOffTest();
+void CubicsToQuadratics_OneOffTests();
void CubicsToQuadratics_RandTest();
void CubicToQuadratics_Test();
void Inline_Tests();
diff --git a/experimental/Intersection/Intersections.cpp b/experimental/Intersection/Intersections.cpp
index 70e7901..01026df 100644
--- a/experimental/Intersection/Intersections.cpp
+++ b/experimental/Intersection/Intersections.cpp
@@ -8,83 +8,93 @@
#include "DataTypes.h"
#include "Intersections.h"
-void Intersections::addCoincident(double s1, double e1, double s2, double e2) {
- SkASSERT((fCoincidentUsed & 1) != 1);
- for (int index = 0; index < fCoincidentUsed; index += 2) {
- double cs1 = fCoincidentT[fSwap][index];
- double ce1 = fCoincidentT[fSwap][index + 1];
- bool s1in = approximately_between(cs1, s1, ce1);
- bool e1in = approximately_between(cs1, e1, ce1);
- double cs2 = fCoincidentT[fSwap ^ 1][index];
- double ce2 = fCoincidentT[fSwap ^ 1][index + 1];
- bool s2in = approximately_between(cs2, s2, ce2);
- bool e2in = approximately_between(cs2, e2, ce2);
+void Intersections::insertCoincidentPair(double s1, double e1, double s2, double e2,
+ const _Point& startPt, const _Point& endPt) {
+ if (fSwap) {
+ remove(s2, e2, startPt, endPt);
+ } else {
+ remove(s1, e1, startPt, endPt);
+ }
+ SkASSERT(coincidentUsed() == fUsed);
+ SkASSERT((coincidentUsed() & 1) != 1);
+ int i1 = 0;
+ int i2 = 0;
+ do {
+ while (i1 < fUsed && !(fIsCoincident[fSwap] & (1 << i1))) {
+ ++i1;
+ }
+ if (i1 == fUsed) {
+ break;
+ }
+ SkASSERT(i1 < fUsed);
+ int iEnd1 = i1 + 1;
+ while (!(fIsCoincident[fSwap] & (1 << iEnd1))) {
+ ++iEnd1;
+ }
+ SkASSERT(iEnd1 < fUsed);
+ double cs1 = fT[fSwap][i1];
+ double ce1 = fT[fSwap][iEnd1];
+ bool s1in = between(cs1, s1, ce1) || startPt.approximatelyEqual(fPt[i1])
+ || startPt.approximatelyEqual(fPt[iEnd1]);
+ bool e1in = between(cs1, e1, ce1) || endPt.approximatelyEqual(fPt[i1])
+ || endPt.approximatelyEqual(fPt[iEnd1]);
+ while (i2 < fUsed && !(fIsCoincident[fSwap ^ 1] & (1 << i2))) {
+ ++i2;
+ }
+ int iEnd2 = i2 + 1;
+ while (!(fIsCoincident[fSwap ^ 1] & (1 << iEnd2))) {
+ ++iEnd2;
+ }
+ SkASSERT(iEnd2 < fUsed);
+ double cs2 = fT[fSwap ^ 1][i2];
+ double ce2 = fT[fSwap ^ 1][iEnd2];
+ bool s2in = between(cs2, s2, ce2) || startPt.approximatelyEqual(fPt[i2])
+ || startPt.approximatelyEqual(fPt[iEnd2]);
+ bool e2in = between(cs2, e2, ce2) || endPt.approximatelyEqual(fPt[i2])
+ || endPt.approximatelyEqual(fPt[iEnd2]);
if ((s1in | e1in) & (s2in | e2in)) {
- double lesser1 = SkTMin(cs1, ce1);
- index += cs1 > ce1;
- if (s1 < lesser1) {
- fCoincidentT[fSwap][index] = s1;
- } else if (e1 < lesser1) {
- fCoincidentT[fSwap][index] = e1;
+ if (s1 < cs1) {
+ fT[fSwap][i1] = s1;
+ fPt[i1] = startPt;
+ } else if (e1 < cs1) {
+ fT[fSwap][i1] = e1;
+ fPt[i1] = endPt;
}
- index ^= 1;
- double greater1 = fCoincidentT[fSwap][index];
- if (s1 > greater1) {
- fCoincidentT[fSwap][index] = s1;
- } else if (e1 > greater1) {
- fCoincidentT[fSwap][index] = e1;
+ if (s1 > ce1) {
+ fT[fSwap][iEnd1] = s1;
+ fPt[iEnd1] = startPt;
+ } else if (e1 > ce1) {
+ fT[fSwap][iEnd1] = e1;
+ fPt[iEnd1] = endPt;
}
- index &= ~1;
- double lesser2 = SkTMin(cs2, ce2);
- index += cs2 > ce2;
- if (s2 < lesser2) {
- fCoincidentT[fSwap ^ 1][index] = s2;
- } else if (e2 < lesser2) {
- fCoincidentT[fSwap ^ 1][index] = e2;
+ if (s2 > e2) {
+ SkTSwap(cs2, ce2);
+ SkTSwap(i2, iEnd2);
}
- index ^= 1;
- double greater2 = fCoincidentT[fSwap ^ 1][index];
- if (s2 > greater2) {
- fCoincidentT[fSwap ^ 1][index] = s2;
- } else if (e2 > greater2) {
- fCoincidentT[fSwap ^ 1][index] = e2;
+ if (s2 < cs2) {
+ fT[fSwap ^ 1][i2] = s2;
+ } else if (e2 < cs2) {
+ fT[fSwap ^ 1][i2] = e2;
+ }
+ if (s2 > ce2) {
+ fT[fSwap ^ 1][iEnd2] = s2;
+ } else if (e2 > ce2) {
+ fT[fSwap ^ 1][iEnd2] = e2;
}
return;
}
- }
- SkASSERT(fCoincidentUsed < 9);
- fCoincidentT[fSwap][fCoincidentUsed] = s1;
- fCoincidentT[fSwap ^ 1][fCoincidentUsed] = s2;
- ++fCoincidentUsed;
- fCoincidentT[fSwap][fCoincidentUsed] = e1;
- fCoincidentT[fSwap ^ 1][fCoincidentUsed] = e2;
- ++fCoincidentUsed;
- // FIXME: assert that no entries in normal range lie between s and e
- remove(s1, e1);
- remove(s2, e2);
+ } while (true);
+ SkASSERT(fUsed < 9);
+ insertCoincident(s1, s2, startPt);
+ insertCoincident(e1, e2, endPt);
}
-void Intersections::cleanUp() {
- SkASSERT(fCoincidentUsed);
- SkASSERT(fUsed);
- // find any entries in fT that could be part of the coincident range
-
-}
-
-// FIXME: this doesn't respect swap, but add coincident does -- seems inconsistent
-void Intersections::insert(double one, double two) {
+int Intersections::insert(double one, double two, const _Point& pt) {
SkASSERT(fUsed <= 1 || fT[0][0] < fT[0][1]);
int index;
- for (index = 0; index < fCoincidentUsed; ++index ) {
- if (approximately_equal(fCoincidentT[0][index], one)
- && approximately_equal(fCoincidentT[1][index], two)) {
- return;
- }
- }
for (index = 0; index < fUsed; ++index) {
- if (approximately_equal(fT[0][index], one)
- && approximately_equal(fT[1][index], two)) {
- return;
+ if (approximately_equal(fT[0][index], one) || pt.approximatelyEqual(fPt[index])) {
+ return -1;
}
if (fT[0][index] > one) {
break;
@@ -93,55 +103,35 @@
SkASSERT(fUsed < 9);
int remaining = fUsed - index;
if (remaining > 0) {
+ memmove(&fPt[index + 1], &fPt[index], sizeof(fPt[0]) * remaining);
memmove(&fT[0][index + 1], &fT[0][index], sizeof(fT[0][0]) * remaining);
memmove(&fT[1][index + 1], &fT[1][index], sizeof(fT[1][0]) * remaining);
+ fIsCoincident[0] += fIsCoincident[0] & ~((1 << index) - 1);
+ fIsCoincident[1] += fIsCoincident[1] & ~((1 << index) - 1);
}
+ fPt[index] = pt;
fT[0][index] = one;
fT[1][index] = two;
++fUsed;
+ return index;
}
-// FIXME: all callers should be moved to regular insert. Failures are likely
-// if two separate callers differ on whether ts are equal or not
-void Intersections::insertOne(double t, int side) {
- int used = side ? fUsed2 : fUsed;
- SkASSERT(used <= 1 || fT[side][0] < fT[side][1]);
- int index;
- for (index = 0; index < used; ++index) {
- if (approximately_equal(fT[side][index], t)) {
- return;
- }
- if (fT[side][index] > t) {
- break;
+void Intersections::remove(double one, double two, const _Point& startPt, const _Point& endPt) {
+ for (int index = fUsed - 1; index >= 0; --index) {
+ if (!(fIsCoincident[0] & (1 << index)) && (between(one, fT[fSwap][index], two)
+ || startPt.approximatelyEqual(fPt[index])
+ || endPt.approximatelyEqual(fPt[index]))) {
+ SkASSERT(fUsed > 0);
+ int remaining = --fUsed - index;
+ if (remaining > 0) {
+ memmove(&fPt[index], &fPt[index - 1], sizeof(fPt[0]) * remaining);
+ memmove(&fT[0][index], &fT[0][index - 1], sizeof(fT[0][0]) * remaining);
+ memmove(&fT[1][index], &fT[1][index - 1], sizeof(fT[1][0]) * remaining);
+ int coBit = fIsCoincident[0] & (1 << index);
+ fIsCoincident[0] -= ((fIsCoincident[0] >> 1) & ~((1 << index) - 1)) + coBit;
+ SkASSERT(!(coBit ^ (fIsCoincident[1] & (1 << index))));
+ fIsCoincident[1] -= ((fIsCoincident[1] >> 1) & ~((1 << index) - 1)) + coBit;
+ }
}
}
- SkASSERT(used < 9);
- int remaining = used - index;
- if (remaining > 0) {
- memmove(&fT[side][index + 1], &fT[side][index], sizeof(fT[side][0]) * remaining);
- }
- fT[side][index] = t;
- side ? ++fUsed2 : ++fUsed;
-}
-
-void Intersections::remove(double one, double two) {
- int index;
- for (index = 0; index < fUsed; ++index) {
- if (approximately_equal(fT[0][index], one)
- && approximately_equal(fT[1][index], two)) {
- goto foundIt;
- }
- if (fT[0][index] > one) {
- return;
- }
- }
- return;
-foundIt:
- SkASSERT(fUsed > 0);
- int remaining = fUsed - index;
- if (remaining > 0) {
- memmove(&fT[0][index], &fT[0][index - 1], sizeof(fT[0][0]) * remaining);
- memmove(&fT[1][index], &fT[1][index - 1], sizeof(fT[1][0]) * remaining);
- }
- --fUsed;
}
diff --git a/experimental/Intersection/Intersections.h b/experimental/Intersection/Intersections.h
index d873ba0..d339116 100644
--- a/experimental/Intersection/Intersections.h
+++ b/experimental/Intersection/Intersections.h
@@ -11,60 +11,40 @@
public:
Intersections()
: fFlip(0)
- , fSwap(0)
#if SK_DEBUG
, fDepth(0)
#endif
+ , fSwap(0)
{
- // OPTIMIZE: don't need to be initialized in release
+#if SK_DEBUG
+ bzero(fPt, sizeof(fPt));
bzero(fT, sizeof(fT));
- bzero(fCoincidentT, sizeof(fCoincidentT));
+ bzero(fIsCoincident, sizeof(fIsCoincident));
+#endif
reset();
}
- void add(double one, double two) {
- for (int index = 0; index < fUsed; ++index) {
- if (approximately_equal(fT[fSwap][index], one)
- && approximately_equal(fT[fSwap ^ 1][index], two)) {
- return;
- }
- }
- SkASSERT(fUsed < 9);
- fT[fSwap][fUsed] = one;
- fT[fSwap ^ 1][fUsed] = two;
- ++fUsed;
- }
-
- // start if index == 0 : end if index == 1
- void addCoincident(double one, double two) {
- for (int index = 0; index < fCoincidentUsed; ++index) {
- if (approximately_equal(fCoincidentT[fSwap][index], one)
- && approximately_equal(fCoincidentT[fSwap ^ 1][index], two)) {
- return;
- }
- }
- SkASSERT(fCoincidentUsed < 9);
- fCoincidentT[fSwap][fCoincidentUsed] = one;
- fCoincidentT[fSwap ^ 1][fCoincidentUsed] = two;
- ++fCoincidentUsed;
- }
-
- void addCoincident(double s1, double e1, double s2, double e2);
-
- // FIXME: this is necessary because curve/curve intersections are noisy
- // remove once curve/curve intersections are improved
- void cleanUp();
-
int coincidentUsed() const {
- return fCoincidentUsed;
+ if (!fIsCoincident[0]) {
+ SkASSERT(!fIsCoincident[0]);
+ return 0;
+ }
+ int count = 0;
+ SkDEBUGCODE(int count2 = 0;)
+ for (int index = 0; index < fUsed; ++index) {
+ if (fIsCoincident[0] & (1 << index)) {
+ ++count;
+ }
+ #if SK_DEBUG
+ if (fIsCoincident[1] & (1 << index)) {
+ ++count2;
+ }
+ #endif
+ }
+ SkASSERT(count == count2);
+ return count;
}
-#if SK_DEBUG
- int depth() const {
- return fDepth;
- }
-#endif
-
void offset(int base, double start, double end) {
for (int index = base; index < fUsed; ++index) {
double val = fT[fSwap][index];
@@ -74,20 +54,34 @@
}
}
- void insert(double one, double two);
- void insertOne(double t, int side);
+ int insert(double one, double two, const _Point& pt);
+ // start if index == 0 : end if index == 1
+ void insertCoincident(double one, double two, const _Point& pt) {
+ int index = insertSwap(one, two, pt);
+ int bit = 1 << index;
+ fIsCoincident[0] |= bit;
+ fIsCoincident[1] |= bit;
+ }
+
+ void insertCoincidentPair(double s1, double e1, double s2, double e2,
+ const _Point& startPt, const _Point& endPt);
+
+ int insertSwap(double one, double two, const _Point& pt) {
+ if (fSwap) {
+ return insert(two, one, pt);
+ } else {
+ return insert(one, two, pt);
+ }
+ }
+
bool intersected() const {
return fUsed > 0;
}
- bool insertBalanced() const {
- return fUsed == fUsed2;
- }
-
// leaves flip, swap alone
void reset() {
- fUsed = fUsed2 = fCoincidentUsed = 0;
+ fUsed = /* fUsed2 = fCoincidentUsed = */ 0;
fUnsortable = false;
}
@@ -122,11 +116,16 @@
SkASSERT(++fDepth < 16);
}
+#if SK_DEBUG
+ int depth() const {
+ return fDepth;
+ }
+#endif
+
+ _Point fPt[9];
double fT[2][9];
- double fCoincidentT[2][9];
- int fUsed;
- int fUsed2;
- int fCoincidentUsed;
+ unsigned short fIsCoincident[2]; // bit arrays, one bit set for each coincident T
+ unsigned char fUsed;
bool fFlip;
bool fUnsortable;
#if SK_DEBUG
@@ -134,9 +133,9 @@
#endif
protected:
// used by addCoincident to remove ordinary intersections in range
- void remove(double one, double two);
+ void remove(double one, double two, const _Point& startPt, const _Point& endPt);
private:
- int fSwap;
+ bool fSwap;
};
#endif
diff --git a/experimental/Intersection/LineCubicIntersection.cpp b/experimental/Intersection/LineCubicIntersection.cpp
index faed89f..1e97ab2 100644
--- a/experimental/Intersection/LineCubicIntersection.cpp
+++ b/experimental/Intersection/LineCubicIntersection.cpp
@@ -107,7 +107,9 @@
double cubicT = rootVals[index];
double lineT = findLineT(cubicT);
if (pinTs(cubicT, lineT)) {
- intersections.insert(cubicT, lineT);
+ _Point pt;
+ xy_at_t(line, lineT, pt.x, pt.y);
+ intersections.insert(cubicT, lineT, pt);
}
}
return intersections.fUsed;
@@ -125,12 +127,12 @@
double rootVals[3];
int roots = horizontalIntersect(axisIntercept, rootVals);
for (int index = 0; index < roots; ++index) {
- double x;
+ _Point pt;
double cubicT = rootVals[index];
- xy_at_t(cubic, cubicT, x, *(double*) NULL);
- double lineT = (x - left) / (right - left);
+ xy_at_t(cubic, cubicT, pt.x, pt.y);
+ double lineT = (pt.x - left) / (right - left);
if (pinTs(cubicT, lineT)) {
- intersections.insert(cubicT, lineT);
+ intersections.insert(cubicT, lineT, pt);
}
}
if (flipped) {
@@ -151,12 +153,12 @@
double rootVals[3];
int roots = verticalIntersect(axisIntercept, rootVals);
for (int index = 0; index < roots; ++index) {
- double y;
+ _Point pt;
double cubicT = rootVals[index];
- xy_at_t(cubic, cubicT, *(double*) NULL, y);
- double lineT = (y - top) / (bottom - top);
+ xy_at_t(cubic, cubicT, pt.x, pt.y);
+ double lineT = (pt.y - top) / (bottom - top);
if (pinTs(cubicT, lineT)) {
- intersections.insert(cubicT, lineT);
+ intersections.insert(cubicT, lineT, pt);
}
}
if (flipped) {
@@ -172,7 +174,7 @@
for (int cIndex = 0; cIndex < 4; cIndex += 3) {
for (int lIndex = 0; lIndex < 2; lIndex++) {
if (cubic[cIndex] == line[lIndex]) {
- intersections.insert(cIndex >> 1, lIndex);
+ intersections.insert(cIndex >> 1, lIndex, line[lIndex]);
}
}
}
@@ -185,10 +187,10 @@
continue;
}
if (cubic[cIndex].x == left) {
- intersections.insert(cIndex >> 1, 0);
+ intersections.insert(cIndex >> 1, 0, cubic[cIndex]);
}
if (cubic[cIndex].x == right) {
- intersections.insert(cIndex >> 1, 1);
+ intersections.insert(cIndex >> 1, 1, cubic[cIndex]);
}
}
}
@@ -200,10 +202,10 @@
continue;
}
if (cubic[cIndex].y == top) {
- intersections.insert(cIndex >> 1, 0);
+ intersections.insert(cIndex >> 1, 0, cubic[cIndex]);
}
if (cubic[cIndex].y == bottom) {
- intersections.insert(cIndex >> 1, 1);
+ intersections.insert(cIndex >> 1, 1, cubic[cIndex]);
}
}
}
diff --git a/experimental/Intersection/LineIntersection.cpp b/experimental/Intersection/LineIntersection.cpp
index 6ab3936..ca6a8e4 100644
--- a/experimental/Intersection/LineIntersection.cpp
+++ b/experimental/Intersection/LineIntersection.cpp
@@ -7,6 +7,7 @@
#include "CurveIntersection.h"
#include "Intersections.h"
#include "LineIntersection.h"
+#include "LineUtilities.h"
/* Determine the intersection point of two lines. This assumes the lines are not parallel,
and that that the lines are infinite.
@@ -25,13 +26,21 @@
p.y = (term1 * byLen - ayLen * term2) / denom;
}
+static int computePoints(const _Line& a, int used, Intersections& i) {
+ i.fPt[0] = xy_at_t(a, i.fT[0][0]);
+ if ((i.fUsed = used) == 2) {
+ i.fPt[1] = xy_at_t(a, i.fT[0][1]);
+ }
+ return i.fUsed;
+}
+
/*
Determine the intersection point of two line segments
Return FALSE if the lines don't intersect
from: http://paulbourke.net/geometry/lineline2d/
*/
-int intersect(const _Line& a, const _Line& b, double aRange[2], double bRange[2]) {
+int intersect(const _Line& a, const _Line& b, Intersections& i) {
double axLen = a[1].x - a[0].x;
double ayLen = a[1].y - a[0].y;
double bxLen = b[1].x - b[0].x;
@@ -57,13 +66,10 @@
if (mayNotOverlap) {
return 0;
}
- if (aRange) {
- aRange[0] = numerA;
- }
- if (bRange) {
- bRange[0] = numerB;
- }
- return 1;
+ i.fT[0][0] = numerA;
+ i.fT[1][0] = numerB;
+ i.fPt[0] = xy_at_t(a, numerA);
+ return computePoints(a, 1, i);
}
/* See if the axis intercepts match:
ay - ax * ayLen / axLen == by - bx * ayLen / axLen
@@ -84,8 +90,6 @@
aPtr = &a[0].y;
bPtr = &b[0].y;
}
- SkASSERT(aRange);
- SkASSERT(bRange);
double a0 = aPtr[0];
double a1 = aPtr[2];
double b0 = bPtr[0];
@@ -98,27 +102,27 @@
if (!between(b0, a0, b1)) {
return 0;
}
- aRange[0] = aRange[1] = 0;
+ i.fT[0][0] = i.fT[0][1] = 0;
} else {
double at0 = (a0 - b0) / aDenom;
double at1 = (a0 - b1) / aDenom;
if ((at0 < 0 && at1 < 0) || (at0 > 1 && at1 > 1)) {
return 0;
}
- aRange[0] = SkTMax(SkTMin(at0, 1.0), 0.0);
- aRange[1] = SkTMax(SkTMin(at1, 1.0), 0.0);
+ i.fT[0][0] = SkTMax(SkTMin(at0, 1.0), 0.0);
+ i.fT[0][1] = SkTMax(SkTMin(at1, 1.0), 0.0);
}
double bDenom = b0 - b1;
if (approximately_zero(bDenom)) {
- bRange[0] = bRange[1] = 0;
+ i.fT[1][0] = i.fT[1][1] = 0;
} else {
int bIn = aDenom * bDenom < 0;
- bRange[bIn] = SkTMax(SkTMin((b0 - a0) / bDenom, 1.0), 0.0);
- bRange[!bIn] = SkTMax(SkTMin((b0 - a1) / bDenom, 1.0), 0.0);
+ i.fT[1][bIn] = SkTMax(SkTMin((b0 - a0) / bDenom, 1.0), 0.0);
+ i.fT[1][!bIn] = SkTMax(SkTMin((b0 - a1) / bDenom, 1.0), 0.0);
}
- bool second = fabs(aRange[0] - aRange[1]) > FLT_EPSILON;
- SkASSERT((fabs(bRange[0] - bRange[1]) <= FLT_EPSILON) ^ second);
- return 1 + second;
+ bool second = fabs(i.fT[0][0] - i.fT[0][1]) > FLT_EPSILON;
+ SkASSERT((fabs(i.fT[1][0] - i.fT[1][1]) <= FLT_EPSILON) ^ second);
+ return computePoints(a, 1 + second, i);
}
int horizontalIntersect(const _Line& line, double y, double tRange[2]) {
@@ -219,7 +223,7 @@
> FLT_EPSILON;
SkASSERT((fabs(intersections.fT[1][0] - intersections.fT[1][1])
<= FLT_EPSILON) ^ second);
- return 1 + second;
+ return computePoints(line, 1 + second, intersections);
#endif
break;
}
@@ -229,7 +233,7 @@
intersections.fT[1][index] = 1 - intersections.fT[1][index];
}
}
- return result;
+ return computePoints(line, result, intersections);
}
static int verticalIntersect(const _Line& line, double x, double tRange[2]) {
@@ -308,7 +312,7 @@
> FLT_EPSILON;
SkASSERT((fabs(intersections.fT[1][0] - intersections.fT[1][1])
<= FLT_EPSILON) ^ second);
- return 1 + second;
+ return computePoints(line, 1 + second, intersections);
#endif
break;
}
@@ -318,7 +322,7 @@
intersections.fT[1][index] = 1 - intersections.fT[1][index];
}
}
- return result;
+ return computePoints(line, result, intersections);
}
// from http://www.bryceboe.com/wordpress/wp-content/uploads/2006/10/intersect.py
diff --git a/experimental/Intersection/LineIntersection.h b/experimental/Intersection/LineIntersection.h
index adb5789..4036f13 100644
--- a/experimental/Intersection/LineIntersection.h
+++ b/experimental/Intersection/LineIntersection.h
@@ -7,13 +7,13 @@
#ifndef LineIntersection_DEFINE
#define LineIntersection_DEFINE
-#include "DataTypes.h"
+#include "Intersections.h"
int horizontalIntersect(const _Line& line, double y, double tRange[2]);
int horizontalLineIntersect(const _Line& line, double left, double right,
double y, double tRange[2]);
void lineIntersect(const _Line& a, const _Line& b, _Point& p);
-int intersect(const _Line& a, const _Line& b, double aRange[2], double bRange[2]);
+int intersect(const _Line& a, const _Line& b, Intersections&);
bool testIntersect(const _Line& a, const _Line& b);
int verticalLineIntersect(const _Line& line, double top, double bottom,
double x, double tRange[2]);
diff --git a/experimental/Intersection/LineIntersection_Test.cpp b/experimental/Intersection/LineIntersection_Test.cpp
index ba15192..283d9df 100644
--- a/experimental/Intersection/LineIntersection_Test.cpp
+++ b/experimental/Intersection/LineIntersection_Test.cpp
@@ -39,20 +39,20 @@
for (index = firstLineIntersectionTest; index < tests_count; ++index) {
const _Line& line1 = tests[index][0];
const _Line& line2 = tests[index][1];
- double t1[2], t2[2];
- int pts = intersect(line1, line2, t1, t2);
+ Intersections ts;
+ int pts = intersect(line1, line2, ts);
if (!pts) {
printf("%s [%zu] no intersection found\n", __FUNCTION__, index);
}
for (int i = 0; i < pts; ++i) {
_Point result1, result2;
- xy_at_t(line1, t1[i], result1.x, result1.y);
- xy_at_t(line2, t2[i], result2.x, result2.y);
+ xy_at_t(line1, ts.fT[0][i], result1.x, result1.y);
+ xy_at_t(line2, ts.fT[1][i], result2.x, result2.y);
if (!result1.approximatelyEqual(result2)) {
if (pts == 1) {
printf("%s [%zu] not equal\n", __FUNCTION__, index);
} else {
- xy_at_t(line2, t2[i ^ 1], result2.x, result2.y);
+ xy_at_t(line2, ts.fT[1][i ^ 1], result2.x, result2.y);
if (!result1.approximatelyEqual(result2)) {
printf("%s [%zu] not equal\n", __FUNCTION__, index);
}
@@ -63,8 +63,8 @@
for (index = firstNoIntersectionTest; index < noIntersect_count; ++index) {
const _Line& line1 = noIntersect[index][0];
const _Line& line2 = noIntersect[index][1];
- double t1[2], t2[2];
- int pts = intersect(line1, line2, t1, t2);
+ Intersections ts;
+ int pts = intersect(line1, line2, ts);
if (pts) {
printf("%s [%zu] no intersection expected\n", __FUNCTION__, index);
}
diff --git a/experimental/Intersection/LineQuadraticIntersection.cpp b/experimental/Intersection/LineQuadraticIntersection.cpp
index 9ec3fb7..3cc27e5 100644
--- a/experimental/Intersection/LineQuadraticIntersection.cpp
+++ b/experimental/Intersection/LineQuadraticIntersection.cpp
@@ -135,7 +135,9 @@
double quadT = rootVals[index];
double lineT = findLineT(quadT);
if (pinTs(quadT, lineT)) {
- intersections.insert(quadT, lineT);
+ _Point pt;
+ xy_at_t(line, lineT, pt.x, pt.y);
+ intersections.insert(quadT, lineT, pt);
}
}
return intersections.fUsed;
@@ -156,12 +158,12 @@
double rootVals[2];
int roots = horizontalIntersect(axisIntercept, rootVals);
for (int index = 0; index < roots; ++index) {
- double x;
+ _Point pt;
double quadT = rootVals[index];
- xy_at_t(quad, quadT, x, *(double*) NULL);
- double lineT = (x - left) / (right - left);
+ xy_at_t(quad, quadT, pt.x, pt.y);
+ double lineT = (pt.x - left) / (right - left);
if (pinTs(quadT, lineT)) {
- intersections.insert(quadT, lineT);
+ intersections.insert(quadT, lineT, pt);
}
}
if (flipped) {
@@ -185,12 +187,12 @@
double rootVals[2];
int roots = verticalIntersect(axisIntercept, rootVals);
for (int index = 0; index < roots; ++index) {
- double y;
+ _Point pt;
double quadT = rootVals[index];
- xy_at_t(quad, quadT, *(double*) NULL, y);
- double lineT = (y - top) / (bottom - top);
+ xy_at_t(quad, quadT, pt.x, pt.y);
+ double lineT = (pt.y - top) / (bottom - top);
if (pinTs(quadT, lineT)) {
- intersections.insert(quadT, lineT);
+ intersections.insert(quadT, lineT, pt);
}
}
if (flipped) {
@@ -207,7 +209,7 @@
for (int qIndex = 0; qIndex < 3; qIndex += 2) {
for (int lIndex = 0; lIndex < 2; lIndex++) {
if (quad[qIndex] == line[lIndex]) {
- intersections.insert(qIndex >> 1, lIndex);
+ intersections.insert(qIndex >> 1, lIndex, line[lIndex]);
}
}
}
@@ -220,10 +222,10 @@
continue;
}
if (quad[qIndex].x == left) {
- intersections.insert(qIndex >> 1, 0);
+ intersections.insert(qIndex >> 1, 0, quad[qIndex]);
}
if (quad[qIndex].x == right) {
- intersections.insert(qIndex >> 1, 1);
+ intersections.insert(qIndex >> 1, 1, quad[qIndex]);
}
}
}
@@ -235,10 +237,10 @@
continue;
}
if (quad[qIndex].y == top) {
- intersections.insert(qIndex >> 1, 0);
+ intersections.insert(qIndex >> 1, 0, quad[qIndex]);
}
if (quad[qIndex].y == bottom) {
- intersections.insert(qIndex >> 1, 1);
+ intersections.insert(qIndex >> 1, 1, quad[qIndex]);
}
}
}
diff --git a/experimental/Intersection/LineUtilities.cpp b/experimental/Intersection/LineUtilities.cpp
index 6e3b966..186fa9b 100644
--- a/experimental/Intersection/LineUtilities.cpp
+++ b/experimental/Intersection/LineUtilities.cpp
@@ -125,3 +125,9 @@
y = one_t * line[0].y + t * line[1].y;
}
}
+
+_Point xy_at_t(const _Line& line, double t) {
+ double one_t = 1 - t;
+ _Point result = { one_t * line[0].x + t * line[1].x, one_t * line[0].y + t * line[1].y };
+ return result;
+}
diff --git a/experimental/Intersection/LineUtilities.h b/experimental/Intersection/LineUtilities.h
index 6052875..d1d4570 100644
--- a/experimental/Intersection/LineUtilities.h
+++ b/experimental/Intersection/LineUtilities.h
@@ -12,6 +12,7 @@
void sub_divide(const _Line& src, double t1, double t2, _Line& dst);
double t_at(const _Line&, const _Point& );
void xy_at_t(const _Line& , double t, double& x, double& y);
+_Point xy_at_t(const _Line& , double t);
enum x_at_flags {
kFindTopMin = 1,
diff --git a/experimental/Intersection/LogoPlay.cpp b/experimental/Intersection/LogoPlay.cpp
new file mode 100644
index 0000000..3c9b75d
--- /dev/null
+++ b/experimental/Intersection/LogoPlay.cpp
@@ -0,0 +1,354 @@
+#include <ctype.h>
+#include "SkPath.h"
+#include "SkParse.h"
+#include "SkPoint.h"
+#include "SkUtils.h"
+#define QUADRATIC_APPROXIMATION 0
+
+const char logoStr[] =
+ "<path fill=\"#0081C6\""
+ "d=\"M440.51,289.479c1.623,1.342,5.01,4.164,5.01,9.531c0,5.223-2.965,7.697-5.93,10.024"
+ "c-0.918,0.916-1.977,1.907-1.977,3.462c0,1.551,1.059,2.397,1.834,3.035l2.545,1.973c3.105,2.613,5.928,5.016,5.928,9.889"
+ "c0,6.635-6.426,13.341-18.566,13.341c-10.238,0-15.178-4.87-15.178-10.097c0-2.543,1.268-6.139,5.438-8.613"
+ "c4.373-2.682,10.307-3.033,13.482-3.249c-0.99-1.271-2.119-2.61-2.119-4.798c0-1.199,0.355-1.907,0.707-2.754"
+ "c-0.779,0.07-1.553,0.141-2.26,0.141c-7.482,0-11.719-5.579-11.719-11.082c0-3.247,1.484-6.851,4.518-9.461"
+ "c4.025-3.318,8.824-3.883,12.639-3.883h14.541l-4.518,2.541H440.51z"
+ "M435.494,320.826c-0.562-0.072-0.916-0.072-1.619-0.072"
+ "c-0.637,0-4.451,0.143-7.416,1.132c-1.553,0.564-6.07,2.257-6.07,7.271c0,5.013,4.873,8.615,12.426,8.615"
+ "c6.775,0,10.379-3.253,10.379-7.624C443.193,326.54,440.863,324.64,435.494,320.826z"
+ "M437.543,307.412"
+ "c1.623-1.627,1.764-3.883,1.764-5.154c0-5.083-3.035-12.99-8.893-12.99c-1.838,0-3.812,0.918-4.945,2.331"
+ "c-1.199,1.483-1.551,3.387-1.551,5.225c0,4.729,2.754,12.565,8.826,12.565C434.508,309.389,436.41,308.543,437.543,307.412z\"/>"
+ "<path fill=\"#FFD200\""
+ "d=\"M396.064,319.696c-11.206,0-17.198-8.739-17.198-16.636c0-9.233,7.542-17.126,18.258-17.126"
+ "c10.357,0,16.844,8.104,16.844,16.635C413.969,310.884,407.557,319.696,396.064,319.696z"
+ "M404.873,313.987"
+ "c1.695-2.257,2.119-5.074,2.119-7.826c0-6.202-2.961-18.042-11.701-18.042c-2.326,0-4.652,0.918-6.342,2.399"
+ "c-2.749,2.465-3.245,5.566-3.245,8.599c0,6.977,3.454,18.463,11.984,18.463C400.436,317.58,403.256,316.242,404.873,313.987z\"/>"
+ "<path fill=\"#ED174F\""
+ "d=\"M357.861,319.696c-11.207,0-17.199-8.739-17.199-16.636c0-9.233,7.544-17.126,18.258-17.126"
+ "c10.359,0,16.845,8.104,16.845,16.635C375.764,310.884,369.351,319.696,357.861,319.696z"
+ "M366.671,313.987"
+ "c1.693-2.257,2.116-5.074,2.116-7.826c0-6.202-2.961-18.042-11.701-18.042c-2.325,0-4.652,0.918-6.344,2.399"
+ "c-2.749,2.465-3.241,5.566-3.241,8.599c0,6.977,3.452,18.463,11.983,18.463C362.234,317.58,365.053,316.242,366.671,313.987z\"/>"
+ "<path fill=\"#0081C6\""
+ "d=\"M335.278,318.591l-10.135,2.339c-4.111,0.638-7.795,1.204-11.69,1.204"
+ "c-19.56,0-26.998-14.386-26.998-25.654c0-13.746,10.558-26.498,28.629-26.498c3.827,0,7.51,0.564,10.839,1.486"
+ "c5.316,1.488,7.796,3.331,9.355,4.394l-5.883,5.599l-2.479,0.565l1.771-2.837c-2.408-2.336-6.805-6.658-15.164-6.658"
+ "c-11.196,0-19.63,8.507-19.63,20.906c0,13.319,9.638,25.861,25.084,25.861c4.539,0,6.874-0.918,9-1.771v-11.407l-10.698,0.566"
+ "l5.667-3.047h15.023l-1.841,1.77c-0.5,0.424-0.567,0.57-0.71,1.133c-0.073,0.64-0.141,2.695-0.141,3.403V318.591z\"/>"
+ "<path fill=\"#49A942\""
+ "d=\"M462.908,316.552c-2.342-0.214-2.832-0.638-2.832-3.401v-0.782v-39.327c0.014-0.153,0.025-0.31,0.041-0.457"
+ "c0.283-2.479,0.992-2.903,3.189-4.182h-10.135l-5.316,2.552h5.418v0.032l-0.004-0.024v41.406v2.341"
+ "c0,1.416-0.281,1.629-1.912,3.753H463.9l2.623-1.557C465.318,316.763,464.113,316.692,462.908,316.552z\"/>"
+ "<path fill=\"#ED174F\""
+ "d=\"M491.742,317.203c-0.771,0.422-1.547,0.916-2.318,1.268c-2.326,1.055-4.719,1.336-6.83,1.336"
+ "c-2.25,0-5.77-0.143-9.361-2.744c-4.992-3.521-7.176-9.572-7.176-14.851c0-10.906,8.869-16.255,16.115-16.255"
+ "c2.533,0,5.141,0.633,7.252,1.972c3.516,2.318,4.43,5.344,4.922,6.963l-16.535,6.688l-5.422,0.422"
+ "c1.758,8.938,7.812,14.145,14.498,14.145c3.59,0,6.193-1.266,8.586-2.461L491.742,317.203z"
+ "M485.129,296.229"
+ "c1.336-0.493,2.039-0.914,2.039-1.899c0-2.812-3.166-6.053-6.967-6.053c-2.818,0-8.094,2.183-8.094,9.783"
+ "c0,1.197,0.141,2.464,0.213,3.73L485.129,296.229z\"/>"
+ "<path fill=\"#77787B\""
+ "d=\"M498.535,286.439v4.643h-0.564v-4.643h-1.537v-0.482h3.637v0.482H498.535z\"/>"
+ "<path fill=\"#77787B\""
+ "d=\"M504.863,291.082v-4.687h-0.023l-1.432,4.687h-0.439l-1.443-4.687h-0.02v4.687h-0.512v-5.125h0.877"
+ "l1.307,4.143h0.018l1.285-4.143h0.891v5.125H504.863z\"/>"
+;
+
+size_t logoStrLen = sizeof(logoStr);
+
+#if QUADRATIC_APPROXIMATION
+////////////////////////////////////////////////////////////////////////////////////
+//functions to approximate a cubic using two quadratics
+
+// midPt sets the first argument to be the midpoint of the other two
+// it is used by quadApprox
+static inline void midPt(SkPoint& dest,const SkPoint& a,const SkPoint& b)
+{
+ dest.set(SkScalarAve(a.fX, b.fX),SkScalarAve(a.fY, b.fY));
+}
+// quadApprox - makes an approximation, which we hope is faster
+static void quadApprox(SkPath &fPath, const SkPoint &p0, const SkPoint &p1, const SkPoint &p2)
+{
+ //divide the cubic up into two cubics, then convert them into quadratics
+ //define our points
+ SkPoint c,j,k,l,m,n,o,p,q, mid;
+ fPath.getLastPt(&c);
+ midPt(j, p0, c);
+ midPt(k, p0, p1);
+ midPt(l, p1, p2);
+ midPt(o, j, k);
+ midPt(p, k, l);
+ midPt(q, o, p);
+ //compute the first half
+ m.set(SkScalarHalf(3*j.fX - c.fX), SkScalarHalf(3*j.fY - c.fY));
+ n.set(SkScalarHalf(3*o.fX -q.fX), SkScalarHalf(3*o.fY - q.fY));
+ midPt(mid,m,n);
+ fPath.quadTo(mid,q);
+ c = q;
+ //compute the second half
+ m.set(SkScalarHalf(3*p.fX - c.fX), SkScalarHalf(3*p.fY - c.fY));
+ n.set(SkScalarHalf(3*l.fX -p2.fX),SkScalarHalf(3*l.fY -p2.fY));
+ midPt(mid,m,n);
+ fPath.quadTo(mid,p2);
+}
+#endif
+
+
+static inline bool is_between(int c, int min, int max)
+{
+ return (unsigned)(c - min) <= (unsigned)(max - min);
+}
+
+static inline bool is_ws(int c)
+{
+ return is_between(c, 1, 32);
+}
+
+static inline bool is_digit(int c)
+{
+ return is_between(c, '0', '9');
+}
+
+static inline bool is_sep(int c)
+{
+ return is_ws(c) || c == ',';
+}
+
+static const char* skip_ws(const char str[])
+{
+ SkASSERT(str);
+ while (is_ws(*str))
+ str++;
+ return str;
+}
+
+static const char* skip_sep(const char str[])
+{
+ SkASSERT(str);
+ while (is_sep(*str))
+ str++;
+ return str;
+}
+
+static const char* find_points(const char str[], SkPoint value[], int count,
+ bool isRelative, SkPoint* relative)
+{
+ str = SkParse::FindScalars(str, &value[0].fX, count * 2);
+ if (isRelative) {
+ for (int index = 0; index < count; index++) {
+ value[index].fX += relative->fX;
+ value[index].fY += relative->fY;
+ }
+ }
+ return str;
+}
+
+static const char* find_scalar(const char str[], SkScalar* value,
+ bool isRelative, SkScalar relative)
+{
+ str = SkParse::FindScalar(str, value);
+ if (isRelative)
+ *value += relative;
+ return str;
+}
+
+static void showPathContour(SkPath::Iter& iter) {
+ uint8_t verb;
+ SkPoint pts[4];
+ while ((verb = iter.next(pts)) != SkPath::kDone_Verb) {
+ switch (verb) {
+ case SkPath::kMove_Verb:
+ SkDebugf("path.moveTo(%1.9gf,%1.9gf);\n", pts[0].fX, pts[0].fY);
+ continue;
+ case SkPath::kLine_Verb:
+ SkDebugf("path.lineTo(%1.9gf,%1.9gf);\n", pts[1].fX, pts[1].fY);
+ break;
+ case SkPath::kQuad_Verb:
+ SkDebugf("path.quadTo(%1.9gf,%1.9gf, %1.9gf,%1.9gf);\n",
+ pts[1].fX, pts[1].fY, pts[2].fX, pts[2].fY);
+ break;
+ case SkPath::kCubic_Verb:
+ SkDebugf("path.cubicTo(%1.9gf,%1.9gf, %1.9gf,%1.9gf, %1.9gf,%1.9gf);\n",
+ pts[1].fX, pts[1].fY, pts[2].fX, pts[2].fY, pts[3].fX, pts[3].fY);
+ break;
+ case SkPath::kClose_Verb:
+ SkDebugf("path.close();\n");
+ break;
+ default:
+ SkDEBUGFAIL("bad verb");
+ return;
+ }
+ }
+}
+
+static void showPath(const SkPath& path) {
+ SkPath::Iter iter(path, true);
+ int rectCount = path.isRectContours() ? path.rectContours(NULL, NULL) : 0;
+ if (rectCount > 0) {
+ SkTDArray<SkRect> rects;
+ SkTDArray<SkPath::Direction> directions;
+ rects.setCount(rectCount);
+ directions.setCount(rectCount);
+ path.rectContours(rects.begin(), directions.begin());
+ for (int contour = 0; contour < rectCount; ++contour) {
+ const SkRect& rect = rects[contour];
+ SkDebugf("path.addRect(%1.9g, %1.9g, %1.9g, %1.9g, %s);\n", rect.fLeft, rect.fTop,
+ rect.fRight, rect.fBottom, directions[contour] == SkPath::kCCW_Direction
+ ? "SkPath::kCCW_Direction" : "SkPath::kCW_Direction");
+ }
+ return;
+ }
+ iter.setPath(path, true);
+ showPathContour(iter);
+}
+
+static const char* parsePath(const char* data) {
+ SkPath fPath;
+ SkPoint f = {0, 0};
+ SkPoint c = {0, 0};
+ SkPoint lastc = {0, 0};
+ SkPoint points[3];
+ char op = '\0';
+ char previousOp = '\0';
+ bool relative = false;
+ do {
+ data = skip_ws(data);
+ if (data[0] == '\0')
+ break;
+ char ch = data[0];
+ if (is_digit(ch) || ch == '-' || ch == '+') {
+ if (op == '\0') {
+ SkASSERT(0);
+ return 0;
+ }
+ }
+ else {
+ op = ch;
+ relative = false;
+ if (islower(op)) {
+ op = (char) toupper(op);
+ relative = true;
+ }
+ data++;
+ data = skip_sep(data);
+ }
+ switch (op) {
+ case 'M':
+ data = find_points(data, points, 1, relative, &c);
+ fPath.moveTo(points[0]);
+ op = 'L';
+ c = points[0];
+ break;
+ case 'L':
+ data = find_points(data, points, 1, relative, &c);
+ fPath.lineTo(points[0]);
+ c = points[0];
+ break;
+ case 'H': {
+ SkScalar x;
+ data = find_scalar(data, &x, relative, c.fX);
+ fPath.lineTo(x, c.fY);
+ c.fX = x;
+ }
+ break;
+ case 'V': {
+ SkScalar y;
+ data = find_scalar(data, &y, relative, c.fY);
+ fPath.lineTo(c.fX, y);
+ c.fY = y;
+ }
+ break;
+ case 'C':
+ data = find_points(data, points, 3, relative, &c);
+ goto cubicCommon;
+ case 'S':
+ data = find_points(data, &points[1], 2, relative, &c);
+ points[0] = c;
+ if (previousOp == 'C' || previousOp == 'S') {
+ points[0].fX -= lastc.fX - c.fX;
+ points[0].fY -= lastc.fY - c.fY;
+ }
+ cubicCommon:
+ // if (data[0] == '\0')
+ // return;
+#if QUADRATIC_APPROXIMATION
+ quadApprox(fPath, points[0], points[1], points[2]);
+#else //this way just does a boring, slow old cubic
+ fPath.cubicTo(points[0], points[1], points[2]);
+#endif
+ //if we are using the quadApprox, lastc is what it would have been if we had used
+ //cubicTo
+ lastc = points[1];
+ c = points[2];
+ break;
+ case 'Q': // Quadratic Bezier Curve
+ data = find_points(data, points, 2, relative, &c);
+ goto quadraticCommon;
+ case 'T':
+ data = find_points(data, &points[1], 1, relative, &c);
+ points[0] = points[1];
+ if (previousOp == 'Q' || previousOp == 'T') {
+ points[0].fX = c.fX * 2 - lastc.fX;
+ points[0].fY = c.fY * 2 - lastc.fY;
+ }
+ quadraticCommon:
+ fPath.quadTo(points[0], points[1]);
+ lastc = points[0];
+ c = points[1];
+ break;
+ case 'Z':
+ fPath.close();
+#if 0 // !!! still a bug?
+ if (fPath.isEmpty() && (f.fX != 0 || f.fY != 0)) {
+ c.fX -= SkScalar.Epsilon; // !!! enough?
+ fPath.moveTo(c);
+ fPath.lineTo(f);
+ fPath.close();
+ }
+#endif
+ c = f;
+ op = '\0';
+ break;
+ case '~': {
+ SkPoint args[2];
+ data = find_points(data, args, 2, false, NULL);
+ fPath.moveTo(args[0].fX, args[0].fY);
+ fPath.lineTo(args[1].fX, args[1].fY);
+ }
+ break;
+ default:
+ SkASSERT(0);
+ return 0;
+ }
+ if (previousOp == 0)
+ f = c;
+ previousOp = op;
+ } while (data[0] != '"');
+ showPath(fPath);
+ return data;
+}
+
+const char pathPrefix[] = "<path fill=\"";
+
+void parseSVG();
+void parseSVG() {
+ const char* data = logoStr;
+ const char* dataEnd = logoStr + logoStrLen - 1;
+ while (data < dataEnd) {
+ SkASSERT(strncmp(data, pathPrefix, sizeof(pathPrefix) - 1) == 0);
+ data += sizeof(pathPrefix) - 1;
+ SkDebugf("paint.setColor(0xFF%c%c%c%c%c%c);\n", data[1], data[2], data[3], data[4],
+ data[5], data[6]);
+ data += 8;
+ SkASSERT(strncmp(data, "d=\"", 3) == 0);
+ data += 3;
+ SkDebugf("path.reset();\n");
+ data = parsePath(data);
+ SkDebugf("canvas->drawPath(path, paint);\n");
+ SkASSERT(strncmp(data, "\"/>", 3) == 0);
+ data += 3;
+ }
+}
+
diff --git a/experimental/Intersection/LogoPlay.h b/experimental/Intersection/LogoPlay.h
new file mode 100644
index 0000000..70e74da
--- /dev/null
+++ b/experimental/Intersection/LogoPlay.h
@@ -0,0 +1,9 @@
+/*
+ * LogoPlay.h
+ * shapeops_edge
+ *
+ * Created by Cary Clark on 2/6/13.
+ * Copyright 2013 __MyCompanyName__. All rights reserved.
+ *
+ */
+
diff --git a/experimental/Intersection/QuadraticBounds.cpp b/experimental/Intersection/QuadraticBounds.cpp
index a86b7ed..193743b 100644
--- a/experimental/Intersection/QuadraticBounds.cpp
+++ b/experimental/Intersection/QuadraticBounds.cpp
@@ -8,11 +8,6 @@
#include "CurveUtilities.h"
#include "Extrema.h"
-static int isBoundedByEndPoints(double a, double b, double c)
-{
- return (a <= b && b <= c) || (a >= b && b >= c);
-}
-
double leftMostT(const Quadratic& quad, double startT, double endT) {
double leftT;
if (findExtrema(quad[0].x, quad[1].x, quad[2].x, &leftT)
@@ -31,12 +26,11 @@
add(quad[2]);
double tValues[2];
int roots = 0;
- if (!isBoundedByEndPoints(quad[0].x, quad[1].x, quad[2].x)) {
+ if (!between(quad[0].x, quad[1].x, quad[2].x)) {
roots = findExtrema(quad[0].x, quad[1].x, quad[2].x, tValues);
}
- if (!isBoundedByEndPoints(quad[0].y, quad[1].y, quad[2].y)) {
- roots += findExtrema(quad[0].y, quad[1].y, quad[2].y,
- &tValues[roots]);
+ if (!between(quad[0].y, quad[1].y, quad[2].y)) {
+ roots += findExtrema(quad[0].y, quad[1].y, quad[2].y, &tValues[roots]);
}
for (int x = 0; x < roots; ++x) {
_Point result;
diff --git a/experimental/Intersection/QuadraticImplicit.cpp b/experimental/Intersection/QuadraticImplicit.cpp
index 50f5633..937bb6a 100644
--- a/experimental/Intersection/QuadraticImplicit.cpp
+++ b/experimental/Intersection/QuadraticImplicit.cpp
@@ -59,7 +59,8 @@
return quarticRootsReal(t4, t3, t2, t1, t0, roots);
}
-static void addValidRoots(const double roots[4], const int count, const int side, Intersections& i) {
+static int addValidRoots(const double roots[4], const int count, double valid[4]) {
+ int result = 0;
int index;
for (index = 0; index < count; ++index) {
if (!approximately_zero_or_more(roots[index]) || !approximately_one_or_less(roots[index])) {
@@ -71,8 +72,9 @@
} else if (approximately_greater_than_one(t)) {
t = 1;
}
- i.insertOne(t, side);
+ valid[result++] = t;
}
+ return result;
}
static bool onlyEndPtsInCommon(const Quadratic& q1, const Quadratic& q2, Intersections& i) {
@@ -106,7 +108,7 @@
for (int i1 = 0; i1 < 3; i1 += 2) {
for (int i2 = 0; i2 < 3; i2 += 2) {
if (q1[i1] == q2[i2]) {
- i.insert(i1 >> 1, i2 >> 1);
+ i.insert(i1 >> 1, i2 >> 1, q1[i1]);
}
}
}
@@ -147,10 +149,10 @@
}
_Point pt2;
xy_at_t(q1, rootTs.fT[0][0], pt2.x, pt2.y);
- if (!pt2.approximatelyEqual(mid)) {
+ if (!pt2.approximatelyEqualHalf(mid)) {
return false;
}
- i.add(rootTs.fT[0][0], tMid);
+ i.insertSwap(rootTs.fT[0][0], tMid, pt2);
return true;
}
@@ -281,11 +283,11 @@
Intersections firstI, secondI;
relaxedIsLinear(pair.first(), rounder, firstI);
for (int index = 0; index < firstI.used(); ++index) {
- i.insert(firstI.fT[0][index] * 0.5, firstI.fT[1][index]);
+ i.insert(firstI.fT[0][index] * 0.5, firstI.fT[1][index], firstI.fPt[index]);
}
relaxedIsLinear(pair.second(), rounder, secondI);
for (int index = 0; index < secondI.used(); ++index) {
- i.insert(0.5 + secondI.fT[0][index] * 0.5, secondI.fT[1][index]);
+ i.insert(0.5 + secondI.fT[0][index] * 0.5, secondI.fT[1][index], secondI.fPt[index]);
}
}
if (m2 < m1) {
@@ -358,59 +360,60 @@
bool useVertical = fabs(q1[0].x - q1[2].x) < fabs(q1[0].y - q1[2].y);
double t;
if ((t = axialIntersect(q1, q2[0], useVertical)) >= 0) {
- i.addCoincident(t, 0);
+ i.insertCoincident(t, 0, q2[0]);
}
if ((t = axialIntersect(q1, q2[2], useVertical)) >= 0) {
- i.addCoincident(t, 1);
+ i.insertCoincident(t, 1, q2[2]);
}
useVertical = fabs(q2[0].x - q2[2].x) < fabs(q2[0].y - q2[2].y);
if ((t = axialIntersect(q2, q1[0], useVertical)) >= 0) {
- i.addCoincident(0, t);
+ i.insertCoincident(0, t, q1[0]);
}
if ((t = axialIntersect(q2, q1[2], useVertical)) >= 0) {
- i.addCoincident(1, t);
+ i.insertCoincident(1, t, q1[2]);
}
- SkASSERT(i.fCoincidentUsed <= 2);
- return i.fCoincidentUsed > 0;
+ SkASSERT(i.coincidentUsed() <= 2);
+ return i.coincidentUsed() > 0;
}
- double roots1[4], roots2[4];
+ int index;
bool useCubic = q1[0] == q2[0] || q1[0] == q2[2] || q1[2] == q2[0];
+ double roots1[4];
int rootCount = findRoots(i2, q1, roots1, useCubic);
// OPTIMIZATION: could short circuit here if all roots are < 0 or > 1
+ double roots1Copy[4];
+ int r1Count = addValidRoots(roots1, rootCount, roots1Copy);
+ _Point pts1[4];
+ for (index = 0; index < r1Count; ++index) {
+ xy_at_t(q1, roots1Copy[index], pts1[index].x, pts1[index].y);
+ }
+ double roots2[4];
int rootCount2 = findRoots(i1, q2, roots2, useCubic);
- addValidRoots(roots1, rootCount, 0, i);
- addValidRoots(roots2, rootCount2, 1, i);
- if (i.insertBalanced() && i.fUsed <= 1) {
- if (i.fUsed == 1) {
- _Point xy1, xy2;
- xy_at_t(q1, i.fT[0][0], xy1.x, xy1.y);
- xy_at_t(q2, i.fT[1][0], xy2.x, xy2.y);
- if (!xy1.approximatelyEqual(xy2)) {
- --i.fUsed;
- --i.fUsed2;
+ double roots2Copy[4];
+ int r2Count = addValidRoots(roots2, rootCount2, roots2Copy);
+ _Point pts2[4];
+ for (index = 0; index < r2Count; ++index) {
+ xy_at_t(q2, roots2Copy[index], pts2[index].x, pts2[index].y);
+ }
+ if (r1Count == r2Count && r1Count <= 1) {
+ if (r1Count == 1) {
+ if (pts1[0].approximatelyEqualHalf(pts2[0])) {
+ i.insert(roots1Copy[0], roots2Copy[0], pts1[0]);
}
}
return i.intersected();
}
- _Point pts[4];
int closest[4];
double dist[4];
- int index, ndex2;
- for (ndex2 = 0; ndex2 < i.fUsed2; ++ndex2) {
- xy_at_t(q2, i.fT[1][ndex2], pts[ndex2].x, pts[ndex2].y);
- }
bool foundSomething = false;
- for (index = 0; index < i.fUsed; ++index) {
- _Point xy;
- xy_at_t(q1, i.fT[0][index], xy.x, xy.y);
+ for (index = 0; index < r1Count; ++index) {
dist[index] = DBL_MAX;
closest[index] = -1;
- for (ndex2 = 0; ndex2 < i.fUsed2; ++ndex2) {
- if (!pts[ndex2].approximatelyEqual(xy)) {
+ for (int ndex2 = 0; ndex2 < r2Count; ++ndex2) {
+ if (!pts2[ndex2].approximatelyEqualHalf(pts1[index])) {
continue;
}
- double dx = pts[ndex2].x - xy.x;
- double dy = pts[ndex2].y - xy.y;
+ double dx = pts2[ndex2].x - pts1[index].x;
+ double dy = pts2[ndex2].y - pts1[index].y;
double distance = dx * dx + dy * dy;
if (dist[index] <= distance) {
continue;
@@ -431,18 +434,15 @@
;
}
}
- if (i.fUsed && i.fUsed2 && !foundSomething) {
+ if (r1Count && r2Count && !foundSomething) {
relaxedIsLinear(q1, q2, i);
return i.intersected();
}
- double roots1Copy[4], roots2Copy[4];
- memcpy(roots1Copy, i.fT[0], i.fUsed * sizeof(double));
- memcpy(roots2Copy, i.fT[1], i.fUsed2 * sizeof(double));
int used = 0;
do {
double lowest = DBL_MAX;
int lowestIndex = -1;
- for (index = 0; index < i.fUsed; ++index) {
+ for (index = 0; index < r1Count; ++index) {
if (closest[index] < 0) {
continue;
}
@@ -454,11 +454,10 @@
if (lowestIndex < 0) {
break;
}
- i.fT[0][used] = roots1Copy[lowestIndex];
- i.fT[1][used] = roots2Copy[closest[lowestIndex]];
+ i.insert(roots1Copy[lowestIndex], roots2Copy[closest[lowestIndex]],
+ pts1[lowestIndex]);
closest[lowestIndex] = -1;
- } while (++used < i.fUsed);
- i.fUsed = i.fUsed2 = used;
+ } while (++used < r1Count);
i.fFlip = false;
return i.intersected();
}
diff --git a/experimental/Intersection/QuadraticIntersection_Test.cpp b/experimental/Intersection/QuadraticIntersection_Test.cpp
index 54536d8..8bddee2 100644
--- a/experimental/Intersection/QuadraticIntersection_Test.cpp
+++ b/experimental/Intersection/QuadraticIntersection_Test.cpp
@@ -29,10 +29,8 @@
printf("[%d] quad2 order=%d\n", (int) index, order2);
}
if (order1 == 3 && order2 == 3) {
- Intersections intersections, intersections2;
- intersect(reduce1, reduce2, intersections);
- intersect2(reduce1, reduce2, intersections2);
- SkASSERT(intersections.used() == intersections2.used());
+ Intersections intersections;
+ intersect2(reduce1, reduce2, intersections);
if (intersections.intersected()) {
for (int pt = 0; pt < intersections.used(); ++pt) {
double tt1 = intersections.fT[0][pt];
@@ -49,10 +47,6 @@
printf("%s [%d,%d] y!= t1=%g (%g,%g) t2=%g (%g,%g)\n",
__FUNCTION__, (int)index, pt, tt1, tx1, ty1, tt2, tx2, ty2);
}
- tt1 = intersections2.fT[0][pt];
- SkASSERT(approximately_equal(intersections.fT[0][pt], tt1));
- tt2 = intersections2.fT[1][pt];
- SkASSERT(approximately_equal(intersections.fT[1][pt], tt2));
}
}
}
@@ -60,6 +54,20 @@
}
static const Quadratic testSet[] = {
+{{0, 0}, {0.51851851851851849, 1.0185185185185186}, {1.2592592592592591, 1.9259259259259258}},
+{{1.2592592592592593, 1.9259259259259265}, {0.51851851851851893, 1.0185185185185195}, {0, 0}},
+
+ {{1.93281168,2.58856757}, {2.38543691,2.7096125}, {2.51967352,2.34531784}},
+ {{2.51967352,2.34531784}, {2.65263731,2.00639194}, {3.1212119,1.98608967}},
+ {{2.09544533,2.51981963}, {2.33331524,2.25252128}, {2.92003302,2.39442311}},
+
+
+{{0.924337655,1.94072717}, {1.25185043,1.52836494}, {1.71793901,1.06149951}},
+{{0.940798831,1.67439357}, {1.25988251,1.39778567}, {1.71791672,1.06650313}},
+
+ {{0.924337655,1.94072717}, {1.39158994,1.32418496}, {2.14967426,0.687365435}},
+ {{0.940798831,1.67439357}, {1.48941875,1.16280321}, {2.47884711,0.60465921}},
+
{{1.7465749139282332,1.9930452039527999}, {1.8320006564080331,1.859481345189089}, {1.8731035127758437,1.6344055934266613}},
{{1.8731035127758437,1.6344055934266613}, {1.89928170345231,1.5006405518943067}, {1.9223833226085514,1.3495796165215643}},
{{1.74657491,1.9930452}, {1.87407679,1.76762853}, {1.92238332,1.34957962}},
@@ -149,8 +157,6 @@
const size_t testSetCount = sizeof(testSet) / sizeof(testSet[0]);
-#define ONE_OFF_DEBUG 1
-
static void oneOffTest1(size_t outer, size_t inner) {
const Quadratic& quad1 = testSet[outer];
const Quadratic& quad2 = testSet[inner];
@@ -186,10 +192,7 @@
}
void QuadraticIntersection_OneOffTest() {
- oneOffTest1(0, 3);
- oneOffTest1(0, 4);
- oneOffTest1(1, 3);
- oneOffTest1(1, 4);
+ oneOffTest1(0, 1);
}
static void oneOffTests() {
@@ -216,6 +219,7 @@
Intersections intersections2;
intersect2(quad1, quad2, intersections2);
SkASSERT(intersections2.coincidentUsed() == 2);
+ SkASSERT(intersections2.used() == 2);
for (int pt = 0; pt < intersections2.coincidentUsed(); ++pt) {
double tt1 = intersections2.fT[0][pt];
double tt2 = intersections2.fT[1][pt];
@@ -268,12 +272,12 @@
static void hullIntersect(const Quadratic& q1, const Quadratic& q2) {
SkDebugf("%s", __FUNCTION__);
- double aRange[2], bRange[2];
+ Intersections ts;
for (int i1 = 0; i1 < 3; ++i1) {
_Line l1 = {q1[i1], q1[(i1 + 1) % 3]};
for (int i2 = 0; i2 < 3; ++i2) {
_Line l2 = {q2[i2], q2[(i2 + 1) % 3]};
- if (intersect(l1, l2, aRange, bRange)) {
+ if (intersect(l1, l2, ts)) {
SkDebugf(" [%d,%d]", i1, i2);
}
}
diff --git a/experimental/Intersection/QuadraticUtilities.cpp b/experimental/Intersection/QuadraticUtilities.cpp
index a84009d..d33fda8 100644
--- a/experimental/Intersection/QuadraticUtilities.cpp
+++ b/experimental/Intersection/QuadraticUtilities.cpp
@@ -5,6 +5,7 @@
* found in the LICENSE file.
*/
#include "CubicUtilities.h"
+#include "Extrema.h"
#include "QuadraticUtilities.h"
#include "TriangleUtilities.h"
@@ -45,6 +46,27 @@
return pointInTriangle((const Triangle&) quad, pt);
}
+_Point top(const Quadratic& quad, double startT, double endT) {
+ Quadratic sub;
+ sub_divide(quad, startT, endT, sub);
+ _Point topPt = sub[0];
+ if (topPt.y > sub[2].y || (topPt.y == sub[2].y && topPt.x > sub[2].x)) {
+ topPt = sub[2];
+ }
+ if (!between(sub[0].y, sub[1].y, sub[2].y)) {
+ double extremeT;
+ if (findExtrema(sub[0].y, sub[1].y, sub[2].y, &extremeT)) {
+ extremeT = startT + (endT - startT) * extremeT;
+ _Point test;
+ xy_at_t(quad, extremeT, test.x, test.y);
+ if (topPt.y > test.y || (topPt.y == test.y && topPt.x > test.x)) {
+ topPt = test;
+ }
+ }
+ }
+ return topPt;
+}
+
/*
Numeric Solutions (5.6) suggests to solve the quadratic by computing
Q = -1/2(B + sgn(B)Sqrt(B^2 - 4 A C))
diff --git a/experimental/Intersection/QuadraticUtilities.h b/experimental/Intersection/QuadraticUtilities.h
index f6fb878..b507b5f 100644
--- a/experimental/Intersection/QuadraticUtilities.h
+++ b/experimental/Intersection/QuadraticUtilities.h
@@ -36,6 +36,7 @@
int quadraticRootsReal(double A, double B, double C, double t[2]);
int quadraticRootsValidT(const double A, const double B, const double C, double s[2]);
void sub_divide(const Quadratic& src, double t1, double t2, Quadratic& dst);
+_Point top(const Quadratic& , double startT, double endT);
void xy_at_t(const Quadratic& , double t, double& x, double& y);
#endif
diff --git a/experimental/Intersection/Simplify.cpp b/experimental/Intersection/Simplify.cpp
index f799699..ed7c62e 100644
--- a/experimental/Intersection/Simplify.cpp
+++ b/experimental/Intersection/Simplify.cpp
@@ -31,6 +31,7 @@
#define APPROXIMATE_CUBICS 1
#define DEBUG_UNUSED 0 // set to expose unused functions
+
#define FORCE_RELEASE 1 // set force release to 1 for multiple thread -- no debugging
#if FORCE_RELEASE || defined SK_RELEASE
@@ -109,7 +110,7 @@
Intersections& intersections) {
MAKE_CONST_LINE(aLine, a);
MAKE_CONST_LINE(bLine, b);
- return intersect(aLine, bLine, intersections.fT[0], intersections.fT[1]);
+ return intersect(aLine, bLine, intersections);
}
static int QuadLineIntersect(const SkPoint a[3], const SkPoint b[2],
@@ -136,7 +137,7 @@
#else
intersect(aQuad, bQuad, intersections);
#endif
- return intersections.fUsed ? intersections.fUsed : intersections.fCoincidentUsed;
+ return intersections.fUsed;
}
#if APPROXIMATE_CUBICS
@@ -152,11 +153,11 @@
MAKE_CONST_CUBIC(aCubic, a);
MAKE_CONST_CUBIC(bCubic, b);
#if APPROXIMATE_CUBICS
- intersect2(aCubic, bCubic, intersections);
+ intersect3(aCubic, bCubic, intersections);
#else
intersect(aCubic, bCubic, intersections);
#endif
- return intersections.fUsed ? intersections.fUsed : intersections.fCoincidentUsed;
+ return intersections.fUsed;
}
static int HLineIntersect(const SkPoint a[2], SkScalar left, SkScalar right,
@@ -366,6 +367,31 @@
CubicDYAtT
};
+static SkPoint LineDXDYAtT(const SkPoint a[2], double ) {
+ return a[1] - a[0];
+}
+
+static SkPoint QuadDXDYAtT(const SkPoint a[3], double t) {
+ MAKE_CONST_QUAD(quad, a);
+ _Point pt;
+ dxdy_at_t(quad, t, pt);
+ return pt.asSkPoint();
+}
+
+static SkPoint CubicDXDYAtT(const SkPoint a[4], double t) {
+ MAKE_CONST_CUBIC(cubic, a);
+ _Point pt;
+ dxdy_at_t(cubic, t, pt);
+ return pt.asSkPoint();
+}
+
+static SkPoint (* const SegmentDXDYAtT[])(const SkPoint [], double ) = {
+ NULL,
+ LineDXDYAtT,
+ QuadDXDYAtT,
+ CubicDXDYAtT
+};
+
static void LineSubDivide(const SkPoint a[2], double startT, double endT,
SkPoint sub[2]) {
MAKE_CONST_LINE(aLine, a);
@@ -428,6 +454,25 @@
sub_divide(aCubic, startT, endT, dst);
}
+static SkPoint QuadTop(const SkPoint a[3], double startT, double endT) {
+ MAKE_CONST_QUAD(quad, a);
+ _Point topPt = top(quad, startT, endT);
+ return topPt.asSkPoint();
+}
+
+static SkPoint CubicTop(const SkPoint a[3], double startT, double endT) {
+ MAKE_CONST_CUBIC(cubic, a);
+ _Point topPt = top(cubic, startT, endT);
+ return topPt.asSkPoint();
+}
+
+static SkPoint (* SegmentTop[])(const SkPoint[], double , double ) = {
+ NULL,
+ NULL,
+ QuadTop,
+ CubicTop
+};
+
#if DEBUG_UNUSED
static void QuadSubBounds(const SkPoint a[3], double startT, double endT,
SkRect& bounds) {
@@ -819,7 +864,7 @@
nextC = 3;
#if 1 // FIXME: try enabling this and see if a) it's called and b) does it break anything
if (dx() == 0 && dy() == 0) {
- SkDebugf("*** %s cubic is line\n");
+ SkDebugf("*** %s cubic is line\n", __FUNCTION__);
fTangent1.cubicEndPoints(fCurvePart, 0, 3);
}
#endif
@@ -1261,31 +1306,50 @@
return false;
}
- void activeLeftTop(SkPoint& result) const {
+ SkPoint activeLeftTop(bool onlySortable, int* firstT) const {
SkASSERT(!done());
+ SkPoint topPt = {SK_ScalarMax, SK_ScalarMax};
int count = fTs.count();
- result.fX = result.fY = SK_ScalarMax;
+ // see if either end is not done since we want smaller Y of the pair
bool lastDone = true;
bool lastUnsortable = false;
+ double lastT = -1;
for (int index = 0; index < count; ++index) {
const Span& span = fTs[index];
- if (span.fUnsortableStart | lastUnsortable) {
+ if (onlySortable && (span.fUnsortableStart || lastUnsortable)) {
goto next;
}
- if (!span.fDone | !lastDone) {
- const SkPoint& xy = xyAtT(index);
- if (result.fY < xy.fY) {
- goto next;
+ if (span.fDone && lastDone) {
+ goto next;
+ }
+ if (approximately_negative(span.fT - lastT)) {
+ goto next;
+ }
+ {
+ const SkPoint& xy = xyAtT(&span);
+ if (topPt.fY > xy.fY || (topPt.fY == xy.fY && topPt.fX > xy.fX)) {
+ topPt = xy;
+ if (firstT) {
+ *firstT = index;
+ }
}
- if (result.fY == xy.fY && result.fX < xy.fX) {
- goto next;
+ if (fVerb != SkPath::kLine_Verb && !lastDone) {
+ SkPoint curveTop = (*SegmentTop[fVerb])(fPts, lastT, span.fT);
+ if (topPt.fY > curveTop.fY || (topPt.fY == curveTop.fY
+ && topPt.fX > curveTop.fX)) {
+ topPt = curveTop;
+ if (firstT) {
+ *firstT = index;
+ }
+ }
}
- result = xy;
+ lastT = span.fT;
}
next:
lastDone = span.fDone;
lastUnsortable = span.fUnsortableEnd;
}
+ return topPt;
}
bool activeOp(int index, int endIndex, int xorMiMask, int xorSuMask, ShapeOp op) {
@@ -1397,7 +1461,8 @@
fTs[tIndexStart].fT, xyAtT(tIndexStart).fX,
xyAtT(tIndexStart).fY);
#endif
- addTPair(fTs[tIndexStart].fT, other, other.fTs[oIndex].fT, false);
+ addTPair(fTs[tIndexStart].fT, other, other.fTs[oIndex].fT, false,
+ fTs[tIndexStart].fPt);
}
if (nextT < 1 && fTs[tIndex].fWindValue) {
#if DEBUG_CONCIDENT
@@ -1406,7 +1471,7 @@
fTs[tIndex].fT, xyAtT(tIndex).fX,
xyAtT(tIndex).fY);
#endif
- addTPair(fTs[tIndex].fT, other, other.fTs[oIndexStart].fT, false);
+ addTPair(fTs[tIndex].fT, other, other.fTs[oIndexStart].fT, false, fTs[tIndex].fPt);
}
} else {
SkASSERT(!other.fTs[oIndexStart].fWindValue);
@@ -1443,11 +1508,12 @@
do {
++tIndex;
} while (!approximately_negative(tStart - fTs[tIndex].fT));
+ SkPoint ptStart = fTs[tIndex].fPt;
do {
++oIndex;
} while (!approximately_negative(oStart - other.fTs[oIndex].fT));
if (tIndex > 0 || oIndex > 0 || fOperand != other.fOperand) {
- addTPair(tStart, other, oStart, false);
+ addTPair(tStart, other, oStart, false, ptStart);
}
tStart = fTs[tIndex].fT;
oStart = other.fTs[oIndex].fT;
@@ -1457,6 +1523,7 @@
nextT = fTs[++tIndex].fT;
} while (approximately_negative(nextT - tStart));
tStart = nextT;
+ ptStart = fTs[tIndex].fPt;
do {
nextT = other.fTs[++oIndex].fT;
} while (approximately_negative(nextT - oStart));
@@ -1464,7 +1531,7 @@
if (tStart == 1 && oStart == 1 && fOperand == other.fOperand) {
break;
}
- addTPair(tStart, other, oStart, false);
+ addTPair(tStart, other, oStart, false, ptStart);
} while (tStart < 1 && oStart < 1 && !approximately_negative(oEnd - oStart));
}
@@ -1563,7 +1630,7 @@
// resolve overlapping ts when considering coincidence later
// add non-coincident intersection. Resulting edges are sorted in T.
- int addT(double newT, Segment* other) {
+ int addT(double newT, Segment* other, const SkPoint& pt) {
// FIXME: in the pathological case where there is a ton of intercepts,
// binary search?
int insertedAt = -1;
@@ -1597,7 +1664,7 @@
}
span->fT = newT;
span->fOther = other;
- span->fPt.fX = SK_ScalarNaN;
+ span->fPt = pt;
span->fWindSum = SK_MinS32;
span->fOppSum = SK_MinS32;
span->fWindValue = 1;
@@ -1733,8 +1800,8 @@
}
}
- int addUnsortableT(double newT, Segment* other, bool start) {
- int result = addT(newT, other);
+ int addUnsortableT(double newT, Segment* other, bool start, const SkPoint& pt) {
+ int result = addT(newT, other, pt);
Span* span = &fTs[result];
if (start) {
if (result > 0) {
@@ -1838,7 +1905,7 @@
// FIXME: this doesn't prevent the same span from being added twice
// fix in caller, SkASSERT here?
- void addTPair(double t, Segment& other, double otherT, bool borrowWind) {
+ void addTPair(double t, Segment& other, double otherT, bool borrowWind, const SkPoint& pt) {
int tCount = fTs.count();
for (int tIndex = 0; tIndex < tCount; ++tIndex) {
const Span& span = fTs[tIndex];
@@ -1858,8 +1925,8 @@
SkDebugf("%s addTPair this=%d %1.9g other=%d %1.9g\n",
__FUNCTION__, fID, t, other.fID, otherT);
#endif
- int insertedAt = addT(t, &other);
- int otherInsertedAt = other.addT(otherT, this);
+ int insertedAt = addT(t, &other, pt);
+ int otherInsertedAt = other.addT(otherT, this, pt);
addOtherT(insertedAt, otherT, otherInsertedAt);
other.addOtherT(otherInsertedAt, t, insertedAt);
matchWindingValue(insertedAt, t, borrowWind);
@@ -2188,6 +2255,14 @@
bool done(const Angle* angle) const {
return done(SkMin32(angle->start(), angle->end()));
}
+
+ SkPoint dxdy(int index) const {
+ return (*SegmentDXDYAtT[fVerb])(fPts, fTs[index].fT);
+ }
+
+ SkScalar dy(int index) const {
+ return (*SegmentDYAtT[fVerb])(fPts, fTs[index].fT);
+ }
bool equalPoints(int greaterTIndex, int lesserTIndex) {
SkASSERT(greaterTIndex >= lesserTIndex);
@@ -2696,8 +2771,7 @@
}
}
- // start here;
- // either:
+ // FIXME: either:
// a) mark spans with either end unsortable as done, or
// b) rewrite findTop / findTopSegment / findTopContour to iterate further
// when encountering an unsortable span
@@ -2710,29 +2784,7 @@
// topmost tangent from y-min to first pt is closer to horizontal
SkASSERT(!done());
int firstT = -1;
- SkPoint topPt;
- topPt.fY = SK_ScalarMax;
- int count = fTs.count();
- // see if either end is not done since we want smaller Y of the pair
- bool lastDone = true;
- bool lastUnsortable = false;
- for (int index = 0; index < count; ++index) {
- const Span& span = fTs[index];
- if (onlySortable && (span.fUnsortableStart || lastUnsortable)) {
- goto next;
- }
- if (!span.fDone | !lastDone) {
- const SkPoint& intercept = xyAtT(&span);
- if (topPt.fY > intercept.fY || (topPt.fY == intercept.fY
- && topPt.fX > intercept.fX)) {
- topPt = intercept;
- firstT = index;
- }
- }
- next:
- lastDone = span.fDone;
- lastUnsortable = span.fUnsortableEnd;
- }
+ SkPoint topPt = activeLeftTop(onlySortable, &firstT);
SkASSERT(firstT >= 0);
// sort the edges to find the leftmost
int step = 1;
@@ -2767,6 +2819,13 @@
tIndex = angle->end();
endIndex = angle->start();
} while (leftSegment->fTs[SkMin32(tIndex, endIndex)].fDone);
+ if (leftSegment->verb() >= SkPath::kQuad_Verb) {
+ SkScalar dyE = leftSegment->dy(endIndex);
+ SkScalar dyS = leftSegment->dy(tIndex);
+ if (dyE < 0 && dyS > 0) {
+ SkTSwap(tIndex, endIndex);
+ }
+ }
SkASSERT(!leftSegment->fTs[SkMin32(tIndex, endIndex)].fTiny);
return leftSegment;
}
@@ -4152,6 +4211,7 @@
Contour* fContours[2];
int fSegments[2];
double fTs[2][2];
+ SkPoint fPts[2];
};
class Contour {
@@ -4176,20 +4236,12 @@
coincidence.fContours[1] = other;
coincidence.fSegments[0] = index;
coincidence.fSegments[1] = otherIndex;
- if (fSegments[index].verb() == SkPath::kLine_Verb &&
- other->fSegments[otherIndex].verb() == SkPath::kLine_Verb) {
- // FIXME: coincident lines use legacy Ts instead of coincident Ts
- coincidence.fTs[swap][0] = ts.fT[0][0];
- coincidence.fTs[swap][1] = ts.fT[0][1];
- coincidence.fTs[!swap][0] = ts.fT[1][0];
- coincidence.fTs[!swap][1] = ts.fT[1][1];
- } else if (fSegments[index].verb() >= SkPath::kQuad_Verb &&
- other->fSegments[otherIndex].verb() >= SkPath::kQuad_Verb) {
- coincidence.fTs[swap][0] = ts.fCoincidentT[0][0];
- coincidence.fTs[swap][1] = ts.fCoincidentT[0][1];
- coincidence.fTs[!swap][0] = ts.fCoincidentT[1][0];
- coincidence.fTs[!swap][1] = ts.fCoincidentT[1][1];
- }
+ coincidence.fTs[swap][0] = ts.fT[0][0];
+ coincidence.fTs[swap][1] = ts.fT[0][1];
+ coincidence.fTs[!swap][0] = ts.fT[1][0];
+ coincidence.fTs[!swap][1] = ts.fT[1][1];
+ coincidence.fPts[0] = ts.fPt[0].asSkPoint();
+ coincidence.fPts[1] = ts.fPt[1].asSkPoint();
}
void addCross(const Contour* crosser) {
@@ -4221,13 +4273,14 @@
return fSegments.count();
}
- int addT(int segIndex, double newT, Contour* other, int otherIndex) {
+ int addT(int segIndex, double newT, Contour* other, int otherIndex, const SkPoint& pt) {
containsIntercepts();
- return fSegments[segIndex].addT(newT, &other->fSegments[otherIndex]);
+ return fSegments[segIndex].addT(newT, &other->fSegments[otherIndex], pt);
}
- int addUnsortableT(int segIndex, double newT, Contour* other, int otherIndex, bool start) {
- return fSegments[segIndex].addUnsortableT(newT, &other->fSegments[otherIndex], start);
+ int addUnsortableT(int segIndex, double newT, Contour* other, int otherIndex, bool start,
+ const SkPoint& pt) {
+ return fSegments[segIndex].addUnsortableT(newT, &other->fSegments[otherIndex], start, pt);
}
const Bounds& bounds() const {
@@ -4340,11 +4393,11 @@
// make sure startT and endT have t entries
if (startT > 0 || oEndT < 1
|| thisOne.isMissing(startT) || other.isMissing(oEndT)) {
- thisOne.addTPair(startT, other, oEndT, true);
+ thisOne.addTPair(startT, other, oEndT, true, coincidence.fPts[0]);
}
if (oStartT > 0 || endT < 1
|| thisOne.isMissing(endT) || other.isMissing(oStartT)) {
- other.addTPair(oStartT, thisOne, endT, true);
+ other.addTPair(oStartT, thisOne, endT, true, coincidence.fPts[1]);
}
if (!thisOne.done() && !other.done()) {
thisOne.addTCancel(startT, endT, other, oStartT, oEndT);
@@ -4352,11 +4405,11 @@
} else {
if (startT > 0 || oStartT > 0
|| thisOne.isMissing(startT) || other.isMissing(oStartT)) {
- thisOne.addTPair(startT, other, oStartT, true);
+ thisOne.addTPair(startT, other, oStartT, true, coincidence.fPts[0]);
}
if (endT < 1 || oEndT < 1
|| thisOne.isMissing(endT) || other.isMissing(oEndT)) {
- other.addTPair(oEndT, thisOne, endT, true);
+ other.addTPair(oEndT, thisOne, endT, true, coincidence.fPts[1]);
}
if (!thisOne.done() && !other.done()) {
thisOne.addTCoincident(startT, endT, other, oStartT, oEndT);
@@ -4411,20 +4464,20 @@
// make sure startT and endT have t entries
if (startT > 0 || oEndT < 1
|| thisOne.isMissing(startT) || other.isMissing(oEndT)) {
- thisOne.addTPair(startT, other, oEndT, true);
+ thisOne.addTPair(startT, other, oEndT, true, coincidence.fPts[0]);
}
if (oStartT > 0 || endT < 1
|| thisOne.isMissing(endT) || other.isMissing(oStartT)) {
- other.addTPair(oStartT, thisOne, endT, true);
+ other.addTPair(oStartT, thisOne, endT, true, coincidence.fPts[1]);
}
} else {
if (startT > 0 || oStartT > 0
|| thisOne.isMissing(startT) || other.isMissing(oStartT)) {
- thisOne.addTPair(startT, other, oStartT, true);
+ thisOne.addTPair(startT, other, oStartT, true, coincidence.fPts[0]);
}
if (endT < 1 || oEndT < 1
|| thisOne.isMissing(endT) || other.isMissing(oEndT)) {
- other.addTPair(oEndT, thisOne, endT, true);
+ other.addTPair(oEndT, thisOne, endT, true, coincidence.fPts[1]);
}
}
#if DEBUG_CONCIDENT
@@ -4554,8 +4607,7 @@
continue;
}
fDone = false;
- SkPoint testXY;
- testSegment->activeLeftTop(testXY);
+ SkPoint testXY = testSegment->activeLeftTop(true, NULL);
if (topStart) {
if (testXY.fY < topLeft.fY) {
continue;
@@ -4908,12 +4960,12 @@
// be nearly equal, any problems caused by this should be taken care
// of later.
// On the edge or out of range values are negative; add 2 to get end
- int addT(double newT, const Work& other) {
- return fContour->addT(fIndex, newT, other.fContour, other.fIndex);
+ int addT(double newT, const Work& other, const SkPoint& pt) {
+ return fContour->addT(fIndex, newT, other.fContour, other.fIndex, pt);
}
- int addUnsortableT(double newT, const Work& other, bool start) {
- return fContour->addUnsortableT(fIndex, newT, other.fContour, other.fIndex, start);
+ int addUnsortableT(double newT, const Work& other, bool start, const SkPoint& pt) {
+ return fContour->addUnsortableT(fIndex, newT, other.fContour, other.fIndex, start, pt);
}
bool advance() {
@@ -5031,9 +5083,9 @@
};
#if DEBUG_ADD_INTERSECTING_TS
-static void debugShowLineIntersection(int pts, const Work& wt,
- const Work& wn, const double wtTs[2], const double wnTs[2]) {
- return;
+static void debugShowLineIntersection(int pts, const Work& wt, const Work& wn,
+ const Intersections& i) {
+ SkASSERT(i.used() == pts);
if (!pts) {
SkDebugf("%s no intersect (%1.9g,%1.9g %1.9g,%1.9g) (%1.9g,%1.9g %1.9g,%1.9g)\n",
__FUNCTION__, wt.pts()[0].fX, wt.pts()[0].fY,
@@ -5041,27 +5093,24 @@
wn.pts()[1].fX, wn.pts()[1].fY);
return;
}
- SkPoint wtOutPt, wnOutPt;
- LineXYAtT(wt.pts(), wtTs[0], &wtOutPt);
- LineXYAtT(wn.pts(), wnTs[0], &wnOutPt);
SkDebugf("%s wtTs[0]=%1.9g (%1.9g,%1.9g %1.9g,%1.9g) (%1.9g,%1.9g)",
__FUNCTION__,
- wtTs[0], wt.pts()[0].fX, wt.pts()[0].fY,
- wt.pts()[1].fX, wt.pts()[1].fY, wtOutPt.fX, wtOutPt.fY);
+ i.fT[0][0], wt.pts()[0].fX, wt.pts()[0].fY,
+ wt.pts()[1].fX, wt.pts()[1].fY, i.fPt[0].x, i.fPt[0].y);
if (pts == 2) {
- SkDebugf(" wtTs[1]=%1.9g", wtTs[1]);
+ SkDebugf(" wtTs[1]=%1.9g (%1.9g,%1.9g)", i.fT[0][1], i.fPt[1].x, i.fPt[1].y);
}
- SkDebugf(" wnTs[0]=%g (%1.9g,%1.9g %1.9g,%1.9g) (%1.9g,%1.9g)",
- wnTs[0], wn.pts()[0].fX, wn.pts()[0].fY,
- wn.pts()[1].fX, wn.pts()[1].fY, wnOutPt.fX, wnOutPt.fY);
+ SkDebugf(" wnTs[0]=%g (%1.9g,%1.9g %1.9g,%1.9g)", i.fT[1][0], wn.pts()[0].fX, wn.pts()[0].fY,
+ wn.pts()[1].fX, wn.pts()[1].fY);
if (pts == 2) {
- SkDebugf(" wnTs[1]=%1.9g", wnTs[1]);
+ SkDebugf(" wnTs[1]=%1.9g", i.fT[1][1]);
}
SkDebugf("\n");
}
static void debugShowQuadLineIntersection(int pts, const Work& wt,
- const Work& wn, const double wtTs[2], const double wnTs[2]) {
+ const Work& wn, const Intersections& i) {
+ SkASSERT(i.used() == pts);
if (!pts) {
SkDebugf("%s no intersect (%1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g)"
" (%1.9g,%1.9g %1.9g,%1.9g)\n",
@@ -5070,31 +5119,25 @@
wn.pts()[0].fX, wn.pts()[0].fY, wn.pts()[1].fX, wn.pts()[1].fY);
return;
}
- SkPoint wtOutPt, wnOutPt;
- QuadXYAtT(wt.pts(), wtTs[0], &wtOutPt);
- LineXYAtT(wn.pts(), wnTs[0], &wnOutPt);
- SkDebugf("%s wtTs[0]=%1.9g (%1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g) (%1.9g,%1.9g)",
- __FUNCTION__,
- wtTs[0], wt.pts()[0].fX, wt.pts()[0].fY,
+ SkDebugf("%s wtTs[0]=%1.9g (%1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g) (%1.9g,%1.9g)", __FUNCTION__,
+ i.fT[0][0], wt.pts()[0].fX, wt.pts()[0].fY,
wt.pts()[1].fX, wt.pts()[1].fY, wt.pts()[2].fX, wt.pts()[2].fY,
- wtOutPt.fX, wtOutPt.fY);
- if (pts == 2) {
- QuadXYAtT(wt.pts(), wtTs[1], &wtOutPt);
- SkDebugf(" wtTs[1]=%1.9g (%1.9g,%1.9g)", wtTs[1], wtOutPt.fX, wtOutPt.fY);
+ i.fPt[0].x, i.fPt[0].y);
+ for (int index = 1; index < pts; ++index) {
+ SkDebugf(" wtTs[%d]=%1.9g (%1.9g,%1.9g)", index, i.fT[0][index],
+ i.fPt[index].x, i.fPt[index].y);
}
- SkDebugf(" wnTs[0]=%g (%1.9g,%1.9g %1.9g,%1.9g) (%1.9g,%1.9g)",
- wnTs[0], wn.pts()[0].fX, wn.pts()[0].fY,
- wn.pts()[1].fX, wn.pts()[1].fY, wnOutPt.fX, wnOutPt.fY);
- if (pts == 2) {
- LineXYAtT(wn.pts(), wnTs[1], &wnOutPt);
- SkDebugf(" wnTs[1]=%1.9g (%1.9g,%1.9g)", wnTs[1], wnOutPt.fX, wnOutPt.fY);
+ SkDebugf(" wnTs[0]=%g (%1.9g,%1.9g %1.9g,%1.9g)", i.fT[1][0], wn.pts()[0].fX, wn.pts()[0].fY,
+ wn.pts()[1].fX, wn.pts()[1].fY);
+ for (int index = 1; index < pts; ++index) {
+ SkDebugf(" wnTs[%d]=%1.9g", index, i.fT[1][index]);
}
SkDebugf("\n");
}
-// FIXME: show more than two intersection points
static void debugShowQuadIntersection(int pts, const Work& wt,
- const Work& wn, const double wtTs[2], const double wnTs[2]) {
+ const Work& wn, const Intersections& i) {
+ SkASSERT(i.used() == pts);
if (!pts) {
SkDebugf("%s no intersect (%1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g)"
" (%1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g)\n",
@@ -5104,29 +5147,26 @@
wn.pts()[2].fX, wn.pts()[2].fY );
return;
}
- SkPoint wtOutPt, wnOutPt;
- QuadXYAtT(wt.pts(), wtTs[0], &wtOutPt);
- QuadXYAtT(wn.pts(), wnTs[0], &wnOutPt);
- SkDebugf("%s wtTs[0]=%1.9g (%1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g) (%1.9g,%1.9g)",
- __FUNCTION__,
- wtTs[0], wt.pts()[0].fX, wt.pts()[0].fY,
+ SkDebugf("%s wtTs[0]=%1.9g (%1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g) (%1.9g,%1.9g)", __FUNCTION__,
+ i.fT[0][0], wt.pts()[0].fX, wt.pts()[0].fY,
wt.pts()[1].fX, wt.pts()[1].fY, wt.pts()[2].fX, wt.pts()[2].fY,
- wtOutPt.fX, wtOutPt.fY);
- if (pts == 2) {
- SkDebugf(" wtTs[1]=%1.9g", wtTs[1]);
+ i.fPt[0].x, i.fPt[0].y);
+ for (int index = 1; index < pts; ++index) {
+ SkDebugf(" wtTs[%d]=%1.9g (%1.9g,%1.9g)", index, i.fT[0][index], i.fPt[index].x,
+ i.fPt[index].y);
}
- SkDebugf(" wnTs[0]=%g (%1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g) (%1.9g,%1.9g)",
- wnTs[0], wn.pts()[0].fX, wn.pts()[0].fY,
- wn.pts()[1].fX, wn.pts()[1].fY, wn.pts()[2].fX, wn.pts()[2].fY,
- wnOutPt.fX, wnOutPt.fY);
- if (pts == 2) {
- SkDebugf(" wnTs[1]=%1.9g", wnTs[1]);
+ SkDebugf(" wnTs[0]=%g (%1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g)",
+ i.fT[1][0], wn.pts()[0].fX, wn.pts()[0].fY,
+ wn.pts()[1].fX, wn.pts()[1].fY, wn.pts()[2].fX, wn.pts()[2].fY);
+ for (int index = 1; index < pts; ++index) {
+ SkDebugf(" wnTs[%d]=%1.9g", index, i.fT[1][index]);
}
SkDebugf("\n");
}
static void debugShowCubicLineIntersection(int pts, const Work& wt,
- const Work& wn, const double wtTs[2], const double wnTs[2]) {
+ const Work& wn, const Intersections& i) {
+ SkASSERT(i.used() == pts);
if (!pts) {
SkDebugf("%s no intersect (%1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g)"
" (%1.9g,%1.9g %1.9g,%1.9g)\n",
@@ -5135,31 +5175,27 @@
wn.pts()[0].fX, wn.pts()[0].fY, wn.pts()[1].fX, wn.pts()[1].fY);
return;
}
- SkPoint wtOutPt, wnOutPt;
- CubicXYAtT(wt.pts(), wtTs[0], &wtOutPt);
- LineXYAtT(wn.pts(), wnTs[0], &wnOutPt);
SkDebugf("%s wtTs[0]=%1.9g (%1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g) (%1.9g,%1.9g)",
__FUNCTION__,
- wtTs[0], wt.pts()[0].fX, wt.pts()[0].fY, wt.pts()[1].fX, wt.pts()[1].fY,
+ i.fT[0][0], wt.pts()[0].fX, wt.pts()[0].fY, wt.pts()[1].fX, wt.pts()[1].fY,
wt.pts()[2].fX, wt.pts()[2].fY, wt.pts()[3].fX, wt.pts()[3].fY,
- wtOutPt.fX, wtOutPt.fY);
- if (pts == 2) {
- CubicXYAtT(wt.pts(), wtTs[1], &wtOutPt);
- SkDebugf(" wtTs[1]=%1.9g (%1.9g,%1.9g)", wtTs[1], wtOutPt.fX, wtOutPt.fY);
+ i.fPt[0].x, i.fPt[0].y);
+ for (int index = 1; index < pts; ++index) {
+ SkDebugf(" wtTs[%d]=%1.9g (%1.9g,%1.9g)", index, i.fT[0][index], i.fPt[index].x,
+ i.fPt[index].y);
}
- SkDebugf(" wnTs[0]=%g (%1.9g,%1.9g %1.9g,%1.9g) (%1.9g,%1.9g)",
- wtTs[0], wn.pts()[0].fX, wn.pts()[0].fY, wn.pts()[1].fX, wn.pts()[1].fY,
- wnOutPt.fX, wnOutPt.fY);
- if (pts == 2) {
- LineXYAtT(wn.pts(), wnTs[1], &wnOutPt);
- SkDebugf(" wnTs[1]=%1.9g (%1.9g,%1.9g)", wnTs[1], wnOutPt.fX, wnOutPt.fY);
+ SkDebugf(" wnTs[0]=%g (%1.9g,%1.9g %1.9g,%1.9g)",
+ i.fT[1][0], wn.pts()[0].fX, wn.pts()[0].fY, wn.pts()[1].fX, wn.pts()[1].fY);
+ for (int index = 1; index < pts; ++index) {
+ SkDebugf(" wnTs[%d]=%1.9g", index, i.fT[1][index]);
}
SkDebugf("\n");
}
// FIXME: show more than two intersection points
static void debugShowCubicQuadIntersection(int pts, const Work& wt,
- const Work& wn, const double wtTs[2], const double wnTs[2]) {
+ const Work& wn, const Intersections& i) {
+ SkASSERT(i.used() == pts);
if (!pts) {
SkDebugf("%s no intersect (%1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g)"
" (%1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g)\n",
@@ -5169,30 +5205,28 @@
wn.pts()[2].fX, wn.pts()[2].fY );
return;
}
- SkPoint wtOutPt, wnOutPt;
- CubicXYAtT(wt.pts(), wtTs[0], &wtOutPt);
- QuadXYAtT(wn.pts(), wnTs[0], &wnOutPt);
SkDebugf("%s wtTs[0]=%1.9g (%1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g) (%1.9g,%1.9g)",
__FUNCTION__,
- wtTs[0], wt.pts()[0].fX, wt.pts()[0].fY, wt.pts()[1].fX, wt.pts()[1].fY,
+ i.fT[0][0], wt.pts()[0].fX, wt.pts()[0].fY, wt.pts()[1].fX, wt.pts()[1].fY,
wt.pts()[2].fX, wt.pts()[2].fY, wt.pts()[3].fX, wt.pts()[3].fY,
- wtOutPt.fX, wtOutPt.fY);
- if (pts == 2) {
- SkDebugf(" wtTs[1]=%1.9g", wtTs[1]);
+ i.fPt[0].x, i.fPt[0].y);
+ for (int index = 1; index < pts; ++index) {
+ SkDebugf(" wtTs[%d]=%1.9g (%1.9g,%1.9g)", index, i.fT[0][index], i.fPt[index].x,
+ i.fPt[index].y);
}
- SkDebugf(" wnTs[0]=%g (%1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g) (%1.9g,%1.9g)",
- wnTs[0], wn.pts()[0].fX, wn.pts()[0].fY, wn.pts()[1].fX, wn.pts()[1].fY,
- wn.pts()[2].fX, wn.pts()[2].fY,
- wnOutPt.fX, wnOutPt.fY);
- if (pts == 2) {
- SkDebugf(" wnTs[1]=%1.9g", wnTs[1]);
+ SkDebugf(" wnTs[0]=%g (%1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g)",
+ i.fT[1][0], wn.pts()[0].fX, wn.pts()[0].fY, wn.pts()[1].fX, wn.pts()[1].fY,
+ wn.pts()[2].fX, wn.pts()[2].fY);
+ for (int index = 1; index < pts; ++index) {
+ SkDebugf(" wnTs[%d]=%1.9g", index, i.fT[1][index]);
}
SkDebugf("\n");
}
// FIXME: show more than two intersection points
static void debugShowCubicIntersection(int pts, const Work& wt,
- const Work& wn, const double wtTs[2], const double wnTs[2]) {
+ const Work& wn, const Intersections& i) {
+ SkASSERT(i.used() == pts);
if (!pts) {
SkDebugf("%s no intersect (%1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g)"
" (%1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g)\n",
@@ -5202,50 +5236,43 @@
wn.pts()[2].fX, wn.pts()[2].fY, wn.pts()[3].fX, wn.pts()[3].fY );
return;
}
- SkPoint wtOutPt, wnOutPt;
- CubicXYAtT(wt.pts(), wtTs[0], &wtOutPt);
- CubicXYAtT(wn.pts(), wnTs[0], &wnOutPt);
SkDebugf("%s wtTs[0]=%1.9g (%1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g) (%1.9g,%1.9g)",
__FUNCTION__,
- wtTs[0], wt.pts()[0].fX, wt.pts()[0].fY, wt.pts()[1].fX, wt.pts()[1].fY,
+ i.fT[0][0], wt.pts()[0].fX, wt.pts()[0].fY, wt.pts()[1].fX, wt.pts()[1].fY,
wt.pts()[2].fX, wt.pts()[2].fY, wt.pts()[3].fX, wt.pts()[3].fY,
- wtOutPt.fX, wtOutPt.fY);
- if (pts == 2) {
- SkDebugf(" wtTs[1]=%1.9g", wtTs[1]);
+ i.fPt[0].x, i.fPt[0].y);
+ for (int index = 1; index < pts; ++index) {
+ SkDebugf(" wtTs[%d]=%1.9g (%1.9g,%1.9g)", index, i.fT[0][index], i.fPt[index].x,
+ i.fPt[index].y);
}
- SkDebugf(" wnTs[0]=%g (%1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g) (%1.9g,%1.9g)",
- wnTs[0], wn.pts()[0].fX, wn.pts()[0].fY, wn.pts()[1].fX, wn.pts()[1].fY,
- wn.pts()[2].fX, wn.pts()[2].fY, wn.pts()[3].fX, wn.pts()[3].fY,
- wnOutPt.fX, wnOutPt.fY);
- if (pts == 2) {
- SkDebugf(" wnTs[1]=%1.9g", wnTs[1]);
+ SkDebugf(" wnTs[0]=%g (%1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g)",
+ i.fT[1][0], wn.pts()[0].fX, wn.pts()[0].fY, wn.pts()[1].fX, wn.pts()[1].fY,
+ wn.pts()[2].fX, wn.pts()[2].fY, wn.pts()[3].fX, wn.pts()[3].fY);
+ for (int index = 1; index < pts; ++index) {
+ SkDebugf(" wnTs[%d]=%1.9g", index, i.fT[0][index]);
}
SkDebugf("\n");
}
#else
-static void debugShowLineIntersection(int , const Work& ,
- const Work& , const double [2], const double [2]) {
+static void debugShowLineIntersection(int , const Work& , const Work& , const Intersections& ) {
}
-static void debugShowQuadLineIntersection(int , const Work& ,
- const Work& , const double [2], const double [2]) {
+static void debugShowQuadLineIntersection(int , const Work& , const Work& , const Intersections& ) {
}
-static void debugShowQuadIntersection(int , const Work& ,
- const Work& , const double [2], const double [2]) {
+static void debugShowQuadIntersection(int , const Work& , const Work& , const Intersections& ) {
}
-static void debugShowCubicLineIntersection(int , const Work& ,
- const Work& , const double [2], const double [2]) {
+static void debugShowCubicLineIntersection(int , const Work& , const Work& ,
+ const Intersections& ) {
}
-static void debugShowCubicQuadIntersection(int , const Work& ,
- const Work& , const double [2], const double [2]) {
+static void debugShowCubicQuadIntersection(int , const Work& , const Work& ,
+ const Intersections& ) {
}
-static void debugShowCubicIntersection(int , const Work& ,
- const Work& , const double [2], const double [2]) {
+static void debugShowCubicIntersection(int , const Work& , const Work& , const Intersections& ) {
}
#endif
@@ -5284,8 +5311,7 @@
case Work::kLine_Segment: {
pts = HLineIntersect(wn.pts(), wt.left(),
wt.right(), wt.y(), wt.xFlipped(), ts);
- debugShowLineIntersection(pts, wt, wn,
- ts.fT[1], ts.fT[0]);
+ debugShowLineIntersection(pts, wt, wn, ts);
break;
}
case Work::kQuad_Segment: {
@@ -5296,7 +5322,7 @@
case Work::kCubic_Segment: {
pts = HCubicIntersect(wn.pts(), wt.left(),
wt.right(), wt.y(), wt.xFlipped(), ts);
- debugShowCubicLineIntersection(pts, wn, wt, ts.fT[0], ts.fT[1]);
+ debugShowCubicLineIntersection(pts, wn, wt, ts);
break;
}
default:
@@ -5311,8 +5337,7 @@
case Work::kLine_Segment: {
pts = VLineIntersect(wn.pts(), wt.top(),
wt.bottom(), wt.x(), wt.yFlipped(), ts);
- debugShowLineIntersection(pts, wt, wn,
- ts.fT[1], ts.fT[0]);
+ debugShowLineIntersection(pts, wt, wn, ts);
break;
}
case Work::kQuad_Segment: {
@@ -5323,7 +5348,7 @@
case Work::kCubic_Segment: {
pts = VCubicIntersect(wn.pts(), wt.top(),
wt.bottom(), wt.x(), wt.yFlipped(), ts);
- debugShowCubicLineIntersection(pts, wn, wt, ts.fT[0], ts.fT[1]);
+ debugShowCubicLineIntersection(pts, wn, wt, ts);
break;
}
default:
@@ -5335,32 +5360,28 @@
case Work::kHorizontalLine_Segment:
pts = HLineIntersect(wt.pts(), wn.left(),
wn.right(), wn.y(), wn.xFlipped(), ts);
- debugShowLineIntersection(pts, wt, wn,
- ts.fT[1], ts.fT[0]);
+ debugShowLineIntersection(pts, wt, wn, ts);
break;
case Work::kVerticalLine_Segment:
pts = VLineIntersect(wt.pts(), wn.top(),
wn.bottom(), wn.x(), wn.yFlipped(), ts);
- debugShowLineIntersection(pts, wt, wn,
- ts.fT[1], ts.fT[0]);
+ debugShowLineIntersection(pts, wt, wn, ts);
break;
case Work::kLine_Segment: {
pts = LineIntersect(wt.pts(), wn.pts(), ts);
- debugShowLineIntersection(pts, wt, wn,
- ts.fT[1], ts.fT[0]);
+ debugShowLineIntersection(pts, wt, wn, ts);
break;
}
case Work::kQuad_Segment: {
swap = true;
pts = QuadLineIntersect(wn.pts(), wt.pts(), ts);
- debugShowQuadLineIntersection(pts, wn, wt,
- ts.fT[0], ts.fT[1]);
+ debugShowQuadLineIntersection(pts, wn, wt, ts);
break;
}
case Work::kCubic_Segment: {
swap = true;
pts = CubicLineIntersect(wn.pts(), wt.pts(), ts);
- debugShowCubicLineIntersection(pts, wn, wt, ts.fT[0], ts.fT[1]);
+ debugShowCubicLineIntersection(pts, wn, wt, ts);
break;
}
default:
@@ -5379,25 +5400,23 @@
break;
case Work::kLine_Segment: {
pts = QuadLineIntersect(wt.pts(), wn.pts(), ts);
- debugShowQuadLineIntersection(pts, wt, wn,
- ts.fT[0], ts.fT[1]);
+ debugShowQuadLineIntersection(pts, wt, wn, ts);
break;
}
case Work::kQuad_Segment: {
pts = QuadIntersect(wt.pts(), wn.pts(), ts);
- debugShowQuadIntersection(pts, wt, wn,
- ts.fT[0], ts.fT[1]);
+ debugShowQuadIntersection(pts, wt, wn, ts);
break;
}
case Work::kCubic_Segment: {
#if APPROXIMATE_CUBICS
swap = true;
pts = CubicQuadIntersect(wn.pts(), wt.pts(), ts);
- debugShowCubicQuadIntersection(pts, wn, wt, ts.fT[0], ts.fT[1]);
+ debugShowCubicQuadIntersection(pts, wn, wt, ts);
#else
wt.promoteToCubic();
pts = CubicIntersect(wt.cubic(), wn.pts(), ts);
- debugShowCubicIntersection(pts, wt, wn, ts.fT[0], ts.fT[1]);
+ debugShowCubicIntersection(pts, wt, wn, ts);
#endif
break;
}
@@ -5410,31 +5429,32 @@
case Work::kHorizontalLine_Segment:
pts = HCubicIntersect(wt.pts(), wn.left(),
wn.right(), wn.y(), wn.xFlipped(), ts);
+ debugShowCubicLineIntersection(pts, wt, wn, ts);
break;
case Work::kVerticalLine_Segment:
pts = VCubicIntersect(wt.pts(), wn.top(),
wn.bottom(), wn.x(), wn.yFlipped(), ts);
- debugShowCubicLineIntersection(pts, wt, wn, ts.fT[0], ts.fT[1]);
+ debugShowCubicLineIntersection(pts, wt, wn, ts);
break;
case Work::kLine_Segment: {
pts = CubicLineIntersect(wt.pts(), wn.pts(), ts);
- debugShowCubicLineIntersection(pts, wt, wn, ts.fT[0], ts.fT[1]);
+ debugShowCubicLineIntersection(pts, wt, wn, ts);
break;
}
case Work::kQuad_Segment: {
#if APPROXIMATE_CUBICS
pts = CubicQuadIntersect(wt.pts(), wn.pts(), ts);
- debugShowCubicQuadIntersection(pts, wt, wn, ts.fT[0], ts.fT[1]);
+ debugShowCubicQuadIntersection(pts, wt, wn, ts);
#else
wn.promoteToCubic();
pts = CubicIntersect(wt.pts(), wn.cubic(), ts);
- debugShowCubicIntersection(pts, wt, wn, ts.fT[0], ts.fT[1]);
+ debugShowCubicIntersection(pts, wt, wn, ts);
#endif
break;
}
case Work::kCubic_Segment: {
pts = CubicIntersect(wt.pts(), wn.pts(), ts);
- debugShowCubicIntersection(pts, wt, wn, ts.fT[0], ts.fT[1]);
+ debugShowCubicIntersection(pts, wt, wn, ts);
break;
}
default:
@@ -5455,9 +5475,10 @@
for (int pt = 0; pt < ts.used(); ++pt) {
// FIXME: if unsortable, the other points to the original. This logic is
// untested downstream.
- int testTAt = wt.addUnsortableT(ts.fT[swap][pt], wt, start);
+ SkPoint point = ts.fPt[pt].asSkPoint();
+ int testTAt = wt.addUnsortableT(ts.fT[swap][pt], wt, start, point);
wt.addOtherT(testTAt, ts.fT[swap][pt], testTAt);
- testTAt = wn.addUnsortableT(ts.fT[!swap][pt], wn, start ^ ts.fFlip);
+ testTAt = wn.addUnsortableT(ts.fT[!swap][pt], wn, start ^ ts.fFlip, point);
wn.addOtherT(testTAt, ts.fT[!swap][pt], testTAt);
start ^= true;
}
@@ -5471,7 +5492,8 @@
}
if (wn.segmentType() >= Work::kQuad_Segment
&& wt.segmentType() >= Work::kQuad_Segment
- && ts.coincidentUsed() == 2) {
+ && ts.fIsCoincident[0]) {
+ SkASSERT(ts.coincidentUsed() == 2);
wt.addCoincident(wn, ts, swap);
continue;
}
@@ -5480,8 +5502,9 @@
for (int pt = 0; pt < pts; ++pt) {
SkASSERT(ts.fT[0][pt] >= 0 && ts.fT[0][pt] <= 1);
SkASSERT(ts.fT[1][pt] >= 0 && ts.fT[1][pt] <= 1);
- int testTAt = wt.addT(ts.fT[swap][pt], wn);
- int nextTAt = wn.addT(ts.fT[!swap][pt], wt);
+ SkPoint point = ts.fPt[pt].asSkPoint();
+ int testTAt = wt.addT(ts.fT[swap][pt], wn, point);
+ int nextTAt = wn.addT(ts.fT[!swap][pt], wt, point);
wt.addOtherT(testTAt, ts.fT[!swap][pt ^ ts.fFlip], nextTAt);
wn.addOtherT(nextTAt, ts.fT[swap][pt ^ ts.fFlip], testTAt);
}
diff --git a/experimental/Intersection/SimplifyNew_Test.cpp b/experimental/Intersection/SimplifyNew_Test.cpp
index 567801b..08dda60 100644
--- a/experimental/Intersection/SimplifyNew_Test.cpp
+++ b/experimental/Intersection/SimplifyNew_Test.cpp
@@ -3629,12 +3629,160 @@
testShapeOp(path, pathB, kDifference_Op);
}
+static void cubicOp8d() {
+ SkPath path, pathB;
+ path.setFillType(SkPath::kWinding_FillType);
+ path.moveTo(0,1);
+ path.cubicTo(0,5, 1,0, 4,0);
+ path.close();
+ pathB.setFillType(SkPath::kWinding_FillType);
+ pathB.moveTo(0,1);
+ pathB.cubicTo(0,4, 1,0, 5,0);
+ pathB.close();
+ testShapeOp(path, pathB, kDifference_Op);
+}
+
+static void cubicOp9d() {
+ SkPath path, pathB;
+ path.setFillType(SkPath::kWinding_FillType);
+ path.moveTo(0,1);
+ path.cubicTo(1,6, 1,0, 2,1);
+ path.close();
+ pathB.setFillType(SkPath::kWinding_FillType);
+ pathB.moveTo(0,1);
+ pathB.cubicTo(1,2, 1,0, 6,1);
+ pathB.close();
+ testShapeOp(path, pathB, kDifference_Op);
+}
+
+static void quadOp9d() {
+ SkPath path, pathB;
+ path.setFillType(SkPath::kWinding_FillType);
+ path.moveTo(0,1);
+ path.quadTo(1,6, 1.5f,1);
+ path.quadTo(1.5f,0.5f, 2,1);
+ path.close();
+ pathB.setFillType(SkPath::kWinding_FillType);
+ pathB.moveTo(0,1);
+ pathB.quadTo(1,2, 1.4f,1);
+ pathB.quadTo(3,0.4f, 6,1);
+ pathB.close();
+ testShapeOp(path, pathB, kDifference_Op);
+}
+
+static void lineOp9d() {
+ SkPath path, pathB;
+ path.setFillType(SkPath::kWinding_FillType);
+ path.moveTo(0,1);
+ path.lineTo(1,6);
+ path.lineTo(1.5f,1);
+ path.lineTo(1.8f,0.8f);
+ path.lineTo(2,1);
+ path.close();
+ pathB.setFillType(SkPath::kWinding_FillType);
+ pathB.moveTo(0,1);
+ pathB.lineTo(1,2);
+ pathB.lineTo(1.4f,1);
+ pathB.lineTo(3,0.4f);
+ pathB.lineTo(6,1);
+ pathB.close();
+ testShapeOp(path, pathB, kDifference_Op);
+}
+
+static void cubicOp1i() {
+ SkPath path, pathB;
+ path.setFillType(SkPath::kWinding_FillType);
+ path.moveTo(0,1);
+ path.cubicTo(1,2, 1,0, 2,1);
+ path.close();
+ pathB.setFillType(SkPath::kWinding_FillType);
+ pathB.moveTo(0,1);
+ pathB.cubicTo(1,2, 1,0, 2,1);
+ pathB.close();
+ testShapeOp(path, pathB, kIntersect_Op);
+}
+
+static void cubicOp10d() {
+ SkPath path, pathB;
+ path.setFillType(SkPath::kWinding_FillType);
+ path.moveTo(0,1);
+ path.cubicTo(1,3, 1,0, 4,1);
+ path.close();
+ pathB.setFillType(SkPath::kWinding_FillType);
+ pathB.moveTo(0,1);
+ pathB.cubicTo(1,4, 1,0, 3,1);
+ pathB.close();
+ testShapeOp(path, pathB, kDifference_Op);
+}
+
+static void cubicOp11d() {
+ SkPath path, pathB;
+ path.setFillType(SkPath::kWinding_FillType);
+ path.moveTo(0,1);
+ path.cubicTo(3,4, 1,0, 5,1);
+ path.close();
+ pathB.setFillType(SkPath::kWinding_FillType);
+ pathB.moveTo(0,1);
+ pathB.cubicTo(1,5, 1,0, 4,3);
+ pathB.close();
+ testShapeOp(path, pathB, kDifference_Op);
+}
+
+static void cubicOp12d() {
+ SkPath path, pathB;
+ path.setFillType(SkPath::kWinding_FillType);
+ path.moveTo(0,1);
+ path.cubicTo(1,6, 1,0, 1,0);
+ path.close();
+ pathB.setFillType(SkPath::kWinding_FillType);
+ pathB.moveTo(0,1);
+ pathB.cubicTo(0,1, 1,0, 6,1);
+ pathB.close();
+ testShapeOp(path, pathB, kDifference_Op);
+}
+
+static void cubicOp13d() {
+ SkPath path, pathB;
+ path.setFillType(SkPath::kWinding_FillType);
+ path.moveTo(0,1);
+ path.cubicTo(4,5, 1,0, 5,3);
+ path.close();
+ pathB.setFillType(SkPath::kWinding_FillType);
+ pathB.moveTo(0,1);
+ pathB.cubicTo(3,5, 1,0, 5,4);
+ pathB.close();
+ testShapeOp(path, pathB, kDifference_Op);
+}
+
+static void cubicOp14d() {
+ SkPath path, pathB;
+ path.setFillType(SkPath::kWinding_FillType);
+ path.moveTo(0,1);
+ path.cubicTo(0,2, 2,0, 2,1);
+ path.close();
+ pathB.setFillType(SkPath::kWinding_FillType);
+ pathB.moveTo(0,2);
+ pathB.cubicTo(1,2, 1,0, 2,0);
+ pathB.close();
+ testShapeOp(path, pathB, kDifference_Op);
+}
+
static void (*firstTest)() = 0;
static struct {
void (*fun)();
const char* str;
} tests[] = {
+ TEST(cubicOp14d),
+ TEST(cubicOp13d),
+ TEST(cubicOp12d),
+ TEST(cubicOp11d),
+ TEST(cubicOp10d),
+ TEST(cubicOp1i),
+ TEST(cubicOp9d),
+ TEST(quadOp9d),
+ TEST(lineOp9d),
+ TEST(cubicOp8d),
TEST(cubicOp7d),
TEST(cubicOp6d),
TEST(cubicOp5d),
@@ -4162,11 +4310,11 @@
static const size_t subTestCount = sizeof(subTests) / sizeof(subTests[0]);
-static void (*firstBinaryTest)() = testOp8d;
+static void (*firstBinaryTest)() = 0;
static bool skipAll = false;
static bool runBinaryTestsFirst = false;
-static bool runReverse = false;
+static bool runReverse = true;
static void (*stopTest)() = 0;
void SimplifyNew_Test() {
diff --git a/experimental/Intersection/op.htm b/experimental/Intersection/op.htm
index 5454fdc..c3ae3c5 100644
--- a/experimental/Intersection/op.htm
+++ b/experimental/Intersection/op.htm
@@ -300,6 +300,17 @@
testSimplifyx(path);
</div>
+<div id="testLine5">
+ path.moveTo(3,0);
+ path.lineTo(6,2);
+ path.lineTo(0,2);
+ path.close();
+ path.moveTo(3,0);
+ path.lineTo(6,2);
+ path.lineTo(0,2);
+ path.close();
+</div>
+
<div id="testLine6">
SkPath path, simple;
path.moveTo(0,0);
@@ -3405,11 +3416,139 @@
pathB.close();
</div>
+<div id="cubicOp8d">
+ path.setFillType(SkPath::kWinding_FillType);
+ path.moveTo(0,1);
+ path.cubicTo(0,5, 1,0, 4,0);
+ path.close();
+ pathB.setFillType(SkPath::kWinding_FillType);
+ pathB.moveTo(0,1);
+ pathB.cubicTo(0,4, 1,0, 5,0);
+ pathB.close();
+</div>
+
+<div id="cubicOp9d">
+ path.setFillType(SkPath::kWinding_FillType);
+ path.moveTo(0,1);
+ path.cubicTo(1,6, 1,0, 2,1);
+ path.close();
+ pathB.setFillType(SkPath::kWinding_FillType);
+ pathB.moveTo(0,1);
+ pathB.cubicTo(1,2, 1,0, 6,1);
+ pathB.close();
+</div>
+
+<div id="quadOp9d">
+ path.setFillType(SkPath::kWinding_FillType);
+ path.moveTo(0,1);
+ path.quadTo(1,6, 1.5f,1);
+ path.quadTo(1.5f,0.8f, 2,1);
+ path.close();
+ pathB.setFillType(SkPath::kWinding_FillType);
+ pathB.moveTo(0,1);
+ pathB.quadTo(1,2, 1.4f,1);
+ pathB.quadTo(3,0.4f, 6,1);
+ pathB.close();
+</div>
+
+<div id="lineOp9d">
+ path.setFillType(SkPath::kWinding_FillType);
+ path.moveTo(0,1);
+ path.lineTo(1,6);
+ path.lineTo(1.5f,1);
+ path.lineTo(1.8f,0.8f);
+ path.lineTo(2,1);
+ path.close();
+ pathB.setFillType(SkPath::kWinding_FillType);
+ pathB.moveTo(0,1);
+ pathB.lineTo(1,2);
+ pathB.lineTo(1.4f,1);
+ pathB.lineTo(3,0.4f);
+ pathB.lineTo(6,1);
+ pathB.close();
+</div>
+
+<div id="cubicOp1i">
+ path.setFillType(SkPath::kWinding_FillType);
+ path.moveTo(0,1);
+ path.cubicTo(1,2, 1,0, 2,1);
+ path.close();
+ pathB.setFillType(SkPath::kWinding_FillType);
+ pathB.moveTo(0,1);
+ pathB.cubicTo(1,2, 1,0, 2,1);
+ pathB.close();
+</div>
+
+<div id="cubicOp10d">
+ path.setFillType(SkPath::kWinding_FillType);
+ path.moveTo(0,1);
+ path.cubicTo(1,3, 1,0, 4,1);
+ path.close();
+ pathB.setFillType(SkPath::kWinding_FillType);
+ pathB.moveTo(0,1);
+ pathB.cubicTo(1,4, 1,0, 3,1);
+ pathB.close();
+</div>
+
+<div id="cubicOp11d">
+ path.setFillType(SkPath::kWinding_FillType);
+ path.moveTo(0,1);
+ path.cubicTo(3,4, 1,0, 5,1);
+ path.close();
+ pathB.setFillType(SkPath::kWinding_FillType);
+ pathB.moveTo(0,1);
+ pathB.cubicTo(1,5, 1,0, 4,3);
+ pathB.close();
+</div>
+
+<div id="cubicOp12d">
+ path.setFillType(SkPath::kWinding_FillType);
+ path.moveTo(0,1);
+ path.cubicTo(1,6, 1,0, 1,0);
+ path.close();
+ pathB.setFillType(SkPath::kWinding_FillType);
+ pathB.moveTo(0,1);
+ pathB.cubicTo(0,1, 1,0, 6,1);
+ pathB.close();
+</div>
+
+<div id="cubicOp13d">
+ path.setFillType(SkPath::kWinding_FillType);
+ path.moveTo(0,1);
+ path.cubicTo(4,5, 1,0, 5,3);
+ path.close();
+ pathB.setFillType(SkPath::kWinding_FillType);
+ pathB.moveTo(0,1);
+ pathB.cubicTo(3,5, 1,0, 5,4);
+ pathB.close();
+</div>
+
+<div id="cubicOp14d">
+ path.setFillType(SkPath::kWinding_FillType);
+ path.moveTo(0,1);
+ path.cubicTo(0,2, 2,0, 2,1);
+ path.close();
+ pathB.setFillType(SkPath::kWinding_FillType);
+ pathB.moveTo(0,2);
+ pathB.cubicTo(1,2, 1,0, 2,0);
+ pathB.close();
+</div>
+
</div>
<script type="text/javascript">
var testDivs = [
+ cubicOp14d,
+ cubicOp13d,
+ cubicOp12d,
+ cubicOp11d,
+ cubicOp10d,
+ cubicOp1i,
+ lineOp9d,
+ quadOp9d,
+ cubicOp9d,
+ cubicOp8d,
cubicOp7d,
cubicOp6d,
cubicOp5d,
@@ -3644,6 +3783,8 @@
testLine9,
testLine7b,
testLine7,
+ testLine6,
+ testLine5,
testSimplifyQuadratic21,
testSimplifyQuadratic20,
testSimplifyQuadratic19,
diff --git a/experimental/Intersection/qc.htm b/experimental/Intersection/qc.htm
index 865fc13..861bdc0 100644
--- a/experimental/Intersection/qc.htm
+++ b/experimental/Intersection/qc.htm
@@ -1888,11 +1888,110 @@
{{x = 1.8746447406062119, y = 1.636550924974228}, {x = 2.7045030849246219, y = 1.7649927124767357}, {x = 4, y = 3}}
</div>
+<div id="cubicOp8">
+{{0,1}, {0,5}, {1,0}, {4,0}},
+{{0,1}, {0,4}, {1,0}, {5,0}},
+
+ {{0,1}, {-0.00421781142,2.47981485}, {0.214213168,2.53784857}},
+ {{0.214213168,2.53784857}, {0.432644147,2.59588228}, {0.924337655,1.94072717}},
+ {{0.924337655,1.94072717}, {1.39158994,1.32418496}, {2.14967426,0.687365435}},
+ {{2.14967426,0.687365435}, {2.90775858,0.0505459108}, {4,0}},
+
+ {{0,1}, {-0.00720132722,2.05525633}, {0.206394399,2.10503282}},
+ {{0.206394399,2.10503282}, {0.419990125,2.15480931}, {0.940798831,1.67439357}},
+ {{0.940798831,1.67439357}, {1.48941875,1.16280321}, {2.47884711,0.60465921}},
+ {{2.47884711,0.60465921}, {3.46827548,0.0465152042}, {5,0}},
+</div>
+
+<div id="cubicOp8a">
+{{x = 0.92433765471479945, y = 1.9407271660071879}, {x = 1.2518504275349398, y = 1.5283649441281617}, {x = 1.7179390069715588, y = 1.0614995059145118}}
+{{x = 0.94079883097732186, y = 1.6743935703752681}, {x = 1.2598825072629554, y = 1.3977856697533602}, {x = 1.7179167190286528, y = 1.0665031295527474}}
+</div>
+
+<div id="cubicOp9d">
+{{0,1}, {1,2}, {1,0}, {6,1}},
+{{0,1}, {1,6}, {1,0}, {2,1}},
+</div>
+
+<div id="cubicOp11d">
+ Cubic cubic1 = {{0,1}, {3,4}, {1,0}, {5,1}};
+ Cubic cubic2 = {{0,1}, {1,5}, {1,0}, {4,3}};
+
+ {{0,1}, {1.10659493,2.10239153}, {1.50615334,2.12918252}},
+ {{1.50615334,2.12918252}, {1.90571174,2.15597351}, {2.1530827,1.71245386}},
+ {{2.1530827,1.71245386}, {2.39265628,1.2948736}, {2.98481198,0.986316183}},
+ {{2.98481198,0.986316183}, {3.57696768,0.677758769}, {5,1}},
+
+ {{0,1}, {0.351042317,2.40055211}, {0.610765407,2.56687524}},
+ {{0.610765407,2.56687524}, {0.870488497,2.73319838}, {1.21251591,2.40319262}},
+ {{1.21251591,2.40319262}, {1.57068059,2.04916077}, {2.21702741,1.98363478}},
+ {{2.21702741,1.98363478}, {2.86337424,1.91810879}, {4,3}},
+</div>
+
+<div id="cubicOp12d">
+{{0, 1}, {1, 6}, {1, 0}, {1, 0}},
+{{0, 1}, {0, 1}, {1, 0}, {6, 1}},
+
+ {{0,1}, {0.298,2.466}, {0.488,2.816}},
+ {{0.488,2.816}, {0.678,3.166}, {0.784,2.808}},
+ {{0.784,2.808}, {0.89,2.45}, {0.936,1.792}},
+ {{0.936,1.792}, {0.982,1.134}, {0.992,0.584}},
+ {{0.992,0.584}, {1.002,0.034}, {1,0}},
+
+ {{0,1}, {-0.0277777778,0.972222222}, {0.444444444,0.777777778}},
+ {{0.444444444,0.777777778}, {0.916666667,0.583333333}, {2.22222222,0.555555556}},
+ {{2.22222222,0.555555556}, {3.52777778,0.527777778}, {6,1}},
+</div>
+
+<div id="cubicOp13d">
+{{0,1}, {4,5}, {1,0}, {5,3}},
+{{0,1}, {3,5}, {1,0}, {5,4}},
+
+ {{0,1}, {1.48018645,2.46752265}, {1.93281168,2.58856757}},
+ {{1.93281168,2.58856757}, {2.38543691,2.7096125}, {2.51967352,2.34531784}},
+ {{2.51967352,2.34531784}, {2.65263731,2.00639194}, {3.1212119,1.98608967}},
+ {{3.1212119,1.98608967}, {3.5897865,1.96578739}, {5,3}},
+
+ {{0,1}, {1.05556321,2.39540407}, {1.46049052,2.58073968}},
+ {{1.46049052,2.58073968}, {1.86541784,2.76607529}, {2.09544533,2.51981963}},
+ {{2.09544533,2.51981963}, {2.33331524,2.25252128}, {2.92003302,2.39442311}},
+ {{2.92003302,2.39442311}, {3.5067508,2.53632493}, {5,4}},
+</div>
+
+<div id="cubicTest4">
+{{x = 0, y = 1}, {x = 4, y = 5}, {x = 1, y = 0}, {x = 5, y = 3}}
+{{x = 0, y = 1}, {x = 1, y = 6}, {x = 1, y = 0}, {x = 2, y = 0}}
+</div>
+
+<div id="cubicTest5">
+{{x = 0, y = 1}, {x = 1, y = 6}, {x = 1, y = 0}, {x = 1, y = 0}}
+{{x = 0, y = 1}, {x = 1, y = 6}, {x = 1, y = 0}, {x = 2, y = 1}}
+</div>
+
+<div id="cubicTest6">
+{{x = 0, y = 1}, {x = 4, y = 5}, {x = 1, y = 0}, {x = 5, y = 3}}
+{{x = 4, y = 4}, {x = 3, y = 4}, {x = 1, y = 2}, {x = 0, y = 0}}
+</div>
+
+<div id="cubicTest7">
+{{x = 0, y = 1}, {x = 1.9274705288631189e-19, y = 1.0000000000000002}, {x = 0.0017190297609673323, y = 0.99828097023903239}, {x = 0.0053709083094631276, y = 0.99505672974365911}}
+</div>
+
</div>
<script type="text/javascript">
var testDivs = [
+ cubicTest7,
+ cubicTest6,
+ cubicTest5,
+ cubicTest4,
+ cubicOp13d,
+ cubicOp12d,
+ cubicOp11d,
+ cubicOp9d,
+ cubicOp8a,
+ cubicOp8,
cubicOp7b,
cubicOp7a,
cubicOp7,
diff --git a/gyp/shapeops_edge.gyp b/gyp/shapeops_edge.gyp
index c8fdd61..2cbc813 100644
--- a/gyp/shapeops_edge.gyp
+++ b/gyp/shapeops_edge.gyp
@@ -19,6 +19,7 @@
'../experimental/Intersection/CubicBezierClip.cpp',
'../experimental/Intersection/CubicBezierClip_Test.cpp',
'../experimental/Intersection/CubicBounds.cpp',
+ '../experimental/Intersection/CubicConvexHull.cpp',
'../experimental/Intersection/CubicIntersection.cpp',
'../experimental/Intersection/CubicIntersection_Test.cpp',
'../experimental/Intersection/CubicIntersection_TestData.cpp',