DocumentCode
2846927
Title
An Efficient SAH-Based KD-Tree Construction Algorithm for Ray Tracing
Author
Wu, Liuzhou ; Chen, Zelin
Author_Institution
Sch. of Comput. Sci. & Eng., South China Univ. of Technol., Guangzhou, China
fYear
2009
fDate
11-13 Dec. 2009
Firstpage
1
Lastpage
4
Abstract
KD-Tree is an important accelerating structure for ray-tracing based realistic rendering. How to construct kd-tree efficiently is very crucial for ray tracing performance. In this paper, we present a fast construction algorithm. It is based on SAH cost estimation function and adopts a clever way to keep sorting order without sorting every time. Thus we reduce the complexity to O(NlogN), which is the asymptotic lower bound for building kd-trees.
Keywords
computational complexity; costing; ray tracing; rendering (computer graphics); sorting; trees (mathematics); KD-tree; SAH cost estimation function; SAH-based kd-tree construction algorithm; computational complexity; ray tracing; realistic rendering; sorting order; Acceleration; Buildings; Chromium; Computer science; Cost function; Heuristic algorithms; Layout; Ray tracing; Sorting; Tree data structures;
fLanguage
English
Publisher
ieee
Conference_Titel
Computational Intelligence and Software Engineering, 2009. CiSE 2009. International Conference on
Conference_Location
Wuhan
Print_ISBN
978-1-4244-4507-3
Electronic_ISBN
978-1-4244-4507-3
Type
conf
DOI
10.1109/CISE.2009.5365130
Filename
5365130
Link To Document