Sometimes we want to divide a space (delimited by a polygon / polyhedral representation) into triangles. This is useful for calculations inside a body such as stress in elastic / breaking simulations and also fluid simulation. There are many ways to to do this. Delaunay is optimal since avoids “skinny triangles”. Algorithms to create Delaunay triangulations include: Flip method, incremental, divide and conquer, and sweepline. For 3D triangle construction from a isosurface input, “isosurface stuffing” (Labelle, SIGGRAPH 2007) can be used:
“The isosurface stuffing algorithm by Labelle and Shewchuk produces a well-conditioned mesh by snapping some vertices to the triangulated surface and refining others using a precomputed stencil”.
Useful when higher resolution is desired near the surface.
Some useful triangulation code:
Triangle
http://www.compgeom.com/~piyush/scripts/triangle/index.html
(in 2D!)
Pyramid
3D version of Triangle but maybe it is not available?
Qhull
http://www.qhull.org/
CGAL
http://www.cgal.org/Manual/last/doc_html/cgal_manual/packages.html#Pkg:Triangulation3
LEDA
http://www.algorithmic-solutions.com/leda/ledar/index.htm
