（计算机软件与理论专业论文）基于kdops的碰撞检测及其算法改进研究.pdf

摘要 碰撞检测是计算机动画，物理仿真，计算几何，机器人学等领域的重要课题， 快速精确的碰撞检测对于提高虚拟环境的真实感和沉浸感有着非常重要的作用。 碰撞检测的研究目标是如何在很高的实时交互要求下完成对大量复杂物体的碰 撞检测。虚拟现实技术中有多种碰撞检测方法，其中层次包围盒方法使用较广泛， 它是用体积稍大且几何特性简单的包围盒来近似地代替复杂的几何对象，并通过 构造树状层次结构来逼近对象的几何模型，从而在对包围盒树进行遍历的过程 中，通过包围盒间的快速相交测试来及早地排除明显不可能相交的基本几何元素 对，只对包围盒重叠的部分进行进一步的相交测试。 本文着重研究了基于k - c l o p s ( k - d i s c r e t e o r i e n t a t i o np o l y t o p e s ) 包围盒的碰撞 检测方法，k - d o p s 包围盒是一种凸多面体，它的面由一些半空间所确定，这些半 空间的外法向是从k 个固定的方向中选取的。k - d o p s 可以看作是a a b b 的扩展， 它不但继承了凸包紧密性好的优点，同时也继承了a a b b 简单性好的优点，通过 调整固定方向集合的大小和取值，可以在紧密性和简单性之间达到一定的折衷。 对象运动后包围盒的更新是层次包围盒方法中的一个重要问题。根据固定方 向凸包的定义和性质，文中提出了一种基于线性规划的更新算法，不需要在构造 包围盒层次时增加任何额外的计算量和存储量，在对象运动后可以仅通过3 k 次 乘法得到更新后的包围盒。 关键词：碰撞检测，k - d o p s ，包围盒，包围盒层次结构，线性规划 a b s t r a c t r e a l - t i m ec o l l i s i o nd e t e c t i o ni sc o n s i d e r e da sa m a j o rc o m p u t a t i o n a lb o t t l e n e c ki n a c h i e v i n gi n t e r a c t i v es i m u l a t i o nf o rc o m p l e x e n v i r o n m e n t i th a sb e e ns t u d i e di nm a n y f i e l d s i n c l u d i n gr o b o t i c s ，c o m p u t e rg r a p h i c s ，c o m p u t e r - a i d e dd e s i g n ，a n d c o m p u t a t i o n a lg e o m e t r y t h eg o a l o fc o l l i s i o nd e t e c t i o ni st o a u t o m a t i c a l l yr e p o r t g e o m e t r i cc o n t a c tw h e n i ti sa b o u tt oo c c u ro rh a sa c t u a l l yo c c u r r e d t h e r ea r em a n y a l g o r i t h m s o fc o l l i s i o nd e t e c t i o n u s i n gi n v i r t u a l r e a l i t yt e c h n o l o g y h i e r a r c h i c a l b o u n d i n gv o l u m ea l g o r i t h mh a sb e e nu s e dw i d e l y , w h i c hi d e ai s t oa p p r o x i m a t et h e o b j e c tw i t h as i m p l e rb o u n d i n gv o l u m et h a ti sal i t t l e b i g g e rt h a nt h eo b j e c t b y b u i l d i n g h i e r a r c h i e s o n o b j e c t ，o n e c a no b t a i n i n c r e a s i n g l y m o r ea c c u r a t e a p p r o x i m a t i o n so f t h eo b j e c t s s od u r i n gt m v e r s i n gh i e r a r c h i c a lb o u n d i n gv o l u m e ，i t s p e e d su p c o l l i s i o nd e t e c t i o nb yg e t t i n gr i do f p r i n i t i v ep a i r s ，w h i c hw i l ln o ti n t e r s e c t c l e a r l yt h r o u g hr a p i di n t e r s e c t i o nt e s tb e t w e e nb o u n d i n gv o l u m e sa n dj u s td e a lw i t h t h o s ew h o s eb o u n d i n gv o l u m ei si n t e r s e c t e d i nt h i sp a p e r , w ea n a l y z eam e t h o d ，b a s e do nk d o p s “k d i s c r e t eo r i e n t a t i o n p o l y t o p e s b o u n d i n gv o l u m e ，ac o n v e xp o l y t o p ew h o s ef a c e t s a r ed e t e r m i n e db y h a l f s p a c e sw h o s eo u t w a r dn o r m a l sc o m ef r o mas m a l l f i x e ds e to fko r i e n t a t i o n s k d o p sc a nb es e e na s a ne x t e n s i o no f a a b b ，i ti n h e r i t sn o to n l yt h et i g h t n e s so f c o n v e xh u l l ，b u ta l s ot h e s i m p l e n e s so fa a b b ：i to v e r c o m el i m i t a t i o n s o fo t h e r b o u n d i n gv o l u m e st h r o u g ha d j u s t i n gt h e f i x e ds e to fko r i e n t a t i o n sa n dm a k e sa p r o m i s eb e t w e e nt i g h t n e s sa n ds i m p l e n e s s u p d a t i n gb o u n d i n g v o l u m e sa f t e rr o t a t i o ni sa ni m p o r t a n t p r o b l e m o f h i e r a r c h i c a l b o u n d i n gv o l u m ea p p r o a c h a nu p d a t i n ga l g o r i t h mb a s e do nl i n e a rp r o g r a m m i n gi s p r o p o s e di nt h i sp a p e rb a s e do nt h ed e f i n i t i o na n dp r o p e r t yo f f i x e dd i r e c t i o nh u l l s t h i sm e t h o dn e e dn o ta d da n ya d d i t i o n a lc o m p u t a t i o na n dm e m o r yd u r i n gb u i l d i n g b o u n d i n g v o l u m eh i e r a r c h i e s i tc a n u p d a t e a b o u n d i n g v o l u m e t h r o u g h 3 k m u l t i p l i c a t i o n k e yw o r d s ：c o l l i s i o nd e t e c t i o n ，k - d o p s ，b o u n d i n gv o l u m e ，b o u n d i n g v o l u m e h i e r a r c h i e s ，l i n e a rp r o g r a m m i n g 第一章引言 第一章引言 1 1 课题背景及其意义 碰撞检测是计算机动画，物理仿真，计算几何，机器人学，c a d c a m 等领域的重 要课题【“，在虚拟环境中，由于用户的交互，物体问经常发生碰撞，为保持虚拟环境的 真实感和用户的沉浸感，快速精确的碰撞检测是必不可少的，虚拟环境中通常包含大量 物体，物体的形状复杂，由于虚拟环境有很高的实时交互要求，对大量复杂的物体的碰 撞检测必须在很短的时间内完成，因此碰撞检测往往成为虚拟环境与其他实时仿真系统 的一大瓶颈，碰撞检测的研究目标是如何在很高的实时交互要求下完成对大量复杂物体 的碰撞检测。 实时性和精确性是碰撞检测的两个重要条件。就实时性而言，针对虚拟环境中的视 觉显示要求碰撞检测的速度至少要达到2 0 h z ，而针对虚拟环境的触觉显示要求，碰撞 检测的速度至少要达到3 0 0 h z 才能维持触觉交互系统的稳定性，要达到1 0 0 0 h z 才能获 得平滑的效果。精确性则取决于具体的应用。 现在虚拟环境中的碰撞检测问题已超越了传统的计算机图形学的研究范围，有其新 的特点和新的要求一个大型的复杂的虚拟环境，如虚拟手术系统1 2 3 】，不仅对碰撞检 测的精度和实时性要求很高，而且通常会涉及到刚体和软体两类模型，每一个虚拟对象 的几何模型都是由成千上万个基本几何元素( 如四面体或三角形) 组成的，虚拟环境的 几何复杂度使得碰撞检测的计算复杂度大大提高。虚拟手术仿真是虚拟现实技术在医学 领域的一个重要应用，对虚拟手术仿真的研究旨在通过精确的器官造型( 几何建模及物 理建模生理建模) ，来逼真地模拟人体组织在外力交互作用下可能发生的变形乃至被切 割或发生碎裂的过程，并通过视觉力学反馈系统及其它可能的感官反馈形式，给用户 提供真实的手术现场的感觉。它不仅可以作为手术培训的模拟器，而且可以用于分析验 证手术方案的可行性，还可以预演手术过程以便及早地发现问题。 虚拟手术仿真系统的目标是提供给用户身临其境的沉浸感和完善的交互能力，为了 达到这一目标，理论上要求视觉反馈的带宽在2 0 h z 以上，触觉反馈的带宽在3 0 0 h z 以 上。这就要求系统必须能够实时计算并显示人体组织在外力作用下的变形分裂，以及相 关的一些生理特征，而碰撞检测是计算软组织变形和分裂的先决条件，只有判定手术器 械与人体组织发生接触后，才有必要实施变形的计算以及切割、缝合等操作，只有根据 碰撞检测的结果，才能准确地计算模型的变形。因此，碰撞检测贯穿于手术仿真的整个 青岛大学硕士论文 过程，精确实时的碰撞检测对虚拟手术的实现起着至关重要的作用 1 2 本文的工作重点 本文实现并验证了一种基于k - c l o p s ( d i s c r e t eo r i e n t a t i o np o i y t o p e s ) 包围盒层次的碰撞 检测方法，为解决复杂环境中的碰撞检测问题提供了一条有效的途径。k - d o p s 是一种特 殊类型的凸包，它由一组半空间决定，这组半空间的外法向来自于k 个固定方向的方向 集。k d o p s 可以看作是a a b b 的扩展，它不但继承了凸包紧密性好的优点，同时也继 承了a a b b 简单性好的优点，通过调整固定方向集合大小和取值，可以在紧密性和简 单性之间达到一定的折衷。 对几种利不同的k - d o p s 包围层次树构造包围盐的方法进行了比较 活动对象运动后包围盒树的更新是虚拟环境中碰撞检测问题的一个重点，以往的 近似法和爬山法都需要在构造包围盒树时增加额外的计算和存储空间，并且在对象运动 后的包围盒更新算法中计算量也比较大。对象的运动通常可用一旋转矩阵和一平移向量 来描述，根据k - d o p s 的定义，我们引入线性规划的思想。根据线性规划的一些基本定 理，对问题进行简化计算。我们的方法不仅在构造树时不需要任何额外的时空开销，而 且在更新包围盒时速度较以往的方法有很大的提高。 1 3 国内外研究动态 1 3 1 近几年的研究热点 1 、空间剖分法【4 】：将整个虚拟空间划分成相等体积的小单元格，只对占据同一单元格或 相邻单元格的几何对象进行相交测试。适用于物体在空间中均匀分布的稀疏环境，比较 典型的方法有八叉树和b s p 树【5 1 。一般来说空间分解算法在每次碰撞检测时都需要确 定每个模型占有的空间单元，如果场景中不可动的模型很多，可以预先划分好空间单元 格并确定每个模型占有的空间单元，当有模型运动时，只需重新计算运动模型所占有的 空闻就可以了。所以该方法通常适用于类似物体在障碍物之间飞行这样的虚拟场合。 2 、距离跟踪法：通过寻找和跟踪两个多面体之间的最近点来计算它们之间的距离，当 距离小于等于零时，发生碰撞。当物体的运动速度不快，相邻帧间运动物体的位移变化 很小时，可以利用桢间的连续性来增量式的计算物体间的距离。常用方法有l i n - c a n n y 算法，e n h a n c e dg j k 算法【2 7 】( 2 劬 3 、基于图像空间的碰撞检测方法【3 ”，一般将三维几何物体通过投影绘制到图像平面上， 降维得到一个二维的图像空间：然后分析该空间中保存在各类缓存的信息；进而检测出 2 第一章引吉 物体之间是否发生干涉。基于图像空间的碰撞检测方法最初由于检测结果的不精确性和 对图形硬件要求过高一直发展较慢，近年来，随着图形硬件卡加速技术的快速发展，研 究人员结合基于物体空间的碰撞检测方法中的一些技术，使得基于图像空间碰撞检测技 术有了新的发展。s h i n y a 等和r o s s i g n a c 等 3 0 做了这方面的开创性工作，提出了简单 有效的干涉检测算法，但要求有特殊的图形硬件来支持；m y s z k o w s k i 等【”峰提出的算 法更为实用，能够处理较复杂的实体；b a c i u 等【3 2 】在r e c o d e 算法中仅采用了深度缓 存和模板缓存，使算法可应用于常规的图形工作站，甚至只具有低端图形卡的p c 机值 得指出的是，上述算法均未能有效地处理非凸的复杂物体，而且所采用的绘制方法也比 较基础，性能不够理想。 4 、包围盒法 6 】：包围盒法被广泛运用于对光线跟踪8 】和求交运算的加速，核心思想利 用体积略大而几何特性简单的包围盒将复杂几何对象包裹起来，在进行碰撞检测时，首先 进行包围盒之间相交测试，只有包围盒相交时，才对其所包裹的对象，做进一步求交计算。 通过构造树状层次结构( 又称包围盒树) 逐渐逼近对象的几何特性。与个物体相对应 的层次结构的节点是空间上包围该物体一部分几何对象的几何近似体：层次结构的根节 点包围了整个物体，每个父节点包围的几何对象是它的所有子节点包围的几何对象之 和，节点从上到下逐渐遥近它包围的几何对象，进行重叠测试时首先判断两包围盒树的 根节点是否相交，如相交则进一步判断它们的子节点相交情况，如最后有相交的叶节点 对，判断每对叶节点包围的基本几何对象是否相交。这种方法也称为混合碰撞检测算法 1 1 3 1 “】一即宽带与窄带相混合的方法，即把快速排除不相交部分的过程称为宽带过程， 而把叶子节点所包围的几何对象进行精确测试以定位碰撞部位的过程称为窄带过程。这 一方法只需对包围盒重叠的部分进行进一步的相交测试，从而可以大大减少参与相交测 试的包围盒的数目，提高碰撞检测的效率。 1 3 2 选择包围盒形状的设计准则 为了评定碰撞检测的性能，我们引入一个代价函数，它最初是w e g h o r s t 、h o o p e r 和g r e e b e r g 在对光线跟踪的研究1 0 1 1 1 中提出的，用以帮助分析包围盒的层次结构的 性能。g o t t s c h a l k 、l i n 和m a n o e h a 在碰撞检测中引用了同样的代价函数以评定碰撞检 测算法的性甜“1 碰撞检测的总耗费f = n u 4 c u + n b v 4c b v + n p + c p n u ：物体运动后包围盒层次中需要修改的节点数。 c u ：修改一个节点的耗费。 名一 青岛大学硕士论文 n b v ：参与重叠测试的包围盒的对数。 c b v ：为一对包围盒作重叠测试的耗费。 n p ：参与求交测试的集合元的对数。 c p ：为一对几何元做求交测试的耗费。 1 。3 3 常用包围盒的比较 常用的包围盒法有s p h e r e ，a a b b ，o b b ，k d o p s 。 1 、s p h e r e ：( 包围球法) 对象的包围球( s p h e r e ) 【1 5 【1 6 ”】被定义为包含该对象的最小的球体，包围球可表示 为 r = ( x ，y ，z ) i ( x - c 。) 2 + ( y c 茹2 + ( z c z ) 2 v - c l i p 【3 7 】：是一个跟踪计算两个多面体间距离的算法库，对l i n c a n n y 算法作了改 进，除了可以检测出两物体间的距离外，还可以报告两物体的穿透位置，及发生。 穿透的物体间的近似距离 2 、可处理非凸物体 r a p i d 3 8 1 ，v - c o l l i d e 3 9 】：精确检测两个物体间碰撞的库，使用o b b t r e e 算法， 输入模型为多变性汤，即物体模型是一组无结构的多变形，不包含任何连接信息和 拓扑约束，适于检测两个距离非常接近的刚体的碰撞。 q u i c k c d 4 0 l ：采用k d o p s 算法，适合检测一个物体在另一个环境中漫游所发生 的碰撞，输入模型是多边形汤。 s o l i d 4 1 1 ：采用a a b b 算法，用于检测多个物体间的碰撞情况，输入是多面体或 多边形汤，是和处理可变形物体的碰撞检测。 7 第二章基于k - d o p s 的包围盒层次结构 第二章基于k - d o p s 的包围盒层次结构 2 1 k - d o p s ( d i $ c r e t eo f i e n t a t i o l 3p o i y t o p e s ) 的定义 d i s c r e t eo r i e n t a t i o np o l y t o p e s ( kd o p s ) 包围盒是一种多面体，它的面由组半空 间h 。所确定，这些半空间的外法向是从k 个固定的方向( d 1 ，d l 【) 中选取的。 设固定的方向集k ( d ，d k ) ，一元组( d 1 - ，d k ) r k ， 其中： x l d i x 叠i ，i = 1 ，k = n ：l 髓 半空间h i = x e r j d j x 到) 在设计k o p s 时，为使相关的耗费尽量减小，通常只选择那些共线但方向完全相 反的向量作为固定法向，因此，每个k _ d o p s 实际上只用到k 2 个方向，即 d 1 + k ，2 = d i x i d i ，x a i ，i _ 1 ，k ，一k ：1 1 2 s t s i = x r 3 1 - d j 妣如。x 口 和 h l ： x r nld t x c t ) 及hl = x r “id l x 0 ；当且仅当a 、b 、c 呈顺时针顺序排列时有d 嘣a ，b ，c ) 0 ；当且仅当a 、b 、c 共线时，d e t ( a ，b ，c ) = o 。 设有顶点坐标已知的a a b c 和a p q r ，为a a b c 的支撑超平面。按以下步骤判 断它们是否相交。 1 ) 判断a p q r 是否与v 相交 如果a a b c 和a p q r 相交，贝j j a p q r 的三个顶点必然位于a a b c 的支撑超平面掣的 两侧，这是因为平面v 将空间分成两个不相交的开半空间v l 和矿r ，y l n 霍= 中，矿r t 7 皿= 中。三角形是三维空间中的一个有界的闭集，如果顶点p 、q 、r 位于某一个开半 空间中( 位于掣的同一侧) ，卿j a p q r c 矿l 或a p q r c 少r ，而a a b c c ，赦a p q r 青岛大学硕士论文 与a a b c 不相交。 计算v 的法线元= 一a b 牙= ( 云一i ) ( j 一西) ，令s p = i 否 s q = i 4 q ，s r = 元a r ，判断 a 如果s p ，s q 和s r 同时为正或同时为负，则顶点p 、q 、r 位于的同一侧，a a b c ： h a p q r 不相交： b 如果它们全部为0 ，贝1 a a b c 和a p q r 共面，可转化为二维平面空间中的三角 形的相交测试，见3 5 3 ： c 如果有一个为0 ，另外两个符号相同，。则p q r 的一个顶点位于平面v 上，要 么这两个三角形不相交，要么相交在该顶点上。此时转化为二维平面空间中判断该顶点 是否位于a a b c 的内部，见3 5 3 ； d 如果有两个为0 ，j t l s p 和s q ，则p q r 的一条边p q 位于平面上，要么这两个 三角形不相交，要么相交在p q 上。此时转化为二维平面空间中线段与三角形间的相交 测试，见3 5 3 ； e 否则p q r 与v 相交，进入步骤2 ) 继续测试。 2 ) 计算a p q r 与的交点 顶点p 、q 、r 位子v 的两侧，假设q 和r 同侧，则线段v q 、线段p r 与掣相交，其交 点即为a p q r 与v 的交点。 线段尸q 上的点可表示成如下向量形式p + t p q ，其* o - t - 0 1 当且仅当顶点a 、b 、c 呈顺时针顺序排列时有d e t ( a ，b ，c ) 0 ，定义点r 位于f g 的右侧是指f ，g ，r 呈顺时针 j 顿序j j 列，即满足d e t ( f ，g ，l ) o 。 a 如果顶点a 、b 、c 位于直线f g 的同一侧，则线段f g 与a a b c 不相交； b 否则，假设a 、b 位于一侧，而c 位于另一侧，a c 、b c 分别与直线f g 相交。 如果f 和g 同时位于b c 的右侧或者同时位于c a 的右侧( a ，b ，c 按逆时针顺序) ，则 线段f g 与a a b c 不相交；否则相交。 3 ) a a b c 和a p q r 的相交测试 二维平面中两个三角形不相交当且仅当存在某一个三角形的一条边，使得另一个三角 形的三个顶点均位于这条边的右侧( 三角形的顶点按逆时针顺序排列) 。因此，我们只 需依次测试寻找这样的一条边即可，如果不存在这样的一条边，则这两个三角形相交。 2 5 第四章包围盒树的更新 第四章包围盒树的更新 虚拟环境中对象运动或变形后，其原来的包围盒树会不再适合要求，必须进行更新， 有两种方法来完成包围盒树的更薪：重新构造包围盒树和只对包围盒树中的部分包围盒 进行更新，前者比后者要多花费大量的宝贵时间。同时根据时空相关性，虚拟环境中的 运动对象通常在每个时间采样点上都会由于运动而产生位置和状态的变化，但相邻时间 点的变化一般不大：对象的变形通常也只发生在部分基本几何元素中，为保证碰撞检测 的实时性，必须在最少的时间内完成包围盒树的更新。因此通常选择后者来处理对象运 动或变形后包围盒树的更新。 41 对象的运动表示 虚拟环境中对象平移或旋转后，其原来的包围盒树会不再适合要求，必须进行更新， 有两种方法来完成包围盒树的更新：重新构造包围盒树和只对包围盒树中的部分包围盒 进行更新，前者比后者要多花费大量的宝贵时间。同时根据时空相关性，虚拟环境中的 运动对象通常在每个时间采样点上都会由于运动而产生位置和状态的变化，但相邻时间 点的变化一般不大：为保证碰撞检测的实时性，必须在最少的时间内完成包围盒树的更 新。因此通常选择后者来处理对象运动或变形后包围盒树的更新 对象的运动分为平移和旋转两类。运动对象可以在虚拟环境中进行六个自由度的 运动，其运动具有很大的任意性，尽管无法得到关于时间的运动方程，但可以从输入设 备得到当前时刻对象相对于原始状态的位置参数和方向参数。 沿x 轴、y 轴和z 轴的平移参数，对应于一个平移向量 t = ( x ，y ，z ) 7 绕x 轴、y 轴和z 轴的旋转参数0 、西、f ，对应于变换矩阵： r o t ( x , e ) ： 1 0 谢0 7 0 c o s 0 0s i n o js lc o s 目j r o t 包伊，忆0 呻0 0c o s 。p ( y ，伊) = l l i s i n 妒i 2 6 青岛大学硕士论文 假设变换次序为绕z 轴、y 轴、x 轴旋转，则合成的旋转矩阵为： = f 兰；：髫0 jl一o。o：sq妒i。si曼n妒pqj1csoi：syv-c薯sin缈v蟊 妊；：跏霹i 薨l c 。s q ，c o s y _ c o s 妒s i n v 8 i n t o 可以用一个变换x r x + t 描述对象从原始状态到当前状态的变化，也可以分解为一 个平移变换x x + t 和一个旋转变换x r x 。 对象平移运动后，对象的平移变换可表示x x + t ，因为k - d o p s 对向量加运算是封 闭的，它的b v - t r e e 中的各节点包围盒只要加上相应的平移矢量，即可得到新位置处的包 对象发生旋转以后，当物体旋转时，如果简单的采用旋转变换修改b v - t r e e ，会导 致手术刀包围盒与环境包围盒的k 个轴方向不一致，在这样两个层次间进行的重叠测 试的耗费远远大于两者轴方向一致的耗费。其新位置处的包围盒不能通过简单的旋转得 到。为了提高碰撞检测的效率，减少包围盒树更新的时间，对不同的包围盒类型可以采 2 7 第四章包围盒树的更新 1 、爬山法 爬山法1 4 “：在最初构造包围盒树的过程中，在计算每个结点时附加计算s v 的凸包，并 保存它的顶点信息，在对象旋转后，对它的凸包进行同样的旋转，然后对原来的kc l o p s 进行局部修改，修改方法是检查k 2 个轴向上的原来的最值顶点，如设上一步某轴向上 的最值顶点w ，将其与相邻顶点作比较，若w 是邻域中的最大值顶点，则不作修改，否 则，爬到沿轴向值增长最大的相邻顶点处，递归执行宜至找到极大值点。此方法利用了 各步间的相关性，对于较小的旋转来说，所花时间较少，最坏情况下的复杂度为o ( k 2 ) 。 该方法的缺陷是需要在每个结点r 上计算5 的凸包，这在很大程度上增加了构造 包围盒树的时间。计算只的凸包的时间为0 ( n l o g h ) ( 口ifi ) 。在对象旋转后计算包 围盒时，虽然减少了需要计算的顶点数，但对于复杂对象，其凸包的顶点数仍然很大。 而且对于不同结点，其凸包的形状和复杂度都是不同的，园此，在更新整个树的过程中， 各个结点的计算没有任何相同之处，必须单独处理每个结点，因此，时间开销仍然是很 大。 2 、近似法 近似法p ”：这种方法考虑计算旋转后的包围盒的包围盒，首先保存各节点在晟初位置 和方向上的k _ d o p s 的顶点v ( s o ，当s v 旋转时，计算旋转后的v ( s v ) 7 自点，对这些项 点直接计算出k，这种包含变换后的s v ，但不是其最小的。dops k f l o p sk _ d o p s 图8 显示用近似法求得的对象旋转后新的k - d o p s 包围盒。 固 图8 用近似法表示的物体旋转后的包围盘 由于 d o p s 包围盒是比对象简单得多的一个几何体，计算它的k - d o p s 的复杂度就 要小得多。相对于爬山法，近似法的速度更快一些。尽管它们都是用一个简单的几何体 一2 8 青岛大学硕士论文 代替基本几何元素的集合计算其包围盒，但由于k - d o p s 的几何复杂度要比凸包小得多， 因此，它的更新速度更快一些。尽管s t , h 法得到的是对象精确的k - d o p s 包围盒，但近 似法更新速度的提高足以弥补近似所增加的包围盒相交测试的开销。此外，它们都需要 在构造包围盒树时增加额外的计算，也需要额外的存储空间。近似法的开销要小一些， 计算k - d o p s 的顶点要比计算的凸包的顶点简单得多，其项点数目也要少得多 4 3 基于线性规划的方法 4 3 1 线性规划的基本概念和相关定理 1 、线性规划的标准形式 线性规划是数学规划的一个重要分支 。它在理论和算法上都比较成熟，在实践 中有着广泛的应用，很多实际课题也可以转化为线性规划问题。线性规划问题是求决策 变量在一组约束下的线性目标函数的最优解的问题 一般线性规划问题的标准定义形式如下： m i n 1 = 1 s t a j x j = b ti = l ，m ，矗 x j oj 2 1 ，n 用矩阵表示： m i nc t x s ta x = b ，x 0 其中4 为m x n 维矩阵，c 和了是n 维列向量，6 为州维列向量。通常工称为决策变量，c 称为价格系数，a 称为约束矩阵，c t x 称为目标函数。 若决策变量x = ( x 。，x 。) 的某个取值x = ( x 1 j ，x 。) 7 满足全部约束条件， 即：a x ，= b ，x 0 则称x 是a x = b 的一个基本可行解，所有可行解组成的集合k 称为a 盖= b 的可行域p = x l a x = b ，x 0 ) 一2 9 第四章包围盒树的更新 可行域p 中的每个可行解x 都对应了一个目标函数值，其中对应的目标函数值最小的 解妒称为最优解，相应的目标函数值c 7 x 。称为最优解。 2 、线性规划中的对偶问题 线性规划中普遍存在配对现象，即对每个线性规划问题，都存在另一个与它有密 切关系得线性规划问题，其中之一称为原问题，另一个称为对偶问题 对偶问题的表达形式： 原问题： m i nc t x s ta x = b ，x 0 对偶问题： m a xb t s ta 7 c 其中，a 、b 、c 的定义同原问题，w 为1 1 1 维列向量。 线性规划基本定理( 4 1 ) ：对于一个相容的标准型线性规划有可行域p ，它在p 上的极 小化目标值z = c t x ，或者是无下界的，或者至少在p 的一个顶点上达到 对偶定理( 4 2 ) ：如果原问题或对偶问题中任何一个存在有限的最优解，则另一个也 存在有限的最优解，且它们的目标函数最优值相等 4 32 线性规斟方法 前面讲道的近似法是一种广泛使用的方法，它适用于任何包围盒类型，但是在复杂 的虚拟环境中，活动对象很有可能随时加入或退出环境，故而需要实时构造k - d o p s 树，计算由1 3 _ 个超平面所确定k d o p s 的顶点的时间开销是十分大的，它会很大程度 上增加k - d o p s 树的构造时间，从而影响到整个系统的性能；再者为k - d o p s 树中每 个结点上包围盒存储其顶点信息需要额外的存储空间，因此这种方法仍具有很大的局限 性。考虑到k - d o p s 自身的一些特点，我们希望能直接根据最初定义它的k 个半平面， 计算出旋转后的k - d o p s 在各个方向上的最大延伸。 设当前变换为x r x + t ，r 为一单位矩阵，t 为向量。令b 为原始位置上结点v 的k - d o p s 包围盒的向量形式，k d o p s 中的点满足条件d x 1 0 使得 m d j o = a d j f - 1 则有 青岛大学硕士论文 d t j o u - 蒯乃= a i b j , i = 1i = l 又根据定理4 。2 得知此时有 故可得 b j o 砸如 b j o d t i o u 又因为u e p ，故有d u 一 b ，对d i o u = b j o 。因此顶点u 在支撑超平面j o 上，也就是说，如果 我们用d 5 0 u 代替问题4 3 中的任何一个方程，求得的顶点u 不会改变。因此我们不需 要考虑关于基( d ，破，吃) 的解，因为如果它是最优的，我们一定可以从别的基 得到，我们把这样的基称作冗余基，由于原问题中的基对应于对偶问题中的顶点，故对 应于冗余基的顶点在求解问题时也是没有用的，称之为冗余顶点。因此，我们只需求解 对偶问题中的非冗余顶点。 首先我们来分析一下对偶顶点的结构。d 7 是一个n k 的矩阵，r d 7 是行满秩的，我 们可以将d 1 中h 个线性独立的列组合成一个基b ，余下的k - n 歹u 称为非基。换言之，我 们可以如此排列d 1 = b 1 n 。我们也可以将任意解向量y 的分量按此相应顺序重新排列， 通常为y = y j y 一。对y b 中的每一个分量，如果它的对应列在基口中，我们称它为基变量， 相类似，孙中的那些分量被称为非基变量。因为历黾一个非奇异的n n 矩阵，我们总可 以将所有非基变量设置为零，即y ”= 0 ，以及对应于基变量来求解该约束方程毋e = c ， y b r “，y b o 。 44 算法流程 算法可以分为三步来进行 1 、寻找所有非冗余基 对任一基口= 矗，如，如) ，令下标集i = j ”j 2 ，。j 。 1 ，2 ，3 ，k ) ，如果 l i 。( 1 ，2 ，3 ，n ) i ，使得b - 1 d ，0 ，即存在d 。可以表示成b 的线性组和，且系数均为正， , l j b 为为冗余基。 2 、计算非冗余对偶顶点 对每个非冗余基b ，计算y = bc ，如果y o ，n y 为非冗余顶点，同时保存对应的基下标 第四章包围盒树的更新 集i 。值得注意的是，可行域q 的非冗余顶点有且只有一个，故它即为线性规划问题4 3 的最优解。对偶顶点不依赖特定的k - d o p s ，即在任一旋转位置，对所有的k - d o p s ， 非冗余顶点都是相同的，因此可以在每一步碰撞检测前预先计算； 3 、计算目标函数b y 由于原问题与对偶问题的目标函数最优值相等，故它也是原问题( 4 1 ) 的最小目标函 数值。故旋转后的k - d o p s 在方向趾的最大延伸为幻+ b r y 由此可见，由于t d = d y ，c = r d ，y = b c ，它们都不依赖于具体的k - d o p s ，可 以预先计算，而非冗余基更是可以在选定包围盒类型时就可以由固定方向集合d 计算得 到；对一个复杂的虚拟环境中，每个时间采样点上需要计算变换后的k - d o p s 的结点是 很多的，而这些预先统一的计算量则显得微不足道。故我们基于线性规划的方法在计算 变换后对象的k - d o p s 时只需要3 次乘法。 与爬山法和近似法相比较，该方法在构造k d o p s 包围盒树时，不需要增加任何额 外的计算和存储空间，而且在为每个需要和环境对象树中结点进行相交测试的结点计算 旋转后的k - d o p s 时，近似法需要3 t m ；k + 1 2 * m 次乘法( k = - i d t ，m = 结点在原始位置上 的k 。d o p s 的顶点数) ，而我们的方法只需要3 k 次乘法，当活动对象复杂度增高，活动 对象包围盒树中结点数增大时，算法的速度将会有明显的提高。 第五章碰撞检测i fz 的特殊问题 第五章碰撞检测中的特殊问题 5 1 时间步长问题的解决方法 时间步长问题的实质是计算频率问题，原因是在有些时间片中物体根本不可能发生 碰撞，故解决时间片问题的目标是避免不必要的时间片中的计算，主要手段是利用已知 物体运动参数，如速度和加速度，来预知物体未来顶碰撞的时间和位置，由此避免多余 的时间片的检测，其局限性是：必须预知物体的菜些运动参数。而虚拟环境中的应用一 般实时交互性很强，很难预先假设物体的运动形式。 为解决时间不长问题，有些算法采用四维几何，其中第四维表示仿真时间，如文献 【4 6 】推出带时间变量的函数来表达凸多面体如何随时间变化，这些函数的根就代表碰撞。 文献 4 5 】采用隔离分析法，快速识别和细化包含碰撞的时空域，但这一方法假定物体随 时间的运动预先完全可知，因此它不适用于虚拟环境这种交互应用。 有些研究者提出四维几何来估计运动物体的未来位置，但不假定物体的运动预先完 全已知，如文献 4 0 对物体的速度和距离定界：定义两个物体的相对速度的上限和它们 之间距离的下限。当碰撞无法发生时，就增大时间步长，但这一方法不能处理非线性运 动。 文献【4 7 】引入限时计算的思想，提出一种碰撞检测算法可在精度和速度之间进行均 衡，该方法是一种逐步求精的方法，算法的第一步是粗估阶段，该阶段利用物体加速度 的上限建立一组时空界，该时空界可以给物体未来的位置一个保守的估计值。根据对两 个物体的时空界求交，可以得到两个物体最早可能发生碰撞的时刻，在这一时刻到来之 前，算法不必检测两个物体的碰撞；当之一时刻到达时，算法对两个物体的包围球作重 叠测试，若无重叠则说明无碰撞，粗估阶段就为两物体计算一组新的时空界，并计算新 时空界的相交时；若两物体包围球有重叠，则称粗估阶段在最粗略情况下找到了两物体 的碰撞，此时，算法切换到精细阶段，该阶段逐步细化两物体在当前桢的碰撞检测精度， 即对两物体逐步采用更精细的近似表示来检测碰撞，在每一步细化后，精细阶段允许被 应用中断，以满足应用的实时性要求，这里，对每个物体的多精度近似表示是一个多精 度的包围球层次树，树的层次每加深一层，就对物体的逼近程度越高，树的根是包围整 个物体的包围球。当精细阶段检测到两物体没有碰撞，或被应用中断后，算法就用返回 粗估阶段。 青岛大学硕士论文 52 特殊应用的碰撞检测 5 2 ，1 可变性物体 可变形物体的几何元的位置或形状随着时间的推移而变化，这种变化与平移，旋转 这类运动相比更复杂，因为物体内部的几何元间的相对空间关系发生了变化。因而可变 形物体的碰撞检测的一个主要考虑的问题是如何在每次变形后快速更新所用的辅助数 据结构以便于变形后的物体相对应。 1 、a a b b 树算法 对于包围盒层次的碰撞检测方法来说，若运用于可变形物体，主要问题是在物体发 生变形时，如何使物体的包围盒层次结构得到快速的修改。文献”中提出一种采用 a a b b 的碰撞检测算法，它一方面改进了a a b b 包围盒重叠测试，另一方面提出当物 体变形对快速修改a a b b 的方法。 作者采用的a a b b 树是与o b b t r e e 类似的一种二叉树，但它的节点a a b b 是沿模 型的局部坐标系轴向的长方形包围盒，而o b b t r e e 中的节点哦o b b 是沿任意方向的长 方形包围盒。o b b 所占的存储空间相对较多，一个o b b 要用1 5 个标量表示，其中，9 个标量表示方向矩阵，3 个标量表示位置，3 个标量表示各方向的长度；而一个a a b b 由于方向是固定的，只要6 个标量表示位置和各轴向的长度。 a a b b 树采用自项向下递归剖分的方法构造。在每一步递归中，计算当前几何元集 的最小a a b b ，并选择个剖分平面对当前几何元集进行划分，如此递归反复，寅到每 个划分子集中只包含一个几何元。因