Main Page | Namespace List | Class Hierarchy | Class List | Directories | File List | Namespace Members | Class Members | File Members | Search for 
Kernel

pathutil.cpp File Reference

(r1785/r1282)

#include "camtypes.h"
#include "pathutil.h"
#include <math.h>
#include "macros.h"

Go to the source code of this file.

Defines

#define EPSILON   (ldexp(1.0,-MAXDEPTH-1))
#define DEGREE   3
#define W_DEGREE   5

Functions

Point2 V2ScaleII (Point2 *v, double s)
double V2SquaredLength (Point2 *a)
Point2 * V2Sub (Point2 *a, Point2 *b, Point2 *c)
double V2Dot (Point2 *a, Point2 *b)
Point2 Bezier (Point2 *V, INT32 degree, double t, Point2 *Left, Point2 *Right)
 Evaluate a Bezier curve at a particular parameter value Fill in control points for resulting sub-curves if "Left" and "Right" are non-null.
double ComputeXIntercept (Point2 *V, INT32 degree)
 Compute intersection of chord from first control point to last with 0-axis.
INT32 CrossingCount (Point2 *V, INT32 degree)
 Count the number of times a Bezier control polygon crosses the 0-axis. This number is >= the number of roots.
INT32 ControlPolygonFlatEnough (Point2 *V, INT32 degree)
 Check if the control polygon of a Bezier curve is flat enough for recursive subdivision to bottom out.
INT32 FindRoots (Point2 *w, INT32 degree, double *t, INT32 depth)
 Given a 5th-degree equation in Bernstein-Bezier form, find all of the roots in the interval [0, 1]. Return the number of roots found.
Point2 * ConvertToBezierForm (Point2 P, Point2 *V)
 Given a point and a Bezier curve, generate a 5th-degree Bezier-format equation whose solution finds the point on the curve nearest the user-defined point.

Variables

const INT32 MAXDEPTH = 64

Define Documentation

#define DEGREE   3
 

Definition at line 112 of file pathutil.cpp.

#define EPSILON   (ldexp(1.0,-MAXDEPTH-1))
 

Definition at line 111 of file pathutil.cpp.

#define W_DEGREE   5
 

Definition at line 113 of file pathutil.cpp.

Function Documentation

Point2 Bezier (  Point2 *  V,
INT32  degree,
double  t,
Point2 *  Left,
Point2 *  Right
) 
 

Evaluate a Bezier curve at a particular parameter value Fill in control points for resulting sub-curves if "Left" and "Right" are non-null.

Point2 Bezier( Point2 *V, INT32 degree, double t, Point2 *Left, Point2 *Right)

Author:
Unattributed (Xara Group Ltd) <camelotdev@xara.com>
Date:
22/08/94
Parameters:
V = Control points of cubic Bezier [INPUTS] degree = The degree of the polynomial t = Parameter value
Left = RETURN left half ctl pts (if NULL return none) [OUTPUTS] Right = RETURN right half ctl pts (if NULL return none)
Returns:
Q(t), a point on the curve

Definition at line 973 of file pathutil.cpp.

00974 {
00975     INT32   i, j;       // Index variables
00976     Point2  Vtemp[W_DEGREE+1][W_DEGREE+1];
00977 
00978     // Copy control points
00979 
00980     for (j =0; j <= degree; j++) 
00981     {
00982         Vtemp[0][j] = V[j];
00983     }
00984 
00985     // Triangle computation
00986 
00987     for (i = 1; i <= degree; i++) 
00988     {   
00989         for (j =0 ; j <= degree - i; j++) 
00990         {
00991             Vtemp[i][j].x = (1.0 - t) * Vtemp[i-1][j].x + t * Vtemp[i-1][j+1].x;
00992             Vtemp[i][j].y = (1.0 - t) * Vtemp[i-1][j].y + t * Vtemp[i-1][j+1].y;
00993         }
00994     }
00995     
00996     if (Left != NULL) 
00997     {
00998         for (j = 0; j <= degree; j++) 
00999         {
01000             Left[j]  = Vtemp[j][0];
01001         }
01002     }
01003     if (Right != NULL) 
01004     {
01005         for (j = 0; j <= degree; j++) 
01006         {
01007             Right[j] = Vtemp[degree-j][j];
01008         }
01009     }
01010 
01011     return (Vtemp[degree][0]);
01012 }

double ComputeXIntercept (  Point2 *  V,
INT32  degree
) 
 

Compute intersection of chord from first control point to last with 0-axis.

double ComputeXIntercept(Point2 *V, INT32 degree)

Author:
Date:
22/08/94
Parameters:
V = Control points of cubic Bezier [INPUTS] degree = The degree of the polynomial
[OUTPUTS] 
Returns:

Definition at line 1031 of file pathutil.cpp.

01032 {
01033     double  XLK, YLK, XNM, YNM, XMK, YMK;
01034     double  det, detInv;
01035     double  S, T;
01036     double  X, Y;
01037 
01038     XLK = 1.0 - 0.0;
01039     YLK = 0.0 - 0.0;
01040     XNM = V[degree].x - V[0].x;
01041     YNM = V[degree].y - V[0].y;
01042     XMK = V[0].x - 0.0;
01043     YMK = V[0].y - 0.0;
01044 
01045     det = XNM*YLK - YNM*XLK;
01046     detInv = 1.0/det;
01047 
01048     S = (XNM*YMK - YNM*XMK) * detInv;
01049     T = (XLK*YMK - YLK*XMK) * detInv;
01050     
01051     X = 0.0 + XLK * S;
01052     Y = 0.0 + YLK * S;
01053 
01054     return X;
01055 }

INT32 ControlPolygonFlatEnough (  Point2 *  V,
INT32  degree
) 
 

Check if the control polygon of a Bezier curve is flat enough for recursive subdivision to bottom out.

INT32 ControlPolygonFlatEnough(Point2 *V, INT32 degree)

Author:
Date:
22/08/94
Parameters:
V = Control points of cubic Bezier [INPUTS] degree = The degree of the polynomial
[OUTPUTS] 
Returns:

Definition at line 1113 of file pathutil.cpp.

01114 {
01115     INT32   i;                      // Index variable
01116     double  *distance;              // Distances from pts to line
01117     double  max_distance_above;     // maximum of these
01118     double  max_distance_below;
01119     double  error;                  // Precision of root
01120     double  intercept_1,
01121             intercept_2,
01122             left_intercept,
01123             right_intercept;
01124     double  a, b, c;                // Coefficients of implicit
01125                                     // eqn for line from V[0]-V[deg]
01126 
01127     /* Find the  perpendicular distance
01128        from each interior control point to
01129        line connecting V[0] and V[degree]   */
01130 
01131     distance = (double *)CCMalloc((unsigned)(degree + 1) * sizeof(double));
01132     {
01133     double  abSquared;
01134 
01135     // Derive the implicit equation for line connecting first
01136     // and last control points
01137 
01138     a = V[0].y - V[degree].y;
01139     b = V[degree].x - V[0].x;
01140     c = V[0].x * V[degree].y - V[degree].x * V[0].y;
01141 
01142     abSquared = (a * a) + (b * b);
01143 
01144         for (i = 1; i < degree; i++)
01145         {
01146         // Compute distance from each of the points to that line
01147             distance[i] = a * V[i].x + b * V[i].y + c;
01148             if (distance[i] > 0.0) 
01149             {
01150                 distance[i] = (distance[i] * distance[i]) / abSquared;
01151             }
01152             if (distance[i] < 0.0) 
01153             {
01154                 distance[i] = -((distance[i] * distance[i]) / abSquared);
01155             }
01156         }
01157     }
01158 
01159 
01160     // Find the largest distance
01161 
01162     max_distance_above = 0.0;
01163     max_distance_below = 0.0;
01164     for (i = 1; i < degree; i++) 
01165     {
01166         if (distance[i] < 0.0) 
01167         {
01168             max_distance_below = MIN(max_distance_below, distance[i]);
01169         };
01170         if (distance[i] > 0.0) 
01171         {
01172             max_distance_above = MAX(max_distance_above, distance[i]);
01173         }
01174     }
01175     CCFree((char *)distance);
01176 
01177     {
01178     double  det, dInv;
01179     double  a1, b1, c1, a2, b2, c2;
01180 
01181     //  Implicit equation for zero line
01182 
01183     a1 = 0.0;
01184     b1 = 1.0;
01185     c1 = 0.0;
01186 
01187     //  Implicit equation for "above" line
01188 
01189     a2 = a;
01190     b2 = b;
01191     c2 = c + max_distance_above;
01192 
01193     det = a1 * b2 - a2 * b1;
01194     dInv = 1.0/det;
01195     
01196     intercept_1 = (b1 * c2 - b2 * c1) * dInv;
01197 
01198     //  Implicit equation for "below" line
01199 
01200     a2 = a;
01201     b2 = b;
01202     c2 = c + max_distance_below;
01203     
01204     det = a1 * b2 - a2 * b1;
01205     dInv = 1.0/det;
01206     
01207     intercept_2 = (b1 * c2 - b2 * c1) * dInv;
01208     }
01209 
01210     // Compute intercepts of bounding box
01211 
01212     left_intercept = MIN(intercept_1, intercept_2);
01213     right_intercept = MAX(intercept_1, intercept_2);
01214 
01215     error = 0.5 * (right_intercept-left_intercept);    
01216     if (error < EPSILON) 
01217     {
01218         return 1;
01219     }
01220     else 
01221     {
01222         return 0;
01223     }
01224 }

Point2* ConvertToBezierForm (  Point2  P,
Point2 *  V
) 
 

Given a point and a Bezier curve, generate a 5th-degree Bezier-format equation whose solution finds the point on the curve nearest the user-defined point.

Point2 *ConvertToBezierForm( Point2 P, Point2* V )

Author:
Date:
22/08/94
Parameters:
P = The point to find t for [INPUTS] V = Control points of cubic Bezier
[OUTPUTS] 
Returns:

Definition at line 1321 of file pathutil.cpp.

01322 {
01323     INT32 i, j, k, m, n, ub, lb;    
01324     INT32 row, column;          // Table indices
01325     Vector2 c[DEGREE+1];        // V(i)'s - P
01326     Vector2 d[DEGREE];          // V(i+1) - V(i)
01327     Point2 *w;                  // Ctrl pts of 5th-degree curve
01328     double cdTable[3][4];       // Dot product of c, d
01329     static double z[3][4] = {   // Precomputed "z" for cubics
01330         {1.0, 0.6, 0.3, 0.1},
01331         {0.4, 0.6, 0.6, 0.4},
01332         {0.1, 0.3, 0.6, 1.0},
01333     };
01334 
01335 
01336     // Determine the c's -- these are vectors created by subtracting
01337     // point P from each of the control points
01338 
01339     for (i = 0; i <= DEGREE; i++) 
01340     {
01341         V2Sub(&V[i], &P, &c[i]);
01342     }
01343     
01344     // Determine the d's -- these are vectors created by subtracting
01345     // each control point from the next
01346 
01347     for (i = 0; i <= DEGREE - 1; i++) 
01348     { 
01349         d[i] = V2ScaleII(V2Sub(&V[i+1], &V[i], &d[i]), 3.0);
01350     }
01351 
01352     // Create the c,d table -- this is a table of dot products of the
01353     // c's and d's
01354     
01355     for (row = 0; row <= DEGREE - 1; row++) 
01356     {
01357         for (column = 0; column <= DEGREE; column++) 
01358         {
01359             cdTable[row][column] = V2Dot(&d[row], &c[column]);
01360         }
01361     }
01362 
01363     // Now, apply the z's to the dot products, on the skew diagonal
01364     // Also, set up the x-values, making these "points"
01365 
01366     w = (Point2 *)CCMalloc((unsigned)(W_DEGREE+1) * sizeof(Point2));
01367     for (i = 0; i <= W_DEGREE; i++) 
01368     {
01369         w[i].y = 0.0;
01370         w[i].x = (double)(i) / W_DEGREE;
01371     }
01372 
01373     n = DEGREE;
01374     m = DEGREE-1;
01375     for (k = 0; k <= n + m; k++) 
01376     {
01377         lb = MAX(0, k - m);
01378         ub = MIN(k, n);
01379         for (i = lb; i <= ub; i++) 
01380         {
01381             j = k - i;
01382             w[i+j].y += cdTable[j][i] * z[j][i];
01383         }
01384     }
01385 
01386     return (w);
01387 }

INT32 CrossingCount (  Point2 *  V,
INT32  degree
) 
 

Count the number of times a Bezier control polygon crosses the 0-axis. This number is >= the number of roots.

INT32 CrossingCount( Point2 *V, INT32 degree)

Author:
Date:
22/08/94
Parameters:
V = Control points of cubic Bezier [INPUTS] degree = The degree of the polynomial
[OUTPUTS] 
Returns:
number of crossings

Definition at line 1078 of file pathutil.cpp.

01079 {
01080     INT32 i;    
01081     INT32 n_crossings = 0;  //  Number of zero-crossings
01082     INT32   sign, old_sign;     //  Sign of coefficients
01083 
01084     sign = old_sign = SGN(V[0].y);
01085     for (i = 1; i <= degree; i++) 
01086     {
01087         sign = SGN(V[i].y);
01088         if (sign != old_sign) n_crossings++;
01089         old_sign = sign;
01090     }
01091     return n_crossings;
01092 }

INT32 FindRoots (  Point2 *  w,
INT32  degree,
double *  t,
INT32  depth
) 
 

Given a 5th-degree equation in Bernstein-Bezier form, find all of the roots in the interval [0, 1]. Return the number of roots found.

INT32 FindRoots( Point2* w, INT32 degree, double* t, INT32 depth)

Author:
Date:
22/08/94
Parameters:
w = Control points of cubic Bezier [INPUTS] degree = The degree of the polynomial depth = The depth of the recursion
t = a list of candidate t-values [OUTPUTS]
Returns:

Definition at line 1245 of file pathutil.cpp.

01246 {  
01247     INT32   i;
01248     Point2  Left[W_DEGREE+1],       // New left and right
01249             Right[W_DEGREE+1];      // control polygons
01250     INT32   left_count,             // Solution count from children
01251             right_count;
01252     double  left_t[W_DEGREE+1],     // Solutions from kids
01253             right_t[W_DEGREE+1];
01254 
01255     switch (CrossingCount(w, degree)) 
01256     {
01257         case 0 : 
01258         {   // No solutions here
01259          return 0;  
01260          break;
01261         }
01262         case 1 : 
01263         {   // Unique solution
01264             // Stop recursion when the tree is deep enough
01265             // if deep enough, return 1 solution at midpoint
01266             if (depth >= MAXDEPTH) 
01267             {
01268                 t[0] = (w[0].x + w[W_DEGREE].x) / 2.0;
01269                 return 1;
01270             }
01271             if (ControlPolygonFlatEnough(w, degree)) 
01272             {
01273                 t[0] = ComputeXIntercept(w, degree);
01274                 return 1;
01275             }
01276             break;
01277         }
01278     }
01279 
01280     // Otherwise, solve recursively after
01281     // subdividing control polygon
01282 
01283     Bezier(w, degree, 0.5, Left, Right);
01284     left_count  = FindRoots(Left,  degree, left_t, depth+1);
01285     right_count = FindRoots(Right, degree, right_t, depth+1);
01286 
01287 
01288     /* Gather solutions together    */
01289     for (i = 0; i < left_count; i++) 
01290     {
01291         t[i] = left_t[i];
01292     }
01293     for (i = 0; i < right_count; i++) 
01294     {
01295         t[i+left_count] = right_t[i];
01296     }
01297 
01298     /* Send back total number of solutions  */
01299     return (left_count+right_count);
01300 }

double V2Dot (  Point2 *  a,
Point2 *  b
) 
 

Definition at line 948 of file pathutil.cpp.

00949 {
00950   return (a->x*b->x + a->y*b->y);
00951 }

Point2 V2ScaleII (  Point2 *  v,
double  s
) 
 

Quick local vector functions to calculate various properties of vectors

Definition at line 923 of file pathutil.cpp.

00924 {
00925     Point2 result;
00926 
00927     result.x = v->x * s; 
00928     result.y = v->y * s;
00929 
00930     return (result);
00931 }

double V2SquaredLength (  Point2 *  a  ) 
 

Definition at line 934 of file pathutil.cpp.

00935 {
00936     return( a->x*a->x + a->y*a->y );
00937 }

Point2* V2Sub (  Point2 *  a,
Point2 *  b,
Point2 *  c
) 
 

Definition at line 940 of file pathutil.cpp.

00941 {
00942   c->x = a->x - b->x;
00943   c->y = a->y - b->y;
00944   return(c);
00945 }

Variable Documentation

const INT32 MAXDEPTH = 64
 

Definition at line 115 of file pathutil.cpp.

Generated on Sat Nov 10 03:49:19 2007 for Camelot by  doxygen 1.4.4