非表示:
キーワード:
-
要旨:
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.
