Graphics Reference
In-Depth Information
formula like equation (11.107) for the NURBS curve derivatives. The reader is again
referred to [PieT95].
Finally, for the situation where one only needs the value and first partial deriva-
tives of a NURBS surface (which is all that is needed for rendering), Luken and Cheng
([LukC96]) analyze the complexity of three ways of computing those values: a two
stage Cox-de Boor method, a knot insertion method based on Lee's approach that we
used in Section 11.5.4, and a forward differencing method. Their conclusion is that
the first of these methods is the best. Although forward differencing actually was the
fastest method it has numerical stability problems.
12.12.6
B-spline Interpolation
Algorithms for finding surfaces that interpolate some given data depend on the struc-
ture of the data. If the data consists of a rectangular array of points, the algorithm
for finding an interpolating B-spline surface is based on the corresponding algorithm
for B-spline curves. We shall outline the steps for one form of bicubic B-spline surface
interpolation.
The Bicubic B-spline Interpolation Problem.
Given parameter values u
i
, i = 0,..., m,
with u
0
< u
1
< ...< u
m
, and v
j
, j = 0,..., n, with v
0
< v
1
< ...< v
n
, and given points
p
ij
, find
a bicubic B-spline surface p(u,v) with the u
i
and v
j
as the n-knots and v-knots, respectively,
and control points
q
st
, s =-1,..., m + 1, t =-1,..., n + 1, so that p(u
i
,v
j
) =
p
ij
.
To motivate the solution to the interpolation problem note that an interpolating
B-spline surface of the form shown in equation (12.46) would satisfy
m
n
m
Â
Â
Â
(
)
=
()
()
=
()
p
=
pu v
,
N
u N
v
q
N
u
r
,
(12.60a)
ij
i
j
s k
,
i
t h
,
j
st
sk
,
i
sj
s
=
0
t
=
0
s
=
0
where
n
Â
()
r
=
Nv
q
.
(12.60b)
sj
t h
,
j
st
t
=
0
Equation (12.60a) shows that for fixed j the
r
sj
are the control points of a spline that
interpolates the column of points
p
ij
, i = 0,..., m, and equation (12.60b) shows that
for fixed i the
q
st
are the control points of a spline that interpolates the row of points
r
sj
, j = 0,..., n. This means that our interpolation problem can be solved in two stages
using results from Section 11.5.5.
(1) First, solve the curve interpolation problem for each column of the array of
points
p
ij
. This will give us cubic B-spline curves p
j
(v) with knots v
j
and control points
r
sj
, i =-1,...m + 1. Note that the solutions are based on the
same
tridiagonal matrix
shown in equation (11.111), which means that the LU-decomposition of that matrix
which is used to solve that system of equations is done only once.
