基于云模型与GPU缓存技术的快速碰撞检测算法研究

论文摘要

碰撞检测问题在计算机图形学、机器人运动路径规划、3D游戏、以及人工计算机辅助设计、虚拟器械制造、人工智能等领域中已有很长的研究历史。近年来随着虚拟现实、分布式、并行化等技术的兴起,碰撞检测问题开始成为热门的研究问题。目前,随着计算机技术的飞速发展,大规模虚拟场景的模型创建变得更加复杂,这增加了碰撞检测的计算复杂度,大大消耗了计算机本身的可利用资源,降低了计算机的运行速度,对其他任务的执行产生了不同程度的制约。面对碰撞检测巨大的计算量问题,国内外许多专家和学者纷纷投入到算法的研究当中,结合相关的计算机技术和自身掌握的知识,对满足实时性和精确性的算法进行了广泛的探索,并使之能够具有普遍性的应用性,为碰撞检测的发展开辟了新的研究方向。在交互式系统之中,实时交互是用户对系统的基本要求。因此,对碰撞检测的实时性和精确性要求极为严格,必须能够及时准确的响应用户的指令。在本文中,作者对相关的计算机技术进行了研究,并结合基本几何元素间的碰撞检测算法,提出了以下两种算法：(1)从降低计算机计算量的角度,提出了一种基于云计算模型的快速碰撞检测算法。其基本原理是充分利用网络的优势资源,集中网络终端的空闲计算机的计算性能,用来处理在进行碰撞检测中庞大的计算量。此算法对空间物体数量没有任何要求,对复杂场景下遇到的庞大的计算量有明显的优势,适合大规模复杂场景的碰撞检测。(2)从处理大规模复杂场景物体图像的角度,提出了一个对虚拟场景复杂程度不敏感的方法。其基本思想是利用GPU图形处理器的优势,通过缓存技术来分析处理场景中对象的图像,得到物体之间碰撞的结论。由于图像处理对场景复杂程度的不敏感性,所以此算法对大型复杂场景的碰撞检测非常有利。

论文目录

• 摘要
• Abstract
• 第一章 绪论
• 1.1 论文选题的背景
• 1.2 论文研究的目的和意义
• 1.3 碰撞检测问题的概述
• 1.4 国内外研究现状
• 1.5 论文的体系结构
• 第二章 碰撞检测的相关理论
• 2.1 碰撞检测
• 2.2 碰撞检测的具体类别
• 2.3 包围盒技术
• 第三章 基于MAP-REDUCE云计算模型的碰撞检测算法
• 3.1 本算法提出的概述
• 3.2 OBB层次包围盒
• 3.3 云计算
• 3.4 Map-Reduce编程模型
• 3.5 基本算法与实现
• 3.6 实验结果与性能分析
• 3.7 本章小结
• 第四章 基于GPU的快速碰撞检测算法
• 4.1 GPU图形硬件处理技术
• 4.2 Cg编程语言简介
• 4.3 OpenGL介绍
• 4.4 缓存及其应用
• 4.5 基于图形的碰撞检测
• 4.6 算法的设计及实验分析
• 4.7 结束语
• 第五章 结论与展望
• 5.1 全文工作总结
• 5.2 今后工作展望
• 致谢
• 参考文献
• 附录
• 作者简介
• 攻读硕士学位期间研究成果