（计算机应用技术专业论文）基于包围盒和空间分割的碰撞检测算法研究.pdf

硕士学位论文 m a s t e r st h e s i s 摘要 准确且快速的碰撞检测对提高虚拟现实环境的沉浸感和真实感具有非常重要 的意义。由于虚拟环境中存在大量的物体对象和物体几何形状的复杂性，使得碰撞 检测过程常常占去大量的存储空间和处理时间，碰撞检测算法的效率决定生成虚拟 场景的实时性和真实性。碰撞检测是虚拟现实技术研究的难点问题。 层次包围盒法和空间分割法是碰撞检测算法中的基本方法，这两种方法的目的 都是为了尽可能的减少需要相交测试的对象或基本几何元素对的数目。为提高碰撞 检测的效率，本文在对这两种算法进行了深入研究的基础上，主要从以下两个方面 进行了研究： 本文依据a a b b 包围盒构造方便和相交测试简单的特点以及a a b b 树的构造 过程特点，提出一种减少a a b b 层次包围盒树内部结点存储所需字节数的方法，从 而加速了碰撞检测算法的执行速度。 本文提出一种均匀空间分割的方法来检测变形体对象之间的碰撞及自碰撞。该 方法采用哈希表作为数据存储结构，以四面体网格为基本几何元素，优化了哈希函 数、哈希表、单元格等参数。实验证明该方法的有效性。虽然算法的研究是以四面 体网格为研究对象，但这一算法同样适合其它变形体对象。 关键词：碰撞检测；层次包围盒；空间分割；哈希表： a b s t r a c t f a s ta n da c c u r a t ec o l l i s i o nd e t e c t i o ni sv e r yi m p o r t a n tt oi m p r o v ei m m e r s i o na n d a u t h e n t i c i t yf o rv i r t u a le n v i r o n m e n t b e c a u s et h e r ee x i s t sal a r g en u m b e ro fo b j e c t sa n d t h ec o m p l e x i t yo ft h eg e o m e t r y ，c o l l i s i o nd e t e c t i o np r o c e s so f t e ns p e n dal o to fs t o r a g e s p a c ea n dp r o c e s s i n gt i m e ，r e a l - t i m ea n da u t h e n t i c i t yo fv i r t u a le n v i r o n m e n ta r ed e t e r m i n e d b yt 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 n c o l l i s i o nd e t e c t i o ni sa l w a y st h eh a r dq u e s t i o ni n v i r t u a lr e a l i t y t h e r ea r em a i n l yt w oa l g o r i t h m so fc o l l i s i o nd e t e c t i o ni nv i r t u a lr e a l i t 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 ma n ds p a c es u b d i v i s i o na l g o r i t h m 1 1 1 ep u r p o s eo ft h e s et w o a l g o r i t h m si st or e d u c et h en u m b e ro fp a i r so fo b j e c t so rp r i m i t i v e st h a tn e e dt ob e c h e c k e df o rc o n l a e t t oi m p r o v et h ee 塌c i e n c yo fc o l l i s i o nd e t e c t i o n ，o nt h eb a s i so fo u r i n d e p t hr e s e a r c h ，w ec h o o s et h ef o l l o w i n ga so u r r e s e a r c hd i r e c t ： d u et ot h ec o n v e n i e n tc o n s t r u c t i o na n ds i m p l ei n t e r s e c t i o nt e s tf o ra a b b ，t h i s p a p e rd e a l sw i t ht h ep r o b l e mo fc o l l i s i o nd e t e c t i o nf r o mi t b a s e do nt h en a t u r eo fa a b b a n dc o n s t r u c t i o np r o c e s so fa a b bt r e e ，w ei n t r o d u c eam e t h o dt h a tc a nr e d u c et h e a m o u n to fb y t eo f a a b bt r e ef o ri n t e r n a ln o d e ，s ot h ea l g o r i t h mi ss p e e d e du p w ep r o p o s eau n i f o r ms p a t i a ls u b d i v i s i o na p p r o a c ht oc o l l i s i o na n ds e l f - c o l l i s i o n d e t e c t i o no fd e f o r m a b l eo b j e c t s t h ep r o p o s e da p p r o a c he m p l o y sh a s hf u n c t i o na sd a t a s t r u c t u r e ，a n dt e t r a h e d r o nm e s h e sa st h ep r i m i t i v e s w ee x p e r i m e n tt h ep a r a m e t e ro ft h e c o l l i s i o nd e t e c t i o na l g o r i t h m ，s u c ha sh a s hf u n c t i o n ，h a s ht a b l es i z e ，s p a t i a lc e l ls i z e o u r a p p r o a c hh a sb e e ni m p l e m e n t e db a s e do nt e t r a h e d r o n ，h o w e v e li t i sn o tr e s t r i c t e dt o t e t r a h e d r o n sa n dc o u l dh a n d l eo t h e ro b j e c tp r i m i t i v e 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 ；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 p a c es u b d i v i s i o n ；h a s h t a b l e ； 硕士学位论文 m a s t e r st h e s i s 华中师范大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，独立进行研究工作 所取得的研究成果。除文中已经标明引用的内容外，本论文不包含任何其他个人或 集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在 文中以明确方式标明。本声明的法律结果由本人承担。 作者签名： 渺证 日期川年6 月g 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有权保 留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。 本人授权华中师范大学可以将本学位论文的全部或部分内容编入有关数据库进行 检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。同时授权中 国科学技术信息研究所将本学位论文收录到中国学位论文全文数据库，并通过 网络向社会公众提供信息服务。 储虢渺 喊计6 月寥日 导师签名：余疋影 日期。哕年6 月孚日 本人已经认真阅读“c a l i s 高校学位论文全文数据库发布章程”，同意将本人的 学位论文提交“c a l i s 高校学位论文全文数据库中全文发布，并可按“章程”中的 规定享受相关权益。圃重诠塞堡蛮卮溢蜃! 旦圭生；旦二生；旦三笙筮盔1 2 导师签名： 彬参 日期叫年6 月兮日 硕士学位论文 m a s t e r st h e s i s 第一章绪论 虚拟现实( v i r t u a lr e a l i t y ) ，简称v r ；又称为灵境、幻真，也称灵境技术或 人工环境。它是利用电脑模拟产生一个三维空间的虚拟世界，提供使用者关于视觉、 听觉、触觉等多个感官的模拟，让使用者如同身临其境一般，可以及时、没有限制 地观察三维空间内的事物。 虚拟现实是通过计算机对复杂数据进行可视化操作与交互的一种全新方式，与 传统的人机界面以及流行的视窗操作相比，虚拟现实在技术和思想上都有了质的飞 跃，具有以下特征： 多感知性：所谓多感知是指除了一般计算技术所具有的视觉感知以外、还有听 觉感知、力觉感知、触觉感知、运动感知等。 沉浸感：又称临场感，是指用户感到作为主角存在于模拟环境中的真实程度， 理想的虚拟环境应该是使用户难以分辨真假，如同在现实世界中的感觉一样。 交互性：指用户对模拟环境内物体的可操作程度和从环境得到反馈的自然程 度。例如，用户可以用手去直接抓取模拟环境中的虚拟物体，这时手有握着的感觉， 并可以感觉物体的重量。 构想性：强调虚拟现实技术应具有广阔的可想象空间，可拓宽人类认知范围， 不仅可再现真实存在的环境，也可以随意去构想客观不存在甚至不可能发生的环 境。 1 1 论文研究背景及意义 虚拟现实的应用使得使用者可以进入一个由计算机产生的虚拟世界，并能与虚 拟对象和虚拟代理相互交互，这样的系统给人的感觉一般是身临其境的，这些应用 中有一个共同点就是要求提供给使用者很强的沉浸感，并需要不断实时更新物体对 象的变化。物理对象之间的相互作用，如接触，触及和投掷通常都能引发碰撞。虚 拟环境中的对象越多，对象的几何特征越复杂，越会增加更大的存储负荷，这样就 需要极其快速的碰撞检测。正因为碰撞检测具有如此广泛的应用范围，所以它一直 都是广为研究的课题。例如，用户伸手去拿虚拟环境的一个杯子，那么系统必须检 测到手和杯子之间有直接的接触，才能进一步仿真手拿杯子的情景。这里有两个问 题需要处理：对象之间的碰撞有两个问题需要处理：一是要检测到碰撞，而是处理 碰撞后的反应问题。本文将重点研究虚拟环境中的碰撞检测问题，对于碰撞反应问 题不予研究，因为此类问题的处理要用到牛顿力学的相关知识，与具体的应j j | j 有关。 刚体和软件是虚拟环境中对象的基本形态，以前的研究士要集t ”于刚体，近年 柬已经把重点放到软体物体上。 在基于物理模拟的虚拟环境和虚拟手术仿真的应用中，软体的碰撞检测都是。 个必不可少的组成部分。图l1 显示为软体碰撞检测的实例，被命名为织物仿真。 在织物仿真巾，动态变形的衣物必须能够处理衣物的自我碰撞阻及相互作用，这就 需要与之相关的碰撞检测算法来处理该类问题。这样的应用要求碰撞检测算法能够 适合于对象的运动与变形。 图12 虚拟环境中的手术仿真 硕士学位论文 m a s t e r st h e s i s 和刚体的碰撞检测相比，软体碰撞检测有许多方面与之不同，这使得该问题的 复杂性大大增加。 碰撞和自碰撞为了实时模拟软体对象的交互，包括自我碰撞的点都必须 考虑在内，这点和刚体的碰撞不同( 在刚体中自碰撞一般是可以忽略的) 。 预处理碰撞检测算法可以被一些有效的数据结构所加速，这些数据结构 包括：层次包围盒，距离场，可以变化的空间分割方法。这样的数据结构 一般可以在预处理阶段建立，并且在刚体的检测方面表现出良好的性能。 但是，由于虚拟场景中的软体对象经常可能发生形变，那么数据结构就需 要频繁的更新。所以上述提到的数据结构对于软体碰撞检测的效率是比较 低的，并且其面对具体的实例也需要做具体的调整。 碰撞信息对于软体的碰撞检测问题，碰撞反应后的信息必须被考虑在 内，所以仅仅检测对象之问的碰撞是不充分的。相反，精确的碰撞信息比 如对象之间的穿透深度必须精确的求出。 效率在手术仿真、游戏、布料仿真这类交互式应用中，碰撞检测算法的 效率对于增强虚拟环境沉浸感是非常重要的，在这些应用当中，交互是一 个非常重要的特点，这就需要高效率的碰撞检测算法。 在本论文中，为了满足动态环境中软体对象的实时交互性要求，我们讨论了解 决上述问题的碰撞检测方法。尽管所讨论的算法适合软体对象，但这些方法也同样 适合刚体对象。 1 2 问题描述 设三维空间r 用三维几何坐标系统凡【l 】表示，其中有纷个运动对象，它们的空 间位置和姿态随着时间而改变，f 表示第f 个对象所占的三维空间，随着时间的变 化r 变成四维坐标系统q ，对象e 沿着一定得轨迹运动变成了巳的子集q ，碰 撞检测就是判断c lnc 2n g 已= 是否成立。 上述定义在理论上给出了碰撞检测的精确方法，但由于物体运动本身和自身模 型的复杂性，导致四维集合g 的计算量过大，碰撞检测实现代价非常之高。对于当 前的计算机硬件系统来说，要满足碰撞检测所要求的实时性和精确性，计算量是不 3 硕士学位论文 m a s t e r st h e s i s 能接受的。通常在实际中采用牺牲计算精度，提高速度的方法。 设虚拟环境中要仿真刀个物体对象：q ，0 2 ，o n ，仿真的时间段是t 。到f l ，对 物体的仿真过程是逐帧进行计算的，设时间步长为址，则碰撞检测的过程可具体表 示为如下算法： c o l l i s i o nd e t e c t i o n ( b ，f i ) ， d l ，0 2 ，q ) ) f o r ( t = t o ，t = f i ：步长为址) f o r ( 物体q 0 l ，0 2 ，q ) ) d o 移动物体d 到t 时刻的位置 f o r ( 物体q q ，0 2 ，q ) ) d o f o r ( d ， q ，0 2 ，q _ l ，o j + l ，o n d o i f ( o , 与o j 相交) t h e n 在t 时刻发生了碰撞 ) 1 3 国内外动态研究 有效的碰撞检测在物理模拟、物理仿真、织物仿真、计算机动画、手术仿真和 3 d 游戏等领域中起着非常重要的作用。国内外学者对该问题的研究已经有几十年的 历史，方法主要有层次包围盒方法、距离场方法、空间分割方法、图像空问方法。 基于层次包围盒的碰撞检测算法已经被证明是高效的，通过这种方法可以快速 排除不可能发生碰撞的物体，从而可以很快检测到可能相交的对象。各种类型的包 围盒先后被研究，其中有包围球【2 ，3 ，4 】，轴向包围盒【5 ，6 】，方向包围盒 7 】，k - d o p s 包围盒。在文献 8 】中，对层次包围盒优化的各种方法被提出。包围盒方法最初被用 来解决刚体对象之间的碰撞检测问题，对于软体对象而言，由于虚拟环境中对象的 不断运动和可能发生变形，层次包围结构就需要不断的快速更新。虽然在优化包围 盒结构方面做了很多改进 9 ，但对于几何形状复杂的物体对象而言，算法仍然需要 相当大的存储丌销，这就造成了算法效率的降低。 除了层次包围盒方法，距离场也是解决对象碰撞检测的一种有效方法，在文献 1 0 中，一种结合包围盒方法和距离场的混合方法被提出。对于需要实时更新处理 的几何形状复杂的对象，由于相互交互作用的要求，这种方法仍然不够快。 4 硕士学位论文 m a s t e r st h e s i s 空间分割的方法也是解决此类问题的一种有效方法。文献 1 1 提出了一个层次 空间分割方法来适用于机器人运动规划问题，但是仅仅能处理刚体对象。该方法比 较适合的虚拟环境是：物体对象数量比较少；物体对象在虚拟空间中分布密度大致 相同。 近年来，基于图形硬件的各种方法被提出，该方法是将三维物体通过向参考面 投影降维得到一个二维的图像空间，然后分析保存在图像空间的各类缓存信息，得 出物体之间是否发生碰撞并进行下一步相应处理。在文献 1 2 中，一种多程渲染的 方法被提出，但是这种方法仅仅用来处理凸对象。虽然基于图像的碰撞检测方法能 有效的处理碰撞检测问题，但对于准确性要求很高的虚拟环境，该方法只能提供有 限碰撞反应的信息，并且不提供准确的碰撞信息，不太适合于虚拟手术这些对准确 性要求很高的虚拟环境。 1 4 本文工作及章节组织 为提高碰撞检测的效率，在综合现有碰撞检测算法的基础上，本文作了如下工 作： ( 1 ) 从存储空间的角度来改进碰撞检测算法。依据a a b b 包围盒本身的特点和 a a b b 树的构造过程，减少a a b b 层次包围盒树内部结点存储所需的字节数，以提 高碰撞检测的效率。 ( 2 ) 提出一种均匀空问分割的方法来检测变形体对象之间的碰掩及自碰撞。该 方法以四面体网格为基本几何元素。由于树类结构的更新浪费大量的时问从而使碰 撞检测的效率降低，所以本文采用哈希表的数据存储结构，并通过实验具体分析了 影响该算法性能的参数：哈希函数、哈希表大小、单元格大小。虽然算法的研究是 以四面体网格为基础的，但这一算法同样适合与其他变形体对象，比如由三角形元 素构成的对象。 本文后面的结构安排如下： 第二章介绍了基本的碰撞检测算法。内容包括常见包围盒类型以及它们的优缺 点比较；基于层次包围盒树的碰撞检测算法；基于空间分割的碰撞检测算法。 第三章论述了基于包围盒树的碰撞检测算法，对碰撞检测的过程进行两个阶段 的划分。论述了层次包围盒树构造、更新的方法，并对基于a a b b 包围盒方法的包 围盒树进行了存储优化。 第四章提出一种均匀空问分割的碰撞检测算法。并通过实验分析了影响该算法 的各个参数。 第五章总结和展望。在对本文所做工作进行总结的基础上，阐述了进一步的工 作目标。 5 第二章相关碰撞检测算法综述 2 1 层次包围盒方法 2 1 1 基本原理+ 层次包围盒方法的基本思想是用一个简单的包围盒将复杂不规则的几何对象 围住，当两个对象作碰撞检测时，如果对象的包围盒不相交，则对象肯定不相交。 只有对象的包围盒相交时，才对其所包含的几何对象做进一步的相交测试。通过构 造包围盒树的层次结构来逼近几何模型，树的根结点包围了整个对象，每个父结点 包围的几何对象是它的所有子结点包围的几何对象之和，进行相交测试时首先判断 两颗包围盒树的根结点是否相交，如相交则递归的进一步判断它们的子结点是否相 交，依据从上到下的访问原则逐渐逼近叶子结点，若最后的叶子结点相交，则判断 每对叶结点包围的基本几何元素( 一般为三角形或者简单四面体) 是否相交。通过 这种方法可以很快减少基本几何元素对相交测试的数目，从而提高碰撞检测的效 率。 一般来说，对于层次碰撞检测算法，其效率主要受以下两个方面的影响： 层次包围盒和物体对象的接近程度 _ 两个层次包围盒之间进行相交测试所需的计算量 对于几何形状很复杂的变形体对象，第一点是没有意义的，这是因为假设当前 的层次非常接近对象，但是在一段时间之后，由于物体的运动或变形，其接近程度 就会变得比较差。下面简单扼要地介绍一下各种类型的包围盒。 2 2 2 层次包围盒的类型 移移 ( a ) 包围球 ( b ) a a b b( c ) o b b 图2 i 包围盒类型 6 硕士学位论文 m a s t e r st h e s i s 1 、包围球( s p h e r e ) 包围球被定义为包含该对象的体积最小球体。要计算给定对象的包围球，首先 要根据对象中基本元素的顶点三维坐标均值来计算包罔球的球心o ( a ，b ，c ) ，然后由 球心坐标和三维坐标点中的最大值之间的距离来确定球半径尺，如图2 1 ( a ) 所示， 假设包围球的球心o ( 口，b ，c ) ，球半径足，则可得出包围球的坐标公式为： a = ( x ，y ，z ) l ( x - a ) 2 + ( y - 6 ) 2 + ( z - e ) 2 轴向包围盒当且仅当它们在x 、y 、z 轴上的投影都有重合的区域时，包围盒才 发生相交。 轴向包围盒的优点是构造简单，缺点是和物体的接近程度比较差，从而导致大 量冗余的包围盒相交测试。 3 方向包围盒o b b ( o r i e n t e db o u n d i n gb o x ) 一个给定对象的方向包围盒o b b 6 被定义为包含该对象且相对于坐标轴方向 任意的体积最小的长方体，相比较与a a b b 、o b b ，它的最大特点是方向的任意性， 这就使得可以根据被包围对象的物理几何特点来尽可能的包围对象，图2 1 ( b ) 所示 7 为一个对象o b b 包围盒的二维示意图。 该类包围盒的重叠测试是基于分离轴的，可以精确的测试复杂几何对象的碰撞 反应问题。相对于球树而言，0 b b 树的缺点是更新速度较慢。如果虚拟场景中存在 大量需要相交测试的对象，树更新所造成的存储负担是不可接受的。 4 固定方向凸包k d o p s k - d o p s 1 3 包围盒是实质上是一种凸多面体，一个对象的k - d o p s 被定义为包含 该对象且它的所有面的法向量都取自一个固定的方向集合( k 个向量) 的凸包，其中 的方向向量为共线且方向相反的向量对。特别地，轴向包围盒a a b b 实际上是6 - d o p s ， 其六个面的法向量分别是+ ( 1 ，o ，0 ) ，+ - ( 0 ，l ，o ) ，+ - ( o ，0 ，1 ) 。图2 1 ( d ) 是一个固定方向凸包的实例，此时k = 6 ，其6 个面的法向量分别是+ 4 5 0 ，+ 一1 3 5 0 ， + 9 0 0 。和a a b b 相比，该类包阐盒的优点是紧密性较好，适合于复杂场景下的对 象碰撞检测。 5 包围盒性能之比较 从简单性上来考虑，包围球无疑是最简单的，其所需存储的数据量也最少( 只 需要两个浮点数) 。其次分别为a a b b 、o b b 、k - d o p s 。 紧密性好，相交测试复杂，但需要测试的包围盒对的数量减少 口 i 一 s p h e r e s a a b b s k - d o p s o b b s 紧密性差，相交测试简单，但需要测试的包围盒对的数量增加 图2 2 不同类型包围盒性能比较 从上图可以看出，不同类型的包围盒其特性也不相同：形状简单的包围盒 a a b b 相交测试速度较快，但由于紧密性较差，需要测试的包围盒对数较多；而形 状复杂的包围盒如k d o p s 重叠测试速度较慢，但由于紧密性好，需要测试的包围 盒对数相对较少。所以我们在选择包围盒类型的时候，应根据虚拟环境中的具体情 况，来选择使用不同类型的包围盒。可以选择其中的一种，也可以选择几种包围盒 8 硕士学位论文 m a s t e r st h e s i s 的综合运用，从而实现虚拟环境对实时性要求，以提高碰撞检测的效率。 2 3 基于包围盒树的碰撞检测算法 一个复杂的几何对象通常是有由很多几何子部分组成的，可进一步求出这些几 何子部分的包围盒，这些子部分又递归地由更小的部分组成，由此可将物体及其子 部分的包围盒组织成层次结构，最常见的是组织成一棵树。在这个棵树中，叶子节 点为对象的基本几何元素( 对于刚体，一般为三角形；对于软体，一般为四面体) ， 根结点对应着对象整体的包围盒，树的内部节点为各个子对象的包围盒。 碰撞检测算法的核心就是通过有效的遍历这两棵树，以确定在当前位置和状态 下，两个对象是否发生碰撞，这是一个双重遍历的过程：算法首先用一个对象的包 围盒树的根结点遍历另一对象的包围盒树，如果能到达另一对象的叶结点，则用该 叶结点遍历第一个对象的包围盒树，如果能到达该对象的叶结点，则进一步做基本 几何元素的相交测试。若父结点对应的包围盒没有相交，则就不用继续对其包含的 孩子结点做重叠测试。 假设，分别为对象包围盒树中的当前要检测的结点，s f 和s f 分别是结点 和咋所对应的基本几何元素的子集。6 ( 圪) ，6 ( ) 为它们的包围盒。具体的碰撞 检测算法的递归伪代码如图2 - 3 所示： 9 硕士学位论文 m a s t e r st h e s i s b o o lt r a v e r s e ( ( 6 ( ) ，6 ( ) ) i f ( 6 ( ) n6 ( 咋) = ) t h e n r e t u r nf a l s e e l s ei f 圪是叶结点t h e n i f k 是叶结点t h e n f o r 任一基本几何元素& f o r 任一基本几何元素斥昂 i f ( 乓n 斥西) t h e n r e t u r nt r u e e l s e f o r 任一子结点巧 t r a v e r s e ( ，) e l s ef o r 任一子结点圪 t r a v e r s e ( 屹，咋) ) 图2 3 碰撞检测算法 上述代码描述了如何检测两个对象是否碰撞，如果程序结果返回f a l s e ，则表明 两对象没有发生碰撞；如果程序返回t r u e ，则表明两对象发生了碰撞。 层次包围盒方法是碰撞检测检测中经常使用的方法。从上述算法流程中可以知 道：如果检测到包围盒不相交，那么就可以迅速排除其包围对象相交的可能性。这 就很大程度节省了时间和空间的丌销。但需要注意的是，这并不表示两个对象确实 要发生碰撞，这是因为包围盒和被包围的对象总是很接近，但并不意味着包围盒和 被包围对象等同于一个物体，需要做精度更高的测试才能得到准确的碰撞结果，即 两对象是否发生碰撞。 2 4 基本几何元素之间的相交测试 在上节所述的递归包围盒层次算法中，算法对碰撞检测问题的处理最终转换为 基本几何元素之间的相交测试，对于刚体，其基本几何元素一般为三角形；对于软 体，其基本几何元素为四面体，因为每个四面体有四个面，故可得出以下结论：只 需对三角形进行相交测试，就能判断两对象是否相交。基本几何元素间相交测试速 度的快慢对碰撞检测算法的效率有着重要的影响。 1 0 硕士学位论文 m a s t e r st h e s i s 假设要检测的三角形分别为a a s d ，a h j k 。传统的测试的基本方法 1 4 ，1 5 是： 检测边a s ，s d ，a d ，是否与a i - 1 j k 相交，如果存在一组相交的情况，那么就能 判断a a s d 和a h j k 相交，否则就不相交。由于该方法要逐一对每条边进行测试， 所以效率比较低。本节在综合各种方法的基础上，对测试方法做出如下改进： 在三维空间足3 内，存在三角形互和乏，其所在的平面分别对应口。和口：，显然 互c 口。，疋c 口：，若互和疋相交，则口。和口：必相交，故可得出三角形对相交的必 要条件是每个三角形与另一三角形所在的平面必相交 2 6 。因此，要判别正和互相 交与否，可首先检测互和口，是否相交，若不相交，则可立即得出z 和瓦不会相交的 结论。具体流程如图2 3 所示： 为便于表述，我们记三角形相交返回值为t r u e ，不相交返回值为f a ls e 。从流 程图可以看出，该方法首先判断不和疋所在的平面o f 。，o f ，是否重合，若重合，则 问题立即转换为二维空间的三角形对相交测试处理；否则，进一步检测互是否在口， 内，若不在，则不相交，若在，则问题转换为三维空间的三角形对相交测试处理。 下面对这个问题进行讨论。 硕士学位论文 m 人s t e r st h e s i s 图2 3 三角形对相交测试流程图 我们设三角形互的顶点是，h ，v 2 ，其到平面口：的有向距离分别为h 。， 日。，日：，对这三个有向距离进行讨论，可得出三角形对相交测试的方法 2 7 ： 如果风，风，日：这三个距离值都不为o ，并且同为正值或负值，则存在以 下两种情况：口。和口：平行；巧和口：不相交( 正在口：的一侧) ，那么我们 就可得出这样的结论：互和砭不可能相交，即返回f a l s e 。 1 2 如果日。= 0 ，h i = 0 ，h ：= 0 。则互在口：内，即两三角形所在的平面是同一个平 面，即口。= 口：。此时问题就被转换为二维空间中三角形对的测试。 如果三个有向距离当中有一个的值为0 ，则对应距离为o 的那个点在平面口：内。 此时需要判断该点和平面瓦的关系。根据空间立体几何的知识，知道点和平面 只存在两种关系：点在平面内；点在平面外。则可得出如下结论：如果点 在兀内，返回t r u e ；如果点在正外，返回f a l s e 。 如果三个有向距离值中存在两个有向的乘积值为负值，则求出口，和口：的相交 的直线k ，记夏nk = a l ，t 2nk = a 2 。根据平面几何的知识可得出：如果彳。和 以有重叠，则返回t r u e ；否则，返回f a l s e 。 2 5 空间分割方法 空问分割碰撞检测算法的基本思想是：对整个虚拟场景空间尺3 沿x 、y 、z 轴进 行分割，形成一系列空间网格，只对同处于一个空间网格内的对象之间进行碰撞检 测，该方法可用于检测变形体对象之间的碰撞及对象自身的碰撞，除了以三角形作 为基本几何元素以外，还可以以其它几何元做基本几何元素，比如四而体。空间分 割方法中用于表示r 3 空间的数据结构很重要，直接能影响到碰撞检测算法的性能和 效率，如图2 5 所示： ( i ) 四叉树( 2 ) 均匀网格( 3 ) b s p 树 圈2 5 空间分割常用的数据结构 硕士学位论文 m a s t e r 。st h e s i s 常用的空间分割的方法有四叉树、b s p 1 6 树、均匀网格等，其中四叉树和b s p 树的数据结构和对象相关的，而使用均匀网格【7 ，1 7 】的方法则与对象无关，这样就 很适合处理变形体对象之间的碰撞检测。均匀空间分割的关键是确定适当的空间网 格的尺寸，这样一方面可以保持碰撞检测的准确性，另一方面保证算法的复杂度不 是太高。 2 6 小结 本章主要介绍了基本的碰撞检测算法。 对于层次包围盒算法，其关键是在对层次包围盒的递归遍历中，通过包围盒间 的相交测试，及早排除所有不可能相交的基本几何元素的集合，只对包围盒相交的 叶结点中的三角形进行精确的相交测试。2 4 节对三角形对相交测试的方法做了一 些改进，目的是减少计算复杂度，提高碰撞检测的效率。 对于空间分割算法，选择一个适合的方法来分割虚拟空间对于算法的效率是非 常重要的，为此，本文在后面提出一种均匀空间分割的方法来处理变形体对象之间 的碰撞检测。 本章讨论的都是非常基本的碰撞检测问题，在后面的章节中，我们将会讨论 层次包围盒树的具体构造方法，以及为提高碰撞检测的速度而对层次包围盒树所做 的存储优化。 1 4 硕士学位论文 m a s t e r st i i e s i s 第三章基于层次包围盒树的碰撞检测算法 3 1 碰撞检测过程 当虚拟场景中的物体个数为n 的时候，很明显的碰撞检测的复杂度是o ( n 2 ) 。 为提高碰撞检测的效率，我们提出混合碰撞检测的概念。混合碰撞检测是指首先在 虚拟空间测试对物体做近似测试，如果两物体有重合的部分，则进一步的做精确测 试以求两物体相交重合的区间。碰撞检测过程分为两个阶段：一是对物体做近似的 相交测试，若两物体相交，则进入第二阶段的精确碰撞检测阶段。这样的方法对于 检测物体之间的碰撞是一个基本的策略。在精确测试阶段，会有若干次精度不同的 相交测试，最后一次的相交测试应是最精确的，下面我们逐步分析这两个检测阶段： 3 1 1 近似测试阶段 近似相交测试的目标是快速排除不可能发生穿透的物体对象，对于相交重叠的 部分则进入精确测试阶段。我们可以引入四维的时空层次，首先关注可能发生碰撞 的物体，对于在虚拟场景中相距比较远的物体对象，我们可以忽略它们发生穿透的 可能性。 在文献【1 8 】中的i - c o l l i d e 系统中，用层次包围盒方法被修剪排除掉不可能发 生碰撞的物体，对于存在重叠的包围盒则做进一步的精确测试。扫描修剪算法是基 于a a b b 轴向包围盒在三维坐标中三个坐标轴上的投影。若两物体发生穿透，则其 包围盒在三个坐标轴上的投影都应相交。根据时空相关性，物体之间的相对位置在 相邻帧之间不会移动很多。在此我们用插入排序来处理投影重叠测试的问题。 3 1 2 精确测试阶段 任意一种碰撞检测算法都与其采用的结构模型有关系，其采用的数据结构也应 代表该结构模型。在精确测试阶段，准确的碰撞被检测到，距离跟踪法是一类基本 的方法，最典型和具有代表性的是l i n c a n n y 算法和g j k 算法。 l i n c a n n y 算法的思想为：在多面体对之间寻找一对距离最近的点，该点被称 硕士学位论文 m a s t e r st h e s i s 为最近特征点。算法的主要目标是检测两个凸多面体之间是否有穿透， 与l i n - c a n n y 算法不同，g j k 算法不是直接对两凸面体进行搜索和跟踪，而是 在多面体的明氏距离多面体参数空间中搜索跟踪执行。这两种算法各有其优缺点， 其具体实现方法不同。算法除了可以检测物体是否发生碰撞之外，还可以检测物体 相互渗透的程度。 使用层次凸多面体包围盒，上述算法还可以扩展到非凸多面体的碰撞检测中 去，虽然该类算法也适合于非凸多面体，但当虚拟环境中凸多面体对象的数量很多 时，该算法的效率会被降低，因此，只有当虚拟环境中存在较少数量的凸面体时， 算法才会表现出比较高的效率执行度。该算法的缺点是：仅仅适合虚拟环境中的刚 体对象，不适合软体对象的碰撞检测。 隐式曲面常用来描述一个物体对象的形状，通常被用来描述变形物体的变形、 分裂和弯曲。一种基于分段的方法【1 9 】能检测碰撞和处理随后的碰撞反应，然而， 这种方法的速度太慢使得它不适合实时的虚拟环境，当保存处理碰撞反应的结果 时，会出现其它不可预料的结果。 和刚体不同，软体对象常常被分解为许多固体的四面体基本几何元素的集合。 这种方法在虚拟手术中非常普遍，这样场景中的对象可以是手术器械、人体组织， 比如手术刀具。迄今为止，还没有非常高效的方法来处理几何形状任意复杂的软体 对象的碰撞检测问题。 层次包围盒和空间分解是在精确测试阶段常用到的两种方法。层次包围盒方法 的优点是：若父结点对应的包围盒不重叠，则就不用继续对其包含的子结点做重叠 测试。 和上面提到的处理凸多面体间的碰撞检测方法不同，层次包围盒树通过逐层来 接近逼真物体：该方法的目标是对物体做一个近似相识的包围盒以越来越接近物 体，该方法一般是对物体做近似的包围，重叠测试的速度通常由选择的包围盒类型 所决定，近年来国内外学者和专家研究的重点大都是选择合适的包围盒类型，涉及 到的主要有下列包围盒树： a a b b 树。即轴向包围盒树，这种树的优点是计算和相交测试简单。 八叉树。八叉树的建立一般是递归地将物体包含的层次空间分成八个基本 元，直到基本元作为树中的一个叶子结点为止。这样的数据结构是比较容 易产生的，产生的算法效率是有效的。这种方法的缺点是树的每个层次所 对应的结点对物体的包围不是很紧密，会产生不少空隙，造成存储空间的 很大浪费。 1 6 硕士学位论文 m a s t e r st h e s i s 球树。这种方法的优点是当对象旋转的时候，树不需要或很少更新。相交 测试也是很简单。缺点是该类包围盒仅适合几何形状类似球类的物体对象。 c 树。这种树是由凸多面体和球类混合组成 2 0 1 。该树的优点是选择最接近 物体的基本几何元素来包围对象，缺点是这种树的层次必须要手动来创建， 不能自动构造。 o b b 树。这种树是由方向包围盒组成。其相交测试的方法是基于分离轴 的，可以精确的测试复杂几何对象的碰撞反应问题。相对于球树而言，o b b 树的缺点是更新速度较慢。如果虚拟场景中存在大量需要重叠测试的对象， 树更新所造成的存储负担是不可接受的。 s h e l l 树。这种树是由o b b 包围盒和球类包围盒构成。涉及到的曲面有贝 塞尔曲面和n u b r s 曲面。 对于虚拟环境中的刚性物体对象，这些数据结构可以在预处理阶段建立，对象 的形状在仿真阶段一般不会发生改变。但对于软体对象，层次包围盒在每个时间段 内都必须更新，这是因为对象容易发生形变和拓扑结构的变化，这就造成很大的计 算开销。 3 2 层次包围盒树的构造 在层次包围盒算法中，包围盒树的构造是至关重要的，因为构造包围盒树所需 的开销直接能影响到碰撞检测的效率，若包围盒树结构层次得当，则可加速算法。 设输入的物体对象模型表示为包含n 个基本元素的集合s ，定义b w r ( s ) 为一个 包围盒树，它在s 上定义了一个包围盒层次，b w r ( s ) 树的根对应于s ，对应包围 盒b ( s ) ，其每个结点1 ，对应于s 的一个子集& ，对应包围盒b ( s ，) ，男阿p ) 树的非 叶子结点有两个或更多子结点，其最大子结点个数为树b v t ( s ) 的度数，记为口。 任一个非叶子结点1 ，的各个子结点所对应的s 的子集构成s ，的一个划分。在树 口玎( s ) 中，各叶结点分别表示s 集合中的一个基本几何元素构成的子集。 由上述定义可知，树8 v t ( s ) 中没有度数为l 的结点，故b v t ( s ) 树的结点总个 数为2 刀一l 。图3 1 所示为二维空间中的一个包围盒层次结构，所用包围盒类型为圆 1 7 硕士学位论文 m a s t e r st h e s i s 形( 基本几何元素为线段) ：图( 1 ) 所示为根结点，所对应集合s 的包围盒6 ( s ) ， 它包含了所有的线段；图( 2 ) 将集合s 的基本几何元素分为1 ，。，1 ，：，1 ，三部分，其 所对应的包围盒y g b ( v 。) ，b ( v ：) ，b ( v ，) ；图( 3 ) 是以图( 2 ) 所示的每个结点为根， 由于h 只包含一个基本几何元素，故只需对，鸭进行分裂即可，并分别为之建立 包围盒结构，由于它的每个包围盒只有基本几何元素( 线段) ，所以它是最后一层 包围盒。由图3 1 所知，通过构造包围盒层次结构，包围盒愈来愈逼近对象，这就 便于进行对象之间进行碰撞检测。 ( 2 ) 图3 1 包围盒层次结构示意图 ( 3 ) b ( v 2 2 ) b ( v 3 2 ) 从基本元素几何s 上构造一棵b v r ( s ) 可以采用两种方法：自底i 句1 - _ 2 1 方法和 自顶向下 2 2 ，2 3 方法。 1 ) 自底向上方法 自底向上方法是先将输入的基本几何元素作为叶子结点，然后利用局部信 息试图将它们递归地组合起来形成父节点，直至找到一个逼近整个集合s 的根 结点。这一方法的关键是如何将若干个子集合并为父集。典型的例子是 b o x t r e e 2 4 。 2 ) 自顶向下方法 1 8 自顶向下的方法是以s 作为根结点，利用整个集合的性质递归地划分结点 以形成子结点，直至到达叶结点，这一方法的关键是一个集合划分为若干个互 不相交的子集合，典型的例子有o b b t r e e s 和k d o p s 。 这两种方法各有其优缺点，目前尚无定论说明哪种方法更好些。自项向下方法 在实际应用中使用的比较多，方法也成熟些。在使用此方法构造包围盒树时，就涉 及到树的度的问题，由于二叉树的计算最简单快速，在此我们选用二叉树( 口= 2 ) 。 自顶向下的方法关键是将一个父结点对应的集合划分成互不相交的子集( 子结 点) 。本文我们采用的是二叉树，则以上问题就是转换为将s ，划分为两部分，共有 2 ”1 一1 种不同的划分方式( n 为墨，的基本几何元素个数) ，当然不能一一去考虑这 些不同的划分方式，通常用的方法是确定一个平面，根据集合中基本几何元素相对 于平面的几何位置来划分，在此称这个平面为分裂平面。 分裂平面把整个几何空间划分为两个半闭空问，一个基本几何元素或属于其左 半空间，或属于其右半空间，或与其相交。对于前两种情况可以把它们分别划分到 左右半空间中，对于后一种情况，对每个基本几何元素指定其中心为其表现点，根 据表现点位于哪一侧来分配元素，而对于表现点仍然位于分裂平面上的基本几何元 素，把其分配给所含元素较少的空间中去。如图3 2 ，由于三角形c 和a 的几何中 心分别在左半空间和右半空间，故将c 分配在左半空间，a 分配在右半空间，三角 形b 的几何中心在分裂平面上，但因分配到右半空间的三角形较少，故将其分配到 右半空间。 1 9 分裂平面 1 、 一 r 、 - d w 隘天 飞 i 广、? 左半窄问 右半空阀 图3 2 基本几何元素的分配 分裂平面的确定通常由两步完成：确定分裂轴即分裂平面的法线。在分裂 轴上寻找分裂点以定位分裂平面。 1 确定分裂轴：通常使用最长轴方法，即选择方向轴使得包围盒沿轴线方向最长。 构造a a b b 包围盒树时从三个坐标轴中选择包围盒的跨度最大的轴作为分裂 轴；构造o b b 包围盒树时可选择包围盒方向最长的边作为分裂轴 3 1