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.     

Polyhedrization of an arbitrary 3D point set

Given a 3D point set, the problem of defining the volume associated, dividing it into a set of regions (elements) and defining a boundary surface is tackled.Several physical problems need to define volume domains, boundary surfaces and approximating functions from a given point distribution. This is for instance the case of particle methods, in which all the information is the particle positions and there are not boundary surfaces definition.Until recently, all the FEM mesh generators were limited to the generation of simple elements as tetrahedral or hexahedral elements (or triangular and quadrangular in 2D problems). The reason of this limitation was the lack of any acceptable shape function to be used in other kind of geometrical elements. Nowadays, there are several acceptable shape functions for a very large class of polyhedra. These new shape functions, together with a generalization of the Delaunay tessellation presented in this paper, gives an optimal marriage and a powerful tool to solve a large variety of physical problems by numerical methods.The domain partition into polyhedra presented here is not a standard mesh generation. The problem here is: for a given node distribution to find a suitable boundary surface and a suitable mesh to be used in the solution of a physical problem by a numerical method. To include new nodes or change their positions is not allowed.     

Automatic construction of boundary parametrizations for geometric multigrid solvers

We present an algorithm that constructs parametrizations of boundary and interface surfaces automatically. Starting with high-resolution triangulated surfaces describing the computational domains, we iteratively simplify the surfaces yielding a coarse approximation of the boundaries with the same topological type. While simplifying we construct a function that is defined on the coarse surface and whose image is the original surface. This function allows access to the correct shape and surface normals of the original surface as well as to any kind of data defined on it. Such information can be used by geometric multigrid solvers doing adaptive mesh refinement. Our algorithm runs stable on all types of input surfaces, including those that describe domains consisting of several materials. We have used our method with success in different fields and we discuss examples from structural mechanics and biomechanics. Editorial responsibility: P. Deuflhard     

PolyFront: an algorithm for fast generation of high quality triangular mesh

In this article the authors present PolyFront, a new triangulation algorithm for two dimensional domains with holes. PolyFront is based on a normal offsetting technique, where a domain is triangulated starting from a discretization of its boundary and constructing the mesh layer by layer going toward the interior of the domain. The authors propose some numerical experiments to compare this algorithm with other four mesh generators. This comparison shows that the algorithm gives good quality meshes with reduced computational time.     

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.     

Point placement algorithms for Delaunay triangulation of polygonal domains

In some applications of triangulation, such as finite-element mesh generation, the aim is to triangulate a given domain, not just a set of points. One approach to meeting this requirement, while maintaining the desirable properties of Delaunay triangulation, has been to enforce the empty circumcircle property of Delaunay triangulation, subject to the additional constraint that the edges of a polygon be covered by edges of the triangulation. In finite-element mesh generation it is usually necessary to include additional points besides the vertices of the domain boundary. This motivates us to ask whether it is possible to trinagulate a domain by introducing additional points in such a manner that the Delaunay triangulation of the points includes the edges of the domain boundary. We present algorithms that given a multiply connected polygonal domain withN vertices, placeK additional points on the boundary inO(N logN + K) time such that the polygon is covered by the edges of the Delaunay triangulation of theN + K points. Furthermore,K is the minimum number of additional points such that a circle, passing through the endpoints of each boundary edge segment, exists that does not contain in its interior any other part of the domain boundary. We also show that by adding only one more point per edge, certain degeneracies that may otherwise arise can be avoided.     

Generalizing the advancing front method to composite surfaces in the context of meshing constraints topology

Being able to automatically mesh composite geometry is an important issue in the context of CAD–FEA integration. In some specific contexts of this integration, such as using virtual topology or meshing constraints topology (MCT), it is even a key requirement. In this paper, we present a new approach to automatic mesh generation over composite geometry. The proposed mesh generation approach is based on a generalization of the advancing front method (AFM) over curved surfaces. The adaptation of the AFM to composite faces (composed of multiple boundary representation (B-Rep) faces) involves the computation of complex paths along these B-Rep faces, on which progression of the advancing front is based. Each mesh segment or mesh triangle generated through this progression on composite geometry is likely to lie on multiple B-Rep faces and consequently, it is likely to be associated with a composite definition across multiple parametric spaces. Collision tests between new front segments and existing mesh elements also require specific and significant adaptations of the AFM, since a given front segment is also likely to lie on multiple B-Rep faces. This new mesh generation approach is presented in the context of MCT, which requires being able to handle composite geometry along with non-manifold boundary configurations, such as edges and vertices lying in the interior domain of B-Rep faces.     

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.     

基于波前法的参数曲面有限元网格生成算法

为克服参数曲面有限元网格生成中的单元形状映射畸变问题,提出一种曲面有限元网格自动生成算法.该算法由弹性矢量确定曲面上新节点的生成方向和空间位置,利用相应的参数域网格进行新单元拓扑相容性判断.在生成闭曲面网格时,通过添加参/虚边界棱边对闭曲面边界进行调整,确保闭曲面边界信息相对其参数域的完整性;在给出闭曲面极点初始化方法和适当设置单元边线段相等条件的基础上,该算法适用于各种不同形式闭曲面的网格自动生成.实验算例表明,文中算法可生成质量良好的参数曲面和组合面有限元网格.     

LayTracks3D: A new approach for meshing general solids using medial axis transform

This paper presents an extension of the all-quad meshing algorithm called LayTracks to generate high quality hex-dominant meshes of general solids. LayTracks3D uses the mapping between the Medial Axis (MA) and the boundary of the 3D domain to decompose complex 3D domains into simpler domains called Tracks. Tracks in 3D have no branches and are symmetric, non-intersecting, orthogonal to the boundary, and the shortest path from the MA to the boundary. These properties of tracks result in desired meshes with near cube shape elements at the boundary, structured mesh along the boundary normal with any irregular nodes restricted to the MA, and sharp boundary feature preservation. The algorithm has been tested on a few industrial CAD models and hex-dominant meshes are shown in the Results section. Work is underway to extend LayTracks3D to generate all-hex meshes.     

三维地质界面网格模型构建算法研究

三维地质模型主要包含地质构造模型和地质属性模型。提出一种局部映射-边界控制的曲面三角化网格模型构建算法,与映射法相比,减少三维空间点映射到二维平面的计算过程,避免因多点到一点的映射关系而生成错误的三角化网格模型。基于地质测量数据特点,原始地质数据经处理后采用点集合形式表示,基于点集数据构建三维三角化网格模型,模拟地质界面的展布形态,控制三角网格质量。采用两种网格边界控制方法,在有边界约束数据和无边界约束数据条件下均能自动更新地质界面三角化网格模型边界。基于断层点数据集测试并展示算法构建的三维三角化网格模型可视化效果,通过断层面三角化网格模型能够反映断层面之间空间位置关系。     

Mesh deformation-based multi-tissue mesh generation for brain images

Multi-tissue meshing is necessary for the realistic building of a biomechanical model of the brain, which has been widely used in brain surgery simulation, brain shift, and non-rigid registration. A two step multi-tissue mesher is developed. First, a coarse multi-tissue mesh is generated by redistributing labels of a body-centered cubic (BCC) mesh. Second, all the surfaces of the submeshes are deformed to their corresponding tissue boundaries. To deform the mesh, two strategies are developed. One is based on a point-based registration (PBR) and the other is based on a robust point matching (RPM). The PBR method explicitly calculates the correspondence, which takes both smoothing and quality into account, then resolves the displacement vector by minimizing an energy function. Unlike PBR method, RPM does not require the correspondence between the source points and the target points to be known in advance. To simultaneously resolve the displacement vector and the correspondence, the Expectation and Maximization optimization is employed to alternately estimate the correspondence and the displacement vector. To effectively cope with outliers, least trimmed square, a robust regression technique, is employed to correct the regression bias induced by outliers. Both methods are effective in deforming the multi-tissue mesh. However, the PBR method favors quality and smoothing, and the RPM method favors fidelity. The resulting mesh is characterized by its flexible control of four mesh properties: (1) tissue-dependent resolution, (2) fidelity to tissue boundaries, (3) smoothness of mesh surfaces, and (4) element quality. Each mesh property can be controlled on a tissue level. Our experiments conducted on synthetic data, clinic MRI, visible human data, and brain atlas effectively demonstrate these features of this multi-tissue mesher.     

Optimal design for 2D wave equations

In this paper We consider a problem of optimal design in 2D for the wave equation with Dirichlet boundary conditions. We introduce a finite element discrete version of this problem in which the domains under consideration are polygons defined on the numerical mesh. We prove that, as the mesh size tends to zero, any limit, in the sense of the complementary-Hausdorff convergence, of discrete optimal shapes is an optimal domain for the continuous optimal design problem. We work in the functional and geometric setting introduced by V. ?veràk in which the domains under consideration are assumed to have an a priori limited number of holes. We present in detail a numerical algorithm and show the efficiency of the method through various numerical experiments.     

用C-C细分法和流形方法构造G2连续的自由型曲面

通过改进Cotrina等利用流形方法构造n边曲面片的算法,以C-C细分网格奇异点的5一环作为控制网构造出了带有均匀三次B样条边界的n边曲面片,使得该曲面片和C-C细分曲面G^2拼接．在此基础上,讨论了C-C细分曲面中n边域的构造和填充,从而为基于任意拓扑网格构造低次G^2连续曲面的问题给出了一个有效的解决方案,实现了用流形方法构造的曲面和C-C细分曲面的融合．最后,给出了几个具体算例．     

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.     

网格参数化研究进展

网格参数化是计算机图形学和数字几何处理的基本工具,有着广泛的应用背景.对网格参数化的研究进展进行了综述,主要从参数域和参数化质量两个方面介绍了网格参数化的研究现状.根据参数域的不同,讨论了平面参数化、基网格参数化、球面参数化以及曲面间的交叉参数化;根据参数化质量的不同,介绍了保长度的参数化、保特征的参数化以及致力于参数域简单的参数化.对参数化进行了分类介绍和讨论分析,概括介绍了每类方法的主要思想,讨论了每类方法的主要特性,对其中一些方法进行了比较分析,并对参数化方法存在的难点问题和未来可能的研究方向进行了总结,以期对参数化的研究进展有全面的了解.     

法向插值偏移曲面

提出一种大规模模型表示方法——法向插值偏移曲面．将模型表示为一个简单的基曲面以及分布在基曲面上的标量偏移场,它具有结构紧凑并易于处理的特点．提出的几何模型由三角网格表示转化为法向插值偏移曲面表示的转化算法,通过原模型的受限简化获得基曲面,利用基曲面上法向量的可插值特性,在简化过程中建立并维护其与原模型之间的一一映射,并将其作为简化限制条件．实验结果表明,基于法向插值偏移曲面的复合模型表示方法精确而高效．     

N-sided patches with B-spline boundaries

We present a method for constructing an n-sided patch of parametric surface, with n greater than 2. The main property of the resulting patch is that its boundary coincides with a B-spline. Thus, it can easily be connected to given B-spline surfaces with fixed continuity conditions.

The patch is built from a star-shaped input mesh that outlines a generic n-hole and a surface in a vicinity of the hole. The main advantages of the method are the following: continuity conditions of arbitrary order k can be imposed; the mesh involved can have an arbitrary number of sides and an arbitrary shape (convex or not); the simplicity of the construction process makes it an easy and flexible method; and finally, the surface near the boundary is a B-spline with piecewise uniform knot sequences and whose control points are vertices of the mesh (both knot sequences and control points are easily computed). We give implementation details for evaluating a surface point and show that the de Boor algorithm can be exploited for efficiency.     

Reduce the stretch in surface flattening by finding cutting paths to the surface boundary

This paper presents a method for finding cutting paths on a 3D triangular mesh surface to reduce the stretch in the flattened surface. The cutting paths link the surface boundary and the nodes where the Gaussian curvature is high, and their total length is minimized. First, a linear algorithm for computing an approximate boundary geodesic distance map is introduced; the map encapsulates the undirected geodesic distance from every triangular node to the surface boundary approximately. This is followed by determining the undirected shortest paths passing through all the nodes where the Gaussian curvature is larger than a threshold. The cutting paths walk along the triangular edges of the given surface. Compared with other similar approaches, our method reaches a faster speed, and can deal with surfaces with widely distributed curvatures.     

曲率约束的隐式曲面三角网格化

提出一种有效的隐式曲面三角网格化算法。从隐式曲面上的一个种子点开始,生成网格的边界作为扩张多边形,且该多边形最小角对应的顶点为扩张点,计算从扩张点处欲生成的三角网格,为了防止新生成的三角网格和已经存在的三角网格重叠,要进行冲突检测。在隐式曲面三角网格化的过程中,扩张多边形是不断变化的,需要重复上述步骤,直至没有扩张多边形时结束。该算法分别应用于解析隐式曲面和变分隐式曲面的三角网格化。实验结果表明,该算法不需要重新网格化的步骤,生成的三角网格具有较高的质量,且三角网格随曲率适应性变化,因此说明了该算法的有效性。