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.     

Universal meshes for smooth surfaces with no boundary in three dimensions

We introduce a method to mesh the boundary Γ of a smooth, open domain in immersed in a mesh of tetrahedra. The mesh follows by mapping a specific collection of triangular faces in the mesh to Γ. Two types of surface meshes follow: (a) a mesh that exactly meshes Γ, and (b) meshes that approximate Γ to any order, by interpolating the map over the selected faces; that is, an isoparametric approximation to Γ. The map we use to deform the faces is the closest point projection to Γ. We formulate conditions for the closest point projection to define a homeomorphism between each face and its image. These are conditions on some of the tetrahedra intersected by the boundary, and they essentially state that each such tetrahedron should (a) have a small enough diameter, and (b) have two of its dihedral angles be acute. We provide explicit upper bounds on the mesh size, and these can be computed on the fly. We showcase the quality of the resulting meshes with several numerical examples. More importantly, all surfaces in these examples were meshed with a single background mesh. This is an important feature for problems in which the geometry evolves or changes, because it could be possible for the background mesh to never change as the geometry does. In this case, the background mesh would be a universal mesh 1 for all these geometries. We expect the method introduced here to be the basis for the construction of universal meshes for domains in three dimensions. Copyright © 2016 John Wiley & Sons, Ltd.     

The tetrahedral finite cell method: Higher‐order immersogeometric analysis on adaptive non‐boundary‐fitted meshes

The finite cell method (FCM) is an immersed domain finite element method that combines higher‐order non‐boundary‐fitted meshes, weak enforcement of Dirichlet boundary conditions, and adaptive quadrature based on recursive subdivision. Because of its ability to improve the geometric resolution of intersected elements, it can be characterized as an immersogeometric method. In this paper, we extend the FCM, so far only used with Cartesian hexahedral elements, to higher‐order non‐boundary‐fitted tetrahedral meshes, based on a reformulation of the octree‐based subdivision algorithm for tetrahedral elements. We show that the resulting TetFCM scheme is fully accurate in an immersogeometric sense, that is, the solution fields achieve optimal and exponential rates of convergence for h‐refinement and p‐refinement, if the immersed geometry is resolved with sufficient accuracy. TetFCM can leverage the natural ability of tetrahedral elements for local mesh refinement in three dimensions. Its suitability for problems with sharp gradients and highly localized features is illustrated by the immersogeometric phase‐field fracture analysis of a human femur bone. Copyright © 2016 John Wiley & Sons, Ltd.     

Coarsening unstructured meshes by edge contraction

A new unstructured mesh coarsening algorithm has been developed for use in conjunction with multilevel methods. The algorithm preserves geometrical and topological features of the domain, and retains a maximal independent set of interior vertices to produce good coarse mesh quality. In anisotropic meshes, vertex selection is designed to retain the structure of the anisotropic mesh while reducing cell aspect ratio. Vertices are removed incrementally by contracting edges to zero length. Each vertex is removed by contracting the edge that maximizes the minimum sine of the dihedral angles of cells affected by the edge contraction. Rarely, a vertex slated for removal from the mesh cannot be removed; the success rate for vertex removal is typically 99.9% or more. For two‐dimensional meshes, both isotropic and anisotropic, the new approach is an unqualified success, removing all rejected vertices and producing output meshes of high quality; mesh quality degrades only when most vertices lie on the boundary. Three‐dimensional isotropic meshes are also coarsened successfully, provided that there is no difficulty distinguishing corners in the geometry from coarsely‐resolved curved surfaces; sophisticated discrete computational geometry techniques appear necessary to make that distinction. Three‐dimensional anisotropic cases are still problematic because of tight constraints on legal mesh connectivity. More work is required to either improve edge contraction choices or to develop an alternative strategy for mesh coarsening for three‐dimensional anisotropic meshes. Copyright © 2003 John Wiley & Sons, Ltd.     

Automatic generation of transitional meshes

Advances in commercial computer‐aided design software have made finite element analysis with three‐dimensional solid finite elements routinely available. Since these analyses usually confine themselves to those geometrical objects for which particular CAD systems can produce finite element meshes, expanding the capability of analyses becomes an issue of expanding the capability of generating meshes. This paper presents a method for stitching together two three‐dimensional meshes with diverse elements that can include tetrahedral, pentahedral and hexahedral solid finite elements. The stitching produces a mesh that coincides with the edges which already exist on the portion of boundaries that will be joined. Moreover, the transitional mesh does not introduce new edges on these boundaries. Since the boundaries of the regions to be stitched together can have a mixture of triangles and quadrilaterals, tetrahedral and pyramidal elements provide the transitional elements required to honor these constraints. On these boundaries a pyramidal element shares its base face with the quadrilateral faces of hexahedra and pentahedra. Tetrahedral elements share a face with the triangles on the boundary. Tetrahedra populate the remaining interior of the transitional region. Copyright © 2001 John Wiley & Sons, Ltd.     

Clustered generalized finite element methods for mesh unrefinement,non‐matching and invalid meshes

In spite of significant advancements in automatic mesh generation during the past decade, the construction of quality finite element discretizations on complex three‐dimensional domains is still a difficult and time demanding task. In this paper, the partition of unity framework used in the generalized finite element method (GFEM) is exploited to create a very robust and flexible method capable of using meshes that are unacceptable for the finite element method, while retaining its accuracy and computational efficiency. This is accomplished not by changing the mesh but instead by clustering groups of nodes and elements. The clusters define a modified finite element partition of unity that is constant over part of the clusters. This so‐called clustered partition of unity is then enriched to the desired order using the framework of the GFEM. The proposed generalized finite element method can correctly and efficiently deal with: (i) elements with negative Jacobian; (ii) excessively fine meshes created by automatic mesh generators; (iii) meshes consisting of several sub‐domains with non‐matching interfaces. Under such relaxed requirements for an acceptable mesh, and for correctly defined geometries, today's automated tetrahedral mesh generators can practically guarantee successful volume meshing that can be entirely hidden from the user. A detailed technical discussion of the proposed generalized finite element method with clustering along with numerical experiments and some implementation details are presented. Copyright © 2006 John Wiley & Sons, Ltd.     

A shape optimization approach for simulating contact of elastic membranes with rigid obstacles

The obstacle problem consists in computing equilibrium shapes of elastic membranes in contact with rigid obstacles. In addition to the displacement u of the membrane, the interface Γ on the membrane demarcating the region in contact with the obstacle is also an unknown and plays the role of a free boundary. Numerical methods that simulate obstacle problems as variational inequalities share the unifying feature of first computing membrane displacements and then deducing the location of the free boundary a posteriori. We present a shape optimization-based approach here that inverts this paradigm by considering the free boundary to be the primary unknown and compute it as the minimizer of a certain shape functional using a gradient descent algorithm. In a nutshell, we compute Γ then u, and not u then Γ. Our approach proffers clear algorithmic advantages. Unilateral contact constraints on displacements, which render traditional approaches into expensive quadratic programs, appear only as Dirichlet boundary conditions along the free boundary. Displacements of the membrane need to be approximated only over the noncoincidence set, thereby rendering smaller discrete problems to be resolved. The issue of suboptimal convergence of finite element solutions stemming from the reduced regularity of displacements across the free boundary is naturally circumvented. Most importantly perhaps, our numerical experiments reveal that the free boundary can be approximated to within distances that are two orders of magnitude smaller than the mesh size used for spatial discretization. The success of the proposed algorithm relies on a confluence of factors- choosing a suitable shape functional, representing free boundary iterates with smooth implicit functions, an ansatz for the velocity of the free boundary that helps realize a gradient descent scheme and triangulating evolving domains with universal meshes. We discuss these aspects in detail and present numerous examples examining the performance of the algorithm.     

SGBEM with Lagrange multipliers applied to elastic domain decomposition problems with curved interfaces using non‐matching meshes

An original approach to the solution of linear elastic domain decomposition problems by the symmetric Galerkin boundary element method is developed. The approach is based on searching for the saddle‐point of a new potential energy functional with Lagrange multipliers. The interfaces can be either straight or curved, open or closed. The two coupling conditions, equilibrium and compatibility, along an interface are fulfilled in a weak sense by means of Lagrange multipliers (interface displacements and tractions), which enables non‐matching meshes to be used at both sides of interfaces between subdomains. The accuracy and robustness of the method is tested by several numerical examples, where the numerical results are compared with the analytical solution of the solved problems, and the convergence rates of two error norms are evaluated for h‐refinements of matching and non‐matching boundary element meshes. Copyright © 2010 John Wiley & Sons, Ltd.     

Optimization of a regularized distortion measure to generate curved high‐order unstructured tetrahedral meshes

We present a robust method for generating high‐order nodal tetrahedral curved meshes. The approach consists of modifying an initial linear mesh by first, introducing high‐order nodes, second, displacing the boundary nodes to ensure that they are on the computer‐aided design surface, and third, smoothing and untangling the mesh obtained after the displacement of the boundary nodes to produce a valid curved high‐order mesh. The smoothing algorithm is based on the optimization of a regularized measure of the mesh distortion relative to the original linear mesh. This means that whenever possible, the resulting mesh preserves the geometrical features of the initial linear mesh such as shape, stretching, and size. We present several examples to illustrate the performance of the proposed algorithm. Furthermore, the examples show that the implementation of the optimization problem is robust and capable of handling situations in which the mesh before optimization contains a large number of invalid elements. We consider cases with polynomial approximations up to degree ten, large deformations of the curved boundaries, concave boundaries, and highly stretched boundary layer elements. The meshes obtained are suitable for high‐order finite element analyses. Copyright © 2015 John Wiley & Sons, Ltd.     

Three‐dimensional immersed finite element methods for electric field simulation in composite materials

This paper presents two immersed finite element (IFE) methods for solving the elliptic interface problem arising from electric field simulation in composite materials. The meshes used in these IFE methods can be independent of the interface geometry and position; therefore, if desired, a structured mesh such as a Cartesian mesh can be used in an IFE method to simulate 3‐D electric field in a domain with non‐trivial interfaces separating different materials. Numerical examples are provided to demonstrate that the accuracies of these IFE methods are comparable to the standard linear finite element method with unstructured body‐fit mesh. Copyright © 2005 John Wiley & Sons, Ltd.     

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.     

Quality improvement of non‐manifold hexahedral meshes for critical feature determination of microstructure materials

This paper describes a novel approach to improve the quality of non‐manifold hexahedral meshes with feature preservation for microstructure materials. In earlier works, we developed an octree‐based isocontouring method to construct unstructured hexahedral meshes for domains with multiple materials by introducing the notion of material change edge to identify the interface between two or more materials. However, quality improvement of non‐manifold hexahedral meshes is still a challenge. In the present algorithm, all the vertices are categorized into seven groups, and then a comprehensive method based on pillowing, geometric flow and optimization techniques is developed for mesh quality improvement. The shrink set in the modified pillowing technique is defined automatically as the boundary of each material region with the exception of local non‐manifolds. In the relaxation‐based smoothing process, non‐manifold points are identified and fixed. Planar boundary curves and interior spatial curves are distinguished, and then regularized using B‐spline interpolation and resampling. Grain boundary surface patches and interior vertices are improved as well. Finally, the optimization method eliminates negative Jacobians of all the vertices. We have applied our algorithms to two beta titanium data sets, and the constructed meshes are validated via a statistics study. Finite element analysis of the 92‐grain titanium is carried out based on the improved mesh, and compared with the direct voxel‐to‐element technique. Copyright © 2009 John Wiley & Sons, Ltd.     

Automatic merging of tetrahedral meshes

A generic algorithm is proposed to merge arbitrary solid tetrahedral meshes automatically into one single valid finite element mesh. The intersection segments in the form of distinct nonoverlapping loops between the boundary surfaces of the given solid objects are determined by the robust neighbor tracing technique. Each intersected triangle on the boundary surface will be triangulated to incorporate the intersection segments onto the boundary surface of the objects. The tetrahedra on the boundary surface associated with the intersected triangular facets are each divided into as many tetrahedra as the number of subtriangles on the triangulated facet. There is a natural partition of the boundary surfaces of the solid objects by the intersection loops into a number of zones. Volumes of intersection can now be identified by collected bounding surfaces from the surface patches of the partition. Whereas mesh compatibility has already been established on the boundary of the solid objects, mesh compatibility has yet to be restored on the bounding surfaces of the regions of intersection. Tetrahedra intersected by the cut surfaces are removed, and new tetrahedra can be generated to fill the volumes bounded by the cut surfaces and the portion of cavity boundary connected to the cut surfaces to restore mesh compatibility at the cut surfaces. Upon restoring compatibility on the bounding surfaces of the regions of intersection, the objects are ready to be merged together as all regions of intersection can be detached freely from the objects. All operations, besides the determination of intersections structurally in the form of loops, are virtually topological, and no parameter and tolerance is needed in the entire merging process. Examples are presented to show the steps and the details of the mesh merging procedure. Copyright © 2012 John Wiley & Sons, Ltd.     

Variational generation of prismatic boundary‐layer meshes for biomedical computing

Boundary‐layer meshes are important for numerical simulations in computational fluid dynamics, including computational biofluid dynamics of air flow in lungs and blood flow in hearts. Generating boundary‐layer meshes is challenging for complex biological geometries. In this paper, we propose a novel technique for generating prismatic boundary‐layer meshes for such complex geometries. Our method computes a feature size of the geometry, adapts the surface mesh based on the feature size, and then generates the prismatic layers by propagating the triangulated surface using the face‐offsetting method. We derive a new variational method to optimize the prismatic layers to improve the triangle shapes and edge orthogonality of the prismatic elements and also introduce simple and effective measures to guarantee the validity of the mesh. Coupled with a high‐quality tetrahedral mesh generator for the interior of the domain, our method generates high‐quality hybrid meshes for accurate and efficient numerical simulations. We present comparative study to demonstrate the robustness and quality of our method for complex biomedical geometries. Copyright © 2009 John Wiley & Sons, Ltd.     

Arbitrary order edge elements for electromagnetic scattering simulations using hybrid meshes and a PML

The use of arbitrary order edge elements for the simulation of two‐dimensional electromagnetic scattering problems on hybrid meshes of triangles and quadrilaterals is described. Single‐frequency incident waves, generated by a source in the far field, are considered and the solution is determined in the frequency domain. For numerical simulation, the solution domain is truncated at a finite distance from the perfectly conducting scatterer and the non‐reflecting boundary condition at the truncated boundary is imposed by the use of a perfectly matched layer (PML). Several examples are included to demonstrate the performance of the proposed procedure. Copyright © 2002 John Wiley & Sons, Ltd.     

Unconstrained plastering—Hexahedral mesh generation via advancing‐front geometry decomposition

The generation of all‐hexahedral finite element meshes has been an area of ongoing research for the past two decades and remains an open problem. Unconstrained plastering is a new method for generating all‐hexahedral finite element meshes on arbitrary volumetric geometries. Starting from an unmeshed volume boundary, unconstrained plastering generates the interior mesh topology without the constraints of a pre‐defined boundary mesh. Using advancing fronts, unconstrained plastering forms partially defined hexahedral dual sheets by decomposing the geometry into simple shapes, each of which can be meshed with simple meshing primitives. By breaking from the tradition of previous advancing‐front algorithms, which start from pre‐meshed boundary surfaces, unconstrained plastering demonstrates that for the tested geometries, high quality, boundary aligned, orientation insensitive, all‐hexahedral meshes can be generated automatically without pre‐meshing the boundary. Examples are given for meshes from both solid mechanics and geotechnical applications. Copyright © 2009 John Wiley & Sons, Ltd.     

An embedded mesh method for treating overlapping finite element meshes

A new technique for treating the mechanical interactions of overlapping finite element meshes is presented. Such methods can be useful for numerous applications, for example, fluid–solid interaction with a superposed meshed solid on an Eulerian background fluid grid. In this work, we consider the interaction of two elastic domains: one mesh is the foreground and defines the surface of interaction, the other is a background mesh and is often a structured grid. Many of the previously proposed methods employ surface defined Lagrange multipliers or penalties to enforce the boundary constraints. It has become apparent that these methods will cause mesh locking under certain conditions. Appropriately applied, the Nitsche method can overcome this locking, but, in its canonical form, is generally not applicable to non‐linear materials such as hyperelastics. The relationship between interior point penalty, discontinuous Galerkin and Nitsche's method is well known. Based on this relationship, a nonlinear theory analogous to the Nitsche method is proposed to treat nonlinear materials in an embedded mesh. Here, a discontinuous Galerkin derivative based on a lifting of the interface surface integrals provides a consistent treatment for non‐linear materials and demonstrates good behavior in example problems. Published 2012. This article is a US Government work and is in the public domain in the USA.     

Automatic construction of non‐obtuse boundary and/or interface Delaunay triangulations for control volume methods

A Delaunay mesh without triangles having obtuse angles opposite to boundary and interface edges (obtuse boundary/interface triangles) is the basic requirement for problems solved using the control volume method. In this paper we discuss postprocess algorithms that allow the elimination of obtuse boundary/interface triangles of any constrained Delaunay triangulation with minimum angle ε. This is performed by the Delaunay insertion of a finite number of boundary and/or interface points. Techniques for the elimination of two kinds of obtuse boundary/interface triangles are discussed in detail: 1‐edge obtuse triangles, which have a boundary/interface (constrained) longest edge; and 2‐edge obtuse triangles, which have both their longest and second longest edge over the boundary/interface. More complex patterns of obtuse boundary/interface triangles, namely chains of 2‐edge constrained triangles forming a saw diagram and clusters of triangles that have constrained edges sharing a common vertex are managed by using a generalization of the above techniques. Examples of the use of these techniques for semiconductor device applications and a discussion on their generalization to 3‐dimensions (3D) are also included. Copyright © 2002 John Wiley & Sons, Ltd.     

Methods for connecting dissimilar three‐dimensional finite element meshes

Two methods are presented for connecting dissimilar three‐dimensional finite element meshes. The first method combines the concept of master and slave surfaces with the uniform strain approach for finite elements. By modifying the boundaries of elements on a slave surface, corrections are made to element formulations such that first‐order patch tests are passed. The second method is based entirely on constraint equations, but only passes a weaker form of the patch test for non‐planar surfaces. Both methods can be used to connect meshes with different element types. In addition, master and slave surfaces can be designated independently of relative mesh resolutions. Example problems in three‐dimensional linear elasticity are presented. Published in 2000 by John Wiley & Sons, Ltd.