Graphics Reference
In-Depth Information
object. Thus, regardless of which other cells (if any) the current object overlaps all
neighboring cells and their contents must be tested for collision.
// Objects placed in single cell based on their bounding sphere center.
// Checking object's cell and all 8 neighboring grid cells:
check object's cell
check northwest neighbor cell
check north neighbor cell
check northeast neighbor cell
check west neighbor cell
check east neighbor cell
check southwest neighbor cell
check south neighbor cell
check southeast neighbor cell
This makes a total of nine cells tested (27 cells in 3D), which is not very promising.
If instead the minimum corner of the axis-aligned bounding box has been used, most
neighboring cells have to be tested only if the current object actually overlaps into
them. The pseudocode for the 2D version of this test reads:
// Objects placed in single cell based on AABB minimum corner vertex.
// Checking object's "minimum corner" cell and up to all 8 neighboring grid cells:
check object's "minimum corner" cell
check north neighbor cell
check northwest neighbor cell
check west neighbor cell
if (object overlaps east cell border) {
check northeast neighbor cell
check east neighbor cell
}
if (object overlaps south cell border) {
check southwest neighbor cell
check south neighbor cell
if (object overlaps east cell border)
check southeast neighbor cell
}
At worst, all nine cells will still have to be checked, but at best only four cells
have to be tested. This makes the minimum corner a much better feature for object
placement than the center point. On the other hand, if objects have been placed in
all cells they overlap the single object test would have to check only those exact cells
