17e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com/* 23284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.comSolving the Nearest Point-on-Curve Problem 37e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.comand 47e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.comA Bezier Curve-Based Root-Finder 57e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.comby Philip J. Schneider 67e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.comfrom "Graphics Gems", Academic Press, 1990 77e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com*/ 87e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com 93284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com /* point_on_curve.c */ 103284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com 117e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com#include <stdio.h> 127e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com#include <malloc.h> 137e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com#include <math.h> 147e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com#include "GraphicsGems.h" 157e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com 167e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com#define TESTMODE 177e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com 187e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com/* 197e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com * Forward declarations 207e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com */ 217e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.comPoint2 NearestPointOnCurve(); 223284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.comstatic int FindRoots(); 233284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.comstatic Point2 *ConvertToBezierForm(); 243284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.comstatic double ComputeXIntercept(); 253284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.comstatic int ControlPolygonFlatEnough(); 263284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.comstatic int CrossingCount(); 273284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.comstatic Point2 Bezier(); 283284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.comstatic Vector2 V2ScaleII(); 297e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com 303284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.comint MAXDEPTH = 64; /* Maximum depth for recursion */ 317e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com 323284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com#define EPSILON (ldexp(1.0,-MAXDEPTH-1)) /*Flatness control value */ 333284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com#define DEGREE 3 /* Cubic Bezier curve */ 343284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com#define W_DEGREE 5 /* Degree of eqn to find roots of */ 357e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com 367e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com#ifdef TESTMODE 377e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com/* 387e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com * main : 393284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com * Given a cubic Bezier curve (i.e., its control points), and some 403284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com * arbitrary point in the plane, find the point on the curve 413284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com * closest to that arbitrary point. 427e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com */ 437e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.commain() 447e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com{ 453284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com 463284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com static Point2 bezCurve[4] = { /* A cubic Bezier curve */ 473284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com { 0.0, 0.0 }, 483284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com { 1.0, 2.0 }, 493284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com { 3.0, 3.0 }, 503284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com { 4.0, 2.0 }, 517e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com }; 527e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com static Point2 arbPoint = { 3.5, 2.0 }; /*Some arbitrary point*/ 533284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com Point2 pointOnCurve; /* Nearest point on the curve */ 547e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com 557e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com /* Find the closest point */ 567e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com pointOnCurve = NearestPointOnCurve(arbPoint, bezCurve); 577e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com printf("pointOnCurve : (%4.4f, %4.4f)\n", pointOnCurve.x, 583284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com pointOnCurve.y); 597e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com} 607e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com#endif /* TESTMODE */ 617e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com 627e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com 637e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com/* 647e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com * NearestPointOnCurve : 653284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com * Compute the parameter value of the point on a Bezier 663284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com * curve segment closest to some arbtitrary, user-input point. 673284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com * Return the point on the curve at that parameter value. 687e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com * 697e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com */ 707e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.comPoint2 NearestPointOnCurve(P, V) 713284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com Point2 P; /* The user-supplied point */ 723284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com Point2 *V; /* Control points of cubic Bezier */ 737e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com{ 743284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com Point2 *w; /* Ctl pts for 5th-degree eqn */ 753284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com double t_candidate[W_DEGREE]; /* Possible roots */ 763284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com int n_solutions; /* Number of roots found */ 773284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com double t; /* Parameter value of closest pt*/ 787e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com 793284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com /* Convert problem to 5th-degree Bezier form */ 807e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com w = ConvertToBezierForm(P, V); 817e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com 827e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com /* Find all possible roots of 5th-degree equation */ 837e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com n_solutions = FindRoots(w, W_DEGREE, t_candidate, 0); 847e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com free((char *)w); 857e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com 867e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com /* Compare distances of P to all candidates, and to t=0, and t=1 */ 877e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com { 883284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com double dist, new_dist; 893284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com Point2 p; 903284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com Vector2 v; 913284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com int i; 927e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com 937e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com 943284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com /* Check distance to beginning of curve, where t = 0 */ 953284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com dist = V2SquaredLength(V2Sub(&P, &V[0], &v)); 963284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com t = 0.0; 973284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com 983284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com /* Find distances for candidate points */ 997e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com for (i = 0; i < n_solutions; i++) { 1003284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com p = Bezier(V, DEGREE, t_candidate[i], 1013284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com (Point2 *)NULL, (Point2 *)NULL); 1023284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com new_dist = V2SquaredLength(V2Sub(&P, &p, &v)); 1033284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com if (new_dist < dist) { 1043284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com dist = new_dist; 1053284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com t = t_candidate[i]; 1063284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com } 1077e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com } 1087e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com 1093284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com /* Finally, look at distance to end point, where t = 1.0 */ 1103284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com new_dist = V2SquaredLength(V2Sub(&P, &V[DEGREE], &v)); 1113284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com if (new_dist < dist) { 1123284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com dist = new_dist; 1133284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com t = 1.0; 1147e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com } 1157e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com } 1167e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com 1177e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com /* Return the point on the curve at parameter value t */ 1187e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com printf("t : %4.12f\n", t); 1197e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com return (Bezier(V, DEGREE, t, (Point2 *)NULL, (Point2 *)NULL)); 1207e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com} 1217e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com 1227e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com 1237e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com/* 1247e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com * ConvertToBezierForm : 1253284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com * Given a point and a Bezier curve, generate a 5th-degree 1263284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com * Bezier-format equation whose solution finds the point on the 1277e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com * curve nearest the user-defined point. 1287e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com */ 1297e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.comstatic Point2 *ConvertToBezierForm(P, V) 1303284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com Point2 P; /* The point to find t for */ 1313284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com Point2 *V; /* The control points */ 1327e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com{ 1333284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com int i, j, k, m, n, ub, lb; 1343284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com int row, column; /* Table indices */ 1353284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com Vector2 c[DEGREE+1]; /* V(i)'s - P */ 1363284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com Vector2 d[DEGREE]; /* V(i+1) - V(i) */ 1373284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com Point2 *w; /* Ctl pts of 5th-degree curve */ 1383284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com double cdTable[3][4]; /* Dot product of c, d */ 1393284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com static double z[3][4] = { /* Precomputed "z" for cubics */ 1403284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com {1.0, 0.6, 0.3, 0.1}, 1413284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com {0.4, 0.6, 0.6, 0.4}, 1423284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com {0.1, 0.3, 0.6, 1.0}, 1437e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com }; 1447e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com 1457e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com 1467e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com /*Determine the c's -- these are vectors created by subtracting*/ 1473284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com /* point P from each of the control points */ 1487e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com for (i = 0; i <= DEGREE; i++) { 1493284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com V2Sub(&V[i], &P, &c[i]); 1507e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com } 1517e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com /* Determine the d's -- these are vectors created by subtracting*/ 1523284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com /* each control point from the next */ 1533284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com for (i = 0; i <= DEGREE - 1; i++) { 1543284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com d[i] = V2ScaleII(V2Sub(&V[i+1], &V[i], &d[i]), 3.0); 1557e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com } 1567e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com 1577e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com /* Create the c,d table -- this is a table of dot products of the */ 1583284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com /* c's and d's */ 1597e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com for (row = 0; row <= DEGREE - 1; row++) { 1603284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com for (column = 0; column <= DEGREE; column++) { 1613284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com cdTable[row][column] = V2Dot(&d[row], &c[column]); 1623284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com } 1637e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com } 1647e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com 1657e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com /* Now, apply the z's to the dot products, on the skew diagonal*/ 1663284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com /* Also, set up the x-values, making these "points" */ 1677e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com w = (Point2 *)malloc((unsigned)(W_DEGREE+1) * sizeof(Point2)); 1687e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com for (i = 0; i <= W_DEGREE; i++) { 1693284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com w[i].y = 0.0; 1703284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com w[i].x = (double)(i) / W_DEGREE; 1717e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com } 1727e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com 1737e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com n = DEGREE; 1747e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com m = DEGREE-1; 1757e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com for (k = 0; k <= n + m; k++) { 1763284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com lb = MAX(0, k - m); 1773284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com ub = MIN(k, n); 1783284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com for (i = lb; i <= ub; i++) { 1793284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com j = k - i; 1803284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com w[i+j].y += cdTable[j][i] * z[j][i]; 1813284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com } 1827e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com } 1837e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com 1847e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com return (w); 1857e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com} 1867e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com 1877e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com 1887e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com/* 1897e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com * FindRoots : 1903284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com * Given a 5th-degree equation in Bernstein-Bezier form, find 1913284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com * all of the roots in the interval [0, 1]. Return the number 1923284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com * of roots found. 1937e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com */ 1947e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.comstatic int FindRoots(w, degree, t, depth) 1953284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com Point2 *w; /* The control points */ 1963284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com int degree; /* The degree of the polynomial */ 1973284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com double *t; /* RETURN candidate t-values */ 1983284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com int depth; /* The depth of the recursion */ 1993284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com{ 2003284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com int i; 2013284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com Point2 Left[W_DEGREE+1], /* New left and right */ 2023284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com Right[W_DEGREE+1]; /* control polygons */ 2033284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com int left_count, /* Solution count from */ 2043284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com right_count; /* children */ 2053284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com double left_t[W_DEGREE+1], /* Solutions from kids */ 2063284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com right_t[W_DEGREE+1]; 2077e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com 2087e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com switch (CrossingCount(w, degree)) { 2093284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com case 0 : { /* No solutions here */ 2103284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com return 0; 2113284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com } 2123284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com case 1 : { /* Unique solution */ 2133284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com /* Stop recursion when the tree is deep enough */ 2143284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com /* if deep enough, return 1 solution at midpoint */ 2153284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com if (depth >= MAXDEPTH) { 2163284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com t[0] = (w[0].x + w[W_DEGREE].x) / 2.0; 2173284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com return 1; 2183284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com } 2193284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com if (ControlPolygonFlatEnough(w, degree)) { 2203284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com t[0] = ComputeXIntercept(w, degree); 2213284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com return 1; 2223284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com } 2233284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com break; 2243284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com } 2257e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com} 2267e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com 2273284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com /* Otherwise, solve recursively after */ 2283284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com /* subdividing control polygon */ 2297e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com Bezier(w, degree, 0.5, Left, Right); 2307e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com left_count = FindRoots(Left, degree, left_t, depth+1); 2317e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com right_count = FindRoots(Right, degree, right_t, depth+1); 2327e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com 2337e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com 2343284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com /* Gather solutions together */ 2357e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com for (i = 0; i < left_count; i++) { 2367e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com t[i] = left_t[i]; 2377e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com } 2387e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com for (i = 0; i < right_count; i++) { 2393284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com t[i+left_count] = right_t[i]; 2407e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com } 2417e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com 2423284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com /* Send back total number of solutions */ 2437e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com return (left_count+right_count); 2447e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com} 2457e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com 2467e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com 2477e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com/* 2487e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com * CrossingCount : 2493284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com * Count the number of times a Bezier control polygon 2503284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com * crosses the 0-axis. This number is >= the number of roots. 2517e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com * 2527e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com */ 2537e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.comstatic int CrossingCount(V, degree) 2543284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com Point2 *V; /* Control pts of Bezier curve */ 2553284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com int degree; /* Degreee of Bezier curve */ 2567e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com{ 2573284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com int i; 2583284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com int n_crossings = 0; /* Number of zero-crossings */ 2593284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com int sign, old_sign; /* Sign of coefficients */ 2607e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com 2617e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com sign = old_sign = SGN(V[0].y); 2627e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com for (i = 1; i <= degree; i++) { 2633284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com sign = SGN(V[i].y); 2643284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com if (sign != old_sign) n_crossings++; 2653284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com old_sign = sign; 2667e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com } 2677e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com return n_crossings; 2687e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com} 2697e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com 2707e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com 2717e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com 2727e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com/* 2737e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com * ControlPolygonFlatEnough : 2743284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com * Check if the control polygon of a Bezier curve is flat enough 2753284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com * for recursive subdivision to bottom out. 2767e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com * 2777e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com */ 2787e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.comstatic int ControlPolygonFlatEnough(V, degree) 2793284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com Point2 *V; /* Control points */ 2803284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com int degree; /* Degree of polynomial */ 2817e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com{ 2823284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com int i; /* Index variable */ 2833284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com double *distance; /* Distances from pts to line */ 2843284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com double max_distance_above; /* maximum of these */ 2853284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com double max_distance_below; 2863284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com double error; /* Precision of root */ 2873284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com double intercept_1, 2883284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com intercept_2, 2893284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com left_intercept, 2903284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com right_intercept; 2913284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com double a, b, c; /* Coefficients of implicit */ 2923284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com /* eqn for line from V[0]-V[deg]*/ 2933284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com 2943284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com /* Find the perpendicular distance */ 2953284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com /* from each interior control point to */ 2963284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com /* line connecting V[0] and V[degree] */ 2973284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com distance = (double *)malloc((unsigned)(degree + 1) * sizeof(double)); 2987e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com { 2993284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com double abSquared; 3007e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com 3013284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com /* Derive the implicit equation for line connecting first *' 3027e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com /* and last control points */ 3033284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com a = V[0].y - V[degree].y; 3043284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com b = V[degree].x - V[0].x; 3053284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com c = V[0].x * V[degree].y - V[degree].x * V[0].y; 3067e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com 3073284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com abSquared = (a * a) + (b * b); 3087e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com 3097e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com for (i = 1; i < degree; i++) { 3103284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com /* Compute distance from each of the points to that line */ 3113284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com distance[i] = a * V[i].x + b * V[i].y + c; 3123284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com if (distance[i] > 0.0) { 3133284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com distance[i] = (distance[i] * distance[i]) / abSquared; 3143284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com } 3153284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com if (distance[i] < 0.0) { 3163284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com distance[i] = -((distance[i] * distance[i]) / abSquared); 3173284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com } 3183284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com } 3197e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com } 3207e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com 3217e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com 3223284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com /* Find the largest distance */ 3237e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com max_distance_above = 0.0; 3247e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com max_distance_below = 0.0; 3257e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com for (i = 1; i < degree; i++) { 3263284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com if (distance[i] < 0.0) { 3273284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com max_distance_below = MIN(max_distance_below, distance[i]); 3283284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com }; 3293284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com if (distance[i] > 0.0) { 3303284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com max_distance_above = MAX(max_distance_above, distance[i]); 3313284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com } 3327e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com } 3337e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com free((char *)distance); 3347e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com 3357e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com { 3363284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com double det, dInv; 3373284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com double a1, b1, c1, a2, b2, c2; 3383284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com 3393284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com /* Implicit equation for zero line */ 3403284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com a1 = 0.0; 3413284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com b1 = 1.0; 3423284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com c1 = 0.0; 3433284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com 3443284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com /* Implicit equation for "above" line */ 3453284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com a2 = a; 3463284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com b2 = b; 3473284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com c2 = c + max_distance_above; 3483284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com 3493284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com det = a1 * b2 - a2 * b1; 3503284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com dInv = 1.0/det; 3513284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com 3523284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com intercept_1 = (b1 * c2 - b2 * c1) * dInv; 3533284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com 3543284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com /* Implicit equation for "below" line */ 3553284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com a2 = a; 3563284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com b2 = b; 3573284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com c2 = c + max_distance_below; 3583284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com 3593284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com det = a1 * b2 - a2 * b1; 3603284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com dInv = 1.0/det; 3613284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com 3623284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com intercept_2 = (b1 * c2 - b2 * c1) * dInv; 3637e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com } 3647e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com 3653284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com /* Compute intercepts of bounding box */ 3667e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com left_intercept = MIN(intercept_1, intercept_2); 3677e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com right_intercept = MAX(intercept_1, intercept_2); 3687e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com 3693284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com error = 0.5 * (right_intercept-left_intercept); 3707e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com if (error < EPSILON) { 3713284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com return 1; 3727e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com } 3737e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com else { 3743284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com return 0; 3757e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com } 3767e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com} 3777e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com 3787e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com 3797e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com 3807e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com/* 3817e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com * ComputeXIntercept : 3823284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com * Compute intersection of chord from first control point to last 3833284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com * with 0-axis. 3843284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com * 3857e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com */ 3867e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com/* NOTE: "T" and "Y" do not have to be computed, and there are many useless 3877e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com * operations in the following (e.g. "0.0 - 0.0"). 3887e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com */ 3897e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.comstatic double ComputeXIntercept(V, degree) 3903284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com Point2 *V; /* Control points */ 3913284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com int degree; /* Degree of curve */ 3927e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com{ 3933284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com double XLK, YLK, XNM, YNM, XMK, YMK; 3943284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com double det, detInv; 3953284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com double S, T; 3963284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com double X, Y; 3977e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com 3987e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com XLK = 1.0 - 0.0; 3997e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com YLK = 0.0 - 0.0; 4007e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com XNM = V[degree].x - V[0].x; 4017e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com YNM = V[degree].y - V[0].y; 4027e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com XMK = V[0].x - 0.0; 4037e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com YMK = V[0].y - 0.0; 4047e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com 4057e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com det = XNM*YLK - YNM*XLK; 4067e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com detInv = 1.0/det; 4077e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com 4087e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com S = (XNM*YMK - YNM*XMK) * detInv; 4097e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com/* T = (XLK*YMK - YLK*XMK) * detInv; */ 4107e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com 4117e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com X = 0.0 + XLK * S; 4127e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com/* Y = 0.0 + YLK * S; */ 4137e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com 4147e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com return X; 4157e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com} 4167e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com 4177e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com 4187e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com/* 4193284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com * Bezier : 4203284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com * Evaluate a Bezier curve at a particular parameter value 4217e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com * Fill in control points for resulting sub-curves if "Left" and 4223284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com * "Right" are non-null. 4233284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com * 4247e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com */ 4257e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.comstatic Point2 Bezier(V, degree, t, Left, Right) 4263284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com int degree; /* Degree of bezier curve */ 4273284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com Point2 *V; /* Control pts */ 4283284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com double t; /* Parameter value */ 4293284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com Point2 *Left; /* RETURN left half ctl pts */ 4303284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com Point2 *Right; /* RETURN right half ctl pts */ 4317e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com{ 4323284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com int i, j; /* Index variables */ 4333284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com Point2 Vtemp[W_DEGREE+1][W_DEGREE+1]; 4347e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com 4357e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com 4363284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com /* Copy control points */ 4377e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com for (j =0; j <= degree; j++) { 4383284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com Vtemp[0][j] = V[j]; 4397e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com } 4407e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com 4413284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com /* Triangle computation */ 4423284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com for (i = 1; i <= degree; i++) { 4433284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com for (j =0 ; j <= degree - i; j++) { 4443284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com Vtemp[i][j].x = 4453284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com (1.0 - t) * Vtemp[i-1][j].x + t * Vtemp[i-1][j+1].x; 4463284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com Vtemp[i][j].y = 4473284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com (1.0 - t) * Vtemp[i-1][j].y + t * Vtemp[i-1][j+1].y; 4483284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com } 4497e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com } 4503284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com 4517e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com if (Left != NULL) { 4523284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com for (j = 0; j <= degree; j++) { 4533284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com Left[j] = Vtemp[j][0]; 4543284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com } 4557e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com } 4567e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com if (Right != NULL) { 4573284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com for (j = 0; j <= degree; j++) { 4583284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com Right[j] = Vtemp[degree-j][j]; 4593284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com } 4607e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com } 4617e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com 4627e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com return (Vtemp[degree][0]); 4637e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com} 4647e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com 4657e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.comstatic Vector2 V2ScaleII(v, s) 4663284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com Vector2 *v; 4673284017a60ea4fc3dc5b95838ba0c301ee1e4e8dskia.committer@gmail.com double s; 4687e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com{ 4697e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com Vector2 result; 4707e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com 4717e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com result.x = v->x * s; result.y = v->y * s; 4727e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com return (result); 4737e0274e80bf87a923cb56f7febb44be36bd8b987caryclark@google.com} 474