基于图形处理器的碰撞检测算法的研究

论文摘要

碰撞检测就是判断某一时刻两个移动的物体之间是否发生了碰撞。作为一个典型而实用的方法,需要考虑在任意离散的时间帧序列,两个物体是否相交。碰撞检测是计算机动画、游戏设计、机器人、计算机图形学等领域的一个重要的研究方向。如一个移动的物体在虚拟现实场景中的漫游,移动的路径通常是通过人机交互临时确定的,在这个过程中,实时的碰撞检测显得尤为重要。尽管目前针对碰撞检测的研究已经有了许多有价值的成果,但随着诸如虚拟现实等新兴领域的涌现以及随之而来的物体模型与场景越来越复杂,人们对交互实时性、场景真实性的要求越来越高,特别是在大型的复杂场景中,由于场景中的物体,甚至移动的物体数目都很多,这就需要反复的进行大量物体间的碰撞检测,从而给碰撞检测问题带来了前所未有的挑战。图形处理器(Graphics Processing Unit,GPU),作为一种高度并行的流处理器,凭借其强大的处理能力和高存储带宽,为实时的、复杂的碰撞检测提供一种有效的方案解决平台。围绕此方面进行的研究成为近几年来GPU的应用之一,并逐渐成为研究热点。本文充分的利用了图形处理器高度的并行处理能力,提出了下面两个算法:1.通过搜索两个凸多面体的分离平面来检测两个凸多面体是否碰撞。该算法使用一个启发式策略搜索两个物体的分离平面,经过有限的步骤,算法或者找到一个分离平面报告物体分离,或者证明两个凸多面体碰撞。在算法中,利用GPU加速了关键步骤——支撑顶点对的计算。并结合在GPU中分区域求最大值的约减(Reduce)方法,给出了适用于复杂场景中多个物体的实时碰撞检测方案。2.提出了一个基于GPU实现的、针对于复杂的封闭、变形物体的实时碰撞检测算法。算法有效的利用了图形处理器中的各种缓存,以及遮挡查询(Occlusion Query)操作,同时该算法还可以应用于自碰撞检测。尽管目前的算法还存在一定的局限性,但算法既不需要复杂的预处理过程,也不需要复杂的数据结构来存储数据,而且算法可以直接应用于可以绘制的各种模型,计算效率较高。我们用多个实例测试了算法的性能,并将上述的算法与其他碰撞检测算法进行了比较。

论文目录

• 摘要
• ABSTRACT
• 第1章 引言
• 1.1 研究背景及意义
• 1.2 研究现状
• 1.3 主要研究内容
• 1.4 本文的组织结构
• 第2章 预备知识
• 2.1 碰撞检测算法框架描述
• 2.2 分离平面
• 2.3 支撑顶点
• 2.4 支撑顶点对与单位支撑顶点向量
• 2.5 图形处理器——GPU
• 2.6 渲染引擎模式Shader Model
• 2.7 Cg语言
• 2.8 图形处理器中的缓存
• 2.8.1 深度缓存
• 2.8.2 模板缓存
• 2.9 遮挡查询（Occlusion Query）
• 2.10 流计算及核心函数Kernel
• 2.11 pingpong技术
• 2.12 基于图形处理器的通用计算（GPGPU）
• 第3章 基于GPU的适用于凸多面体的精确的碰撞检测算法
• 3.1 GHS-jump算法概述
• 3.2 基于GPU的支撑顶点对的计算
• 3.2.1 顶点的纹理表示
• 3.2.2 点乘运算
• 3.2.3 数据的压缩存储
• 3.2.4 求点积最大值
• 3.3 多个物体的碰撞检测
• 3.3.1 一个纹理中同时求得不同区域的最大值
• 3.3.2 多个物体的GHS-jump算法
• 3.4 实验
• 3.5 算法小结
• 第4章 基于图像空间的任意形状的碰撞检测算法
• 4.1 碰撞检测算法
• 4.1.1 碰撞区域的可见性
• 4.1.2 基本算法
• 4.1.3 算法分析
• 4.1.4 碰撞检测算法
• 4.2 算法优化
• 4.2.1 判断分离状态
• 4.2.2 绘制顺序
• 4.2.3 碰撞结果的获取
• 4.3 自碰撞检测算法
• 4.4 实验及结果
• 4.4.1 与其他算法的比较
• 4.4.2 算法的局限性
• 4.5 小结
• 第5章 结束语
• 5.1 工作总结
• 5.2 未来的工作
• 参考文献
• 致谢
• 攻读学位期间发表的主要学术论文和参与的主要项目
• 学位论文评阅及答辩情况表