Marsh D. Applied Geometry for Computer Graphics and CAD

Подождите немного. Документ загружается.

6. B´ezier Curves I 157

6.36. By writing a program, or using a computer package, implement the

de Casteljau algorithm for a general B´ezier curve to (a) obtain the

coordinate of any point on the curve, and (b) determine the control

points of the two segments obtained by subdivision.

6.10 Applications

In this section the de Casteljau algorithm is applied to three problems: (i)

rendering a B´ezier curve, (ii) ﬁnding the points of intersection of a B´ezier curve

and a line, and (iii) ﬁnding the points of intersection of two B´ezier curves.

The reader should note that there are alternative methods which solve these

problems. The algorithms discussed in this section indicate how the properties

of the B´ezier representation can be applied to these problems.

6.10.1 Rendering

To render a curve means to obtain a plot of it. The main step of the rendering

algorithm is an application of the de Casteljau algorithm to subdivide the curve.

Step 1: Apply the de Casteljau algorithm with t =1/2 to subdivide the B´ezier

curve into two curve segments denoted B

left

and B

right

Step 2: If B

left

is “near linear” (using the criterion described below) then go

to step 3; else, go to step 1 and apply the algorithm to B

left

. Similarly, if

right

is near linear go to step 3; else go to step 1 and apply the algorithm

to B

right

The algorithm continues to subdivide the newly obtained curve segments

that are not near linear. Eventually, the subdivision produces curve segments

that are near linear and no further subdivisions take place.

Step 3: The segment is near linear and can be approximated by its control

polygon. Draw the control polygon.

Each time step 3 is executed, the control polygon of a segment of the curve

is drawn. The union of all these control polygons gives a linear approximation

of the original B´ezier curve.

Test to Determine Whether a B´ezier Curve is Near Linear

There are a number of ways of deciding whether or not a curve is close to be-

ing linear. One method requires the user to specify a tolerance >0. For a plane

158 Applied Geometry for Computer Graphics and CAD

curve, the control points are enclosed in a rectangle (see Figure 6.14(a)), called

a minmax bounding box, with lower left corner (x

min

) and upper right

corner (x

max

), where x

min

max

is the minimum/maximum x-coordinate

of any control point, and y

min

max

is the minimum/maximum y-coordinate of

any control point. The curve is considered linear if the horizontal or vertical

dimensions of the box are less than . The smaller the tolerance the greater the

number of subdivisions computed, and the smoother the resulting approxima-

tion to the curve.

A more sophisticated alternative is to determine the largest distance of

any interior control point (i.e. a control point which is not an endpoint) from

the line through the endpoints of the curve as shown in Figure 6.14(b). This

is a more computationally expensive method than the minmax box method,

but generally it will result in fewer subdivisions which will give a saving in

computations. A further improvement of the algorithm can be obtained by

02 4

Figure 6.14 (a) Minmax bounding box, and (b) test for near linearity

subdividing at values other than t =1/2. In general, the point B(1/2) is not

exactly half-way along the curve. So the algorithm could be improved if the

subdivision takes place nearer to half-way as this would reduce the number of

subdivisions. To determine the value of t which corresponds to half-way requires

considerable additional computation, and it is not obvious whether this results

in a more eﬃcient algorithm.

6.10.2 Intersection of a Planar B´ezier Curve and a Line

A planar B´ezier curve B(t)ofdegreen can intersect a line  in the plane in up

to n points. (It is assumed that B(t) is not a line segment and intersecting  in

an inﬁnite set.) A simple algorithm to compute the points of intersection is as

follows.

6. B´ezier Curves I 159

Step 1: Test whether the convex hull of the control points intersects the line

(see below for details). If so, go to step 2 as there may be an intersection;

else, the curve does not intersect the line and the curve may be disregarded.

Step 2: Test to see if the curve is near linear. If so, go to step 3; else, apply

the de Casteljau algorithm to subdivide the curve into two B´ezier curve

segments and repeat step 1 with each segment.

Step 3: The curve (or curve segment) is linear and may be approximated by

a line segment (for example, by the line joining the ﬁrst and last control

points), and intersected with  using the algorithm implemented in Exercise

6.36. The intersection is a point of intersection of the B´ezier curve and .

Test to Determine Whether a Convex Hull Intersects a Line

Suppose the line  has the equation ax+by+c = 0. A line partitions the plane

into two regions, one on either side of the line. The regions are distinguished

by the fact that points (x, y) in one region satisfy ax + by + c>0, and points

in the other satisfy ax + by + c<0. All control points of a curve lie on one

side of the line if and only if the convex hull does not intersect the line. Thus a

simple check for intersection would be to determine whether ax

+ by

+ c has

the same sign for every control point b

)(i =0,...,n) as illustrated in

Figure 6.15.

Neither the convex

hull nor the curve

intersects the line

Convex hull

intersects the

line, but the

curve does not

Both the convex

hull and the curve

intersect the line

Figure 6.15 Convex hull test

6.10.3 Intersection of Two B´ezier Curves

Determining the points of intersection of two curves is a complex problem. A

curve of degree m intersects another of degree n in up to m × n points. (This

result follows from a more general result known as Bezout’s theorem [11].)

160 Applied Geometry for Computer Graphics and CAD

For example, two cubic curves can meet in as many as nine points. A simple

algorithm to compute the intersection points of two B´ezier curves is as follows.

Step 1: Test to see if the convex hulls of the control polygons intersect (see

below for details). If so, go to step 2 as the curves may intersect; else the

curves cannot intersect and may be disregarded.

Step 2: Test whether the curves are linear. If so, go to step 3; else, apply the

de Casteljau algorithm to subdivide each curve into two segments, and to

give a total of four pairs of curve segments. Go to step 1 and apply the

algorithm to each pair.

Thus, each pair of subdivided curve segments is treated in a similar manner

to the original pair. Each subdivision produces curves with control points that

have successively smaller convex hulls. The subdivision process will stop when

the curve segments are near linear. Alternatively, the subdivision process could

be coded to stop after a ﬁxed number of iterations (obviously with some loss

of precision in the computation of the intersection points).

Step 3: Since both curves are near linear, the curves may be approximated

by line segments (for example, by the line joining the ﬁrst and last control

points). The two linear segments are intersected (using the algorithm of

Exercise 6.36) to determine the point of intersection of the two segments.

Test to Determine Whether Two Convex Hulls are Intersecting

The simplest method is to enclose each convex hull in a minmax bounding

box. The two boxes are easily checked for overlap.

EXERCISES

6.37. Implement the B´ezier rendering algorithm using (a) the simple rect-

angular bounding box criterion, and (b) the distance to line criterion.

Compare the performance of the two algorithms for curves of small

and large degrees, and for nearly linear curves which are parallel or

at an angle to the x-ory-axes.

6.38. Determine algorithms which (a) approximate a nearly linear B´ezier

curve by a line, and (b) determine the intersection of two linear seg-

ments. Use the algorithms to implement the line/B´ezier intersection,

and B´ezier/B´ezier intersection algorithms.

B´ezier Curves II

7.1 Spatial B´ezier Curves

A spatial B´ezier curve B(t)=



i=0

i,n

(t) is obtained when the control

points b

are three-dimensional. Spatial B´ezier curves satisfy the properties of

planar B´ezier curves given in Section 6.7, namely, the endpoint interpolation

and endpoint tangent conditions, invariance under aﬃne transformations, the

convex hull property (CHP), and the variation diminishing property (VDP). In

general, the convex hull of the set of control points is a volume. In the special

case when the control points are coplanar the convex hull is a planar region

and the CHP implies that the B´ezier curve is contained in a plane. The VDP

in the spatial case states that a plane intersects a B´ezier curve in less than or

equal to the number of intersections of that plane with the control polygon.

The de Casteljau algorithm is executed in a similar manner to the two-

dimensional case, except that the linear interpolation is applied to three coor-

dinates rather than two (as illustrated in the next example).

Example 7.1

Let a spatial cubic B´ezier curve be speciﬁed by control points b

(1, 2, 1),

(3, 0, 4), b

(6, −3, 2), and b

(4, 2, 3). The endpoints of the curve are b

(1, 2, 1)

and b

(4, 2, 3). The endpoint tangent vectors are 3 ((3, 0, 4) − (1, 2, 1)) =

(6, −6, 9) and 3 ((4, 2, 3) − (6, −3, 2)) = (−6, 15, 3). The point B(0.3), for in-

stance, is obtained by applying the de Casteljau algorithm with t =0.3tothe

161

162 Applied Geometry for Computer Graphics and CAD

three-dimensional control points

(1, 2, 1) (3, 0, 4) (6, −3, 2) (4, 2, 3)

(1.6, 1.4, 1.9) (3.9, −0.9, 3.4) (5.4, −1.5, 2.3)

(2.29, 0.71, 2.35) (4.35, −1.08, 3.07)

(2.908, 0.173, 2.566)

Hence B(0.3) = (2.908, 0.173, 2.566). The de Casteljau algorithm also subdi-

vides the curve into two segments (as described in Section 6.9): B

left

deﬁned

by control points

(1, 2, 1), (1.6, 1.4, 1.9) , (2.29, 0.71, 2.35) , (2.908, 0.173, 2.566)

and B

right

deﬁned by control points

(2.908, 0.173, 2.566) , (4.35, −1.08, 3.07) , (5.4, −1.5, 2.3) , (4, 2, 3) .

7.2 Derivatives of B´ezier Curves

Many computations involving curves, such as determining tangents and nor-

mals, require the calculation of derivatives. Derivatives of B´ezier curves are

obtained from the derivatives of the Bernstein basis functions. For instance,

the derivatives of the cubic Bernstein basis functions B

0,3

(t)=(1− t)

1,3

(t)=3(1− t)

t, B

2,3

(t)=3(1− t)t

,andB

3,3

(t)=t

are



0,3

(t)=−3(1 − t)

= −3B

0,2

(t) ,



1,3

(t)=3(1− t)

− 6t(1 − t)=3(1− 4t +3t

)=3B

0,2

(t) − 3B

1,2

(t) ,



2,3

(t)=3t(2 − 3t)=3B

1,2

(t) − 3B

2,2

(t) , and



3,3

(t)=3t

=3B

2,2

(t) .

Hence, the derivative of a cubic B´ezier curve B(t)=



i=0

i,3

(t)is



(t)=−3b

0,2

(t)+3b

0,2

(t) − B

1,2

(t))

+3b

1,2

(t) − B

2,2

(t)) + 3b

2,2

(t) ,

=3(b

− b

0,2

(t)+3(b

− b

1,2

(t)+3(b

− b

2,2

(t) .

The generalizations of the above formulae for B´ezier curves of degree n are

expressed in Theorems 7.2 and 7.3.

7. B´ezier Curves II 163

Theorem 7.2

The ﬁrst and second derivatives of the Bernstein basis functions B

i,n

(t)of

degree n satisfy



i,n

(t)=

(i − nt)

t(1 − t)

i,n

(t) ,



i,n

(t)=



i(i − 1) − 2i(n − 1)t + n(n − 1)t

(1 − t)



i,n

(t) ,



i,n

(t)=n (B

i−1,n−1

(t) − B

i,n−1

(t)) .

Proof

Diﬀerentiating B

i,n

(t)=





(1 − t)

n−i

by the product rule gives



i,n

(t)=







−(n − i)(1− t)

n−i−1

+ i(1 − t)

n−i

i−1





i − nt

t(1 − t)





(1 − t)

n−i

which establishes the ﬁrst formula. The second formula is obtained by diﬀer-

entiating the ﬁrst formula,



i,n

(t)=



i − nt

t(1 − t)





i,n

(t)+

(i − nt)

t(1 − t)



i,n

(t) ,

(2it − nt

− i)

(1 − t)

i,n

(t)+

(i − nt)

(1 − t)

i,n

(t)



i(i − 1) − 2i(n − 1)t + n(n − 1)t

(1 − t)



i,n

(t) .

The third formula is Exercise 7.5.

Theorem 7.3

The ﬁrst derivative of a B´ezier curve of degree n is



(t)=

n−1



i=0

(1)

i,n−1

(t) , (7.1)

where b

(1)

= n (b

i+1

− b

164 Applied Geometry for Computer Graphics and CAD

Proof

Applying the third formula B



i,n

(t)=n (B

i−1,n−1

(t) − B

i,n−1

(t)) of Theorem

7.2 and using the fact that B

−1,n−1

(t)=B

n,n−1

(t) = 0, gives



(t)=



i=0



i,n

(t)=



i=0

n (B

i−1,n−1

(t) − B

i,n−1

(t))



i=0

i−1,n−1

(t) −



i=0

i,n−1

(t)



i=1

i−1,n−1

(t) −

n−1



i=0

i,n−1

(t) .

Renumbering the ﬁrst summation of the previous line gives



(t)=

n−1



i=0

i+1

i,n−1

(t) −

n−1



i=0

i,n−1

(t)=

n−1



i=0

n (b

i+1

− b

) B

i,n−1

(t) .

The second and higher order derivatives of B(t) are obtained by repeated appli-

cations of the ﬁrst derivative formula. Note that the formulae apply to spatial

as well as planar B´ezier curves.

Corollary 7.4

The second derivative of a B´ezier curve of degree n is



(t)=

n−2



i=0

(2)

i,n−2

(t) ,

where b

(2)

=(n − 1)



(1)

i+1

− b

(1)



= n (n − 1) (b

i+2

− 2b

i+1

+ b

Corollary 7.5

The rth derivative of a B´ezier curve of degree n is

(r)

(t)=

n−r



i=0

(r)

i,n−r

(t) ,

where

(r)

= n(n − 1) ...(n − r +1)



j=0

(−1)

r−j





i+j

7. B´ezier Curves II 165

Example 7.6

Consider the cubic B´ezier curve deﬁned by control points b

(2, 1), b

(5, 6),

(6, 2), and b

(9, 3). The diﬀerences of the control points are

(5, 6) − (2, 1) = (3, 5), (6, 2) − (5, 6) = (1, −4), (9, 3) − (6, 2) = (3, 1) .

Multiply each diﬀerence by 3 to give the control points of the ﬁrst derivative

(1)

(9, 15), b

(1)

(3, −12), b

(1)

(9, 3) .

Therefore, the derivative of the cubic is the quadratic B´ezier curve

(1 − t)

(9, 15) + 2(1 − t)t(3, −12) + t

(9, 3) .

To determine the second derivative, take the diﬀerences of the control points

of the ﬁrst derivative

(3, −12) − (9, 15) = (−6, −27) , (9, 3) − (3, −12) = (6, 15) ,

and multiply by (n −1) = 2 to give b

(2)

(−12, −54) and b

(2)

(12, 30). Hence the

second derivative of the cubic is the linear B´ezier curve

(1 − t)(−12, −54) + t(12, 30) . (7.2)

Then, for instance, the tangent vector of the curve at the point corresponding

to parameter t =0.5 is obtained by substituting t =0.5 in the ﬁrst derivative

(1 − 0.5)

(9, 15) + 2(1 − 0.5)0.5(3, −12) + 0.5

(9, 3) = (6.0, −1.5) .

EXERCISES

7.1. Apply the de Casteljau algorithm with t =0.3 to the spatial cu-

bic B´ezier curve B(t) with control points b

(2, 7, 4), b

(4, 6, 5),

(5, 8, 4), and b

(3, 5, 3). Determine B(0.3) and the control points

of the two curve segments obtained by subdividing at t =0.3.

7.2. Determine the ﬁrst and second derivatives of the cubic B´ezier curve

with control points b

(6, 3), b

(4, 3), b

(1, 2), and b

(−1, 2).

7.3. Determine the ﬁrst and second derivatives of the quartic B´ezier

curve with control points b

(1, 1), b

(1, 3), b

(5, 6), b

(6, 2), and

(4, −1).

7.4. Determine an expression, in terms of the control points, for the ac-

celeration vectors (second derivatives) at the endpoints of a B´ezier

curve of degree n.

166 Applied Geometry for Computer Graphics and CAD

7.5. Prove the ﬁnal result of Theorem 7.2 that the Bernstein basis func-

tions satisfy B



i,n

(t)=n (B

i−1,n−1

(t) − B

i,n−1

(t)).

7.6. Extend your computer implementation of the de Casteljau algorithm

to apply to spatial B´ezier curves.

7.3 Conversions Between Representations

All polynomial curves can be represented in B´ezier form. Suppose a polynomial

curve of degree n is expressed in the monomial form

+ a

t + ···+ a

=(p

+ p

t + ···+ p

+ q

t + ···+ q

) (7.3)

over the interval [0, 1]. The points a

are called monomial control points.The

curve can be converted into B´ezier form by multiplying the monomial control

points by a conversion matrix. For instance, expanding the expression for a

quadratic B´ezier curve gives

(1−t)

2(1−t)t+b

=(b

−2b

+(−2b

+2b

)t+ b

. (7.4)

A comparison of the coeﬃcients with those of a

+ a

t + a

gives

= b

, a

=2(b

− b

), and a

= b

− 2b

+ b

The relationship between the control points of the two representations can be

expressed in the matrix form

⎛

⎝

⎞

⎠

⎛

⎝

100

−220

1 −21

⎞

⎠

⎛

⎝

⎞

⎠

. (7.5)

The inverse matrix can be used to express the B´ezier control points in terms

of the monomial control points

⎛

⎝

⎞

⎠

⎛

⎝

100

111

⎞

⎠

⎛

⎝

⎞

⎠

. (7.6)

The two conversion matrices are denoted

Bez =

⎛

⎝

100

−220

1 −21

⎞

⎠

, and Bez

−1

⎛

⎝

100

111

⎞

⎠

Let a =





and b =





, then the conversions (7.5)

and (7.6) may be written

a = Bez·b , and b = Bez

−1

·a . (7.7)