（计算机软件与理论专业论文）基于三角网格的变形体碰撞检测算法研究.pdf

浙江大学硕士学位论文 摘要 随着计算机图形学的飞速发展，呈现在人们面前的三维世界越来越逼真，然 而技术的进步带来的不仅仅是漂亮的画面，物理模拟给人们带来的是真实的感 受。物理模拟在影视制作、计算机游戏等应用领域占据越来越重要的地位，它释 放了人们的想象，给我们带来了空前的互动性。作为物理模拟中的重要一部分， 碰撞检测引起了人们越来越多的关注，特别是可变形体碰撞检测技术，它不但是 近期计算机图形学的研究热点，而且在布料模拟和虚拟手术中有着极为重要的应 用，因此，本文对面向布料模拟的可变形体碰撞检测技术进行了描述和讨论。 碰撞检测是整个物理模拟过程中计算负担最重的部分，常常是瓶颈所在，两 对于可变形体的碰撞检测，这种瓶颈现象显得更为明显，因为与刚体碰撞检测相 比较，可变形体的碰撞检测有更多的问题需要考虑和处理：无法进行有效的预处 理、可能存在的自碰撞检测、精确获取碰撞信息等等。在以实时性和交互性为特 征的应用中，比如虚拟手术、游戏等，有效的可变形体碰撞检测算法对模拟的性 能有着极其重要的意义。 本文以布料模拟为应用对象，对可变形体碰撞检测技术进行了讨论，涉及到 两种经典算法，并对算法中的各方面问题进行了描述。从总体上来讲，本文的主 要贡献和创新如下： 1 利用基于基元连通性的自底向上方法创建层次包围体，并在创建过程中 记录基元的邻接关系，为自碰撞查询提供必要的信息。 2 借鉴混合式更新方法的思想，对自顶向下更新方法进行改进。 3 在自碰撞查询中对层次包围体节点进行“兄弟”方式的碰撞查询，从而 消除冗余查询。 4 改进了以基元为对象的空间哈希方法，突破了用于体模型碰撞检测的“点 一四面体”碰撞查询。 本文第一章介绍了可变形体碰撞检测的背景知识、研究现状以及本文的研究 内容：第二章介绍了用于可变形体碰撞检测的基元碰撞检测以及一些特殊情况下 的改进；第三章和第四章分别介绍了层次包围体算法和空间剖分算法，对其中的 涉及到众多问题进行了分析，并列出了关键问题和较难理解问题的算法伪码；第 五章介绍了c d k i t 库的设计、实现与应用：第六章总结全文，并对一些将来的 研究进行了展望。 关键字：物理模拟，碰撞检测，可交形体碰撞检测，布料模拟，虚拟手术，自碰 撞，碰撞查询，层次包围体，空间剖分。 浙江 学硕士学位论文 a b s t r a c t b e n e f i t e df r o mt h er a p i dd e v e l o p m e n to fc o m p u t e rg r a p h i c s ，t h e3 dw o r l dp r e s e n t s u si sm o r ea n dm o r er e a l i t y b u tt h ed e v e l o p m e n to f t e c h n o l o g yn o to n l yb r i n g sp r e t r y s c e n e s ，b u ta l s ot h er e a lf e e l i n g a sam a i np a r to fc o m p u t e rg r a p h i c s ，p h y s i c a l l y b a s e ds i m u l a t i o np l a y sa ni m p o r t a n tr o l ei nm o v i ep r o d u c t i o na n dc o m p u t e rg a m e s i t r e l e a s e so u ri m a g i n a t i o na n db r i n g su sm u c hm o r ei n t e r a c t i v ef e e l i n g st h a nb e f o r ea s a l li m p o r t a n tp a r to f p h y s i c a l l yb a s e ds i m u l a t i o n ，c o l l i s i o nd e t e c t i o ni sm o r ea n dm o r e a t t r a c t e d b yp e o p l e ，e s p e c i a l l y t h ec o l l i s i o nd e t e c t i o nf o rd e f o r m a b l e o b j e c t s c o l l i s i o nd e t e c t i o nf o rd e f o r m a b l eo b j e c t sh a sb e e nam a j o ri n t e r e s to ft h er e s e a r c ho f c o m p u t e rg r a p h i c sr e c e n t l y ，a n di tp l a y sa ni m p o r t a n tr o l ei nc l o t hs i m u l a t i o na n d s u r g e r ys i m u l a t i o n t h i st h e s i sd i s c u s s e st w ok i n d so fc l a s s i c a la l g o r i t h m si nt h ea r e a o f d e f o r m a b l ec o l l i s i o nd e t e c t i o nf a c e dt ot h ec l o t hs i m u l a t i o n t h ec o m p u t a t i o n a lb u r d e no fc o l l i s i o nd e t e c t i o ni sv e r yh e a v ya n di ti sa l w a y st h e b o t t l e n e c ko ft h ep h y s i c a l l yb a s e ds i m u l a t i o n c o m p a r e dt oc o l l i s i o nd e t e c t i o nf o r r i g i do b j e c t s c o l l i s i o n d e t e c t i o nf o rd e f o n n a b l eo b j e c t si n t r o d u c e sa d d i t i o n a l c h a l l e n g i n gp r o b l e m s ：w e c a n td oe f f i c i e n tp r e - p r o c e s s ；s e l fc o l l i s i o nh a st ob e c o n s i d e r e d ；h o wt oa c q u i r ep r e c i s ec o l l i s i o ni n f o r m a t i o na n de t c i ni n t e r a c t i v eo r r e a l t i m ea p p l i c a t i o n ss u c ha sv i r t u a ls u r g e r ya n dc o m p u t e rg a m e s ，t h ee f f i c i e n c yo 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 m sf o rd e f o i m a b l eo b j e c t si se s p e c i a l l yi m p o r t a n t t h i st h e s i sd i s c u s s e st w ok i n d so t lc o l l i s i o nd e t e c t i o na l g o r i t h m sf o rd e f o r m a b l e o b j e c t s ，a n dd e s c r i b e sa l lk i n d so fp r o b l e m si nt h ea l g o r i t h m s s p e c i f i c a l l y , w em a k e t h ef o l l o w i n gc o n t r i b u t i o n sa n di n n o v a t i o n s ： 1 i n t r o d u c i n gt h eb o t t o mt ou pa l g o r i t h mb a s e d o nt h ec o n n e c t i v i t yo fe l e m e n t s t oc r e a t et h eb v h a l s ow ec a l lc o l l e c tt h ea d j a c e n c yi n f o r m a t i o nd u r i n gt h i sp r o c e s s 2 m o d i f y i n gt h eu pt ob o t t o ma l g o r i f l u nt ou p d a t i n gt h eb v h 3 i n t r o d u c i n gt h e “t a n d e m ”a l g o r i t h mi ns e l f c o l l i s i o nd e t e c t i o nt oe l i m i n a t et h e r e d u p l i c a t eq u e r y , 4 。m o d i f l y i n gt h ee l e m e n t sb a s e ds p a t i a lh a s h i n gs oa st ou s e v e r t e x t r i a n g l e a l g o r i t h mo t h e rt h a l l “v e r t e x t e t r a h e d r o n ”w h i c hi sf o rv o l u m em o d e l t h er e m a i n d e ro ft h et h e s i si so r g a n i z e da sf o l l o w s c h a p t e rl i n t r o d u c e st h e b a c k g r o u n d sa n dt h es t a t eo ft h ea r to fc o l l i s i o nd e t e c t i o na l g o r i t h m sf o rd e f o r m a b l e o b j e c t s a l s oi ti n t r o d u c e st h em a i nc o n t e n ti nt h et h e s i s c h a p t e r2i n t r o d u c e st 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 sf o re l e m e n t sw h i c hw i l lb eu s e df o rd e f o r m a b l eo b j e c t s a n ds o m em o d i f i e da l g o r i t h m sf o rs o m es p e c i a la p p l i c a t i o n c h a p t e r3a n dc h a p t e r4 i n t r o d u c et h eb o u n d i n gv o l u m eh i e r a r c h i e sa n ds p a t i a ls u b d i v i s i o n w ed i s c u s sa l l k i n d so fp r o b l e m si nt h ea l g o r i t h m s ，a n da l s og i v et h ep s e u d oc o d ef o rs o m e k e y p r o b l e m sa n di n d i g e s t i b l ep r o b l e m s ，c h a p t e r5i n t r o d u c e st h ed e s i g n ，i m p l e m e n ta n d a p i ：- l i c a t i o no ft h e c d k i tw h i c hc o n t a i n s0 1 1 1 7a l li m p l e m e n tf o rt 1 1 ea l g o r i t h m s c h a p t e r6c o n c l u d e st h i st i l e s i sa n dd i s c u s s e ss o m ef u t u r ew o r k 浙江太学硕士学位论文 k e y w o r d s ：p h y s i c a l l yb a s e ds i m u l a t i o n ，c 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 nf o r d e f o r m a b l eo b j e c t s ，c l o t hs i m u l a t i o n ，v i r t u a ls u r g e r y , s e l fc o l l i s i o n ，c o l l i s i o n q u e r y , b o u n d i n gv o l u m eh i e r a r c h i e s ，s p a t i a ls u b d i v i s i o n 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得逝姿盘生或其他教育机 构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献 均已在论文中作了明确的说明并表示谢意。 学位论文作者签名：罗谦 签字日期：y 弼年y 月心f ；： 学位论文版权使用授权书 本学位论文作者完全了解堑：至三盘堂有关保留、使用学位论文的规定， 有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和 借阅。本人授权迸姿盘堂可以将学位论文的全部或部分内容编入有关数据库 进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名 甲罅 签字日期：7 影年月j j ，日 学位论文作者毕业后去向 工作单位： 通讯地址： 引隧备。骗弛 签字r 期：y 弼年) 月，上目 电话 邮编 浙江大学硕士学位论文 1 1 引言 第一章绪论 与真实世界中的物体相比，在虚拟世界中，虚拟物体的位置只由计算机中的 数据决定，而并不占有真实的空间，因此，没什么可以阻止它们相互穿透。为了 避免这种不真实的穿透现象出现，在模拟运动过程时，必须进行碰撞检测，并在 发现碰撞的情况下做相应的处理。 有关碰撞检测问题的研究源于1 9 7 0 年代，迄今为止，已经有大量的碰撞检测 成果被开发出来，它们被广泛应用于计算几何，机器人学等领域，在这些领域中 以计算机图形学更为突出。计算机图形学中的大量应用，包括计算机辅助设计、 虚拟现实、物理模拟等等都需要有快速、健壮的碰撞检测。 随着计算机动画、交互式虚拟现实等技术的快速发展，以及目前三维几何模 型越来越复杂，虚拟场景规模越来越太，碰撞检测再次面临真实性、实时性的巨 大挑战，这些使对碰撞检测的研究一直处于计算机图形学中的热点位置。 近些年来基于物理的模拟和动画逐渐兴起，其中对一些高端技术的研究，包 括真实感流体模拟、毛发模拟、树木模拟、碎裂模拟等更是成为计算机图形学中 的研究重点、热点和难点。在这些高端的研究中，还包括对可变形体碰撞检测技 术的研究，本文的主要目的就是针对可变形体的特点，阐述其碰撞检测中的众多 问题，并对该领域中的一些经典算法进行了仔细的研究和分析，再结合不同应用， 提供自己的一套解决方案； 1 2 论文研究背景 1 2 1 基于物理的动画 基于物理模型的动画技术是八十年代后期发展起来的一种新的计算机动画 技术。经过多年的发展，它已在图形学中成为一种具有潜在优势的三维造型和运 动模拟技术。尽管该技术比传统动画技术的计算复杂度要高得多，但它能逼真地 模拟各种自然物理现象，这是基于几何的传统动画生成技术所无法比拟的。著名 动画软件m a y a 、s o f t i m a g e 等在基于动力学的动画功能方面已经相当成熟，它们 能处理诸如重力、风、碰撞检测等在内的复杂动力学模型。 传统动画技术要求预先描述物体在某时刻的瞬时几何位置、方向和形状， 其运动则往往通过关键帧技术来完成。因而，欲模拟一个逼真的自然运动需要动 画设计者细致、耐心的调整，要求动画设计者依赖其对真实物理世界的直观感觉 来设计物体在场景中的运动。但由于真实世界中物体的运动往往非常复杂，因而， 浙江大学硕士学位论文 采用传统的动画设计技术一般来说难以生成令人满意的运动。今天，许多动画师 不得不采用一些特殊的软件来模拟特定的物体运动。基于物理模型的动画技术则 考虑了物体在真实世界中的属性，如它具有质薰、转动惯矩、弹性、摩擦力等， 并采用动力学原理来自动产生物体的运动。当场景中的物体受到外力作用时，牛 顿力学中的标准动力学方程可用来自动生成物体在各个时间点的位置、方向及其 形状。此时，计算机动画设计者不必关心物体运动过程的细节，只需确定物体运 动所需的一些物理属性及一些约束关系，如质量、外力等。 总体上来说，基于物理的模拟大致可分为三类，即剐体运动模拟、柔体变 形运动以及流体运动模拟。在剐体运动模拟方面，其研究重点集中在采用牛顿动 力学的各种方程来模拟刚体系统的运动。物体的变形一直是计算机图形学的研究 热点，由于传统的表面变形均是基于几何的，其形变状态完全人为给定，因而变 形过程缺乏真实性。从上世纪8 0 年代后期开始，学者们提出了基于物理模型的 柔性物体的变形问题，不同的物理模型已经可以真实的模拟出多种柔性物体的运 动，例如布料。在基于物理的流体模拟方面，其中涉及的现象包括烟雾，流体运 动界面、波浪、气泡、火焰、以及爆炸等，这些现象的模拟也一赢是计算机图形 学中的热门话题。 1 2 2 碰撞处理 在基于物理的动画中，有非常重要的一环，即是碰撞处理。与真实世界中的 物体相比，在虚拟世界中，虚拟物体的位置只由计算机中的数据决定，而并不占 有真实的空间，因此，没什么可以阻止它们相互穿透。为了避免这种不真实的穿 透现象出现，在运动过程模拟时，必须进行碰撞检测，并对碰撞后的物体进行碰 撞响应处理，这个过程被称为碰撞处理。 碰撞检测主要是检测物体之间是否发生相交，整个过程考虑自q 是几何问题。 碰撞检测是整个模拟过程中计算负担最重的部分，常常是瓶颈所在，因此有效的 碰撞检测算法对模拟的性能有极其重要的意义。 碰撞检测通常可以划分为几个阶段，见图1 1 。 当场景中有n 个物体，用蛮力方法做碰撞检钡i 的时间复杂度将达到0 ( 2 ) ， 这会严重影响算法效率，初步检测阶段主要是应用一些优化策略或方法来快速排 除明显不发生碰撞的物体，找出潜在的相交区域或潜在的相交物体对。常用的方 法有“掠扫和裁剪”方法f 2 1 等。 浙江大学硕士学位论文 详细检测阶段根据已经确定的潜在相交区域或潜在的相交物体对做进一步 的相交测试。通常这个阶段能够给出更多的碰撞信息，例如接触点、穿透深度、 相邻信息等等，这些信息对后来的碰撞响应提供支持。其中有大量的研究集中在 快速的基元相交测试【4 1 ，快速的穿透深度计算5 等等。 碰撞检测的下一个阶段是碰撞响应，其作用是使物体不发生穿透，同时保证 物体之间不发生相互滑动。碰撞响应主要有两大类，即基于几何的方法和基于物 理的方法。其中基于几何的方法主要是保持物体在碰撞前的几何位置约束；基于 物理的方法通常又有三种方法：附加反推力、计算惩罚力鹕l l g l 和基于约束的方 法b o l l ”。 包含碰撞处理的一个简单物理模拟框架如图1 2 ，其中模拟模块包括碰撞求 解、约束求解、运动求解、时间控制等功能，它将更新整个系统的状态，包括位 置、速度、受力情况等。 图1 _ 2 简单物理模拟框架 1 2 3 可变形体碰撞检测 碰撞检测是计算机图形学中的一个研究重点，目前已经有大量的论文和研究 成果v 2 1 ，但大多数都是将注意力放在刚性物体上。可变形体碰撞检测是基于物 理的交互式模拟和动画的一个重要组成部分，近些年来，它已经成为计算机图形 学中一个研究热点，并且有大量的论文致力于解决这方面的问题，此外，有大量 的应用需要应用到这方面的技术，例如虚拟手术和布料模拟等等。 浙扛大学硕士学位论文 详细检测阶段根据已经确定的潜在相交区域或潜在的相交物体对做进一步 的相交测试。通常这个阶段能够给出更多的碰撞信息，例如接触点、穿透深度、 相邻信息等等，这些信息对后来的碰撞响应提供支持。其中有大量的研究集中在 快速的基元相交测试【3 】 4 】，快速的穿透深度计算【5j 【6 1 等等。 碰撞检测的下一个阶段是碰撞响应，其作用是使物体不发生穿透，同时保证 物体之间不发生相互滑动。碰撞响应主要有两大类，即基于几何的方法和基于物 理的方法。其中基于几何的方法主要是保持物体在碰撞前的几何位置约束；基于 物理的方法通常又有三种方法：附加反推力o ”、计算惩罚力1 9 1 和基于约束的方 法。 包含碰撞处理的一个简单物理模拟框架如图1 2 ，其中模拟模块包括碰撞求 解、约束求解、运动求解、时间控制等功能，它将更新整个系统的状态包括位 置、速度、受力情况等。 图1 2 简单物理模拟框架 1 2 3 可变形体碰撞检测 碰撞检测是计算机图形学中的一个研究重点，目前已经有大量的论文和研究 成果”“，但太多数都是将注意力放在刚牲物体上。可变形体碰撞检测是基于物 理的交互式模拟和动画的一个重要组成部分。近些年来，它已经成为计算机图形 学中一个研究热点，并且有大量的论文致力于解决这方面的问题，此外，有大量 的应用需要应用到这方面的技术，例如虚拟手术和布料模拟等等。 的应用需要应用到这方面的技术，例如虚拟手术和布料模拟等等。 浙江大学珂i 士学位论文 1 2 3 1 难点与挑战 与刚体碰撞检测相比较，可变形体的碰撞检测更加复杂，需要有更多的考虑 和处理，其中主要包括： 碰撞和自碰撞：可变形体的碰撞检测不光需要考虑物体间的碰撞，还需要考 虑自碰撞，图1 3 ，因此需要设计更为有效的检测算法。 预处理：在刚体的碰撞检测中，通过使用些空间数据结构可以使算法的效 率得到很大的提高，这些数据结构的建立都在预处理阶段完成。而可变形体的碰 撞检测中，这些数据需要不停的更新，从而使性能大幅下降，因此需要对数据的 选择非常小心。 图1 3 可变形体的自碰撞 碰撞信息：正确的碰撞处理需要获取大量的碰撞信息，包括接触点、穿透深 度等等，针对可变形体的特性，需要有合适的方法来快速获取这些信息。 效率：在虚拟手术、游戏等应用中，交互性是这些应用的关键特征，所以对 碰撞检测算法的效率要求非常严格，特别是可变形体。 1 2 3 2 研究现状 可变形体碰撞检测主要有如下几种主要算法，即层次包围体，空间剖分，随 机方法，距离场，图象空间方法。 层次包围体( b v h ) 1 4 1 已经被证明是一种极为有效的的碰撞检澳算法，之前主 要应用于刚体碰撞检测中，针对可变形体的特点，需要对着重考虑如下些问题： 包围体选择：对包围体的选择主要考虑它们的更新速度和对物体的拟和程 度，这是一对矛盾的概念，通常需要有个折中。 树的选择：层次包围体是典型的树型结构。对树的选择将影响算法效率。通 常的选择有二叉树、四叉树、八叉树。树的选择也需要在访问深度、每层访问消 浙江大学硕士学位论文 耗间做个折中。 层次结构的建立和更新：层次结构的生成可以在预处理阶段完成，算法的选 择需要保证树的平衡性。而对可变形物体来说，在模拟过程中，层次结构的更新 比重新建立要有效的多。 碰撞查询：其中主要是树的遍历问题，这和树的选择有紧密关系。 此外，层次包围体还被用于加速连续碰撞检测( c c d ) 空间剖分方法是开发空间局部性的一种方法，它将整个虚拟空间划分为一个 个体索，物体被放置在体素内，最终的碰撞检测只发生在处于同一个体素的基元 之间。 根据不同的空间划分方法，可以分为：物体相关的非均匀空间划分，例如 k - d 树、八叉树、b s p 树等；物体无关的统一网格划分”】i “1 【l ”。 图i 4 层次包围体结构 空间哈希f l a j 也是空间剖分中的一种常用方法，它根据组成物体的基元的空 间位置，将它们哈希到哈希表格中，最终的碰撞检测将发生在位于哈希表格中同 一个哈希桶内的基元间。 图1 5 统一网格划分和八叉树划分 在实际的模拟中，绝对精确的模拟是不必须的，因为在完全精确和似是而非 浙江丈学硕士学位论文 的模拟效果面前，我们的眼睛无法辨别其中的差异，而且，对模拟的实时性要求 要远高于精确性，随机方法的碰撞检测就是这些思想的体现，它进行的就是近似 的碰撞检测。 随机方法主要有两类：a d l 3 树f ”】、随机最近特征跟踪1 a 图1 6 随机方法的两种类型 距离场是在封闭曲面外围定义一个距离，这个距离是所有点能够接近该益面 的最小距离，并且这个距离是带符号的，用以区别内部和外部。用距离场表达 个封闭曲面可以使曲面摆脱拓扑关系的约束，并且为碰撞检测和碰撞响应过程中 的距离、法向量等的计算提供方便。 距离场方法包括以下几个主要方面：距离场的生成口”，这个过程可以在预 处理阶段完成：利用距离场检测碰撞陋j ，距离场可以消除边一边相交测试，而 是用简单的点一面相交测试作为基元相交测试；距离场的更新，这个过程通常是 瓶颈所在。综上，距离场方法非常适合做刚性物体和可变形物体之间的碰撞检测。 图1 7 距离场 近些年来，基于图象空间的方法开始被越来越多的用在了碰撞检测上，这 些方法通常处理物体的投影以加速碰撞查询。图象空间方法不需要预处理，而且 借助图形硬件实现，速度快，非常适合动态可变形物体的碰撞检测。 最新的成果中，利用图象空间方法已经可以快速解决任意形状，可变形物体 的碰撞检测 2 1 1 ，并且对此方法的改进版已经可以检测可变形物体的自碰撞1 2 ”。 虽然图象空间方法速度快，但也有明显的缺陷，即无法为后续的碰撞响应提供足 够的碰撞信息，例如接触点、穿透深度等。 浙江大学硕士学位论文 可变形物体的自碰撞一直是难点问题，目前主流的解决方法是基于曲率的启 发式方法，同时还有考虑邻接关系。具体将在第三章介绍。 1 2 3 3 主要应用 图1 8 图象空间方法 可变形物体碰撞检测有许多重要应用，其中两个最主要的是：布料模拟、 虚拟手术，见图l 9 。 布料模拟”叫包括简单的布料动画，布料覆盖动画，服装试穿模拟和穿衣 服的虚拟人动画等等，近些年来大量的论文都集中在这个领域，其中还有不少研 究集中在物理建模、碰撞响应和数值求解方面。 图i 9 布料模拟和虚拟手术 虚拟手术是可变形体碰撞检测的另一个重要应用，而且在医学上有非常重要 的意义，这其中涉及到器官与手术器械之间的碰撞检测 2 7 1 、器官与器官之间的 碰撞2 8 1 以及器官的自碰撞2 0 1 等问题。 1 3 论文的提出、研究内容和创新 1 3 1 论文提出 尽管有关可变形体碰撞检测的研究成果已经比较丰富，但随着计算机图形学 的不断发展，以及包括虚拟现实在内的新兴领域的涌现，实际应用对碰撞检测技 浙江大学硕士学位论文 术的要求越来越高。论文的提出基于以下几个问题。 1 针对可变形体特点以及具体应用，不同检测方法需要考虑的问题很多， 如何在各个关键问题的多种方案中进行选择，为不同方法总结出一整套合理的解 决方案。 2 对复杂场景以及精细模型的处理能力。随着图形硬件技术的发展，系统 已经可以实时显示大规模场景，这些场景常常有成百上千万的面片。在这种场景 中进行碰撞检测，对碰撞检测算法就提出了更高的要求。随着场景中多边形面片 数的增多，多数算法的效率往往会迅速下降。 3 自碰撞问题。含个面片的可变形体自碰撞检测的复杂度达到o ( n2 ) ， 如何开发合理的算法，尽可能降低复杂度，提高整个碰撞检测算法的效率。 1 3 。2 论文研究内容 本文针对可变形体碰撞检测的特点，对层次包围体、空间剖分两种经典算法 进行了仔细的研究，对其中的各种问题进行了分析，并结合各种可能会碰到的问 题进行考虑，提出了适合各自算法的一整套方案。 1 基元碰撞检测 对“点三角形”碰撞和“边一边”碰撞进行了分析，并对特殊场景下的简 化进行了讨论。 2 层次包围体方法。 对包围体的选择、层次包围体树型结构的选择、层次包围体的建立、层次包 围体的更新等方法进行了研究，并对各种不同方案的性能差别进行了分析。其中 还对自碰撞检测算法进行了分析和研究，包括基于曲率的启发式算法和邻接判断 算法。 最后，对碰撞查询算法进行了讨论，包括可变形体的自碰撞查询算法以及可 变形体与其他模型间的碰撞查询算法。 3 空间剖分方法。 对统一网格划分方法，包括体素大小的选择、基元( 点、线、面) 的体奈化进 行了研究。特别是自碰撞检测处理，对基于曲率的启发式算法和邻接判断簿法在 空间剖分方法中可能会遇到的问题进行了分析，并提出解决方案。最后，对空间 哈希方法进行了讨论，并对其性能、关键参数进行了分析。 本文的绝大多数研究内容均在可变形体碰撞检测库c d k i t 中得到了实现。此 外，c d k i t 库还为以后可能的补充和升级定义了接口。 浙江大学硕士学位论文 1 3 3 论文创新 本文对两种经典算法中的诸多方面都进行了描述和讨论，并对其中一些关键 问题进行了自己的修改和创新。 l 。基于几何基元连通性的层次包围体自底向上构建方法。充分考虑到可变 形体碰撞检测的特点，为了减少自碰撞检测的消耗，通过这种方法自底向上生成 层次结构，可在节点归并过程中记录基元的邻接关系，从而为自碰撞检测提供了 必要的信息。具体描述见3 3 2 节。 2 对自顶向下的层次包围体更新方法进行改进。综合自顶向下、自底向上、 混合式更新的优缺点，采用一种新的更新方式，对层次包围体的树结构进行更新 的过程中计算树的深度，首先只更新到某一个深度，当发现更深的节点需要被遍 历时，再继续更新下去。具体描述见3 4 节。 3 在自碰撞检测中采用“兄弟”方式的碰撞查询。通常的碰撞查询方式对 层次包围体的树结构进行遍历会产生大量的冗余查询，采用“兄弟”方式的碰撞 查询可以很好的解决这一问题。具体描述见3 5 2 节。 4 两种不同的空间哈希方法。空间哈希方法可以改善空间剖分方法中内存 要求高、碰撞查询耗时大的问题，文中讨论了两种不同的空间啥希方法，即哈希 的对象不同，在以基元为对象的方法中，文中的讨论突破了以往“点一四面体” 的碰撞查询。具体描述见4 6 2 节。 1 4 论文的组织结构 本文的研究集中在层次包围体、空间剖分两种方法上，对其中的主要问题进 行了分析、研究，并在c d k i t 库中得到了实现，最终应用到了布料动画中。 全文的组织如下：第一章是绪论，讨论了可变形体碰撞检测中的主要问题、 研究现状以及主要应用；第二章介绍可变形体碰撞检测中的基元相交测试，并介 绍了在不同应用的简化和改进；第三章和第四章分别介绍层次包围体方法和空间 剖分方法，对其中的关键问题进行了分析，列出了关键问题和较难理解问题的算 法伪码，并对自碰撞问题进行了分析：第五章介绍c d k i t 库的设计与实现，并给 出了我们的实验结果；第六章对本文的研究进行了总结，指出其解决的主要问题 以及缺陷和不足，并对未来的进一步研究提出展望。 塑坚查兰堡圭堂些堡塞 r ” ? 一一一 5 研究背景i l 研究内容、目标i 【。j l ，。一一。j l 第三章层次包围体 点一三角形ii 边一边i 厂 l 特殊情况l 第四章空间剖分 图1 i 0 论文组织结构 宪、鼓据结构设计l 1、，。、，一 l o 一 困习骂翟熙冒翟翼 翮一 匦囹 互卫 浙江大学钡士学位论文 2 1 引言 第二章基元碰撞检测 1 2 2 节介绍了碰撞检测通常的两个阶段，其中详细检测阶段是真正计算相 交，以及提供各种碰撞信息的阶段。这个阶段要对已经确定的潜在相交区域或潜 在相交物体对做进一步碰撞检测，其中的重要环节就是基元碰撞检测。根据可变 形体的不同模型，基元碰撞检测有许多不同种类，包括基本几何实体间的相交检 测、三角面片和基本几何实体间的相交测试、三角面片之间的相交测试等等。 本文中讨论的基元是三角面片，因此我们只考虑三角面片之间的相交测试， 这其中包括了多种不同类型的相交测试，即“点一三角形”、“边一三角形”、“三 角形一三角形”、“边一边”。对可变形物体来说，三角形形状不停在发生变化， 因此需要有特殊的方式检测上述碰撞。 假设t 。时刻两个三角形不发生碰撞，而且我们知道三角形上各顶点的位蔑与 速度，那么，在k ，f 。+ 岔f 时间间隔内的碰撞检测任务就是检测在该时间间隔内 是否存在碰撞现象。当三角形和三角形发生碰撞，只有两种碰撞形式会发生： “点一三角形”碰撞，一个三角形的顶点穿过另个三角形； “边一边”碰撞，一个三角形的边与另一个三角形的边相交。 图2 1“点一三角形”碰撞、“边一边”碰撞 2 2 “点一三角形”碰撞牡9 假设e ( t ) 是移动的顶点，一( f ) 、b ( f ) 、c ( t ) 为移动三角形的三个顶点， 匕、l 、是它们在时间间隔k ，t 。+ a t 】内的常量速度，于是我们有 a ( t ) = a ( t 。) + 0 一“) ，b ( f ) = 口( “) + p t o ) ，c ( t ) = c ( t o ) + ( f t o ) 。 如果在k ，“+ 出】内存在碰撞，尸( f ) 应该落在三角形a b c ( t ) 内，于是看： 3 t k ，如+ 出l 使得 ，+ 。，、 3 u ，v 【o ，l j “+ v 重1 ，a p ( t ) = u a b ( t ) + v a c ( t ) 浙江大学硕士学位论文 但这个方程是个非线性系统，为了解决这个闻题，我们转变思路，有关系： a p ( t ) o ( 磅= 0 ( 式2 2 ) 其中n ( t ) = a b ( t ) a c ( t ) ，为三角形a b c ( t ) 的法向量。这是一个三次方程， 可以解得t ，当t 不落在区间【f 0 ，f 。+ 出】内，则不发生碰撞；否则，为了证明p 不仅与a b c ( t ) 共面，而且落在三角形a b c ( t ) 内，将，代入式2 1 求解“，v ，此时 式2 1 为线形系统。 ( r ，”，v ) 为该系统的解，如果存在多个解，则，最小的解对应第一个碰撞点。 2 3 “边一边”碰擅牡钟 为了检测不同三角形上的边在时间间隔 f o ，f 。+ a t j 内是否相交，我们可以假 设a b ( t ) 为第一个三角形上的一条边，c d ( t ) 为另一个三角形上的一条边，如果 存在相交，则满足如下关系： | f 【，o ，f o + 缸| 使得 ，+ 。 3 u ，v t o ，i 】 u a b ( t ) = v c d ( t ) 同样这也是一个非线性系统，为了解决这个问题，我们转变思路，当碰撞发 生时，四个点a 、b 、c 、d 将共面，于是有关系： l 4 b ( f ) c d ( r ) j a c ( t ) = 0 ( 式2 4 ) 求解这个三次方程，可得t ，当f 不落在区间k ，“+ a t 】内，则不发生碰撞； 否则，将所入式2 3 求解“，v ，( r ，“，v ) 为该系统的解。 2 4 可变形三角形间碰撞检测 目前还没有算法可以直接对两个可变形三角形进行相交测试，因此将三角形 间的相交测试分解为上述两种基本情况来解决问题但这两种基元碰撞检测中涉 及到三次方程的求解，而且为了精确的检测两个三角形的碰撞，需要进行6 次“点 一三角形”碰撞检测，9 次“边一边”碰撞检测，见算法a l g o r i t h m2 1 。 浙江大学硕士学位论文 a l g o r i t h m2 1 v o i de l e m e n t c o l l i s i o n d e t e c t i a n ( p t r i a n g t e a ，p t r i a n g t e bj ，6 次“点一三角形”碰撞检测 f o re a c hp v e r t e xo fp t r i a n g l e a v e r t e x t r i a n g l e c o l l i s i o n ( p v e r t e x , 口r i a n g t e b f o re a c hp v e r t e xo f p t r i a n g l e b v e r t e x t r i a n g l e c o l l i s i o n ( p v e r t e x ，p t i i a n g l e aj 9 次“边一边”碰撞检测 f o re a c hp e d g e ao f p t r i a n g l e , , t f o re a c hp e d g e bo fp t r i a n g l e b e d g e e d g e c o l l i s i o n ( p e d g e a p e d g e b 2 5 特殊情况 在模拟过程中，有些特殊情况可以简化碰撞检测。在可变形体与刚性物体， 特别是静止物体的碰撞检测中，由于刚体不发生形状的变化，所以，我们可以修 改“点一三角形”碰撞检测，并且对特殊情况进行修改，从而消除“边一边”碰 撞检测。 对“点一三角形”碰撞检测，我们可以通过计算点在时间间隔【f ，f + a t 】内的 轨迹是否与三角形相交来判断是否发生碰撞】。 尸( f ) 、。- k 卜、地) t t | 一 图2 2 顶点轨迹与三角形相交测试 首先判断线段是否与三角形所在的平面相交，如果相交则计算交点并判断交 点是否落在三角形内，如落在三角形内，则在该时间间隔内并发生碰撞。 如果三角面片不够精细，那么仅仅考虑“点一三角形”碰撞检测，有些碰撞 无法检测到，见图2 3 ，这也是引入“边边”碰撞检测的原因。 图2 ，3 “点一三角形”碰撞检测缺陷 为了解决这一问题，可以在刚体表面加上一层薄的包围体1 ，见图2 4 ，当 浙江大学硕士学位论文 检测到点与包围体表面碰撞即认为发生碰撞，这样就避免了上述问题，同时消除 了“边一边”碰撞检测。 图2 4 消除“边一边”碰撞检测 因此我们可以为刚体表面预生成包围体，并对其中较尖锐的部分生成更厚的 包围体，具体算法【，1 1 可以根据判断两相邻三角形的夹角大小，如图2 5 - a 所示， 如果五和正的夹角a 小于某个阙值，则认为这是尖锐部分。或者如图2 5 - bn s , ， 如果顶点尸周围的所有三角形的角度之和口= q 小于某个阈值，则认为这是尖 锐部分。 图2 5 尖锐部分判断 。此外，为了在表面三角面片比较稀疏的情况下消除“边一边”碰撞检测，还 可以采用自适应的例子系统，实时插入“虚拟点”【”】，但需要增加额外的计算 消耗，文中不做解释。 2 6 小结 本章介绍了可变形体碰撞检测中需要用到的基元碰撞检测，根据不同的应用 可以采用不同的方法，这些基元碰撞检测方法对应整个碰撞处理过程中的详细检 测阶段，对不同算法来说，这部分是通用的。对可变形三角形来说，碰撞检测可 分解为6 次“点一三角形”碰撞检测和9 次“边一边”碰撞检测；而在可变形体 与刚性物体的碰撞检测中，我们可以修改“点一三角形”碰撞检测，并对刚体表 面进行向外膨胀，从而消除“边一边”碰撞检测，以达到提高算法效率的目的。 4 浙江大学硕士学位论文 3 1 基本溉念 第三章层次包围体 层次包围体是一种典型的空闻数据结构，它的设计理念是避免对所有几何基 元进行穷举碰撞测试，它的用途非常广泛，除了碰撞检测，它还能用在光线跟踪、 最近邻域查询、遮挡剔除等可视性算法上。 和八叉树、二叉空间剖分( b s p ) 树等空间数据结构不同，它们都是对整个虚 拟空间进行划分，而层次包围体是对物体或几何基元进行划分，直到达到某个叶 子节点的标准为止。 定义： 假设为o = 0 。，d ：，吒 为物体或几何基元的集合，那么o 的层次包围体结 构b v h ( o ) 可以定义为： 1 如果蚓= g ，那么b v h ( o ) 为一个叶子节点，里面存储集合0 以及0 的 包围体。 2 如果1 0 l p ，那么b v h ( o ) 可定义为一个根节点，它包含n 个子节点 h ( v ) = v ，v ，v 。) ，每个子节点v 。又是一个层次包围体结构b v h ( 9 ) ，并且包 含b v h ( o ，) 的包围体，其中0 ，c 0 并且y 0 。= 0 。 定义中有两个关键参数e 和珂，其中e 为划分到叶子节点的阚值，一般为1 ， 也可取其他值，通常为2 ”，视具体应用而异。月为层次结构中每个