基于局部三维Delaunay的插值网格边界增量构造算法

网格构造的质量和效率是插值于大规模测量点三角网格构造算法的关键,但在算法中既保证插值网格的三维Delaunay性质又实现网格的线性构造仍存在困难。笔者针对此问题,提出了基于局部三维Delaunay的插值网格边界增量构造算法,利用网格的局部Delaunay构造及其边界的循环膨胀、分裂及自裁减操作实现整个模型的自动构造。应用实例表明,算法在保证构造网格满足三维Delaunay性质的同时,线性构造任意拓扑结构的三角网格模型。     

Quality improvement of non‐manifold hexahedral meshes for critical feature determination of microstructure materials

This paper describes a novel approach to improve the quality of non‐manifold hexahedral meshes with feature preservation for microstructure materials. In earlier works, we developed an octree‐based isocontouring method to construct unstructured hexahedral meshes for domains with multiple materials by introducing the notion of material change edge to identify the interface between two or more materials. However, quality improvement of non‐manifold hexahedral meshes is still a challenge. In the present algorithm, all the vertices are categorized into seven groups, and then a comprehensive method based on pillowing, geometric flow and optimization techniques is developed for mesh quality improvement. The shrink set in the modified pillowing technique is defined automatically as the boundary of each material region with the exception of local non‐manifolds. In the relaxation‐based smoothing process, non‐manifold points are identified and fixed. Planar boundary curves and interior spatial curves are distinguished, and then regularized using B‐spline interpolation and resampling. Grain boundary surface patches and interior vertices are improved as well. Finally, the optimization method eliminates negative Jacobians of all the vertices. We have applied our algorithms to two beta titanium data sets, and the constructed meshes are validated via a statistics study. Finite element analysis of the 92‐grain titanium is carried out based on the improved mesh, and compared with the direct voxel‐to‐element technique. Copyright © 2009 John Wiley & Sons, Ltd.     

法矢量法实现网格模型简化

提出一种基于顶点法矢量和面片法矢量的网格简化算法,能在大幅度简化的情况下,简化模型依然能保持良好的视觉效果.算法采用边折叠实现网格模型的简化,首先,建立网格模型上每个顶点的不平度,以此来衡量顶点局部对视觉效果的贡献程度;其次,度量三角形在边折叠后的变形误差,用于衡量边折叠对视觉效果所造成的畸变程度;最后,综合顶点不平度和三角形的变形误差,建立边折叠代价函数,并以此指导网格的简化.此外,在此简化算法的基础上,还提出一个递进网格传输的框架,并实现了一个基于浏览器的可视化原型系统.     

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.     

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.     

Localized remeshing techniques for three‐dimensional metal forming simulations with linear tetrahedral elements

The localized remeshing technique for three‐dimensional metal forming simulations is proposed based on a mixed finite element formulation with linear tetrahedral elements in the present study. The numerical algorithm to generate linear tetrahedral elements is developed for finite element analyses using the advancing front technique with local optimization method which keeps the advancing fronts smooth. The surface mesh generation using mesh manipulations of the boundary elements of the old mesh system was made to improve mesh quality of the boundary surface elements, resulting in reduction of volume change in forming simulations. The mesh quality generated was compared with that obtained from the commercial CAD package for the complex geometry like lumbar. The simulation results of backward extrusion and bevel gear and spider forgings indicate that the currently developed simulation technique with the localized remeshing can be used effectively to simulate the three‐dimensional forming processes with a reduced computation time. Copyright © 2006 John Wiley & Sons, Ltd.     

COMBINATION OF ADAPTIVITY AND MESH SMOOTHING FOR THE FINITE ELEMENT ANALYSIS OF SHELLS WITH INTERSECTIONS

A compatible hierarchical adaptive scheme is proposed which allows to control both density and geometrical properties of meshes with four-node linear finite shell elements. The algorithm produces a sequence of meshes with two aims, nearly equal distribution of the local error in each element and a mesh with regular elements, thus internal element angles near 90° and length ratios of adjacent element sides near unity. This goal is achieved in an efficient manner imposing a combination of a local smoothing algorithm with the adaptive mesh generation. New created nodes are positioned on the real shell surface and shell boundaries which may be given e.g. by CAD data. Also the shell directors are determined from the normals on the real geometry. Shell intersections are detected automatically as common curves of two adjacent shell parts. As a shell continuum cannot be assumed for these intersections and thus simple standard adaptive schemes fail, shell intersections have to be treated in a way similar to shell boundaries. For some numerical examples the developed algorithms are demonstrated and the resulting meshes are shown. © 1997 by John Wiley & Sons, Ltd.     

GradH‐Correction: guaranteed sizing gradation in multi‐patch parametric surface meshing

In this paper a new method, called GradH‐Correction, for the generation of multi‐patch parametric surface meshes with controlled sizing gradation is presented. Such gradation is obtained performing a correction on the size values located on the vertices of the background mesh used to define the control space that governs the meshing process. In the presence of a multi‐patch surface, like shells of BREP solids, the proposed algorithm manages the whole composite surface simultaneously and as a unique entity. Sizing information can spread from a patch to its adjacent ones and the resulting size gradation is independent from the surface partitioning. Theoretical considerations lead to the assertion that, given a parameter λ, after performing a GradH‐Correction of level λ over the control space, the unit mesh constructed using the corrected control space is a mesh of gradation λ in the real space (target space). This means that the length ratio of any two adjacent edges of the mesh is bounded between 1/λ and λ. Numerical results show that meshes generated from corrected control spaces are of high quality and good gradation also when the background mesh has poor quality. However, due to mesh generator imprecision and theoretical limitations, guaranteed gradation is achieved only for the sizing specifications and not for the generated mesh. Copyright © 2004 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.     

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

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.     

Mesh improvement by minimizing a weighted sum of squared element volumes

We describe a new mesh smoothing method that consists of minimizing the sum of squared element volumes over the free vertex positions. To the extent permitted by the fixed vertices and mesh topology, the resulting mesh elements have uniformly distributed volumes. In the case of a triangulation, uniform volume implies well‐shaped triangles. If a graded mesh is required, the element volumes may be weighted by centroidal values of a sizing function, resulting in a mesh that conforms to the required vertex density. The method has both a local and a global implementation. In addition to smoothing, the method serves as a simple parameter‐free means of untangling a mesh with inverted elements. It applies to all types of meshes, but we present test results here only for planar triangle meshes. Our test results show the new method to be fast, superior in uniformity or conformity to a sizing function, and among the best methods in terms of triangle shape quality. We also present a new angle‐based method that is simpler and more effective than alternatives. This method is directly aimed at producing well‐shaped triangles and is particularly effective when combined with the volume‐based method. It also generalizes to anisotropic mesh smoothing. Copyright © 2014 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.     

An adaptive remeshing procedure for discontinuous finite element limit analysis

An adaptive remeshing procedure is proposed for discontinuous finite element limit analysis. The procedure proceeds by iteratively adjusting the element sizes in the mesh to distribute local errors uniformly over the domain. To facilitate the redefinition of element sizes in the new mesh, the interelements discontinuous field of elemental bound gaps is converted into a continuous field, ie, the intensity of bound gap, using a patch‐based approximation technique. An analogous technique is subsequently used for the approximation of element sizes in the old mesh. With these information, an optimized distribution of element sizes in the new mesh is defined and then scaled to match the total number of elements specified for each iteration in the adaptive remeshing process. Finally, a new mesh is generated using the advancing front technique. This adaptive remeshing procedure is repeated several times until an optimal mesh is found. Additionally, for problems involving discontinuous boundary loads, a novel algorithm for the generation of fan‐type meshes around singular points is proposed explicitly and incorporated into the main adaptive remeshing procedure. To demonstrate the feasibility of our proposed method, some classical examples extracted from the existing literary works are studied in detail.     

基于"边折叠"的可逆累进网格生成算法的研究

在分析已有累进网格生成算法的基础上,提出一种基于“边折叠”网格化简方法的累进网格生成算法,构造了累进网格的表示新方法。算法消除了累进网格技术中的二义性,具有支持多种网格类型、保持相邻层次细节模型间的平滑过渡等特点。实验表明,算法具有有效性和可靠性。     

Templatized refinement of triangle meshes using surface interpolation

Mesh refinement is an important process with regards to achieving good accuracy for computational simulation and analysis. Currently, there is a lack of a high‐fidelity refinement algorithm for the accurate modelling of geometry in the absence of a physical geometric model. This paper focuses on using a surface interpolation procedure based on a quartic triangular Bezier patch to approximate the underlying geometry of a mesh and to determine the locations of new subdivision vertices. A robust methodology is used for feature retention and accurate curve fitting at sharp edges and hard vertices. This extends the applicability of the surface fitting procedure to any arbitrary geometric configuration. The refinement is based on a new 1:9 subdivision scheme and its implementation is discussed in detail. Despite its high order subdivision footprint, computational efficiency is made possible by the effective use of lookup tables. Copyright © 2005 John Wiley & Sons, Ltd.     

Applications of mesh smoothing: copy,morph, and sweep on unstructured quadrilateral meshes

Mesh smoothing is demonstrated to be an effective means of copying, morphing, and sweeping unstructured quadrilateral surface meshes from a source surface to a target surface. Construction of the smoother in a particular way guarantees that the target mesh will be a ‘copy’ of the source mesh, provided the boundary data of the target surface is a rigid body rotation, translation, and/or uniform scaling of the original source boundary data and provided the proper boundary node correspondence between source and target has been selected. Copying is not restricted to any particular smoother, but can be based on any locally elliptic second‐order operator. When the bounding loops are more general than rigid body transformations the method generates high‐quality, ‘morphed’ meshes. Mesh sweeping, if viewed as a morphing of the source surface to a set of target surfaces, can be effectively performed via this smoothing algorithm. Published in 1999 by John Wiley & Sons, Ltd. This article is a U.S. government work and is in the public domain in the United States.     

A surface remeshing approach

A method is presented to remesh three‐dimensional discrete data surfaces. The originality of the method resides in mimicking heavily the classical adva10ncing front method for quality while always relying on a valid mesh for robustness. Therefore, local operations are applied in a first step to obtain a mesh of appropriate length scale compared to the specified size, and an original procedure has been developed for refinement that automatically degenerates to a surface mesh optimization if the size map has been respected. A valid mesh is then always available during the remeshing procedure. A new background grid is proposed that relies on a Cartesian mesh for the size distribution. Interpolation is performed very quickly and the size distribution is smoothed out to provide a slowly varying mesh size distribution. Various numerical results are presented to illustrate the efficiency but mainly the quality and robustness of the method. Copyright © 2010 John Wiley & Sons, Ltd.     

An error‐estimate‐free and remapping‐free variational mesh refinement and coarsening method for dissipative solids at finite strains

A variational h‐adaptive finite element formulation is proposed. The distinguishing feature of this method is that mesh refinement and coarsening are governed by the same minimization principle characterizing the underlying physical problem. Hence, no error estimates are invoked at any stage of the adaption procedure. As a consequence, linearity of the problem and a corresponding Hilbert‐space functional framework are not required and the proposed formulation can be applied to highly non‐linear phenomena. The basic strategy is to refine (respectively, unrefine) the spatial discretization locally if such refinement (respectively, unrefinement) results in a sufficiently large reduction (respectively, sufficiently small increase) in the energy. This strategy leads to an adaption algorithm having O(N) complexity. Local refinement is effected by edge‐bisection and local unrefinement by the deletion of terminal vertices. Dissipation is accounted for within a time‐discretized variational framework resulting in an incremental potential energy. In addition, the entire hierarchy of successive refinements is stored and the internal state of parent elements is updated so that no mesh‐transfer operator is required upon unrefinement. The versatility and robustness of the resulting variational adaptive finite element formulation is illustrated by means of selected numerical examples. Copyright © 2008 John Wiley & Sons, Ltd.     

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.