Graphics Reference
In-Depth Information
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
n
1/3
rule: given
n
objects, divide space into a
k
n
1/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.
×
k
×
k
grid, with
k
=
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.
