i
i
i
i
i
i
i
i
5
Linear Algebra
Perhaps the most universal tools of graphics programs are the matrices that
change or transform points and vectors. In the next chapter, we will see
how a vector can be represented as a matrix with a single column, and how
the vector can be represented in a different basis via multiplication with a
square matrix. We will also describe how we can use such multiplications to
accomplish changes in the vector such as scaling, rotation, and translation. In this
Figure 5.1. The signed
area of the parallelogram is
|ab|, and in this case the
area is positive.
chapter, we review basic linear algebra from a geometric perspective, focusing on
intuition and algorithms that work well in the two- and three-dimensional case.
This chapter can be skipped by readers comfortable with linear algebra. How-
ever, there may be some enlightening tidbits even for such readers, such as the
development of determinants and the discussion of singular and eigenvalue de-
composition.
5.1 Determinants
We usually think of determinants as arising in the solution of linear equations.
However, for our purposes, we will think of determinants as another way to mul-
tiply vectors. For 2D vectors a and b, the determinant |ab| is the area of the
Figure 5.2. The
signed volume of the paral-
lelepiped shown is denoted
by the determinant
|abc|,
and in this case the volume
is positive because the vec-
tors form a right-handed ba-
sis.
parallelogram formed by a and b (Figure 5.1). This is a signed area, and the
sign is positive if a and b are right-handed and negative if they are left-handed.
This means |ab| = −|ba|. In 2D we can interpret “right-handed” as meaning we
rotate the first vector counterclockwise to close the smallest angle to the second
vector. In 3D the determinant must be taken with three vectors at a time. For
three 3D vectors, a, b,andc, the determinant |abc| is the signed volume of the
91
i
i
i
i
i
i
i
i
92 5. Linear Algebra
parallelepiped (3D parallelogram; a sheared 3D box) formed by the three vectors
(Figure 5.2). To compute a 2D determinant, we first need to establish a few of its
properties. We note that scaling one side of a parallelogram scales its area by the
same fraction (Figure 5.3):
|(ka)b| = |a(kb)| = k|ab|.
Also, we note that “shearing” a parallelogram does not change its area (Fig-
ure 5.4):
Figure 5.3. Scaling a par-
allelogram along one direc-
tion changes the area in the
same proportion.
|(a + kb)b| = |a(b + ka)| = |ab|.
Finally, we see that the determinant has the following property:
|a(b + c)| = |ab|+ |ac|, (5.1)
because as shown in Figure 5.5 we can “slide” the edge between the two parallel-
ograms over to form a single parallelogram without changing the area of either of
the two original parallelograms.
Now let’s assume a Cartesian representation for a and b:
Figure 5.4. Shearing
a parallelogram does not
change its area. These
four parallelograms have
the same length base and
thus the same area.
|ab| = |(x
a
x + y
a
y)(x
b
x + y
b
y)|
= x
a
x
b
|xx| + x
a
y
b
|xy| + y
a
x
b
|yx|+ y
a
y
b
|yy|
= x
a
x
b
(0) + x
a
y
b
(+1) + y
a
x
b
(−1) + y
a
y
b
(0)
= x
a
y
b
− y
a
x
b
.
This simplification uses the fact that |vv | =0for any vector v, because the
parallelograms would all be collinear with v and thus without area.
In three dimensions, the determinantof three 3D vectorsa, b,andc is denoted
|abc|. With Cartesian representations for the vectors, there are analogous rules
for parallelepipeds as there are for parallelograms, and we can do an analogous
expansion as we did for 2D:
|abc| = |(x
a
x + y
a
y + z
a
z)(x
b
x + y
b
y + z
b
z)(x
c
x + y
c
y + z
c
z)|
= x
a
y
b
z
c
− x
a
z
b
y
c
− y
a
x
b
z
c
+ y
a
z
b
x
c
+ z
a
x
b
y
c
− z
a
y
b
x
c
.
Figure 5.5. The geometry
behind Equation 5.1. Both
of the parallelograms on the
left can be sheared to cover
the single parallelogram on
the right.
As you can see, the computation of determinants in this fashion gets uglier as the
dimension increases. We will discuss less error-prone ways to compute determi-
nants in Section 5.3.
Example. Determinants arise naturally when computing the expression for one
vector as a linear combination of two others—for example, if we wish to express
a vector c as a combination of vectors a and b:
c = a
c
a + b
c
b.
i
i
i
i
i
i
i
i
5.2. Matrices 93
Figure 5.6. On the left, the vector c can be represented using two basis vectors as
a
c
a +
b
c
b. On the right, we see that the parallelogram formed by a and c is a sheared version of
the parallelogram formed by
b
c
b and a.
We can see from Figure 5.6 that
|(b
c
b)a| = |ca|,
because these parallelograms are just sheared versions of each other. Solving for
b
c
yields
b
c
=
|ca|
|ba|
.
An analogous argument yields
a
c
=
|bc|
|ba|
.
This is the two-dimensional version of Cramer’s rule which we will revisit in
Section 5.3.2.
5.2 Matrices
A matrix is an array of numeric elements that follow certain arithmetic rules. An
example of a matrix with two rows and three columns is
1.7 −1.24.2
3.04.5 −7.2
.
Get Fundamentals of Computer Graphics, 3rd Edition now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
