11 .2
`
`Parametric Cubic Curves
`
`4 99
`
`Increasing knot multiplicity has two effects. First, each k:not value 11 will automatically
`lie within the convex hull of the points P1_ 3, P1_ 2, and P1_ 1• If 11 and t1• 1 are equal, they
`must lie in the convex hull of P1_ 3, P1_ 2, and P1_ 1, and in the convex hull of P1_ 2, P1_ 1,
`and P1• This means they must actually lie on the line segment between P1 _ 2 and P1_ 1• ln the
`same way, if t1 = 11 + 1 = 11 +2• then this k:not must lie at P1 _ 1• If 11 = t;. 1 = 11 H = 11 +a• then
`the knot must lie both at P1 _ 1 and at P 1-the curve becomes broken. Second, the multiple
`k:nots will reduce parametric continuity: from Cl to C1 continuity for one extra k:not
`(multiplicity 2); from c• to co continuity for two extra knots (multiplicity 3); from co to no
`continuity for three extra k:nots (multiplicity 4).
`Figure 11 .27 provides further insight for a specific case. Part (a) shows the case when
`all knots have multiplicity I. Each curve segment is defined by four control points and four
`blending functions, and adjacent curve segments each share three control points. For
`instance, curve segment Q3 is defined by points P0, P., P2, and P3; curve segment Q4 is
`defined by points P., P2> P3 and P4; and curve segment Q5 is defined by points P2, P3, P4 ,
`and P5• Part (b) shows a double knot, t4 = t5 , for which the curve segment Q4 has zero
`length. Segments Q3 and Q5 are thus adjacent but share only two control points, P2 and P3;
`the two curve segments hence have less ''in common,'' as implied by the loss of l degree of
`continuity. For the triple k:not in part (c), only control point P3 is shared in common: the
`one that the two curve segments now interpolate. Because only one control point is shared,
`we can expect only one constraint, CO continuity, to be satisfied at the join. The knot of
`multiplicity 4, shown in part (d), causes a discontinuity, or break, in the curve. Hence,
`several disjoint splines can be represented by a single knot sequence and set of control
`points. Figure 11 .28 provides additional understanding of the relations among k:nots, curve
`segments, and control points. Table I I . I summarizes the effects of mu.ltiple control points
`and multiple k:nots.
`
`TABLE 11 .1 COMPARISON OF THE EFFECTS OF MULTIPLE CONTROL POINTS
`AND OF MULTIPLE KNOTS
`
`3
`
`4
`
`Multiplicity
`I
`2
`
`Multiple control points
`ct <J!•
`etc•
`Knots constrained to a smaller
`convex hull.
`ctc;G
`Curve interpolates the triple control
`point.
`Curve segments on either side of the
`join are linear.
`ctc;G
`Curve interpolates the quadruple
`control points.
`Curve segments on either side of the
`join are linear and interpolate the
`control points on either side of the
`join.
`•except for spec.ial case discussed in Section 11 .2.
`
`Multiple knots
`ct <;1•
`C'G'
`Knots constrained to a smaller
`convex hull of fewer control points.
`C'(;G
`Curve interpolates control point.
`
`Can control shape of curve segments
`on either side of the join.
`
`There is a discontinuity in the curve.
`
`Curve stops on one control point.
`resumes at next.
`Can control shape of curve segments
`on either side of the discontinuity.
`
`TEXAS INSTRUMENTS EX. 1009 - 532/1253
`
`

`
`500
`
`Representing Curves and Surfaces
`
`y
`
`P,
`
`p2
`
`I "
`"
`"
`"
`"
`" "
`
`Ps
`
`X
`
`(a)
`
`Po
`
`p.
`
`p7
`
`• Knot
`t Control point
`
`y
`
`P,
`
`p2
`
`p5
`
`p6
`
`L - - - - - - - - - -+ X
`
`(b)
`
`• Knot
`t Control point
`
`Fig. 11 .27 The effect of multiple knots. In (a), with knot sequence (0, 1. 2. 3, 4, 5),
`there are no multiple knots; all the curve segments join with C" and G2 continuity. The
`convex hulls containing each curve segment are also shown. In (b), with knot sequence
`(0, 1. 1. 2. 3. 4). there is a double knot, so curve segment 0. degenerates to a point.
`The convex hulls containing 0 3 and ~meet along the edge P/'3, on which the join point
`is forced to lie. The join has C' and G2 continuity. In (c). with knot sequence (0. 1, 1, 1,
`
`Figure 11.29 illustrates the complexity of shapes that can be represented with this
`technique. Notice part (a) of the figure, with knot sequence (0, 0, 0, 0, I, I , I, 1): The
`curve interpolates the endpoints but not the two intermediate points, and is a Bezier curve.
`The other two curves also start and stop with triple knots. This causes the tangent vectors at
`the endpoints to be determined by the vectors Pr/'1 and P ,._ 1P ,., gjving Bezier-like control
`to the curves at the start and stop points.
`interactive creation of nonuniform splines typically involves pointing at control
`points, with multiple control points indicated simply by successive selection of the same
`point. Figure 11.30 shows a way of specifying knot values interactively. Another
`way is to point directly at the curve with a multibutton mouse: A double click on one but(cid:173)
`ton can indicate a double control point; a double click on another button, a double
`knot.
`
`TEXAS INSTRUMENTS EX. 1009 - 533/1253
`
`

`
`11 .2
`
`Parametric Cubic Curves
`
`501
`
`y ~
`
`p2
`
`p5
`
`Pe
`
`I
`I
`I
`I
`I
`I
`------- 4
`• Knot
`• Control point
`
`p7
`
`I
`
`P,
`
`13
`
`Po
`
`y
`
`P,
`
`Po
`
`~.~~5~16
`
`p3
`
`p2
`
`)(
`
`(c)
`
`14 = 15 = 16
`
`p3
`
`)(
`
`(d)
`
`/
`
`/
`/. 0
`7
`
`Pe
`- -;
`I
`I
`I
`I
`I
`I
`= 17 --- ---- 4
`~
`• Knot
`• Control point
`
`p5
`
`r
`
`p7
`
`2. 3), there is a triple knot, so curve segments a. and ~ degenerate to points. The
`convex hulls containing 0 3 and ~ meet only at P3• where the join point is forced to be
`located. The two curve segments share only control point P3, with C0 continuity. In (d),
`with knot sequence (0. 1, 1, 1, 1. 2). there is a quadruple knot, which causes a
`discontinuity in the curve because curve segments 0 3 and Or have no control points in
`common.
`
`11.2.5 Nonuniform, Rational Cubic Polynomial Curve Segments
`
`General rational cubic curve segments are ratios of polynomials:
`
`_ Z(t)
`_ Y(t)
`_ X(t)
`x(t) - W(t)' y(t) - W(t )' z(t) - W(r) '
`
`( 11.45)
`
`where X(t), Y(t), Z(t), and W (t) are all cubic polynomial curves whose control points are
`defined in homogeneous coordinates. We can also think of the curve as existing in
`homogeneous space as Q(t) = [X(t) Y(t) Z(r) W(t)]. As alw.tys, moving from
`homogeneous space to 3-space involves dividing by W(t). Any nonrational curve can be
`transformed to a rational curve by adding W(t) = I as a fourth element. In general, the
`
`TEXAS INSTRUMENTS EX. 1009 - 534/1253
`
`

`
`502
`
`Representing Curves and Surfaces
`
`Curve
`segment 0 1
`
`Control
`point P1 1 -5
`
`Curve
`segment 0 1
`
`Control
`point P1 I- 5
`
`Curve
`segment 0 1
`
`i - 2
`
`i - 1
`
`i + 1
`
`i + 2
`
`i + 3
`
`c2
`continuity
`
`I- 4
`
`I - 3
`
`I- 2
`
`i - 1
`
`I + 1
`
`i + 2
`
`i + 3
`
`(a)
`
`I - 2
`
`I - 1
`
`i + 1
`
`I + 2
`
`I + 3
`
`c'
`continuity
`
`I- 4
`
`I - 3
`
`I - 2
`
`I - 1
`
`I + 1
`
`I + 2
`
`I + 3
`
`(b)
`
`I - 2
`
`I - 1
`
`I + 1
`
`I + 2
`
`I + 3
`
`co
`continuity
`
`Control
`point P1
`
`I - 5
`
`I - 4
`
`1- 3
`
`I - 2
`
`I - 1
`
`I + 1
`
`I + 2
`
`; + 3
`
`Curve
`segment 0 1
`
`Control
`point P1 I- 5
`
`(c)
`
`I- 2
`
`I - 1
`
`I + 1
`
`I + 2
`
`I + 3
`
`No
`continuity
`
`; - 4
`
`i - 3
`
`i - 2
`
`i - 1
`
`I + 1
`
`I + 2
`
`1 +3
`
`(d)
`
`Fig. 11 .28 The relationship among curve segments, control points, and multiple knots
`for nonuniform B-splines. lines connect curve segments to their control points; gray
`lines are used for curve segments that do not appear because their knot interval is zero
`(i.e., the knot multiplicity is greater than one), causing them to have zero length. In (a), all
`knots are single. In (b), there is a double knot, so segment i is not drawn. In (c), there is a
`triple knot, so two segments are not drawn; thus, the single point, i - 1, is held in
`common betw een adjacent segments i - 1 and i + 2. In (d), w ith a quadruple knot,
`segments i - 1 and i + 3 have no points in common, causing the curve to be
`disconnected between points i - 1 and i.
`
`polynomials in a rational curve can be Bezier, Hermite, or any other type. When they are
`B-splines, we have nonuniform rational B-splines, sometimes called NURBS [FORR80).
`Rational curves are useful for two reasons. The first and most important reason is that
`they are invariant under rotation, sealing, tran.slation and perspective transformations of the
`control points (nonrational curves are invariant under only rotation, scaling, and transla(cid:173)
`tion). This means that the perspective transformation needs to be applied to only the control
`
`TEXAS INSTRUMENTS EX. 1009 - 535/1253
`
`

`
`11 .2
`
`Parametric Cubic Curves
`
`503
`
`Po
`10= 11= 12= 13= 0
`
`(a)
`
`op 5
`5
`
`14=1 5a le =1
`
`(b)
`
`Pe•
`
`• Ps
`11= 1e=2
`(c)
`
`Fig. 11 .29 Examples of shapes defined using nonrational 8-splines and multiple knots.
`Part (a) is just a B6zier curve segment, with knot sequence (0, 0, 0, 0, 1, 1, 1, 1 ). and
`hence just one curve segment, 0 3• Parts (b) and (c) have the same knot sequence, (0, 0 ,
`0, 0 , 1, 1, 1, 2, 2. 3. 4, 5. 5. 5, 5) but different control points. Each curve has curve
`segments 0, to 0 10• Segments 0.. a,, and 0 7 are located at multiple knots and have zero
`length.
`
`1
`
`2
`
`3
`
`4
`
`5
`
`+ I 4.0 ~
`~ 1.0 I 2.0 I 2.0 I
`
`New Value:
`
`Step: 1.0
`
`Fig. 11 .30 An interaction technique developed by Cartes Castellsagu~ for specifying
`knot values. The partial knot sequence is shown, and cari be scrolled left and right w ith
`the horizontal arrows. One knot value, selected with the cursor, can be incremented up
`and down using the vertical arrows, in increments specified by value Step. The selected
`knot value can also be replaced with a new typed-in value.
`
`TEXAS INSTRUMENTS EX. 1009 - 536/1253
`
`

`
`504
`
`Representing Curves and Surfaces
`
`( ~12, ..J2/2, -IM)
`
`( - 1, 0, 1)
`
`(1, 0, 1)
`
`(-1, o. 1)
`
`(1, o. 1)
`
`( - -/M, - ~12, ..J2/2)
`
`(~2.-~2. -IM)
`
`(0, - 1, 1)
`
`(a)
`
`! (0, -1, 0) • -COy
`••
`
`(b)
`
`Fig. 11 .3 1 The control points for defining a circle as a rational spline in 20.
`Coordinates are (X, Y. W). The knot vector is (0, 0, 0, 1, 1, 2, 2. 3, 3, 4 , 4), with the first
`and last control points repeated. The choice of P0 is a rbitrary.
`
`points, which can then be used to generate the perspective transformation of the original
`curve. The alternative to converting a nonrational curve to a rational curve prior to a
`perspective transformation is first to generate points on the curve itself and then to apply the
`perspective transformation to each point, a far less efficient process. This is analogous to the
`observation that the perspective transformation of a sphere is not the same as a sphere
`whose center and radius are the transformed center and radius of the original sphere.
`A second advantage of rational splines is that, unlike nonrationals, they can define
`precisely any of the conic sections. A conic can be only approximated with nonrationals, by
`using many control pointS close to the conic. This second property is useful in those
`applications, particularly CAD, where general curves and surfaces as well as c.onics are
`needed. Both types of entities can be defined with NURBS.
`Defining conics requires only quadratic, not cubic, polynomials. Thus, the B;,a(t)
`blending functions from the recurrence Eq. (11.44) are used in the curve of the form
`Q;(t) = P;-.J1;-u(1) + P;_ 18 ; _1.a(t) + P!J;,a(t)
`
`(11.46)
`
`T~ ways of creating a unit circle centered at the origin are shown in Fig. 11.31 . Note that,
`with quadratic B-splines, a double knot causes a control point to be interpolated, and triple
`knots fix the starting and ending pointS of the curv:: on control pointS.
`For further discussion of conics and NURBS, see [FAUX79; BOHM84; TILL83].
`
`11 .2 .6 Other Spline Forms
`
`Very often, we have a series of positions and want a curve smoothly to interpolate (pass
`through) them. This might arise with a series of pointS read from a data tablet or mouse, or
`a series of 30 points through which a curve or camera path is to pass. The Catmuli-Rom
`family of interpolating or approximating splines [CATM74a] , also called Overlrauser
`
`TEXAS INSTRUMENTS EX. 1009 - 537/1253
`
`

`
`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.
`
`TEXAS INSTRUMENTS EX. 1009 - 538/1253
`
`

`
`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.
`
`TEXAS INSTRUMENTS EX. 1009 - 539/1253
`
`

`
`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
`
`TEXAS INSTRUMENTS EX. 1009 - 540/1253
`
`

`
`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,.
`
`TEXAS INSTRUMENTS EX. 1009 - 541/1253
`
`

`
`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 " ·
`
`TEXAS INSTRUMENTS EX. 1009 - 542/1253
`
`

`
`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)
`
`TEXAS INSTRUMENTS EX. 1009 - 543/1253
`
`

`
`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..
`
`TEXAS INSTRUMENTS EX. 1009 - 544/1253
`
`

`
`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.
`
`TEXAS INSTRUMENTS EX. 1009 - 545/1253
`
`

`
`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 subd