基于K-DOPS的快速碰撞检测算法研究

论文摘要

碰撞检测是虚拟现实、动画仿真、计算机辅助设计等领域不可回避的问题之一,其基本任务是确定两个或多个物体彼此之间是否发生接触或穿透。尽管人们已经取得了一系列成果,但是这些算法侧重于考虑碰撞检测的精确性,很少涉及实时性。随着计算机软硬件及网络等技术的日益成熟,交互实时性、场景真实性要求令碰撞检测再度成为图形学研究的热点。本文主要研究基于K-DOPS包围盒方法的碰撞检测,阐述了K-DOPS包围盒的原理,提出并证明了一种快速区间测试法以解决两个K-DOPS包围盒间的相交测试问题,通过查找两个包围盒在由固定方向集合所定义的方向轴上的范围区间是否存在不重叠的情况,来判断它们是否不相交。通过这种简单的区间测试法,两个包围盒间的相交测试最多只需要k次比较运算（k为固定方向集合的大小）。在充分开发和利用虚拟环境中对象运动的时空相关性的基础上,提出了加速对象间碰撞检测速度的遍历跟踪策略。这是一个启发式的策略,通过跟踪上一时间采样点对包围盒树的遍历过程,确定当前时间采样点的遍历路径,从而有效地减少了遍历过程中包围盒相交测试的次数,提高了算法效率,同时通过对跟踪表的维护,保证了碰撞检测的正确性和有效性。

论文目录

• 摘要
• Abstract
• 1 绪论
• 1.1 研究背景和意义
• 1.2 问题描述
• 1.3 国内外研究状况
• 1.4 论文结构
• 2 碰撞检测技术
• 2.1 碰撞检测基本思想
• 2.2 碰撞检测算法分类
• 2.3 碰撞检测算法流程
• 2.3.1 初步检测阶段
• 2.3.2 详细检测阶段
• 3 K-DOPS 包围盒的原理
• 3.1 基本定义
• 3.2 K-DOPS（DISCRETE ORIENTATION POLYTOPES）的定义
• 3.3 固定方向集的选择
• 3.4 向量的表示
• 3.5 K-DOPS 的计算
• 3.6 K-DOPS 包围盒特性
• 3.6.1 包围盒树
• 3.6.2 构造包围盒树
• 3.7 本章小结
• 4 碰撞检测算法及相交测试
• 4.1 碰撞检测算法
• 4.2 K-DOPS 间相交测试
• 4.3 区间测试的次序
• 4.4 基本几何元素间的相交测试
• 4.4.1 三维空间中的三角形相交测试
• 4.4.2 二维平面中三角形相交测试
• 4.5 本章小结
• 5 碰撞检测的加速方法
• 5.1 时空相关性
• 5.2 遍历跟踪策略
• 5.3 跟踪表的维护
• 5.3.1 向下更新
• 5.3.2 向上更新
• 5.4 本章小结
• 6 实验结果与分析
• 6.1 代价函数
• 6.2 构造 K-DOPS 树的时空开销
• 6.3 平均碰撞检测时间
• 6.4 加速算法验证与分析
• 7 总结与展望
• 参考文献
• 致谢
• 攻读学位期间发表的学位论文及科研成果