Game Development Reference
In-Depth Information
course on linear algebra is to solve a system of equations such as
−5x
1
+ x
2
+ x
3
= −10,
2x
1
+ 2x
2
+ 4x
3
= 12,
x
1
− 3x
3
= 9,
which has the solution
x
1
= 3,
x
2
= 7,
x
3
= −2.
Matrix notation was invented to avoid the tedium involved in duplicating
every x and =. For example, the system above can be more quickly written
as
2
4
−5
3
2
3
2
4
−10
3
1
1
x
1
x
2
x
3
5
4
5
5
2
2
4
=
12
9
.
1
0
−3
Perhaps the most direct and obvious place in a video game where a large
system of equations must be solved is in the physics engine. The constraints
to enforce nonpenetration and satisfy user-requested joints become a sys-
tem of equations relating the velocities of the dynamic bodies. This large
system
3
is then solved each and every simulation frame. Another common
place for traditional linear algebra methods to appear is in least squares
approximation and other data-fitting applications.
Systems of equations can appear where you don't expect them. Indeed,
linear algebra has exploded in importance with the vast increase in com-
puting power in the last half century because many di
cult problems that
were previously neither discrete nor linear are being approximated through
methods that are both, such as the finite element method. The challenge
begins with knowing how to transform the original problem into a matrix
problem in the first place, but the resulting systems are often very large and
can be di
cult to solve quickly and accurately. Numeric stability becomes
a factor in the choice of algorithms. The matrices that arise in practice are
not boxes full of random numbers; rather, they express organized relation-
ships and have a great deal of structure. Exploiting this structure artfully
is the key to achieving speed and accuracy. The diversity of the types of
structure that appear in applications explains why there is so very much to
know about linear algebra, especially numerical linear algebra.
This topic is intended to fill a gap by providing the geometric intuition
that is the bread and butter of video game programming but is left out of
3
It's a system of inequalities, but similar principles apply.
Search WWH ::
Custom Search