Spatial Data Structures - Computer Graphics: Principles and Practice - page 1093

Listing 37.15: Bounding volume hierarchy using axis-aligned boxes.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

template < class Value , class Trait = PrimitiveKeyTrait< Value >>
class BoxBVH {
class Node {
public :
std::vector<Node * > childArray;

/ * Children in this leaf node. These are pointers because a value
may appear in two different nodes. * /
List< Value * > valueArray;

AABox bounds;
};

Node * root;
...
};

The bounding volumes chosen tend to be balls or axis-aligned boxes because
those admit compact storage and intersection queries. These are also known as
sphere trees or AABB trees, respectively.

37.7 Grid

37.7.1 Construction
A grid is the generalization of a radix-based 1D array. It divides a finite rectangu-
lar region of space into equal-sized grid cells or buckets (see Figure 37.13). Any

Spatial structure

g

b

(16, 6)

(3, 6)

(12, 3)

a

(1, 4) e

c

d

(7.5, 2.5)

(13, 1)

(8, 2)

f

Logical structure

g

c d f a e b

Figure 37.13: A depiction of a 2D grid of values with point keys. The logical structure is
that of an implementation that unrolls the underlying 2D array in row-major order starting
from the bottom row.