A Delaunay Refinement Algorithm for Quality 2-Dimensional Mesh Generation

We present a simple new algorithm for triangulating polygons and planar straightline graphs, It provides "shape" and "size" guarantees:

• All triangles have a bounded aspect ratio.

• The number of triangles is within a constant factor of optimal.

Such "quality" triangulations are desirable as meshes for the finite element method, in which the running time generally increases with the number of triangles, and where the convergence and stability may be hurt by very skinny triangles. The technique we use-successive refinement of a Delaunay triangulation-extends a mesh generation technique of Chew by allowing triangles of varying sizes. Compared with previous quadtree-based algorithms for quality mesh generation, the Delaunay refinement approach is much simpler and generally produces meshes with fewer triangles. We also discuss an implementation of the algorithm and evaluate its performance on a variety of inputs.     

The focal geometry of circular and conical meshes

Circular meshes are quadrilateral meshes all of whose faces possess a circumcircle, whereas conical meshes are planar quadrilateral meshes where the faces which meet in a vertex are tangent to a right circular cone. Both are amenable to geometric modeling – recently surface approximation and subdivision-like refinement processes have been studied. In this paper we extend the original defining property of conical meshes, namely the existence of face/face offset meshes at constant distance, to circular meshes. We study the close relation between circular and conical meshes, their vertex/vertex and face/face offsets, as well as their discrete normals and focal meshes. In particular we show how to construct a two-parameter family of circular (resp., conical) meshes from a given conical (resp., circular) mesh. We further discuss meshes which have both properties and their relation to discrete surfaces of negative Gaussian curvature. The offset properties of special quadrilateral meshes and the three-dimensional support structures derived from them are highly relevant for computational architectural design of freeform structures. Another aspect important for design is that both circular and conical meshes provide a discretization of the principal curvature lines of a smooth surface, so the mesh polylines represent principal features of the surface described by the mesh.      

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.     

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.     

Optimal algebraic multilevel preconditioning for local refinement along a line

The application of some recently proposed algebraic multilevel methods for the solution of two-dimensional finite element problems on nonuniform meshes is studied. The locally refined meshes are created by the newest vertex mesh refinement method. After the introduction of this refinement technique it is shown that, by combining levels of refinement, a preconditioner of optimal order can be constructed for the case of local refinement along a line. Its relative condition number is accurately estimated. Numerical tests demonstrating the performance of the proposed preconditioners will be reported in a forthcoming paper.     

Four-triangles adaptive algorithms for RTIN terrain meshes

We present a refinement and coarsening algorithm for the adaptive representation of Right-Triangulated Irregular Network (RTIN) meshes. The refinement algorithm is very simple and proceeds uniformly or locally in triangle meshes. The coarsening algorithm decreases mesh complexity by reducing unnecessary data points in the mesh after a given error criterion is applied. We describe the most important features of the algorithms and give a brief numerical study on the propagation associated with the adaptive scheme used for the refinement algorithm. We also present a comparison with a commercial tool for mesh simplification, Rational Reducer, showing that our coarsening algorithm offers better results in terms of accuracy of the generated meshes.     

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.     

Strongly regular family of boundary-fitted tetrahedral meshes of bounded C2 domains

We give a constructive proof that for any bounded domain of the class C² there exists a strongly regular family of boundary-fitted tetrahedral meshes. We adopt a refinement technique introduced by K?í?ek and modify it so that a refined mesh is again boundary-fitted. An alternative regularity criterion based on similarity with the Sommerville tetrahedron is used and shown to be equivalent to other standard criteria. The sequence of regularities during the refinement process is estimated from below and shown to converge to a positive number by virtue of the convergence of q-Pochhammer symbol. The final result takes the form of an implication with an assumption that can be obviously fulfilled for any bounded C² domain.     

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.     

Toward anisotropic mesh construction and error estimation in the finite element method

Directional, anisotropic features like layers in the solution of partial differential equations can be resolved favorably by using anisotropic finite element meshes. An adaptive algorithm for such meshes includes the ingredients Error estimation and Information extraction/Mesh refinement. Related articles on a posteriori error estimation on anisotropic meshes revealed that reliable error estimation requires an anisotropic mesh that is aligned with the anisotropic solution. To obtain anisotropic meshes the so‐called Hessian strategy is used, which provides information such as the stretching direction and stretching ratio of the anisotropic elements. This article combines the analysis of anisotropic information extraction/mesh refinement and error estimation (for several estimators). It shows that the Hessian strategy leads to well‐aligned anisotropic meshes and, consequently, reliable error estimation. The underlying heuristic assumptions are given in a stringent yet general form. Numerical examples strengthen the exposition. Hence the analysis provides further insight into a particular aspect of anisotropic error estimation. © 2002 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 18: 625–648, 2002; DOI 10.1002/num.10023     

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.     

Delaunay refinement algorithms for triangular mesh generation

Delaunay refinement is a technique for generating unstructured meshes of triangles for use in interpolation, the finite element method, and the finite volume method. In theory and practice, meshes produced by Delaunay refinement satisfy guaranteed bounds on angles, edge lengths, the number of triangles, and the grading of triangles from small to large sizes. This article presents an intuitive framework for analyzing Delaunay refinement algorithms that unifies the pioneering mesh generation algorithms of L. Paul Chew and Jim Ruppert, improves the algorithms in several minor ways, and most importantly, helps to solve the difficult problem of meshing nonmanifold domains with small angles.

Although small angles inherent in the input geometry cannot be removed, one would like to triangulate a domain without creating any new small angles. Unfortunately, this problem is not always soluble. A compromise is necessary. A Delaunay refinement algorithm is presented that can create a mesh in which most angles are 30° or greater and no angle is smaller than arcsin[( , where φ60°is the smallest angle separating two segments of the input domain. New angles smaller than 30° appear only near input angles smaller than 60°. In practice, the algorithm's performance is better than these bounds suggest.

Another new result is that Ruppert's analysis technique can be used to reanalyze one of Chew's algorithms. Chew proved that his algorithm produces no angle smaller than 30° (barring small input angles), but without any guarantees on grading or number of triangles. He conjectures that his algorithm offers such guarantees. His conjecture is conditionally confirmed here: if the angle bound is relaxed to less than 26.5°, Chew's algorithm produces meshes (of domains without small input angles) that are nicely graded and size-optimal.     

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.     

Method for constructing meshes adapting to the solution of boundary value problems for ordinary differential equations of the second and fourth orders

To solve boundary value problems for ordinary differential equations of the second and fourth orders, we suggest a method for constructing a sequence of adaptively refined and coarsened meshes in a version of the finite element method with piecewise cubic Hermite basis functions. The construction of the meshes is based on C-norm estimates of the variation in the approximate solution or in the value of the functional to be minimized under the addition of a test point to a mesh interval or the deletion of a point from the current mesh. We present the results of numerical experiments used to assess the efficiency of the method. By way of example, problems whose solutions have singularities of the boundary layer type were used in these experiments. We carry out a comparison with a version of the method based on the uniform mesh refinement.     

Parallel anisotropic mesh adaptivity with dynamic load balancing for cardiac electrophysiology

Simulations in cardiac electrophysiology generally use very fine meshes and small time steps to resolve highly localized wavefronts. This expense motivates the use of mesh adaptivity, which has been demonstrated to reduce the overall computational load. However, even with mesh adaptivity performing such simulations on a single processor is infeasible. Therefore, the adaptivity algorithm must be parallelised. Rather than modifying the sequential adaptive algorithm, the parallel mesh adaptivity method introduced in this paper focuses on dynamic load balancing in response to the local refinement and coarsening of the mesh. In essence, the mesh partition boundary is perturbed away from mesh regions of high relative error, while also balancing the computational load across processes. The parallel scaling of the method when applied to physiologically realistic heart meshes is shown to be good as long as there are enough mesh nodes to distribute over the available parallel processes. It is shown that the new method is dominated by the cost of the sequential adaptive mesh procedure and that the parallel overhead of inter-process data migration represents only a small fraction of the overall cost.     

An adaptive boundary element method for the exterior Stokes problem in three dimensions

^** Email: vjervin{at}clemson.edu^*** Email: norbert.heuer{at}brunel.ac.uk We present an adaptive refinement strategy for the h-versionof the boundary element method with weakly singular operatorson surfaces. The model problem deals with the exterior Stokesproblem, and thus considers vector functions. Our error indicatorsare computed by local projections onto 1D subspaces definedby mesh refinement. These indicators measure the error separatelyfor the vector components and allow for component-independentadaption. Assuming a saturation condition, the indicators giverise to an efficient and reliable error estimator. Also we describehow to deal with meshes containing quadrilaterals which arenot shape regular. The theoretical results are underlined bynumerical experiments. To justify the saturation assumption,in the Appendix we prove optimal lower a priori error estimatesfor edge singularities on uniform and graded meshes.     

Efficient implementation of WENO schemes to nonuniform meshes

Most of the standard papers about the WENO schemes consider their implementation to uniform meshes only. In that case the WENO reconstruction is performed efficiently by using the algebraic expressions for evaluating the reconstruction values and the smoothness indicators from cell averages. The coefficients appearing in these expressions are constant, dependent just on the scheme order, not on the mesh size or the reconstruction function values, and can be found, for example, in Jiang and Shu (J Comp Phys 126:202–228, 1996). In problems where the geometrical properties must be taken into account or the solution has localized fine scale structure that must be resolved, it is computationally efficient to do local grid refinement. Therefore, it is also desirable to have numerical schemes, which can be applied to nonuniform meshes. Finite volume WENO schemes extend naturally to nonuniform meshes although the reconstruction becomes quite complicated, depending on the complexity of the grid structure. In this paper we propose an efficient implementation of finite volume WENO schemes to nonuniform meshes. In order to save the computational cost in the nonuniform case, we suggest the way for precomputing the coefficients and linear weights for different orders of WENO schemes. Furthermore, for the smoothness indicators that are defined in an integral form we present the corresponding algebraic expressions in which the coefficients obtained as a linear combination of divided differences arise. In order to validate the new implementation, resulting schemes are applied in different test examples.      

Boundary conforming Delaunay mesh generation

A boundary conforming Delaunay mesh is a partitioning of a polyhedral domain into Delaunay simplices such that all boundary simplices satisfy the generalized Gabriel property. It’s dual is a Voronoi partition of the same domain which is preferable for Voronoi-box based finite volume schemes. For arbitrary 2D polygonal regions, such meshes can be generated in optimal time and size. For arbitrary 3D polyhedral domains, however, this problem remains a challenge. The main contribution of this paper is to show that boundary conforming Delaunay meshes for 3D polyhedral domains can be generated efficiently when the smallest input angle of the domain is bounded by arccos 1/3 ≈ 70.53°. In addition, well-shaped tetrahedra and an appropriate mesh size can be obtained. Our new results are achieved by reanalyzing a classical Delaunay refinement algorithm. Note that our theoretical guarantee on the input angle (70.53°) is still too strong for many practical situations. We further discuss variants of the algorithm to relax the input angle restriction and to improve the mesh quality.     

Maximum norm a posteriori error estimates for a 1D singularly perturbed semilinear reaction-diffusion problem

^{A singularly perturbed semilinear two-point boundary-value problemis discretized on arbitrary non-uniform meshes. We present second-ordermaximum norm a posteriori error estimates that hold true uniformlyin the small parameter. Their application to monitor-functionequidistribution and a posteriori mesh refinement are discussed.Numerical results are presented that support our theoreticalestimates.}     

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.