反求工程中点云三角化算法的研究及其实现

反求工程技术是结合当前先进的激光扫描技术和几何造型技术的一种新的实体建模技术。当前的激光扫描技术能够获取各种拓扑结构的机械零件的点云数据，其测量精度能够满足反求工程技术重建实体模型的需要。几何造型技术一直是CAD／CAM的核心技术和研究基础，主要研究在计算机中表示、设计、显示和分析复杂三维形体的理论和方法。这两种技术的发展使得反求工程成为当前的研究热点，是企业实现产品设计现代化、缩短设计周期、提高产品质量、增强市场应变能力和生存能力的又一种强有力的技术手段。 在反求工程技术中，对实体的描述存在多种模型。点云模型运用三维空间的离散点集来表示物体，最大的优点在于可以表示任意物体，易于进行布尔操作。三角网格模型形状简单，便于计算，而且可以表示任意拓扑结构的物体，能以任意精度逼近曲面物体，已经成为各种造型系统的标准表示方法之一。参数曲面模型一直是描述几何形状的主要工具，广泛应用于飞机、汽车、轮船等具有复杂外形的产品设计与制造中。由于参数化表示具有与坐标轴无关，可直接进行几何变换以及几何不变性等优点，它已经成为CAGD中曲面的主要表示形式。三种模型之间可以通过各种重建方法相互转换。 反求工程中实现点云的三维模型重建有多种反求策略，其中最常见的反求策略是首先通过三维激光扫描仪在物体表面测得一些离散点，然后用数据预处理技术对点云进行压缩、去噪等处理，再用散乱点重构算法生成三角网格模型，最后基于网格模型进行网格优化、压缩、区域分割后，重建点云的参数曲面模型。 本文研究了反求流程中的点云三角化算法及其实现。通过对现有成果的研究，改进和实现了一种基于曲面局平特性，在投影平面内重建某个采样点的Delaunay三角化，然后在边界点上进行区域增长的点云三角化算法。该算法基于半边数据结构和四种被证明可完整重建任意拓扑点云的拓扑操作，保证了区域增长时三角网格一直是流形曲面。该算法对每个点只执行一次操作，时间复杂度是线性的。只要点云数据在局部满足局平特性，该算法可以可靠稳定地重建任意拓扑结构的三角网格。各种类型和各种来源的实例也证明该算法的实用性。 该算法已经在反求工程软件RE-SOFT中得以实现，并应用于各种拓扑结构的机械零件的三角网格曲面重建。重建的结果再次证明了该算法在时间复杂度和重建质量上的优势。 本文还研究了基于三角网格的拓扑操作，并指出各种拓扑操作的合法性，实现了其中换边、删边和删点三种基本的拓扑操作，证明了基于半边数据结构的网格结构有利于网格的后续操作，包括网格优化、压缩、区域分割等操作。本文还实现了一种减少网格与原曲面二阶属性误差的网格优化算法。该算法在重建尖锐边处凹凸性有一定作用。