Cost prediction for ray shooting in octrees

Boris Aronov, Hervé Brönnimann, Allen Y. Chang, Yi Jen Chiang

    Research output: Contribution to journalArticlepeer-review


    The ray shooting problem arises in many different contexts and is a bottleneck of ray tracing in computer graphics. Unfortunately, theoretical solutions to the problem are not very practical, while practical methods offer few provable guarantees on performance. Attempting to combine practicality with theoretical soundness, we show how to provably measure the average performance of any ray-shooting method based on traversing a bounded-degree spatial decomposition, where the average is taken to mean the expectation over a uniform ray distribution. An approximation yields a simple, easy-to-compute cost predictor that estimates the average performance of ray shooting without running the actual algorithm. We experimentally show that this predictor provides an accurate estimate of the efficiency of executing ray-shooting queries in octree-induced decompositions, irrespective of whether or not the bounded-degree requirement is enforced, and of the criteria used to construct the octrees. We show similar guarantees for decompositions induced by kd-trees and uniform grids. We also confirm that the performance of an octree while ray tracing or running a radio-propagation simulation is accurately captured by our cost predictor, for ray distributions arising from realistic data.

    Original languageEnglish (US)
    Pages (from-to)159-181
    Number of pages23
    JournalComputational Geometry: Theory and Applications
    Issue number3
    StatePublished - Jul 2006


    • Average performance
    • Cost model
    • Cost prediction
    • Octree
    • Ray shooting
    • Space decomposition
    • Uniform grid
    • kd-tree

    ASJC Scopus subject areas

    • Computer Science Applications
    • Geometry and Topology
    • Control and Optimization
    • Computational Theory and Mathematics
    • Computational Mathematics


    Dive into the research topics of 'Cost prediction for ray shooting in octrees'. Together they form a unique fingerprint.

    Cite this