11 .2
`
`Parametric Cubic Curves
`
`505
`
`splinu (8REW77), are useful for this situation. One member of this spline family is able to
`interpolate the points P 1 to P,. _1 from the sequence of points P0 toP •. In addition, the
`tangent vector at point P; is parallel to the line connecting points P;_ 1 and P;. 1, as shown in
`Fig. 11.32. However, these splines do not posess the convex-hull property. The natural
`(interpolating) splines also interpolate points, but without the local control afforded by the
`Catmuii- Rom splines.
`Designating MeR as the Catrnull-Rom basis matrix and using the same geometry
`matrix Ga.. of Eq. ( I 1.32) as was used for 8 -splines, the representation is
`
`-3
`- 1
`3
`-5 4
`2
`I
`Q'(t) = T · MeR · Ga.. = 2 · T · -I O
`I
`[
`0
`2
`0
`
`I ] [P;-al
`O p;_~ .
`- 1 p._
`P1
`
`0
`
`(I 1.47)
`
`A method for rapidly displaying Catmuii- Rom curve.~ is given in [BARR88b].
`Another spline is the uniformly shaped {J-spline [BARS88; 8ART87}, which has 1~
`additional parameters, /31 and f3r, to provide further control over shape. It uses the same
`geometry matrix Gs.; as the 8-spline, and has the convex hull property. The {J-spline basis
`matrix M1 is
`
`-2(/3r + /3l + 13. + I) 2
`3(f3r + 2/3~)
`0
`0
`6f3t
`2
`0
`
`-2{3~ 2(/3t + /3~ + /3~ + 13.>
`- 3(/3t + 2{3f + 2{3'{)
`I 6M
`M =-
`" s - 6{3~
`6<Pr - P.>
`f3r + 4{{3f + 13.>
`2{3~
`s = f3r + 2/3: + 4/3f + 4/3. + 2.
`( I 1.48)
`The first parameter, {3., is called the bias parameter; the second parameter, f3r, is called
`the tension parameter. If /31 = I and f3r = 0, M, reduces to Ms. (Eq. (I 1.34)) for 8-splines.
`As /31 is increased beyond I, the spline is " biased," or influenced more, by the tangent
`vector on the parameter-increasing side of the points, as shown in Fig. 11 .33. For values of
`/31 less than I, the bias is in the other direction. As the tension parameter f3t increases, the
`spline is pulled closer to the lines connecting the control points, as seen in Fig. 11.34.
`
`p '•
`
`Fig. 11 .32 A Catmuii-Rom spline. The points are interpolated by the spline. which
`passes through each point in a direction parallel to the line between the adjacent points.
`The straight line segments indicate these directions.
`
`0538
`
`

`
`506
`
`Representing Curves and Surfaces
`
`y(l)
`
`•
`
`•
`
`•
`
`•
`
`•
`
`1\
`
`•
`JJ,. 1
`
`•
`
`•
`
`•
`
`J\
`
`•
`
`(J, = 2
`
`•
`
`•
`
`•
`
`•
`
`•
`
`•
`
`v
`
`•
`•
`•
`•
`•
`fJ, = 8
`fJ, . 4
`tJ, ·-
`L - - - - - -- - - - - - - - -- - - - - - - -- *l
`Fig. 11 .33 Effect on a uniformly shaped ,8-spline of increasing the bias parameter {J,
`from 1 to infinity.
`
`y(t)
`
`•
`
`•
`
`•
`
`•
`
`1\
`
`•
`
`•
`JJ2. 0
`•
`
`•
`
`•
`
`•
`
`1\
`
`•
`
`•
`{\= 4
`
`•
`
`•
`
`•
`•
`{\ = 16
`~--
`' - - - - - - -- - - - - - - - -- *)
`
`Fig. 11 .34 Effect on a uniformly shaped ,8-spline of increasing the tension parameter
`fJ.; from 0 to infinity.
`
`0539
`
`

`
`11 .2
`
`Parametric Cubic Curves
`
`507
`
`These ,8-splines are called uniformly slulped because {31 and f3z apply uniformly, over
`all curve segments. This global effect of {31 and f3z violates the spirit of local control.
`Continuously shaped {3-sp/ines and discretely slulped {3 splines associate distinct values of {31
`and f3z with each control point, providing a local, rather than a global, effect [BARS83;
`BART87].
`Although ,8-splines provide more shape generality than do 8-splines, they are (fl but
`only CJ continuous at the join points. This is not a drawback in geometric modeling, but can
`introduce a velocity discontinuity into an animation's motion path. In the special case
`{31 = I, the ,8-splines are C1 continuous.
`A variation on the Hermite form useful for controlling motion paths in animation was
`developed by Kochanek and Bartels [KOCH84). The tangent vector R1 at point P1 is
`11 = (I - ai)(l + bi)(l + c1)(P· _ p . ) +(I - a;)(l - b;)(l - ci)(P
`_ p .\
`2
`2
`lh
`" 1
`t -1
`(11.49)
`
`(+1
`
`I
`
`and the tangent vector RH 1 at point P;. 1 is
`R· + (I - a;. 1)(1 + b1• 1)( 1 - ci+ 1)(P,- _ P,-_ ,)
`2
`t+l
`
`+ (I - a1 . . )(1 - b1• 1X I + c1• 1)(P
`2
`i+l
`
`_ P;)
`. .
`
`(11.50)
`
`See Exercise 11.16 for how to find the basis matrix MKB.
`The parameters a1, b1, and c1 control different aspects of the path in the vicinity of point
`P1: a1 controls how sharply the curve bends, b1 is comparable to f3 .. the bias of ,8-splines,
`and c1 controls continuity at P1• This last parameter is used to model the rapid change in
`direction of an object that bounces off another object.
`
`11 .2 . 7 Subdividing Curves
`
`Suppose you have just created a connected series of curve segments to approximate a shape
`you are designing. You manipulate the control points, but you cannot quite get the shape
`you want. Probably, there are not enough control points to achieve the desired effect. There
`are two ways to increase the number of control points. One is the process of degree
`elevation: The degree of the splines is increased from 3 to 4 or more. Th.is adjustment is
`sometimes necessary, especially if higher orders of continuity are needed, but is generally
`undesirable because of the additional inflection points allowed in a single curve and the
`additional computational time needed to evaluate the curve. In any case, the topic is beyond
`the scope of our discussion; for more details, see [FARI86).
`The second, more useful way to increase the number of control points is to subdivide
`one or more of the curve segments into two segments. For instance, a Bezier curve segment
`with its four control points can be subdivided into two segments with a total of seven control
`points (the two new segments share a common point). The two new segments exactly match
`the one original segment until any of the control points are actually moved; then, one or
`both of the new segments no longer matches the original. For nonuniform 8 -splines, a more
`general process know as refinement can be used to add an arbitrary number of control points
`
`0540
`
`

`
`508
`
`Representing Curves and Surfaces
`
`10 a curve. Another reason for subdividing is to display a curve or surface. We elaborate on
`this in Section 11 .2.9, where we discuss tests for stopping the subdivision.
`Given a .Bezier curve Q(t) defined by points P1, P1, P1, and P4, we want to find a left
`curve defined by points L~> Lt. L,, and L4 , and a right curve defined by points R~> R1, R,. and
`R4, such that the left curve is coincident with Q on the interval 0 :s t < tand the right curve
`is coincident with Q on the interval t :s t < I. The subdivision can be accomplished using a
`geometric construction technique developed by de Casteljau (DECA59] to evaluate a .Bezier
`curve for any value oft. The point on the curve for a parameter value oft is found by
`drawing the construction line LaH so that it divides P 1P1 and P,P1 in the ratio of t:(l -
`t),
`HR1 so that it similarly divides P,P1 and P,P4, and 4Rt 10 likewise divide LaH and HR1• The
`point L4 (which is also R1) divides L,R1 by the same ratio and gives the point Q(t). Figure
`11 .35 shows the construction for 1 = f, the case of interest.
`All the points are easy to compute with an add and shift to divide by 2:
`La = (P1 + P1)/2, H "' (P1 + Pr)/2, La = (l..t + H)/2, R3 = (P3 + PJI2,
`R1 = (H + Ra)/2, L4 = R1 = (L, + R,)/2.
`( ll.S I)
`These results can be reorganized into matrix form , so as to give the left .Bezier division
`matrix Of; and the right .Bezier division matrix ~ These matrices can be used to find the
`geometry matrices G{; of points for the left Bezier curve and ~ for the right Bezier curve:
`
`~ = ~ . G, " k[~ ~ l m~J
`! ~ m~J
`
`I
`I 0
`~ = ~ . Gs = 8 0
`[
`0
`Notice that each of the new control points L; and R1 is a weighted sum of the points P1,
`with the weights positive and summing to I. Thus, each of the new control points is in the
`convex hull of the set of original control points. Therefore, the new control points are no
`fanher from the curve Q(t) than are the original control points, and in general are closer
`
`( 11.52)
`
`P • R
`• •
`Fig. 11 .35 The Bezier curve defined by the points P, is divided at t = t into a left
`curve defined by the points L, and a right curve defined by the points R,.
`
`0541
`
`

`
`11 .2
`
`•
`Parametric Cubic Curves
`
`50 9
`
`!han the original points. This variation-diminishing property is true of all splines !hat have
`the convct-hull property. Also notice the symmetry between Dfi and ~. a consequence of
`the symmetry in the geometrical construction.
`Dividing the Bezier curve att =torten gives the interactive user !he control needed,
`but it might be better to allow the user to indicate a point on the curve at which a split is to
`occur. Given such a point, it is easy to find !he approximate corresponding value of 1. The
`splitting then proceeds as described previously, except that the construction Lines are
`divided in the t:(l -
`t) ratio (see Exercise 11.22).
`The corresponding matrixes Dfj, and Dt for B-spline subdivision are
`[' 4 0
`'] [P,_,l
`I 6
`I 0 P;-t
`I
`G~ = Dfi. · Gu., = S ~ 4 4 0 P,_ 1
`6
`I
`P,
`I J•-•]
`[' 6
`
`R
`
`-
`
`I 0 4 4 0 P,_,
`Gu., - ~ G~~~; - g ~ I 6
`- -
`I P,_ 1
`0 4 4
`P1
`
`'
`
`•
`
`(11.53)
`
`•
`
`Careful examina.ion of these tv.u equations shows !hat the four control points of G0.,
`are replaced by a total of five new control points, shared between GIJ., and G~. However,
`the spline segments on either s.ide of !he one being divided are still defined by some of the
`control points of Gu.,. Thus, changes to any of the five new control points or four old control
`points cause the 8 -spline to be no longer connected. This problem is avoided with
`nonuniform 8 -splines.
`Subdividing nonuniform 8-splines is not as is simple as specifying two splitting
`matrices, because there is no explicit basis matrix: The basis is defined recursively. The
`basic approach is to add knots to the knot sequence. Given a nonuniform 8-spline defined
`by !he control points P0, • •• , P. and a value of 1 = t' at which to add a knol (and hence to
`add a control point), we want to find !he new control points Q0, ••• , Q.H !hat define the
`same curve. (The value t' might be determined via user interaction-see Exercise 11 .21.)
`The value t' satisfies 1; < t' < 'i•l· 8ohm [86HM80] has shown that the new control points
`are given by
`
`Qo = Po
`Q1 = (I - a1)Pi-l + a;P;,
`Q •• l = P.
`
`I :s i :s n
`
`( 11 .54)
`
`where a, is given by:
`
`a, = I .
`
`t' -
`a,=
`I; .a
`a1 = 0,
`
`I ·
`• '
`t,
`
`l:Si:Sj-3
`
`j - 2:Si:Sj
`
`(division by zero is zero)
`
`( 11.55)
`
`j + I :s i :s " ·
`
`0542
`
`

`
`61 0
`
`Representing Curves and Surfaces
`
`This algorithm is a special case of the more general Oslo algorithm [COHE80], which
`inserts any number of knotS into a 8 -spline in a single set of oomputations. lf more than a
`few knotS are being inserted at once, the Oslo algorithm is more efficient than is the BOhm
`algorithm.
`AsanexampleofBOhmsubdivision,considertheknotsequence(O, O,O,O,I,I,I, 1),
`the four x coordinates of the control point vector (5.0, 8.0. 9.0, 6.0), and a new knot at
`1 = 0.5 (i.e., n = 3, j = 3). The a1 values defined by Eq. ( 11 .55) are (0.5, 0.5, 0.5).
`Applying Eq. ( 11 .54) we find that the x coordinates of the new Q; control pointS are (5.0,
`6.5. 8.5, 7.5, 6.0).
`Notice that adding a knot causes two old control pointS to be replaced by three new
`oontrol pointS. Furthermore, segments adjacent to the subdivided segment are defined only
`in terms of the new control points. Contrast this to the less attractive case of uniform-S(cid:173)
`spline subdivision, in which four old control pointS are replaced by five new ones and
`adjacent segments are defined with the old control points, which are no longer used for the
`two new segments.
`Hierarchical 8-spline refinement is another way to gain finer control over the shape of a
`cuM: [FORS89]. Additional control points are added to local regions of a cuM:, and a
`hierarchical data structure is built relating the new control points to the original points. Use
`of a hierarchy allows further additional refinement. Storing the hierarchy rather than
`replacing the old control points with the larger number of new oontrol points means that the
`original control points can continue to be used for coarse overall shaping of the curve, while
`at the same time the new control points can be used for oontrol of details.
`
`11 .2 .8 Conversion Between Representations
`
`It is often necessary to convert from one representation to another. That is, given a curve
`represented by geometry vector C1 and basis matrix M1, we want to find the equivalent
`geometry matrix C2 for basis matrix M2 such that the two curves are identical: T · M2 • C2 =
`T · M1 • C1• This equality can be rewritten as M1 • C2 = M1 • C1• Solving for C2• the
`unknown geometry matrix, we find
`Mi 1 • M2 • G2 = M2- 1 • M1 • C1, or C2 = Mi 1 • M1 • C1 = M1.2 • C1• (11.56)
`That is, the matrix that converts a known geometry vector for representation I into the
`geometry vector for representation 2 is just Mu = M2- 1 • M 1•
`As an example, in converting from 8-spline to Shier form , the matrix MBt.8 is
`
`The inverse is
`
`Mko • Mi ' M• • ~[1 ~ j !]
`M.., • MO' M, • [ ~ -7 2 ~]
`
`- I
`2
`-I 2
`-7
`2
`
`( I 1 57)
`
`( 11 .58)
`
`0543
`
`

`
`11 .2
`
`Paramet ric Cubic Curves
`
`511
`
`Nonuniform B-splines have no explicit basis matrix; recall that a nonuniform B-spline
`over four points with a knot sequence of (0, 0, 0, 0, I, I, I, I) is just a B~zier curve. Thus,
`a way to convert a nonuniform B-spline to any of the other forms is first to convert to B&ier
`form by adding multiple knots using either the Biihm or Oslo algorithms mentioned in
`Section II. 2. 7, to make all knots have multiplicity 4. Then the B~zier form can be
`converted to any of the other forms that have basi.s matrices.
`
`11 .2 .9 Drawing Curves
`
`There are two basic ways to draw a parametric cubic. The first is by iterative evaluation of
`.x(1), y(1), and z(l) for incrementally spaced values of 1, plotting lines between successive
`points. The second is by recursive subdivision that stops when the control points get
`suffic.iently close to the curve itself.
`In the introduction to Section 11.2, simple brute-force iterative evaluation display was
`described, where the polynomials were evaluated at successive values of 1 using Horner's
`rule. The cost was nine multiplies and I 0 additions per 30 point. A much more efficient
`way repeatedly to evaluate a cubic polynomial is with forward differences. The forward
`difference 11/(1) of a function /(I) is
`11/(1) = /(1 + 8) - /(1), 8 > 0,
`
`(11.59)
`
`which can be rewritten as
`
`(1 1.60)
`
`(11.61)
`
`( II. 62)
`
`/(1 + 8) = /(1) + 11/(1).
`Rewriting Eq. (11 .60) in iterative terms, we have
`fu 1 =f. + 11/,,
`where f is evaluated at equal intervals of size 8, so that 1, = n8 and f. = /(IJ.
`For a third-degree polynomial,
`/(1) = a13 + b12 + Cl + d = T · C,
`so the forward difference is
`(at3 + b12 + c1 + d) ( 11.63)
`11/(1) = a(1 + 8}3 + b(1 + 8)2 + c(1 + 8) + d -
`= 3al28 + t(3a82 + 2M) + a83 + M 2 + c8.
`Thus, 11/(1) is a second-degree polynomial. This is unfortunate, because evaluating Eq.
`( 11.61 ) still involves evaluating 11/(1), plus ao addition. But forward differences can be
`applied to 11/(1) to s implify its evaluation. From Eq. (11.6 1), we write
`11o/(1) = 11(11/(1)) = l1f(1 + 6) - 11/(1).
`Applying tbis to Eq. (11.63) gives
`112j'(1) = 6a821 + 6a83 + 2b82•
`This is now a first-degree equation in 1. Rewriting ( 11.64) and using the index n, we obtain
`11'lJ. = l1f. + 1 -
`
`( 11.64)
`
`( 11.65)
`
`( 11.66)
`
`l1f..
`
`0544
`
`

`
`512
`
`Representing Curves and Surfaces
`
`Reorganizing and replacing 11 by 11 -
`I yields
`tJ.f. = tJ.f. - 1 + tJ."f. - 1·
`(11.67)
`Now, to evaluate tJ.f. for use in Eq. (I 1.61), we evaluate tJ."f.-1 and add it to tJ.f. _1.
`Because tJ."f. _1 is linear in 1, this is less work than is evaluating tJ.f. directly from the
`second-degree polynomial Eq. (II . 63).
`The process is repeated once more to avoid direct evaluation of Eq. ( 11.65) to find
`tJ."f(t):
`
`tJ.":f(t) = 6ao1.
`tJ."f(r) = tJ.(tJ."f(r)) = tJ."f(r + 8) -
`The third forward difference is a constant, so further forward differences are not needed.
`Rewriting Eq. (11.68) with n, and with tJ."f. as a constant yields
`
`( 11.68)
`
`( 11.69)
`
`One further rewrite, replacing 11 with 11 - 2, completes the development:
`tJ."f.- 1 = tJ.":f. - 2 + 6ao3.
`This result can be used in Eq. ( 11.67) to calculate A/., which is then used in Eq. (11 .61) to
`find/.+ 1•
`To use the forward differences in an algorithm that iterates from 11 = 0 to 110 = I, we
`compute the initial conditions with Eqs. ( 11.62), (11.63), (11.65), and ( 11.68) fort= 0.
`They are
`
`(11.70)
`
`fo = d, tJ.fo = ao3 + b02 +co, tJ."fo = 6al>3 +2M2, tJ.% = 6ao3.
`These initial condition calculations can be done by direct evaluation of the four equations.
`Note that, however, if we define the vector of initial differences as D, then
`
`( 11.71 )
`
`D = [£~] = [k 2~2 g i] [:].
`
`( 11 .72)
`
`603 0
`tJ.%
`0 0
`d
`Rewriting, with the 4 x 4 matrix represented as £(8), yields D = E(li)C. Because we are
`dealing with three functions, x(t), y(t), and z(t), there are three corresponding setS of initial
`conditions, D. = E(li)C •• D, = E(li)C,. and D, = E(li)C,.
`Based on this derivation, the algorithm for displaying a parametric cubic curve is given
`in Fig. 11.36. This procedure needs just nine additions and no multiplies per 3D point, and
`just a few adds and multiplies are used for initialization I This is considerably better than the
`I 0 additions alld nine multiplies needed for the simple brute-force iterative evaluation using
`Homer's rule. Notice, however, that error accumulation can be an issue with this algorithm,
`and sufficient fractional precision must be carried to avoid it. For instance, if n = 64 and
`integer arithmetic is used, then 16 bitS of fractional precision are needed; if 11 = 256, 22 bits
`are needed [BART87).
`Recursive subdivision is the second way to display a curve. Subdivision stops
`adaptively, when the curve segment in question is flat enough to be approximated by a line.
`
`0545
`
`

`
`11 .2
`
`Parametric Cubic Curves
`
`613
`
`void DrawCurveFwdDif (
`I• number of steps used to draw a curve • I
`lot n,
`double x, double ru, double t.?x, double tlx,
`I• initial values for .t{l) polynomial at I = 0, computed as Dr = £(6)Cz. •I
`double y, double fly, double A1y, double !l3y,
`I• initial values for y(l) polynomial 011 = 0, computed as D• = £(6)C •. •I
`double z, double /lz, double ll2t, double A3z
`I • initial values for z(t) polynomial at I = 0, computed as D. = £(6)C •. •I
`I • The step size 6 used to calculate Dr . D •• and D. is 1/rr . •I
`
`)
`
`{
`
`}
`
`int i:
`
`I• Go to stan of curve •I
`
`MoveAbs3 (x, y, z);
`ror (i = 0; 1 < n; i++) {
`x += ru; 4K + =A1.r; A2x += A3x:
`y += fly; Ay += A2y; A2y += A3y;
`llz += A2z; A1t += A3z;
`t += l!.z;
`UnMbsJ (x, y, z);
`I• Draw a shon line segment • I
`
`}
`I• DrawCurveFwdDif • I
`
`Fig. 11 .36 Procedure to display a parametric curve using forward differences.
`
`Details vary for each type of curve, because the subdivision process is slightly different for
`each curve, as is the flatness test. The general algorithm is given in Fig. I 1.37.
`The Bezier representation is particularly appropriate for recursive subdivision display.
`Subdivision is fast, requiring only six shiftS and six adds in Eq. (I 1.51). The test for
`"straightness" of a Bezier curve segment is also simple, being based on the convex hull
`formed by the four control pointS; see Fig. 11.38. lf the larger of distances t4 and d1 is less
`than some threshold E, then the curve is approximated by a straight line drawn between the
`endpointS of the curve segment. For the Bezier form, the endpointS are P1 and P., the first
`and last control points. Were some other form used, the flatness test would be more
`complicated and the endpointS might have to be calculated. Thus, conversion to B~zier
`form is appropriate for display by recursive subdivision.
`More detail on recursive-subdivision display can be found in fBARS85; BARS87;
`LANE80]. If the subdivision is done with integer arithmetic, less fractional precision is
`
`void DrawCurveRecSub (cun.oe, ')
`{
`
`I• Test control points to be witltin t of a line •I
`
`If (Straigbt (curve, f))
`Drawline (curve);
`else {
`SubdivideCurve (cr~rve, lefiCurve, rightCurve);
`OrawCurveRecSub (lefiCt~rve, t);
`DrawC\lrveRecSub (righ1Curve, t):
`
`}
`I • DrawCurveRecSub •I
`}
`Fig. 11 .37 Procedure to display a curve by recursive subdivision. Straight is a
`procedure that returns true if the curve is sufficiently flat.
`
`0546
`
`

`
`514
`
`Representing Curves and Surfaces
`
`Fig. 11 .38 Flatness test for a curve segment. If dl and d3 are both less than some£, the
`segment is declared to be flat and is approximated by the line segment P,P,.
`
`needed than in the forward difference method. If a.t most eight levels of recursion arc needed
`(a reasonable expectation), only 3 bits of fractional precision are necessary; if 16, 4 bi.ts.
`Recursive subdivision is attractive because it avoids unnecessary computation, whereas
`forward differencing uses a fixed subdivision. The forward-difference step size 6 must be
`small enough that the portion of the curve with the smallest radius of curvature is
`approximated satisfactorily. For nearly straight portions of the curve, a much larger step
`size would be acceptable. LLANE80a] gives a method for calculating the step size 6 to
`obtain a given maximum deviation from the true curve. On the other hand , recursive
`subdivision takes time to test for flatness. An alternative is to do recursive subdivision down
`to a fixed depth, avoiding the flatness test at the cost of some extra subdivision (see Exercise
`11.30).
`A hybrid approach, adaptive forward differencing [LIEN87; SHAN87; SHAN89], uses
`the best features of both the forward differencing and subdivision methods. The basic
`strategy is forward differencing, but an adaptive step size is used. Computationally efficient
`methods to double or halve the step size are used to keep it close to I pixel. This means that
`essentially no straight-line approximations arc used bet\veen computed points.
`
`11 .2 .1 0 Comparison of the Cubic Curves
`
`The different types of parametric cubic curves can be compared by several different criteria,
`such as ease of interactive manipulation, degree of continuity at join points, generality, and
`speed of various computations using the representations. Of course, it is not necessary to
`choose a single representation, since it is possible to convert between all representations, as
`discussed in Section 11.2.8. For instance, nonuniform rational B-splines can be used as an
`internal representation, while the user might interactively manipulate Bezier control points
`or Hem1ite control points and tangent vectors. Some interactive graphics editors provide the
`user with Hermite curves while representing them internally in the B~zier form supported
`by PostScript [ADOB85a].ln general, the user of an interactive CAD system may be given
`several choices, such as Hermite, Bezier, uniform B-splines, and nonuniform B-splines.
`The nonuniform rational B-spline representation is likely to be used inte.rally, because it is
`the most general.
`Table 11 .2 compares most of the curve forms mentioned in this section. Ease of
`interactive manipulation is not included explicitly in the table, because the latter is quite
`
`0547
`
`

`
`TABLE 11 .2 COMPARISON OF SEVEN DIFFERENT FORMS OF PARAMETRIC CUBIC CURVES
`
`... ...
`
`N
`
`Hennite
`NIA
`
`Uniform
`~z.ier B·s21ine
`Yes
`Yes
`
`Unifonnly
`shaped
`P·spline
`Yes
`
`Nonuniform
`B·s21inc
`Yes
`
`Convex bull
`defined by
`control points
`Interpolates
`some control
`points
`Interpolates
`all control
`points
`Ease of
`subdivision
`Continuities
`inherent in
`repm;eotatioo
`Continuities
`easily achieved
`Number of
`parameters
`controlling
`a curve segment
`•ExcqK for special case di.aiSSCd in Section 11.2.
`tFour of 1be parameletS are local so each sqment. 1wo are globalro the enlire CUM:.
`
`Yes
`
`Yes
`
`No
`
`Yes
`
`No
`
`No
`
`Good
`
`Best
`
`Avg
`
`~
`(j
`
`c•
`G'
`4
`
`~
`G'
`
`C'
`G'
`4
`
`C'
`G'
`
`C'
`(JI•
`
`4
`
`No
`
`No
`
`Avg
`
`~
`G'
`c•
`(JI•
`6t
`
`No
`
`No
`
`High
`
`C'
`G'
`
`C'
`G'"
`s
`
`Catmull- Rom Kochanek- Bartels
`No
`No
`
`Yes
`
`Yes
`
`Avg
`
`c•
`G'
`c•
`G'
`4
`
`Yes
`
`Yes
`
`Avg
`
`c•
`G'
`c•
`G'
`7
`
`.,
`• il
`3
`!
`...
`:::1 •
`(')
`c:
`2:
`...
`
`(')
`
`c: < • •
`111 ...
`
`111
`
`0548
`
`

`
`51 6
`
`Representi ng Curves and Surfaces
`
`application specific. " Number of parameters controlling a curve segment" is the four
`geometrical constraints plus other parameters, such as knot spacing for nonuniform splines,
`/31 and f3.t. for /3-splines, or a, b, or c for the Kochanek-Bartels case. "Continuity easily
`achieved" refers to constraints such as forcing control points to be collinear to allow G1
`continuity. Because C" continuity is more restrictive than G", any form that can attain C"
`can by definition also attain at least c·.
`When only geometric continuity is required, as is often the case for CAD, the choice is
`narrowed to the various types of splines, all of which can achieve both G1 and G2 continuity.
`Of the three types of splines in the table, uniform B-splines are the most limiting. The
`possibility of multiple knots afforded by nonuniform B-splines gives more shape control to
`the user, as does the use of the /31 and f3.z shape parameters of the /3-splines. Of course, a
`good user interface that allows the user to exploit this power easily is important.
`To interpolate the digitized points of a camera path or shape contour, CatmuU-Rom or
`Kochanek-Bartels splines are preferable. When a combination of interpolation and tangent
`vector control is desired, the Bezier or Hermite form is best.
`It is customary to provide the user with the ability to drag control points or tangent
`vectors interactively, continually displaying the updated spline. Figure 11.23 shows such a
`sequence forB-splines. One of the disadvantages of B-splines in some applications is that
`the control points are not on the spli ne itself. It is possible, however, not to display the
`control points, allowing the user instead to interact with the knots (which must be marked
`so they can be selected). When the user selects a knot and moves it by some(~. ~y), the
`control point weighted most heavily in determining the position of the join point is also
`moved by(~. ~y). The join does not move the full(~. ~y), because it is a weighted sum
`of several control points, only one of which was moved. Therefore, the cursor is
`repositioned on the join. This process is repeated in a loop until the user stops draggi11g.
`
`11 .3 PARAMETRIC BICUBIC SURFACES
`
`Pardmetric bicubic surfaces are a generalization of parametric cubic curves. Recall the
`general form of the parametric cubic curve Q(t) = T · M · G, where G, the geometry vector,
`is a constant. First, for notational convenience, we replace t with s, giving Q(s) = S · M · G.
`If we now allow the points in G to vary in 3D along some path that is parameterized on t , we
`have
`
`Q(s t) = S · M · G(t) = S · M · [g:~~~l
`
`'
`
`G3(t) ·
`G,(t)
`
`(I I. 73)
`
`Now. for a fixed t1, Q(s, t1) is a curve because G(t1) is constant. Allowing t to take on some
`t1 is very small, Q(s, 1) is a slightly different curve.
`new value-say, tr-where tz -
`Repeating this for arbitrarily many other Vdlues of t2 between 0 and I , an entire family of
`curves is defined, each arbirrarily close to another curve. The set of all such curves defines a
`surface. Lf the G/.t) are themselves cubics, the surface is said to be a parametric bicubic
`surface.
`
`0549
`
`

`
`11 .3
`
`Parametric Bicubic Surfaces
`
`5 17
`
`Continuing with the case that the G,(l) are cubics, each can be represented as G/.1) =
`T · M · G1, where G; = 16n l c g11 g,.]T (the G and 1 are used to distinguish from the G
`used for the curve). Hence, I n is the first element of the geometry vector for curve G/.1), and
`so on.
`Now let us transpose the equation G;(l) = T · M · G1, using the identity (A · 8 · C? =
`cr. sr. AT. The result is G,(l) = G,T. MT. rr = [gn l f2
`l i3 1 .. 1 . MT. rr. If we now
`substitute this result in Eq. ( 11.73) for each of the four points, we ha\'e
`
`l u I tt g., ' ••]
`Q(s, 1) = S . M . l u
`l u g,. . M1 . J'r
`l rz
`I Jt I a 1,.
`g,
`[
`, ., 1.: l .s 1 ..
`
`( 11.74)
`
`or
`
`Q(s, 1) = s . M . G . MT. rr, 0 s s, I s I.
`Written separately for each of x, y, and z, the form is
`x(s, 1) = S · M · G, · M1 · J'r,
`}~s. 1) = s. M . c,. MT · rr.
`z(s, 1) = S · M · G, · MT · J'r.
`(11.76)
`Gi\'en this general form, we now move on to examine specific ways to specify surfaces using
`different geometry matrixes.
`
`(11 .75)
`
`11 .3 .1 Hermite Surfaces
`Hermite surfaces are completely defined by a 4 x 4 geometry matrix G8 . Derivation of Gu
`follows the same approach used to find Eq. (11.75). We further elaborate the derivation
`here, applying it justto x(s, 1). First, we replace 1 by s in Eq. ( 11.13), to get x(s) = S • M" ·
`G~~,. Rewriting this further so that the Hermite geometry vector Gu, is not constant, but is
`rather a function of 1, we obtain
`
`( 11.77)
`
`The functions P 1,(1) and P ._(1) define the x components of the starting and ending points for
`the curve in parameters. Similarly, R1,(1) and R4,{1) are the tangent vectors at these points.
`For any specific value of 1, there are two specific endpoints and tangent vectors. Figure
`11.39 shows P 1(1), P4(t), and the cubic ins that is defined when t = 0.0, 0.2, 0.4, 0.6, 0.8,
`and 1.0. The surface patch is essentially a cubic interpolation between P 1(1) = Q (0, 1) and
`P4(t) • Q (l, 1) or, altemati\'ely, between Q(s, 0) and Q(s, 1).
`In the special case that the four intcrpolants Q(O, 1), Q(l , l), Q(s, 0), and Q(s, I) are
`straight lines, the result is a ruled surface. If the intcrpolants are also coplanar, then the
`surface is a four-sided planar polygon.
`
`0550
`
`

`
`518
`
`Rel)fesenting Curves and Surfaces
`
`Fig. 11 .39 lines of constant parameter values on a bicubic surface: P,(t) is at s • 0,
`P,(t) is at s • 1.
`
`Continuing with the derivation, let each of P1(t), Pit), R1(t), and Rit) be represented in
`Hennite fonn as
`
`I,
`
`H
`
`P (t) = T · M 111
`'
`f u
`lu •
`
`['Ill
`
`( 11.78)
`
`( 11.79)
`
`(11.80)
`
`These four cubics can be rewritten together as a single equation:
`[P 1(r) P4(r) R1(t) R.(t)), = T • MH • Gl;,,
`
`where
`
`l ul
`l u I tt l u
`G,._ = It~ Ia
`I a ~~ .
`I ll l u 1'43
`I s.
`[
`, ., 142 143 g .. •
`Transposing both sides of Eq. (I 1.79) resultS in
`
`[fu f11
`l t1
`g11
`l c1
`
`f u
`l u I a
`f u g,
`l o
`l o
`
`P,(t)l
`Pc(r) _
`R1(r)
`-
`Rit)
`
`•
`
`[
`
`' 14] 1~ ~ . rr = GH. . MJ . rr.
`l u
`g ..
`
`z
`
`( 11.81)
`
`0551
`
`

`
`11 .3
`
`Parametric Bicubic Surfaces
`
`619
`
`Substituting Eq. (11.81) into Eq. ( I I.TI) yields
`x(s, t) = S · M8 • G8 , • M~ · 7";
`
`( 11.82)
`
`similarly,
`y(s, t) = S · M8 • Gu, · M~ · 7", z(s, 1) = S · Mn · Gn, · M~ · 7".
`( 11.83)
`The three 4 x 4 matrixes Gn,• Gn,• and Gn, play the same role for Hermite surfaces as
`did the single matrix G8 for curves. The meanings of the 16 elements of Gu can be
`understood by relating them back to Eqs. (11.77) and (11.78). The element l u. is x(O, 0)
`because it is the starting point for P1,(1), which is in tum the starting point for x(s, 0).
`Similarly, g1~ is x(O, I) because it is the ending point of P1,(1), which is in tum the starting
`point for x(s, 1). Furthermore, g11, is ax1a1(0, 0) because it is the starting tangent vector for
`P1,(t), and l aa, is a2xJasa1(0, 0) because it is the starting tangent vector of R1,(1), which in
`tum is the starting slope of x(s, 0).
`Using these interpretations, we can write Gn, as
`
`x( I, 0)
`
`x(l , I)
`
`GH,=
`
`x(O, 0)
`
`x(O, I)
`
`a
`a
`atx(O, I )
`alx(O, 0)
`a
`a
`alx( I, 0)
`alx(l, I )
`a!
`(J!
`a
`a
`asx(O, 0) asx(O, I ) asalx(O, 0) asalx(O, I)
`a2
`a!
`a
`a
`asx(l , 0)
`asx(l , I)
`asalx(l, I)
`asalx( I ' 0)
`
`( 11.84)
`
`The upper-left 2 x 2 portion of Gu, contains the x coordinates of the four comers of
`the patch. The upper-right and lower-left 2 x 2 areas give the x coordinates of the tangent
`vectors along each parametric direction of the patch. The lower-right 2 x 2 portion has at
`its comers the partial derivatives with respect to both sand t. These partials are often called
`the twists, because the greater they are, the greater the coricscrewlike twist at the comers.
`Figure 11.40 shows a patch whose comers are labeled to indicate these parameters.
`This Hermite form of bicubic patches is an alternative way to express a restricted form
`of the Coons patch [COON67]. These more general patches permit boundary curves and
`slopes to be any curves. (The Coons patch was developed by the late Steven A. Coons
`[HERZSO), an early pioneer in CAD and com