On Improving KD-Trees for Ray Shooting
Vlastimil Havran, Jiřı́ Bittner · Digital Library (University of West Bohemia) · 2002
Efficient ray shooting algorithm is inherently required by many computer graphics algorithms, particularly in image synthesis. Practical ray shooting algorithms aiming at the average-case complexity use some underlying spatial data structure such as $kd$-tree. We show the new termination criteria algorithm that improves the space and time complexity of the $kd$-tree construction. It provides efficient ray-shooting queries and does not require any specific constants from a user. Further, we show how to apply a novel clipping algorithm into the $kd$-tree within construction phase in order to improve its properties.