bezlen.c

[Game.Programming].Academic - Graphics Gems (6 books source code)

/*
 *  BezierLength.c, 1994 
 *
 *  Jens Gravesen
 *  Mathematical Institute
 *  Technical University of Denmark
 *  email: [e-mail]
 *
 *  The file contain six functions length<n><x>, (with <n>=1,2,3 and
 *  <x>=a, r) which calculate the length of a Bezier curve with a
 *  given bound on the absolute error (<x>=a) or the relative error
 *  (<x>=r), using the error estimates:
 *  1) Lp-Lc.
 *  2) (Lp-Lc)^2.
 *  3) (La^1-La^0)/15.
 *
 *  It is assumed that elsewhere there are defined 
 *  1) A type: BezierCurve which contains information on a BezierCurve
 *     such as the degree and the coordinates of the control points. Eg.:
 *     typedef struct{
 *       int dim, deg; 
 *       double **Q;
 *     } BezierCurve;
 *  Functions:
 *  2) double degree(BezierCurve *b);
 *       which returns the degree of *b. It could be a macro:
 *       #define degree(b) (b)->deg
 *
 *  3) BezierCurve *DiffBezierCurve(BezierCurve *b); 
 *       which returns a pointer to a BezierCurve containing the
 *       forward differences of*b, or NULL in case of failure. 
 *
 *  4) void FreeBezierCurve(BezierCurve *b);
 *       which frees the memory occupied by *b.
 *
 *  5) double length_of_sum(BezierCurve *b);
 *       which returns the length of the sum of the control points of *b.
 *
 *  6) double sum_of_length(BezierCurve *b);
 *       which returns the sum of the length of the control points of *b.
 *
 *  7) BezierCurve *destructive_subdiv(BezierCurve *b); 
 *       The function returns a pointer to the forward difference of b
 *	 and leaves the forward difference of b in b. In case of failure 
 *	 the function returns NULL.
 *
 *  We assume all this has been declared in a header file say, BezierCode.h
 *
 */

#include <math.h>
#include "BezierCode.h"   /* arbitrary name, see above */
 
#define SQRT2      1.4142135623730951
#define ONE_OVER15 0.0666666666666667
#define ABS(x)     (x)<0?-(x):(x)

/* Forward declarations: */
static double destructive_length_1a(BezierCurve *b, double eps);
static double destructive_length_1r(BezierCurve *b, double eps);
static double destructive_length_2a(BezierCurve *b, double eps);
static double destructive_length_2r(BezierCurve *b, double eps);
static double destructive_length_3a(BezierCurve *b, double La0, double eps);
static double destructive_length_3r(BezierCurve *b, double La0, double eps); 



/*********************************************************************
 *  Public functions: 
 *********************************************************************/

/*  
 * -----------------------------------------------------------------
 * BezierLength1a
 *  
 *      Given a BezierCurve produces the arc-length of the curve with 
 *      a given bound on the absolut error.
 *      Using Lp-Lc as the error estimate.
 *  
 *  Results:
 *      The return value is normally the length of the curve, in case
 *      of failure the function returns -HUGE_VAL.
 *
 *  Side effects:
 *      None.
 *
 *------------------------------------------------------------------
 */
double BezierLength1a(b, eps)
     BezierCurve *b;            /* The Bezier Curve */
     double eps;                /* The given tolerance */
{
  BezierCurve *db;

  db = DiffBezierCurve(b);  
  if (!db) {                     /* Something is wrong, */ 
    return -HUGE_VAL;            /* signal it with negative length */
  }
  return destructive_length_1a(db, eps)/(degree(b)+1);
                                 /* destructive_length_1a works with */
				 /* the length multiplied by degree(b)+1 */
} 



/*  
 * -----------------------------------------------------------------
 * BezierLength1r
 *  
 *      Given a BezierCurve produces the arc-length of the curve with 
 *      a given bound on the relative error.
 *      Using Lp-Lc as the error estimate.
 *  
 *  Results:
 *      The return value is normally the length of the curve, in case
 *      of failure the function returns -HUGE_VAL.
 *
 *  Side effects:
 *      None.
 *
 *------------------------------------------------------------------
 */
double BezierLength1r(b, eps)
     BezierCurve *b;            /* The Bezier Curve */
     double eps;                /* The given tolerance */
{
  BezierCurve *db;

  db = DiffBezierCurve(b);  
  if (!db) {                     /* Something is wrong, */ 
    return -HUGE_VAL;            /* signal it with negative length */
  }
  eps /= (degree(b)+1);          /* destructive_length_1r works with */
				 /* the length multiplied by degree(b)+1 */
  return destructive_length_1r(db, eps)/(degree(b)+1);
} 



/*  
 * -----------------------------------------------------------------
 * BezierLength2a
 *  
 *      Given a BezierCurve produces the arc-length of the curve with 
 *      a given bound on the absolut error.
 *      Using (Lp-Lc)^2 as the error estimate.
 *  
 *  Results:
 *      The return value is normally the length of the curve, in case
 *      of failure the function returns -HUGE_VAL.
 *
 *  Side effects:
 *      None.
 *
 *------------------------------------------------------------------
 */
double BezierLength2a(b, eps)
     BezierCurve *b;            /* The Bezier Curve */
     double eps;                /* The given tolerance */
{
  BezierCurve *db;
  
  db = DiffBezierCurve(b);
  if (!db) {                   /* Something is wrong, */ 
    return -HUGE_VAL;          /* signal it with negative length */
  }
  eps = sqrt(eps);             /* (Lp-Lc)^2 < eps <=> Lp-Lc < sqrt(eps) */
  return destructive_length_2a(db, eps)/(degree(b)+1);
                               /* destructive_length_1a works with */
			       /* the length multiplied by degree(b)+1 */
} 



/*  
 * -----------------------------------------------------------------
 * BezierLength2r
 *  
 *      Given a BezierCurve produces the arc-length of the curve with 
 *      a given bound on the relative error.
 *      Using (Lp-Lc)^2 as the error estimate.
 *  
 *  Results:
 *      The return value is normally the length of the curve, in case
 *      of failure the function returns -HUGE_VAL.
 *
 *  Side effects:
 *      None.
 *
 *------------------------------------------------------------------
 */
double BezierLength2r(b, eps)
     BezierCurve *b;            /* The Bezier Curve */
     double eps;                /* The given tolerance */
{
  BezierCurve *db;
  
  db = DiffBezierCurve(b);
  if (!db) {                     /* Something is wrong, */ 
    return -HUGE_VAL;            /* signal it with negative length */
  }
  eps /= (degree(b)+1);          /* destructive_length_1r works with */
				 /* the length multiplied by degree(b)+1 */
  return destructive_length_2r(db, eps)/(degree(b)+1);
} 



/*  
 * -----------------------------------------------------------------
 * BezierLength3a
 *  
 *      Given a BezierCurve produces the arc-length of the curve with 
 *      a given bound on the absolut error.
 *      Using (La^1-La^0)/15 as the error estimate.
 *  
 *  Results:
 *      The return value is normally the length of the curve, in case
 *      of failure the function returns -HUGE_VAL.
 *
 *  Side effects:
 *      None.
 *
 *------------------------------------------------------------------
 */
double BezierLength3a(b, eps)
     BezierCurve *b;            /* The Bezier Curve */
     double eps;                /* The given tolerance */
{
  BezierCurve *db;
  double Lp, Lc, L;
  
  db = DiffBezierCurve(b);
  if (!db) {                    /* Something is wrong, */
    return -HUGE_VAL;           /* signal it with negative length */
  }
  Lp = sum_of_length(db);
  Lc = length_of_sum(db);
  L = 2*Lc + degree(db)*Lp;     /* La^0*(deg+1) of the curve*/

  eps *= 30*(degree(b)+1);      /* (La^1-La)/15 < eps  <=> */
				/* 2*(La^1-La)*(deg+1) < 30*(deg+1)*eps */

  return destructive_length_3a(db,L,eps)/(2*degree(b)+2); 
                                /* destructive_length_3 works with the */
                                /* lenght multiplied by degree(b)+1, */
				/* and return works with curves which */
				/* have twice the right size */ 
}



/*  
 * -----------------------------------------------------------------
 * BezierLength3r
 *  
 *      Given a BezierCurve produces the arc-length of the curve with 
 *      a given bound on the relative error.
 *      Using (La^1-La^0)/15 as the error estimate.
 *  
 *  Results:
 *      The return value is normally the length of the curve, in case
 *      of failure the function returns -HUGE_VAL.
 *
 *  Side effects:
 *      None.
 *
 *------------------------------------------------------------------
 */
double BezierLength3r(b, eps)
     BezierCurve *b;            /* The Bezier Curve */
     double eps;                /* The given tolerance */
{
  BezierCurve *db;
  double Lp, Lc, L;
  
  db = DiffBezierCurve(b);
  if (!db) {                /* Something is wrong, */
    return -HUGE_VAL;       /* signal it with negative length */
  }
  Lp = sum_of_length(db);
  Lc = length_of_sum(db);
  L = 2*Lc + degree(db)*Lp; /* La^0*(deg+1) of the curve */

  
 
  eps *= 15;                /* (La^1-La)/15 < eps*La^1 <=> */
                            /* (La^1-La)*(deg+1) < 15*eps*La^1*(deg+1) */

  return destructive_length_3r(db,L,eps)/(2*degree(b)+2); 
                            /* destructive_length_3 works with the */
                            /* length multiplied by degree(b)+1, and */
			    /* the size of the curves is twice the */
			    /* right size */ 
}



/*********************************************************************
 * Private functions: 
 *********************************************************************/

/*  
 * -----------------------------------------------------------------
 * destructive_length_1a
 *  
 *      Given the forward differences of a BezierCurve produces the 
 *      arc-length of the curve multiplied by (n+1), (n = the degree of
 *      original curve), with the bound (n+1)*eps on the absolut error.
 *      Using Lp-Lc as the error estimate.
 *  
 *  Results:
 *      The return value is normally the length of the curve, in case
 *      of failure the function returns -HUGE_VAL.
 *
 *  Side effects:
 *      The memory held by the input curve is freed.
 *