Graphics Reference
In-Depth Information
the AABB overlaps, as all colliding objects are guaranteed to be in those cells. The
test would thus simply read:
// Objects placed in all cells overlapped by their AABB.
// Checking object's "minimum corner" cell and up to 3 neighboring grid cells:
check object's "minimum corner" cell
if (object overlaps east cell border)
check east neighbor cell
if (object overlaps south cell border) {
check south neighbor cell
if (object overlaps east cell border)
check southeast neighbor cell
}
Four tested cells is now the worst case, and a single cell the best case. Although
this makes for the fastest test, it complicates the code for updating when objects move
(having to update up to eight cells in a 3D grid) and is likely to use more memory than
single-cell storage. In addition, collision between two objects can now be reported
multiple times and thus pair collision status must be maintained (as discussed in
Section 7.7.1).
7.1.6.2 All Tests at a Time
If instead of testing a single object at a time all objects are tested at the same time,
the single-cell placement case can be optimized utilizing the fact that object pair
checking is commutative. In other words, checking object
A
against object
B
is the
same as checking object
B
against object
A
. For example, if objects in the current grid
cell check for collision with the neighbor cell to the east, when the time comes for the
east cell to check against its neighboring cells the cell to the west of it can safely be
ignored. A consequence is that all objects that can be collided with must also test for
collisions
against
other objects. In other words, this scheme does not allow checking
just a single moving object in a static grid of objects. It is important that all possible
overlap relationships between cells be covered by the performed tests. For instance,
a common mistake is to assume that the NE-versus-SW cell relationship does not
have to be tested. However, this is a flawed assumption because two objects assigned
to cells
A
and
B
are colliding in a third cell
C
(Figure 7.6).
Returning to the case in which objects are placed on the center point, all neighbors
now do not have to be checked. It is sufficient to check half the neighbors and let
the remaining half of directionally opposing tests be covered by the commutativity
relation. The test could therefore simply read:
// Objects placed in single cell based on their bounding sphere center.
// All objects are checked for collisions at the same time, so collisions
