第 1 章 绪论
1.1 研究背景和意义
随着计算机硬件与软件技术的快速发展，虚拟现实技术随之迅速兴起，它利用计算机生成一种模拟环境，并通过多种专用虚拟现实设备（比如头盔、眼镜等）让用户使用人类的对世界的感知技能对虚拟世界中的场景和物体进行观察和操作，同时提供视、听、摸等实时感知。随着计算机软硬件及网络等技术的日益成熟，虚拟现实的三维空间表现能力、自然的人机交互式操作环境以及给人带来身临其境的感受，将从根本上改变人与计算机之间枯燥、生硬和被动的现状[1]。为了满足虚拟现实环境中所需要的沉浸感、交互性、构想性三大要求，不仅要求从视觉上可以感知到真实的虚拟环境，同时还要求从操纵中感受到实时的环境动态反馈[2]。这是指模拟的物体不仅要可被观测，还需要有一定的物理属性，以实现与用户的多种互动。因此不可穿透性就是物体最重要的特性，在用户与物体的交互过程中，各个物体之间不能直接发生穿透，在对物体进行推拉等操作时，要能真实感受到力的存在，因此碰撞检测技术在虚拟现实技术中占有重要的地位[3]。
碰撞检测技术是计算机图形学、虚拟现实等领域的热点问题。碰撞检测的主要任务是在虚拟场景中检测两个或者更多的物体是否发生了接触，也就是检测它们之间是否占有同一空间，当它们占有同一空间时也就是产生了碰撞[4]。从上世纪 70 年代开始，许多研究者就对碰撞检测技术进行了研究，主要应用领域在虚拟装配以及机器人路径规划等领域中，但是由于计算机硬件水平较低和算法技术水平的影响，模拟环境中的碰撞检测通常不能实时的完成，不能满足大部分应用场景的实时需要。随着计算机硬件水平提高以及游戏、动画和虚拟场景等的大规模应用，实时碰撞检测技术开始迅速发展起来。同时，随着近年来计算机图形技术的发展，大规模复杂场景的实时仿真受到了广泛关注，人们对于复杂场景中的交互性和操控要求不断提高，对碰撞检测算法的实时性和精确性的要求也越来越高[5]。
.........................
1.2 国内外研究现状
经过几十年不断发展，国内外研究者已经在碰撞检测领域做了许多贡献，提出了许多高效的碰撞检测算法。通过时间域碰撞检测算法可分为三类：静态碰撞检测算法、离散碰撞检测算法和动态碰撞检测算法[7]。在碰撞检测技术的研究初期，碰撞检测需求场景通常是在场景中物体在整个时间轴中不发生变化和位移的碰撞检测过程，即静态碰撞检测，一般该算法对算法精确性要求较高，不追求算法的实时性。随着计算机技术水平的提高，对碰撞检测算法实时性的要求越来越高，随之出现了一种离散碰撞检测算法，它将场景中动态的碰撞检测过程划分成许多的离散时间片，在每个时间片内进行静态碰撞检测，实际上是一种伪连续碰撞检测方法，该方法存在的缺陷是可能会出现穿刺和漏检的情况。之后虽然许多学者提出了许多的动态碰撞检测算法，但由于其不能满足大规模计算场景实时性的需求，离散碰撞检测算法仍然是现如今碰撞检测领域计算方法的研究重点[8]。下面分别介绍下主要的碰撞检测算法。
1、基于空间剖分的碰撞检测算法
空间剖分法是将虚拟环境空间场景通过某种规则划分成小的单元，每个单元包含许多物体对象，通过对象列表记录每个小的单元中所有包含的物体对象，在实际碰撞检测过程中只需要检测同一个单元下或者相邻单元中的物体对象是否发生碰撞，不相邻的物体由于距离较远不宜发生干涉，同时也可以实现一个物体不同部分的自我干涉检测。
在 1990 年,Turk 等人在[9]中首次提出在均匀剖分中使用空间哈希表(SpatialHashing)来加快查询速度。均匀剖分方法是根据需求把场景空间均匀的划分成大小一致的网格。这种方法比较适合物体位置分布较为分散的情况;反之如果待检测物零部件处于较为集中的区域，最坏情况会导致2O(n) 的时间复杂度。常用的空间剖分方法还有四叉树(quartree)[10]、八叉树(octree)[11]、k-d 树[12]、R-tree[13]和 BSP 树[14]等。
..........................
第 2 章 虚拟装配碰撞问题分析
2.1 虚拟装配中碰撞检测问题表达与描述
虚拟装配的实质是在计算机上模拟零部件的装配过程，不仅能够分析零部件的装配性能，还能确定最佳的装配方案[35]。现如今，通常的虚拟装配过程主要是通过静态的约束条件实现零部件的分离过程，实际操作中装配环境一般为动态的，需要人为进行零部件位置角度的调整、装配顺序的变更以及装配路径的规划，系统需要实时对人工的操作调整进行验证。因此需要在零部件装配过程中引入碰撞检测系统以便验证虚拟装配环节人工设置是否具有可行性。
虚拟装配环境中，碰撞通常发生在移动的物体（待装配零部件、工具等）与静止物体（虚拟场景、已装配好的零部件等）。因此可以只对因装配需要而产生干涉可能的零部件之间进行具体细致的碰撞检测，对虚拟装配场景中静止的部分物体采用粗略的包围盒简单检测。这样不仅可以满足整个虚拟装配环境中碰撞检测功能的需求，同时还可以整体提高碰撞检测的效率。在虚拟装配环境中，由于场景一般为动态变化的，因此采用离散碰撞检测方法。
在实际检测过程中，“零部件之间距离为 0”并不能作为判断零部件是否产生干涉的依据，因为碰撞检测算法在计算模型间的碰撞时采用的是离散的时间步，因此模型在碰撞检测过程中的运动是离散的，如果将距离阈值设置为 0，有可能发生碰撞穿刺现象，无法实现准确的碰撞检测[36]。因此需要对待装配零部件的碰撞范围设定一个大于 0 的阈值条件[37]。
在研究碰撞检测算法时，需要考虑到三维模型的集合表达方式。计算机中三维模型表示通常为实际模型的近似表示，一般由大量基本多边形组成三维模型的基本形状，基本的位置、大小等信息由组成三维模型的多边形的坐标组合表示。多边形通过公共边能够连接为一个大型的多边形表面模型，称之为多边形网格。多边形网格是构建几何模型最常使用的方法。多边形网格按照顶点、边以及面片来加以定义。这种构造物体的方式通常被称为显式表示方式。如图 2-1 所示，计算机中三维模型的多边形网格目前通用都是将三角形作为基本的图元。
...........................
2.2 包围盒技术
包围盒碰撞检测算法指的是通过对各种复杂形状的物体利用一些简单的几何图形来构建包围盒进行碰撞检测的方法。它能简化碰撞检测的复杂度，提高检测的效率，具体的原理就是在复杂物体上构建一个简单几何物体组成包围盒，通过对包围盒进行检测来代替对物体的检测，只有在检测到包围盒相交时物体才有可能发生穿透现象，包围盒不相交时物体一定不会发生穿透。基于此，通过包围盒就能尽可能排除掉空间中不相交的物体，找到可能发生碰撞的物体。
常见的包围盒类型通过形状一般分为以下几类：球体包围盒（Sphere）、轴向包围盒[38]（Axis-Aligned Bounding Boxes：AABB）、有向包围盒[39]（Oriented BoundingBox：OBB）、离散方向多面体[40]（Discrete Orientation Polytopes: k-DOP）等，如图 2-3 所示是不同包围盒在二维平面上的构造效果。
.......................
第 3 章 层次包围盒算法...............................14
3.1 基于 AABB 和 Sphere 的混合层次包围盒算法.........................14
3.1.1 算法描述...........................14
3.1.2 混合层次包围盒树形结构的改进..............................14
第 4 章 基于蚁群算法的随机碰撞检测算法................................22
4.1 随机碰撞检测算法.................................22
4.1.1 算法描述.................................22
4.1.2 随机碰撞检测问题描述.................................23
第 5 章 碰撞检测算法在虚拟装配中的应用....................................33
5.1 概述.................................33
5.2 虚拟装配系统..................................33
第 5 章 碰撞检测算法在虚拟装配中的应用
5.1 概述
在本章所介绍阿虚拟装配系统基于 Unity 开发，Unity 又称作 Unity3D，是由Unity Technologies 所开发的一个由用户创建诸如三维视频、场景可视化、实时场景仿真等类型内容的综合性仿真应用系统开发工具。本系统采用的碰撞检测算法主要用到了 OpenGL，OpenGL（Open Graphics Library）是用于渲染 2D、3D 矢量图形的跨语言、跨平台的应用程序编程接口。这个接口由近 350 个不同的函数调用组成，用来从简单的图形比特绘制复杂的三维景象。OpenGL 可以利用了厂商硬件进行渲染加速，先通常运用于图形渲染、三维图像开发等。
本章系统应用了 OpenGL 的 GLFW 库，支持 OpenGL，用来管理窗口，读取输入，处理事件等。
.......................
第 6 章 总结与展望
6.1 总结
本文主要针对基于蚁群算法的虚拟装配系统中的碰撞检测算法进行研究。应用混合层次包围盒技术建立基本的碰撞检测方法结构，在碰撞检测算法详细检测阶段中引入了随机碰撞检测算法，将碰撞问题转化成二维
