分布式环境下基于方向包围盒的碰撞检测

Collision detection based on oriented bounding box in distributed environment

对于碰撞检测占用内存多、计算量大、数据负载高的问题,提出了基于MapReduce模型的方向包围盒(OBB)碰撞检测算法,采用OBB来描述被检对象的几何模型,把复杂模型的碰撞检测抽象成为简单元素的相交测试,并利用云计算关键技术MapReduce模型分布式遍历层次包围盒树进行相交测试,从而提高检测速度。实验表明,在构造的动态场景运行1500步时,该算法比其他算法在帧频和所需时间上最少有着322%和51%的效率提高。

To solve the problem of numerous occupation of memory, large amount of calculation and high load of data in collision detection, this paper presented an Oriented Bounding Box （OBB） collision detection algorithm based on MapReduce model. This algorithm could improve the speed of collision detection by using OBBs to describe the geometry model of measured object, so the collision detection of complex models could be abstracted into intersection test of simple elements, MapReduce model was used as key technology of cloud computing to traverse OBB-trees in distribution way to conduct the intersection test. The experiment shows that this algorithm has a minimum of 322% and 51% efficiency improvement than others in frame rate and time cost when the constructed dynamic scene runs 1 500 steps.