i
i
i
i
i
i
i
i
12.3. Spatial Data Structures 281
t
xmin
and t
xmax
expands to:
if (x
d
≥ 0) then
t
xmin
=(x
min
− x
e
)/x
d
t
xmax
=(x
max
− x
e
)/x
d
else
t
xmin
=(x
max
− x
e
)/x
d
t
xmax
=(x
min
− x
e
)/x
d
A similar code expansion must be made for the y cases. A major concern is that
horizontal and vertical rays have a zero value for y
d
and x
d
, respectively. This
will cause divide by zero which may be a problem. However, before addressing
this directly, we check whether IEEE floating point computation handles these
cases gracefully for us. Recall from Section 1.5 the rules for divide by zero: for
any positive real number a,
+a/0=+∞;
−a/0=−∞.
Consider the case of a vertical ray where x
d
=0and y
d
> 0. We can then
calculate
t
xmin
=
x
min
− x
e
0
;
t
xmax
=
x
max
− x
e
0
.
There are three possibilities of interest:
1. x
e
≤ x
min
(no hit);
2. x
min
<x
e
<x
max
(hit);
3. x
max
≤ x
e
(no hit).
For the first case we have
t
xmin
=
positive number
0
;
t
xmax
=
positive number
0
.
This yields the interval (t
xmin
,t
xmin
)=(∞, ∞). That interval will not overlap
with any interval, so there will be no hit, as desired. For the second case, we have
t
xmin
=
negative number
0
;
t
xmax
=
positive number
0
.
i
i
i
i
i
i
i
i
282 12. Data Structures for Graphics
This yields the interval (t
xmin
,t
xmin
)=(−∞, ∞) which will overlap with all
intervals and thus will yield a hit as desired. The third case results in the interval
(−∞, −∞) which yields no hit, as desired. Because these cases work as desired,
we need no special checks for them. As is often the case, IEEE floating point
conventions are our ally. However, there is still a problem with this approach.
Consider the code segment:
if (x
d
≥ 0) then
t
min
=(x
min
− x
e
)/x
d
t
max
=(x
max
− x
e
)/x
d
else
t
min
=(x
max
− x
e
)/x
d
t
max
=(x
min
− x
e
)/x
d
This code breaks down when x
d
= −0. This can be overcome by testing on the
reciprocal of x
d
(A. Williams et al., 2005):
a =1/x
d
if (a ≥ 0) then
t
min
= a(x
min
− x
e
)
t
max
= a(x
max
− x
e
)
else
t
min
= a(x
max
− x
e
)
t
max
= a(x
min
− x
e
)
12.3.2 Hierarchical Bounding Boxes
The basic idea of hierarchical bounding boxes can be seen by the common tactic
of placing an axis-aligned 3D bounding box around all the objects as shown in
Figure 12.25. Rays that hit the bounding box will actually be more expensive
to compute than in a brute force search, because testing for intersection with the
box is not free. However, rays that miss the box are cheaper than the brute force
search. Such bounding boxes can be made hierarchical by partitioning the set of
Figure 12.25. A2Draye
+
t
d is tested against a 2D
bounding box.
objects in a box and placing a box around each partition as shown in Figure 12.26.
The data structure for the hierarchy shown in Figure 12.27 might be a tree with
the large bounding box at the root and the two smaller bounding boxes as left and
right subtrees. These would in turn each point to a list of three triangles. The
intersection of a ray with this particular hard-coded tree would be:
if (ray hits root box) then
if (ray hits left subtree box) then
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
i
i
i
i
i
i
i
i
284 12. Data Structures for Graphics
left-hit = (left = NULL) and (left → hit(a + tb, t
0
, t
1
,lrec))
right-hit = (right = NULL) and (right → hit(a + tb, t
0
, t
1
, rrec))
if (left-hit and right-hit) then
if (lrec.t < rrec.t) then
rec = lrec
else
rec = rrec
return true
else if (left-hit) then
rec = lrec
return true
else if (right-hit) then
rec = rrec
return true
else
return false
else
return false
Note that because left and right point to surfaces rather than bvh-nodes
specifically, we can let the virtual functions take care of distinguishing between
internal and leaf nodes; the appropriate hit function will be called. Note that
if the tree is built properly, we can eliminate the check for left being
NULL. If we want to eliminate the check for right being NULL, we can
replace NULL right pointers with a redundant pointer to left. This will
end up checking left twice, but will eliminate the check throughout
the tree. Whether that is worth it will depend on the details of tree
construction.
There are many ways to build a tree for a bounding volume hierarchy. It is
convenient to make the tree binary, roughly balanced, and to have the boxes of
sibling subtrees not overlap too much. A heuristic to accomplish this is to sort
the surfaces along an axis before dividing them into two sublists. If the axes are
definedbyanintegerwithx =0, y =1,andz =2we have:
function bvh-node::create(object-array A, int AXIS)
N = A.length
if (N=1)then
left = A[0]
right = NULL
bbox = bounding-box(A[0])
i
i
i
i
i
i
i
i
12.3. Spatial Data Structures 285
else if (N=2)then
left-node = A[0]
right-node = A[1]
bbox = combine(bounding-box(A[0]), bounding-box(A[1]))
else
sort A by the object center along AXIS
left= new bvh-node(A[0..N/2 − 1], (AXIS +1) mod 3)
right = new bvh-node(A[N/2..N−1], (AXIS +1) mod 3)
bbox = combine(left → bbox, right → bbox)
The quality of the tree can be improved by carefully choosing AXIS each time.
One way to do this is to choose the axis such that the sum of the volumes of the
bounding boxes of the two subtrees is minimized. This change compared to ro-
tating through the axes will make little difference for scenes composed of isotopi-
cally distributed small objects, but it may help significantly in less well-behaved
scenes. This code can also be made more efficient by doing just a partition rather
than a full sort.
Another, and probably better, way to build the tree is to have the subtrees
contain about the same amount of space rather than the same number of objects.
To do this we partition the list based on space:
function bvh-node::create(object-array A, int AXIS)
N = A.length
if (N =1)then
left = A[0]
right = NULL
bbox = bounding-box(A[0])
else if (N =2)then
left = A[0]
right = A[1]
bbox = combine(bounding-box(A[0]), bounding-box
(A[1
]))
else
find the midpoint m of the bounding box of A along AXIS
partition A into lists with lengths k and (N-k) surrounding m
left = new bvh-node(A[0..k], (AXIS +1) mod 3)
right = new bvh-node(A[k+1..N−1], (AXIS +1) mod 3)
bbox = combine(left → bbox, right → bbox)
Although this results in an unbalanced tree, it allows for easy traversal of empty
space and is cheaper to build because partitioning is cheaper than
sorting.
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.