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.     

Generation and optimization of tetrahedral meshes by advancing front technique

An algorithm for tetrahedron mesh generation and optimization with respect to a shape and a size criterion is presented. A well distributed set of nodes is first generated by an octree method, and the set is then triangulated. The advancing front technique is used to mesh the whole volume. Emphasis has been placed on management of the front. The method involves priority construction of enhanced quality tetrahedra. Each face is assigned to a front corresponding to the quality of the best tetrahedron which can be constructed. Elements are destroyed in the case of non-convergence. Optimization procedures make local use of the algorithm used to mesh the complete model. Industrial examples of relatively complex volumes are given, demonstrating that a high quality and optimized mesh can be obtained by the proposed method. © 1998 John Wiley & Sons, Ltd.     

Multi-time-step integration using nodal partitioning

An algorithm is presented which integrates different groups of nodes of a finite element mesh with different time steps and different integrators. Since the nodal groups are updated independently no unsymmetric systems need be solved. Stability is demonstrated by showing that an energy norm of the solution decreases after every update if the time step is less than a given critical value. The element eigenvalue inequality theorem is used to give the critical time step in terms of element eigenvalues.     

A distortion measure to validate and generate curved high‐order meshes on CAD surfaces with independence of parameterization

A framework to validate and generate curved nodal high‐order meshes on Computer‐Aided Design (CAD) surfaces is presented. The proposed framework is of major interest to generate meshes suitable for thin‐shell and 3D finite element analysis with unstructured high‐order methods. First, we define a distortion (quality) measure for high‐order meshes on parameterized surfaces that we prove to be independent of the surface parameterization. Second, we derive a smoothing and untangling procedure based on the minimization of a regularization of the proposed distortion measure. The minimization is performed in terms of the parametric coordinates of the nodes to enforce that the nodes slide on the surfaces. Moreover, the proposed algorithm repairs invalid curved meshes (untangling), deals with arbitrary polynomial degrees (high‐order), and handles with low‐quality CAD parameterizations (independence of parameterization). Third, we use the optimization procedure to generate curved nodal high‐order surface meshes by means of an a posteriori approach. Given a linear mesh, we increase the polynomial degree of the elements, curve them to match the geometry, and optimize the location of the nodes to ensure mesh validity. Finally, we present several examples to demonstrate the features of the optimization procedure, and to illustrate the surface mesh generation process. Copyright © 2015 John Wiley & Sons, Ltd.     

基于向量夹角的三角网格模型简化算法

提出以顶点向量夹角为剔除准则,运用顶点去除方法进行网格简化的算法。该算法首先计算每个网格顶点与其周围相邻顶点所形成的方向向量,然后根据方向向量的平均夹角来识别和简化网格中的平面区域,之后再以该顶点所处区域是否比较平坦为顶点去除限制条件,判断该顶点是否符合安全去除原则,这样可以保留特征顶点,进而保持物体的视觉特征。在顶点去除后,还需要对因此而形成的多边形进行三角形网格重建,以填补空洞。该算法在简化质量和简化速率方面取得了较好的平衡。     

Automatic element reordering for finite element analysis with frontal solution schemes

This paper describes an element reordering algorithm which is suitable for use with a frontal solution package. The procedure is shown to generate efficient element numberings for a wide variety of test examples. In an effort to obtain an optimum elimination order, the algorithm first renumbers the nodes, and then uses this result to resequence the elements. This intermediate step is necessary because of the nature of the frontal solution procedure, which assembles variables on an element-by-element basis but eliminates them node by node. To renumber the nodes, a modified version of the King¹ algorithm is used. In order to minimize the number of nodal numbering schemes that need to be considered, the starting nodes are selected automatically by using some concepts from graph theory. Once the optimum numbering sequence has been ascertained, the elements are then reordered in an ascending sequence of their lowest-numbered nodes. This ensures that the new elimination order is preserved as closely as possible. For meshes that are composed of a single type of high-order element, it is only necessary to consider the vertex nodes in the renumbering process. This follows from the fact that mesh numberings which are optimal for low-order elements are also optimal for high-order elements. Significant economies in the reordering strategy may thus be achieved. A computer implementation of the algorithm, written in FORTRAN IV, is given.     

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 motion techniques for the ALE formulation in 3D large deformation problems

Efficient mesh motion techniques are a key issue to achieve satisfactory results in the arbitrary Lagrangian–Eulerian (ALE) finite element formulation when simulating large deformation problems such as metal‐forming. In the updated Lagrangian (UL) formulation, mesh and material movement are attached and an excessive mesh distortion usually appears. By uncoupling mesh movement from material movement, the ALE formulation can relocate the mesh to avoid distortion. To facilitate the calculation process, the ALE operator is split into two steps at each analysis time step: UL step (where deformation due to loading is calculated without convective terms) and Eulerian step (where mesh motion is applied). In this work, mesh motion is performed by new nodal relocation methods, developed for eight‐node hexahedral elements, which can move internal and boundary nodes, improving and concentrating the mesh in critical zones. After mesh motion, data is transferred from the UL mesh to the relocated mesh using an expansion of stresses in a Taylor's series. Two numerical applications are presented, comparing results of UL and ALE formulation with results found in the literature. Copyright © 2004 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.     

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.     

Stability of an explicit multi-time step integration algorithm for linear structural dynamics equations

A proof of stability is developed for an explicit multi-time step integration method of the second order differential equations which result from a semidiscretization of the equations of structural dynamics. The proof is applicable to an algorithm that partitions the mesh into subdomains according to nodal groups which are updated with different time steps. The stability of the algorithm is demonstrated by showing that the eigenvalues of the amplification matrices lie within the unit circle and that a pseudo-energy remains constant. Bounds on the stable time steps for the nodal partitions are developed in terms of element frequencies.     

Anisotropic tetrahedral meshing via bubble packing and advancing front

This paper presents a new computational method for anisotropic tetrahedral meshing. The method can control element anisotropy based on a specified 3×3 tensor field defined over a volumetric domain. Our method creates a tetrahedral mesh in two steps: (1) placing nodes at the centres of tightly packed ellipsoidal cells, called bubbles, in the domain, and (2) connecting the nodes by a modified advancing front followed by local transformation. The method creates a high‐quality anisotropic mesh that conforms well to a specified tensor field. Copyright © 2003 John Wiley & Sons, Ltd.     

A three-step renumbering procedure for high-order finite element analysis

An efficient renumbering method for high-order finite element models is presented. The method can be used to reduce the profile and wavefront of a coefficient matrix arising in high-order finite element computation. The method indirectly performs node renumbering and involves three main steps. In the first step, nodes at corners of the elements are numbered using an existing renumbering algorithm. In the second step, elements are numbered in an ascending order of their least new corner node numbers. Finally, based on the new element numbers, both corner and non-corner nodes are renumbered using an algorithm that simulates the node elimination procedure in a frontal solution method. The method is compared to the algorithms that directly perform node renumbering. The numerical results indicate that the three-step algorithm presented here is an order of magnitude faster and the resulting renumbering produces excellent profile and wavefront characteristics of the coefficient matrix. © 1998 John Wiley & Sons, Ltd.     

A Strategy to Support Design Processes for Fibre Reinforced Thermoset Composite Materials

The concept stage in the design for a new composite part is a time when several fundamental decisions must be taken and a considerable amount of the budget is spent. Specialized commercial software packages can be used to support the decision making process in particular aspects of the project (e.g. material selection, numerical analysis, cost prediction,...). However, a complete and integrated virtual environment that covers all the steps in the process is not yet available for the composite design and manufacturing industry. This paper does not target the creation of such an overarching virtual tool, but instead presents a strategy that handles the information generated in each step of the design process, independently of the commercial packages used. Having identified a suitable design parameter shared in common with all design steps, the proposed strategy is able to evaluate the effects of design variations throughout all the design steps in parallel. A case study illustrating the strategy on an industrial part is presented.     

Three‐dimensional grayscale‐free topology optimization using a level‐set based r‐refinement method

In this paper, we propose a three‐dimensional (3D) grayscale‐free topology optimization method using a conforming mesh to the structural boundary, which is represented by the level‐set method. The conforming mesh is generated in an r‐refinement manner; that is, it is generated by moving the nodes of the Eulerian mesh that maintains the level‐set function. Although the r‐refinement approach for the conforming mesh generation has many benefits from an implementation aspect, it has been considered as a difficult task to stably generate 3D conforming meshes in the r‐refinement manner. To resolve this task, we propose a new level‐set based r‐refinement method. Its main novelty is a procedure for minimizing the number of the collapsed elements whose nodes are moved to the structural boundary in the conforming mesh; in addition, we propose a new procedure for improving the quality of the conforming mesh, which is inspired by Laplacian smoothing. Because of these novelties, the proposed r‐refinement method can generate 3D conforming meshes at a satisfactory level, and 3D grayscale‐free topology optimization is realized. The usefulness of the proposed 3D grayscale‐free topology optimization method is confirmed through several numerical examples. Copyright © 2017 John Wiley & Sons, Ltd.     

Asynchronous collision integrators: Explicit treatment of unilateral contact with friction and nodal restraints

This article presents asynchronous collision integrators and a simple asynchronous method treating nodal restraints. Asynchronous discretizations allow individual time step sizes for each spatial region, improving the efficiency of explicit time stepping for finite element meshes with heterogeneous element sizes. The article first introduces asynchronous variational integration being expressed by drift and kick operators. Linear nodal restraint conditions are solved by a simple projection of the forces that is shown to be equivalent to RATTLE. Unilateral contact is solved by an asynchronous variant of decomposition contact response. Therein, velocities are modified avoiding penetrations. Although decomposition contact response is solving a large system of linear equations (being critical for the numerical efficiency of explicit time stepping schemes) and is needing special treatment regarding overconstraint and linear dependency of the contact constraints (for example from double‐sided node‐to‐surface contact or self‐contact), the asynchronous strategy handles these situations efficiently and robust. Only a single constraint involving a very small number of degrees of freedom is considered at once leading to a very efficient solution. The treatment of friction is exemplified for the Coulomb model. Special care needs the contact of nodes that are subject to restraints. Together with the aforementioned projection for restraints, a novel efficient solution scheme can be presented. The collision integrator does not influence the critical time step. Hence, the time step can be chosen independently from the underlying time‐stepping scheme. The time step may be fixed or time‐adaptive. New demands on global collision detection are discussed exemplified by position codes and node‐to‐segment integration. Numerical examples illustrate convergence and efficiency of the new contact algorithm. Copyright © 2013 The Authors. International Journal for Numerical Methods in Engineering published by 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.     

Rapid re-meshing and re-solution of three-dimensional boundary element problems for interactive stress analysis

Structural design of mechanical components is an iterative process that involves multiple stress analysis runs; this can be time consuming and expensive. It is becoming increasingly possible to make significant improvements in the efficiency of this process by increasing the level of interactivity. One approach is through real-time re-analysis of models with continuously updating geometry. A key part of such a strategy is the ability to accommodate changes in geometry with minimal perturbation to an existing mesh. This work introduces a new re-meshing algorithm that can generate and update a boundary element mesh in real-time as a series of small changes are sequentially applied to the associated model. The algorithm is designed to make minimal updates to the mesh between each step whilst preserving a suitable mesh quality that retains accuracy in the stress results. This significantly reduces the number of terms that need to be updated in the system matrix, thereby reducing the time required to carry out a re-analysis of the model. A range of solvers are assessed to find the most efficient and robust method of re-solving the system. The GMRES algorithm, using complete approximate LU preconditioning, is found to provide the fastest convergence rate.