Graphics Reference
In-Depth Information
Chapter
3
A Math and Geometry
Primer
Collision detection is an area of a very geometric nature. For example, in a world sim-
ulation both world and objects of that world are represented as geometrical entities
such as polygons, spheres, and boxes. To implement efficient intersection tests for
these entities, a thorough grasp of vectors, matrices, and linear algebra in general is
required. Although this topic assumes the reader already has some experience with
these topics, the coverage in this chapter is provided for convenience, serving as a
quick review of relevant concepts, definitions, and identities used throughout the
topic. The presentation is intended as an informal review, rather than a thorough for-
mal treatment. Those readers interested in a more formal and encompassing coverage
of vector spaces, and linear algebra and geometry in general, may want to consult
texts such as [Hausner98] or [Anton00].
This chapter also presents some concepts from computational geometry (for exam-
ple,Voronoi regions and convex hulls) and from the theory of convex sets (separating
planes, support mappings, and Minkowski sums and differences). These concepts
are important to many of the algorithms presented in this topic.
3.1
Matrices
A
matrix
A
is an
m
×
n
rectangular array of numbers, with
m
rows and
n
columns:
⎡
⎣
⎤
⎦
=[
a
11
a
12
···
a
1
n
a
21
a
22
···
a
2
n
A
=
a
ij
]
.
.
.
.
.
.
.
a
m
1
a
m
2
···
a
mn
23
