基于Delaunay生长法的三维点云曲面建模研究

随着计算机科学技术,尤其是计算机图形图像学,三维扫描仪技术的发展,三维散乱点云曲面重建技术已成为当前研究的热点,点云曲面重建是指对采样得到的数据点进行三维重建,使重建后的模型能最佳的还原真实物体。三维曲面重建技术可以快速,精准,正确的重构出高质量的曲面模型,因此被广泛的运用于地质,逆向工程,机器人,CAD/CAM,医疗,文物保护等领域。对于重建对象是一系列离散点时,目前比较成熟的三维曲面重建算法有贪婪投影算法和泊松算法。贪婪投影算法的主要思想是将空间中的点投影至一平面内,然后对投影得到的点云作平面内的三角化,从而得到各个点的连接关系。该算法的思想简单,易于实现,但对于表面复杂的物体,存在投影多值的问题,导致重建后的曲面出现狭长三角形和交叉重叠的三角形,并且由于信息丢失会产生大量的空洞。泊松算法的基本思路是根据指示函数的梯度值等于有向点云的内法线,构建泊松方程来求解指示函数,最后通过提取等值面来完成重建工作。泊松算法重构的曲面是十分光滑的,但其无法刻画出高细节的曲面模型,并且该算法仅适用于封闭的,带法向量的点云模型。针对现有散乱点云三维曲面重建算法时间和空间复杂度高,适用范围小,曲面质量低等缺点,本文深入研究二维Delaunay生长算法,提出一种基于自适应外接圆的Delaunay生长算法,该算法能快速缩小备选扩展点的范围,与传统的生长算法相比,执行效率至少提高了一个数量级。将改进的二维Delaunay生长算法运用到三维空间,提出一种改进的基于三维Delaunay三角剖分的生长算法,该算法采用空间自适应外接球方法获得最优的备选扩展点集,通常情况下该方法会找到唯一的一点,若存在多个备选扩展点则通过约束准则和评价函数进行筛选,确保所形成的三角形近似于Delaunay三角形。利用改进的Delaunay生长算法可以弥补贪婪投影算法和泊松算法的不足,并具备以下三个优点:一是采用自适应外接球策略,可快速的找到最优的备选扩展点,极大的提高了搜索点的效率。二是通过约束准则不仅保证了曲面的平滑性而且限制了狭长三角形的生长,该算法的剖分效果很好。三是可对无法向量的点云进行三维曲面重建。因此该算法能处理大规模无法向量的点云数据,并能快速,精准的构建出高质量的曲面网格。