Cost-driven octree construction schemes: An experimental study. (English) Zbl 1060.65553
Summary: 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.
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.
MSC:
| 65D18 | Numerical aspects of computer graphics, image analysis, and computational geometry |
Keywords:
Ray shooting; Cost model; Cost prediction; Average performance; Octree; Space decomposition; numerical examples; computer graphics; algorithmSoftware:
GenocopReferences:
| [1] | Appel, A., Some techniques for shading machine renderings for solids, (AFIPS Joint Computer Conf. Proc., vol. 32 (1968), AFIPS), 37-45 |
| [2] | Aronov, B.; Brönnimann, H.; Chang, A. Y.; Chiang, Y.-J., Cost prediction for ray shooting, (Proc. 18th Annu. ACM Sympos. Comput. Geom. (2002), ACM: ACM New York), 293-302 · Zbl 1414.68109 |
| [3] | Aronov, B.; Fortune, S., Approximating minimum weight triangulations in three dimensions, Discrete Comput. Geom., 21, 4, 527-549 (1999) · Zbl 0933.68138 |
| [4] | Arvo, J.; Kirk, D., A survey of ray tracing acceleration techniques, (Glassner, A. S., An Introduction to Ray Tracing (1989), Morgan Kaufmann), 201-262 |
| [5] | Bertoni, H. L., Radio Propagation for Modern Wireless Systems (2000), Prentice-Hall: Prentice-Hall Upper Saddle River, NJ |
| [6] | Bertoni, H. L.; Torrico, S. A., Propagation prediction for urban systems, (Godara, L., Handbook on Antennas in Wireless Communications (2002), CRC Press) |
| [7] | Brönnimann, H.; Glisse, M., Cost-optimal trees for ray shooting, (Proc. 6th Latin American Symp. Theoretical Informatics. Proc. 6th Latin American Symp. Theoretical Informatics, Lecture Notes in Computer Science, vol. 2976 (2004), Springer: Springer Berlin), 349-358 · Zbl 1196.68297 |
| [8] | Cassen, T.; Subramanian, K. R.; Michalewicz, Z., Near-optimal construction of partitioning trees using evolutionary techniques, (Proc. of Graphics Interface ’95 (1995), Canad. Inf. Proc. Soc.: Canad. Inf. Proc. Soc. Toronto), 16-19 |
| [9] | F. Cazals, M. Sbert, Some integral geometry tools to estimate the complexity of 3d scenes, Research Report no. 3204, INRIA, 1997; F. Cazals, M. Sbert, Some integral geometry tools to estimate the complexity of 3d scenes, Research Report no. 3204, INRIA, 1997 |
| [10] | A.Y. Chang, A survey of geometric data structures for ray tracing, Technical Report TR-CIS-2001-06, CIS Department, Polytechnic University, 2001; A.Y. Chang, A survey of geometric data structures for ray tracing, Technical Report TR-CIS-2001-06, CIS Department, Polytechnic University, 2001 |
| [11] | Cleary, J. G.; Wyvill, G., Analysis of an algorithm for fast ray tracing using uniform space subdivision, The Visual Computer, 4, 65-83 (1988) |
| [12] | Glassner, A. S., Space subdivision for fast ray tracing, IEEE Comput. Graph. Appl., 15-22 (1984) |
| [13] | Fortune, S., Algorithms for the prediction of indoor radio propagation, Manuscript, 1998, Available at |
| [14] | Glassner, A., Space subdivision for fast ray tracing, IEEE Comput. Graph. Appl., 15-22 (1984) |
| [15] | Goldsmith, J.; Salmon, J., Automatic creation of object hierarchies for ray tracing, IEEE Comput. Graph. Appl., 14-20 (1984) |
| [16] | Haines, E., The standard procedural database (SPD), Version 3.13, 3D/Eye, 1992, Home page at |
| [17] | Havran, V., Heuristic ray shooting algorithms, Ph.D. Thesis, Department of Computer Science and Engineering, Faculty of Electrical Engineering, Czech Technical University in Prague, November 2000, Available at |
| [18] | Kaplan, M. R., The use of spatial coherence in ray tracing, (Techniques for Computer Graphics (1987), Springer: Springer Berlin), 173-193 |
| [19] | Kim, S. C.; Guarino, B.; Willis, T.; Erceg, V.; Fortune, S.; Valenzuela, R.; Thomas, L.; Ling, J.; Moore, J., Radio propagation measurements and prediction using three-dimensional ray tracing in urban environments at 908 Mhz and 1.9 Ghz, IEEE Trans. Vehicular Technol., 48, 931-946 (1999) |
| [20] | Klimaszewski, K.; Woo, A.; Cazals, F.; Haines, E., Additional notes on nested grids, Ray Tracing News, 10, 3 (1997), Available at |
| [21] | MacDonald, J. D.; Booth, K. S., Heuristics for ray tracing using space subdivision, The Visual Computer, 6, 153-166 (1990) |
| [22] | Michalewicz, Z., Genetic Algorithms+Data Structures=Evolution Programs (1996), Springer: Springer Berlin · Zbl 0841.68047 |
| [23] | Möller, T.; Trumbore, B., Fast, minimum storage ray-triangle intersection, J. Graphics Tools, 2, 1, 21-28 (1987), Code available at |
| [24] | D.W. Moore, Simplicial mesh generation with applications, Ph.D. Dissertation, Cornell University, 1992; D.W. Moore, Simplicial mesh generation with applications, Ph.D. Dissertation, Cornell University, 1992 |
| [25] | Naylor, B., Constructing good partitioning trees, (Proc. of Graphics Interface ’93 (1993), Canad. Inf. Proc. Soc.: Canad. Inf. Proc. Soc. Toronto), 181-191 |
| [26] | Reinhard, E.; Kok, A. J.F.; Jansen, F. W., Cost prediction in ray tracing, (Proc. Eurographics Workshop, Rendering Techniques ’96, Porto, Portugal (1996), Springer: Springer Berlin), 41-50 |
| [27] | Rubin, S. M.; Whitted, T., A 3-dimensional representation for fast rendering of complex scenes, Proc. Computer Graphics (SIGGRAPH’80), 14, 3, 110-116 (1980) |
| [28] | Samet, H., Applications of Spatial Data Structures (1990), Addison-Wesley: Addison-Wesley Reading, MA |
| [29] | Scherson, I.; Caspary, E., Data structures and the time complexity of ray tracing, The Visual Computer, 3, 4, 201-213 (1987) |
| [30] | K.R. Subramanian, D.S. Fussell, Factors affecting performance of ray tracing hierarchies, TR-90-21, University of Texas at Austin, 1990; K.R. Subramanian, D.S. Fussell, Factors affecting performance of ray tracing hierarchies, TR-90-21, University of Texas at Austin, 1990 |
| [31] | Subramanian, K. R.; Fussell, D. S., Automatic termination criteria for ray tracing hierarchies, (Proc. of Graphics Interface ’91 (1991), Canad. Inf. Proc. Soc.: Canad. Inf. Proc. Soc. Toronto), 93-100 |
| [32] | Sutherland, I. E.; Sproul, R. F.; Schumacker, R. A., A characterization of ten hidden surface algorithms, ACM Computing Surveys, 6, 5, 1-55 (1974) · Zbl 0287.68024 |
| [33] | Stanford University, The Stanford 3D Scanning Repository. Home page at |
| [34] | Weghorst, H.; Hooper, G.; Greenberg, D. P., Improved computational methods for ray tracing, ACM Trans. Graph., 3, 1, 52-69 (1984) |
| [35] | Whang, K. Y.; Song, J. W.; Chang, J. W.; Kim, J. Y.; Choand, W. S.; Park, C. M.; Song, I. Y., Octree-R: An adaptive octree for efficient ray tracing, IEEE Trans. Visual Comp. Graph., 1, 343-349 (1995) |
| [36] | Whitted, T., An improved illumination model for shading display, Comm. ACM, 23, 6, 343-349 (1980) |
| [37] | Yagel, R.; Cohen, D.; Kaufman, A., Discrete ray tracing, IEEE Comput. Graph. Appl., 12, 5, 19-28 (1992) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
