Bounding Spheres
A bounding sphere can be
defined as a center position and a radius, where a radius represents the
size of the sphere from the center to the outer surface. This is shown
in Figure 3.
Keep in mind that the difference between the radius and the diameter is
that the diameter is the size of the sphere from one end of the surface
to the other side as it crosses the center. The radius is essentially
half the diameter.
The
benefit of using spheres is that mathematically you can test for things
such as collisions and visibility faster than you can test boxes or
other shapes. The downside to spheres is that depending on the shape,
there can be more wasted space within the sphere’s volume, or even the
box. An example of this is shown in Figure 4, in which the same object has a box around it (left) and a sphere (right).
Because one shape
(depending on the object) can lead to more wasted space than other
shapes, using them can also be a little less accurate in various tests.
For example, in Figure 5
two objects might register collision when testing only their bounding
spheres when in reality they do not touch. There are solutions to this,
which will be discussed in the next section, “Bounding Hierarchies.”
To calculate a bounding sphere in DirectX, we can use the function D3DXComputeBoundingSphere(),
which takes as parameters a list of 3D vectors that represent the
entire model, the total number of vertices in the model, the size of
each vertex, and the output addresses that will store the center
position of the model or bounding sphere and the bounding sphere’s
radius. The D3DXComputeBoundingSphere() function has the following function prototype according to the DirectX SDK.
HRESULT D3DXComputeBoundingSphere(
CONST D3DXVECTOR3 *pFirstPosition,
DWORD NumVertices,
DWORD dwStride,
D3DXVECTOR3 *pCenter,
FLOAT *pRadius
);
You can test a ray for collision with the bounding sphere by calling the D3DXSphereBoundProbe() function, which takes as parameters the center position and radius of the sphere and the ray’s position and direction. The D3DXSphereBoundProbe() function has the following function prototype according to the DirectX SDK.
BOOL D3DXSphereBoundProbe(
CONST D3DXVECTOR3 *pCenter,
FLOAT Radius,
CONST D3DXVECTOR3 *pRayPosition,
CONST D3DXVECTOR3 *pRayDirection
);
Bounding Hierarchies
Using
one of the simple shades as bounding geometry can lead to very fast
tests such as for collision detection, but these tests are not the most
accurate in many situations. Not only can there be wasted space within
the volume of the shape, but it is difficult to determine much
information from tests on a single bounding geometry. For example, in a
first-person shooter game, what if you wanted to know if the player was
shot in the arm, leg, head, and so on so that an appropriate animation
can be played?
The solution is to use
bounding hierarchies. The simple method requires you to break your
model into pieces, each of which can have its own bounding geometry. For
example, take a 3D character model. You can place bounding boxes around
the arms, legs, feet, head, torso, hands, and so forth. This makes it
much easier to detect the specific region of impact because more
bounding geometry pieces are used in the model (see Figure 6).
The amount of detail needed determines what parts of the model have
their own bounding geometry. If you need to know which finger was hit,
you could have bounding geometry around each finger of both hands, even
if that might be overkill in most games.
Also,
you can efficiently combine a hierarchy of geometry with one large
bounding box or sphere to improve performance when you must use the
hierarchy for specific or more accurate tests. For example, you can use
the larger bounding box or sphere of a model to determine if something
is possible (e.g., possible collision, possible visibility, possible
occlusion) and then use the bounding hierarchy to obtain more accurate
results if that first test passes. This method can be very useful in
games for which you must have more detailed information (such as a
fighting game) if you don’t want to do those more accurate tests unless
they are necessary.
If you do not need to go as
far as bounding geometry hierarchies, you can take just a bounding box
and sphere and use those. For example, you can use the very fast
bounding sphere to determine if something is possible and then test the
bounding box if the first test passes to get slightly more accurate
results. If that is accurate enough for the application you are
developing, you could stop there and assume that whatever you are
testing is true.
