Search

SUMMARY A new constrained boundary recovery method for three dimensional Delaunay triangulations is presented. It successfully resolves the difficulties related to the minimal addition of Steiner points and their good placement. Applications to full mesh generation are discussed and numerical examples are provided to illustrate the effectiveness of guaranteed recovery procedure. Copyright 2004 John Wiley & Sons, Ltd.

The centroidal Voronoi tessellation based Delaunay triangulation (CVDT) provides an optimal distribution of generating points with respect to a given density function and accordingly generates a high-quality mesh. In this paper, we discuss algorithms for the construction of the constrained CVDT from an initial Delaunay tetrahedral mesh of a three-dimensional domain. By establishing an appropriate relationship between the density function and the specified sizing field and applying the Lloyd's iteration, the constrained CVDT mesh is obtained as a natural global optimization of the initial mesh. Simple local operations such as edges/faces flippings are also used to further improve the CVDT mesh. Several complex meshing examples and their element quality statistics are presented to demonstrate the effectiveness and efficiency of the proposed mesh generation and optimization method. Copyright © 2003 John Wiley & Sons, Ltd.

Given a boundary surface mesh (a set of triangular facets) of a polyhedron, the problem of deciding whether or not a triangulation exists is reported to be NP-hard. In this paper, an algorithm to triangulate a general polyhedron is presented which makes use of a classical Delaunay triangulation algorithm, a phase for recovering the missing boundary facets by means of facet partitioning, and a final phase that makes it possible to remove the additional points defined in the previous step. Following this phase, the resulting mesh conforms to the given boundary surface mesh. The proposed method results in a discussion of theoretical interest about existence and complexity issues. In practice, however, the method should provide what we call ‘ultimate’ robustness in mesh generation methods. Copyright © 2003 John Wiley & Sons, Ltd.

We describe an algorithm which generates tetrahedral decomposition of a general solid body, whose surface is given as a collection of triangular facets. The principal idea is to modify the constraints in such a way as to make them appear in an unconstrained triangulation of the vertex set apriori. The vertex set positions are randomized to guarantee existence of a unique triangulation which satisfies the Delaunay empty-sphere property. (Algorithms for robust, parallelized construction of such triangulations are available.) In order to make the boundary of the solid appear as a collection of tetrahedral faces, we iterate two operations, edge flip and edge split with the insertion of additional vertex, until all of the boundary facets are present in the tetrahedral mesh. The outcome of the vertex insertion is another triangulation of the input surfaces, but one which is represented as a subset of the tetrahedral faces. To determine if a constraining facet is present in the unconstrained Delaunay triangulation of the current vertex set, we use the results of Rajan which re-formulate Delaunay triangulation as a linear programming problem.

In this paper we discuss, study and compare two linear algorithms for the triangulation refinement problem: the known longest-side (triangle bisection) refinement algorithm, as well as a new algorithm that uses longest side bisection techniques for refining Delaunay triangulations. We show that the automatic point insertion criterion, taken from the fractal property of optimal (linear) longest-side bisection algorithms, assures the construction of good quality Delaunay triangulations in linear time. Numerical evidence, showing that the practical behaviour of the new algorithm is in complete agreement with the theory, is included. © 1997 by John Wiley & Sons, Ltd.

A simple and robust boundary triangulation algorithm is proposed and, based on it, completely automatic Delaunay mesh generation procedures are developed. The algorithm is equally applicable to convex, non-convex and multiply connected planar domains. In this approach, given the nodes, the number of triangles formed is precisely known and any desired control over mesh generation is possible.

The paper describes the development of an automated triangulation algorithm for arbitrary domains. The method involves octree decomposition and subdomain meshing using Delaunay triangulation. Extension to three dimensional objects involving curved boundary surfaces is briefly described.

The Delaunay triangulation has been used in several methods for generating finite element tetrahedral meshes in three-dimensional polyhedral regions. Other types of three-dimensional triangulations are possible, such as a triangulation satisfying a local max-min solid angle criterion. In this paper, we present experimental results to show that max-min solid angle triangulations are better than Delaunay triangulations for finite element tetrahedral meshes, since the former type of triangulations contains tetrahedra of better shape than the latter type. We also describe how mesh points are generated and triangulated in our tetrahedral mesh generation method.

One approach to fully automatic mesh generation in two and three dimensions is to generate and triangulate a set of points within and on the boundary of a geometry using the properties of the Delaunay triangulation. Because the point data generate mesh topology of greater dimension, it is necessary to insure topological compatibility and perform classification of the resulting mesh with respect to the original geometry. Necessary and sufficient conditions for classification of mesh topology on three-dimensional planar geometry are given, as well as a discussion of the more complex case of curved geometry. This paper also presents conditions to insure topological compatibility along with techniques for identifying and resolving cases of incompatibility.

This paper investigates the possibility of integrating the two currently most popular mesh generation techniques, namely the method of advancing front and the Delaunay triangulation algorithm. The merits of the resulting scheme are its simplicity, efficiency and versatility. With the introduction of ‘non-Delaunay’ line segments, the concept of using Delaunay triangulation as a means of mesh generation is clarified. An efficient algorithm is proposed for the construction of Delaunay triangulations over non-convex planar domains. Interior nodes are first generated within the planar domain. These interior nodes and the boundary nodes are then linked up together to produce a valid triangulation. In the mesh generation process, the Delaunay property of each triangle is ensured by selecting a node having the smallest associated circumcircle. In contrast to convex domains, intersection between the proposed triangle and the domain boundary has to be checked; this can be simply done by considering only the ‘non-Delaunay’ segments on the generation front. Through the study of numerous examples of various characteristics, it is found that high-quality triangular element meshes are obtained by the proposed algorithm, and the mesh generation time bears a linear relationship with the number of elements/nodes of the triangulation.