On building fast kd-Trees for Ray Tracing, and on doing that in O(N log N)
Top Cited Papers
- 1 September 2006
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
Though a large variety of efficiency structures for ray tracing exist, kd-trees today seem to slowly become the method of choice. In particular, kd-trees built with cost estimation functions such as a surface area heuristic (SAH) seem to be important for reaching high performance. Unfortunately, most algorithms for building such trees have a time complexity of O(N log2 N), or even O(N2). In this paper, we analyze the state of the art in building good kd-trees for ray tracing, and eventually propose an algorithm that builds SAH kd-trees in O(N log N), the theoretical lower boundKeywords
This publication has 10 references indexed in Scilit:
- Fast kd-tree Construction with an Adaptive Error-Bounded HeuristicPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2006
- RT-DEFORM: Interactive Ray Tracing of Dynamic Scenes using BVHsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2006
- Experiences with Streaming Construction of SAH KD-TreesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2006
- On building fast kd-Trees for Ray Tracing, and on doing that in O(N log N)Published by Institute of Electrical and Electronics Engineers (IEEE) ,2006
- Ray Tracing Animated Scenes using Motion DecompositionComputer Graphics Forum, 2006
- Balancing Considered Harmful — Faster Photon Mapping using the Voxel Volume Heuristic —Computer Graphics Forum, 2004
- Distributed interactive ray tracing of dynamic scenesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2004
- Heuristics for ray tracing using space subdivisionThe Visual Computer, 1990
- AnO(n logn) algorithm for the all-nearest-neighbors ProblemDiscrete & Computational Geometry, 1989
- Automatic Creation of Object Hierarchies for Ray TracingIEEE Computer Graphics and Applications, 1987