Graphics Reference
In-Depth Information
because the coefficients of the other terms vanish. See Theorem 11.5.1.4. This expres-
sion only uses the knots u
r-m
, u
r-m+1
,..., u
r+m+1
. Let N
i,j
= N
i,j
(u). The Cox-de Boor
definition of the N
i,j
computes p(u) based on the following diagram, which shows the
nonzero terms:
N
NN
NN
0
0
r
,
1
0
0
r
,
2
r
-
1 2
,
0
N
0
r
,
3
r
-
1 3
,
r
-
2 3
,
.
.
0
NN
...
N
N
0
rk
,
r
-
1
,
k
r k
-
+
2
,
k
r k
-
+
1
,
k
Furthermore, to compute p(u) one just needs a one-dimensional array. Starting with
some appropriate initial values, one can compute the final B-spline value by com-
puting new values of the array from previous ones using the recursive formulas for
the N
i,j
. With regard to derivatives, by differentiating the N
i,k
(u) using formula (11.69b)
and using a simple inductive argument it is easy to show that the following recursive
formula holds for the first derivative:
d
du
Nu
k
-
1
k
uu
Nu
-
-
1
()
=
()
+
()
Nu
.
ik
,
ik
,
-
1
i
+-
11
,
k
u
-
u
ik
+-
1
i
ik
+
i
+
1
Higher derivatives can be expressed similarly, with the dth derivative being a linear
combination of the functions N
i+j,k-d
(u), 0 £ j £ d. See [PieT95]. This means that both
the value of the curve and its derivatives can be computed in a recursive fashion using
a single array. In order to simplify the notation in the algorithm, we re-index the knots
so that they become u
0
,u
1
,...,u
2m+1
. The control points
p
r-m
,
p
r-m+1
,...,
p
r
, are re-
indexed with new index varying from 0 to m. This will put u into the interval [u
m
,
u
m+1
) (or (u
m
, u
m+1
] in the one special case). After the re-indexing, the procedure
Deriv-
atives
in Algorithm 11.5.4.2 then computes the values we want. The algorithm used
comes from [LeeE82]. The proof of its correctness uses a knot insertion-type argu-
ment. When d = 0, that is, when we only want the value of the function, then the algo-
rithm reduces to the standard de Boor algorithm described in Section 11.5.2. The
Boolean variable fromRight in the algorithm determines which end of the span is
closest to u. It is used to select the code that will produce the most accurate result
numerically. If one only needs the value and first derivative of a curve, then Luken
and Cheng ([LukC96]) describe a two stage Cox-de Boor method that is somewhat
better than Lee's algorithm.
Next, we consider the evaluation problem for NURBS curves p(u). Fortunately,
by switching to homogeneous coordinates we do not need anything new because the
hard part, the evaluation of the ordinary B-splines N
i,k
(u), has already been done.
Algorithm 11.5.4.3 computes p(u). Finding derivatives is more complicated because
we have quotients. We describe the algorithm in [PieT95]. Let A(u) and w(u) be the
numerator and denominator functions of p(u), respectively, that is,
