Cost-driven octree construction schemes: an experimental study

Recently, we introduced a simple cost predictor that reflects the average cost of ray shooting with a given octree (Cost prediction for ray shooting, in: Proc. 18th Annu. ACM Sympos. Comput. Geom., ACM, New York, 2002, pp. 293-302), and showed a termination criterion (cost-driven k-greedy) that guarantees a cost within a constant factor of optimal (Cost-optimal trees for ray shooting, in: Proc. LATIN'04, Lecture Notes in Comput. Sci., vol. 2976, Springer, Berlin, 2004, pp. 349-358). In this study, we compare this criterion with several octree construction schemes widely used in the computer graphics literature (such as bounding the number of objects in a leaf and the maximum depth). Our experimental results show that the octrees constructed using our schemes are generally comparable to or better than those built with a priori fixed parameters. We then fine-tune the predictor and observe the behavior of our algorithm on octrees built to support a simple ray-tracing engine. It appears to work well in practice.