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.
collision detection parallel technology divide and conquer symmetry breaking Mized BVH
Wei Zhao Ruipu Tan
College of Computer Science & Technology Jilin University Changchun, Jilin, China School of Computer Science & Engineering Changchun University of Technology Changchun, Jilin, China
国际会议
北京
英文
1-5
2008-09-26（万方平台首次上网日期，不代表论文的发表时间）