Boundary enforcement by facet splits in Delaunay based mesh generation.

Numerical Grid Generation in Computational Field Simulations, The International Society of Grid Generation, pp.203-221, September 2000

MESHING
RESEARCH
CORNER

P. L. George
INRIA, Gamma Project,Domaine de Voluceau, Rocquencourt,
BP 105, 78153 Le Chesnay Cedex, France.
email: paul-louis.george@inria.fr

S. H. Lo
The University of HongKong, HongKong (visiting professor to INRIA, Gamma Project).
email: hreclsh@hkucc.hku.hk

Abstract

Issues related to triangulating an arbitrary polyhedron are addressed. Given a boundary surface mesh (a set of triangular facets), a Delaunay triangulation of the corresponding mesh vertices does not in general include all these given boundary facets. This question is the main difficulty in such methods and is reported to be N P -complete. A robust algorithm to triangulate a general polyhedron is proposed which consists of recovering the missing boundary facets by means of facet partitioning using straightforward local operators. The additional points defining these partitions are the intersection between the Delaunay triangulation of the vertices of the polyhedron and the missing facets. Our method solves the difficult problem of triangulating an arbitrary polyhedron if points are allowed to be introduced on the surface mesh so as to split the initial facets. Examples are given to show the efficiency of the method.