Game Development Reference
In-Depth Information
y
y
(a)
(b)
x
x
Figure 8.1. A bounding volume aligned to the coordinate axes is usually a poor choice
for most vertex distributions.
distributed in such a way that the box enclosing them contains a lot of empty
space. As Figure 8.1(b) demonstrates, choosing a bounding box that is aligned to
the natural axes of the data set can greatly reduce the size of the box. We present
a method for determining the natural alignment in the next section.
8.1.1 Principal Component Analysis
We can reduce the size of each of our bounding volumes by determining a coor-
dinate system that is naturally aligned to the set of vertices belonging to each tri-
angle mesh. We can calculate these coordinate axes by using a statistical method
called principal component analysis . Principal component analysis allows us to
find a coordinate space in which a set of data composed of multiple variables,
such as the x , y , and z coordinates stored in an array of vertex positions, can be
separated into uncorrelated components. The primary principal component of the
data is represented by the direction in which the data varies the most.
To determine the natural coordinate system for an arbitrary set of N vertices
12
PP
,
,
, where
,
P
=
,,
yz
, we first calculate the mean (average) position
x
N
i
i
i
i
m using the formula
1
N
m
=
P .
(8.1)
i
N
i
=
1
We then construct a 3
×
3
matrix C called the covariance matrix as follows.