虚拟环境中碰撞检测算法的研究和实现

作     者：刘超 

作者单位：南京航空航天大学 

学位级别：硕士

导师姓名：蒋夏军

授予年度：2018年

学科分类：08[工学] 080202[工学-机械电子工程] 080203[工学-机械设计及理论] 0804[工学-仪器科学与技术] 0802[工学-机械工程] 

主      题：碰撞检测 方向包围盒 轴向包围盒 层次包围盒树 空间三角形相交检测 

摘      要：虚拟环境中的碰撞检测是计算机图形学、机器人路径规划、虚拟装配以及计算机动画等诸多领域的核心问题之一,其基本任务是检测虚拟环境中的模型之间是否相交。高效的碰撞检测算法对增加虚拟场景的沉浸感和真实性起着至关重要的作用,虚拟环境中涉及的三维模型越来越复杂,导致模型之间的碰撞检测也更为复杂。如何提高碰撞检测算法的效率是当前研究的重点内容。基于现有的碰撞检测系统框架,主要对碰撞检测过程中的粗略检测算法和精确检测算法进行了研究,在深入理解层次包围盒技术以及空间三角形相交检测技术的基础上,分别为层次包围盒碰撞检测算法,以及层次包围盒结构中三角形相交测试算法提出了新的改进方案,并实现了一个新的实时碰撞检测系统。对于层次包围盒结构,提出了一种基于轴向包围盒和方向包围盒的双重层次包围盒结构,与传统的层次包围盒算法相比,该算法主要有以下改进:(1)计算最小方向包围盒时,在主成分分析法的基础上增加了面积加权的思想;(2)证明了双重包围盒结构中不同类型包围盒之间的相交检测是强烈相关的,基于此,算法中方向包围盒的相交测试只需检测5条潜在的分离轴;(3)在层次包围盒的遍历过程中,使用了一种基于启发式的深度优先遍历算法。对于精确相交测试,提出了一种适用于方向包围盒结构的三角形相交检测算法。该算法用矩形的表达式替换三角形的顶点坐标,结合粗略检测阶段得到的坐标变换矩阵,避免了大量三角形的顶点坐标变换操作,同时,替换后的三角形顶点包含许多零值,这些零值可以进一步减少检测过程中的计算量。实验结果表明以上改进算法比传统算法具有更好的性能。