基于包围盒和空间分割的碰撞检测算法研究

论文摘要

准确且快速的碰撞检测对提高虚拟现实环境的沉浸感和真实感具有非常重要的意义。由于虚拟环境中存在大量的物体对象和物体几何形状的复杂性,使得碰撞检测过程常常占去大量的存储空间和处理时间,碰撞检测算法的效率决定生成虚拟场景的实时性和真实性。碰撞检测是虚拟现实技术研究的难点问题。层次包围盒法和空间分割法是碰撞检测算法中的基本方法,这两种方法的目的都是为了尽可能的减少需要相交测试的对象或基本几何元素对的数目。为提高碰撞检测的效率,本文在对这两种算法进行了深入研究的基础上,主要从以下两个方面进行了研究:本文依据AABB包围盒构造方便和相交测试简单的特点以及AABB树的构造过程特点,提出一种减少AABB层次包围盒树内部结点存储所需字节数的方法,从而加速了碰撞检测算法的执行速度。本文提出一种均匀空间分割的方法来检测变形体对象之间的碰撞及自碰撞。该方法采用哈希表作为数据存储结构,以四面体网格为基本几何元素,优化了哈希函数、哈希表、单元格等参数。实验证明该方法的有效性。虽然算法的研究是以四面体网格为研究对象,但这一算法同样适合其它变形体对象。

论文目录

• 摘要
• Abstract
• 第一章 绪论
• 1.1 论文研究背景及意义
• 1.2 问题描述
• 1.3 国内外动态研究
• 1.4 本文工作及章节组织
• 第二章 相关碰撞检测算法综述
• 2.1 层次包围盒方法
• 2.1.1 基本原理
• 2.2.2 层次包围盒的类型
• 2.3 基于包围盒树的碰撞检测算法
• 2.4 基本几何元素之间的相交测试
• 2.5 空间分割方法
• 2.6 小结
• 第三章 基于层次包围盒树的碰撞检测算法
• 3.1 碰撞检测过程
• 3.1.1 近似测试阶段
• 3.1.2 精确测试阶段
• 3.2 层次包围盒树的构造
• 3.3 层次包围盒树的更新
• 3.3.1 对象运动后包围盒的更新
• 3.3.2 对象变形后包围盒树的更新
• 3.4 基于AABB树的存储优化
• 3.5 小结
• 第四章 基于均匀空间分割的碰撞检测算法
• 4.1 基于空间分割的碰撞检测算法
• 4.2 参数分析
• 4.2.1 哈希函数
• 4.2.2 哈希表大小
• 4.2.3 空间网格大小
• 4.3 算法复杂度
• 4.4 实验
• 4.5 小结
• 第五章 总结和展望
• 5.1 对所做的工作的总结
• 5.2 下一步的工作
• 参考文献
• 攻读学位期间发表的论文
• 致谢