虚拟环境中碰撞检测问题的研究

论文摘要

从上个世纪90年代起,随着计算机网络的快速发展,虚拟现实技术得到了迅速的发展和有力的支持。而在虚拟现实领域中,碰撞检测是其应用的一个重要方面。精确而快速的碰撞检测可以提高虚拟环境的真实性和沉浸感,而虚拟环境本身的复杂性和实时性又对碰撞检测提出了更高的要求。本文以虚拟装配系统的设计为研究背景,针对不同性质的物体采用不同的碰撞检测方法,研究了解决刚体碰撞的基于层次包围盒的碰撞检测算法和解决变形体碰撞的基于小生境PSO的碰撞检测算法。层次包围盒是有效解决刚体碰撞检测问题的方法,本文通过用体积略大而几何特性简单的包围盒来近似地描述所包围的物体,并通过遍历层次二叉树来检测包围盒之间是否发生碰撞,进而继续对包围盒内的基本几何元素进行相交测试以确定物体之间是否发生碰撞。本文将群智能算法中的粒子群算法引入到碰撞检测领域,结合小生境和采样技术,解决了动态多峰值环境中的变形体的碰撞检测问题。本文对以上两种算法进行了实验,分别验证了其对刚体之间和变形体之间进行碰撞检测的效果。实验表明,两种算法均能精确而快速的检测其相应物体的碰撞。本文采用以上两种算法,实现了在虚拟装配系统中的碰撞检测,从而更进一步的证明了算法的正确性和精确性。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 概况
• 1.2 本文研究的目的和意义
• 1.3 碰撞检测技术的发展及研究现状
• 1.3.1 国外研究状况
• 1.3.2 国内研究状况
• 1.4 本文的研究内容
• 1.5 论文的结构
• 第二章 碰撞检测的基本概念
• 2.1 数学概念
• 2.2 几何概念
• 2.2.1 凸多边形
• 2.2.2 凸壳
• 2.2.3 三角剖分
• 2.2.4 Voronoi 图
• 2.2.5 树
• 2.3 优化问题
• 2.4 碰撞检测的基本算法
• 2.4.1 包围盒
• 2.4.2 空间剖分法
• 2.4.3 距离场
• 2.4.4 图像空间方法
• 2.4.5 随机碰撞检测方法
• 2.4.6 智能算法
• 2.5 碰撞算法的性能评价函数
• 2.6 本章小结
• 第三章 基于混合层次包围盒的碰撞检测算法
• 3.1 算法概述
• 3.2 表面的凸分解
• 3.3 层次二叉树的建立
• 3.4 包围盒的构造
• 3.5 包围盒树更新
• 3.6 层次包围盒的碰撞检测
• 3.6.1 层次包围盒的遍历
• 3.6.2 OBB 包围盒的重叠测试
• 3.6.2.1 分离轴原理
• 3.6.2.2 OBB 包围盒间的重叠测试
• 3.6.3 基本几何元素测试
• 3.7 算法的测试
• 3.8 本章小结
• 第四章 基于粒子群算法的碰撞检测
• 4.1 粒子群算法简介
• 4.1.1 基本原理
• 4.1.2 数学描述
• 4.1.3 参数分析
• 4.1.4 PSO 的设计步骤
• 4.1.5 最优化问题
• 4.1.6 动态多目标环境问题
• 4.2 基于小生境粒子群算法的随机碰撞检测
• 4.2.1 基本模型
• 4.2.2 小生境粒子群算法
• 4.2.3 算法流程
• 4.3 实验与性能分析
• 4.3.1 采样与精度调整
• 4.3.2 粒子群规模
• 4.3.3 变形体的碰撞检测
• 4.3.4 性能对比
• 4.4 本章小结
• 第五章 虚拟装配系统中的碰撞检测
• 5.1 虚拟装配
• 5.2 虚拟装配系统的基本组成
• 5.2.1 虚拟零件建模
• 5.2.2 碰撞检测
• 5.3 虚拟装配系统中碰撞检测的实现
• 5.4 本章小结
• 结论与展望
• 参考文献
• 致谢
• 攻读学位期间发表的学术论文目录