Graphics Reference
In-Depth Information
point
P
within the extent of the grid lies in exactly one cell. The multidimensional
index of that cell is given by subtracting the minimal vertex of the grid from
P
,
dividing by the extent of one cell, and then rounding down. For a grid with the
minimal corner at the origin and cells of extent one distance unit in each dimen-
sion, this is simply the “floor” of the point. Thus, if we hold cell extent constant,
the containing cell can be found in constant time, but the storage space for the
structure will be proportional to the sum of the number of members
and
the vol-
ume of the grid. Intersection queries on a grid generally run in time proportional
to the volume of the query shape (or length, for a ray).
Grids are simple and efficient to construct compared to trees, and insertion and
removal incur comparatively little memory allocation or copying overhead. They
are thus well suited to dynamic data and are frequently used for collision detection
and other nearest-neighbor queries on dynamic objects.
Listing 37.16 shows one possible representation of a grid in three dimensions,
with some auxiliary methods. The underlying representation is a multidimensional
array. As for images, which are 2D arrays of pixels, grids are frequently imple-
mented by unrolling along each axis in turn to form a 1D array. In the listing,
the
cellIndex
method maps points to 3D indices and the
cell
method returns a
reference to the cell given by a 3D index in constant time.
Listing 37.16: Sample implementation of a 3D x-major grid and
some helper functions.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
struct
Index3 {
int
x, y, z;
};
template
<
class
Value
,
class
Bounds = PrimitiveKeyTrait<
Value
>>
class
Grid3D {
/
*
In length units, such as meters.
*
/
float
cellSize;
Index3 numCells;
typedef
List<
Value
, Bounds> Cell;
/
*
There are numCells.x
*
numCells.y
*
numCells.z cells.
*
/
std::vector<Cell> cellArray;
/
*
Map the 1D array to a 3D array. (x,y,z) is a 3D index.
*
/
Cell& cell(
const
Index3& i) {
return
cellArray[i.x + numCells.x
*
(i.y + numCells.y
*
z)];
}
Index3 cellIndex(
const
Point3
&P)
const
{
return
Index3(floor(P.x / cellSize),
floor(P.y / cellSize),
floor(P.z / cellSize));
}
bool
inBounds(
const
Index3& i)
const
{
return
(i.x >= 0) && (i.x < numCells.x) &&
(i.y >= 0) && (i.y < numCells.y) &&
(i.z >= 0) && (i.z < numCells.z);
}
...
};
