Game Development Reference
In-Depth Information
cient gives us one unknown. This system of equations can be put into an
n×n matrix,
5
which can be solved by standard techniques such as Gaussian
elimination or LU decomposition. Such techniques are outside the scope of
this topic, but you can learn about them in practically any good book on
linear algebra or numerical methods.
Solving a matrix is a relatively time-consuming computational process,
requiring O(n
3
) time for an n × n matrix in the worst case. Luckily there
are more e
cient approaches. As we did with Aitken's algorithm, we solve
a large complicated problem by dividing it into a series of smaller, simpler
problems, and then combining those results. Aitken's algorithm is a recur-
sive procedure, but here we will make one “simple” problem per control
point.
Let's ignore the y's for now and think only about the t's. What if
we could create a polynomial for each knot t
i
such that the polynomial
evaluates to unity at that knot, but for all the other knots it evaluates to
zero? If we denote the ith polynomial as ℓ
i
, then this idea can be expressed
in mathspeak: ℓ
i
(t
i
) = 1, and ℓ
i
(t
j
) = 0 for all j = i. For example, let's
assume n = 4. Then our polynomials would have the following values at
the knots:
ℓ
1
(t
1
) = 1,
ℓ
1
(t
1
) = 0,
ℓ
3
(t
1
) = 0,
ℓ
4
(t
1
) = 0,
ℓ
1
(t
2
) = 0,
ℓ
2
(t
2
) = 1,
ℓ
3
(t
2
) = 0,
ℓ
4
(t
2
) = 0,
ℓ
1
(t
3
) = 0,
ℓ
2
(t
3
) = 0,
ℓ
3
(t
3
) = 1,
ℓ
4
(t
3
) = 0,
ℓ
1
(t
4
) = 0,
ℓ
2
(t
4
) = 0,
ℓ
3
(t
4
) = 0,
ℓ
4
(t
4
) = 1.
If we were able to create polynomials with the above properties, we would
be able to use them as basis polynomials. We would scale each basis poly-
nomial ℓ
i
by the corresponding coordinate value y
i
, and add all the scaled
polynomials together:
n
Interpolating polynomial
in Lagrange basis form
P(t) =
y
i
ℓ
i
(t) = y
1
ℓ
1
(t) +y
2
ℓ
2
(t) + +y
n−1
ℓ
n−1
(t) +y
n
ℓ
n
(t). (13.7)
i=1
You might want to take a moment to convince yourself that this polynomial
actually interpolates the control points, meaning P(t
i
) = y
i
.
Notice that the basis polynomials depend only on the knot vector (the
t's) and not on the coordinate values (the y's). Because of this, a set of
basis polynomials can be used to quickly construct multiple curves with the
same knot vector. This is precisely the situation we find ourselves in when
5
This type of matrix, in which each row or column is a geometric series of the powers
of some term, is known as a Vandermonde matrix, after the French mathematician
Alexandre-Theophile Vandermonde (1735-1796).
Search WWH ::
Custom Search