论文部分内容阅读
近年来,随着三维建模技术的逐渐成熟以及计算机软硬件技术的飞速发展,三维模型在医疗业、视频影视产业、建筑工程业等诸多领域有着广泛的应用,对三维模型的研究也更加深入细致。我们知道在几何学中,两点间的最短距离是连接这两点的直线段,而在三维模型中,物体表面两点间的最短路径称为测地线。三维模型的测地线在计算机、工业制造、航海业等诸多领域都有着巨大的应用前景,因此,受到研究者普遍关注的测地线研究成为三维模型研究的又一热点问题。三维模型的表示方法有许多种,如样条曲面表示法,三角网格表示方法,四边形表示方法等,由于三角形网格模型表示方法简单且灵活,获取方式多样,并且受到当前图形硬件的巨大支持,已逐渐成为目前表示几何模型的流行的方式。本文也是基于三角网格模型来进行研究的。关于三角网格模型上测地线的计算算法按精确度分类,可分为精确算法和近似算法,本文针对三角网格模型上的测地线精确算法及其应用进行了研究,主要工作有以下几个方面:(1)详细介绍了三角网格模型上精确测地线计算的经典算法MMP(Mitchell, Mount, Papadimitrious)。该算法是根据点光源直线传播的原理,通过窗口的传播得出测地线路经,整个算法的时间复杂度为o(n2log n)(n为顶点个数)。同时,通过实验将MMP算法和近似算法FMM(Fast Marching Method)在时间效率和计算精度上进行了对比,为进一步的模型匹配实验奠定了良好的基础。(2)研究了基于精确算法(MMP)的偏心变换问题。三维可视图形的识别、处理和表示可以被统称为抽象化,抽象化即提取图形的主要特点和性质,偏心变换就是根据距离变换的思想提出的一种抽象出模型描述符的方法,其中最短路径的计算采用的MMP算法。相对基于欧式距离计算的距离变换,偏心变换具有更好的稳定性和抗干扰能力。(3)通过测地线偏心变换的直方图实现模型的匹配。三维模型的匹配首先要对三维模型进行特征提取,本文提出了一种三维模型的描述符,即偏心直方图描述符,通过对三维模型的偏心直方图的比较,来实现三维模型的匹配。