大规模离散点集Delaunay三角剖分加点策略的分析

局部变换法和Watson算法是离散点集Delaunay三角剖分的常用算法,算法过程中逐点添加、局部优化是三角网格生成速度的重要影响因素.按位置相邻次序逐点添加时易产生外接圆较大的扁平三角形,引起较大范围的局部优化,三角网格的生成速度下降.在位置相邻次序的点集中随机选择部分点生成相对匀称的初始三角网格,再依次添加数据点,可有效减少局部优化消耗的时间,提高三角网格的生成速度.以激光扫描测量数据为例,切分为不同数量的点集进行三角剖分测试,当数据点数大于20000点时,采用部分随机点优化策略,其三角剖分速度比直接按位置相邻次序添加的方法提高一倍以上,且数据量越大,效率越高.     

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

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

一种三维离散点数据生成非结构四面体算法

3D离散点数据的Delaunay三角剖分是构造曲面网格的关键技术之一。针对常用的基于三角网递推原理的Delaunay四面体局部构造生成算法中往往存在的四面体不相容问题,本文提出在当前点的局部计算中构造新四面体时,除了参考当前局部计算之前已生成的四面体集约束关系外,同时考虑当前点局部计算过程中生成的四面体集约束关系的非结构四面体生成算法,从而改善了新生成四面体与已有四面体的不相容性。文中最后给出的实验结果验证了本文算法的有效性。     

带特征线约束的Delaunay三角剖分最优算法的研究及实现

为了提高特征线约束的Delaunay三角剖分的速度和功率,从两个方面进行改进;一是生成无约束的Delaunay三角网时,采用进行剖分算法;二是在约束线上插入点时,应用取三角形外接圆与特征线交点的方法。并行剖分算法具有较好的加速性能;“交点”插入算法考虑了特征线的影响域及Delaunay三角形规则的边界条件,在满足全局Delaunay三角剖分的前提下,使插入的点最少,对原有的网格影响最小。     

球面凸类图形Delaunay三角剖分再分算法及其收敛性分析

在计算曲面Ricci Flow时,会因为三角网格中存在过小的角而出现不收敛的情况。针对这种不收敛的问题,提出一种提高最小角角度的球面凸类图形Delaunay三角剖分再分算法。首先,给出球面凸类图形Delaunay三角剖分再分算法。它的核心操作有两个：1）如果某条Delaunay劣弧被"侵占",通过添加Delaunay劣弧中点分割Delaunay劣弧;2）如果存在"瘦"球面三角形,通过添加球面三角形外接球面小圆圆心分解球面三角形。然后,利用局部特征尺度探索出所提算法的收敛条件并给出输出顶点的一个上界公式。根据实验输出的网格验证,所提算法网格生成的球面三角形没有狭小的角,适合用来计算Ricci Flow。     

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

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

一种基于三维Delaunay三角化的曲面重建算法

提出一种基于三维Delaunay三角化的区域增长式曲面重建方法。该方法以空间点云的Delaunay三角化为基础,结合局部区域增长的曲面构造,较以往方法具有人为参与更少、适用范围更广的优点。算法采用增量式插入点的方式构建空间Delaunay划分,采用广度优先算法,以外接圆最小为准则从Delaunay三角化得到的四面体中抽取出合适的三角片构成曲面。该算法的设计无须计算原始点集的法矢,且孔洞系数对重建的结果影响很小,重建出的三角网格面更符合原始曲面的几何特征。无论待建曲面是否是封闭曲面,本算法均可获得较好的重建效果。     

用随机增量局部转换算法实现三维点集的Delaunay三角剖分

Delaunay三角剖分作为计算几何中的一个核心问题,尤其适用于三维网格生成.因此就需要开发出高效、健壮性的算法来实现.本文在原有算法的基础上提出了随机增量局部转换的算法来实现三维点集的Delaunay三角剖分.采用不退化的四点生成最初的三角剖分,每次加入一点,通过局部交换使新的三角剖分保持Delaunay性质,直到处理完所有点.还讨论了局部交换的思想和对不同面类型的处理方法,给出了两个剖分实例.     

复杂地质体中多值面的网格生成算法

针对现有的网格生成算法无法处理在自然界中大量存在的多值面地质现象，基于分割－归并方法，提出一种分裂－重构算法。在生成初始约束Delaunay三角形网格之后，遵循连续折线的正负区测试准则，对网格中的局部顶点进行分裂，重构相关的三角形的点、边以及三角形的拓扑关系。实验表明，该算法能够有效地生成多值面的网格。     

约束三角剖分在雨量等值线的应用

雨量等值线在水文、防汛领域应用广泛,Delaunay三角剖分具有空外接圆和最大的最小角度两个良好性质,对于非规则分布的离散点数据进行三角剖分内插是生成等值线的最常用的算法,但实际应用中往往都术是凸壳进行三角化,而是有限定边（或限定点）对三角剖分进行约束。该文在标准Delaunay三角剖分基础上,分析了逐点插入法的基本原理,基于此提出了一种解决有限定边的约束三角网格剖分生成等值线的方法,给出了限定边进行三角剖分的算法,同时对边界采用网格加密和邻域内插算子进行边界附件插值,提高等值线的边界拟合精度,并在雨量等值线生成中得到较好应用。     

Delaunay三角网高效构建及地形仿真应用

针对基于离散点的Delaunay三角网构建过程中待插入点的定位耗时问题,提出Delaunay三角网高效构建算法,并将其用于三维地形仿真应用中。对大量数据点进行分块排序预处理后,运用空间自相关理论使下一个待插入点总是紧邻新近插入点,融合最短路径定位算法和三角形面积法,结合三角形重心与点、有向线段的关系遍历三角形,减少遍历时间。在对三角网进行LOP局部优化时,采用Delaunay四叉树保存待调整的所有边的节点信息,提高遍历效率。实验结果证明,该算法构建的三维地表真实感较强,并且具有较低的时间复杂度。     

Delaunay三角网通用合并算子及分治算法的简化

Delaunay三角网在未来地学数值模拟中将发挥重要作用。分治算法是一种著名的经典构网算法,但其子网合并过程十分复杂,限制了其应用。提出使用通用算子的概念,并用从以往算法中独立出来的算子和3个新算子来简化分治算法的子网合并。扩展三角形算子用于构造每个新三角形并维护三角网的拓扑关系和边界链表。凹边界填充算子对边界链表用递归来自动完成凹边界的智能三角形填充。子网合并算子先用一个新三角形连接两个子三角网,再合并边界链表,调用凹边界填充算子填充子网间的缝隙区域。所有算子都基于有向边的数据结构和用链表管理的三角网外边界,借助链表操作,使算法的构建简洁而又高效。除分治法外,这些算子还被成功用于构建其他算法。由随机点集以及LiDAR点云的测试表明,所有算法的构网均准确无误且分治算法的执行效率较高。     

以优先点为中心的Delaunay三角网生长算法

目的 Delaunay三角网具备的优良性质使其得到广泛的应用,构建Delaunay三角网是计算几何的基础问题之一,为了高效、准确地构建大规模点集的Delaunay三角网,提出一种基于优先点的改进三角网生长算法.方法 算法以逆时针次序的一条凸包边为初始基边,使用基边对角最大化并按照逆时针次序选定第3点构建一个Delaunay三角形,通过待扩展边列表中的数据判断新生成的两条边是否需要扩展,采用先进先出的方式从待扩展边列表中取边作为基边,以优先点为中心构建局部Delaunay三角网使优先点尽快成为封闭点,再从点集中删除此封闭点.结果 对于同一测试点集,改进算法运行时间与经典算法运行时间的比率不超过1/3,且此比率随点集规模增长逐步下降.相比经典算法,改进算法在时间效率上有较大提升.结论 本文改进算法对点集规模具有较好的自适应性与较高的构网效率,可用于大规模场景下Delaunay三角网的构建.     

三维物体表面重建的分支处理算法研究

根据平面点集Delaunay三角剖分的特性,将Delaunay三角剖分应用到分支问题上,改进和实现了一种分支问题处理算法。将相邻层轮廓线投影到同一个剖面上形成一个带约束边的平面点集,并将它们Delaunay三角化,根据这些三角形组来生成新的轮廓线,使轮廓线一一对应。实验结果表明该算法实现的效果较符合实际情况,能有效地处理各种不同情况。     

An adaptive sampling strategy for Kriging metamodel based on Delaunay triangulation and TOPSIS

Metamodels have been widely used in engineering design and optimization. Sampling method plays an important role in the constructing of metamodels. This paper proposes an adaptive sampling strategy for Kriging metamodel based on Delaunay triangulation and TOPSIS (KMDT). In the proposed KMDT, Delaunay triangulation is employed to partition the design space according to current sample points. The area of each partitioned triangle is used to indicate the degree of dispersion of sample points, and the prediction error of Kriging metamodel at each triangle’s centroid is used to represent the local error of each triangle region. By calculating the weight of the area and prediction error for each triangle region using the entropy method and TOPSIS, the degree of dispersion of sample points and local errors of metamodel are taken into consideration to make a trade-off between global exploration and local exploitation during the sequential sampling process. As a demonstration, the proposed approach is compared to other three sampling methods using several numerical cases and the modeling of the aerodynamic coefficient for a three-dimensional aircraft. The result reveals that the proposed approach provides more accurate metamodel at the same simulation cost, which is very important in metamodel-based engineering design problems.     

狄洛尼三角剖分在LOD点删除简化中的应用探讨

LOD(Level of Details)层次细节模型的提出为三维复杂场景的实现提供了有力的技术支持.LOD简化通过顶点删除、边压缩、面片收缩操作来减少场景中的面片数,降低场景复杂度从而加快绘制速度.利用点删除操作进行模型简化时,需要对删除顶点后所形成的多边形"空洞"进行三角化再剖分,不同的剖分方法所形成的三角形网格质量是不同的.引入有限元网格剖分的概念,使用狄洛尼(Delaunay)三角剖分法则,提出对凸闭包自身三角化构建方法,对一个凸多边形进行了最优的剖分.所形成的三角形网格满足狄洛尼法则中的最大-最小角特性和空外接圆特性两个重要原则.     

一种基于边指针搜索及区域划分的三角剖分算法

针对大规模数据处理时Delaunay三角剖分过于耗时的问题, 本文提出了一种基于边指针搜索及区域划分的三角剖分算法.基于边指针设计了一种能够反映三角形之间位置关系的数据结构, 并优化了目标三角形的搜索路径.基于该数据结构, 利用区域划分进一步降低目标三角形的搜索深度.超级三角形所在的正方形被划分成具有相同尺寸的区域, 目标三角形的搜索从插入点所在的区域的入口三角形开始, 这大大缩小了目标三角形的搜索范围.实验证明, 与传统的Delaunay三角剖分算法相比, 该算法的效率显著提升.     

基于快速Delaunay三角化的散乱点曲面重建算法

针对现有三维重建算法速度较慢的问题,提出了一种基于快速Delaunay三角化的散乱数据点的三维重建算法。首先,提出一种新的平面Delaunay三角化插入点目标三角形定位算法,利用插入点的方向搜索线与三角形是否相交以及交点个数加速目标三角形定位,不用额外判断点是否在三角形内;其次,自动检测曲面漏洞,利用凸壳的边界拼接方法进行漏洞弥补。实验结果表明,本算法不仅能较好地重建出三维模型,而且有较高的效率。     

多尺度形态滤波及弹性匹配技术在类星体谱线识别中的应用

本文提出了一种类星体谱线证认方法。首先针对特征为极值点的信号，研究了多尺度膨胀（腐蚀）关于极值点数的两种重要特性及其应用。其一是单调率特性，根据它自动选择滤波器尺度，有效地滤除脉冲噪声；另一种是单调性，它是＂从粗到精＂策略来重新恢复极值特征位置的理论基础。根据这些性质，对光谱进行多尺度膨胀（腐蚀）和特征恢复，以滤除脉冲噪声而不影响谱线特征。然后研究弹性匹配技术应用于谱线证认，并指出了匹配方法中参量的物理意义。该方法对其他一些应用领域也行之有效