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.     

Eulerian shape design sensitivity analysis and optimization with a fixed grid

Conventional shape optimization based on the finite element method uses Lagrangian representation in which the finite element mesh moves according to shape change, while modern topology optimization uses Eulerian representation. In this paper, an approach to shape optimization using Eulerian representation such that the mesh distortion problem in the conventional approach can be resolved is proposed. A continuum geometric model is defined on the fixed grid of finite elements. An active set of finite elements that defines the discrete domain is determined using a procedure similar to topology optimization, in which each element has a unique shape density. The shape design parameter that is defined on the geometric model is transformed into the corresponding shape density variation of the boundary elements. Using this transformation, it has been shown that the shape design problem can be treated as a parameter design problem, which is a much easier method than the former. A detailed derivation of how the shape design velocity field can be converted into the shape density variation is presented along with sensitivity calculation. Very efficient sensitivity coefficients are calculated by integrating only those elements that belong to the structural boundary. The accuracy of the sensitivity information is compared with that derived by the finite difference method with excellent agreement. Two design optimization problems are presented to show the feasibility of the proposed design approach.     

Generation of triangular mesh with specified size by circle packing

This paper describes an algorithm for the generation of a finite element mesh with a specified element size over an unbound 2D domain using the advancing front circle packing technique. Unlike the conventional frontal method, the procedure does not start from the object boundary but starts from a convenient point within the open domain. As soon as a circle is added to the generation front, triangular elements are directly generated by properly connecting frontal segments with the centre of the new circle. Circles are packed closely and in contact with the existing circles by an iterative procedure according to the specified size control function. In contrast to other mesh generation schemes, the domain boundary is not considered in the process of circle packing, this reduces a lot of geometrical checks for intersection between frontal segments. If the mesh generation of a physical object is required, the object boundary can be introduced. The boundary recovery procedure is fast and robust by tracing neighbours of triangular elements. The finite element mesh generated by circle packing can also be used through a mapping process to produce parametric surface meshes of the required characteristics. The sizes of circles in the pack are controlled by the principal surface curvatures. Five examples are given to show the effectiveness and robustness of mesh generation and the application of circle packing to mesh generation over curved surfaces.     

Generation of finite element mesh with variable size over an unbounded 2D domain

With the advance of the finite element, general fluid dynamic and traffic flow problems with arbitrary boundary definition over an unbounded domain are tackled. This paper describes an algorithm for the generation of finite element mesh of variable element size over an unbounded 2D domain by using the advancing front circle packing technique. Unlike the conventional frontal method, the procedure does not start from the object boundary but starts from a convenient point within an open domain. The sequence of construction of the packing circles is determined by the shortest distance from the fictitious centre in such a way that the generation front is more or less a circular loop with occasional minor concave parts due to element size variation. As soon as a circle is added to the generation front, finite elements are directly generated by properly connecting frontal segments with the centre of the new circle. In contrast to other mesh generation schemes, the domain boundary is not considered in the process of circle packing, this reduces a lot of geometrical checks for intersection with frontal segments, and a linear time complexity for mesh generation can be achieved. In case the boundary of the domain is needed, simply generate an unbounded mesh to cover the entire object. As the element adjacency relationship of the mesh has already been established in the circle packing process, insertion of boundary segments by neighbour tracing is fast and robust. Details of such a boundary recovery procedure are described, and practical meshing problems are given to demonstrate how physical objects are meshed by the unbounded meshing scheme followed by the insertion of domain boundaries.     

Four- and eight-node hybrid-Trefftz quadrilateral finite element models for helmholtz problem

In this paper, four- and eight-node quadrilateral finite element models which can readily be incorporated into the standard finite element program framework are devised for plane Helmholtz problems. In these models, frame (boundary) and domain approximations are defined. The former is obtained by nodal interpolation and the latter is truncated from Trefftz solution sets. The equality of the two approximations are enforced along the element boundary. Both the Bessel and plane wave solutions are employed to construct the domain approximation. For full rankness, a minimal of four and eight domain modes are required for the four- and eight-node elements, respectively. By using local coordinates and directions, rank sufficient and invariant elements with minimal and close to minimal numbers of domain approximation modes are devised. In most tests, the proposed hybrid-Trefftz elements with the same number of nodes yield close solutions. In absolute majority of the tests, the proposed elements are considerably more accurate than their single-field counterparts.     

闭合三角网格的优化切割与保角映射

提出一种自动地将任意闭合三角网格切开并保角映射到二维平面域的算法.通过对自动提取的模型初始切割线逐步优化得到模型切割线,优化过程由一个与保角映射扭曲度和合法性相关的成本函数控制.为了减小映射扭曲,算法中不预先固定参数域边界,而在参数化过程中自动地确定网格的自然边界.实验结果表明,该算法通过优化切割线和参数域边界有效地降低了三角形形状扭曲,并保证了参数化结果的合法性.     

Adaptive modification of time evolving meshes

The accuracy of a finite element computation depends on the mesh size and the distribution of mesh points. Adapting the mesh to capture the salient features in the finite element computation can provide a much more accurate solution without imposing an excessive increase in mesh size and computational cost. When the shape of the meshed domain is evolving in time mesh adaptation is essential in order to maintain conformity of the mesh with the domain boundaries. Mesh adaptation for time evolving domains can be accomplished through a combination of mesh movement with mesh modification by selective coarsening and enrichment of various regions in the mesh. Large deformations of the computational domain and boundary can be accommodated if overall mesh quality is maintained after each adaptation cycle.     

Dual Mesh Resampling

The dual of a 2-manifold polygonal mesh without boundary is commonly defined as another mesh with the same topology (genus) but different connectivity (vertex–face incidence), in which faces and vertices occupy complementary locations and the position of each dual vertex is computed as the center of mass (barycenter or centroid) of the vertices that support the corresponding face. This barycenter dual mesh operator is connectivity idempotent but not geometrically idempotent for any choice of vertex positions, other than constants. In this paper we construct a new resampling dual mesh operator that is geometrically idempotent for the largest possible linear subspace of vertex positions. We look at the primal and dual mesh connectivities as irregular sampling spaces and at the rules to determine dual vertex positions as the result of a resampling process that minimizes signal loss. Our formulation, motivated by the duality of Platonic solids, requires the solution of a simple least-squares problem. We introduce a simple and efficient iterative algorithm closely related to Laplacian smoothing and with the same computational cost. We also characterize the configurations of vertex positions where signal loss does and does not occur during dual mesh resampling and the asymptotic behavior of iterative dual mesh resampling in the general case. Finally, we describe the close relation existing with discrete fairing and variational subdivision, and define a new primal–dual interpolatory recursive subdivision scheme.     

Dynamic inelastic structural analysis by boundary element methods

Summary Boundary element methodologies for the determination of the response of inelastic two-and three-dimensional solids and structures as well as beams and flexural plates to dynamic loads are briefly presented and critically discussed. Elastoplastic and viscoplastic material behaviour in the framework of small deformation theories are considered. These methodologies can be separated into four main categories: those which employ the elastodynamic fundamental solution in their formulation, those which employ the elastostatic fundamental solution in their formulation, those which combine boundary and finite elements for the creation of an efficient hybrid scheme and those representing special boundary element techniques. The first category, in addition to the boundary discretization, requires a discretization of those parts of the interior domain expected to become inelastic, while the second category a discretization of the whole interior domain, unless the inertial domain integrals are transformed by the dual reciprocity technique into boundary ones, in which case only the inelastic parts of the domain have to be discretized. The third category employs finite elements for one part of the structure and boundary elements for its remaining part in an effort to combine the advantages of both methods. Finally, the fourth category includes special boundary element techniques for inelastic beams and plates and symmetric boundary element formulations. The discretized equations of motion in all the above methodologies are solved by efficient step-by-step time integration algorithms. Numerical examples involving two-and three-dimensional solids and structures and flexural plates are presented to illustrate all these methodologies and demonstrate their advantages. Finally, directions for future research in the area are suggested.     

Adaptive boundary layer meshing for viscous flow simulations

A procedure for anisotropic mesh adaptation accounting for mixed element types and boundary layer meshes is presented. The method allows to automatically construct meshes on domains of interest to accurately and efficiently compute key flow quantities, especially near wall quantities like wall shear stress. The new adaptive approach uses local mesh modification procedures in a manner that maintains layered and graded elements near the walls, which are popularly known as boundary layer or semi-structured meshes, with highly anisotropic elements of mixed topologies. The technique developed is well suited for viscous flow applications where exact knowledge of the mesh resolution over the computational domain required to accurately resolve flow features of interest is unknown a priori. We apply the method to two types of problem cases; the first type, which lies in the field of hemodynamics, involves pulsatile flow in blood vessels including a porcine aorta case with a stenosis bypassed by a graft whereas the other involves high-speed flow through a double throat nozzle encountered in the field of aerodynamics.     

Shape sensitivity analysis using a fixed basis function finite element approach

An approach is presented for the determination of solution sensitivity to changes in problem domain or shape. A finite element displacement formulation is adopted and the point of view is taken that the finite element basis functions and grid are fixed during the sensitivity analysis; therefore, the method is referred to as a “fixed basis function” finite element shape sensitivity analysis. This approach avoids the requirement of explicit or approximate differentiation of finite element matrices and vectors and the difficulty or errors resulting from such calculations. Effectively, the sensitivity to boundary shape change is determined exactly; thus, the accuracy of the solution sensitivity is dictated only by the finite element mesh used. The evaluation of sensitivity matrices and force vectors requires only modest calculations beyond those of the reference problem finite element analysis; that is, certain boundary integrals and reaction forces on the reference location of the moving boundary are required. In addition, the formulation provides the unique family of element domain changes which completely eliminates the inclusion of grid sensitivity from the shape sensitivity calculation. The work is illustrated for some one-dimensional beam problems and is outlined for a two-dimensional C⁰ problem; the extension to three-dimensional problems is straight-forward. Received December 5, 1999?Revised mansucript received July 6, 2000     

Generation of anisotropic mesh by ellipse packing over an unbounded domain

With the advance of the finite element method, general fluid dynamic and traffic flow problems with arbitrary boundary definition over an unbounded domain are tackled. This paper describes an algorithm for the generation of anisotropic mesh of variable element size over an unbounded 2D domain by using the advancing front ellipse packing technique. Unlike the conventional frontal method, the procedure does not start from the object boundary but starts from a convenient point within an open domain. The sequence of construction of the packing ellipses is determined by the shortest distance from the fictitious centre in such a way that the generation front is more or less a circular loop with occasional minor concave parts due to element size variation. As soon as an ellipse is added to the generation front, finite elements are directly generated by properly connecting frontal segments with the centre of the new ellipse. Ellipses are packed closely and in contact with the existing ellipses by an iterative procedure according to the specified anisotropic metric tensor. The anisotropic meshes generated by ellipse packing can also be used through a mapping process to produce parametric surface meshes of various characteristics. The size and the orientation of the ellipses in the pack are controlled by the metric tensor as derived from the principal surface curvatures. In contrast to other mesh generation schemes, the domain boundary is not considered in the process of ellipse packing, this reduces a lot of geometrical checks for intersection between frontal segments. Five examples are given to show the effectiveness and robustness of anisotropic mesh generation and the application of ellipse packing to mesh generation over various curved surfaces.     

Topological improvement procedures for quadrilateral finite element meshes

This paper presents a set of procedures for improving the topology of unstructured quadrilateral finite element meshes. These procedures are based on the topology of the finite element mesh, and all operations act only on local regions of the mesh. The goal is to optimize the topology such that the smoothing process can produce the best possible element quality. Topological improvement procedures are presented both for elements that are interior to the mesh and for elements connected to the boundary. Also presented is a discussion of efficiency and optimal ordering of the procedures. Several example meshes are included to show the effectiveness of the current approach in improving element qualities in a finite element mesh.     

基于非结构网格的Gas-Kinetic方法

为解决带有复杂几何边界条件的高速流体计算问题,提出基于非结构网格的Gas-Kinetic方法.对于二维非结构网格,以三角形网格作为计算单元,形成在该网格控制单元中物理量导数求解的新方法.通过物理量导数得到在控制体积元边界上的通量,然后用每个计算时间步中求出的边界通量和控制体积元中的物理量,求出下一计算时间步所需的新物理量,依次进行计算直到计算结果收敛为止.采用NACA0012翼型进行数值计算验证,结果表明该方法简单高效,适用于低速和高速流体的计算.     

Toward a Meta-Model for Computational Engineering

Geometric modeling and finite element analysis have matured in recent decades. Both methods are used extensively in engineering design. However, the link between geometric modeling, physical modeling and finite element analysis is currently cumbersome, error-prone, and ad-hoc. Topological domain modeling provides the missing link. In this paper, we propose a combined topological modeling and finite element modeling method that allows not only topological modeling, but also promotes geometric and physical modeling, by providing a topological base space for the definition of finite element meshes, fields, and the definition and solution of boundary value problems. We call the method the Constructive Topological Domain Method (CTDM). In this method, Primitive Topological Domains (PTDs), each possessing a natural coordinate space, are combined in multiple n-dimensional Cartesian coordinate spaces, called charts, using generalizations of Boolean set operations, to create Constructed Topological Domains (CTDs) capable of acting as the base spaces of fiber bundles. The charts are glued together to create an atlas, within which the CTD is defined. The fiber of the bundle may describe, in addition to geometry, physical fields like density, stress, and temperature. Finite element meshes may be defined upon each of the PTDs from which the CTD is constructed, enabling the definition and solution of boundary value problems, thus avoiding the difficult and messy problem of creating a single finite element mesh to represent the entire CTD. A modified finite element method, to handle the individually meshed PTDs, is described. The boundary conditions may be specified as analytical or as finite element-based fields upon each of the PTDs. The CTDM appears to be a promising approach to robust mathematical and computational modeling of physical objects. Simple examples are presented. ID="A1"Correspondance and offprint requests to: W. Gerstle, Department of Civil Engineering, University of New Mexico, Albuquerque, NM 87131, USA. E-mail: gerstle@unm.edu     

Coupling finite elements and auxiliary sources

We consider second-order scalar elliptic boundary value problems on unbounded domains, which model, for instance, electrostatic fields. We propose a discretization that relies on a Trefftz approximation by multipole auxiliary sources in some parts of the domain and on standard mesh-based primal Lagrangian finite elements in other parts. Several approaches are developed and, based on variational saddle point theory, rigorously analyzed to couple both discretizations across the common interface:1. Least-squares-based coupling using techniques from PDE-constrained optimization.2. Coupling through Dirichlet-to-Neumann operators.3. Three-field variational formulation in the spirit of mortar finite element methods.We compare these approaches in a series of numerical experiments.     

Asymptotic boundary conditions with immersed finite elements for interface magnetostatic/electrostatic field problems with open boundary

Many of the magnetostatic/electrostatic field problems encountered in aerospace engineering, such as plasma sheath simulation and ion neutralization process in space, are not confined to finite domain and non-interface problems, but characterized as open boundary and interface problems. Asymptotic boundary conditions (ABC) and immersed finite elements (IFE) are relatively new tools to handle open boundaries and interface problems respectively. Compared with the traditional truncation approach, asymptotic boundary conditions need a much smaller domain to achieve the same accuracy. When regular finite element methods are applied to an interface problem, it is necessary to use a body-fitting mesh in order to obtain the optimal convergence rate. However, immersed finite elements possess the same optimal convergence rate on a Cartesian mesh, which is critical to many applications. This paper applies immersed finite element methods and asymptotic boundary conditions to solve an interface problem arising from electric field simulation in composite materials with open boundary. Numerical examples are provided to demonstrate the high global accuracy of the IFE method with ABC based on Cartesian meshes, especially around both interface and boundary. This algorithm uses a much smaller domain than the truncation approach in order to achieve the same accuracy.     

MooNMD – a program package based on mapped finite element methods

The basis of mapped finite element methods are reference elements where the components of a local finite element are defined. The local finite element on an arbitrary mesh cell will be given by a map from the reference mesh cell. This paper describes some concepts of the implementation of mapped finite element methods. From the definition of mapped finite elements, only local degrees of freedom are available. These local degrees of freedom have to be assigned to the global degrees of freedom which define the finite element space. We will present an algorithm which computes this assignment. The second part of the paper shows examples of algorithms which are implemented with the help of mapped finite elements. In particular, we explain how the evaluation of integrals and the transfer between arbitrary finite element spaces can be implemented easily and computed efficiently. Communicated by: M.S. Espedal, A. Quarteroni, A. Sequeira     

MooNMD – a program package based on mapped finite element methods

The basis of mapped finite element methods are reference elements where the components of a local finite element are defined. The local finite element on an arbitrary mesh cell will be given by a map from the reference mesh cell. This paper describes some concepts of the implementation of mapped finite element methods. From the definition of mapped finite elements, only local degrees of freedom are available. These local degrees of freedom have to be assigned to the global degrees of freedom which define the finite element space. We will present an algorithm which computes this assignment. The second part of the paper shows examples of algorithms which are implemented with the help of mapped finite elements. In particular, we explain how the evaluation of integrals and the transfer between arbitrary finite element spaces can be implemented easily and computed efficiently.