TY - JOUR

T1 - Cost-driven octree construction schemes

T2 - An experimental study

AU - Aronov, Boris

AU - Brönnimann, Hervé

AU - Chang, Allen Y.

AU - Chiang, Yi Jen

N1 - Funding Information:
✩ Work on this paper has been supported by NSF ITR Grant CCR-0081964. Research of the first author has also been supported in part by NSF Grant CCR-9972568, the second author by NSF CAREER Grant CCR-0133599, and the fourth author by NSF CAREER Grant CCR-0093373 and NSF Grant ACI-0118915. A preliminary version of this paper appeared as B. Aronov, H. Brönnimann, A.Y. Chang, Y.-J. Chiang, Cost-driven octree construction schemes: an experimental study, in: Proc. 19th Annual ACM Symposium on Computational Geometry, 2003, pp. 227–236. * Corresponding author. E-mail addresses: aronov@poly.edu (B. Aronov), hbr@poly.edu (H. Brönnimann), achang@cis.poly.edu (A.Y. Chang), yjc@poly.edu (Y.-J. Chiang).

PY - 2005/5

Y1 - 2005/5

N2 - Given a scene consisting of objects, ray shooting queries answer with the first object encountered by a given ray, and are used in ray tracing and radiosity for rendering photo-realistic images in graphics, radio propagation simulation, and many other problems. We focus on one popular data structure for answering ray shooting queries - 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. While practitioners usually rely on experience and heuristics, it is difficult to fix a set of parameter values that is good for all possible scenes. 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.

AB - Given a scene consisting of objects, ray shooting queries answer with the first object encountered by a given ray, and are used in ray tracing and radiosity for rendering photo-realistic images in graphics, radio propagation simulation, and many other problems. We focus on one popular data structure for answering ray shooting queries - 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. While practitioners usually rely on experience and heuristics, it is difficult to fix a set of parameter values that is good for all possible scenes. 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.

KW - Average performance

KW - Cost model

KW - Cost prediction

KW - Octree

KW - Ray shooting

KW - Space decomposition

UR - http://www.scopus.com/inward/record.url?scp=84867946299&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84867946299&partnerID=8YFLogxK

U2 - 10.1016/j.comgeo.2004.07.005

DO - 10.1016/j.comgeo.2004.07.005

M3 - Article

AN - SCOPUS:84867946299

SN - 0925-7721

VL - 31

SP - 127

EP - 148

JO - Computational Geometry: Theory and Applications

JF - Computational Geometry: Theory and Applications

IS - 1-2

ER -