Three-dimensional conforming Delaunay mesh generation

[Next]:

PARDISO, improvements for symmetric indefinite linear

[Up]:

Projects

[Previous]:

Process simulation in gas turbine engineering

[Contents]

[Index]

Subsections

Three-dimensional conforming Delaunay mesh generation

Collaborator: H. Si, J. Fuhrmann, K. Gärtner

Description:

Mesh generation is one of the crucial points for many applications of numerical methods to real-world problems. Delaunay meshes have many optimal mathematical properties which are favorite for finite element and finite volume methods. Automatically generating conforming Delaunay meshes from arbitrary 3D geometries is a problem far from having been solved in computational geometry. Our work focuses on both theoretical and practical aspects of this problem. Algorithms are needed to generate Delaunay meshes. We are developing provable and efficient algorithms. On the other hand, the program TetGen for computing 3D Delaunay meshes is continuously developing and has been improved significantly. In the year 2004, a new algorithm [1] for generating constrained Delaunay tetrahedralization has been developed and implemented. A new version (v 1.3) of TetGen [2] with many new features was released.

Constrained Delaunay tetrahedralizations

A fundamental problem in mesh generation is to decompose a 3D domain $\Omega$ into tetrahedra which should respect the boundary $\Gamma$ of $\Omega$ . Constrained Delaunay tetrahedralizations (CDTs) are variations of the Delaunay tetrahedralizations which are perfect structures for the problem. Furthermore, they are essential for getting the conforming Delaunay meshes. We have developed an algorithm [1] for triangulating any piecewise linear complex (PLC) into a CDT. It has two advantages over other available methods: (1) it efficiently explores the available locally geometrical information to construct the Steiner points, hence it uses less additional points, and the creation of unnecessarily short edges can be avoided; and (2) it handles small input angles automatically, there is no need to preprocess sharp corners. This algorithm has been implemented in our 3D Delaunay mesh generator TetGen [2]. The implementation shows that this algorithm can be made robust and efficient. Moreover, there is no restriction on the size and complexity of the input geometries. Two examples with complicated geometrical shapes are shown in Figure 1.

**Fig. 1:** Examples of constrained Delaunay tetrahedralizations. Left: A CAD model of a mechanical part. The surface mesh has 57270 nodes, 114680 triangles. Right: A computer- reconstructed model of the statue of a happy buddha. It has 31881 nodes, 65561 triangles.
$\makeatletter \@ZweiProjektbilderNocap[h]{0.37\textwidth}{engine-plc1.eps}{happy1-plc.eps} \makeatother$

TetGen Version 1.3

TetGen is a 3D tetrahedral mesh generator. It generates exact Delaunay tetrahedralizations, constrained Delaunay tetrahedralizations, and quality conforming Delaunay meshes. TetGen is written in C++ and includes a suite of state-of-the-art algorithms. It can be compiled into an executable program or a library which can be integrated into other applications. The code is highly portable and has been successfully compiled and tested on all major operating systems, e.g., Unix/Linux, MacOS, Windows, etc. It is publicly available for non-commercial use at http://tetgen.berlios.de.

Version 1.3 introduced some re-design. The year 2004 was focused on enhancing the ability to mesh geometries with arbitrarily complicated shapes. Version 1.3 includes our new constrained Delaunay tetrahedralization algorithm [1] and many other useful features such as refining pre-generated meshes, automatically detecting incorrect inputs, and so on.

Figure 2 is an example created by pdelib2: Adaptive mesh generation for a heat conduction problem. The pictures show a sequence of meshes refined by using the -i switch and the corresponding solutions.

$\begin{figure}\makeatletter \@DreiProjektbilderNocap[h]{0.25\textwidth}{grid_00023.eps}{grid_00055.eps}{grid_00090.eps} \makeatother \end{figure}$

**Fig. 2:** Examples of adaptive mesh refinement by TetGen (use -i switch). The grid is coarse and refined again in some regions corresponding to the moving hot spot.
$\makeatletter \@DreiProjektbilderNocap[h]{0.25\textwidth}{sol_00023.eps}{sol_00055.eps}{sol_00090.eps} \makeatother$

References:

H. SI, K. GÄRTNER, An algorithm for three-dimensional constrained Delaunay tetrahedralizations, in: Proceedings of the Forth International Conference on Engineering Computational Technology, B. Toppings, C.M. Soares, eds., Civil-Comp Press, Stirling, 2004, p. 16. ISBN 0-948749-97-0 CD-ROM.
H. SI, TetGen, a quality tetrahedral mesh generator and three-dimensional Delaunay triangulator, v1.3, WIAS Technical Report no. 9, 2004 .