home *** CD-ROM | disk | FTP | other *** search
/ Collection of Hack-Phreak Scene Programs / cleanhpvac.zip / cleanhpvac / FAQSYS18.ZIP / FAQS.DAT / NURBS.TXT < prev    next >
Text File  |  1996-07-31  |  9KB  |  255 lines
  1. About Nonuniform Rational B-Splines - NURBS
  2.  
  3. a summary by Markus Altmann
  4.  
  5. NURBS are industry standard tools for the representation and design of
  6. geometry [ROGERS]. Some reasons for the use of NURBS are, that they:
  7. [PIEGL][ROGERS]
  8.  
  9.    * offer one common mathematical form for both, standard analytical
  10.      shapes (e.g. conics) and free form shapes;
  11.  
  12.    * provide the flexibility to design a large variety of shapes;
  13.  
  14.    * can be evaluated reasonably fast by numerically stable and accurate
  15.      algorithms;
  16.  
  17.    * are invariant under affine as well as perspective transformations;
  18.  
  19.    * are generalizations of non-rational B-splines and non-rational and
  20.      rational Bezier curves and surfaces.
  21.  
  22. However, one of the drawbacks NURBS have, is the need for extra storage to
  23. define traditional shapes (e.g. circles). This results from parameters in
  24. addition to the control points, but finally allow the desired flexibility
  25. for defining parametric shapes. NURBS-shapes are not only defined by
  26. control points; weights, associated with each control point are also
  27. necessary. A NURBS curve C(u), for examples, which is a vector-valued
  28. piecewise rational polynomial function, is defined as: [PIEGL]
  29.  
  30.                 sum(i = 0, n){w_i * P_i * N_i,k(u)}
  31.         C(u) = -------------------------------------,    (1)
  32.                   sum(i = 0, n){w_i * N_i,k(u)}
  33.  
  34. where
  35.  
  36.         w_i : weights
  37.         P_i : control points (vector)
  38.         N_i,k : normalized B-spline basis functions of degree k
  39.  
  40. These B-splines are defined recursively as:
  41.  
  42.                 u - t_i
  43.    N_i,k(u) = ----------- * N_i,k-1(u) +
  44.               t_i+k - t_i
  45.  
  46.                 t_i+k+1 - u
  47.               ---------------  * N_i+1,k-1(u)   (2)
  48.               t_i+k+1 - t_i+1
  49.  
  50. and
  51.  
  52.                     / 1, if t_i <= u < t_i+1
  53.         N_i,0(u) = <
  54.                     \ 0, else
  55.  
  56. where t_i are the knots forming a knot vector
  57.  
  58.         U = { t_0, t_1, ... , t_m }.
  59.  
  60. The Knot Vector
  61.  
  62. The knot vector uniquely determines the B-splines as it is obvious from
  63. (2). The relation between the number of knots (m+1), the degree (k) of
  64. N_i,k and the number of control points (n+1) is given by m = n + k + 1
  65. [PEIGL][ROGERS].
  66.  
  67. The sequence of knots in the knot vector U is assumed to be nondecreasing,
  68. i.e. t_i <= t_i+1. Each successive pair of knots represents an interval
  69. [t_i, t_i+1) for the parameter values to calculate a segment of a shape
  70. [FOLEY][WATT].
  71.  
  72. For NURBS, the relative parametric intervals (knot spans) need not be the
  73. same for all shape segments, i.e. the knot spacing is nonuniform, leading
  74. to a non-periodic knot vector of the form
  75.  
  76.    U = { a, ... , a, t_k+1, ... , t_m-k-1, b, ... , b },   (3)
  77.  
  78. where a and b are repeated with multiplicity of k+1 [ROGERS][PIEGL]. The
  79. multiplicity of a knot affects the parametric continuity at this knot
  80. [FOLEY]. Non-periodic B-splines, like NURBS, are infinitely continuously
  81. differentiable in the interior of a knot span and k-M-1 times continuously
  82. differentiable at a knot, where M is the multiplicity of the knot [ROGERS].
  83. (In contrast, a periodic knot vector U = { 0, 1, ... , n } is everywhere
  84. k-1 times continuously differentiable.) Considering the knot vector for
  85. NURBS, the end knot points (t_k, t_n+1) with multiplicity k+1 coincide with
  86. the end control points P_0, P_n.
  87.  
  88. Since the knot spacing could be nonuniform, the B-splines are no longer the
  89. same for each interval [t_i, t_i+1) and the degree of the B-Spline can vary
  90. [WATT][FOLEY]. Considering the whole range of parameter values represented
  91. by the knot vector, the different B-splines build up continuous
  92. (overlapping) blending functions N_i,k(u), as defined in (2), over this
  93. range (Fig. 1) [WATT]. These blending functions have the following
  94. properties: [WATT][ROGERS]
  95.  
  96.   1. N_i,k(u) >= 0, for all i, k, u;
  97.  
  98.   2. N_i,k(u) = 0, if u not in [t_i, t_i+k+1), meaning local support of k+1
  99.      knot spans, where N_i,k(u) is nonzero;
  100.  
  101.   3. if u in [t_i, t_i+1), the non-vanishing blending functions are
  102.      N_i-k,k(u), ..., N_i,k(u)
  103.  
  104.   4. sum(j=i-k, i){N_j,k(u)} = sum(i=0, n){N_i,k(u)} = 1, (partition of
  105.      unity)
  106.  
  107.   5. in case of multiple knots, 0/0 is deemed to be zero.
  108.  
  109. 1. and 4. together result into the convex hull, the control points build up
  110. for a shape defined by NURBS [WATT]. 2. and 3. show, that k+1 successive
  111. control points define a shape segment, and a control point is involved in
  112. k+1 neighboring shape segments. Therefore, changing a control point or
  113. weight influences just k+1 shape segments, defined over the interval given
  114. in 2.
  115.  
  116. Curve/Surface Definition
  117.  
  118. The previous definition of a NURBS-curve (1) can be rewritten using
  119. rational basis functions [PEIGL][ROGERS][WATT]
  120.  
  121.                           w_i * N_i,k(u)
  122.         R_i,k(u) = ----------------------------
  123.                    sum(j = 0, n){w_j * N_j,k(u)}
  124.  
  125. into
  126.  
  127.         C(u) = sum(i = 0, n){P_i * R_i,k(u)}.
  128.  
  129. [Image]
  130. Fig. 1: Cubic NURBS curve with associated blending functions.
  131.  
  132. A NURBS-surface is define in a similar way:
  133.  
  134.     S(u, v) = sum(i = 0, n)sum(j = 0, m) P_i,j * R_i,k, j,l(u, v) ,
  135.  
  136. where
  137.  
  138.                                  w_i,j * N_i,k(u) * N_j,l(v)
  139. R_i,k,j,l(u, v) = ---------------------------------------------------------
  140.                   sum(r = 0, n){sum(s = 0, m){w_r,s * N_r,k(u) * N_s,l(u)}}
  141.  
  142. The rational basis functions have the same properties as the blending
  143. functions [PEIGL][ROGERS]. One point to emphasize, is their invariance
  144. under affine and (even) perspective transformations. Therefore, only the
  145. control points have to be transformed to get the appropriate transformation
  146. of the NURBS shape.
  147.  
  148. Computational Algorithm
  149.  
  150. NURBS can be evaluated effectively by using homogeneous coordinates
  151. [PEIGL][ROGERS]. The following steps perform the evaluation:
  152.  
  153.   1. add one dimension to the control points (e.g. P = (x, y) -> P'(x, y,
  154.      1)) and multiply them by their corresponding weights, i.e. in 2D:
  155.      P_i(x_i, y_i) -> P_i'(w_i * x_i, w_i * y_i, w_i)
  156.  
  157.   2. calculate NURBS in homogeneous coordinates:
  158.  
  159.         C'(u) = sum(i = 0, n){P_i'(u) * N_i,k(u)}
  160.  
  161.   3. map "homogeneous" NURBS back to original coordinate system with:
  162.  
  163.                              / ( X1/W, X2/W, ... , Xn/W ), if W not = 0
  164.  map( X1, X2, ... ,Xn, W) = <
  165.                              \ ( X1, X2, ... , Xn ), if W = 0
  166.  
  167.                          sum(i = 0, n){w_i * P_i * N_i,k(u)}
  168.    C(u) = map( C'(u) ) = -----------------------------------
  169.                             sum(i = 0, n){w_i * N_i,k(u)}
  170.  
  171. For u in [t_i, t_i+1), the only existing blending functions to consider in
  172. evaluation of the curve at u are N_i-k,k(u), ..., N_i,k(u). An effective
  173. algorithm for the computation of the non-vanishing blending functions
  174. exists in [deBOOR pp. 132 - 135].
  175.  
  176. The Weights
  177.  
  178. As mentioned above, changing the weight w_i of a control point P_i affects
  179. only the range [t_i, t_i+k+1) (in case of a curve). The geometric meaning
  180. of the weights is shown as follows (Fig. 2) [PEIGL][ROGERS].
  181.  
  182. Defining the points:
  183.  
  184.                 B = C(u; w_i = 0)
  185.                 N = C(u; w_i = 1)
  186.                 B_i = C(u; w_i not = {0, 1})
  187.  
  188. [Image]
  189. Fig. 2: Geometric meaning of weights (w_3).
  190.  
  191. N and B_i can also be expressed as:
  192.  
  193.                 N = (1 - a) * B + a * P_i
  194.                 B_i = (1 - b) * B + b * P_i ,
  195.  
  196. where
  197.  
  198.                 a = R_i,k(u; w_i = 1)
  199.                 b = R_i,k(u).
  200.  
  201. The following identity is obtained from the expression of a and b:
  202.  
  203.         (1 - a)/a : (1 - b)/b = P_iN/BN : P_iB_i/BB_i = w_i ,
  204.  
  205. which is called the cross- or double ratio of the four points P_i, B, N,
  206. B_i. From these expressions, the effect of shape modification can be
  207. derived:
  208.  
  209.    * B_i sweeps out on a straight line segment
  210.  
  211.    * if w_i = 0 then P_i has no effect on shape
  212.  
  213.    * if w_i increases, so b and the curve is pulled toward P_i and pushed
  214.      away from P_j, for j not= i
  215.  
  216.    * if w_i decreases, so b and the curve is pushed away from P_i and
  217.      pulled toward P_j, for j not= i
  218.  
  219.    * if w_i -> infinity then b -> 1 and B_i -> P_i, if u in [t_i, t_i+k+1)
  220.  
  221. ---------------------------------------------------------------------------
  222. References:
  223.  
  224. [deBOOR]
  225.      C. deBoor,
  226.      "A Practical Guide to Splines",
  227.      1978, New York, Springer-Verlag
  228.  
  229. [FOLEY]
  230.      James D. Foley et al.,
  231.      "Introduction to Computer Graphics",
  232.      1994, Addision-Wesley
  233.  
  234. [PEIGL]
  235.      Les Piegl
  236.      "On NURBS: A Survey",
  237.      Jan 01, 1991, IEEE Computer Graphics and Applications, Vol. 11, No. 1,
  238.      pp. 55 - 71
  239.  
  240. [ROGERS]
  241.      David F. Rogers, Rae A. Earnshaw (editors),
  242.      "State of the Art in Computer Graphics - Visualization and Modeling",
  243.      1991, New York, Springer-Verlag, pp. 225 - 269
  244.  
  245. [WATT]
  246.      Alan Watt, Mark Watt,
  247.      "Advanced Animation and Rendering Techniques",
  248.      1992, New York, AMC press, Addision-Wesley
  249.  
  250.      ----------------------------------------------------------------------
  251.       [CS563]   Go to the CS563 Home Page
  252.  
  253.      ----------------------------------------------------------------------
  254.      Markus Altmann / madwpi@cs.wpi.edu
  255.