Graphics Reference
In-Depth Information
B
A
Figure 7.6
Objects
A
and
B
are assigned to a cell based on the location of their top left-hand
corners. In this case, overlap may occur in a third cell. Thus, to detect intersection between
objects cells must be tested against their NE or SW neighbor cells.
// in the opposite direction will be handled when checking the objects
// existing in those cells.
check object's cell
check east neighbor cell
check southwest neighbor cell
check south neighbor cell
check southeast neighbor cell
This approach requires that all objects are tested, and thus these five tests cannot
be combined with any border overlap test (as was done earlier), because that would
prevent some necessary tests from occurring. For example, say object
A
does not
overlap into the east neighbor cell and that the neighbor cell is not tested against.
However, there could still be an object
B
in the east cell that overlaps into the cell to
its west (overlapping with object
A
), but because the east cell does not test against
its west neighbor any overlap between
A
and
B
would go undetected. Furthermore,
as some (but not all) collisions will be detected twice per frame this approach would
require that overlap status be recorded (for instance in a collision-pair matrix).
The case in which objects are placed in a single cell based on the minimum corner
point can be similarly simplified. Here, however, border overlap tests can be used to
minimize the number of neighboring cells checked further. This test now reads:
// Objects placed in single cell based on AABB minimum corner vertex.
// All objects are checked for collisions at the same time, so collisions
// in the opposite direction will be handled when checking the objects
// existing in those cells.
check object's "minimum corner" cell
check southwest neighbor cell
if (object overlaps east cell border)
check east neighbor cell
if (object overlaps south cell border) {
check south neighbor cell
