ISSN:
1432-2315
Keywords:
Octree
;
Ray tracing
;
Space subdivision
;
Splitting plane
;
Surface area
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
Notes:
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.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01911006
Permalink