散乱点云的三角划分算法研究

通过对当前的三角网格划分方法进行比较分析,提出了一种散乱点云的3D三角网格划分算法。该算法不需如同二维划分方法那样要对散乱点云对应的自由曲面分片投影,而是直接在3D空间,根据离散点集所对应的曲面形态变化,利用网格扩展、边界环分裂和边界环封闭,逐层收缩生成三角网格。该算法能方便地处理空间多种曲面的散乱点云数据,并且生成的三角网格形态优良,布局合理。     

散乱点云的三角网格重构

基于增量扩散法的思想,提出并实现了一个散乱点云的三角网格重构算法,算法首先利用体素网格的散列表对散乱点进行组织,然后在确定了初始种子三角形的基础上,基于活动边扩展规则构造新的三角形,使网格不断向周围扩展直到活动边表空为止,最后算法合并棱边并计算每个三角形的顶点法矢,最终构造出散乱点云的三角网格。     

多连通曲面离散点集的3D三角划分算法研究

在对非封闭曲面、简单封闭曲面和多连通封闭曲面的特点进行分析之后,提出了一种多连通封闭曲面离散点集的3D三角划分算法.该算法无须对离散点集所对应的自由曲面进行分片,直接在3D空间根据曲面的形态变化向前逐层推进生成三角网格.算法同时还适用于非封闭曲面和简单封闭曲面两种情形.实验结果表明,该算法的划分效果优良,能够满足曲面重构的需要.     

一种平面点集凸包与三角网格综合生成的算法

平面点集作为一种觉数学模型,其上常做的运算是求其凸包和三角网格,目前二者的研究是独立进行的,鉴于在很多情形下这两种处理结果均需要,提出了一种综合算法：在对离散点集进行ｄｅｌａｕｎａｙ剖分的过程中,增加对三角形边界的判别、管理功能,记录其中作为点集凸包边界的线段,使得在实现剖分的同时产生出点集的凸包,从而提高了算法效率,且当该算法实现单一的点集剖分或凸包功能或是用于简单多边形的凸包与剖分时效果也很好     

任意平面域上离散点集的三角化方法

本文提出了一种快速、有效的三角化算法,实现了任意平面域上散乱数据的三角化,生成的网络符合Delaunay准则,网格的优化是在网格生成过程中完成的,算法复杂度与点数呈近似线性关系.该算法运用于石油地质勘探领域,成功地解决了包含复杂断层的大规模数据点的三角化问题.     

实现3D离散点优化三角划分的三维算法

本文系统研究了３Ｄ离散数据的直接三角划分，并解决了与多值曲面相对应离散数据的分片三角划分问题。实现这一算法的关键是将这些与多值曲面相对应的离散数据按有关的特征线分解，慢之转化成较简单的问题分别进行处理。目前，这种分片三角划分算法已在Ｂｅｚｉｅｒ三角曲面插值中取得了良好的效果。     

三维散乱点集的曲面三角剖分

根据三维散乱点集构造曲面剖分在 CAGD/CAD、反求工程等方面有着十分广泛的应用 .本文回顾了三维散乱点集曲面三角剖分的两种主要方法即平面投影法和直接剖分法 ,对几种常用的算法作了较为详细的描述 ,同时对剖分算法中经常出现的数据结构作了详细的介绍 .由于剖分采用的优化准则决定了剖分结果 ,因此本文讨论了几种常用的剖分优化准则 ,并举例对几种优化准则进行了较详细的分析比较 .最后简要地讨论了算法复杂度以及目前剖分的主要研究方向 ,并指出在实际工程应用中对复杂曲面采样得到的散乱点集 ,要得到光顺和保形的三角剖分 ,需要新的剖分准则和算法 .     

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

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

基于平行截面的三维散乱点物体表面重构

三维物体的散乱点构型技术是近几年计算机视觉领域中的热点问题,它在众多行业有着广泛的应用前景。该文提出了一种新的能够适用于大多数物体的构型方法,并且计算量也相应地得到了控制。     

二维点集三角剖分的动态生成与修改

本文在已有算法的基础上提出了一个二维点集三角剖分的动态生成与修改算法。当点逐个增加或删除时,只需进行局部剖分即可保证整体三角剖分符合Delaunay性质,对点的插入位置及删除顺序未加任何限制。本文还给出了关于这一算法正确性的证明及算法复杂性分析。 本算法可应用于二维点集一阶Voronoi图的动态生成与修改,其基本思想可以扩展到三维空间。     

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

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

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

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

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

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

一种基于散乱数据插值的网格图象变形方法

提出一种基于特征点运动分解和散乱灰度数据插值的网格图象变形算法,以改进传统的两步扫描网格变形法在扫描顺序和变形效果上的不足。将原始图象的象素坐标一次性映射至目标图象,再对映射后得到的散乱坐标点的灰度进行散乱数据插值以恢复目标图象的象素信息。为了提高灰度映射的效率,引入一种基于Delaunay三角剖分的三角线性插值的方法来处理大规模散乱数据的插值。最后通过实例证明该算法的变形效果较两步扫描网格变形法有显著提高。     

一种基于映射法的散乱点云Delaunay三角剖分算法

针对直接在三维空间构建海量点云的Delaunay三角网格效率低下,提出一种新的基于映射法的Delau-nay三角网格构建算法.首先提出一种基于区域增长法的点云分片方法,能够保证对分片后的点云数据进行映射而不产生重叠;然后保持空间点云之间的距离特性,将三维点云映射到二维平面;在二维平面内进行Delaunay三角剖分,再将结果返回到三维空间内.实验结果表明,算法能够构建质量较好的三角网格.由于该算法将点云的三角剖分转换到低维空间,通过实验结果对比本算法与其他算法效果,证明该方法能够更快地完成重构.     

基于二维凸多边形内散乱点的三角划分新算法

基于给定的平面散点数据,提出了逐层提取轮廓线,并将轮廓线之间的区域进行三角划分的新算法。实现这一算法的关键是在给定阈值的条件下逐层提取内部离散点的轮廓线,再在所提取的轮廓线间进行等比例三角划分。最后,利用Lawson提出的局部优化过程来优化分割好的三角形网。通过实验证明了算法的有效性。     

结合间接邻域的散乱点云三角网格曲面重构

对于非均匀散乱点云,多数基于区域生长方法的曲面重构往往容易出现孔洞等缺陷。针对该问题,在K邻域点集的基础上提出间接邻域点集的概念,对以点为生长对象进行区域生长的三角网格曲面重构方法进行了研究,实现三角网格曲面重构。以生长点的邻域点集为样点估算微切平面,将邻域点投影至该平面上,并按照右手定则、逆时针方向进行排序,通过拓扑正确性原则从点列中去除错误的连接点,优化局部网格,选择较好的连接点,实现网格曲面的区域生长。     

基于离散数据的自由曲面三角网格实现算法

针对自由曲面三角网格实现过程中三角网格的数目和形态等质量问题,提出一种采用最小权法直接实现三角划分的算法。分析和总结了三角形网格的优化方法,制定了具体的三维优化过程,不仅分析指出了现在主流三维划分的优点和局限性,而且结合环域网格的特点,制定了用增加点法完成的三维优化方法。提高了三角划分的速度,改善了三角单元质量,并提高了对三角单元进行修正的速度,实验结果证明了算法的有效性。     

基于散乱点的任意拓扑曲面建模及绘制研究

对曲面建模进行了研究,提出了一种基于散乱点的曲面重建方法.给出三维空间的散乱点,采用3个步骤重构出三角化曲面:首先按近似共面程度对点集聚类,把接近共面的点归为同一类,然后根据空间点的邻接关系进行局部调整,最后对点集和点集之间的区域进行三角割分,得到三角化曲面,所得曲面用OpenGL进行绘制.     

散乱数据拟合的自适应分片逆尺度空间算法

散乱数据拟合(逼近)是在信号处理、计算机图形学等领域中被广泛研究的问题, 近些年,利用优化方法获得散乱数据的稀疏表示逼近解也成为了优化和曲面重构交叉领域的热 点。基于由B 样条生成的PSI 空间中的散乱点曲面拟合问题和分片稀疏的联系,将分片稀疏性 引入到Bregman 逆尺度空间算法(ISS)中,提出一种自适应的分片逆尺度空间(aP_ISS)算法,处 理散乱数据的曲面拟合问题。通过对逆尺度空间系统分片符号一致性分析,得到了自适应分片 逆尺度空间系统的性能保证定理和避免了aP_ISS 参数的选取。应用到散乱点曲面重构问题上 的数值实验结果表明,该算法不仅可以有效拟合曲面,还能够较好保护分片稀疏性。