Spatial coherence, spatial division or space tracing refer to the subdivision of 3-space to take advantage of spatial structure of the objects. The technique, rather than checking rays against all objects in the scene or against bounded volume approximations to the objects in the scene, "poses" the question: "Is the 3-space region through which the ray is currently passing occupied by any objects?".
Bounding volume schemes associate a volume with an object, whereas the subdivision schemes addressed here represent the objects as volumes by labelling the 3D space.
Major disadvantages of the bounding volume approach are:
In spatial sub-division methods we build up (in a pre-processing stage) additional structure to the objects to constrain the search.
A general protocol for spatial coherence schemes is:
An octree is a hierarchical data structure that specifies the occupancy of cubic regions (which vary in size) of object space.
A large region is either
and the corresponding quadtree is
To construct the quadtree,
For constructing an octree, we need only a trivial modification of the above procedure by
The basic idea is to trace a ray from subregion to subregion. We need as input an octree and a ray together with its start point, P. The output is either an intersection point or the indication of empty intersection.
A 2D example is given in Watt and Watt, page 224 (Figure 9.13). The spatial subdivision in that example is terminated when each sub-region contains on one object.
Step 1 above can be implemented by a typical tree search algorithm. The maximum number of nodes that can be traversed is equal to the maximum depth of the tree.
In practice, the depth is small for even subdivision as fine as 1024 x 1024 x 1024 where the result octree depth will have a maximum of log8(1024x1024x1024) = 10.
When building the octree data structure there are certain trade-offs that you can consider. Firstly you can limit the depth of the tree so the search is faster, but this means that in the smallest subdivision there may be several (more than one anyway) candidates for the intersection calculation. Alternatively we can continue the subdivision until each cell contains a single object, making the intersection calculation faster, but which may make the maximum length of any branch very long.
One of the disadvantages of octrees is that the volumes that contain a single object may be large. This is equivalent to a bounding volume which has a large "void" area - ie. the bounding shape is inappropriate for the object shape. This results in unnecessary intersection calculations.
Spatially Enumerated Auxiliary Data Structure
The name SEADS suggests dividing all of the space of interest into equally sized cells regardless of their occupancy by objects, as shown in the example below;
Since here the sub-division occurs regardless of whether the cell is occupied by an object or not, SEADS will generate more cells than the octree. This therefore results in unnecessary demand for storage and this is the primary disadvantage of this method - it has heavy space overheads.
This data structure is analogous to the 2D sub-division of the screen into pixels. It is this fact that gives rise to the major advantage of this technique - fast tracking algorithms are possible. The fast tree search algorithm in question is referred to as the 3D-DDA (Digital Differential Analyser). It is an extension of the DDA, which is used to determine the set of pixels passed through by a line. It is extended to track a ray through the 3D SEADS grid. The speed of the algorithm arises from the fact that floating point multiplication and division are avoided, requiring only addition, subtraction and comparison - predominantly integer addition on the cell coordinates. (recall the advantages of using structured grids).
The BSP tree is essentially the same as the octree, with changes to the data structure representation used to index into the tree. In a general scene, objects will often be unevenly distributed throughout the occupied space.
Binary space partitioning scheme is used to provide a balanced tree according to the scene. When a BSP is used to represent sub-division of space into cubic cells, it has no advantage over an octree. However, the divisions need not be even.
Octree, SEADS, and Binary Space Partitioning all have two potential problems.
This problem can be resolved if we add a unique tag for each object. The result of intersection tests for each object with respect to the ray are then made available.
This problem can be avoided by adopting a more effective termination condition. That is, we terminate the ray tracing when the nearest intersection point is contained in the current box.