: 2D example of the sub division of an object
Each object is defined in its own reference frame, and a transformation matrix
(
) is applied to it to place it in the global frame. Within its local
frame, each object has a bounding box (or container) defined which has sides
parallel to the local axis planes. This container is divided up into a number
of voxels, and there also exists a matrix whose elements correspond to the
voxels. Thus matrix cell 
contains a list of the polygons that
occupy the corresponding voxel. The object's container is divided up into
voxels using the following scheme:
First the box is divided in half by a plane that is perpendicular to the
longest side of the container. Successive steps follow the same rule, and the
process terminates after M steps. If the dimensions of the matrix are
denoted by 
then the following rule holds:
M is the order of the matrix. Calculating dimensions and voxel sizes using this method provides a better spatial division that is dependent on the geometry of the object, and the order M.
The next step (in this initialization of an object) that is carried out is determining which polygons of an object occupy which voxels, and setting up the matrix appropriately.
This process is carried out once for each object (unless the object under goes a change in structure).
Bounding volume intersection testing is carried out in the global frame using
bounding boxes applied to each object. These global bounding boxes are
calculated by transforming the minimum and maximum axis values of an object's
local frame (the minimum and maximum corners of an object's container) into the
global frame, and then from this small set of values, determining global
minimum and maximum values (and thus the global bounding box). As can be seen
from figure 
this doesn't necessarily give the best bounding
volume for the object, and can result in testing of the objects for
intersection even when their containers don't interfere with each other.
Figure: Global bounding box test
The chief advantage of using bounding boxes generated in this manner is the speed with which they are calculated and can be checked for interference. Performing an exact interference test on the transformed containers would be an expensive task, and using other bounding volumes (such as a sphere), would require all the vertices of an object to be transformed, then a bounding volume calculated from the transformed points. This has to be done at every step in the simulation, including when the collision detection module is using bisection and trying to find the state when the objects in a database are just in contact. If objects only under went translation and rotation, then the use of spheres would be acceptable because they don't need to be recalculated under these conditions. However when there is scaling (and this may not be uniform scaling along all 3 axis) then they need to be recalculated.
Once it has been found that the global bounding boxes of two objects interfere, the next step is to test to see which voxels of the objects' containers are involved. Even if the global bounding box test fails to report a non-interference status when the objects' containers aren't intersecting, the next stage of the collision detection process quickly determines this fact, so the penalty for not having a better bounding volume is small.
