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/