Hexahedral mesh smoothing via local element regularization and global mesh optimization

The quality of finite element meshes is one of the key factors that affect the accuracy and reliability of finite element analysis results. In order to improve the quality of hexahedral meshes, we present a novel hexahedral mesh smoothing algorithm which combines a local regularization for each hexahedral mesh, using dual element based geometric transformation, with a global optimization operator for all hexahedral meshes. The global optimization operator is composed of three main terms, including the volumetric Laplacian operator of hexahedral meshes and the geometric constraints of surface meshes which keep the volumetric details and the surface details, and another is the transformed node displacements condition which maintains the regularity of all elements. The global optimization operator is formulated as a quadratic optimization problem, which is easily solved by solving a sparse linear system. Several experimental results are presented to demonstrate that our method obtains higher quality results than other state-of-the-art approaches.     

Seams and wedges in plastering: A 3-D hexahedral mesh generation algorithm

This paper describes mesh correction techniques necessary for meshing an arbitrary volume with a completely hexahedral mesh. Specifically, it describes seams and wedges, mechanisms that overcome major hurdles encountered in the preliminary work on the plastering algorithm. The plastering algorithm iteratively projects layers of elements inward from a quadrilateral discretization of the volume's bounding faces. Seams and wedges resolve incompatibilities in the mesh and in the progressing boundary, thus ensuring the correct formation of a hexahedral mesh from the plastering algorithm.     

子分元素法:一种体网格压缩算法

提出了一个包含六面体,四面体,金字塔以及三棱柱单元的混合体网格的压缩与解压算法。首先对非四面体单元按照最小节点标号策略进行子分,然后利用修改的增长缝合算法压缩子分后的四面体网格,解压阶段再通过面删除操作来恢复原始网格。压缩后每个四面体约需10bits的存储,初步试验表明,对于通常的六面体网格,能将数据模型压缩至原先的1／4。     

Hexahedral mesh generation constraints

For finite element analyses within highly elastic and plastic structural domains, hexahedral meshes have historically offered some benefits over tetrahedral finite element meshes in terms of reduced error, smaller element counts, and improved reliability. However, hexahedral finite element mesh generation continues to be difficult to perform and automate, with hexahedral mesh generation taking several orders of magnitude longer than current tetrahedral mesh generators to complete. Thus, developing a better understanding of the underlying constraints that make hexahedral meshing difficult could result in dramatic reductions in the amount of time necessary to prepare a hexahedral finite element model for analysis. In this paper, we present a survey of constraints associated with hexahedral meshes (i.e., the conditions that must be satisfied to produce a hexahedral mesh). In presenting our formulation of these constraints, we will utilize the dual of a hexahedral mesh. We also discuss how incorporation of these constraints into existing hexahedral mesh generation algorithms could be utilized to extend the class of geometries to which these algorithms apply. We also describe a list of open problems in hexahedral mesh generation and give some context for future efforts in addressing these problems.     

All-hexahedral mesh generation via inside-out advancing front based on harmonic fields

The generation of hexahedral meshes is an open problem that has undergone significant research. This paper deals with a novel inside-out advancing front method to generate unstructured all-hexahedral meshes for given volumes. Two orthogonal harmonic fields, principal and radial harmonic fields, are generated to guide the inside-out advancing front process based on a few user interactions. Starting from an initial hexahedral mesh inside the given volume, we advance the boundary quadrilateral mesh along the streamlines of radial field and construct layers of hexahedral elements. To ensure high quality and uniform size of the hexahedral mesh, quadrilateral elements are decomposed in such a way that no non-hexahedral element is produced. For complex volume with branch structures, we segment the complex volume into simple sub-volumes that are suitable for our method. Experimental results show that our method generates high quality all-hexahedral meshes for the given volumes.     

Anisotropic quadrilateral mesh generation: An indirect approach

In this paper a new indirect approach is presented for anisotropic quadrilateral mesh generation based on discrete surfaces. The ability to generate grids automatically had a pervasive influence on many application areas in particularly in the field of Computational Fluid Dynamics. In spite of considerable advances in automatic grid generation there is still potential for better performance and higher element quality. The aim is to generate meshes with less elements which fit some anisotropy criterion to satisfy numerical accuracy while reducing processing times remarkably. The generation of high quality volume meshes using an advancing front algorithm relies heavily on a well designed surface mesh. For this reason this paper presents a new technique for the generation of high quality surface meshes containing a significantly reduced number of elements. This is achieved by creating quadrilateral meshes that include anisotropic elements along a source of anisotropy.     

A methodology for quadrilateral finite element mesh coarsening

High fidelity finite element modeling of continuum mechanics problems often requires using all quadrilateral or all hexahedral meshes. The efficiency of such models is often dependent upon the ability to adapt a mesh to the physics of the phenomena. Adapting a mesh requires the ability to both refine and/or coarsen the mesh. The algorithms available to refine and coarsen triangular and tetrahedral meshes are very robust and efficient. However, the ability to locally and conformally refine or coarsen all quadrilateral and all hexahedral meshes presents many difficulties. Some research has been done on localized conformal refinement of quadrilateral and hexahedral meshes. However, little work has been done on localized conformal coarsening of quadrilateral and hexahedral meshes. A general method which provides both localized conformal coarsening and refinement for quadrilateral meshes is presented in this paper. This method is based on restructuring the mesh with simplex manipulations to the dual of the mesh. In addition, this method appears to be extensible to hexahedral meshes in three dimensions. Sandia National Laboratories is a multiprogram laboratory operated by Sandia Corporation, a Lockheed Martin Company, for the United States Department of Energy under Contract DE-AC04-94AL85000.     

Parallel quadrilateral subdomain generation for finite element analysis

In this article the Sub-domain Generation Method (SGM) previously developed for finite element meshes composed of triangular elements is generalised to account for meshes composed of arbitrary quadrilateral elements. A neural network of enhanced accuracy was developed to predict the number of quadrilaterals generated within each coarse quadrilateral element after refinement using an adaptive re-meshing procedure. Partitioning of the meshes was undertaken on the coarse mesh using a genetic algorithm to optimise the partitions considering both load balancing and interprocessor communication of the subsequent finite element analysis. A series of examples of increasing refinement were decomposed by considering a single coarse mesh of a fixed number of elements.     

An approach to automated decomposition of volumetric mesh

Mesh decomposition is critical for analyzing, understanding, editing and reusing of mesh models. Although there are many methods for mesh decomposition, most utilize only triangular meshes. In this paper, we present an automated method for decomposing a volumetric mesh into semantic components. Our method consists of three parts. First, the outer surface mesh of the volumetric mesh is decomposed into semantic features by applying existing surface mesh segmentation and feature recognition techniques. Then, for each recognized feature, its outer boundary lines are identified, and the corresponding splitter element groups are setup accordingly. The inner volumetric elements of the feature are then obtained based on the established splitter element groups. Finally, each splitter element group is decomposed into two parts using the graph cut algorithm; each group completely belongs to one feature adjacent to the splitter element group. In our graph cut algorithm, the weights of the edges in the dual graph are calculated based on the electric field, which is generated using the vertices of the boundary lines of the features. Experiments on both tetrahedral and hexahedral meshes demonstrate the effectiveness of our method.     

Motorcycle graph enumeration from quadrilateral meshes for reverse engineering

Recently proposed quad-meshing techniques allow the generation of high-quality semi-regular quadrilateral meshes. This paper outlines the generation of quadrilateral segments using such meshes. Quadrilateral segments are advantageous in reverse engineering because they do not require surface trimming or surface parameterization. The motorcycle graph algorithm of Eppstein et al. produces the motorcycle graph of a given quadrilateral mesh consisting of quadrilateral segments. These graphs are preferable to base complexes, because the mesh can be represented with a smaller number of segments, as T-joints (where the intersection of two neighboring segments does not involve the whole edge or the vertex) are allowed in quadrilateral segmentation.The proposed approach in this study enumerates all motorcycle graphs of a given quadrilateral mesh and optimum graph for reverse engineering is then selected. Due to the high computational cost of enumerating all these graphs, the mesh is cut into several sub-meshes whose motorcycle graphs are enumerated separately. The optimum graph is then selected based on a cost function that produces low values for graphs whose edges trace a large number of highly curved regions in the model. By applying several successive enumeration steps for each sub-mesh, a motorcycle graph for the given mesh is found. We also outline a method for the extraction of feature curves (sets of highly curved edges) and their integration into the proposed algorithm. Quadrilateral segments generated using the proposed techniques are validated by B-spline surfaces.     

The All-Hex Geode-Template for Conforming a Diced Tetrahedral Mesh to any Diced Hexahedral Mesh

Take a hexahedral mesh and an adjoining tetrahedral mesh that splits each boundary quadrilateral into two triangles. Separate the meshes with a buffer layer of hexes. Dice the original hexes into eight, and the tetrahedra into four hexahedra. Then I show that the buffer layer hexes can be filled with the geode-template, creating a conforming all-hex mesh of the entire model. The geode-template is composed of 26 hexahedra. The hexahedra have acceptable quality, depending on the geometry of the buffer layer. The method used to generate the geode-template is general, based on interleaving completed dual surfaces, and might be extended to other transition problems.     

Least-squares approximation of affine mappings for sweep mesh generation: functional analysis and applications

Sweep methods are one of the most robust techniques to generate hexahedral meshes in extrusion volumes. The main issue in sweep algorithms is the projection of cap surface meshes along the sweep path. The most competitive technique to determine this projection is to find a least-squares approximation of an affine mapping. Several functional formulations have been defined to carry out this least-squares approximation. However, these functionals generate unacceptable meshes for several common geometries in CAD models. In this paper we present a new comparative analysis between these classical functional formulations and a new functional presented by the authors. In particular, we prove under which conditions the minimization of the analyzed functionals leads to a full rank linear system. Moreover, we also prove the equivalences between these formulations. These allow us to point out the advantages of the proposed functional. Finally, from this analysis we outline an automatic algorithm to compute the nodes location in the inner layers.     

Face coloring in unstructured CFD codes

We propose an algorithm for preventing race conditions in the evaluation of the surface integral contributions in edge-based CFD solvers by coloring the faces (or edges) of the computational mesh. We use a partitioning algorithm that separates the edges of triangular elements into three groups, the faces of quadrilateral and tetrahedral elements into four groups, and the faces of hexahedral elements into six groups. Our method is also applicable to hybrid meshes. We then extend this partitioning to adaptively refined, nonconforming meshes. We use the coloring to reduce code memory requirements by eliminating buffering. The coloring is also used to renumber and reorder elemental data to optimize reading and writing to memory, thus reducing access latencies and accelerating computations.     

A grid-based algorithm for the generation of hexahedral element meshes

An algorithm for the generation of hexahedralelement meshes is presented. The algorithm works in two steps: first the interior of the volume is filled with a regular grid; then the boundary region is meshed by using basically twodimensional operations.The algorithm was designed for use in the fem-simulation of metal forming processes where a remeshing must be done very often. In principle, it can be used for meshing any geometry with hexahedral elements and examples of meshes for geometries arising from various applications are given. The algorithm is checked against the criteria proposed by Sabin [1] (Advances in Engineering Software, 13, 220–225).     

A strategy of automatic hexahedral mesh generation by using an improved whisker-weaving method with a surface mesh modification procedure

One of the demands for three dimensional (3D) finite element analyses is the development of an automatic hexahedral mesh generator. For this problem, several methods have been proposed by many researchers. However, reliable automatic hexahedral mesh generation has not been developed at present. In this paper, a new strategy of fully automatic hexahedral mesh generation is proposed. In this strategy, the prerequisite for generating a hexahedral mesh is a quadrilateral surface mesh. From the given surface mesh, combinatorial dual cycles (sheet loops for the whisker-weaving algorithm) are generated to produce a hexahedral mesh. Since generating a good quality hexahedral mesh does not depend only on the quality of quadrilaterals of the surface mesh but also on the quality of the sheet loops generated from it, a surface mesh modification method to remove self-intersections from sheet loops is developed. Next, an automatic hexahedral mesh generator by the improved whisker-weaving algorithm is developed in this paper. By creating elements and nodes on 3D real space during the weaving process, it becomes possible to generate a hexahedral mesh with fewer bad-quality elements. Several examples will be presented to show the validity of the proposed mesh generation strategy.     

Global Structure Optimization of Quadrilateral Meshes

We introduce a fully automatic algorithm which optimizes the high‐level structure of a given quadrilateral mesh to achieve a coarser quadrangular base complex. Such a topological optimization is highly desirable, since state‐of‐the‐art quadrangulation techniques lead to meshes which have an appropriate singularity distribution and an anisotropic element alignment, but usually they are still far away from the high‐level structure which is typical for carefully designed meshes manually created by specialists and used e.g. in animation or simulation. In this paper we show that the quality of the high‐level structure is negatively affected by helical configurations within the quadrilateral mesh. Consequently we present an algorithm which detects helices and is able to remove most of them by applying a novel grid preserving simplification operator (GP‐operator) which is guaranteed to maintain an all‐quadrilateral mesh. Additionally it preserves the given singularity distribution and in particular does not introduce new singularities. For each helix we construct a directed graph in which cycles through the start vertex encode operations to remove the corresponding helix. Therefore a simple graph search algorithm can be performed iteratively to remove as many helices as possible and thus improve the high‐level structure in a greedy fashion. We demonstrate the usefulness of our automatic structure optimization technique by showing several examples with varying complexity.     

A two-dimensional paving mesh generator for triangles with controllable aspect ratio and quadrilaterals with high quality

Certain classes of problems result in solution fields of which the characteristic length scales vary with the orientation. Often the orientation of these length scales is related to the orientation of the boundaries. Such solution fields can be captured by the finite element method, using a mesh that is refined in the direction of the short length scales and coarse in the other directions. These meshes contain elements with high aspect ratios in a predefined pattern.The mesh generator presented here can render triangles with high aspect ratios through a paving algorithm. The paving algorithm that is employed applies both triangles and quadrilaterals, combining the advantages of both to render a qualitatively good, oriented triangular mesh, with a concentration of elements in the direction where the internal length scales of the solution field are the shortest.The mesh generator produces triangles with one (almost) orthogonal corner. When low aspect ratio triangles are generated, these are well suited for conversion to quadrilateral elements. Test results indicate that quadrilateral meshes converted from the mesh generator introduced here have a considerably better quality than those converted from several other triangular mesh generators.     

Hexahedral and Tetrahedral Mesh Untangling

We investigate a well-motivated mesh untangling objective function whose optimization automatically produces non-inverted elements when possible. Examples show the procedure is highly effective on tetrahedral meshes and on many hexahedral meshes constructed via mapping or sweeping algorithms.     

Localized coarsening of conforming all-hexahedral meshes

Finite element mesh adaptation methods can be used to improve the efficiency and accuracy of solutions to computational modeling problems. In many applications involving hexahedral meshes, localized modifications which preserve a conforming all-hexahedral mesh are desired. Effective hexahedral refinement methods that satisfy these criteria have recently become available; however, due to hexahedral mesh topology constraints, little progress has been made in the area of hexahedral coarsening. This paper presents a new method to locally coarsen conforming all-hexahedral meshes. The method works on both structured and unstructured meshes and is not based on undoing previous refinement. Building upon recent developments in quadrilateral coarsening, the method utilizes hexahedral sheet and column operations, including pillowing, column collapsing, and sheet extraction. A general algorithm for automated coarsening is presented and examples of models that have been coarsened with this new algorithm are shown. While results are promising, further work is needed to improve the automated process.     

Automatic unstructured all-hexahedral mesh generation from B-Reps for non-manifold CAD assemblies

This paper describes an automatic and robust approach to convert non-manifold CAD assemblies into unstructured all-hexahedral meshes conformal to the given B-Reps (boundary-representations) and with sharp feature preservation. In previous works, we developed an octree-based isocontouring method to construct unstructured hexahedral meshes for arbitrary non-manifold and manifold domains. However, sharp feature preservation still remains a challenge, especially for non-manifold CAD assemblies. In this paper, boundary features such as NURBS (non-uniform rational B-Splines) curves and surface patches are first extracted from the given B-Reps. Features shared by multiple components are identified and distinguished. To preserve these non-manifold features, one given surface patch may need to be split into several small ones. An octree-based algorithm is then carried out to create an unstructured all-hexahedral base mesh, detecting and preserving all the sharp features via a curve and surface parametrization. Two sets of local refinement templates are provided for adaptive mesh generation, along with a novel 2-refinement implementation. Vertices in the base mesh are categorized into four groups based on the given non-manifold topology, and each group is relocated using various methods with all sharp features preserved. After this stage, a novel two-step pillowing technique is developed for such complicated non-manifold domains to eliminate triangle-shaped quadrilateral elements along the curves and “doublets”, handling non-manifold and manifold features in different ways. Finally, a combination of smoothing and optimization is used to further improve the mesh quality. Our algorithm is automatic and robust for non-manifold and manifold domains. We have applied our algorithm to several complicated CAD assemblies.