基于混合包围盒的碰撞检测算法的优化研究

摘要

在当今3D模型成为虚拟现实、游戏引擎、计算机仿真等领域的主流趋势下，三维物体间的碰撞检测问题已经成为了不可避免的问题之一。随着人们日益增加的对于虚拟场景逼真度和沉浸感的需求，碰撞检测问题必将再次成为研究热点。
　　 本文以三维环境中相对复杂的不变形刚体之间的碰撞检测问题为研究背景，以基于包围盒的一类碰撞检测算法为研究对象，以对传统层次包围盒算法进行改进为研究目标。通过学习基于包围盒的碰撞检测算法的基本理论，融合国内外对于层次包围盒以及混合层次包围盒的最新研究，提出了一种改进的基于混合层次包围盒AOs的碰撞检测算法。
　　 本文在基于包围盒的碰撞检测算法的三个关键技术点做了如下工作:
　　 (1)层次树的构建方面:本文提出了一种新型的混合层次树结构AOs，上下层分别采用AABB和OBB包围盒，根节点额外附加一层Sphere包围盒，并且从理论角度进行了详细的合理性论证。
　　 (2)层次树的遍历方面:本文算法引用了性能比较优越的“同时下降”原则，并融合了“时空相关性”的思想，解决了相交测试时，节点“如何向下遍历”以及“从哪开始遍历”这两个问题。
　　 (3)层次树的更新方面:本文算法在更新策略上做了一定程度的改进，把前人“部分更新”的思想应用到自身AOs混合层次树结构上，并且结合自身层次树的特点，给出了适合自身的更新方法。
　　 随后，利用视景仿真引擎VegaPrime搭建了仿真实验平台，以发生碰撞时的运算时间、检测精度以及总体性能几个方面为考察目标，设计了两个实验场景。通过对实验结果的对比分析，验证了本文算法相对于传统算法的性能优势，以及本文算法在处理相对复杂的不变形刚体之间的碰撞检测问题时的可行性与有效性。

目录

声明

摘要

1 绪论

1．1 研究背景与意义

1．2 国内外研究概况

1．3 研究目标及内容

1．4 论文结构

2 基于包围盒的碰撞检测算法

2．1 碰撞检测的基本理论

2．1．1 碰撞检测的基本原理

2．1．2 碰撞检测算法的分类

2．2 常用包围盒技术

2．2．1 包围盒的基本思想

2．2．2 AABB包围盒

2．2．3 OBB包围盒

2．2．4 Sphere包围盒

2．2．5 k-DOP包围盒

2．2．6 常用包围盒的性能评价

2．3 基于层次包围盒的碰撞检测算法

2．3．1 算法的基本思想

2．3．2 层次包围盒树的概念

2．3．3 层次包围盒树的实现方法

2．3．4 基于层次包围盒的碰撞检测算法的性能评价

2．4 混合层次包围盒碰撞检测算法的研究

2．4．1 算法的研究意义

2．4．2 算法的基本思想

2．5 本章小结

3 改进的基于混合包围盒的碰撞检测算法

3．1 改进型算法AOs的基本思想

3．1．1 算法的基本思想和改进之处

3．1．2 算法的特点

3．2 AOs混合包围盒树的构建

3．2．1 混合包围盒结构的设计思路

3．2．2 构建的过程

3．2．3 图元集合的划分方法

3．3 AOs混合包围盒树的遍历

3．3．1 遍历方法的总体流程

3．3．2 层次树的下降规则

3．3．3 基于时空相关性理论的优化

3．3．4 包围盒间的相交测试

3．4 AOs混合包围盒树的更新

3．4．1 更新策略的优化

3．4．2 层次树的更新

3．5 本章小结

4 改进的碰撞检测算法的应用设计

4．1 实验环境与工具

4．1．1 视景仿真引擎Vega Prime

4．1．2 三维建模工具Creator

4．2 仿真实验平台的工作原理

4．3 仿真实验平台的搭建

4．4 本章小结

5 实例应用与分析

5．1 实验测试的目标

5．2 实验过程与结果分析

5．2．1 实验一：定向碰撞实验

5．2．2 实验二：随机碰撞实验

5．3 实验结论

5．4 本章小结

6 总结与展望

6．1 工作总结

6．2 进一步的工作与展望

致谢

参考文献