k-d Trees For Raytracing

Contribution to the research seminar on visualization in winter semester 1998/1999
by Jiri Hladuvka, Institute of Computer Graphics, Vienna University of Technology, Austria.

Abstract

There are several possibilities how to make a ray-tracing or ray-casting faster. One outstanding class of approaches employs data structures for speeding up the the search for a closest intersection on a ray. Data structures which support efficient geometric search allow us to look at only a small percentage of the scene to determine the closest intersection. Octrees, BSP trees, and nested bounding volumes are examples of explicitly hierarchical search structures of this type.

This topic focuses on use of k-d trees as a binary space partitioning (BSP) structure used for raytracing. k-d tree (Slide 4), as proposed by Bentley [1] is a structure for fast searching in multidimensional spaces. Just for better interpretation, in case of raytracing, the space to be searched in is mostly 2 or 3 dimensional Euclidean Space (Slide 5).
The structure proposed in [1] forces, however, periodical cycling of partitioning planes leading to undesirable deep trees. The depth of tree can be (in general case) decreased using so-called relaxed k-d (r-k-d) trees (Slide 6) which allow the discriminants (partitioning plane orientations) be arbitrary. In case of r-k-d trees, the depth is usually less (Slides 7 and 8), so such a structure is used for raytracing purposes instead of the originally proposed one.

A large amount of work in area of k-d tress in raytracing was done by K.R.Subramanian ( [3], [4], [5] ) In his diploma thesis, he came up with idea to use, for raytracing purpose, k-d tree as a BSP structure. In his further work, he compared (according ray-tracing benchmark test [7]) influence of factors (Slides 9 to 13) to the performance of using k-d trees. These include type of ray traversal, partitioning strategies and bounding volumes

The results at graph (slide 14) point out how important may be the choice of partitioning strategy and the power of bounding volumes.

References

  1. J. L. Bentley , Data Structures for range searching , Computing Surveys, 11(4), December 1979
  2. A. S. Glassner , Space Subdivision for fast ray tracing , IEEE Computer Graphics and Applications, 4(1):15-22, October 1984
  3. K. R. Subramanian, Fast Ray Tracing Using k-d Trees , Department of Computer Science, The University of Texas at Austin, Master's Thesis, 1987
  4. K. R. Subramanian, Factors Affecting Performance of ray Tracing Hierarchies, TR-90-21, The University of Texas at Austin, August 1990.
  5. K. R. Subramanian, Adapting Search Structures to Scene Characteristics for Ray Tracing, PhD Dissertation, Department of Computer Science, The University of Texas at Austin, December 1990.
  6. A. D. Brown, Design and Analysis of Spatial Data Structures, Ph.D. Thesis Project, 1998
  7. E. A. Haines, A proposal for standard graphics environments, IEEE Computer Graphics and Applications, pages 3-5, November 1987

(See also slide 15)

Jiri Hladuvka
Last modified: Wed Jan 22 15:18:16 MET