src/mesa/math/m_eval.h

   1
   2 #ifndef _M_EVAL_H
   3 #define _M_EVAL_H
   4
   5 #include "glheader.h"
   6
   7 void _math_init_eval( void );
   8
   9
  10 /*
  11  * Horner scheme for Bezier curves
  12  *
  13  * Bezier curves can be computed via a Horner scheme.
  14  * Horner is numerically less stable than the de Casteljau
  15  * algorithm, but it is faster. For curves of degree n
  16  * the complexity of Horner is O(n) and de Casteljau is O(n^2).
  17  * Since stability is not important for displaying curve
  18  * points I decided to use the Horner scheme.
  19  *
  20  * A cubic Bezier curve with control points b0, b1, b2, b3 can be
  21  * written as
  22  *
  23  *        (([3]        [3]     )     [3]       )     [3]
  24  * c(t) = (([0]*s*b0 + [1]*t*b1)*s + [2]*t^2*b2)*s + [3]*t^2*b3
  25  *
  26  *                                           [n]
  27  * where s=1-t and the binomial coefficients [i]. These can
  28  * be computed iteratively using the identity:
  29  *
  30  * [n]               [n  ]             [n]
  31  * [i] = (n-i+1)/i * [i-1]     and     [0] = 1
  32  */
  33
  34
  35 void
  36 _math_horner_bezier_curve(const GLfloat *cp, GLfloat *out, GLfloat t,
  37                           GLuint dim, GLuint order);
  38
  39
  40 /*
  41  * Tensor product Bezier surfaces
  42  *
  43  * Again the Horner scheme is used to compute a point on a
  44  * TP Bezier surface. First a control polygon for a curve
  45  * on the surface in one parameter direction is computed,
  46  * then the point on the curve for the other parameter
  47  * direction is evaluated.
  48  *
  49  * To store the curve control polygon additional storage
  50  * for max(uorder,vorder) points is needed in the
  51  * control net cn.
  52  */
  53
  54 void
  55 _math_horner_bezier_surf(GLfloat *cn, GLfloat *out, GLfloat u, GLfloat v,
  56                          GLuint dim, GLuint uorder, GLuint vorder);
  57
  58
  59 /*
  60  * The direct de Casteljau algorithm is used when a point on the
  61  * surface and the tangent directions spanning the tangent plane
  62  * should be computed (this is needed to compute normals to the
  63  * surface). In this case the de Casteljau algorithm approach is
  64  * nicer because a point and the partial derivatives can be computed
  65  * at the same time. To get the correct tangent length du and dv
  66  * must be multiplied with the (u2-u1)/uorder-1 and (v2-v1)/vorder-1.
  67  * Since only the directions are needed, this scaling step is omitted.
  68  *
  69  * De Casteljau needs additional storage for uorder*vorder
  70  * values in the control net cn.
  71  */
  72
  73 void
  74 _math_de_casteljau_surf(GLfloat *cn, GLfloat *out, GLfloat *du, GLfloat *dv,
  75                         GLfloat u, GLfloat v, GLuint dim,
  76                         GLuint uorder, GLuint vorder);
  77
  78
  79 #endif