“Isosurface stuffing: fast tetrahedral meshes with good dihedral angles” by Labelle and Shewchuk

The isosurface stuffing algorithm fills an isosurface with a uniformly sized tetrahedral mesh whose dihedral angles are bounded between 10.7° and 164.8°, or (with a change in parameters) between 8.9° and 158.8°. The algorithm is whip fast, numerically robust, and easy to implement because, like Marching Cubes, it generates tetrahedra from a small set of precomputed stencils. A variant of the algorithm creates a mesh with internal grading: on the boundary, where high resolution is generally desired, the elements are fine and uniformly sized, and in the interior they may be coarser and vary in size. This combination of features makes isosurface stuffing a powerful tool for dynamic fluid simulation, large-deformation mechanics, and applications that require interactive remeshing or use objects defined by smooth implicit surfaces. It is the first algorithm that rigorously guarantees the suitability of tetrahedra for finite element methods in domains whose shapes are substantially more challenging than boxes. Our angle bounds are guaranteed by a computer-assisted proof. If the isosurface is a smooth 2-manifold with bounded curvature, and the tetrahedra are sufficiently small, then the boundary of the mesh is guaranteed to be a geometrically and topologically accurate approximation of the isosurface.

1. Alliez, P., Cohen-Steiner, D., Yvinec, M., and Desbrun, M. 2005. Variational Tetrahedral Meshing. ACM Transactions on Graphics 24, 3, 617–625. Special issue on Proceedings of SIGGRAPH 2005. Google ScholarDigital Library
2. Amenta, N., and Bern, M. 1999. Surface Reconstruction by Voronoi Filtering. Discrete & Computational Geometry 22, 4 (Dec.), 481–504.Google Scholar
3. Amenta, N., Choi, S., Dey, T. K., and Leekha, N. 2002. A Simple Algorithm for Homeomorphic Surface Reconstruction. International Journal of Computational Geometry and Applications 12, 1-2, 125–141.Google ScholarCross Ref
4. Bærentzen, J. A., and Aanæs, H. 2002. Generating Signed Distance Fields from Triangle Meshes. Tech. Rep. IMM-TR-2002-21, Informatics and Mathematical Modelling, Technical University of Denmark, Lyngby, Denmark.Google Scholar
5. Baker, B. S., Grosse, E., and Rafferty, C. S. 1988. Nonobtuse Triangulation of Polygons. Discrete and Computational Geometry 3, 2, 147–168. Google ScholarDigital Library
6. Bank, R. E., and Scott, L., R. 1989. On the Conditioning of Finite Element Equations with Highly Refined Meshes. SIAM Journal on Numerical Analysis 26, 6 (Dec.), 1383–1394. Google ScholarDigital Library
7. Bern, M., Eppstein, D., and Gilbert, J. R. 1994. Provably Good Mesh Generation. Journal of Computer and System Sciences 48, 3 (June), 384–409. Google ScholarDigital Library
8. Bey, J. 1995. Tetrahedral Grid Refinement. Computing 55, 355–378. Google ScholarDigital Library
9. Bloomenthal, J. 1994. An Implicit Surface Polygonizer. In Graphics Gems IV. Academic Press, ch. IV.8. 324–349. Google ScholarDigital Library
10. Cheng, S.-W., and Dey, T. K. 2002. Quality Meshing with Weighted Delaunay Refinement. In Proceedings of the Thirteenth Annual Symposium on Discrete Algorithms, 137–146. Google ScholarDigital Library
11. Cheng, S.-W., Dey, T. K., Edelsbrunner, H., Facello, M. A., and Teng, S.-H. 2000. Sliver Exudation. Journal of the ACM 47, 5 (Sept.), 883–904. Google ScholarDigital Library
12. Chew, L. P. 1989. Guaranteed-Quality Triangular Meshes. Tech. Rep. TR-89-983, Department of Computer Science, Cornell University.Google Scholar
13. Chew, L. P. 1997. Guaranteed-Quality Delaunay Meshing in 3D. In Proceedings of the Thirteenth Annual Symposium on Computational Geometry, 391–393. Google ScholarDigital Library
14. Edelsbrunner, H., and Guoy, D. 2001. An Experimental Study of Sliver Exudation. In Tenth International Meshing Roundtable, 307–316.Google Scholar
15. Eppstein, D., Sullivan, J. M., and Üngör, A. 2004. Tiling Space and Slabs with Acute Tetrahedra. Computational Geometry: Theory and Applications 27, 3 (Mar.), 237–255. Google ScholarDigital Library
16. Freitag, L. A., and Ollivier-Gooch, C. 1997. Tetrahedral Mesh Improvement Using Swapping and Smoothing. International Journal for Numerical Methods in Engineering 40, 21 (Nov.), 3979–4002.Google ScholarCross Ref
17. Fuchs, A. 1998. Automatic Grid Generation with Almost Regular Delaunay Tetrahedra. In Seventh International Meshing Roundtable, 133–148.Google Scholar
18. Jamet, P. 1976. Estimations d’Erreur pour des Élements Finis Droits Presque Dégénérés. RAIRO Analyse Numérique 10, 43–61.Google Scholar
19. Křížek, M. 1992. On the Maximum Angle Condition for Linear Tetrahedral Elements. SIAM Journal on Numerical Analysis 29, 2 (Apr.), 513–520. Google ScholarDigital Library
20. Labelle, F. 2006. Sliver Removal by Lattice Refinement. In Proceedings of the Twenty-Second Annual Symposium on Computational Geometry, 347–356. Google ScholarDigital Library
21. Li, X.-Y., and Teng, S.-H. 2001. Generating Well-Shaped Delaunay Meshes in 3D. In Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, 28–37. Google ScholarDigital Library
22. Lorensen, W. E., and Cline, H. E. 1987. Marching Cubes: A High Resolution 3D Surface Construction Algorithm. In Computer Graphics (SIGGRAPH ’87 Proceedings), 163–170. Google ScholarDigital Library
23. Mitchell, S. A., and Vavasis, S. A. 2000. Quality Mesh Generation in Higher Dimensions. SIAM Journal on Computing 29, 4, 1334–1370. Google ScholarDigital Library
24. Molino, N., Bridson, R., Teran, J., and Fedkiw, R. 2003. A Crystalline, Red Green Strategy for Meshing Highly Deformable Objects with Tetrahedra. In Twelfth International Meshing Roundtable, 103–114.Google Scholar
25. Naylor, D. J. 1999. Filling Space with Tetrahedra. International Journal for Numerical Methods in Engineering 44, 10 (Apr.), 1383–1395.Google ScholarCross Ref
26. Ohtake, Y., Belyaev, A., Alexa, M., Turk, G., and Seidel, H.-P. 2003. Multi-Level Partition of Unity Implicits. ACM Transactions on Graphics 22, 3 (July), 463–470. Special issue on Proceedings of SIGGRAPH 2003. Google ScholarDigital Library
27. Osher, S., and Fedkiw, R. 2002. Level Set Methods and Dynamic Implicit Surfaces. Springer-Verlag, New York.Google Scholar
28. Oudot, S., Rineau, L., and Yvinec, M. 2005. Meshing Volumes Bounded by Smooth Surfaces. In Proceedings of the 14th International Meshing Roundtable, 203–219.Google Scholar
29. Sethian, J. A. 1996. A Fast Marching Level Set Method for Monotonically Advancing Fronts. Proceedings of the National Academy of Sciences 93, 4 (Feb.), 1591–1595.Google ScholarCross Ref
30. Shen, C., O’Brien, J. F., and Shewchuk, J. R. 2004. Interpolating and Approximating Implicit Surfaces from Polygon Soup. ACM Transactions on Graphics 23, 3 (Aug.), 896–904. Special issue on Proceedings of SIGGRAPH 2004. Google ScholarDigital Library
31. Shewchuk, J. R. 2002. What Is a Good Linear Element? Interpolation, Conditioning, and Quality Measures. In Eleventh International Meshing Roundtable, 115–126.Google Scholar
32. Sommerville, D. M. Y. 1923. Space-Filling Tetrahedra in Euclidean Space. Proceedings of the Edinburgh Mathematical Society 41, 49–57.Google ScholarCross Ref
33. Yerry, M. A., and Shephard, M. S. 1984. Automatic Three-Dimensional Mesh Generation by the Modified-Octree Technique. International Journal for Numerical Methods in Engineering 20, 11 (Nov.), 1965–1990.Google ScholarCross Ref
34. Zhao, H.-K., Osher, S., and Fedkiw, R. 2001. Fast Surface Reconstruction Using the Level Set Method. In Workshop on Variational and Level Set Methods, 194–202. Google ScholarDigital Library