Cost-Optimal  Quadtrees for Ray Shooting

Written with Marc Glisse and David Wood.
Abstract: Given a set $ S$ of objects, called a scene, the ray-shooting problem asks, given a ray, what is the first object in $ S$ 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 $ [0,1]^2$ in $ \mathbb{R}^2$, or points, segments and triangles inside the unit cube $ [0,1]^3$ in $ \mathbb{R}^3$).

The following cost measure was introduced by Aronov et al. [1] for the purpose of predicting the traversal cost of shooting a ray in $ \mathbb{R}^d$, while using a quadtree (for $ d=2$) or an octree (for $ d=3$) to store $ S$:

$\displaystyle c_S(\mathcal{T}) = \sum_{\sigma\in\L (\mathcal{T})}( \gamma+ \vert S\cap\sigma\vert ) \times \lambda_{d-1}(\sigma),$ (1)

where $ \L (\mathcal{T})$ is the set of leaves of the quadtree, $ S\cap\sigma$ is the set of scene objects meeting a leaf $ \sigma$, and $ \lambda_{d-1}(\sigma)$ is the perimeter (if $ d=2$) or surface area (if $ d=3$) of $ \sigma$. The coefficient $ \gamma$ 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 $ S$ is fixed, we simply denote the cost by $ c(\mathcal{T})$. If we assume the cost of finding the neighboring cell meet by a ray is bounded by $ \gamma$, 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].

We wish to construct trees with as low a cost as possible. We first give a lower bound on the infimum $ M(S)$ of the cost of any quadtree, for any given $ S$. We then examine several algorithms which do, or don't, give guaranteed optimal cost, or bounded approximation ratio. Our main result is that the $ 3$-lookahead greedy algorithm (introduced below) produces quadtrees with cost $ O(M)$ both for points and for segments.

References

Related publications

Copyright © 2002, Hervé Brönnimann, hbr@poly.edu
Last modified: Thu Jul 11th, 2002