ON IMPROVING KD-TREES FOR RAY SHOOTING
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.
Keywords: ray shooting, ray casting, spatial data structures, clipping,
$kd$-tree.