An Efficient Parametric Algorithm for Octree Traversal
J. Revelles , C. Ureña , M. Lastra

Dpt. Lenguajes y Sistemas Informáticos, E.T.S. Ingenierı́a Informática,
University of Granada, Spain,
e-mail: [jrevelle,almagro]@ugr.es,
URL: http://giig.ugr.es

Dpt. de Informática, E.U.P. Linares,
University of Jaén, Spain,
e-mail: mlastral@ujaen.es

ABSTRACT
An octree is a well known hierarchical spatial structure which is widely used in Computer Graphics algorithms. One of the most frequent operations is the computation of the octree voxels intersected by astraight line. This has a number of applications, such as ray-object intersection tests speed-up and visualisation of hierarchical density models by ray-casting. Several methods have been proposed to achieve thisgoal, which differ in the order in which intersected voxels are visited. In this paper we introduce a new
top-down parametric method. The main difference with previously proposed methods is related to descent
movements, that is, the selection of a child sub-voxel from the current one. This selection, as the algorithm,
is based on the parameter of the ray and comprises simple comparisons. The resulting algorithm is easy to
implement, and efficient when compared to other related top-down and bottom-up algorithms for octrees.
Finally, a comparison with Kelvin’s method for binary trees is presented.
Keywords: Octree, Binary tree, Ray Tracing, Acceleration Techniques

1 Introduction
By Octree Traversing we mean the process of finding the subset of voxels in an octree pierced by a directed line. As stated in the abstract, this has several
applications in Computer Graphics. Maybe the best
known one is the speeding-up of intersection tests ofa line with a set of objects. In this case, the octree
is used as a spatial index. Each voxel holds a pointerto the subset of objects that it intersects or contains.
Then, the set of objects hit by the ray is necessarily included in the set of objects intersecting voxels
pierced by the ray. By traversing the octree it is possible to restrict the ray-object intersection test to thisset of objects. This is only an improvement when
the traversal process is much faster than the test on
all objects. Octrees are also used in solid modelling.
In this case, the density of one or several materials
is considered constant for each voxel of the octree.
Generally, the internal structure of this density distribution can be visualised by using a rendering algorithm which displays it as a transparent material.
For these kind of algorithms, the accumulated opac-

ity along a ray is computed by obtaining the traversed
voxels. Several algorithms for octree traversing havebeen proposed [Agate91, Cohen93, Endl94, Fujim86,
Garga93, Glass84, Jevan89, Samet89, Sung91]. They
can be classified into two groups, according to the order in which pierced voxels are obtained:
Bottom-Up Methods: Traversing starts at the first terminal node intersected by the ray. A process calledneighbour finding is used to obtain the next terminal node from the current one [Glass84, Samet89,
Samet90].
Top-Down Methods: These methods start from theroot voxel (that is, from the one covering all others). Then a recursive procedure is used. From thecurrent node, its direct descendants hit by the ray
are obtained, and the process is (recursively) repeatedfor each of them, until terminal voxels are reached[Agate91, Cohen93, Endl94, Janse85, Garga93].
In this paper we introduce a new top-down algorithm.
This new algorithm is based on the parametric representation of the ray. This representation allows us tomap real values (parameter values) to ray points. The
algorithm computes the parameter values at which the
ray intersects the three planes that divide each voxel. These values are computed incrementally, byusing additions and divisions by two. In essence,
this algorithm is related to other parametric top-downalgorithms, such as the one introduced by Jansen[Janse85], Arvo [Arvo88], and Agate [Agate91]. Afterward, Sung and Shirley [Sung92] proposed a version on a BSP tree of Jansen’s work. Authors of these
papers pointed out that the cost of traversing an octree
and a BSP tree are similar, (these results have beenformally presented by Reinhard [Reinh96]). Both parametric methods (for octrees and BSPs) are based on
the same principles as our work. However, here we
propose a new method for selecting the first sub-voxelof a voxel, by using comparisons on previously obtained parameter values. This allows us to avoid theneighbour finding process, thus saving memory andcomputing time. With respect to the movements between neighbour voxels with the same parent voxel,
we use an algorithm which is also based on the ray
parameter, as the algorithm described by Amanatides[Amana87].
Sung [Sung91] presented an octree traversal algorithm which has the same theoretical basis as the 3DDDA traversal algorithm [Amana87] for uniform spatial subdivision, however, for unbalanced octrees, efficiency decreases. This is due to the fact that Sung’s algorithm uses the smallest octree leaf as traversal baseunit.
Moreover, we must refer a significant work presented
by J. Spackman and P.J. Willis [Spack91]. The authors presented a very efficient algorithm to traverse
an octree that only employed operations with integer
arithmetic throughout the traversal. That algorithm
is outlined into the paper and it is very robust. In
essence, both algorithms must be equivalent because
they use the same principles for each movement. We
think the proposed method in this paper is easy to understand and very didactic for teaching.
This paper is organised as follows: section 2 describes
a simplified version of the algorithm for quadtrees.
The extension for octrees is detailed in section 3. A
comparison in terms of efficiency with other methods, such as the bottom-up method introduced by
Samet [Samet89], two extensions of it proposed byEndl [Endl94], and a recursive top-down method[Garga93], is also included. We use the same software system for all the algorithms.

2

The Algorithm for 2D caseWe define a ray  as a pair   , where  
is the origin, and    is the unit length direction vector. For each real value  exists a
point ! "#$#%&!"## on the ray, where ! and %&! aretwo scalar functions defined as follows:
!"#')(*%&!"#+,(*

A node - in a quadtree is the set of points inside anaxis-aligned rectangle (whose four edges have equal
length). Formally, - is the set of points #% suchthat ./-1023254&- and %. -102%632%/47- ,where . #849#%&. and % 4 are four scalar valued functions which define the position of each node - (wealso define : ;- as the length of each edge of - )From the above definitions, we deduce that an intersection between a ray  and a node - occurs if at least
one real value  exists such that:
./-0<?

! "#=3>847;-%.;-=0>% ! #=3>%(2)47;-

The algorithm we propose is called a parametric algorithm because all computations use values of such that "!&"#$#%&!"#@ is a point on a node boundary. For a node - and ray  , * . -/#$#* . -/@7 , and  4-/#$#  4-/@ are defined as the ray parametervalues for which the ray intersects with the boundaryof the node. Formally, these values obey the following equalities:
E!"*BA@;-/##C

A -%&!&*$A#;-/##D%&A#;-E
E

EGFIH1J(3)LK&M

By using the inverse functions of ! , and %&! the above
parameter values can be defined explicitlyE BA -/@NA -POQ $A -/@7T

"% A -SO RS
 RP 

E
E

EUFIH1JVKM(4)
being  , and  the origin of the half line, and  and   the unit length direction vector. These four values are computed for each node when traversing thequadtree. Initially they are obtained for the root node,and then an incremental computation is performed foreach child node. In order to detail this incremental
computation, we first define the following quantities
W
W

 

;-/#XY  4-/@7ZO[  .&;-/# 

-/#XY  4-/#ZO[  .
W

Results show that the new algorithm is more efficientthan these other methods except on the algorithm presented by Spackman and Willis. Furthermore, its simplicity makes it straightforward to implement, as canbe observed in the source code listings in section 4.

(1)

-/@7(5)

Substituting (4) into (5), we get *;-/#X\: -@R ,for each node - . In the case that - isW non-terminal,for
all children -7A of - we have *W -7A@#]W
*-/@7 R^ . Similar relations hold for* . Thus,
WW
the values * and * can be incrementally computed for a child node just by halving the value for

Y
2

3

2

6

0

Z

7
7

6

6

 h,Asi

54

4

If a  exists obeying (9), then *hgAjiQ0_g3_*hlkm . The
inverse implication also holds, thus equation (9) is
equivalent to

X
Figure 1: Labeled octree (the hidden node haslabel 1).
the parent node. If we substitute the following recurrence relationsW./- A '.

;-(_:;- A%.;- A D%&.-`(a:

A
W

- A

(6)

% A

into (4) we obtainW  .&- A @7N

./-(_:

- A
A

OQ


RP 
W

./-SO



RS




(b;:

W
  .-/@W

In this case, A andllowing two vectors:

(

W
%&A

- A @R 
A

W
 

- A @7A

are components of the fo-

;-/#=3< hlkm

(10);-/#When above condition is true, all values of in the interval t *h,Asiu#*hlkm& are mapped to points
"! "#$#%&!"#@ which belong to the node. If the condition is false, no intersection occurs. It is now possible
to outline the proposed parametric algorithm used totraverse a quadtree. First, we check condition (10) for
the root node. If this condition is not satisfied then the
ray does not intersect with the octree. But where it is,
the four parameters   .#  .9 and "  49#  4$ need to becomputed for the root node by using (4). The main recursive procedure is subsequently executed accepting
a node as input parameter, and its corresponding fourparameter values. In cases where the node is terminal, this node is added to the resulting pierced nodes
list. If it is non-terminal, those child nodes which are
pierced by the ray are checked using (10) for each ofthem. A recursive call to the procedure is carried out
for each of them.

W
c
W

%d

J
J

@LK&VKM(7)

VK& LK&M

The last result also holds for * . . Thus, we haveshown how these values can be incrementally computed for all child nodes of the current node. The
computation of these values for the root node e is carried out by using (4).
Knowing the definitions of a node and a ray, we easily
deduce that an intersection between a ray  and a node
- occurs if at least one real value  exists such that:?

.

;-0<!&#3<

4 -% .

-0%&!"#3>%

4 -

By taking all these results into account, we can now
rewrite the condition 8 by using the parameters of theray. For instance, taking condition !&#3 4 ;-from (8), we can substitute 4 - by !* 4 -/#@ ,then, as ! is an increasing function, we obtain f3
* 4 -/@ . By using the other inequalities in (8) thesame way, we can state that an intersection between and  occurs if and only if exists g_ such that  .-/#a03>  4-/@7  .

-/#a03>  47;-/#(9)This equation can be further simplified by defining*h,Aji and *hlkm for a node - and a ray  as
 hgAji-/@N

nfop8  .

-/@7$#  ./-/@# hlkm-/@N

ndqjr`  4-/#$#  4&-/@7@

q2

tx0
tym

q3

txm

q2

q3

q0

q1

tym

tx0

q1

q0

ty0

ty0

Figure 2: Sub-nodes crossed when * .1v(2D case).

* .

(8)

Where a intersection occurs, an interval o values of 
satisfies the above inequalities. This interval is closed
at the left and open on the right for half lines with apositive or zero valued direction vector.

?

txm

q2

q3

q2

q3

q0

q1

tym
txm
q0

tym
q1

ty0
tx0
tx0

ty0
txm

Figure 3: Sub-nodes crossed when   .
(2D case).
v

  .

Note that, for any non-terminal node - , * . - . #w. Other child nodes
* . -/# , and * 4 - . xy* . - 4
behave in a similar way. Thus, computation of the entry and exit parameters for each child node of - is redundant, because some of them can be taken directlyfrom the parent node, and the others are shared byseveral child nodes. In fact, there are just six different

parameters for a child node. These are the four parameters of the parent plus the following two values:
*Bhz;-/#X"* . -/@`(* 4 -/#@@R^*$hz;-/#X"* .

-/@7{(=* 4 -/@#@R&^(11)

Here  Bh ;-/# is the value of the ray parameter forwhich the ray crosses the horizontal line which divides the node in two equal halves. A similar equation
holds for  Lh . This kind of coherence can be used to
improve the algorithm further by using a sequential
algorithm. The selection of pierced sub-nodes of anode is carried out in two steps:
1. Select the first sub-node hit by the ray
2. For each pierced node, select the next one, until
the current parent node is exited.

3.1

Obtaining the First Crossed NodeTo find the first sub-voxel at which the ray enters
the current voxel, first we obtain the entry face ofthe current voxel. This step is made by computing
w$
|mBB@~|~BB@~|#BB . In table 2 we show the entry
plane selected for each case. Once the entry plane has been
determined, four sub-nodes are candidates. To determine
the first sub-node crossed, we examine | m} B , | } B , and|~@})9 . In table 1 the necessary comparisons are shown.
The results of evaluating this condition (a bit) is copied to
one of the bits which form the index of the first sub-nodecrossed. When a condition is true, the bit associated is set
to  , otherwise it is set to  . For each entry plane there
are two conditions, so we have four possibilities, one foreach sub-node touched by that plane. In this way, any node
could be selected with the exception of node  , because theray direction vector components are assumed to be positive.
The whole process can be implemented using the l operator to combine the necessary bits. Several illustrations

Assuming a node e is crossed by a ray  , and the ray
direction components are non negative, then the next
implications hold:

Entry
Plane
¡d¢

if |~}Ss&~9{|}{ &~9 thenif |})9{|m})9 the ray crosses $ , andif | m B{| } 9 the ray crosses   .
if |m}9{|V 9 the ray crosses m .
else if |m}BS1|~}9 the ray crosses B , andif | B9{|m})9 the ray crosses m .
if |  } BS| B 9 the ray crosses   .

¡¤£

¢£

Conditions to
examineBit
affected|m}BS1|~@V9



| }

B{| # 9| m}

B{|  9| }

9{| m 9Table 1: Comparisons to obtain the first nodeintersected.

Maximum

3 Extending the algorithm to octrees

A recursive top-down parametric algorithm called HERO is
described in the paper by Agate et al.[Agate91]. The maindifference with the proposed algorithm is in the computation of the sequence of visited sub-voxels from the current
voxel (see section 3.2).

|~@})9{| B9|#}BP|mV9

These assumptions may be easily proved (see figures 2 and
3). When | m} and | } are computed, only three comparisons are necessary to determine the sub-nodes which arecrossed.

To extend the above algorithm to traverse an octree, wehave into account the two steps previously detailed, including the third dimension when necessary. With respect tothe first step, we introduce a new method which allows
the use of a nine parameter set to compute which voxel ispierced first. This computation avoids neighbour finding
to obtain the first voxel, as it is the case for the algorithm
introduced by Glassner[Glass84] and improved in otherpapers[Arvo88, Samet89, Endl94]. This yields a simpler
method. The following sections describe these two steps indetail. The second step is carried out by using a parametric
DDA algorithm, as described by Amanatides[Amana87],
but restricted to eight voxels (which can be viewed as a
x
z

uniform grid space). The parameter values arecomputed by successive additions[Amana87]. In our case,the values are incrementally computed from those of theparent by using three additions and three shifts.




|~m
|~
|~@

Entry plane
¢¥£

¡¤£
¡d¢

Table 2: First plane intersected.
are shown below to explain in greater detail the first step fora quad-tree case. If the comparison of |m and |  results| mc¦|  then the first edge crossed is edge 1. For thiscase, the first sub-node crossed can be $ or m (Figure 2).
However, when the above comparison results |~ ¦ |~m ,then the first edge crossed is edge 2. In this case, the subnode that can be crossed is either V or  (Figure 3).

3.2

Obtaining the Next NodeOnce the first sub-node of a node has been found, thesequence of the rest of the traversed sub-nodes must be
obtained[Amana87]. Since the location of the sub-nodes
is fixed, we can design an automaton whose states correspond to the voxels and whose transitions are associated tothe movements between neighbouring sub-nodes visited sequentially by the ray. In figure 5 all possible transitions areshown. For a given ray, the sequence of traversed nodes orstates visited will be established so that the followed pathis one of the possible ones in the before mentioned figure.
In order to obtain the exact path followed by the ray it will
be necessary to compute the face where the ray leaves eachof the visited nodes, which will make it possible to obtainthe next node to be visited. Let § be the current visited
node. The ray can leave this node through the following
¢¥£
¡¤£
¡d¢
,
or
and this is calculated by getting thefaces:
minimum of |~Bm §B@¨|~Vm §B@~|~$§L . In figure 4 a 2D example of computation of the exit edge for node B is shown.
You can see how the ordering of | B and | L determine theexit edge.

o
2

o
2

o
3

o3

the exit plane. From node number © , node number  is the
only one that can be reached because movements along the¡¢or axes would mean that the ray leaves the parent node.
The longest path includes four nodes and an example is theone including the sub-nodes "&V#ª&#V which involve threetransitions. In each one we choose the minimum of those
three values. Therefore two comparisons are made in eachtransition which, when added to the four operations needed
to obtain the first sub-node, results in ten comparisons in themost unfavourable case.
In the HERO algorithm it is necessary to sort a list of potentially visited sub-voxels and then explicitly check eachof them for intersection. However our algorithm is simpler because this is not necessary, as visited sub-voxels are
obtained sequentially. Some computations are unnecessary
because non-visited sub-voxels are not considered at all.
Thus this yields a faster and simpler algorithm.

tx1
ty1
tx1

ty1
o0

o1

r

o1

o0

Figure 4: Exit Edge.

Table 3 shows the next visited node given the current nodeand the exit plane. The entries labelled with ”End” meanthat the ray leaves node  . For example, if the first node isCurrent
sub-node(state)
0
1
2
3
4
5
6
7

Exit
plane
YZ
4
5
6
7
End
End
End
End

Exit
plane
XZ
2
3
End
End
6
7
End
End

Exit
plane
XY
1
End
3
End
5
End
7
End

Table 3: State transitions.

011

3

7

111

010
2

6 110

001

000

0

1

5
4

101

100



Figure 5: Sub-nodes that can be reached froman initial node.
, the nodes that can be visited are 4, 2 and 1, depending on

r’
2

6

0

4

Figure 6: Reflection transformation for thegeneralisation.

3.3

Generalising for Rays Parallel to One Main
Axis

In the case that «¬ is zero for any ­ , the direction vector« of the ray is parallel to an octree face or even to one of
the main axes. In this case, some of the entry and exit parameters are not defined, because their definition involves adivision by «¬ . In our algorithm, we have tried to keep the
program simple, avoiding any special case handling. So wehave chosen to allow the parameters to take infinite values.
This way the intersections between a ray and a plane may
occur at an infinite distance from the origin of the ray. Notethat in this case the interval of parameter values at which
the ray is in a voxel may be equal to the whole real line.
Any parameter |¬~ with ­f®¯m°±²³´ and µ)®=¯Lm¶¶¶#B´
can take real values and also the values ·I¸ and ¹l¸ . All
operations involving parameter values should take this into
account. We set °ºL)»_¹l¸ for all ° ¦  and °²ºV)»Y·I¸
for all °¼½ . We also have ·I¸Ty°\¾¹l¸ for all
real values ° . With these definitions it is possible to obtain
the initial entry and exit parameters for the root voxel, andalso to compare parameter values. The computation of |~¬~}is also affected by infinite values. Assuming that «d»¿ ,ray enters any voxel  if and only if | m &Bd»·I¸and |BmBÀ»Á¹l¸ . In this case, the value |~m} cannot
be computed because |mZ¹1|~B is undefined. However, inthese conditions it can be shown that:Â|~m}¥9À»

¹l¸

when

·I¸

otherwiseÃ°²BB¹Ä°mB


(12)

Å

Similar relations can be derived for the other axes, thus wehave a method to obtain |~¬~} in these cases. This ensuresthat the comparisons yield the correct parameter intervals
where the ray intersects the voxels (including the case whenthose intervals are equal to the whole real line), and the visited voxels are also correct. Some hardware architectures
include infinite values in the set of allowed real values, andare produced after a division by zero has taken place.

3.4 Generalising for Rays with Negative Directions
As has been pointed out at the beginning, this method only
works properly if the direction vector of the ray has no negative components. To solve this problem, eight different
versions of the method, one for each sub-voxel, could be
written and implemented. However, this solution has been
avoided because of the redundant code that would be necessary to produce. An example where the ray direction is¡
only negative for the axis is now considered. In this casethe ray can be reflected with respect to the middle plane ofthe octree to turn the negative direction component positive.
Starting from the reflected ray, the visited nodes must be relabelled and this way the previous scheme is valid. One raywith origin Ã and direction « is transformed to other ray Ã/Æand « Æ by using the following relations:
« Æ
Ã

Æ

·Z«
»

»

Ç7B·ÈÃ/

float value is the minimum of the three float values. Function Û7ÑÕ7Ü Ó7×BÑ$Ý²ÐmÔ&Ú9Ù is used to perform any computation
required when a terminal node is reached by the ray. Its
parameter is a pointer to that node.
Þßjàjá âsßsãäåæsçè/ç5éêsëjáìä²èsçísîïjçèjçìðjãñsãè5ò7ëjåìñsèsãã²óësåìñ¨ôBèsçí/èõöç÷²ø5éá ù8ò è¨ú äsûsüsø;ú øjõö è~ú ëû/÷²ësåñsýsþsàsáìÿsãsýè~ú ëûué
è~ú äû/÷²ýè~ú äsû5éç ÷8éá ù8ò è¨ú äsísüsø;ú øjõö è~ú ëí/÷²ësåñsýsþsàsáìÿsãsýè~ú ëíué
è~ú äí/÷²ýè~ú äsí5éç ÷ 5é
á ù8ò è¨ú äsÿsüsø;ú øjõö è~ú ëÿ/÷²ësåñsýsþsàsáìÿsã ýè~ú ëÿué
è~ú äÿ/÷²ýè~ú äsÿ5éç ÷ éñûjø ÷5ò ësåñsýþûð"á ß²ý/è¨ú ëûjõè~ú äû8éñû÷5ò ësåñsýþûðçû²ý/è¨ú ëûjõè~ú äû8éñíjø ÷5ò ësåñsýþíð"á ß²ý/è¨ú ëíjõè~ú äí8éñí÷5ò ësåñsýþíðçû²ý/è¨ú ëíjõè~ú äí8éñÿjø ÷5ò ësåñsýþÿð"á ß²ý/è¨ú ëÿjõè~ú äÿ8éñÿ÷5ò ësåñsýþÿðçû²ý/è¨ú ëÿjõè~ú äÿ8é
á ù8ò sçû8ò ñûsø;ô ñsísøô ñÿjøsõ/üáìß5ò ñûô ñsíô ñÿìõsõïèsëjåîjàìÞsñèjãã5ò ñsûsøô ñíjøô ñsÿsø;ô9ñûô ñsíô ñÿô7ësåñsýsþèsësëñõéêsëjáìä²ïèjësåîjàìÞ ñèjãã5òèjãç ñsûsø;ôVèjãç ñsísø;ô9èsãç èjãç ñsûôVèjãç ñsíô9èsãç ßjëäjã/óßõöèsãsç ñûð¨ôBñíð¨ôBñÿðéá ßsñzåìÞsèèjëäjã5é
á ù8ò ñûìüø¨ú øLñí üsø;ú ø Lñÿìüø¨ú øsõèjãñÞsèß8é
ö


(13)



5

A pseudocode of the algorithm will now be shown, whererecursion is used for ease of understanding, although thismay be avoided by implementing an iterative algorithmwith a stack. We consider an octree as a data structurethat contains a pointer to the root node whose type isnode. It also contains its dimensions called (xmin, xmax,
ymin, ymax, zmin, zmax), and its size called sizei, where
¡
¢
£
µX®Ä¯


´ . Each non-terminal node has eight pointers
pointing to its eight children. Function ÏÐLÑ&ÒLÓ Ô&ÕVÖ7× implements tables 1 and 2, such as described in section 3.1.
Function Ô×VØ Ô&ÕVÖ7× implements table 3. This function accepts three ÏÙBÕ9ÚVÓ values, and three Ð$Ô7Ó values as parameters. The function returns the µ -th integer where the µ -thá ù8ò ßsýþñísïsã ÷÷    jõïsèsësåîñjãèð"á ßjç5ò ßõ5éèjãñÞsèß8éñûð²÷/ø¨ú jó"ò ñsûsøñûìõ5éñíð²÷/ø¨ú jó"ò ñsísøñíìõ5éñÿð²÷/ø¨ú jó"ò ñsÿsøñÿìõ5é

The only difference will be in the labelling of the sub-nodesof a node. In figure 6 it can be observed when the origi
nal ray traverses sub-nodes É#© of the octree and that
the transformed ray traverses sub-nodes & #© which would
produce wrong movements in the octree. To avoid this, afunction Ê is needed to transform labels, so that when node
µ is computed as the next node, in fact Êµ; is accessed. In
the example, where «  Á , the image by Ê of the sub
nodes would be: É&#Ë#©##B *ª9 . Function Ê changes
the value of the most significant bit of the binary representation of a node label. In general (any component of thedirection can be negative) it is necessary to change label
bits when the direction component corresponding to that bit¡
is negative. This is done by using a l operation withthe original label and an integer value lower than 8 (3 bits).

Formally, Êµ;,»¼µÌ[Í , where Í¤»¼É9Ç  ¹
Ç  ¹=Ç  , andwhere Ç ¬ is  if « ¬ Î , and  in other case (for each axis
­ ).

4 Parametric Algorithm Pseudocodeñÿsø;ôñÿô

åìÞsèèjëäjã÷/ùáìèjàñsîßjëäjã8òVñsûsø;ôVñsísø;ôVñsÿsø;ô9ñûð~ôBñíð~ôBñÿðõéäsëö à!á ñjåæ8ò åìÞsèèjëäjãsõ
ö ø#"VïsèsësåîsàÞñsèsãsã8òVñsûsø;ôVñsísø;ôVñsÿsø;ô9ñûð~ôBñíð~ôBñÿð~ôBßsýþjàëß%$ ç&õéåÞèèjëäsã ÷²ßsãsîßjëäjãòBñsûð¨ô'¨ô9ñíð~ô(ôBñÿð¨ô)õésèsãç+*ué,"VïsèsësåîsàÞñsèsãsã8òVñsûsø;ôVñsísø;ôVñsÿð~ô9ñûð~ôBñíð~ôBñÿôBßsýþjàëß%$ -ìç&õéåÞèèjëäsã ÷²ßsãsîßjëäjãòBñsûð¨ô(;ô9ñíð~ô(.ôBñÿô(/²õésèsãç+*ué
#"VïsèsësåîsàÞñsèsãsã8òVñsûsø;ôVñsíð~ôVñsÿsø;ô9ñûð~ôBñíôBñÿð~ôBßsýþjàëß%$ -ìç&õéåÞèèjëäsã ÷²ßsãsîßjëäjãòBñsûð¨ô(0;ô9ñíô(/ôBñÿð¨ô(.²õésèsãç+*ué.#"VïsèsësåîsàÞñsèsãsã8òVñsûsø;ôVñsíð~ôVñsÿð~ô9ñûð~ôBñíôBñÿôBßsýþjàëß%$ .-ìç&õéåÞèèjëäsã ÷²ßsãsîßjëäjãòBñsûð¨ô(1;ô9ñíô(/ôBñÿô(/²õésèsãç+*ué
2"VïsèsësåîsàÞñsèsãsã8òVñsûð~ôVñsísø;ôVñsÿsø;ô9ñûôBñíð~ôBñÿð~ôBßsýþjàëß%$ -ìç&õéåÞèèjëäsã ÷²ßsãsîßjëäjãòBñsûô(/;ô9ñíð~ô(0ôBñÿð¨ô(²õésèsãç+*ué
#"VïsèsësåîsàÞñsèsãsã8òVñsûð~ôVñsísø;ôVñsÿð~ô9ñûôBñíð~ôBñÿôBßsýþjàëß%$ -ìç&õéåÞèèjëäsã ÷²ßsãsîßjëäjãòBñsûô(/;ô9ñíð~ô(1ôBñÿô(/²õésèsãç+*ué
0#"VïsèsësåîsàÞñsèsãsã8òVñsûð~ôVñsíð~ôVñsÿsø;ô9ñûôBñíôBñÿð~ôBßsýþjàëß%$ 0-ìç&õéåÞèèjëäsã ÷²ßsãsîßjëäjãòBñsûô(/;ô9ñíô(/ôBñÿð¨ô(1²õésèsãç+*ué
1#"VïsèsësåîsàÞñsèsãsã8òVñsûð~ôVñsíð~ôVñsÿð~ô9ñûôBñíôBñÿôBßsýþjàëß%$ 1-ìç&õéåÞèèjëäsã ÷3/5é
sèsãç+*ué æá!ã5ò åìÞèsè+ëäsãsü/jõ5é

Results

The proposed method was implemented in a rendering system written in C++, which already included several acceleration techniques based on octrees, and a wide range of algorithms for octree traversal. Time comparisons were madefor these algorithms.
The comparisons were carried out on a Silicon Graphics
Indigo 2 with a MIPS R4000 processor and 64MB ofRAM. Three different scenes were used: the first is asphere flake with 1890 objects (see figure 10), the second is a structure, composed of spheres and cylinders,with 4320 objects (see figure 11), and the third a patio with 4350 objects (see figure 12). Space subdivision
has been applied to these scenes using octrees with maximum depth levels 5, 6, 7 and 8. The traversal algorithms

CPU Time (sec.)

Sphere-Flake

4

4500
4000
3500
3000
2500
2000
1500
1000

Sam
SamC
SamN
Gar
Par

5

6
7
Octree depth level

8

Figure 7: Timing graph for Sphere-Flake.

Figure 10: Sphere-Flake.

Architecture
CPU Time (sec.)

8000

4

Sam
SamC
SamN
Gar
Par

7000
6000
5000
4000
3000
2000
5

6
7
Octree depth level

8

Figure 8: Timing graph for Architecture.
Figure 11: Architecture.
used to compare the performances with our method were:Samet[Samet89] (Sam), SametCorner[Endl94] (SamC) andSametNet[Endl94] (SamN) as bottom-up algorithms, andGargantini[Garga93] (Gar) as top-down algorithm. The
time comparisons are plotted in figures 7, 8, and 9. SametNet method requires much memory because pointers toneighbour voxels must be kept within each voxel (they are
required for the neighbour finding process). So, a higher
rendering time is obtained after increasing the octree depth
level due to swap time. In summary, we can see that the Gargantini method presents better results than the other bottomup methods shown. In Gargantini’s paper, we may see acomparison with Samet’s method. The improvement of thefirst one is shown in terms of execution time and a run-time
analysis.

CPU Time (sec.)

Patio

4

10000
9000
8000
7000
6000
5000
4000
3000
2000
1000

5.1

Comparison with the Binary Tree Structure

To study the efficiency of our method [Sung92], a comparison with the Kelvin Sung method has been done. We haveobtained two images from the same scene. The renderingsystem was the same in both cases. One of these images
was rendered using an octree structure, and the other usinga binary tree. The scene is shown in Figure 14. This scene .
has one object per leaf node. The number of spheres is
We ran three tests setting 5 to ª , É , and Ë . The total num
ber of spheres was Ë7 , É976B© , and ª V©'8 . The cpu time
employed when using the octrees was &¶ É:9 ,  ¶ 79 and©¶ 8(9lower than the time for the binary trees.
These results shows that octrees are more efficient than bi-

Sam
SamC
SamN
Gar
Par

5

6
7
Octree depth level

8

Figure 9: Timing graph for Patio.

Figure 12: Patio.

nary trees when the tree is full or nearly full, due to thenumber of necessary descents to reach one terminal node.
In an octree, the number of recursive calls to the main function is lower, meanwhile the rest of computations are basically equivalent (as it was established by Reinhard et al.
[Reinh96]).

OctreeBinary Treevances in Computer Graphics Hardware IV R.L.
Grimsdale, W. Strasser (eds) Springer-Verlag, New
York, 1991.
[Amana87] J. Amanatides, A. Woo. A Fast Voxel Traversal
Algorithm for Ray Tracing. Eurographics’87. Proceedings of the European Computer Graphics Conference and Exhibition, August 1987, pp 3-10.
[Arvo88] J. Arvo. Linear-time voxel walking for octrees.
Ray Tracing News 1(12), March 1988. Available under anonymous ftp from drizzle.cs.uoregon.edu[Cohen93] D. Cohen, A. Shaked. Photo-Realistic Imaging
of Digital Terrains. Computer Graphics Forum Vol.
12(3), pp 363-376, 1993.

Figure 13: Bintree and Octree equivalent structures (depth level for octree is 1, and 3 for bintree).

[Coqui85] S. Coquillart. An improvement of the raytracing algorithm. Eurographics’85: Proceedingsof the European Computer Graphics Conference
and Exhibition, Ed C. E. Vandoni, pp. 77-88, 1985.
[Endl94] R. Endl, M. Sommer. Classification of RayGenerators in Uniform Subdivisions an Octrees for
Ray Tracing. Computer Graphics Forum Vol. 13(1),1994.
[Fujim86] A. Fujimoto, K. Iwata. ARTS: Accelerated Ray
Tracing System. IEEE Computer Graphics & Applications Vol. 6(4), pp. 16-26. 1986.
[Garga93] I. Gargantini, H.H. Atkinson. Ray Tracing an
Octree: Numerical Evaluation of the First Intersection. Computer Graphics Forum Vol. 12(4), 1993.
[Glass84] A. S. Glassner. Space Subdivision for Fast Ray
Tracing. IEEE Computer Graphics & Applications
Vol. 4(10), pp. 15-22 October 1984.

Figure 14: 3D array of spheres.

6 Conclusions
The recursive top-down algorithm which has been presented
improves the performance of existing ones, as the time
graphs show. It minimizes the number of operations because they are carried out in a top-down recursive style, andusing at each stage the results of the previous stage. Besides
efficiency, it is also desirable for any method to be easy toread, comprehend and implement into a rendering system.
This method is very easy to understand and to incorporate
into such systems because of its simplicity, when comparedto other referenced algorithms.

7 Acknowledgements[Janse85] F.W. Jansen. Data Structures for Ray-tracing.
Data Structures for Raster Graphics L. Kessner, F.
Peters, M. van Lierop (eds). Springer-Verlag, 1985,
pp. 57-73.
[Jevan89] D. Jevans, B. Wyvill. Adaptive Voxel Subdivision
for Ray Tracing. Graphics Interface’89, pp. 164172. June 1989.
[Reinh96] E. Reinhard, Arjan J.F. Kok, F.W. Jansen. Cost
Prediction in Ray Tracing. Rendering Techniques
96, Springer-Verlag, 1996, pp. 42-51.
[Samet89] H. Samet. Implementing Ray Tracing with Octrees and Neighbor Finding”. Computer & Graphics Vol. 13(4), pp. 445-460, 1989.
[Samet90] H. Samet. Applications of Spatial Data Structures: Computer Graphics, Image Processing, and
GIS. Addison-Wesley 1990.
[Spack91] J. Spackman, P.J. Willis. The Smart Navigationof a Ray Through an Oct-Tree: Computer & Graphics Vol. 15(2), pp.185-194, 1991.

This work has been supported by a grant coded as TIC950614-C03-02, and TIC98-0973-C03-01 from the Committee for Science and Technology of the Spanish Government(CICYT).

[Sung91] K. Sung. A DDA Octree Traversal Algorithm for
Ray Tracing. Eurographics’91. Proceedings of theEuropean Computer Graphics Conference and Exhibition, F.H Post and W. Barth (eds), pp. 73-85,
North Holland, 1991.

REFERENCES[Sung92] K. Sung, P. Shirley. Ray Tracing with the BSP
tree. Graphics Gems III. pp. 271-274, 1992.

[Agate91] M. Agate, R.L. Grimsdale, P.F. Lister. The
HERO Algorithm for Ray Tracing Octrees. Ad-