（计算机软件与理论专业论文）基于aabb包围盒的碰撞检测算法的研究.pdf

硕士学位论文 m a s t e r st h e s i $ 摘要 碰撞检测是计算机动画、计算机图形学、机器人路径规划等领域的重要课题。 近几年来，随着虚拟现实技术和分布式仿真技术的兴起，碰撞检测问题成为一个研 究热点。快速的碰撞检钡4 对提高虚拟环境的真实性、增强虚拟环境的交互性有着至 关重要的作用。 层次包围盒方法是解决碰撞检测问题时间复杂性的一种有效的方法，它是用体 积略大而几何特性简单的包围盒来近似地描述复杂的几何对象，并通过构造树状层 次结构来逼近对象的几何模型。本文首先分析了不同类型的包围盒及其相关算法， 由于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 相交测试的速度直接影响着碰撞检测算法的整体速度，包围盒排序法是 进行a a b b 间相交测试的有效方法。本文采用一维空问排序法将a a b b 的端点值 投影到三个坐标轴上，基于对象运动的时空相关性，选用希尔排序法对投影值序列 进行排序。由于碰撞行为的局部性，算法在排序之前对坐标轴进行适当的划分，避 免了不必要的相交测试，提高了全局搜索阶段算法的速度。 在算法的局部检测阶段，本文从存储空间角度来加快对从b b 树的遍历。由于 构造的a a b b 树是一棵二叉树，树中每个内部节点只有两个孩子节点，结合孩子节 点的包围盒信息可以得到其父结点的包围盒，因此可以压缩存储a a b b 树。算法首 先简化树中每个节点存储结构的包围盒信息，减少父结点和孩子节点间冗余数据的 存储，然后将树中所有叶节点的存储信息放置到其父节点里，从a a b b 树的存储结 构里删除叶结点。实验表明，结合包围盒和叶结点的存储优化，既节省了算法所需 的存储空间，又加快了算法的执行速度。 关键词：碰撞检测；a a b b 包围盒；排序；重叠测试；存储优化 硕士擘位论文 m a s t e r st h e s i s 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 dmm a n yf i e l d s ，s u c ha sc o m p u t a t i o n a l g e o m e t r y , c o m p u t e rg r a p h i c sa n dr o b o tm o t i o np l a n n i n g i nr e c e n ty e a r s ，c o l l i s i o n d 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 f v i r t u a lr 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 n t e c h n o l o g y f a s ta n de x a c tc 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 er e a l i t ya n d e 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 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 s a l le f f e c t i v em e t h o dt or e s o l v et h et 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 sa l i t t 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 o d u r i n gt 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 e a w a yp r i m i t i v e sp a i r s ，w h i c hw i l ln 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 t b e t w e e nb o u n d i n gv o l u m e sa n d j u s td e a lw i t ht 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 fb 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 ft h i sa p p r o a c h t h i sp a p e r a n a l y z e sd i f f e r e n tb o u n d i n gv o l u m e sa n dc o r r e l a t i v ea l g o r i t h m s b e c a u s ea a b b p a r a l l e l sc o o r d i n a t e , w ec h o o s ei tt oa p p r o x i m a t et h eo b j e c t a n a l y z i n gt 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 mb a s e do na a b b ，w ef o u n dt h a tt h es p e e do fa l g o r i t h mc a nb e a f f e c t e db yt h r e ef a c t o r s ：i 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 s ，t r a v e r s i n go f a a b bt r e ea n di n t e r s e c t i o nt e s tb e t w e e np r i m i t i v e s t h i sp a p e rs u m m a r i z e st h em e t h o d s a b o u tt h r e ef a c t o r sa n d p r o v i d e si m p r o v e m e n tm e t h o d sf r o mt e m p o r a l s p a c i a lc o h e r e n c e a n dm e m o r y a p a c e t h ei m p l e m e n t a t i o ns p e e do f c o l l i s i o nd e t e c t i o na l g o r i t h mi sa f f e c t e db yi n t e r s e c t i o n t e s tb e t w e e na a b b b o u n d i n gv o l u m e sd i r e c t l y b o u n d i n gv o l u m es o r t i n gi sa ne f f e c t i v e m e t h o dt oe s t i m a t et h ei n t e r s e c t i o nb e t w e e na a b b w ed o n ta d o p to fi n s e r t i o ns o r t a l g o r i t h mb u tt h ed i m i n i s h i n gi n c r e m e n ts o r ta l g o r i t h mt os o r ta a b b s o r t h o g o n a l p r o j e c t i o n so n t ot h ea x e so ft h e c o o r d i n a t es y s t e m c o l l i s i o ni sal o c a lb e h a v i o r , i e 。a l l o b j e c tc a no n l yc o l l i d ew i t ho b j e c t si ni t sp r o x i m i t ya n di sh a r d l ya f f e c t e db yo b j e c t sf a r a w a yf r o mw h e r et h eo b j e c ti s b u tt h eo r t h o g o n a lp r o j e c t i o n so ft w or e m o v e do b j e c t s c a no v e r l a po no n ea x i sp o s s i b l y , i no r d e rt oo v e r c o m et h i s ，d u r i n gt h es o r t i n g p r o c e d u r e e a c ha x i si sc u ti n t oas e r i e so fs e g m e n t sc o n t a i n i n gt h e ( n e a r l y ) f l a m en u m b e ro f p r o j e c t i o ni n t e r v a l s t h i sw i l lr e d u c et h ec o m p u t a t i o n a lt i m eo fc 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 ，a n ds p e e d su pt h eg l o b a ls e a r c hp r o c e d u r e 硕士擘住论文 m a s t e r st h e s i s c o l l i s i o nd e t e c t i o na l g o r i t h mb a s e do na a b bt r e ei s i m p r o v e df r o mas p a c e p e r s p e c t i v ei nl o c a ls e a r c hp r o c e d u r e f r o mt h ec o n s t r u c t i n gp r o c e s so fa a b bt r e e , t h e a m o u n to fb y t eo fa a b b b o u n d i n g - v o l u m ef o ri n t e r n a ln o d ei sr e d u c e d w ew i d et h e b o u n d i n g - v o l u r n e o u tf r o ml e a t n o d e ss t r u c t u r eb a s e do n af a s t t r i a n g l e - t r i a n g l e i n t e r s e c t i o nt e s ta l g o r i t h m a n dt h e nw i p et h el e a fn o d e so u t w eo p t i m i z et h es t o r a g eo f a a b bb o u n d i n g - v o l u m ea n dl e a fn o d ea tt h es a m et i m e n 坞d i r e c tr e s u ri st h a ti tc a n s a v eal a r g ea m o u n to f s p a c ea n ds p e e du pt h ea l g o r i t h m k e yw o r d s ：c o l l i s i o nd e t e c t i o n ；a a b bb o u d i n gv o l u m e ；s o r t i n g ；i n t e r s e c t i o nt e s t ； m e m o r y - o p t i m i z e d 华中师范大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，独立进行研究工作 所取得的研究成果。除文中已经标明引用的内容外，本论文不包含任何其他个人或 集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在 文中以明确方式标明。本声明的法律结果由本人承担。 作者签名：王魄莱日期：扣7 年z 月是日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有权 保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借 阅。本人授权华中师范大学可以将本学位论文的全部或部分内容编入有关数据库进 行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。同时授权 中国科学技术信息研究所将本学位论文收录到中国学位论文全文数据库，并通 过网络向社会公众提供信息服务。 作者签名：五魂彖 日期：棚年6 月日 导师 日期 本人已经认真阅读“c a l i s 高校学位论文全文数据库发布章程”，同意将本人的 学位论文提交“c a l i s 高校学位论文全文数据库”中全文发布，并可按“章程”中的 规定享受相关权益。囤壶论塞握銮后澄唇；旦圭生；旦= 生i 旦三生筮查! 作者签名：互碗策 日期扣7 年6 月6 日 导师始念哟 嘲。少6 月7 日 硕士擘住论文 m a s t e r st h e s j s 第一章绪论 1 1 研究背景和意义 随着计算机硬件技术的不断发展，虚拟环境已成为计算机科学的一个重要研究 领域，可广泛地应用于教育、国防、医学、艺术、娱乐等多个方面【l l 。在虚拟环境 中，由于用户的交互和对象的运动，对象间经常可能发生碰撞。为了保持环境的真 实性，真实地表现对象的运动，系统需要及时检测到这些碰撞，并计算相应的碰撞 反应，更新绘制结果，否则对象间会发生穿透现象等不真实的现象，破坏虚拟环境 的真实感和用户的沉浸感。例如在一个虚拟手术系统中，为了给训练者提供精确地 力反馈以及沉浸感，碰撞检测模块必须能够把手术器械和人体组织碰撞的结构准确 而又实时地传递给力反馈设备。 近几年来，随着虚拟现实技术和分布式仿真技术的兴起，碰撞检测问题成为一 个研究的热点。碰撞检测在很多领域是非常重要的，例如计算机图形学、机器人学、 计算几何、计算机械学等。在计算机图形学和计算几何里，碰撞检测在很多应用里 出现，比如视频游戏、仿真计算机辅助设计；在机器人学里，碰撞检测是机器人路 径规划和控制的一个必要的组成部分，它帮助驾驶机器离开周围的障碍物。 但是，一个虚拟环境通常包含若干个静止的环境对象和运动着的活动对象，每 一个虚拟对象的几何模型都是由成千上万个基本几何元素( 如四面体或三角形) 组 成的，虚拟环境的几何复杂度使得碰撞检测的计算复杂度大大提高，而参与者与虚 拟环境的交互又要求实时完成，因此碰撞检测模块需要占用大量的存储空间和处理 时间，往往导致系统处理的瓶颈。例如在一个虚拟手术系统中，为了提供给用户真 实的沉浸感以及精确的交互能力，碰撞检测模块必须能够实时的计算手术刀和人体 组织的碰撞并给出精确的碰撞结果。这就要求碰撞检测算法必须具有良好的时间复 杂度以及空间复杂度。 国内外学者在碰撞检测领域做了大量的工作，大部分研究都集中于解决虚拟场 景中刚体对象之间的碰撞检测。相对于刚体对象而言，软体对象( 又称变形体) 有 其特殊的物理特性，它们会在外力的作用下变形，即组成软体对象的基本几何元素 的几何形状的改变和数量上的增减，例如人体的器官软组织或布料。因此，对变形 体对象进行碰撞检测的算法就要求有更好的效率，才能满足虚拟环境的实时性。近 几年的研究热点集中于处理变形体对象的碰撞检测，从各个方面来加速变形体对象 的碰撞检测过程以及解决变形体对象的自碰撞问题。 硕士学住论文 m a s t e r st h e s i s 1 2 问题描述 碰撞问题牵涉到碰撞检测和碰撞响应两部分内容。碰撞检测的目标是发现碰撞 并报告；碰撞响应是在碰撞发生后，根据碰撞点和其它参数促使发生碰撞的对象作 出正确的动作，以反应真实的动态效果。碰撞响应问题属于力学的研究领域【”鼬嗣。 本文研究的主要是碰撞检测问题。 通常碰撞检测可以分为静态碰撞检测、伪动态碰撞检测和动态碰撞检测三类。 其中静态碰撞检测是判断一个活动对象在某一特定的位置和方向是否与环境对象 相交；伪动态碰撞检测是根据活动对象的运动路径检测它是否在某一离散的采样位 置方向上与环境对象相交；动态碰撞检测则是检测活动对象扫过的空间区域是否与 环境对象相交。静态碰撞检测一般没有实时性的要求，其算法是动态碰撞检测算法 的基础；动态碰撞检测的研究一般都考虑到四维时空问题或结构空间精确的建模； 伪动态碰撞检测有关于时间点和运动参数之间的信息，可以通过开发时空相关性获 得较好的性能。虚拟环境中的碰撞检测一般属于伪动态碰撞检测的范围。 虚拟环境中的碰撞检测问题可以简化描述如下：碰撞检测系统的输入模型为一 个静态的环境对象和一个动态的活动对象的几何模型，它们均为基本几何元素的集 合。其中环境对象可以包括刚体对象，也可以包括软体对象，它们的位置和方向不 会发生变化，但软体对象可能会在外力的作用下发生变形。活动对象可以在虚拟环 境中自由运动，方向和大小完全取决于仿真过程或者用户控制的输入设备，无法用 关于时间的运动方程来表示，只能褥到某一时闻采样点相对于前一时闻采样点或一 固定参照物的运动信息( 旋转角度和平移量) 。其任务是确定在某一时刻两个几何 模型是否发生干涉，即它们的交集是否不为空，如发生了碰撞，还需确定碰撞点( 参 与碰撞的基本几何元素) 。 虚拟环境中对象所用的几何模型可分为面模型和体模型两类【7 j 。面模型用对象 的边界来表现对象，而不包括对象内部信息，其基本几何元素多为三角形；体模型 采用体元来描述对象，可描述对象的内部信息，其基本几何元素多为四面体。面模 型相对简单一些，而且绘制技术成熟，处理方便，但难以进行整体形式上的体操作 ( 如拉伸、压缩等) ，多用于刚体对象的几何建模。体模型拥有对象的内部信息， 可以很好地表达模型在外力作用下的体特征( 变形、分裂等) ，但体模型所耗存储 量大，计算量也大，一般用于软体对象的几何建模。 最原始最简单的碰撞检测方法是一种蛮力计算的方法，即对两个几何模型中的 所有基本几何元素进行两两相交测试，尽管这种方法可以得到正确的结果，但当模 硕士擘位论文 m a s t e r st h e s i $ 型的复杂度增高时，这种o ( n 2 ) 次的相交测试也是无法容忍的。例如，对一个包含 1 0 0 ，0 0 0 个三角形的三维环境和一个由1 0 ，0 0 0 个三角形构成的活动对象，如果使用 这种蛮力计算法，那么在活动对象的每一个位置，需要执行l 亿次三角形与三角形 相交测试以确定在当前时间活动对象是否与环境发生碰撞。以当前的软硬件能力， 这大约需要l 2 个小时的时间，这与实时交互所需要的每秒3 0 0 次( 触觉反馈宽 带) 以上的碰撞检测的要求相差甚远，因此，速度是虚拟环境中的碰撞检测的核心 问题【”。 1 3 国内外研究动态 1 3 1 碰撞检测算法 碰撞检测问题的相关研究源于1 9 7 0 年代。近三十年来，研究人员已经在碰撞 检测领域做了相当多有意义的工作，形成了二些较为成熟的技术。碰撞检测算法使 用在很多不同的研究领域，在两个几何模型间的碰撞检测算法大致可分为三类：几 何方法、空间分解法和层次包围盒方法【9 1 几何方法主要是分析每个单独模型的拓扑结构，跟踪并且计算两个或多个模型 问的最近特征( 点、边、面) 。几何方法比较典型的是l i n - c a n n y 算法( 加j 和e n h a n c e d g j k 算法f l l l 。 空间分解法主要是先将整个虚拟空间划分为相等体积的小的单元格，将对象分 配给一个或多个单元格，然后对占据了同一单元格或相邻单元格的所有对象对进行 碰撞检测。空间划分法比较典型的例子有k - d 树【1 2 】。八叉树 2 , 1 3 1 ，b s p 树【1 4 1 5 】，四 面体网和规则网格等。空间分解法通常适用于稀疏的环境中分布比较均匀的几何对 象间的碰撞检测。采用层次划分方法进行空间分解，如八叉树，b s p 树等，可以进 一步提高算法的速度。空间分解法存在的问题是何时终止划分空间单元格以及设置 单元格大小。 层次包围盒方法是碰撞检测算法中广泛使用的一种方法，它曾经在计算机图形 学的许多应用领域( 如光线跟踪等) 0 6 , 1 7 1 8 1 9 1 中得到深入的研究。该方法主要是将 对象以层次方式( 即包围盒树) 组织起来。初检测时根据包围盒间的相交测试快速 排除不相交的对象，再对包围盒相交的对象进行精确的碰撞检测。基于包围盒的碰撞 检测方法的不同点在于树的节点的包围盒类型不同或者采用不同的技术来建立、更 新和平衡包围盒树。典型的包围盒有轴对齐包围盒( a a b b ) 、球包围盒、方向包围 盒( o b b ) 和离散方向凸包围盒( k d o p ) 。 近些年，随着图形硬件计算性能的迅速增长，一类基于图像空间的碰撞检测算 法进入了一个新的快速发展阶段。该方法一般将三维几何对象通过投影绘制到图像 平面上，降维得到一个二维的图像空间；然后分析该空间中保存在各类缓存的信息， 迸而检测出对象之间是否发生干涉。这类算法优势在于能有效利用图形硬件加速技 术来减轻c p u 的计算负荷，从而达到提高算法效率的目的。图形硬件辅助碰撞检 测的方法由s h i n y a 等和r o s s i g n a c 等于1 9 9 1 年前后开创性地提出i 捌。 近年来的研究热点主要集中于变形体对象的碰撞检测。刚体对象在场景中只作 平移和旋转运动，其碰撞检测相比变形体对象而言简单些。变形体对象会在运动中 发生变形，适用于刚体对象的层次包围盒方法就不能直接的用于变形体对象上。当 变形体对象发生变形时，其包围盒树必须实时的重新构建或者更新，而重新构建整 个数据结构的时间耗费在一个实时的仿真环境中是不能接受的，因此在层次包围盒 方法中必须避免整棵树的重新构建。研究者根据不同包围盒的特性进行改进，将层 次包围盒方法也用于变形体对象的碰撞检测。 s m i t he ra l l 2 l j 提出了一种基于a a b b 包围盒的解决变形体对象的方法，该方法 在每一步都重新计算对象的包围盒，其缺点是当模型复杂时不能得到实时计算。 v a n d e n b e r g e n l 2 2 】提出了一种基于s o l i d 库的方法，并在每个时候由叶子节点 开始完成自底向上的更新，缺点是发生大尺度变形时，a a b b 包围盒的紧密性就比 较差并且包围盒与包围盒之间有非常大的重叠区域。 y a s h i f u m ik i t a m u r a t 2 3 】等人提出了一种用于解决复杂场景下的变形体的碰撞检 测算法，这种算法的本质是包围盒方法与空间分解法的结合。此方法的缺点是采用 八叉树的数据结构复杂。 j m e z g e 一2 4 j 等人在模仿布料仿真时对层次包围盒结构作了很多优化。它采用的 包围盒类型是k - d o p s ，由于k - d o p s 在最坏情况下只需k 2 次相交测试，因此j m e z g e r 等人采用的是四叉树。这样做的优点是减少相交测试时递归调用的深度，从某种意 义上减少了内存消耗。另外它还采用了“向量圆锥”来解决自相交问题。 m a t t h i a st e s c h n e r l 2 5 】等人提出了用一种优化的哈希表来解决变形体以及自相交 问题。 国防科学技术大学魏迎梅【s l 等人提出了一种基于固定方向凸包f d h 包围盒层 次的碰撞检测方法，用于虚拟手术仿真，为解决复杂环境中的碰撞检测问题提供了 一条有效的途径。 浙江大学范昭炜【2 0 】等人对实时碰撞检测技术进行了研究，利用图形硬件的高计 算性能、可编程性及多处理机的并行计算能力来加速碰撞检测过程。 4 硕士擘位论文 m a s t e r st h e s l s 1 3 2 常用的包围盒类型 碰撞检测领域中研究最多的包围盒主要有：轴对齐包围盒( a x i sa l i g n e d b o u n d i n gb o x ) 、包围球( s p h e r e ) 、方向包围盒( o r i e n t e db o u n d i n gb o x ) 、离散方 向凸包包围盒( 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 ) 等。 1 、轴对齐包围盒 轴对齐包围盒a a b b ( a x i sa l i g n e db o u n d i n gb o x ) 是一个长方体包围盒，其各 轴的方向与坐标轴的方向一致，即一个给定对象的a a b b 被定义为包含该对象且边 平行于坐标轴的最小的正六面体，如图1 1 ( a ) 所示。a a b b 可表示为 r = ( x ，y , z ) k x 吃， - y - h y ，乞 - z 吃 值。其中，吃，哆，乞，吃分别是该 a a b b 在z 坐标轴上投影的最小和最大坐标值。 锣 ( a ) a a b b 包围盒( b ) 包围球( c ) o b b 包围盒( d ) k - d o p 包围盒( k ) 图1 1 各种包围盒的二维示意图 给定对象的a a b b 的计算十分简单只需分别计算对象中各个元素的顶点的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 的6 个最大最小值的组合，可以得n a a b b 8 个顶点，对这8 个顶点进行相应的旋转，并 根据旋转后的顶点计算新的a a b b 。当对象发生变形后，可以重新计算a a b b 树中发 生变形了的叶结点。可见，a a b b 的优点是包围盒之间的相交检测与方向无关，同 时包围盒占内存少，构造和修改方便，因此也适合于可变形的模型。 基于a a b b 包围盒的碰撞检测算法的相关知识将在第二章作具体介绍。 5 硕士肇位论文 m a s t e r st h e s i s 2 、包围球 包围球( s p h e r e ) 类似于a a b b ，也是简单性好紧密性差的一类包围盒，包围球 被定义为包含该对象的最小的球体。包围球可表示为 r = ( 五乃z ) ( x 一巳) 2 + ( _ ) ，一6 ) 2 + ( z 一乞) 2 0 ：当且仅当a 、b 、c 呈顺时针顺序排 列时有d e t ( a ，b ，o 0 ；当且仅当顶点a 、b 、c 呈顺时针顺序排列时有 d e t ( a ，b ，c ) 0 ，定义点r 位于丽的右侧是指f ， g ，r 呈顺时针顺序排列，即满足d e t ( f ，g ，l ) 0 。 如果顶点a 、b 、c 位于直线f g 的同一侧，则线段f g 与a a b c 不相交； 否则，假设a 、b 位于一侧，而c 位于另一侧，：牙、否否分别与直线f g 相交。如果f 和g 同时位于b c 的右侧或者同时位于c 的右侧( a ，b ，c 按逆时针顺序) ，则线段f g 与m 曰c 不相交；否则相交。 ( 3 ) a a b c 和a p p r 的相交测试 二维平面中两个三角形不相交当且仅当存在某一个三角形的一条边，使得另一 个三角形的三个顶点均位于这条边的右侧( 三角形的顶点按逆时针顺序排列) 。因 此，我们只需依次测试寻找这样的一条边即可，如果不存在这样的一条边，则这两 个三角形相交。 1 9 硕士擘位论文 m a s t e r st h e s l s 2 3 3 改进的三角形与三角形相交测试 三角形与三角形快速相交测试算法通过计算两个三角形所属平面的位置关系来 快速判定三角形是否相交。假定两个三角形分别为t l 和t 2 ，三角形定义为三个顶 点的集合，基本步骤如下i 删： ( 1 ) 计算t 1 的平面方程，得到平面f 1 。 ( 2 ) 计算t 2 的三个顶点，匕。，到平面f 1 的有符号距离分别为d i s t v 2 0 ，d i s t 吃。 ，d i s t ( 3 ) l a d 较d i s t ，d i s t 匕i ，d i s t v 2 2 的符号。果d i s t ，d i s t 匕，d i s t 符号相同，并 且都不等于0 ，则两个三角形的平面平行但不共面，即两个三角形不相交，结束算 法；如果d 衙，d i s t 匕。，d i s t 2 都等于0 ，则t 1 和t 2 共面，则转步骤( 4 ) ；否则，转 ( 5 ) 。 ( 4 ) 执行二维空间中的三角形相交测试。测试t l 的三条边与t 2 的三条边是否 相交，如果有一对边相交，则两个三角形相交；如果每对边都不相交，则进一步进 行顶点与三角形的测试，以此来判断t l 是否在t 2 内部或者t 2 是否在t 1 内部；如 果t 1 和t 2 互不包含，则t l 和t 2 不相交。 ( 5 ) 计算t 2 的平面方程，得到平面f 2 。 ( 6 ) 计算f l 和f 2 的交线l 。 ( 7 ) 分别计算t 1 和t 2 的两条边与l 的交点形成的相交区间，即线段和f ，。如 果区间 和不重叠，则t 1 和t 2 不相交，返回假。否则t l 和t 2 相交，返回真。 2 3 4 改进的三角形与包围盒相交测试 三角形与包围盒的快速相交测试基于“分离轴”理论【4 钔。基本步骤如下： ( 1 ) 将三角形与包围盒平移，使得包围盒的中心与坐标原点重合。 ( 2 ) 计算包围盒与三角形是否能被1 3 条轴线( 从b b 的三个法向量，三角形的 法向量，三角形的三条边分别与包围盒的三个法向量的叉积形成的9 条轴线) 分离 到两侧。如果可以，则两者不相交，返回假；否则只要有1 个轴线不能将两者分离， 则三角形与包围盒相交。当轴线为a a b b 的法向量时，转步骤三；当轴线为三角形 的法向量时，转步骤四；当轴线为向量叉积形成的9 条轴线时，转步骤五。 硕士擘住论文 m a s t e r st h e s i s ( 3 ) 进行包围盒与三角形的最小包围盒的重叠测试。 ( 4 ) 进行平面与包围盒的快速测试。寻找包围盒的与三角形平面法向量方向最 接近平齐的对角线的两个端点，如果最小的端点位于平面的正面，则三角形与包围 盒不相交，否则两者相交。 ( 5 ) 将三角形的三个顶点和包围盒分别投影到轴线上。三角形的三个顶点投影 到轴线上时，寻找投影点的最大值m a x 和最小值m i l l ，包围盒投影到轴线上时，寻 找投影的区间半径r ，如果m a x ，则三角形与包围盒不相交，否则 相交。 2 1 硕士学位论文 m a s t e r st h e s i $ 第三章a a b b 包围盒的全局搜索优化 3 1a a b b 包围盒的相交测试原理 三维空间里的对象相交问题可以转化至4 二维或一维空间里来处理。通过降低维 度来提高处理问题的效率。这里将三维空间的包围盒的重叠测试问题转化到一维空 问来进行。两个包围盒有重叠当且仅当它们在三个坐标轴上的投影区段都有重叠。 证明过程如下： 定理l 如果两个凸多面体不相交，那么一定存在一个空间平面，使得该平面的 法向量或者垂直于其中一个凸多面体的一个面，或平行于分别来自两个凸多面体的 两条边的叉乘积。 定理中的空间平面称为分离面，类似可以定义分离轴，即空间中的一条轴且两 个凸多面体在该轴上的投影区段不重叠。显然一条分离轴存在当且仅当与它垂直的 分离面存在，由此可得如下推理： 推理如果两个凸多面体不相交，那么一定存在一条分离轴，使两凸多面体在该 轴上的投影区段不重叠，且该轴或垂直于其中一凸多面体的一个面，或平行于分别 来自两凸多面体的两条边的叉乘积。 对于a a b b 包围盒，因为a a b b 是凸多面体，所以根据推理可得：若两个a a b b 在三个坐标轴上的投影区段均重叠，那么它们必相交。 又因为a a b b 的三个边方向分别与工、y 、z 三个坐标轴平行，面的法向量方 向也是分别与三个坐标轴方向平行的，所以可能的分离轴方向也只有三个，即工、y 、 z 坐标轴方向，因此，若两a a b b 相交，则它们不存在分离轴，即它们在三个坐标 轴上的投影区段均重叠。 由此证明两个a a b b 包围盒相交当且仅当它们在三个坐标轴上的投影区段均重 叠。这里以二维空间为例，给出了两个对象相交及其a a b b 包围盒投影重叠的状态， 如图3 1 所示。 硕士擘住论文 m a s t e r st h e s i s c a ) 对象相交 ( b ) 对象的a a b b 包围盒相交 图3 1 二维空间里的对象及其包围盒相交 由a a b b 的定义知a a b b 上具有最小和最大x 、y 、z 坐标值的点必定是顶点， 且它们在三个坐标轴上的投影值是该a a b b 在相应坐标轴上投影的最小和最大值 线段。不妨称具有最小坐标值的顶点为最小顶点，同样称具有最大坐标值的顶点为 最大顶点，这样判断两a a b b 是否相交，只要通过分别比较它们的最小顶点和最大 顶点四个点的x 、y ，z 坐标值即可。假设两个a a b b 的最小顶点和最大顶点分别 为日( 厶。，厶。，厶：) ，q l ( q 。，q 。，q ：) 和最( z 。，厶。，厶：) ，q 2 ( 乜。，马。，皿：) ，判断它们 是否相交的具体算法如图3 2 所示： 图3 2 两个a a b b 相交测试算法 3 2 时空相关性 假设在一个应用系统中时间采样点间隔足够小以致对象没有经历大的移动，并 且( 或者) 在两个时间采样点里，对象总的数量没有大的增加或减少，这样应用中 的一些特征在两个连续的时间采样点里没有大的改变，这个属性称为时空相关性。 即从上个时间采样点到当前时间采样点里，对象的移动和变形是微小的，同时，对 象总数量的改变在一个可以接受的范围里。大多数动态应用里都提出了时空相关 硕士学位论文 m a s t e r st h e s i s 性。 在虚拟环境中，对象的运动具有很大的随意性，它通常取决于动态约束或外部 力量的作用，不能用关于时间的函数准确地描述，故而无法提前获得它们在下一时 间采样点的信息。为了达到实时交互的目的，碰撞检测的时间采样点的取值就十分 紧密( 为保证视觉上的自然流畅，刷新速度一般不低于2 0 帧秒，而在力反馈系统 中为保证触觉的真实感，带宽一般不低于3 0 0 h z t 3 8 】) ；此外对象在虚拟环境中进行 六个自由度的旋转和平移运动，其运动路径是连续的。密集的时间采样点使得在一 个时间段内活动对象的位置和状态的变化都很小；同时，在上一个时间采样点，如 果两个对象没有发生碰撞，则在当前的时间点，它们很可能仍不碰撞；如果两个对 象发生碰撞，则在当前的时间点，它们很可能仍发生碰撞，并且碰撞点与上一碰撞 点位置邻近，这一特性说明虚拟环境中对象的运动具有时空相关性。时空相关性使 得相邻时间采样点上的碰撞检测具有很大的相似性，可以利用这一特性有效地提高 碰撞检测的效率。 本文引入时空相关性的概念，利用它来加速对象在系统轴上的排序过程。在当 前时间采样点得到的排序序列对下一个时间采样点而言可以认为是几乎排好序的 序列，这样在碰撞检测算法的全局搜索阶段就可以较快速的从多个对象中找到需要 进一步进行精确碰撞检测的对象。同时本文的后续工作也将利用时空相关性来加快 对象变形后的更新操作。 3 3 从明的排序方法 假设虚拟环境中的每个对象都被一个a a b b 包围盒所包围，如果对所有对象直 接进行两个包围盒问的相交测试，那么所需要的计算时间是比较大的。为了减少计 算时间，可以对包围盒进行排序来确定相交的包围盒，从而确定需要进一步进行碰 撞检测的对象对。如何对包围盒进行排序呢? 本文采用降低维度的方法。 将三维空间中的a a b b 包围盒投影到二维空间，得到一些长方形区域，再对这 些区域进行二维空间排序，确定哪些包围盒有相交，把这个方法称为二维空间排序 法。类似的，也可将三维空间中的a a b b 包围盒投影到一维空间，即x 、y 、z 坐 标轴上，得到一些一维区间，再对三个坐标轴上的投影区间进行排序来确定相交的 包围盒，此方法称为一维空间排序法。 经典的基于a a b b 包围盒的i - c o l l i d e 算法库采用的是一维空间排序法。本文 针对此方法提出了改进方法。文献【3 6 1 也提出了排序的改进方法。在典型的虚拟空间 中，任一时刻只有部分对象会发生碰撞，因此在将包围盒向一个坐标轴( j 轴) 投 影得到一系列区间后，经区间排序，就可以排除掉不与其它任何对象相交的对象。 如果重叠的区间对数不多，就按次序验证这些区间对在其它坐标轴( y 轴、z 轴) 上是否相交。这样不仅节省了存储空间，而且避免了很多无所谓的排序和搜索。有 时，第一次投影排序后排除的对象可能很少。比较稳妥的办法是采用二维空间排序 法，即将对象包围盒向坐标面( 工一y 面) 投影，然后用矩形排序算法进行筛选，最 后验证重叠的矩形对在另一坐标轴( z 轴) 上的投影是否相交。 由3 1 节可知，两个从b b 彼此相交当且仅当他们在相应系统轴上的垂直投影 都是重叠的。这就意味着，三维空间的包围盒重叠测试问题可以简化为一维的，排 序a a b b 的一维投影可以得到重叠区间。对大多数情况，这个排序的列表将拥有时 空相关性，即它们在两个时间采样点的改变是微小的。i - c o l l i d e 算法对投影列表 采用的是插入排序法，本文采用一个特殊的排序算法来有效地处理投影列表：希尔 排序。希尔排序由s h e l l 在1 9 5 9 年【3 9 】首次提出，是一个较老的排序算法。一般来 说，和快速排序或堆排序相比，它的效率比较差。然而，希尔排序作为插入排序的 延伸，对一个近乎排好序的输入，能够达到o ( n ) 的速度，同时也比插入排序要强健 些。因此本文采用希尔排序法对a a b b 在三个坐标轴上的投影值进行排序。 在排序操作时，保存当前时间采样点的投影列表，在下一个时间采样点就只需 要修改运动对象的投影值。同时，还需要跟踪和记录投影区间的重叠状态变化情况， 以此来判断包围盒是否相交。 3 4 排序过程的优化 碰撞行为和其它机械现象类型，它也是一个局部行为，比如碰撞中发生的变形。 也就是说，一个对象仅能和它附近的对象碰撞，几乎不受离它较远的对象的影响。 碰撞的这个属性经常被称为空间定位。例如在图3 3 里，对象b 没有和对象a 接触， 因此它们应该被认为没有碰撞。然而，对象a 和8 在x 轴上的投影重叠，当对所有 对象的投影值一起排序时，对象a 和b 将不可避免的被记录一次重叠。这样，随着 对象数量的增加，重叠测试过程将比排序过程更加费时。 为了克服这点，这里在排序过程中将每个坐标轴划分为一系列包含相同数目投 影区间的子段。当每个坐标轴上的投影区问数不能等值划分时，使得最后一个子段 的投影区间数小于前面的子段含有的投影区阃数。例如在某个坐标轴上有1 1 0 个投 影区间，需要划分为4 个子段，则前3 个子段含有3 0 个投影区间，第4 个子段含 有2 0 个投影区间。一般来说，坐标轴划分的越细，算法的执行速度将越快。但是， 图3 3 二维空间的轴划分 不能无限制的划分下去，在一个方向上一个a a b b 包围盒只能被划分一次。图3 4 中 对象m 被划分了两次，则中间斜线阴影部分将不会参与碰撞检测。而且在实际应用 中，一般也不需要通过细分坐标轴来提高算法的执行性能。如果在应用中碰到了体 积非常大的对象，在执行碰撞检测之前算法也会通过预处理过程将对象划分为一些 体积较小的部分，以方便算法的执行。 图3 4 轴划分的限制 伴随着坐标轴的划分，虚拟环境中的对象也被划分为一系列子部分，子部分服 从于重叠测试。如图3 3 所示，石轴和y