学位论文 > 优秀研究生学位论文题录展示
三角网格模型的求交算法研究与实现
作 者: 张少丽
导 师: 王毅刚;陈小雕
学 校: 杭州电子科技大学
专 业: 计算机应用技术
关键词: 碰撞检测 三角网格 模型求交 层次包围盒 空间剖分
分类号: 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
|
相似论文
- 基于模型的水稻根系可视化研究,S511
- 虚拟手术中建模与仿真关键技术研究,TP391.41
- 虚拟校园的三维建模与设计,TP391.9
- 汽车起重机模拟作业系统关键技术的研究,TH213.6
- 河北旅游职业学院虚拟校园漫游系统设计与实现,TP391.9
- 基于OGRE的压延塑化三维仿真系统的设计与实现,TP391.9
- 自动化排牙系统的研究与实现,R783
- 车辆驾驶模拟器视景仿真技术研究,TP391.9
- 动画自动生成中三维虚拟角色路径规划的研究与实现,TP391.41
- 树随风动模拟中的碰撞检测问题研究,TP391.9
- 虚拟旅游景区漫游系统的研究,TP391.9
- 树枝断裂现象的可视化模拟,TP391.41
- 虚拟矿井的设计与实现,TD214
- 弹簧数控卷绕仿真系统研究,TH135
- 虚拟现实中物理引擎关键技术的研究与应用,TP391.9
- 基于虚拟现实技术的校园漫游系统,TP391.9
- 离散曲面高斯曲率估算算法研究,TP391.41
- 虚拟手术仿真系统中碰撞检测的研究,TP391.9
- 实时三维漫游系统中关键技术研究与实现,TP391.41
- 网格曲面求交及其交线的等距线构造,TP391.72
中图分类: > 工业技术 > 自动化技术、计算机技术 > 计算技术、计算机技术 > 计算机的应用 > 信息处理(信息加工) > 模式识别与装置 > 图像识别及其装置
© 2012 www.xueweilunwen.com
|