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

一种三维碰撞检测并行算法的设计与实现

作　者: 胡祥潇
导　师: 胡迎松
学　校: 华中科技大学
专　业: 计算机应用技术
关键词: 碰撞检测轴对齐包围盒二叉空间剖分并行
分类号: TP391.9
类　型: 硕士论文
年　份: 2011年
下　载: 75次
引　用: 0次
阅　读: 论文下载

内容摘要

随着计算机软硬件以及网络等技术的日益成熟,人们迫切希望能对现实世界进行真实的模拟,以解决实际问题。而碰撞检测问题是计算机动画,物理仿真,计算几何,机器人学,计算机游戏等领域的重要课题。在虚拟环境中,碰撞检测可以为物体之间的交互建立良好的基础。因此,如何在很高的实时交互要求下完成对大量复杂物体的相交测试是碰撞检测研究的首要目标。分析和比较了当前几种常用碰撞检测算法的优势和不足,有效地结合轴对齐包围盒(Aligned Axis Bounding Box,AABB)算法和二叉空间剖分(Binary Space Partitioning,BSP)算法进行碰撞检测。根据两种碰撞检测算法自身的特点,把BSP算法应用于碰撞初步检测阶段,把AABB算法应用于详细碰撞检测阶段,并优化AABB的更新算法,减少计算量,从而提高碰撞检测效率;给出了一种新的分治策略,在多处理器机器上利用多进程和多线程技术,根据虚拟环境中的复杂度,把碰撞检测问题分而治之分配给不同的线程并行处理;通过主从进程模式来进行通信控制。算法充分地利用了硬件资源,从而大大地提高了碰撞检测效率,也增强了虚拟环境的真实性和可靠性。在总体安全监测与评估平台上的三维实时显示与报警模块中,结合基于BSP和AABB的三维碰撞检测并行算法设计了相关的测试案例,并与基本碰撞检测算法、串行碰撞检测算法进行对比,从理论时间复杂度和实际运行时间两方面进行了性能测试。测试结果表明,使用基于BSP和AABB的三维并行碰撞检测时,系统帧率明显增加,系统运行更加流畅。

全文目录

摘要  4-5
Abstract  5-8
1 绪论  8-13
  1.1 课题背景  8-9
  1.2 国内外研究现状  9-11
  1.3 研究内容与组织结构  11-13
2 碰撞检测相关技术分析  13-20
  2.1 碰撞检测基本理论  13
  2.2 碰撞检测算法分类  13-19
  2.3 碰撞检测算法框架  19
  2.4 本章小结  19-20
3 基于BSP 和AABB 的三维碰撞检测并行算法的设计  20-34
  3.1 算法总体架构  20-21
  3.2 BSP 树的构造  21-24
  3.3 AABB 树的构造  24-28
  3.4 串行碰撞检测  28-31
  3.5 并行处理  31-33
  3.6 本章小结  33-34
4 算法实现及性能测试  34-47
  4.1 算法实验平台  34-36
  4.2 算法的实现  36-42
  4.3 算法性能测试  42-46
  4.4 本章小结  46-47
5 总结与展望  47-49
  5.1 本文主要工作  47
  5.2 进一步研究方向  47-49
致谢  49-50
参考文献  50-54
附录攻读学位期间发表论文目录  54

一种三维碰撞检测并行算法的设计与实现

内容摘要

全文目录

相似论文