3D Delaunay mesh generation

[Next]:

PARDISO, improved parallel efficiency for direct

[Up]:

Project descriptions

[Previous]:

pdelib Algorithms and software

[Contents]

[Index]

Subsections

COG

TetGen

3D Delaunay mesh generation

Collaborator: I. Schmelzer , H. Si , K. Gärtner , H. Langmach

Description:

The generation of three-dimensional boundary conforming Delaunay meshes is an essential task in the development of simulation tools for many of the projects within and without WIAS. Project works include the further development of the mesh generator COG, and the development of the open source mesh generation tool TetGen.

COG

In complex CAD and computer graphics applications, it happens that for some object a surface grid is already available but is too fine for a given application. The typical example is that a surface grid has been created for one application like computer-aided design, and we need a surface grid for another application like visualization where the rendering of a grid with too much detail would be too slow. During the year 2002, in a cooperation with I. Bremer (research group ``Nonlinear Optimization and Inverse Problems''), based on the mesh generator COG, a fully automatical algorithm for such surface grid coarsening has been developed and implemented. The basic ansatz is to create a three-dimensional grid with COG and to extract the surface grid afterwards. Furthermore, an interface of COG to the IRIS Performer library has been created in order to be able to use this algorithm in a complex visualization context.

Fig. 1: `COG`: Full (left) and reduced (right) model of a robot. The number of triangles has been reduced to the half.
$\makeatletter \@ZweiProjektbilderNocap[h]{0.45\textwidth}{kr150.eps.gz}{kr150-r.eps.gz} \makeatother$

TetGen

Starting with the year 2002, the Weierstrass Institute supports the development of the mesh generator TetGen developed by Hang Si. The source code is available from http://tetgen.berlios.de . This code is based on algorithms which essentially generalize the successful approach used in two space dimensions in the code triangle [1] to three space dimensions. The aim of this project is twofold: There are several open problems in 3D mesh generation. Algorithm development based on a well-developed mathematical understanding of the problems shall provide a sound base for more robust tools. The support of a publicly available code (corresponding to the Open Source development paradigm) is an ideal vehicle for initiating communication between research groups interested in these developments.

At the other hand, there is considerable practical interest in having a robust tool just now. Correspondingly, TetGen is being improved within many respects of stability and user-friendliness.

During 2002, project works focused on the following subjects:

A new geometry library was added to TetGen which is based on numerically stable evaluation of geometric predicates. This library largely improved the stability and robustness of TetGen.
A new structure ``tetgenio'' was added which allows input/output data directly from memory.
A program (plcview) based on the gltools library can now be used to view the input geometry (.node, .poly, and .smesh) of TetGen.
The code has been ported and debugged on several UNIX systems available at WIAS.

Fig. 2: TetGen: Constrained Delaunay tetrahedralization of the geometry of a human spine. Geometry courtesy by Hae Jung Yang, Department of Physics, Chosun University, South Korea
$\makeatletter \@ZweiProjektbilderNocap[h]{0.45\textwidth}{spine-full.eps.gz}{spine-split.eps.gz} \makeatother$

References:

SHEWCHUK, J.R., Triangle: Engineering a 2D quality mesh generator and Delaunay triangulator, in: Applied Computational Geometry: Towards Geometric Engineering, M.C. Lin, D. Manocha, eds. Springer, 1996, pp. 203-222.
SI, H., TetGen. A 3D Delaunay tetrahedral mesh generator. v.1.2 Users manual, WIAS Technical Report no. 4, 2002.