Tetrahedral Mesh Generation for Deformable Bodies

Neil Molino (Stanford University)
Robert Bridson (Stanford University)
Ronald Fedkiw (Stanford University)

Submitted to SCA 2003


Motivated by the simulation of deformable bodies, we propose a new tetrahedral mesh generation algorithm that produces both high quality elements and a mesh that is well conditioned for subsequent large deformations. We use a signed distance function defined on a grid in order to represent the object geometry. After tiling space with a uniform lattice based on crystallography, we identify a subset of these tetrahedra that adequately fill the space occupied by the object. Then we use the signed distance function or other user defined criteria to guide a red green mesh subdivision algorithm that results in a candidate mesh with the appropriate level of detail. After this, both the signed distance function and topological considerations are used to prune the mesh as close to the desired shape as possible while keeping the mesh flexible for large deformations. Finally, we compress the mesh to tightly fit the object boundary using either masses and springs, the finite element method or an optimization approach to relax the positions of both the interior and boundary nodes. The resulting mesh is well suited for simulation since it is highly structured, has robust topological connectivity in the face of large deformations, and is readily refined if deemed necessary during subsequent simulation.

PDF (3.4MB)