@INPROCEEDINGS{SzirmayKalos2002:SCCG,
AUTHOR = {Szirmay-Kalos, L{\'a}szl{\"o} and Havran, Vlastimil and Bal{\'a}zs,
Benedek and Sz{\'e}csi, L{\'a}szl{\"o}},
EDITOR = {Chalmers, Alan},
TITLE = {On the Efficiency of Ray-shooting Acceleration Schemes},
BOOKTITLE = {Proceedings of the 18th Spring Conference on Computer Graphics (SCCG 2002)},
PADDRESS = {New York, USA},
ADDRESS = {Budmerice, Slovakia},
PUBLISHER = {ACM Siggraph},
ISBN = {1-58113-608-0},
YEAR = {2002},
PAGES = {89--98},
ABSTRACT = {This paper examines the efficency of different
ray-shooting acceleration schemes, including the
uniform space subdivision, octree and kd-tree. We use
simple computational model , which assume that the
objects are uniformly distributed in space. The
efficiency is characterized by two measures,
including the expected number of ray-object
intersections needed to identified the first
intersected object, and the expected number of steps
on the space partitioning data structure. We can
come to the interesting conclusion that these numbers
are constant and are independent of the number of
objects in the scene. The number of intersections is
determined by how well the cells of the partitioning
data structure enclose the objects. Such analysis
helps to understand why kd-tree is better than octree
and uniform space subdivision and provides hints to
improve their implementation.},
}