基于局部三维Delaunay的插值网格边界增量构造算法

网格构造的质量和效率是插值于大规模测量点三角网格构造算法的关键,但在算法中既保证插值网格的三维Delaunay性质又实现网格的线性构造仍存在困难。笔者针对此问题,提出了基于局部三维Delaunay的插值网格边界增量构造算法,利用网格的局部Delaunay构造及其边界的循环膨胀、分裂及自裁减操作实现整个模型的自动构造。应用实例表明,算法在保证构造网格满足三维Delaunay性质的同时,线性构造任意拓扑结构的三角网格模型。     

三角网格曲面模型的拟均匀细化算法

提出了一种无需计算曲面解析表示形式的三角网格曲面模型拟均匀细化算法.该算法首先将曲面体表面离散化得到初始网格;然后对初始网格进行区域标定,得到互斥子区域,藉此将空间网格曲面拟均匀细化问题转化为一系列的平面网格细化问题;其次再根据给定的网格细化间距对每个子区域进行拟均匀细化;最后对所有网格进行整体优化,从而实现了任意网格曲面模型的拟均匀细化.实验证明,提出的算法操作简单,效率高,细化后得到的网格质量高.     

三维Delaunay剖分的断层直接插入算法

研究了在三维空间中进行的Delaunay四面体剖分。在讨论了四面体网格与插入的受限平面数据的各种相交构形的基础上,提出了一种断层直接插入的算法。该算法可以应用于三维数据点集的受限四面体剖分,也可以应用于不同的数据场网格之间的相交运算等问题。     

基于Voronoi最小邻近点集的Delaunay三角化方法

针对局部条件下网格生成的需求,提出一种基于节点的Delaunay三角化生成算法,该算法以Delaunay三角形及其对偶Voronoi图的局部性特征为基础,通过在局部搜索最小Voronoi邻近点集,来生成约束点附近的局部网格,通过建立背景索引网格,来提高算法效率。给出算法的原理证明、程序实现、效率分析和测试结果,并给出了算法的应用领域。     

二维任意域约束Delaunay三角化的实现

本文设计了一种逐点加入一局部换边法,提出并证明了二维约束边在约束Ｄｅｌａｕｎａｙ三角化中存在的条件,并据此用中点加点法实现了二维任意域的Ｄｅｌａｕｎａｙ三角剖分,生成的网格均符合Ｄｅｌａｕｎａｙ优化准则,网格的优化在网格生成过程中完成,算法复杂度与点数呈近似线性关系,给出了算法在平面域剖分和包含复杂断层的石油地质勘探散乱数据点集剖分的应用实例。     

一种利用Delaunay三角剖分的碰撞检测算法

虚拟现实中物体对象分布及运动情况呈现复杂多样,碰撞检测算法很难达到实时性和准确性的要求.提出了一种基于Delaunay三角剖分的多物体碰撞检测实时算法.该算法运用包围体紧密拟合物体对象,以包围体的中心构建离散数据点集,生成Delaunay三角网格,实施碰撞检测,避免层次包围盒和空间划分的不利因素,物体的更新等操作限定在局部的三角形内.实验表明在多物体的碰撞检测中,即使存在若干移动物体,算法能够满足实时性和准确性的要求.     

无网格方法数值结果的可视化方法与实现

科学计算可视化是科学计算中不可缺少的一个组成部分,其主要任务是将数值模拟产生的大量复杂的数据信息通过计算机技术转换成图形、图像信息。无网格方法是一种基于点的数值计算方法,各离散点之间没有联结信息,其数值结果的可视化后处理是一件很困难的事情,尤其当离散点随机分布时,更是如此。Delaunay 三角化是十分理想的散乱数据的可视化工具,它可以根据一组随机分布的离散点数据生成唯一的近似等边三角形。首先介绍了 Voronoi 图与 Delaunay 三角化的基本原理,然后介绍了实现 Delaunay 三角剖分的算法及无网格方法数值结果可视化的实现方法,最后给出了无网格方法可视化的若干应用实例。     

三角网格曲面的球面参数化

提出了一种球面参数化三角网格曲面的方法。结合平面凸参数化和球面参数化,计算出封闭网格的切割线边界,网格边界映射到球面的凸区域边界上。然后分别参数化各子网格,最后将三角网格内部点映射到球面上。并用实例验证了此方法的可行性和有效性。     

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

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

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

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

Variational surface reconstruction based on Delaunay triangulation and graph cut

A novel method for surface reconstruction from an unorganized point set is presented. An energy functional based on a weighted minimal surface model is proposed for surface reconstruction, which is efficiently minimized by graph cut methods. By solving the minimization problem on the graph dual to a Delaunay‐based tetrahedral mesh, the advantages of explicit and implicit methods for surface reconstruction are well integrated. A triangular surface mesh homeomorphic to the original surface can be extracted directly from the tetrahedral mesh provided a sufficient sampling density exists. Difficult cases involving undersampling, non‐uniformity, noises and topological complexities can be handled effectively as well. Furthermore, for the first time, multi‐phase surface reconstruction is realized based on the graph cut methods. Various examples are included for demonstrating the efficiency and effectiveness of the proposed method. Copyright © 2010 John Wiley & Sons, Ltd.     

Adaptive tetrahedral mesh generation by constrained Delaunay refinement

This paper presents a tetrahedral mesh generation method for numerically solving partial differential equations using finite element or finite volume methods in three‐dimensional space. The main issues are the mesh quality and mesh size, which directly affect the accuracy of the numerical solution and the computational cost. Two basic problems need to be resolved, namely boundary conformity and field points distribution. The proposed method utilizes a special three‐dimensional triangulation, so‐called constrained Delaunay tetrahedralization to conform the domain boundary and create field points simultaneously. Good quality tetrahedra and graded mesh size can be theoretically guaranteed for a large class of mesh domains. In addition, an isotropic size field associated with the numerical solution can be supplied; the field points will then be distributed according to it. Good mesh size conformity can be achieved for smooth sizing informations. The proposed method has been implemented. Various examples are provided to illustrate its theoretical aspects as well as practical performance. Copyright © 2008 John Wiley & Sons, Ltd.     

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.     

The boundary recovery and sliver elimination algorithms of three‐dimensional constrained Delaunay triangulation

A boundary recovery and sliver elimination algorithm of the three‐dimensional constrained Delaunay triangulation is proposed for finite element mesh generation. The boundary recovery algorithm includes two main procedures: geometrical recovery procedure and topological recovery procedure. Combining the advantages of the edges/faces swappings algorithm and edges/faces splittings algorithm presented respectively by George and Weatherill, the geometrical recovery procedure can recover the missing boundaries and guarantee the geometry conformity by introducing fewer Steiner points. The topological recovery procedure includes two phases: ‘dressing wound’ and smoothing, which will overcome topology inconsistency between 3D domain boundary triangles and the volume mesh. In order to solve the problem of sliver elements in the three‐dimensional Delaunay triangulation, a method named sliver decomposition is proposed. By extending the algorithm proposed by Canvendish, the presented method deals with sliver elements by using local decomposition or mergence operation. In this way, sliver elements could be eliminated thoroughly and the mesh quality could be improved in great deal. Copyright © 2006 John Wiley & Sons, Ltd.     

3D boundary recovery by constrained Delaunay tetrahedralization

Three‐dimensional boundary recovery is a fundamental problem in mesh generation. In this paper, we propose a practical algorithm for solving this problem. Our algorithm is based on the construction of a constrained Delaunay tetrahedralization (CDT) for a set of constraints (segments and facets). The algorithm adds additional points (so‐called Steiner points) on segments only. The Steiner points are chosen in such a way that the resulting subsegments are Delaunay and their lengths are not unnecessarily short. It is theoretically guaranteed that the facets can be recovered without using Steiner points. The complexity of this algorithm is analyzed. The proposed algorithm has been implemented. Its performance is reported through various application examples. Copyright © 2010 John Wiley & Sons, Ltd.     

Tetrahedral mesh generation using Delaunay refinement with non‐standard quality measures

This paper studies the practical performance of Delaunay refinement tetrahedral mesh generation algorithms. By using non‐standard quality measures to drive refinement, we show that sliver tetrahedra can be eliminated from constrained Delaunay tetrahedralizations solely by refinement. Despite the fact that quality guarantees cannot be proven, the algorithm can consistently generate meshes with dihedral angles between 18^circ and 154^°. Using a fairer quality measure targeting every type of bad tetrahedron, dihedral angles between 14^° and 154^° can be obtained. The number of vertices inserted to achieve quality meshes is comparable to that needed when driving refinement with the standard circumradius‐to‐shortest‐edge ratio. We also study the use of mesh improvement techniques on Delaunay refined meshes and observe that the minimum dihedral angle can generally be pushed above 20^°, regardless of the quality measure used to drive refinement. The algorithm presented in this paper can accept geometric domains whose boundaries are piecewise smooth. Copyright © 2011 John Wiley & Sons, Ltd.     

点序对Delaunay三角剖分局部优化的影响

局部变换法和Watson算法是属于逐点添加、局部优化的离散点集Delaunay三角剖分的常用方法,不同的加点次序对这两种算法的局部优化影响较大。研究发现按位置相邻次序加点的方法易产生外接圆较大的扁平三角形,引起较多三角形的局部优化,而按随机次序加点,网格生成过程中网格单元相对匀称,局部优化的三角形较少。以激光点扫描采集的数据为例,统计分析了局部优化三角形的数量及分布特征,点数大于50000时,相邻次序加点方法局部优化三角形的总量是随机次序加点方法的1.6倍以上。建立离散数据的矩形空间索引,按索引轮流加点,点序对局部优化的影响降低,相邻次序加点方法局部优化的三角形总量是随机次序加点方法的1.1~1.3倍,其中随机次序加点与没有空间索引的随机次序相比,局部优化的三角形数量仅增加了约1%。     

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

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