（计算机软件与理论专业论文）基于obb包围盒的碰撞检测算法改进.pdf

k - 1 4 论文的研究意义4 1 5 论文结构安排4 第2 章经典的层次包围盒方法6 2 1 包围盒的原理6 2 2 包围盒方法的分类6 2 2 1 包围球( s p h e r e ) 6 2 2 2 轴对齐包围盒( a a b ba x i s a l i g n e db o u n d i n gb o x e s ) 7 2 2 3 方向包围盒( o b b ) 8 2 2 4 离散有向多面体( k d o p s ) 9 2 3 层次包围树 2 3 1 层次包围树的度 2 3 2 层次包围树的构造 2 4 包围盒树的更新 2 5 层次包围盒方法的性能分析 2 6 各种包围盒的优缺点 第3 章o b b 层次包围盒的构造和碰撞检测 3 1o b b 的计算 3 2o b b 包围树的构造 3 2 1 构造o b b 树的过程 3 2 2o b b 树划分要点 3 3o b b 包围盒的碰撞检测 3 3 1o b b 层次二叉树的遍历 l l o j i 3 3 2o b b 包围盒间的相交测试2 1 3 3 3o b b 包围盒的分离轴2 1 3 3 4o b b 包围盒间的重叠测试2 2 3 2 基本几何元素之间的相交测试2 4 3 2 1 分离轴检测法2 4 3 2 2 区间检测法2 5 第4 章算法的优化和设计2 6 4 1 分层构造包围树2 6 4 2 剔除不相交节点2 7 4 3 下层的o b b 包围3 0 4 4 程序设计流程31 第5 章模拟实验结论3 3 5 1 实验的设计原则3 3 5 2 碰撞检测系统v c o l l i d e 3 3 5 3 实验结果和数据分析3 4 第6 章总结与展望3 6 参考文献3 7 致谢3 9 发表论文及参加课题一览表4 0 i 指导教师陈宏刚教授 摘要 目前，3 d 游戏已经成为计算机游戏领域的主流，虚拟现实交互式仿真等都有很广泛的应 用，不可否认的是，随着这些应用的复杂度不断上升，在处理这类较人的数据时，与碰撞检 测相关的数据结构和算法也变得日趋复杂。无论是游戏，还是其他类型的模拟仿真应用程序， 碰撞检测始终是程序开发的核心之处。 本文选用的o b b 层次包围盒算法，就是碰撞检测算法中应用比较广的一种方法。其他还 有诸如球形包围盒，轴对齐包围盒( 从b b ) 和离散有向多面体( k d o p s ) 等算法。在众多算 法中，又以o b b 的检测性能最好。论文着重论述了基于o b b 碰撞检测算法的相关问题。主要 从事了以下几个方面的工作： ( 1 ) 在研究o b b 包围盒同有特性的基础上，通过研究构建o b b 层次包围树、包围盒间的 重叠测试和三角形间重叠测试等问题，发现相对于s p h e r e 方法o b b 有较高的重叠测试复杂度， 利用s p h e r e 检测的简单性提出分层构建o b b 层次包围树的改进方法。 ( 2 ) 提出将算法分为两级碰撞检测第一级用s p h e r e 包围盒作为层次包围树的上层， 通过s p h e r e 的快速检测筛选出重叠的物体对象送到下层检测，其中采用双向链表结构对 s p h e r e 包围盒进行管理，在每一帧中更新链表；o b b 包围盒作为下层包围，用二叉树构建层 次树，提供精确的碰撞检测。模拟实验根据程序中的结果做出碰撞信息的报告，并记录每一 帧内发生碰撞的物体对象i d 。 实验数据表明，经过层次优化后的o b b 碰撞检测算法，通过上层的初步筛选能减少无用 检测的时间浪费，使得整体检测效率比单纯的o b b 检测有所提高，特别是在场景中模型数量 比较多时，效果更为明显。本文的研究成果，对于碰撞检测算法的优化有一定的实验依据。 关键字：o b b 碰撞检测分离轴层次包围盒 l n i a b s t r a c t n o w d a y s ，3 dg a m e sh a v ed e v e l o p e di n t ot h em a i n s t r e a ms e c t o r si nt h ec o m p u t e rg a m e sa n d h a v eb e e nw i d e l yu s e di nt h ea r e ao fv i r t u a lr e a l i t ya n di n t e r a c t i o ns i m u l a t i o n ，e t c u n d o u b t e d l y , a s t h e s ea p p l i c a t i o n sa r eb e c o m i n gm o r ea n dm o r ec o m p l i c a t e d ，t h ed a t as t r u c t u r e sa n da l g o r i t h m r e l a t e dt ot h ec o l l i s i o nd e t e c t i o na r ei n c r e a s i n g l yb e c o m em o r ei n t r i c a t ec o r r e s p o n d i n g l yw h e n d e a l i n gw i t hs u c hk i n do fl a r g e rd a t a c o l l i s i o nd e t e c t i o nh a sa l w a y sb e e nt h ec o r et e c h n i q u ei nt h e p r o g r a md e v e l o p m e n tn om a t t e ri nt h eg a m e so rs o m eo t h e ra p p l i c a t i o n so fs i m u l a t i o n i nm yp a p e r ，1w o u l dt a l ka b o u tt h eo b b ，w h i c hi sam e t h o dw i d e l yu s e di nt h ec o l l i s i o n d e t e c t i o n ，o t h e rm e t h o d ss u c ha sa a b ba n dk d o p a sa n ds oo na r ei n f e r i o rt oo b bw h e nt a l k e d a b o u ti t sd e t e c t i o np e r f o r m a n c e b a s e do nt h er e s e a r c ha n da n a l y s i so ft h ei n h e r e n tc h a r a c t e r i s t i c so fo b b ，t h ef u r t h e rr e s e a r c h a n db u i l d i n go fo b b ，t h eo v e r l a pt e s ta m o n gt h eb o u n d i n gv o l u m e sa sw e l la st h et r i a n g l e s if o u n d t h a to b bh a sh i g ht e s tc o m p l e x i t y , s o1w o u l dp r e f e rt op u tf o r w a r dt h em e t h o d so fi m p r o v i n gt h e c o n s t r u c t i o no f o b b b yt a k i n ga d v a n t a g eo f t h es i m p l i c i t yo f t h es p h e r et e s t t h ei d e ao fd i v i d i n gt h ea l g o r i t h m si n t ot w ol e v e l so fc o l l i s i o nd e t e c t i o n ：f o rt h ef i r s tl e v e l ，w e c h o o s et h es p h e r eo b ba st h et o pl a y e ro ft h eh i e r a r c h i c a lb o u n d i n gt r e e t h r o u g ht h ef a s tt e s to f s p h e r e ，w ew o u l ds c r e e nt h eo v e r l a p p e do b j e c t sa n dt h e nd e l i v e ri tt ot h eu p p e rl a y e rf o rt e s t d u r i n g t h ep r o c e s s ，w ew o u l du s et h ed o u b l el i n k e dl i s t st om a n a g et h es p h e r eo b bi ne v e r yu p d a t e dl i n k l i s t o b b ，t h el o w e rb o u n d i n gb o x , u s e dt op r o v i d et h ee x a c tc o l l i s i o nt e s t t h ev i r t u a le x p e r i m e n t w o u l dg i v et h er e p o r to ft h ec o l l i s i o nb a s e do nt h er e s u l to ft h ep r o c e d u r ea n dw o u l dr e c o r dt h e c r a s h e do b j e c t si ne v e r yf r a m e a st h ed a t ad r a w nf r o mt h ee x p e r i m e n t ，t h ei m p r o v e do b bc o l l i s i o nt e s ta l g o r i t h m sc a nr e d u c e t h ew a s t eo ft i m es p e n ti nt h eu s e l e s st e s ti nt h eu p p e rs c r e e n i n g ，w h i c hi n c r e a s e dt h eo v e r a l l e f f i c i e n c yc o m p a r e dw i t ht h ep u r eo b bt e s t c o n s e q u e n t l y , t h ea c h i e v e m e n t si nm yp a p e ro f f e r e d s o m ee x p e r i m e n t a lb a s i sf o rt h eo p t i m i z a t i o no fc o l l i s i o nt e s ta l g o r i t h m s k e yw o r d s - o b b ；c o l l i s i o nd e t e c t ；s e p a r a t i o na x i s ；h i e r a r c h yb o u n d i n gb o x t i 譬 u “ i 两南大学硕+ 学伊论文第1 章绪论 1 1 引言 第1 章绪论 自从计算机面世以来，人们就考虑怎么用计算机来描述现实中的真实世界。 随着技术的发展，软件编程和硬件实现都有了长足的进步，在计算机中模拟的现 实世界也越来越逼真。特别是近些年来虚拟现实技术的发展和3 d 游戏的广泛流行， 人们对于计算机中模拟的世界的真实性要求就越来越高。表现真实性的关键就在 于怎么表现出现实世界不同对象间的物理关系( 比如人的触感) ，在计算机中就表 现为相互间的碰撞问题。碰撞检测的算法，就是为了解决怎样检测两个不可能发 生穿透的物体在它们运动变化过程中什么时候会发生碰撞。 在计算机游戏中，碰撞检测要保证真实世界的正确虚拟化，例如禁止人物穿 越墙壁，防止人物掉入地板下等；同时在射击游戏中，还将判断人物是否被子弹 射中。在机器人模拟程序中，碰撞检测可以用于路径的检测，从而使机器人能够 避开障碍物。在一些应用程序中，例如动画渲染和路径规划，它们对于碰撞检测 的实时性没有太高要求，而在其他应用程序中，特别是在计算机游戏中，就特别 强调对碰撞检测的实时性，以保证游戏画面能够保持在一个较高的帧率上绘制。 在这些复杂的场景中，经常包含有大量的几何物体，因此，如何应对这种复杂场 景中大量不规则物体之间的碰撞，并作出快速而精确的检测产生比较真实的反应， 一直是碰检测问题的研究难点与重点。 1 2 碰撞检测算法的发展 从上世纪七十年代开始，人们已经关注到在计算机中如何描述几何物体碰撞 检测的问题，随着研究的不断深入，在这几十年来已经研究出很多不同的解决方 法，从而推动着相关领域的发展。 一开始人们从简单的问题着手，研究在某一个时间段内，两个相对静止的物 体它们之间是否发生了碰撞。这种算法看起来比较笨拙，它只能在这些预先设定 好的时间段内进行检测，没有太多的时效性。在这方面有过贡献的学者有d o b k i n 乜3 ， a g a r w a l 3 1 和c h a z e l l e 43 等。 后来随着研究的不断深入，人们开始考虑在更加复杂的环境中怎样解决连续 运动的物体间碰撞的问题。连续碰撞检测算法是指在一个连续的时间间隔 f n ，0 一 内，判断运动中的物体是否与其他物体发生碰撞的算法；由于连续碰撞检测算法 的研究涉及到了包括时间在内的四维空间问题和对空间结构精确的建模，所产生 两南人学硕+ 学位论文第1 章绪论 的算法复杂度较高、计算速度比较慢，特别是在大型场景中不能进行高效的实时 碰撞检测；c a m e r o n 砖3 ，c a n n y 阳3 ，r e d o n 盯8 3 在这方面都进行了较好的研究。 为了应对连续碰撞检测算法的复杂度和非实时性的问题，研究人员又提出了 把连续的时间轴分成不同的离散点( 。0 , i 一2 ”) ，分别在时间轴上的每个离散 点上对场景中的物体进行碰撞检测。这样，在每个时间离散点上都可以看作是类 似于静态碰撞检测的问题阳3 。但是，由于采用的时间点是离散的，在整个检测过程 中，每两个离散点之间的时间段里物体有没有发生碰撞我们无法得知。有可能这 个时间段间隔的太久了，两个物体在这个过程发生了碰撞，而在下一个离散点上 碰撞结束，这样在检测时我们会误以为两个物体没有发生碰撞。也有可能两个物 体在前一个离散点之后就发生碰撞一直持续到下一个离散点才检测出来，这时两 个物体已经发生了碰撞重叠，使物体之间的真实性大大降低。 虽然离散碰撞检测算法存在着一些问题，但由于其检测过程的快速性能较好 地迎合多数实时碰撞检测的应用需求，所以离散碰撞检测算法依然是碰撞算法的 研究重点和热点；此外，人们还通过一些优化方法在一定程度上减缓了离散碰撞 检测算法的不足点；比如，自适应补偿技术和可中断的碰撞检测技术等都有助于 改善这两个问题旧1 0 1 1 1 。 由于物体对象的空间结构特性，有人利用物体这种特性，研究出一种基于物 体空间的碰撞检测方法。这其中基于图像控件的碰撞检测算法是近些年比较新颖 的算法。我们知道计算机处理图形运算和显示的硬件接口就是由g p u 来实现的， 这种算法就是利用g p u 的高效的物理绘制功能进行快速的检测，从硬件的级别上 提高检测的速率，相对于软件实现要快很多。而且，硬件的发展速度很快，现在 的g p u 芯片的运算速度已经超越了c p u 的速度，采用这种方法进行检测的效率也 有了飞速的发展，这将成为以后研究碰撞检测的热点。 另外也有从表示物体的几何结构特性上着手研究，我们知道每一个物体对象 都是由基本的几何形体构成的，比如三角形、四边形。h u b b a r d 等人以此提出基于 多边形来表示的模型方法，把物体表面简单地表示为一组多边形的集合，通过对 多边形几何的检测来判断两个物体是否发生碰撞，基于这种原理的碰撞检测算法 也是一个研究的热门旧3 。 基于特征的碰撞检测算法采用最邻近特征算法的思想，按照多面体的特征对 顶点、边、面等进行区间划分，并对每个特征构建所对应的区域称作v o r o n o i 的 区域。把一些相互之间距离较近的特征点构成的区域就叫做v o r o n o i 区域，参照 物体空间的连贯性来提高v o r o n o i 区域之间的碰撞检测效率n 利。 另外一种叫做g j k 的基于单纯形的碰撞检测算法n 引。该算法将两物体看作一 个单纯形，通过单纯形的几何特征来计算之间的分离或碰撞情况。 2 阿南大学硕十学伊论文 第1 章绪论 用几何划分的方法可以将两个几何模型间的碰撞检测问题分为两类：空间分 解法( s p a c ed e c o m p o s i t i o n ) n 钔和层次包围盒( h i e r a r c h i c a lb o u n d i n gv o l u m e ) n 5 1 方法。这两个方法的目的都是为了尽可能早的排除不相交的基本几何元素对的 数目，剔除对碰撞检测没有影响的基本几何元素，来提高碰撞检测的效率。 空间分解法是将整个虚拟空间分解成数个体积相等的小单元格，在每个时刻 每个对象都会分配到一个或多个单元中，对于运动中的对象，只需在下一时刻重 新计算对象所占的单元格。对占据同一单元格或者占据相邻单元格的几何对象进 行碰撞检测。从而把两个对象间的碰撞问题转化为包含该对象的单元格之间的碰 撞检测。该方法适用于物体在充满障碍物的空间中移动这样的场景，因为障碍物 占据的单元格是固定的，只需同步更新物体所占的单元格n 刮。 层次包围盒方法是近年来碰撞检测技术中应用最广的一种算法。利用空间分 解法的思想，用体积较大结构简单的几何体( 称作包围盒) 来近似地代替复杂的 物体对象。由于物体对象较大，通常将物体对象分成不同的层次，在每一层次上 用包围盒对其进行包围。以物体对象作为分解树的根结点，通过一定的分解方法 将对象分解成一个由包围盒组成的树形结构，每一个包围盒作为树中每一层的结 点，一直分解到简单的几何元( 三角形或四边形) 为止，从而至上而下逐渐逼近 所包围的物体对象。在进行碰撞检测时，对两个物体的层次结构进行层间的比较， 首先判断两个包围盒树的根节点是否相交，如相交则进一步判断它们的子节点是 否相交，以此类推如果直到判断到基本几何元素时依然相交，则可判定两物体对 象发生了碰撞。这种碰撞检测方法也称为混合碰撞检测算法 1 7 。把快速排除不 相交部分的过程成为粗略( b r o a dp h a s e ) 过程，把节点间进行精确碰撞检测的过 程称为精细( n a r r o wp h a s e ) 过程。这种方法只需对两对包围盒间相交的部分进 行深层次的检测，从而可以大大减少参与进行碰撞检测的包围盒数目，提高了碰 撞检测的效率。 但是，这种方法通常只适用于刚体( 即形状大小不会发生改变的物体) 对象， 对于软体的对象，由于它们会发生形变，每次发生变形后都要重新构建新的层次 包围树，因此不能做到实时检测。对于软体之间的碰撞检测，其算法往往比较复 杂，相关研究人员提出过基于线性规划的更新算法和一种基于s o l i d 库的方法在 模型发生变形时更新相关的结点。不过软体对象之间的碰撞检测算法发展还不完 善有很多需要改进的地方。 1 3 碰撞检测算法的设计因素 在设计碰撞检测系统时，有很多因素会影响到设计者的选择，概括起来有以 两南人学硕十学何论文 第1 覃绪论 下几点： 程序中物体对象的表达方式。场景中物体的几何表达方式将会直接影响到相 关算法的选择，当系统内所要求的约束条件比较少时，可以选用比较通用的碰撞 检测算法，来满足系统的要求。 查询类型的多样化。在碰撞检测中，如果系统要求的检测精度越高，那么它 所需要的计算量就越大，可能还需要额外的数据结构来进行支持。 环境参数的影响。对于一个碰撞检测的模拟环境，它自身包含了很多参数来 描述系统的运行，这些参数( 例如对象的数量、尺寸以及位置关系、是否发生移 动、是刚体还是软体) 都会影响到碰撞检测算法的选择。 检测算法的健壮性。实时碰撞检测系统的要求比较高，而且也会受到物体对 象形状大小的影响，在对它们进行相互检测时，即使两个碰撞的物体之间的检测 间距每次发生较小的误差，在一定时间后也将会对整体的碰撞检测产生较大的偏 差影响。 以上这几条说明了不同的系统对于系统内碰撞检测的实时性和精确性的要求 不尽相同，以上提到这么多种碰撞检测算法，大部分检测算法都是针对于某一具 体场合设计的，并没有哪一种算法适应在所有的需求中。而且，这些算法大部分 都集中于处理在静态环境下两个包围盒树之间的碰撞检测研究，对于动态环境下 较复杂的场景中多对象间的碰撞检测问题，还没有比较高效的算法产生。 1 4 论文的研究意义 随着科学技术的发展，在实时交互系统和不断注重体验的3 d 游戏的广泛应用， 虚拟场景中的物体模型越来越多，对碰撞检测的精度和效率要求比较高。在虚拟 系统中，怎么协调碰撞检测的实时性和精确性，怎样提高在动态环境下复杂场景 中多物体对象间的碰撞检测效率问题，是很多学者的研究方向和重点。本文也在 着重探讨如何提高碰撞检测算法的效率问题。 1 5 论文结构安排 论文的各章节安排如下： 第一章首先介绍研究背景以及相关碰撞检测方法的概述，还有对论文研究意 义的分析。 第二章介绍了三种经典的层次包围盒方法的构建和检测方法，介绍树的度的 概念，以及构造层次包围盒树的方法，以及怎样对树进行更新，最后比较了每种 层次包围盒方法的优缺点，介绍各自适用的范围。 4 两南人学硕十学伊论文第1 罩绪论 第三章详细介绍o b b 包围盒的构造和计算，怎样构造和遍历o b b 树；以及 o b b 包围盒间的相交测试，二叉树的遍历和更新，和基本几何元素之间相交测试 所用到的面检测法。 第四章介绍分层优化的方法以及详细的算法描述。 第五章提供相关的实验结果和对比。 第六章是总结与展望，提出今后的工作重点和研究方向。 两南大学硕十学何论文第2 章经媳的层沸：包同盒方法 第2 章经典的层次包围盒方法 2 1 包围盒的原理 层次包围盒方法是碰撞检测算法中使用比较广泛的一种方法，是在1 9 7 6 年由 c l a r k 提出的；它的基本思想是用体积略大且几何特性比较简单的包围盒来近似地 描述复杂的几何对象，从而构造成能够接近对象的树形层次结构模型1 8 】。一个包 围盒( b v ) 是一个简单的体空间，它能够包围一个或多个具有复杂形状的物体。 这种简单的包围体的相交测试相对于复杂形状的物体来说，具有一定的计算优势。 并不是所有几何对象都可以充当有效的包围盒，包围盒的期望特征有下面几 条： 1 、有低耗费的相交测试。 2 、能实现紧密的包含。 3 、计算所需的花费较少。 4 、易于进行盒体的旋转和变换。 5 、每个包围盒在计算机内存中占有的内存较少。 为了支持低消耗的碰撞检测，包围盒应该具有较为简单的几何形体，同时包 围盒形状应尽量与物体对象之间实现较为紧密的结合，并且在这种紧密结合与低 消耗之间形成一种平衡关系。一般情况下，包围盒的计算需要采用预处理方式而 不是实时计算，在系统运行之前，计算机首先把物体的包围盒关系保存在计算机 内存中，所以如何减少包围盒在内存中的占有量也是一个需要考虑的问题。 2 2 包围盒方法的分类 在碰撞检测领域中研究比较多的包围盒主要有：包围球( s p h e r e ) 、沿坐标轴 的包围盒( a a b ba x i s a l i g n e db o u n d i n gb o x e s ) 、方向包围盒( o b bo r i e n t e d b o u n d i n gb o x ) 、固定方向的凸包f d h ( f i x e dd i r e c t i o nh u l l ) 等。 2 2 1 包围球( s p h e r e ) 一个对象的包围球( s p h e r e ) 被定义为包含该对象的最小的球体n 9 1 。球体几何 特性比较简单，基本不受旋转变换的影响，只需要简单地平移至一个新的位置就 完成了旋转变换。球体按照球心和半径的关系可以定义出一个包围球在计算机中 的保存结构，只需要保存球体的球心坐标和半径长度，这样可以节省保存所需的 内存空间。 计算包围球的球心可以通过选取物体对象的各坐标轴上的六个端点，选择其 6 两南大学硕十学伊论文第2 章经典的层次包同盒方法 中间隔距离最远的两个点，这两个点的中心即为确定的球心，根据这个球心位置 预先确定出一个不太精确的包围球体；然后再对所有的顶点进行遍历，将那些位 于当前球体外部的顶点包含进来，相对于原球心，新球的半径将向外延伸至所有 的外部顶点，这样所有的顶点都将被最终确定的包围球所包含住。假设球心为o ( 坐标为l x y ：) ，球半径为r ，那么包围球的表示方式为： r = ( x ，y ，z ) j ( x c ) 2 + ( y c y ) 2 + ( z c ：) 2 00 6 攉入操作f3 一。 _ 茹一品扩赢巍 一赢乙亲之毒 图2 1 层次树的构造方法 2 3 2 1 自顶向下的构造方法 自顶向下的构造算法可以按照递归的方式加以描述。算法开始于输入的物体 对象本身，在后续的操作中将这个物体对象划分至两个子集合中，该过程将再次 针对这两个子集实现递归调用以构造下面的分支层次结构，同时作为子节点链接 至其父包围盒的节点上。这样循环往复向下递归划分，在递归结束后结构成该物 体对象的包围盒树。 为了简化划分过程，通常采用分割平面来将原集合划分为两个子集。但是会 出现所选的分割平面跨越了几何物体这种情况。一种方法是将物体对象一分为二 放入相对应的子集中，同时对象将被分割成更小的形体，从而降低了相应的相交 测试量。但是，这种跨越分割也有一个缺陷：分割后的几何物体将可能再次面临 分割，这将使得产生的子节点的个数急剧增加。 另一种方法是不对物体对象进行分割，而是计算它相对于分割面的质心位置， 从而确定它到底属于哪个子集。对于质心正好处在分割面上的，则将它放入较小 ， 、 两南大学硕十学伊论文第2 章经典的层次包同龠方法 的子集中去，这样能保证两个子集所含的包围盒数大致相等，使树的结构尽量平 衡。 这种划分方法尽可能的把相邻的几何元素分到同一集合中去，但是关键是如 何选择合适的分裂平面。通常的选择方法是：先确定分裂平面的法线( 分裂轴) ， 然后确定分裂轴上的分裂点来定位分裂平面的位置。通常有下面几种选择方法来 确定分裂点： a 质心坐标的平均值：具有良好平衡特征的树型结构有时无需提供最佳查询 时间，当沿着最大方差轴进行分割时，采用对象均值将优于中值法，并且连续进 行均值分割将生成空间紧凑的树型结构、减少相关的操作量并获得快速查询时间。 对象均值算法的时间消耗为o ( n ) 级别。 b 中值方法：在对象中值处实施分割将使得子集间的图元呈现均匀分布状态， 从而可生成较为平衡的树型结构。通过对定点排序，该总值算法的时间消耗可达 到o ( n l o g 刀) 级别。 c 包围盒中值法：算法只检测包围盒且不包括其中的对象数据，分割点计算过 程的时间消耗为常数级。该算法常用于父节点包围盒中的既定轴上( 如利用最大 间距面定义的轴) 。 2 3 2 2 自底向上的方法 与自项向下方法相比，自底向上方法的实现过程比较复杂而且构建过程也比 较耗时，但通常能够生成最优树汹3 。采用自底向上方法构造树型结构时，首先需 要建立图元的包围盒，这些包围盒形成了树型结构的叶节点。基于某种合并策略， 可以从包围盒结果集中选择两个( 或多个) 叶节点，并再次构造其包围盒并替代 集合中的原节点。这一组合过程持续递归向上进行，直至集合中只包含树根节点 的包围体，即整个物体对象。 其中选择的合并策略是：选择一组节点并使其包围盒所占空间最小，使两个 节点实现合并，考察全部可能的计算其包围盒，最终得到具有最小包围盒的两个 节点。这种算法的时间复杂度为o ( n 2 ) ，构造一棵完整的树还需要循环n 1 次，因 此构造全过程是时间复杂度为o ( n 3 ) 。 2 3 2 3 插入算法 插入算法还可称为扩充算法，构造过程将开始于一棵空树且每次插入一个对 象，从而建立相应的树型结构。 对象搜索相应的插入位置并执行插入操作，且依据相关权值，树型结构得以 逐步扩充。如果插入对象大于现有节点，插入过程将会在层次结构的顶部结束操 1 2 f 、 两南人学硕十学位论文第2 章经典的层次包| 苇f 盒方法 作；较小的插入对象将位于现有相关节点的内部，且插入过程将会在层次结构的 底部结束其操作；其次，若对象距现有节点距离较远，插入过程也将会在层次结 构的顶部结束操作。针对原对象的集合，这种方法所生成的树能够比较真实的反 应聚类状态。 树型结构的最终结构依赖于所插入的对象，插入算法的速度不低于自项向下 的方法，并且能产生较好的计算结果。但是，很少有碰撞检测系统采用这种插入 的构造算法。 2 4 包围盒树的更新 在一个碰撞检测的环境中，物体对象通常不会保持静止状态，而是会不断发 生运动变化的。静态的碰撞检测系统中，通过记录在初始状态时物体对象的位置 和形状关系来构建系统预处理阶段所得到的包围盒树结构。但是，由于在大多数 环境中，物体对象很有可能发生运动变化，使得环境中某些物体对象的位置和状 态也都会发生变化，改变了先前生成的包围盒树中所描绘的环境中的空间结构， 这样为了进行碰撞检测，我们需要对预先生成的包围盒树进行实时的更新。但是 如果在每次系统内部发生变化的时候，都重新构造新的树，产生的开销会影响到 碰撞检测的实时性。为了满足碰撞检测快速准确的要求，在物体发生运动变化后， 我们希望通过较为简单的方法对包围盒树进行快速的更新。 在虚拟环境中，活动对象的运动类型可以分解为旋转和平移两类。虽然物体 对象的运动方式是随意性的，不能通过准确的公式进行确定，但是可以根据当前 时刻物体对象的位置来确定它相对于初始状态的位置参数和方向参数。沿x 轴、y 轴和z 轴的平移参数，对应于一个平移向量t = ( x ，y ，z ) 7 ，以及绕x 轴、y 轴和z 轴的旋转参数队仍杪，对应的变换矩阵为心利： - 1 0 0 r o t ( x ，= l0 c o s o s i n o l 1 0 s i n oc 。s 0j i c o s a p 0 s i n ol r o t ( y ，缈) = 1 01o i l - s i n 血p 0 c o s t pi c o s g r - s i n 0 l r o t ( z ，v ) = ls i n 妙 c o s y 0l l 00 l j 假设物体对象的变换次序为绕x 轴、y 轴和z 轴旋转，那么合成的旋转矩阵为： 两南人学硕+ 学伊论文 第2 章经典的层次包闸盒方法 r = r o t ( x ，o ) r o t ( y ，o ) r o t ( z ，少) = 医 = 巴 o c o s o s i n0 0 c o s 0 s i n0 0 s i n 0 c o s 0 o s i n 0 c o s o c o s 0 一s i n c o s 妒c o s y s i n l 一s i n 妒c o s 沙 一c o s 缈s i n 沙 c o s l s i n 妒c o s y s i n l f ，0 c o s q 0 ol f _ c o s e c o s vc o s c p s i n vs i n 矽 l = lc o s o s i n + s i n o s i n c p c o sc o s o c o s v s i n o s i n 妒s i n y s i n o c o s c p s i n o s i n v c o s o s i n p c o s vs i n o c o s v + c o s o s i n o s i n vc o s o c o s oi 用x 一般+ z 描述物体对象相对原始状态所发生的变化，它可以分解为一个平 移上的变换x j x + = f 。和一个旋转变换x _ r x 。 在一个物体对象发生平移运动之后，对包围盒进行相同的平移变换，可以得 到新位置处相对应的包围盒。当物体对象发生旋转运动后，对包围盒的旋转变换 比较复杂，每一种包围盒类型的旋转变换都是不一样的。 对于球形包围盒，由于球体的旋转对称性，物体对象的旋转，并不会使它的 球心和半径的坐标发生变化，只需考虑在平移方向上的运动影响，将球形包围盒 的球心加上平移向量t 即可。 对于o b b 包围盒，由于物体对象的o b b 是根据它自身的几何树形决定的， 包围盒的轴向跟物体对象的轴向是一致的。在物体对象发生运动后，可以对它的 包围盒做同样的运动变化，这样得到的o b b 包围盒还是跟变化前的包围盒一样， 只是位置发生了改变。这样，对于o b b 包围盒树的更新，只需要对o b b 包围盒 进行同样的旋转变换，对o b b 包围盒的基底乘以同样的旋转矩阵，然后再加上一 个平移的向量t 即可，o b b 包围盒相对于物体对象的位置还是不变的。 2 5 层次包围盒方法的性能分析 上述介绍过的几种类型的包围盒方法各有优缺点，各自能适用于某一特定场 合，在进行碰撞检测测试时，需要根据不同的应用领域中的不同的检测要求，来 选择合适的包围盒进行比较高效和精确的层次包围盒方法。对于层次包围盒查询 的期望性能，相关研究人员已经总结出一种碰撞检测时间效率评价的公式： t = n b x c b 七np x c p 七n 。x c h 1 4 矿y 吣m 0 c s 。l 1j 缈 缈 m 0 宝 s c n u 1 0 丌iiii卫=ijji皿 两南人学硕卜学伊论文第2 章经典的层次包同盒方法 字符 rn bg n d c p n 。e 表表示表示表示物体对象 表示表示表示修 示碰撞基本的几测试一对在运动变换之后包 参与重叠测试一对改每一个节 检测的 何元素问 几何元素含它的包围盒层次 描述测试的包包围盒重点所需耗费 总代价 相交测试相交所花中需要更新的节点 鼍 嗣盒对数叠的代价的时间 函数的次数费的代价数 各字符如上表示。 山- t - 右此笛沣不霪亘时白围合巨汾- d ：l ：j - 7 - 前寥曲 簖z 寸的县臣一俪可f ! j 省m 欠 比如o b b 算法中物体的包围盒是在物体的局部坐标系中计算得到的，只有在对包 围盒进行重叠测试时才根据物体的位置和方向将包围盒转换到世界坐标系中。而 k d o p s 算法是在全局坐标系中来计算物体对象的包围盒的，每当物体运动时，它 所包围的层次结构需要进行重新计算。 从耗费公式的构成可以看出，模型中几何形状的复杂度、基本几何元素的数 量和模型之间的距离等因素对公式的结果影响比较大，而且这些变量是可以通过 计算来进行压缩的；在碰撞检测中，进行相交处理的包围盒数目越多，花费的时 间就越长；采用结构简单的包围盒，可以缩短更新包围盒所花费的时间；在包围 物体对象的包围盒类型一定时，包围盒树中的节点越少，需要的耗费也就越少； 设计能满足耗费尽量低的要求，应尽量使包围盒的设计满足下面几条准则陋引： a 提高包围盒相交检测的速度。 b 包围盒要提高对包围物体对象包围的紧密性，可以减少参与重叠测试的包围 盒对数和基本几何元素对数。 c 肩邑够快速的更新包围盒，减少物体对象形变时的更新消耗。 d 提高基本几何元素问相交检测的速度。 2 。6 各种包围盒的优缺点 由于包围球是比较简单的包围盒体，而且由于包围球的旋转对称的特性，使 得它所包围的物体在发生旋转平移时，不需要对包围球进行更新，有效的减少了 n 。的消耗。但是，当物体对象发生形变时，需要对包围球进行更新，而且由于包 围球对物体对象的包围紧密性较差， 法。 因此在精确的碰撞检测中很少用的包围球方 两南人学硕十学何论文第2 章经典的层次包闸盒方法 a a b b 包围盒在总是沿着被包围物体对象的局部坐标系的三条轴向方向构建， 在构建的时候比较简单，应用比较广泛，而且由于a a b b 测试的简单性，在软体 对象的碰撞检测中也适用。不过，a a b b 包围盒与o b b 包围盒有同样的缺点，它 们的包围紧密性都比较差，特别是对于跟坐标轴不平行的细长刚体对象，包围的 紧密性更差，所以只适用于物体对象在虚拟空间中分布较为稀疏的情况，或者是 应用于对碰撞精度要求不高的系统中。 o b b 包围盒有任意方向构建包围盒的特性，所以能比包围球和a a b b 更紧密 的包围物体对象。而且，由于o b b 可以根据它所包围物体对象的特征调整它的方 向轴来尽可能严密的包围物体，可以有效减少无用包围盒的数目，使参与相交测 试的包围盒数目大大降低。在物体发生运动变化时，可以对o b b 包围盒进行相应 的旋转平移，减少花在运动变换上的消耗。但是，由于o b b 任意方向包围的特性， o b b 包围盒树中每一层节点的包围盒都是有其各自的特征的，跟它上下层的节点 间的关联性不大，使得在构建o b b 树时的时间相对较复杂。对于软体对象，当对 象发生形变时，需要全部更新o b b 树上的所有节点，所花费的时间很长，无法满 足实时计算的需求，所以软体对象间的碰撞检测也不适用于基于o b b 碰撞检测的 算法。 固定方向凸包的f d h 包围盒，它的相交测试可以通过在不同方向上的范围区 间的相交测试来完成。构成它的包围盒中所有面的法向量属于某个固定方向的向 量集合，其简单性也比较好。由于它的这种特性，对物体对象的包围紧密型也较 好。可以通过线性规划的方法在物体对象发生旋转变换后来进行包围盒树的优化 计算。在物体对象发生形变后，用子节点的f d h 来合成父节点的f d h ，通过自底 向上的顺序，来进行一层层的向上构建整个节点变形后的包围盒树。在大多数情 况下o b b 包围盒的紧密性要优于f d h 。 通过上面的分析可以看出，不同类型的包围盒它们之间的特性是不尽相同的。 包围球和a a b b 的包围紧密程度不如形状复杂和灵活的方向包围盒o b b ；由于形 状简单的包围盒间重叠测试的速度比较快，能比使用形状复杂的包围盒间重叠测 试的耗费降低，但是又同时增加了形状简单的包围盒需要测试的数目。碰撞检测 的耗费大小与其所应用的物体对象之间有很大的关系，比如对两个几乎重合的同 心球问的碰撞检测，o b b 包围盒的性能是最佳的，因为在这种情况下，包围盒的 紧密性是最重要的，紧密性较差的包围盒通常很难找到包围盒不相交的情况，从 而导致大量的包围盒重叠测试和基本几何元素间的相交测试。但是，在计算o b b 是，不仅需要计算集合中所有元素的协方差矩阵及其特征向量，还要计算集合中 每个顶点在三个特征向量上的最大值，所需要的开销比其他几种包围盒的要大。 1 6 两南大等：硕十学伊论文第3 市o b b 层汐：包同龠的构造 第3 章o b b 层次包围盒的构造和碰撞检测 在前一章，我们介绍了几种不同的碰撞检测算法，以及层次包围盒树的构建。 在本章中，将主要介绍怎样计算合适的o b b 以及如何构造o b b 包围盒树。在我 们的碰撞检测系统中，主要采用的就是用o b b 包围盒和球形包围盒相结合的方式 对物体对象进行包围，并按照层次二叉树结构进行自顶向下的构造。 3 1o b b 的计算 在场景检测、虚拟现实、3 d 游戏场景等领域中较多的采用了o b b 碰撞检测 方法。一个给定对象的方向包围盒o b b 被定义为包含该对象且相对于坐标轴方向 任意的最小的长方体“9 1 。o b b 的计算关键是怎样去寻找一条最佳的方向轴，能够 满足在这个方向轴上确定的包围盒能够紧密的包围住物体对象。通常我们利用包 围盒体的几何特性，计算出所有顶点坐标分布的均值，将得到的值作为包围盒 的中心，再计算协方差矩阵c ，然后利用矩阵c 的特征向量，计算出o b b