Skip to main content
SpringerLink
Log in

Automatic mesh generation for complex three-dimensional regions using a constrained Delaunay triangulation

  • Published:
Engineering with Computers Aims and scope Submit manuscript

Abstract

This paper describes a method for generating tetrahedral meshes. The algorithm, based on the Delaunay triangulation, can treat objects of essentially arbitrary complexity. In order to preserve the surface triangulation of solid objects, it is necessary to override the Delaunay property and redefine the triangulation when points are introduced that are close to solid boundaries. Details of this constrained Delaunay algorithm are presented and an efficient implementation of the triangulation method is described. Techniques for controlling the distribution of mesh points and tetrahedron quality are also discussed.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Similar content being viewed by others

References

  1. Martinelli, L.; Jameson, A. (1988) Validation of a multigrid method for the Reynolds averaged equations. AIAA Paper 88-0414, January

  2. Holst T.L. (1987) Viscous transonic airfoil workshop compendium of results, AIAA Paper 87-1460, January

  3. Peterson, VL.; Ballhaus Jr., W.F. (1987) History of the aerodynamic simulation program, supercomputing in aerospace. NASA CP 2454, March

  4. Baker, T.J. (1988) Developments and trends in three dimensional mesh generation. In: Proceedings of Transonic Symposium, NASA Langley, April, also Appl. Num. Math., 5(4), 1989

  5. Mavriplis, D.; Jameson A. (1987) Multigrid solution of the two-dimensional Euler equations on unstructured triangular meshes. AIAA 25th Aerospace Sciences Meeting, Reno, AIAA Paper 87-0353, January

  6. Jameson, A.; Baker, T.J.; Weatherill, N.P. (1986) Calculation of Inviscid transonic flow over a complete aircraft, AIAA 24th aerospace sciences meeting, Reno, AIAA Paper 86-0103, January

  7. Jameson, A.; Baker, T.J. (1987) Improvements to the aircraft Euler Method. AIAA 25th Aerospace Sciences Meeting, Reno, AIAA Paper 87-0452, January

  8. Peraire, J.; Peiro, J.; Formaggia, L.; Morgan, K.; Zienkiewicz, O.C. (1988) Finite element Euler computations in three dimensions, AIAA 26th Aerospace Sciences Meeting, Reno, AIAA Paper 88-0032, January

  9. Löhner, R. (1988) Generation of three-dimensional unstructured grids by the advancing—Front method, AIAA 26th Aerospace Sciences Meeting, Reno, AIAA Paper 88-0515, January

  10. Shephard, M.S.; Guerinoni, F.; Flaherty, J.E.; Ludwig, R.A.; Baehmann, P.L. (1988) Finite octree mesh generation for automated adaptive three-dimensional flow analysis. In: Proceedings of Second International Conference on Numerical Grid Generation in Computational Fluid Mechanics, Miami, pp. 709–718, December

  11. Cavendish, J.C.; Field, D.A.; Frey, W.H. (1985) An approach to automatic three-dimensional finite element mesh generation. Int. J. Numer. Meth. Eng., 21, pp 329–347

    Article  Google Scholar 

  12. Perronnet, A. (1988) A Generator of tetrahedral finite elements for multimaterial objects or fluids. In: Proceedings of Second International Conference on Numerical Grid Generation in Computational Fluid Mechanics, Miami, pp. 719–728, December

  13. Cendes, Z.J.; Shahnasser, S.H. (1983). Magnetic field computations using Delaunay triangulation and complementary finite element methods. IEEE Trans. Magnetics, MAG-19 (6)

  14. Baker, T.J. (1987) Three dimensional mesh generation by triangulation of arbitrary point sets. AIAA 8th Computational Fluid Dynamics Conference, AIAA Paper 87-1124-CP, Hawaii, June

  15. Holmes, D.G.; Lamson, S.H. (1986) Adaptive triangular meshes for compressible flow solutions. Proceedings of First International Conference on Numerical Grid Generation in Computational Fluid Dynamics, Landshut FRG, pp. 413–424, July

  16. George, P.L.; Hecht, F.; Saltel, E. (1988) Constraint of the boundary and automatic mesh generation. In: Proceedings of Second International Conference on Numerical Grid Generation in Computational Fluid Mechanics, Miami, pp. 589–597, December

  17. Bowyer, A. (1981) Computing dirichlet tessellations. Comput. J. 24(2), 162–166

    Article  Google Scholar 

  18. Lee, D.T.; Lin, A.K. (1986) Generalized Delaunay triangulation for planar graphs. Discrete Computat. Geom. 1, 201–217

    Article  Google Scholar 

  19. Sibson, B. (1978) Locally equiangular triangulations. Comput. J. 21(3), 243–245

    Article  Google Scholar 

  20. Jackins, C.L.; Tanimoto, S.L. (1980) Octrees and their use in the representation of three-dimensional objects. Comput. Graphics Image Proc. 14, 249–270

    Google Scholar 

  21. Meagher, D. (1982) Geometric modeling using octree encoding. Comput. Graphics Image Proc., 19, 129–147

    Article  Google Scholar 

  22. Löhner, R. (1988) Some useful data structures for the generation of unstructured grids, Commun. Appl. Num. Meth. 4, 123–135

    Article  Google Scholar 

  23. Strang, G.; Fix, G.J. (1973) An analysis of the finite element method. Englewood Cliffs, NJ: Prentice-Hall

    Google Scholar 

  24. Babuška, I.; Aziz, A.K. (1976) On the angle condition in the finite element method. SIAM J. Num. Anal. 13(2), 214–226

    Article  Google Scholar 

  25. Baker, T. J. (1989) Element quality in tetrahedral meshes. In: Proceedings of Seventh International Conference on Finite Element Methods in Flow Problems, Huntsville, pp. 1018–1024, April

Download references

Author information

Authors and Affiliations

  1. Department of Mechanical and Aerospace Engineering, Princeton University, 08544, Princeton, NJ, USA

    Timothy J. Baker

Authors
  1. Timothy J. Baker
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Baker, T.J. Automatic mesh generation for complex three-dimensional regions using a constrained Delaunay triangulation. Engineering with Computers 5, 161–175 (1989). https://doi.org/10.1007/BF02274210

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF02274210

Keywords

Search

Navigation