Volume Meshing and Simulation with Tetrahedra

CS 493 Lecture, Dr. Lawlor

To simulate a solid, you need a solid mesh, not just triangles.  In 2D, you can use the Delaunay triangulation to make a good triangle mesh from scattered points.  TetGen can build a tetrahedral mesh using the 3D version of this, the Delaunay tetrahedralization. 

To use TetGen:
  1. Download the source code.
  2. Compile the C++ code predicates.cxx and tetgen.cxx into a "tetgen" executable.
  3. Remesh or decimate, triangulate, and export your surface to Stanford .ply format, which TetGen can read.
  4. Run with command line arguments:
This will dump the XYZ vertex/node locations (including interior nodes) to MODEL.1.node, the node numbers for each tetrahedron to MODEL.1.ele, and the renumbered surface mesh to MODEL.1.face.  I crudely converted these to javascript function calls with these UNIX awk commands, and some hand editing on the first and last lines; it'd be cleaner to read them directly from JavaScript (via XMLHttpRequest) or convert them in C++.
	awk '{printf("vertex(%.3f,%.3f,%.3f);\n",  $2,$3,$4); }' < MODEL.1.node > model.js
	awk '{printf("tet(%d,%d,%d,%d);\n",  $2,$3,$4,$5); }' < MODEL.1.ele >> model.js
	awk '{printf("face(%d,%d,%d);\n",  $2,$3,$4); }' < MODEL.1.face >> model.js
   Play with the 3D Tet Mesh Demo

Be aware that many surface modeling programs, including Blender, can produce fairly spiky narrow triangles, which results in spiky narrow tetrahedra.  These are fine for rendering, but don't always work well for simulation, where the numerics work better for larger angles.  You can get better-shaped triangles by remeshing the surface (in Blender, Add Modifier -> Geometry -> Remesh), which internally uses a "marching cubes" type volumetric re-subdivision of the mesh, at a selectable resolution.  After applying, enter Edit Mode, select all, and triangulate with Mesh -> Faces -> Quads to Tris.

Given a tet mesh, you can construct springs along each edge (every pair of vertices is connected with an edge, so this is easy).  In fact, typically the same indexed vertex scheme used for faces is extended for tets.  You can even use the same single vertex list, and index into it from an array of tets for simulation, and then index into it from an array of faces for rendering.  There might be a few interior vertices used only for simulation, but the graphics card is fine with this.

Springs work fine to make tets appear rigid in 3D, unlike cubes, which collapse when made from springs.  However, if a tet gets pushed inside out, it tends to stay inverted rather than snapping back.  Back in 2004, Iriving, Teran, and Fedkiw showed how to support fully invertible finite elements--the key trick being to create and invert a "body matrix" for each tet when you load the mesh.  This lets them do huge deformations like squashing meshes between gears, although the computations involve fairly expensive matrix operations like diagonalization and eigendecomposition for every tet at every timestep.  Recent research in this area has added support for complete merge/split topological changes, like splatting goo meshes (2009).

It is fairly simple to allow springs to "break" if they are stretched too far; you just measure the current displacement, and if it's more than some threshold, you mark the element as broken, so it applies no forces.