Subsections
Collaborator: I. Schmelzer
,
H. Si
,
K. Gärtner
,
H. Langmach
Description:
The generation of threedimensional 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.
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 computeraided
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 threedimensional 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.

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 welldeveloped
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 userfriendliness.
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

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. 203222.
 SI, H.,
TetGen. A 3D Delaunay tetrahedral mesh
generator. v.1.2 Users manual,
WIAS Technical Report no. 4, 2002.
LaTeX typesetting by I. Bremer
5/16/2003