（计算机应用技术专业论文）基于图像空间的碰撞检测.pdf

基于图像空间的碰撞检测 庄华( 计算机应用技术) 指导教师：朱连章( 教授) 徐嘉丽( 副教授) 摘要 本论文详细论述了作者攻读硕士学位期间在碰撞检测方面从事 的研究工作主要从事了基于图像空间的碰撞检测算法的研究工作。 碰撞检测是机器人、动画仿真与虚拟现实等领域中一个非常关键 的问题，其基本任务是确定两个或多个物体彼此之间是否发生接触或 穿透。尽管针对碰撞检测已有了大量有价值的研究成果，但随着诸如 虚拟现实等新兴领域的涌现及随之而来的人们对交互实时性、场景真 实性要求的不断提高，碰撞检测技术所面临的问题也日益突出，其中 最核心的问题是如何有效地提高碰撞检测的速度。 在对各类碰撞检测算法做出全面了解、透彻分析的基础上，针对 碰撞检测技术目前存在的问题，本文详细分析、扩展并验证了一种基 于图像空间的实时碰撞检测算法。该算法对如何利用图形硬件的高计 算性能，加速碰撞检测过程进行了有益的探索性研究。 算法首先在预处理阶段将物体表面分解为凸面片，构建与凸面片 相对应的o b b 凸包围体，并将凸分解结果合理地组织成层次二叉树， 同时采用三角形带压缩这一绘制加速技术加快碰撞检测阶段的绘制 速度。然后算法结合了图形硬件的可编程功能，对c u l l i d e 算法中 潜在碰撞集的特点进行了分析，提出新的裁减方案，以减少物体的相 交测试计算，最后算法将c p u 的相交计算映射到g p u 中，均衡c p u 与g p u 的负载，并通过0 b b 包围盒组成的层次包围体结构来提高物体间碰撞 检测速度。 在p c 机上( c p u 为p 42 4 g ，7 7 8 m br a m ) ，使用v c + + 与o p e n g l 实现了基于图像空间的碰撞检测算法，取得了良好的的效果。 关键词：碰撞检测，0 1 3 8 包围盒，可编程图形单元( g p u ) ，通用计算， 潜在碰撞集 i m a g es p a c e c o l l i s i o nd e t e c t i o n z 硝u a n gh u a ( c o m p u t e ra p p l i c a t i o nt e c h n o l o g y ) d i r e c t e db y p r o f e s s o r z h u l i a n - z h a n g ，a s s o c i a t e p r o f e s s o r x u j i a - l i a b s t r a c t t h i st h e s i sd e s c r i b e st h ea u t h o r sw o r ko nc o l l i s i o nd e c e t i o n t h e r e s e a r c hf o c u s e do ni m a g e s p a c ec o l l i s i o nd e t e c t i o n r e a l t i m ec o l l i s i o nd e t e c t i o ni so r eo f t h em o s ti m p o r t a n tp r o b l e m si n t h ef i e l d so f r o b o t i c s , c o m p u t e ra n i m a t i o n , a n dv i r t n a lr e a l i t y , e t c i t s f i m d a m e n t a lt a s ki st od e t e c tw h e t h e rt h e r ea r ec o n t a c t so rp e n e t r a t i o n s b e t w c c nt w oo ra m o n g m u l t i p l eo b j e c t s t h o u g ht h e r eh a v eb e e nm a n y r e s e a r c ha c h i e v e m e n t so ns o l v i n gt h ep r o b l e mo f c o l l i s i o nd e t e c t i o n , t h i s p r o b l e mi sy e tt ob es o l v e dw i t ht h ee m e r g e n c eo f s u c h t e c h n i q u e sa s v i l t u a lr e a l i t y , a n dt h ed e m a n d so f r e a lt i m ei n t e r a e t i v i t ya n dr e a l i s t i c s i m u l a t i o no f m o t i o n so f v i r t u a lo b j e c t s t h ec o r eo f t h ep r o b l e mi st o i m p r o v e t h es p e e do f c o l l s i o nd e t e c t i o ne f f i c i e n t l y b a s e do nt h ei n t e n s i v es u r v e ya n d c o m p r e h e n s i v ea n a l y s e so f v a r i o u sa p p r o a c h e st oc o l l i s i o nd e t e c t i o n , s e v e r a la l g o r i t h m sh a v eb e e n a n a l y z e d , t h i sp a p e re x p a n d e da n di m p l e m e n t e da n d v e r i f i e dt oe x p l o r e 纽 i m a g es p a c ec o l l i s i o nd e t e c t i o na l g o r i t h m t h i sa l g o r i t h me x p l o r et h e p o s s i b i l i t y o f s p e e d i n g u p t h e p r o c e s s o f c o l l i s i o n d e t e c t i o n o n h o w t o u s e t h eh i g hc o m p u t i n gp o w e ro f g r a p h i c sh a r d w a r e f i r s tt h ea l g o r i t h md e c o m p o s et h es u r f a c e so f a no b j e c ti n t oal i s to f c o n v e xp i e c e sa n do r g a n i z et h ec o n v e xp i e c e si n t oab i n a r yt r e ew i t h n o d e sc o m p o s e do f c o n v e xp i e c e s ，a n db ya d o p t i n gt r i a n g l es t r i p c o m p r e s s i o n , w h i c h i sak i n do f r e a lt i m er e n d e r i n g t e c h n i q u e s f u r t h e r m o r e ，w i t ht h ep r o g r a m m a b l ef u n c t i o no f g r a p h i c sh a r d w a r e ，w e a n a l y s i st h ec h a r a c t e ro fp c s ，m a k eg o o du s eo f n e ww a yo f c u l l i n gt o r e d u c et h ei n t e r s e c t i o nt e s t a tl a s t ，t h ea l g o r i t h mr e a l i z et h em i g r a t i o no f c o l l i s i o nd e t e c t i o nt op r o g r a m m a b l eg p u , i t 啪b a l a n c ：et h el o a db e h w e n c p ua n dg p u ，d u r i n gt h i sp r o c e s s ，t h eo b bw i l lb eu s e dt oi m p r o v et h e s p e e do f c o l l i s i o nd e t e c t i o n u s i n gv c + + a n do p e n g l i m a g es p a c 圮c o l l i s i o nd e t e c t i o nw a s r e a l i z e do np e r s o n a lc o m p u t e rw i t hp e n t i u m v 2 6 6 g h z , 7 7 8 mm e m o r y k e yw o r d s ：c o l l i s i o nd e t e c t i o n , o r i e n t e db o u n d i n gb o x ，g r a p h i c s p r o c e s s i n gu n i t , g e n c r a l - p u r l ) o s ec o m p u t a t i o n , p o t e n t i a l l yc o l l i d i n gs e t 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及 取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得 石油大学或其它教育机构的学位或证书而使用过的材料。与我一同工 作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并 表示了谢意。 签名：泖 。1 1 - 。一加7 年缸月 日 关于论文使用授权的说明 本人完全了解石油大学有关保留、使用学位论文的规定，即：学 校有权保留送交论文的复印件及电子版，允许论文被查阅和借阅；学 校可以公布论文的全部或部分内容，可以采用影印、缩印或其他复制 手段保存论文。 ( 保密论文在解密后应遵守此规定) 学生签名： 导师签名： o 月 莎月 1 日 日 年 年 叼夕 羟 中茸石油大学( 华东) 硕士论文 第j 章绪论 1 1 研究背景和意义 第1 章绪论 碰撞检测是机器人、动画仿真、虚拟现实等领域不可回避的问题 之一，其基本任务是确定两个或多个物体彼此之间是否发生接触或穿 透。之所以需要在物体间进行碰撞检测，是基于现实世界中的一个简 单观察事实，即在不破坏物体的前提下，两个或多个物体不可能同时 占有同一空间区域。有关碰撞检测问题的研究源于1 9 7 0 年代。当时， 在机器人路径规划、自动装配规划等领域中，为检测机器人与场景中 的物体或零件与零件之间是否发生碰撞，产生了一系列碰撞检测算 法。但由于当时的计算条件及具体应用的特性( 如事先可预知机器人 运动的轨迹) 等因素，碰撞检测计算大都不是实时完成的。 随着计算机软硬件及网络等技术的日益成熟，尤其是计算机动画 仿真、虚拟现实等技术的快速发展，人们迫切希望能对现实世界进行 真实模拟，而这其中亟需的关键技术之一即是实肘碰撞检测。目前， 三维几何模型越来越复杂，虚拟环境的场景规模越来越大，同时人们 对交互的实时性、场景的真实性的要求越来越高。严苛的实时性和真 实性要求在向研究者们提出巨大挑战的同时，也令实时碰撞检测再度 成为研究热点 中国石油大学( 华东) 硕士论文第1 章绪论 1 2 国内外研究现状 近二十年来，国内外研究人员己经在碰撞检测领域中做了相当多 有意义的工作，其中有些工作影响重大。 从空间域的角度来分，碰撞检测算法大体可分为两大类：一类是 基于物体空间的碰撞检测算法；一类是基于图像空间的碰撞检测算 法。 基于物体空间的碰撞检测算法一直是人们研究的重点，己有相当 的研究成果。研究人员把各种技术如层次表示法、几何推理、代数范 式、空间划分、解析方法和最优化方法“卜嘲等应用到碰撞检测中，如 国内的王兆其，王志强，李学庆。国外的l i n ，j i m e n e z 。1 等。 多边形表示模型是计算机图形学中最常用的几何模型，其特点是 表示简单、通用，因此很多碰撞检测算法都面向多边形表示模型设计。 多边形表示模型中多边形集合是一种常用的几何表示模型。这种表示 模型中，物体表面被简单地表示为一组多边形的集合。面向这种表示 模型的碰撞检测算法一般有较广的适用范围。 基于特征的碰撞检测算法基本上都是源自于1 9 9 9 年l i n c a n n y 的“最邻近特征算法”。它们都按照多面体的特征( 如顶点、边、面等) 进行区间剖分，并对每个特征建构其相应的v o r o n o i 区域。这类算法 依据v o r o n o i 区域的特性利用物体空间的连贯性提高效率。 而基于单纯形的碰撞检测算法，即g j k 算法。这类算法通常将两 物体看作一个单纯形，通过单纯形的几何特性来计算它们之间的分离 或刺穿距离。 几何模型除了多边形表示模型外，还有一类称为非多边形表示模 中国石油大学( 华东) 硕士论文 第1 章绪论 型，包括了c s g 表示模型、隐函数曲面、参数曲面和体表示模型等。 c s g ( c o n s t r u c t i v es o l i dg e o m e t r y ) 表示模型用一些基本体素如 长方体、球、柱体、锥体和圆环等，通过集合运算如并、交、差等操 作来组合形成物体。c s g 表示的优点之一是它使得物体形状的建构更 直观，即可以通过剪切( 交、差) 和粘贴( 并) 简单形状物体来形成更复 杂的物体。这也使得它更容易找到碰撞的确切位置。由c s g 表示的特 殊性，基于该类模型表示的碰撞检测算法主要面向c a d 应用。 空间剖分法其场景的层次剖分方法主要有均匀剖分、b s p 树、k - d 树和八叉树( o c t r e e ) 等。基于这些空间剖分技术的碰撞检测算法也 频繁出现。但这类碰撞检测算法较难在处理不同的场景和具有不同形 状及复杂度的物体时保持比较一致的检测效率。 层次包围体树法中物体的层次包围体树可以根据其所采用包围 体类型的不同来加以区分，主要包括层次包围球树、a a b b 层次树 ( a l i g n e da x i sb o u n d i n gb o x ) ，0 8 b 层次树( o r i e n t e db o u n d i n g b o x ) ，k - d o p 层次树( 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 ) ，o u o s p o 层次树( q u a n t i z e do r i e n t a t i o ns l a b sw i t hp r i m a r yo r i e n t a t i o n s ) 、 凸块层次树以及混合层次包围体树等等。建构物体层次包围体树既可 采取自顶向下的策略，也可自底向上来进行。目前基于层次包围体树 的算法多数采取自顶向下的方式来建构物体的层次包围体树。采用不 同的层次包围体树的碰撞检测算法各有其优缺点。 另外一类碰撞检测算法就是基于图像空间的，这些算法一般利用 图形硬件对物体的二维图象采样和相应的深度信息来判别两物体之 间的相交情况。这类算法优势在于能有效利用图形硬件加速技术来减 中国石油大学( 华东) 硕士论文第l 章绪论 轻c p u 的计算负荷，从而达到提高算法效率的目的。但是基于图像空 间的碰撞检测算法由于其检测结果的不精确性和依赖硬件支持而一 直发展较慢。近些年，随着图形硬件计算性能的迅速增长，基于图象 像空间的碰撞检测算法进入了一个新的快速发展阶段“1 。 s h i n y a 等和r o s s i g n a c ”1 等于1 9 9 1 年前后开创性地提出了图形硬 件辅助碰撞检测的方法。随后，m y s z k o w s k i “1 等利用模板缓存( s t e n c i l b u f e r ) 检测每帧的变化状况，提出了一种有效的改进算法。1 9 9 9 年及 2 0 0 2 年b a c i u 嗍伽等进一步利用深度缓存和模扳缓存的组合功能，提 高图像空间碰撞检测算法的效率，并使算法可在常规图形工作站甚至 是普通个人台式电脑上运行。2 0 0 1 年h o f f 等和k i m 等将图像空间碰 撞检测算法和物体空间碰撞检测算法结合起来，利用二者优点增强了 算法的功能，同时通过一定的负载平衡策略，在c p u 与图形硬件单元 ( g p u ) 问进行合理调配来保证算法的整体效率。 1 3 研究思路及内容 针对碰撞检铡技术目前存在的问题，本文围绕如何有效地提高碰 撞检测算法的效率以及如何在突破基于图像空间算法在适用性和检 测精度上的局限性等问题上展开了研究，将物体空间碰撞检测算法和 图像空间碰撞检测算法更为合理的结合起来，并以提高碰撞检测效率 和准确率作为主要的研究目标。 具体研究内容包括以下几个方面： ( i ) 利用表面凸分解和凸块层次树使基于图像空间的碰撞检测 算法能够处理任意形状物体之间的碰撞检测，采用三角带绘制加速 4 中国石油大学华东) 硕士论文 第1 章绪论 技术提高算法效率； ( 2 ) 分析了g p u 硬件编程的原理和适用性以及着色语言的原理； ( 3 ) 通过图形硬件的可编程功能，利用其并行性提高基于图像 的碰撞检测算法的速度与精确性，在c p u 与图形硬件单元( g p u ) 间进行 合理调配来保证算法的整体效率； 1 4 主要创新点 ( 1 ) 运用潜在碰撞集理论结合硬件遮挡查询功能减少相交物体 对测试提出新的裁剪方案； ( 2 ) 通过数据预处理阶段建立层次包围体进行算法优化，并将 最终的检测映射为流计算模式； ( 3 ) 将碰撞检测的各个检测阶段在c p u 与g p u 间进行负载均衡， 使得算法更为合理。 1 5 论文的组织结构 第1 章为绪论，介绍了课题产生的背景，国内外研究现状和所面 临的问题，进而提出了本文的研究目标，以及它所具有的价值意义， 并简述了论文主要工作内容，最后给出了各章内容安排； 第2 章介绍了碰撞检测算法的一般框架；并对各个阶段的具体方 法作了详细的分析； 第3 章介绍目前主要的几种碰撞检测算法，包括面向凸体的、基 于一般表示的和基于层次包围体树以及基于图像空间的碰撞检测算 法等； 中国石油大学( 华东) 硕士论文 第l 章绪论 第4 章介绍了g p u 通用计算。首先分析了6 p u 可编程的硬件原理， 然后列举了已经成功运用的各个领域的通用计算，最后讲述了g p u 编 程的语言工具； 第5 章介绍一种新的基于图像空间的快速碰撞检测算法。该算法 将图形硬件的计算优势和简化的几何模型表示结合起来实现复杂物 体间的实时碰撞检测，并利用潜在碰撞集的理论进行算法优化，并利 用g p u 的并行性，将最后精简的相交测试计算映射为流模式； 第6 章对整篇论文做了概要的总结，并对进一步的工作做了展望。 6 中国石油大学( 华东) 硕士论文 第2 章碰撞检测算法过程 第2 章碰撞检测算法过程 总体而言，碰撞检测算法在处理包含大量物体的复杂场景时，或 者首先将多数明显不相交的物体对进行快速排除，然后再对可能相交 的物体对进行进一步检测，或者采用场景空间剖分( 如场景八叉树) 来 快速确定可能存在物体相交的区域，然后在这些潜在的相交区域中进 行下一步操作。我们把这个过程统称为碰撞检测算法的初步检测阶 段。而对于初步检测阶段的后继阶段，我们称之为碰撞检测算法的详 细检测阶段。在详细检测阶段中，基于层次包围体树的碰撞检测算法 首先会同时遍历物体对的层次树，递归检测层次树节点之间是否相 交，直到层次树叶子节点，进而精确检测叶子节点中所包围的物体多 边形面片或基本体素之间是否相交。而基于空间剖分的碰撞检测算法 在详细检测阶段则逐步地对潜在相交区域进行细分，并检测细分后的 子区域内是否有物体相交，直到细分子区域中发现有不同物体的基本 体素或多边形面片之间发生精确相交。 分析这些算法在详细检测阶段的步骤，可将其划分为两个层次， 一是逐步求精层：二为精确求交层。在逐步求精层中算法进行层次树 的遍历或者逐步细分潜在的相交区域。而精确求交层中算法主要处理 多边形面片或基本体素之间的精确相交检测。由此可归纳出一个统一 的碰撞检测算法框架，如图2 1 所示。 中国石油大学( 华东) 硕士论文第2 章碰撞检测算法过程 详细检测阶段 勰戮糕需灞熟麓嚣 p 糊蚧段p 矛聱譬鬟匕= 确求享曼，i ? 激施蓬；鬣蠡缀鬟 图2 - 1 碰撞检测算法的一般框架 2 1 初步检测阶段 当动态场景中物体的个数超过两个，碰撞检测遇到的最明显的问 题就是需要对所有n 个物体进行两两求交检测，其时间复杂度达到0 ( n 2 ) 。这个问题也被称为“完全物体对检测问题”。很明显，这是 任何碰撞检测算法在处理多物体的场景时都会遇到的严重影响算法 效率的问题。因此，当场景中物体个数较多时，非常有必要利用一些 优化策略或方法来快速排除明显不发生碰撞的物体，找出潜在的相交 区域或潜在的相交物体对。初步检测阶段所采用的技术主要有两种： 一种是空间剖分法”；另一种是基于插入捧序的“掠扫和裁剪”法 ( s w e e pa n dp r u n e ) 伽。 空问剖分法将场景均匀剖分成一个小方块区间，检查这些小方块 内是否有物体存在，否则将不包括物体的区间剔除，从而快速判断出 潜在的相交区域。空间剖分方式如图2 2 所示。 8 中国石油大学( 华东) 硕士论文 第2 章碰撞检测算法过程 图2 - 2 空间翻分不例 另一种初步检测的方法是c o h e n 等提出的“掠扫和裁剪”法。掠 扫和裁剪法将场景中所有物体的a a b b 包围分别投影到x ，y ，z 三个 坐标轴上，并对每个物体在各坐标轴投影区间的边界值进行排序。两 个物体包围盒在所有坐标轴的投影区间均有重叠时表明这两物体的 包围盒相交。图3 3 给出了物体包围盒在一个轴向的投影情况由于 时间连贯性，场景中物体发生移动时每帧之间物体的相对位置不会发 生明显的改变，它们的包围盒在各坐标轴的投影位置也就不会有明显 的变化。插入捧序法在处理基本有序的队列捧序时非常快速有效，因 此算法采用插入捧序法有效保持各轴上的区间边界表有序，同时检查 投影位置的变化情况。当发现物体a a b b 包围盒有重叠时才触发算法 详细检测阶段的运行。 9 中国石油大学( 华东) 硕士论文第2 章碰撞检测算法过程 1 23 图2 - 3 掠扫与裁减方法中物体包围盒在一个轴向的投影情况 “掠扫和裁剪”方法的时间复杂度为0 ( n ) ，因此用其处理“完 全物体对检测问题”非常有效，计算负荷也很小。它虽然不能处理固 定步长所引起的刺穿问题，但对于物体个数一定的场景可以确保在常 数时间内完成初步碰撞检测。这就使得它在处理有大量运动物体且要 求稳定帧率的动态场景中的碰撞检测时具有一定的优势。 2 2 详细检测阶段 碰撞检测算法经过初步检测阶段确定了潜在的相交区域或潜在 的相交物体对集合之后，转入详细检测阶段。详细检测阶段已经确定 的潜在的相交区域或潜在的相交物体对集合做进一步的相交测试。这 个过程又分为两个层次，一个是逐步求精层：一个是精确求交层。 2 2 1 逐步求精层 一般算法框架中详细检测阶段的逐步求精层通常采用两种典型的 l o 中国石油大学( 华东 硕士论文 第2 章碰撞检测算法过程 加速技术：空间层次剖分技术和层次包围体树技术。 空间剖分技术与初步检测阶段的空间剖分技术相类似，但要把潜 在的相交区域子空间继续剖分下去，直到找到相交物体的多边形面 片。 。 层次包围体结构树技术是指算法利用预先建构好的物体层次包 围体树，通过同时遍历物体对的层次包围体树，递归检测它们层次包 围体树上的各层节点包围体之间的相交情况，直到各个层次树的叶子 节点，最终获取物体对的相交检测结果的技术。不同层次树叶子节点 所包含的多边形之间的相交检测则由精确求交层的相交检测过程来 完成。作为示例，图2 3 给出了一个遍历层次包围体二叉树的递归算 法伪代码。构建层次包围体树的好处就是物体包围体之间的相交测试 极为简单，能够排除不交情况。层次包围体树在每一层中不断逼近物 体，这本质上也是一种用层次细节( l e v e lo fd e t a i l ，l o d ) 表示物 体的方法，但又不同于在快速绘制复杂物体或山脉地形表面时采用多 分辨率方法中使用的多边形层次细节。在实时绘制中使用层次细节技 术的目的是为了在加快绘制速度的前提下，尽可能地保证绘制结果与 初始模型近似。而在碰撞检测的逐步求精层采用l o d 技术总是尽量保 守地逼近原物体模型，选择包围体的首要准则不是如何更逼近原模 型，而是保证包围体之间的相交检铡速度。 输入：a ，b 两物体的层次包围体二叉树b v t ， b v t “。 输出布尔值。t r u e 为相交，f a l s e 为不相交。 b o o ld e t e cr e c u r s i v e ( b v t 。，b v t b ) 中国石油大学( 华东) 硕士论文第2 章碰撞检测算法过程 i f ( 检测到b v t 。与b v t “两个包围体之间不相交) 返回两物体不发生碰撞的结果： i f ( b v t ，b v t 。均为叶子节点) 精确检测b v t 。，b v t “所包围的多边形面之间是否相交； 返回精确求交检测的结果； e l s ei f ( b 儿为叶子节点，b v t 。为非叶子节点) d e t e c t _ r e c u r s i v e ( b v t 。，b v t h 的左子节点) ； d e t e c tr e c u r s i v e ( b v t 。，b v t h 的右子节点) ； e l s ei f ( b n 为非叶子节点，b v t 。为叶子节点) d e t e c t _ r e c u r s i v e ( b v t 。的左子节点，b y t b ) ； d e t e c tr e c u r s i v e ( b v t 。的右子节点，b v t b ) ； e l s e b v t ，b v t “均为非叶子节点 d e t e c t _ _ r e c u r s i v e ( b v t h ，b v t h 的左子节点) ； o e t e c tr e c u r s i v e ( b v t b ，b v t b 的右子节点) ； d e t e c t _ _ r e c u r s i v e ( b v t 。的左子节点，b v t b ) ； d e t e c t _ r e c u r s i v e ( b 1 忆的右子节点，b v t h ) ； 图2 - 3 层次包围体二叉树的递归遍历算法 2 2 2 精确求交层 如前所述，任何碰撞检测算法都要依赖于物体的表示模型。详细 检测阶段的精确求交层便极大地依赖于物体所采用的表示方法。在精 中国石油大学( 华东) 硕士论文第2 章碰撞检测算法过程 确求交层中，碰撞检测算法主要处理多边形面片或基本体素之间的精 确相交检测。 基于多边形表示的碰撞检测算法在精确求交层中需要进行多边 形与多边形之间的相交检测。由于多边形均可转化为三角形，并且三 角形之间的相交检测更简单，因而有很多研究工作集中于三角形之间 的快速相交检测。 精确求交并不一定总是通过三角形的相交检测来实现。对于凸体 之间的碰撞检测可以通过计算两者之间的距离或刺穿深度来实现。例 如l i n 和c a n n y 所提出的基于特征的碰撞检测算法就是通过找出最邻 近特征的距离来判断两物体是否精确相交。类似算法还有g i l b e r t 等 提出的基于单纯形的碰撞检测算法。该算法也是通过计算物体之间的 距离来判断物体是否相交。 中国石油大学( 华东) 硕士论文 第3 章碰撞检测算法 第3 章碰撞检测算法 下面介绍碰撞检测领域的代表性研究工作和最新研究成果，具体 分为以下四个方面：( 1 ) 面向凸体的碰撞检测算法；( 2 ) 基于一般表示 的碰撞检测算法；( 3 ) 基于层次包围体树的碰撞检测算法；( 4 ) 基于图 像空间的碰撞检测算法。 3 1 面向凸体的碰撞检测算法 面向凸体的碰撞检测算法大体上又可分为两类：一类是基于特征 的碰撞检测算法；另一类是基于单纯形的碰撞检测算法。 3 1 1 基于特征的碰撞检测算法 顶点，边和面称为多面体的特征。基于特征的碰撞检测算法主要 通过判别两个多面体的顶点、边和面之间的相互关系进行它们之间的 相交检测。所有基于特征的方法基本上都源自于l i n - c a n n y o ”的工作。 l i n - c a n n y 算法通过计算两个物体间最邻近特征的距离来确定它 们是否相交。该算法利用了连贯性来加快相交检测的速度。具体地， 因为在连续的两帧之间最邻近特征一般不会明显变化，因此可通过将 当前的最邻近特征保存到特征缓存中来加快下一帧的相交检测速度。 当最邻近特征发生了变化后，算法依据特征的v o r o n o i 区域先查找与 上一帧中保留特征的相邻特征，以此提高查找效率，从而提高相交检 测的效率。当碰撞检测的时间步相对物体移动速度较小时，算法可在 1 4 中周石油大学( 华东) 硕士论文 第3 章碰撞检测算法 预定的常数时间内进行特征跟踪。这里假定碰撞检测算法每个循环计 算是在场景运动变化后进行的。 i c o l l i d e 是以l i n - c a n n y 算法为基础，结合了时间连贯性的一个 精确的碰撞检测共享库，可用于由凸多面体构成的模型，并能够处理 多个运动物体组成的场景。 然而，l i n - c a n n y 算法并不能够处理刺穿多面体的情况。面对刺 穿情况，算法会进入死循环。一个简单的解决办法是在算法达到最大 循环数后强制中止，返回物体发生碰撞。但这种解决方法太慢，且无 法判定物体是否真正相互刺穿。事实上，只要物体不是移动太慢或碰 撞检测的时间间隔不是十分短，物体相互刺穿的现象非常常见。算法 无法检测刺穿，这对实时应用环境和虚拟现实是不可想象的。当相互 刺穿发生又要求更精确的接触时间信息时，就要回溯到碰撞发生的精 确瞬间，这种过程也是非常缓慢和繁琐的。p o n a m g i 等引入了凸多面 体的伪内部v o r o n o i 区域来克服这个问题。但同时引入了需要解决的 其它问题，包括如何处理平行特征面等特殊情况和如何配置容错阈值 以将算法调整到理想性能等问题。 另一个具有代表性的基于特征的碰撞检测算法是v - - c l i p ( y o r o n o i - c l i p ) 。m i r t i c h 宣称解决了l i n - c a n n y 算法的局限性。 v - c l i p 算法能处理刺穿情况，不需要用容错阈值来调整，而且不会有 死循环的现象。同时由于特例情况少而实现起来更加简单它是目前 所有算法中，处理凸体之间的碰撞检测最快速有效的算法之一。v c i i p 既可以处理凸体，也可处理非凸体，甚至还可处理不连通的物体，在 物体发生刺穿时还能返回刺穿深度。它的算法效率相对i - c o l l i d e 和 1 5 中国石油大学( 华东) 硕士论文第3 章碰撞检测算法 e n h a n c e dg j k 有明显的改善，而且比较强壮。 之后，北卡罗莱纳大学e h m a n n 等开发的s w i f t ( s p e e d yw a l k i n g v i ai m p r o v e df e a t u r et e s t i n g ) 算法达到了更优的算法效率。该算 法结合了基于v o r o n o i 区域的特征跟踪法和多层次细节表示两种技 术，可适用于具有不同连贯性程度的场景，并能够提高碰撞检测的计 算速度。它比i - c o l l i d e ，v c l i p 和e n h a n c e dg j k 算法速度更快，也更 强壮，但在少数情况下还是会陷入死循环。比较可惜的是，它一般只 处理凸体或由凸块组成的物体。算法能够检测出两物体的相交情况并 计算出最小距离，确定出相交的物体对，但并不能求出刺穿深度。 针对s w i f t 算法仅能处理凸体的缺陷，e h m a n n 等通过对s w i f t 算法 进行扩展提出3 s w i f t + + 算法在预处理阶段将场景中所有物体进行表 面凸分解，并重新组织凸分解产生的结果凸片，建构出各个物体的凸 块层次树( 图4 1 ) 。与r a p i d ，p q p 和q u i c k c d 等算法相比，s w i f t + + 的性能更加可靠，不受场景复杂度的影响。算法能处理任意形状物体 间的碰撞检测，它除了可返回两物体对的相交检测结果，还可计算出 最小距离和确定相交部分的信息( 如点，边，面等) ，但仍不能求出 刺穿深度。 3 1 2 面向单纯形的碰撞检测算法 这类算法是d n g i l b e r t ，j o h n s o n 和k e e n r t h i 率先提出的，称为 g j k 算法。面向单纯形的碰撞算法是与基于特征的算法相对应的一类 算法。 g j l ( 算法以计算一对凸体之间的距离为基础。假定两凸体a 和b ， 1 6 中国石油大学( 华东) 硕士论文 第3 章碰撞检澳i 算法 用d ( a ，b ) 来表示a 与b 之间的距离，则距离可以用下面公式( 3 1 ) 表示： d ( a ，b ) = m i n li x y ii ：x e a ，y e b ( 3 一i ) 算法将返回两物体间最邻近的两个点a ，b ，它们满足公式( 3 2 ) ： i a b il = d ( a ，b )a e a ，b b ( 3 2 ) a ，b 之间距离用m i n k o w s k i 和a - b 的形式可表示为公式( 3 3 ) ： dc a ，b ) = ii v ( a b ) ll ( 3 3 ) 其中v ( c ) 为c 中的点到原点的距离，也即公式( 3 4 ) ： v ( c ) e c 且ii v ( c ) | | = m i n | f x ll ：x e c ( 3 4 ) 从而就有a - b = v ( a - b ) 。 这样算法就将a ，b 两凸体间的相交检测转化为在单纯形( a _ b ) 上找出距离原点最近的点。单纯形是三角形在任意维度上的概括性名 称，多数情况下都可把多面体看作一个点集的凸包。相交检测所有操 作都在这些点的子集所定义的单纯形上进行。 g j k 算法的主要优点在于除了可检测出两物体是否相交，还能返 回刺穿深度。r a b b i t z 利用连贯性对g j k 进行了改进。c a m e r o n 等又 进一步改进了该算法，提出了g j k 增强算法( e n h a n e e dg j k ) 。g j k 增强算法在g j k 的基础上引入了爬山思想( h i l lc l i m b i n g ) ，提高了 算法效率。该算法性能与i - c o l l i d e 和v c l i p 算法性能相近，能够在 常数时间内计算出两凸体对之间的距离。该算法在时间复杂度上基本 和l i n - c a n n y 相同，但同时它又克服了l i n - c a n n y 算法主要的弱点。 l i r t i c h 称v - c l i p 算法比e n h a n c e dg j k 算法需要更少的浮点运算， 效率更高，但同时他也承认c j k 类的算法能更好地计算刺穿深度。 1 7 中国石油大学( 华东) 硕士论文第3 章碰撞检测算法 b e r g e n 等开发的s o l i d 算法( s o f t w a r el i b r a r y f o r i n t e r f e r e n c ed e t e c t i o n ) ，也是一个基于g j k 的碰撞检测算法。它 除了采用g j k 的基本思想，还结合了基于a a b b 的掠扫和裁剪的增量 剔除技术，并通过缓存上一帧中物体对的分离轴，利用帧与帧的连贯 性来判别潜在的相交物体对，以加快算法效率。 所有面向凸体的算法都宣称精确求交处理非凸的多面体也是简 单的，认为非凸多面体可由凸子块组成的层次结构表示。这些算法先 对凸子块的包围体进行相交测试，如果发现相交再进一步检测包围体 内的凸子块是否相交，因此称为“开包裹法”。这些算法本身虽然对 凸体特别有效，但当物体的非凸层次增加时，它们的检测速度会迅速 下降。因此这些算法更适用于对包含少量凸体的场景进行实时碰撞检 测。对于其他情况，基于层次表示的碰撞检测算法将更加实用。 3 2 基于一般表示的碰撞检测算法 碰撞检测算法中有不少是专门面向某种墨体表示模型而设计的， 包括面向c s g 表示模型的碰撞检测算法、面向参数曲面的碰撞检测算 法和面向体表示模型的碰撞检测算法等。 3 2 1 面向c s g 表示模型的碰撞检测算法 z e i l l e r 提出了一种面向c s g 表示模型的碰撞检测算法。他将算法 分为三个部分。第一部分求, h c s g 树的每个节点的包围体用于快速确 定可能的相交部分：第二部分针对所有c s g 树表示的物体创建类似八 叉树的层次结构，采用这种结构找到同时包含两物体体素的予空间； 1 8 中圊石油大学( 华东) 硕士论文 第3 章碰撞检测算法 在最后一部分，检测子空间中基本体素之间的相交关系。 s u 等在算法预处理阶段首先将c s 6 表示模型转化为边界表示模型 ( b r e p ) ，然后混合两种表示，把每个c s 6 的基本体素与对应b r e p 的面 片关联起来。此外，还对c s g 树中的非叶子节点建构相应包围体，并 在相交检测时采用自适应的包围体选择策略以快速确定潜在相交区 域，从而提高算法效率。该算法结合了包围体技术的快速性和基于多 边形表示相交检测的精确性来提高碰撞检测算法效率。与s u 算法相类 似的还有p o u t r a i n 等提出的一种混合边界表示和c s 6 表示的碰撞检测 算法。算法利用了包括c s g 在内的多种表示方法，将包围体、层次细 分和空间剖分等技术融合起来实现实时碰撞检测。 3 2 2 面向参数曲面的碰撞检测算法 t u r n b u l l 等提出了一种面向n u b r s 表示凸体的碰撞检测算法，该 算法借助“支持映射”( s u p p o r tm a p p i n g ) 来求出两凸体之间的距离。 “支持映射”通过给定的支持函数( s u p p o r tf u n c t i o n ) 和方向，获取 两个凸体之间的最小距离，同时返回两物体距离最近的两个顶点，如 图3 1 所示。利用这种思想t u r n b u l l 提高了n 1 j b r s 曲面表示物体间的碰 撞检测速度。等也提出了其他面向参数曲面的碰撞检测算法。 1 9 中国石油大学( 华东) 硕士论文第3 章碰撞检测算法 图3 - 1 支持映射示例 3 2 3 面向体表示模型的碰撞检测算法 面向体表示模型的碰撞检测算法通常用于虚拟手术，因为体表示 模型可以表示物体内部的相关数据。体表示的简单性也使其可用于对 碰撞检测算法速度要求极高的应用，如面向触觉反馈的碰撞检测计 算。触觉反馈中由于人对触觉的敏感度，系统对碰撞检测的计算要求 非常高，通常要求刷新频率达到1 0 0 0 h z 。对于如此高的计算速度要求， 除结合具体场景的特点来加速算法外，往往会考虑以牺牲精度为代价 来提高碰撞检测的速度。 m c n e e l y 等在1 9 9 9 年针对b o e i n g 公司飞机设计时所遇到的问题， 提出了一种相当快速的面向触觉反馈的实时碰撞检测算法v o x e l m a p p o i n t s h e l l 。该算法将整个场景先均匀分割为小的立方体，称为体素 ( v o x e l ) ，然后把场景中静止的部分组织为一个类似八叉树的层次结 构树，同时从运动物体所占用的体素中获取点壳( p o i n t s h e l l ) 来表 示运动物体。如此，检测运动物体是否与静止物体发生碰撞就只需判 中国石油大学( 华东) 硕士论文 第3 章碰撞检测算法 断点壳上的点是否位于包含静止物体的体素之内。该算法的特点是能 处理任意形状的物体，碰撞检测速度非常快速且强壮，但遗憾的是它 不能有效处理含有大量运动物体的动态场景，且碰撞检测的精度也比 较低。 面向特定表示模型的碰撞检测算法一般有其特殊的应用领域，例 如，面向c s g 表示模型和面向参数曲面表示的碰撞检测多用于c a d 应用 中，它们检测速度较慢，但一般比较精确。而面向体表示的碰撞检测 算法在虚拟手术中较常用，也有用于触觉反馈中的。这类算法的优势 在于可以对物体的内部进行处理，并能够达到较快的检测速度，但由 于体表示的不精确性使其很难保证碰撞检测结果的精确性。 3 3 基于层次包围体树的碰撞检测算法 在算法分类中，曾讨论过在碰撞检测算法中所使用的包围体类 型。对应于每一类的包围体都有一个代表性的碰撞检测算法。下面一 一讨论，并对它们的优缺点进行比较。图3 2 演示了包围体的类型? ( a ) 包围球( b ) a a b b 包围盒( c ) o b b 包围体( d ) 6 - d r o p 包围体 图3 -