逆向工程中圆锥曲面重建技术和裁剪算法的研究

逆向工程技术是随着计算机技术的发展以及数据测量技术的进步而迅速发展起来的一门新兴学科与技术，在计算机视觉、计算生物、几何造型和数字化制造等领域具有广泛的应用。曲面重建和裁剪技术是逆向工程中的重要组成部分，直接决定着重建模型的质量和重建效率，具有重要的研究意义。曲面重建研究已经取得了很大成绩，但是仍然存在着一些有待解决的难点问题，其中包括重建曲面的复杂性较高；数据点集的重建质量较差；自动化程度不高，需要大量的人机交互等。本文对这方面的问题展开了研究，提出了基于一个简单曲面的全自动曲面重建算法，即圆锥形曲面重建方法，同时为曲面重建质量的保证提供了理论证明。在模型重建过程中，需要大量的裁剪计算，使得裁剪效率直接影响到模型重建的速度。本文也对裁剪计算进行了研究，提出了一种高效的任意多边形的线裁剪计算方法，能自适应地降低计算复杂度，进而降低模型重建速度。 本论文的创新工作主要是在以下四个方面： 1. 提出了圆锥形快速重建点云模型的方法。对具有n个点的圆锥形点云模型，在误差阈值为ε的情况下，该方法的时间复杂度为O(n/ε3)，较以往的最快时间复杂度为O(nlogn/ε4+n/ε5)的算法有了明显的提高，并在理论上证明了重建后的圆锥的体积小于原始模型体积的(1+ε)倍。 2. 在圆锥形快速重建点云模型方法的基础上进行了改进，改进后的算法将求取全局最优解的过程修改为求取局部最优解，减少了大量的计算，将时间复杂度降至O(n/ε)。实验结果表明该算法能收敛到全局最优解。 3. 提出了采用多个圆锥进行模型重建的近似方法。该方法是一个全自动的方法，它可以有效地解决具有任意轴向的线性点云模型的圆锥重建问题（该问题是一个NP-难问题）。该方法将点云模型自适应地划分成一些子集，并对每个子集用一个圆锥来重建，使得圆锥包含对应子集内所有点。 4. 提出了基于凸片段的一般多边形线裁剪算法。该算法将多边形窗口的边顺序地分割成一些片段，使得每个片段都能局部地形成一个凸多边形，称为凸片段，并建立一个二叉树来管理这些凸片段。在裁剪计算时，先根据二叉树快速找到与被裁剪线段相交的凸片段，再利用高效的凸多边形线裁剪算法对这些凸片段进行裁剪操作。该方法能有效地降低裁剪计算的时间复杂度，使其在O(logN)~O(N)之间自适应地变化，且大部分情况下是小于O(N)的。