Abstract:
Given a set 
of objects, called a scene, the
ray-shooting
problem asks, given a ray, what is the first object in
intersected
by this ray. A popular approach to speed up ray-shooting queries is to
construct a
space decomposition such as a quadtree in 2D and an octree in 3D. The
query is then answered by traversing the leaves of the tree as they are
intersected by the ray, and for each cell in turn, testing for an
intersection between the ray and the subset of objects intersecting
that
cell. In this paper, the only objects we consider are simplices (points
and segments inside the unit square 
in
,
or points,
segments and triangles inside the unit cube 
in
).
We
denote the tree by 
in either 2D or 3D, and use the notation 
for quadtrees specifically, and 
for octrees. When
possible, we try
and give results valid for any dimension (the tree is then called a box
tree, or tree for short).
There as been a lot of work on quadtrees and octrees in the mesh
generation and graphics community (see the book by Samet [10]
and the thesis of Moore [7]
for references). Since they are
used for discretizing the underlying space, usual
considerations include the tradeoff between the size of the tree and
their accuracy with respect to a certain measure. Here we introduce a
novel problematic on quadtrees (via a cost function) and revisit the
basics of box trees in this new light.
The following cost measure was introduced by Aronov et
al. [1] for the
purpose of predicting the traversal
cost of shooting a ray in 
,
while using a quadtree (for 
) or
an octree (for 
) to store :
 |
(1) |
where 
is the set of leaves
of the quadtree, 
is
the set of scene objects meeting a leaf 
, and
is
the perimeter length (if ) or surface area (if )
of .
The coefficient 
depends on the implementation, and models the
ratio of the cost of the tree traversal (per cell) to that of a
ray-object intersection test (per test).
When is fixed, we simply denote the cost by
.
If we assume that the cost of finding the neighboring cell along a ray
is
bounded by , then this cost function provably models the
cost of
finding all the objects intersected by a random line, with respect to a
rigid-motion invariant distribution of lines [1].
This assumption is valid only for balanced trees (see definition
below),
but the cost function becomes a lower bound for general trees.
In addition, the experiments in [1] show that for many
scenes, this is
also a good estimation of the cost of finding the first object
intersected by a random ray, for either balanced or unbalanced trees.
In [1], the
emphasis is to on evaluating experimentally
the accuracy of the cost measure to predict the cost of ray shooting.
In [6] and in this
paper,
we are interested in estimating the quality of a tree with respect to
its cost. In particular, we wish to construct trees with cost as low
as possible. In [6],
we gave a lower bound on the
infimum 
of the cost of any quadtree, for any given ,
and
showed that the so-called 
-greedy algorithm produces quadtrees
with cost 
both for points and for
segments. In this paper, we extend those
results to octrees (we provide the explicit constants).
We also examine
the effect of rebalancing the tree on the cost measure.
A result of independent interest is an algorithm to rebalance a tree in
time proportional to its final size (and object-cell incidences).
The best algorithm to date has a multiplicative overhead proportional
to
the depth of the tree.
