i
i
i
i
i
i
i
i
12.3. Spatial Data Structures 283
check three triangles for intersection
if (ray intersects right subtree box) then
check other three triangles for intersection
if (an intersections returned from each subtree) then
return the closest of the two hits
else if (a intersection is returned from exactly one subtree) then
return that intersection
else
return false
else
return false
Some observations related to this algorithm are that there is no geometric ordering
Figure 12.26. The bound-
ing boxes can be nested by
creating boxes around sub-
sets of the model.
between the two subtrees, and there is no reason a ray might not hit both subtrees.
Indeed, there is no reason that the two subtrees might not overlap.
A key point of such data hierarchies is that a box is guaranteed to bound all
objects that are below it in the hierarchy, but they are not guaranteed to contain
all objects that overlap it spatially, as shown in Figure 12.27. This makes this
Figure 12.27. The
gray box is a tree node
that points to the three gray
spheres, and the thick black
box points to the three black
spheres. Note that not all
spheres enclosed by the
box are guaranteed to be
pointed to by the corre-
sponding tree node.
geometric search somewhat more complicated than a traditional binary search on
strictly ordered one-dimensional data. The reader may note that several possible
optimizations present themselves. We defer optimizations until we have a full
hierarchical algorithm.
If we restrict the tree to be binary and require that each node in the tree have a
bounding box, then this traversal code extends naturally. Further, assume that all
nodes are either leaves in the tree and contain a primitive, or that they contain one
or two subtrees.
The bvh-node class should be of type surface, so it should implement
surface::hit. The data it contains should be simple:
class bvh-node subclass of surface
virtual bool hit(ray e + td, real t
0
, real t
1
, hit-record rec)
virtual box bounding-box()
surface-pointer left
surface-pointer right
box bbox
The traversal code can then be called recursively in an object-oriented style:
function bool bvh-node::hit(ray a + tb, real t
0
, real t
1
, hit-record rec)
if (bbox.hitbox(a + tb, t
0
, t
1
)) then
hit-record lrec, rrec