OPTIMAL DELAUNAY POINT INSERTION

An efficient algorithm for Delaunay triangulation of a given set of points in d dimensions is presented. Various steps of the point insertion algorithm are reviewed and many acceleration procedures are implemented to speed up the triangulation process. New features include the search for a neighbouring point by a layering scheme, locating the containing simplex by a random walk, formulas of important geometrical quantities of a new simplex based on those of an old one, a novel approach in establishing the adjacency relationship using connection matrices. The resulting scheme seems to be one of the fastest triangulation algorithms known, which enables us to generate tetrahedra in ℝ³ with a linear generation rate of 15 000 tetrahedra per second for randomly generated points on an HP 735 workstation.     

New longest-edge algorithms for the refinement and/or improvement of unstructured triangulations

In this paper I introduce a new mathematical tool for dealing with the refinement and/or the improvement of unstructured triangulations: the Longest-Edge Propagation Path associated with each triangle to be either refined and/or improved in the mesh. This is defined as the (finite) ordered list of successive neighbour triangles having longest-edge greater than the longest edge of the preceding triangle in the path. This ideal is used to introduce two kinds of algorithms (which make use of a Backward Longest-Edge point insertion strategy): (1) a pure Backward Longest-Edge Refinement Algorithm that produces the same triangulations as previous longest-edge algorithms in a more efficient, direct and easy-to-implement way; (2) a new Backward Longest-Edge Improvement Algorithm for Delaunay triangulations, suitable to deal (in a reliable, robust and effective way) with the three important related aspects of the (triangular) mesh generation problem: mesh refinement, mesh improvement, and automatic generation of good-quality surface and volume triangulation of general geometries including small details. The algorithms and practical issues related with their implementation (both for the polygon and surface quality triangulation problems) are discussed in this paper. In particular, an effective boundary treatment technique is also discussed. The triangulations obtained with the LEPP–Delaunay algorithm have smallest angles greater than 30° and are, in practice, of optimal size. Furthermore, the LEPP–Delaunay algorithms naturally generalize to three-dimensions. © 1997 by John Wiley & Sons, Ltd.     

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

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

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.     

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.     

Node placement for triangular mesh generation by Monte Carlo simulation

A new approach of node placement for unstructured mesh generation is proposed. It is based on the Monte Carlo method to position nodes for triangular or tetrahedral meshes. Surface or volume geometries to be meshed are treated as atomic systems, and mesh nodes are considered as interacting particles. By minimizing system potential energy with Monte Carlo simulation, particles are placed into a near‐optimal configuration. Well‐shaped triangles or tetrahedra can then be created after connecting the nodes by constrained Delaunay triangulation or tetrahedrization. The algorithm is simple, easy to implement, and works in an almost identical way for 2D and 3D meshing. Copyright © 2005 John Wiley & Sons, Ltd.     

UNSTRUCTURED GRID GENERATION AND A SIMPLE TRIANGULATION ALGORITHM FOR ARBITRARY 2-D GEOMETRIES USING OBJECT ORIENTED PROGRAMMING

This paper describes the logic of a dynamic algorithm for a general 2D Delaunay triangulation of arbitrarily prescribed interior and boundary nodes. The complexity of the geometry is completely arbitrary. The scheme is free of specific restrictions on the input of the geometrical data. The scheme generates triangles whose associated circumcircles contain no nodal points except their vertices. There is no predefined limit for the number of points and the boundaries. The direction of generation of the triangles cannot be determined a priori as opposed to the moving front techniques. An automatic node placement scheme reflecting the initial boundary point spacings is used. The successive refinement scheme results in such a point distribution that the triangulation algorithm need not perform any geometric intersection check for overlapped triangles and penetrated boundaries. Further computational saving is provided by using a special binary tree (ADT) in which the points are ordered such that contiguous points in the list are neighbours in physical space. The method consists of a set of simple rules to understand. The dynamic nature of the Object Oriented Programming (OOP) of the algorithms provides efficient memory management on the insertion, deletion and searching processes. The computational effort bears a linear relation-ship between the CPU time and the total number of nodes. Some of the existing methods in the literature regarding triangular mesh generation are discussed in context. © 1997 by John Wiley & Sons, Ltd.     

The boundary recovery and sliver elimination algorithms of three‐dimensional constrained Delaunay triangulation

A boundary recovery and sliver elimination algorithm of the three‐dimensional constrained Delaunay triangulation is proposed for finite element mesh generation. The boundary recovery algorithm includes two main procedures: geometrical recovery procedure and topological recovery procedure. Combining the advantages of the edges/faces swappings algorithm and edges/faces splittings algorithm presented respectively by George and Weatherill, the geometrical recovery procedure can recover the missing boundaries and guarantee the geometry conformity by introducing fewer Steiner points. The topological recovery procedure includes two phases: ‘dressing wound’ and smoothing, which will overcome topology inconsistency between 3D domain boundary triangles and the volume mesh. In order to solve the problem of sliver elements in the three‐dimensional Delaunay triangulation, a method named sliver decomposition is proposed. By extending the algorithm proposed by Canvendish, the presented method deals with sliver elements by using local decomposition or mergence operation. In this way, sliver elements could be eliminated thoroughly and the mesh quality could be improved in great deal. Copyright © 2006 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.     

Mesh generation/refinement using fractal concepts and iterated function systems

A novel method of mesh generation is proposed which is based on the use of fractal concepts to derive contractive, affine transformations. The transformations are constructed in such a manner that the attractors of the resulting maps are a union of the points, lines and surfaces in the domain. In particular, the mesh nodes may be generated recursively as a sequence of points which are obtained by applying the transformations to a coarse background mesh constructed from the given boundary data. A Delaunay triangulation or similar edge connection approach can then be performed on the resulting set of nodes in order to generate the mesh. Local refinement of an existing mesh can also be performed using the procedure. The method is easily extended to three dimensions, in which case the Delaunay triangulation is replaced by an analogous 3-D tesselation.     

‘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.     

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

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

Adaptive tetrahedral mesh generation by constrained Delaunay refinement

This paper presents a tetrahedral mesh generation method for numerically solving partial differential equations using finite element or finite volume methods in three‐dimensional space. The main issues are the mesh quality and mesh size, which directly affect the accuracy of the numerical solution and the computational cost. Two basic problems need to be resolved, namely boundary conformity and field points distribution. The proposed method utilizes a special three‐dimensional triangulation, so‐called constrained Delaunay tetrahedralization to conform the domain boundary and create field points simultaneously. Good quality tetrahedra and graded mesh size can be theoretically guaranteed for a large class of mesh domains. In addition, an isotropic size field associated with the numerical solution can be supplied; the field points will then be distributed according to it. Good mesh size conformity can be achieved for smooth sizing informations. The proposed method has been implemented. Various examples are provided to illustrate its theoretical aspects as well as practical performance. Copyright © 2008 John Wiley & Sons, Ltd.     

无网格方法数值结果的可视化方法与实现

科学计算可视化是科学计算中不可缺少的一个组成部分,其主要任务是将数值模拟产生的大量复杂的数据信息通过计算机技术转换成图形、图像信息。无网格方法是一种基于点的数值计算方法,各离散点之间没有联结信息,其数值结果的可视化后处理是一件很困难的事情,尤其当离散点随机分布时,更是如此。Delaunay 三角化是十分理想的散乱数据的可视化工具,它可以根据一组随机分布的离散点数据生成唯一的近似等边三角形。首先介绍了 Voronoi 图与 Delaunay 三角化的基本原理,然后介绍了实现 Delaunay 三角剖分的算法及无网格方法数值结果可视化的实现方法,最后给出了无网格方法可视化的若干应用实例。     

一种裁剪曲面自适应三角剖分算法

本文介绍了一种裁剪曲面按精度三角剖分算法。三角剖分过程在参数域和曲面空间同时进行，参数域上控制三角片的拓扑关系，曲面空间进行精度检测。算法的核心思想是将裁剪曲面三角剖分视为约束剖分问题，从而使得三角形的细分操作拓展为有效域内插入散乱节点的三角剖分问题。算法简便、实用，三角化结果品质良好，已成功地应用于数控加工刀具轨迹干涉处理等具有精度要求的应用领域。     

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.     

点序对Delaunay三角剖分局部优化的影响

局部变换法和Watson算法是属于逐点添加、局部优化的离散点集Delaunay三角剖分的常用方法,不同的加点次序对这两种算法的局部优化影响较大。研究发现按位置相邻次序加点的方法易产生外接圆较大的扁平三角形,引起较多三角形的局部优化,而按随机次序加点,网格生成过程中网格单元相对匀称,局部优化的三角形较少。以激光点扫描采集的数据为例,统计分析了局部优化三角形的数量及分布特征,点数大于50000时,相邻次序加点方法局部优化三角形的总量是随机次序加点方法的1.6倍以上。建立离散数据的矩形空间索引,按索引轮流加点,点序对局部优化的影响降低,相邻次序加点方法局部优化的三角形总量是随机次序加点方法的1.1~1.3倍,其中随机次序加点与没有空间索引的随机次序相比,局部优化的三角形数量仅增加了约1%。     

Selective refinement: A new strategy for automatic node placement in graded triangular meshes

Automating triangular finite element mesh generation involves two interrelated tasks: generatine a distribution of well-placed nodes on the boundary and in the interior of a domain, and constructing a triangulation of these nodes. For a given distribution of nodes, the Delaunay triangulation generally provides a suitable mesh, and Watson's algorithm²⁶ provides a flexible means of constructing it. In this paper, a new method is described for automating node placement in a Delaunay triangulation by seieclive refinement of an initial triangulation. Grading of the mesh is controlled by an explicit or implicit node spacing function. Although this paper describes the technique only in the planar context, the method generalizes to three dimensions as well.     

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.