Automated refinement of conformal quadrilateral and hexahedral meshes

Conformal refinement using a shrink and connect strategy, known as pillowing or buffer insertion, contracts and reconnects contiguous elements of an all‐quadrilateral or an all‐hexahedral mesh in order to locally increase vertex density without introducing hanging nodes or non‐cubical elements. Using layers as shrink sets, the present method automates the anisotropic refinement of such meshes according to a prescribed size map expressed as a Riemannian metric field. An anisotropic smoother further enhances vertex clustering to capture the features of the metric. Both two‐ and three‐dimensional test cases with analytic control metrics confirm the feasibility of the present approach and explore strategies to minimize the trade‐off between element shape quality and size conformity. Additional examples using discrete metric maps illustrate possible practical applications. Although local vertex removal and reconnection capabilities have yet to be developed, the present refinement method is a step towards an automated tool for conformal adaptation of all‐quadrilateral and all‐hexahedral meshes. Copyright © 2004 John Wiley & Sons, Ltd.     

Adaptive mesh refinement and coarsening for cohesive zone modeling of dynamic fracture

Adaptive mesh refinement and coarsening schemes are proposed for efficient computational simulation of dynamic cohesive fracture. The adaptive mesh refinement consists of a sequence of edge‐split operators, whereas the adaptive mesh coarsening is based on a sequence of vertex‐removal (or edge‐collapse) operators. Nodal perturbation and edge‐swap operators are also employed around the crack tip region to improve crack geometry representation, and cohesive surface elements are adaptively inserted whenever and wherever they are needed by means of an extrinsic cohesive zone model approach. Such adaptive mesh modification events are maintained in conjunction with a topological data structure (TopS). The so‐called PPR potential‐based cohesive model (J. Mech. Phys. Solids 2009; 57 :891–908) is utilized for the constitutive relationship of the cohesive zone model. The examples investigated include mode I fracture, mixed‐mode fracture and crack branching problems. The computational results using mesh adaptivity (refinement and coarsening) are consistent with the results using uniform mesh refinement. The present approach significantly reduces computational cost while exhibiting a multiscale effect that captures both global macro‐crack and local micro‐cracks. Copyright © 2012 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.     

A new method for coarsening tetrahedral meshes

To coarsen a mesh, we usually remove a set of selected nodes one by one. Currently, the basic operation used to remove a node is edge collapsing, which does not perform well when applied to handling narrow regions in a tetrahedron mesh and could produce low‐quality elements or even fail to give valid results. To overcome the drawbacks of edge collapsing, we present a new node‐removal operator created by revising a topological transformation called small polyhedron reconnection. This new operator can guarantee success if the cavity that forms after a node is removed is meshable, and it produces higher‐quality results and keeps the nodes unmoved, which is preferred for applications such as multigrid hierarchies. In addition, 2 other aspects of mesh coarsening that determine whether a node should be removed and the sequence in which to remove the selected nodes are also studied. Our strategy consists of constructing a coarse node set using the sphere‐packing method and removing the nodes in a reversed kd‐tree sequence. The excellent performance of the new method is demonstrated by applying it to examples of adaptive meshing and multigrid hierarchy creation and comparing the results with those of the edge collapsing method.     

Tetrahedral mesh generation using Delaunay refinement with non‐standard quality measures

This paper studies the practical performance of Delaunay refinement tetrahedral mesh generation algorithms. By using non‐standard quality measures to drive refinement, we show that sliver tetrahedra can be eliminated from constrained Delaunay tetrahedralizations solely by refinement. Despite the fact that quality guarantees cannot be proven, the algorithm can consistently generate meshes with dihedral angles between 18^circ and 154^°. Using a fairer quality measure targeting every type of bad tetrahedron, dihedral angles between 14^° and 154^° can be obtained. The number of vertices inserted to achieve quality meshes is comparable to that needed when driving refinement with the standard circumradius‐to‐shortest‐edge ratio. We also study the use of mesh improvement techniques on Delaunay refined meshes and observe that the minimum dihedral angle can generally be pushed above 20^°, regardless of the quality measure used to drive refinement. The algorithm presented in this paper can accept geometric domains whose boundaries are piecewise smooth. Copyright © 2011 John Wiley & Sons, Ltd.     

Automatic generation of anisotropic quadrilateral meshes on three‐dimensional surfaces using metric specifications

A new algorithm for constructing full quadrilateral anisotropic meshes on 3D surfaces is proposed in this paper. The proposed method is based on the advancing front and the systemic merging techniques. Full quadrilateral meshes are constructed by systemically converting triangular elements in the background meshes into quadrilateral elements.By using the metric specifications to describe the element characteristics, the proposed algorithm is applicable to convert both isotropic and anisotropic triangular meshes into full quadrilateral meshes. Special techniques for generating anisotropic quadrilaterals such as new selection criteria of base segment for merging, new approaches for the modifications of the background mesh and construction of quadrilateral elements, are investigated and proposed in this study. Since the final quadrilateral mesh is constructed from a background triangular mesh and the merging procedure is carried out in the parametric space, the mesh generator is robust and no expensive geometrical computation that is commonly associated with direct quadrilateral mesh generation schemes is needed. Copyright © 2002 John Wiley & Sons, Ltd.     

Parallel refinement and coarsening of tetrahedral meshes

This paper presents a parallel adaptation procedure (coarsening and refinement) for tetrahedral meshes in a distributed environment. Coarsening relies upon an edge collapsing tool. Refinement uses edge‐based subdivision templates. Mesh optimization maintains the quality of the adapted meshes. Focus is given to the parallelization of the various components. Scalability requires repartitioning of the mesh before applying either coarsening or refinement. Relatively good speed‐ups have been obtained for all phases of the proposed adaptation scheme. Copyright © 1999 John Wiley & Sons, Ltd.     

Variational generation of prismatic boundary‐layer meshes for biomedical computing

Boundary‐layer meshes are important for numerical simulations in computational fluid dynamics, including computational biofluid dynamics of air flow in lungs and blood flow in hearts. Generating boundary‐layer meshes is challenging for complex biological geometries. In this paper, we propose a novel technique for generating prismatic boundary‐layer meshes for such complex geometries. Our method computes a feature size of the geometry, adapts the surface mesh based on the feature size, and then generates the prismatic layers by propagating the triangulated surface using the face‐offsetting method. We derive a new variational method to optimize the prismatic layers to improve the triangle shapes and edge orthogonality of the prismatic elements and also introduce simple and effective measures to guarantee the validity of the mesh. Coupled with a high‐quality tetrahedral mesh generator for the interior of the domain, our method generates high‐quality hybrid meshes for accurate and efficient numerical simulations. We present comparative study to demonstrate the robustness and quality of our method for complex biomedical geometries. Copyright © 2009 John Wiley & Sons, Ltd.     

Verification of three‐dimensional anisotropic adaptive processes

A verification methodology for adaptive processes is devised. The mathematical claims made during the process are identified and measures are presented in order to verify that the mathematical equations are solved correctly. The analysis is based on a formal definition of the optimality of the adaptive process in the case of the control of the L^∞‐norm of the interpolation error. The process requires a reconstruction that is verified using a proper norm. The process also depends on mesh adaptation toolkits in order to generate adapted meshes. In this case, the non‐conformity measure is used to evaluate how well the adapted meshes conform to the size specification map at each iteration. Finally, the adaptive process should converge toward an optimal mesh. The optimality of the mesh is measured using the standard deviation of the element‐wise value of the L^∞‐norm of the interpolation error. The results compare the optimality of an anisotropic process to an isotropic process and to uniform refinement on highly anisotropic 2D and 3D test cases. Copyright © 2011 John Wiley & Sons, Ltd.     

Quality improvements in extruded meshes using topologically adaptive generalized elements

This paper describes a method to extrude near‐body volume meshes that exploits topologically adaptive generalized elements to improve local mesh quality. Specifically, an advancing layer algorithm for extruding volume meshes from surface meshes of arbitrary topology, appropriate for viscous fluid flows, is discussed. First, a two‐layer reference mesh is generated from the layer initial surface mesh by extruding along the local surface normals. The reference mesh is then smoothed using a Poisson equation. Local quality improvement operations such as edge collapse, face refinement, and local reconnection are performed in each layer to drive the mesh toward isotropy and improve the transition from the extruded mesh to a void‐filling tetrahedral mesh. A few example meshes along with quality plots are presented to demonstrate the efficacy of this approach. Copyright © 2004 John Wiley & Sons, Ltd.     

Achieving finite element mesh quality via optimization of the Jacobian matrix norm and associated quantities. Part II—A framework for volume mesh optimization and the condition number of the Jacobian matrix

Three‐dimensional unstructured tetrahedral and hexahedral finite element mesh optimization is studied from a theoretical perspective and by computer experiments to determine what objective functions are most effective in attaining valid, high‐quality meshes. The approach uses matrices and matrix norms to extend the work in Part I to build suitable 3D objective functions. Because certain matrix norm identities which hold for 2×2 matrices do not hold for 3×3 matrices, significant differences arise between surface and volume mesh optimization objective functions. It is shown, for example, that the equality in two dimensions of the smoothness and condition number of the Jacobian matrix objective functions does not extend to three dimensions and further, that the equality of the Oddy and condition number of the metric tensor objective functions in two dimensions also fails to extend to three dimensions. Matrix norm identities are used to systematically construct dimensionally homogeneous groups of objective functions. The concept of an ideal minimizing matrix is introduced for both hexahedral and tetrahedral elements. Non‐dimensional objective functions having barriers are emphasized as the most logical choice for mesh optimization. The performance of a number of objective functions in improving mesh quality was assessed on a suite of realistic test problems, focusing particularly on all‐hexahedral ‘whisker‐weaved’ meshes. Performance is investigated on both structured and unstructured meshes and on both hexahedral and tetrahedral meshes. Although several objective functions are competitive, the condition number objective function is particularly attractive. The objective functions are closely related to mesh quality measures. To illustrate, it is shown that the condition number metric can be viewed as a new tetrahedral element quality measure. Published in 2000 by John Wiley & Sons, Ltd.     

Octree‐based reasonable‐quality hexahedral mesh generation using a new set of refinement templates

An octree‐based mesh generation method is proposed to create reasonable‐quality, geometry‐adapted unstructured hexahedral meshes automatically from triangulated surface models without any sharp geometrical features. A new, easy‐to‐implement, easy‐to‐understand set of refinement templates is developed to perform local mesh refinement efficiently even for concave refinement domains without creating hanging nodes. A buffer layer is inserted on an octree core mesh to improve the mesh quality significantly. Laplacian‐like smoothing, angle‐based smoothing and local optimization‐based untangling methods are used with certain restrictions to further improve the mesh quality. Several examples are shown to demonstrate the capability of our hexahedral mesh generation method for complex geometries. Copyright © 2008 John Wiley & Sons, Ltd.     

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.     

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

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

Computational Morphogenesis: Morphologic constructions using polygonal discretizations

To consistently coarsen arbitrary unstructured meshes, a computational morphogenesis process is built in conjunction with a numerical method of choice, such as the virtual element method with adaptive meshing. The morphogenesis procedure is performed by clustering elements based on a posteriori error estimation. Additionally, an edge straightening scheme is introduced to reduce the number of nodes and improve accuracy of solutions. The adaptive morphogenesis can be recursively conducted regardless of element type and mesh generation counting. To handle mesh modification events during the morphogenesis, a topology-based data structure is employed, which provides adjacent information on unstructured meshes. Numerical results demonstrate that the adaptive mesh morphogenesis effectively handles mesh coarsening for arbitrarily shaped elements while capturing problematic regions such as those with sharp gradients or singularity.     

Adaptive triangular–quadrilateral mesh generation

In this paper, we begin by recalling an adaptive mesh generation method governed by isotropic and anisotropic discrete metric maps, by means of the generation of a unit mesh with respect to a Riemannian structure. We propose then an automatic triangular to quadrilateral mesh conversion scheme, which generalizes the standard case to the anisotropic context. In addition, we introduce an optimal vertex smoothing procedure. Application test examples, in particular a CFD test, are given to demonstrate the efficiency of the proposed method. © 1998 John Wiley & Sons, Ltd.     

Geometry independence for a meshing engine for 2D manifolds

The ‘meshing engine’ of the title is a software component that generates unstructured triangular meshes of two‐dimensional triangles for a variety of contexts. The mesh generation is based on the well‐known technique of iterative Delaunay refinement, for which the Euclidean metric is intrinsic. The meshing engine is to be connected to applications specific host programs which can use a geometry that is different from the intrinsic geometry of the mesh, i.e. locally, the Euclidean plane. An application may require a surface mesh for embedding in a three‐dimensional geometry, or it might use a Riemannian metric to specify a required anisotropy in the mesh, or both. We focus on how the meshing engine can be designed to be independent of the embedding geometry of a host program but conveniently linked to it. A crucial tool for these goals is the use of an appropriate local co‐ordinate system for the triangles as seen by the meshing engine. We refer to it as the longest edge co‐ordinate system. Our reference to ‘linking’ the meshing engine and host system is both general and technical in the sense that the example meshes provided in the paper have all been generated by the same object code of a prototype of such a meshing engine linked to host programs defining different embedding geometries. Copyright © 2004 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.     

Hybrid parallel multigrid preconditioner based on automatic mesh coarsening for 3D metal forming simulations

A parallel multigrid (MG) method is developed to reduce the large computational costs involved by the finite element simulation of highly viscous fluid flows, especially those resulting from metal forming applications, which are characterized by using a mixed velocity/pressure implicit formulation, unstructured meshes of tetrahedra, and frequent remeshings. The developed MG method follows a hybrid approach where the different levels of nonnested meshes are geometrically constructed by mesh coarsening, while the linear systems of the intermediate levels result from the Galerkin algebraic approach. A linear O(N) convergence rate is expected (with N being the number of unknowns), while keeping software parallel efficiency. These objectives lead to selecting unusual MG smoothers (iterative solvers) for the upper grid levels and to developing parallel mesh coarsening algorithms along with parallel transfer operators between the different levels of partitioned meshes. Within the utilized PETSc library, the developed MG method is employed as a preconditioner for the usual conjugate residual algorithm because of the symmetric undefinite matrix of the system to solve. It shows a convergence rate close to optimal, an excellent parallel efficiency, and the ability to handle the complex forming problems encountered in 3‐dimensional hot forging, which involve large material deformations and frequent remeshings.