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.     

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.     

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.     

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三角化算法

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

One machine,one minute,three billion tetrahedra

This paper presents a new scalable parallelization scheme to generate the 3D Delaunay triangulation of a given set of points. Our first contribution is an efficient serial implementation of the incremental Delaunay insertion algorithm. A simple dedicated data structure, an efficient sorting of the points, and the optimization of the insertion algorithm have permitted to accelerate reference implementations by a factor three. Our second contribution is a multithreaded version of the Delaunay kernel that is able to concurrently insert vertices. Moore curve coordinates are used to partition the point set, avoiding heavy synchronization overheads. Conflicts are managed by modifying the partitions with a simple rescaling of the space-filling curve. The performances of our implementation have been measured on three different processors: an Intel core-i7, an Intel Xeon Phi, and an AMD EPYC, on which we have been able to compute three billion tetrahedra in 53 seconds. This corresponds to a generation rate of over 55 million tetrahedra per second. We finally show how this very efficient parallel Delaunay triangulation can be integrated in a Delaunay refinement mesh generator, which takes as input the triangulated surface boundary of the volume to mesh.     

三维复杂模型的多分辨率显示

对基于三角剖分网的三维面模型的多分辨率显示计算基本原理进行了探讨,并提出了基于三角剖分网的复杂面模型的分阶渐进的多分辨率显示算法,通过实践证明,该算法具有算法简单,显示效果好的特点。     

Inserting a surface into an existing unstructured mesh

In this work, a new method for inserting a surface as an internal boundary into an existing unstructured tetrahedral mesh is developed. The surface is discretized by initially placing vertices on its bounding curves, defining a length scale at every location on each boundary curve based on the local underlying mesh, and equidistributing length scale along these curves between vertices. The surface is then sampled based on this boundary discretization, resulting in a surface mesh spaced in a way that is consistent with the initial mesh. The new points are then inserted into the mesh, and local refinement is performed, resulting in a final mesh containing a representation of the surface while preserving mesh quality. The advantage of this algorithm over generating a new mesh from scratch is in allowing for the majority of existing simulation data to be preserved and not have to be interpolated onto the new mesh. This algorithm is demonstrated in two and three dimensions on problems with and without intersections with existing internal boundaries. Copyright © 2015 John Wiley & Sons, Ltd.     

An algorithm for triangulating smooth three-dimensional domains immersed in universal meshes

We describe an algorithm to recover a boundary-fitting triangulation for a bounded C²-regular domain immersed in a nonconforming background mesh of tetrahedra. The algorithm consists in identifying a polyhedral domain ω_h bounded by facets in the background mesh and morphing ω_h into a boundary-fitting polyhedral approximation Ω_h of Ω. We discuss assumptions on the regularity of the domain, on element sizes and on specific angles in the background mesh that appear to render the algorithm robust. With the distinctive feature of involving just small perturbations of a few elements of the background mesh that are in the vicinity of the immersed boundary, the algorithm is designed to benefit numerical schemes for simulating free and moving boundary problems. In such problems, it is now possible to immerse an evolving geometry in the same background mesh, called a universal mesh, and recover conforming discretizations for it. In particular, the algorithm entirely avoids remeshing-type operations and its complexity scales approximately linearly with the number of elements in the vicinity of the immersed boundary. We include detailed examples examining its performance.     

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

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

基于球面三角网格逼近的等距曲面逼近算法

给出了一种基于球面三角网格逼近的等距曲面逼近新算法。利用三角网格逼近基球面,然后计算此三角网格按中心沿在曲面扫凉而成空间区域的边界作为等距曲面的逼近。该算法计算简单,方便地解决了整体误差问题,而且所得到的逼近曲面是与原曲面同次数的NURBS曲面。     

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.     

A new automatic adaptive 3D solid mesh generation scheme for thin‐walled structures

A new algorithm to generate three‐dimensional (3D) mesh for thin‐walled structures is proposed. In the proposed algorithm, the mesh generation procedure is divided into two distinct phases. In the first phase, a surface mesh generator is employed to generate a surface mesh for the mid‐surface of the thin‐walled structure. The surface mesh generator used will control the element size properties of the final mesh along the surface direction. In the second phase, specially designed algorithms are used to convert the surface mesh to a 3D solid mesh by extrusion in the surface normal direction of the surface. The extrusion procedure will control the refinement levels of the final mesh along the surface normal direction. If the input surface mesh is a pure quadrilateral mesh and refinement level in the surface normal direction is uniform along the whole surface, all hex‐meshes will be produced. Otherwise, the final 3D meshes generated will eventually consist of four types of solid elements, namely, tetrahedron, prism, pyramid and hexahedron. The presented algorithm is highly flexible in the sense that, in the first phase, any existing surface mesh generator can be employed while in the second phase, the extrusion procedure can accept either a triangular or a quadrilateral or even a mixed mesh as input and there is virtually no constraint on the grading of the input mesh. In addition, the extrusion procedure development is able to handle structural joints formed by the intersections of different surfaces. Numerical experiments indicate that the present algorithm is applicable to most practical situations and well‐shaped elements are generated. Copyright © 2004 John Wiley & Sons, Ltd.     

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

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

Meshing curved wire‐frame models through energy minimization and packing of ellipses

In the initial phase of structural part design, wire‐frame models are sometimes used to represent the shapes of curved surfaces. Finite Element Analysis (FEA) of a curved surface requires a well shaped, graded mesh that smoothly interpolates the wire frame. This paper describes an algorithm that generates such a triangular mesh from a wire‐frame model in the following two steps: (1) construct a triangulated surface by minimizing the strain energy of the thin‐plate‐bending model, and (2) generate a mesh by the bubble meshing method on the projected plane and project it back onto the triangulated surface. Since the mesh elements are distorted by the projection, the algorithm generates an anisotropic mesh on the projected plane so that an isotropic mesh results from the final projection back onto the surface. Extensions of the technique to anisotropic meshing and quadrilateral meshing are also discussed. The algorithm can generate a well‐shaped, well‐graded mesh on a smooth curved surface. Copyright © 1999 John Wiley & Sons, Ltd.     

Optimization of a regularized distortion measure to generate curved high‐order unstructured tetrahedral meshes

We present a robust method for generating high‐order nodal tetrahedral curved meshes. The approach consists of modifying an initial linear mesh by first, introducing high‐order nodes, second, displacing the boundary nodes to ensure that they are on the computer‐aided design surface, and third, smoothing and untangling the mesh obtained after the displacement of the boundary nodes to produce a valid curved high‐order mesh. The smoothing algorithm is based on the optimization of a regularized measure of the mesh distortion relative to the original linear mesh. This means that whenever possible, the resulting mesh preserves the geometrical features of the initial linear mesh such as shape, stretching, and size. We present several examples to illustrate the performance of the proposed algorithm. Furthermore, the examples show that the implementation of the optimization problem is robust and capable of handling situations in which the mesh before optimization contains a large number of invalid elements. We consider cases with polynomial approximations up to degree ten, large deformations of the curved boundaries, concave boundaries, and highly stretched boundary layer elements. The meshes obtained are suitable for high‐order finite element analyses. Copyright © 2015 John Wiley & Sons, Ltd.     

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.     

裁剪曲面的三角化及图形显示

结合自主版权的超人ＣＡＤ／ＣＡＭ系统的开发，本文提出了一种适合于裁剪曲面图形显示的曲面三角化算法，该算法将曲面的三角化转化为曲面参数域的三角化，并将二维图形的集合运算与Ｄｅｌａｕｎａｙ三角剖分应有和于曲面参数域边界的处理，从而使裁剪曲面在边界上的三角形分布均匀。