aboutsummaryrefslogtreecommitdiffhomepage
diff options
context:
space:
mode:
Diffstat
-rw-r--r--experimental/Intersection/DataTypes.h8
-rw-r--r--experimental/Intersection/EdgeWalker_TestUtility.cpp9
-rw-r--r--experimental/Intersection/LineIntersection.cpp2
-rw-r--r--experimental/Intersection/LineParameters.h2
-rw-r--r--experimental/Intersection/QuadraticImplicit.cpp30
-rw-r--r--experimental/Intersection/QuarticRoot.cpp92
-rw-r--r--experimental/Intersection/Simplify.cpp72
-rw-r--r--experimental/Intersection/SimplifyNew_Test.cpp142
-rw-r--r--experimental/Intersection/bc.htm117
-rw-r--r--experimental/Intersection/op.htm158
10 files changed, 570 insertions, 62 deletions
diff --git a/experimental/Intersection/DataTypes.h b/experimental/Intersection/DataTypes.h
index 0c51a20647..c87beb033b 100644
--- a/experimental/Intersection/DataTypes.h
+++ b/experimental/Intersection/DataTypes.h
@@ -74,6 +74,10 @@ inline bool approximately_zero(float x) {
return fabs(x) < FLT_EPSILON;
}
+inline bool approximately_zero_squared(double x) {
+ return fabs(x) < FLT_EPSILON * FLT_EPSILON;
+}
+
inline bool approximately_equal(double x, double y) {
if (approximately_zero(x - y)) {
return true;
@@ -101,10 +105,6 @@ inline float approximately_pin(float x) {
return approximately_zero(x) ? 0 : x;
}
-inline bool approximately_zero_squared(double x) {
- return approximately_zero(x);
-}
-
inline bool approximately_greater_than_one(double x) {
return x > 1 - FLT_EPSILON;
}
diff --git a/experimental/Intersection/EdgeWalker_TestUtility.cpp b/experimental/Intersection/EdgeWalker_TestUtility.cpp
index fa590c318a..4897cbc908 100644
--- a/experimental/Intersection/EdgeWalker_TestUtility.cpp
+++ b/experimental/Intersection/EdgeWalker_TestUtility.cpp
@@ -136,10 +136,10 @@ static int pathsDrawTheSame(const SkPath& one, const SkPath& two,
if (!c) {
delete canvasPtr;
}
- if (errors2 >= 3 || errors > 96) {
+ if (errors2 >= 6 || errors > 160) {
SkDebugf("%s errors2=%d errors=%d\n", __FUNCTION__, errors2, errors);
}
- if (errors2 >= 4 || errors > 192) {
+ if (errors2 >= 7) {
drawAsciiPaths(scaledOne, scaledTwo, true);
}
error2x2 = errors2;
@@ -205,7 +205,7 @@ int comparePaths(const SkPath& one, const SkPath& two, SkBitmap& bitmap,
if (errors2x2 == 0) {
return 0;
}
- const int MAX_ERRORS = 5;
+ const int MAX_ERRORS = 8;
if (errors2x2 > MAX_ERRORS && gComparePathsAssert) {
SkDebugf("%s errors=%d\n", __FUNCTION__, errors);
showPath(one);
@@ -271,6 +271,7 @@ bool testSimplifyx(SkPath& path, bool useXor, SkPath& out, State4& state,
}
int result = comparePaths(path, out, state.bitmap, state.canvas);
if (result && gPathStrAssert) {
+ SkDebugf("addTest %s\n", state.filename);
char temp[8192];
bzero(temp, sizeof(temp));
SkMemoryWStream stream(temp, sizeof(temp));
@@ -298,7 +299,7 @@ static int threadIndex;
State4 threadState[maxThreadsAllocated];
static int testNumber;
static const char* testName;
-static bool debugThreads = false;
+static bool debugThreads = true;
State4* State4::queue = NULL;
pthread_mutex_t State4::addQueue = PTHREAD_MUTEX_INITIALIZER;
diff --git a/experimental/Intersection/LineIntersection.cpp b/experimental/Intersection/LineIntersection.cpp
index d565d91909..11f42ba2d5 100644
--- a/experimental/Intersection/LineIntersection.cpp
+++ b/experimental/Intersection/LineIntersection.cpp
@@ -28,7 +28,7 @@ int intersect(const _Line& a, const _Line& b, double aRange[2], double bRange[2]
byLen * axLen - ayLen * bxLen == 0 ( == denom )
*/
double denom = byLen * axLen - ayLen * bxLen;
- if (approximately_zero_squared(denom)) {
+ if (approximately_zero(denom)) {
/* See if the axis intercepts match:
ay - ax * ayLen / axLen == by - bx * ayLen / axLen
axLen * (ay - ax * ayLen / axLen) == axLen * (by - bx * ayLen / axLen)
diff --git a/experimental/Intersection/LineParameters.h b/experimental/Intersection/LineParameters.h
index d4d741932c..fc1bcc873a 100644
--- a/experimental/Intersection/LineParameters.h
+++ b/experimental/Intersection/LineParameters.h
@@ -53,7 +53,7 @@ public:
bool normalize() {
double normal = sqrt(normalSquared());
- if (approximately_zero_squared(normal)) {
+ if (approximately_zero(normal)) {
a = b = c = 0;
return false;
}
diff --git a/experimental/Intersection/QuadraticImplicit.cpp b/experimental/Intersection/QuadraticImplicit.cpp
index c8635d408c..be54ed688e 100644
--- a/experimental/Intersection/QuadraticImplicit.cpp
+++ b/experimental/Intersection/QuadraticImplicit.cpp
@@ -91,23 +91,26 @@ bool intersect2(const Quadratic& q1, const Quadratic& q2, Intersections& i) {
double roots1[4], roots2[4];
int rootCount = findRoots(i2, q1, roots1);
// OPTIMIZATION: could short circuit here if all roots are < 0 or > 1
- int rootCount2 = findRoots(i1, q2, roots2);
+#ifndef NDEBUG
+ int rootCount2 =
+#endif
+ findRoots(i1, q2, roots2);
assert(rootCount == rootCount2);
addValidRoots(roots1, rootCount, 0, i);
addValidRoots(roots2, rootCount, 1, i);
_Point pts[4];
bool matches[4];
- int index;
- for (index = 0; index < i.fUsed2; ++index) {
- xy_at_t(q2, i.fT[1][index], pts[index].x, pts[index].y);
- matches[index] = false;
+ int index, ndex2;
+ for (ndex2 = 0; ndex2 < i.fUsed2; ++ndex2) {
+ xy_at_t(q2, i.fT[1][ndex2], pts[ndex2].x, pts[ndex2].y);
+ matches[ndex2] = false;
}
for (index = 0; index < i.fUsed; ) {
_Point xy;
xy_at_t(q1, i.fT[0][index], xy.x, xy.y);
- for (int inner = 0; inner < i.fUsed2; ++inner) {
- if (approximately_equal(pts[inner].x, xy.x) && approximately_equal(pts[inner].y, xy.y)) {
- matches[index] = true;
+ for (ndex2 = 0; ndex2 < i.fUsed2; ++ndex2) {
+ if (approximately_equal(pts[ndex2].x, xy.x) && approximately_equal(pts[ndex2].y, xy.y)) {
+ matches[ndex2] = true;
goto next;
}
}
@@ -118,14 +121,15 @@ bool intersect2(const Quadratic& q1, const Quadratic& q2, Intersections& i) {
next:
++index;
}
- for (index = 0; index < i.fUsed2; ) {
- if (!matches[index]) {
- if (--i.fUsed2 > index) {
- memmove(&i.fT[1][index], &i.fT[1][index + 1], (i.fUsed2 - index) * sizeof(i.fT[1][0]));
+ for (ndex2 = 0; ndex2 < i.fUsed2; ) {
+ if (!matches[ndex2]) {
+ if (--i.fUsed2 > ndex2) {
+ memmove(&i.fT[1][ndex2], &i.fT[1][ndex2 + 1], (i.fUsed2 - ndex2) * sizeof(i.fT[1][0]));
+ memmove(&matches[ndex2], &matches[ndex2 + 1], (i.fUsed2 - ndex2) * sizeof(matches[0]));
continue;
}
}
- ++index;
+ ++ndex2;
}
assert(i.insertBalanced());
return i.intersected();
diff --git a/experimental/Intersection/QuarticRoot.cpp b/experimental/Intersection/QuarticRoot.cpp
index e0ec2b0f29..8e3664bef5 100644
--- a/experimental/Intersection/QuarticRoot.cpp
+++ b/experimental/Intersection/QuarticRoot.cpp
@@ -61,6 +61,8 @@ static int quadraticRootsX(const double A, const double B, const double C,
}
}
+#define USE_GEMS 0
+#if USE_GEMS
// unlike cubicRoots in CubicUtilities.cpp, this does not discard
// real roots <= 0 or >= 1
static int cubicRootsX(const double A, const double B, const double C,
@@ -92,7 +94,7 @@ static int cubicRootsX(const double A, const double B, const double C,
}
}
else if (R2plusQ3 < 0) { /* Casus irreducibilis: three real solutions */
- const double theta = 1.0/3 * acos(-R / sqrt(-Q3));
+ const double theta = acos(-R / sqrt(-Q3)) / 3;
const double _2RootQ = 2 * sqrt(-Q);
s[0] = _2RootQ * cos(theta);
s[1] = -_2RootQ * cos(theta + PI / 3);
@@ -106,12 +108,84 @@ static int cubicRootsX(const double A, const double B, const double C,
num = 1;
}
/* resubstitute */
- const double sub = 1.0/3 * a;
+ const double sub = a / 3;
for (int i = 0; i < num; ++i) {
s[i] -= sub;
}
return num;
}
+#else
+
+static int cubicRootsX(double A, double B, double C, double D, double s[3]) {
+ if (approximately_zero(A)) { // we're just a quadratic
+ return quadraticRootsX(B, C, D, s);
+ }
+ if (approximately_zero(D)) {
+ int num = quadraticRootsX(A, B, C, s);
+ for (int i = 0; i < num; ++i) {
+ if (approximately_zero(s[i])) {
+ return num;
+ }
+ }
+ s[num++] = 0;
+ return num;
+ }
+ double a, b, c;
+ {
+ double invA = 1 / A;
+ a = B * invA;
+ b = C * invA;
+ c = D * invA;
+ }
+ double a2 = a * a;
+ double Q = (a2 - b * 3) / 9;
+ double R = (2 * a2 * a - 9 * a * b + 27 * c) / 54;
+ double Q3 = Q * Q * Q;
+ double R2MinusQ3 = R * R - Q3;
+ double adiv3 = a / 3;
+ double r;
+ double* roots = s;
+
+ if (R2MinusQ3 > -FLT_EPSILON / 10 && R2MinusQ3 < FLT_EPSILON / 10 ) {
+ if (approximately_zero(R)) {/* one triple solution */
+ *roots++ = -adiv3;
+ } else { /* one single and one double solution */
+
+ double u = cube_root(-R);
+ *roots++ = 2 * u - adiv3;
+ *roots++ = -u - adiv3;
+ }
+ }
+ else if (R2MinusQ3 < 0) // we have 3 real roots
+ {
+ double theta = acos(R / sqrt(Q3));
+ double neg2RootQ = -2 * sqrt(Q);
+
+ r = neg2RootQ * cos(theta / 3) - adiv3;
+ *roots++ = r;
+
+ r = neg2RootQ * cos((theta + 2 * PI) / 3) - adiv3;
+ *roots++ = r;
+
+ r = neg2RootQ * cos((theta - 2 * PI) / 3) - adiv3;
+ *roots++ = r;
+ }
+ else // we have 1 real root
+ {
+ double A = fabs(R) + sqrt(R2MinusQ3);
+ A = cube_root(A);
+ if (R > 0) {
+ A = -A;
+ }
+ if (A != 0) {
+ A += Q / A;
+ }
+ r = A - adiv3;
+ *roots++ = r;
+ }
+ return (int)(roots - s);
+}
+#endif
int quarticRoots(const double A, const double B, const double C, const double D,
const double E, double s[4]) {
@@ -121,8 +195,19 @@ int quarticRoots(const double A, const double B, const double C, const double D,
}
return cubicRootsX(B, C, D, E, s);
}
- double u, v;
int num;
+ int i;
+ if (approximately_zero(E)) {
+ num = cubicRootsX(A, B, C, D, s);
+ for (i = 0; i < num; ++i) {
+ if (approximately_zero(s[i])) {
+ return num;
+ }
+ }
+ s[num++] = 0;
+ return num;
+ }
+ double u, v;
/* normal form: x^4 + Ax^3 + Bx^2 + Cx + D = 0 */
const double invA = 1 / A;
const double a = B * invA;
@@ -165,7 +250,6 @@ int quarticRoots(const double A, const double B, const double C, const double D,
num += quadraticRootsX(1, q < 0 ? v : -v, z + u, s + num);
}
// eliminate duplicates
- int i;
for (i = 0; i < num - 1; ++i) {
for (int j = i + 1; j < num; ) {
if (approximately_equal(s[i], s[j])) {
diff --git a/experimental/Intersection/Simplify.cpp b/experimental/Intersection/Simplify.cpp
index b5403bfbb4..827c6178ff 100644
--- a/experimental/Intersection/Simplify.cpp
+++ b/experimental/Intersection/Simplify.cpp
@@ -503,10 +503,16 @@ public:
if (y == 0 && ry == 0 && x * rx < 0) {
return x < rx;
}
- AngleValue cmp = x * ry - rx * y;
+ AngleValue x_ry = x * ry;
+ AngleValue rx_y = rx * y;
+ AngleValue cmp = x_ry - rx_y;
if (!approximately_zero(cmp)) {
return cmp < 0;
}
+ if (approximately_zero(x_ry) && approximately_zero(rx_y)
+ && !approximately_zero_squared(cmp)) {
+ return cmp < 0;
+ }
// at this point, the initial tangent line is coincident
#if !HIGH_DEF_ANGLES // old way
AngleValue dy = approximately_pin(fDy + fDDy);
@@ -536,6 +542,9 @@ public:
return dx * rdy < rdx * dy;
#else // new way
if (fSide * rh.fSide <= 0) {
+ // FIXME: running demo will trigger this assertion
+ // (don't know if commenting out will trigger further assertion or not)
+ // commenting it out allows demo to run in release, though
SkASSERT(fSide != rh.fSide);
return fSide < rh.fSide;
}
@@ -555,21 +564,35 @@ public:
#else
SkASSERT(fVerb == SkPath::kQuad_Verb); // worry about cubics later
SkASSERT(rh.fVerb == SkPath::kQuad_Verb);
- // FIXME: until I can think of something better, project a ray perpendicular from the
- // end of the shorter tangent through both curves and use the resulting angle to sort
+ // FIXME: until I can think of something better, project a ray from the
+ // end of the shorter tangent to midway between the end points
+ // through both curves and use the resulting angle to sort
// FIXME: some of this setup can be moved to set() if it works, or cached if it's expensive
double len = fTangent1.normalSquared();
double rlen = rh.fTangent1.normalSquared();
SkPoint ray[2];
- const Quadratic& q = len < rlen ? fQ : rh.fQ;
- ray[0].fX = SkDoubleToScalar(q[1].x);
- ray[0].fY = SkDoubleToScalar(q[1].y);
- ray[1].fX = SkDoubleToScalar((q[0].x + q[2].x) / 2);
- ray[1].fY = SkDoubleToScalar((q[0].y + q[2].y) / 2);
Intersections i, ri;
- int roots = QuadRayIntersect(fPts, ray, i);
+ int roots, rroots;
+ bool flip = false;
+ do {
+ const Quadratic& q = (len < rlen) ^ flip ? fQ : rh.fQ;
+ double midX = (q[0].x + q[2].x) / 2;
+ double midY = (q[0].y + q[2].y) / 2;
+ // FIXME: Ugh! this feels like a huge hack, not sure what else to do
+ while (approximately_equal(q[1].x, midX) && approximately_equal(q[1].y, midY)) {
+ SkASSERT(midX - q[1].x || midY - q[1].y);
+ midX += midX - q[1].x;
+ midY += midY - q[1].y;
+ }
+ ray[0].fX = SkDoubleToScalar(q[1].x);
+ ray[0].fY = SkDoubleToScalar(q[1].y);
+ ray[1].fX = SkDoubleToScalar(midX);
+ ray[1].fY = SkDoubleToScalar(midY);
+ SkASSERT(ray[0] != ray[1]);
+ roots = QuadRayIntersect(fPts, ray, i);
+ rroots = QuadRayIntersect(rh.fPts, ray, ri);
+ } while ((roots == 0 || rroots == 0) && (flip ^= true));
SkASSERT(roots > 0);
- int rroots = QuadRayIntersect(rh.fPts, ray, ri);
SkASSERT(rroots > 0);
SkPoint loc;
SkScalar best = SK_ScalarInfinity;
@@ -1499,6 +1522,8 @@ public:
SkTDArray<Angle> angles;
addTwoAngles(startIndex, endIndex, angles);
buildAngles(endIndex, angles);
+ // OPTIMIZATION: check all angles to see if any have computed wind sum
+ // before sorting (early exit if none)
SkTDArray<Angle*> sorted;
sortAngles(angles, sorted);
#if DEBUG_SORT
@@ -1567,13 +1592,15 @@ public:
continue;
}
SkPoint edge[4];
- // OPTIMIZE: wrap this so that if start==0 end==fTCount-1 we can
- // work with the original data directly
double startT = fTs[start].fT;
double endT = fTs[end].fT;
(*SegmentSubDivide[fVerb])(fPts, startT, endT, edge);
// intersect ray starting at basePt with edge
Intersections intersections;
+ // FIXME: always use original and limit results to T values within
+ // start t and end t.
+ // OPTIMIZE: use specialty function that intersects ray with curve,
+ // returning t values only for curve (we don't care about t on ray)
int pts = (*VSegmentIntersect[fVerb])(edge, top, bottom, basePt.fX,
false, intersections);
if (pts == 0) {
@@ -1589,6 +1616,14 @@ public:
double testT = startT + (endT - startT) * foundT;
(*SegmentXYAtT[fVerb])(fPts, testT, &pt);
if (bestY < pt.fY && pt.fY < basePt.fY) {
+ if (fVerb > SkPath::kLine_Verb
+ && !approximately_less_than_zero(foundT)
+ && !approximately_greater_than_one(foundT)) {
+ SkScalar dx = (*SegmentDXAtT[fVerb])(fPts, testT);
+ if (approximately_zero(dx)) {
+ continue;
+ }
+ }
bestY = pt.fY;
bestT = foundT < 1 ? start : end;
hitT = testT;
@@ -1760,7 +1795,7 @@ public:
otherNonZero = bSumWinding & bXorMask;
}
altFlipped ^= lastNonZeroSum * sumWinding < 0; // flip if different signs
- #if DEBUG_WINDING
+ #if 0 && DEBUG_WINDING
SkASSERT(abs(sumWinding) <= gDebugMaxWindSum);
SkDebugf("%s [%d] maxWinding=%d sumWinding=%d sign=%d altFlipped=%d\n", __FUNCTION__,
nextIndex, maxWinding, sumWinding, nextAngle->sign(), altFlipped);
@@ -1963,7 +1998,7 @@ public:
nextSegment = nextAngle->segment();
sumWinding -= nextSegment->spanSign(nextAngle);
altFlipped ^= lastNonZeroSum * sumWinding < 0; // flip if different signs
- #if DEBUG_WINDING
+ #if 0 && DEBUG_WINDING
SkASSERT(abs(sumWinding) <= gDebugMaxWindSum);
SkDebugf("%s [%d] maxWinding=%d sumWinding=%d sign=%d altFlipped=%d\n", __FUNCTION__,
nextIndex, maxWinding, sumWinding, nextAngle->sign(), altFlipped);
@@ -3934,6 +3969,11 @@ static int innerContourCheck(SkTDArray<Contour*>& contourList,
continue;
}
double indexDx = angle->dx();
+ test = angle->segment();
+ if (test->verb() > SkPath::kLine_Verb && approximately_zero(indexDx)) {
+ const SkPoint* pts = test->pts();
+ indexDx = pts[2].fX - pts[1].fX - indexDx;
+ }
if (indexDx < 0) {
left = index;
} else if (indexDx > 0) {
@@ -3984,6 +4024,10 @@ static int innerContourCheck(SkTDArray<Contour*>& contourList,
}
// see if a + change in T results in a +/- change in X (compute x'(T))
SkScalar dx = (*SegmentDXAtT[test->verb()])(test->pts(), tHit);
+ if (test->verb() > SkPath::kLine_Verb && approximately_zero(dx)) {
+ const SkPoint* pts = test->pts();
+ dx = pts[2].fX - pts[1].fX - dx;
+ }
#if DEBUG_WINDING
SkDebugf("%s dx=%1.9g\n", __FUNCTION__, dx);
#endif
diff --git a/experimental/Intersection/SimplifyNew_Test.cpp b/experimental/Intersection/SimplifyNew_Test.cpp
index 980baa8d02..d317abab85 100644
--- a/experimental/Intersection/SimplifyNew_Test.cpp
+++ b/experimental/Intersection/SimplifyNew_Test.cpp
@@ -2698,12 +2698,152 @@ static void testQuadratic28() {
testSimplifyx(path);
}
-static void (*firstTest)() = testQuadratic28;
+static void testQuadratic29() {
+ SkPath path;
+ path.moveTo(0, 0);
+ path.quadTo(1, 0, 2, 1);
+ path.lineTo(0, 2);
+ path.close();
+ path.moveTo(0, 0);
+ path.lineTo(0, 0);
+ path.quadTo(1, 0, 0, 1);
+ path.close();
+ testSimplifyx(path);
+}
+
+static void testQuadratic30() {
+ SkPath path;
+ path.moveTo(0, 0);
+ path.quadTo(1, 0, 1, 2);
+ path.lineTo(1, 2);
+ path.close();
+ path.moveTo(0, 0);
+ path.lineTo(1, 0);
+ path.quadTo(0, 1, 1, 2);
+ path.close();
+ testSimplifyx(path);
+}
+
+static void testQuadratic31() {
+ SkPath path;
+ path.moveTo(0, 0);
+ path.quadTo(1, 0, 1, 2);
+ path.lineTo(1, 2);
+ path.close();
+ path.moveTo(0, 0);
+ path.lineTo(1, 0);
+ path.quadTo(0, 1, 1, 3);
+ path.close();
+ testSimplifyx(path);
+}
+
+static void testQuadratic32() {
+ SkPath path;
+ path.moveTo(0, 0);
+ path.quadTo(1, 0, 2, 3);
+ path.lineTo(2, 3);
+ path.close();
+ path.moveTo(0, 0);
+ path.lineTo(0, 0);
+ path.quadTo(3, 1, 0, 2);
+ path.close();
+ testSimplifyx(path);
+}
+
+static void testQuadratic33() {
+ SkPath path;
+ path.moveTo(0, 0);
+ path.quadTo(2, 0, 0, 1);
+ path.lineTo(0, 1);
+ path.close();
+ path.moveTo(0, 0);
+ path.lineTo(1, 1);
+ path.quadTo(2, 1, 2, 2);
+ path.close();
+ testSimplifyx(path);
+}
+
+static void testQuadratic34() {
+ SkPath path;
+ path.moveTo(0, 0);
+ path.quadTo(2, 0, 0, 1);
+ path.lineTo(0, 1);
+ path.close();
+ path.moveTo(1, 0);
+ path.lineTo(1, 1);
+ path.quadTo(2, 1, 1, 2);
+ path.close();
+ testSimplifyx(path);
+}
+
+static void testQuadratic35() {
+ SkPath path;
+ path.moveTo(0, 0);
+ path.quadTo(0, 1, 1, 1);
+ path.lineTo(1, 3);
+ path.close();
+ path.moveTo(2, 0);
+ path.lineTo(3, 0);
+ path.quadTo(0, 1, 1, 1);
+ path.close();
+ testSimplifyx(path);
+}
+
+static void testQuadratic36() {
+ SkPath path;
+ path.moveTo(0, 0);
+ path.quadTo(2, 1, 2, 3);
+ path.lineTo(2, 3);
+ path.close();
+ path.moveTo(3, 1);
+ path.lineTo(1, 2);
+ path.quadTo(3, 2, 1, 3);
+ path.close();
+ testSimplifyx(path);
+}
+
+static void testQuadratic37() {
+ SkPath path;
+ path.moveTo(0, 0);
+ path.quadTo(0, 2, 1, 2);
+ path.lineTo(1, 2);
+ path.close();
+ path.moveTo(0, 0);
+ path.lineTo(3, 1);
+ path.quadTo(0, 2, 1, 2);
+ path.close();
+ testSimplifyx(path);
+}
+
+static void testQuadratic38() {
+ SkPath path;
+ path.moveTo(1, 0);
+ path.quadTo(0, 1, 1, 1);
+ path.lineTo(1, 1);
+ path.close();
+ path.moveTo(1, 0);
+ path.lineTo(1, 2);
+ path.quadTo(2, 2, 1, 3);
+ path.close();
+ testSimplifyx(path);
+}
+
+static void (*firstTest)() = testQuadratic38;
static struct {
void (*fun)();
const char* str;
} tests[] = {
+ TEST(testQuadratic38),
+ TEST(testQuadratic37),
+ TEST(testQuadratic36),
+ TEST(testQuadratic35),
+ TEST(testQuadratic34),
+ TEST(testQuadratic33),
+ TEST(testQuadratic32),
+ TEST(testQuadratic31),
+ TEST(testQuadratic30),
+ TEST(testQuadratic29),
TEST(testQuadratic28),
TEST(testQuadratic27),
TEST(testQuadratic26),
diff --git a/experimental/Intersection/bc.htm b/experimental/Intersection/bc.htm
index 8a659f71d2..95a8d754ab 100644
--- a/experimental/Intersection/bc.htm
+++ b/experimental/Intersection/bc.htm
@@ -83,11 +83,38 @@ $2 = {{
}}
</div>
+<div id="quad36">
+(gdb) p fQ
+$2 = {{
+ x = 1.8883839294261275,
+ y = 2.1108590606904345
+ }, {
+ x = 1.888463903363252,
+ y = 2.1111576060205435
+ }, {
+ x = 1.8885438199983176,
+ y = 2.1114561800016824
+ }}
+(gdb) p rh.fQ
+$3 = {{
+ x = 1.8883839294260976,
+ y = 2.1108590606903377
+ }, {
+ x = 1.8886366953645748,
+ y = 2.1109850143489544
+ }, {
+ x = 1.8888888888888888,
+ y = 2.1111111111111112
+ }}
+(gdb)
+</div>
+
</div>
<script type="text/javascript">
var testDivs = [
+ quad36,
quad21g,
quad21a,
quad21b,
@@ -100,17 +127,23 @@ var testDivs = [
var scale, columns, rows, xStart, yStart;
-var ticks = 0.1;
+var ticks = 10;
var at_x = 13 + 0.5;
var at_y = 13 + 0.5;
-var decimal_places = 0; // make this 3 to show more precision
-
+var init_decimal_places = 1; // make this 3 to show more precision
+var decimal_places;
var tests = [];
var testTitles = [];
var testIndex = 0;
var ctx;
var fat1 = true;
var fat2 = false;
+var ctl1 = true;
+var ctl2 = false;
+var ctlPts1 = true;
+var ctlPts2 = false;
+var minScale = 1;
+var subscale = 1;
function parse(test, title) {
var curveStrs = test.split("{{");
@@ -156,22 +189,30 @@ function init(test) {
ymax = Math.max(ymax, curve[idx + 1]);
}
}
- var subscale = 1;
+ subscale = 1;
+ decimal_places = init_decimal_places;
if (xmax != xmin && ymax != ymin) {
while ((xmax - xmin) * subscale < 0.1 && (ymax - ymin) * subscale < 0.1) {
subscale *= 10;
- if (subscale > 100000) {
- break;
- }
+ decimal_places += 1;
+ // if (subscale > 100000) {
+ // break;
+ // }
}
}
- columns = Math.ceil(xmax) - Math.floor(xmin) + 1;
- rows = Math.ceil(ymax) - Math.floor(ymin) + 1;
- xStart = Math.floor(xmin);
- yStart = Math.floor(ymin);
+ columns = Math.ceil(xmax * subscale) - Math.floor(xmin * subscale) + 1;
+ rows = Math.ceil(ymax * subscale) - Math.floor(ymin * subscale) + 1;
+
+ xStart = Math.floor(xmin * subscale) / subscale;
+ yStart = Math.floor(ymin * subscale) / subscale;
var hscale = ctx.canvas.width / columns / ticks;
var vscale = ctx.canvas.height / rows / ticks;
- scale = Math.floor(Math.min(hscale, vscale)) * subscale;
+ minScale = Math.floor(Math.min(hscale, vscale));
+ scale = minScale * subscale;
+ // while (columns < 1000 && rows < 1000) {
+ // columns *= 2;
+ // rows *= 2;
+ // }
}
function drawPoint(px, py, xoffset, yoffset, unit) {
@@ -197,15 +238,15 @@ function draw(test, title, _at_x, _at_y, scale) {
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.moveTo(_at_x + 0, _at_y + i * minScale);
+ ctx.lineTo(_at_x + unit * columns, _at_y + i * minScale);
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.moveTo(_at_x + i * minScale, _at_y + 0);
+ ctx.lineTo(_at_x + i * minScale, _at_y + unit * rows);
ctx.stroke();
}
@@ -215,13 +256,13 @@ function draw(test, title, _at_x, _at_y, scale) {
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);
+ num = xStart + i / subscale;
+ ctx.fillText(num.toFixed(decimal_places), xoffset + num * unit - 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);
+ num = yStart + i / subscale;
+ ctx.fillText(num.toFixed(decimal_places), 0, yoffset + num * unit + 0);
}
// draw curve 1 and 2
@@ -259,6 +300,30 @@ function draw(test, title, _at_x, _at_y, scale) {
drawFat(test[0], xoffset, yoffset, unit);
if (fat2)
drawFat(test[1], xoffset, yoffset, unit);
+ if (ctl1)
+ drawCtl(test[0], xoffset, yoffset, unit);
+ if (ctl2)
+ drawCtl(test[1], xoffset, yoffset, unit);
+ if (ctlPts1)
+ drawCtlPts(test[0], xoffset, yoffset, unit);
+ if (ctlPts2)
+ drawCtlPts(test[1], xoffset, yoffset, unit);
+}
+
+function drawCtl(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[2] * unit, yoffset + curve[3] * unit);
+ ctx.lineTo(xoffset + curve[4] * unit, yoffset + curve[5] * unit);
+ ctx.stroke();
+}
+
+function drawCtlPts(curve, xoffset, yoffset, unit) {
+ drawPoint(curve[0], curve[1], xoffset, yoffset, unit);
+ drawPoint(curve[2], curve[3], xoffset, yoffset, unit);
+ drawPoint(curve[4], curve[5], xoffset, yoffset, unit);
}
function drawFat(curve, xoffset, yoffset, unit) {
@@ -303,6 +368,18 @@ function redraw() {
function doKeyPress(evt) {
var char = String.fromCharCode(evt.charCode);
switch (char) {
+ case 'c':
+ ctl2 ^= true;
+ if (ctl2 == false)
+ ctl1 ^= true;
+ drawTop();
+ break;
+ case 'd':
+ ctlPts2 ^= true;
+ if (ctlPts2 == false)
+ ctlPts1 ^= true;
+ drawTop();
+ break;
case 'f':
fat2 ^= true;
if (fat2 == false)
diff --git a/experimental/Intersection/op.htm b/experimental/Intersection/op.htm
index 4643ade47e..2063152c7a 100644
--- a/experimental/Intersection/op.htm
+++ b/experimental/Intersection/op.htm
@@ -1410,11 +1410,169 @@ path.close();
path.close();
</div>
+<div id="testQuadratic29">
+ path.moveTo(0, 0);
+ path.quadTo(1, 0, 2, 1);
+ path.lineTo(0, 2);
+ path.close();
+ path.moveTo(0, 0);
+ path.lineTo(0, 0);
+ path.quadTo(1, 0, 0, 1);
+ path.close();
+</div>
+
+<div id="testQuadratic30">
+ path.moveTo(0, 0);
+ path.quadTo(1, 0, 1, 2);
+ path.lineTo(1, 2);
+ path.close();
+ path.moveTo(0, 0);
+ path.lineTo(1, 0);
+ path.quadTo(0, 1, 1, 2);
+ path.close();
+</div>
+
+<div id="testQuadratic31">
+ path.moveTo(0, 0);
+ path.quadTo(1, 0, 1, 2);
+ path.lineTo(1, 2);
+ path.close();
+ path.moveTo(0, 0);
+ path.lineTo(1, 0);
+ path.quadTo(0, 1, 1, 3);
+ path.close();
+</div>
+
+<div id="testQuadratic32">
+ path.moveTo(0, 0);
+ path.quadTo(1, 0, 2, 3);
+ path.lineTo(2, 3);
+ path.close();
+ path.moveTo(0, 0);
+ path.lineTo(0, 0);
+ path.quadTo(3, 1, 0, 2);
+ path.close();
+</div>
+
+<div id="testQuadratic33">
+ path.moveTo(0, 0);
+ path.quadTo(2, 0, 0, 1);
+ path.lineTo(0, 1);
+ path.close();
+ path.moveTo(0, 0);
+ path.lineTo(1, 1);
+ path.quadTo(2, 1, 2, 2);
+ path.close();
+</div>
+
+<div id="testQuadratic34">
+ path.moveTo(0, 0);
+ path.quadTo(2, 0, 0, 1);
+ path.lineTo(0, 1);
+ path.close();
+ path.moveTo(1, 0);
+ path.lineTo(1, 1);
+ path.quadTo(2, 1, 1, 2);
+ path.close();
+</div>
+
+<div id="testQuadratic35">
+ path.moveTo(0, 0);
+ path.quadTo(0, 1, 1, 1);
+ path.lineTo(1, 3);
+ path.close();
+ path.moveTo(2, 0);
+ path.lineTo(3, 0);
+ path.quadTo(0, 1, 1, 1);
+ path.close();
+</div>
+
+<div id="testQuadratic36">
+ path.moveTo(0, 0);
+ path.quadTo(2, 1, 2, 3);
+ path.lineTo(2, 3);
+ path.close();
+ path.moveTo(3, 1);
+ path.lineTo(1, 2);
+ path.quadTo(3, 2, 1, 3);
+ path.close();
+</div>
+
+<div id="testQuadratic37">
+ path.moveTo(0, 0);
+ path.quadTo(0, 2, 1, 2);
+ path.lineTo(1, 2);
+ path.close();
+ path.moveTo(0, 0);
+ path.lineTo(3, 1);
+ path.quadTo(0, 2, 1, 2);
+ path.close();
+</div>
+
+<div id="testQuadratic38">
+ path.moveTo(1, 0);
+ path.quadTo(0, 1, 1, 1);
+ path.lineTo(1, 1);
+ path.close();
+ path.moveTo(1, 0);
+ path.lineTo(1, 2);
+ path.quadTo(2, 2, 1, 3);
+ path.close();
+</div>
+
+<div id="testQuadratic39">
+path.moveTo(15.5, 0);
+path.quadTo(46.5, 15.5, 46.5, 31);
+path.lineTo(15.5, 0);
+path.close();
+path.moveTo(46.5, 15.5);
+path.lineTo(0, 31);
+path.quadTo(0, 31, 15.5, 31);
+path.lineTo(46.5, 15.5);
+ path.close();
+</div>
+
+<div id="testQuadratic39a">
+path.moveTo(34.875, 19.375);
+path.lineTo(15.5, 0);
+path.quadTo(32.9687576, 8.73437881, 40.5937271, 17.4687576);
+path.lineTo(34.875, 19.375);
+path.close();
+path.moveTo(36.1666641, 20.6666679);
+path.lineTo(15.5, 31);
+path.lineTo(0, 31);
+path.lineTo(34.875, 19.375);
+path.lineTo(36.1666641, 20.6666679);
+path.close();
+path.moveTo(41.1812401, 18.15938);
+path.quadTo(46.5, 24.5796909, 46.5, 31);
+path.lineTo(36.1666641, 20.6666679);
+path.lineTo(41.1812401, 18.15938);
+path.close();
+path.moveTo(40.5937271, 17.4687576);
+path.lineTo(46.5, 15.5);
+path.lineTo(41.1812401, 18.15938);
+path.quadTo(40.8951759, 17.8140678, 40.5937271, 17.4687576);
+ path.close();
+</div>
+
</div>
<script type="text/javascript">
var testDivs = [
+ testQuadratic39,
+ testQuadratic39a,
+ testQuadratic38,
+ testQuadratic37,
+ testQuadratic36,
+ testQuadratic35,
+ testQuadratic34,
+ testQuadratic33,
+ testQuadratic32,
+ testQuadratic31,
+ testQuadratic30,
+ testQuadratic29,
testQuadratic28,
testQuadratic27,
testQuadratic26,
generated by cgit v1.2.3 (git 2.39.1) at 2024-12-19 02:45:11 +0000