Cost-driven octree construction schemes: An experimental study

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.