散乱数据点集的三角划分算法研究

在对当前的三角网格划分方法进行比较分析后,提出了一种散乱数据点集的3D三角网格划分算法,该算法不需如同二维划分方法一样要对散乱点集对应的自由曲面分片投影,并可自然处理含有凹边界及孔域的曲面数据点集,利用网格扩展、边界环分裂和边界环封闭,根据曲面的变化逐层推进生成三角网格,使算法能方便地处理非封闭曲面、空间剪裁曲面、封闭曲面、空间多连通曲面等各种曲面的散乱数据。     

散乱点云的三角网格重构

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

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

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

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

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

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

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

散乱点云的快速增量网格重建算法

散乱数据的网格重建是数字几何处理的基础性技术之一.本文提出一种快速增量式散乱点云网格重建算法,运用波前( Wave Front)方法渐进地由点云数据生成物体表面的网格模型.该算法以一个”种子”三角形初始化搜索队列,以逐渐生成的新边为搜索元素,借助Kd-树空间划分技术和搜索约束条件,快速完成优化点的评估及三角面片重建,可在保证网格质量的同时,过滤部分对重建效果意义不大的点.实验表明,该算法能够高效、可靠地生成具有不同几何复杂度的原始曲面二维流形三角网格逼近,适用于海量数据点的网格重建.     

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

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

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

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

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

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

点云重构三角网格的生长型神经气算法

为克服点云噪声、不均匀分布和复杂拓扑结构对三角网格重构的限制,改进了生长型神经气重构算法.以样本在网格局部投影作为神经元插入判据,自适应调节网格增长速度,保持几何变换与拓扑变换的协调.利用非流形边检测机制删除冗余连接,保持网格的拓扑有效性.网络学习过程中动态更新三角片结构,且在孔洞修复阶段扩大近邻查找范围,连接近邻节点中的边界点,直到网格收敛,最终得到正确的欧拉示性数.算例表明,改进的算法对带噪声点云具有鲁棒性,可根据非均匀点云的分布自动调整网格密度,且能重构具有复杂拓扑结构的曲面.重构的三角网格对曲面逼近精度较高,网格出度均匀,三角形近似等边.     

一种散乱点云空间直接剖分算法

散乱点云的三角剖分在曲面重建中发挥着重要作用。在对三角剖分基本方法深入分析的基础上对此类点云提出了一种高效的重构算法。本算法将基于动态球策略的搜索算法引入到曲面重建中,源于增量式计算的思想,结合约束准则和设计的顶点度量函数,从基础三角面片开始扩展到覆盖整个物体表面。分析及实验结果表明,该算法能有效地对点云数据进行三角网格化,同时剖分后的三角网格曲面最大限度地保持了原有曲面的特性,证明了提出的基于动态球的曲面重构算法应用于散乱点云曲面重构问题的可行性。     

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

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

一种快速三维散乱点云的三角剖分算法

改进了一种三维散乱点云三角剖分算法。三角剖分是点云数据曲面重构的主要算法之一,但针对三维散乱点云的三角剖分存在剖分效率不高,剖分得到的三角曲面形状无法控制,细节特征表现不足的问题。提出了基于空间栅格划分的三角剖分算法,并提出了一个新的评价函数,以控制三角网格曲面的生长。实验证明,改进后的算法极大的提高了剖分效率,而且能保证最终生成的三角网格曲面平滑而保有丰富的细节特征,适用于在虚拟现实、曲面重构等领域推广使用。     

基于VTK的散乱点集三角网重建算法研究

散乱点数据在机械产品测量造型、地理信息系统等众多领域来说都较易得到。为使VTK可视化平台中的数据处理及面显示应用面更广,本文设计了基于平坦度的自适应增量的网格构造算法,将散乱点数据格式转换成VTK数据格式,从而利用VTK流水线机制进行面绘制。该算法实现了空间直接三角剖分,而且动态调整逼近误差。实验证明,该算法能
高效、可靠地生成贴近原始曲面的三角网格,并取得较理想的VTK绘制效果。该算法对于三角剖分问题和VTK可视化平台的数据处理具有一定的理论和实际意义。     

一种用于信度网推理的高效三角化算法

信度网是不确定性知识表达和推理的有力工具。信度网的精确推理是NPC问题,计算的主要困难在于将信度网三角化并构造一棵最小权的join tree上。此项研究提出了一种新的三角化算法MsLB-Triang,该算法同时利用了无向图三角化的Direc性质与LB-单纯性质,在生成的三角化图的总权以及增加边的数目上均明显优于目前广泛采用的Min.Weight Heuristic算法。     

基于CAD模型的3D散乱数据点三角剖分方法

提出了一种针对空间大规模散乱数据点三角剖分的方法。该方法基于可用的CAD模型,采用“分而治之”的思想。对齐测量数据点与CAD模型、记录数据点及在CAD裁剪NURBS曲面实体上投影点。分别对每块实体的参数区域(u,v)相应点2D-Delaunay三角化、根据R2区域的连通结构反构造出3D三角网。进行冗余三角形删除和网格片缝合等优化处理。与其他方法不同的是,它不受测量数据的分布方式和物体曲面形状的拓扑结构限制。实际的算例结果表明,该方法高效且可靠实用。     

散乱点集Delaunay三角剖分的分布并行算法

为了加快大数据集Ｄｅｌａｕｎａｙ三角剖分的速度,提出了一种能对任意散乱点集进行Ｄｅｌａｕｎａｙ三角剖分的分布并行算法,算法具有容错性和自动负载平衡的能力,文中对其设计和实现方法进行了详细讨论,对算法的复杂性进行了分析,实验结果表明该算法的加速效果明显。     

Triangulation of Points,Lines and Conics

The problem of reconstructing 3D scene features from multiple views with known camera motion and given image correspondences is considered. This is a classical and one of the most basic geometric problems in computer vision and photogrammetry. Yet, previous methods fail to guarantee optimal reconstructions—they are either plagued by local minima or rely on a non-optimal cost-function. A common framework for the triangulation problem of points, lines and conics is presented. We define what is meant by an optimal triangulation based on statistical principles and then derive an algorithm for computing the globally optimal solution. The method for achieving the global minimum is based on convex and concave relaxations for both fractionals and monomials. The performance of the method is evaluated on real image data.