Abstract
Ray tracing requires testing of many rays to determine intersections with objects. A way of reducing the computation is to organize objects into hierarchical data structures. We examine two heuristics for space subdivisions using bintrees, one based on the intuition that surface area is a good estimate of intersection probability, one based on the fact that the optimal splitting plane lies between the spatial median and the object median planes of a volume. Traversal algorithms using cross links between nodes are presented as generalizations of ropes in octrees. Simulations of the surface area heuristic and the cross link scheme are presented. These results generalize to other hierarchical data structures.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Amanatides J, Woo A (1987) A fast voxel traversal algorithm for ray tracing. Proc Eurographics '87:1–10
Arnaldi B, Priol T, Bouatouch K (1987) A new space subdivision method for ray tracing CSG modeled scenes. Visual Computer 3:98–108
Cleary JG, Wyvill G (1988) Analysis of an algorithm for fast ray tracing using uniform space subdivision. Visual Comput 4:65–83
Cook RL, Porter T, Carpenter L (1984) Distributed ray tracing. Comput Graph 18:137–145
Fujimoto A, Tanaka T, Iwata K (1986) ARTS: accelerated ray-tracing system. IEEE Comput Graph Appl 6:16–26
Glassner AS (1984) Space subdivision for fast ray tracing. IEEE Comput Graph Appl 4:15–22
Glassner AS (1987a) An overview of ray tracing SIGGRAPH '87 Introduction to Ray Tracing Course Notes
Glassner AS (1987b) Spacetime ray tracing for animation. SIGGRAPH '87 Introduction to Ray Tracing Course Notes
Glassner AS (1988) Spacetime ray tracing for animation. IEEE Comput Graph Appl 8:60–70
Goldsmith J, Salmon J (1987) Automatic creation of object hierarchies for ray tracing. IEEE Comput Graph Appl 7:14–20
Heckbert PS (1982) Color image quantization for frame buffer display. Comput Graph 16:297–307
Kaplan MR (1985) The uses of spatial coherence in ray tracing. SIGGRAPH '85 Course Notes no 11
Kay TL, Kajiya JT (1986) Ray tracing complex scenes. Comput Graph 20:269–277
Kindon SJ (1986) Speeding up ray-scene intersections. Thesis, Univ Waterloo
MacDonald JD (1988) Space subdivision algorithms for ray tracing. Thesis, Univ Waterloo
Rubin SM, Whitted T (1980) A three-dimensional representation for fast rendering of complex scenes. Comput Graph 14:110–116
Samet H (1984) The quadtree and related hierarchical data structures. Comput Surv 16:187–260
Samet H, Webber RE (1988) Hierarchical data structures and algorithms for computer graphics. IEEE Comput Graph Appl 8:48–68; 8:59–75
Scherson ID, Caspary E (1987) Data structures and the time complexity of ray tracing. Visual Comput 3:201–213
Stone L (1975) Theory of optimal search. Academic Press, New York
Weghorst H, Hooper G, Greenberg DP (1984) Improved computational methods for ray tracing. ACM Trans Graphics 3:52–69
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
MacDonald, J.D., Booth, K.S. Heuristics for ray tracing using space subdivision. The Visual Computer 6, 153–166 (1990). https://doi.org/10.1007/BF01911006
Issue Date:
DOI: https://doi.org/10.1007/BF01911006