（计算机科学与技术专业论文）虚拟环境中碰撞检测问题的研究.pdf

国防科学技术大学研究生院学位论文 摘要 碰撞检测问题在机器人运动规划、计算机图形学等领域中有很长的研究历史， 近年来随着虚拟现实、分布交互仿真等技术的兴起，碰撞检测，特别是软体碰撞检 测问题开始成为研究的热点。精确的碰撞检测对提高虚拟环境的真实性、增强虚拟 环境的沉浸感有着至关重要的作用，而虚拟环境自身的复杂性和实时性又对碰撞检 测提出了更高的要求。 层次包围盒方法是解决碰撞检测问题固有时间复杂性的一种有效的方法，它是 用体积略大而几何特性简单的包围盒来近似地描述复杂的几何对象，并通过构造树 状层次结构来逼近对象的几何模型，从而在对包围盒树进行遍历的过程中，通过包 围盒间的快速相交测试来及早地排除明显不可能相交的基本几何元素对，而只对包 围盒重叠的部分元素进行进一步的相交测试，以提高碰撞检测的速度。包围盒类型 的选择是层次包围盒方法的基础和关键。 本文以虚拟手术仿真为应用背景，着重论述了一种基于固定方向凸包包围盒层 次的碰撞检测方法。固定方向凸包是一种特殊类型的凸包，它的所有面方向都来自 一个固定的方向集合，它克服了以往包围盒类型的缺点，在紧密性和简单性之间达 到了一定的折衷。本文在充分研究了固定方向凸包的固有特性的基础上，开发并证 明了它适用于复杂环境中软体碰撞检测的性质，并着重解决了包围盒间的相交测试、 对象运动后包围盒的更新、对象变形后包围盒树的更新等问题。 文中提出并证明了一种快速区间测试法以解决两个固定方向凸包包围盒问的相 交测试问题，通过查找两个包围盒在由固定方向集合所定义的方向轴上的范围区间 是否存在不重叠的情况，来判断它们是否不相交。通过这种简单的区间测试法，两 个包围盒间的相交测试最多只需要k 次比较运算( k 为固定方向集合的大小) 。 对象运动后包围盒的更新是层次包围盒方法中的一个重要问题。根据固定方向 凸包的定义和性质，文中提出了一种基于线性规划的更新算法，不需要在构造包围 盒层次时增加任何额外的计算量和存储量，在对象运动后可以仅通过3 k 次乘法得到 更新后的包围盒。 对象变形后的处理是碰撞检测问题的一个难点。本文在对几种变形情况进行分 析的基础上，分别提出了相应的解决方法，并着重提出了一种自底向上的包围盒树 快速更新算法，通过k 次比较运算由子结点的包围盒得到父结点的包围盒，以解决 拉压变形和拓扑变化后包围盒树的更新问题。 此外，本文在充分开发和利用虚拟环境中对象运动的时空相关性的基础上，提 出了加速对象间碰撞检测速度的遍历跟踪策略。这是个启发式的策略，通过跟踪 第1 页 国防科学技术大学研究生院学位论文 上一时间采样点对包围盒树的遍历过程，确定当前时间采样点的遍历路径，从而有 效地减少了遍历过程中包围盒相交测试的次数，提高了算法效率，同时通过对跟踪 表的维护，保证了碰撞检测的正确性和有效性。 实验结果和具体应用表明，基于固定方向凸包包围盒层次的碰撞检测方法不仅 能很好地解决刚体间的碰撞检测，而且为解决和处理软体对象环境中的碰撞检测闯 题提供了一种可靠而有效的途径。本文的研究成果，对大规模复杂环境中的碰撞检 测有重要的理论价值和实际意义。 关键词：碰撞检测，包围盒，固定方向凸包，空间分解，层次包围盒，线性规划 第1 1 页 国防科学技术大学研究生院学位论文 a b s t r a c t c o l l i s i o nd e t e c t i o nh a sb e e nr e s e a r c h e di nm a n yf i e l d ss u c ha sr o b o tm o t i o np l a n n i n g a n dc o m p u t e rg r a p h i c sf o ral o n gt i m e i nt h el a t e ry e a r s ，w i t ht h er i s i n go fv i r t u a lr e a l i t y a n dd i s t r i b u t e di n t e r a c t i v es i m u l a t i o n ，m a n yr e s e a r c h e sf o c u so nc o l l i s i o nd e t e c t i o n ， e s p e c i a l l yc o l l i s i o nd e t e c t i o nw i t hf l e x i b l eo b j e c t s e f f i c i e n ta n de x a c tc o l l i s i o nd e t e c t i o n i sv e r yi m p o r t a n tt oi m p r o v er e a l i t ya n de n h a n c ei m m e r s i o nf o rv i r t u a le n v i r o n m e n t ，a n d t h ec o m p l e x i t ya n dr e a l - t i m eo fv i r t u a le n v i r o n m e n tb r i n gn e wr e q u i r e m e n tt oc o l l i s i o n d e t e c t i o n b o u n d i n gv o l u m eh i e r a r c h yp r o v i d e sa ne f f e c t i v em e t h o dt or e s o l v et h ei n t r i n s i ct i m e c o m p l e x i t yi nc o l l i s i o nd e t e c t i o n t h ei d e ab e h i n di ti st oa p p r o x i m a t et h eo b j e c tw i t ha s i m p l e rb o u n d i n gv o l u m et h a ti sal i u l eb i g g e rt h a nt h eo b j e c t i nb u i l d i n gh i e r a r c h i e so n o b j e c t ，o n ec a no b t a i ni n c r e a s i n g l ym o r ea c c u r a t ea p p r o x i m a t i o n so ft h eo b j e c t s s od u r i n g t r a v e r s i n gb o u n d i n gv o l u m eh i e r a r c h y , i ts p e e d su pc o l l i s i o nd e t e c t i o nb yp r u n ea w a y p r i m i t i v ep a i r s ，w h i c hw i l l n o ti n t e r s e c tc l e a r l yt h 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 n b o u n d i n gv o l u m e sa n dj u s td e a l 、i t l lt 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 t h e c h o i c eo f b o u n d i n gv o l u m ei st h eb a s i ca n dk e yp r o b l e mo f t h i sa p p r o a c h w i t ht h eb a c k g r o u n do fs u r g e r ys i m u l a t i o n ，t h i sp a p e rp r o p o s e sac o l l i s i o nd e t e c t i o n m e t h o db a s e do nf i x e dd i r e c t i o nh u l lb o u n d i n gv o l u m et r e e f i x e dd i r e c t i o nh u l l si sa s p e c i a lc o n v e xh u l l ，w h o s eo u t w a r dn o r m a lo f f a c e t sc o m e sf r o maf i x e dd i r e c t i o ns e t i t o v e r c o m el i m i t a t i o n so fo t h e rb o u n d i n gv o l u m e sa n dm a k e sap r o m i s eb e t w e e nt i g h t n e s s a n ds i m p l e n e s s b a s e do nr e s e a r c h i n ga n dd e v e l o p i n gi n t r i n s i cc h a r a c t e ro ff i x e dd i r e c t i o n h u l l s ，t h i sp a p e rd e v e l o p sa n dp r o v e st h ep r o p e r t yw h i c hm a k ei tc a nb ea p p l yt oc o l l i s i o n d e t e c t i o ni nc o m p l e xe n v i r o n m e n ta n dr e s o l v e st h ep r o b l e m sa b o u ti n t e r s e c t i o nt e s t s b e t w e e nb o u n d i n gv o l u m e s ，u p d a t i n gb o u n d i n gv o l u m e sa f t e rr o t a t i o na n du p d a t i n g b o u n d i n gv o l u m eh i e r a r c h ya f t e rd e f o r m a t i o n t h i sp a p e rb r i n g sf o r w a r da n dp r o v e sar a p i di n t e r v a lt e s tf o rr e s o l v i n gi n t e r s e c t i o n t e s t sb e t w e e nb o u n d i n gv o l u m e s i td e t e r m i n et w ob o u n d i n gv o l u m ed on o to v e r l a pb y c h e c k i n gi fo n eo ft h e i rb o u n di n t e r v a l so nd i r e c t i o na x i sd e f i n e db yt h ef i xd i r e c t i o ns e t d o e sn o to v e r l a p t h u st h ei n t e r s e c t i o nt e s tb e t w e e nt w ob o u n d i n gv o l u m e sn e e do n l ya t r f , o s tkc o m p a r i s o n s ( ki st h es i z eo ff i x e dd i r e c t i o ns e t ) u p d a t i n gb o u n d i n gv o l u m e sa f t e rr o t a t i o n i sa ni m p o r t a n tp r o b l e mo fh 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 第1 i i 页 国防科学技术大学研究生院学位论文 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 a yo ff i x e dd i r e c t i o nh u l l s t h i s m 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 gb 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 nu p d a t eab o u n d i n gv o l u m et h r o u g h3 km u l t i p l i c a t i o n d e f o r m a t i o no fo b j e c ti sad i f f i c u l t yi nc o l l i s i o nd e t e c t i o n t h i sp a p e ra n a l y s i st h r e e k i n d so fd e f o r m a t i o n sa n dp r o p o s er e s o l v i n gm e t h o dr e s p e c t i v e l y ab o t t o m u pu p d a t i n g m e t h o di sp r o p o s ee s p e c i a l l yw h i c hc a nc o m p u t et h eb o u n d i n gv o l u m eo fp a r e n tn o d e t h r o u g hb o u n d i n gv o l u m e so f t h et w oc h i l d r e nb ykc o m p a r i s o n f u r t h e r m o r e ，at r a v e r s et r a c i n gs t r a t e g yt h a tc a ns p e e du pc o l l i s i o nd e t e c t i o ni s p r o p o s e di n t h i sp a p e rb a s e do nd e v e l o p i n ga n du t i l i z i n gt e m p o r a l s p a t i a lc o h e r e n c ei n v i r t u a le n v i r o n m e n t t h i si sah e u r i s t i cs t r a t e g y i tc a nr e d u c et h ei n t e r s e c t i o nt e s t sn e e dt o b ec o m p u t e db e t w e e nb o u n d i n gv o l u m e sb yt r a c i n gt h et r a v e r s ep r o c e s si np r e v i o u st i m et o g a i nt r a v e r s ep a t hi nc u r r e n tt i m e t h ec o r r e c t n e s sa n dv a l i d i t yo f c o l l i s i o nd e t e c t i o nc a l lb e g u a r a m e e db ym a i n t a i n i n gt h et r a c i n gl i s t i th a sb e e ni l l u s t r a t e db ye x p e r i m e n tr e s u l t sa n dc o n c r e t ea p p l i c a t i o nt h a tt h em e t h o d b a s e do nb o u n d i n gv o l u m eh i e r a r c h yo ff i x e dd i r e c t i o nh u l lc a nn o to n l yr e s o l v ec o l l i s i o n d e t e c t i o nb e t w e e ns o l i do b j e c t s ，b u ta l s op r o v i d ea nr e l i a b l ea n de f f i c i e n tw a yt or e s o l v e a n dd e a lw i t hc o l l i s i o nd e t e c t i o ni nf l e x i b l ee n v i r o n m e n t t h er e s e a r c hi nt h i sp a p e r p r o v i d e sg r e a tt h e o r e t i c a lv a l u ea n dp r a c t i c a lm e a n i n gt oc o l l i s i o nd e t e c t i o ni nl a r g e - s c a l e c o m p l e xe n v i r o n m e n t s k e y w o r d s ：c o l l i s i o nd e t e c t i o n ，b o u n d i n gv o l u m e ，f i x e d d i r e c t i o n h u l l ，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 ，l i n e a rp r o g r a m m i n g 第1 v 页 第一章引言 碰撞检测问题在机器人运动规划、计算机动画等领域都有着悠久的研究历史和重 要的研究意义。碰撞检测问题基于现实生活中一个普遍存在的事实：两个不可穿透的 对象不可能共享相同的空间区域。在机器人研究中，机器人与障碍物间的碰撞检测是 机器人的运动规划和避免碰撞的基础；在计算机动画中，对象必须能够针对碰撞检测 的结果做出如实的合理的响应，反映出真实的动态效果。近年来，随着虚拟现实技术 和分布交互仿真等技术的兴起，碰撞检测再一次成为研究的热点。 1 1 研究背景和意义 随着计算机软硬件技术的不断发展，虚拟环境已成为计算机科学的一个重要研究 领域可广泛地应用于教育、国防、医学、艺术、娱乐等多个方面【l 】。为保证虚拟环 境的真实性，参与者不仅要能从视觉上如实地看到虚拟环境中的虚拟对象以及它们的 表现，而且能身i 临其境地与它们发生各种交互，这就首先要求虚拟环境中的固体对象 是不可穿透的，当参与者接触到对象并进行拉、推、抓取等操作时，能真实地感觉到 碰撞的存在并实时做出相应的反应。此外，一个虚拟环境通常包含若干个静止的环境 对象和运动着的活动对象，每一个虚拟对象的几何模型都是由成千上万个基本几何元 素( 如四面体或三角形) 组成的，虚拟环境的几何复杂度使得碰撞检测的计算复杂度 大大提高，而参与者与虚拟环境的交互又要求实时完成，因此碰撞检测往往成为虚拟 环境中的一个瓶颈。由此可见，精确的碰撞检测对提高虚拟环境的真实性、增强虚拟 环境的沉浸感有着至关重要的作用，而虚拟环境自身的复杂性和实时性对碰撞检测提 出了更高的要求。 本文的应用背景是虚拟手术仿真( s u r g e r ys i m u l a t i o n ，又称为m e d i c a lv r 【2 】) 。虚 拟手术仿真是虚拟现实技术在医学领域的一个重要应用，对虚拟手术仿真的研究旨在 通过精确的器官造型( 几何建模及物理建模，生理建模) ，来逼真地模拟人体组织在外 力交互作用下可能发生的变形乃至被切割或发生碎裂的过程，并通过视觉力学反馈 系统及其它可能的感官反馈形式，给用户提供真实的手术现场的感觉。它不仅可以作 为手术培训的模拟器，而且可以用于分析验证手术方案的可行性，还可以预演手术过 程以便及早地发现问题。 虚拟手术仿真系统的目标是提供给用户身临其境的沉浸感和完善的交互能力，为 了达到这一目标，理论上要求视觉反馈的带宽在2 0 h z 以上，触觉反馈的带宽在3 0 0 h z 以上【3 】。这就要求系统必须能够实时计算并显示人体组织在外力作用下的变形和分 第 1 页 裂，以及相关的一些生理特征，而碰撞检测是计算软组织变形和分裂的先决条件，只 有判定手术器械与人体组织发生接触后，才有必要实施变形的计算以及切割、缝合等 操作，只有根据碰撞检测的结果，才能准确地计算模型的变形。因此，碰撞检测贯穿 于手术仿真的整个过程。 在虚拟手术仿真系统中，需要处理的是大量的复杂的人体组织模型，包括刚体组 织( 如骨骼) 和软体组织。软体组织在整个人体构造中占据相当大的比例，许多重要 的器官( 如人脑、肝脏等) 都属于软体组织的范畴。相对于刚体，软体有其特殊的物 理特性，它们不仅会在外力的作用下发生变形，而且会因为切割和缝合等操作发生拓 扑结构的改变，具体表现为组成软组织模型的基本几何元素的几何形状的改变和数量 上的增减。此外，碰撞检测的结果不仅要报告碰撞的基本情况，还要为变形计算提供 更详细的信息，因此虚拟手术仿真对碰撞检测提出了更高的要求。 1 2 问题描述 碰撞问题包括碰撞检测和碰撞响应两部分。碰撞检测的目标是发现碰撞并报告： 碰撞响应是在碰撞发生后，根据碰撞点和其它参数促使发生碰撞的对象做出正确的动 作，以反应真实的动态效果。碰撞响应涉及到力学反馈、运动物理学等领域的知识 h 5 6 7 ”。我们研究的主要是碰撞检测问题。 通常碰撞检测可以分为静态碰撞检测，伪动态碰撞检测和动态碰撞检测三类。其 中静态碰撞检测是判断一活动对象在某一特定的位置和方向是否与环境对象相交：伪 动态碰撞检测是根据活动对象的运动路径检测它是否在某一离散的采样位置方向上 与环境对象相交；动态碰撞检测则是检测活动对象扫过的空间区域是否与环境对象相 交。静态碰撞检测一般没有实时性的要求，在计算几何中有着广泛的研究r 0 1 0 ，i 1 ；动 态碰撞检测的研究一般都考虑到四维时空问题或结构空间精确的建模【1 2 ”，1 4 ：而伪动 态碰撞检测有关于时间点和运动参数之间的信息，可以通过开发时空相关性获得较好 的性能。虚拟环境中的碰撞检测一般属于伪动态碰撞检测的范围。 我们可以对虚拟环境中的碰撞检测问题简化描述如下：碰撞检测系统的输入模型 为一个静态的环境对象和一个动态的活动对象的几何模型，它们均为基本几何元素的 集合。其中环境对象可以包括刚体对象，也可以包括软体对象，它们的位置和方向不 会发生变化，但软体对象会可能在外力的作用下发生变形。活动对象可以在虚拟环境 中自由运动，方向和大小完全取决于仿真过程或者用户控制的输入设备，无法用关于 时间的运动方程来表示，只能得到某一时间采样点相对于前一时间采样点或一固定参 照物的运动信息( 旋转角度和平移量) 。其任务是确定在某一时刻两个几何模型是否 发生干涉，即它们的交集是否不为空，如发生了碰撞，还需确定碰撞点( 参与碰撞的 基本几何元素) 。 第2页 国防科学技术大学研究生院学位论文 从目前的研究来看，几何模型可分为面模型和体模型两类。面模型用面片来表现 对象的表面，其基本几何元素多为三角形；体模型用体素来描述对象的结构，其基本 几何元素多为四面体。面模型相对简单一些，而且绘制技术成熟，处理方便，但难以 进行整体形式上的体操作( 如拉伸、压缩等) ，多用于刚体对象的几何建模。体模型 拥有对象的内部信息，可以很好地表达模型在外力作用下的体特征( 变形、分裂等) ， 但计算的时间和空间复杂度也相应增加，一般用于软体对象的几何建模。 最原始最简单的碰撞检测方法是一种蛮力计算的方法，即对两个几何模型中的所 有基本几何元素进行两两相交测试，尽管这种方法可以得到正确的结果，但当模型的 复杂度增高时，这种o ( n 2 ) 次的相交测试显然是无法容忍的。例如，对一个包含1 0 0 ，0 0 0 个三角形的三维环境和一个由1 0 ，0 0 0 个三角形构成的活动对象，如果使用这种蛮力 计算法，那么在活动对象的每个位置，需要执行1 亿次三角形一三角形相交测试以 确定在当前时间活动对象是否与环境发生碰撞。以当前的软硬件能力，这大约需要 i 以个小时的时间，这与实时交互所需要的每秒3 0 0 次( 触觉反馈带宽) 以上的碰撞 检测的要求相差甚远，因此，速度是虚拟环境中的碰撞检测的核心问题。 1 3 相关工作 在过去的几十年中，碰撞检测在计算几何和机器人等领域得到了广泛的研究，形 成了一些较为成熟的技术。在两个几何模型间的碰撞检测算法大致可分为两类：空间 分解法( s p a c ed 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 树 i l s l ，八叉树6 1 ，b s p 树 1 7 , 1 s ，四面体网和规则网格等。采用层次划分方法进行空 间分解，如八叉树，b s p 树等，可以进一步提高算法的速度。空间分解法通常适用于 稀疏的环境中分布比较均匀的几何对象间的碰撞检测。 层次包围盒方法是碰撞检测算法中广泛使用的一种方法，它曾经在计算机图形学 的许多应用领域( 如光线跟踪等) 1 9 , 2 0 , 2 1 , 2 2 】中得到深入的研究。其基本思想是是用体 积略大而几何特性简单的包围盒来近似地描述复杂的几何对象，进而通过构造树状层 次结构可以越来越逼近对象的几何模型，直到几乎完全获得对象的几何特性，从而只 需对包围盒重叠的部分进行进一步的相交测试。 s s u r i 等人f 2 3 翻，2 5 j 对包围盒方法进行了一系列的理论研究，证明了包围盒方法的 有效盐。对一组对象s = 只，b ，只) ，引入了两个参数：相似比( a s p e c tr a t i o ) 口和 比例因子( s c a l ef a c t o r ) 盯。相似比可以衡量对象的延伸率( e l o n g a t e d n e s s ) ，在经典 国防科学技术大学研究生院学位论文 几何中，矩形的相似比被定义为其长与宽的比，扩展到二维以上空间中的任意对象， 对象尸的相似比可定义为包围对象p 的最小的球6 ( 尸) 与对象尸所包含的最大的球c ( p ) 之间的体积比，目p a ( 耻器舞包围盒，故口= 毒咄) ；一组对象s 的比例因 子描述了最大的对象与最小的对象间的差异，定义盯= r 警n 警n 卷勰。则包围 盒相交的数目k b 与实际相交的对象数目k 符合以下比例关系k 。= p ( ”+ k 。) ， p = o ( a 仃l 0 9 2 仃) 。在大多数情况下，口和盯都是很小的常数，则进一步可证明 k 6 = d ( k ) + d ( n ) ，使用包围盒方法可以使碰撞检测的算法复杂度从o ( n 2 ) 降低为 o ( n l 0 9 2 以+ 妫) 。 层次包围盒方法的关键在于包围盒类型的选择，对用于碰撞检测的包围盒有以下 两方面的约束：( 1 ) 简单性。包围盒应该是简单的几何体。至少应该比被包围的几何 对象简单。简单性不仅表现为几何形状简单易于计算，而且包括相交测试算法的快速 简单。f 2 1 紧密性。包围盒应该尽可能地贴近被包围的几何对象。紧密性可以用包围 盒b 与被包围对象g 间的h a u s d o r f f g 巨离r 来衡量( r = m a 。x m i ，n d i s t ( b ，g ) ) ，r 越小， 紧密性越好，紧密性直接关系到需要进行相交测试的包围盒的数目。 1 3 1 基于a 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 ) 在碰撞检测的研究历史 中使用得最久最广，一个给定对象的a a b b 被定义为包含该对象且各边平行于坐标 轴的最小的六面体。图1 1 ( a ) 给出了一个简化了的二维平面中的例子。 给定对象e 的a a b b 的计算十分简单，我们只需分别计算组成对象的基本几何 元素集合s e 中各个元素的顶点的x 坐标、y 坐标和z 坐标的最大值和最小值即可；但 是，a a b b 的紧密性相对较差，尤其是对于沿斜对角方向放置的瘦长形对象，用a a b b 将留下很大的边角空隙，从而导致大量冗余的包围盒相交测试。 a a b b 间的相交测试也比较简单，两个a a b b 相交当且仅当它们在三个坐标轴 上的投影区间均重叠。定义a a b b 的六个最大最小值分别确定了它在三个坐标轴上 的投影区间，因此a a b b 闻的相交测试最多只需要六次比较运算。 使用a a b b 的碰撞检测系统有i - c o l l i d e 2 6 , 2 7 , 2 8 , 2 9 , 3 0 , 3 1 ，o c o l l i d e 3 2 ，”，3 4 1 和 s o l i d 3 5 , 3 6 1 等。i - c o l l i d 适用于大量运动着的对象间的碰撞检测，o c o l l i d e 是对 i - c o l l i d e 的改进，它使用“分离向量算法”取代i - c o l l i d e 中的“最近特征对算 法”进行相交测试，在某些情况下，其速度甚至可以比i - c o l l i d e 快一阶。但是 国防科学技术大学研究生院学位论文 i - c o l l i d e 和q c o l l i d e 要求处理对象是刚性并且是凸的，不适合复杂的虚拟环境 中的情况。s o l i d 是荷兰e i n d h o v e n 大学开发的一个基于a a b b 包围盒层次的碰撞 检测系统，它使用一种简化了的分离轴测试方法进行a a b b 间的重叠测试，并涉及 模型变形的处理，但它仅研究了模型顶点位移这一种变形，没有考虑拓扑结构变化的 情况。 ( a ) a a b b ( b ) 包围球 ( c ) o b b 图1 1常见的包围盒类型 1 3 2 基于包围球的碰撞检测 包围球 3 7 3 8 】类似于a a b b ，也是简单性好紧密性差的一类包围盒，包围球被定义 为包含该对象的最小的球体，如图1 1 所示。计算给定对象e 的包围球，首先需分 别计算s e 中所有元素的顶点的x 坐标、y 坐标和z 坐标均值以确定包围球的球心c ， 再由球心与三个最大值坐标所确定的点间的距离计算半径r 。包围球的计算时间略多 于a a b b ，但存储一个包围球只需两个浮点数。 包围球间的相交测试也相对比较简单。对于两个包围球( c l ，r 1 ) 和( c 2 ，r 2 ) ， 如果球心距离小于半径之和，即b c ，l + r 2 ，则两包围球相交，可迸一步简化为 判断c ，一c ：) ( c 1 一c ：) ( + 吒) 2 。故包围球间的相交测试需要4 次加减运算、4 次乘 法运算和1 次比较运算。 包围球的紧密性在所有包围盒类型中是比较差的，它除了对在三个坐标轴上分布 得比较均匀的几何体外，几乎都会留下很大的空隙，通常需要花费大量的预处理时间 以构造一个好的层次结构逼近对象，这在h u b b a r d 的工作中得到验 3 9 , 4 0 , 4 1 。相对于 a a b b 而言，在大多数情况下包围球无论是紧密性还是简单性都有所不如，因此，它 是使用得比较少的一种包围盒。 当对象发生旋转运动时，包围球不需要做任何更新，这是包围球比较优秀的一个 特性，当几何对象进行频繁的旋转运动时，采用包围球可能得到较好的结果。当对象 发生变形时，很难从子结点的包围球合成父结点的包围球，只能重新计算。 第5页 国防科学技术大学研究生院学位论文 1 3 3 基于o b b 的碰撞检测 方向包围盒o b b ( o r i e n t e db o u n d i n gb o x ) 是近年来比较著名的一个包围盒类型。 一个给定对象的o b b 被定义为包含该对象且相对于坐标轴方向任意的最小的长方 体。o b b 最大特点是它的方向的任意性，这使得它可以根据被包围对象的形状特点 尽可能紧密地包围对象( 图1 1 ( c ) 为一个简化的二维示意图) ，但同时也使得它的相交 测试变得复杂。 1 9 8 1 年，b a l l a r d 提出的用于逼近曲线的二维层次结构“s t r i pt r e e ”【4 2 】，其实就是 二维平面中的方向包围盒，继而b a r e q u e t 等人将它扩展到三维空间，称作“b o x t r e e ” h 3 】，用于光线跟踪和碰撞检测领域。1 9 9 6 年北卡罗莱纳州大学的g o t t s c h a l k 等人开 发研制了基于o b b 包围盒层次( 称作“o b b t r e e ”) 的r a p i d 系统 4 4 , 4 5 ，主要解决 一个活动对象在大型复杂环境模型中的碰撞检测问题，该系统基于分离轴理论进行包 围盒间的相交测试，当时声称是最快的碰撞检测算法，曾一度作为评价碰撞检测算法 的标准。 o b b 的计算相对复杂一些，其关键是寻找最佳方向，并确定在该方向上包围对 象的包围盒的最小尺寸。不失一般性，假设s e 中的基本几何元素为三角形，第i 个 三角形的顶点用p 7 ，q 。和r 表示，则s e 的均值和协方差矩阵c 计算如下： = 五1 善n0 5 ) c m = 石1 b j + q j q ：+ 一j ， 1 j ，k 3 j ，j = l 其中，p 。= p 。一，q 。= q 。一，。= r 一，它们均为贸3 中的一个向量，例如 一l p = k ：，p ：，p ：j ，c 为一个3 3 的对称矩阵。 协方差矩阵c 的三个特征向量是正交的，正规化后可作为一个基底，它确定了 o b b 的方向，分别计算s e 中各个元素的顶点在该基底的三个轴上的最大值和最小值， 以确定该o b b 的大小。存储一个o b b 需要1 5 个浮点数( 表示方向的3 个基底向量 共9 个浮点数和表示范围的6 个浮点数) 。 o b b 间的相交测试基于分离轴理论。若两个o b b 在一条轴线上( 不一定是坐标 轴) 上的投影不重叠，则这条轴称为分离轴。若一对o b b 间存在一条分离轴，则可 以判定这两个o b b 不相交。对任何两个不相交的凸三维多面体，其分离轴要么垂直 于任伺一个多面体的某一个面，要么同时垂直于每个多面体的某一条边。因此，对一 对o b b ，只需测试1 5 条可能是分离轴的轴( 每个o b b 的3 个面方向再加上每个o b b 的3 个边方面的两两组合) ，只要找到一条这样的分离轴，就可以判定这两个o b b 是 不相交的，如果这1 5 条轴都不能将这两个o b b 分离，则它们是相交的。 第6页 尽管o b b 间相交测试的代价比较大，但它的紧密性是最好的，可以成倍地减少 参与相交测试的包围盒的数目和基本几何元素的数目，在大多数情况下其总体性能要 优于a a b b 和包围球。此外，当几何对象发生旋转运动后，只要对o b b 的基底进行 同样的旋转即可。因此，对于刚体间的碰撞检测，o b b 不失为一种较好的选择，但 迄今为止，还没有一种有效的方法能够较好地解决对象变形后o b b 树的更新问题， 而重新计算每个结点的o b b 的代价又太大。故而o b b 不适用于软体对象环境中的碰 撞检测。 1 3 4 其它方法 还有一些其它的碰撞检测方法，如四维几何约束方法n “，它主要是用一个第四维 向量表示仿真时间，从而可以极精确地定位所有的接触，但是它需要事先定义活动对 象关于时间的运动方程，不适合于对象自由运动的情况。h u b b a r d 的时空约束的方法 4 6 1 1 4 7 1 也是用第四维来表示时间，他提出了一种用精度换取速度的思想，并结合了层 次包围球的方法进行快速移动的对象间的碰撞检测的研究。 在以往碰撞检测的研究工作中，大多数算法都是针对刚体对象间的碰撞检测，而 对软体( 可变形模型) 研究比较少，这主要是因为软体的建模和变形算法对碰撞检测 有很大的影响。瑞士的g e n e v a 大学曾对布和其它纺织品的表面的变形算法的碰撞检 测有一定的研究【1 4 】：在s o l i d 2 0 版本中也增加了对可变形模型的碰撞检测的内容， 但它们都具有一定的局限性。a s m i t h 的算法 4 8 1 在每一步都重新计算对象的a a b b 以提取碰撞区域( a a b b 重叠的部分) ，通过空间划分法对所有包含在重叠区域中的 对象的面构造o c t r e e ，再进行边一面对间的精确的相交测试。该方法尽管可以解决软 体对象环境中的碰撞检测，但它在每一步都需要重新计算重叠区域并构造o c t r e e ，虽 然采用了一定的优化措施，但其开销仍很大。故而，复杂环境，尤其是包含软体对象 的复杂环境中的碰撞检测问题，仍有待进一步的研究。 1 4 主要贡献 本文的主要贡献如下： 提出了一种基于固定方向凸包f d h ( f i x e dd i r e c t i o nh u l l ) 包围盒层次的碰撞 检测方法，为解决复杂环境中的碰撞检测问题提供了一条有效的途径。固定 方向凸包是一种特殊类型的凸包，同时它也可以看作是a a b b 的扩展，它不 但继承了凸包紧密性好的优点，同时也继承了a a b b 简单性好的优点，通过 调整固定方向集合大小和取值，可以在紧密性和简单性之间达到定的折衷。 开发并证明了固定方向凸包适用于碰撞检测的性质。固定方向凸包的所有面 第7页 方向都来自一个固定的方向集合，我们在给出了它的严格的数学定义的基础 上，根据复杂环境中碰撞检测对包围盒的要求，开发并证明了固定方向凸包 适用于碰撞检测的性质，为正确解决碰撞检测问题提供理论依据。 提出了种基于线性规划的方法提高活动对象旋转后包围盒层次的更新速 度。活动对象运动后包围盒树的更新是虚拟环境中碰撞检测问题的一个重点， 以往的解决方法都需要在构造包围盒树时增加额外的计算和存储空间，并且 在对象运动后的包围盒更新算法中计算量也比较大。对象的运动通常可用一 旋转矩阵和一平移向量来描述，根据f d h 的定义，我们引入线性规划的思想， 根据线性规划的一些基本定理，对问题进行简化计算。我们的方法不仅在构 造树时不需要任何额外的时空开销，而且在更新包围盒时速度较以往的方法 有很大的提高。 提出了一种自底向上的更新方法不仅解决了软体对象的变形问题，而且解决 了拓扑结构发生变化的情况。软体对象的变形一直是碰撞检测问题中的难点。 软体对象的几何模型的变化使得最初构造的包围盒树不再适用于当前状态下 的对象，拓扑结构的变化导致原先的包围盒树中某些结点无效。为此，我们 提出了一种自底向上的更新方法，由两个子结点的f d h 包围盒通过k 次比较 运算得到其父结点的包围盒，从而保证了碰撞检测的正确性和有效性。 充分开发并利用虚拟环境中对象运动的时空相关性，提出可以加快碰撞检测 算法速度的遍历跟踪策略。虚拟环境中的对象运动的时空相关性使得相邻时 间采样点发生碰撞的情况具有很大的相似性，为此我们提出了一个启发式的 遍历跟踪策略，通过跟踪上一时间采样点活动对象在环境对象树中的遍历过 程，确定当前时间采样点活动对象的遍历路径，从而有效地减少了包围盒间 相交测试的数目，提高了算法的效率。 以虚拟手术仿真为应用背景，设计并实现了复杂环境中碰撞检测软件包。虚 拟手术仿真中所涉及的两类对象：手术器械和人体组织，分别属于刚体对象 和软体对象的范畴，手术仿真的目标是逼真地模拟人体组织在手术器械的作 用下发生变形乃至被切割发生碎裂的过程。碰撞检测是形变和压力计算的基 础，同时也是切割和缝合的先决条件，而形变和压力计算以及切割和缝合又 对碰撞检测提出了更高的要求，碰撞检测的结果不仅要报告碰撞的基本情况， 还要为变形计算提供更详细的信息。我们基于f d h 包围盒层次的碰撞检测方 法已较好地应用于虚拟手术仿真系统s s o s 中。 通过实验证明，我们的方法不仅在处理刚体闻的碰撞检测时较以往的算法有 所提高，而且可以较好地处理刚体对象与软体对象间的碰撞检测问题。 第8页 1 5 论文结构 本论文全文共九章。 第一章为引言。 第二章给出了本文将要用到的一些基本概念和定理。 第三章给出了固定方向凸包的严格定义，并详细介绍了构造基于固定方向凸包的 包围盒层次的原则和方法。 第四章讨论了基于固定方向凸包包围盒层次的碰撞检测方法。着重论述了包围盒 树的双重遍历算法，f d h 包围盒间的快速相交测试的方法，并以三角形为例介绍了 基本