论文部分内容阅读
寻径技术一直是人工智能中比较重要的研究内容,广泛应用于游戏、虚拟现实、导航、机器人等领域。随着计算机图形学技术的发展,场景的立体化、复杂化,三维场景的寻径得到了越来越多的关注。A~*算法是寻径算法里的最为经典的算法。A~*算法是一种启发式搜索算法,其核心是到目标点的路径代价估计函数。该函数包含两项,一项表示起始节点到当前节点实际距离,另一项启发式函数表示当前节点到目标节点的距离估计。启发式函数越准确,A~*寻径的效率越高。在三维场景中,路径生成效率往往受限于复杂的三维表面,例如孔洞、表面扭曲等。在这种复杂的场景下,传统的启发式函数很难准确地估计节点间的距离。本文提出一种基于谱分析的启发式函数,以得到尽量准确的路径代价估计值用于A~*寻径。该方法通过寻找合适的谱分解方法将复杂三维场景的距离信息尽可能等距地嵌入到一个合适的谱空间,在后续寻径中,通过计算该谱空间上点对的欧式距离可以较好求得启发式函数的值。以往基于预计算的改进方法往往受限于点对距离的空间存储,时间效率等,本文的算法很好的解决了空间存储问题,在时间上也有很好的提升。本文分析比较了几种谱分解的方法,基于这些方法选取合适的嵌入谱空间,并分析其应用于三维场景寻径启发式函数的可行性。基于局部特性保持的谱方法主要是通过保持局部的几何关系进行谱分解映射到谱空间,而其全局的几何特性相对保持较差。而全局特性保持的谱方法,特别是距离保持的谱方法,比较契合本文的应用需求。本文经过分析比对采用了保距的多维尺度分析(MDS)谱分解方法来嵌入到合适的谱空间,求解启发式函数。我们还进行了场景测试实验,根据场景对应谱空间上的点对欧式距离进行启发式三维场景寻径,进而验证算法的可行性及性能。实验表明,本文的方法在三维场景寻径方面具有较好的表现。