基于云计算Map-Reduce模型的快速碰撞检测算法

Fast collision detection algorithm based on Cloud Map-Reduce model

针对人机交互系统中碰撞检测实时性、精确性的要求,本文提出了一种基于云计算模型的快速碰撞检测算法。1提出一种新的分裂平面构建OBB平衡包围盒树方法;2引入了标记遍历树概念,对进行碰撞检测的OBB任务树采用堆栈进行深度或广度遍历标记,减少相交检测次数;3采用Map-Reduce云模型对任务树进行划分,划分后子任务采用云模型并行执行,减少了检测时间;4对每个子任务结果进行标识,将标识后的子任务作逻辑运算,通过运算结果判断是否发生了碰撞。对比实验结果表明:与经典的I-COLLIDE、MPI及Pipelining等算法相比,该算法在效率、精确性方面具有明显优势,能够满足复杂虚拟空间人机交互的实时性和精确性的要求。

To meet the real-time and accuracy requirements of collision detection in Human-computer Interface（HCI）system,a fast collision detection algorithm is developed based on cloud computing model.First,a new construction method of balanced OBB bounding box tree by split plane is proposed.Second,the concept of marked traversing tree is introduced,and it is marked in depth or breadth traversal using stack on OBB to reduce the number of intersections in collision detection.Third,the task tree is divided using Map-reduce Model（MRM）,and it is executed in parallel for the sub-tasks after division by the cloud model,thus to reduce the detection time.Finally,each sub-task result is identified and logical operation on the identified sub-task is carried out;the operation result is used to determine whether collision has taken place or not.Comparative experimental results show that,compared with the classic I-COLLIDE,MPI and Pipelining algorithms,the proposed algorithm has obvious advantages in terms of efficiency and accuracy that can meet the requirements of real-time and accuracy of HCI in complex virtual space.