Collision
detection and response is a very important topic in 3D video games.
Models and objects in a video game are usually made up of thousands of
polygons. The environments themselves can be in the high thousands or
millions of polygons. When detecting collision between triangles, the
operation is usually a very CPU-expensive process, even for just a
single triangle, let alone thousands upon thousands of them. What is
needed is a way to quickly detect collisions between objects, along with
other factors such as visibility determination. This is where bounding
geometry comes into play.
The idea behind
bounding geometry is that the bounding geometry serves as a very simple
representation of a more complex object. Bounding geometry is any simple
shape that surrounds an object so that the object fits inside the
bounding geometry’s volume as tightly as possible. These shapes include
spheres, boxes, ellipsoids, and so forth. An example of a bounding box
and sphere, the most common types of bounding geometry used, is shown in
Figure 1.
The need to simplify
various tests such as collision detection is extremely important in
video games because everything has to run as efficiently and effectively
as possible. This requires performing tests as fast as possible to
avoid slowing down the
CPU and to get the most out of the processing power of the machine.
This is the purpose of using bounding geometry, which is significantly
faster than working on the polygon level of models and objects.
Mathematically, a box can be tested quickly for whether it is in view or
is touching another box far faster than the triangles of a model, so
using the simplified shape is a very fast substitution.
The DirectX SDK
includes functions to create a bounding box and bounding sphere around a
piece of geometry. In this section we’ll discuss the DirectX bounding
box and bounding sphere support.
Bounding Boxes
A box can be defined
using two vectors, where the first vector stores the minimum X, Y, and Z
values for the box and the second vector stores the maximum X, Y, and Z
values. If you know the minimum X and maximum X, for example, you will
be able to know where each of the box’s corners is along the X axis. If
you also know the minimum and maximum Y and Z values, you can generate a
box out of them. To test if a point or another object intersects
(touches) the box, you can test if the point or object falls entirely
within this minimum and maximum range that defines the bounding box.
Looking at a 2D example, you can see that the object being tested falls
within both the X and Y axes of the bounding box, meaning the object is
inside of it. This is shown in Figure 2.
Objects with volume, such as another box, touch the bounding box only
if any part of it is on the surface of the bounding box or inside it.
A
box can be any size along the width, height, and depth axes, which are
defined by the two vectors that represent the box. A cube, on the other
hand, is a box that has the same value for the width, height, and depth,
forming a perfectly even shape along all axes. To represent a cube, you
only need to know the center position and the size of the cube. This
size is used for the width, height, and depth. |
To calculate the bounding box you can call the D3DXComputeBoundingBox() function. This function takes as parameters a list of points specified as D3DXVECTOR3
3D vectors, the total number of vertices in the list, the size of each
vertex, and output addresses that will store the minimum and maximum
values of the computed bounding box. The D3DXComputeBoundingBox() function has the following function prototype according to the DirectX SDK.
HRESULT D3DXComputeBoundingBox(
CONST D3DXVECTOR3 *pFirstPosition,
DWORD NumVertices,
DWORD dwStride,
D3DXVECTOR3 *pMin,
D3DXVECTOR3 *pMax
);
You can test if a ray hits the bounding box by calling the D3DXBoxBoundProbe()
function. This function takes as parameters the minimum and maximum
values of the bounding box, the position (origin) of the ray, and the
direction vector of the ray. The function prototype for the D3DXBoxBoundProbe() function is as follows according to the DirectX SDK.
BOOL D3DXBoxBoundProbe(
CONST D3DXVECTOR3 *pMin,
CONST D3DXVECTOR3 *pMax,
CONST D3DXVECTOR3 *pRayPosition,
CONST D3DXVECTOR3 *pRayDirection
);
