（计算机软件与理论专业论文）变形体的碰撞检测算法研究.pdf

摘要 一个快速并且健壮的碰撞检测检测算法在很多领域比如虚拟现实、计算 机游戏、计算机辅助设计都扮演着重要角色。近几年来，随着虚拟现实技术 和分布式仿真技术的兴起，碰撞检测问题成为一个研究的热点。 相对于刚体对象，变形对象表现在当它移动时组成变形体对象的顶点之 间的相对位置发生变化。对于刚体对象，大部分碰撞检测算法所依赖的数据 结构都可以在预处理阶段处理完毕。但对于变形体对象，适用于刚体对象的 碰撞检测算法将不能直接应用。因为顶点之间的相对位移发生变化，因此用 于碰撞检测算法的数据结构必须实时的重新构建或者更新。 对于变形体的碰撞检测算法，本文从两个方面对传统的算法进行改进。 第一种方法是处理可变形体对象时更新而不是重新构建数据结构，因为重新 构建整个数据结构的时间耗费在一个实时的仿真环境中是不能接受的。同时 通过压缩方法对传统a a b b 层次包围盒进行了改进，通过从空间的角度来对 传统的层次a a b b 包围盒进行优化，从而节省了大量的存储空间，提高了变 形体的碰撞检测效率。第二种方法提出了一种基于包围盒方法与空间分解方 法相结合的碰撞检测算法，与其他碰撞检测算法相比较，本算法不仅具有能 够节省空间，而且时间复杂度也比较低。除此之外，本算法不仅能够找出发 生碰撞的基本几何，l 素对，而且还能够精确地找出碰撞点。 关键词：碰撞检测，变形体，a a b b ，哈希表，空问分解 a b s t r a c t ar a p i da n dr o b u s tc o l l i s i o nd e t e c t i o na l g o r i t h mp l a y sa ni m p o r t a n tr o l ei n m a n yf i e l d ss u c ha sv i r t u a lr e a l i t y ，c o m p u t e rg a m ea n dc o m p u t e ra i dd e s i g n i n r e c e n ty e a r s ，c o l l i s i o nd e t e c t i o nh a sb e e nah o tt o p i cw i t ht h eb o o mo fv i r t u a l r e a l i t ya n dd i s t r i b u t e ds i m u l a t i o nt e c h n o l o g y c o m p a r e dw i t hr i g i do b j e c t ，t h ed e f o r m a b l eo b j e c th a st h ed i s t i n c t i v ef e a t u r e t h a tt h er e l a t i v ep o s i t i o no fv e r t i c e sc o m p r i s i n gt h eo b j e c tc h a n g e sw h e nt h eo b j e c t m o v e s f o rr i g i do b je c t ，t h ed a t as t r u c t u r e st h a tm o s tc o l l i s i o nd e t e c t i o n a l g o r i t h m sd e p e n d0 ne n di nt h ep r e p r o c e s s i n gp h a s e b u tf o rd e f o r m a b l eo b j e c t ， t h ec o l l i s i o nd e t e c t i o na l g o r i t h mf i tf o rr i g i do b j e c tc a r l ta p p l yt ot h ed e f o r m a b l e o b j e c t b e c a u s et h er e l a t i v ed i s p l a c e m e n to fv e r t i c e sc h a n g e s ，t h ed a t as t r u c t u r e a p p l i e dt oc o l l i s i o nd e t e c t i o nm u s tb er e b u i l to rr e f i ti nr e a lt i m e t h i sp a p e rh a st r i e dt om a k ei m p r o v e m e n t sf r o mt w oa s p e c t sf o rt h ec o l l i s i o n d e t e c t i o na l g o r i t h mo fd e f o r m a b l eo b j e c t s f i r s t ，i m p r o v e m e n ti sm a d et ot h e t r a d i t i o n a la a b bh i e r a r c h i c a lb o u n d i n gb o x e s b y t h ec o m p r e s s i v ea a b b b o u n d i n gb o x ，t r y i n gt oo p t i m i z et h et r a d i t i o n a lh i e r a r c h i c a lb o u n d i n gb o x e sf r o m as p a c ep e r s p e c t i v e t h ed i r e c tr e s u l ti st h a ti tcans a v eal a r g ea m o u n to fs p a c e a n de n h a n c et h ee f f i c i e n c yo fc o l l i s i o nd e t e c t i o nd r a m a t i c a l l y t h es e c o n dm e t h o d p r o p o s e san e wc o l l i s i o nd e t e c t i o na l g o r i t h mt h a t c o m b i n e sb o u n d i n gv o l u m e b o x e sm e t h o da n ds p a c es u b d i v i s i o nm e t h o d i tc a ns o l v et h ec o l l i s i o nd e t e c t i o n p r o b l e m sb e t w e e nd e f o r m a b l eo b j e c t s c o m p a r e dw i t ho t h e rc o l l i s i o nd e t e c t i o n a l g o r i t h m ，t h ea l g o r i t h mt h i sp a p e rp r o p o s e sn o to n l yh a st h ea d v a n t a g et h a ti tc a n s a v et h es t o r a g es p a c eb u ta l s oi t st i m ec o m p l e x i t yi sc o m p a r a t i v e l yl o w b e s i d e s ， i tcanf i n dn o to n l yt h ec o l l i d i n ge l e m e n t a r yg e o m e t r ye l e m e n tp a i r sb u ta l s ot h e p r e c i s ec o l l i d i n gp o i n t s k e yw o r d s ：c o l l i s i o nd e t e c t i o n ，d e f o r m a b l eo b j e c t ，a a b b ，h a s ht a b l e ， s p a c es u b d i v i s i o n 第一章引言 第一章引言 1 1 课题的研究背景及其意义 一个快速并且健壮的碰撞检测检测算法在很多领域比如虚拟现实、 计算机游戏、计算机辅助设计都扮演着重要角色。在一个虚拟手术系统 2 1 1 2 1 中，为了给口f f 练者提供精确的力反馈以及沉浸感( i m m e r s i o n ) ，碰撞 检测模块必须能够把手术器械和人体组织碰撞的结果准确而又实时的传 递给力反馈设备。近几年来，随着虚拟现实技术和分布式仿真技术的兴 起，碰撞检测问题成为一个研究的热点f 3 j 。 碰撞检测是虚拟现实应用中的一个核心问题。譬如，在一个虚拟场 景中，为了模拟的真实性我们必须避免两个物体的互相穿透 ( i n t e r p e n e t r a t i o n ) 。此外为了给出真实的物理现象或反应，我们不仅要判 断物体之间是否发生碰撞，而且还要在发生碰撞的情况下精确的定位发 生碰撞的位置。如果一个虚拟场景对精度要求的不高，我们可以只求出 相交的基本几何元素对，但如果是一个类似于虚拟手术这样的对精度要 求非常高的系统，我们必须能够求出碰撞点。本文提出的第二种碰撞检 测算法能够精确的求出碰撞点。 此外碰撞检测模块占去大量的存储空间和处理时间，往往导致系统 处理的瓶颈。譬如在一个虚拟手术系统中，为了提供给用户真实的沉浸 感以及精确的交互能力，碰撞检测模块必须能够实时的计算手术刀和人 体组织的碰撞并给出精确的碰撞结果。这就要求碰撞检测算法必须具有 良好的时间复杂度以及空间复杂度。 随着计算机硬件处理能力的不断增强，对处理复杂场景以及细节渲 染方面提出了更高的需求。其中的一点就表现在当虚拟场景中包含变形 对象时，例如人体的器官软组织或布料。尽管在碰撞检测领域国内外学 者做了大量的工作，但是这些科研工作大部分都集中于解决虚拟场景中 刚体之间的碰撞检测。近几年碰撞检测的热点集中在变形体方面，尤其 l 青岛大学硕士学位论文 是解决变形体的自相交问题以及拓扑结构改变的情形。 1 2 国内外研究动态以及本文工作 碰撞检测算法主要分为两大流派分别是空间分解法f 4 】( s p a c e d e c o m p o s i t i o 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 s ) 。空间分 解法是将整个虚拟空间划分成相等体积的小的单元格，只对占据了同一 单元格或相邻单元格的几何对象进行相交测试。空间分解法比较典型的 例子有k d t 6 1 树，o c t r e e l 7 1 树，b s p l 8 1 树。采用层次划分方法进行空间分 解，如八叉树1 4 6 1 1 47 1 ，b s p 树等，可以进一步提高算法的速度。空间分解 法通常适用于稀疏的环境中分布比较均匀的几何对象间的碰撞检测。空 间分解法存在的问题是何时终止分解空间单元格以及设置单元格大小。 除了上面提到的两种方法之外，还有另外两种方法今年来得到较广 泛的使用。距离跟踪法的原理是通过寻找和跟踪两个多面体之间的最近 点来计算它们之间的距离，当距离小于等于零时，发生碰撞。当物体的 运动速度不快，相邻帧间运动物体的位移变化很小时，可以利用帧间的 连续性来增量式的计算物体间的距离。常用方法有l i n c a n n y 算法， e n h a n c e dg j k 算法 9 1 1 1 0 】 基于图像空间的碰撞检测方法 1 1 】，一般将三维几何物体通过投影绘 制到图像平面上，降维得到一个二维的图像空间；然后分析该空间中保 存在各类缓存的信息：进而检测出物体之间是否发生干涉。近年来，随 着图形硬件卡等加速技术的快速发展，研究人员结合基于物体空间的碰 撞检测方法中的一些技术，使得基于图像空间碰撞检测技术有了新的发 展。s h i n y a f l 2 】和r o s s i g n a c f l 3 做了这方面的开创性工作，提出了简单有 效的干涉检测算法，但要求有特殊的图形硬件来支持；m y s z k o w s k i 等【1 4 等提出的算法更为实用，能够处理较复杂的实体； 相对于刚体对象，变形对象表现在组成软体对象的顶点之间的相对 位置发生变化或者是在拓扑结构改变时导致基本几何元素的增加或减 2 第一章引言 少。这就导致了适用于刚体对象的层次包围盒方法不能直接的用于变形 对象上。因为此时包围盒树必须实时的重新构建或者更新。而重新构建 整个数据结构的时间耗费在一个实时的仿真环境中是不能接受的，因此 在层次包围盒方法中必须避免整棵树的重新构建。 s m i t he ta l 15 提出一种解决软体对象的方法，该方法在每一步都重 新计算对象的包围盒，其缺点是当模型复杂时不能得到实时计算；v a nd e n b e r g e n 1 6 】提出了一种基于s o l i d 17 】库的方法，并在每个时刻由叶子节 点开始完成自底向上的更新，缺点是发生大尺度变形时，包围盒的紧密 性就比较差并且包围盒与包围盒之间有非常大的重迭区域。本文的第一 种方法【18 也是自底向上更新，但不同之处是利用a a b b 包围盒的特性 对存储空间进行优化，因此可以看作是对s o l i d 的改进。 y a s h i f u m ik i t a m u r a 【19 等人提出了一种用于解决复杂场景下的变形 体的碰撞检测算法，这种算法的本质也是包围盒方法与空间分解法的结 合。该算法首先求出每个物体的a a b b 包围盒，然后对这些包围盒进行 相交测试并求出这些包围盒之间的相交区域( 在相交的| j 提下) 。下一步 针对每个相交的包围盒对所对应物体的基本几何元素，判断它们是否与 包围盒相交区域相交。如果相交，对这些基本几何元素建立八叉树的数 据结构，求出每个空间网格内相交的基本几何元素对。这种方法由于在 第二阶段采用的是空间分解法，它对处于空间同一网格内的基本几何元 素进行测试，因此能够解决自相交( s e l f - i n t e r s e c t i o n ) 闯题。此方法的 缺点是采用八叉树的数据结构复杂，而本文的第二种方法在其第二阶段 空间分解法中采用的是简单的哈希表数据结构，其时间和空间复杂度都 较低。 j m e z g e r 2 0 等人在模仿布料仿真时对层次包围盒结构作了很多优 化。它采用的包围盒类型是k - d o p s 2 l 】，使用它的原因是在更新时父节点 的包围盒完全可由子节点的包围盒来求出，这样就可以当布料变形时完 成从底向上的更新。由于k d o p s 在最坏情况下只需k 2 次相交测试，因 3 青岛大学硕士学位论文 此j m e z g e r 等人采用的是四叉树( 4 - a r y ) 。这样做的优点是减少相交测 试时递归调用的深度，从某种意义上减少了内存消耗。此算法采用的是 一种“膨胀”的k - d o p s ( i n f l a t e dk - d o p s ) ，即在通常的k d o p s 在k 2 个 方向上增大间距s ，这样当基本几何元素移动的距离小于s 时，物体的 包围盒不需要更新，因此很大程度上减少了包围盒更新的次数进而加快 碰撞检测的速度。另外它还采用了“向量圆锥”( n o r m a lc o n e s ) 来解决 自相交问题。 m a t t h i a st e s c h n e r 2 2 1 等人提出了用一种优化的哈希表来解决变形体 以及自相交问题。本文的第二种方法中的第二阶段采用的数据结构也是 哈希表，但实现细节不同。另外，本方法还增加了第一阶段即用a a b b 包围盒来快速排出不相交的物体，来加快碰撞检测的效率。近年来基于 图形硬件的图像一空间技术( i m a g e - s p a c et e c h n i q u e ) 【2 3 】【2 4 】【2 5 】被提出来 用于解决碰撞检测。 第二章传统的层次包围盒方法 第二章传统的层次包围盒方法 由于本文后面的压缩a a b b 方法是对传统的层次包围盒方法的改 进，因此首先对传统的层次包围盒进行简单介绍。层次包围盒方法是碰 撞检测算法中广泛使用的一种方法，它曾经在计算机图形学的许多应用 领域( 如光线跟踪1 2 6 1 2 7 1 等) 中得到深入的研究。 2 1 层次包围盒方法基本原理 层次包围盒方法的思想是利用体积稍大而几何特性简单的包围盒将 复杂几何对象近似，在进行碰撞检测时，首先在包围盒之间进行相交测试， 如果包围盒之间不相交，则物体肯定不相交。只有包围盒相交时，才对 其所近似的基本对象做进一步相交测试。通过构造包围盒树逐渐逼近对 象的几何特性，与一个物体相对应的层次结构的节点是空间上包围该物 体部分几何对象的几何近似体：层次结构的根节点包围了整个物体， 每个父节点包围的几何对象是它的所有予节点包围的几何对象之和，节 点从上到下逐渐逼近它包围的几何对象，进行相交测试时首先判断两棵 包围盒树的根节点是否相交，如相交则递归的进一步判断它们的子节点 相交情况，如果最后的叶子节点相交，判断每对叶节点包围的基本几何 元素( 通常为三角形或四面体) 是否相交。这种方法能够大大减少蛮力 计算方法中n 2 的相交测试次数。 评价层次包围盒方法有两个指标1 3j ：简单性和紧密性。简单性是指 选择的包围盒类型要尽可能简单，这样不仅可以减少相交测试时需要的 计算量而且也可以节省内存耗费。这不但要求几何形状简单容易计算， 而且要求相交测试算法简单快速；紧密性要求包围盒尽可能的贴近被包 围的对象，这一属性直接关系到需要进行相交测试的包围盒的数目，紧 密性越好，参与相交测试的包围盒数目就越少。 2 2 用于碰撞检测的层次包围盒的类型 最常用的包围盒类型有：沿坐标轴的包围盒( a a b bh x is - h l i g n e d 5 青岛大学硕士学位论文 b o u n d in gb o x e s ) 2 s 】、包围球( s p h e r e ) 2 9 1 、方向包围盒( 0 b bo r ie n t e d b o u n d i n gb o x ) 1 30 】、固定方向凸包包围盒( f d hf ix e dd i r e c t io nh u l l ) 3 1 1 等。下面简单介绍一下应用较多的并且非常典型的a a b b 以及o b b 以及 包围球，并对它们作一下比较。 2 2 1a a b b 层次包围盒方法 对象的a a b b ( a x i s a l i g n e db o u n d i n gb o x e s ) 包围盒定义为包围该对象 且各边平行于坐标轴的最小的六面体，如图2 1 所示。a a b b 可表示为 r 5 ( x ，y ，z ) ll x s x s h x ，l y y ! h y ，i ：s z 三h ： 值。其中l 。，h 。，l y ，h y ，l ：，h ：分别 是该a a b b 在x 、y 、z 坐标轴上投影的最小和最大坐标值。 a a b b 的优点是计算十分简单，只需分别计算组成对象的基本几何元 素集合中各个元素的顶点的x 、y 、z 坐标的最大值和最小值即可；同时 a a b b 间的相交测试也最多只需要六次判断，两个a a b b 相交当且仅当它们 在三个坐标轴上的投影区间都重叠 a a b b 包围盒在碰撞检测中应用得最多。采用a a b b 的碰撞检测库主要 有i c o l l i d e ( i n t e r a c t iv ec o l l is i o nd e t e c t i o n ) 1 3 2 】 3 3 】【3 4 】和 q - c o l l i d e ( q u ic kc o l l i s i o nd e t e c t i o n ) f 3 5 儿3 6 1 1 3 7 1 以及s o l i d 碰撞检测库 【l7 1 。 图2 1 对象的 a b b 包围盒 6 第一章传统的层次包围盒方法 2 2 2o b b 层次包围盒方法 一个给定对象的方向包围盒o b b ( o f ie 1 3 t e db o u n d in gb o x ) 1 38 1 被定 义为包含该对象且相对于坐标轴方向任意的最小的长方体。如图2 2 所 示。假定一个o b b 的中心为c ，三个相互正交的方向为v2 、v2 和v 。，三方向 上边长的“半径”为r 、r 。和r 、，则o b b 确定的区域为：r = ( c + a r ，v 1 + b f2 v 2 + c r 。v ia ，b ，c ( 一l ，1 ) ) 。 o b b 最大特点是它的方向的任意性，这使得它可以根据被包围对象的 形状特点尽可能紧密的包围对象，因此它可以很大的减少相交测试的次 数，但同时也使得它的相交测试变得复杂。它的另一个优点是当物体发 生旋转时，对象的o b b 包围盒更新非常快，因为它只需要中心点做同样的 旋转即可。o b b 的计算相对复杂一些，关键是找出最佳方向，并确定在该 方向上包围对象的包围盒的最小尺寸。 1 9 9 6 年g o t ts c h a l k 等人完成了一个称为o b b t r e e s 的“r a p i d ”系统 1 3 9 ，该系统也基于方向包围盒o b b ，曾一度被认为是碰撞检测衡量的基 准。其算法基于分离轴理论( 即检测在少数分离轴上的投影是否重叠) ， 能大大提高算法的效率。 图2 2 对象的o b b 包围盒 2 2 3 包围球方法 对象的包围球 4 8 【4 9 儿5 0 1 ( s p h e r e ) 被定义为包含该对象的最小的球体， 包围球可表示为 7 青岛大学硕士学位论文 r = ( x ，y ，z ) 1 ( x - c 。) 2 + ( y c y ) 2 + ( z c z ) 2 r 2 ) 其中( c 。，c 。，c ：) 是球的中心坐标，r 是球的半径。如图2 3 所示 计算给定对象的包围球，首先需分别计算组成对象的基本几何元素 集合中所有元素的顶点的x 、y 、z 坐标的均值以确定包围球的球心，再由 球心与三个最大值坐标所确定的点间的距离确定半径r 。包围球闻的相交 测试也比较简单。对于两个包围球( c l ，r 1 ) 和( c 2 ，r 2 ) ，如果球心距离 小于两球半径之和，即 c 卜c 2l 三r l + r 2 ，则两包围球相交。 图2 3 对象的包鼹球 包围球的优点是计算简单，并且它是所有的包围盒类型中所需存储 空间最小的一种包围盒类型。 2 2 4a a b b 幂口o b b 的比较 a a b b 是比较简单的一类包围盒。但对于沿斜对角方向放置的瘦长形 对象，其紧密性较差。由于a a b b 相交测试的简单性及较好的紧密性，因 此得到了广泛的应用，同时a a b b 还具有一个特殊的数学属性，父节点的 包围盒完全可以由其两个孩子节点的包围盒求出，这意味着在重新构建 包围盒树时可以从叶子节点进行自底向上的更新，因此适用于软体对象 的碰撞检测。本文的第一种方法正是利用这一数学属性。 o b b 的简单性要比a a b b 包围盒差，但它的紧密性是比较好的，可以大 大减少参与相交测试的包围盒的数目，因此总体性能要优于a a b b 和包围 第二章传统的层次包罔盒方法 球。当几何对象发生旋转运动后，只要对o g g 进行同样的旋转即可。因此 o b b 适用于复杂场景下刚体之间的碰撞检测。但迄今为止，还没有一种有 效的方法能够较好地解决对象变形后o b b 树的更新问题，而重新计算每个 结点的o b b 的代价又太大，所以o b b 不适用变形体的碰撞检测，这也是本 文未采用o b b 的原因。 2 3 层次包围盒的碰撞检测算法流程 ( 1 ) ：根据几何建模的结果构造出初始状态下两类对象的包围盒树 ( 具体的构建方法稍后讲) ( 2 ) ：基于包围盒树的碰撞检测算法，判断是否相交，如果相交还 需进一步判断基本几何元素是否相交。 ( 3 ) ：确定时间采样点，在每个时阃采样点进行包围盒树的更新。 此时又包含两类问题活动对象运动后的包围盒树的更新环境对 象变形后包围盒树的更新。 ( 4 ) ：返回步骤二。 ( 5 ) ：到达时间采样点的终点，结束( 其实还应包含碰撞响应，但 这里不考虑) 这里的关键是步骤( 1 ) 和步骤( 3 ) ，下面用两小节的内容进行阐述。 2 4 包围盒树的构建 对给定的n 个基本几何元素的集合s ，定义s 上的包围盒层次结构 b v t ( s ) 为一棵树，简称包围盒树。其中结点v 的所有予结点所对应的基 本几何元素的子集合构成了对v 所对应的基本几何元素的子集s 。的个 划分。图2 4 所示为一个二维空间中的包围盒层次结构示例，其包围盒 类型为圆，基本几何元素为线段。进行计算时用圆形代替各层次的对象 就会简单：图a 为第一层包围盒，它包含了对象的所有基本几何元素； 图b 是第二层包围盒，它将所有基本几何元素分为三部分，并分别为它 青岛大学硕士学位论文 们建立包围盒；图c 以第2 2 层的每个节点为根，继续将它们所含的元素 进行分裂，并分别建立包围盒，它是最后一层包围盒，因为它的每个包 围盒只包含个基本几何元素一线段。由图可知，通过构造层次结构， 可以越来越逼近对象的几何特征。 t o p 删 s e c c n i dh 函 b ) l e a fl e v e l ( c ) 图2 4 包围盒层次 通常有两种方法来构造包围盒树，自顶向下【4 0 】和自底向上 4 1 】方法 2 4 1 自底向上方法 自底向上方法是从集合s 的基本几何元素出发，每个元素对应个叶 节点，然后利用任何局部信息递归地对它们进行分组归并，形成父节点， 直到得到一个单一的根节点( 即集合s ) 。自底向上方法的核心是如何把 若干个集合归并为一个父集。 1 0 第一二章传统的层次包围盒方法 2 4 2 自顶向下方法 自顶向下以全集s 作为根节点，利用基于全集的信息递归地对这个节 点进行划分以形成其子节点，直到到达叶节点，即如何把一个集合划分 成若干个子集。这里涉及到一个问题树的度，即树的最大子节点数，大 多数情况下选择树的度为2 ，本文的所有算法都采用度数为2 。自顶向下 方法的核心是如何把一个集合划分成若干个不相交的子集，相对而言， 自硕向下的方法在碰撞检测中使用得较多，技术更成熟一些，也比自底 向上的方法更为健壮更易实现，因此本文的算法采用这一方法构造包围 盒树。图2 5 是一个自顶向下的例子。 2 4 3 分裂平面 图2 5 自顶向下构建包围盒 自顶向下的关键是把一个集合分解成两个不相交的子集，在构建包 围盒树的时候采用的是分裂平面的思想。分裂平面是一个平面，它可以 把整个空间划分为两个闭半空间，一个基本几何元素或者属于平面的左 半空间；或者属于平面的右半空间；或与平面相交，跨越这两个半空间 1 l 青岛人学硕士学1 1 i 7 ：论文 ( 如基本几何元素为三角形，还可能在平面内) 。对于前两种情况可以 很自然的把它们划分到两个不同子集中，而对后一种情况可以根据其中 心的位置来判断，即根据中心点在平面的哪一侧来决定，如中心点恰好 位于平面上，那么将它分配给所含元素较少的子集。如图2 6 1 ；) f 示。 h 鞭，蛐1 卜 怠 磐 车赣 图2 6 基于分裂平面的划分方法 分裂平面的选择可以通过两个步骡来完成，第一步是选择分裂轴， 第二步是选择分裂点。 ( 1 ) 确定分裂轴：通常使用最长轴方法，即选择方向轴使得包围盒 沿轴线方向最长，对于本文采用a a b b 包围盒该方法仅需要两次比较即可 确定，简单快速。 ( 2 ) 确定分裂点：选择好与分裂平面正交的轴线后，必须确定分裂 点以定位分裂平面，有两种方法： a 中值方法1 4 2 1 ：选择集合中所有基本几何元素的表现点在分裂轴上 的投影的中值。该方法简单快速，而且可以得到两个大小相等的子集， 从而得到棵基本平衡的包围盒树，尤其当集合中的基本几何元素大小 相差不多时，该方法更有效。 b 平均值方法【4 3 1 ：选择集合中所有基本几何元素的表现点在分裂轴 上的投影的平均值。此方法通常可以使子结点的包围盒体积更小，从而 提高了碰撞检测的速度；但使树的平衡性有定的伤害，使构造树的时 1 2 第二章传统的层次包围盒方法 间增加。 2 5 包围盒树的更新 在每个时间点当物体的位移发生变化时，该物体的包围盒树也应发 生相应的变化。包围盒树的更新也是在碰撞检测算法最耗时的操作，因 此应该避免对整棵树的重新构建而应该更新这棵树。这里应考虑两种情 况，分别为刚体对象和变形体对象的包围盒树更新。对于刚体对象的包 围盒更新，由于顶点之间的相对位移不发生任何变化，因此只需要考虑 平移和旋转两种情形。而对于变形体对象情况则复杂的多，因为又分为 两种情况即拓扑结构改变和拓扑结构不改变两种情形。 2 5 1 刚体对象运动后的包围盒树更新 对象的运动分为平移和旋转两类3 1 。运动对象可以在虚拟环境中进 行六个自由度的运动，其运动具有很大的任意性，尽管无法得到关于时 间的运动方程，但可以从输入设备得到当前时刻对象相对于原始状态的 位置参数和方向参数。 沿x 轴、y j i ；l t t 和z 轴的乎移参数，对应于个平移向量 3 】 t = ( x ，y ，z ) ，t 绕x 轴、y 轴和z 轴的旋转参数o 、由、1 l r ，对应于变换 矩阵： r o t ( x ，口) = r 1 00 1 oc o s 口一s i n 口l 【o s i n 口 c 。s 口j rc o sq 9 0 s i n p 010 l s i n 矿ue o s 妒j f c o s - s 洫矿0 1 s i n gc o s f 0 f l oo 1 j 1 3 青岛大学硕士学位论文 假设变换次序为绕z 轴、y 轴、x 轴旋转，则合成的旋转矩阵为： r = r o t ( x ，0 ) r o t ( y ，妒) r o t ( z ，) 10 = 10 c o s o 0s i n 0 l0 - - 10 c o s o os i n 0 c o s 妒c o s p = c o s o s i n v + s i n o s i n ( o c o s p , l s i n o s i n ；c ，- c o s o s i n 伊c o s - s i n p0 c o s v 0 01 -c嚣ospsinpvcos 5 i ? 0 s i nc o s c o s 习 妒 妒pp c o s o c o s p , 一s i n 臼s i n 妒c o s y s i n o c o s + c o s o s i n 9 ，c o s v s i n 妒 s i n 曰c o s p c o s o c o s oj 可以用一个变换x r x + t 描述对象从原始状态到目前状态的变化， 也可以分解为一个平移变换x x + t 和一个旋转变换x r x 。 对象平移运动后，对其包围盒进行同样的平移转换，即可得到新位 置处的包围盒。对象发生旋转以后，其新位置处的包围盒不能通过简单 的旋转得到。为了提高碰撞检测的效率，减少包围盒树更新的时间，对 不同的包围盒类型可以采用不同的更新方法。 对于a a b b 的更新1 1 1 ，这里采用一种近似法：先求出a a b b 最长边 的一半( 称为a a b b 的半径) ，用r a d i u s 表示，当a a b b 发生运动变换 以后，用中心到各边的距离为r a d i u s 的立方体来近似代替新位置处的 a a b b 包围盒，只要对原中心进行同样的变换x r x + t ，即得到新a a b b 包围盒的中心。这样做虽然所得的包围盒不是包围对象的最小的包围盒， 但不会影响碰撞检测的正确性，因为包围盒本身就是对被包围对象的近 似。这样做的坏处是可能增加检测的包围盒数目，好处是更新时间会大 大减少，相对于碰撞检测效率来说还是值得的。而对于o b b ，由于o b b 包围盒的性质，只需要对o b b 的中心作相应的平移和旋转即可。 在基于包围盒树的碰撞检测算法中，在每个时间点，并不需要对对 1 4 y m o 一 一 ll，llj 妒 妒 m 0 s co 0 妒 叩 o 量 c _，l1，00lj 旧口o 血 一 c 乏 一 一一 。舢础 第二章传统的层次包围盒方法 象的每一个节点都进行相交检测，在用一个对象的节点遍历另一对象树 的过程中，如果在某一个节点处发现它们的包围盒不相交，则该节点的 所有后代节点都不再需要进行相交测试，因此不需要对该对象的包围盒 树进行彻底的更新，而仅对需要进行相交测试的节点计算新的a a b b 包围 盒。 2 5 2 变形对象运动后的包围盒树更新 在变形体对象环境中1 3 ) ，刚体对象与变形体对象间的碰撞会导致变 形体对象的变形，对象自身属性的改变也会导致其形状的变化，具体表 现为组成对象的基本几何元素形状的改变和数量上的增减。而在预处理 阶段为对象构造的包围盒树是基于原始状态下对象的基本几何元素集台 的，而基本几何元素形状的改变导致原来的包围盒不再适用于当前的对 象，数量的增减导致原先的包围盒树中某些节点无效。为了得到正确的 碰撞检测结果，同时考虑到速度问题，重新构造包围盒树的代价太大， 我们希望能通过对包围盒树的快速更新来保证碰撞检测的正确性和实时 性，也就是说要使更新的包围盒尽可能的少，这样就提高了包围盒树的 更新速度。变形体对象的变形依据拓扑结构是否发生变化可分为两种， 即拉压变形和拓扑结构的变化，下面分别讨论这两种情况下变形体对象 包围盒树的更新： ( 1 ) 拉压变形是指在外力作用下【52 1 ，组成软体对象的某些基本几何元 素的位置和形状发生了变化，具体表现为基本几何元素顶点位移的变化。 对象发生拉压变形后，各元素变形的幅度不等，此时无法用一个变换函 数来统一描述整个变形。以a a b b 为例( 其他包围盒类型比如o b b 不具备 a a b b 的这一数学属性，本文后面会有具体的证明) ，处理方法是：首先 重新计算所有发生变形的基本几何元素的a a b b 包围盒，然后按照自底向 上的方法对包围盒树进行更新，通过两个子节点的包围盒更新其父节点 的包围盒，这种更新也是比较简单的，为两个a a b b 子节点求其父节点， 青岛大学硕士学位论文 只需要六次比较即可确定，即分别求出它们在x 、y 、z 三个坐标轴上投 影的最大、最小值。虚拟手术中拉压变形通常只使顶点发生轻微的位移， 且只发生在少数节点中，这样很有可能子节点的包围盒发生变化，但却 不会影响到父节点的包围盒。因此并不需要对所有节点作更新，只有当 一个节点的某个子节点的包围盒发生变化时才需向上更新。本文的第一 种方法正是利用了a a b b 的这个属性。 ( 2 ) 对象拓扑结构的变化是指组成对象的基本几何元素的集合发生 变化，包括：增加新的基本几何元素到集合中、从集合中去除某些基本 几何元素、某些基本几何元素发生分裂，产生新的基本几何元素。虚拟 手术的切割变形过程可能涉及到后两种变形。当从集合中去除某个元素 时，可以从包围盒树中删除相关的叶节点，并且用它的兄弟节点取代它 的父节点。因为是集合中的元素数减少，而所有前代节点上的包围盒依 然能够包围相应的基本几何元素的子集，只是它可能不是最小的包围盒， 又因为包围盒思想的本身就只是对所包围对象的一个近似，因此这样不 会产生错误的碰撞检测结果。 当集合中某个元素发生分裂时，由于该元素是所有新产生元素的并 集，所以它所在叶节点上的包围盒仍然是所有新元素的包围盒，因此， 只要在该叶节点上构造所有新产生元素的包围盒子树即可实现包围盒树 的更新。 1 6 第三章压缩的包围盒碰撞检测算法 第三章压缩的包围盒碰撞检测算法 3 1s o ld 算法 s o l id 【1 7 】采用的包围盒类型是a a b b ，一个物体的a a b b 是包围该物体 并平行于坐标轴的最小的六面体，计算一个物体的a a b b a 常简单，只需求 出构成物体的基本几何元素集合中每个元素的顶点坐标在x ，y ，z 轴上的 最大值和最小值即可。基于此特征，a a b b 具有一个非常好的数学特性， 父节点的包围盒完全可阻由其两个孩子节点的包围盒求出( s 0 1 id 采用的 是二叉树结构) 。s o l i d 算法也正是利用了这项特性来完成从叶子节点开 始的自底向上的动态更新，本文所提出的压缩算法也是基于此特性。下 面给出其数学证明。 设父节点的基本几何元素集合最= 巨，巨，e ，其左右孩子节点的 基本几何元素集合分别为k = 最，最，乓j ( 研 一) ，匙= 邑。e 。e 其中满足l 。n = o ，岛u r 。= 呢。父节点的a a b b 为爿( 最) ，其左右孩子节 点的a a b b 分别为a ( z 。) ，a ( r 。) a 设求基本几何元素集合e 的a a b b 包围盒的 操作为a ( e ) ，即需要证明a ( 4 4 ) u 4 r 。) ) = 爿( 最) 。由于求a a b b 包围盒在 三个坐标轴上的操作相同，不失一般性，以下只证明x 轴。设k 集合在x 轴上投影的最小值为x 。( l ) ，最大值为k 。( ) 。r 。集合在x 轴上投影的 最小值为以。( r ) ，最大值为k 。( r ) 。设最集合在j 轴上投影的最小值为 瓦m ( f ) ，最大值为瓦。( f ) 。由于k n = g ， 因此 以i n ( f ) = m i n 瓦。( 上) ，瓦。( r ) ) 。同理瓦。( f ) - - m a x x m 。( ) ，“。( r ) 。由于一 青岛大学硕士学位论文 个物体的a a b b 是用其基本几何元素在x ，y ，z 轴上的最大值最小值来存储 的，因此可以认为彳( ) = 工。( ) ，x m 。( ) ) ，爿( 啦) = 置。( r ) ，x 。( r ) 。 a ( a ( l e ) u a ( r 。) ) 操作就是在集合 x 。( 上) ，x 。( ) ，x 。，。( r ) ，爿。( r ) 中分别求 出最小值和最大值根据先前的叙述很明显就是瓦。( ，) 和瓦。( f ) ，即 爿( 疋) 。图3 1 给出了其图形表示a 3 。2 压缩算法 图3 1 包含左右子节点的a a b b 包围盒 在一般的应用中，为了指定包围盒的范围，四个字节的f l o a t 型浮点 数就能满足要求。因此每个节点需要6 日s i z e o f ( f l o a t ) = 2 4 个字节。一颗完 全二叉树摊序n 个基本的三角形面片恰好需要2 n 1 个节点。因此当三角 形面片的数量超过2 ”时，所需的节点数就会大于2 1 51 。此时为了增加 检索的效率，需要给每个节点添加两个四字节的分别指向左右子树的索 引。当节点是一个叶子节点时，则可以利用根节点不会被任何一个内部 节点索引的性质，可以令叶子节点的一个索引为1 ( 根节点的编号为i ) ， 另一个索引为三角形的编号。据此性质则可以迅速的定位叶子节点。此 时每个节点需要存储2 4 + 8 = 3 2 个字节。 前面已经证明父节点的a a b b 完全可以由其左右两个子节点的 a a b b 求出。这就意味着父节点和其两个子节点之间存在大量的数据冗 第三章压缩的包闸盒碰撞检测算法 余，两个子节点最多有6 个范围值不同于父节点。因此可以把冗余的值 只保存一份，这可以通过在父节点中增加一个字节的标志位来完成。 在此结构中，用一位来表示哪一个范围属于哪一个子节点。用“1 ” 表示这个范围值属于左子节点，“0 ”表示这个范围值属于右子节点。这 一共需六位，剩余的两位表示节点是否为叶子节点，“l ”代表是而“0 ” 则恰好楣反。约定在存储结构中，a a b b 盒是按照z ，y ，z 并按最小值最大 值依次排列。即表示为( x 。，x 。，r , o 。，z m l , z 。) 。 爿( k ) 2 ( 1 1 2 ，2 3 ，3 2 ，7 ，8 ，5 3 ，9 8 ) ，a ( r e ) = ( ! 7 ，1 0 9 ，一9 6 ，4 9 ，1 9 ，8 ，0 ) 很明显，此时4 ( 最) = ( 1 1 2 ，1 0 9 ，一9 6 ，7 8 ，1 9 ，9 8 ) 此时，父节点的存储结 构见表3 i 表3 1 父节点的存储结构 10011 oll 标志位( 一个字节) 范嗣值( 4 6 = 2 4 个字节) 左子节点或三角形索引 右子节点或三角形索引 ( 4 个字节) ( 4 个字节) 从父节点的标志位可以很容易识别它的范围值是取自左右子节点中 的那一个。比如表1 中的标志位的第四位为l ，第四位代表k ，这就代表 圪。取自左子节点，因此左子节点中的圪。= 7 ，8 就可以只在父节点中存储 一次。可以看出父节点中的标志位的前六位中0 和1 的个数是相同的。 1 9 青岛大学硕士学位论文 这并不是偶然现象，以图3 1 中的二维空间为例，父节点的 瓦m ，瓦。，圪。，圪。分别来自左、右、右、左子节点。但有两种特殊情况见图 3 2 ，图3 3 g b a f j 念冀移 梦妙 c d i 图3 2 左右子节点有一个相同值的a a b b 在图3 2 中左子节点a b c 的a a b b 包围盒为f g b e ，右子节点a c d 的a a b b 包围盒为j a h i ，父节点的a a b b 包围盒为j g b k 从图