Game Development Reference
In-Depth Information
dealing with a 3D curve, which is really three one-dimensional curves that
share the same knot sequence.
Of course, all of this would work only if we knew the basis polynomials,
and finding ℓ
i
is itself a problem of polynomial interpolation. However,
the “data points” we wish ℓ
i
to interpolate are all either 0 or 1, so ℓ
i
can
be expressed in a simple form. Such basis polynomials are called Lagrange
basis polynomials.
6
A Lagrange
7
basis polynomial ℓ
i
for knot vector t
1
...t
n
looks like Equation (13.8):
Lagrange Basis Polynomial
t − t
j
t
i
− t
j
t − t
0
t
i
− t
0
t − t
i−1
t
i
− t
i−1
t − t
i+1
t
i
− i
i+1
t − t
n
ℓ
i
(t) =
=
t
i
− t
n
. (13.8)
1≤j≤n,
j=i
This trick works because at the knot t
i
, all the terms in the product equal
1, causing the entire expression to evaluate to 1, and at any other knot,
one of the terms in the product is 0, which causes the entire expression to
evaluate to 0.
Let's apply this to our example S curve. Recall that it used the uniform
knot vector (0,
3
,
3
,1). Here, we work through the first basis polynomial
and just present the results for the others:
t − t
2
t
1
t − t
3
t
1
t − t
4
t
1
t − 1/3
0 − 1/3
t − 2/3
0 − 2/3
t − 1
0 − 1
ℓ
1
(t) =
=
− t
2
− t
3
− t
4
3t − 1
−1
3t − 2
−2
t − 1
−1
=
(3t − 1)(3t − 2)(t − 1)
−2
=
= −(9/2)t
3
+ 9t
2
− (11/2)t + 1,
6
Although they are named for Joseph Louis Lagrange (1736-1813), Lagrange basis
polynomials were discovered in 1779 by Edward Waring (1736-1798). It may be inter-
esting to some readers that Lagrange is Ian Parberry's PhD adviser's PhD adviser's,. . . ,
PhD adviser back 10 iterations.
7
It's important to pronounce the name of this French mathematician “luh-
GRAWNGE”. Otherwise, people might think you are talking about the small Texas town
of La Grange (pronounced “luh-GRAYNGE”). To the authors' knowledge, La Grange,
Texas is not the namesake of any basis polynomials, although ZZ Top did name a song
after the town in honor of a nearby brothel.
Search WWH ::
Custom Search