USSCD:一个基于均匀空间分割的快速碰撞检测算法

被引：8

作者：

李焱

卢晓军

贺汉根

机构：

[1] 国防科技大学机电工程与自动化学院自动化所,国防科技大学机电工程与自动化学院自动化所,国防科技大学机电工程与自动化学院自动化所长沙,长沙,长沙

来源：

中国图象图形学报 | 2003年 / 12期

关键词：

人工智能(520·20); 虚拟环境; 碰撞检测; 空间分割;

D O I：

暂无

中图分类号：

TP391.9 [计算机仿真];

学科分类号：

080203 ;

摘要：

对于存在大量运动物体的虚拟环境 ,碰撞检测往往成为影响系统计算效率的瓶颈 ,为提高多体碰撞检测的效率 ,提出了一个基于均匀空间分割的快速多体碰撞检测算法—— USSCD.该算法首先将物体空间均匀分割成一系列单元格 ,然后在每个单元格 ,通过基于 AVL排序的扫描排除法进行碰撞检测 .同时依据物体的分布密度 ,提出了一个计算单元格尺寸的优化方法 .通过一系列实验 ,测试了 USSCD算法的性能 ,并与 I- COL L IDE算法进行比较 .实验结果表明 ,在均匀分布条件下 ,当物体数量较大时 ,USSCD的效率高于 I- COL L IDE算法 ,而且 ,U SSCD算法的效率基本不受物体运动相关性的影响 .

引用

页码：84 / 89

页数：6

共 4 条

[1]

Interactive collision detection for molecular graphics. Turk G. . 1989

[2]

Fast collision detection among multiple moving spheres. Kim D J,Guibas L J,Shin S J. IEEE Transactions on Visualization and Computer Graphics . 1998

[3]

I COLLIDE: An interactive and exact collision detection system for large-scale environments. Cohen Jonathan D,Lin M C,Manocha Dinesh,et al. In: Proceedings of the Symposium on Interactive 3D Graphics[C], ACM, New York,NY, USA . 1995

[4]

Efficient collision detection for animation and robotics. Lin M C. . 1993

← 1 →