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.

Search Nedrilad ::

Custom Search