基于混合包围盒与三角形相交的碰撞检测优化算法
2018-10-16孙敬荣卢新明
计算机工程与应用 2018年19期
关键词:检测
孙敬荣,卢新明
1.山东科技大学,山东 青岛 266590
2.山东科技大学 山东省智慧矿山信息技术省级重点实验室,山东 青岛 266590
1 引言
碰撞检测(Collision Detection,CD)是虚拟网络游戏、物理仿真[1]、虚拟仿真技术[2]、机器人技术[3]、数控加工等的关键技术。现阶段在碰撞检测领域的研究方法主要有:基于物体空间的碰撞检测算法和图像空间的碰撞检测算法[4]。层次包围盒是一类经典的碰撞检测算法,同时三角形相交检测也是一类在碰撞检测中应用广泛的算法。随着虚拟现实应用内容的复杂化以及应用领域的日益扩大,应用环境的实时性以及复杂性对碰撞干涉检测的要求越来越高,单一的基于层次包围盒或传统三角形相交已经很难满足人们对碰撞检测准确性与速度的需求。并且,近几年国内外对三角形相交测试的研究十分的活跃,但基本都过度重视了算法的速度,而忽视了稳定性。该研究旨在通过结合并优化包围盒算法与三角形相交算法以保证碰撞检测的速度与准确性。
2 算法原理
基于对碰撞检测的研究,将碰撞干涉检测分为预处理检测和详细检测两阶段,在预处理阶段,将待测空间均匀划分,然后算法基于混合层次包围盒树,对处在同一网格区域内的相邻对象构造混合层次包围盒树。当两个待测物体的AABB-OBB混合层次包围盒树建成后,通过遍历两棵混合包围盒树,进行包围盒之间的相交测试:当两个包围盒未相交时,该节点停止检测;当包围盒相交时,对该节点的子节点进行检测;……
登录APP查看全文
