Computational & Technology Resources
an online resource for computational,
engineering & technology publications
Civil-Comp Proceedings
ISSN 1759-3433
CCP: 91
PROCEEDINGS OF THE TWELFTH INTERNATIONAL CONFERENCE ON CIVIL, STRUCTURAL AND ENVIRONMENTAL ENGINEERING COMPUTING
Edited by: B.H.V. Topping, L.F. Costa Neves and R.C. Barros
Paper 281

Generation of Delaunay Meshes

D. Krybus and B. Patzák

Department of Mechanics, Faculty of Civil Engineering, Czech Technical University in Prague, Czech Republic

Full Bibliographic Reference for this paper
, "Generation of Delaunay Meshes", in B.H.V. Topping, L.F. Costa Neves, R.C. Barros, (Editors), "Proceedings of the Twelfth International Conference on Civil, Structural and Environmental Engineering Computing", Civil-Comp Press, Stirlingshire, UK, Paper 281, 2009. doi:10.4203/ccp.91.281
Keywords: Delaunay triangulation, mesh generation, alpha shape, Lagrangian formulation, fluid-structure interaction, finite element method.

Summary
This paper deals with the description and implementation of algorithms used for a construction of a finite element mesh. First, the requirements for a fluid-structure interaction (FSI) are summarized and discussed. In particular, the particle finite element method (PFEM) [1] is considered. This method is based on a Lagrangian formulation. Compared to traditional approaches, convective terms are not present in the characteristic equations. In the PFEM nodes can be viewed as particles which can freely move and even separate from the main domain. The finite element mesh must be rebuilt in order to avoid numerical instabilities as a consequence of large distortions. The FSI problem, as such, is solved in a standard way by employing a stabilized finite element method necessary to handle the incompressibility condition.

Delaunay triangulation [2] was chosen as a suitable meshing method. It triangulates a given point set on the basis of satisfying the empty circumscribed circle property. The triangulation leads to a quite numerically stable mesh and can by simply extended to a three-dimensional space.

Described triangulation was implemented using incremental Bowyer-Watson algorithm [3,4]. It consists of sequentially adding new points in the current triangulation. After the new point is inserted, each triangle is checked, if the Delaunay empty circumscribed circle property is violated. Affected triangles are removed from the triangulation and the empty space is retriangulated.

One of disadvantages is a possible round-off error. In such case the standard Delaunay-based algorithm will produce elements, which could cause numerical difficulties. Extension of the basic algorithm considers the case, when more than three nodes can lie on a same circumscribed circle and avoids the generation of skewed triangles by allowing the general polygonal shape element.

The particle finite element method presented above offers an extension of the finite element package OOFEM [5] in order to enable FSI-analysis. Delaunay triangulation represents the first step of solving coupled fluid-structure interaction problems by using OOFEM. A simple C++ code was programmed by the authors for the development and primary testing of the algorithm in two dimensions. Triangulation of a small point set is illustrated on several examples.

References
1
E. Oñate, S.R. Idelsohn, F. Del Pin, R. Aubry, "The particle finite element method. An overview", International Journal of Computational Method, 1, 267-307, 2007.
2
B. Delaunay, "Sur la sphére vide", Izvestia Akademii Nauk SSSR, Otdelenie Matematicheskikh i Estestvennykh Nauk, 7:793-800, 1934.
3
A. Bowyer, "Computing Dirichlet tessellations", The Computer Journal, 24, 162-166, 1981. doi:10.1093/comjnl/24.2.162
4
D.F. Watson, "Computing the n-dimensional Delaunay tessellation with application to Voronoi polytopes", The Computer Journal, 24, 167-172, 1981. doi:0.1093/comjnl/24.2.167
5
B. Patzák, "OOFEM project homepage", http://www.oofem.org, 2000.

purchase the full-text of this paper (price £20)

go to the previous paper
go to the next paper
return to the table of contents
return to the book description
purchase this book (price £140 +P&P)