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:
- Download the source code.
- Compile the C++ code predicates.cxx and tetgen.cxx into a
"tetgen" executable.
- Remesh or decimate, triangulate, and export your surface to
ASCII .stl or Stanford .ply format, which TetGen
can read.
- Run with command line arguments:
- Generate bigger tets inside: tetgen -peqOB YOURMODEL.ply
- Generate mostly the same size everywhere: tetgen -pq1.1OB
YOURMODEL.ply
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.