Quadrilateral surface meshes without self-intersecting dual cycles for hexahedral mesh generation

Several promising approaches for hexahedral mesh generation work as follows: Given a prescribed quadrilateral surface mesh they first build the combinatorial dual of the hexahedral mesh. This dual mesh is converted into the primal hexahedral mesh, and finally embedded and smoothed into the given domain. Two such approaches, the modified whisker weaving algorithm by Folwell and Mitchell, as well as a method proposed by the author, rely on an iterative elimination of certain dual cycles in the surface mesh. An intuitive interpretation of the latter method is that cycle eliminations correspond to complete sheets of hexahedra in the volume mesh.

Although these methods can be shown to work in principle, the quality of the generated meshes heavily relies on the dual cycle structure of the given surface mesh. In particular, it seems that difficulties in the hexahedral meshing process and poor mesh qualities are often due to self-intersecting dual cycles. Unfortunately, all previous work on quadrilateral surface mesh generation has focused on quality issues of the surface mesh alone but has disregarded its suitability for a high-quality extension to a three-dimensional mesh.

In this paper, we develop a new method to generate quadrilateral surface meshes without self-intersecting dual cycles. This method reuses previous b-matching problem formulations of the quadrilateral mesh refinement problem. The key insight is that the b-matching solution can be decomposed into a collection of simple cycles and paths of multiplicity two, and that these cycles and paths can be consistently embedded into the dual surface mesh.

A second tool uses recursive splitting of components into simpler subcomponents by insertion of internal two-manifolds. We show that such a two-manifold can be meshed with quadrilaterals such that the induced dual cycle structure of each subcomponent is free of self-intersections if the original component satisfies this property. Experiments show that we can achieve hexahedral meshes with a good quality.     

Stochastic Domain Decomposition for Time Dependent Adaptive Mesh Generation

The efficient generation of meshes is an important component in the numerical solution of problems in physics and engineering. Of interest are situations where global mesh quality and a tight coupling to the solution of the physical partial differential equation (PDE) is important. We consider parabolic PDE mesh generation and present a method for the construction of adaptive meshes in two spatial dimensions using stochastic domain decomposition that is suitable for an implementation in a multi- or many-core environment. Methods for mesh generation on periodic domains are also provided. The mesh generator is coupled to a time dependent physical PDE and the system is evolved using an alternating solution procedure. The method uses the stochastic representation of the exact solution of a parabolic linear mesh generator to find the location of an adaptive mesh along the (artificial) subdomain interfaces. The deterministic evaluation of the mesh over each subdomain can then be obtained completely independently using the probabilistically computed solutions as boundary conditions. A small scaling study is provided to demonstrate the parallel performance of this stochastic domain decomposition approach to mesh generation. We demonstrate the approach numerically and compare the mesh obtained with the corresponding single domain mesh using a representative mesh quality measure.     

Robust intersection of structured hexahedral meshes and degenerate triangle meshes with volume fraction applications

Two methods for calculating the volume and surface area of the intersection between a triangle mesh and a rectangular hexahedron are presented. The main result is an exact method that calculates the polyhedron of intersection and thereafter the volume and surface area of the fraction of the hexahedral cell inside the mesh. The second method is approximate, and estimates the intersection by a least squares plane. While most previous publications focus on non-degenerate triangle meshes, we here extend the methods to handle geometric degeneracies. In particular, we focus on large-scale triangle overlaps, or double surfaces. It is a geometric degeneracy that can be hard to solve with existing mesh repair algorithms. There could also be situations in which it is desirable to keep the original triangle mesh unmodified. Alternative methods that solve the problem without altering the mesh are therefore presented. This is a step towards a method that calculates the solid area and volume fractions of a degenerate triangle mesh including overlapping triangles, overlapping meshes, hanging nodes, and gaps. Such triangle meshes are common in industrial applications. The methods are validated against three industrial test cases. The validation shows that the exact method handles all addressed geometric degeneracies, including double surfaces, small self-intersections, and split hexahedra.     

An efficient algebraic multigrid method for quadratic discretizations of linear elasticity problems on some typical anisotropic meshes in three dimensions

The quality of the mesh used in the finite element discretizations will affect the efficiency of solving the discreted linear systems. The usual algebraic solvers except multigrid method do not consider the effect of the grid geometry and the mesh quality on their convergence rates. In this paper, we consider the hierarchical quadratic discretizations of three‐dimensional linear elasticity problems on some anisotropic hexahedral meshes and present a new two‐level method, which is weakly independent of the size of the resulting problems by using a special local block Gauss–Seidel smoother, that is LBGS_v iteration when used for vertex nodes or LBGS_m iteration for midside nodes. Moreover, we obtain the efficient algebraic multigrid (AMG) methods by applying DAMG (AMG based on distance matrix) or DAMG‐PCG (PCG with DAMG as a preconditioner) to the solution of the coarse level equation. The resulting AMG methods are then applied to a practical example as a long beam. The numerical results verify the efficiency and robustness of the proposed AMG algorithms. Copyright © 2015 John Wiley & Sons, Ltd.     

Quading triangular meshes with certain topological constraints

In computer graphics and geometric modeling, shapes are often represented by triangular meshes (also called 3D meshes or manifold triangulations). The quadrangulation of a triangular mesh has wide applications. In this paper, we present a novel method of quading a closed orientable triangular mesh into a quasi-regular quadrangulation, i.e., a quadrangulation that only contains vertices of degree four or five. The quasi-regular quadrangulation produced by our method also has the property that the number of quads of the quadrangulation is the smallest among all the quasi-regular quadrangulations. In addition, by constructing the so-called orthogonal system of cycles our method is more effective to control the quality of the quadrangulation.     

Improvements on Delaunay-based three-dimensional automatic mesh generator

This paper describes an automatic mesh generator providing tetrahedral meshes suitable in general for finite element simulations. The mesh generator is of the Delaunay type and the paper focuses on recent improvements relative to this a priori well-known method.     

Heuristic algorithm for generating multilevel Cartesian meshes inmultidimensional regions with moving boundaries

Universal algorithm for fully automated generation of multilevel Cartesian mesh in arbitrary planar regions with moving boundaries is developed and discussed in details. It uses multilevel tree technology and heuristic enabling flexible mesh adaptation to changes of boundaries. Efficient mixed coding for mesh storing is presented. Suggested algorithm generates meshes with properties most desirable for computing various field distribution problems. Main parts of elaborated algorithm are generalized for multidimensional meshes.     

Finite element and boundary element contact stress analysis with remeshing technique

The fundamental part of the contact stress problem solution using a finite element method is to locate possible contact areas reliably and efficiently. In this research, a remeshing technique is introduced to determine the contact region in a given accuracy. In the proposed iterative method, the meshes near the contact surface are modified so that the edge of the contact region is also an element’s edge. This approach overcomes the problem of surface representation at the transition point from contact to non-contact region. The remeshing technique is efficiently employed to adapt the mesh for more precise representation of the contact region. The method is applied to both finite element and boundary element methods. Overlapping of the meshes in the contact region is prevented by the inclusion of displacement and force constraints using the Lagrange multipliers technique. Since the method modifies the mesh only on the contacting and neighbouring region, the solution to the matrix system is very close to the previous one in each iteration. Both direct and iterative solver performances on BEM and FEM analyses are also investigated for the proposed incremental technique. The biconjugate gradient method and LU with Cholesky decomposition are used for solving the equation systems. Two numerical examples whose analytical solutions exist are used to illustrate the advantages of the proposed method. They show a significant improvement in accuracy compared to the solutions with fixed meshes.     

Local transformations of hexahedral meshes of lower valence

The modification of conforming hexahedral meshes is difficult to perform since their structure does not allow easy local refinement or un-refinement such that the modification does not go through the boundary. In this paper we prove that the set of hex flipping transformations of Bern et al. (2002) [1] is the only possible local modification on a geometrical hex mesh of valence less than five i.e., with less than five edges per vertex. We propose a new basis of transformations that can generate sequences of local modifications on hex meshes of valence less than six. For quadrilateral meshes, we show the equivalence between modifying locally the number of quads on a mesh and the number of its internal vertices.     

Generating Layer-Adapted Meshes Using Mesh Partial Differential Equations

We present a new algorithm for generating layer-adapted meshes for the finite element solution of singularly perturbed problems based on mesh partial differential equations (MPDEs). The ultimate goal is to design meshes that are similar to the well-known Bakhvalov meshes, but can be used in more general settings: specifically two-dimensional problems for which the optimal mesh is not tensor-product in nature. Our focus is on the efficient implementation of these algorithms, and numerical verification of their properties in a variety of settings. The MPDE is a nonlinear problem, and the efficiency with which it can be solved depends adversely on the magnitude of the perturbation parameter and the number of mesh intervals. We resolve this by proposing a scheme based on $h$-refinement. We present fully working FEniCS codes [Alnaes et al., Arch. Numer. Softw., 3 (100) (2015)] that implement these methods, facilitating their extension to other problems and settings.     

Mixed methods on quadrilaterals and hexahedra

We describe a new family of discrete spaces suitable for use with mixed methods on certain quadrilateral and hexahedral meshes. The new spaces are natural in the sense of differential geometry, so all the usual mixed method theory, including the hybrid formulation, carries over to these new elements with proofs unchanged. Because transforming general quadrilaterals into squares introduces nonlinearity and because mixed methods involve the divergence operator, the new spaces are more complicated than either the corresponding Raviart-Thomas spaces for rectangles or corresponding finite element spaces for quadrilaterals. The new spaces are also limited to meshes obtained from a rectangular mesh through the application of a single global bilinear transformation. Despite this limitation, the new elements may be useful in certain topologically regular problems, where initially rectangular grids are deformed to match features of the physical region. They also illustrate the difficulties introduced into the theory of mixed methods by nonlinear transformations.     

A Comparative Numerical Study of Meshing Functionals for Variational Mesh Adaptation

We present a comparative numerical study for three functionals used for variational mesh adaptation. One of them is a generalization of Winslow's variable diffusion functional while the others are based on equidistribution and alignment. These functionals are known to have nice theoretical properties and work well for most mesh adaptation problems either as a stand-alone variational method or combined within the moving mesh framework. Their performance is investigated numerically in terms of equidistribution and alignment mesh quality measures. Numerical results in 2D and 3D are presented.     

An inequality on the edge lengths of triangular meshes

We give a short proof of the following geometric inequality: for any two triangular meshes A and B of the same polygon C, if the number of vertices in A is at most the number of vertices in B, then the maximum length of an edge in A is at least the minimum distance between two vertices in B. Here the vertices in each triangular mesh include the vertices of the polygon and possibly additional Steiner points. The polygon must not be self-intersecting but may be non-convex and may even have holes. This inequality is useful for many purposes, especially in proving performance guarantees of mesh generation algorithms. For example, a weaker corollary of the inequality confirms a conjecture of Aurenhammer et al. [Theoretical Computer Science 289 (2002) 879-895] concerning triangular meshes of convex polygons, and improves the approximation ratios of their mesh generation algorithm for minimizing the maximum edge length and the maximum triangle perimeter of a triangular mesh.     

A constrained optimization approach to finite element mesh smoothing

The quality of a finite element solution has been shown to be affected by the quality of the underlying mesh. A poor mesh may lead to unstable and/or inaccurate finite element approximations. Mesh quality is often characterized by the “smoothness” or “shape” of the elements (triangles in 2-D or tetrahedra in 3-D). Most automatic mesh generators produce an initial mesh where the aspect ratio of the elements are unacceptably high. In this paper, a new approach to produce acceptable quality meshes from a topologically valid initial mesh is presented. Given an initial mesh (nodal coordinates and element connectivity), a “smooth” final mesh is obtained by solving a constrained optimization problem. The variables for the iterative optimization procedure are the nodal coordinates (excluding, the boundary nodes) of the finite element mesh, and appropriate bounds are imposed on these to prevent an unacceptable finite element mesh. Examples are given of the application of the above method for 2- and 3-D meshes generated using automatic mesh generators. Results indicate that the new method not only yields better quality elements when compared with the traditional Laplacian smoothing, but also guarantees a valid mesh unlike the Laplacian method.     

On using meshes of mixed element types in adaptive finite element analysis

Four different automatic mesh generators capable of generating either triangular meshes or hybrid meshes of mixed element types have been used in the mesh generation process. The performance of these mesh generators were tested by applying them to the adaptive finite element refinement procedure. It is found that by carefully controlling the quality and grading of the quadrilateral elements, an increase in efficiency over pure triangular meshes can be achieved. Furthermore, if linear elements are employed, an optimal hybrid mesh can be obtained most economically by a combined use of the mesh coring technique suggested by Lo and Lau and a selective removal of diagonals from the triangular element mesh. On the other hand, if quadratic elements are used, it is preferable to generate a pure triangular mesh first, and then obtain a hybrid mesh by merging of triangles.     

A SECOND ORDER CONTROL-VOLUME FINITE-ELEMENT LEAST-SQUARES STRATEGY FOR SIMULATING DIFFUSION IN STRONGLY ANISOTROPIC MEDIA

An unstructured mesh finite volume discretisation method for simulating diffusion in anisotropic media in two-dimensional space is discussed. This technique is considered as an extension of the fully implicit hybrid control-volume finite-element method and it retains the local continuity of the flux at the control volume faces. A least squares function recon-struction technique together with a new flux decomposition strategy is used to obtain an accurate flux approximation at the control volume face, ensuring that the overall accuracy of the spatial discretisation maintains second order. This paper highlights that the new technique coincides with the traditional shape function technique when the correction term is neglected and that it significantly increases the accuracy of the previous linear scheme on coarse meshes when applied to media that exhibit very strong to extreme anisotropy ratios. It is concluded that the method can be used on both regular and irregular meshes,and appears independent of the mesh quality.     

Adaptive mesh refinement for the control of cost and quality in finite element analysis

Adaptive strategies are a necessary tool to make finite element analysis applicable to engineering practice. In this paper, attention is restricted to mesh adaptivity. Traditionally, the most common mesh adaptive strategies for linear problems are used to reach a prescribed accuracy. This goal is best met with an h-adaptive scheme in combination with an error estimator. In an industrial context, the aim of the mechanical simulations in engineering design is not only to obtain greatest quality but more often a compromise between the desired quality and the computation cost (CPU time, storage, software, competence, human cost, computer used). In this paper, we propose the use of alternative mesh refinement criteria with an h-adaptive procedure for 3D elastic problems. The alternative mesh refinement criteria (MR) are based on: prescribed number of elements with maximum accuracy, prescribed CPU time with maximum accuracy and prescribed memory size with maximum accuracy. These adaptive strategies are based on a technique of error in constitutive relation (the process could be used with other error estimators) and an efficient adaptive technique which automatically takes into account the steep gradient areas. This work proposes a 3D method of adaptivity with the latest version of the INRIA automatic mesh generator GAMHIC3D.     

Superior mesh quality with automatic node mergers

Automatic surface :meshers have been designed with the intent to eliminate the manual effort involved in creating a finite element model. Naturally, the quality of the mesh must be such that the solver will yield accurate results. For geometries having boundaries with short edges relative to the rest of the geometry, the existing meshers yield poor-quality meshes. Hence, the stress analyst must manually attain reasonable mesh quality. This manual effort is very tedious and time consuming. Mesh quality improvement techniques such as smoothing, fail to improve the mesh quality. In this work, a new technique is introduced, which improves the initial boundary node loop quality, and in turn yields high-quality meshes. Examples show marked improvement in quality, and the meshes are comprised of fewer elements.     

Quality mesh generation for molecular skin surfaces using restricted union of balls

Quality surface meshes for molecular models are desirable in the studies of protein shapes and functionalities. However, there is still no robust software that is capable to generate such meshes with good quality. In this paper, we present a Delaunay-based surface triangulation algorithm generating quality surface meshes for the molecular skin model. We expand the restricted union of balls along the surface and generate an ε-sampling of the skin surface incrementally. At the same time, a quality surface mesh is extracted from the Delaunay triangulation of the sample points. The algorithm supports robust and efficient implementation and guarantees the mesh quality and topology as well. Our results facilitate molecular visualization and have made a contribution towards generating quality volumetric tetrahedral meshes for the macromolecules.     

Adaptive finite element analysis of structures under transient dynamic loading using modal superposition

In this paper, the error estimation and adaptive strategy developed for the linear elastodynamic problem under transient dynamic loading based on the Z–Z criterion is utilized for 2D and plate bending problems. An automatic mesh generator based on “growth meshing” is utilized effectively for adaptive mesh refinement. Optimal meshes are obtained iteratively corresponding to the prescribed domain discretization error limit and for a chosen number of basis modes satisfying modal truncation errors. Numerous examples show the effectiveness of the integrated approach in achieving the target accuracy in finite element transient dynamic analysis.