基于GPU并行加速碰撞检测算法的研究

摘要

碰撞检测在计算机图形学中主要是指虚拟场景中两个或多个物体在同一时刻是否占据同一个位置。碰撞检测自从计算机出现以后，就一直受到人们的关注和研究，随着计算机技术的发展，人们对虚拟场景的的真实性要求也越来越高，而碰撞检测对虚拟场景是否具有真实感和沉浸感非常关键。随着时间的发展，研究人员针对提高碰撞检测的效率研究出了很多算法，这些算法对于当时的特定场景产生了很好的效果，具有一定的实时性。然而，随着虚拟场景复杂程度的增加以及物体的精细程度提高，其实时性大受影响。近年来，随着图形处理器飞速发展，GPU的架构和功能发生了革命性的变化，使得GPU可以应用于通用计算，因而，对如何解决碰撞检测实时性问题提供了新的思路和方法。
　　本文通过对典型的碰撞检测算法进行深入分析，利用GPU强大的并行处理能力，提出了一种基于GPU并行加速的碰撞检测算法，从以下几个方面对算法进行了设计和改进：
　　①通过深入分析传统的基于AABB层次包围树的碰撞检测算法，发掘算法中可以并行化的部分，在构建层次包围盒树时，采用自底向上的方式并行处理，加快生成和更新层次树的速度。
　　②在对层次树进行遍历时，也进行了并行优化处理，得到一种基于GPU通用计算的实时碰撞检测算法。在对两个物体进行碰撞检测时，直接利用三角形与另一个物体的层次包围盒树进行遍历，判断其相交情况，由于算法使用CUDA线程的方式来进行处理，因此只需执行一个遍历的过程，其时间复杂度为O(N)，相比于CPU的时间复杂度O(N2)，有很大改进。当碰撞检测结束后，GPU将碰撞结果数据返回给CPU，进行下一步处理。这种利用“CPU+GPU异构运算”思想，利用各自的优势，将不同的任务分配到不同端来执行，使得算法性能更佳。
　　实验结果表明，基于GPU并行加速碰撞检测算法取得了很好的效果，即使对更加复杂的模型和场景，仍然满足碰撞检测实时性的要求。

目录

封面

中文摘要

英文摘要

目录

1 绪 论

1.1 研究背景与意义

1.2 碰撞检测算法概述

1.3 国内外相关研究进展

1.4 本文主要工作和组织结构

2 碰撞检测算法的一般框架

2.1 引言

2.2 初步检测阶段

2.3 详细检测阶段

2.4 小结

3 主要碰撞检测算法

3.1 空间剖分法

3.2 层次包围盒

3.3 基于图像空间的碰撞检测算法

3.4 小结

4 基于GPU碰撞检测介绍

4.1 GPU通用计算

4.2 基于GPU流计算的碰撞检测算法

4.3 CUDA平台介绍

4.4 小结

5 基于CUDA架构AABB包围盒树并行化碰撞检测算法

5.1 引言

5.2 算法概述

5.3 并行生成包围盒树

5.4 并行遍历包围树

5.5 实验结果及分析

5.6 小结

6 总结与展望

6.1 本文工作总结

6.2 下一步工作展望

致谢

参考文献

附录 A．作者在攻读硕士学位期间发表的论文目录