Print (gzipped Postscript) |
Print (PDF) | On-Screen (PDF) | Slides (PDF) |
---|---|---|---|
EG 2004 (2.5 MB) | EG 2004 (2.4 MB) | EG 2004 (2.4 MB) | EG 2004 (2 MB) |
XViD (35 MB) |
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.
@INPROCEEDINGS{Zach04f, author = "Jan Klein and Gabriel Zachmann", title = "Point Cloud Collision Detection", booktitle = "Com{\-}pu{\-}ter Graphics forum (Proc. EUROGRAPHICS)", editor = "M.-P. Cani and M. Slater", year = "2004", month = "Aug 30 -- Sep 3", volume = "23", number = "3", pages = "567--576", address = "Grenoble, France", url = "http://www.gabrielzachmann.org/", }