Game Development Reference
In-Depth Information
This is a very common way to represent a plane: the position is any location on the
plane, and the direction points out at right angles to the plane. The same plane can be
generated if we reverse the direction: it would still be at right angles to the plane but
facing in the opposite direction. The fact that the direction vector points out from one
side of the plane means that we can distinguish one side from the other. Any object is
either on the side where the direction is pointing or on the other side. This distinction
allows us to select the appropriate child node in the BSP.
To determine which side of the plane an object lies on, we make use of the geo-
metric interpretation of the scalar product given in chapter 2. Recall that the scalar
product allows us to find the component of one vector in the direction of another:
c
=
( p o
p P )
·
d P
where p o is the position of the object we are interested in (we normally use the po-
sition of the center of its bounding volume), p P is the position of any point on the
plane (i.e., the point we are using to store the plane), and d P is the direction in which
the plane is facing.
If c is positive, then the object lies on the side of the plane to which its direction
points. If it is negative, then the object lies on the opposite side. If c is zero, then it
lies exactly on the plane. The direction vector, d P , should be a normalized vector, in
which case
gives the distance of the object from the plane.
Assuming that the object has a spherical bounding volume, we can determine
whether it is completely on one side of the plane by checking if
|
c
|
|
c
|
r o
where r o is the radius of the bounding volume for the object.
We can build a BSP tree from nodes that contain a plane and two child nodes:
struct BSPNode
{
Plane plane;
BSPNode front;
BSPNode back;
};
In practice each child node ( front and back ) can hold either another node or a set
of objects. Unlike for bounding volume hierarchies, it is not normal to have only one
object at each leaf of the tree.
In the same way as we saw for the bounding sphere hierarchy, this could be im-
plemented in C++ as
typedef vector<Object*> BSPObjectSet;