Date: 21 Mar 2003
From: jyrki@diku.dk
Subject: Geometry talk

Topic: Cost-driven octree optimization: an experimental study
Speaker: Hervé Brönnimann, Polytechnic University, New York
Time:  Tuesday, 25 March 2003, 15.15–16.00
Place: UP1 at DIKU

Ray shooting is the basic geometric primitive behind visibility in
3D, and is used extensively in ray tracing and radio-propagation
simulations. A standard approach to speed up ray shooting is the use
of spatial decompositions such as kD-trees, or octrees.

In this talk, I will present a simple-to-evaluate cost measure on
octrees, that demonstrably predicts the cost of ray shooting for a
given scene. Using this cost measure, we seek to get better data
structures for ray shooting: we present a construction for octrees
that provably achieves a constant factor of the optimal cost.

We experimentally evaluate this construction against other
octree-construction strategies, including both cost-aware and
cost-oblivious schemes. We show that our strategy achieves an
approximation ratio very close to 1, but that another simpler
strategy (whose worst-case ratio is very bad) is usually competitive
for all scenes of practical application.

PE-labs home page: http://www.diku.dk/~jyrki/PE-lab/