An indirect approach for automatic generation of quadrilateral meshes with arbitrary line constraints

A new approach to the automatic generation of a quadrilateral mesh with arbitrary line constraints is proposed in this paper. It is an indirect all‐quad mesh generation and presented in the following steps: (1) discretizing the constrained lines within the domain; (2) converting the above domain to a triangular mesh together with the line constraints; (3) transforming the generated triangular mesh with line constraints to an all‐quad mesh through performing an advancing front algorithm from the line constraints, which enables the construction of quadrilaterals layer by layer, and roughly keeps the feature of the initial triangular mesh; (4) optimizing the topology of the quadrilateral mesh to reduce the number of irregular nodes; (5) smoothing the generated mesh toward high‐quality all‐quad mesh generation. Finally, a few application examples are given to demonstrate the reliability and usefulness of the proposed algorithm. Copyright © 2011 John Wiley & Sons, Ltd.     

NURBS曲面的四边形网格的分割与逼近

介绍了一个用于对NURBS曲面进行四边形网格的分割与逼近的算法。该算法采用二叉树递归分割的方法分割和逼近曲面，所分割的四边形除了在高度方向和曲面边界处满足给定精度外，同时在四边形四条边界满足给定的切矢精度。实例测试结果表明，用本文所述算法生成的四边形网格具有网格逼近原曲面、网格四边形接近于规则四边形等特点。     

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.     

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.     

LayTracks: a new approach to automated geometry adaptive quadrilateral mesh generation using medial axis transform

A new mesh generation algorithm called ‘LayTracks’, to automatically generate an all quad mesh that is adapted to the variation of geometric feature size in the domain is described. LayTracks combines the merits of two popular direct techniques for quadrilateral mesh generation—quad meshing by decomposition and advancing front quad meshing. While the MAT has been used for the domain decomposition before, this is the first attempt to use the MAT, for the robust subdivision of a complex domain into a well defined sub‐domain called ‘Tracks’, for terminating the advancing front of the mesh elements without complex interference checks and to use radius function for providing sizing function for adaptive meshing. The process of subdivision of a domain is analogous to, formation of railway tracks by laying rails on the ground. Each rail starts from a node on the boundary and propagates towards the medial axis (MA) and then from the MA towards the boundary. Quadrilateral elements are then obtained by placing nodes on these rails and connecting them inside each track, formed by adjacent rails. The algorithm has been implemented and tested on some typical geometries and the quality of the output mesh obtained are presented. Extension of this technique to all hexahedral meshing is discussed. Copyright © 2004 John Wiley & Sons, Ltd.     

An algorithm to generate quadrilateral or triangular element surface meshes in arbitrary domains with applications to crack propagation

A new hybrid algorithm for automatically generating either an all-quadrilateral or an all-triangular element mesh within an arbitrarily shaped domain is described. The input consists of one or more closed loops of straight-line segments that bound the domain. Internal mesh density is inferred from the boundary density using a recursive spatial decomposition (quadtree) procedure. All-triangular element meshes are generated using a boundary contraction procedure. All-quadrilateral element meshes are generated by modifying the boundary contraction procedure to produce a mixed element mesh at half the density of the final mesh and then applying a polygon-splitting procedure. The final meshes exhibit good transitioning properties and are compatible with the given boundary segments which are not altered. The algorithm can support discrete crack growth simulation wherein each step of crack growth results in an arbitrarily shaped region of elements deleted about each crack tip. The algorithm is described and examples of the generated meshes are provided for a representative selection of cracked and uncracked structures.     

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.     

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

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.     

高精度自适应的四边形网格重建

提出了海量数据点集的四边形网格重建算法。首先根据精度要求简化数据点,按一定规则连接相邻的简化数据点生成多边形网格,对网格中高斯曲率较大的顶点进行局部细分提高其精度,然后对多边形网格进行整体细分使其全部转化为四边形网格,最后分裂度较大的顶点对其进行优化。实验结果表明,算法对拓扑结构较为复杂的海量数据点集的四边形网格重建是行之有效的。     

Quadrilateral approaches for accurate free mesh method

This paper presents the formulation of free mesh method and two approaches of the method by incorporating quadrilateral elements. The approaches do not have any difference with the original free mesh method in their fundamental algorithms, wherein local system equations with triangular elements are created nodewise to create the global system equations, and their implementation is therefore very easy. The first approach creates quadrilateral elements inside every triangular element, whilst quadrilateral elements are generated outside every triangular element in the second approach. The results of numerical examples indicate that the approaches improve the accuracy of free mesh method, further opening the possibility for more improvement using an accurate quadrilateral element. Copyright © 2000 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.     

任意平面区域的变密度四边形网格生成方法

：基于三角形网格的合并方法,首先生成光滑过渡的变密度三角形网格,然后进行三角形的合并,接着将合并后残留的三角形细分成三个较小的四边形,相应把合并生成的四边形进一步细分成四个较小的四边形,最终生成了光滑过渡的四边形网格。     

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.     

Converting an unstructured quadrilateral mesh to a standard T-spline surface

This paper presents a novel method for converting any unstructured quadrilateral mesh to a standard T-spline surface, which is C ²-continuous except for the local region around each extraordinary node. There are two stages in the algorithm: the topology stage and the geometry stage. In the topology stage, we take the input quadrilateral mesh as the initial T-mesh, design templates for each quadrilateral element type, and then standardize the T-mesh by inserting nodes. One of two sufficient conditions is derived to guarantee the generated T-mesh is gap-free around extraordinary nodes. To obtain a standard T-mesh, a second sufficient condition is provided to decide what T-mesh configuration yields a standard T-spline. These two sufficient conditions serve as a theoretical basis for our template development and T-mesh standardization. In the geometry stage, an efficient surface fitting technique is developed to improve the geometric accuracy. In addition, the surface continuity around extraordinary nodes can be improved by adjusting surrounding control nodes. The algorithm can also preserve sharp features in the input mesh, which are common in CAD (Computer Aided Design) models. Finally, a Bézier extraction technique is used to facilitate T-spline based isogeometric analysis. Several examples are tested to show the robustness of the algorithm.     

基于黎曼度量参数曲面四边形网格生成方法及UG实现

论文给出了基于黎曼度量的参数曲面网格生成的改进铺砖算法。阐述了曲面自身的黎曼度量,并且运用黎曼度量计算二维参数域上单元节点的位置,从而使映射到三维物理空间的四边形网格形状良好。文中对原有铺砖法相交处理进行了改进,在运用铺砖法的同时调用UG-NX强大的二次开发库函数获取相应的信息,直接在UG-NX模型的表面生成四边形网格。算例表明,该法能在曲面上生成质量好的网格。     

THE WHISKER WEAVING ALGORITHM: A CONNECTIVITY-BASED METHOD FOR CONSTRUCTING ALL-HEXAHEDRAL FINITE ELEMENT MESHES

This paper introduces a new algorithm called whisker weaving for constructing unstructured, all-hexahedral finite element meshes. Whisker weaving is based on the Spatial Twist Continuum (STC), a global interpretation of the geometric dual of an all-hexahedral mesh. Whisker weaving begins with a closed, all-quadrilateral surface mesh bounding a solid geometry, then constructs hexahedral element connectivity advancing into the solid. The result of the whisker weaving algorithm is a complete representation of hex mesh connectivity only: Actual mesh node locations are determined afterwards. The basic step of whisker weaving is to form a hexahedral element by crossing or intersecting dual entities. This operation, combined with seaming or joining operations in dual space, is sufficient to mesh simple block problems. When meshing more complex geometries, certain other dual entities appear such as blind chords, merged sheets, and self-intersecting chords. Occasionally specific types of invalid connectivity arise. These are detected by a general method based on repeated STC edges. This leads into a strategy for resolving some cases of invalidities immediately. The whisker weaving implementation has so far been successful at generating meshes for simple block-type geometries and for some non-block geometries. Mesh sizes are currently limited to a few hundred elements. While the size and complexity of meshes generated by whisker weaving are currently limited, the algorithm shows promise for extension to much more general problems.