上海交通大学学报

上海交通大学学报（自然版） ›› 2012, Vol. 46 ›› Issue (06): 962-966.

• 自动化技术、计算机技术 • 上一篇    下一篇

快速高效的碰撞检测算法

印桂生1，王海玲1，2，张菁1，倪军2，王建3   

  1. (1.哈尔滨工程大学 计算机科学与技术学院，哈尔滨 150001；2.爱荷华大学 医学院，爱荷华 52242； 3.哈尔滨工程大学 网络信息中心，哈尔滨 150001)
  • 收稿日期:2011-08-20 出版日期:2012-06-28 发布日期:2012-06-28

Fast Efficient Collision Detection

YIN  Gui-Sheng-1, WANG  Hai-Ling-1, 2 , ZHANG  Jing-1, NI  Jun-2, WANG  Jian-3   

  1. (1. College of Computer Science and Technology, Harbin Engineering University, Harbin 150001, China; 2. Carver College of Medicine, University of Iowa, Iowa 52242, USA; 3. Centre of Network Information, Harbin Engineering University, Harbin 150001, China)
  • Received:2011-08-20 Online:2012-06-28 Published:2012-06-28

摘要： 为了提高碰撞检测算法的效率，提出了一种快速高效的碰撞检测方法.利用Morton码存储物体信息，给出一种改进的图层级结构，可快速分割物体空间，减少物体对相交检测；利用图形处理器(GPU)的并行处理特性进行物体包围盒层级树构建、树遍历，不仅可以快速处理碰撞检测中的事务，还可节省存储空间.实验表明，该方法能够快速构建物体层级结构，并能进行高效的碰撞检测计算.

关键词: 碰撞检测, 计算机图形, 层次结构, 图形处理器, 并行计算

Abstract: To speed up collision detection, a novel parallel algorithm for collision detection was proposed. Firstly, spatial Morton codes are used in linear ordering for geometric primitives, this is fast to build bounding volume hierarchies. Secondly, a top-down approach that uses the graph of model to build hierarchies optimized from skeletons connection. Thirdly, both algorithms are combined into a hybrid algorithm that need few memories for GPU construction performance and scalability leading to significantly decreased build time. The experimental results show the algorithm has efficient speedup to construct hierarchies of models with up to several million triangles and is fast for collision detection.

Key words: collision detection, computer graphics, hierarchy, graphics processing unit, parallel computing

中图分类号: