  Point cloud models are a common shape representation for several reasons.
Three-dimensional scanning devices are widely used nowadays and points are an
attractive primitive for rendering complex geometry. Nevertheless, there is not
much literature on collision detection for point cloud models. This paper
presents a novel collision detection algorithm for large point cloud models
using voxels, octrees and bounding spheres hierarchies (BSH). The scene graph
is divided in voxels. The objects of each voxel are organized into an octree.
Due to the high number of points in the scene, each non-empty cell of the
octree is organized in a bounding sphere hierarchy, based on an R-tree
hierarchy like structure. The BSH hierarchies are used to group neighboring
points and filter out very quickly parts of objects that do not interact with
other models. Points derived from laser scanned data typically are not
segmented and can have arbitrary spatial resolution thus introducing
computational and modeling issues. We address these issues and our results show
that the proposed collision detection algorithm effectively finds intersections
between point cloud models since it is able to reduce the number of bounding
volume checks and updates.
