Fast kd-Tree Construction for 3D-rendering Algorithms like Ray Tracing

Document type: Conference Papers
Peer reviewed: Yes
Author(s): Sajid Hussain, Håkan Grahn
Title: Fast kd-Tree Construction for 3D-rendering Algorithms like Ray Tracing
Conference name: International Symposium on Visual Computing (ISVC)
Year: 2007
Pagination: 681-690
Publisher: Springer-Verlag
City: California
ISI number: 000251785200067
Organization: Blekinge Institute of Technology
Department: School of Engineering - Dept. of Systems and Software Engineering (Sektionen för teknik – avd. för programvarusystem)
School of Engineering S- 372 25 Ronneby
+46 455 38 50 00
Authors e-mail:
Language: English
Abstract: Many computer graphics rendering algorithms and techniques use
ray tracing for generation of natural and photo-realistic images. The efficiency
of the ray tracing algorithms depends, among other techniques, upon the data
structures used in the background. kd-trees are some of the most commonly
used data structures for accelerating ray tracing algorithms. Data structures using
cost optimization techniques based upon Surface Area Heuristics (SAH) are
generally considered to be best and of high quality. During the last decade, the
trend has been moved from off-line rendering towards real time rendering with
the introduction of high speed computers and dedicated Graphical Processing
Units (GPUs). In this situation, SAH-optimized structures have been considered
too slow to allow real-time rendering of complex scenes. Our goal is to demonstrate
an accelerated approach in building SAH-based data structures to be used
in real time rendering algorithms. The quality of SAH-based data structures
heavily depends upon split-plane locations and the major bottleneck of SAH
techniques is the time consumed to find those optimum split locations. We present
a parabolic interpolation technique combined with a golden section search
criteria for predicting kd-tree split plane locations. The resulted structure is
30% faster with 6% quality degradation as compared to a standard SAH approach
for reasonably complex scenes with around 170k polygons.
Subject: Computer Science\Computersystems
Computer Science\General
Computer Science\General
Keywords: Kd-Tree, ray tracing, optimization