shape ops work in progress
working on quad/quad intersection
git-svn-id: http://skia.googlecode.com/svn/trunk@5326 2bbb7eff-a529-9590-31e7-b0007b416f81
diff --git a/experimental/Intersection/CubicLineSegments.cpp b/experimental/Intersection/CubicLineSegments.cpp
new file mode 100644
index 0000000..b7408a8
--- /dev/null
+++ b/experimental/Intersection/CubicLineSegments.cpp
@@ -0,0 +1,39 @@
+/*
+ * 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 "CubicLineSegments.h"
+#include "QuadraticLineSegments.h"
+#include <algorithm> // used for std::max
+
+// http://cagd.cs.byu.edu/~557/text/cagd.pdf 2.7
+// A hodograph is the first derivative curve
+void hodograph(const Cubic& cubic, Quadratic& hodo) {
+ hodo[0].x = 3 * (cubic[1].x - cubic[0].x);
+ hodo[0].y = 3 * (cubic[1].y - cubic[0].y);
+ hodo[1].x = 3 * (cubic[2].x - cubic[1].x);
+ hodo[1].y = 3 * (cubic[2].y - cubic[1].y);
+ hodo[2].x = 3 * (cubic[3].x - cubic[2].x);
+ hodo[2].y = 3 * (cubic[3].y - cubic[2].y);
+}
+
+// A 2nd hodograph is the second derivative curve
+void secondHodograph(const Cubic& cubic, _Line& hodo2) {
+ Quadratic hodo;
+ hodograph(cubic, hodo);
+ hodograph(hodo, hodo2);
+}
+
+// The number of line segments required to approximate the cubic
+// see http://cagd.cs.byu.edu/~557/text/cagd.pdf 10.6
+double subDivisions(const Cubic& cubic) {
+ _Line hodo2;
+ secondHodograph(cubic, hodo2);
+ double maxX = std::max(hodo2[1].x, hodo2[1].x);
+ double maxY = std::max(hodo2[1].y, hodo2[1].y);
+ double dist = sqrt(maxX * maxX + maxY * maxY);
+ double segments = sqrt(dist / (8 * FLT_EPSILON));
+ return segments;
+}
diff --git a/experimental/Intersection/CubicLineSegments.h b/experimental/Intersection/CubicLineSegments.h
new file mode 100644
index 0000000..0c80a64
--- /dev/null
+++ b/experimental/Intersection/CubicLineSegments.h
@@ -0,0 +1,12 @@
+/*
+ * 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 "DataTypes.h"
+
+void hodograph(const Cubic& , Quadratic& hodo);
+void secondHodograph(const Cubic& , _Line& hodo2);
+double subDivisions(const Cubic& );
diff --git a/experimental/Intersection/Intersection_Tests.cpp b/experimental/Intersection/Intersection_Tests.cpp
index 00931e5..9b63cea 100644
--- a/experimental/Intersection/Intersection_Tests.cpp
+++ b/experimental/Intersection/Intersection_Tests.cpp
@@ -14,7 +14,7 @@
void Intersection_Tests() {
int testsRun = 0;
- // SimplifyAngle_Test();
+// QuadraticBezierClip_Test();
SimplifyNew_Test();
Simplify4x4QuadraticsThreaded_Test(testsRun);
QuadLineIntersectThreaded_Test(testsRun);
@@ -24,10 +24,10 @@
SimplifyDegenerate4x4TrianglesThreaded_Test(testsRun);
Simplify4x4QuadralateralsThreaded_Test(testsRun);
SkDebugf("%s total testsRun=%d\n", __FUNCTION__, testsRun);
+ SimplifyAngle_Test();
SimplifyFindNext_Test();
SimplifyFindTop_Test();
QuadraticReduceOrder_Test();
- QuadraticBezierClip_Test();
QuadraticIntersection_Test();
SimplifyAddIntersectingTs_Test();
diff --git a/experimental/Intersection/Intersections.h b/experimental/Intersection/Intersections.h
index f855c45..c1e1ce9 100644
--- a/experimental/Intersection/Intersections.h
+++ b/experimental/Intersection/Intersections.h
@@ -11,9 +11,12 @@
public:
Intersections()
: fUsed(0)
+ , fCoincidentUsed(0)
, fSwap(0)
{
+ // OPTIMIZE: don't need to be initialized in release
bzero(fT, sizeof(fT));
+ bzero(fCoincidentT, sizeof(fCoincidentT));
}
void add(double one, double two) {
@@ -26,6 +29,19 @@
++fUsed;
}
+ // start if index == 0 : end if index == 1
+ void addCoincident(double one, double two) {
+ if (fCoincidentUsed > 0
+ && approximately_equal(fCoincidentT[fSwap][fCoincidentUsed - 1], one)
+ && approximately_equal(fCoincidentT[fSwap ^ 1][fCoincidentUsed - 1], two)) {
+ --fCoincidentUsed;
+ return;
+ }
+ fCoincidentT[fSwap][fCoincidentUsed] = one;
+ fCoincidentT[fSwap ^ 1][fCoincidentUsed] = two;
+ ++fCoincidentUsed;
+ }
+
void offset(int base, double start, double end) {
for (int index = base; index < fUsed; ++index) {
double val = fT[fSwap][index];
@@ -52,7 +68,9 @@
}
double fT[2][9];
+ double fCoincidentT[2][9];
int fUsed;
+ int fCoincidentUsed;
private:
int fSwap;
};
diff --git a/experimental/Intersection/QuadraticBezierClip.cpp b/experimental/Intersection/QuadraticBezierClip.cpp
index 2fa9ff6..6df2d1b 100644
--- a/experimental/Intersection/QuadraticBezierClip.cpp
+++ b/experimental/Intersection/QuadraticBezierClip.cpp
@@ -22,6 +22,7 @@
endLine.quadEndPoints(q1);
if (!endLine.normalize()) {
printf("line cannot be normalized: need more code here\n");
+ assert(0);
return false;
}
diff --git a/experimental/Intersection/QuadraticBezierClip_Test.cpp b/experimental/Intersection/QuadraticBezierClip_Test.cpp
index a3d14ce..4c6f0d7 100644
--- a/experimental/Intersection/QuadraticBezierClip_Test.cpp
+++ b/experimental/Intersection/QuadraticBezierClip_Test.cpp
@@ -9,14 +9,31 @@
#include "QuadraticIntersection_TestData.h"
static const Quadratic testSet[] = {
+ // data for oneOffTest
{{8.0000000000000071, 8.0000000000000071},
{8.7289570079366854, 8.7289570079366889},
{9.3914917259458743, 9.0593802763083691}},
{{8.0000000000000142, 8.0000000000000142},
{8.1250000000000107, 8.1250000000000071},
- {8.2500000000000071, 8.2187500000000053}}
+ {8.2500000000000071, 8.2187500000000053}},
+ // data for oneAtEndTest
+ {{0.91292418204644155, 0.41931201426549197},
+ {0.70491388044579517, 0.64754305977710236},
+ {0, 1 }},
+ {{0.21875, 0.765625 },
+ {0.125, 0.875 },
+ {0, 1 }}
};
+static void oneAtEndTest() {
+ const Quadratic& quad1 = testSet[2];
+ const Quadratic& quad2 = testSet[3];
+ double minT = 0;
+ double maxT = 1;
+ bezier_clip(quad1, quad2, minT, maxT);
+}
+
+
static void oneOffTest() {
const Quadratic& quad1 = testSet[0];
const Quadratic& quad2 = testSet[1];
@@ -47,6 +64,7 @@
}
void QuadraticBezierClip_Test() {
+ oneAtEndTest();
oneOffTest();
standardTestCases();
}
diff --git a/experimental/Intersection/QuadraticIntersection.cpp b/experimental/Intersection/QuadraticIntersection.cpp
index 4adc681..be3f680 100644
--- a/experimental/Intersection/QuadraticIntersection.cpp
+++ b/experimental/Intersection/QuadraticIntersection.cpp
@@ -8,6 +8,10 @@
#include "Intersections.h"
#include "IntersectionUtilities.h"
#include "LineIntersection.h"
+#include "LineUtilities.h"
+#include "QuadraticLineSegments.h"
+#include "QuadraticUtilities.h"
+#include <algorithm> // for swap
class QuadraticIntersections : public Intersections {
public:
@@ -28,6 +32,8 @@
if (!bezier_clip(quad1, quad2, minT2, maxT2)) {
return false;
}
+ quad1Divisions = 1 / subDivisions(quad1);
+ quad2Divisions = 1 / subDivisions(quad2);
int split;
if (maxT1 - minT1 < maxT2 - minT2) {
intersections.swap();
@@ -45,48 +51,48 @@
protected:
bool intersect(double minT1, double maxT1, double minT2, double maxT2) {
+ bool t1IsLine = maxT1 - minT1 <= quad1Divisions;
+ bool t2IsLine = maxT2 - minT2 <= quad2Divisions;
+ if (t1IsLine | t2IsLine) {
+ return intersectAsLine(minT1, maxT1, minT2, maxT2, t1IsLine, t2IsLine);
+ }
Quadratic smaller, larger;
// FIXME: carry last subdivide and reduceOrder result with quad
sub_divide(quad1, minT1, maxT1, intersections.swapped() ? larger : smaller);
sub_divide(quad2, minT2, maxT2, intersections.swapped() ? smaller : larger);
- Quadratic smallResult;
- if (reduceOrder(smaller, smallResult) <= 2) {
- Quadratic largeResult;
- if (reduceOrder(larger, largeResult) <= 2) {
- double smallT[2], largeT[2];
- const _Line& smallLine = (const _Line&) smallResult;
- const _Line& largeLine = (const _Line&) largeResult;
- // 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 (approximately_equal(minT, maxT)) {
+ double smallT, largeT;
+ _Point q2pt, q1pt;
if (intersections.swapped()) {
- minT1 = (minT1 + maxT1) / 2;
- minT2 = interp(minT2, maxT2, minT);
+ largeT = interp(minT2, maxT2, minT);
+ xy_at_t(quad2, largeT, q2pt.x, q2pt.y);
+ xy_at_t(quad1, minT1, q1pt.x, q1pt.y);
+ if (approximately_equal(q2pt.x, q1pt.x) && approximately_equal(q2pt.y, q1pt.y)) {
+ smallT = minT1;
+ } else {
+ xy_at_t(quad1, maxT1, q1pt.x, q1pt.y); // FIXME: debug code
+ assert(approximately_equal(q2pt.x, q1pt.x) && approximately_equal(q2pt.y, q1pt.y));
+ smallT = maxT1;
+ }
} else {
- minT1 = interp(minT1, maxT1, minT);
- minT2 = (minT2 + maxT2) / 2;
+ smallT = interp(minT1, maxT1, minT);
+ xy_at_t(quad1, smallT, q1pt.x, q1pt.y);
+ xy_at_t(quad2, minT2, q2pt.x, q2pt.y);
+ if (approximately_equal(q2pt.x, q1pt.x) && approximately_equal(q2pt.y, q1pt.y)) {
+ largeT = minT2;
+ } else {
+ xy_at_t(quad2, maxT2, q2pt.x, q2pt.y); // FIXME: debug code
+ assert(approximately_equal(q2pt.x, q1pt.x) && approximately_equal(q2pt.y, q1pt.y));
+ largeT = maxT2;
+ }
}
- intersections.add(minT1, minT2);
+ intersections.add(smallT, largeT);
return true;
}
return false;
}
-
int split;
if (intersections.swapped()) {
double newMinT1 = interp(minT1, maxT1, minT);
@@ -113,6 +119,70 @@
return chop(minT1, maxT1, minT2, maxT2, split);
}
+bool intersectAsLine(double minT1, double maxT1, double minT2, double maxT2,
+ bool treat1AsLine, bool treat2AsLine)
+{
+ _Line line1, line2;
+ if (intersections.swapped()) {
+ std::swap(treat1AsLine, treat2AsLine);
+ std::swap(minT1, minT2);
+ std::swap(maxT1, maxT2);
+ }
+ // do line/quadratic or even line/line intersection instead
+ if (treat1AsLine) {
+ xy_at_t(quad1, minT1, line1[0].x, line1[0].y);
+ xy_at_t(quad1, maxT1, line1[1].x, line1[1].y);
+ }
+ if (treat2AsLine) {
+ xy_at_t(quad2, minT2, line2[0].x, line2[0].y);
+ xy_at_t(quad2, maxT2, line2[1].x, line2[1].y);
+ }
+ int pts;
+ double smallT, largeT;
+ if (treat1AsLine & treat2AsLine) {
+ double t1[2], t2[2];
+ pts = ::intersect(line1, line2, t1, t2);
+ for (int index = 0; index < pts; ++index) {
+ smallT = interp(minT1, maxT1, t1[index]);
+ largeT = interp(minT2, maxT2, t2[index]);
+ if (pts == 2) {
+ intersections.addCoincident(smallT, largeT);
+ } else {
+ intersections.add(smallT, largeT);
+ }
+ }
+ } else {
+ Intersections lq;
+ pts = ::intersect(treat1AsLine ? quad2 : quad1,
+ treat1AsLine ? line1 : line2, lq);
+ bool coincident = false;
+ if (pts == 2) { // if the line and edge are coincident treat differently
+ _Point midQuad, midLine;
+ double midQuadT = (lq.fT[0][0] + lq.fT[0][1]) / 2;
+ xy_at_t(treat1AsLine ? quad2 : quad1, midQuadT, midQuad.x, midQuad.y);
+ double lineT = t_at(treat1AsLine ? line1 : line2, midQuad);
+ xy_at_t(treat1AsLine ? line1 : line2, lineT, midLine.x, midLine.y);
+ coincident = approximately_equal(midQuad.x, midLine.x)
+ && approximately_equal(midQuad.y, midLine.y);
+ }
+ for (int index = 0; index < pts; ++index) {
+ smallT = lq.fT[0][index];
+ largeT = lq.fT[1][index];
+ if (treat1AsLine) {
+ smallT = interp(minT1, maxT1, smallT);
+ } else {
+ largeT = interp(minT2, maxT2, largeT);
+ }
+ if (coincident) {
+ intersections.addCoincident(smallT, largeT);
+ } else {
+ intersections.add(smallT, largeT);
+ }
+ }
+ }
+ return pts > 0;
+}
+
bool chop(double minT1, double maxT1, double minT2, double maxT2, int split) {
++depth;
intersections.swap();
@@ -146,6 +216,8 @@
Intersections& intersections;
int depth;
int splits;
+double quad1Divisions; // line segments to approximate original within error
+double quad2Divisions;
};
bool intersect(const Quadratic& q1, const Quadratic& q2, Intersections& i) {
diff --git a/experimental/Intersection/QuadraticLineSegments.cpp b/experimental/Intersection/QuadraticLineSegments.cpp
index ee6ffee..5e26d35 100644
--- a/experimental/Intersection/QuadraticLineSegments.cpp
+++ b/experimental/Intersection/QuadraticLineSegments.cpp
@@ -6,3 +6,29 @@
*/
#include "QuadraticLineSegments.h"
+// http://cagd.cs.byu.edu/~557/text/cagd.pdf 2.7
+// A hodograph is the first derivative curve
+void hodograph(const Quadratic& quad, _Line& hodo) {
+ hodo[0].x = 2 * (quad[1].x - quad[0].x);
+ hodo[0].y = 2 * (quad[1].y - quad[0].y);
+ hodo[1].x = 2 * (quad[2].x - quad[1].x);
+ hodo[1].y = 2 * (quad[2].y - quad[1].y);
+}
+
+// A 2nd hodograph is the second derivative curve
+void secondHodograph(const Quadratic& quad, _Point& hodo2) {
+ _Line hodo;
+ hodograph(quad, hodo);
+ hodo2.x = hodo[1].x - hodo[0].x;
+ hodo2.y = hodo[1].y - hodo[0].y;
+}
+
+// The number of line segments required to approximate the quad
+// see http://cagd.cs.byu.edu/~557/text/cagd.pdf 10.6
+double subDivisions(const Quadratic& quad) {
+ _Point hodo2;
+ secondHodograph(quad, hodo2);
+ double dist = sqrt(hodo2.x * hodo2.x + hodo2.y * hodo2.y);
+ double segments = sqrt(dist / (8 * FLT_EPSILON));
+ return segments;
+}
diff --git a/experimental/Intersection/QuadraticLineSegments.h b/experimental/Intersection/QuadraticLineSegments.h
index 755afcb..640a69b 100644
--- a/experimental/Intersection/QuadraticLineSegments.h
+++ b/experimental/Intersection/QuadraticLineSegments.h
@@ -5,3 +5,8 @@
* found in the LICENSE file.
*/
+#include "DataTypes.h"
+
+void hodograph(const Quadratic& , _Line& hodo);
+void secondHodograph(const Quadratic& , _Point& hodo2);
+double subDivisions(const Quadratic& );
diff --git a/experimental/Intersection/QuadraticUtilities.cpp b/experimental/Intersection/QuadraticUtilities.cpp
index 43bd013..8971fca 100644
--- a/experimental/Intersection/QuadraticUtilities.cpp
+++ b/experimental/Intersection/QuadraticUtilities.cpp
@@ -20,6 +20,11 @@
*/
+// note: caller expects multiple results to be sorted smaller first
+// note: http://en.wikipedia.org/wiki/Loss_of_significance has an interesting
+// analysis of the quadratic equation, suggesting why the following looks at
+// the sign of B -- and further suggesting that the greatest loss of precision
+// is in b squared less two a c
int quadraticRoots(double A, double B, double C, double t[2]) {
B *= 2;
double square = B * B - 4 * A * C;
@@ -30,23 +35,27 @@
double Q = (B + (B < 0 ? -squareRt : squareRt)) / -2;
int foundRoots = 0;
double ratio = Q / A;
- if (ratio > -FLT_EPSILON && ratio < 1 + FLT_EPSILON) {
- if (ratio < FLT_EPSILON) {
+ if (approximately_zero_or_more(ratio) && approximately_one_or_less(ratio)) {
+ if (approximately_less_than_zero(ratio)) {
ratio = 0;
- } else if (ratio > 1 - FLT_EPSILON) {
+ } else if (approximately_greater_than_one(ratio)) {
ratio = 1;
}
- t[foundRoots++] = ratio;
+ t[0] = ratio;
+ ++foundRoots;
}
ratio = C / Q;
- if (ratio > -FLT_EPSILON && ratio < 1 + FLT_EPSILON) {
- if (ratio < FLT_EPSILON) {
+ if (approximately_zero_or_more(ratio) && approximately_one_or_less(ratio)) {
+ if (approximately_less_than_zero(ratio)) {
ratio = 0;
- } else if (ratio > 1 - FLT_EPSILON) {
+ } else if (approximately_greater_than_one(ratio)) {
ratio = 1;
}
- if (foundRoots == 0 || fabs(t[0] - ratio) >= FLT_EPSILON) {
+ if (foundRoots == 0 || !approximately_negative(ratio - t[0])) {
t[foundRoots++] = ratio;
+ } else if (!approximately_negative(t[0] - ratio)) {
+ t[foundRoots++] = t[0];
+ t[0] = ratio;
}
}
return foundRoots;
diff --git a/experimental/Intersection/Simplify.cpp b/experimental/Intersection/Simplify.cpp
index 103c534..cea2f69 100644
--- a/experimental/Intersection/Simplify.cpp
+++ b/experimental/Intersection/Simplify.cpp
@@ -35,7 +35,7 @@
#define DEBUG_UNUSED 0 // set to expose unused functions
-#if 1 // set to 1 for multiple thread -- no debugging
+#if 0 // set to 1 for multiple thread -- no debugging
const bool gRunTestsInOneThread = false;
diff --git a/experimental/Intersection/SimplifyNew_Test.cpp b/experimental/Intersection/SimplifyNew_Test.cpp
index 799e78b..53839ae 100644
--- a/experimental/Intersection/SimplifyNew_Test.cpp
+++ b/experimental/Intersection/SimplifyNew_Test.cpp
@@ -2512,12 +2512,26 @@
testSimplifyx(path);
}
-static void (*firstTest)() = testQuadratic18;
+static void testQuadratic19() {
+ SkPath path;
+ path.moveTo(0, 0);
+ path.quadTo(1, 0, 0, 1);
+ path.lineTo(0, 1);
+ path.close();
+ path.moveTo(0, 0);
+ path.lineTo(0, 0);
+ path.quadTo(2, 0, 0, 1);
+ path.close();
+ testSimplifyx(path);
+}
+
+static void (*firstTest)() = testQuadratic19;
static struct {
void (*fun)();
const char* str;
} tests[] = {
+ TEST(testQuadratic19),
TEST(testQuadratic18),
TEST(testQuadratic17x),
TEST(testQuadratic15),
diff --git a/experimental/Intersection/bc.htm b/experimental/Intersection/bc.htm
new file mode 100644
index 0000000..684f1c0
--- /dev/null
+++ b/experimental/Intersection/bc.htm
@@ -0,0 +1,301 @@
+<!-- bezier clip visualizer -->
+<html>
+<head>
+<div style="height:0">
+
+<div id="clip1">
+(gdb) p smaller
+$2 = {{
+ x = 0.91292418204644155,
+ y = 0.41931201426549197
+ }, {
+ x = 0.70491388044579517,
+ y = 0.64754305977710236
+ }, {
+ x = 0,
+ y = 1
+ }}
+(gdb) p larger
+$3 = {{
+ x = 0.21875,
+ y = 0.765625
+ }, {
+ x = 0.125,
+ y = 0.875
+ }, {
+ x = 0,
+ y = 1
+ }}
+(gdb) p distance2y
+$1 = {{
+ x = 0,
+ y = 0.080355482722450078
+ }, {
+ x = 0.5,
+ y = 0.038383741101172597
+ }, {
+ x = 1,
+ y = 0
+ }}
+</div>
+
+</div>
+
+<script type="text/javascript">
+
+var testDivs = [
+ clip1,
+];
+
+var scale, columns, rows, xStart, yStart;
+
+var ticks = 0.1;
+var at_x = 13 + 0.5;
+var at_y = 13 + 0.5;
+var decimal_places = 0; // make this 3 to show more precision
+
+var tests = [];
+var testTitles = [];
+var testIndex = 0;
+var ctx;
+var fat1 = true;
+var fat2 = false;
+
+function parse(test, title) {
+ var curveStrs = test.split("{{");
+ var pattern = /\$?-?\d+\.*\d*/g;
+ var curves = [];
+ for (var c in curveStrs) {
+ var curveStr = curveStrs[c];
+ var points = curveStr.match(pattern);
+ var pts = [];
+ for (var wd in points) {
+ var num = parseFloat(points[wd]);
+ if (isNaN(num)) continue;
+ pts.push(num);
+ }
+ if (pts.length > 0)
+ curves.push(pts);
+ }
+ if (curves.length == 2) {
+ tests.push(curves);
+ testTitles.push(title);
+ }
+}
+
+function init(test) {
+ var canvas = document.getElementById('canvas');
+ if (!canvas.getContext) return;
+ canvas.width = window.innerWidth - at_x;
+ canvas.height = window.innerHeight - at_y;
+ ctx = canvas.getContext('2d');
+ var xmin = Infinity;
+ var xmax = -Infinity;
+ var ymin = Infinity;
+ var ymax = -Infinity;
+ for (var curves in test) {
+ var curve = test[curves];
+ var last = curve.length;
+ for (var idx = 0; idx < last; idx += 2) {
+ xmin = Math.min(xmin, curve[idx]);
+ xmax = Math.max(xmax, curve[idx]);
+ ymin = Math.min(ymin, curve[idx + 1]);
+ ymax = Math.max(ymax, curve[idx + 1]);
+ }
+ }
+ var subscale = 1;
+ while ((xmax - xmin) * subscale < 0.1 && (ymax - ymin) * subscale < 0.1) {
+ subscale *= 10;
+ }
+ columns = Math.ceil(xmax) - Math.floor(xmin) + 1;
+ rows = Math.ceil(ymax) - Math.floor(ymin) + 1;
+ xStart = Math.floor(xmin);
+ yStart = Math.floor(ymin);
+ var hscale = ctx.canvas.width / columns / ticks;
+ var vscale = ctx.canvas.height / rows / ticks;
+ scale = Math.floor(Math.min(hscale, vscale)) * subscale;
+}
+
+function drawPoint(px, py, xoffset, yoffset, unit) {
+ var label = px.toFixed(decimal_places) + ", " + py.toFixed(decimal_places);
+ var _px = px * unit + xoffset;
+ var _py = py * unit + yoffset;
+ ctx.beginPath();
+ ctx.arc(_px, _py, 3, 0, Math.PI*2, true);
+ ctx.closePath();
+ ctx.fill();
+ ctx.fillText(label, _px + 5, _py);
+}
+
+function draw(test, title, _at_x, _at_y, scale) {
+ ctx.fillStyle = "rgba(0,0,0, 0.1)";
+ ctx.font = "normal 50px Arial";
+ ctx.fillText(title, 50, 50);
+ ctx.font = "normal 10px Arial";
+
+ var unit = scale * ticks;
+ ctx.lineWidth = 1;
+ var i;
+ for (i = 0; i <= rows * ticks; ++i) {
+ ctx.strokeStyle = (i % ticks) != 0 ? "rgb(160,160,160)" : "black";
+ ctx.beginPath();
+ ctx.moveTo(_at_x + 0, _at_y + i * scale);
+ ctx.lineTo(_at_x + unit * columns, _at_y + i * scale);
+ ctx.stroke();
+ }
+ for (i = 0; i <= columns * ticks; ++i) {
+ ctx.strokeStyle = (i % ticks) != 0 ? "rgb(160,160,160)" : "black";
+ ctx.beginPath();
+ ctx.moveTo(_at_x + i * scale, _at_y + 0);
+ ctx.lineTo(_at_x + i * scale, _at_y + unit * rows);
+ ctx.stroke();
+ }
+
+ var xoffset = xStart * -unit + _at_x;
+ var yoffset = yStart * -unit + _at_y;
+
+ ctx.fillStyle = "rgb(40,80,60)"
+ for (i = 0; i <= columns; i += (1 / ticks))
+ {
+ num = (xoffset - _at_x) / -unit + i;
+ ctx.fillText(num.toFixed(0), i * unit + _at_y - 5, 10);
+ }
+ for (i = 0; i <= rows; i += (1 / ticks))
+ {
+ num = (yoffset - _at_x) / -unit + i;
+ ctx.fillText(num.toFixed(0), 0, i * unit + _at_y + 0);
+ }
+
+ // draw curve 1 and 2
+ var curves, pts;
+ for (curves in test) {
+ var curve = test[curves];
+ ctx.beginPath();
+ ctx.moveTo(xoffset + curve[0] * unit, yoffset + curve[1] * unit);
+ switch (curve.length) {
+ case 6:
+ ctx.quadraticCurveTo(
+ xoffset + curve[2] * unit, yoffset + curve[3] * unit,
+ xoffset + curve[4] * unit, yoffset + curve[5] * unit);
+ break;
+ case 8:
+ ctx.bezierCurveTo(
+ xoffset + curve[2] * unit, yoffset + curve[3] * unit,
+ xoffset + curve[4] * unit, yoffset + curve[5] * unit,
+ xoffset + curve[6] * unit, yoffset + curve[7] * unit);
+ break;
+ }
+ if (curves == 2) ctx.strokeStyle = curves ? "red" : "blue";
+ ctx.stroke();
+ ctx.strokeStyle = "rgba(0,0,0, 0.3)";
+ ctx.beginPath();
+ ctx.moveTo(xoffset + curve[0] * unit, yoffset + curve[1] * unit);
+ ctx.lineTo(xoffset + curve[2] * unit, yoffset + curve[3] * unit);
+ ctx.lineTo(xoffset + curve[4] * unit, yoffset + curve[5] * unit);
+ if (curve.length == 8)
+ ctx.lineTo(xoffset + curve[6] * unit, yoffset + curve[7] * unit);
+ ctx.stroke();
+ }
+ // optionally draw fat lines for cruve
+ if (fat1)
+ drawFat(test[0], xoffset, yoffset, unit);
+ if (fat2)
+ drawFat(test[1], xoffset, yoffset, unit);
+}
+
+function drawFat(curve, xoffset, yoffset, unit) {
+ var last = curve.length - 2;
+ ctx.strokeStyle = "rgba(0,0,0, 0.5)";
+ ctx.beginPath();
+ ctx.moveTo(xoffset + curve[0] * unit, yoffset + curve[1] * unit);
+ ctx.lineTo(xoffset + curve[last] * unit, yoffset + curve[last + 1] * unit);
+ ctx.stroke();
+ // draw line parallel to end points through control points
+ var dx = curve[last] - curve[0];
+ var dy = curve[last + 1] - curve[1];
+ drawParallelLine(curve[2], curve[3], dx, dy, xoffset, yoffset, unit);
+ if (curve.length == 8)
+ drawParallelLine(curve[4], curve[5], dx, dy, xoffset, yoffset, unit);
+}
+
+function drawParallelLine(x, y, dx, dy, xoffset, yoffset, unit) {
+ var x1 = x - dx;
+ var y1 = y - dy;
+ var x2 = x + dx;
+ var y2 = y + dy;
+ ctx.beginPath();
+ ctx.moveTo(xoffset + x1 * unit, yoffset + y1 * unit);
+ ctx.lineTo(xoffset + x2 * unit, yoffset + y2 * unit);
+ ctx.stroke();
+}
+
+function drawTop() {
+ init(tests[testIndex]);
+ redraw();
+}
+
+function redraw() {
+ ctx.beginPath();
+ ctx.rect(0, 0, ctx.canvas.width, ctx.canvas.height);
+ ctx.fillStyle="white";
+ ctx.fill();
+ draw(tests[testIndex], testTitles[testIndex], at_x, at_y, scale);
+}
+
+function doKeyPress(evt) {
+ var char = String.fromCharCode(evt.charCode);
+ switch (char) {
+ case 'f':
+ fat2 ^= true;
+ if (fat2 == false)
+ fat1 ^= true;
+ drawTop();
+ break;
+ case 'N':
+ testIndex += 9;
+ case 'n':
+ if (++testIndex >= tests.length)
+ testIndex = 0;
+ mouseX = Infinity;
+ drawTop();
+ break;
+ case 'P':
+ testIndex -= 9;
+ case 'p':
+ if (--testIndex < 0)
+ testIndex = tests.length - 1;
+ mouseX = Infinity;
+ drawTop();
+ break;
+ }
+}
+
+function handleMouseClick() {
+}
+
+function handleMouseOver() {
+}
+
+function start() {
+ for (i = 0; i < testDivs.length; ++i) {
+ var title = testDivs[i].id.toString();
+ var str = testDivs[i].firstChild.data;
+ parse(str, title);
+ }
+ drawTop();
+ window.addEventListener('keypress', doKeyPress, true);
+ window.onresize = function() {
+ drawTop();
+ }
+}
+
+</script>
+</head>
+
+<body onLoad="start();">
+<canvas id="canvas" width="750" height="500"
+ onmousemove="handleMouseOver()"
+ onclick="handleMouseClick()"
+ ></canvas >
+</body>
+</html>
diff --git a/experimental/Intersection/op.htm b/experimental/Intersection/op.htm
index 441bd16..d0c2116 100644
--- a/experimental/Intersection/op.htm
+++ b/experimental/Intersection/op.htm
@@ -1299,11 +1299,23 @@
path.close();
</div>
+<div id="testQuadratic19">
+ path.moveTo(0, 0);
+ path.quadTo(1, 0, 0, 1);
+ path.lineTo(0, 1);
+ path.close();
+ path.moveTo(0, 0);
+ path.lineTo(0, 0);
+ path.quadTo(2, 0, 0, 1);
+ path.close();
+</div>
+
</div>
<script type="text/javascript">
var testDivs = [
+ testQuadratic19,
testQuadratic18,
testQuadratic17x,
testQuadratic16b,