Proceedings: GI 2014

Efficient collision detection while rendering dynamic point clouds

Mohamed Radwan , Stefan Ohrhallinger , Michael Wimmer

Proceedings of Graphics Interface 2014: Montréal, Québec, Canada, 7 - 9 May 2014, 25-33

DOI 10.20380/GI2014.04

  • Bibtex

    author = {Radwan, Mohamed and Ohrhallinger, Stefan and Wimmer, Michael},
    title = {Efficient collision detection while rendering dynamic point clouds},
    booktitle = {Proceedings of Graphics Interface 2014},
    series = {GI 2014},
    year = {2014},
    issn = {0713-5424},
    isbn = {978-1-4822-6003-8},
    location = {Montr{\'e}al, Qu{\'e}bec, Canada},
    pages = {25--33},
    numpages = {9},
    doi = {10.20380/GI2014.04},
    publisher = {Canadian Human-Computer Communications Society},
    address = {Toronto, Ontario, Canada},


A recent trend in interactive environments is the use of unstructured and temporally varying point clouds. This is driven by both affordable depth cameras and augmented reality simulations. One research question is how to perform collision detection on such point clouds. State-of-the-art methods for collision detection create a spatial hierarchy in order to capture dynamic point cloud surfaces, but they require O(NlogN) time for N points. We propose a novel screen-space representation for point clouds which exploits the property of the underlying surface being 2D. In order for dimensionality reduction, a 3D point cloud is converted into a series of thickened layered depth images. This data structure can be constructed in O(N) time and allows for fast surface queries due to its increased compactness and memory coherency. On top of that, parts of its construction come for free since they are already handled by the rendering pipeline. As an application we demonstrate online collision detection between dynamic point clouds. It shows superior accuracy when compared to other methods and robustness to sensor noise since uncertainty is hidden by the thickened boundary.