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

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

三维重构中任意平面多边形轮廓的自适应Delaunay三角剖分

根据Delaunay三角剖分唯一、最优的特点,详细阐述了Delaunay三角剖分应用于特定的任意多边形轮廓的实现算法,介绍了相关的轮廓预处理技术,并对本算法提出了两点改进,给出了该三角剖分的应用实例。     

通用点线面集Delaunay三角剖分与动态编辑

总结并提出了一种通用点线面集Delaunay三角剖分与动态编辑的统一算法。可以实现离散点的Delaunay三角剖分,约束线、面的Delaunay三角剖分,任意多边形内带特征约束(包括点、线、面)的三角剖分,一般Delaunay三角剖分的外边界都是其离散点集的凸包,且内岛屿一般没有挖掉,本算法实现了Delaunay三角剖分时内、外边界的保界处理。     

基于EMST的平面点集Delaunay三角剖分

提出一种基于欧几里德最小支撑树(EMST)的平面点集Delaunay三角剖分算法.该算法使用线性时间的随机算法求出平面点集的EMST,逐次加入一边构成三角网络,按照最小角最大化的三角化准则,通过局部变换得到平面点集的Delaunay三角剖分.采用的随机化算法有效节省了寻找EMST的计算时间,提高了整个算法的效率.     

三维散乱点云快速曲面重建算法

提出了一种基于Delaunay三角剖分的三维散乱点云快速曲面重建算法。算法首先计算点云的Delaunay三角剖分, 从Delaunay四面体提取初始三角网格, 根据Voronoi体元的特征构造优先队列并生成种子三角网格, 然后通过区域生长的方式进行流形提取。实验结果表明, 该算法可以高效、稳定地重构具有复杂拓扑结构、非封闭曲面甚至是非均匀采样的点云数据。与传统的基于Delaunay的方法比较, 该算法仅需要进行一次Delaunay三角剖分, 无须极点的计算, 因此算法的重构速度快。     

基于重心Delaunay三角剖分的蓝噪声点采样算法

为了生成带有高质量蓝噪声性质的采样分布,提出一种基于重心Delaunay三角剖分的点采样算法.该算法将Delaunay三角剖分与1-邻域三角片重心相结合,迭代地将每个采样点移至其1-邻域三角片的重心处并更新采样点之间的拓扑连接关系;重心通过给定的密度函数计算得出.实验结果表明,本文算法在运行效率与鲁棒性方面均有一定优势.     

一种基于剖分与聚类的三维手势建模方法

针对有些建模方法需要设置复杂参数,或所建模型不够平滑、完整,以及出现多余网格等问题,提出了一种基于Delaunay三角剖分与K-Means聚类的三维手势静态建模方法。首先对点云进行半径滤波,再把点云投影在X0Y平面上,然后进行Delaunay三角剖分,对于剖分得到的三角网格中的长边与短边,使用K-Means算法聚为两类,最后删除含有长边的三角面片,得到完整手势的三维模型。实验结果表明,该方法有利于减少多余的网格面,形成的三维手势模型的网格面也较为平滑、完整。     

基于Delaunay三角网的任意多边形三角剖分算法研究

文章通过分析现有多边形三角剖分算法,给出一种基于Delaunay三角网的任意复杂多边形三角剖分的改进算法。算法首先忽略多边形顶点与边线间的逻辑关系,将其看做散乱顶点的集合,然后采用Delaunay三角化方法对点集进行合理剖分,再依据多边形顶点及边线间的逻辑关系,逐一将那些不合理的三角网剔除,最终重新组合出符合要求的三角网格。     

点云的形状与曲线重建算法

针对平面无序带噪点云的曲线重建问题,给出了点云形状的定义并提出了构造点云形状的算法.该算法基于Delaunay三角剖分,在构造好点云的Delaunay三角剖分后对三角剖分进行细化,使得在点云中的点周围形成空间上的局部均匀采样;基于集合论中的基本概念定义点云中内点、外点和边界点,并且明确地定义了点云的形状,根据Delaunay三角剖分细化时,选择不同的参数得到不同层次的点云的形状;选择合适的参数得到相应形状后,通过薄化过程得到具有流形结构的曲线.实验结果表明,采用文中算法得到的重建曲线很好地反映了点云的形状,验证了该算法的有效性.     

一个利用法矢的散乱点三角剖分算法

曲面上散乱点的三角剖分在曲面重建中发挥着重要作用,借助于曲面上的法矢信息和三维Delaunay三角剖分算法,该文给出了一种新的散乱点三角剖分算法,输入一组散乱点以及所在曲面S在这些散乱点处的一致定向的法矢信息,该算法将产生一张插值散乱点的三角网格曲面M,并且曲面M可以近似地看成是曲面S的三角剖分,算法的主要步骤分为两步：首先通过曲面S的一致定向的法矢信息,在曲面S的同一侧添加辅助点,利用这些辅助点来剔除Delaunay三角剖分中产生的不需要的三角片;然后将剩余的三角片连接成一张完整的网格曲面,与基于中轴的三角剖分算法相比,该文算法需要更少和更简单的计算,与局部三角剖分算法相比,该文算法可以更有效地避免重建后的曲面产生自交,该文的算法可用于任意拓扑的光滑曲面重建。     

四叉树高效Delaunay三角网生成算法

实现了一种以地形为应用背景的大规模离散点快速生成TIN的算法,该算法首先对大规模离散点按一定的阈值进行四叉树分割,然后对四叉树的每个叶子块分别以凸壳技术构三角网,而后再自底向上合并具有相同父亲节点的块,最后进行全局优化,生成Delaunay三角网.经实际地形数据验证结果表明：同样的算法,采用四叉树分块比采用平均分块策略有着更高的执行效率.     

矢量法在刀具半径补偿技术中的应用研究

刀具半径补偿技术是CNC系统的关键技术之一,是加工轨迹插补运算的数据来源与依据。根据编程轨迹及刀具半径值规划出刀具中心的运动轨迹,尤其是轨迹转接点坐标值,是保证零件轮廓正确性的必要前提。引入方向矢量的概念,研究矢量法在刀具半径补偿技术中的应用,实现了C功能刀具半径补偿,很好地解决了二维刀补中唯一解的确定这一复杂难题。该算法已经应用于自主研发的TDNC-L4数控铣削系统和数控车削系统,初步实现了该理论成果的实例化验证。     

离散点集3D三角划分算法在裁剪曲面中的实现

提出一种在3D空间直接对曲面离散数据点进行三角网格划分的算法,该方法适用于非封闭曲面、封闭曲面及多连通复杂曲面的离散点集,同时也能处理剪载曲面的离散点集,得到优良的三角网格。在引入边界环融合的概念的基础上,详细阐述算法如何实现对剪载裁曲面离散点集三角划分,并给出应用实例。     

基于RDWT与改进SIFT的DT网格运动估计与补偿*

为进一步提高运动估计和补偿的效果,提出了一种基于RDWT与改进SIFT的DT网格运动估计算法。首先在RDWT域内提取潜在运动区（PMA）,并设计了自适应的特征点提取模板;然后对SIFT算法进行了改进,它能快速进行特征点的精确提取与匹配,进而生成DT网格;最后利用仿射变换在PMA内进行运动估计与补偿。实验表明,该算法能快速有效地提取视频图像的特征点,在保持较高峰值信噪比(PSNR)的情况下提高运动估计的效率,且重建图像的主观质量很好,较现有基于不规则三角网格的运动估计算法在PSNR和效率上有一定优势。     

点与三角形位置关系对三角网格拓扑的影响

逐点添加、局部优化的Watson算法和局部变换法是生成大规模离散点集Delaunay三角网格的常用方法。点与三角形位置关系判别和三角形外接圆包含点的测试分别是局部变换法和Watson算法正确生成Delaunay三角网格的重要环节。计算误差会导致点与三角形位置关系以及三角形外接圆包含点的错误判别,从而生成几何拓扑关系不正确的三角网格。采用相对位置坐标可以提高面积坐标和外接圆圆心、半径的计算精度。以等高线地图采集的地形数据为例,用改进的算法生成了包含393252个离散点的Delaunay三角网格。     

面向并行的动态增量式Delaunay三角剖分算法

三角剖分是计算机图形学中的重要话题。并行三角剖分算法的发展对传统三角剖分算法提出了新需求,其中之一即是给定一个点数不断增大的点集,实现对该点集三角剖分的快速增量更新。虽然现今已有一些增量三角剖分算法,但都无法支持新增点落入原有三角剖分之外的情况。为解决此问题,提出了三角剖分的外扩技术,基于插入法设计了增量三角剖分算法TID。该算法能够支持任意次、任意数量、任意位置点的增量添加。TID算法能够对任意分布的点集均给出唯一三角剖分结果。对TID算法的性能评估表明,TID算法比现有算法具有更高的计算效率,且增量功能引入的额外开销较小。此外,该算法已成功作为局地三角剖分算法用于并行三角剖分算法中。     

基于仿射不变约束与快速EKF滤波的航拍图像稳像

考虑到航拍机载成像平台抖动严重、视频稳像匹配环节精度不一致的特点以及航拍图像稳像技术快速、准确的要求,提出了一种结合仿射不变约束与快速扩展卡尔曼(Extend Kalman Filter,EKF)滤波的图像稳像算法。该算法首先以视频参考帧中的角点量作为特征点,通过Harris检测器选择出稳定角点;然后对待配准点构建Delaunay三角网进行初始匹配,提出利用仿射不变约束方法筛选出精确匹配点;最后利用快速EKF运动滤波方法实时估计和修正噪声的统计特性,从而解决摄像机扫描运动中存在的抖动问题。在对大量分辨率为640×480pixel的航拍图像的仿真实验中,可通过仿射不变约束实现精确的模型估计,采用的快速运动补偿方法在补偿过程中耗时为5.054ms,比传统的运动补偿方法节约了69.5%的时间。实验结果表明,该算法能够实时稳定航拍视频帧间的抖动现象,并能有效跟随场景的真实扫描。     

一种多张裁减曲面的快速三角化算法

针对多张裁减曲面的三角化问题,提出一种多张裁减曲面三角化边界的算法。该算法在进行多张裁减曲面的三角化时,采用点对应的方法离散曲面的公共边界,因而能有效地防止曲面相交处出现裂缝、孔洞和覆盖等现象,提高了多张裁减曲面三角化算法的正确性。同时采用了目前比较先进的基于局部优先的平面任意区域三角剖分算法,因而提高了三角化的效率。     

An on-line algorithm for constrained Delaunay triangulation

A constrained Delaunay triangulation is a Delaunay triangulation of a set of points and straight-line segments. A constrained Delaunay triangulation is a basic tool for describing a topographic surface in several applications. In this paper, the definition of constrained Delaunay triangulation is introduced and its basic properties are discussed. Existing algorithms for constrained Delaunay triangulation are briefly analyzed. A new on-line algorithm for constrained Delaunay triangulation that is based on the stepwise refinement of an existing triangulation by the incremental insertion of points and constraint segments is proposed.