Cost-driven octree construction schemes: An experimental study

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

    Research output: Chapter in Book/Report/Conference proceedingConference contribution


    Many algorithmic problems are interesting to both theoreticians and practitioners, but in a different manner. While the theoreticians have traditionally focused on worst-case scenarios which is often not very useful in practice, the practitioners are sometimes stuck in the hacking culture and arrive at solutions that only work well in a few specific cases. An example of such an algorithmic problem is ray shooting. Imposing some data structure to support ray-shooting queries usually helps to improve the efficiency of the algorithm. We focus on one such data structure - the octree. It is flexible and adaptive and has many applications. However, its degree of adaptiveness usually depends on manually selected parameters controlling its termination criteria. It is difficult to fix a set of parameter values that is good for all possible scenes. One approach to resolve this problem is to construct a data structure which "tunes itself" to the input without using arbitrary preset parameters, so that a single algorithm is suitable for all situations. Surprisingly, only a few investigations have focused on this approach compared to the huge amount of research papers on ray shooting from both the theoreticians and the practitioners. We take some steps in this direction by evaluating several octree construction schemes for use in ray shooting, some widely used in the computer graphics literature (such as bounding the number of objects in a leaf and the maximum depth) and some developed in companion papers as part of this research (cost-driven k-greedy termination criteria). Our experimental results show that the octrees constructed using our schemes are better than those built with a priori fixed parameters. Our octree construction algorithm is driven by a simple ost predictor and has been proven elsewhere to approximate the optimal tree to within a constant factor. We fine-tune the predictor and observe the behavior of our algorithm on octrees built to support a simple ray-tracing engine and compare its performance with those of commonly used alternatives. It appears to work well in practice.

    Original languageEnglish (US)
    Title of host publicationProceedings of the Annual Symposium on Computational Geometry
    Number of pages10
    StatePublished - 2003
    EventNineteenth Annual Symposium on Computational Geometry - san Diego, CA, United States
    Duration: Jun 8 2003Jun 10 2003


    OtherNineteenth Annual Symposium on Computational Geometry
    Country/TerritoryUnited States
    Citysan Diego, CA


    • Average performance
    • Cost model
    • Cost prediction
    • Octree
    • Ray shooting
    • Space decomposition

    ASJC Scopus subject areas

    • Software
    • Geometry and Topology
    • Safety, Risk, Reliability and Quality
    • Chemical Health and Safety


    Dive into the research topics of 'Cost-driven octree construction schemes: An experimental study'. Together they form a unique fingerprint.

    Cite this