shape ops work in progress
good checkpoint: nearly all tests pass solidly here
git-svn-id: http://skia.googlecode.com/svn/trunk@7420 2bbb7eff-a529-9590-31e7-b0007b416f81
diff --git a/experimental/Intersection/CubicIntersection.cpp b/experimental/Intersection/CubicIntersection.cpp
index 8de6398..9316f34 100644
--- a/experimental/Intersection/CubicIntersection.cpp
+++ b/experimental/Intersection/CubicIntersection.cpp
@@ -206,7 +206,10 @@
delta2 = cubicDelta(dxy2, tangent2, scale2 / precisionUnit);
}
+#if SK_DEBUG
int debugDepth;
+#endif
+
// this flavor approximates the cubics with quads to find the intersecting ts
// OPTIMIZE: if this strategy proves successful, the quad approximations, or the ts used
// to create the approximations, could be stored in the cubic segment
@@ -217,14 +220,14 @@
// t range ala is linear inner. The range can be figured by taking the dx/dy and determining
// the fraction that matches the precision. That fraction is the change in t for the smaller cubic.
static bool intersect2(const Cubic& cubic1, double t1s, double t1e, const Cubic& cubic2,
- double t2s, double t2e, Intersections& i) {
+ double t2s, double t2e, double precisionScale, Intersections& i) {
Cubic c1, c2;
sub_divide(cubic1, t1s, t1e, c1);
sub_divide(cubic2, t2s, t2e, c2);
SkTDArray<double> ts1;
- cubic_to_quadratics(c1, calcPrecision(c1), ts1);
+ cubic_to_quadratics(c1, calcPrecision(c1) * precisionScale, ts1);
SkTDArray<double> ts2;
- cubic_to_quadratics(c2, calcPrecision(c2), ts2);
+ cubic_to_quadratics(c2, calcPrecision(c2) * precisionScale, ts2);
double t1Start = t1s;
int ts1Count = ts1.count();
for (int i1 = 0; i1 <= ts1Count; ++i1) {
@@ -277,14 +280,22 @@
} else {
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;
assert(debugDepth < 10);
+#endif
i.swap();
intersect2(cubic2, SkTMax(to2 - dt2, 0.), SkTMin(to2 + dt2, 1.),
- cubic1, SkTMax(to1 - dt1, 0.), SkTMin(to1 + dt1, 1.), i);
+ cubic1, SkTMax(to1 - dt1, 0.), SkTMin(to1 + dt1, 1.), scale, i);
i.swap();
+#if SK_DEBUG
--debugDepth;
-
+#endif
}
}
t2Start = t2;
@@ -336,9 +347,11 @@
tMin = std::min(tMin, local2.fT[0][index]);
tMax = std::max(tMax, local2.fT[0][index]);
}
+#if SK_DEBUG
debugDepth = 0;
+#endif
return intersect2(cubic1, start ? 0 : 1, start ? 1.0 / precisionUnit : 1 - 1.0 / precisionUnit,
- cubic2, tMin, tMax, i);
+ cubic2, tMin, tMax, 1, i);
}
// FIXME: add intersection of convex null on cubics' ends with the opposite cubic. The hull line
@@ -346,16 +359,20 @@
// 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
debugDepth = 0;
- bool result = intersect2(c1, 0, 1, c2, 0, 1, i);
+#endif
+ bool result = intersect2(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;
}
diff --git a/experimental/Intersection/CubicIntersection_Test.cpp b/experimental/Intersection/CubicIntersection_Test.cpp
index 2e738fc..94d86ea 100644
--- a/experimental/Intersection/CubicIntersection_Test.cpp
+++ b/experimental/Intersection/CubicIntersection_Test.cpp
@@ -98,6 +98,15 @@
}
static const Cubic testSet[] = {
+{{0, 0}, {0, 1}, {1, 1}, {1, 0}},
+{{1, 0}, {0, 0}, {0, 1}, {1, 1}},
+
+{{95.837747722788592, 45.025976907939643}, {16.564570095652982, 0.72959763963222402}, {63.209855865319199, 68.047528419665767}, {57.640240647662544, 59.524565264361243}},
+{{51.593891741518817, 38.53849970667553}, {62.34752929878772, 74.924924725166022}, {74.810149322641152, 34.17966562983564}, {29.368398119401373, 94.66719277886078}},
+
+{{39.765160968417838, 33.060396198677083}, {5.1922921581157908, 66.854301452103215}, {31.619281802149157, 25.269248720849514}, {81.541621071073038, 70.025341524754353}},
+{{46.078911165743556, 48.259962651999651}, {20.24450549867214, 49.403916182650214}, {0.26325131778756683, 24.46489805563581}, {15.915006546264051, 83.515023059917155}},
+
{{65.454505973241524, 93.881892270353575}, {45.867360264932437, 92.723972719499827}, {2.1464054482739447, 74.636369140183717}, {33.774068594804994, 40.770872887582925}},
{{72.963387832494163, 95.659300729473728}, {11.809496633619768, 82.209921247423594}, {13.456139067865974, 57.329313623406605}, {36.060621606214262, 70.867335643091849}},
@@ -295,7 +304,7 @@
void CubicIntersection_RandTest() {
srand(0);
- const int tests = 1000000; // 10000000;
+ const int tests = 10000000;
for (int test = 0; test < tests; ++test) {
Cubic cubic1, cubic2;
for (int i = 0; i < 4; ++i) {
diff --git a/experimental/Intersection/CubicReduceOrder.cpp b/experimental/Intersection/CubicReduceOrder.cpp
index fdc7265..87d9fd8 100644
--- a/experimental/Intersection/CubicReduceOrder.cpp
+++ b/experimental/Intersection/CubicReduceOrder.cpp
@@ -151,14 +151,11 @@
lineParameters.cubicEndPoints(cubic, startIndex, endIndex);
// FIXME: maybe it's possible to avoid this and compare non-normalized
lineParameters.normalize();
- int mask = other_two(startIndex, endIndex);
- int inner1 = startIndex ^ mask;
- int inner2 = endIndex ^ mask;
- double distance = lineParameters.controlPtDistance(cubic, inner1);
+ double distance = lineParameters.controlPtDistance(cubic, 1);
if (!approximately_zero(distance)) {
return false;
}
- distance = lineParameters.controlPtDistance(cubic, inner2);
+ distance = lineParameters.controlPtDistance(cubic, 2);
return approximately_zero(distance);
}
diff --git a/experimental/Intersection/DataTypes.h b/experimental/Intersection/DataTypes.h
index a6516fa..ef9bcef 100644
--- a/experimental/Intersection/DataTypes.h
+++ b/experimental/Intersection/DataTypes.h
@@ -28,6 +28,7 @@
const double FLT_EPSILON_CUBED = FLT_EPSILON * FLT_EPSILON * FLT_EPSILON;
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) {
@@ -56,6 +57,10 @@
return fabs(x) < FLT_EPSILON_SQRT;
}
+inline bool approximately_zero_inverse(double x) {
+ return fabs(x) > FLT_EPSILON_INVERSE;
+}
+
// Use this for comparing Ts in the range of 0 to 1. For general numbers (larger and smaller) use
// AlmostEqualUlps instead.
inline bool approximately_equal(double x, double y) {
@@ -247,11 +252,11 @@
}
bool intersects(_Rect& r) const {
- assert(left < right);
- assert(top < bottom);
- assert(r.left < r.right);
- assert(r.top < r.bottom);
- return r.left < right && left < r.right && r.top < bottom && top < r.bottom;
+ assert(left <= right);
+ assert(top <= bottom);
+ assert(r.left <= r.right);
+ assert(r.top <= r.bottom);
+ return r.left <= right && left <= r.right && r.top <= bottom && top <= r.bottom;
}
void set(const _Point& pt) {
diff --git a/experimental/Intersection/Intersection_Tests.cpp b/experimental/Intersection/Intersection_Tests.cpp
index bf86c07..8b4052f 100644
--- a/experimental/Intersection/Intersection_Tests.cpp
+++ b/experimental/Intersection/Intersection_Tests.cpp
@@ -15,13 +15,13 @@
void Intersection_Tests() {
int testsRun = 0;
- QuadraticIntersection_Test();
+ SimplifyNew_Test();
+ CubicToQuadratics_Test();
CubicIntersection_OneOffTest();
+ QuadraticIntersection_Test();
QuarticRoot_Test();
CubicIntersection_RandTest();
- SimplifyNew_Test();
CubicsToQuadratics_RandTest();
- CubicToQuadratics_Test();
Simplify4x4RectsThreaded_Test(testsRun);
Simplify4x4QuadraticsThreaded_Test(testsRun);
QuadLineIntersectThreaded_Test(testsRun);
diff --git a/experimental/Intersection/QuadraticImplicit.cpp b/experimental/Intersection/QuadraticImplicit.cpp
index 9cd24e9..054be64 100644
--- a/experimental/Intersection/QuadraticImplicit.cpp
+++ b/experimental/Intersection/QuadraticImplicit.cpp
@@ -13,6 +13,10 @@
#include "QuadraticUtilities.h"
#include "TSearch.h"
+#if SK_DEBUG
+#include "LineUtilities.h"
+#endif
+
/* given the implicit form 0 = Ax^2 + Bxy + Cy^2 + Dx + Ey + F
* and given x = at^2 + bt + c (the parameterized form)
* y = dt^2 + et + f
@@ -141,8 +145,11 @@
return (u >= 0) && (v >= 0) && (u + v < 1);
}
+// returns false if there's more than one intercept or the intercept doesn't match the point
+// returns true if the intercept was successfully added or if the
+// original quads need to be subdivided
static bool addIntercept(const Quadratic& q1, const Quadratic& q2, double tMin, double tMax,
- Intersections& i) {
+ Intersections& i, bool* subDivide) {
double tMid = (tMin + tMax) / 2;
_Point mid;
xy_at_t(q2, tMid, mid.x, mid.y);
@@ -156,10 +163,15 @@
line[1].y += dxdy.y;
Intersections rootTs;
int roots = intersect(q1, line, rootTs);
+ if (roots == 0) {
+ if (subDivide) {
+ *subDivide = true;
+ }
+ return true;
+ }
if (roots == 2) {
return false;
}
- SkASSERT(roots == 1);
_Point pt2;
xy_at_t(q1, rootTs.fT[0][0], pt2.x, pt2.y);
if (!pt2.approximatelyEqual(mid)) {
@@ -170,7 +182,7 @@
}
static bool isLinearInner(const Quadratic& q1, double t1s, double t1e, const Quadratic& q2,
- double t2s, double t2e, Intersections& i) {
+ double t2s, double t2e, Intersections& i, bool* subDivide) {
Quadratic hull;
sub_divide(q1, t1s, t1e, hull);
_Line line = {hull[2], hull[0]};
@@ -182,6 +194,12 @@
int roots = intersect(q2, *testLines[index], rootTs);
for (int idx2 = 0; idx2 < roots; ++idx2) {
double t = rootTs.fT[0][idx2];
+#if SK_DEBUG
+ _Point qPt, lPt;
+ xy_at_t(q2, t, qPt.x, qPt.y);
+ xy_at_t(*testLines[index], rootTs.fT[1][idx2], lPt.x, lPt.y);
+ SkASSERT(qPt.approximatelyEqual(lPt));
+#endif
if (approximately_negative(t - t2s) || approximately_positive(t - t2e)) {
continue;
}
@@ -227,25 +245,25 @@
}
if (split == 0) { // there's one point
- if (addIntercept(q1, q2, tMin, tMax, i)) {
+ if (addIntercept(q1, q2, tMin, tMax, i, subDivide)) {
return true;
}
i.swap();
- return isLinearInner(q2, tMin, tMax, q1, t1s, t1e, i);
+ return isLinearInner(q2, tMin, tMax, q1, t1s, t1e, i, subDivide);
}
// At this point, we have two ranges of t values -- treat each separately at the split
bool result;
- if (addIntercept(q1, q2, tMin, tsFound[split - 1], i)) {
+ if (addIntercept(q1, q2, tMin, tsFound[split - 1], i, subDivide)) {
result = true;
} else {
i.swap();
- result = isLinearInner(q2, tMin, tsFound[split - 1], q1, t1s, t1e, i);
+ result = isLinearInner(q2, tMin, tsFound[split - 1], q1, t1s, t1e, i, subDivide);
}
- if (addIntercept(q1, q2, tsFound[split], tMax, i)) {
+ if (addIntercept(q1, q2, tsFound[split], tMax, i, subDivide)) {
result = true;
} else {
i.swap();
- result |= isLinearInner(q2, tsFound[split], tMax, q1, t1s, t1e, i);
+ result |= isLinearInner(q2, tsFound[split], tMax, q1, t1s, t1e, i, subDivide);
}
return result;
}
@@ -266,11 +284,11 @@
if (!approximately_zero_sqrt(measure)) {
return false;
}
- return isLinearInner(q1, 0, 1, q2, 0, 1, i);
+ return isLinearInner(q1, 0, 1, q2, 0, 1, i, NULL);
}
// FIXME: if flat measure is sufficiently large, then probably the quartic solution failed
-static bool relaxedIsLinear(const Quadratic& q1, const Quadratic& q2, Intersections& i) {
+static void relaxedIsLinear(const Quadratic& q1, const Quadratic& q2, Intersections& i) {
double m1 = flatMeasure(q1);
double m2 = flatMeasure(q2);
#if SK_DEBUG
@@ -280,12 +298,25 @@
}
#endif
i.reset();
- if (m1 < m2) {
- isLinearInner(q1, 0, 1, q2, 0, 1, i);
- return false;
- } else {
- isLinearInner(q2, 0, 1, q1, 0, 1, i);
- return true;
+ const Quadratic& rounder = m2 < m1 ? q1 : q2;
+ const Quadratic& flatter = m2 < m1 ? q2 : q1;
+ bool subDivide = false;
+ isLinearInner(flatter, 0, 1, rounder, 0, 1, i, &subDivide);
+ if (subDivide) {
+ QuadraticPair pair;
+ chop_at(flatter, pair, 0.5);
+ 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]);
+ }
+ 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]);
+ }
+ }
+ if (m2 < m1) {
+ i.swapPts();
}
}
@@ -428,9 +459,7 @@
}
}
if (i.fUsed && i.fUsed2 && !foundSomething) {
- if (relaxedIsLinear(q1, q2, i)) {
- i.swapPts();
- }
+ relaxedIsLinear(q1, q2, i);
return i.intersected();
}
double roots1Copy[4], roots2Copy[4];
diff --git a/experimental/Intersection/QuadraticUtilities.cpp b/experimental/Intersection/QuadraticUtilities.cpp
index c1fab05..d8755a3 100644
--- a/experimental/Intersection/QuadraticUtilities.cpp
+++ b/experimental/Intersection/QuadraticUtilities.cpp
@@ -97,7 +97,9 @@
// unlike quadratic roots, this does not discard real roots <= 0 or >= 1
int quadraticRootsReal(const double A, const double B, const double C, double s[2]) {
- if (approximately_zero(A)) {
+ const double p = B / (2 * A);
+ const double q = C / A;
+ if (approximately_zero(A) && (approximately_zero_inverse(p) || approximately_zero_inverse(q))) {
if (approximately_zero(B)) {
s[0] = 0;
return C == 0;
@@ -106,8 +108,6 @@
return 1;
}
/* normal form: x^2 + px + q = 0 */
- const double p = B / (2 * A);
- const double q = C / A;
const double p2 = p * p;
#if 0
double D = AlmostEqualUlps(p2, q) ? 0 : p2 - q;
diff --git a/experimental/Intersection/Simplify.cpp b/experimental/Intersection/Simplify.cpp
index 618dc30..1094496 100644
--- a/experimental/Intersection/Simplify.cpp
+++ b/experimental/Intersection/Simplify.cpp
@@ -1017,12 +1017,14 @@
void cubicTo(const SkPoint& pt1, const SkPoint& pt2, const SkPoint& pt3) {
lineTo();
moveTo();
+ fDefer[1] = pt3;
+ nudge();
+ fDefer[0] = fDefer[1];
#if DEBUG_PATH_CONSTRUCTION
SkDebugf("path.cubicTo(%1.9g,%1.9g, %1.9g,%1.9g, %1.9g,%1.9g);\n",
- pt1.fX, pt1.fY, pt2.fX, pt2.fY, pt3.fX, pt3.fY);
+ pt1.fX, pt1.fY, pt2.fX, pt2.fY, fDefer[1].fX, fDefer[1].fY);
#endif
- fPathPtr->cubicTo(pt1.fX, pt1.fY, pt2.fX, pt2.fY, pt3.fX, pt3.fY);
- fDefer[0] = fDefer[1] = pt3;
+ fPathPtr->cubicTo(pt1.fX, pt1.fY, pt2.fX, pt2.fY, fDefer[1].fX, fDefer[1].fY);
fEmpty = false;
}
@@ -1070,6 +1072,7 @@
return;
}
moveTo();
+ nudge();
fEmpty = false;
#if DEBUG_PATH_CONSTRUCTION
SkDebugf("path.lineTo(%1.9g,%1.9g);\n", fDefer[1].fX, fDefer[1].fY);
@@ -1081,16 +1084,26 @@
const SkPath* nativePath() const {
return fPathPtr;
}
+
+ void nudge() {
+ if (fEmpty || !AlmostEqualUlps(fDefer[1].fX, fFirstPt.fX)
+ || !AlmostEqualUlps(fDefer[1].fY, fFirstPt.fY)) {
+ return;
+ }
+ fDefer[1] = fFirstPt;
+ }
void quadTo(const SkPoint& pt1, const SkPoint& pt2) {
lineTo();
moveTo();
+ fDefer[1] = pt2;
+ nudge();
+ fDefer[0] = fDefer[1];
#if DEBUG_PATH_CONSTRUCTION
SkDebugf("path.quadTo(%1.9g,%1.9g, %1.9g,%1.9g);\n",
- pt1.fX, pt1.fY, pt2.fX, pt2.fY);
+ pt1.fX, pt1.fY, fDefer[1].fX, fDefer[1].fY);
#endif
- fPathPtr->quadTo(pt1.fX, pt1.fY, pt2.fX, pt2.fY);
- fDefer[0] = fDefer[1] = pt2;
+ fPathPtr->quadTo(pt1.fX, pt1.fY, fDefer[1].fX, fDefer[1].fY);
fEmpty = false;
}
@@ -5097,7 +5110,6 @@
SkDebugf("\n");
}
-#if APPROXIMATE_CUBICS
// 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]) {
@@ -5112,7 +5124,7 @@
}
SkPoint wtOutPt, wnOutPt;
CubicXYAtT(wt.pts(), wtTs[0], &wtOutPt);
- CubicXYAtT(wn.pts(), wnTs[0], &wnOutPt);
+ 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,
@@ -5163,7 +5175,7 @@
}
SkDebugf("\n");
}
-#endif
+
#else
static void debugShowLineIntersection(int , const Work& ,
const Work& , const double [2], const double [2]) {
@@ -5181,7 +5193,6 @@
const Work& , const double [2], const double [2]) {
}
-#if APPROXIMATE_CUBICS
static void debugShowCubicQuadIntersection(int , const Work& ,
const Work& , const double [2], const double [2]) {
}
@@ -5190,7 +5201,6 @@
const Work& , const double [2], const double [2]) {
}
#endif
-#endif
static bool addIntersectTs(Contour* test, Contour* next) {
@@ -5340,6 +5350,7 @@
#else
wt.promoteToCubic();
pts = CubicIntersect(wt.cubic(), wn.pts(), ts);
+ debugShowCubicIntersection(pts, wt, wn, ts.fT[0], ts.fT[1]);
#endif
break;
}
@@ -5370,16 +5381,13 @@
#else
wn.promoteToCubic();
pts = CubicIntersect(wt.pts(), wn.cubic(), ts);
+ debugShowCubicIntersection(pts, wt, wn, ts.fT[0], ts.fT[1]);
#endif
break;
}
case Work::kCubic_Segment: {
- #if APPROXIMATE_CUBICS
pts = CubicIntersect(wt.pts(), wn.pts(), ts);
debugShowCubicIntersection(pts, wt, wn, ts.fT[0], ts.fT[1]);
- #else
- pts = CubicIntersect(wt.pts(), wn.pts(), ts);
- #endif
break;
}
default:
diff --git a/experimental/Intersection/SimplifyNew_Test.cpp b/experimental/Intersection/SimplifyNew_Test.cpp
index 823693c..4cad7e1 100644
--- a/experimental/Intersection/SimplifyNew_Test.cpp
+++ b/experimental/Intersection/SimplifyNew_Test.cpp
@@ -3536,12 +3536,26 @@
testSimplifyx(path);
}
+static void testQuadratic93() {
+ SkPath path;
+ path.moveTo(3, 0);
+ path.quadTo(0, 1, 3, 2);
+ path.lineTo(0, 3);
+ path.close();
+ path.moveTo(1, 0);
+ path.lineTo(2, 0);
+ path.quadTo(1, 1, 2, 2);
+ path.close();
+ testSimplifyx(path);
+}
+
static void (*firstTest)() = 0;
static struct {
void (*fun)();
const char* str;
} tests[] = {
+ TEST(testQuadratic93),
TEST(testCubic1),
TEST(testQuadralateral1),
TEST(testLine85),
@@ -3870,6 +3884,8 @@
TEST(testLine1),
};
+static const size_t testCount = sizeof(tests) / sizeof(tests[0]);
+
static void testIntersect1() {
SkPath one, two;
one.addRect(0, 0, 6, 6, SkPath::kCW_Direction);
@@ -4034,8 +4050,6 @@
testShapeOp(path, pathB, kDifference_Op);
}
-static const size_t testCount = sizeof(tests) / sizeof(tests[0]);
-
static struct {
void (*fun)();
const char* str;
@@ -4065,7 +4079,7 @@
static void (*firstBinaryTest)() = testOp8d;
static bool skipAll = false;
-static bool runBinaryTestsFirst = true;
+static bool runBinaryTestsFirst = false;
static bool runReverse = false;
static void (*stopTest)() = 0;
diff --git a/experimental/Intersection/op.htm b/experimental/Intersection/op.htm
index 8c8a991..e2db44b 100644
--- a/experimental/Intersection/op.htm
+++ b/experimental/Intersection/op.htm
@@ -3317,11 +3317,23 @@
path.close();
</div>
+<div id="testQuadratic93">
+ path.moveTo(3, 0);
+ path.quadTo(0, 1, 3, 2);
+ path.lineTo(0, 3);
+ path.close();
+ path.moveTo(1, 0);
+ path.lineTo(2, 0);
+ path.quadTo(1, 1, 2, 2);
+ path.close();
+</div>
+
</div>
<script type="text/javascript">
var testDivs = [
+ testQuadratic93,
testCubic1,
testQuadralateral1,
testLine85,
diff --git a/experimental/Intersection/qc.htm b/experimental/Intersection/qc.htm
index 2cf3592..9b1cbbe 100644
--- a/experimental/Intersection/qc.htm
+++ b/experimental/Intersection/qc.htm
@@ -1639,11 +1639,82 @@
{{72.9633878,95.6593007}, {42.7738746,88.4730382}, {31.1932785,80.2458029}},
</div>
+<div id="cubic25">
+{{x = 39.765160968417838, y = 33.060396198677083}, {x = 5.1922921581157908, y = 66.854301452103215}, {x = 31.619281802149157, y = 25.269248720849514}, {x = 81.541621071073038, y = 70.025341524754353}}
+{{x = 46.078911165743556, y = 48.259962651999651}, {x = 20.24450549867214, y = 49.403916182650214}, {x = 0.26325131778756683, y = 24.46489805563581}, {x = 15.915006546264051, y = 83.515023059917155}}
+ {{39.765161,33.0603962}, {30.6426004,41.804305}, {26.9359756,44.8138368}},
+ {{26.9359756,44.8138368}, {21.5667569,48.8605535}, {26.2727712,47.6735862}},
+ {{26.2727712,47.6735862}, {31.3832959,46.2642047}, {45.8264929,49.1528875}},
+ {{45.8264929,49.1528875}, {60.2696898,52.0415702}, {81.5416211,70.0253415}},
+
+ {{46.0789112,48.2599627}, {35.5887068,48.1941457}, {27.2014026,45.6924463}},
+ {{27.2014026,45.6924463}, {19.5490336,43.4817863}, {15.020365,44.2719744}},
+ {{15.020365,44.2719744}, {10.4916964,45.0621625}, {10.3896311,53.6689795}},
+ {{10.3896311,53.6689795}, {10.2875658,62.2757965}, {15.9150065,83.5150231}},
+</div>
+
+<div id="cubic26">
+{{x = 95.837747722788592, y = 45.025976907939643}, {x = 16.564570095652982, y = 0.72959763963222402}, {x = 63.209855865319199, y = 68.047528419665767}, {x = 57.640240647662544, y = 59.524565264361243}}
+{{x = 51.593891741518817, y = 38.53849970667553}, {x = 62.34752929878772, y = 74.924924725166022}, {x = 74.810149322641152, y = 34.17966562983564}, {x = 29.368398119401373, y = 94.66719277886078}}
+ {{95.8377477,45.0259769}, {72.4120612,32.1119735}, {61.9589898,30.3422249}},
+ {{61.9589898,30.3422249}, {51.5059185,28.5724763}, {49.7502617,33.4480576}},
+ {{49.7502617,33.4480576}, {47.9946048,38.3236388}, {50.6611618,45.345625}},
+ {{50.6611618,45.345625}, {53.3277187,52.3676112}, {56.1412886,57.0370775}},
+ {{56.1412886,57.0370775}, {58.9548585,61.7065438}, {57.6402406,59.5245653}},
+
+ {{51.5938917,38.5384997}, {54.39659,47.5609728}, {56.9124968,51.2509862}},
+ {{56.9124968,51.2509862}, {59.4284036,54.9409997}, {60.7901347,55.8937858}},
+ {{60.7901347,55.8937858}, {63.1940269,56.8659601}, {59.551481,59.5998651}},
+ {{59.551481,59.5998651}, {56.8806183,61.8512737}, {49.6576236,69.6523525}},
+ {{49.6576236,69.6523525}, {42.434629,77.4534313}, {29.3683981,94.6671928}},
+</div>
+
+<div id="quad23">
+{{x = 56.14128857485079, y = 57.037077517172825}, {x = 58.954858484191291, y = 61.706543802985237}, {x = 57.640240647662544, y = 59.524565264361243}}
+{{x = 59.551480981235549, y = 59.599865066889976}, {x = 56.880618274428095, y = 61.851273706132794}, {x = 49.657623623535379, y = 69.652352522894546}}
+</div>
+
+<div id="cubic27">
+{{x = 56.14128857485079, y = 57.037077517172825}, {x = 57.779490695232283, y = 59.900114769069532}, {x = 58.754163691193881, y = 61.229157895422141}, {x = 57.640240647662544, y = 59.524565264361243}}
+{{x = 56.14128857485079, y = 57.037077517172825}, {x = 58.954858484191291, y = 61.706543802985237}, {x = 57.640240647662544, y = 59.524565264361243}}
+</div>
+
+<div id="testCubic1">
+{{0, 0}, {0, 1}, {1, 1}, {1, 0}},
+{{1, 0}, {0, 0}, {0, 1}, {1, 1}},
+
+ {{0,0}, {0.0185185185,0.5}, {0.259259259,0.666666667}},
+ {{0.259259259,0.666666667}, {0.5,0.833333333}, {0.740740741,0.666666667}},
+ {{0.740740741,0.666666667}, {0.981481481,0.5}, {1,0}},
+
+ {{1,0}, {0.5,0.0185185185}, {0.333333333,0.259259259}},
+ {{0.333333333,0.259259259}, {0.166666667,0.5}, {0.333333333,0.740740741}},
+ {{0.333333333,0.740740741}, {0.5,0.981481481}, {1,1}},
+</div>
+
+<div id="testCubic1a">
+{{x = 0.30075438676757493, y = 0.69070348972827045}, {x = 0.30339450221247349, y = 0.69543451478800855}, {x = 0.30613761677734441, y = 0.7001387457168422}, {x = 0.30898373046218741, y = 0.70481409186990207}}
+{{x = 0.29518590813009821, y = 0.69101626953781281}, {x = 0.29986125428315819, y = 0.69386238322265548}, {x = 0.30456548521199123, y = 0.69660549778752689}, {x = 0.30929651027172955, y = 0.69924561323242507}}
+</div>
+
+<div id="testCubic1b">
+{{x = 0.3039751936710845, y = 0.69622610811401087}, {x = 0.3037698832307662, y = 0.69610758676672113}}
+{{x = 0.3037698832307662, y = 0.69610758676672113}, {x = 0.30387252963474076, y = 0.69616688005807803}}
+{{x = 0.30387252963474076, y = 0.69616688005807803}, {x = 0.3039751936710845, y = 0.69622610811401087}}
+</div>
+
</div>
<script type="text/javascript">
var testDivs = [
+ testCubic1b,
+ testCubic1a,
+ testCubic1,
+ cubic27,
+ cubic26,
+ quad23,
+ cubic25,
quad22,
cubic24,
quad21,
@@ -1857,8 +1928,7 @@
var ticks = 10;
var at_x = 13 + 0.5;
var at_y = 23 + 0.5;
-var init_decimal_places = 1; // make this 3 to show more precision
-var decimal_places;
+var decimal_places = 3;
var tests = [];
var testTitles = [];
var testIndex = 0;
@@ -1869,6 +1939,7 @@
var drawCubics = true;
var drawQuads = true;
var drawControlLines = true;
+var xmin, xmax, ymin, ymax;
function parse(test, title) {
var curveStrs = test.split("{{");
@@ -1900,10 +1971,10 @@
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;
+ xmin = Infinity;
+ xmax = -Infinity;
+ ymin = Infinity;
+ ymax = -Infinity;
for (var curves in test) {
var curve = test[curves];
var last = curve.length;
@@ -1923,14 +1994,18 @@
while (testW * subscale > 10 && testH * subscale > 10) {
subscale /= 10;
}
+ calcFromScale();
+}
+
+function calcFromScale() {
xStart = Math.floor(xmin * subscale) / subscale;
yStart = Math.floor(ymin * subscale) / subscale;
var xEnd = Math.ceil(xmin * subscale) / subscale;
var yEnd = Math.ceil(ymin * subscale) / subscale;
var cCelsW = Math.floor(ctx.canvas.width / 10);
var cCelsH = Math.floor(ctx.canvas.height / 10);
- testW = xEnd - xStart;
- testH = yEnd - yStart;
+ var testW = xEnd - xStart;
+ var testH = yEnd - yStart;
var scaleWH = 1;
while (cCelsW > testW * scaleWH * 10 && cCelsH > testH * scaleWH * 10) {
scaleWH *= 10;
@@ -2009,6 +2084,10 @@
ctx.beginPath();
ctx.moveTo(xoffset + curve[0] * unit, yoffset + curve[1] * unit);
switch (curve.length) {
+ case 4:
+ ctx.lineTo(
+ xoffset + curve[2] * unit, yoffset + curve[3] * unit);
+ break;
case 6:
ctx.quadraticCurveTo(
xoffset + curve[2] * unit, yoffset + curve[3] * unit,
@@ -2023,7 +2102,7 @@
}
if (curves == 2) ctx.strokeStyle = curves ? "red" : "blue";
ctx.stroke();
- if (drawControlLines) {
+ if (drawControlLines && curve.length >= 6) {
ctx.strokeStyle = "rgba(0,0,0, 0.3)";
ctx.beginPath();
ctx.moveTo(xoffset + curve[0] * unit, yoffset + curve[1] * unit);
@@ -2037,6 +2116,12 @@
var x, y;
var t = curveT;
switch (curve.length) {
+ case 4:
+ var a = 1 - t;
+ var b = t;
+ x = a * curve[0] + b * curve[2];
+ y = a * curve[1] + b * curve[3];
+ break;
case 6:
var one_t = 1 - t;
var a = one_t * one_t;
@@ -2058,7 +2143,7 @@
break;
}
drawPoint(x, y, xoffset, yoffset, unit);
- var num = curveT.toFixed(3);
+ var num = curveT.toFixed(decimal_places);
ctx.beginPath();
ctx.rect(200,10,200,10);
ctx.fillStyle="white";
@@ -2106,6 +2191,17 @@
drawCubics ^= true;
redraw();
break;
+ case 'd':
+ decimal_places++;
+ redraw();
+ break;
+ case 'D':
+ decimal_places--;
+ if (decimal_places < 1) {
+ decimal_places = 1;
+ }
+ redraw();
+ break;
case 'l':
drawControlLines ^= true;
redraw();
@@ -2135,6 +2231,18 @@
drawQuads ^= true;
redraw();
break;
+ case '-':
+ case '_':
+ subscale /= 2;
+ calcFromScale();
+ redraw();
+ break;
+ case '+':
+ case '=':
+ subscale *= 2;
+ calcFromScale();
+ redraw();
+ break;
}
}
@@ -2159,7 +2267,7 @@
function handleMouseOver() {
calcXY();
- var num = mouseX.toFixed(3) + ", " + mouseY.toFixed(3);
+ var num = mouseX.toFixed(decimal_places) + ", " + mouseY.toFixed(decimal_places);
ctx.beginPath();
ctx.rect(30,10,200,10);
ctx.fillStyle="white";