Tetrahedral mesh generation and optimization based on centroidal Voronoi tessellations

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.     

Q‐Morph: an indirect approach to advancing front quad meshing

Q‐Morph is a new algorithm for generating all‐quadrilateral meshes on bounded three‐dimensional surfaces. After first triangulating the surface, the triangles are systematically transformed to create an all‐quadrilateral mesh. An advancing front algorithm determines the sequence of triangle transformations. Quadrilaterals are formed by using existing edges in the triangulation, by inserting additional nodes, or by performing local transformations to the triangles. A method typically used for recovering the boundary of a Delaunay mesh is used on interior triangles to recover quadrilateral edges. Any number of triangles may be merged to form a single quadrilateral. Topological clean‐up and smoothing are used to improve final element quality. Q‐Morph generates well‐aligned rows of quadrilaterals parallel to the boundary of the domain while maintaining a limited number of irregular internal nodes. The proposed method also offers the advantage of avoiding expensive intersection calculations commonly associated with advancing front procedures. A series of examples of Q‐Morph meshes are also presented to demonstrate the versatility of the proposed method. Copyright © 1999 John Wiley & Sons, Ltd.     

Variational Delaunay approach to the generation of tetrahedral finite element meshes

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 à priori. 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. Copyright © 2001 John Wiley & Sons, Ltd.     

Delaunay triangulation of non-convex planar domains

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.     

‘Ultimate’ robustness in meshing an arbitrary polyhedron

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.     

Recovery of an arbitrary edge on an existing surface mesh using local mesh modifications

This study describes an algorithm for recovering an edge which is arbitrarily inserted onto a pre‐triangulated surface mesh. The recovery process does not rely on the parametric space of the surface mesh provided by the geometric modeller. The topological and geometrical validity of the surface mesh is preserved through the entire recovery process. The ability of inserting and recovering an arbitrary edge onto a surface mesh can be an invaluable tool for a number of meshing applications such as boundary layer mesh generation, solution adaptation, preserving the surface conformity, and possibly as a primary tool for mesh generation. The edge recovery algorithm utilizes local surface mesh modification operations of edge swapping, collapsing and splitting. The mesh modification operations are decided by the results of pure geometrical checks such as point and line projections onto faces and face‐line intersections. The accuracy of these checks on the recovery process are investigated and the substantiated precautions are devised and discussed in this study. Copyright © 2001 John Wiley & Sons, Ltd.     

Automatic generation of transitional meshes

Advances in commercial computer‐aided design software have made finite element analysis with three‐dimensional solid finite elements routinely available. Since these analyses usually confine themselves to those geometrical objects for which particular CAD systems can produce finite element meshes, expanding the capability of analyses becomes an issue of expanding the capability of generating meshes. This paper presents a method for stitching together two three‐dimensional meshes with diverse elements that can include tetrahedral, pentahedral and hexahedral solid finite elements. The stitching produces a mesh that coincides with the edges which already exist on the portion of boundaries that will be joined. Moreover, the transitional mesh does not introduce new edges on these boundaries. Since the boundaries of the regions to be stitched together can have a mixture of triangles and quadrilaterals, tetrahedral and pyramidal elements provide the transitional elements required to honor these constraints. On these boundaries a pyramidal element shares its base face with the quadrilateral faces of hexahedra and pentahedra. Tetrahedral elements share a face with the triangles on the boundary. Tetrahedra populate the remaining interior of the transitional region. Copyright © 2001 John Wiley & Sons, Ltd.     

面向四面体网格生成的曲面Delaunay三角化算法

提出了一种曲面域Delaunay三角网格的直接构造算法。该算法在曲面网格剖分的边界递归算法和限定Delaunay四面体化算法的基础上,利用曲面采样点集的空间Delaunay四面体网格来辅助曲面三角网格的生成,曲面上的三角网格根据最小空球最小准则由辅助四面体网格中选取,每个三角形都满足三维Delaunay空球准则,网格质量有保证,并且极大的方便了进一步的曲面边界限定下的Delaunay四面体化的进行。     

The construction of improved‐quality mesh on a curved surface using mapping factors

Abstract

The Delaunay triangulation is broadly used on flat surfaces to generate well‐shaped elements. But the properties of Delaunay triangulation do not exist on curved surfaces whose Jacobians are different. In this paper we will present a modified algorithm to improve the shape of triangulation for the curved surface. The experiment results show that making use of “mapping factors” in the Delaunay triangulation and Laplacian method can produce better mesh (most aspect ratios≤3) on a curved surface.     

THREE-DIMENSIONAL FINITE ELEMENT MESHING BY INCREMENTAL NODE INSERTION

This paper describes an efficient algorithm for fully automated three-dimensional finite element meshing which is applicable to non-convex geometry and non-manifold topology. This algorithm starts with sparsely placed nodes on the boundaries of a geometric model and a corresponding 3-D Delaunay triangulation. Nodes are then inserted incrementally by checking the tetrahedral mesh geometry and topological compatibility between Delaunay triangulation and the geometric model. Topological compatibility is checked in a robust manner by a method which relies more on a mesh's topology than its geometry. The node placement strategy is tightly coupled to an incremental Delaunay triangulation algorithm, and results in a low growth rate of computational time.     

Coarsening unstructured meshes by edge contraction

A new unstructured mesh coarsening algorithm has been developed for use in conjunction with multilevel methods. The algorithm preserves geometrical and topological features of the domain, and retains a maximal independent set of interior vertices to produce good coarse mesh quality. In anisotropic meshes, vertex selection is designed to retain the structure of the anisotropic mesh while reducing cell aspect ratio. Vertices are removed incrementally by contracting edges to zero length. Each vertex is removed by contracting the edge that maximizes the minimum sine of the dihedral angles of cells affected by the edge contraction. Rarely, a vertex slated for removal from the mesh cannot be removed; the success rate for vertex removal is typically 99.9% or more. For two‐dimensional meshes, both isotropic and anisotropic, the new approach is an unqualified success, removing all rejected vertices and producing output meshes of high quality; mesh quality degrades only when most vertices lie on the boundary. Three‐dimensional isotropic meshes are also coarsened successfully, provided that there is no difficulty distinguishing corners in the geometry from coarsely‐resolved curved surfaces; sophisticated discrete computational geometry techniques appear necessary to make that distinction. Three‐dimensional anisotropic cases are still problematic because of tight constraints on legal mesh connectivity. More work is required to either improve edge contraction choices or to develop an alternative strategy for mesh coarsening for three‐dimensional anisotropic meshes. Copyright © 2003 John Wiley & Sons, Ltd.     

Triangulation of cubic panorama for view synthesis

An unstructured triangulation approach, new to our knowledge, is proposed to apply triangular meshes for representing and rendering a scene on a cubic panorama (CP). It sophisticatedly converts a complicated three-dimensional triangulation into a simple three-step triangulation. First, a two-dimensional Delaunay triangulation is individually carried out on each face. Second, an improved polygonal triangulation is implemented in the intermediate regions of each of two faces. Third, a cobweblike triangulation is designed for the remaining intermediate regions after unfolding four faces to the top/bottom face. Since the last two steps well solve the boundary problem arising from cube edges, the triangulation with irregular-distribution feature points is implemented in a CP as a whole. The triangular meshes can be warped from multiple reference CPs onto an arbitrary viewpoint by face-to-face homography transformations. The experiments indicate that the proposed triangulation approach provides a good modeling for the scene with photorealistic rendered CPs.     

二维任意域约束Delaunay三角化的实现

本文设计了一种逐点加入一局部换边法,提出并证明了二维约束边在约束Ｄｅｌａｕｎａｙ三角化中存在的条件,并据此用中点加点法实现了二维任意域的Ｄｅｌａｕｎａｙ三角剖分,生成的网格均符合Ｄｅｌａｕｎａｙ优化准则,网格的优化在网格生成过程中完成,算法复杂度与点数呈近似线性关系,给出了算法在平面域剖分和包含复杂断层的石油地质勘探散乱数据点集剖分的应用实例。     

Automatic construction of non‐obtuse boundary and/or interface Delaunay triangulations for control volume methods

A Delaunay mesh without triangles having obtuse angles opposite to boundary and interface edges (obtuse boundary/interface triangles) is the basic requirement for problems solved using the control volume method. In this paper we discuss postprocess algorithms that allow the elimination of obtuse boundary/interface triangles of any constrained Delaunay triangulation with minimum angle ε. This is performed by the Delaunay insertion of a finite number of boundary and/or interface points. Techniques for the elimination of two kinds of obtuse boundary/interface triangles are discussed in detail: 1‐edge obtuse triangles, which have a boundary/interface (constrained) longest edge; and 2‐edge obtuse triangles, which have both their longest and second longest edge over the boundary/interface. More complex patterns of obtuse boundary/interface triangles, namely chains of 2‐edge constrained triangles forming a saw diagram and clusters of triangles that have constrained edges sharing a common vertex are managed by using a generalization of the above techniques. Examples of the use of these techniques for semiconductor device applications and a discussion on their generalization to 3‐dimensions (3D) are also included. Copyright © 2002 John Wiley & Sons, Ltd.     

Constrained boundary recovery for three dimensional Delaunay triangulations

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.     

Aspects of three-dimensional constrained Delaunay meshing

Presented in this paper are the theoretical aspects of node addition to a non-convex, multiboundary mesh of tetrahedral elements as used in finite element modelling. The method used is derived from Watson¹ and Shenton and Cendes² and is extended to deal with node addition on inter-material boundaries. Several situations are identified that result in an illegal insertion polyhedron (IP), these could be caused by the ‘constrained’ nature of the mesh, adjacent objects with different material properties, or degenerate node configurations. A new Delaunay algorithm is described that checks for illegal cases of the IP and then corrects them, this checking relies on the consistent ordering of the element nodes. It is shown that a particular type of illegal IP can easily be identified and corrected using this technique. The Delaunay algorithm is then applied to automatic mesh generation, and modification to the basic Delaunay algorithm is described so that previously meshed edges and faces of the current object being meshed are not deleted during the addition of subsequent nodes. This ‘protection’ method only becomes viable by recognizing the node ordering sense of the IP faces.     

Robust boundary triangulation and delaunay triangulation of arbitrary planar domains

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.     

Triangular meshes for regions of complicated shape

A method using techniques of computational geometry for triangular mesh generation for regions with complicated polygonal boundaries in the plane is presented. The input to the method includes the desired number of triangles and a mesh smoothness parameter to be specified, as well as the polygonal curves of the region's boundary and, possibly, internal interfaces. The triangulation generated conforms to the length scales of the edges of the boundary curves, but the method can be extended to provide additional control of the triangulation by a mesh distribution function. The region is decomposed into convex subregions in two stages, such that triangles of one length scale can be generated in each subregion. This decomposition uses algorithms which run in times that are linear in the number of vertices of the input polygons. Details of two major computational experiments are provided.     

3D boundary recovery by constrained Delaunay tetrahedralization

Three‐dimensional boundary recovery is a fundamental problem in mesh generation. In this paper, we propose a practical algorithm for solving this problem. Our algorithm is based on the construction of a constrained Delaunay tetrahedralization (CDT) for a set of constraints (segments and facets). The algorithm adds additional points (so‐called Steiner points) on segments only. The Steiner points are chosen in such a way that the resulting subsegments are Delaunay and their lengths are not unnecessarily short. It is theoretically guaranteed that the facets can be recovered without using Steiner points. The complexity of this algorithm is analyzed. The proposed algorithm has been implemented. Its performance is reported through various application examples. Copyright © 2010 John Wiley & Sons, Ltd.     

Automatic triangulation of arbitrary planar domains for the finite element method

The object of this paper is to describe a new algorithm for the semi-automatic triangulation of arbitrary, multiply connected planar domains. The strategy is based upon a modification of a finite element mesh genration algorithm recently developed. ¹ The scheme is designed for maximum flexibility and is capable of generating meshes of triangular elements for the decomposition of virtually any multiply connected planar domain. Moreover, the desired density of elements in various regions of the problem domain is specified by the user, thus allowing him to obtain a mesh decomposition appropriate to the physical loading and/or boundary conditions of the particular problem at hand. Several examples are presented to illustrate the applicability of the algorithm. An extension of the algorithm to the triangulation of shell structures is indicated.