Simplification and improvement of tetrahedral models for simulation

ABSTRACT

Most 3D mesh generation techniques require simplification and mesh improvement stages to prepare a tetrahedral model for efficient simulation. We have developed an algorithm that both reduces the number of tetrahedra in the model to permit interactive manipulation and removes the most poorly shaped tetrahedra to allow for stable physical simulations such as the finite element method. The initial tetrahedral model may be composed of several different materials representing internal structures. Our approach targets the elimination of poorly-shaped elements while simplifying the model using edge collapses and other mesh operations, such as vertex smoothing, tetrahedral swaps, and vertex addition. We present the results of our algorithm on a variety of inputs, including models with more than a million tetrahedra. In practice, our algorithm reliably reduces meshes to contain only tetrahedra that meet specified shape requirements, such as the minimum solid angle.

REFERENCES

• 1: A. Adler. On the bisection method for triangles. Mathematics of Computation, 40(162):571--574, April 1983.
• 2: Douglas N. Arnold , Arup Mukherjee , Luc Pouly, Locally Adapted Tetrahedral Meshes Using Bisection, SIAM Journal on Scientific Computing, v.22 n.2, p.431-448, 2000 [doi>10.1137/S1064827597323373]
• 3: I. Babuska and A. Aziz. On the angle condition in the finite element method. SIAM Journal of Numerical Analysis, 13(2):214--226, 1976.
• 4: T. J. Baker. Automatic mesh generation for complex three-dimensional regions using a constrained delaunay triangulation. Engineering with Computers, (5):161--175, 1989.
• 5: R. E. Bank, A. H. Sherman, and A. Weiser. Some refinement algorithms and data structures for regular local mesh refinement. pages 3--17, 1983.
• 6: R. E. Bank and J. Xu. An algorithm for coarsening unstructured meshes. Numerische Mathematik, 73(1):1--36, 1996.
• 7: J. Bey, Tetrahedral grid refinement, Computing, v.55 n.4, p.355-378, 1995 [doi>10.1007/BF02238487]
• 8: P. R. Cavalcanti and U. T. Mello. Three-dimensional constrained delaunay triangulation: a minimalist approach. In Proceedings of the 8th International Meshing Roundtable, pages 119--129, 1999.
• 9: Y.-J. Chiang and X. Lu. Progressive simplification of tetrahedral meshes preserving all isosurface topologies. Computer Graphics Forum, 22(1):493--504, 2003.
• 10: Prashant Chopra , Joerg Meyer, TetFusion: an algorithm for rapid tetrahedral mesh simplification, Proceedings of the conference on Visualization '02, October 27-November 01, 2002, Boston, Massachusetts
• 11: P. Cignoni , D. Constanza , C. Montani , C. Rocchini , R. Scopigno, Simplification of Tetrahedral meshes with accurate error evaluation, Proceedings of the conference on Visualization '00, p.85-92, October 2000, Salt Lake City, Utah, United States
• 12: Barbara M. Cutler , Julie Dorsey , Leonard Mcmillan, Procedural authoring of solid models, 2003
• 13: Barbara Cutler , Julie Dorsey , Leonard McMillan , Matthias Müller , Robert Jagnow, A procedural approach to authoring solid models, ACM Transactions on Graphics (TOG), v.21 n.3, July 2002
• 14: T. K. Dey, H. Edelsbrunner, S. Guha, and D. V. Nekhayev. Topology preserving edge contraction. Publ. Inst. Math. (Beograd) (N.S.), 66:23--45, 1999.
• 15: H. Edelsbrunner and D. Guoy. An experimental study of sliver exudation. Engineering With Computers, Special Issue on 'Mesh Generation' (10th IMR 2001), 18(3):229--240, 2002.
• 16: L. Freitag and C. Ollivier-Gooch. Tetrahedral mesh improvement using swapping and smoothing. International Journal for Numerical Methods in Engineering, 40:3979--4002, 1997.
• 17: W. H. Frey and D. Field. Mesh relaxation: A new technique for improving triangulations. International Journal for Numerical Methods in Engineering, 31(6): 1121--1133, 1991.
• 18: Sarah F. Frisken , Ronald N. Perry , Alyn P. Rockwood , Thouis R. Jones, Adaptively sampled distance fields: a general representation of shape for computer graphics, Proceedings of the 27th annual conference on Computer graphics and interactive techniques, p.249-254, July 2000 [doi>10.1145/344779.344899]
• 19: F. Ganovelli and C. O'Sullivan. Animating cuts with on-the-fly re-meshing. In Eurographics 2001 - short presentations, pages 243--247, 2001.
• 20: Michael Garland , Paul S. Heckbert, Surface simplification using quadric error metrics, Proceedings of the 24th annual conference on Computer graphics and interactive techniques, p.209-216, August 1997 [doi>10.1145/258734.258849]
• 21: Igor Guskov , Zoë J. Wood, Topological noise removal, No description on Graphics interface 2001, p.19-26, June 07-09, 2001, Ottawa, Ontario, Canada
• 22: Hugues Hoppe, Progressive meshes, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.99-108, August 1996 [doi>10.1145/237170.237216]
• 23: Hugues Hoppe , Tony DeRose , Tom Duchamp , John McDonald , Werner Stuetzle, Mesh optimization, Proceedings of the 20th annual conference on Computer graphics and interactive techniques, p.19-26, September 1993 [doi>10.1145/166117.166119]
• 24: Barry Joe, Construction of three-dimensional improved-quality triangulations using local transformations, SIAM Journal on Scientific Computing, v.16 n.6, p.1292-1307, Nov. 1995 [doi>10.1137/0916075]
• 25: Tao Ju , Frank Losasso , Scott Schaefer , Joe Warren, Dual contouring of hermite data, Proceedings of the 29th annual conference on Computer graphics and interactive techniques, July 23-26, 2002, San Antonio, Texas
• 26: Michal Křížek, On the maximum angle condition for linear tetrahedral elements, SIAM Journal on Numerical Analysis, v.29 n.2, p.513-520, April 1992 [doi>10.1137/0729031]
• 27: Peter Lindstrom , Greg Turk, Fast and memory efficient polygonal simplification, Proceedings of the conference on Visualization '98, p.279-286, October 18-23, 1998, Research Triangle Park, North Carolina, United States
• 28: A. Liu and B. Joe. Relationship between tetrahedron shape measures. BIT, 34:268--287, 1994.
• 29: Anwei Liu , Barry Joe, Quality local refinement of tetrahedral meshes based on bisection, SIAM Journal on Scientific Computing, v.16 n.6, p.1269-1291, Nov. 1995 [doi>10.1137/0916074]
• 30: R. Lohner. Generation of three-dimensional unstructured grids by the advancing front method. In International Journal for Numerical Methods in Fluids, volume 8, pages 1135--1149, 1988.
• 31: Joseph M. Maubach, Local bisection refinement for N-simplicial grids generated by reflection, SIAM Journal on Scientific Computing, v.16 n.1, p.210-227, Jan. 1995 [doi>10.1137/0916014]
• 32: Gary L. Miller , Dafna Talmor , Shang-Hua Teng, Optimal good-aspect-ratio coarsening for unstructured meshes, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.538-547, January 05-07, 1997, New Orleans, Louisiana, United States
• 33: Matthias Müller , Leonard McMillan , Julie Dorsey , Robert Jagnow, Real-time simulation of deformation and fracture of stiff materials, Proceedings of the Eurographic workshop on Computer animation and simulation, p.113-124, September 02-03, 2001, Manchester, UK
• 34: Matthias Müller , Julie Dorsey , Leonard McMillan , Robert Jagnow , Barbara Cutler, Stable real-time deformations, Proceedings of the 2002 ACM SIGGRAPH/Eurographics symposium on Computer animation, July 21-22, 2002, San Antonio, Texas [doi>10.1145/545261.545269]
• 35: Vijay Natarajan , Herbert Edelsbrunner, Simplification of Three-Dimensional Density Maps, IEEE Transactions on Visualization and Computer Graphics, v.10 n.5, p.587-597, September 2004 [doi>10.1109/TVCG.2004.32]
• 36: Gregory M. Nielson , Junwon Sung, Interval volume tetrahedrization, Proceedings of the 8th conference on Visualization '97, p.221-ff., October 18-24, 1997, Phoenix, Arizona, United States
• 37: S. J. Owen. A survey of unstructured mesh generation technology. In 7th International Meshing Roundtable, pages 239--267, 1998. http://www.andrew.cmu.edu/user/sowen/softsurv.html.
• 38: S. Pirzadeh. Three-dimensional unstructured viscous grids by the advancing-layers method. 34(1):43--49, January 1996.
• 39: M.-C. Rivara and C. Levin. A 3-D refinement algorithm suitable for adaptive and multi-grid techniques. Communications in Applied Numerical Methods, 8:281--290, 1992.
• 40: William J. Schroeder , Jonathan A. Zarge , William E. Lorensen, Decimation of triangle meshes, ACM SIGGRAPH Computer Graphics, v.26 n.2, p.65-70, July 1992
• 41: Jonathan Richard Shewchuk , Gary L. Miller , David R. O'Hallaron, Delaunay refinement mesh generation, 1997
• 42: Oliver G. Staadt , Markus H. Gross, Progressive tetrahedralizations, Proceedings of the conference on Visualization '98, p.397-402, October 18-23, 1998, Research Triangle Park, North Carolina, United States
• 43: Issac J. Trotts , Bernd Hamann , Kenneth I. Joy , David F. Wiley, Simplification of tetrahedral meshes, Proceedings of the conference on Visualization '98, p.287-295, October 18-23, 1998, Research Triangle Park, North Carolina, United States
• 44: M. A. Yerry and M. S. Shephard. Automatic three-dimensional mesh generation by the modified octree technique. International Journal For Numerical Methods in Engineering, (20):1965--1990, 1984.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling