一种空间曲面上散乱数据的快速三角剖分新算法

在现有三角剖分方法研究的基础上,提出了一种空间曲面上点云数据的快速三角剖分新算法。以区域生长法为主导,通过表面法向量向外原则提出了一种种子三角形选取与构造的新方法,改进生长算法,采用逆时针方式搜寻最优扩展点来生成三角形网格。该算法的总体时间复杂度为O（KN）,能够快速高质量的生成三角网格模型。     

存在约束条件的复杂曲面三角网格剖分方法

针对存在特征约束条件的复杂曲面三角剖分提出了一种新的算法，该算法首先将该类复杂曲面划分成平面参数域，产生较为均匀的参数域，进而对各子平面参数域进行平面参数域的三角剖分，然后将所得到的各子平面参数域映射为空间Beizier网格结点，形成粗网格三角剖分后进行各子曲面片间G^1连续的拼接运算，最后动用曲率标准和细分规则进行三角剖分质量的优化。该方法不但可以较好处理复杂曲面，而且能克服曲面网格产生裂缝。     

基于数学形态学与拓扑规则的三角网格修补算法

针对散乱点云数据在三角剖分过程中产生的拓扑缺陷,提出一种基于数学形态学运算和拓扑规则的网格拓扑修补算法。通过交互的方式选择需要修改的区域,使用自适应分层栅格的缺陷识别技术提取有拓扑缺陷的网格的顶点,从而确定待修复区域的边界,然后利用数学形态学的开启运算和闭合运算去除该修复区域的拓扑缺陷,并利用基于柄体理论的拓扑运算法则对该区域进行局部拓扑修改,生成二维流形的三角网格。应用实例表明,由于不需要对整个点云数据重新进行三角剖分,简化数据处理的过程,该算法具有运算速度快、结果准确性好的优点,并能较好地消除网格中的拓扑缺陷,有效地提高三角网格的显示精度,最终得到具有几何一致性和网格单元拓扑一致性的三角网格模型。     

散乱点云的三角网格曲面重建算法

在采用计算机视觉法获取物体三维重建数据的过程中,为了得到较完整的模型信息,所测得的曲面点通常带有大量冗余,而这些冗余数据的存在大大增加了曲面重建的难度.在此背景下,我们针对散乱无序、无任何几何拓扑信息的密集数据,提出了一种空间三角网格直接剖分算法.该算法能够节省存储空间,提高曲面重建效率,保证输出的曲面网格优质.算法首先对原始数据进行预处理,然后采用空间栅格法及Delaunay空球等准则,扩展动态三角网,最后统一法向量输出完整的三角网格模型.通过实例证明,算法重建速度快,曲面网格质量高.     

面向船体外板曲面重建的散乱点云精简算法

针对船体外板形变曲面实时检测与快速高效三维重建的要求。提出了以空间层次剖分和特征曲率相融合的精简算法,通过k-d树剖分准则将三维点云数据剖分成不同层次空间,层层递归形成树状数据模型,在每个节点空间内,同时分别利用K-邻域计算、曲率估算,获得点云特征曲率信息,设定可调的曲率阈值,依据阈值将同一数据源的点云数据区分为不同曲率大小的区域,运用不同的精简算法,实现保持曲面基本特征的曲面重建。实验结果分析,该算法保证曲面重建的基础上,大大减少了曲面的点云数量,提高了曲面重建效率。     

基于模糊聚类的Kohonen神经网络三角网格曲面重建

针对密集点云的三角网格曲面重建,提出一种用于数据精简和分块的神经网络算法:将模糊聚类方法与Kohonen神经网络算法结合.该算法具有按不同曲率进行曲面点云分块重建的能力,而且提高了自组织神经网络的效率.并应用该算法进行了仿真试验,建立了三角拓扑网格曲面,验证了算法的有效性.     

基于三角Bézier曲面的三角网格模型光顺算法

针对三角网格模型整体光顺效果较差的问题,提出一种基于三角Bézier曲面的三角网格模型光顺算法,该算法采用R*S树组织三角网格模型的动态索引,对三角网格模型进行精确保形精简,根据保形精简后三角网格模型型面几何特征构造整体G1连续三角Bézier曲面,将其作为三角网格模型的光顺参考曲面。通过将三角网格顶点映射于光顺参考曲面上,实现三角网格模型的光顺处理。实例证明该算法可对各种复杂型面的三角网格模型获得理想的整体光顺效果,并有效保留原模型的型面特征。     

摄影测量点云数据精简研究

针对摄影测量过程及所得点云数据的特征,利用模板法计算曲面曲率以确定曲面的精简比,对曲率图像进行非均匀网格滤波,实现了对摄影测量点云数据的精简。计算过程简洁方便,实验结果保持了原有数据的形态。该方法适用于摄影测量点云数据的后期处理。     

反求工程中过渡曲面特征提取算法研究

针对反求工程中常见的过渡曲面特征，提出了一种过渡曲面特征的提取算法。该算法包括数据分块和过渡曲面参数提取两部分，在数据分块算法中，通过数据精简，曲率估算和曲率比较等步骤，将过渡区域的数据点从原努点云数据中分离出来，在过渡曲面参数提取算法中，通过圆柱拟合和过渡区域跟踪算法，计算出一系列过渡曲面的截面线，该算法和已有的过渡曲面特征提取算法相比，无需人工交互，而且适用于等半径过渡曲面特征和变半径过渡曲面特征。     

任意三角形控制网格的二元四次箱样条曲面算法

二元三方向剖分是方向最少的三角剖分,建立在其上的二元三向箱样条在工程曲面造型等领域有着极为广 泛的应用。规范的二元三向四次箱样条曲面计算仅针对网格中点的价数均为6的情形,从规范的算法出发,提出 了一种任意价数控制点的情形下的曲面计算算法,并对算法进行了较为详细的分析。分析及试验结果表明,按该 算法生成的曲面有较好的整体光顺特性,各面片间是C1连续的,而对某一个三角面片内部则是C2连续的。由于 本算法适用于任意的三角形控制网格,因此在CAD／CAGD等曲面造型中有很高的实用价值。     

Triangular mesh generation employing a boundary expansion technique

This paper presents a triangulation method for modelling very large sets of cloud data. The three-dimensional (3D) data sets are produced by a machine vision system and/or coordinate measuring machine (CMM). The algorithm is suitable for processing the data collected from objects composed of free form surface patches especially with interior holes. This is accomplished from the 3D data sets in two steps. Firstly, the original cloud data is reduced into a simplified data set employing a data reduction technique (voxel binning method), in which the error between the cloud data and the meshed surface is used to control the data reduction. Secondly, the triangulation process starts with a randomly selected seed triangle. The triangular mesh extends outward by continuously linking suitable external points to it along the boundary edges of the meshed area. A complex free form surface with interior holes can be triangulated in one computing session without manually dividing it into several simple patches. The error-based data reduction parameters are extracted from the cloud data set, by a series of local surface patches, and the required spatial error between the final triangulation and the cloud data. Experimental results are given to illustrate the efficacy of the technique for rapidly constructing a geometric model from 3D digitised cloud data.     

基于局部细分曲面拟合的散乱数据孔洞修补算法

在逆向工程应用中,对于带有孔洞的散乱测量数据,给出了孔洞自动识别算法,通过提取孔洞邻域的局部数据进行三角网格划分和网格化简,得到带有孔洞的基网格.提出了基网格孔洞三角划分方法进行孔洞填补,在此基础上采用最小二乘方法进行Loop细分曲面拟合得到光滑的细分曲面片.以孔洞边界为基准,给出了细分曲面裁剪算法去除拟合曲面的多余部分,最后得到精确的孔洞填补数据.     

A progressive point cloud simplification algorithm with preserved sharp edge data

Due to recent advances in high-speed 3D laser-scanning technologies, the set of dense points collected from the external boundary surface of a physical object, often referred to as the point cloud data, is emerging as a new representation format of 3D shapes. A typical point cloud data set contains millions of coordinate data points, and this leads to significant computational challenges for the subsequent data processing tasks in practical applications. This paper presents a new point cloud simplification algorithm to reduce the number of data points scanned from a mechanical part, in which the boundary surfaces often contain sharp edges. Because of the distinct feature represented by data points located on or near the sharp edges (edge points), these points should always be retained by the simplification process. The proposed algorithm thus identifies these edge points first and then progressively removes the least important data point until the specified data reduction ratio is reached. The quantification of a point’s importance is based on points in its neighborhood and corresponds to the point’s contribution to the representation of local surface geometry. The effectiveness of the proposed algorithm is demonstrated through the simplification results of several practical point cloud data sets.     

ALGORITHM OF PRETREATMENT ON AUTOMOBILE BODY POINT CLOUD

As point cloud of one whole vehicle body has the traits of large geometric dimension,huge data and rigorous reverse precision,one pretreatment algorithm on automobile body point cloud is put forward.The basic idea of the registration algorithm based on the skeleton points is to construct the skeleton points of the whole vehicle model and the mark points of the separate point cloud,to search the mapped relationship between skeleton points and mark points using congruence triangle method and to match the whole vehicle point cloud using the improved iterative closed point(ICP)algorithm. The data reduction algorithm,based on average square root of distance,condenses data by three steps, computing datasets' average square root of distance in sampling cube grid,sorting order according to the value computed from the first step,choosing sampling percentage.The accuracy of the two algo- rithms above is proved by a registration and reduction example of whole vehicle point cloud of a certain light truck.     

特征保持点云数据精简

由于三维扫描设备采集的点云数据庞大,本文提出了一种特征保持的点云精简方法以在减少冗余数据的同时更好地保持原始曲面的几何特征。首先,利用K均值聚类法在空间域对点云全局聚类,对点云构建K-d树并以K-d树的部分节点作为初始化聚类中心。然后,用主成分分析法估计点云法矢和候选特征点,遍历每个聚类,若类中包含特征点则将该类细分为多个子类,细分时将聚类映射到高斯球。最后,基于自适应均值漂移法对高斯球上的数据进行分类,高斯球上的聚类结果对应为空间聚类细分结果,各聚类中心的集合为精简结果。以多个实物模型为例验证了算法的有效性。结果表明,本文方法精简的点云在平坦区域保留少数点,在高曲率区域保留更多的点。相比于非均匀网格、层次聚类、K均值点云精简法,该方法对包含尖锐特征的曲面精简误差最小,更好地保留了原始曲面的几何特征。     

特征提取的点云自适应精简

作为一种反映物体形貌的三维信息,点云数据的原始数据量十分庞大,直接对过多的数据进行操作会影响后续重建等工作。本文提出了一种新的点云特征提取自适应精简算法。首先对原始点云进行空间划分,构建点的k邻域,设置特征参数,进行特征分析,识别不同区域的信息和数据。然后针对平面数据预先进行边界的检测和提取,对剩余部分进行精简。最后,针对非平面区域,先提取特征,再根据曲率的不同进行不同程度的精简。办公室数据扫描实验结果表明,处理大小为百万以内点的点云模型可以在几秒之内完成,精简比能够达到90%以上,与原始数据间的误差较小:平面部分在精简前后平均偏差均在0.02mm以内,波动很小,为0.005 7mm;非平面区域精简前后的平均偏差均在0.08mm左右,差值仅为0.000 3mm,精简精度得以保证。因此,利用提出的算法处理后的数据能更好地展示物体的形貌。     

基于Matlab三维数据点三角剖分方法研究

逆向工程中点云数据点三角划分处理,在散乱数据插值曲面构造、快速原型制造以及有限元分析等方面有着重要的应用.根据Delaunay三角划分理论及Lawson优化准则,借助于Matlab中用于点云处理模块快速实现了空间散乱数据点的直接三角划分,给出了数据点三角划分程序代码,并以某小客车车身外表面点云数据处理过程加以验证,给出其外形数据点Delaunay三角划分以及凸壳包络图,由此可以早期发现逆向设计过程中可能存在的问题,从而减少后期修改次数,极大缩短新产品的开发周期,提高了设计精度.     

一种基于八邻域深度差的点云边缘提取算法

提出了一种基于八邻域深度差(8N-DD)的点云边缘提取算法。算法根据目标特征的点云,对每个特征点沿深度方向进行垂直投影并对投影点进行栅格划分,计算出每个栅格内投影点所对应深度的平均值作为该栅格的深度值;然后比较每个栅格与其八邻域栅格的深度差,根据深度差判断该栅格内是否存在边缘点,并采用排序法从栅格内筛选出目标的点云边缘点。针对含有非孔洞和孔洞的两种典型点云数据,利用八邻域深度差算法进行点云边缘提取,验证了算法的有效性。     

结构光检测点云精简与重构参数自动调节方法

针对薄壁叶片的点云扫描采样会产生特征消失、三角重构会产生孔洞现象的问题,提出一种改进的点云精简以及重构的方法。首先,根据法向量夹角阈值和欧氏距离提取叶片外轮廓;其次,计算点云的平均曲率和高斯曲率,设定阈值对点云划分子集,采用索引空间法对点云数据进行精简;然后,采用贪婪算法针对距离阈值系数和三角形参数对叶片点云进行实验分析,得出没有孔洞的贪婪三角参数经验值;最后对距离阈值系数和点云平均间距拟合出关系式,实现贪婪重构的参数自动调节。实验结果表明,在总体精简率为90%左右时,相较于另外两种方法,标准偏差分别下降了26.45%和19.92%,外轮廓尺寸平均偏差分别下降了79.81%和47.97%。按照提出的方法设置重构参数,重构质量良好,对薄壁叶片实现在机智能加工检测具有良好的应用参考。     

反求工程中复杂多面体模型的网格简化算法

提出一种新的基于顶点删除准则的多面体模型简化算法.该算法使用局部几何和拓扑特征移去满足简化标准的顶点,并对移去顶点后产生的空洞进行剖分区域划分,进而分别进行局部三角化.算法实现简单、速度快,能够有效处理高斯曲率近于零而平均曲率较大的网格,解决了以往一些算法对此根本不能进行简化的问题.实验表明,该算法可以简化具有复杂拓扑结构的网格模型,适用于在反求工程中获得的以重构精度为主要目标的多面体模型的简化.