In the technique explained in the previous section 
, volumes
are associated with objects. With spatial subdivision (or spatial coherence),
the reverse is the case and objects are associated with volumes. In ray
tracing this technique reduces the number of object intersection tests carried
out by limiting the tests to the objects that occupy the sub-space the ray
is passing through. With collision detection, the number of objects that are
tested against each other is reduced to just the objects that occupy a given
sub-space. Spatial coherence is a more intuitive method for speeding up
collision detection --- only test objects against each other if they are close.
The hierarchical bounding volume scheme exhibits spatial coherence because
the hierarchy is generated by grouping together objects that are close.
Three of the more common methods of spatial sub-division that have been used in ray tracing are octrees, binary space partitioning trees (BSP trees), and uniform spatial division.
: quadtree division of a 2D scene
Octrees are the 3D equivalent of quadtrees, and divide space up into cubic
regions known as voxels. The basic algorithm is to divide a region into 8
equally sized voxels, using planes parallel to the x, y, and z axis, if
the region contains greater than m objects and the depth of the octree hasn't
exceeded its limit. The number of objects, m, is usually one or two.
Figure shows a 2D scene that has been
subdivided using the criteria that regions are subdivided if they contain one
or more objects (or parts of objects), with the quadtree limited to a depth of
4. The example is easily extended to 3 dimensions. The octree described in
this section is a variant used to speed up ray tracing by limiting the number
of objects a ray is tested against. Octrees can also be used to
represent objects in a similar manner to the way pixels are used to
represent objects in 2D.
The octree allows adaptive subdivision and makes use of object coherence --- regions that are densely populated by objects can be more finely subdivided, while sparsely populated regions can be subjected to less subdivision. Also regions that are near each other are represented in the tree by nodes that are close to each other. Adaptive subdivision can lead to trees that are extremely unbalanced and which incur high search costs when a ray is being tracked through the object space (which involves a traversal of the octree).
This problem doesn't apply when using the octree to increase the efficiency of collision detection, as the tree doesn't need to be traversed so there is no need to worry about producing balanced trees. In fact the octree structure doesn't need to be stored (Glassner [Gla84] also doesn't explicitly store the octree structure in his method for increasing the speed of tree traversal). With spatial subdivision, we are only interested in determining which objects are close to each other, and thus which objects need to be tested against each other. Once a region has been divided such that it has no more than m objects contained within, collision detection can be carried out between the m objects, after which the region can be ignored (for the current time step at least).
Binary space partitioning trees (BSP trees) are closely related to octrees and quadtrees. In n dimensional space, subdivision consists of partitioning space into two subspaces by a n-1 dimensional plane, and then classifying elements as belonging to one or the other of the subspaces. One subspace is regarded as positive and the other as negative, while the actual splitting plane is arbitrarily assigned as belonging to either space. Elements that span the partitioning plane are split into two or more pieces and these pieces are added to the appropriate subspace.
Figure shows the creation of a BSP tree in 2D. In this
example the partitioning lines are restricted to being parallel to the x and
y axis, and at each partitioning the line chosen is at the opposite
orientation to the previous one. The subspaces a, b, c, d, e, and
f, exist at the nodes of the tree, while x and y are the partitioning
lines.
By restricting the splitting planes appropriately and having the right
splitting criteria, BSP trees can be made to behave like octrees and quadtrees.
Figure: Binary space partitioning of a 2D space
Generally there is no restriction on the orientation of the splitting planes. The choice of splitting plane, as well as at what point tree construction should terminate (eg. when each leaf node has less than m objects), depends on the intended use of the tree. Often the planes are chosen from amongst the support planes of the polygons in the object database (if the objects are being modelled with a polygonal representation), and classification and splitting is at the polygon level.
To create a balanced tree the splitting planes should be chosen so that equal numbers of objects are placed in the resulting sub regions. In conflict with this criteria for choosing a splitting plane is the goal of minimizing the number of objects split. Choosing the partitioning planes to produce a balanced tree will often cause a lot of splitting of objects, while reducing splitting often gives an unbalanced tree. However in using a BSP tree to reduce the number of objects tested against each other, traversal of the tree isn't required (as with the octree), and the structure of the tree needn't be stored.
In their ``Accelerated Ray-Tracing System'' (ARTS), Fujimoto, Tanaka, and Iwata [FTI86] used a uniform spatial division scheme which they called SEADS (Spatially Enumerated Auxiliary Data Structure). In the SEADS scheme, space is simply divided into a fixed number of equally sized voxels. The main advantage of this was the increased speed with which a ray could be tracked through the structure, compared with tracking a ray through an octree or BSP tree.
The disadvantages of SEADS are that it completely fails to take into account
the coherency of objects in a scene, and it makes ``unnecessary'' [WW92]
demands on memory. The uniform division means regions of high object density
have the same level of division as regions of low object density. High costs
in memory occur because empty regions can be represented by many empty voxels
compared with the octree structure where an empty region is represented by one
voxel (or a few voxels). Using finer spatial division to reduce the
number of objects in each cell results in an 
increase in the memory
required (where n is the number of cells along a coordinate axis).
However the results presented by Fujimoto showed that the SEADS scheme still out performed octrees in ray tracing scenes, which was due mainly to the speed of ray tracking through SEADS. Their experiments also showed that there was an optimum number of cells that provided the best results, so that using finer spatial division (and hence more memory) wasn't necessary.
As noted before, the chief advantage of SEADS is the fast tracking of a ray through the structure which (again, as noted before) isn't needed with collision detection. However Fujimoto also found that the encoding time for SEADS was an order of magnitude shorter than that required for setting up the octree. This is important in the collision detection scheme where the object database changes over time and the spatial division structure needs to be rebuilt/modified constantly throughout the animation simulation.
Pradhan and Mukhopadhyay [PM91], and Hsiung and Thibadeau [HT92] developed hybrid octree-SEADS methods that minimize the disadvantages, and maximize the advantages inherent to each scheme.
