GJK碰撞检测算法的研究和改进

论文摘要

碰撞检测是机器人、动画仿真与虚拟现实等领域中一个非常关键的问题,其基本任务是确定两个或多个物体彼此之间是否发生接触或穿透。尽管针对碰撞检测已有了大量有价值的研究成果,但随着诸如虚拟现实等新兴领域的涌现及随之而来的人们对交互实时性、场景真实性要求的不断提高,碰撞检测技术所面临的问题也日益突出,其中最核心的问题是如何有效地提高碰撞检测的速度。本文重点研究了基于距离跟踪的Gilbert-Johnson-Keerth（简称GJK）碰撞算法。GJK是通过支持映射来计算空间中两个凸体间距的渐进算法,虽然其数学模型比较复杂,且难以理解,但是基于GJK模型的算法有快速,易实施且适用于多种凸体的优点。传统的基于GJK模型的碰撞检测通过距离跟踪来检测物体是否碰撞,在算法的执行速度和稳定方面还有所欠缺,本文首先对GJK模型在性能、健壮性以及内存消耗方面作了改进,然后将GJK模型应用于以下两方面:一是将其以最优的方式应用于碰撞检测;二是计算相互穿刺物体间的穿刺深度,并对最终的实现代码做了进一步的优化。

论文目录

• 摘要
• Abstract
• 1 引言
• 1.1 研究背景和意义
• 1.2 国内外的研究动态
• 1.3 论文的主要工作
• 2 基本概念
• 2.1 超平面（Hyperplane）
• 2.2 凸包（Convex Hull）
• 2.3 支持映射（Support Mapping）
• 2.4 闵可夫斯基和（Minkowski Sum）
• 2.5 小结
• 3 Gilbert-Johnson-Keerthi（简称 GJK）模型
• 3.1 关于 GJK 模型的简介
• 3.2 GJK 距离检测算法的伪代码
• 3.3 JOHNSON 距离计算模型
• 3.4 GJK 中凸体及其支持映射
• 3.4.1 多胞形（Polytope）的支持映射（Support Mapping）
• 3.4.2 盒（Box）的支持映射（Support Mapping）
• 3.4.3 球（Sphere）的支持映射（Support Mapping）
• 3.4.4 锥体（Cone）的支持映射（Support Mapping）
• 3.4.5 柱体（Cylinder）的支持映射（Support Mapping）
• 3.4.6 仿射变换（Affine Transformation）
• 3.4.7 Minkowski 和（Minkowski Sum）
• 3.5 GJK 算法存在的问题和解决方案
• 3.5.1 Johnson 距离计算模型引入误差和解决方案
• 3.5.2 结束条件导致的异常及解决方案
• 3.5.3 特殊边界导致的异常及修正
• 3.5.4 修正后的 GJK 算法
• 3.6 小结
• 4 GJK 算法的快速实现和应用
• 4.1 GJK 算法的快速实现
• 4.1.1 缓存向量差
• i^X 行列式的值'>4.1.2 缓存Δ_i^X行列式的值
• 4.1.3 通过定理提速
• 4.2 GJK 算法在碰撞检测方面的应用
• 4.3 GJK 在穿刺深度（Penetration Depth）计算方面的应用
• 4.3.1 二维空间穿刺深度的计算
• 4.3.2 三维空间穿刺深度的计算
• 4.3.3 穿刺深度算法初始化的问题
• 4.3.4 穿刺深度算法存在的问题以及修正
• 4.4 小结
• 5 编码和实验结果
• 5.1 数据结构以及算法编码
• 5.2 实验部分
• 5.2.1 碰撞检测实验部分
• 5.2.2 GJK 穿刺深度计算算法实验部分
• 5.3 小结
• 6 工作总结和展望
• 攻读硕士期间发表的论文
• 致谢
• 参考文献