Christer Ericson Real Time Collision Detection en 324 386

Chapter 7
Spatial Partitioning
Recall from Chapter 2 that pairwise processing is expensive, and that the idea of
broad-phase processing is to restrict pairwise tests to objects near enough that they
could possibly intersect. Spatial partitioning techniques provide broad-phase process-
ing by dividing space into regions and testing if objects overlap the same region of
space. Because objects can only intersect if they overlap the same region of space, the
number of pairwise tests is drastically reduced. This chapter explores three types of
spatial partitioning methods: grids, trees, and spatial sorting.
7.1 Uniform Grids

A very effective space subdivision scheme is to overlay space with a regular grid.
This grid divides space into a number of regions, or grid cells, of equal size. Each
object is then associated with the cells it overlaps. As only objects overlapping a
common cell could possibly be in contact, in-depth tests are only performed against
those objects found sharing cells with the object tested for collision. The farther
apart two objects are the less likely they overlap the same cells, and with an appro-
priately spaced grid only objects very likely to overlap would be subject to further
pairwise tests.
Thanks to the uniformity of the grid, accessing a cell corresponding to a particular
coordinate is both simple and fast: the world coordinate values are simply divided
by the cell size to obtain the cell coordinates. Given the coordinates to a specific cell,
neighboring cells are also trivial to locate. This conceptual as well as implementational
simplicity has made grids both a good and popular choice for space subdivision.
Grids are known by many other names, including regions, buckets, sectors, and
zones.
285
286 Chapter 7 Spatial Partitioning
(a) (b) (c) (d)
Figure 7.1 Issues related to cell size. (a) A grid that is too fine. (b) A grid that is too coarse
(with respect to object size). (c) A grid that is too coarse (with respect to object complexity).
(d) A grid that is both too fine and too coarse.
7.1.1 Cell Size Issues

In terms of performance, one of the most important aspects of grid-based methods
is choosing an appropriate cell size. There are four issues related to cell size that can
hamper performance (Figure 7.1).
1. The grid is too fine. If the cells are too small, a large number of cells must be updated
with associativity information for the object, which will take both extra time and
space. The problem can be likened to fitting elephant-size objects into matchbox-
size cells. Too fine of a grid can be especially bad for moving objects, due to the
number of object links that must be both located and updated.
2. The grid is too coarse (with respect to object size). If the objects are small and the grid
cells are large, there will be many objects in each cell. As all objects in a specific cell
are pairwise tested against each other, a situation of this nature can deteriorate to
a worst-case all-pairs test.
3. The grid is too coarse (with respect to object complexity). In this case, the grid cell
matches the objects well in size. However, the object is much too complex, affect-
ing the pairwise object comparison. The grid cells should be smaller and the objects
should be broken up into smaller pieces, better matching the smaller grid cell size.
4. The grid is both too fine and too coarse. It is possible for a grid to be both too fine and
too coarse at the same time. If the objects are of greatly varying sizes, the cells can
be too large for the smaller objects while too small for the largest objects.
Case 4 is addressed in more detail in Section 7.2, on hierarchical grids. Taking the
remaining cases into consideration, cell size is generally adjusted to be large enough
(but not much larger) to fit the largest object at any rotation. This way, the number
of cells an object overlaps is guaranteed to be no more than four cells (for a 2D grid;
eight for a 3D grid). Having objects overlap only a small number of cells is important.
7.1 Uniform Grids 287
It limits the amount of work required to insert and update objects in the grid, and to
perform the actual overlap tests.
Under the normal assumption of frame-to-frame noninterpenetration of objects,
with cells and objects being almost the same size the maximum number of objects in
a cell is bounded by a small constant. Consequently, resolving collisions within a cell
using an all-pairs approach results in only a small number of pairwise object tests.
With cell size selected, grid dimensions are determined by dividing the diameter
of the simulation space by the diameter of the cells. If memory use for storing the
grid itself is a concern, the cell size can be increased at the cost of possible decreased
performance. However, more grid cells do not necessarily have to translate into use
of more memory (more on this in the following sections).
In ray tracing a popular method for determining the grid dimensions has been the
n1/3 rule: given n objects, divide space into a k × k × k grid, with k = n1/3 . The ratio of
cells to objects is referred to as the grid density. Recent results indicate that a density
of 1 is not very good, and a much higher density is suggested [Havran99].
It is sometimes claimed that it is difficult to set a near-optimal cell size, and that
if cell size is not correctly set grids become expensive in terms of performance or
prohibitively memory intensive (see, for example, [Cohen95]). Practical experience
suggests that this is not true. In fact, for most applications although it is easy to pick
bad parameter values it is equally easy to pick good ones.
7.1.2 Grids as Arrays of Linked Lists

The natural way of storing objects in a grid is to allocate an array of corresponding
dimension, mapping grid cells to array elements one-to-one. To handle the case
of multiple objects ending up in a given cell, each array element would point to a
linked list of objects, or be NULL if empty. If objects are inserted at the head of
the list, insertion is trivially O(1). For a single-linked list, updating and deletion of
an arbitrary object is O(n). However, updating and deletion can also be made O(1)
by using a double-linked list and having the objects maintain direct pointers to the
linked-list entries of all cells the objects are in.
The easiest way of maintaining these linked lists is to embed the links within the
objects themselves. When the maximum number of cells overlapped by an object has
been limited by an appropriate choice of cell size, object-embedded links are a good
solution that both improves data cache coherency and simplifies the code by avoiding
the need for a specific system for allocation of link cells.
A drawback with using a dense array of this type is that for large grids just storing
the list headers in each grid cell becomes prohibitive in terms of memory require-
ments. Making the grid cells larger is not a good solution, in that this will lower
performance in areas in which objects are clustered — the most important case to
handle. The next few sections present some alternative grid representations with
lower memory requirements.
7.1.3 Hashed Storage and Infinite Grids

Perhaps the most effective alternative to using a dense array to store the grid is to
map each cell into a hash table of a fixed set of n buckets (Figure 7.2). In this scheme,
the buckets contain the linked lists of objects. The grid itself is conceptual and does
not use any memory. An example of a simple multiplicative hash function, mapping
a tuple consisting of the cell position coordinates into a bucket index, follows.
// Cell position
struct Cell {
Cell(int32 px, int32 py, int32 pz) { x = px; y = py; z = pz; }
int32 x, y, z;
};
#define NUM_BUCKETS 1024
// Computes hash bucket index in range [0, NUM_BUCKETS-1]

int32 ComputeHashBucketIndex(Cell cellPos)
{
const int32 h1 = 0x8da6b343; // Large multiplicative constants;
const int32 h2 = 0xd8163841; // here arbitrarily chosen primes
const int32 h3 = 0xcb1ab31f;
int32 n = h1 * cellPos.x + h2 * cellPos.y + h3 * cellPos.z;
n = n % NUM_BUCKETS;
if (n < 0) n += NUM_BUCKETS;
return n;
}
Note that it is surprisingly easy to construct hash functions that although perhaps
not bad, are just not very good (and there are no guarantees the previous hash
function is particularly strong). For information on constructing more sophisticated
hash functions see [Binstock96], [Jenkins97], or [Knuth98].
Performing a hash mapping of this type has the added benefit of allowing the grid
to be unbounded in size. The mapping function wraps world coordinates into a finite
number of cells (thereby making boundary checks for accessing neighboring cells
unnecessary). Although the world may consist of an infinite amount of cells, only a
finite number of them are overlapped by objects at a given time. Thus, the storage
required for a hashed grid is related to the number of objects and is independent of
the grid size.
To avoid having to perform a hash table lookup to find out that a cell is in fact
empty and is not in the table, a dense bit array with 1 bit per cell in the grid can be
used as a quick pretest indicator of whether a cell is empty or not. (Of course, this
optimization is only possible by keeping the grid fixed in size.)
index = hash(x,y) mod n
index: 0 1 n–1
Figure 7.2 A (potentially infinite) 2D grid is mapped via a hash function into a small number
of hash buckets.
To handle collisions (the mapping of two keys to the same bucket) in the hash
table, two methods are traditionally used: open hashing and closed hashing. In open
hashing (also known as separate chaining), each bucket is allowed to contain a linked
list of records. When a new entry is added to the hash table, the bucket index is
computed and the entry is added at the start of the linked list of the corresponding
bucket. Each of the stored records contains a key along with associated data. In this
case, the key would be the original cell coordinates and the data would be the head
of a linked list of objects contained in that cell. As this representation ends up with
buckets containing lists of lists, the code for updating the data structure as objects
are added or deleted from a grid cell and its corresponding bucket becomes slightly
more complicated than desired.
In contrast, closed hashing (or open addressing) stores records directly within the
hash buckets themselves. When the computed bucket index of a new entry points
at an occupied bucket, new bucket indices are computed (in a consistent manner)
until an empty bucket is found and the record is inserted. The simplest such method,
known as linear probing, simply tries subsequent buckets until one is found, wrapping
around at the end of the hash table if necessary. Although linear probing has good
cache behavior, it performs poorly as the hash table fills. Using linear probing, hash
table utilization should not be much higher than 50% for good performance. Other,
better but more complicated, probing approaches exist. See [Knuth98] for a detailed
analysis of the behavior of linear probing and alternative probing methods.
A problem with closed hashing is that objects cannot be directly deleted from the
hash table, but must be lazily deleted to avoid having subsequent searches fail. A
lazy deletion involves marking the slot so that it is free for an insertion yet is not
considered empty, which would (incorrectly) terminate a search of the hash table for
some other object.
A third solution is to use the open hashing method but exclude the first-level
linked list and have the buckets directly contain a list of objects. This results in very
simple code with low overhead, but the lack of a stored key introduces two problems
that must be addressed. First, when performing tests against the content of a specific
cell it is now possible its bucket will contain both objects of interest as well as those
from other cells, which happened to map to the same bucket. To avoid spending time
peforming expensive narrow-phase tests on distant objects, in-depth tests must be
preceded by a bounding volume test to cull irrelevant objects. Such culling is a good
overall strategy anyway, in that nonoverlapping objects can share buckets regardless
of hash table representation.
Second, a related problem occurs when several cells are tested by the same query.
If two or more of the cells have been aliased to the same nonempty hash bucket, its
content will be checked several times for the same query. Fortunately, this seemingly
serious problem is easily solved by a time-stamping method in which hash buckets
are labeled each time they are queried. The label consists of a unique identifier that
changes for each query made. During a query, if a hash bucket is found labeled with
the current identifier the bucket has already been examined and can be ignored. Time
stamping is further described in Section 7.7.2.
A different approach to extending a grid when an object moves out of the region
covered by the grid is described in [Reinhard00]. Separating the grid into both logical
and physical parts, the logical grid is allowed to grow as the object moves outside the
grid. However, the extra cells thus introduced are mapped onto the existing physical
grid through a toroidal wrapping of logical cell coordinates modulo the size of the
physical grid. The size of the logical grid now determines whether an object near
the physical grid boundary must consider collisions against objects in its toroidal
neighbor cells on the opposite side of the grid.
7.1.4 Storing Static Data

When grid data is static, such as when it represents world polygon data instead of
dynamic objects, the need for a linked list can be removed altogether [Haines99].
Rather than storing the data in linked lists, the idea is to store all cell data in a single
contiguous array. Figure 7.3 illustrates the same grid with the data stored using linked
lists (a) and into an array (b).
The grid data can be assigned to an array in a two-pass process. In the first pass,
the static data is iterated over, but instead of assigning the data to overlapped grid
cells only a counter per cell is incremented when data would normally have been
assigned to the cell. After all data is processed, counts have thereby been obtained
for all n grid cells, with ak indicating the number of objects in cell Ck . At this point an
array of m elements
m= ai
0≤i<n
G F C A
H B G F C A H B I E D
I E D
(a) (b)
Figure 7.3 (a) A grid storing static data as lists. (b) The same grid with the static data stored
into an array.
is allocated. Each cell is also associated with an index number bk into this array,
where
b0 = 0
bk = bk−1 + ak−1 .
The data is then in a second pass iterated over again. This time, the ak objects over-
lapping cell Ck are stored with help from the associated index number into the array
at indices bk through bk + ak − 1. Because all data for each cell is stored contigu-
ously in the array, and because no links are needed between the contiguous entries,
the resulting array-based grid uses less memory and is more cache efficient than a
representation based on linked lists.
7.1.5 Implicit Grids

An alternative to storing a grid explicitly is to store it implicitly, as the Cartesian
product of two or more arrays. That is, the grid is now represented by two arrays
(three in 3D), wherein one array corresponds to the grid rows and the other to the
grid columns. As before, each array element points to a linked list of objects. An object
is inserted into the grid by adding it to the lists of the grid cells it overlaps, for both the
row and column array (Figure 7.4). Overlap testing for an object is now performed
by checking to see if the object overlaps another object in both the row cells and the
column cells it straddles.
Compared to the dense array representation, this scheme can result in either fewer
or more list insertions. If the object is fully contained within a single grid cell of the
implicit grid, it is inserted into two lists (one row and one column list), whereas in
the previous scheme it would have been inserted in just one list. However, if the
object were to overlap, say, 4 × 4 grid cells, it would be inserted into eight lists for
the implicit grid (four row lists and four column lists) instead of 16, improving on the
worst case. When objects overlap few cells the overlap test for this approach becomes
more costly, not only because there are more objects in the lists that are being tested
but because (many) more lists have to be checked.
C
C
E E D C
D
B D B
A A
D D E E B
A C
Figure 7.4 A 4 × 5 grid implicitly defined as the intersection of 9 (4 + 5) linked lists. Five
objects have been inserted into the lists and their implied positions in the grid are indicated.
4 11000
3
1 01010
00100
2
0 00101
10000 00010 00110 00101 01001
Figure 7.5 A 4 × 5 grid implicitly defined as the intersection of 9 (4 + 5) bit arrays. Five
objects have been inserted into the grid. The bit position numbers of the bits set in a bit array
indicate that the corresponding object is present in that row or column of the grid.
A more novel storage approach is to allocate, for each row and column of the grid,
a bit array with 1 bit for each object in the world. Placing an object into the grid now
simply involves setting the bit in the bit array in both the row and column bit arrays
for the grid cell corresponding to the object (Figure 7.5).
An object exists in a grid cell if and only if the bit arrays of the row and column of
the cell both have the bit corresponding to that object set. Testing for the presence of
objects in a cell is therefore as simple as performing a bitwise AND operation on the
two bit arrays.
When the query object overlaps several grid cells, the distributive properties of
bitwise operators can be used to reduce the amount of computation needed. For
example, assume an object overlaps rows ri and ri+1 and columns cj and cj+1 . The
objects potentially intersected are given by the union of all bits set in the bitwise
intersection of each of the four grid cells (ri , cj ), (ri , cj+1 ), (ri+1 , cj ), and (ri+1 , cj+1 ). If
r[i] and c[j] correspond to the bit masks of row cell i and column cell j, respectively,
this method gives the resulting union b of bits as
b = (r[i] & c[j]) | (r[i] & c[j+1]) | (r[i+1] & c[j]) | (r[i+1] & c[j+1]);
However, the distributive properties of the bitwise operators allow this expression
to be more efficiently computed as
b = (r[i] | r[i+1]) & (c[j] | c[j+1]);
This rewrite generalizes to an arbitrary number of cells overlapped, so that the

bitwise OR of all overlapped row cells and of all column cells is first computed. Then
the bitwise AND between the resulting bit fields gives the final result. This method
is illustrated by the following code.
// Define the two global bit arrays

const int NUM_OBJECTS_DIV_32 = (NUM_OBJECTS + 31) / 32; // Round up
int32 rowBitArray[GRID_HEIGHT][NUM_OBJECTS_DIV_32];
int32 columnBitArray[GRID_WIDTH][NUM_OBJECTS_DIV_32];
void TestObjectAgainstGrid(Object *pObject)

{
// Allocate temporary bit arrays for all objects and clear them
int32 mergedRowArray[NUM_OBJECTS_DIV_32];
int32 mergedColumnArray[NUM_OBJECTS_DIV_32];
memset(mergedRowArray, 0, NUM_OBJECTS_DIV_32 * sizeof(int32));
memset(mergedColumnArray, 0, NUM_OBJECTS_DIV_32 * sizeof(int32));
// Compute the extent of grid cells the bounding sphere of A overlaps.

// Test assumes objects have been inserted in all rows/columns overlapped
float ooCellWidth = 1.0f / CELL_WIDTH;
int x1 = (int)floorf((pObject->x - pObject->radius) * ooCellWidth);
int x2 = (int)floorf((pObject->x + pObject->radius) * ooCellWidth);
int y1 = (int)floorf((pObject->y - pObject->radius) * ooCellWidth);
int y2 = (int)floorf((pObject->y + pObject->radius) * ooCellWidth);
assert(x1 >= 0 && y1 >= 0 && x2 < GRID_WIDTH && y2 < GRID_HEIGHT);
// Compute the merged (bitwise-or’ed) bit array of all overlapped grid rows.
// Ditto for all overlapped grid columns
for (int y = y1; y <= y2; y++)
for (int i = 0; i < NUM_OBJECTS_DIV_32; i++)

mergedRowArray[i] |= rowBitArray[y][i];
for (int x = x1; x <= x2; x++)
for (int i = 0; i < NUM_OBJECTS_DIV_32; i++)
mergedColumnArray[i] |= columnBitArray[x][i];
// Now go through the intersection of the merged bit arrays and collision test
// those objects having their corresponding bit set
for (int i = 0; i < NUM_OBJECTS_DIV_32; i++) {
int32 objectsMask = mergedRowArray[i] & mergedColumnArray[i];
while (objectsMask) {
// Clears all but lowest bit set (eg. 01101010 -> 00000010)
int32 objectMask = objectsMask & (objectsMask - 1);
// Get index number of set bit, test against corresponding object
// (GetBitIndex(v) returns log_2(v), i.e. n such that 2∧ n = v)
int32 objectIndex = GetBitIndex(objectMask) + i * 32;
TestCollisionAgainstObjectNumberN(objectIndex);
// Mask out tested object, and continue with any remaining objects
objectsMask ∧ = objectMask;
}
}
}
A simplified version of implicit grids using bit arrays can be used as a coarse
broad-phase rejection method. Instead of having a bit array indicating exactly what
objects are in each row and column of the grid, a single bit can be used to indi-
cate the presence of an object in a row or column. If no bit is set for the rows and
columns an object overlaps, the object cannot be in overlap and no further testing is
necessary.
Table 7.1 illustrates memory use for three different grid representations: the implicit
grid using bit arrays, a dense array (with double-linked lists), and a sparse array (also
using double-linked lists). Up to roughly 1,000 objects and a grid size of 100 × 100,
the implicit bit grid uses less memory than the other two representations. The implicit
bit grid also uses memory in a cache-friendly way and is overall a very efficient spatial
partitioning method.
7.1.6 Uniform Grid Object-Object Test

As mentioned earlier, grid cell sizes are usually constrained to be larger than the
largest object. This way, an object is guaranteed to overlap at most the immediately
neighboring cells, thereby greatly simplifying the overlap testing code. Still, a few
key issues remain when it comes to assigning objects to cells and performing the
Table 7.1 Memory use (in bytes) for three different grid representations: implicit grid (with bit arrays),
dense array (with double-linked list), and a sparse array (with double-linked list).
Grid size (m × n)
10 × 10 50 × 50 100 × 100 500 × 500

10 40 200 400 2,000
100 260 1,300 2,600 13,000 Implicit grid (bit arrays):
bytes = objects/8(m + n)
Objects in grid
1,000 2,500 12,500 25,000 125,000

10,000 25,000 125,000 250,000 1,250,000
10 480 10,080 40,080 1,000,080
100 1,200 10,800 40,800 1,000,800 Dense array (double-linked list):
bytes = 4mn + objects · (4 + 4)
1,000 8,400 18,000 48,000 1,008,000
10,000 80,400 90,000 120,000 1,080,000
10 240 560 960 4,160
100 1,680 2,000 2,400 5,600 Sparse array (double-linked list):
bytes = 4(m + n) + objects · (4 · 2 + 4 · 2)
1,000 16,080 16,400 16,800 20,000
10,000 160,080 160,400 160,800 164,000
object-object tests. Should objects be placed in just one representative cell or all cells
they overlap? If just one cell, what object feature should be used to determine which
cell the object goes into? The next two sections look at these issues in the context of
how the test queries are issued: if they are issued one at a time (allowing objects to
move between successive tests) or if they are all issued simultaneously.
7.1.6.1 One Test at a Time

Consider the case in which objects are associated with a single cell only. When a given
object is associated with its cell, in addition to testing against the objects associated
with that cell additional neighboring cells must also be tested. Which cells have to
be tested depends on how objects can overlap into other cells and what feature has
been used to associate an object with its cell. The choice of feature generally stands
between the object bounding sphere center and the minimum (top leftmost) corner
of the axis-aligned bounding box.
If objects have been placed with respect to their centers, any object in the neighbor-
ing cells could overlap a cell boundary of this cell and be in collision with the current
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
}
if (object overlaps south cell border) {
if (object overlaps east cell border)
}
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
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:
}
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
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
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.

}
When testing neighboring cells, range checking of grid coordinates can be avoided
by placing a layer of sentinels (dummy cells) around the border of the grid.
7.1.7 Additional Grid Considerations

Some issues relevant to efficient implementations remain. First, the presentation
given here has implied that grids are kept from frame to frame and are incrementally
updated. Although this is a good approach in general, arguments can also be made for
a simpler approach in which the grid is simply cleared and all objects are readded from
scratch each frame. For example, if most or all objects move, the latter operation may
turn out cheaper than trying to update the grid data structure. Rebuilding the grid each
frame also typically requires simpler data structures, which tends to reduce memory
requirements (such as single-linked lists instead of double-linked lists). Readding all
objects each frame also means objects can be tested as they are added, avoiding the
potential problem of getting both A-collides-with-B and B-collides-with-A reported.
A second thing to keep in mind is that not all objects have to be added to the grid
at all times. When testing distinct collision groups against each other, the objects of
the first group can be directly added to the grid. Then, when testing the objects of the
second group against the grid they do not have to be added to the grid at all. They
only have to be used as query objects. An example of such a scenario is a group of
enemy objects and another group of player bullets.
Last, it is worthwhile considering grid cell volumes and cell orientations different
from those explored here. For instance, assume the grid is primarily used for per-
forming line segment queries against a given set of objects in the plane (as discussed
further in Section 7.4.2). Because lines at an angle may pass through more cells than
do horizontal or vertical lines, it would be possible to have two grids, both containing
the same set of objects but one grid at a 45-degree relative orientation to the other.
Based on the orientation of a given line segment, the appropriate grid can now be
used for the intersection query to improve efficiency.
Similarly, compare the regular uniform grid and the staggered hexagonal-like grid
cell arrangement shown in Figure 7.7. Assume the spherical objects A and B are at
most half the size of the grid cell side, are assigned to a single cell, and are tested
one at a time. In this scenario, if the objects are placed using their centers A must
check collisions against nine cells whereas B would have to check against just seven
cells. If instead A and B were boxes, assigned using the top left-hand corner, A would
have to test against five cells (center, east, south, southeast, and either northwest or
southwest) and B only four cells (center, east, southwest, and southeast).
A B
(a) (b)
Figure 7.7 (a) In a regular grid, grid cell A has eight neighbors. (b) In a hexagonal-type grid,
grid cell B has just six neighbors.
7.2 Hierarchical Grids

The most significant problem with uniform grids is their inability to deal with objects
of greatly varying sizes in a graceful way. When objects are much larger than the grid
cell size and end up overlapping many cells, updating the position of a moving object
becomes very expensive. If the cell size is adjusted to hold the larger objects, the grid
becomes less spatially discriminatory as more small objects now end up in the same
cell, with loss of performance as a result. Fortunately, this size problem can effectively
be addressed by the use of hierarchical grids (or hgrids), a grid structure particularly
well suited to holding dynamically moving objects.
The hierarchical grid, as described here, consists of a number of grids of vary-
ing cell sizes, all overlapping to cover the same space. Depending on use, these
grids can be either 2D or 3D. Given a hierarchy containing n levels of grids and let-
ting rk represent the size of the grid cells at level k in the hierarchy, the grids are
arranged in increasing cell size order, with r1 < r2 < . . . < rn . Level 1 is the low-
est level, and level n is the highest level. The number of levels does not have to
be fixed.
To facilitate fast insert and delete operations, objects are inserted into a single
cell on just one of the levels. As the objects can still extend into other cells on that
level, to minimize the number of neighboring cells that have to be tested for colli-
sions objects are inserted into the hgrid at the level where the cells are large enough
to contain the bounding volume of the object. Given an object P, this level L is
denoted L = Level(P). This way, the object is guaranteed to overlap at most four
cells (or eight, for a 3D grid). At this point, the object is inserted into the cell in
which its center (based on the object bounding sphere) or top left-hand position
(based on the object AABB) is in. An example of an hgrid of this type is shown in
Figure 7.8.
The grid cells can assume any relative size and should ideally be selected with
respect to existing object sizes. In practice, a simple procedure for setting up the
7.2 Hierarchical Grids 301
5
4
3 B D
2 F
1 A C E
A B C D E F
Figure 7.8 A small 1D hierarchical grid. Six objects, A through F, have each been inserted in
the cell containing the object center point, on the appropriate grid level. The shaded cells are
those that must be tested when performing a collision check for object C.
hierarchy works well. Let the cells at level 1 just encompass the smallest objects. Then
successively double the cell size so that cells of level k + 1 are twice as wide as cells
of level k. Repeat the doubling process until the highest-level cells are large enough
to encompass the largest objects. In general, this setup serves well to minimize the
number of cells an object overlaps. It is still possible to do better in specific instances,
however. For instance, if there are only two object sizes clearly two grid levels
suffice.
Testing whether an arbitrary object A is in collision with objects stored in the hgrid
is done by traversing through all hgrid levels. At each level, A is tested against not only
those grid cells its bounding volume overlaps but those neighboring cells that could
have objects extending into the cells that are overlapped (as discussed in Section
7.1.6). Note that it is not sufficient to check just the immediately neighboring cells to
the cell the object is in. A large object, when checked against the grid, would cover a
lot of cells at the lowest level and not just the immediate neighborhood.
If not just a single object, but all n objects are tested at the same time, testing does
not have to proceed over all hgrid levels. Instead, each object can start testing from
its insertion level. This follows, as smaller objects will test against the grid levels of
larger objects.
Overall, the hgrid structure is not much different from a tree structure, such as an
octree, implemented using arrays. However, one key feature that sets it apart from
the tree structures is the lack of a tree “top.” That is, the hgrid corresponds to just
the last few levels of the tree. The top levels of a tree rarely contain any objects and
are simply traversed just to reach the lower levels at which the objects reside. Hgrids
avoid these empty levels and gain extra speed in doing so.
To speed up the collision testing further, it is worthwhile keeping track of the total
number of objects on each grid level. Levels that contain no objects can then be
excluded from testing.
Hgrids can be very memory expensive when each grid level is allocated as a dense
array. For this reason they are best implemented using hashed storage, as described
in Section 7.1.3.
7.2.1 Basic Hgrid Implementation

This section outlines a simple and straightforward implementation of an hgrid. The
hash table approach used is open hashing without the use of keys. Consequently, both
bounding volume tests as well as time stamping (Section 7.7.2) must be used to avoid
processing irrelevant and already processed data. The hgrid is assumed to have the
following minimal structure:
struct HGrid {
uint32 occupiedLevelsMask; // Initially zero (Implies max 32 hgrid levels)
int objectsAtLevel[HGRID_MAX_LEVELS]; // Initially all zero
Object *objectBucket[NUM_BUCKETS]; // Initially all NULL
int timeStamp[NUM_BUCKETS]; // Initially all zero
int tick;
};
It is assumed that objects are inserted into the hgrid based on their bounding
spheres. For the sake of simplicity, the given code links objects within a bucket using
single-linked lists, with the list pointer embedded in the object. Use of a double-
linked list would allow removal in O(1) time, instead of O(n) time. Associating each
hgrid cell with an array (of object pointers) also allows removal in O(1) time. The latter
option requires some bookkeeping to handle the arrays overflowing, but is overall
a faster and more cache-friendly option. Let the object representation contain the
following variables.
struct Object {
Object *pNextObject; // Embedded link to next hgrid object
Point pos; // x, y (and z) position for sphere (or top left AABB corner)
float radius; // Radius for bounding sphere (or width of AABB)
int bucket; // Index of hash bucket object is in
int level; // Grid level for the object
... // Object data
};
Cells are here assumed to be square (cubical for a 3D hgrid). The ratio of the
diameter of the largest sphere that goes into a cell at a particular level with respect to
the cell side size is given by:
const float SPHERE_TO_CELL_RATIO = 1.0f/4.0f; // Largest sphere in cell is 1/4*cell size

The smaller the ratio is, the fewer cells must be examined at a given level, on
average. However, it also means that the average number of objects per cell increases.
An appropriate ratio is application specific. When traversing from level to level, the
grid cell side increases by the following factor:
const float CELL_TO_CELL_RATIO = 2.0f; // Cells at next level are 2*side of current cell
Adding an object into the hgrid now can be done as follows.
void AddObjectToHGrid(HGrid *grid, Object *obj)

{
// Find lowest level where object fully fits inside cell, taking RATIO into account
int level;
float size = MIN_CELL_SIZE, diameter = 2.0f * obj->radius;
for (level = 0; size * SPHERE_TO_CELL_RATIO < diameter; level++)
size *= CELL_TO_CELL_RATIO;
// Assert if object is larger than largest grid cell

assert(level < HGRID_MAX_LEVELS);
// Add object to grid square, and remember cell and level numbers,
// treating level as a third dimension coordinate
Cell cellPos((int)(obj->pos.x / size), (int)(obj->pos.y / size), level);
int bucket = ComputeHashBucketIndex(cellPos);
obj->bucket= bucket;
obj->level = level;
obj->pNextObject = grid->objectBucket[bucket];
grid->objectBucket[bucket] = obj;
// Mark this level as having one more object. Also indicate level is in use
grid->objectsAtLevel[level]++;
grid->occupiedLevelsMask |= (1 << level);
}
Removing an object from the hgrid is done in a corresponding manner.
void RemoveObjectFromHGrid(HGrid *grid, Object *obj)

{
// One less object on this grid level. Mark level as unused if no objects left
if (--grid->objectsAtLevel[obj->level] == 0)
grid->occupiedLevelsMask &= ∼(1 << obj->level);
// Now scan through list and unlink object ’obj’

int bucket= obj->bucket;
Object *p = grid->objectBucket[bucket];
// Special-case updating list header when object is first in list
if (p == obj) {
grid->objectBucket[bucket] = obj->pNextObject;
return;
}
// Traverse rest of list, unlinking ’obj’ when found
while (p) {
// Keep q as trailing pointer to previous element
Object *q = p;
p = p->pNextObject;
if (p == obj) {
q->pNextObject = p->pNextObject; // unlink by bypassing
return;
}
}
assert(0); // No such object in hgrid
}
Checking an object for collision against objects in the hgrid can be done as follows.
It is assumed that nothing is known about the number of objects tested at a time,
and thus all grid levels are traversed (except when it can be concluded that there are
no more objects to be found in the grid).
// Test collisions between object and all objects in hgrid

void CheckObjAgainstGrid(HGrid *grid, Object *obj,
void (*pCallbackFunc)(Object *pA, Object *pB))
{
float size = MIN_CELL_SIZE;
int startLevel = 0;
uint32 occupiedLevelsMask = grid->occupiedLevelsMask;
Point pos = obj->pos;
// If all objects are tested at the same time, the appropriate starting
// grid level can be computed as:
// float diameter = 2.0f * obj->radius;
// for ( ; size * SPHERE_TO_CELL_RATIO < diameter; startLevel++) {
// size *= CELL_TO_CELL_RATIO;
// occupiedLevelsMask >>= 1;
// }
// For each new query, increase time stamp counter

grid->tick++;
for (int level = startLevel; level < HGRID_MAX_LEVELS;

size *= CELL_TO_CELL_RATIO, occupiedLevelsMask >>= 1, level++) {
// If no objects in rest of grid, stop now
if (occupiedLevelsMask == 0) break;
// If no objects at this level, go on to the next level
if ((occupiedLevelsMask & 1) == 0) continue;
// Compute ranges [x1..x2, y1..y2] of cells overlapped on this level. To

// make sure objects in neighboring cells are tested, by increasing range by
// the maximum object overlap: size * SPHERE_TO_CELL_RATIO
float delta = obj->radius + size * SPHERE_TO_CELL_RATIO + EPSILON;
float ooSize = 1.0f / size;
int x1 = (int)floorf((pos.x - delta) * ooSize);
int y1 = (int)floorf((pos.y - delta) * ooSize);
int x2 = (int) ceilf((pos.x + delta) * ooSize);
int y2 = (int) ceilf((pos.y + delta) * ooSize);
// Check all the grid cells overlapped on current level

for (int x = x1; x <= x2; x++) {
for (int y = y1; y <= y2; y++) {
// Treat level as a third dimension coordinate
Cell cellPos(x, y, level);
int bucket = ComputeHashBucketIndex(cellPos);
// Has this hash bucket already been checked for this object?
if (grid->timeStamp[bucket] == grid->tick) continue;
grid->timeStamp[bucket] = grid->tick;
// Loop through all objects in the bucket to find nearby objects

Object *p = grid->objectBucket[bucket];
while (p) {
if (p != obj) {
float dist2 = Sqr(pos.x - p->pos.x) + Sqr(pos.y - p->pos.y);
if (dist2 <= Sqr(obj->radius + p->radius + EPSILON))
pCallbackFunc(obj, p); // Close, call callback function
}
p = p->pNextObject;
}
}
}
} // end for level
}
When, as here, a callback is used to call a function to handle two colliding objects
it is important that the callback function not change the hgrid data structure itself.
Because CheckObjAgainstGrid() is in the middle of operating on the data structure,
such changes would cause reentrancy problems, leading to missed collisions at best
and crashes at worst.
7.2.2 Alternative Hierarchical Grid Representations

Even though the hgrid is a great improvement over the basic nonhierarchical grid, a
problem remains. When objects are tested one at a time, a large object could cover a
lot of cells on the lowest levels, making for an expensive test in that it is intersected
against the contents of all of these cells. Two hgrid schemes that address this problem
are given in [Mirtich96b, Mirtich97], by whom the hgrid is referred to as a hierarchical
spatial hash table.
The first scheme is to insert the objects in order of decreasing size, such that all
objects going into grid level k are inserted before those that go into level k − 1. With
this restriction, the newly inserted object has to be tested only against cells on the
level at which it is being inserted and against cells on higher levels. Lower levels
do not have to be tested because they are by order of insertion empty. To handle
the dynamic addition and deletion of objects, a separate data structure would be
necessary to maintain the sorted insertion and testing order of existing objects. An
example of this scheme is shown in Figure 7.9.
For the second scheme, objects are no longer inserted in a single cell on just one
level. Instead, the object is inserted in all cells it overlaps, starting at the lowest
grid level at which the cells are large enough to contain the object, repeating for all
overlapped grid cells of higher-level grids.
In the second scheme, given a pair (A, B) of objects in the grid, determining if
they overlap can now be done by testing if they share a common cell at level L =
max(Level(A), Level(B)). In other words, the test is if they overlap on the larger of the
two initial insertion levels for the objects. No other levels have to be tested.
5
4
3 B B D
2 F
1 A A C C E E
A B C D E F
Figure 7.9 In Mirtich’s (first) scheme, objects are inserted in all cells overlapped at the
insertion level. As in Figure 7.8, the shaded cells indicate which cells must be tested when
performing a collision check for object C.
7.3 Trees 307
In that this test relies on knowing which pairs to test, pair information has to be
tracked separately. Whenever an object A is stored in a grid cell containing another
object B, a counter corresponding to the pair (A, B) is incremented, and the pair
is added to the tracking data structure. When either object moves out of one of
their common cells, the counter is decremented. When the counter reaches zero, the
pair is removed from the tracking data structure because they are no longer close.
Only pairs in the tracking data structure undergo narrow-phase collision detection
checking. The cost of moving an object is now much larger, but thanks to spa-
tial coherence the larger grid cells have to be updated only infrequently. Overall,
this scheme trades the cost of updating cells for the benefit of having to test fewer
grid cells.
7.2.3 Other Hierarchical Grids

As presented, a drawback with the hierarchical grid is that it is not very appropriate
for handling world geometry, which often consists of large amounts of unevenly
distributed small static data. Representing the lowest-level grid as a dense grid will
be extremely expensive is terms of storage. Similarly, a sparse representation using
hashing is likely to cause slowdown when a large number of cells is intersected due to
cache misses and the extra calculations involved. For this particular type of problem,
other types of hierarchical grids are more suited. Many of these have their origins in
ray tracing.
Of these, the most straightforward alternative is the recursive grid [Jevans89]. Here,
a uniform grid is constructed over the initial set of primitives. For each grid cell
containing more than some k primitives, a new, finer, uniform grid is recursively
constructed for that cell. The process is stopped when a cell contains less than some
m objects or when the depth is greater than n (usually 2 or 3). Compared to the
original hgrid, the lowest-level grids no longer span the world and they will require
less memory for a dense grid representation.
Two other grid alternatives are hierarchy of uniform grids [Cazals95] and adaptive
grids [Klimaszewski97]. Both of these use object clustering methods to identify groups
of primitives that should be contained within their own subgrids inside a larger
uniform grid. More information and a thorough comparison of these two and other
methods can be found in [Havran99].
7.3 Trees
Trees were discussed in the previous chapter in the context of bounding volume
hierarchies. Trees also form good representations for spatial partitioning. This section
explores two tree approaches to spatial partitioning: the octree and the k-d tree.
6 3
7
1
0 4
5
Figure 7.10 Numbering of the eight child nodes of the root of an octree.
7.3.1 Octrees (and Quadtrees)

The archetypal tree-based spatial partitioning method is the octree. It is an axis-aligned
hierarchical partitioning of a volume of 3D world space. As the name suggests, each
parent node in the octree has eight children. Additionally, each node also has a finite
volume associated with it. The root node volume is generally taken to be the smallest
axis-aligned cube fully enclosing the world. This volume is then subdivided into eight
smaller equal-size subcubes (also called cells, octants, or cubelets) by simultaneously
dividing the cube in half along each of the x, y, and z axes (Figure 7.10). These subcubes
form the child nodes of the root node. The child nodes are, in turn, recursively
subdivided in the same fashion. Typical criteria for stopping the recursive creation
of the octree include the tree reaching a maximum depth or the cubes getting smaller
than some preset minimum size. By virtue of construction, the associated volume of
space for each node of the tree fully contains all descendant nodes.
Even though the geometric boundaries of a node can, for instance, be passed
down and refined as the octree is traversed, the node structure is often enhanced to
contain both node position and extent. This simplifies tree operations at the cost of
extra memory. In addition, if the requirement for splitting into eight child volumes of
equal size is relaxed to allow off-center splitting independently on all three axes, this
volume information must be stored in the nodes.
// Octree node data structure

struct Node {
Point center; // Center point of octree node (not strictly needed)
float halfWidth; // Half the width of the node volume (not strictly needed)
Node *pChild[8]; // Pointers to the eight children nodes
Object *pObjList; // Linked list of objects contained at this node
};
7.3 Trees 309
The analogous structure to the octree in two dimensions is known as a quadtree.

The world is now enclosed in an axis-aligned bounding square, and is subdivided
into four smaller squares at each recursive step.
Just as binary trees can be represented in a flat array without using pointers,
so can both quadtrees and octrees. If the tree nodes are stored in the zero-based
array node[N], then being at some parent node node[i], the children would for
a quadtree be node[4*i+1] through node[4*i+4] and for an octree node[8*i+1]
through node[8*i+8]. This representation requires the tree being stored as a
complete tree.
Where a complete binary tree of n levels has 2n − 1 nodes, a complete d-ary tree
of n levels has (dn − 1) / (d − 1) nodes. Using this type of representation, a complete
seven-level octree would require just short of 300,000 nodes, limiting most trees to
five or possibly six levels in practice.
As the tree must be preallocated to a specific depth and cannot easily grow further,
the array representation is more suitable for static scenes and static octrees. The
pointer-based representation is more useful for dynamic scenes in which the octree
is constantly updated.
7.3.2 Octree Object Assignment

Octrees may be built to contain either static or dynamic data. In the former case, the
data may be the primitives forming the world environment. In the latter case, the
data is the moving entities in the world.
In the static scenario, it is straightforward to form the octree using top-down con-
struction. Initially, all primitives in the world are associated with the root volume. As
the root volume is split, the set of primitives is reassigned to the child cells it overlaps,
duplicating the primitives when they overlap more than one cell. The procedure is
repeated recursively, with the stopping criteria of not subdividing cells containing
fewer than some fixed number of primitives or when primitives are assigned to all of
the children (obviating further subdivision).
Determining to which child volumes to assign a primitive can be done by first
dividing the primitives by the octree x-axis partitioning plane, splitting any straddling
primitives into two parts, one for each side. Both sets are then similarly split for the
y-axis partitioning plane, and the resulting four sets are split once more by the z-axis
plane. The eight final sets are then assigned to the corresponding child node. Whether
a primitive must be split by a given partitioning plane is determined by testing to see
if it has vertices on both sides of the plane. Splitting of polygon primitives is discussed
in detail in Section 8.3.4.
An alternative assignment approach is not to split the primitives. Instead, for each
child volume and each primitive a full AABB-primitive overlap test is performed to see
if the primitive should be assigned to that volume. Although perhaps a conceptually
simpler method, this test is more expensive.
Figure 7.11 A quadtree node with the first level of subdivision shown in black dotted lines,
and the following level of subdivision in gray dashed lines. Dark gray objects overlap the first-
level dividing planes and become stuck at the current level. Medium gray objects propagate
one level down before becoming stuck. Here, only the white objects descend two levels.
To avoid duplication of geometry between multiple octree nodes, the original set of
primitives is stored in an array beforehand and a duplicate set of primitives is passed
to the construction function. Each of the duplicate primitives is given a reference to
the original primitive. When primitives are split, both parts retain the reference to the
original primitive. As tree leaf nodes are generated, rather than storing the split-up
duplicate geometry the references to the original set of primitives are stored. As the
tree is static, this work is best done in a preprocessing step.
Duplicating the primitives across overlapped octants works great for a static envi-
ronment. However, this approach is inefficient when the octree holds dynamic objects
because the tree must be updated as objects move. For the dynamic scenario, a better
approach is to restrict placement of objects to the lowest octree cell that contains
the object in its interior. By associating the object with a single cell only, a minimum
amount of pointer information must be updated when the object moves. A drawback
of restricting objects to lie within a single octree cell is that objects may be higher in
the tree than their size justifies. Specifically, any object straddling a partitioning plane
will become“stuck”at that level, regardless of the relative size between the object and
the node volume (Figure 7.11). This problem is addressed later. From here on, it is
assumed the octree is of the dynamic variety.
The octree can begin as an empty tree grown on demand as objects are inserted.
It can also be preallocated to alleviate the cost of dynamically growing it. Given
the previous octree node definition, preallocating a pointer-based octree down to a
specified depth can be done as:
// Preallocates an octree down to a specific depth

Node *BuildOctree(Point center, float halfWidth, int stopDepth)
{
if (stopDepth < 0) return NULL;
7.3 Trees 311
else {
// Construct and fill in ’root’ of this subtree
Node *pNode = new Node;
pNode->center = center;
pNode->halfWidth = halfWidth;
pNode->pObjList = NULL;
// Recursively construct the eight children of the subtree

Point offset;
float step = halfWidth * 0.5f;
for (int i = 0; i < 8; i++) {
offset.x = ((i & 1) ? step : -step);
offset.y = ((i & 2) ? step : -step);
offset.z = ((i & 4) ? step : -step);
pNode->pChild[i] = BuildOctree(center + offset, step, stopDepth - 1);
}
return pNode;
}
}
Because objects have been restricted to reside in a single cell, the simplest linked-
list solution for handling multiple objects in a cell is to embed the linked-list next
pointer in the object. For the sample code given here, the object is assumed to be
structured as follows.
struct Object {
Point center; // Center point for object
float radius; // Radius of object bounding sphere
...
Object *pNextObject; // Pointer to next object when linked into list
};
The code for inserting an object now becomes:
void InsertObject(Node *pTree, Object *pObject)

{
int index = 0, straddle = 0;
// Compute the octant number [0..7] the object sphere center is in
// If straddling any of the dividing x, y, or z planes, exit directly
for (int i = 0; i < 3; i++) {

float delta = pObject->center[i] - pTree->center[i];
if (Abs(delta) < pTree->halfWidth + pObject->radius) {
straddle = 1;
break;
}
if (delta > 0.0f) index |= (1 << i); // ZYX
}
if (!straddle && pTree->pChild[index]) {
// Fully contained in existing child node; insert in that subtree
InsertObject(pTree->pChild[index], pObject);
} else {
// Straddling, or no child node to descend into, so
// link object into linked list at this node
pObject->pNextObject = pTree->pObjList;
pTree->pObjList = pObject;
}
}
InsertObject() can be changed so that whenever a child node pointer is NULL

a new node is allocated and linked into the tree, with the object inserted into this
new node.
if (!straddle) {
if (pTree->pChild[index] == NULL) {
pTree->pChild[index] = new Node;
...initialize node contents here...
}
InsertObject(pTree->pChild[index], pObject);
} else {
...same as before...
}
If nodes should be deleted in a corresponding manner whenever they no longer

contain any objects, a pointer (or similar mechanism) is required in the node structure
to be able to access the parent node for updating. The creation of new nodes can be
delayed until a node contains n objects. When this happens, the node is split into
eight child nodes, and the objects are reassigned among the children. When creating
child nodes dynamically, all that is needed to build an octree incrementally is to create
the initial root node; all other nodes are created as needed. Testing a dynamic octree
7.3 Trees 313
for collisions can be done as a recursive top-down procedure in which the objects of
each nonempty node are checked against all objects in the subtree below the node.
// Tests all objects that could possibly overlap due to cell ancestry and coexistence
// in the same cell. Assumes objects exist in a single cell only, and fully inside it
void TestAllCollisions(Node *pTree)
{
// Keep track of all ancestor object lists in a stack
const int MAX_DEPTH = 40;
static Node *ancestorStack[MAX_DEPTH];
static int depth = 0; // ’Depth == 0’ is invariant over calls
// Check collision between all objects on this level and all

// ancestor objects. The current level is included as its own
// ancestor so all necessary pairwise tests are done
ancestorStack[depth++] = pTree;
for (int n = 0; n < depth; n++) {
Object *pA, *pB;
for (pA = ancestorStack[n]->pObjList; pA; pA = pA->pNextObject) {
for (pB = pTree->pObjList; pB; pB = pB->pNextObject) {
// Avoid testing both A->B and B->A
if (pA == pB) break;
// Now perform the collision test between pA and pB in some manner
TestCollision(pA, pB);
}
}
}
// Recursively visit all existing children

for (int i = 0; i < 8; i++)
if (pTree->pChild[i])
TestAllCollisions(pTree->pChild[i]);
// Remove current node from ancestor stack before returning

depth--;
}
7.3.3 Locational Codes and Finding the Octant for a Point

Consider a query point somewhere inside the space occupied by an octree. The leaf
node octant in which the point lies can be found without having to perform direct
Figure 7.12 The cells of a 4 × 4 grid given in Morton order.
comparisons with the coordinates of the octree nodes. Let the point’s coordinates be
given as three floats x, y, and z. Remap each of these into binary fractions over the range
[0 . . . 1]. For instance, if the octree’s x range spans [10 . . . 50], then an x coordinate of
25 would map into the fraction (25 − 10)/(50 − 10) = 0. 375 = 0. 01100000. Note
that this does not require either all dimensions to be the same or that they be powers
of 2. By virtue of construction, it should be clear that the most significant bit of the
binary fraction for the x coordinate specifies whether the point lies to the left of the
octree yz plane through the octree center point (when the bit is 0) or to the right of
it (when the bit is 1). Taking the three most significant bits of the binary fractions for
x, y, and z together as a unit, they form the index number (0–7) of the root’s child
node, in which the point lies. Similarly, the three next-most significant bits specify
the subnode within that node in which the point lies, and so on until a leaf node has
been reached.
The resulting binary string of interleaved bits of the three binary fractions can be
seen as a key, a locational code, directly describing a node position within the tree.
Nodes output in sorted order based on this locational code are said to be in Morton
order (Figure 7.12).
Given the locational code for the parent node, a new locational code for one of
its child nodes is easily constructed by left-shifting the parent key by 3 and adding
(or ORing) in the parent’s child index number (0–7) for the child node childKey =
(parentKey << 3) + childIndex. Locational codes can be used in a very memory-
efficient octree representation, explored next.
7.3.4 Linear Octrees (Hash-based)

Although the pointer-based representation is likely to save memory over the flat
array-based representation for average trees, the former still requires up to eight
child pointers to be stored in the octree nodes. These likely constitute a major part of
the memory required to hold the tree.
A clever nonpointer-based representation alternative is the linear octree. A linear
octree consists of just the octree nodes containing data, in which each node has
7.3 Trees 315
been enhanced to contain its own locational code. The locational codes for both the
parent node and all children nodes can be computed from the stored locational code.
As such, the octree nodes no longer need explicit pointers to the children, thereby
becoming smaller.
// Octree node data structure (hashed)

struct Node {
Point center; // Center point of octree node (not strictly needed)
int key; // The location (Morton) code for this node
int8 hasChildK; // Bitmask indicating which eight children exist (optional)
Object *pObjList; // Linked list of objects contained at this node
};
The size of a node can be explicitly stored or it can be derived from the “depth”of
the locational code. In the latter case, a sentinel bit is required in the locational code
to be able to distinguish between, say, 011 and 000000011, turning these into 1011
and 1000000011, respectively. The code for this follows.
int NodeDepth(unsigned int key)

{
// Keep shifting off three bits at a time, increasing depth counter
for (int d = 0; key; d++) {
// If only sentinel bit remains, exit with node depth
if (key == 1) return d;
key >>= 3;
}
assert(0); // Bad key
}
To be able to access the octree nodes quickly given just a locational code, the
nodes are stored in a hash table using the node’s locational code as the hash key. This
hashed storage representation provides O(1) access to any node, whereas locating an
arbitrary node in a pointer-based tree takes O(log n) operations.
To avoid a failed hash table lookup, the node is often enhanced (as previously) with
a bitmask indicating which of the eight children exist. The following code for visiting
all existing nodes in a linear octree illustrates both how child nodes are computed
and how the bitmask is used.
void VisitLinearOctree(Node *pTree)

{
// For all eight possible children
for (int i = 0; i < 8; i++) {

// See if the ith child exist
if (pTree->hasChildK & (1 << i)) {
// Compute new Morton key for the child
int key = (pTree->key << 3) + i;
// Using key, look child up in hash table and recursively visit subtree
Node *pChild = HashTableLookup(gHashTable, key);
VisitLinearOctree(pChild);
}
}
}
A hashed octree similar to this is described in [Warren93].
7.3.5 Computing the Morton Key

Given three integer values representing the x, y, and z coordinates of an octree leaf,
the corresponding Morton key can be computed by the following function.
// Takes three 10-bit numbers and bit-interleaves them into one number
uint32 Morton3(uint32 x, uint32 y, uint32 z)
{
// z--z--z--z--z--z--z--z--z--z-- : Part1By2(z) << 2
// -y--y--y--y--y--y--y--y--y--y- : Part1By2(y) << 1
// --x--x--x--x--x--x--x--x--x--x : Part1By2(x)
// zyxzyxzyxzyxzyxzyxzyxzyxzyxzyx : Final result
return (Part1By2(z) << 2) + (Part1By2(y) << 1) + Part1By2(x);
}
The support function Part1By2() splits up the bits of each coordinate value,
inserting two zero bits between each original data bit. Interleaving the intermedi-
ate results is then done by shifting and adding the bits. The function Part1By2() can
be implemented as:
// Separates low 10 bits of input by two bits

uint32 Part1By2(uint32 n)
{
// n = ----------------------9876543210 : Bits initially
// n = ------98----------------76543210 : After (1)
// n = ------98--------7654--------3210 : After (2)
7.3 Trees 317
// n = ------98----76----54----32----10 : After (3)

// n = ----9--8--7--6--5--4--3--2--1--0 : After (4)
n = (n ∧ (n << 16)) & 0xff0000ff; // (1)
n = (n ∧ (n << 8)) & 0x0300f00f; // (2)
n = (n ∧ (n << 4)) & 0x030c30c3; // (3)
n = (n ∧ (n << 2)) & 0x09249249; // (4)
return n;
}
The equivalent code for interleaving 2D coordinates (for a quadtree) follows.
// Takes two 16-bit numbers and bit-interleaves them into one number
uint32 Morton2(uint32 x, uint32 y)
{
return (Part1By1(y) << 1) + Part1By1(x);
}
// Separates low 16 bits of input by one bit

uint32 Part1By1(uint32 n)
{
// n = ----------------fedcba9876543210 : Bits initially
// n = --------fedcba98--------76543210 : After (1)
// n = ----fedc----ba98----7654----3210 : After (2)
// n = --fe--dc--ba--98--76--54--32--10 : After (3)
// n = -f-e-d-c-b-a-9-8-7-6-5-4-3-2-1-0 : After (4)
n = (n ∧ (n << 8)) & 0x00ff00ff; // (1)
n = (n ∧ (n << 4)) & 0x0f0f0f0f; // (2)
n = (n ∧ (n << 2)) & 0x33333333; // (3)
n = (n ∧ (n << 1)) & 0x55555555; // (4)
return n;
}
If sufficient bits are available in the CPU registers, the calls to the support function
can be done in parallel. For example, using a modified Part1By1() function that
operates on 32-bit numbers giving a 64-bit result, the Morton2() function presented
previously can be written as:
uint32 Morton2(uint32 x, uint32 y)

{
// Merge the two 16-bit inputs into one 32-bit value
uint32 xy = (y << 16) + x;
// Separate bits of 32-bit value by one, giving 64-bit value

uint64 t = Part1By1_64BitOutput(xy);
// Interleave the top bits (y) with the bottom bits (x)
return (uint32)((t >> 31) + (t & 0x0ffffffff));
}
In general, for the 2D case just presented, handling n-bit inputs would require
4n-bit numbers being available in the intermediate calculations.
7.3.6 Loose Octrees

Consider again the problem of objects becoming stuck high up in a dynamic octree due
to straddling of the partitioning planes. An effective way of dealing with this problem
is to expand the node volumes by some amount to make them partially overlapping
(Figure 7.13). The resulting relaxed octrees have been dubbed loose octrees [Ulrich00].
The loose nodes are commonly extended by half the side width in all six directions
(but may be extended by any amount). This effectively makes their volume eight times
larger.
Assuming spherical objects, the objects are propagated into the child node in which
the sphere center is contained. Only when the sphere extends outside the loose cell
would it remain at the current level.
With these larger nodes, objects now descend deeper into the tree, giving the parti-
tioning more discriminatory power. Unfortunately positioned but otherwise pairwise
distant objects that previously became stuck high up in the tree are less likely to
have to be tested against other objects. Another benefit of the loose nodes is that the
(a) (b)
Figure 7.13 (a) The cross section of a regular octree, shown as a quadtree. (b) Expanding the
nodes of the octree, here by half the node width in all directions, turns the tree into a loose
octree. (The loose nodes are offset and shown in different shades of gray to better show their
boundaries. The original octree nodes are shown as dashed lines.)
7.3 Trees 319
depth at which an object will be inserted can be computed from the size of the object,
allowing for O(1) insertions.
This power does not come for free, however. The larger nodes overlap more neigh-
boring nodes, and more nodes have to be examined to determine whether any two
objects must be tested against each other. Still, in most cases the reduction in pairwise
tests makes loose octrees attractive for collision detection purposes.
Loose octrees are similar in structure to hierarchical grids. The key difference is
that octrees are rooted. This means that time is spent traversing the (largely) empty
top of the tree to get at the lower-level nodes where the objects are, due to objects
generally being much smaller than the world. In comparison, the hgrid is a shallower,
rootless structure providing faster access to the nodes where the objects are stored.
In addition, hgrid levels can be dynamically deactivated so that no empty levels
are processed and processing stops when no objects exist on the remaining levels.
A linearized or array-based octree allows similar optimizations. The corresponding
optimization for a pointer-based octree is to maintain a subtree object-occupancy
count for each node. The cost of updating these occupancy counts is proportional to
the height of the tree, whereas the hgrid level occupancy counters are updated in O(1)
time. Thanks to the automatic infinite tiling performed by the hash mapping, a hashed
hgrid does not need to know the world size. The octree cannot easily accommodate
an unbounded world without growing in height. Overall, hgrids seem to perform
somewhat better than loose octrees for collision detection applications.
7.3.7 k-d Trees

A generalization of octrees and quadtrees can be found in the k-dimensional tree,
or k-d tree [Bentley75], [Friedman77]. Here, k represents the number of dimensions
subdivided, which does not have to match the dimensionality of the space used.
Instead of simultaneously dividing space in two (quadtree) or three (octree) dimen-
sions, the k-d tree divides space along one dimension at a time. Traditionally, k-d trees
are split along x, then y, then z, then x again, and so on, in a cyclic fashion. However,
often the splitting axis is freely selected among the k dimensions. Because the split
is allowed to be arbitrarily positioned along the axis, this results in both axis and
splitting value being stored in the k-d tree nodes. An efficient way of storing the two
bits needed to represent the splitting axis is presented in Section 13.4.1. One level
of an octree can be seen as a three-level k-d tree split along x, then y, then z (all
splits selected to divide the space in half). Figure 7.14 shows a 2D spatial k-d tree
decomposition and the corresponding k-d tree layout.
Splitting along one axis at a time often accommodates simpler code for operating
on the tree, in that only the intersection with a single plane must be considered.
Furthermore, because this plane is axis aligned, tests against the plane are numerically
robust.
For collision detection, k-d trees can be used wherever quadtrees or octrees are
used. Other typical uses for k-d trees include point location (given a point, locate the
A C I
D F
B
E
G
H I J
H
J A B C
D E F G
(a) (b)
Figure 7.14 A 2D k-d tree. (a) The spatial decomposition. (b) The k-d tree layout.
region it is in), nearest neighbor (find the point in a set of points the query point is
closest to), and range search (locate all points within a given region) queries.
The following code illustrates how to visit all nodes of a k-d tree a given sphere
overlaps. One interesting problem is correctly rejecting subtree volumes the sphere is
outside of, even when the sphere straddles one or more of the supporting hyperplanes
of the halfspaces forming the volume. The solution adopted here is to maintain the
point inside the volume closest to the sphere center during traversal. Initially this
variable, volNearPt, is set to the sphere center. As the traversal recurses the far side
of the splitting plane (the side the sphere is not on), the point is clamped to the
splitting plane to determine the closest point on the volume boundary. The distance
between volNearPt and the query sphere center can now be used to cull subtrees.
struct KDNode {
KDNode *child[2]; // 0 = near, 1 = far
int splitType; // Which axis split is along (0, 1, 2, ...)
float splitValue; // Position of split along axis
...
};
// Visit k-d tree nodes overlapped by sphere. Call with volNearPt = s->c
void VisitOverlappedNodes(KDNode *pNode, Sphere *s, Point &volNearPt)
{
if (pNode == NULL) return;
// Visiting current node, perform work here

...
7.3 Trees 321
// Figure out which child to recurse into first (0 = near, 1 = far)

int first = s->c[pNode->splitType] > pNode->splitValue;
// Always recurse into the subtree the sphere center is in

VisitOverlappedNodes(pNode->child[first], s, volNearPt);
// Update (by clamping) nearest point on volume when traversing far side.
// Keep old value on the local stack so it can be restored later
float oldValue = volNearPt[pNode->splitType];
volNearPt[pNode->splitType] = pNode->splitValue;
// If sphere overlaps the volume of the far node, recurse that subtree too
if (SqDistPointPoint(volNearPt, s->c) < s->r * s->r)
VisitOverlappedNodes(pNode->child[first ∧ 1], s, volNearPt);
// Restore component of nearest pt on volume when returning

volNearPt[pNode->splitType] = oldValue;
}
This code framework is easily extended to, for instance, locate the nearest neighbor
object to the query sphere by starting with a sphere of unbounded size, shrinking the
sphere as objects are encountered within the sphere. Note that the shape of the
regions in a k-d tree will affect the number of nodes being visited. For example, if
many narrow regions are next to each other, a wide query is likely to overlap all
regions. To limit the number of nodes being visited, it is best to avoid regions narrow
in one or more dimensions. Such nonnarrow regions are commonly referred to as fat
regions.
The efficiency of k-d trees (in the context of ray tracing) is discussed in
[MacDonald90]. An in-depth treatment of octrees, quadtrees, k-d trees, and similar
spatial data structures is found in [Samet90a] and [Samet90b].
7.3.8 Hybrid Schemes

The previously described methods can also form the basis of various hybrid strategies.
For instance, after having initially assigned objects or geometry primitives to a uniform
grid, the data in each nonempty grid cell could be further organized in a tree structure.
The grid now serves as a fast way of locating the appropriate trees (in a forest of trees)
to perform further tests against (Figure 7.15a).
Grids can also be used as “acceleration structures” into a single tree hierarchy.
Consider a uniform grid of tree node pointers in which each pointer has been directed
to the tree node whose volume bounds the corresponding grid cell as tightly as
possible (Figure 7.15b). Instead of traversing from the root to the node an object is in,
(a) (b)
Figure 7.15 (a) A grid of trees, each grid cell containing a separate tree. (b) A grid indexing
into a single tree hierarchy, each grid cell pointing into the tree at which point traversal
should start.
it suffices to locate the grid cell the object is inside and follow the pointer to the
correct tree node. Using a grid in this manner can help bypass a large portion of the
tree during queries.
To handle the case of going to the correct node when an object is on a grid cell
boundary overlapping two or more cells, the grid cells can be made loose, similar to
the nodes in a loose octree. The grid cell that encompasses the object is now used
to find the entry point into the tree structure.
7.4 Ray and Directed Line Segment Traversals

Particularly common in many applications, games in particular, are line pick tests.
These are queries involving rays or directed line segments. Typical uses include line-
of-sight tests and tests for whether or not a fired bullet hits an enemy. They can also
be used as the primary collision query. One such example could be performing line
picks down from the wheels of a vehicle to attach the vehicle to the terrain below.
To accelerate these queries, hierarchical structures are used to minimize the number
of objects that have to be intersected by the ray or segment. The key idea is to first
spatially partition the world into a number of cells. The ray is then traced through
those cells it pierces and intersected against any objects they might contain. The next
two sections illustrate how ray queries are performed on k-d trees and uniform grids.
7.4.1 k-d Tree Intersection Test

The basic idea behind intersecting a ray or directed line segment with a k-d tree is
straightforward. The segment S(t) = A + t d is intersected against the node’s splitting
plane, and the t value of intersection is computed. If t is within the interval of the
7.4 Ray and Directed Line Segment Traversals 323
segment, 0 ≤ t < tmax, the segment straddles the plane and both children of the
tree are recursively descended. If not, only the side containing the segment origin is
recursively visited.
By first descending the side of the segment origin, overlapped k-d tree nodes are
guaranteed to be traversed in order near to far. Thus, assuming the closest intersection
point is sought, when a hit is detected among the node contents the test procedure
can exit early, not having to test any other nodes.
// Visit all k-d tree nodes intersected by segment S = a + t * d, 0 <= t < tmax
void VisitNodes(KDNode *pNode, Point a, Vector d, float tmax)
{
if (pNode == NULL) return;
// Visiting current node, perform actual work here

...
// Figure out which child to recurse into first (0 = near, 1 = far)

int dim = pNode->splitType;
int first = a[dim] > pNode->splitValue;
if (d[dim] == 0.0f) {
// Segment parallel to splitting plane, visit near side only
VisitNodes(pNode->child[first], a, d, tmax);
} else {
// Find t value for intersection between segment and split plane
float t = (pNode->splitValue - a[dim]) / d[dim];
// Test if line segment straddles splitting plane

if (0.0f <= t && t < tmax) {
// Yes, traverse near side first, then far side
VisitNodes(pNode->child[first], a, d, t);
VisitNodes(pNode->child[first ∧ 1], a + t * d, d, tmax - t);
} else {
// No, so just traverse near side
VisitNodes(pNode->child[first], a, d, tmax);
}
}
}
This procedure can be rewritten to avoid explicit recursion, in the manner described
in Chapter 6. Only small changes are required to accommodate traversals for octrees
and BSP trees. It is also possible to directly link the faces of a leaf to the leaf
nodes they border, allowing direct traversal from one leaf to the next. As a face
(a) (b)
Figure 7.16 Cell connectivity for a 2D line. (a) An 8-connected line. (b) A 4-connected line.
In 3D, the corresponding lines would be 26-connected and 6-connected, respectively.
may border more than just one leaf node, a quadtree or k-d tree stored at the
face is used to divide the face area and link each area with the correct neighboring
leaf node.
7.4.2 Uniform Grid Intersection Test

Shooting a ray through a uniform grid is very similar to the rasterization steps per-
formed by, say, the Bresenham line-drawing algorithm [Rogers98]. However, there
is an important difference. In rasterization, the line may intersect cells that are not
filled in (Figure 7.16a). For collision detection, this would be fatal; all pierced cells
must be visited or some objects may not be tested. The traversal method used must
enforce 6-connectivity of the cells visited along the line. Cells in 3D are said to be
6-connected if they share faces only with other cells (in 2D, the same cells would
be called 4-connected). If cells are also allowed to share edges, they are considered
18-connected. A cell is 26-connected if it can share a face, edge, or vertex with another
cell (called 8-connected in 2D).
Bresenham-like methods are categorized by stepping along the major axis, taking
a step along the minor axis (axes) when an error term has built up. It is possible to
extend these methods to step through the missed cells when the step along the minor
axis is performed. For a thorough derivation of how to do so see [Joy86].
In this section a slightly different method is presented, due to [Amanatides87] and
[Cleary88]. This method is symmetric and does not use the concept of a major stepping
axis. Cells are assumed to be square. In the following, the term segment means a
directed line segment and the term ray will sometimes be used synonymously. To
simplify the presentation, the grid is assumed to be 2D.
The key idea is that as a ray leaves a cell it pierces a cell boundary. Whether to
step along the x axis or the y axis depends on whether a vertical or a horizontal
boundary is pierced. This decision is made easy by maintaining two variables, tx and
ty, containing the distance from the ray origin along the ray to the next vertical and
(i, j) (i, j + 1) (i + 1, j)
ty ty
tx tx
(a) (b) (c)
Figure 7.17 Illustrating the values of tx, ty, tx, and ty. (a) tx is the distance between
two vertical boundaries. (b) ty is the distance between two horizontal boundaries. (c) For
cell (i, j ), the distance tx to the next horizontal boundary is less than the distance ty to the
next horizontal boundary, and thus the next cell to visit is (i + 1, j ).
horizontal boundary. If tx is less than ty, a vertical boundary will be pierced before the
next horizontal one is encountered, and the algorithm proceeds to step left or right
along the x axis (depending on the direction of the ray) to the next cell.
As the step is made, tx is updated to represent the distance to the next vertical
boundary. For uniform-size cells, the distance moved along the ray is constant from
one vertical boundary to the next, and thus the change made to tx can be precom-
puted. This value is called tx (Figure 7.17a). The stepping value from one horizontal
boundary to the next is similarly constant and kept as ty (Figure 7.17b).
In Figure 7.17c, the current cell is denoted (i, j). Because tx (the distance from the
ray origin to the next vertical boundary) is less than ty, the next cell visited is (i + 1, j).
Assuming the cell side to be M units wide, tx is given by

dx 2 + dy2
tx = M .
dx
For the line segment (x1 , y1 ) − (x2 , y2 ), dx = |x2 − x1 | and dy = y2 − y1 . The initial
values of tx and ty are computed slightly differently depending on which direction
the segment is pointing in. With the ray origin at (x1 , y1 ), for the given x coordinate
(x1 ) the nearest vertical boundary to the left has a value of minx = M x1 /M. The
nearest vertical boundary to the right has a value of maxx = minx + M. If the ray is
directed to the right, the value of tx can therefore be computed as

dx 2 + dy2
tx = (maxx − x1 ) .
dx
兹苵苵苵苵苵苵苵苵苵
dx2 + dy2
兹苵苵苵苵苵苵苵苵苵
dx2 + dy2 tx = (maxx – x1)
tx = (x1 – minx) dx
dx
maxx = M x1 /M + M
minx = M x1 /M tx
minx = M x1 /M
(x1, y1)
(x1, y1)
tx
maxx = M x1 /M + M
x1 – minx maxx – x1
(a) (b)
Figure 7.18 Computing the initial value of tx (done analogously for ty) (a) for a ray directed
to the left and (b) for a ray directed to the right.
If instead the ray is directed to the left, the corresponding expression is

dx 2 + dy2
tx = (x1 − minx) .
dx
These derivations are illustrated in Figure 7.18. The initial value of ty is computed in
an analogous fashion.
To keep track of which cell is currently visited, first the cell (i, j) that the ray or
directed line segment originates in is found. A direction (di, dj) is then computed for
the ray. For a ray directed up and to the right, the direction would be (1, 1). For a ray
going to the left, it would be (−1, 0), and so on. Each time the ray passes through a cell
boundary, a step of di or dj is made along the x axis or y axis respectively, depending on
whether the boundary was vertical or horizontal. For a line segment, the coordinates
of the ending cell are computed in advance to minimize the traversal cost.
The following code implements the full grid traversal. Note that because the term
dx 2 + dy2 is constant and occurs in all four of the tx, ty, tx, and ty terms it can
be dropped, greatly simplifying the initialization calculations.
void VisitCellsOverlapped(float x1, float y1, float x2, float y2)

{
// Side dimensions of the square cell
const float CELL_SIDE = 30.0f;
// Determine start grid cell coordinates (i, j)

int i = (int)(x1 / CELL_SIDE);
int j = (int)(y1 / CELL_SIDE);
// Determine end grid cell coordinates (iend, jend)

int iend = (int)(x2 / CELL_SIDE);
int jend = (int)(y2 / CELL_SIDE);
// Determine in which primary direction to step

int di = ((x1 < x2) ? 1 : ((x1 > x2) ? -1 : 0));
int dj = ((y1 < y2) ? 1 : ((y1 > y2) ? -1 : 0));
// Determine tx and ty, the values of t at which the directed segment

// (x1,y1)-(x2,y2) crosses the first horizontal and vertical cell
// boundaries, respectively. Min(tx, ty) indicates how far one can
// travel along the segment and still remain in the current cell
float minx = CELL_SIDE * floorf(x1/CELL_SIDE), maxx = minx + CELL_SIDE;
float tx = ((x1 < x2) ? (x1 - minx) : (maxx - x1)) / Abs(x2 - x1);
float miny = CELL_SIDE * floorf(y1/CELL_SIDE), maxy = miny + CELL_SIDE;
float ty = ((y1 < y2) ? (y1 - miny) : (maxy - y1)) / Abs(y2 - y1);
// Determine deltax/deltay, how far (in units of t) one must step

// along the directed line segment for the horizontal/vertical
// movement (respectively) to equal the width/height of a cell
float deltatx = CELL_SIDE / Abs(x2 - x1);
float deltaty = CELL_SIDE / Abs(y2 - y1);
// Main loop. Visits cells until last cell reached

for (;;) {
VisitCell(i, j);
if (tx <= ty) { // tx smallest, step in x
if (i == iend) break;
tx += deltatx;
i += di;
} else { // ty smallest, step in y
if (j == jend) break;
ty += deltaty;
j += dj;
}
}
}
Instead of using the i and j coordinates to index into some array grid[i][j], it
is possible to maintain a pointer to the current cell and step the pointer directly by
adding appropriate values to the pointer instead of adding di and dj to a set of index
variables.
The described algorithm can of course be implemented for the traversal of a 3D

grid. In this case the structure of the main loop becomes:
for (;;) {
VisitCell(i, j, k);
if (tx <= ty && tx <= tz) { // tx smallest, step in x
if (i == iend) break;
tx += deltatx;
i += di;
} else if (ty <= tx && ty <= tz) { // ty smallest, step in y
if (j == jend) break;
ty += deltaty;
j += dj;
} else { // tz smallest, step in z
if (k == kend) break;
tz += deltatz;
k += dk;
}
}
It should be noted that as tx and ty are float variables it is possible that rounding
errors may cause the cells visited during traversal to be different from those visited by
an algorithm using exact arithmetic. If this is a concern, objects should be considered
as extended by some small epsilon before being assigned to the grid. It is also possi-
ble to turn this algorithm into an all-integer algorithm by using integer-only inputs
and multiplying through tx, ty, tx, and ty by the denominators involved in the
initialization code. An all-integer 4-connected line-drawing algorithm is described
in [Barerra03].
If the objects stored in the grid can be concave, it is important to make sure that the
intersection point of a detected intersection lies within the current cell. Otherwise,
when a concave object straddles multiple cells the object could have been hit several
cells away, and there might be a hit with a different object in any of the cells between.
Section 7.7 presents methods for avoiding having to perform multiple intersection
tests against the same objects in such situations as just described.
There are several possible optimizations that can be performed on ray queries on
uniform grids. For example, note that a ray at an angle passes through more cells
than an axis-aligned ray. Therefore, one possible optimization is to have several grids
oriented differently and pick the most aligned one to trace a ray through. Another
optimization is to apply a move-to-front reordering heuristic to objects in a cell. As
intersected objects are likely to be intersected again on the next query, having an early
upper bound on the distance to the nearest intersected object allows more distant
objects within the same cell to be quickly culled using a quick distance test. Additional
optimizations can be found in the ray-tracing literature [Glassner89], [Shirley00].
7.5 Sort and Sweep Methods 329
7.5 Sort and Sweep Methods

A drawback of inserting objects into the fixed spatial subdivisions that grids and
octrees represent is having to deal with the added complications of objects straddling
multiple partitions. An alternative approach is to instead maintain the objects in some
sort of sorted spatial ordering. One way of spatially sorting the objects is the sort and
sweep method [Baraff92] (referred to as sweep and prune in [Cohen95]).
First consider the case of detecting overlap among 1D bounding boxes. Each such
box corresponds to an interval [b, e] on the coordinate axis. Given n such intervals,
all b and e values can be inserted into a sorted list (Figure 7.19). By sweeping the list,
active intervals can be tracked by adding them to a list whenever their b values are
encountered and removing them when their e values are encountered. Whenever a
new interval is added to the list, it has also been found to overlap the already active
intervals on the list.
By considering their projection intervals onto the x, y, and z axes, AABBs in 3D
can be identified as three independent such intervals. Thus, for each coordinate axis a
sorted linked list is maintained of the start and end values of the corresponding AABB
projection intervals of all objects. The collisions for a single object can on average be
found in near constant time by querying neighboring objects for overlap. Only those
objects within the projection interval of the tested object have to be examined. Linked
lists also allow for dynamic updating whenever an object moves.
After the lists have been sorted, as objects generally do not move very far between
frames the lists will remain almost sorted from one frame to the next. To exploit
temporal coherence effectively, the lists are kept from frame to frame and they are
maintained sorted using a simple insertion sort, which has linear behavior for nearly
ordered lists.
To allow for fast updates during the sorting pass, the lists need to be double linked.
Start and end list sentinels help both to simplify (by removing special case tests such
as testing for empty lists or reaching either end of the list) and speed up the code
[Knuth98].
b0 b1 e0 b2 e1 e2 b3 b4 e3 e4
Figure 7.19 Projected AABB intervals on the x axis.

Figure 7.20 Objects clustered on the y axis (caused, for example, by falling objects settling
on the ground). Even small object movements can now cause large positional changes in the
list for the clustered axis.
In general, updating lists for n objects is expected time O(n). However, coherence
can break down due to clustering of objects. Specifically, sorting can deteriorate to
O(n2 ) on the clustered axis because of small world movements causing large positional
movements in the list. Unfortunately, such clustering is common. For instance, having
all objects on a surface, such as a floor, will cause tight clustering on the vertical axis
(Figure 7.20).
One solution to the global situation in which objects tend to cluster on, say, the
y axis is to track only the x and z lists. In most situations, sorting on just two axes is
likely to be sufficient, which also has the benefit of reducing the memory overhead of
this scheme. In some cases, it might even be worthwhile to pick axes other than the
normal x, y, and z ones to sort on. For instance, the x = y axis could be considered
in situations in which objects tend to cluster on x or y. Although this may lessen the
clustering problem for specific applications, the problem still remains. Section 7.5.2
suggests an alternative implementation avoiding the worst-case O(n2 ) behavior.
7.5.1 Sorted Linked-list Implementation

To maintain the axis-sorted lists of projection interval extents, two types of struc-
tures are required: one that is the linked-list element corresponding to the minimum
or maximum interval values and another one to link the two entries. A naive
implementation would look as follows.
struct AABB {
Elem *pMin[3]; // Pointers to the three minimum interval values (one for each axis)
Elem *pMax[3]; // Pointers to the three maximum interval values (one for each axis)
Object *pObj; // Pointer to the actual object contained in the AABB
};
struct Elem {
AABB *pAABB; // Back pointer to AABB object (to find matching max/min element)
Elem *pLeft; // Pointer to the previous linked list element
Elem *pRight; // Pointer to the next linked list element

float value; // The actual min or max coordinate value
int minmax:1; // A min value or a max value?
};
Here, the lists themselves would be represented by the three list headers:
Elem *gListHead[3];
By merging minimum and maximum values into one element each, space is con-
served (as only a single back pointer to the AABB object is needed). In addition, the
combined structure needs just one flag value, as its contained coordinate values are
either min or max values. This results in the following structures.
struct AABB {
Elem *pMin; // Pointer to element containing the three minimum interval values
Elem *pMax; // Pointer to element containing the three minimum interval values
};
struct Elem {
AABB *pAABB; // Back pointer to AABB object (to find matching max/min element)
Elem *pLeft[3]; // Pointers to the previous linked list element (one for each axis)
Elem *pRight[3]; // Pointers to the next linked list element (one for each axis)
float value[3]; // All min or all max coordinate values (one for each axis)
int minmax:1; // All min values or all max values?
};
Because the Elem structs do not move (only their contained pointers are being
relinked), this representation can be refined further by placing the structs contiguously
in memory. Given a pointer to either Elem struct, the corresponding min or max
element can always be found either before or after (respectively) the current one.
As the AABB struct was only needed to link the Elem structs, the pair of Elem structs
can effectively serve as the new AABB structure. Whereas previously AABB structs and
Elem structs were allocated separately, now the AABB struct contains all required data
and only a single structure need be allocated.
struct AABB {
Elem min; // Element containing the three minimum interval values
Elem max; // Element containing the three maximum interval values

};
struct Elem {
Elem *pLeft[3]; // Pointers to the previous linked list element (one for each axis)
Elem *pRight[3]; // Pointers to the next linked list element (one for each axis)
float value[3]; // All min or all max coordinate values (one for each axis)
int minmax:1; // All min values or all max values?
};
Given a pointer to an Elem struct, the corresponding AABB is located in this way:
AABB *GetAABB(Elem *pElem)

{
return (AABB *)(pElem->minmax ? (pElem - 1) : pElem);
}
Compared to the previous representation, this saves four pointers (16 bytes at
4 bytes per pointer) per AABB. By embedding the structure inside the objects them-
selves, the pointer to the object would no longer be needed and an additional 4 bytes
would be saved. With a little trickery, the minmax bit fields could be moved from the
Elem structs into the AABB struct to save some additional memory. They could, in fact,
be embedded within one of the other structure fields and thus take up no extra space.
This is still quite an expensive structure at about 76 to 84 bytes per object, depending
on implementation. Further savings can be had by turning the 32-bit pointers into
16-bit indices, assuming that at no time will there be more than 65,536 objects (which
is a safe assumption for many applications).
In the following code it is assumed the three lists have been initialized to have
both start and end sentinels. Sentinels can be set up as follows.
enum {
MIN_ELEM = 0, // Indicates AABB minx, miny, or minz element
MAX_ELEM = 1 // Indicates AABB maxx, maxy, or maxz element
};
// Initialize the lists, with start and end sentinels

AABB *pSentinel = new AABB;
for (int i = 0; i < 3; i++) {
pSentinel->min.pLeft[i] = NULL; // not strictly needed
pSentinel->min.pRight[i] = &pSentinel->max;
pSentinel->max.pLeft[i] = &pSentinel->min;
pSentinel->max.pRight[i] = NULL; // not strictly needed
pSentinel->min.value[i] = -FLT_MAX;
pSentinel->max.value[i] = FLT_MAX;
gListHead[i] = &pSentinel->min;
}
// Note backwardness of initializing these two
pSentinel->min.minmax = MAX_ELEM;
pSentinel->max.minmax = MIN_ELEM;
Inserting a new AABB into the sorted lists is done by scanning the lists for the
appropriate insertion point. To simplify the presentation here, the overlap pair sta-
tus is calculated in a separate pass after the new AABB has been inserted. To make
the code more efficient, the overlap pair status could be updated at the same time
objects are inserted by interleaving the routines. (Note that it is not possible to deter-
mine all overlapping pairs just by examining the Elem structs between the min and
max element. The latter test would miss overlap with a larger AABB, completely
encompassing the new AABB.)
To keep track of which collisions are active, the following code assumes the
existence of two functions AddCollisionPair() and DeleteCollisionPair() that
register and unregister, respectively, a pair of objects as being colliding.
void InsertAABBIntoList(AABB *pAABB)

{
// For all three axes
for (int i = 0; i < 3; i++) {
// Search from start of list
Elem *pElem = gListHead[i];
// Insert min cell at position where pElem points to first larger element.
// Assumes large sentinel value guards from falling off end of list
while (pElem->value[i] < pAABB->min.value[i])
pElem = pElem->pRight[i];
pAABB->min.pLeft[i] = pElem->pLeft[i];
pAABB->min.pRight[i] = pElem;
pElem->pLeft[i]->pRight[i] = &pAABB->min;
pElem->pLeft[i] = &pAABB->min;
// Insert max cell in the same way. Can continue searching from last
// position as list is sorted. Also assumes sentinel value present
while (pElem->value[i] < pAABB->max.value[i])
pElem = pElem->pRight[i];
pAABB->max.pLeft[i] = pElem->pLeft[i];
pAABB->max.pRight[i] = pElem;
pElem->pLeft[i]->pRight[i] = &pAABB->max;
pElem->pLeft[i] = &pAABB->max;
}
// Now scan through list and add overlap pairs for all objects that
// this AABB intersects. This pair tracking could be incorporated into
// the loops above, but is not done here to simplify the code
for (Elem *pElem = gListHead[0]; ; ) {
if (pElem->minmax == MIN_ELEM) {
if (pElem->value[0] > pAABB->max.value[0])
break;
if (AABBOverlap(pAABB, GetAABB(pElem)))
AddCollisionPair(pAABB, GetAABB(pElem));
} else if (pElem->value[0] < pAABB->min.value[0])
break;
}
}
After the position of an AABB has changed, the lists must be updated:
// This updating code assumes all other elements of list are sorted
void UpdateAABBPosition(AABB *pAABB)
{
// For all three axes
for (int i = 0; i < 3; i++) {
Elem *pMin = &pAABB->min, *pMax = &pAABB->max, *t;
// Try to move min element to the left. Move the roaming pointer t left
// for as long as it points to elem with value larger than pMin’s. While
// doing so, keep track of the update status of any AABBs passed over
for (t = pMin->pLeft[i]; pMin->value[i] < t->value[i]; t = t->pLeft[i])
if (t->minmax == MAX_ELEM)
if (AABBOverlap(pAABB, GetAABB(t)))
if (!HasCollisionPair(pAABB, GetAABB(t)))
AddCollisionPair(pAABB, GetAABB(t));
// If t moves from its original position, move pMin into new place
if (t != pMin->pLeft[i])
MoveElement(i, pMin, t);
// Similarly to above, try to move max element to the right

for (t = pMax->pRight[i]; pMax->value[i] > t->value[i]; t = t->pRight[i])
if (t->minmax == MIN_ELEM)
if (AABBOverlap(pAABB, GetAABB(t)))
if (!HasCollisionPair(pAABB, GetAABB(t)))
AddCollisionPair(pAABB, GetAABB(t));
if (t != pMax->pRight[i])
MoveElement(i, pMax, t->pLeft[i]);
// Similarly to above, try to move min element to the right

for (t = pMin->pRight[i]; pMin->value[i] > t->value[i]; t = t->pRight[i])
if (t->minmax == MAX_ELEM)
if (HasCollisionPair(pAABB, GetAABB(t)))
DeleteCollisionPair(pAABB, GetAABB(t));
if (t != pMin->pRight[i])
MoveElement(i, pMin, t->pLeft[i]);
// Similarly to above, try to move max element to the left

for (t = pMax->pLeft[i]; pMax->value[i] < t->value[i]; t = t->pLeft[i])
if (t->minmax == MIN_ELEM)
if (HasCollisionPair(pAABB, GetAABB(t)))
DeleteCollisionPair(pAABB, GetAABB(t));
if (t != pMax->pLeft[i])
MoveElement(i, pMax, t);
}
}
The support function to move the AABB elements within the list is given by:
void MoveElement(int i, Elem *pElem, Elem *pDest)

{
// Unlink element...
pElem->pLeft[i]->pRight[i] = pElem->pRight[i];
pElem->pRight[i]->pLeft[i] = pElem->pLeft[i];
// ...and relink it _after_ the destination element
pElem->pLeft[i] = pDest;
pElem->pRight[i] = pDest->pRight[i];
pDest->pRight[i]->pLeft[i] = pElem;
pDest->pRight[i] = pElem;
}
The preceding code should be a sufficient framework for implementing the addi-
tional code required to complete the linked-list implementation of sort and sweep.
7.5.2 Array-based Sorting

The strength of the linked-list approach is twofold. First, it can handle a large number
of objects, memory permitting. Second, when none or just a few objects move, little
or no work is required to maintain the data structures from frame to frame. Unfor-
tunately, the rather hefty memory overhead for each object AABB is a drawback. The
worst-case O(n2 ) clustering behavior is equally serious.
An alternative is to implement axial extent sorting using arrays. Arrays are more
inflexible when it comes to dynamically allowing more objects, but they use less
memory. Using arrays, even if a single object moves the whole array might need
updating, and thus a full sorting pass is required regardless. At the same time, the
clustering problem is virtually removed and worst-case performance is determined
by the sorting algorithm used [for example, O(n log n) for Quicksort or O(kn) for
radix sort]. Unlike lists, this remains constant even if all objects move, or if they move
over large distances. Using arrays simplifies the code and provides cache-friendly
accessing of memory. The following implementation operates on a single array of
pointers, pointing to the object AABBs.
struct AABB {
Point min;
Point max;
...
};
AABB *gAABBArray[MAX_OBJECTS];
For each pass of the sort-and-sweep algorithm one of the coordinate axes is
selected as the axis to sort along. (The selection is described later.) The selected
axis is specified through a global variable.
int gSortAxis = 0; // Specifies axis (0/1/2) to sort on (here arbitrarily initialized)
Given a sorting axis, the pointers are sorted in ascending order based on the
minimum value of the referenced AABB. To simplify the presentation, the following
code uses stdlib’s qsort(). The required comparison function needed for qsort() to
sort the AABBs is:
// Comparison function for qsort. Given two arguments A and B must return a
// value of less than zero if A < B, zero if A = B, and greater than zero if A > B
int cmpAABBs(const void *a, const void *b)

{
// Sort on minimum value along either x, y, or z (specified in gSortAxis)
float minA = (*(AABB **)a)->min[gSortAxis];
float minB = (*(AABB **)b)->min[gSortAxis];
if (minA < minB) return -1;
if (minA > minB) return 1;
return 0;
}
After the array has been sorted, it is scanned for overlapping boxes. To avoid
keeping track of currently active intervals as the array is swept, this particular imple-
mentation scans the array forward for overlapping objects to the end of the currently
tested box interval.
void SortAndSweepAABBArray(void)
{
// Sort the array on currently selected sorting axis (gSortAxis)
qsort(gAABBArray, MAX_OBJECTS, sizeof(AABB *), cmpAABBs);
// Sweep the array for collisions

float s[3] = { 0.0f, 0.0f, 0.0f }, s2[3] = { 0.0f, 0.0f, 0.0f }, v[3];
for (int i = 0; i < MAX_OBJECTS; i++) {
// Determine AABB center point
Point p = 0.5f * (gAABBArray[i]->min + gAABBArray[i]->max);
// Update sum and sum2 for computing variance of AABB centers
for (int c = 0; c < 3; c++) {
s[c] += p[c];
s2[c] += p[c] * p[c];
}
// Test collisions against all possible overlapping AABBs following current one
for (int j = i + 1; j < MAX_OBJECTS; j++) {
// Stop when tested AABBs are beyond the end of current AABB
if (gAABBArray[j]->min[gSortAxis] > gAABBArray[i]->max[gSortAxis])
break;
if (AABBOverlap(gAABBArray[i], gAABBArray[j]))
TestCollision(gAABBArray[i], gAABBArray[j]);
}
}
// Compute variance (less a, for comparison unnecessary, constant factor)

for (int c = 0; c < 3; c++)

v[c] = s2[c] - s[c] * s[c] / MAX_OBJECTS;
// Update axis sorted to be the one with greatest AABB variance

gSortAxis = 0;
if (v[1] > v[0]) gSortAxis = 1;
if (v[2] > v[gSortAxis]) gSortAxis = 2;
}
During the sweep pass, the variances of the AABB centers along each of the three
axes are computed. After the pass is completed, the axis corresponding to the largest
variance is selected for use the next time the routine is called. This method does
not entirely avoid pathological cases. When objects are clustering in more than one
dimension, worst-case O(n2 ) behavior could still arise.
Insertions are O(1) by adding new AABBs after the position last used in the array.
The sorting pass absorbs the cost of bringing the AABBs to their proper place. When
an AABB is removed, its corresponding pointer also has to be removed from the
array. Given an AABB, a binary search over the array locates the pointer in O(log n)
time. The last pointer in the array replaces the pointer to be deleted. If removals are
frequent, a back pointer inside the AABB structure to the array pointer could be filled
in during the sweep pass, making deletions O(1) as well.
7.6 Cells and Portals

Having an explicit spatial partitioning scheme just for collision detection is not always
necessary. Sometimes it is sufficient to tie into a hierarchical organization already
present for the efficient rendering of world geometry, such as a scene graph. An exam-
ple of an organizational structure that lends itself well to being used with collision
detection is the cells-and-portals method [Teller92], [Luebke95].
This method was developed for rendering architectural walkthrough systems.
These are categorized by heavily occluded environments with high depth complex-
ity. However, the amount of visible geometry in a typical architectural scene is low
in comparison to the total geometry contained in the view frustum. The cells-and-
portals method exploits the occluded nature of these scenes to reduce the amount of
geometry that has to be rendered. The method proceeds by dividing the world into
regions (cells) and the boundaries that connect them (portals). Rooms in the scene
would correspond to cells, and doorways and windows to portals. The portals define
connections between cells and both directly and indirectly determine which cells can
be viewed from a given cell (Figure 7.21).
Rendering a scene partitioned into cells and portals starts with drawing the geom-
etry for the cell containing the camera. After this cell has been rendered, the rendering
7.6 Cells and Portals 339
1 2 3
Figure 7.21 A simple portalized world with five cells (numbered) and five portals (dashed).
The shaded region indicates what can be seen from a given viewpoint. Thus, here only cells
2, 3, and 5 must be rendered.
function is called recursively for adjoining cells whose portals are visible to the
camera. During recursion, new portals encountered are clipped against the current
portal, narrowing the view into the scene. Recursion stops when either the clipped
portal becomes empty, indicating the new portal is not visible to the camera, or
when no unvisited neighboring cells are available.
The portals are implemented as non-self-intersecting polygons. The cells them-
selves are traditionally defined by convex polyhedra. Being convex, the polygons in
the cell can be rendered in any order without risk of overlap, thus obviating the
need to sort polygons. (However, with the Z-buffer capabilities of modern hardware
convex cells are no longer a requirement.) The following pseudocode illustrates an
implementation of this rendering procedure.
RenderCell(ClipRegion r, Cell *c)

{
// If the cell has not already been visited this frame...
if (c->lastFrameVisited != currentFrameNumber) {
// ...timestamp it to make sure it is not visited several
// times due to multiple traversal paths through the cells
c->lastFrameVisited = currentFrameNumber;
// Recursively visit all connected cells with visible portals
for (Portal *pl = c->pPortalList; pl != NULL; pl = pl->pNextPortal) {
// Clip the portal region against the current clipping region
ClipRegion visiblePart = ProjectAndIntersectRegion(r, pl->boundary);
1 2 3
C
4
5
B
Figure 7.22 There are no objects in the cells overlapped by A, and thus object A does not
need to test against any objects. Objects B and C must be tested against each other, as C
crosses the portal between cells 3 and 5 and thus lies partly in the same cell as B.
// If portal is not completely clipped its contents must be partially

// visible, so recursively render other side through the reduced portal
if (!EmptyRegion(visiblePart))
RenderCell(visiblePart, pl->pAdjoiningCell);
}
// Now render all polygons (done last, for back-to-front rendering)
for (Polygon *p = c.pPolygonList; p != NULL; p = p->pNextPolygon)
RenderPolygon(p);
}
}
The same cells-and-portals structure can be used to optimize collision detection

queries. Initially, objects are associated with the cells containing their center point. As
objects move, a ray test determines whether the object has moved out of the current
cell. If it has, connected portals are tested against to find which neighboring cell the
object moved into.
For object-object queries, given an object A only the objects in A’s assigned cell
and those in adjoining cells whose portal A overlaps must now be checked against.
Similarly, for object-world collisions only the polygons in the current cell and those
of any overlapped cells must be checked against (Figure 7.22).
The BSP trees of Chapter 8 serve to divide the world into convex regions and the
resulting spatial partitioning can be used for collision detection in a manner similar
to the cells-and-portals method. In fact, BSP trees are often used in the automated
generation of cells and portals.
7.7 Avoiding Retesting 341
7.7 Avoiding Retesting

A potential concern with partitioning schemes in which a single object may overlap
multiple partitions is that the same two objects can be subject to testing against each
other multiple times. This is clearly a problem when the pairwise test is expensive. If
not handled correctly, it could also lead to collision-resolution code being run for the
objects more than once. A similar problem occurs in ray-tracing applications, wherein
shooting a ray through a uniform grid can result in the ray being tested multiple times
against the same object located in several grid cells. In both cases, it would be wasteful
to perform the same tests multiple times because the same objects are encountered
again. Depending on the situation, a few alternative solutions are available.
7.7.1 Bit Flags

A straightforward solution to the retesting problem is to use a bit flag for indicating
whether an intersection test has already been performed. In the case of shooting rays
through a grid, there would be one bit per object. For object-object intersection tests,
there would be a bit for every pair of objects. If the bit is set, the object (or pair of
objects) in question has already been tested and any further testing can be skipped.
If the bit is not set, the full test must be performed, after which the bit would be set
to indicate the completion of the test.
In the object-object case, the bit flags are easily stored in an array indexed by the
two object indices. In that the array entries (a, b) and (b, a) would represent the same
pair, to avoid wasting memory only the upper triangular half above the diagonal
would actually have to be stored. With a maximum of n objects, the array would then
only have to hold n(n − 1)/2 bits instead of n2 bits. Given two object indices a and b,
with a < b, the index of the corresponding bit is now computed as

bitindex = a(2n − a − 3) 2 + b − 1
instead of
bitindex = an + b.
The following code illustrates a possible implementation of a bit flag array for object-
object intersection testing.
// Allocate enough words to hold a bit flag for each object pair
const int32 MAX_OBJECTS = 1000;
const int32 MAX_OBJECT_PAIRS = MAX_OBJECTS * (MAX_OBJECTS – 1) / 2;

int32 bitflags[(MAX_OBJECT_PAIRS + 31) / 32];
...
void TestObjectPair(int32 index0, int32 index1)
{
assert(index0 != index1);
// Find which object index is smaller and which is larger
int32 min = index0, max = index1;
if (index1 < index0) {
min = index1;
max = index0;
}
// Compute index of bit representing the object pair in the array
int32 bitindex = min * (2 * MAX_OBJECTS - min - 3) / 2 + max - 1;
// Look up the corresponding bit in the appropriate word
int32 mask = 1L << (bitindex & 31);
if ((bitflags[bitindex >> 5] & mask) == 0) {
// Bit not set, so pair has not already been processed;
// process object pair for intersection now
...
// Finally mark object pair as processed
bitflags[bitindex >> 5] |= mask;
}
}
Although this works well for object-object testing, it is less than ideal in the ray-
shooting case. In the object-object scenario, the array of bit flags would have to be
reset once per frame, which is not too bad. For ray shooting, however, the array
would have to be reset for each ray tested! In a typical game there might be tens
or hundreds of ray-like tests performed each frame. Even for a modest number of
objects, this operation now quickly becomes very expensive.
7.7.2 Time Stamping

An alternative way of keeping track of already-tested objects that works better for
the ray-shooting scenario is to keep a running counter that increments for each ray
query and assign the counter number, commonly referred to as a time stamp, to each
object after it has been tested. Then, just before an object is to be tested the time
stamp is checked to see if the object has already been tested in the current frame and
can therefore be ignored.
Figure 7.23 illustrates how time stamping works. First, consider the interaction with
object A only. In cell 1, the ray is tested against A. Because there is no intersection
1 2 3 4
C
A
B
Figure 7.23 Using time stamping avoids having to intersect the ray against object A twice,
in both cells 1 and 2, as the ray is traced through the uniform grid. By storing the computed
intersection with object B into a mailbox, the intersection can be reused in cell 3 without
having to be recomputed.
between A and the ray, A is simply tagged with the time stamp of the ray and the
ray processing continues to the next cell. In cell 2, the ray is again tested against A,
but because it has already been time stamped with the current time object A can be
safely ignored.
However, consider what happens with object B. It is also tested against in cell 1.
There is an intersection between B and the ray, but the intersection point is in cell 3.
Because the intersection point is not in the current cell, it is possible that there could
be another intersection in the cells between (and in fact there is, with object C in
cell 3). Thus, the ray processing must continue to subsequent cells. Before continuing
to the next cell, the intersection with B must be compared to the best intersection
stored so far to see if it constitutes a closer intersection. Because B happens to be
the first object intersected, this is clearly the case and a pointer to B along with the
parametric time at which the ray strikes B are saved as the currently best intersection.
Before B is finally time stamped, it also makes sense to update the number of cells
being traversed by the ray query. Because it is now known that there is an intersection
in cell 3, there is no need to continue processing into cell 4. In cell 2, objects A and
B have to be tested again, but both have been time stamped and are thus ignored,
with processing continued to cell 3. In cell 3, B is again tested and ignored because
of its time stamp. The ray is also tested against object C, which it intersects. As the
intersection with C is found to be closer than the stored intersection with object
B, the best intersection is updated to correspond to this new intersection. At this
point, because there are no more objects to test in cell 3 and the ray processing
was earlier set to stop in this cell the query can now return with the intersection
with C as the result after having performed the intersection test with each object
once only.
One slight problem remains. Regardless of the size used for the time stamp
counter, eventually it will overflow. If enough bits have been assigned for the
counter — which could well approach 64 bits for certain applications — the problem
can safely be ignored as not happening during the uptime of the application. Assume
for now that to conserve memory only an 8-bit counter was used. Every 256 ticks, the
time stamp counter will now overflow and at that time all stored time stamps will
have to be reset. If they are not, an object that has not been time stamped in 256 ticks
and is suddenly tested would incorrectly report that it has already been tested in the
current time slice!
The time stamping technique described here has been described in the context
of ray tracing as mailboxes [Amanatides87]. Another approach to eliminating mul-
tiple intersections and redundant calculations is the residency masks described in
[Cychosz92].
In most applications, resetting the time stamp values will go unnoticed. However,
for applications with a huge number of objects this operation could become expensive.
For those applications, the solution is then to not reset all time stamp values at once.
This solution is explored in the next section.
7.7.3 Amortized Time Stamp Clearing

The one-time overhead of resetting time stamp counters can be lessened using an
amortized clearing scheme. Instead of clearing the counters all at once when the
global counter overflows, the set of all time stamp counters can be divided into
smaller blocks with a single block being reset each frame.
The best illustration of this amortized method is through a small example (see
Table 7.2). Consider having some n objects, say 10, that are divided into three blocks
(of three, three, and four objects each). Let the time stamp counters also count up
to three. At start, all objects are initialized to have a time stamp of 0. On the first
frame, the global time stamp counter is incremented to 1. After all objects have been
updated, it is possible for each block to contain objects with time stamps of either 0
or 1. Before ending the first frame, block 0 is cleared to the current value of the global
time stamp counter.
The same procedure is now repeated on each successive frame, with the next
block of objects cleared, again to the current value of the global counter of that frame.
Referring to Table 7.2, note that at the end of frame 4 there can no longer exist an
object with a time stamp of value 1, which is the value the global counter will assume
on frame 5. Similarly, at the end of frame 5 there is no object with a time stamp value
of 2, and so on for all subsequent frames.
To further illustrate how the amortized clearing method works, the following code
is an example of what an implementation of the method could look like. First, some
required constant values are defined.
// Use 8 bits for the time stamp counter [0..255]

#define MAX_COUNTER_VALUE 255
// Divide up all time-stamped objects into as many blocks

#define NUM_BLOCKS MAX_COUNTER_VALUE
Table 7.2 Indicating possible time stamp values for objects in the three blocks at various points. At the
point at which objects are about to be updated there is never an object with a time stamp
equal to the current global time stamp. Thus, even though only a few objects are cleared
each frame there is never a time stamp conflict.
Frame Counter Block 0 Block 1 Block 2 Comment
0 0 0 0 0 All object time stamps are cleared to 0 on

startup
1 1 0/1 0/1 0/1 Incrementing global counter, updating
objects
1 0/1 0/1 Clearing (time stamps of objects in) block
0 to 1
2 2 1/2 0/1/2 0/1/2 Incrementing global counter, updating
objects
1/2 2 0/1/2 Clearing block 1 to 2
3 3 1/2/3 2/3 0/1/2/3 Incrementing global counter, updating
objects
1/2/3 2/3 3 Clearing block 2 to 3
4 0 0/1/2/3 0/2/3 0/3 Incrementing global counter, updating
objects
0 0/2/3 0/3 Clearing block 0 to 0; now no object with
time stamp of 1
5 1 0/1 0/1/2/3 0/1/3 Incrementing global counter, updating
objects
0/1 1 0/1/3 Clearing block 1 to 1; now no object with
time stamp of 2
6 2 0/1/2 1/2 0/1/2/3 Incrementing global counter, updating
objects
0/1/2 1/2 2 Clearing block 2 to 2; now no object with
time stamp of 3
Once at initialization, all object time stamp counters are cleared to zero.
blockToClear = 0;
tickCounter = 0;
for (i = 0; i < MAX_OBJECTS; i++)
object[i].timeStamp = tickCounter;
During each frame the time stamp counters are used as normal.
// Increment the global time stamp counter

tickCounter++;
// Do any and all object testing required for the frame
for (i = 0; i < MAX_OBJECTS; i++) {
if (object[i].timeStamp == tickCounter) {
// Already processed this object this frame, do nothing
continue;
} else {
// Process object for intersection here
...
// Mark object as processed
}
}
At the end of each frame — or between rays in case of shooting rays — a subset of
all stored time stamps is cleared by marking them with the current time stamp value
(which has served its purpose for this frame).
// Reset the time stamp for all objects in the current block to be cleared
from = blockToClear * MAX_OBJECTS / MAX_COUNTER_VALUE;
to = (blockToClear + 1) * MAX_OBJECTS / MAX_COUNTER_VALUE;
for (i = from; i < to; i++)
// Indicate that the next block should be cleared the next frame
if (++blockToClear >= NUM_BLOCKS)
blockToClear = 0;
// Wrap the global time stamp counter when it exceeds its maximum value
if (tickCounter >= MAX_COUNTER_VALUE - 1)
tickCounter = 0;
The same technique can be applied for amortized clearing of other buffers. For
example, by setting aside a few bits of the time stamp it could be used to spread the
clearing of a (software) Z-buffer over a number of frames.
7.8 Summary
Spatial partitioning is an approach to accelerating broad-phase processing by dividing
space into disjoint regions and associating scene objects with all regions they overlap.
7.8 Summary 347
Pairwise tests then must be performed only for those objects that share a region. In
some cases objects are associated with just a single region, in which case neighboring
regions also must be explored for potential collisions.
In this chapter, three types of spatial partitioning methods were explored: grids,
trees, and spatial sorting. Grids are often uniform, meaning that they consist of grid
cells of equal size. When large, grids may consume large amounts of memory. One
way to reduce the memory requirements of grids is to use hashed storage, as described
in Section 7.1.3, which has the benefit of allowing the grid to be of infinite extent.
Grids can also be expressed implicitly. The implicit bit grid, in particular, is a very
efficient spatial partitioning method. The hierarchical grid addresses the problem of
objects being of greatly varying sizes, making it difficult to set a grid cell size for a
uniform grid.
One of the tree representations described was the octree. It partitions space into
eight uniform-size cells, then recursively partitions the cells in the same way. Thanks
to their regular structure, octrees can be represented linearly, obviating the need to
represent tree links using pointers, and thereby saving memory. The octree can also
be made loose, meaning that its cells are expanded to overlap partially. Loose octrees
address the problem of objects not being able to descend farther down the tree when
they straddle a splitting plane (and are only allowed to be referenced from a single
octree cell).
The k-d tree is a generalization of the octree in that it can represent the same
spatial partitioning as the octree, but not vice versa. The k-d tree divides space into
two, along one dimension at a time and at an arbitrary position. The simpler structure
of the k-d tree makes queries on it easier.
Spatial sorting involves maintaining all objects in a sorted structure along one or
more axes. The sorted structure is incrementally updated when objects move. Because
the structure is sorted, object collisions are detected by examining neighboring objects
without requiring a search.
Chapter 8 discusses one additional tree representation, which is a generalization
of k-d trees. This representation can also be used as a spatial partitioning method.

Christer Ericson Real Time Collision Detection en 324 386

Uploaded by

Copyright:

Available Formats

Christer Ericson Real Time Collision Detection en 324 386

Uploaded by

Document Information

Original Description:

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Christer Ericson Real Time Collision Detection en 324 386

Uploaded by

Copyright:

Available Formats

Chapter 7

7.1 Uniform Grids

(a) (b) (c) (d)

7.1.1 Cell Size Issues

7.1.2 Grids as Arrays of Linked Lists

7.1.3 Hashed Storage and Inﬁnite Grids

#define NUM_BUCKETS 1024

// Computes hash bucket index in range [0, NUM_BUCKETS-1]

index = hash(x,y) mod n

7.1.4 Storing Static Data

7.1.5 Implicit Grids

10000 00010 00110 00101 01001

b = (r[i] | r[i+1]) & (c[j] | c[j+1]);

This rewrite generalizes to an arbitrary number of cells overlapped, so that the

// Define the two global bit arrays

void TestObjectAgainstGrid(Object *pObject)

// Compute the extent of grid cells the bounding sphere of A overlaps.

for (int i = 0; i < NUM_OBJECTS_DIV_32; i++)

7.1.6 Uniform Grid Object-Object Test

10 × 10 50 × 50 100 × 100 500 × 500

1,000 2,500 12,500 25,000 125,000

7.1.6.1 One Test at a Time

// Objects placed in single cell based on their bounding sphere center.

// Objects placed in single cell based on AABB minimum corner vertex.

// Objects placed in all cells overlapped by their AABB.

7.1.6.2 All Tests at a Time

// Objects placed in single cell based on their bounding sphere center.

// in the opposite direction will be handled when checking the objects

// Objects placed in single cell based on AABB minimum corner vertex.

if (object overlaps east cell border)

7.1.7 Additional Grid Considerations

7.2 Hierarchical Grids

7.2.1 Basic Hgrid Implementation

const float SPHERE_TO_CELL_RATIO = 1.0f/4.0f; // Largest sphere in cell is 1/4*cell size

Adding an object into the hgrid now can be done as follows.

void AddObjectToHGrid(HGrid *grid, Object *obj)

// Assert if object is larger than largest grid cell

Removing an object from the hgrid is done in a corresponding manner.

void RemoveObjectFromHGrid(HGrid *grid, Object *obj)

// Now scan through list and unlink object ’obj’

// Test collisions between object and all objects in hgrid

// For each new query, increase time stamp counter

for (int level = startLevel; level < HGRID_MAX_LEVELS;

// Compute ranges [x1..x2, y1..y2] of cells overlapped on this level. To

// Check all the grid cells overlapped on current level

// Loop through all objects in the bucket to find nearby objects

7.2.2 Alternative Hierarchical Grid Representations

7.2.3 Other Hierarchical Grids

7.3.1 Octrees (and Quadtrees)

// Octree node data structure

The analogous structure to the octree in two dimensions is known as a quadtree.

7.3.2 Octree Object Assignment

// Preallocates an octree down to a specific depth

// Recursively construct the eight children of the subtree

The code for inserting an object now becomes:

void InsertObject(Node *pTree, Object *pObject)

for (int i = 0; i < 3; i++) {

InsertObject() can be changed so that whenever a child node pointer is NULL

If nodes should be deleted in a corresponding manner whenever they no longer

void AddObjectToHGrid(HGrid grid, Object obj)

void RemoveObjectFromHGrid(HGrid grid, Object obj)

void InsertObject(Node pTree, Object pObject)

AABB GetAABB(Elem pElem)

void MoveElement(int i, Elem pElem, Elem pDest)

int cmpAABBs(const void a, const void b)