152

Heuristics for Ray Tracing Using Space Subdivision

J . David MacDonald and Kellogg S . Booth
Computer Graphics Laboratory, Department of Computer Science
University of Waterloo , Waterloo , Ontario , Canada N2L 3G1
Tel: 519/888-4534, E-Mail: KSBooth @cgl.waterloo .edu

Abstract
Ray tracing requires testing rays against a scene todetermine which objects, if any, are intersected . An
efficient method of reducing the computation
involved in the intersection tests is to organize theobjects into a hierarchical data structure. We
describe two heuristics for constructing spacesubdivisions that partition objects using bin trees . One
is based on the intuitive notion that the surface areaof an object is a good estimate of its probability ofintersecting a ray . The second heuristic arises fromthe observation that the optimal splitting plane for a
volume lies between the spatial median plane and theobject median plane of the volume. Techniques fortraversing the space subdivision are then discussedwith suggestions for reducing the traversal costs byincorporating cross links between nodes , generalizing
Samet's notion of ropes for octrees. Simulation
results are presented for the surface area heuristic andthe cross link scheme. These results for the bin trees
generalize to other common hierarchical data
structures .
Keywords: octree, ray tracing, space subdivision,
surface area heuristic .
1. Preliminaries
Ray tracing is a popular algorithm for computer
rendering of synthetic images. The main reason thatthe use of ray tracing is so widespread is thesimplicity of coding and the comparative ease withwhich ray tracing renders many realistic effects,
including shadows , penumbrae, reflection , refraction(transparency), and motion blur [2] . The principal
drawback of ray tracing is its comparatively highcomputational cost , which is due primarily to the highoccurrence of one basic operation, the ray-sceneintersection test. An introduction to ra y tracing may
be found in [5] .

The simplest, brute force method of determining
the ray-scene intersection is to test the ray against
each object, remembering which object, if any , has
the nearest point of intersection . This has been vastly

improved with the use of scene structuring [3- 4, 6-8,
10- 11, 13, 16], which reduces the number of rayobject intersection tests required .
Scenes are modelled with a variety of different
implicitly and explicitly defined objects and surfaces.
They range from simple objects , such as spheres,
ellipses, triangles , polygons, and parallelepipeds, tomore complex surfaces such as cubic patches, spline
surfaces, and implicit functions . For all but thesimplest of these , an intersection test of a ray with theobject is a nontrivial computation. To speed up theintersection test, a bounding volume is placed aroundthe object. The bounding volume is typically a very
simple type of object with an easy intersection test,
such as a sphere or a parallelepiped which has sides
perpendicular to a major axis. In order to determine
if a ray intersects a particular object, the ray is firsttested against the object's bounding volume. If theray does not intersect the bounding volume, it does
not intersect the object inside. Otherwise, the ray
must be tested against the object in the usual manner:
A common type of object for bounding volumes is arectangular parallelepiped or box with each side
perpendicular to a major axis.
The notion of a bounding box generalizes to theidea of scene structuring with a hierarchical data
structure. There are two main classes of hierarchy
applicable to ordering the scene, each a dual of the
Object subdivision groups the objects
other.
composing a scene, recording the space that eachobject inhabits. Space subdivision subdivides space,recording the objects that inhabit each region of
space.
A hierarchical extents tree is a recursive
subdivision of objects in this manner. The root of thetree corresponds to a bounding volume containing allof the objects in the scene . The children of a nodecorrespond to a set of bounding volumes that divide
the objects contained in the node's bounding volume .
When the number of objects in a node's bounding
volume is one , the node is given a single child where
the object is actually stored . Although reference ismade to objects enclosed by , or contained within, aGraphics Interface '89

153

node's bounding volume, it should be observed that
objects are actually only stored in the leaves.
Algorithms to build object subdivisions are reported
in [8,12].
The dual of object subdivision is spacesubdivision, which subdivides object space into
disjoint subregions, recording the objects which
inhabit each subset of space. The octree is a common
type of space subdivision. Initially, the octree
consists of only one node, representing the bounding
volume containing all of the objects in the scene,
exactly the same as the root of a hierarchical extent
tree. Using three splitting planes , one perpendicular
to each of the three major axes, the bounding volume
is divided into eight smaller ones with eight childrenof the root created (hence the term "octree"). Eachobject is placed in whichever child encloses it. Eachof the children may be re cursively subdivided .
The bounding volumes associated with nodes areusually referred to as voxels, which is the threedimensional analog of a pixel. Sometimes an object
belongs in more than one voxel. In this case either
the object is split into new objects that do not belong
in more than one node's voxel or the object (moreoften a pointer to the object) is stored in both nodes[3,4,10]. As with the hierarchical extent tree, theresulting octree has all of the objects stored in theleaves and none in the interior nodes . Unlike thehierarchical extent tree, a single leaf may containmore than one object.
If a ray intersects the root node of an octree, it isrecursively tested against the children of intersected
node. When a leaf node is intersected, all of theobjects stored in it are tested for intersection and thenearest, if any, is recorded. The octree allows testingnodes in the order that the ray passes through thembecause it subdivides space into disjoint regions . The
algorithm can halt as soon as it finds a leaf in which
an object is intersected.

The choice of splitting planes for each axis ofsubdivision in an octree may be any arbitrary planewithin the current box. Often the plane that is
halfway between the sides of the box, the spatial
median, is chosen. We refer to this as uniform spacesubdivision. Choosing the spatial median means thatthe positions of the planes need not be stored in eachnode because they can be generated from knowing
the limits of the node .
There is an important clarification to be madeconcerning the determination of whether a certain
object belongs in a given node of an octree. An
object belongs in a node only if the surface of theobject intersects the node's box. The reason for thisis that the point of intersection of a ray with an object
cannot occur within a box that does not contain somepart of the surface.

Octrees have a problem peculiar to spacesubdivisionhierarchies.
Dependingontheimplementation , an object may be stored in morethan one node and may not be totally enclosed by any
particular node . Therefore, an intersection test of aray with an object may find an intersection point
outside the current node . The algorithm as describedso far assumes that this is the nearest point ofintersection and halts . However, because theintersection point may be outside the node, we haveno guarantee that there is not a closer intersection
point with some other object in the scene. Only rayobject intersections within the node currently being
examined are valid . To avoid testing a ray with thesame object more than one time , ray -object cache canbe used [1] .
The two-way analog of the eight-way octree isthe k-d tree or billtree [14] . The only difference is that
where the octree divides a node into eight subnodes
using three splitting planes, a bin tree divides a node
into only two subnodes using just one splitting plane.
Any octree can be represented by a corresponding
bintree . The subdivision of a node in an octree isrepresented by three levels of subdivision of a node ina bintree. Not all bintree subdivisions can be
represented exactly by an octree. It is often moreconvenient and more efficient to use bintrees forspace subdivision [10].
In the following sections we review threeparticular space subdivision techniques in terms of
their costs for construction , tra versal , and storage. We
then introduce two heuristics for constructing spacesubdivisions and a neighbour link strategy for
improving traversal and storage costs. We report on
simulations that test these ideas using bin tree
implementations .
2. Previous Space Subdivision Algorithms
Glassner gives one of · the earliest publishedapplications of octrees to ray tracing using the spatial
median splitting planes [4], with later papers
Glassner's
elaborating on the technique [6 ,7].
method of construction is a simple breadth first
technique. Nodes which have more than a certain
number of objects are subdivided until a predetermined size of tree is reached. The tree building
is governed by two parameters: the maximum numberof nodes and the threshold value used for determining
whether to split a node. Glassner's algorithm
subdivides the smaller volume, rather than the large
node. It is likely that only a few rays go through thesmall node, while many intersect the large node.
Therefore, subdividing the smaller gives very little
performance gain . It is probably better to subdivide
the larger node .
The crux of the problem is that Glassner's
algorithm does not take into account any measure of
the chance of a ray intersecting a node . Glassner

Graphics Interface '89

154

presents an improved algorithm [6] in which a node is
subdivided if it contains more than a threshold
number of objects, or if it is larger than a given
volume. It seems that the choice of threshold is very
critical to the perform ance of this algorithm.
During ray tracing , the ray progresses throughthe volumes defined by the leaves of the octree,
alternately functions to enumerate the leaf nodesintersected by the ray in order of nearness to the ray
origin . The objects within the enumerated leaves aretested for intersection and the ray tracing algorithm
halts at the first intersected object.
Each time the ray enters a new leaf of theoctree, the traversal procedure starts at the root node
and works down the tree node-by-node until a leaf isfound . But two consecutive leaves along the path of
a ray generally share several ancestor nodes .
Glassner's approach ignores this .
A simple
optimization of Glassner's traversal algorithm would
be to perform a binary search among the ancestors for
Even with thisthe lowest common ancestor.
optimization , we suspect th at for really large octrees
the doubly logarithmic search time would still be asignificant overhead. Perhaps the worst drawback to
Glassner's traversal algorithm is the problem of
ensuring that a "good" hash function exists, since thisis the mechanism used to rapidly access nodes in th eoctree. This is not adequately described by Glassner
for large octrees. A basic problem seems to be that
Glassner's approach is geometric in nature andignores the connectivity (or topology) implicit in theoctree.

adaptation of the standard two dimensional DDA(digital differential analyzer) used to draw lines .
ARTS uses a uniform space subdivision with explicit
storage of the octree as a tree. This method issuperior to Glassner's hash table strategy in terms ofstorage, requiring about 16 percent less space.
In addition to being more compact, the ARTS
method has faster traversal times because of the
explicit links to the children and because space ispartitioned into small voxels of a fixed size. Using
incremental integer arithmetic,
the algorithm
determines the voxels that a ray travels through and,using these, which leaves of the octree the rayintersects. The size of the voxels is appropriately
chosen so that the smallest leaf node in the octree is anonnegative power of two times the size of the small
voxels. The splitting planes of the octree coincidewith faces of the small voxels, allowing astraightforward mapping of a small voxel to a leaf
node . The ARTS system traverses upwards from theprevious leaf only as far as required and then down to
the leaf in question. It is claimed that this can bedone quite efficiently using byproducts of theincremental integer arithmetic algorithm.
We see three basic bottlenecks in the publisheddescriptions of these space subdivision algorithms: theconstruction of optimal hierarchies given a fixed
number of nodes, the traversal time as rays are traced
through vol umes, and the storage costs associatedwith individual nodes . These issues are addressed inturn in the following sections.
3. The Surface Area Heuristic

Kaplan describes an implementation of a bin tree
very similar to Glassner's octree approach [10] . A
node is subdivided at the spatial median in each of
the three coordinates and three levels of sub nodes are
created to represent the subdivision . The traversal
algorithm for a bin tree is simpler and a bintree
typically
resultsin fewer
leaves than thecorresponding octree.
The construction of the tree is governed by thesame criteria as G lassner's second method [6] . A
node is subdivided if it contains more than athreshold number of objects , or if it is larger than athreshold size. Kaplan suggests using one as thethreshold number of objects. The problems with thisapproach are the same as for Glassner's method.
Fujimoto, Tanaka, and Iwata described what
they consider to be a significant speed breakthroughwith regard to space subdivision structures for ray
tracing [3]. Their ARTS implementation, which
stands for "accelerated ray tracing system," isdistinguished from Glassner's method by the speed of
its traversal algorithm , as opposed to the uniqueness
The traversal algorithm usesof its octree.
incremental integer arithmetic to enumerate the space
through which a ray travels . It is a three dimensional

The construction of the bin tree or octree is typicallyinsignificant compared to the computation spent in
actually traversing the tree to determine ray-object
intersections . Therefore it would be advantageous to
devote a greater effort to creating a more efficienttree, under the assumption that the extra time would
then be recovered during tree traversal.
A heuristic approach for bin tree construction canbe derived from Stone's [15] observation that the
number of rays likely to intersect a convex object isroughly proportional to its surface area , assuming thatthe ray ongms and d irections are uniformly
distributed throughout object space and that all
origins are sufficiently far from the object. Thisobservation has been used to provid e a measure of
the likelihood that a ray will intersect a bounding
volume in a hierarchical extent tree [8). We derive asimilar prediction of the number of objects , interior
nodes , and leaves intersected in a space subdivisionhierarchy.
We assume that all rays intersect th e bounding
vo lume for the entire scene . Thus every ray intersects
the root voxel.
We further assume that theprobability of a ray intersecting any interior orGraphics Interface '89

155

exterior node is equal to the surface area of the node
divided by the surface area of the root. This resultsin the following intersection estimates .

# of interior nodes hit per ray =Ni~SA (i)/SA (root)i-I# of leaves hit per ray =NI~ SA (/) /SA (root)

1-1# of objects tested for intersection per ray =NI~ SA (1)'N (l)/SA (root)

1-1

where the various quantities are
Ni = # of interior nodes
NI =SA (i) =# of leaves

surface area of interior node i

ray intersects one of these leaves. Therefore a given
object may be tested against the same ray several
times .
As observed before , this is usuallyunacceptable, and is avoided by caching objects
intersected against a ray so that each object is tested
at most once per ray. The cost function given above
must be modified to account for this caching.
To derive the correct cost function , we require ameasure of the probability that a ray intersects atleast one leaf from the set of leaves within which aparticular object resides. This is equivalent todetermining the probability that a ray intersects thevolume defined by the union of the set of leaves.
Because this union may be non-convex, theprobability of ray intersection must be estimated byfinding a convex region to approximate the nonconvex region. A simple approximation is the sum of
the areas of the projection of the set onto the six facesof the root bounding volume divided by the rootbounding volume's surface area. For a convex object,
this measure is exactly equal to its surface area
divided by the root bounding volume's surface area.
We can use this approximation for the set of leaves
for all objects, whether the set of leaves for eachobject is convex or not. This makes the object
portion of the cost of a tree

SA (/) = surface area of leaf node I

N.

Co' ~ SAset(S/(o»0- 1

N (I) = # of objects stored in leaf I

object cost per ray = - - - - , - - - - SA (root)

Given these measures of the node , leaf, andobject visits performed during traversal of the tree , anestimate of the cost of the tree can be obtained . The
costs associated with these three components dependon the particular implementation of the traversal
algorithm and may be determined theoretically or
experimentally. The total cost of a particular tree isdetermined from the three sums above and the three
related costs, which are assumed to be constants for agiven implementation . This is expressed ascost of tree =
Ni

NI

NI

i-I

i-I

1- 1

C;, ~SA (i)+C( ~SA (I)+C o ' ~ SA (I) 'N(I)where the new quantities are
No =# of objects

S/(O) = leaves in which object 0 resides
SAset(s) =approximate surface area of set s

If we assume that the above costs are accurate,
we can use these equations to govern the constructionof the tree , choosing nodes to subdivide so as tominimize the total cost of the tree for a given numberof nodes in the tree. We call this rule the surface area
heuristic.

SA (root)

where the new quantities are
Ci = cost of traversing an interior node
Cl = cost of traversing a leaf

Co = cost of testing an object for intersection

This cost function assumes that rays do notintersect any objects , but also represents an upperbound for rays that do intersect objects . The costfunction implies that if an object occurs in two or
more leaves, it is tested for intersection each time a

The validity of the surface area heuristic wastested using a simulation . A set of 100 boxes withrandom sizes and positions were created , where eachbox was a standard rectangular parallelepiped.
100 ,000 random rays were traced through thebounding volume enclosing the boxes. These rays
had origins outside the bounding volume, and weredirected towards the bounding volume . The statistics
recorded are presented in graphical form in Figure 1,
where each point represents the surface area of a box
and the number of rays which intersected the box.
The number of rays intersecting a box is thus shown
to be directly proportional to its surface area to within
statistical varia tion.

Graphics Interface '89

156

Experimental Verification of Surface Area Metric

5000

0 0

4500
>.
'"

'"

0::
c::

0

0
0

4000

cil oB

3500

0

o'lb

.~

'"'"....
'"
i::

-

2000

'"E

1500

::l

Z

1000

0

~ o

_°
~,t"

2500 .

.Cl

....

00

3000

....0

0

0

0

:3':J

500
~

0
0

c#

oo1l

20

40

60

80

100

120

140

160

180

200

Surface Area

Figure 1. Surface area heuristic data .

The graph illustrates that the number of rays
intersecting a box is proportional to its surface area,
assuming random rays. However , this does not provethat the estimates of interior and leaf nodesintersected are correct because the search is truncatedas soon as an intersection is found. The number ofobject tests also cannot be assumed to be provenfromanbecausetheestimate is derived
approximation of a possibly concave set of leaves by aconvex volume. To test the validity of theseestimates, a further simulation was performed .
Random scenes of objects and random bin trees
were created using the surface area heuristic. These
were used to trace random rays as in the previous
simulation . The estimated numbers of interior nodes,
leaves, and objects visited were compared with theactual numbers from the ray tracing . Each scene
contained a random number of objects between 10
and 500 , with random distribution in size from .01 to
1. The bin tree created for the scene contained arandom number of nodes between 10 and 1000 , where
nodes were subdivided in random order along arandom axis at a random position within thecorresponding voxels. 529 random scenes werecreated and 10000 rays were traced for each scene.
Table 1 summarizes the results of the simulation .
In all cases the actual number is proportional tothe estimated number. In the case of the number ofinterior nodes and leaves intersected, the estimate
actually provides an upper bound rather than an
average case estimate. This is understandable , as thederivation of the estimate assumes that the rays hit noobjects. The constants of proportionality may
therefore be used in conjunction with the surface area
heuristic to give a more accurate estimate of theaverage number of interior nodes and leaves

intersected. The estimate of the number of objects
intersected was shown to be quite accurate , with aconstant of proportionality close to one .
One reason that this estimate provided anaverage case estimate, rather than an upper bound, isthat there are too few objects in the scene.
Truncating the search as soon as an intersection was
found probably did not save many intersection tests
because each ray may have intersected zero or one
objects . Therefore the estimate provided an averagecase estimate. With denser scenes , the object
intersection estimate should probably be scaled downin the same way as the interior and leaf node
estimates .
4. Spatial Median Versus O bject Media n
In all of the octree and bintree constructions the
position of the splitting planes is arbitrary, even if thesurface area heuristic is employed. Traditionally, thesplitting plane is chosen as the spatial median,resulting in a uniform space subdivision . Heckbert(9) employed a medial! split algorithm that chooses a
splitting plane based on the object medial! in a k-dtree , where the objects are colour triplets (points).
The object median is the splitting plane that places
one half of the objects on each side of the plane. The
cost estimate developed using the surface area
heuristic can also be applied to selecting "good"
splitting planes in this extended model.
In the following discussions of splitting planes,
we will only consider the bintree. We assume that
only major planes are used as splitting planes and we
ignore the possibility of an object straddling a splitting
plane. We have to choose a parameter b , whereb = 0 corresponds to the lower limit of the splitting

Graphics Interface '89

157

Table 1

Quantity# rays intersecting box# interior nodes intersected# leaves intersected# object tests

Actual27.5. surface area
0.752 . estimate
0.831 . estimate
1.03 . estimate

plane b = 1 is the upper limit. Choosing b = 0.5 isequivalent to selecting the spatial median .
Let us look at the cost as a function of thisparameter b . We observe that the internal node andleaf node components of this cost savings function are
constant with respect to b . Therefore, for the
purposes of minimizing cost, one can minimize thefunctionf(b) = LSA(b) ·L(b) + RSA(b) ·(n -L(b»-SA ·nwhere n is the number of objects in the node , L (b) is
the number of objects to the left of the plane at b,
and n -L (b) is the number to the right. The surface
area of the left and right sub nodes are LSA (b) andRSA (b) , respectively. and the surface area of the node
itself is SA . The first term represents the probability
that a ray intersects the left subnode multiplied by the
number of intersection tests performed in the left
subnode . The second term is a similar quantity forthe right subnode . The SA·/1 term is the amount ofwork required if the node were not subdivided andthus is an amount of work saved by changing theoriginal node from a leaf to an internal node . hence
the minus sign. This last quantity is a constant withrespect to b , so it may be removed from the function.
resulting in the following function to be minimized .
f(b) = LSA (b)-L (b) + RSA (b ) ·(I1-L (b»To find a "good" splitting plane. one might
evaluate this function at several different positions
and choose the position with the minimum value .
However, let us examine the behaviour of thisfunction. The value of this function at the spatial
median (b=0.5) isCorr. Coeff.
.995
.945
.900
.985

LSA (0.5)+RSA (0.5) which is 2 ·LSA (0 .5). This showsthat picking the object median results in the samegain as picking the spatial median. Intuitively, one
might assume that picking the object median would
be a reasonable heuristic for choosing an arbitrary
splitting plane , but the above observation indicatesthat it is equivalent to the standard spatial mediansubdivision.
The optimum heuristic is to pick the splitting
plane which minimizes f(b). Differentiating withrespect to b givesf' (b) = LSA '(b) -L (b) + LSA (b) -L' (b)+/1 ·RSA'(b)- RSA 'Cb )·L(b) - RSA (b)-L ' (b)which can be simplified by substituting -LSA ' (b) for
RSA' (b) because LSA (b) + RSA (b) is a constant,giving.
f'(b) = (2 ·L(b)-n) ·LSA '( b) + (LSA(b)-RSA(b» ·L ' (b)Since L (b) is a discontinuous function, L ' (b) is notdefined . However. for the purposes of minimizationof f(b). we can assume that L' (b) is always
nonnegative (the number of objects stored in the left
subnode cannot decrease as b increases) .
Let us investigate the case where the object
median lies at some point b<0 .5 . To the left of theobject median. f' (b) is negative , because L (b)<;and LSA (b ) <RSA (b).

To the right of the spa tial

median. f' (b) is positive, because L (b»;andLSA (b » RSA (b). Therefore the minimum must occur

n ·LSA (0.5)

because LSA (0.5) = RSA (0.5) . Curiously enough, thevalue of this function at the object median , where
half of the objects are on each side of the splitting
plane and L (b )=~ is(LSA (b)+RSA (b» · ;Std. Dev.
5.2%
12.7 %
14.1%
9.5 %= n ·LSA(0 .5)

because LSA (b )+RSA (b) is a constant independent of
b
which
means
that
we
can
substitutebetween the object median and the spatial median in
the case where the object median is to the left of thespatial median . A similar proof can be used for theother case where the object median is to the right ofthe spatial median, thereby proving that for any nodeand set of objects within it. the optimum splitting
plane occurs between the object median and thespatial median. reducing the required search range .
The optimum splitting plane actually occurs
within this reduced range and at the upper or lower
edge of one of the objects within the range, rather

Graphics Interface '89

158

than in the middle of "white space" . To takeadvantage of this reduced range , one must first findthe object median , which is easy if the objects are
sorted, but otherwise requires a search of the space.
If one does not want to perform this search, one candetermine how man y objects are on each side of thespatial median , thereby determining on which side of
the spatial median the object median occurs . This
allows one to cut the search space in )1alf. In thecases of small numbers of objects, one can try
splitting planes at the limits of each object within theappropriate half and record the maximum. For large
numbers of objects, one might try a small set of
splitting planes at equally spaced intervals , or evenrandomly selected , within the appropriate half.
Alternatively , a cheap heuristic is to select the
splitting plane midway between the object median andthe spatial median .
Because of space limitations , we have not dealt
with objects spanning the slicing plane in this paper.
Our results can be extended to handle this case as
well .
5, Comparisons
Having verified the surface area metric as reasonably
accurate, different construction techniques for spacesubdivision were investigated. Four new construction
algorithms. as well as Kaplan 's algorithm , were
implemented for purposes of comparison andevaluation. All algorithms were implemented on
bintrees . The construction algorithms consist of twoalgorithms where the spatia l median is chosen as the
splitting plane . two algorithms where the splitting
plane can be in an arbitrary position , and Kaplan'salgorithm as a standard of comparison. Thesealgorithms are the following.
Kaplall's Algorithm (zero degrees of freedom in the

splitting plane selection): This is simply Kaplan'salgorithm with a threshold value of one. Nodes
are subdivided until they contain zero or one
objects, in a breadth-first order. The maximum
height of the tree was set to 30 , which was felt tobe large enough not to restrict the growth , yetprovide a practical bound.
Arbitrary Acyclic (two degrees of freedom): Splitting

planes can be anywhere within the node , and anode ma y be divided along any of the three axes .
The optimal splitting plane is determined bysampling at nine equally spaced intervals within
the node, recording the maximum value of thefunction given previously . Nine is an arbitrary
parameter chosen so as to attempt to focus on
the optimal plane , yet not incur unreasonableamounts of computation . A node is subdivided
along whichever axis provides the greatest gain
and nodes are subdivided according to highest
gain .

Arbitrary Cyclic (one degree of freedom) : same as

Arbitrary Acyclic , except that the first level ofsubdivision always occurs along the x axis , thesecond along the y axis, the third along the zaxis, cycling through the three axes.
Spatial Mediall Acyclic (one degree of freedom): sameas Arbitrary Acyclic, except that the spatial
median is always chosen as splitting plane .
Spatial Mediall Cyclic (zero degrees of freedom) : sameas Arbitrary Cyclic, except that the spatial
median is always chosen as splitting plane .
These algorithms were encoded as simply as
possible without any attempts to optimize the code.
It was felt that it was more important that the code becorrect , and our emphasis was verification , rather
than efficiency . Statistics on the trees were recorded
during the construction of the tree. The statistics
include the number of interior nodes, the number of
empty leaves , the number of non-empty leaves(containing one or more objects) , the estimatednumber of leaves visited , estimated number ofinterior nodes visited, and the estimated number ofobjects tested for intersection .
The ultimate goal of the strategies for building
the space subdivision structures is to improve
performance in ac tual ray tracing systems . The
performance should therefore be evaluated withscenes that represent a reasonable sample of all scenes
subjected to ray tracing. Five scene types proposedby Kingdon were used [12] . The object distributions
are based on three simple random number generators:
V 3 , which selects a random point within a unit
sphere ; VO, which selects a random point on the unit
sphere; and V', which returns the output of VO scaled
by a Gaussian distributed random number with amean of 0 and variance of 1. The five scene types
used in the simulations were the following.
Small Spherical: a set of triangles whose first vertices
are V 3 distributed in space and whose other two

vertices are O.OIO ·Vo distributed offsets from thefirst point.
Large Spherical : a set of triangles whose first vertices
are V 3 distributed in space and whose other two
vertices are 0.333 ' VO distributed offsets from thefirst po in t.
Small Gaussiall : a set of triangles whose first vertices
are 0.333 ' V' distributed in space and whose

other two vertices are O.OIO ·Vo distributed offsetsfrom the first point.
Large Gaussiall : a set of triangles whose first vertices

are 0.333 ·V' distributed in space and whose
other two vertices are 0 .333 ' VO distributed offsetsfrom the first point.

Graphics Interface '89

1591024 Small Spherical Objects

10

'V
'V
'V
'V

9

'V
'V
'V

8

'V
'V
'V

7
>.

'"

~

....
Q)
0.

6

~

~

U
Q)

5

:0
0

....0
....

1l

4

E

Z'"

3

2

500 1000 1500 2000 2500 3000 3500 4000 4500 5000 5500 6000 6500 7000 7500 8000
Number of Leaves

Legend:

•
oo
•
\l

•

Arbitrary Acyclico•Spatial Median Acyclic
Spatial Median Cyclic
Kaplan (Spatial Median)o Arbitrary Cyclic\lFigure 2. Summary of simulations .

Three Random Verti ces: a set of triangles whose
vertices are U 3 distributed in space , creating a setof dense, interpenetrating triangles .

The small spherical and small Gaussian scenes
contain triangles that are roughly

2~0

times thewidth of the scene, while the large spherical and large
Gaussian scenes contain triangles approximately~

times the width of the scene , attempting to simulate
the limits of object sizes in typical scenes . The
Gaussian distributions provide a cluster of objects
while the spherical distributions provide more spreadout objects. Six instances of each scene were used ,varying only in the number of objects comprising thescene . The numbers used were 256 , 512, 1024, 2048 ,

4096 , 8192 . The maximum number of nodes was set
according to the amount of time and memory
required and range from 2000 to 8000 nodes,
depending on the scene type . Also , for some scene
types, only the first five scene sizes were used , tolimit computer usage .
Data from the simulations was analyzed tocompare the various algorithms. Figure 2 shows agraph of the results for 1024 small spherical objects .
The other cases were similar , but are omitted fromthis paper due to space limitations.
In summary , the estimated number of nodes andleaves visited for a given scene were very similar over
all five algorithms , as is evident from examining theirgraphs . Overall , the arbitrary acyclic algorithm

Graphics Interface '89

160

performed slightly better than the rest in terms ofnumber of nodes and leaves visited. However , thenumber of objects intersected varied widely over thedifferent construction algorithms . For this reason andbecause the object cost is typically higher than theother two costs , let us concentrate on the number ofobjects intersected in order to evaluate the algorithms'
performance.

be subdivided . The selection of the next node to
subdivide is , as in the arbitrary acyclic algorithm , thenode which has the highest estimated gain . When the
hybrid algorithm resorts to selecting the spatial
median . the gain associated with this split is set at thethreshold, rather than the actual value. which would
be lower. This hyb rid algorithm was run on each of
the five scene types containing 1024 objects , except
for the scene type containing three random vertices,which had only 64 objects for efficiency. It performs
better overall than any of the other algorithms (it wasoutperformed slightly by the arbitrary acyclic
algorithm in the case of a large Gaussian scene).

For the small spherical and small Gaussian scene
types, the arbitrary acyclic algorithm performed thebest, providing up to three orders of magnitude
reduction in the number of objects tested forintersection . For the large spherical and large
Gaussian scene types, the arbitrary acyclic algorithm
was also the best. but only up to one order ofmagnitude better. However. for the scenes consistingof three random vertices , the Kaplan method
performed best. The general rule seems to be thatthe arbitrary acyclic algorithm performs best forscenes with non-overlapping small objects, while
Kaplan 's performs best for denser scenes withinterconnected objects.

It is interesting to note that the portions of thegraphs pertaining to Kaplan 's algorithms often
contain line segments and abrupt changes of slope.
These are due to the fact that after some point in theconstruction of the tree , Kaplan 's algorithm
essentially builds the tree level by level. The line
segment portions correspond to individual levels, andthe abrupt changes in slope correspond to the fillingof a leVel.

The explanation for this behavior is that thearbitrary acyclic algorithm is a greedy algorithm,
governing the subdivision by only looking one step inadvance . If subdividing a node is not immediately
advantageous. then it is not subdivided. even if
subjecting the node to two levels of subdivision would
be advantageous. Kaplan's algorithm. by virtue of its
breadth-first nature and an inability to evaluate thebenefit of subdividing a node , may subdivide a node
many times, resulting in a gain where the arbitrary
acyclic algorithm would not.

At the end of each simulation, the total numberof object instances (number of objects stored at theleaves) were recorded . The arbitrary algorithms
produced near optimum numbers , that is, only 10 or
20 percent mor.e object instances than objects, while
Kaplan 's and the other two spatial median algorithms
produced trees with up to ten times as many object
instances as objects. The reason for this is theimplicit motivation to keep objects in as few leaves as
possible , provided by the cost function used inselecting the splitting plane fur arbitrary subdivision.

These observations indicate that a hybrid of thearbitrary acyclic and Kaplan 's algorithms mightprovide optimum performance in all scene types. A
hybrid implementation was performed where thearbitrary acyclic algorithm was applied to a node firstto determine an optimum splitting plane. If it does
not find a speed gain above a certain thresholddependent upon the surface area of the node , thenthe spatial median is chosen . The coordinate isdependent on the level of the node, similar to
Kaplan's method except that nodes are only
subdivided with one level of subdivision at a time(rather than three levels) . This forces the algorithm
to assume that subdividing a node results in adecrease in cost. even if the one-step look ahead
indicates an increase. Thus . a node which theoriginal algorithm does not find advantageous tosubdivide may be subdivided by the hybrid algorithm,
resulting in a tree with a higher cost than if the noderemained a leaf. The children of this node may thenbe subdivided, possibly resulting in an overall
decrease in the cost of the tree.

6. Storage

This process is used , as in the other algorithms,
only to determine the splitting plane , splitting
coordinate, and estimated gain. if the node were to

The simplest and most obvious method of storing thebintree (octree) is as an explicit tree with two (eight)
pointers per node . This has a large spacerequirement, motivating the more compact octree
schemes of Glassner [4] and Fujimoto et al. [3].
The storage method has a marked effect on the
speed of traversing a tree . In ray tracing the internal
nodes of a space subdivision are not interesting. All
useful information is in the leaves. The traversal cost
can be decreased by storing links to neighbours oneach of the six faces of each leaf. Samet [14J
describes such links in quadtrees , which he terms
ropes. For the purposes of the following discussion ,let each face of each leaf have exactly one neighbour ,defined as the smallest node (interior or leaf) whosevox el's surface totally encloses the face of the leaf inquestion. By this definition , the neighbours of a leaf
are not necessarily leaves . However , .this definition
guarantees that each leaf has exactly one neighbour
per face (except le aves on the boundary of the scene,
which have none) .

Graphics Interface '89

161

n leaves

1 leafy
2n links
Figure 3. Neighbour links in octree.

During traversal of the structure it is necessary to
determine the face exited . The neighbour link of thisface is followed and if the neighbour of the face is aleaf, processing of the objects within the leaf is
performed. If the neighbour is an interior node, thenthe exit point of the current leaf must be computed
and used to descend the neighbour's subtree to findthe appropriate leaf. This strategy eliminates all
upward traversal of the tree and some downward
traversal. In general. when a ray travels from one
area to an area of equal or lower subdivision, theneighbour is a leaf and the hierarchy traversal cost is
zero. It is only when travelling to an area of higher
subdivision that there is any hierarchy cost. In thiscase the cost is less than the corresponding cost of themethods described earlier because the upward
traversal to the common ancestor is eliminated andsome of the downward traversal may also be avoided(about equal to the upward traversal eliminated).
Therefore. the neighbour links reduce the hierarchy
cost significantly, at the added expense of six pointers
per leaf.
A further modification of the neighbour links is
to redefine the neighbours of a face as all leaves
adjacent to that face . Now, all neighbours are leaves,
but any given face may have more than one
neighbour , which requires more memory per leaf thanthe previous link strategy. However, in the case of
spatial median subdivision, the amount of memory
required is now less than 12 pointers per leaf on
average, only twice that of the former method. The
average 12 pointers per leaf stems from theobservation that, although some faces have a large
number of neighbours , others have only one
neighbour, with the average being two pointers per
face. This is illustrated in Figure 3, which shows 11+1

which is less than two pointers per face. Witharbitrary subdivision, the number of pointers per face
may be higher , because Figure 3 no longer covers all
possible subdivision cases .
The storage of the neighbours for a leaf consistsof six integers representing the number of neighboursof each face , plus a list of pointers to the neighboursof each face . Alternatively , the neighbours could be
stored in a two dimensional bintree (or quadtree) toquickly determine the appropriate neighbour for agiven exit point.
This complete neighbour lillks scheme eliminates
the hierarchical traversal altogether, because finding
the next node only requires following the links, but it
introduces the additional cost of determining whichlink to follow if a leaf has more than one neighbour
on a given face . We assume that the number ofneighbours of a leaf is proportional to its surface
area.
Better search performance may result by using a
two dimensional bin tree to search for the neighbours
or by performing a binary search on the sorted
neighbour lists . Either of these two methods reduces
the expected number of tests per face to log ncomplexity.
The form of the tests is single
comparisons in the case of the two dimensional
bintree, rather than four comparisons. The expected
number of comparisons is therefore proportional toNI~SA (l)logSA (l)1- 1

faces, and 2 '11 links , and hence ~ links per leaf ,
11+1

NI
1
-2
" - - ' -'logNI
1~1
2
3
Nl 3

3v'N/' logNI

Graphics Interface '89

162

Table 2Up / Down Traversals , 1000 nodes
Scene Type1000 Small Spherical
1000 Large Spherical
1000 Small Gaussian
1000 Large Gaussian
64 3-Random Verts

Up
36 .35589981
15.85369968
33 .94269943
24 .50469971
15.17660046

Although it appears that the neighbour links
approach may have large space requirements, there isa memory-speed tradeoff that can be invoked.
Instead of defining links to occur at all leaves , one
can define the links to occur at all interior nodes that
only have leaves for children. This decreases theextra space to approximately one eighth of theoriginal space requirements in the octree case, or one
half in the case of a bin tree. This method incurs thesame traversal cost as the original neighbour links
plus one additional upward traversal per leaf andpossibly one downward traversal.
More generally, the linking can be defined only
for the set of nodes at a particular height above theleaves. For example, links may be stored in all nodes
which are a fixed distance 11 above the deepest leaf intheir subtree. The case 11 = 1 corresponds to theabove method of storing at all nodes that only haveleaves for children. The amount of memory required
is proportional to(t)nin the case of an octree, yet

the extra traversal cost is only proportional to n . A
suitable value of 11 results in an appropriate tradeoff
between space and the additional up and down
traversals. For practical cases 11 can be chosen so thatthe extra indirection to follow links is modest and the
additional storage for links is vanishingly small.
A neighbour links strategy was implemented,
using the simple definition of neighbours which gives
exactly one neighbour per face , as opposed to thecomplete neighbour links strategy. One instance ofeach of the five scene types was used to build anarbitrary acyclic type bintree, with the neighbour links
for each leaf computed. All scenes had 1000 objects
and the bintrees constructed contained 1000 nodes.
After building the bintrees, 10000 random rays weretraced and the number of parent-to-child and childto-parent movements were recorded for each of theconventional traversal algorithms and the neighbour
links method. These numbers indicate the savings intraversal cost by using the neighbour links strategy .
Table 2 summarizes the number of parent-tochild and child-to-parent traversals recorded from thesimulation. The second and third columns give thenumber of up and down links followed for theconventional traversal algorithms . The fourth column

Down
36.38169861
20.09070015
33 .94810104
25 .91119957
19.25169945

Neighbours Down
9.951199532
8.987500191
10.09840012
8.954000473
9.043399811

gives the number of down links followed for theneighbour link algorithms (there are no up links
followed). If it is assumed that the cost of a single
upward traversal is equivalent to a single downward
traversal, then these numbers show that the neighbour
link scheme decreases the traversal cost to between ;1and '4 of the cost of an ARTS-type traversal method.

Storage of the lists of objects that belong in eachleaf have large space requirements . Glassner stores
all the object lists in a single array of object indices,where each list ends with a " nil" index. Glassner's
scheme provides a separate object list for each leaf.
A more compact scheme would allow more than one
leaf to point to the same object list. In cases where
there are many duplicate leaf lists, this scheme would
result in significant memory savings. There would be
an added cost during the traversal phase in order to
identify duplicate lists but only one extra level ofindirection. Even more savings would result if lists
which are subsets of other lists are identified, and apointer to the beginning of a sublist within a larger
list used to avoid explicit storage of the sublist. The
larger list would have to bc organized so that the
sublist is at the end.
The most compact scheme is to partition the setof objects into equivalence classes , where each
equivalence class is a set of objects which belong inthe same set of leaves. In the worst case , each
equivalence class consists of one object, in which casethis scheme is equivalent to the above many-to-one
linking with the overhead being a single extra level ofindirection . The object list for a leaf is thus a list ofequivalence classes , rather than a list of object
indices .
Althoughthe computationof theequivalence classes might be quite expensive, it is
only computed once when the space subdivision isconstructed . The savings in space might welloutweigh the extra computing time .
7. Summary

The cost of ray tracing using space subdivision trees
can be estimated by the number of interior nodes,
leaves , and objects visited per ray, and the respective
costs of these visits . This paper reports new

Graphics Interface '89

163

construction algorithms which represent considerable
improvement over conventional methods in terms of
reducing the number of nodes, leaves, and objects
visited by a ray . The algorithms employ the surface
area heuristic and a heuristic for estimating the
optimal splitting plane between the spatial medianand the object median .
The efficiency of traversal has been improved byattacking its two main costs, the processing of interior
nodes (a major improvement) and the computation of
the ray exit point (a minor improvement). The
neighbour link strategy has been introduced tosignificantly reduce the number of interior nodes
visited compared to G lassner's algorithms .
Many of the ideas in this paper should carry overto hierarchical extent trees . All of the ideas should
be examined with respect to higher-dimensional data
structures , dynamic data structures , and multiprocessor algorithms. We suggest a few areas for
future research as our closing remarks.
In computer animation, it is common for scenes
to change from frame to frame, as objects appear,
disappear , and change position, shape , colour , andother attributes. The data structures representing thescene must be updated to reflect these changes. An
important issue when choosing a data structure to
represent scenes is whether the structure allows
dynamic modification as the scene changes andwhether the dynamic modification is more efficientthan rebuilding a static structure each time the scenechanges. The restriction to static structures is notunreasonable, as static structures are appropriate incases where the viewpoint changes often compared tothe objects in the scene. But when this is not thecase,
our algorithms must be extended toaccommodate dynamic changes. One specific methodof dealing with dynamic objects is to treat time as
simply another dimension , with the data structure
subdividing the objects in 4-space . Glassner [7] hasreported on such an approach .
Our discussion has not addressed issues related
to multiprocessors . Other authors have suggested avariety of techniques for utilizing multiprocessors in
ray tracing. We believe that many of our techniques
can be applied as well.
Acknowledgements
This work was supported by an operating grant and a
postgraduate scholarship from the Natural Sciencesand Engineering Research Council of Canada and byequipment and operating funds from Digital
Equipment of Canada.
References
[1]

[2]

Cook , R . L., Porter, T., and Carpenter , L.,
Distributed
Ray
Tracing,
Proceedingsof
SIGGRAPH '84 , July , 1984 , pp . 137-145 .

[3]

Fujimoto , A., Tanaka, T., and Iwata, K"
ARTS: Accelerated Ray-Tracing System, IEEE
Computer Graphics and Applications , 4(10),October, 1984, pp. 15-22.

[4]

Glassner, A.S. , Space Subdivision for Fast Ray
Tracing ,IEEE
ComputerGraphics
andApplications, 4(10), October, 1984, pp . 15-22.

[5]Glassner, A .S.., An Overview of Ray Tracing,
SIGGRAPH 1987 Introduction to Ray Tracing
Course Notes , July , 1987 , pp. 1-20.

[6]Glassner, A .S., Spacetime Ray Tracing for
Animation, SIGGRAPH 1987 Imroductioll to Ray
Tracing Course Notes, July, 1987, pp. 1-17.

[7] Glassner, A.s. , Spacetime Ray Tracing for
Animation , IEEE Computer Graphics
Applications, March, 1988, pp. 60-70 .

and

[8]

Goldsmith, J. and Salmon, J., Automatic
Creation of Object Hierarchies for Ray Tracing,IEEE Computer Graphics and Applications, May,
1987, pp. 14-20 .

[9]

Heckbert, P.S. , Color Image Quantization for
Frame Buffer Display , Proceedings of SIGGRAPH'82 , July 26-30,1982, pp . 297-307.

[10] Kaplan, M. R. , The Uses of Spatial Coherencein Ray Tracing , SIGGRAPH '85 Course Notes 1 J,
July 22-26 , 1985.
[11] Kay, T . L., and Kajiya , J. T ., Ray Tracing
Complex Scenes , Computer Graphics , 20( 4),August, 1986, pp . 269-277 .
[12] Kingdon , S. J . , Speedillg
Intersections , Master Thesis ,Waterloo, 1986.

Up Ray-Scene
University of[13] Rubin, S. M. , and Whitted , T., A ThreeDimensional Representation for Fast Renderingof Complex Scenes, Computer Graphics, 14(3),July, 1980 , pp . 110-116.
[14] Samet. H., The Quadtree and Related
Hierarchical Data Structures, Computing Surveys,
16(2), June, 1984, pp. 187-260.
[15] Stone, L., Theory of Optimal Search , Academic
Press , New York, 1975, pp. 27-28.
[16] Weghorst , H., Hooper, G ., and Greenberg , D.
P .. Improved Computational Methods for Ray
Tracing, ACM Transactions on Graphics, 3(1),January , 1984, pp. 52-69.

Amanatides , J ., (personal communication) .

Graphics Interface '89