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

三角网格模型的求交算法研究与实现

作　者: 张少丽
导　师: 王毅刚；陈小雕
学　校: 杭州电子科技大学
专　业: 计算机应用技术
关键词: 碰撞检测三角网格模型求交层次包围盒空间剖分
分类号: TP391.41
类　型: 硕士论文
年　份: 2009年
下　载: 86次
引　用: 0次
阅　读: 论文下载

内容摘要

本论文主要研究了三角网格模型求交算法。三角面片的剔除很大程度上影响了求交算法的效率,而这类剔除工作是基于碰撞检测来实现的。碰撞检测的目的就是检测多个模型在空间位置上是否部分或完全重合,这样就可以在模型进行求交之前剔除大量不相交的三角面片。虽然碰撞检测技术已经比较成熟,有很多经典的研究成果,但随着计算机图形学的快速发展,三角网格模型的复杂度不断提升,导致求交算法需要处理的三角面片数量也成倍增加。为了满足人们对场景真实性、交互实时性的更高需求,寻求一种快速准确的碰撞检测算法成为当前需要迫切解决的问题。本文在研究和分析了大量碰撞检测算法的基础上,总结了目前主流碰撞检测算法各自的优缺点。这些算法包括空间剖分法、AABB层次包围盒树方法和OBB层次包围盒树算法,对如何将这些算法进行适当的结合和改进,以提高碰撞检测过程的效率并应用于模型间的求交计算进行了一定的探索性研究。空间剖分算法需要判断每个三角面片所占的空间小立方体,这样可以一步定位两个模型的相交情况,但效率不高,尤其是模型复杂度较高时,问题就更加突出。OBB层次包围盒树方法可以用比较快的速度剔除大量不相交的三角面片,但定位可能相交的三角面片这一操作却是一个层层迭代的过程,从这个角度来说就会降低一定的效率。针对两个算法各自的问题,本文对其进行了改进:只对一个求交模型建立包围盒并进行剖分,进一步确定组成模型的三角面片所占的空间小立方体,进行第一次的剔除。然后再对剩余的模型用OBB层次包围盒树进行剔除操作,最后对剩下的三角面片进行求交。改进后的算法在一定程度上提高了求交前期三角面片间的碰撞检测效率,并能剔除较多的三角面片,为下一步的求交工作减轻负担。AABB层次包围盒树方法相对OBB层次包围盒,包围盒紧密性比较差,可能会导致大量冗余的包围盒需要进行相交测试,但这种方法构造简单、操作简便。本文结合了AABB层次包围盒和OBB层次包围盒的优点,提出一种新的求交算法。每次求交操作都直接作用于模型的包围盒,求出包围盒的相交部分,然后将相交包围盒以外的三角面片全部剔除。对剩余的三角面片重建包围盒再次进行求交剔除操作,当剩余的模型三角面片达到某个设定的阈值之后包围盒求交停止进行。通过这一操作,能够剔除较多数量的三角面片,一定程度上减少了进入下一阶段求交的三角面片数。然后再利用OBB层次包围盒对剩余的三角面片进行进一步的剔除,最后对剩余的三角面片进行两两求交。最后,我们使用VC++与OpenGL实现了上述的两个改进的算法,实验表明,两种算法应用于三角网格模型间的求交计算,求交性能有所提高。

全文目录

摘要  5-6
ABSTRACT  6-10
第1章绪论  10-17
  1.1 引言  10-11
  1.2 三角网格模型的相关概念  11-13
    1.2.1 单纯复形  11-12
    1.2.2 三角网格  12-13
    1.2.3 法向网格  13
  1.3 论文的研究意义  13
  1.4 国内外研究现状  13-15
  1.5 论文研究的主要内容  15-16
  1.6 论文的组织结构  16-17
第2章模型求交过程与碰撞检测算法介绍  17-34
  2.1 三角网格模型求交算法过程  17-23
    2.1.1 模型求交的一般流程  17
    2.1.2 初步检测阶段  17-19
    2.1.3 详细检测阶段  19-20
    2.1.4 具体求交计算  20-23
  2.2 主要碰撞检测算法介绍  23-34
    2.2.1 面向凸体的碰撞检测算法  23-25
      2.2.1.1 基于特征的碰撞检测算法  23-24
      2.2.1.2 基于单纯形的碰撞检测算法  24-25
    2.2.2 基于一般表示的碰撞检测算法  25-26
      2.2.2.1 面向CSG 表示模型的碰撞检测算法  25
      2.2.2.2 面向参数曲面的碰撞检测算法  25-26
      2.2.2.3 面向体表示模型的碰撞检测算法  26
    2.2.3 基于层次包围盒树的碰撞检测算法  26-31
      2.2.3.1 AABB 包围盒树算法  27-28
      2.2.3.2 层次包围球树算法  28
      2.2.3.3 OBB 层次包围盒树算法  28-29
      2.2.3.4 K-DOPs 层次包围盒树算法  29-30
      2.2.3.5 扫成球层次包围盒树算法  30-31
    2.2.4 基于图像空间的碰撞检测算法  31-32
    2.2.5 基于流的碰撞检测算法  32-34
第3章基于空间剖分方法的改进算法  34-46
  3.1 空间剖分法  34-35
  3.2 OBB 层次包围盒检测  35-39
    3.2.1 OBB 包围盒的计算  35-36
    3.2.2 OBB 包围盒树的构造  36
    3.2.3 OBB 包围盒的相交测试  36-38
    3.2.4 OBB 包围盒树的碰撞检测  38-39
  3.3 算法改进  39-42
  3.4 实验结果及分析  42-45
  3.5 小结  45-46
第4章基于层次包围盒方法的改进算法  46-55
  4.1 AABB 层次包围盒检测  46-48
  4.2 算法提出背景  48-49
  4.3 算法实现  49-51
  4.4 实验结果及分析  51-54
  4.5 小结  54-55
第5章总结与展望  55-57
  5.1 本文工作总结  55-56
  5.2 对今后工作的展望  56-57
致谢  57-58
参考文献  58-62
附录  62

三角网格模型的求交算法研究与实现

内容摘要

全文目录

相似论文