Graphics Reference
In-Depth Information
The Problem:
Given an arbitrary NURBS curve
n
S
wN (u)
p
i
i,k
i
i
=
0
n
p (u) =
S
wN (u)
i
i,k
i
=
0
of order k , knot vector U = {u
0
,u
1
, º ,u
n+k
), weights w
i
, and control points
p
i
= (x
i
,y
i
,z
i
) , to compute p(u).
Step 1:
Use Algorithm 11.5.4.1 to find the span that contains u.
Step 2:
Let
P
i
= (x
i
w
i
,y
i
w
i
,z
i
w
i
,w
i
) . Use Algorithm 11.5.4.2 to evaluate
n
S
P (u) =
N
i,k
(u)
P
i
= (P
1
(u),P
2
(u),P
3
(u),P
4
(u)) .
i=
0
(The only change to Algorithm 11.5.4.2 is that we allow control points
to be 4-tuples rather than 3-tuples.)
P(u)
P(u)
,
P(u)
P(u)
,
P(u)
P(u)
)
Step 3:
p (u) = (
1
2
3
4
4
4
Algorithm 11.5.4.3.
A NURBS curve evaluation algorithm.
which provides us with a recursive way to compute p
(d)
(u). Algorithm 11.5.4.4 uses
equation (11.107) to compute the derivative of NURBS curves. Note that to speed up
the algorithm we have assumed that the binomial coefficients have been precomputed
and stored in an array binom[..,..].
11.5.5
B-Spline Interpolation
This section returns to the interpolation problem and describes another approach
using B-splines.
The cubic B-spline interpolation problem:
Given parameter values u
i
, i = 0,..., n, with
u
0
< u
1
< ...< u
n
, and points
p
i
, find a cubic B-spline curve p(u) with the u
i
as knots and
control points
q
j
, j =-1,..., n + 1, so that p(u
i
) =
p
i
.
Following [Fari97] we shall solve the B-spline interpolation problem by using the
fact that this spline can be represented as a piecewise cubic Bézier curve with control
points
b
j
, so that
p
i
=
b
3i
. See Theorem 11.5.2.12. The idea will be to use the well-
defined relationships between the
b
j
and the
p
i
and also those between the
b
j
and the
q
k
. Eliminating the
b
j
from these relationships will give us the relationship between
the
p
i
and
q
k
that we are after.
