Generation of Tetrahedral Meshes with Multiple Elements through Thin Sections

Finite element simulations in domains with strong gradients across thin sections typically require meshes with multiple elements through these sections to accurately capture the solution. Most of the published techniques for isotropic mesh generation are not suited for the creation of such meshes in general, arbitrarily complex, non-manifold domains. In this paper, an automatic method is described for identification of thin sections of a domain and anisotropic refinement of an initial mesh to introduce a user-requested number of elements through the thin sections. The method uses local mesh modification operations to effect the refinement and subsequent realignment of edges along the thickness direction and perpendicular to it. Results are presented for a number of general models to illustrate the capability of the mesh generator.     

Complexity and Modeling Aspects of Mesh Refinement into Quadrilaterals

We investigate the following mesh refinement problem: Given a mesh of polygons in three-dimensional space, find a decomposition into strictly convex quadrilaterals such that the resulting mesh is conforming and satisfies prescribed local density constraints. The conformal mesh refinement problem is shown to be feasible if and only if a certain system of linear equations over GF(2) has a solution. To improve mesh quality with respect to optimization criteria such as density, angles, and regularity, we introduce a reduction to a minimum cost bidirected flow problem. However, this model is only applicable if the mesh does not contain branching edges, that is, edges incident to more than two polygons. The general case with branchings, however, turns out to be strongly -hard. To enhance the mesh quality for meshes with branchings, we introduce a two-stage approach which first decomposes the whole mesh into components without branchings, and then uses minimum cost bidirected flows on the components in a second phase. Received March 10, 1997; revised August 15, 1997.     

Approximate Shape Quality Mesh Generation

We present two techniques for simplifying the list processing required in standard iterative refinement approaches to shape quality mesh generation. The goal of these techniques is to gain simplicity of programming, efficiency in execution, and robustness of termination. ‘Shape quality’ for a mesh generation method usually means that, under suitable conditions, a mesh with all angles exceeding a prescribed tolerance is generated. The methods introduced in this paper are truncated versions of such methods. They depend on the shape improvement properties of the terminal-edge LEPP-Delaunay refinement technique; we refer to them as approximate shape quality methods. They are intended for geometry-based preconditioning of coarse initial meshes for subsequent refinement to meet data representation needs. One technique is an algorithm re-organization to avoid maintaining a global list of triangles to be refined. The re-organization uses a recursive triangle processing strategy. Truncating the recursion depth results in an approximate method. Based on this, we argue that the refinement process can be carried out using a static list of the triangles to be refined that can be identified in the initial mesh. Comparisons of approximate to full shape quality meshes are provided.     

Shape optimization of quad mesh elements

We study the problem of optimizing the face elements of a quad mesh surface, that is, re-sampling a given quad mesh to make it possess, as much as possible, face elements of some desired aspect ratio and size. Unlike previous quad mesh optimization/improvement methods based on local operations on a small group of elements, we adopt a global approach that does not introduce extra singularities and therefore preserves the original quad structure of the input mesh. Starting from a collection of quad patches extracted from an input quad mesh, two global operations, i.e. re-sampling and re-distribution, are performed to optimize the number and spacings of grid lines in each patch. Both operations are formulated as simple optimization problems with linear constraints.     

Transitive mesh space of a progressive mesh

The paper investigates the set of all selectively refined meshes that can be obtained from a progressive mesh. We call the set the transitive mesh space of a progressive mesh and present a theoretical analysis of the space. We define selective edge collapse and vertex split transformations, which we use to traverse all selectively refined meshes in the transitive mesh space. We propose a complete selective refinement scheme for a progressive mesh based on the transformations and compare the scheme with previous selective refinement schemes in both theoretical and experimental ways. In our comparison, we show that the complete scheme always generates selectively refined meshes with smaller numbers of vertices and faces than previous schemes for a given refinement criterion. The concept of dual pieces of the vertices in the vertex hierarchy plays a central role in the analysis of the transitive mesh space and the design of selective edge collapse and vertex split transformations.     

A template-based approach for parallel hexahedral two-refinement

We provide a template-based approach for generating locally refined all-hex meshes. We focus specifically on refinement of initially structured grids utilizing a 2-refinement approach where uniformly refined hexes are subdivided into eight child elements. The refinement algorithm consists of identifying marked nodes that are used as the basis for a set of four simple refinement templates. The target application for 2-refinement is a parallel grid-based all-hex meshing tool for high performance computing in a distributed environment. The result is a parallel consistent locally refined mesh requiring minimal communication and where minimum mesh quality is greater than scaled Jacobian 0.3 prior to smoothing.     

Feature aligned quad dominant remeshing using iterative local updates

In this paper we present a new algorithm which turns an unstructured triangle mesh into a quad dominant mesh with edges well aligned to the principal directions of the underlying surface. Instead of computing a globally smooth parameterization or integrating curvature lines along a tangent vector field, we simply apply an iterative relaxation scheme which incrementally aligns the mesh edges to the principal directions. We further obtain the quad dominant mesh by dropping the not-aligned diagonal edges from the triangle mesh. A post-processing stage is introduced to further improve the results. The major advantage of our algorithm is its conceptual simplicity since it is merely based on elementary mesh operations such as edge collapse, flip, and split. Various results are presented in the paper; they show a good alignment to surface features and rather uniform distribution of mesh vertices. This makes them well suited, e.g., as Catmull-Clark Subdivision control meshes.     

Procedural CAD Model Edge Tolerance Negotiation for Surface Meshing

Geometrical models output from CAD software often require modification before they may be used for analysis-quality mesh generation. This is due primarily to the inconsistencies in tolerances used by the CAD operator and the tolerances required for analysis. This paper presents a method for construction of watertight surface meshes directly on imperfect non-modified CAD models. The method is based on a hierarchical grid topology structure that defines a surface mesh by a grid and a collection of curves defining the boundary. Curve boundaries on component surfaces are iteratively split and merged according to user-set tolerances, allowing adjacent surface meshes to become computationally watertight via their shared edge curves. The collection of watertight surface meshes may then be made model-inde-pendent through interactive agglomeration of the surface meshes, followed by refinement and decimation sweeps to remove artifacts of original surface edges. Interactive procedures used for difficult cases are also explained, as are ongoing efforts for further automation.     

Anisotropic Surface Remeshing without Obtuse Angles

We present a novel anisotropic surface remeshing method that can efficiently eliminate obtuse angles. Unlike previous work that can only suppress obtuse angles with expensive resampling and Lloyd‐type iterations, our method relies on a simple yet efficient connectivity and geometry refinement, which can not only remove all the obtuse angles, but also preserves the original mesh connectivity as much as possible. Our method can be directly used as a post‐processing step for anisotropic meshes generated from existing algorithms to improve mesh quality. We evaluate our method by testing on a variety of meshes with different geometry and topology, and comparing with representative prior work. The results demonstrate the effectiveness and efficiency of our approach.     

Two-dimensional Delaunay-based anisotropic mesh adaptation

Science and engineering applications often have anisotropic physics and therefore require anisotropic mesh adaptation. In common with previous researchers on this topic, we use metrics to specify the desired mesh. Where previous approaches are typically heuristic and sometimes require expensive optimization steps, our approach is an extension of isotropic Delaunay meshing methods and requires only occasional, relatively inexpensive optimization operations. We use a discrete metric formulation, with the metric defined at vertices. To map a local sub-mesh to the metric space, we compute metric lengths for edges, and use those lengths to construct a triangulation in the metric space. Based on the metric edge lengths, we define a quality measure in the metric space similar to the well-known shortest-edge to circumradius ratio for isotropic meshes. We extend the common mesh swapping, Delaunay insertion, and vertex removal primitives for use in the metric space. We give examples demonstrating our scheme’s ability to produce a mesh consistent with a discontinuous, anisotropic mesh metric and the use of our scheme in solution adaptive refinement.     

Combinatorial Construction of Seamless Parameter Domains

The problem of seamless parametrization of surfaces is of interest in the context of structured quadrilateral mesh generation and spline-based surface approximation. It has been tackled by a variety of approaches, commonly relying on continuous numerical optimization to ultimately obtain suitable parameter domains. We present a general combinatorial seamless parameter domain construction, free from the potential numerical issues inherent to continuous optimization techniques in practice. The domains are constructed as abstract polygonal complexes which can be embedded in a discrete planar grid space, as unions of unit squares. We ensure that the domain structure matches any prescribed parametrization singularities (cones) and satisfies seamlessness conditions. Surfaces of arbitrary genus are supported. Once a domain suitable for a given surface is constructed, a seamless and locally injective parametrization over this domain can be obtained using existing planar disk mapping techniques, making recourse to Tutte's classical embedding theorem.     

Simplification of composite parametric surface meshes

This paper concerns the simplification of composite parametric surface meshes which conform to the boundary of each constituting patch. The goal is to eliminate the small edges which result from this boundary patch preserving constraint, provided that these small edges belong to an almost flat area. To this end, two tolerance areas with respect to the initial reference mesh are introduced to keep close to the surface. The reference mesh is then simplified and optimized (in terms of shape quality) so that the resulting mesh belongs to these tolerance areas. Several examples of surface meshes are provided in order to assess the efficiency of the simplification method.     

Enhanced medial-axis-based block-structured meshing in 2-D

New techniques are presented for using the medial axis to generate decompositions on which high quality block-structured meshes with well-placed mesh singularities can be generated. Established medial-axis-based meshing algorithms are effective for some geometries, but in general, they do not produce the most favourable decompositions, particularly when there are geometric concavities. This new approach uses both the topological and geometric information in the medial axis to establish a valid and effective arrangement of mesh singularities for any 2-D surface. It deals with concavities effectively and finds solutions that are most appropriate to the geometric shapes. Resulting meshes are shown for a number of example models.     

A Subspace Method for Fast Locally Injective Harmonic Mapping

We present a fast algorithm for low‐distortion locally injective harmonic mappings of genus 0 triangle meshes with and without cone singularities. The algorithm consists of two portions, a linear subspace analysis and construction, and a nonlinear non‐convex optimization for determination of a mapping within the reduced subspace. The subspace is the space of solutions to the Harmonic Global Parametrization (HGP) linear system [BCW17], and only vertex positions near cones are utilized, decoupling the variable count from the mesh density. A key insight shows how to construct the linear subspace at a cost comparable to that of a linear solve, extracting a very small set of elements from the inverse of the matrix without explicitly calculating it. With a variable count on the order of the number of cones, a tangential alternating projection method [HCW17] and a subsequent Newton optimization [CW17] are used to quickly find a low‐distortion locally injective mapping. This mapping determination is typically much faster than the subspace construction. Experiments demonstrating its speed and efficacy are shown, and we find it to be an order of magnitude faster than HGP and other alternatives.     

Progressive Lossless Mesh Compression Via Incremental Parametric Refinement

In this paper, we propose a novel progressive lossless mesh compression algorithm based on Incremental Parametric Refinement, where the connectivity is uncontrolled in a first step, yielding visually pleasing meshes at each resolution level while saving connectivity information compared to previous approaches. The algorithm starts with a coarse version of the original mesh, which is further refined by means of a novel refinement scheme. The mesh refinement is driven by a geometric criterion, in spirit with surface reconstruction algorithms, aiming at generating uniform meshes. The vertices coordinates are also quantized and transmitted in a progressive way, following a geometric criterion, efficiently allocating the bit budget. With this assumption, the generated intermediate meshes tend to exhibit a uniform sampling. The potential discrepancy between the resulting connectivity and the original one is corrected at the end of the algorithm. We provide a proof-of-concept implementation, yielding very competitive results compared to previous works in terms of rate/distortion trade-off.     

一种保持纹理的网面简化算法

在计算机视觉领域,三维网面的简化不仅要求保持物体形状和拓扑关系,还要求保持物体表面法线,纹理,颜色和边缘等物体特征,以使计算机视觉系统能有效地表示,描述,识别和理解物体和场景,为此讨论了一种基于边操作（边收缩,边分裂）,并具有颜色或灰度纹理特征保持的三维网面的简化算法,该算法将网面不对称最大距离作为形状改变测度,将邻域内颜色或灰度最大改变量作为纹理改变测试,从而在大量简化模型数据的同时,有效地保持了模型的几何形状,拓扑关系,颜色或灰度特征,以及网面顶点均匀分布。     

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.     

A nonconforming finite element method¶with anisotropic mesh grading¶for the incompressible Navier–Stokes equations¶in domains with edges

Any solution of the incompressible Navier–Stokes equations in three-dimensional domains with edges has anisotropic singular behaviour which is treated numerically by using anisotropic finite element meshes. The velocity is approximated by Crouzeix–Raviart (nonconforming 𝒫₁) elements and the pressure by piecewise constants. This method is stable for general meshes since the inf-sup condition is satisfied without minimal or maximal angle condition. The existence of solutions to the discrete problems follows. Consistency error estimates for the divergence equation are obtained for anisotropic tensor product meshes. As applications, the consistency error estimate for the Navier–Stokes solution and some discrete Sobolev inequalities are derived on such meshes. These last results provide optimal error estimates in the uniqueness case by the use of appropriately refined anisotropic tensor product meshes, namely, if N _e is the number of elements of the mesh, we prove that the optimal order of convergence h∼ N _e ^{− 1/3}. Received:July 2001 / Accepted: July 2002