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
Videos on Youtube
Visualization of our Algorithm
This work was partially supported by DFG grant ZA292/1-1 and the
 research project, founded by the Federal Minstry of Education and Research (BMBF) grant Avilus / 01 IM 08 001 U.
|
|
