Graphics Reference
In-Depth Information
(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.
