The construction of improved‐quality mesh on a curved surface using mapping factors

Abstract

The Delaunay triangulation is broadly used on flat surfaces to generate well‐shaped elements. But the properties of Delaunay triangulation do not exist on curved surfaces whose Jacobians are different. In this paper we will present a modified algorithm to improve the shape of triangulation for the curved surface. The experiment results show that making use of “mapping factors” in the Delaunay triangulation and Laplacian method can produce better mesh (most aspect ratios≤3) on a curved surface.     

跟踪式偏振光三角法测头

针对三角法测量的不足,设计了一种跟踪式偏振光三角法测头。对三角测量法的理论分析表明减小测量范围能提高测量精度。测头结合表面跟踪方法与三角测量法,跟踪使测量范围不受限制;仅在小范围内进行三角法测量,测量精度大大提高。对金属表面的反射特性进行了分析和推导,得出镜面反射与漫反射具有不同的偏振特性。通过偏振滤光减少了镜面反射光对测量的影响,从而降低了对被测表面材质的要求。本文给出了测头结构和工作原理。试验表明,测头能测量镜面反射较强的金属表面,测头可自动跟踪表面,并可结合测距仪实现表面形状的高精度测量。     

一种裁剪曲面自适应三角剖分算法

本文介绍了一种裁剪曲面按精度三角剖分算法。三角剖分过程在参数域和曲面空间同时进行，参数域上控制三角片的拓扑关系，曲面空间进行精度检测。算法的核心思想是将裁剪曲面三角剖分视为约束剖分问题，从而使得三角形的细分操作拓展为有效域内插入散乱节点的三角剖分问题。算法简便、实用，三角化结果品质良好，已成功地应用于数控加工刀具轨迹干涉处理等具有精度要求的应用领域。     

Variational Delaunay approach to the generation of tetrahedral finite element meshes

We describe an algorithm which generates tetrahedral decomposition of a general solid body, whose surface is given as a collection of triangular facets. The principal idea is to modify the constraints in such a way as to make them appear in an unconstrained triangulation of the vertex set à priori. The vertex set positions are randomized to guarantee existence of a unique triangulation which satisfies the Delaunay empty‐sphere property. (Algorithms for robust, parallelized construction of such triangulations are available.) In order to make the boundary of the solid appear as a collection of tetrahedral faces, we iterate two operations, edge flip and edge split with the insertion of additional vertex, until all of the boundary facets are present in the tetrahedral mesh. The outcome of the vertex insertion is another triangulation of the input surfaces, but one which is represented as a subset of the tetrahedral faces. To determine if a constraining facet is present in the unconstrained Delaunay triangulation of the current vertex set, we use the results of Rajan which re‐formulate Delaunay triangulation as a linear programming problem. Copyright © 2001 John Wiley & Sons, Ltd.     

Possibilities of a triangulation laser method for measuring a surface of complex relief

Interconnection of roughness for a measured surface with the possible triangulation angle is studied and the limits for applying laser triangulation meters in which diffusive reflection is used are determined. __________ Translated from Metrologiya, No. 8. pp. 32–36, August, 2007.     

From medical images to anatomically accurate finite element grids

The successful application of computational modelling of blood flow for the planning of surgical and interventional procedures to treat cardiovascular diseases strongly depends on the rapid construction of anatomical models. The large individual variability of the human vasculature and the strong dependence of blood flow characteristics on the vessel geometry require modelling on a patient‐specific basis. Various image processing and geometrical modelling techniques are integrated for the rapid construction of geometrical surface models of arteries starting from medical images. These discretely defined surfaces are then used to generate anatomically accurate finite element grids for hemodynamic simulations. The proposed methodology operates directly in 3D and consists of three stages. In the first stage, the images are filtered to reduce noise and segmented using a region‐growing algorithm in order to obtain a properly defined boundary of the arterial lumen walls. In the second stage, a surface triangulation representing the vessel walls is generated using a direct tessellation of the boundary voxels. This surface is then smoothed and the quality of the resulting triangulation is improved. Finally, in the third stage, the triangulation is subdivided into so‐called discrete surface patches for surface gridding, the desired element size distribution is defined and the finite element grid generated. Copyright © 2001 John Wiley & Sons, Ltd.     

基于球面三角网格逼近的等距曲面逼近算法

给出了一种基于球面三角网格逼近的等距曲面逼近新算法。利用三角网格逼近基球面,然后计算此三角网格按中心沿在曲面扫凉而成空间区域的边界作为等距曲面的逼近。该算法计算简单,方便地解决了整体误差问题,而且所得到的逼近曲面是与原曲面同次数的NURBS曲面。     

金属表面对光学非接触测头的影响

首先简单介绍了三角法测头的结构和工作原理,对金属表面的反射特性进行了分析和推导,提出了三解法测量金属表面时存在的几个问题以及解决方案。     

基于Delaunay三角剖分的层析图像离散数据表面重建算法

提出一种基于Delaunay三角剖分思想的层析图像离散数据的表面重建算法。该算法考虑了组成最优重建表面的三角片的形态特点,以三角片集的内角矢量最大为优化目标,根据Delaunay三角剖分思想,采用局部判定的方法,逐次选取最佳几何形态的三角片,组成最优的重建表面。     

A new automatic hexahedral mesher based on cutting

A new method is presented leading to a 20‐node brick element mesh for an arbitrary structure based on a triangulation of the structure's surface. Starting from a hexahedral master mesh encompassing the structure, the elements which are intersected by the triangulation are determined, cut and remeshed. The resulting hexahedral mesh can be tied to the underlying elements by multiple point constraints or can be continued throughout the complete structure leading to a pure 20‐node brick mesh. Several examples show the effectiveness of the method. Copyright © 2001 John Wiley & Sons, Ltd.     

Graded tetrahedral finite element meshes

Vertices in the body centred cubic (bcc) lattice are used to create a tetrahedral spatial decomposition. With this spatial decomposition an octree approach is combined with Delaunay triangulations to decompose solids into tetrahedral finite element meshes. Solids must have their surfaces triangulated and the vertices in the triangulation are finite element nodes. Local densities of interior tetrahedra are controlled by the densities of surface triangles. Accuracy of the decomposition into finite elements depends on the accuracy of the surface triangulation which can be constructed with state of the art computer aided design systems.     

An investigation into design of fair surfaces over irregular domains using data-dependent triangulation

Design of fair surfaces over irregular domains is a fundamental problem in computer-aided geometric design (CAGD), and has applications in engineering sciences (in aircraft, automobile, ship science etc.). In the design of fair surfaces over irregular domains defined over scattered data, it was widely accepted till recently that the classical Delaunay triangulation be used because of its global optimum property. However, in recent times it has been shown that for continuous piecewise linear surfaces, improvements in the quality of fit can be achieved if the triangulation pattern is made dependent upon some topological or geometric property of the data set or is simply data dependent. The fair surface is desired because it ensures smooth and continuous surface planar cuts, and these in turn ensure smooth and easy production of the surface in CAD/CAM, and favourable resistance properties. In this paper, we discuss a method for construction of C¹ piecewise polynomial parametric fair surfaces which interpolate prescribed ℜ³ scattered data using spaces of parametric splines defined on H³ triangulation. We show that our method is more specific to the cases when the projection on a 2-D plane may consist of triangles of zero area, numerically stable and robust, and computationally inexpensive and fast. Numerical examples dealing with surfaces approximated on plates, and on ships have been presented.     

裁剪曲面的三角化及图形显示

结合自主版权的超人ＣＡＤ／ＣＡＭ系统的开发，本文提出了一种适合于裁剪曲面图形显示的曲面三角化算法，该算法将曲面的三角化转化为曲面参数域的三角化，并将二维图形的集合运算与Ｄｅｌａｕｎａｙ三角剖分应有和于曲面参数域边界的处理，从而使裁剪曲面在边界上的三角形分布均匀。     

‘Ultimate’ robustness in meshing an arbitrary polyhedron

Given a boundary surface mesh (a set of triangular facets) of a polyhedron, the problem of deciding whether or not a triangulation exists is reported to be NP‐hard. In this paper, an algorithm to triangulate a general polyhedron is presented which makes use of a classical Delaunay triangulation algorithm, a phase for recovering the missing boundary facets by means of facet partitioning, and a final phase that makes it possible to remove the additional points defined in the previous step. Following this phase, the resulting mesh conforms to the given boundary surface mesh. The proposed method results in a discussion of theoretical interest about existence and complexity issues. In practice, however, the method should provide what we call ‘ultimate’ robustness in mesh generation methods. Copyright © 2003 John Wiley & Sons, Ltd.     

Efficient three-dimensional Delaunay triangulation with automatic point creation and imposed boundary constraints

A method is described which constructs three-dimensional unstructured tetrahedral meshes using the Delaunay triangulation criterion. Several automatic point creation techniques will be highlighted and an algorithm will be presented which can ensure that, given an initial surface triangulation which bounds a domain, a valid boundary conforming assembly of tetrahedra will be produced. Statistics of measures of grid quality are presented for several grids. The efficiency of the proposed procedure reduces the computer time for the generation of realistic unstructured tetrahedral grids to the order of minutes on workstations of modest computational capabilities.     

Measurement of surface roughness profile by a triangulation method

Some aspects of measuring surface roughness parameters using a laser triangulation method are considered. A connection is established between surface roughness and scattering indicatrices with probing radiation polarization parameters of a semiconductor laser. A marked effect is noted of the form and position of the polarization plane on the measurement error for linear values. __________ Translated from Metrologiya, No. 6. pp. 21–27, June, 2008.     

New longest-edge algorithms for the refinement and/or improvement of unstructured triangulations

In this paper I introduce a new mathematical tool for dealing with the refinement and/or the improvement of unstructured triangulations: the Longest-Edge Propagation Path associated with each triangle to be either refined and/or improved in the mesh. This is defined as the (finite) ordered list of successive neighbour triangles having longest-edge greater than the longest edge of the preceding triangle in the path. This ideal is used to introduce two kinds of algorithms (which make use of a Backward Longest-Edge point insertion strategy): (1) a pure Backward Longest-Edge Refinement Algorithm that produces the same triangulations as previous longest-edge algorithms in a more efficient, direct and easy-to-implement way; (2) a new Backward Longest-Edge Improvement Algorithm for Delaunay triangulations, suitable to deal (in a reliable, robust and effective way) with the three important related aspects of the (triangular) mesh generation problem: mesh refinement, mesh improvement, and automatic generation of good-quality surface and volume triangulation of general geometries including small details. The algorithms and practical issues related with their implementation (both for the polygon and surface quality triangulation problems) are discussed in this paper. In particular, an effective boundary treatment technique is also discussed. The triangulations obtained with the LEPP–Delaunay algorithm have smallest angles greater than 30° and are, in practice, of optimal size. Furthermore, the LEPP–Delaunay algorithms naturally generalize to three-dimensions. © 1997 by John Wiley & Sons, Ltd.     

A feature‐preserving volumetric technique to merge surface triangulations

Several extensions and improvements to surface merging procedures based on the extraction of iso‐surfaces from a distance map defined on an adaptive background grid are presented. The main objective is to extend the application of these algorithms to surfaces with sharp edges and corners. In order to deal with objects of different length scales, the initial background grids are created using a Delaunay triangulation method and local voxelizations. A point enrichment technique that introduces points into the background grid along detected surface features such as ridges is used to ensure that these features are preserved in the final merged surface. The surface merging methodology is extended to include other Boolean operations between surface triangulations. The iso‐surface extraction algorithms are modified to obtain the correct iso‐surface for multi‐component objects. The procedures are demonstrated with various examples, ranging from simple geometrical entities to complex engineering applications. The present algorithms allow realistic modelling of a large number of complex engineering geometries using overlapping components defined discretely, i.e. via surface triangulations. This capability is very useful for grid generation starting from data originated in measurements or images. Copyright © 2002 John Wiley & Sons, Ltd.     

飞机表面划痕非接触测量仪的研究

介绍了一种飞机表面划痕非接触测量仪。它以激光三角传感器为主要组成部件，并附以机械扫描装置，可完成被测飞机表面划痕的非接触测量。在分析了被测表面散、反射特性的基础上，给出了激光三角传感器正确放置方式，并提出改善测量精度的传感器姿态调整法。针对浅划痕测量时噪声较大的特点，提出利用子波分析的方法突出被测划痕形貌的信号处理方法，实验表明了此方法的可行性。本测量仪具有非接触测量、测量范围大、精度高、结构简单、成本较低的特点。     

Algorithms for refining triangular grids suitable for adaptive and multigrid techniques

Two general algorithms for refining triangular computational meshes based on the bisection of triangles by the longest side are presented and discussed. The algorithms can be applied globally or locally for selective refinement of any conforming triangulation and always generate a new conforming triangulation after a finite number of interactions even when locally used. The algorithms also ensure that all angles in subsequent refined triangulations are greater than or equal to half the smallest angle in the original triangulation; the shape regularity of all triangles is maintained and the transition between small and large triangles is smooth in a natural way. Proofs of the above properties are presented. The second algorithm is a simpler, improved version of the first which retains most of the properties of the latter. The algorithms can be used either for constructing irregular computational meshes or for locally refining any given triangulation. In this sense they can be adequately combined with adaptive and/or multigrid techniques for solving finite element systems. Examples of the application of the algorithms are given and two possible generalizations are pointed out.