基于SIMD指令的柔性物体并行碰撞检测  

Parallel Collision Detection Between Deformable Objects Using SIMD Instructions

作　　者：唐敏[1] MANOCHA Dinesh 童若锋[1] 

机构地区：[1]浙江大学计算机学院,杭州310027 [2]北卡罗莱纳大学教堂山分校,教堂山北卡罗莱纳州美国27599

出　　处：《计算机学报》2009年第10期2042-2051,共10页Chinese Journal of Computers

基　　金：国家自然科学基金(60803054);教育部-英特尔信息技术专项科研基金项目(MOE-INTEL-09-05)资助

摘　　要：复杂场景中柔性物体间的碰撞检测依然难以满足交互设计的要求.为了提高处理速度,文中给出了一种充分利用现代CPU的并行处理能力的碰撞检测算法.算法基于两方面的并行处理:即基于SIMD指令的指令级并行处理和基于多线程的任务级并行处理.算法给出了一种针对SIMD指令特别优化的k-DOP模型——SIMD-DOP,从理论上分析了该包围盒的高效性,并与常规的16-DOP和24-DOP进行了运行效率对比.通过使用SIMD-DOP同时在多核间进行负载均衡,算法获得了优化的并行加速.文中算法已经在一台16核工作站上针对一组复杂测试场景进行了验证.Continuous collision detection among deformable objects in complex scenes is still hard to fulfill the demand for interactive design. To speedup processing, a collision detection algorithm which can fully exploit the parallel computing capability of modern CPU is proposed. The algo- rithm is based on a two-level parallel processing. SIMD instruction based instruction level parallel processing and multi-thread based task-level parallel processing. A SIMD instruction friendly k- DOP, SIMD-DOP, is designed. It has been analyzed, and compared with 16-DOP and 24-DOP in running efficiency. By using SIMD-DOP and balancing computing loads among multi-cores, opti- mized accelerations have achieved. The algorithm has been implemented on a workstation with 16 cores, and tested by using several complex benchmarks.

关 键 词：连续碰撞检测 柔性物体 SIMD指令 并行碰撞检测 包围盒层次结构 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]