Graphics Reference
In-Depth Information
11.8
Subdivision of Curves
Bézier and B-spline curves are easy to manipulate by moving control points. On the
other hand, we may have too few control points to get the exact shape we want. What
is needed is to be able to add control points, or also knots in the case of B-splines, to
get the desired freedom in shape manipulation. Besides, the fact is that a given curve
can be represented in an infinite number of ways in terms of control points and/or
knots. It is up to us to choose which we like the best. For efficiency one usually wants
the representation that uses the smallest such number, but as we can see, that is not
always the important criterion.
To solve our shape manipulation problem, the general idea will be to subdivide
the shape and express each piece by means of its own independent control data with
the result that the whole curve is then defined by a larger set of control data. We begin
by stating a general form of this problem and then show how it relates to cubic curves.
Later we shall see what this means for Bézier and B-spline curves.
The general subdivision problem:
Suppose that we are given a curve p(u) with domain
[a,b], which is expressed in the form
()
=
()
++
()
+
()
++
()
(11.123)
pu
f u
p
...
f u
p
g u
v
...
g u
v
,
1
1
s
s
1
1
t
t
where the
p
i
are “points” and the
v
i
are “vectors” in
R
m
and the f
i
(u) and g
i
(u) are real-
valued functions. Let c and d be real numbers with a £ c £ d £ b. The problem is to find a
curve q(u) so that
(1) q(u) has the
same
domain [a,b] as p(u),
(2) q(u) traces out the same set as p|[c,d], that is, q([a,b]) = p([c,d]), and
(3) the formula for q(u) has the same form as p(u), that is,
()
=
()
++
()
()
++
()
qu
f u
q
...
f u
q
+
g u
w
...
g u
w
.
1
1
s
s
1
1
t
t
for some points
q
i
and vectors
w
i
(the basis functions f
i
(u) and g
i
(u) are kept unchanged).
Let us see how the problem can be handled in the case of an
arbitrary
cubic curve
p(u) (higher degree curves can be handled similarly). Suppose p(u) has domain [0,1]
and is defined by an equation
p
p
p
p
Ê
ˆ
0
Á
Á
Á
˜
˜
˜
()
=
(
)
1
32
pu
u u u
1
M
,
(11.124)
2
Ë
¯
3
where
M
is some matrix and the
p
i
are
either
points
or
vectors. We shall work out the
subdivision problem in the case where the interval is to be divided at the value c. The
function u Æ cu reparameterizes [0,1] as [0,c]. Substituting cu for u in (11.124) gives
