点云数据三角化.doc

第1章、。在制造工业中最常使用的是坐标测量机(CoordinateMeasuringMachine,CMM)。坐标测量机能精确测量物体表面上点的位置,但其测量速度较慢,当测量点数较多时,效率很低,一般用在对精度要求较高的场合,如检查零件的形状精度、位置精度等。当需要大量获取零件表面的数据点时,一般使用激光扫描仪(LaserScanner)。激光扫描仪能在相对较短的时间内得到大量零件表面的数据点。puterizedTomography,CT)。CT得到的是物体的轮廓线,数据点呈层状分布,每一层代表物体的一个剖面。这些测量设备得到的数据点形式各不相同,虽然在局部上某些数据点具有有组织的状态,如激光扫描仪和CT所得的数据点呈现层状的特点,但在全局上基本均表现出散乱的特点。所谓散乱数据的三角剖分就是给定一组散乱数据点,将各数据点之间以三角形相互连接,形成一张三角网格。其实质是以三角网格反映数据点与其邻近点间的拓扑连接关系。而正确的拓扑连接关系将有效揭示散乱数据集所蕴涵的原始物体表面的形状和拓扑结构。,也是最重要最关键的一步,基于散乱数据点三角剖分构造散乱数据插值曲面的过程如图1所示:,它是构造散乱数据插值曲面的前置处理步骤。平面域内的散乱数据的三角剖分研究己经经历了相当长的时间,相关理论与算法己经相当成熟,特别是Delaunay三角剖分及其优化准则等研究成果使得平面内的散乱数据点的三角剖分已经不再困难。但在把平面内的算法推广到空间曲面上时,由于空间曲面散乱数据点之间拓扑关系的复杂性,对其直接剖分的理论和算法尚不完善。在处理空间曲面上数据点时,一般的算法都是基于平面凸域的或者是已知各种约束条件的情况,对于与多值曲面对应的空间曲面上散乱数据点的三角剖分算法研究的较少,且在算法效率和剖分效果上还远远不能让人满意。散乱数据曲面重构的难点在于如何在数据点集中快速自动得到邻近点间正确的拓扑连接关系。目前的测量设备能够在短时间内得到数万乃至几十万数据点,所能体现的曲面形状信息越来越精细和复杂,因此对曲面构造的效率和效果提出了较高的要求。研究散乱数据特别是大规模散乱数据的三角剖分,对于迅速构建数据点之间的拓扑连接关系,进而构造插值曲面具有十分重要的意义。散乱数据的三角剖分不但是构造散乱数据插值曲面的重要基础,对三维数据场的可视化、快速原型制造等新技术的研究也有巨大的推动作用。因此广泛应用于测量造型、计算机视觉、医学、气像、勘探、环保等领域中。本文所要研究三维散乱数据的直接剖分方法旨在探索解决与复杂曲面对应的散乱数据点的三角化方法,快速准确地生成优化的三角网格,为构造散乱数据插值曲面做好准备。因此本文关于空间曲面上散乱数据三角剖分方法的研究对散乱数据插值曲面的构造以及逆向工程曲面重构方法的研究有着重要的现实意义,对三维数据场的可视化、基于CT图像的体数据的三维模型重建等应用研究也有一定的借鉴与参考价值。,在计算几何散乱数据插值曲面构造和三维数据场可视化中得到了广泛应用。对空间曲面上散乱数据的三角剖分方法的研究不论是在二维平面区域还是在三维空间区域上都己经有了很多成果,尤其是对二维平面散乱数据三角剖分的研究,其理论和算法已经比较成熟,相对来说对空间曲面乱数据的三角剖分,特别是曲面形状比较复杂、散乱数据点的数目很大时,目前的算法在适应性、执行效率等方面还有待进一步提高。:给定一组散乱数据点{Vi}(i=1,2,?,n),如何将各数据点之间以三角形相互连接,形成一张三角网格,并使网格质量较优。该问题的解是散乱点集{Vi}的一个三角剖分T,其实质是以三角网格M反映各个数据点与其邻近点之间的拓扑连接关系,从而揭示数据点之间的内在本质联系。三角剖分所涉及的问题在实际应用中根据数据点位置的不同有三种情况:二维,三维实体和空间曲面。根据这种情况,空间曲面上散乱数据的三角剖分可分为对空间曲面上散乱数据投影域的剖分和在空间中直接剖分两种类型。空间曲面上散乱数据的投影域包括平面域和球面域。直接三角剖分方法研究如何直接将空间曲面上散乱数据点在空间中连接成一个优化的三角网格。:给定dE中k个不相同的点1P,2P,3P……kP点集P=1 1a p+2 2a p+3 3a p+…+k ka p(ka∈R,1a≥0,1a+2a+3