《虚拟现实中的碰撞检测技术word文档格式6049402.docx》由会员分享，可在线阅读，更多相关《虚拟现实中的碰撞检测技术word文档格式6049402.docx（85页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、碰撞检测技术的研究摘 要实时精确的碰撞撞检测对于提高虚拟环环境的真实性性、增强虚拟拟环境的沉浸浸感有着至关关重要的作用用。 该文对碰撞检测测相关技术进进行了深入的的研究,主要要包括以下几几个方面的内内容：首先介绍了虚虚拟现实技术术的发展及现现状、碰撞检检测的研究现现状；然后简简单介绍了碰碰撞检测一些些基础理论知知识，着重介绍常常用的碰撞检检测算法。紧紧接着，简单单介绍了OppenGL编编程的基础知知识和面向对对象编程的特特点。在碰撞撞检测算法的的应用中，运运用OBB包围盒盒层次树的碰撞检测测算法，提出了一种一一般多面体间间碰撞检测的的可行性方案，并用软软件对该方案案进行实现，同同时指出该方方案
2、的优缺点点。最后,对对全文进行了了总结,并指指出今后的研究方向。关键词：虚拟现现实 碰撞检测 包围盒层次树 OBBSTUDY AAND IMMPLEMEENTATIION ONN COLLLISIONNDETECTIION TEECNOLOOGY OFF VIRTTUAL RREALITTYAbstracctReal-tiime annd acccuratee colllisionn detectioon is very imporrtant to immprovee reallity aand ennhance illuusion of immmersiion foor virrtual e
3、nvirronmennt.This paaper sstudiees thee techhniquee of ccollission ddetecttion ddeeplyy.It ccontaiins thhe folllowinng parrts:Firstlyy,thiss papeer revviews recennt ressearchh on coollisiion deetectiion fiield.TThen iit inttroducces soome baasic kknowleedge aand emmphasiizes oon inttroducce of colli
4、ision detectiion allgoritthm.Neext,itt intrroducees OpeenGL aand Orrienteed-objject llanguaage prrogramm charracterr.In ccollission ddetectioon impplemenntatioon chaptter,a schemme of colliision detecction betweeen geenerall polyyhedroon is preseented by ussing bboundiing hiierarcchy voolume algorri
5、thm.The mmethodd is iimplemmentedd by vvc6.0.And iit anaalysess advaantagee and disaddvantaage off the methood.Finnally,the cconcluusion is drrawn aand thhe worrk of futurre ressearchh is ppresennted.KEY WORRDS: virttual rrealitty coollisiion deetectiion bboundiing hiierarcchy voolume OBB 目 录第一章绪 论论
6、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 LL
7、in-Caanny算法法概述193.3.3适应应性准则20第四章 编程基基础理论254.1 OpeenGL编程程基础254.1.1 OOpenGLL基本特点254.1.2 OOpenGLL实现274.1.3 OOpenGLL图形绘制284.1.4 OOpenGLL光照处理294.1.5 OOpenGLL纹理映射304.1.6深度度测试324.2面向对象象的编程324.3 OpeenGL编程程环境的设置置33第五章 碰撞检检测算法的应应用355. 1物体建建模355. 2场景绘绘制385.3碰撞检测测算法的应用用415.3. 1 基础理论415.3.2 碰碰撞检测的实实现过程435.3.4用户户
8、交互505.4本程序的的优缺点52第六章 总结与与展望54主要参考文献55第一章 绪 论1.1虚拟现实实技术发展及及现状1.1.1 虚虚拟现实的特特点自20世纪900年代初以来来，虚拟现实实技术一直是是信息领域研研究、开发和和应用的热点点方向之一。虚虚拟现实（VVirtuaal Reaality）,也称为“人人工现实”或或“临境”技技术，是多媒媒体发展的更更高境界，虚虚拟现实以更更加高级的集集成化和交互互性，给用户户以更加逼真真的体验，可可广泛应用在在模拟训练、科科学可视化等等领域，将是是今后十分活活跃的技术课课题。虚拟现实就是用用计算机技术术生成一个逼逼真的，集听听、视、触及及嗅觉为一体体的
9、感觉世界界，用户以人人的自然技能能与虚拟现实实交互考察，包包含三层意思思：11) 虚拟实体是用计计算机来生成成的一个逼真真的实体，“逼逼真”就是要要达到三维视视觉，甚至其他三维感觉觉。2) 用户可以通过人人的自然技能能（如头和眼眼的转动、手手势等其他身身体动作）与与环境交互。3) 虚拟现实往往要要借助于一些些三维传感设设备来完成交交互动作，如如头盔立体显显示、数据手套、数据服装装、三维鼠标标等。虚拟现实是一种种高度集成技技术，是计算算机、机器人人、人工智能能以及心理学学等发展的联联合结晶，因因此取决于三三维实时图像像显示、三维维定位跟踪传传感技术、人人工智能技术术、高速并行行计算机技术术及人的
10、行为为学等领域的的研究进展。因因此虚拟现实实技术的研究究和实现难度度很高，美国国著名图形学学专家J.FFoley讲讲过：“虚拟拟现实是人机机接口设计中中最后一个堡堡垒，也是最最有意义的领领域。”虚拟现实的基本本特征可以概概括为三个“II”,即Immmersiion-Innteracction-Imagiinatioon(沉浸-交互-构思思)。它强调调了人在信息息处理过程中中的主导作用用，使信息处处理从以计算算机为中心转转到以人为中中心。虚拟现实这一概概念起源于IIvan SSutherrland在在1965年年发表的一篇篇题为“Thhe Ulttimatee Dispplay”的的报告。在该该
11、报告中提出出利用计算机机系统构造一一个具有视觉觉、听觉和感感觉真实感的的世界。19968年，IIvan SSutherrland开开发了第一个个可以跟踪头头部运动的头头盔显示器（hhead-MMounteed Dissplay,简称HMDD）。HMDD根据用户在在虚拟世界的的位置来显示示相应的内容容，当用户移移动或转动头头部时，通过过HMD所看看到的虚拟世世界也随之发发生改变。后后来，许多人人在这方面进进行了大量研研究，并取得得了一些进展展。1.1.2 国国内外虚拟现现实技术的研研究状况在虚拟现实领领域，国内外外专家和学者者已经做出了了许多研究工工作。国外研究状况：1）美国的研究究状况美国是虚
12、拟现实实技术的发源源地。其水平平基本上就代代表国际发展展的水平。目目前美国在该该领域的基础础研究主要集集中在感知、用用户界面、后后台软件和硬硬件四个方面面。2）日本的研究究状况在当前实用虚拟拟现实技术的的研究与开发发中,日本是是居于领先位位置的国家之之一，主要致致力于建立大大规模虚拟现现实知识库的的研究。另外外在虚拟现实实的游戏方面面的研究也做做了很多工作作。NEC公司计算算机和通信分分部中的系统统研究实验室室开发了一种种虚拟现实系系统，它能让让操作者都使使用“代用手手”去处理三三维CAD中中的形体模型型，该系统通通过VPL公公司的数据手手套把对模型型的处理与操操作者手的运运动联系起来来。东京
13、大学的广濑濑研究室重点点研究虚拟现现实的可视化化问题。为了了克服当前显显示和交互作作用技术的局局限性，他们们正在开发一一种虚拟全息息系统。富士通实验室有有限公司正在在研究的一个个项目是虚拟拟生物与虚拟拟现实环境的的相互作用。他他们还在研究究虚拟现实中中的手势识别别，已经开发发了一套神经经网络姿势识识别系统，该该系统可以识识别姿势，也也可以识别表表示词的信号号语言。3）英国的研究究与开发在VR开发的某某些方面，特特别是在分布布并行处理、辅辅助设备 （包包括触觉反馈馈）设计和应应用研究方面面，英国在欧欧洲是领先的的。国内研究状况：和一些发达国家家相比，我国国虚拟现实技技术还有一定定的差距，但但是一
14、些国内内大学都也做做出很多研究究。1) 北京航空航天大大学首先进行行了一些基础础知识方面的的研究，并着着重研究了虚虚拟环境中物体物理特特性的表示与与处理；在虚虚拟现实中的的视觉接口方方面开发出了了部分硬件，并并提出了有关关算法及实现现方法等。 2) 浙江大学CADD&CG国家家重点实验室室开发出了一一套桌面型虚虚拟建筑环境境实时漫游系系统。另外，他们们还研制出了了在虚拟环境境中一种新的的快速漫游算算法和一种递递进网格的快快速生成算法法。3) 哈尔滨工业大学学计算机系已已成功地虚拟拟出了人的高高级行为中特特定人脸图像像的合成，表情的合成和唇唇动的合成等等技术问题，并并正在研究人人说话时头势势和手
15、势动作作等。4) 清华大学对虚拟拟现实的临场场感的方面进进行了研究，他他们还针对室室内环境水平平特征丰富的特点，提出出借助图像变变换，使立体体视觉图像中中对应水平特特征呈现形状状一致性，以以利于实现特特征匹配，并并获取物体三三维结构的新颖颖算法。5) 西安交通大学对对虚拟现实中中的关键技术术，立体显示示技术进行了了研究。他们们在借鉴人类视觉特性的基基础上提出了了一种基于JJPEG标准准压缩编码新新方案，并获获得了较高的的压缩比、信信噪比以及解解压速度。1.2碰撞检测测的研究现状状1.2.1意义义及特点目前，虚拟现现实真实性的的研究大量集集中在视觉、听听觉和触觉等等几个方面。例例如采用几何何建模
16、方法来来表示虚拟环环境中的实体体，然后使用用纹理映射、消消隐和光照计计算等方法生生成逼真的环环境。虚拟现现实只有逼真真的外观是不不够的，还需需要有逼真的的状态变化，例例如，实体位位置、方向和和形状等状态态变化规律与与真实世界中中相同或相似似，即虚拟现现实中的实体体需要具有运运动逼真性。碰碰撞检测和响响应是虚拟现现实中的一项项重要技术，是是其基本特性性之一“沉浸浸感”的重要要保证。碰撞检测的两个个重要约束条条件是实时性性和精确性2。就实实时性而言，针针对虚拟环境境中的视觉显显示要求，碰碰撞检测的速速度至少要达达到24Hzz;而针对虚虚拟环境中的的触觉显示要要求，碰撞检检测的速度至至少要达到330
17、0Hz才才能维持触觉觉交互系统的的稳定性，要要达到10000Hz才能能获得平滑的的效果。精确确性取决于具具体的应用，比比如对于环境境漫游系统，一一般只要近似似模拟碰撞检检测情况，此此时，若两个个物体实际没没有发生碰撞撞但其距离比比较近（如在在某一阈值内内），就可以以将其当作是是发生了碰撞撞，并粗略计算碰撞撞位置。而对对于虚拟手术术仿真、虚拟拟装配等应用用，就要精确确地检测碰撞撞的发生和计计算碰撞发生生的位置。1.2.2碰撞撞检测的研究究现状3碰撞检测最早早被广泛用于于生产中的自自动操作和处处理，即虚拟拟组装和拆卸卸。近年来，碰碰撞检测和响响应的研究在在虚拟现实中中扮演了越来来越重要的角角色，特
18、别是是用碰撞检测测和响应来模模拟现实生活活中的接触、抓抓、移动和打打击等情况。下面我们将对于碰撞检测的研究状况进行简单介绍。对于碰撞检测测和响应的研研究主要集中中在对实体间间精确碰撞检检测算法和碰碰撞响应的处处理。目前已已经形成了一一些比较成熟熟的算法。虚虚拟现实中检检测两个实体体之间是否发发生了碰撞，实实际上就是检检测这两个实实体所占的几几何空间是否否相交，常用用的方法有离离散方法和连连续方法。离离散方法（DDiscreete Meethodss）也称为静静态方法（SStaticc Methhods）,是指当检测测时间（Tss,Te）内内是否发生碰碰撞，则仅在在TsTss+t1TTs+t2T
19、ss+tkTTe一系列离离散的时间点点上进行碰撞撞检测。Mooore,MM.和Willhelmss,J.提出出了两种基于于实体模型点点、边和面几几何关系的碰碰撞检测方法法。一种方法法直接计算两两个实体顶点点、边和面之之间的关系，另另一种方法是是使用点积来来判断一个点点是否进入另另一个实体内内部。M.KK.Ponaamgi,DD.Manoocha,MMing CC.Lin等等人提出了一一种基于Vooronoii区域的碰撞撞检测方法。这这种方法利用用虚拟环境中中实体运动的的一致性，即即实体运动状状态的变化在在dt时间内内是有限的，大大大减少了检检测两个凸多多面体是否碰碰撞的时间，取取得了实时碰碰撞
20、检测的突突破性进展。连连续方法（CContinnuum MMethodds）也称为为动态方法（DDynamiic Metthods）,是指检测当当前实体从当当前状态运动动到下一状态态所滑过的四四维空间与其其它实体同时时滑过的四维维空间是否发发生重叠。TT.Dufff的区间分析析（Inteerval Analyysis）方方法就是一种种连续碰撞检检测方法。由由于连续方法法比较复杂，计计算量比较大大，所以绝大大多数虚拟现现实系统采用用离散的碰撞撞检测方法。当检测到虚拟环环境中发生碰碰撞时，需要要根据碰撞情情况修改发生生碰撞实体的的运动表示，即即修改实体的的运动方程，确确定实体的损损坏和形变，实实现
21、碰撞对实实体的影响，这这就是碰撞响响应。在虚拟拟现实研究初初期，对碰撞撞响应的要求求比较简单。例例如，在虚拟拟漫游系统碰碰撞检测只是是当检测到碰碰撞时禁止该该方向的运动动。现在对碰碰撞响应的研研究越来越多多。目前对碰碰撞响应的研研究主要有两两个方向，一一类是研究针针对虚拟实体体物理特性的的碰撞响应，即即碰撞对实体体的运动行为为和本身特性性的影响。例例如美国联邦邦铁路部（FFRA）对防防撞性评估系系统的研究，主要分为三步：第一步是对单节机动有轨车辆碰撞物理特性的定义；第二步是机动有轨车辆碰撞动力学模型的建立；第三步是计算碰撞结果，评估两铁路系统的防撞性。另一类着重于研究碰撞响应的图形效果，即碰撞
22、后实体损伤的图形表示和一些烟火等特殊效果。在STOW97的联合演练中，已经完成了炮弹爆炸后所产生的弹坑，道路、桥梁及建筑物不同程度的损坏，车辙和一些明显痕迹的图形效果。关于平面碰撞检检测问题的研研究主要有33个方面，包包括可碰撞、可可移动区域和和最初碰撞部部位的检测。近近10几年来来，许多专家家学者对平面面碰撞问题进进行了深入的的研究，并取取得一些很好好的结果，提提出了许多算算法。Tettsuya，TToshiaaki和Maario等人人提出了一种种称为空间占占有的方法，即即物体在目标标空间移动，当当试图占有相相同的球体时时来检测它们们的碰撞221。这种种算法基于这这样一条原理理：没有任何何物
23、体和其他他物体占有同同一个球体，也也不需要特殊殊的计算来检检测碰撞。并并且，在它们们的方法中，每每个物体连同同它们所占有有的球体在33D空间中都都被赋予一个个名字，因而而其他物体知知道它们和哪哪个物体发生生碰撞。Chhin及Waang研究了了两个多边形形的相交和最最小距离问题题。利用可视视边链和凸的的顶点相对于于其内部点的的单调性，提提出了判别凸凸n-边形和和一个简单非非凸m-边形形的相交问题题的最优算法法22，并并且研究了当当两个多边形形相交时一个个多边形是否否被另一个多多边形完全包包含的问题，其其时间复杂度度都为O(mm+n)。DDavid Barafff研究了平平面内多个凸凸多边形的碰碰
24、撞问题，并并采用将凹多多边形分解为为凸多边形的的方法来求解解碰撞问题，其其实质还是凸凸多边形的碰碰撞问题223。关于三维空间碰碰撞问题的研研究一般有可可碰撞和碰撞撞规避两方面面。所谓可碰碰撞问题就是是物体A和BB在空间沿给给定轨迹移动动时是否发生生碰撞。可移移动区域就是是物体A沿给给定的规律运运动，而不与与物体B发生生碰撞的所有有可能运动的的区域。最初初碰撞点的检检测就是当物物体A以给定定的运动规律律运动，并将将与物体B发发生碰撞时，检检测它们在最最初发生碰撞撞时的接触部部位。碰撞规规避就是两个个或多个物体体的无碰撞运运动。从对平平面碰撞检测测问题的研究究中，可得到到有力和巧妙妙的技巧。而而对
25、于空间（3D）的情情形，则潜藏藏着难以克服服的困难，这这也许是平面面碰撞问题已已得到很深入入的研究，并并提出了很多多种最优算法法，而对于空空间问题尚少少有高效算法法的一个原因因吧。很多学科都对研研究和模拟三三维物体的干干涉问题感兴兴趣。物体的的干涉是两个个或多个物体体的体积占有有相同的空间间。通常，物物体的干涉有有两大类，即即静态干涉和和动态碰撞检检测。动态碰碰撞检测就是是沿特定轨迹迹移动的物体体的干涉检测测。动态碰撞撞检测算法又又可分为两大大类：判断断移动的物体体之间是否发发生碰撞亦即即可碰撞问题题；检测到到碰撞的存在在并采取措施施进行规避，也也就是碰撞规规避问题。静静态干涉检测测算法根据所
26、所用实体表示示模型的不同同，现有实体体干涉检验算算法大致可分分成两类。一一类算法主要要基于B-rrep模型。在在这方面，GGanterr提出空间分分割技术224。另一类算法法是以层次模模型为基础的的，如八叉树树干涉检验算算法和层次SSpheree检验算法25 226277。动态碰碰撞检测可应应用两类技术术，第1类技技术是一种基基于在给定轨轨迹上反复利利用静态干涉涉检测被称为为“单步检测测”的方法，第第2类技术是是基于产生称称之为“扫描描实体”的物物体。对于这这两类技术的的研究许多研研究者都提出出自己的算法法aruyaama提出了了一种递归空空间分割算法法和一种一般般的面对面相相交算法。然然而，
27、Boyyse提出了了第1种可用用的单步检测测系统288 Ganteer及Isaarankuura发展了了单步检测方方法，提出了了一种空间分分割技术的方方法。Hahhn采用层次次包围盒技术术来加速多面面体场景的碰碰撞检测。MMoore与与Wilheelems根根据Cyruus-Becck裁剪算法法提出了一种种凸多面体碰碰撞检测算法法，即通过检检测多面体顶顶点是否相互互包含来判定定它们是否发发生碰撞。对对于具有n个个凸多面体、每每个多面体有有m个顶点的的问题，此算算法的时间复复杂度为O(n2m2)；对于凹多多面体则分解解为多个凸多多面体来处理理。Gantter和Issara nnkura提提出了一
28、种空空间分割的方方法，即将给给定物体所占占有的空间划划分成一系列列子空间，将将碰撞测试限限定在两物体体的重叠子空空间中进行，并并且在重叠子子空间里的元元素都按最大大、最小来排排序，从而进进一步减少了了测试时间。最最坏情况下的的处理时间为为O(*N22/2)，*N 是重叠叠区域的单元元面的总个数数。1.3论文的工工作和组织结结构碰撞检测是虚虚拟现实中的的关键技术，能能够增强虚拟拟环境的真实实感和用户的的沉浸感，并并在计算机动动画、物理仿仿真、计算几几何、机器人人学、CADD/CAM等等领域有广泛泛的应用。因因此对碰撞检检测技术的研研究具有十分分重要的意义义。本论文的整体体框架如下：第一章， 简要
29、介绍了虚拟拟现实技术的的发展及现状状，然后主要要介绍了研究究碰撞检测技技术的意义，最后后介绍了碰撞撞检测技术在在国内外研究究发展与现状状。第二章， 介绍碰撞检测的的一些基本理理论。为了进进一步深入研研究碰撞检测测技术，首先先第三章， 有必要了解一些些相关基础理理论。在本章章中主要介绍绍了碰撞的定定义、碰撞检检测的模型类类别、碰撞检检测的场景特特征及其碰撞撞检测技术的的基本原理。第四章， 着重介绍了常用用的一些碰撞撞检测算法。分分别介绍了空空间剖分法、包包围盒层次树树法、基于特特征的距离计计算增量算法法等算法原理和优缺点。第五章， 介绍了OpennGL编程基基础和面向对对象编程。主要针对即即将用
30、到一些些知识进行简简介。主要介介绍了OpeenGL基本本特点、OppenGL实实现、OpeenGL图形形绘制、OppenGL光光照模型、OOpenGLL纹理贴图等等知识和介绍绍了面向对象象编程的特点点、OpennGL编程环环境设置。第六章， 介绍碰撞检测算算法的应用。采用OBB包围盒层次树算法实现一个碰撞检测场景。本章中简要介绍了场景实现步骤，并用流程图清晰展示了碰撞检测的实现过程。然后分析本实例程序实现的优缺点。第七章， 总结了本论文的的主要工作内内容，并提出出了下一步工工作的目标。第二章 碰撞检检测理论2.1碰撞的定定义3在现实世界中中，碰撞是一一种常见的动动力学现象。其其特点是整个个过程
31、时间短短暂，一般在在10-2秒以内，并并在碰撞实体体之间产生相相当大的冲击击力，使实体体发生形变，并并在一定程度度上改变实体体的运动状态态。在虚拟现现实系统中一一般通过检测测两个实体所所占的几何空空间是否相交交来判断是否否发生碰撞。在在现实世界中中，每个实体体都占有一定定几何空间，而而且不可能出出现两个实体体相互穿透的的现象。当虚虚拟现实系统统中两个实体体所占有的几几何空间试图图相互穿透时时，系统就认认为这两个实实体发生了碰碰撞。如果有四维空空间来描述运运动实体，前前三维是通常常意义上的三三维空间，第第四维是时间间，那末一个个实体就可以以用四维空间间中的点集来来描述，即：其中：S是构构成实体的
32、三三维空间点集集，L(t)是确定实体体t时刻空间间位置的函数数。通过L(t)(S)可以给出三三维空间点集集中每个点tt时刻的位置置。假设用四四维空间中的的点集S1*和S2 *来描述两两个实体S11和S2以及及它们的运动动，则碰撞检检测可以描述述为在某时刻刻某两个实体体所占空间位位置的关系，即即：对于,有 SS1*和 S2*，当且仅当当S1* S2* 时，发生碰碰撞。2.2碰撞检测测的模型类别别虚拟环境中的物物体所用的模模型大体分为为面模型和体体模型两大类类。面模型用用物体的边界界来表示物体体，而不包括括物体内部信信息。体模型型采用体元来来表示物体，可可描述物体的的内部信息。体体模型所耗存存储量
33、大，计计算量也大。而而面模型的研研究和应用比比体模型的成成熟多。由于于凸多面体有有很好的性质质，因而可以以获得较高效效率的基于凸凸多面体的碰碰撞检测算法法。对于一般般的体，由于处理理相对比较复复杂，往往采采用将一般的的体分解成几几个凸多面体体再进行逐个个碰撞检测。所以碰撞检测的研究工作大多是基于面模型的，少数是基于体模型的。面模型又可进一一步分为很多多种，如多面面体模型、CCSG、隐式式曲面、参数数化曲面等。其其中，最常用用的一种是多多面体模型，特特别是三角形形模型。多面面体模型是一一种简洁，通通用的表示方方法，几乎应应用于表示任任何形状的物物体，而且便便于操作，易易于实现硬件件加速。多面体模
34、型又有有多种形式，碰碰撞检测算法法也可能对模模型的形式有有要求，如很很多算法要求求输入模型是是实体，即可可表示成闭合合曲面，其中中，不少算法法利用物体的的凸性来加速速，因而进一一步要求输入入模型是凸多多面体，对非非凸多面体则则做特殊处理理；另一些算算法对输入模模型则不做特特殊处理要求求，输入模型型被表示成一一组无拓扑约约束的三角片片，这类算法法通用性比较较好。本论文文输入模型便便是一组无拓拓扑约束的三三角片。2.3碰撞检测测的场景特征征2场景可按物体的的运动状态分分为静态部分分和动态部分分，静态部分分间的碰撞检检测可离线计计算，而动态态部分如果事事先能知道物物体的运动轨轨迹，其碰撞撞检测可离线
35、线计算。但是是虚拟环境是是一个实时交交互系统，物物体的运动轨轨迹一般是未未知的，故碰碰撞检测要实实时地进行。在在虚拟环境中中有些物体是是静态的，有有些物体是动动态的，动态态物体越多，碰碰撞发生的概概率越大，其其碰撞检测的的复杂程度越越高。场景中的运动物物体还可分为为刚体和柔体体，刚体物体体在运动中不不改变物体形形状，其运动动形式局限于于平移和旋转转；柔体物体体在运动中会会改变物体的的形状，其运运动形式除了了平移、旋转转还有变形，如如心脏的跳动动。故柔体物物体的碰撞检检测比刚体要要复杂得多。在在本论文中我我们只针对刚刚体物体进行行碰撞检测。2.4碰撞检测测技术的基本本原理如果两个安全封封闭的多面
36、体体发生相互碰碰撞时，其中中一个多面体体至少会有一一个面与另一一个多面体的的至少一个面面发生相交。若若能在碰撞发发生时，立刻刻检测到相交交，然后将两两个物体的位位置稍做调整整，可消除碰碰撞现象。如如下是碰撞检检测基本算法法描述：设在一虚拟环境境中要仿真nn个物体：AA1,A2,An,其对物体的的仿真过程是是逐帧计算的的，从T0到到T1按时间间步长dT进进行计算。/在虚拟环境境中调用碰撞撞检测过程2Simulattion()for (T=T0 too T1,步步长为dT)do 获得用户的输入入；更新A1,A22,An各各物体的行为为；if (colllisioonDeteect(T,A1,AA2
37、,Ann找到了碰碰撞) theen 计算碰碰撞反应；绘制n个物体AA1,A2,An/碰撞检测过过程，Tprrev为全局局变量，初值值为（T0-dT）,ddt为碰撞检检测的步长，collisiionDettect（TTcurr, A1,A2,AAn）for (t=Tprevv to TTcurr,步长为dtt)do for (AA1,A2,An中中每个物体AAi)do 移动Aii到其在时间间t的位置;for(A11,A2,An中每每个物体Aii)do for(Aii+1,AAn中每个个物体Oj)doif (Oi与与Oj相交) theen 报告在在时间t发生生了碰撞；Tprev = Tcurrr；
38、以上是碰撞检测测思想的一种种最基本的方方法，在实际际应用过程中中可以根据需需要对该方法法进一步改进进，以得到更更高效的碰撞撞检测算法。第三章 碰撞检检测算法由于碰撞检测的的重要应用，人人们对它进行行了广泛而深深入的研究，算算法种类也很很多。在很多多时候，对碰碰撞检测实时时性要求很强强，需要碰撞撞检测的几何何模型集合中中模型复杂且且很多，在这这种情况下，一一般是针对虚虚拟场景的特特点、几何模模型的几何与与运动等特点点设计可高效效应用于该虚虚拟场景的算算法，如有些些算法适用于于凸多面体几几何模型、有有些适用于可可运动模型少少的虚拟场景景。然而还没有能能够满足所有有情况的通用用碰撞检测算算法。3.1
39、空间剖分分法空间剖分法通常常将空间剖分分成均匀的单单元，每个物物体对应一个个或多个单元元中，只有当当物体处于同同一单元空间间中才可能相相交，这时应应该对该单元元空间进行精精确的碰撞检检测。采用空空间剖分思想想19的算算法一般用树树的方式逐步步分割空间，可可以进一步加加速碰撞检测测。常用的空空间剖分方法法是BSP4、八叉叉树5（如图图3-1）、均匀网格格6、3-d树7。八叉树用用树的结构表表示空间的分分解情况，根根是整个空间间，将每个父父结点空间用用三个分别与与坐标轴垂直直的分割面分分成大小相等等的八份，每每一份作为它它的一个子结结点，分割不不断进行直到到与子结点相相交的三角形形数目小于一一个阈
40、值或者者与子结点相相交的三角形形属于同一模模型，该子结结点成为一个个叶结点；如如果来自两个个模型的三角角形与同一个个叶结点相交交，那末需要要对这两个模模型进行碰撞撞检测。BSSP树与八叉叉树相似，但但是二叉树。33-d树是一一种特殊的BBSPs树，用用来分割空间间的分割面都都是与某一个个坐标轴垂直直的。一般，空空间剖分算法法在每次碰撞撞检测时都需需要确定每个个模型占有的的空间单元，如如果场景中不不可动的模型型很多，可以以预先划分好好空间单元并并计算出每个个模型占有的的空间单元，当当有模型运动动时，只要重重新计算运动动模型占有的的空间单元就就可以。所以以空间剖分算算法比较适合合用于稀疏的的环境中
41、分布布比较均匀的的几何对象间间的碰撞检测测，如图3-2。图3-1 八八叉树图3-2 空间剖分法法在场景中的的应用3.2包围盒层层次树法另一种常用方法法是包围盒，包包围盒方法被被广泛应用于于对光线跟踪和求交交运算的加速速。其基本思路路是用体积略略大而几何特特性简单的包包围盒将复杂杂的几何形体体围住，当对对两个物体做做碰撞检测时时，首先检测测包围盒是否否相交，若不不相交，则两两个物体不相相交。反之，需需要进一步对对两个物体进进行精确检测测，此方法可可以快速排除除不相交的物物体，加速了了算法。与一一个物体相对对应的层次树树的结点是空空间上包围该该物体一部分分几何结构的的几何近似体体：层次树的的根结点
42、是包包围了整个物物体，每个父父结点包围的的几何结构是是它所有子结结点包围的几几何结构之和和；结点从上上到下逐渐逼逼近它包围的的几何结构。判判断两个模型型是否相交时时，首先判断断两个层次树树的根结点是是否相交；如如果两个父结结点相交，那那末将它们的的子结点分别别进行相交判判断；如果最最后有相交的的叶结点对，判断每对对叶结点包围围的几何结构构是否相交，如如果有相交的的几何结构对对，则模型相相交，反之不不相交。比较典型的包围围盒类型有包包围球（sppheress）8 、沿坐标轴的的包围盒AAABB（axxis allignedd bounnding box）9、方向向包围盒OBBB(oriiente
43、dd bounnding box)等等。层次包围围盒法则应用用于复杂环境境中的碰撞检检测。3.2.1包围围盒形状的设设计准则选择哪种形状状的包围盒通通常取决于应应用领域及其其蕴含的不同同约束条件。例例如在光线跟踪算算法中，包围围盒应能紧密密包围物体，同同时又便于高高效地对一条条光线和包围围盒做求交测测试。对于碰碰撞检测算法法，可借助一一个耗费函数数来分析2其中：是碰撞检测的总总耗费；是参与重叠测试试的包围盒的的对数，是一一对包围盒做做重叠测试的的耗费；是参与求交测试试的几何元的的对数，是一一对几何元做做求交测试的的耗费；是物体运动后包包围盒层次需要修改改的结点个数数，是修改一个个结点的耗费费；
44、根据这一耗费费函数，可以以推测理想的的包围盒应满满足如下要求求：l 在各层次上紧凑凑地逼近输入入模型及其子子部分，以减减少、；l 支持快速为一对对包围盒做重重叠测试，以以减少；l 当物体旋转或平平移时，支持持对其包围盒盒层次中结点点的快速修改改，以减少3.2.2包围围盒类型从上节知道选选择不同类型型的包围盒直直接影响到碰碰撞检测算法法的效率。本本节将详细介介绍一些常用用的包围盒类类型20，并分析各自自的优缺点。1） 沿坐标轴的包围围盒AABBB（axiss aliggned bboundiing booxes）AABB在碰撞撞检测的研究究历史中使用用最悠久，一一个AABBB被定义为包包含该对象
45、且且边平行于坐标轴的的最小正六面面体。如图33-3所示，基基于AABBB碰撞检测系系统的有I-colliide100、SOLLID111等。AABB间的相相交测试比较较简单，两个个AABB相相交当且仅当当在三个坐标标轴投影区间间均重叠。但但是AABBB紧密性比较较差，尤其是是对于沿斜对对角线放置的的瘦长物体，用用AABB将将留下很大边边角空隙，从而导导致大量冗余余的包围盒相相交测试。这这样的话，减减少、，同时可能增加。 图3-3 AAABB包围围盒2） 包围球（sphheres）包围球类似AAABB,是一一种简单性好好紧凑性差的的一类包围盒盒，包围球被被定义为包含该对象的最最小球体。如如图3-
46、4所所示图3-4 包包围球包围盒盒包围球间的相交交测试也相对对比较简单。对对于两个包围围球(1,1)和(2,22),如果球球心距离小于于半径之和,即|1-2| （1+2）,则两包围围球相交,可可进一步简化化为判断(1-2)(1-2) (1+2)2。故包围球球间的相交测测试需要4次次加减运算、44次乘法运算算和1次比较较运算。包围球的紧密性性在所有包围围盒类型中是是比较差的,它除了对在在三个坐标轴轴上分布的比较均匀的的几何体外,几乎都会留留下很大的空空隙,通常需需要花费大量量的预处理时时间以构造一一个好的层次次结构逼近对对象,这在HHubbarrd的工作中中得到验证。相相对于AABBB而言,在在大多数情况况下包围球无无论是紧密性性还是简单性性都有所不如如,因此,它它是使用得比比较少的一种种包围盒。当当对象发生旋旋转运动时,包围球不需需要做任何更更新,这是包包围球比较优优秀的一个特特性,当几何何对象进行频频繁的旋转运运动时,采用用包围球可能能得到较好的的结果。当对对象发生变形形时,很难从从子结点的包包围球合成父父结点的包围围球,只能重重新计算。3） 方向包围盒OBBB(oriientedd bounnding box)OBB是Gotttschaalk在19996年实现的RAPPID系统中中首先使用的的13,当当时该系统声声称是最快的的碰撞检测系系统,曾