Protosphere

A GPU-Assisted Prototype Guided Sphere Packing Algorithm for Arbitrary Objects

We present a new algorithm that is able to efficiently compute a space filling sphere packing for arbitrary objects. It is independent of the object's representation (polygonal, NURBS, CSG,...); the only precondition is that it must be possible to compute the distance from any point to the surface of the object. Moreover, our algorithm is not restricted to 3D but can be easily extended to higher dimensions.

The basic idea is very simple and related to prototype based approaches known from machine learning. This approach directly leads to a parallel algorithm that we have implemented using CUDA. As a byproduct, our algorithm yields an approximation of the object's medial axis that has applications ranging from path-planning to surface reconstruction.

Sphere packings have proven to be very efficient when doing collision detection, which was the starting point of our research.

For further informations about our new geometric data structure that is based on sphere packings, the "Inner Sphere Trees", please visit our project website.

A model of a dragon filled with 5000 spheres (left). As a side effect of our algorithm, we get an approximation of the medial axis in the first iteration (right).

Publications

• ProtoSphere: A GPU-Assisted Prototype Guided Sphere Packing Algorithm for Arbitrary Objects , IEEE , 2011. [BibTex]

Videos on Youtube

Visualization of our Algorithm

This work was partially supported by DFG grant ZA292/1-1 and the research project, funded by the Federal Minstry of Education and Research (BMBF) grant Avilus / 01 IM 08 001 U.