Point Cloud Collision Detection

M. -P. Cani and M. Slater (Editors)
J. Klein and Gabriel Zachmann
In proceedings of Eurographics 2004, pages 567-576, Sept. 2004
 

Abstract

In the past few years, many efficient rendering and surface reconstruction algorithms for point clouds have been developed. However, collision detection of point clouds has not been considered until now, although this is a prerequisite to use them for interactive or animated 3D graphics. We present a novel approach for time-critical collision detection of point clouds. Based solely on the point representation, it can detect intersections of the underlying implicit surfaces. The surfaces do not need to be closed.

We construct a point hierarchy where each node stores a sufficient sample of the points plus a sphere covering of a part of the surface. These are used to derive criteria that guide our hierarchy traversal so as to increase convergence. One of them can be used to prune pairs of nodes, the other one is used to prioritize still to be visited pairs of nodes. At the leaves we efficiently determine an intersection by estimating the smallest distance.

We have tested our implementation for several large point cloud models. The results show that a very fast and precise answer to collision detection queries can always be given.

Keywords: animation, approximation of surfaces and contours, computational geometry and object-modeling, geometric algorithms, languages and systems, object hierarchy, physically-based modeling, three-dimensional graphics and realism, virtual reality

Download Paper

Download Paper

Additional Material

Bibtex

@INPROCEEDINGS{klein-2004-point-2,
     author = {Klein, J. and Zachmann, Gabriel},
     editor = {Cani, M. -P. and Slater, M.},
      pages = {567--576},
      title = {Point Cloud Collision Detection},
  booktitle = {Eurographics 2004},
     volume = {23},
     number = {3},
       year = {2004},
      month = sep,
   keywords = {animation, approximation of surfaces and contours, computational geometry and object-modeling,
               geometric algorithms, languages and systems, object hierarchy, physically-based modeling,
               three-dimensional graphics and realism, virtual reality},
   abstract = {In the past few years, many efficient rendering and surface reconstruction algorithms for point
               clouds have been developed. However, collision detection of point clouds has not been considered
               until now, although this is a prerequisite to use them for interactive or animated 3D graphics. We
               present a novel approach for time-critical collision detection of point clouds. Based solely on the
               point representation, it can detect intersections of the underlying implicit surfaces. The surfaces
               do not need to be closed.
               
               We construct a point hierarchy where each node stores a sufficient sample of the points plus a
               sphere covering of a part of the surface. These are used to derive criteria that guide our hierarchy
               traversal so as to increase convergence. One of them can be used to prune pairs of nodes, the other
               one is used to prioritize still to be visited pairs of nodes. At the leaves we efficiently determine
               an intersection by estimating the smallest distance.
               
               We have tested our implementation for several large point cloud models. The results show that a very
               fast and precise answer to collision detection queries can always be given.}
}