A NEW PARALLEL COLLISION DETECTION ALGORITHM BASED ON MIXED BVH AND SYMMETRY BREAKING

摘要

Collision detection is a key technology of Virtual Reality, and the speed and precision are very important meaning for collision detection. In this paper, we present a new parallel collision detection algorithm based on symmetry breaking and divide-and- conquer technologies. At first, we incorporate the merits of both AABB bounding box and bounding spheres to construct a hybrid bounding representation of arbitrary non-convex polyhedra (S-AABB) for attaining speed, especially the S-AABB is balanced using divide-and-conquer technologies. Then we apply Symmetry Breaking — k-Coloring technology which is also important in parallel algorithm in order to reduce different categories, and assign them to different processors; Also multi-thread is used in multi-processor computer. At last, experiments results have shown that our algorithm is advantageous over other current typical collision detection algorithms such as I-COLLIDE [1], so can meets the real-time and accurate requirements in complex interactive virtual environment.