i
i
i
i
i
i
i
i
904 A. Some Linear Algebra
Some theoretical results of great use are: i)tr(A)=
n−1
i=0
a
ii
=
n−1
i=0
λ
i
, ii)det(A)=
.
n−1
i=0
λ
i
, iii)ifA is real (consists of only
real values) and is symmetric, i.e., A = A
T
, then its eigenvalues are real
and the different eigenvectors are orthogonal.
Orthogonal Matrices
Here, we will shed some light on the concept of an orthogonal matrix, its
properties, and its characteristics. A square matrix, M,withonlyreal
elements is orthogonal if and only if MM
T
= M
T
M = I.Thatis,when
multiplied by its transpose, it yields the identity matrix.
The orthogonality of a matrix, M, has some significant implications
such as: i) |M| = ±1, ii) M
−1
= M
T
, iii) M
T
is also orthogonal,
iv) ||Mu|| = ||u||, v) Mu ⊥ Mv ⇔ u ⊥ v, vi)ifM and N are
orthogonal, so is MN.
The standard basis is orthonormal because the basis vectors are mutu-
ally orthogonal and of length one. Using the standard basis as a matrix,
we can show that the matrix is orthogonal:
8
E =(e
x
e
y
e
z
)=I,and
I
T
I = I.
To clear up some possible confusion, an orthogonal matrix is not the
same as an orthogonal vector set (basis). Informally, the difference is that
an orthogonal matrix must consist of normalized vectors. A set of vectors
may be mutually perpendicular, and so be called an orthogonal vector set.
However, if these are inserted into a matrix either as rows or columns,
this does not automatically make the matrix orthogonal, if the vectors
themselves are not normalized. An orthonormal vector set (basis), on the
other hand, always forms an orthogonal matrix if the vectors are inserted
into the matrix as a set of rows or columns. A better term for an orthogonal
matrix would be an orthonormal matrix, since it is always composed of an
orthonormal basis, but even mathematics is not always logical.
A.3.2 Change of Base
Assume we have a vector, v, in the standard basis (see Section 1.2.1),
described by the coordinate axes e
x
, e
y
,ande
z
.Furthermore,wehave
another coordinate system described by the arbitrary basis vectors f
x
, f
y
,
and f
z
(which must be noncoplanar, i.e., |f
x
f
y
f
z
| =0). Howcanv be
expressed uniquely in the basis described by f
x
, f
y
,andf
z
? The solution is
given below, where w is v expressed in the new basis, described by F [741]:
Fw =
f
x
f
y
f
z
w = v
⇐⇒
w = F
−1
v.
(A.42)
8
Note that the basis is orthonormal, but the matrix is orthogonal, though they mean
thesamething.
i
i
i
i
i
i
i
i
A.4. Homogeneous Notation 905
A special situation occurs if the matrix F is orthogonal, which implies
that the inverse is easily obtained by F
−1
= F
T
. Therefore, Equation A.42
simplifies to Equation A.43:
w = F
T
v =
⎛
⎝
f
T
x
f
T
y
f
T
z
⎞
⎠
v =
⎛
⎝
f
x
·v
f
y
·v
f
z
·v
⎞
⎠
. (A.43)
Orthogonal coordinate system changes are the most common ones in
the context of computer graphics.
A.4 Homogeneous Notation
This section is probably the most important in this chapter, since it influ-
ences many areas of computer graphics and is almost never treated in a
common linear algebra book.
A point describes a location in space, while a vector describes a direction
and has no location. Using 3×3 matrices (or 2×2 for two dimensions), it is
possible to perform linear transformations such as rotations, scalings, and
shears on coordinates. However, translation cannot be performed using
such matrices. This lack is unimportant for vectors, for which translation
has no meaning, but translation is meaningful for points.
Homogeneous notation is useful for transforming both vectors and
points, and includes the ability to perform translation only on points.
It augments 3 × 3 matrices to the size of 4 × 4, and three-dimensional
points and vectors get one more element. So a homogeneous vector is
p =(p
x
,p
y
,p
z
,p
w
). As will soon be made clear, p
w
= 1 for points, and
p
w
= 0 for vectors. For projections, other values can be used for p
w
(see
Section 4.6). When p
w
=0andp
w
= 1, then the actual point is obtained
through homogenization, where all components are divided by p
w
.This
means the point (p
x
/p
w
,p
y
/p
w
,p
z
/p
w
, 1) is obtained.
Equation A.44 shows how a 3 × 3matrix,M, is augmented (in the
simplest case) into the homogeneous form:
M
4×4
=
⎛
⎜
⎜
⎝
m
00
m
01
m
02
0
m
10
m
11
m
12
0
m
20
m
21
m
22
0
0001
⎞
⎟
⎟
⎠
. (A.44)
Rotation, scaling, and shear matrices can replace M in this equation,
and affect both vectors and points, as they should. A translation, however,
uses the additional elements of the augmented matrix to obtain the goal of
i
i
i
i
i
i
i
i
906 A. Some Linear Algebra
the foundation. A typical translation matrix, T, which translates a point
by a vector, t, is shown in Equation A.45:
T =
⎛
⎜
⎜
⎝
100t
x
010t
y
001t
z
000 1
⎞
⎟
⎟
⎠
. (A.45)
The combination of a linear transform followed by a translation is called
an affine transform.
It is quickly verified that a vector v =(v
x
,v
y
,v
z
, 0) is unaffected by the
Tv transform due to the fact that its last element is 0. If the point p =
(p
x
,p
y
,p
z
, 1) is transformed as Tp, the result is (p
x
+ t
x
,p
y
+ t
y
,p
z
+ t
z
, 1),
i.e., p translated by t.
Matrix-matrix multiplications (and thus concatenations of homo-
geneous matrices) and matrix-vector multiplications are carried out pre-
cisely as usual. In Chapter 4, many kinds of different homogeneous trans-
forms will be introduced and thoroughly dissected.
A.5 Geometry
This section is concerned with presenting some useful geometrical tech-
niques that are used extensively in, for example, Chapter 16.
A.5.1 Lines
Two-Dimensional L ines
For two-dimensional lines, there are two main mathematical descriptions:
the implicit form and the explicit form. The latter is parametric, and a
typical equation for it is Equation A.46:
r(t)=o + td. (A.46)
Here, o is a point on the line, d is the direction vector of the line, and
t is a parameter that can be used to generate different points, r,onthe
line.
9
The implicit form is different in that it cannot generate points explicitly.
Assume, instead, that on our line of interest, called L, any point can be
described by p =(p
x
,p
y
)=(x, y), where the latter coordinate notation
9
The points are named r here because in other chapters the line is usually referred
to as a ray.
i
i
i
i
i
i
i
i
A.5. Geometry 907
Figure A.5. Notation used for the implicit form of a two-dimensional line equation. L is
the line, p and q are points on the line, and n is a vector perpendicular to the direction
of L.
is used only in Equation A.47, because this is the line equation form that
most people learn first:
ax + by + c =0. (A.47)
For p to lie on the line L, it must fulfill this equation. Now, if the
constants a and b are combined into a vector n =(n
x
,n
y
)=(a, b), then
Equation A.47 can be expressed using the dot product as
n · p + c =0. (A.48)
A common task is, naturally, to compute the constants of a line. Look-
ing at Figure A.5 and using its notation, we may see that one way of
describing L would be n ·(p −q)=0,whereq is another point on the line.
Thus, n must be perpendicular to the line direction, i.e., n =(p − q)
⊥
=
(−(p
y
− q
y
),p
x
− q
x
)=(a, b), and c = −q · n. Then, given two points on
L, n =(a, b)andc can be calculated.
Rewriting Equation A.48 as a function, f (p)=n · p + c, allows some
very useful properties to be derived. Nothing is now assumed about p;it
can be any point in the two-dimensional plane. First, if again q ∈ L,the
following holds:
1. f(p)=0⇐⇒ p ∈ L.
2. f(p) > 0 ⇐⇒ p lies on the same side of the line as the point q + n.
3. f(p) < 0 ⇐⇒ p lies on the same side of the line as the point q − n.
This test is usually called a half-plane test and is used in, for example,
some point-in-polygon routines (see Section 16.9). Second, f (p)happens
to be a measure for the perpendicular distance from p to L.Infact,it
i
i
i
i
i
i
i
i
908 A. Some Linear Algebra
turns out that the signed distance, f
s
, is found by using Equation A.49:
f
s
(p)=
f(p)
||n||
. (A.49)
If ||n|| =1,thatis,n is normalized, then f
s
(p)=f(p).
Three-Dimensional Lines
In three dimensions, the implicit form of a line is often expressed as the
intersection between two nonparallel planes. An explicit form is shown in
Equation A.50. This equation is heavily used in computing the intersection
between a line (or ray) and a three-dimensional surface:
r(t)=o + td. (A.50)
This is exactly the same equation used for the two-dimensional line, except
that the points and the direction vector are now three dimensional.
Thedistancefromapointp to r(t) can be computed by first projecting
p onto r(t), using Equation A.17. Assuming d is normalized, this is done
by computing the vector w =((p −o) ·d)d. Then the sought-for distance
is ||(p − o) − w||.
A.5.2 Planes
Since the three-dimensional plane is a natural extension of the two-
dimensional line, it can be expected that the plane has similar properties
as the line. In fact, any hyperplane, which is the name for a plane of an
arbitrary dimension, has these similar characteristics. Here, the discussion
will be limited to the three-dimensional plane.
First, the plane can be described in both explicit and implicit form.
Equation A.51 shows the explicit form of the three-dimensional plane:
p(u, v)=o + us + vt. (A.51)
Here, o is a point lying on the plane, s and t are direction vectors that
span the plane (i.e., they are noncollinear), and u and v are parameters
that generate different points on the plane. The normal of this plane is
s × t.
The implicit equation for the plane, called π, shown in Equation A.52,
is identical to Equation A.48, with the exception that the plane equation
is augmented with an extra dimension, and c has been renamed to d:
n · p + d =0. (A.52)
Again, n is the normal of the plane, p is any point on the plane, and
d is a constant that determines part of the position of the plane. As was
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.