Abstract: 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.

Key words: artificial intelligent, collision detection, human-computer interaction, cloud computing, parallel technology, Map - Reduce