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.     

A control approach for pore size distribution in the bone scaffold based on the hexahedral mesh refinement

Tissue engineering is the application of that knowledge to the building or repairing of tissues. Generally, engineered tissue is a combination of living cells and a support structure called scaffolds. Modeling, design and fabrication of tissue scaffold with intricate architecture, porosity and pore size for desired tissue properties presents a challenge in tissue engineering. In this paper, a control approach for pore size distribution in the bone scaffold based on the hexahedral mesh refinement is presented. Firstly, the bone scaffold modeling approach based on the shape function in the finite element method is provided. The resulting various macroporous morphologies can be obtained. Then conformal refinement algorithm for all-hexahedral element mesh is illustrated. Finally, a modeling approach for constructing tissue engineering (TE) bone scaffold with defined pore size distribution is presented. Before the conformal refinement of all-hexahedral element mesh, a 3D mesh with various hexahedral elements must be provided. If all the pores in the bone scaffold need to be reduced, that means that the whole hexahedral mesh needs to be refined. Then the solid entity can be re-divided with altered subdivision parameters. If the pores in the local regions of bone need to be reduced, that means that 3D hexahedral mesh in the local regions needs to be refined. Based on SEM images, the pore size distribution in the normal bone can be obtained. Then, according to the conformal refinement of all-hexahedral element meshes, defined hexahedral size distribution can be gained, which leads to generate defined pore size distribution in the bone scaffold, for the pore morphology and size are controlled by various subdivided hexahedral elements. Compared to other methods such as varying processing parameters in supercritical fluid processing and multi-interior architecture design, the method proposed in this paper enjoys easy-controllability and higher accuracy.     

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.     

Three dimensional discontinuous Galerkin methods for Euler equations on adaptive conforming meshes

In the numerical simulation of three dimensional fluid dynamical equations, the huge computational quantity is a main challenge. In this paper, the discontinuous Galerkin (DG) finite element method combined with the adaptive mesh refinement (AMR) is studied to solve the three dimensional Euler equations based on conforming unstructured tetrahedron meshes, that is according the equation solution variation to refine and coarsen grids so as to decrease total mesh number. The four space adaptive strategies are given and analyzed their advantages and disadvantages. The numerical examples show the validity of our methods.     

MOAB-SD: integrated structured and unstructured mesh representation

Structured and semi-structured (a.k.a. swept or extruded) hexahedral meshes are used in many types of engineering analysis. In finite element analysis, regions of structured and semi-structured mesh are often connected in an unstructured manner, preventing the use of a globally consistent parametric space to represent these meshes. This paper describes a method for mapping between the parametric spaces of such regions, and methods for representing these regions and interfaces between them. Using these methods, a 57% reduction in mesh storage cost is demonstrated, without loss of any information. These methods have been implemented in the MOAB mesh database component, which provides access to these meshes from both structured and unstructured functions. The total cost for representing structured mesh in MOAB is less than 25 MB per million elements using double-precision vertex coordinates; this is only slightly larger than the space required to store vertex coordinates alone.Sandia is a multiprogram laboratory operated by Sandia corporation, a Lockheed Martin company, for the United States department of energy under contract DE-AC04-94AL85000. This work was performed under the auspices of the U.S. Department of Energy, Office of Advanced Scientific Computing, SciDAL program.     

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.     

Simultaneous untangling and smoothing of quadrilateral and hexahedral meshes using an object-oriented framework

In this work, we present a simultaneous untangling and smoothing technique for quadrilateral and hexahedral meshes. The algorithm iteratively improves a quadrilateral or hexahedral mesh by minimizing an objective function defined in terms of a regularized algebraic distortion measure of the elements. We propose several techniques to improve the robustness and the computational efficiency of the optimization algorithm. In addition, we have adopted an object-oriented paradigm to create a common framework to smooth meshes composed by any type of elements, and using different minimization techniques. Finally, we present several examples to show that the proposed technique obtains valid meshes composed by high-quality quadrilaterals and hexahedra, even when the initial meshes contain a large number of tangled elements.     

A Case Study in Hexahedral Mesh Generation: Simulation of the Human Mandible

We provide a case study for the generation of pure hexahedral meshes for the numerical simulation of physiological stress scenarios of the human mandible. Du to its complex and very detailed free-form geometry, the mandible model is very demanding. This test case is used as a running example to demonstrate the applicability of a combinatorial approach for the generation of hexahedral meshes by means of successive dual cycle eliminations, which has been proposed by the second author in previous work. We report on the progress and recent advances of the cycle elimination scheme. The given input data, a surface triangulation obtained from computed tomography data, requires a substantial mesh reduction and a suitable conversion into a quadrilateral surface mesh as a first step, for which we use mesh clustering and b-matching techniques. Several strategies for improved cycle elimination orders are proposed. They lead to a significant reduction in the mesh size and a better structural quality. Based on the resulting combinatorial meshes, gradient-based optimized smoothing with the condition number of the Jacobian matrix as objective together with mesh untangling techniques yielded embeddings of a satisfactory quality. To test our hexahedral meshes for the mandible model within an FEM simulation we used the scenario of a bite on a ‘hard nut.’ Our simulation results are in good agreement with observations from biomechanical experiments.     

Local refinement of three-dimensional finite element meshes

Mesh refinement is an important tool for editing finite element meshes in order to increase the accuracy of the solution. Refinement is performed in an iterative procedure in which a solution is found, error estimates are calculated, and elements in regions of high error are refined. This process is repeated until the desired accuracy is obtained.Much research has been done on mesh refinement. Research has been focused on two-dimensional meshes and three-dimensional tetrahedral meshes ([1] Ning et al. (1993) Finite Elements in Analysis and Design, 13, 299–318; [2] Rivara, M. (1991) Journal of Computational and Applied Mathematics 36, 79–89; [3] Kallinderis; Vijayar (1993) AIAA Journal,31, 8, 1440–1447; [4] Finite Element Meshes in Analysis and Design,20, 47–70). Some research has been done on three-dimensional hexahedral meshes ([5] Schneiders; Debye (1995) Proceedings IMA Workshop on Modelling, Mesh Generation and Adaptive Numerical Methods for Partial Differential Equations). However, little if any research has been conducted on a refinement algorithm that is general enough to be used with a mesh composed of any three-dimensional element (hexahedra, wedges, pyramids, and/or retrahedra) or any combination of three-dimensional elements (for example, a mesh composed of part hexahedra and part wedges). This paper presents an algorithm for refinement of three-dimensional finite element meshes that is general enough to refine a mesh composed of any combination of the standard three-dimensional element types.     

Fun sheet matching: towards automatic block decomposition for hexahedral meshes

Depending upon the numerical approximation method that may be implemented, hexahedral meshes are frequently preferred to tetrahedral meshes. Because of the layered structure of hexahedral meshes, the automatic generation of hexahedral meshes for arbitrary geometries is still an open problem. This layered structure usually requires topological modifications to propagate globally, thus preventing the general development of meshing algorithms such as Delaunay??s algorithm for tetrahedral meshes or the advancing-front algorithm based on local decisions. To automatically produce an acceptable hexahedral mesh, we claim that both global geometric and global topological information must be taken into account in the mesh generation process. In this work, we propose a theoretical classification of the layers or sheets participating in the geometry capture procedure. These sheets are called fundamental, or fun-sheets for short, and make the connection between the global layered structure of hexahedral meshes and the geometric surfaces that are captured during the meshing process. Moreover, we propose a first generation algorithm based on fun-sheets to deal with 3D geometries having 3- and 4-valent vertices.     

车身冲压模型腔表面四边形网格的局部粗化

给定一车身冲压模型腔表面上结构化的四边形网格，通过单元合并对网格进行自动的粗化，其目的在于简化冲压仿真模型，提高仿真计算速度，首先，根据单元节点曲率半径的分布，搜寻出满足单元合并条件的初始四边形区域，接头，判断初始合交区域的边界过渡条件，最后，进行单合并，冲压成型仿真应用实例证明，文中算法既提高了仿真速度，又保持了仿真精度，该算法可以推广到任意曲面结构化四边形网格的局部粗化问题。     

A constructive approach to constrained hexahedral mesh generation

Mitchell proved that a necessary and sufficient condition for the existence of a topological hexahedral mesh constrained to a quadrilateral mesh on the sphere is that the constraining quadrilateral mesh contains an even number of elements. Mitchell’s proof depends on Smale’s theorem on the regularity of curves on compact manifolds. Although the question of the existence of constrained hexahedral meshes has been solved, the known solution is not easily programmable; indeed, there are cases, such as Schneider’s Pyramid, that are not easily solved. Eppstein later utilized portions of Mitchell’s existence proof to demonstrate that hexahedral mesh generation has linear complexity. In this paper, we demonstrate a constructive proof to the existence theorem for the sphere, as well as assign an upper-bound to the constant of the linear term in the asymptotic complexity measure provided by Eppstein. Our construction generates 76 × n hexahedra elements within the solid where n is the number of quadrilaterals on the boundary. The construction presented is used to solve some problems posed by Schneiders and Eppstein. We will also use the results provided in this paper, in conjunction with Mitchell’s Geode-Template, to create an alternative way of creating a constrained hexahedral mesh. The construction utilizing the Geode-Template requires 130 × n hexahedra, but will have fewer topological irregularities in the final mesh.     

Implicit Hierarchical Quad‐Dominant Meshes

We present a method for producing quad‐dominant subdivided meshes, which supports both adaptive refinement and adaptive coarsening. A hierarchical structure is stored implicitly in a standard half‐edge data structure, while allowing us to efficiently navigate through the different level of subdivision. Subdivided meshes contain a majority of quad elements and a moderate amount of triangles and pentagons in the regions of transition across different levels of detail. Topological LOD editing is controlled with local conforming operators, which support both mesh refinement and mesh coarsening. We show two possible applications of this method: we define an adaptive subdivision surface scheme that is topologically and geometrically consistent with the Catmull–Clark subdivision; and we present a remeshing method that produces semi‐regular adaptive meshes.     

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.     

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.     

The receding front method applied to hexahedral mesh generation of exterior domains

Two of the most successful methods to generate unstructured hexahedral meshes are the grid-based methods and the advancing front methods. On the one hand, the grid-based methods generate high-quality hexahedra in the inner part of the domain using an inside–outside approach. On the other hand, advancing front methods generate high-quality hexahedra near the boundary using an outside–inside approach. To combine the advantages of both methodologies, we extend the receding front method: an inside–outside mesh generation approach by means of a reversed advancing front. We apply this approach to generate unstructured hexahedral meshes of exterior domains. To reproduce the shape of the boundaries, we first pre-compute the mesh fronts by combining two solutions of the Eikonal equation on a tetrahedral reference mesh. Then, to generate high-quality elements, we expand the quadrilateral surface mesh of the inner body towards the unmeshed external boundary using the pre-computed fronts as a guide.     

A Survey of Indicators for Mesh Quality Assessment

We analyze the joint efforts made by the geometry processing and the numerical analysis communities in the last decades to define and measure the concept of “mesh quality”. Researchers have been striving to determine how, and how much, the accuracy of a numerical simulation or a scientific computation (e.g., rendering, printing, modeling operations) depends on the particular mesh adopted to model the problem, and which geometrical features of the mesh most influence the result. The goal was to produce a mesh with good geometrical properties and the lowest possible number of elements, able to produce results in a target range of accuracy. We overview the most common quality indicators, measures, or metrics that are currently used to evaluate the goodness of a discretization and drive mesh generation or mesh coarsening/refinement processes. We analyze a number of local and global indicators, defined over two- and three-dimensional meshes with any type of elements, distinguishing between simplicial, quadrangular/hexahedral, and generic polytopal elements. We also discuss mesh optimization algorithms based on the above indicators and report common libraries for mesh analysis and quality-driven mesh optimization.     

Topological and geometrical properties of hexahedral meshes

Over the years, there have been a number of practical studies with working definitions of ‘mesh’ as related to computational simulation, however, there are only a few theoretical papers with formal definitions of mesh. Algebraic topology papers are available that define tetrahedral meshes in terms of simplices. Algebraic topology and polytope theory has also been utilized to define hexahedral meshes. Additional literature is also available describing particular properties of the dual of a mesh. In this paper, we give several formal definitions in relation to hexahedral meshes and the dual of hexahedral meshes. Our main goal is to provide useful, understandable and minimal definitions specifically for computer scientists or mathematicians working in hexahedral meshing. We also extend these definitions to some useful classifications of hexahedral meshes, including definitions for ‘fundamental’ hexahedral meshes and ‘minimal’ hexahedral meshes.     

Quad‐Mesh Generation and Processing: A Survey

Triangle meshes have been nearly ubiquitous in computer graphics, and a large body of data structures and geometry processing algorithms based on them has been developed in the literature. At the same time, quadrilateral meshes, especially semi‐regular ones, have advantages for many applications, and significant progress was made in quadrilateral mesh generation and processing during the last several years. In this survey we discuss the advantages and problems of techniques operating on quadrilateral meshes, including surface analysis and mesh quality, simplification, adaptive refinement, alignment with features, parametrisation and remeshing.     

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.