Solid Models via Tetrahedra

CS 482 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 ASCII .stl or 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("edge(%d,%d);\n", $2,$3); }' < MODEL.1.edge >> 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 Spring Model 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.

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, or just remove the element from your list.