基于八叉树精确划分型值点的碰撞检测算法  

The algorithm of collision detection based on octrees of data points

作　　者：崔云飞[1] 苏凡囤[1] 王海涛[1] 郑桂凯 赵洋 刁孝发 

机构地区：[1]解放军理工大学野战工程学院 [2]95944部队装备股 [3]济南军区工程科研设计所

出　　处：《微型机与应用》2013年第20期80-82,90,共4页Microcomputer & Its Applications

摘　　要：针对虚拟现实中碰撞检测的快速计算问题,提出一种新的粗略碰撞检测与精确碰撞检测相结合的检测算法。首先利用AABB包围盒法排除不可能相交的物体,然后对可能发生碰撞的包围盒采用八叉树算法进行空间分割,在包围盒内找到由型值点形成的三角形面片,利用三角形面片的碰撞检测算法精确地判断物体是否碰撞。通过与OBB包围盒算法的碰撞检测数据对比,验证了该方法的有效性。A hierarchical collision detection algorithm from coarse detection to fine detection was established in the paper. Fimtly, bounding volumes which are not intersected clearly will be removed rapidly by AABB intersection test. Secondly, divide bounding volumes whieh are intersected by octree division method and find out data points. Generate lines between data points and then constitute the triangle faces. Lastly, the algorithm detects intersection between two triangles from two objects. After testing and comparison with OBB collision detection algorithm, the efficiency of the algorithm is greatly improved.

关 键 词：碰撞检测 AABB包围盒 八叉树 型值点 三角形面片 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]