Experiences with Streaming Construction of SAH KD-Trees

Stefan Popov, Johannes Günther, Hans-Peter Seidel, and Philipp Slusallek

Teaser 1 Teaser 2 Teaser 3 Teaser 4 Teaser 5 Teaser 6 Teaser 7


A ma­jor rea­son for the re­cent ad­vance­ments in ray trac­ing per­for­mance is the use of op­ti­mized ac­cel­er­a­tion struc­tures, namely kd-trees based on the sur­face area heuris­tic (SAH). Though al­go­rithms ex­ist to build these search trees in O(n log n), the con­struc­tion times for larger scenes are still high and do not al­low for re­build­ing the kd-tree ev­ery frame to sup­port dy­namic changes.

In this pa­per we pro­pose mod­i­fi­ca­tions to pre­vi­ous kd-tree con­struc­tion al­go­rithms that sig­nif­i­cantly in­crease the co­her­ence of mem­ory ac­cesses dur­ing con­struc­tion of the kd-tree. Ad­di­tion­ally we pro­vide the­o­ret­i­cal and prac­ti­cal re­sults re­gard­ing con­ser­va­tively sub-sampling of the SAH cost func­tion.


RT06 (Best Paper Award)
6 pages
1544 kb

bibtex entry

Additional Material

Example SAH cost function

SAH cost function [pdf] 19 kb

[eps] 26 kb

[png] 21 kb

Valid XHTML 1.0 Transitional