学位论文 > 优秀研究生学位论文题录展示

优化的OBB碰撞检测算法研究

作　者: 姜鹏程
导　师: 潘振宽
学　校: 青岛大学
专　业: 计算机软件与理论
关键词: 碰撞检测层次包围盒 OBB树分离轴相交测试
分类号: TP311.52
类　型: 硕士论文
年　份: 2005年
下　载: 256次
引　用: 5次
阅　读: 论文下载

内容摘要

层次包围盒是碰撞检测算法中广泛使用的一种方法。常见包围盒类型有Sphere、AABB、OBB、k-DOP和convex hull等。就刚体间碰撞检测而言,性能最好的是基于OBB的碰撞检测算法,其曾一度被作为碰撞检测算法的评价标准。本文是以大型复杂环境模型中的刚体为研究对象,着重论述了基于OBB碰撞检测方法的相关问题。主要从事了以下几个方面的工作: (1) 在研究OBB等层次包围盒固有特性的基础上,通过具体实现构建OBB和OBB树、包围盒间重叠测试等技术,比较了OBB适用于复杂环境中刚体碰撞检测的优势,并针对OBB存在的缺点和不足加以优化。 (2) 针对基于OBB碰撞检测算法存在的缺陷,研究利用包围盒与基本几何元素相交测试的优化方法,消除叶子结点包围盒,精简OBB层次结构;同时在基本几何元素相交测试中引入类似分离轴的方法,加快检测速度。通过多种检测方法的组合,得出基于OBB的优化层次结构和混合算法。实验结果和具体应用表明,基于OBB的碰撞检测方法能很好地解决复杂环境中刚体间的碰撞检测问题。本文的研究成果,对大规模复杂环境中的碰撞检测有一定的理论价值和实际意义。

全文目录

第一章引言  6-12
  1.1 碰撞检测原理及分类  6-7
  1.2 碰撞检测算法的发展  7-10
  1.3 本文的主要工作  10-12
第二章经典的层次包围盒方法  12-24
  2.1 层次包围盒原理  12-13
  2.2 包围盒方法的分类  13-16
    2.2.1 包围球方法  13-14
    2.2.2 沿坐标轴包围盒方法  14
    2.2.3 方向包围盒方法  14-15
    2.2.4 固定方向凸包方法  15-16
  2.3 包围盒树的构造  16-18
    2.3.1 自底向上方法  16-17
    2.3.2 自顶向下方法  17
    2.3.3 剖分策略和过程  17-18
  2.4 对象运动后包围盒树的更新  18-20
  2.5 层次包围盒方法的性能分析  20-24
    2.5.1 碰撞检测的耗费函数  20-21
    2.5.2 OBB与其他包围盒的比较  21-24
第三章基于OBB的碰撞检测方法  24-37
  3.1 OBB包围盒树  24-27
    3.1.1 计算OBB  24-26
    3.1.2 构造OBB树  26-27
  3.2 OBB碰撞检测算法  27-29
    3.2.1 传统的OBB碰撞检测算法  27-28
    3.2.2 引入Cache理念的OBB算法  28-29
  3.3 OBB间的重叠测试  29-32
    3.3.1 分离轴原理  30
    3.3.2 OBB间重叠测试的实现  30-32
  3.4 基本几何元素间的相交测试  32-37
    3.4.1 三角形的相交测试  33-35
    3.4.2 相交测试的优化流程  35-37
第四章优化的OBB包围盒层次结构  37-43
  4.1 存储问题综述  37-38
  4.2 早期存储优化  38
  4.3 优化的碰撞检测混合算法  38-41
  4.4 B-P测试的实现  41-43
第五章 OBB碰撞检测算法实例  43-46
  5.1 重要的数据结构  43-44
  5.2 碰撞检测实例及结果分析  44-46
第六章总结与展望  46-47
参考文献  47-52
致谢  52-53
学位论文独创性声明、学位论文知识产权权属声明  53-54

优化的OBB碰撞检测算法研究

内容摘要

全文目录

相似论文