变形物体碰撞检测技术研究

论文摘要

碰撞检测及其相关问题有着悠久的研究历史,在计算机图形学、计算几何、机器人学、CAD/CAM等研究领域具有十分重要的作用。近年来随着虚拟现实、分布交互仿真等技术的兴起,人们对交互的实时性、场景的真实性的要求越来越高,变形物体的实时碰撞检测成为了研究的热点。本文在对各类碰撞检测算法作出全面了解和透彻分析的基础上,从以下几个方面对变形物体的碰撞检测问题进行研究,提出新的检测碰撞的思想和方法,从而使碰撞检测技术有进一步的发展。(1)从提高碰撞检测的实时性和通用性方面入手,将人工智能中经典的粒子群优化算法引入到碰撞检测领域,提出了应用粒子群优化算法的通用随机碰撞检测算法。该算法在继承一般碰撞检测算法优点的同时,突破了它们的局限性,不但能够在保证效率的前提下处理无拓扑物体的碰撞检测问题而且也可以处理任意物体表示模型之间的碰撞检测,具有较强的通用性;此外检测精度和速度可以人为的调整以满足不同应用的需求,增加了碰撞检测系统的灵活性。(2)结合层次包围体树结构和随机碰撞检测算法的优点提出了一种大型复杂变形物体的快速碰撞检测方法。该算法利用层次包围体树快速剔除物体上不相交的区域,只在碰撞了的节点内进行智能搜索,既避免了单纯采用粒子群优化方法目标空间过大造成的搜索速度慢的缺点,又减少单纯使用层次包围体树的方法所消耗的大量存储空间和更新速度慢等问题。(3)在分析研究虚拟装配领域的实际问题的基础上,针对虚拟装配系统中的变形物体的特点,提出了一种基于组件的碰撞检测技术。其中重点研究了基于物体OBB包围盒的组件层次包围体树的构建和更新问题,提出了快速的组件OBB包围盒的生成算法、求两OBB包围盒凸壳的快速算法和N个物体构成组件层次体树的建构与更新的方法。实验证明组件模型具有构建层次分明、运动更新简便、能完成自我碰撞检测等诸多优点。

论文目录

• 内容提要
• 第一章 绪论
• 1.1 碰撞检测技术发展和现状
• 1.2 碰撞检测系统一般结构
• 1.3 主要算法简介
• 1.3.1 基于层次包围体树的碰撞检测算法
• 1.3.2 空间剖分
• 1.3.3 距离场
• 1.3.4 基于图像空间的碰撞检测
• 1.3.5 比较与讨论
• 1.4 研究目标与工作
• 第二章 粒子群优化的随机碰撞检测算法
• 2.1 粒子群优化算法
• 2.1.1 基本原理
• 2.1.2 数学描述
• 2.1.3 基本流程
• 2.1.4 参数分析
• 2.1.5 多目标PSO 算法
• 2.1.6 动态多目标环境问题
• 2.2 PSO 优化的随机碰撞检测
• 2.2.1 随机碰撞检测概述
• 2.2.2 问题模型
• 2.2.3 基本算法流程
• 2.2.4 特征采样
• 2.2.5 适应度的计算
• 2.3 基于聚类小生境PSO 的通用随机碰撞检测算法
• 2.3.1 基于密度的聚类
• 2.3.2 碰撞检测核心算法
• 2.3.3 快速跟踪策略
• 2.3.4 更新策略
• 2.4 实验与性能分析
• 2.4.1 采样与精度调整
• 2.4.2 粒子群规模
• 2.4.3 更新速度
• 2.4.4 性能对比
• 2.5 本章小结
• 第三章 基于层次包围体树的混合碰撞检测算法
• 3.1 层次包围体树
• 3.1.1 AABB 包围盒
• 3.1.2 坐标变换
• 3.1.3 相交测试
• 3.1.4 AABB 层次包围体树的构建
• 3.1.5 AABB 层次包围体树的更新
• 3.1.5.1 包围盒的更新
• 3.2 混合碰撞检测核心算法
• 3.2.1 算法描述
• 3.2.2 自底向上更新包围体树
• 3.2.3 节点内部的更新
• 3.3 试验与讨论
• 3.4 本章小结
• 第四章 基于组件技术的碰撞检测算法
• 4.1 基本概念与定义
• 4.1.1 主元分析
• 4.1.2 凸壳
• 4.1.3 方向包围盒OBB
• 4.2 组件OBB 算法
• 4.3 投影法求两OBB 凸壳顶点
• 4.3.1 二维空间两个OBB 凸壳顶点
• 4.3.2 三维两个OBB 凸壳顶点
• 4.4 组件层次包围体树的构建
• 4.4.1 基于AABB 包围盒的N 个物体组件层次包围体树算法
• 4.4.2 基于OBB 包围盒N 个物体组件算法
• 4.5 组件层次包围体树的更新
• 4.5.1 增加物体
• 4.5.2 移出物体
• 4.6 实验与分析
• 4.6.1 利用两个物体OBB 包围盒生成组件包围盒
• 4.6.2 N 个物体组件层次包围体树的建立
• 4.7 应用实例：虚拟组件手
• 4.7.1 划分
• 4.7.2 建立部件层次模型
• 4.7.3 建立组件手层次模型
• 4.7.4 组件虚拟手运动更新
• 4.7.5 虚拟手碰撞检测和自我碰撞检测
• 4.7.6 实验与分析
• 4.8 本章小结
• 第五章 总结与展望
• 参考文献
• 致谢
• 作者攻读博士期间发表的论文情况
• 学位论文摘要（中文）
• 学位论文摘要（英文）