一种基于八叉树的OBB包围盒碰撞检测方法.pdf

第 26卷第 4 期 　　　 计算机应用与软件 Vo l26 No. 4 2009年 4 月 　　 Compu ter App lication s and Software Ap r. 2009 一种基于八叉树的 O BB包围盒碰撞检测方法 1 2 1 1 1 周俊玮 　万 　宇 　万旺根 　林继承 　陶　道 1 (上海大学通信与信息工程学院　上海 200072) 2 (香港科技大学 　香港 ) 摘 　要 　　碰撞检测技术是大规模复杂场景渲染的关键技术之一 ,它可以有效地提高虚拟环境的真实感和沉浸感 。碰撞检测的研 究目标是如何在很高的实时交互要求下完成大量复杂物体的相交检测 。提出一种将场景图中的 OBB 包围盒以八叉树的形式划分 , 并利用八叉树的层次结构实现有效碰撞检测的方法 ,该方法从宏观到微观的搜索方式可以快速确定需要进行相交检测的对象列表 , 有效地避免所有几何节点与运动节点的相交检测 ,提高了碰撞检测的效率 ,并且采用 OBB 包围盒来描述几何模型 ,有效地提高碰撞 检测的精度 。 关键词 　　八叉树 　碰撞检测 　有向包围盒 A M ETHOD O F COLL IS IO N D ETECT IO N W ITH O BB BA SED O N O C TREE 1 2 1 1 1 Zhou Junwei 　W an Yu 　W an W anggen 　L in J icheng 　Tao D ao 1 (S chool of Comm un ica tion and Inf orm a tion Eng ineering, S hangha i Un iversity, S hang ha i 2 000 72, Ch ina) 2 (H ong Kong Un iversity of S cience and Technology, H ongkong, Ch ina) A b stract　　Co llision detection is one of the key technologies, wh ich is u sed in rendering comp licated largescale scene. The truth and im m ersion of virtual environm en t can be imp roved greatly in th is way. The study p urpo se of co llision detection is how to fin ish interactive detec tion w ith a lot of comp lex objects in very h igh real tim e interactive need. In th is p ap er, we divided OBB s (O riented Bounding Box) in the scene grap h by O ctree, then imp lem en t collision detection effectively by the h ierach ical structure of O ctree. The list of objects wh ich need to be i