虚拟现实中的碰撞检测技术word文档格式.docx

碰撞检测技术的研究摘 要实时精确的碰撞检测对于提高虚拟环境的真实性、增强虚拟环境的沉浸感有着至关重要的作用。 该文对碰撞检测相关技术进行了深入的研究,主要包括以下几个方面的内容：首先介绍了虚拟现实技术的发展及现状、碰撞检测的研究现状；然后简单介绍了碰撞检测一些基础理论知识，着重介绍常用的碰撞检测算法。紧接着，简单介绍了OpenGL编程的基础知识和面向对象编程的特点。在碰撞检测算法的应用中，运用OBB包围盒层次树的碰撞检测算法，提出了一种一般多面体间碰撞检测的可行性方案，并用软件对该方案进行实现，同时指出该方案的优缺点。最后,对全文进行了总结,并指出今后的研究方向。关键词：虚拟现实 碰撞检测 包围盒层次树 OBB56 -STUDY AND IMPLEMENTATION ON COLLISIONDETECTION TECNOLOGY OF VIRTUAL REALITYAbstractReal-time and accurate collision detection is very important to improve reality and enhance illusion of immersion for virtual environment.This paper studies the technique of collision detection deeply.It contains the following parts:Firstly,this paper reviews recent research on collision detection field.Then it introduces some basic knowledge and emphasizes on introduce of collision detection algorithm.Next,it introduces OpenGL and Oriented-object language program character.In collision detection implementation chapter,a scheme of collision detection between general polyhedron is presented by using bounding hierarchy volume algorithm.The method is implemented by vc6.0.And it analyses advantage and disadvantage of the method.Finally,the conclusion is drawn and the work of future research is presented.KEY WORDS: virtual reality collision detection bounding hierarchy volume OBB 目 录第一章绪 论11.1虚拟现实技术发展及现状11.1.1 虚拟现实的特点11.1.2 国内外虚拟现实技术的研究状况21.2碰撞检测的研究现状31.2.1意义及特点31.2.2碰撞检测的研究现状41.3论文的工作和组织结构6第二章 碰撞检测理论82.1碰撞的定义382.2碰撞检测的模型类别82.3碰撞检测的场景特征292.4碰撞检测技术的基本原理9第三章 碰撞检测算法113.1空间剖分法113.2包围盒层次树法123.2.1包围盒形状的设计准则133.2.2包围盒类型133.3 基于特征的距离计算增量算法163.3.1基本概念163.3.2 Lin-Canny算法概述193.3.3适应性准则20第四章 编程基础理论254.1 OpenGL编程基础254.1.1 OpenGL基本特点254.1.2 OpenGL实现274.1.3 OpenGL图形绘制284.1.4 OpenGL光照处理294.1.5 OpenGL纹理映射304.1.6深度测试324.2面向对象的编程324.3 OpenGL编程环境的设置33第五章 碰撞检测算法的应用355. 1物体建模355. 2场景绘制385.3碰撞检测算法的应用415.3. 1 基础理论415.3.2 碰撞检测的实现过程435.3.4用户交互505.4本程序的优缺点52第六章 总结与展望54主要参考文献55第一章 绪 论1.1虚拟现实技术发展及现状1.1.1 虚拟现实的特点自20世纪90年代初以来，虚拟现实技术一直是信息领域研究、开发和应用的热点方向之一。虚拟现实（Virtual Reality）,也称为“人工现实”或“临境”技术，是多媒体发展的更高境界，虚拟现实以更加高级的集成化和交互性，给用户以更加逼真的体验，可广泛应用在模拟训练、科学可视化等领域，将是今后十分活跃的技术课题。虚拟现实就是用计算机技术生成一个逼真的，集听、视、触及嗅觉为一体的感觉世界，用户以人的自然技能与虚拟现实交互考察，包含三层意思：11) 虚拟实体是用计算机来生成的一个逼真的实体，“逼真”就是要达到三维视觉，甚至其他三维感觉。2) 用户可以通过人的自然技能（如头和眼的转动、手势等其他身体动作）与环境交互。3) 虚拟现实往往要借助于一些三维传感设备来完成交互动作，如头盔立体显示、数据手套、数据服装、三维鼠标等。虚拟现实是一种高度集成技术，是计算机、机器人、人工智能以及心理学等发展的联合结晶，因此取决于三维实时图像显示、三维定位跟踪传感技术、人工智能技术、高速并行计算机技术及人的行为学等领域的研究进展。因此虚拟现实技术的研究和实现难度很高，美国著名图形学专家J.Foley讲过：“虚拟现实是人机接口设计中最后一个堡垒，也是最有意义的领域。”虚拟现实的基本特征可以概括为三个“I”,即Immersion-Interaction-Imagination(沉浸-交互-构思)。它强调了人在信息处理过程中的主导作用，使信息处理从以计算机为中心转到以人为中心。虚拟现实这一概念起源于Ivan Sutherland在1965年发表的一篇题为“The Ultimate Display”的报告。在该报告中提出利用计算机系统构造一个具有视觉、听觉和感觉真实感的世界。1968年，Ivan Sutherland开发了第一个可以跟踪头部运动的头盔显示器（head-Mounted Display,简称HMD）。HMD根据用户在虚拟世界的位置来显示相应的内容，当用户移动或转动头部时，通过HMD所看到的虚拟世界也随之发生改变。后来，许多人在这方面进行了大量研究，并取得了一些进展。1.1.2 国内外虚拟现实技术的研究状况在虚拟现实领域，国内外专家和学者已经做出了许多研究工作。国外研究状况：1）美国的研究状况美国是虚拟现实技术的发源地。其水平基本上就代表国际发展的水平。目前美国在该领域的基础研究主要集中在感知、用户界面、后台软件和硬件四个方面。2）日本的研究状况在当前实用虚拟现实技术的研究与开发中,日本是居于领先位置的国家之一，主要致力于建立大规模虚拟现实知识库的研究。另外在虚拟现实的游戏方面的研究也做了很多工作。NEC公司计算机和通信分部中的系统研究实验室开发了一种虚拟现实系统，它能让操作者都使用“代用手”去处理三维CAD中的形体模型，该系统通过VPL公司的数据手套把对模型的处理与操作者手的运动联系起来。东京大学的广濑研究室重点研究虚拟现实的可视化问题。为了克服当前显示和交互作用技术的局限性，他们正在开发一种虚拟全息系统。富士通实验室有限公司正在研究的一个项目是虚拟生物与虚拟现实环境的相互作用。他们还在研究虚拟现实中的手势识别，已经开发了一套神经网络姿势识别系统，该系统可以识别姿势，也可以识别表示词的信号语言。3）英国的研究与开发在VR开发的某些方面，特别是在分布并行处理、辅助设备 （包括触觉反馈）设计和应用研究方面，英国在欧洲是领先的。国内研究状况：和一些发达国家相比，我国虚拟现实技术还有一定的差距，但是一些国内大学都也做出很多研究。1) 北京航空航天大学首先进行了一些基础知识方面的研究，并着重研究了虚拟环境中物体物理特性的表示与处理；在虚拟现实中的视觉接口方面开发出了部分硬件，并提出了有关算法及实现方法等。 2) 浙江大学CAD&CG国家重点实验室开发出了一套桌面型虚拟建筑环境实时漫游系统。另外，他们还研制出了在虚拟环境中一种新的快速漫游算法和一种递进网格的快速生成算法。3) 哈尔滨工业大学计算机系已成功地虚拟出了人的高级行为中特定人脸图像的合成，表情的合成和唇动的合成等技术问题，并正在研究人说话时头势和手势动作等。4) 清华大学对虚拟现实的临场感的方面进行了研究，他们还针对室内环境水平特征丰富的特点，提出借助图像变换，使立体视觉图像中对应水平特征呈现形状一致性，以利于实现特征匹配，并获取物体三维结构的新颖算法。5) 西安交通大学对虚拟现实中的关键技术，立体显示技术进行了研究。他们在借鉴人类视觉特性的基础上提出了一种基于JPEG标准压缩编码新方案，并获得了较高的压缩比、信噪比以及解压速度。1.2碰撞检测的研究现状1.2.1意义及特点目前，虚拟现实真实性的研究大量集中在视觉、听觉和触觉等几个方面。例如采用几何建模方法来表示虚拟环境中的实体，然后使用纹理映射、消隐和光照计算等方法生成逼真的环境。虚拟现实只有逼真的外观是不够的，还需要有逼真的状态变化，例如，实体位置、方向和形状等状态变化规律与真实世界中相同或相似，即虚拟现实中的实体需要具有运动逼真性。碰撞检测和响应是虚拟现实中的一项重要技术，是其基本特性之一“沉浸感”的重要保证。碰撞检测的两个重要约束条件是实时性和精确性2。就实时性而言，针对虚拟环境中的视觉显示要求，碰撞检测的速度至少要达到24Hz;而针对虚拟环境中的触觉显示要求，碰撞检测的速度至少要达到300Hz才能维持触觉交互系统的稳定性，要达到1000Hz才能获得平滑的效果。精确性取决于具体的应用，比如对于环境漫游系统，一般只要近似模拟碰撞检测情况，此时，若两个物体实际没有发生碰撞但其距离比较近（如在某一阈值内），就可以将其当作是发生了碰撞，并粗略计算碰撞位置。而对于虚拟手术仿真、虚拟装配等应用，就要精确地检测碰撞的发生和计算碰撞发生的位置。1.2.2碰撞检测的研究现状3碰撞检测最早被广泛用于生产中的自动操作和处理，即虚拟组装和拆卸。近年来，碰撞检测和响应的研究在虚拟现实中扮演了越来越重要的角色，特别是用碰撞检测和响应来模拟现实生活中的接触、抓、移动和打击等情况。下面我们将对于碰撞检测的研究状况进行简单介绍。对于碰撞检测和响应的研究主要集中在对实体间精确碰撞检测算法和碰撞响应的处理。目前已经形成了一些比较成熟的算法。虚拟现实中检测两个实体之间是否发生了碰撞，实际上就是检测这两个实体所占的几何空间是否相交，常用的方法有离散方法和连续方法。离散方法（Discrete Methods）也称为静态方法（Static Methods）,是指当检测时间（Ts,Te）内是否发生碰撞，则仅在Ts<Ts+t1<Ts+t2<<Ts+tk<Te一系列离散的时间点上进行碰撞检测。Moore,M.和Wilhelms,J.提出了两种基于实体模型点、边和面几何关系的碰撞检测方法。一种方法直接计算两个实体顶点、边和面之间的关系，另一种方法是使用点积来判断一个点是否进入另一个实体内部。M.K.Ponamgi,D.Manocha,Ming C.Lin等人提出了一种基于Voronoi区域的碰撞检测方法。这种方法利用虚拟环境中实体运动的一致性，即实体运动状态的变化在dt时间内是有限的，大大减少了检测两个凸多面体是否碰撞的时间，取得了实时碰撞检测的突破性进展。连续方法（Continuum Methods）也称为动态方法（Dynamic Methods）,是指检测当前实体从当前状态运动到下一状态所滑过的四维空间与其它实体同时滑过的四维空间是否发生重叠。T.Duff的区间分析（Interval Analysis）方法就是一种连续碰撞检测方法。由于连续方法比较复杂，计算量比较大，所以绝大多数虚拟现实系统采用离散的碰撞检测方法。当检测到虚拟环境中发生碰撞时，需要根据碰撞情况修改发生碰撞实体的运动表示，即修改实体的运动方程，确定实体的损坏和形变，实现碰撞对实体的影响，这就是碰撞响应。在虚拟现实研究初期，对碰撞响应的要求比较简单。例如，在虚拟漫游系统碰撞检测只是当检测到碰撞时禁止该方向的运动。现在对碰撞响应的研究越来越多。目前对碰撞响应的研究主要有两个方向，一类是研究针对虚拟实体物理特性的碰撞响应，即碰撞对实体的运动行为和本身特性的影响。例如美国联邦铁路部（FRA）对防撞性评估系统的研究，主要分为三步：第一步是对单节机动有轨车辆碰撞物理特性的定义；第二步是机动有轨车辆碰撞动力学模型的建立；第三步是计算碰撞结果，评估两铁路系统的防撞性。另一类着重于研究碰撞响应的图形效果，即碰撞后实体损伤的图形表示和一些烟火等特殊效果。在STOW97的联合演练中，已经完成了炮弹爆炸后所产生的弹坑，道路、桥梁及建筑物不同程度的损坏，车辙和一些明显痕迹的图形效果。关于平面碰撞检测问题的研究主要有3个方面，包括可碰撞、可移动区域和最初碰撞部位的检测。近10几年来，许多专家学者对平面碰撞问题进行了深入的研究，并取得一些很好的结果，提出了许多算法。Tetsuya，Toshiaki和Mario等人提出了一种称为空间占有的方法，即物体在目标空间移动，当试图占有相同的球体时来检测它们的碰撞21。这种算法基于这样一条原理：没有任何物体和其他物体占有同一个球体，也不需要特殊的计算来检测碰撞。并且，在它们的方法中，每个物体连同它们所占有的球体在3D空间中都被赋予一个名字，因而其他物体知道它们和哪个物体发生碰撞。Chin及Wang研究了两个多边形的相交和最小距离问题。利用可视边链和凸的顶点相对于其内部点的单调性，提出了判别凸n-边形和一个简单非凸m-边形的相交问题的最优算法22，并且研究了当两个多边形相交时一个多边形是否被另一个多边形完全包含的问题，其时间复杂度都为O(m+n)。David Baraff研究了平面内多个凸多边形的碰撞问题，并采用将凹多边形分解为凸多边形的方法来求解碰撞问题，其实质还是凸多边形的碰撞问题23。关于三维空间碰撞问题的研究一般有可碰撞和碰撞规避两方面。所谓可碰撞问题就是物体A和B在空间沿给定轨迹移动时是否发生碰撞。可移动区域就是物体A沿给定的规律运动，而不与物体B发生碰撞的所有可能运动的区域。最初碰撞点的检测就是当物体A以给定的运动规律运动，并将与物体B发生碰撞时，检测它们在最初发生碰撞时的接触部位。碰撞规避就是两个或多个物体的无碰撞运动。从对平面碰撞检测问题的研究中，可得到有力和巧妙的技巧。而对于空间（3D）的情形，则潜藏着难以克服的困难，这也许是平面碰撞问题已得到很深入的研究，并提出了很多种最优算法，而对于空间问题尚少有高效算法的一个原因吧。很多学科都对研究和模拟三维物体的干涉问题感兴趣。物体的干涉是两个或多个物体的体积占有相同的空间。通常，物体的干涉有两大类，即静态干涉和动态碰撞检测。动态碰撞检测就是沿特定轨迹移动的物体的干涉检测。动态碰撞检测算法又可分为两大类：判断移动的物体之间是否发生碰撞亦即可碰撞问题；检测到碰撞的存在并采取措施进行规避，也就是碰撞规避问题。静态干涉检测算法根据所用实体表示模型的不同，现有实体干涉检验算法大致可分成两类。一类算法主要基于B-rep模型。在这方面，Ganter提出空间分割技术24。另一类算法是以层次模型为基础的，如八叉树干涉检验算法和层次Sphere检验算法25 2627。动态碰撞检测可应用两类技术，第1类技术是一种基于在给定轨迹上反复利用静态干涉检测被称为“单步检测”的方法，第2类技术是基于产生称之为“扫描实体”的物体。对于这两类技术的研究许多研究者都提出自己的算法aruyama提出了一种递归空间分割算法和一种一般的面对面相交算法。然而，Boyse提出了第1种可用的单步检测系统28 Ganter及Isarankura发展了单步检测方法，提出了一种空间分割技术的方法。Hahn采用层次包围盒技术来加速多面体场景的碰撞检测。Moore与Wilhelems根据Cyrus-Beck裁剪算法提出了一种凸多面体碰撞检测算法，即通过检测多面体顶点是否相互包含来判定它们是否发生碰撞。对于具有n个凸多面体、每个多面体有m个顶点的问题，此算法的时间复杂度为O(n2m2)；对于凹多面体则分解为多个凸多面体来处理。Ganter和Isara nkura提出了一种空间分割的方法，即将给定物体所占有的空间划分成一系列子空间，将碰撞测试限定在两物体的重叠子空间中进行，并且在重叠子空间里的元素都按最大、最小来排序，从而进一步减少了测试时间。最坏情况下的处理时间为O(*N2/2)，*N 是重叠区域的单元面的总个数。1.3论文的工作和组织结构碰撞检测是虚拟现实中的关键技术，能够增强虚拟环境的真实感和用户的沉浸感，并在计算机动画、物理仿真、计算几何、机器人学、CAD/CAM等领域有广泛的应用。因此对碰撞检测技术的研究具有十分重要的意义。本论文的整体框架如下：第一章， 简要介绍了虚拟现实技术的发展及现状，然后主要介绍了研究碰撞检测技术的意义，最后介绍了碰撞检测技术在国内外研究发展与现状。第二章， 介绍碰撞检测的一些基本理论。为了进一步深入研究碰撞检测技术，首先第三章， 有必要了解一些相关基础理论。在本章中主要介绍了碰撞的定义、碰撞检测的模型类别、碰撞检测的场景特征及其碰撞检测技术的基本原理。第四章， 着重介绍了常用的一些碰撞检测算法。分别介绍了空间剖分法、包围盒层次树法、基于特征的距离计算增量算法等算法原理和优缺点。第五章， 介绍了OpenGL编程基础和面向对象编程。主要针对即将用到一些知识进行简介。主要介绍了OpenGL基本特点、OpenGL实现、OpenGL图形绘制、OpenGL光照模型、OpenGL纹理贴图等知识和介绍了面向对象编程的特点、OpenGL编程环境设置。第六章， 介绍碰撞检测算法的应用。采用OBB包围盒层次树算法实现一个碰撞检测场景。本章中简要介绍了场景实现步骤，并用流程图清晰展示了碰撞检测的实现过程。然后分析本实例程序实现的优缺点。第七章， 总结了本论文的主要工作内容，并提出了下一步工作的目标。第二章 碰撞检测理论2.1碰撞的定义3在现实世界中，碰撞是一种常见的动力学现象。其特点是整个过程时间短暂，一般在10-2秒以内，并在碰撞实体之间产生相当大的冲击力，使实体发生形变，并在一定程度上改变实体的运动状态。在虚拟现实系统中一般通过检测两个实体所占的几何空间是否相交来判断是否发生碰撞。在现实世界中，每个实体都占有一定几何空间，而且不可能出现两个实体相互穿透的现象。当虚拟现实系统中两个实体所占有的几何空间试图相互穿透时，系统就认为这两个实体发生了碰撞。如果有四维空间来描述运动实体，前三维是通常意义上的三维空间，第四维是时间，那末一个实体就可以用四维空间中的点集来描述，即：其中：S是构成实体的三维空间点集，L(t)是确定实体t时刻空间位置的函数。通过L(t)(S)可以给出三维空间点集中每个点t时刻的位置。假设用四维空间中的点集S1*和S2 *来描述两个实体S1和S2以及它们的运动，则碰撞检测可以描述为在某时刻某两个实体所占空间位置的关系，即：对于,有 S1*和 S2*，当且仅当S1* S2* 时，发生碰撞。2.2碰撞检测的模型类别虚拟环境中的物体所用的模型大体分为面模型和体模型两大类。面模型用物体的边界来表示物体，而不包括物体内部信息。体模型采用体元来表示物体，可描述物体的内部信息。体模型所耗存储量大，计算量也大。而面模型的研究和应用比体模型的成熟多。由于凸多面体有很好的性质，因而可以获得较高效率的基于凸多面体的碰撞检测算法。对于一般的体，由于处理相对比较复杂，往往采用将一般的体分解成几个凸多面体再进行逐个碰撞检测。所以碰撞检测的研究工作大多是基于面模型的，少数是基于体模型的。面模型又可进一步分为很多种，如多面体模型、CSG、隐式曲面、参数化曲面等。其中，最常用的一种是多面体模型，特别是三角形模型。多面体模型是一种简洁，通用的表示方法，几乎应用于表示任何形状的物体，而且便于操作，易于实现硬件加速。多面体模型又有多种形式，碰撞检测算法也可能对模型的形式有要求，如很多算法要求输入模型是实体，即可表示成闭合曲面，其中，不少算法利用物体的凸性来加速，因而进一步要求输入模型是凸多面体，对非凸多面体则做特殊处理；另一些算法对输入模型则不做特殊处理要求，输入模型被表示成一组无拓扑约束的三角片，这类算法通用性比较好。本论文输入模型便是一组无拓扑约束的三角片。2.3碰撞检测的场景特征2场景可按物体的运动状态分为静态部分和动态部分，静态部分间的碰撞检测可离线计算，而动态部分如果事先能知道物体的运动轨迹，其碰撞检测可离线计算。但是虚拟环境是一个实时交互系统，物体的运动轨迹一般是未知的，故碰撞检测要实时地进行。在虚拟环境中有些物体是静态的，有些物体是动态的，动态物体越多，碰撞发生的概率越大，其碰撞检测的复杂程度越高。场景中的运动物体还可分为刚体和柔体，刚体物体在运动中不改变物体形状，其运动形式局限于平移和旋转；柔体物体在运动中会改变物体的形状，其运动形式除了平移、旋转还有变形，如心脏的跳动。故柔体物体的碰撞检测比刚体要复杂得多。在本论文中我们只针对刚体物体进行碰撞检测。2.4碰撞检测技术的基本原理如果两个安全封闭的多面体发生相互碰撞时，其中一个多面体至少会有一个面与另一个多面体的至少一个面发生相交。若能在碰撞发生时，立刻检测到相交，然后将两个物体的位置稍做调整，可消除碰撞现象。如下是碰撞检测基本算法描述：设在一虚拟环境中要仿真n个物体：A1,A2,An,其对物体的仿真过程是逐帧计算的，从T0到T1按时间步长dT进行计算。/在虚拟环境中调用碰撞检测过程2Simulation()for (T=T0 to T1,步长为dT)do 获得用户的输入；更新A1,A2,An各物体的行为；if (collisionDetect(T,A1,A2,An找到了碰撞) then 计算碰撞反应；绘制n个物体A1,A2,An/碰撞检测过程，Tprev为全局变量，初值为（T0-dT）,dt为碰撞检测的步长，collisionDetect（Tcurr, A1,A2,An）for (t=Tprev to Tcurr,步长为dt)do for (A1,A2,An中每个物体Ai)do 移动Ai到其在时间t的位置;for(A1,A2,An中每个物体Ai)do for(Ai+1,An中每个物体Oj)doif (Oi与Oj相交) then 报告在时间t发生了碰撞；Tprev = Tcurr；以上是碰撞检测思想的一种最基本的方法，在实际应用过程中可以根据需要对该方法进一步改进，以得到更高效的碰撞检测算法。第三章 碰撞检测算法由于碰撞检测的重要应用，人们对它进行了广泛而深入的研究，算法种类也很多。在很多时候，对碰撞检测实时性要求很强，需要碰撞检测的几何模型集合中模型复杂且很多，在这种情况下，一般是针对虚拟场景的特点、几何模型的几何与运动等特点设计可高效应用于该虚拟场景的算法，如有些算法适用于凸多面体几何模型、有些适用于可运动模型少的虚拟场景。然而还没有能够满足所有情况的通用碰撞检测算法。3.1空间剖分法空间剖分法通常将空间剖分成均匀的单元，每个物体对应一个或多个单元中，只有当物体处于同一单元空间中才可能相交，这时应该对该单元空间进行精确的碰撞检测。采用空间剖分思想19的算法一般用树的方式逐步分割空间，可以进一步加速碰撞检测。常用的空间剖分方法是BSP4、八叉树5（如图3-1）、均匀网格6、3-d树7。八叉树用树的结构表示空间的分解情况，根是整个空间，将每个父结点空间用三个分别与坐标轴垂直的分割面分成大小相等的八份，每一份作为它的一个子结点，分割不断进行直到与子结点相交的三角形数目小于一个阈值或者与子结点相交的三角形属于同一模型，该子结点成为一个叶结点；如果来自两个模型的三角形与同一个叶结点相交，那末需要对这两个模型进行碰撞检测。BSP树与八叉树相似，但是二叉树。3-d树是一种特殊的BSPs树，用来分割空间的分割面都是与某一个坐标轴垂直的。一般，空间剖分算法在每次碰撞检测时都需要确定每个模型占有的空间单元，如果场景中不可动的模型很多，可以预先划分好空间单元并计算出每个模型占有的空间单元，当有模型运动时，只要重新计算运动模型占有的空间单元就可以。所以空间剖分算法比较适合用于稀疏的环境中分布比较均匀的几何对象间的碰撞检测，如图3-2。图3-1 八叉树图3-2 空间剖分法在场景中的应用3.2包围盒层次树法另一种常用方法是包围盒，包围盒方法被广泛应用于对光线跟踪和求交运算的加速。其基本思路是用体积略大而几何特性简单的包围盒将复杂的几何形体围住，当对两个物体做碰撞检测时，首先检测包围盒是否相交，若不相交，则两个物体不相交。反之，需要进一步对两个物体进行精确检测，此方法可以快速排除不相交的物体，加速了算法。与一个物体相对应的层次树的结点是空间上包围该物体一部分几何结构的几何近似体：层次树的根结点是包围了整个物体，每个父结点包围的几何结构是它所有子结点包围的几何结构之和；结点从上到下逐渐逼近它包围的几何结构。判断两个模型是否相交时，首先判断两个层次树的根结点是否相交；如果两个父结点相交，那末将它们的子结点分别进行相交判断；如果最后有相交的叶结点对，判断每对叶结点包围的几何结构是否相交，如果有相交的几何结构对，则模型相交，反之不相交。比较典型的包围盒类型有包围球（spheres）8 、沿坐标轴的包围盒AABB（axis aligned bounding box）9、方向包围盒OBB(oriented bounding box)等。层次包围盒法则应用于复杂环境中的碰撞检测。3.2.1包围盒形状的设计准则选择哪种形状的包围盒通常取决于应用领域及其蕴含的不同约束条件。例如在光线跟踪算法中，包围盒应能紧密包围物体，同时又便于高效地对一条光线和包围盒做求交测试。对于碰撞检测算法，可借助一个耗费函数来分析2其中：是碰撞检测的总耗费；是参与重叠测试的包围盒的对数，是一对包围盒做重叠测试的耗费；是参与求交测试的几何元的对数，是一对几何元做求交测试的耗费；是物体运动后包围盒层次需要修改的结点个数，是修改一个结点的耗费；根据这一耗费函数，可以推测理想的包围盒应满足如下要求：l 在各层次上紧凑地逼近输入模型及其子部分，以减少、；l 支持快速为一对包围盒做重叠测试，以减少；l 当物体旋转或平移时，支持对其包围盒层次中结点的快速修改，以减少3.2.2包围盒类型从上节知道选择不同类型的包围盒直接影响到碰撞检测算法的效率。本节将详细介绍一些常用的包围盒类型20，并分析各自的优缺点。1） 沿坐标轴的包围盒AABB（axis aligned bounding boxes）AABB在碰撞检测的研究历史中使用最悠久，一个AABB被定义为包含该对象且边平行于坐标轴的最小正六面体。如图3-3所示，基于AABB碰撞检测系统的有I-collide10、SOLID11等。AABB间的相交测试比较简单，两个AABB相交当且仅当在三个坐标轴投影区间均重叠。但是AABB紧密性比较差，尤其是对于沿斜对角线放置的瘦长物体，用AABB将留下很大边角空隙，从而导致大量冗余的包围盒相交测试。这样的话，减少、，同时可能增加。 图3-3 AABB包围盒2） 包围球（spheres）包围球类似AABB,是一种简单性好紧凑性差的一类包围盒，包围球被定义为包含该对象的最小球体。如图3-4所示图3-4 包围球包围盒包围球间的相交测试也相对比较简单。对于两个包围球(1,1)和(2,2),如果球心距离小于半径之和,即|1-2| （1+2）,则两包围球相交,可进一步简化为判断(1-2)·(1-2) (1+2)2。故包围球间的相交测试需要4次加减运算、4次乘法运算和1次比较运算。包围球的紧密性在所有包围盒类型中是比较差的,它除了对在三个坐标轴上分布的比较均匀的几何体外,几乎都会留下很大的空隙,通常需要花费大量的预处理时间以构造一个好的层次结构逼近对象,这在Hubbard的工作中得到验证。相对于AABB而言,在大多数情况下包围球无论是紧密性还是简单性都有所不如,因此,它是使用得比较少的一种包围盒。当对象发生旋转运动时,包围球不需要做任何更新,这是包围球比较优秀的一个特性,当几何对象进行频繁的旋转运动时,采用包围球可能得到较好的结果。当对象发生变形时,很难从子结点的包围球合成父结点的包围球,只能重新计算。3） 方向包围盒OBB(oriented bounding box)OBB是Gottschalk在1996年实现的RAPID系统中首先使用的13,当时该系统声称是最快的碰撞检测系统,曾一度作为评价碰撞检测算法的标准。一个给定对象的OBB被定义为包含该对象且相对于坐标轴方向任意的最小的正六面体。OBB最大特点是它的方向的任意性,这使得它可以根据被包围对象的形状特点尽可能紧密地包围对象(如图3-5),但同时也使得它的相交测试变得复杂。 图3-5 OBB方向包围盒OBB的计算相对复杂一些,其关键是寻找最佳方向,并确定在该方向上包围对象的包围盒的最小尺寸。OBB间的相交测试基于分离轴理论。若两个OBB在一条轴线上(不一定是坐标轴)上的投影不重叠,则这条轴称为分离轴。若一对OBB间存在一条分离轴,则可以判定这两个OBB不相交。对任何两个不相交的凸三维多面体,其分离轴要么与任一多面体的某一个面垂直,要么同时垂直于每个多面体的某一条边。因此,对一对OBB,只需测试15条可能是分离轴的轴(每个OBB的3个面方向再加上每个OBB的3个边方面的两两组合),只要找到一条这样的分离轴,就可以判定这两个OBB是不相交的,如果这15条轴都不能将这两个OBB分离,则它们是相交的。两个OBB的相交测试最多需要15次比较运算、60次加减运算、81次乘法运算和24次绝对值运算。尽管OBB间相交测试的代价比较大,但它的紧密性是最好的,可以成倍地减少参与相交测试的包围盒的数目和基本几何元素的数目,在大多数情况下其总体性能要优于AABB和包围球。此外,当几何对象发生旋转运动后,只要对OBB的基底进行同样的旋转即可。因此,对于刚体间的碰撞检测, OBB不失为一种较好的选择,但迄今为止,还没有一种有效的方法解决对象变形后OBB树的更新问题,而重新计算每个结点的OBB的代价又太大,故而OBB不适用于软体对象环境中的碰撞检测。OBB算法采用任意方向的包围盒作为物体及子部分的包围盒，组成OBB树。该算法的主要特点是采用了一个“分离轴”方法来检测两个包围盒是否相交，此方法大大加速了包围盒测试过程，从而从整体上加速了算法。此外，该算法力图使包围盒与物体很紧凑，以提高包围盒的检测命中效率。为一个物体创建OBB树的过程可分为两部分：1)为表示该物体的多边形集合计算一个OBB包围盒首先将所有多于三条边的多边形分割成三角片，即把物体表面三角化。然后采用一阶和二阶方法对构成物体的所有三角形的所有三角片的顶点进行统计，分别求得均值U、协方差矩阵C。设第i个三角片的顶点是pi,qi,ri,则有其中n是三角片个数，=-，=-，=-C是一个对称矩阵，而对称矩阵的特征根是正交的。将C的3个特征根归一化，作为一个基。沿基的每个轴向，找到轴向的极点顶点，根据各轴向上的这些极点顶点来规定OBB的大小，将基的轴向作为OBB的方向，使OBB包围各轴向上的极点顶点。因此3个特征向量中有两个分别表示最大和最小的方差方向，这样构造出来包围盒与物体比较紧凑。2)将OBB组成树状结构创建包围盒层次结构的方法通常有两种：自底向上和自顶向下。自底向上方法首先为组成物体的每个多边形分别计算包围盒，然后将它们逐渐合并成更大的包围盒，直到构成一棵树；自顶向下方法首先为整个物体计算包围盒，然后递归地对物体进行剖分，直到所有叶结点不可再分。3.3 基于特征的距离计算增量算法3.3.1基本概念在实体和几何建模中，主要有两种表达方案：边界表达模型（B-rep）和构造实体几何模型（CSG）。边界表达：通过描述实体的表面来表达实体，这样我们关于物体内、外部的全部信息。这样表达提供了两类信息：（1）几何信息用来描述面、边、顶点的参数；（2）拓扑信息顶点、边、面的邻近和连接关系。构造实体几何模型：它用一个体素的布尔运算表达式来表达实体。CSG操作运算包括旋转、平移、正规化并、正规化差和正规化交。CSG的标准体素是球、圆柱、圆锥、平行六面体、三角棱柱及圆环。为了产生一个体素，需要指定这些体素的尺寸（比如长方体的高、宽和长）。每个物体都有与之相关联的局部坐标系。通过基本CSG操作运算，相对整体世界坐标系放置各物体，就可以表达物体的空间位置。Voronoi图14Voronoi图在求解点集或其他几何对象与距离有关问题都起着很重要的作用。图3-6设、是平面上两点，L是线段的垂直平分线，L将平面分成两部分、，位于内的点具有特性：d(,)<d(,),其中d(,)表示与之间的欧几里德距离，i=1,2。这意味着，位于内的点与平面其他点更接近点，也就是说，内的点是比平面上其他点更接近于点的轨迹，即为V(),如图图3-6示。如果用H(,)表示半平面，而= H(,)，则有V()=H(,)，V()=H(,)。给定平面上n个点的点集S,S= 。定义V()=，即表示比其他点更接近点的轨迹是n-1个半平面的交，它是一个不多于n-1条边的凸多边形域，称为关联于的Voronoi多边形33。图3-7中表示关联于的Voronoi多边形，它是一个四边形