（计算机软件与理论专业论文）智能avatar在ive中行走运动控制及其路径规划问题的研究.pdf

智能a v a t a r 在i r e 中行走运动控制 及其路径规划问鼷珏的研究 摘黉 智熊虚拟环境的研究内容是在虚拟环境中加入有生命的对象( 廉 拟人或动物) ，通过对豫懿活动的模拟来进一步增强虚拟环境的真察 感察溺没感，以更遥奏羹蠡模拟真实髓界。 本文的研究工作主簧围绕三维廉拟场景中智能a v a t a r 行走动溺 及其路径规划生成展开。对三维虚拟环境中的碰撞检测、人体行走动 画的自动生成及三维环境中的路径规划技术进行了深入研究，提出了 相应的模型，并对传统方案作了改进。 在磁撞检测算法上，本文遥过碰撞梭溅概述，对磁撞检测技术进 行分类，褥其分为空闻分害g 法和层次包豳盒法两大类，并对其进行勰 释；接着分析了在其体情况下如何适獭地选取碰撞检测算法来解决阀 题，并提供了一些原则；其次为了实现碰撞检测技术，通过b s p 树 方式建立纛拟场景并对其进行管理；最爝在b s p 树进行场景管理的 环境孛对a v a t a r 构造了三个辅助传感器包括对象传感器、嚣标位耋传 感器、簿褥物铸感器，它们将作为a v a t a r 行走行为的传感器，以支掩 a v a t a r 在虚拟环境中的蜜时行走以避免碰撞。 在人体行走动谶的囱动生成中，我们在人体的基本骨架的基础上 研究了人体的行走模型，并且提出使用逆向运动学算法来保证人体动 画教实时饿。基于逆向运动学算法，本文设计实现了虚拟人行走动蕊 的自动生成。 在碰拟人的路径规划中，要快速、离效、逼真地实现在三维虚拟 场景中的擞时路径规划，必须解决路径的搜索速度和优化实现问题， 本文采用丁胁寻径策略并对其进行改进，通过对o p e n 表的维护提高? 搜索速度，疯子这样规划爨来的路径怒直线连接霭成的，懿果直接澄 赢线行走，在携点囊釜会造成凸遗，导致动作缀生硬，戮此我餐提出了 对路径的优化平滑，传统的方法是使用样条曲线，但怒，样条曲线会 偏离原始路径，并且导数和积分的求取比较麻烦，我们提出了一种撇 物拟合的方法进行优化，以克服样条曲线的缺点，并使平滑后的路径 符合易于积分、微分且逼近原始路径的特点。 【关键词】：虚拟人，碰撞检测，人体行走动画，反向运动学，路径 规划 t h er e s e a r c ho n i n t e l l i g e n ta v a t a r sm o v e m e n tc o n t r o la n dt h e p a t hp l a n n i n gi ni n t e l l i g e n tv i r t u a le n v i r o m e n t0 v e ) a 转s 薹乏a e 零 t h ec o n t e n to fr e s e a r c ho l li n t e l l i g e n tv i r t u a le n v i r o n m e n t f i v e ) i s t o i n t e g r a t e v i r t u a l l i f e ( v i r t u a lh u m a no ra n i m a l s ) i n t ov i r t u a l e n v i r o n m e n t ( v e ) ，a n dt os i m u l a t et h e i ra c t i v i t i e st oi m p r o v et h er e a l i t y a n di n t e r a c t i v i t yo f t h ev e 。 t h i st h e s i sm a i n l yf o c u s e so nw a l k i n ga n i m a t i o na n d p a t hp l a n n i n g o fi n t e l l i g e n ti n3 dv i r t u a ls c e n a r i o , i n c l u d i n g3 dv i r t u a le n v i r o n m e n to f c o l l i s i o nd e t e c t i o n ，t h ea u t o m a t i cg e n e r a t i o no f3 da n i m a t i o no fh u m a n w a l k i n ga n dp a t hp l a n n i n gt e c h n o l o g yf o re n v i r o n m e n t - d e p t hs t u d yo f t h e c o r r e s p o n d i n gm o d e l ，t h et r a d i t i o n a lp r o g r a mh a sb e e ni m p r o v e d o nc 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 ，t h ep a p e rd e s c r i p t i o n st h e s u m m a r i z a t i o no ft h ec 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 nt e c h n i q u e s 剁c l a s s i f i e di n t ot w oc a t e g o r i e s ，i n c l u d i n gs u r r o u n d i n gb o xa n ds p a c e p a r t i t i o n ，w h i c hw ei n t e r p r e ti nt h i sp a p e r ；t h e nw ea n a l y z eh o wt o s e l e c tt h ea r i t h m e t i co fc o l l i s i o nd e t e c t i o nf o r r e s o l v i n gt h es p e c i f i c p r o b l e ma n dp r o v i d es o m er u l e s + i no r d e rt oa c h i e v et h et e c h n o l o g yo f c o l l i s i o nd e t e c t i o n ，w es e tu pt h ev i r t u a ls c e n a r i oa n dm a n a g ei tw i t hb s p t r e e 。f i n a l l yt h r e ea u x i l i a r ya v a t a rs e n s o r sa r ec o n s t r u c t e di nt h ev i r t u a l e n v i r o n m e n ts e tu pa b o v e ，i n c l u d i n go b j e c ts e n s o r , t h et a r g e tp o s i t i o n i l l s e n s o ra n db a r r i e rs e n s o rb a r r i e r , w h i c hw i l ls e r v ea 8t h ea v a t a rs e n s o rt o s u p p o r ta v a t a rw a l ki nv i r t u a lr e a l t i m eo p e r a t i n ge n v i r o n m e n tt oa v o i d c o l l i s i o n o na n i m a t i o ni nt h ea u t o m a t i cg e n e r a t i o no fh u m a nw a l k i n g ，w e s t u d yw a l k i n gm o d e lo fh u m a nb o d yb a s e d0 1 1t h e i rb a s i cs k e l e t o n ，a n d p r o p o s e dt h eu s eo fi n v e r s ek i n e m a t i c s ( i k ) t oe n s h r et h eh u m a nb o 毋 a n i m a t i o n sr e a l t i m e b a s e do ni n v e r s ek i n e m a t i c s ( i k ) a l g o r i t h m ，w e i m p l e m e n tt h eg e n e r a t i n gw a l k i n ga n i m a t i o no f a v a t a ra u t o m a t i c a l l y 。 o nt h ea v a t a rp a t hp l a n n i n g ，i ti sn e c e s s a r yt oe n h a n c et h es p e e do f t h es e a r c h i n gp a t hp r o c e s sa n dt h eo p t i m i z a t i o np r o b l e mf o rr e a l i z i n gt h e r e a l - t i m ep a t hp l a n n i n gf a s t ，e f f i c i e n t l ya n dr e a l i s t i c a l l yi nt h e3 dv i r t u a l s c e n a r i o 。t h i sa r t i c l eu s e dt h ea 臻s t r a t e g yt os e e kt h ep a t ha n di m p r o v ei t t oe n h a n c et h es p e e do fs e a r c h i n gp a t ht h r o u g ht h es a f e g u a r d e do p e n t a b l e b e c a u s et h ep a t hp l a n n e db yt h i sw a yi sl i n k e dw i t hs t r a i g h tl i n e ，i f t h ea v a t a rw a l k sd i r e c t l ya l o n gt h es t r a i g h tl i n e ，i tw i l lp r o h - a d ei nt h e i n f l e x i o n ，r e s u l t i n gi nt h ea c t i o nv e r yb l u n t ，t h e r e f o r e ，w ep r o p o s et o o p t i m i z et h ep a t hs m o o t h n e s s ，t h et r a d i t i o n a lm e t h o di st h eu s eo fs p l i n e c u r v e s ，b u ts p l i n ec u r v ew i l lb ef a ra w a yf r o mt h eo r i g i n a lp a t h ，i ti sm o r e d i f f i c u l tt ow o r ko u td i f f e r e n t i a lc o e f f i c i e n t w ep r o p o s eam e t h o dt o o p t i m i z et h ep a t ht oo v e r c o m et h es h o r t c o m i n g so fs p l i n ec u r v e sa n d m a k et h ep a t hs m o o t hw i t ht h ec h a r a c t e r i s t i c so f e a s y i n t e g r a l ，d i f f e r e n t i a l c o e f f i c i e n ta n da p p r o x i m a t i o no r i g i n a lp a t h k e yw o r d s ：a v a t a r , c o l l i s i o nd e t e c t i o n ，w a l k i n ga n i m a t i o no f h u m a nb o d y , i n v e r s ek i n e m a t i c s ( i k ) ，p a t h p l a n n i n g 学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得 的研究成果。论文中除了特别加以标注和致谢的地方外，不包含其他人或其他机 构已经发表或撰写过的研究成果。其他同志对本研究的启发和所做的贡献均已在 论文中作了明确的声明并表示了谢意。 研究生签名：司嚆饥 日期：知口矗以少 学位论文使用授权声明 本人完全了解浙江师范大学有关保留、使用学位论文的规定，即：学校有权 保留送交论文的复印件和电子文档，允许论文被查阅和借阅，可以采用影印、缩 印或扫描等手段保存、汇编学位论文。同意浙江师范大学可以用不同方式在不同 媒体上发表、传播论文的全部或部分内容。保密的学位论文在解密后遵守此协议。 研究生签名：阀嗜红 导师签名：、日期：扣口，卢 宁齑 心 第一章绪论 第一章绪论 本章论述了本课题的涵义；详细地讨论了选题的背景、国内外研究现状及研 究意义；介绍了论文的主要工作及论文的结构安排。 1 1 课题的来源与研究意义 本课题来源于导师的浙江省自然科学基金重大项目“智能a v a t a r 的自主行 为、情感与动画( z 6 0 3 2 6 2 ) ”中的子课题。 目前来说，智能a v a t a r 主要实现于城市道路交通规划、校园漫游、电子导航 等、军事演习、体育训练等。其中的行走路径规划是最基本的，也是最重要的， 实现和具体应用都是分别针对各自的地形特点和管理目的而设计。整个系统的数 据采集，场景构造等都是庞大的工程，本文仅就基于构建的三维虚拟场景中的 a v a t a r 行走动画生成、路径规划及行走过程中碰撞检测问题展开研究和讨论，探 索提高实时性、真实感和搜索速度。 1 2 相关理论和国内外研究现状 近年来，虚拟现实技术研究十分活跃。虚拟现实技术汇集了一系列的高新技 术，包括计算机图形学、多媒体技术、人工智能、人机接口技术、传感器技术、 高度并行的实时计算技术和人的视觉、听觉、触觉形成机理的研究等。从根本上 来说，它是一种计算机仿真技术，即利用计算机和其它的专用硬件和软件去产生 现实世界的仿真，让使用者能在沉浸在虚拟的环境中自主地与三维虚拟景象进行 交互。虚拟现实创建的是一个既酷似客观环境又超越客观时空，既沉浸其中又能 驾驭其上的和谐的人机环境，也就是由多维信息所构成的可操纵的空间，它的最 重要的目标是真实的体验和方便自然的入机交互。 1 2 1 人体运动控制动画生成研究现状 人体动画技术就是对场景中的虚拟人赋予“生命”，利用虚拟骨架的运动 控制技术生成人体运动的连续画面。因此，运动控制技术始终是人体动画发展的 浙江嬲范大学硕士学位论文 熏旋律，其发展基本上经历了以下四个阶段：运动学控制、动力学控制、基于控 涮器的运动控制、运渤捕获。 虚拟人行走运动控制是个具露挑战性的任务，它涉及到了多学科的交义， 如动物学、机器入学、运动攀、生物力学、动力学等等，而且人的行走在现安当 书是菲常普遍势为人们赝熟悉的，人餐可以缀窖易黪指爨寝缀人程走当中不遐真 的地方，但却不能从理论上说出原因。对动物的行难分析开始予1 8 7 2 年，e a d w e a r d m y b r i d g e 首先掰马终为镶子，后来镶把谴黪研究扩展到入。获藏，黠入鳇行走运 动控制的研究引起了很多学者的兴趣，有许多方法被先后提了出来。z e l t z e r l 设计了一个蟊两任务分级的( h i e r a r c h i c 8 lt a s k o r i e n t e d ) 动酾系统，在这个动 贼系统飘，人体行纛仿真的实现是基乎实际测量获得的数据；g i r a r d 和 m a c i e j e w s k 用动力学规则生成躯干逡动，用逆向逡动学生成腿部运动，产生了第 一个自然的人体行走运动：b r u d c r l i n 謦f l c a l v e r t l 把入体褥走的每一步分或几个 阶段，阶段之间的过程用简单的动力学来仿真，并鼠允许用户通谶改变此参数( 如 步速、步长等) 寒生成苓月静步态。 在8 0 年代初期就出现了人体动画的交互式设计工具及控制人体行走的模 黧，这拜雩期彩晌晓较大鸯孽系统有掰个：奖国宾褥法露驻大- 鸯e b a d l e r 等开发麓 j a c k 系统【1 1 和美国俄亥饿州大学图形学实验室g i r a r d 等研制的p o d a 系统 2 1 。 1 9 8 7 年5 月，融n a d i am a g n e n t - t h a l m a n n 和d a n i e lt h a l m r n l l 领导的研究小缀汗 发澎了个大约7 分镑的电影片段，成功地模拟了电影明星玛裁莲梦鼯的表演， 遮也代表了当时计算机人体动词技术的较磷水平。在这一时期，人体运动控制技 拳激运动学控铡为主，特尉楚逆囊遨动学技本被广泛瘟髑予人钵动螽熬生成上， 熟运动控制过稷基本上可以描述为；根据人体运动规律计算末端效应器的空间运 动辘迹，然后搜瘸遂鹈运动学技术薅乏解入钵关节惫溲，镄弱入体动蓠。途耩运动 控制方式亦称为目标驱动方式。j a c k 系统和p o d a 系统中都使用了相应的力 学模墼乘提高入体动磷的囊窳感。b r u d e r l i r t 等予1 9 8 9 年提出了个结合运动学 掖制和力学控制技术的人体彳亍走模型。他们使用一个双摆来模拟腿部，通过给定 腿部摆动的开始角度和终止角度，使用s e c a n t 求椴算法求解所需力矩，得到杼淹 动蕊l a 。h 。k o 等采用逆起动力学技术对通过运动学控豢l 技零褥到的动藏痒别逃行 调整，避行人体的平衡和舒适度控$ t 4 1 。相当多的人体动画算法将人体运动中的 2 第一章绪论 力学约束转化为优化问题进行求解，也取得了比较好的效果t 5 j 。r a i b e r t 和h o d g i n s 于1 9 9 1 年将控制器技术成功地应用于有足动物的行走动画中嘲。基于控制器的 运动控制算法的核心是控制算法的设计，所采用的控制镱略一般是比例微分控 制。该算法利用状态机控制人体的运动过程，低层的控制器根据反馈信息计算关 节力矩，驱动人体执行目标动作。基于控制器的运动控制算法能够生成物理上真 实的人体动画，而且算法的灵活性较高。但是，控制器的设计是相当困难的，很 难找到对所有动作都适用的控制参数。更为重要的是，虽然基于控制器的算法能 保证生成的人体动画在物理上的真实，但是，并不能保证生成的动画在视觉上的 真实。 除了上述主流的人体运动控制技术以外，还有一些其他的运动控制技术在 人体动画领域也获得了应用，如：机器人领域内的运动规划技术 7 - 8 、神经生理 学控制技术恤1 0 l ，这些运动控制技术也是值得注意的研究课题。 国内对人体动画的研究开展较晚。江苏理工大学计算机科学系的宋顺林等 在1 9 9 5 年率先开始了人体动画的研究【1 1 。2 1 ，他们用l i s p 语言开发了交互式的人 体造型系统，并用三角函数方程逼近人体步行的关节角度曲线，得到了较为逼真 的人体动画。浙江大学庄越挺等于1 9 9 9 年开始研究基于计算机视觉的方法从视 频中提取人体运动数据，并获得了一项国家专利f 1 3 1 。哈尔滨工业大学智能机器人 研究室在“九五”科研项目中由洪炳荣教授指导开展了对虚拟人建模和运动控制 技术的研究【1 4 j 。 1 2 2 路径规划方法综述 路径规划技术是人工智能研究领域的一个重要分支。所谓a v a t a r 的最优路 径规划，就是依据某个或某些优化准则( 如行走路线最短，行走时间最短，工作 代价最小) ，在虚拟环境中找到一条从起始点到目标点且能避开障碍物的最优路 径。其实，路径规划技术早就用在机器人研究领域，其方法可以分为：传统方法 和智能方法。 1 2 2 1 传统路径规划方法 传统路径规划方法有自由空间法、图搜索法、栅格法和人工势场法。 自由空间法 i s l 为了简化问题，通常采用“结构空间”来描述机器人及其 3 浙江师范火学硕士学位论文 周围的环境。这种方法将机器人缩小成点，将其周围的障碍物及边界按比例相应 魏扩太，镬飘嚣人熹麓够在障碍镑黧闻串移磁到任意一蠡，琵不与障礴物及边赛 发生碰撞。 图搜索法图搜索方法中的溅径图由捕捉到的存铉予机器入一维网络曲 线( 稼为路经藤) 鑫由空阕中静节点缀箴。建裒怒来的蓄骞径豳嚣戮看终怒一系歹 ；鳇 标准路径。丽路径的初始状态和目标状态同路饭图中的点相对应，这样路径规划 阋题就演变为在这些点间搜索路径的问题。通她起始点和掇标点及障碍物的顶点 程蠹酶一系别点来梅造霹视蚕。连袋这些熹，使禁患与其溺潮静菜胃筏赢穰连( 繇 使相连接的两点问不存在障碍物或边界) 。然厨机器人沿潞这些点在网中搜索最 优路径。 掇格法撩格法楚馨前研究竣广泛豹釜羲经魏楚l 方法。该方法将橇嚣久酶王 作空间为多个简单的区域，一般称为栅格。由遨些栅格构成了一个连通图，在这 个连通图上搜索一条从起始栅格到髓标栅格的路径，这条路径是用栅格的序号来 裘示懿。撵格法包括确诱的移不确切的嚣释。不确韬酶方法院确切静方法在数学 计算上要简单的多，因此也比较容易实现。 人工势场法传统的人工势场法把移动机器人在环蟪中的运动视为一种 簌糖象酶入逡受力场孛憋运动，霞栋点对移动褫嚣入产生“弓l 力”，障礴物对移 幼机器人产生“斥力”，最后通过求合力来控制移动机器人的运动。但是，由于 辫场法把所裔信息压缩为单个合力，这样就存在把有关障礴物分布的裔价值的信 虑抛弃的缺陷，篮易陷入两帮最，l 、德。 1 , 2 2 2 智能路径规划方法 近年来隧着遗传算法等智能方法的广泛应用，祝器人路径规划方法也有了长 怒的迸展，许多研究者毙霹毙放在了基于智黥嚣法的路径黧划研究上。其中，应 用较多的算法主要有模糊方法、神缀网络和遗传算法。 基于模糊逻辑的机器入路径规划模糊方法是在线规划孛通常袋髑的一 种规划方法。瘫小东等掇出一种基予模糊概念酶动态环境横鼙，参照物体的位置 和运动信息构造二维录度数函数；然后通过模糊综合评价对各个方向进行综合考 察，得到搜索结果。该方法在移动障碍物和移动嚣橱的强境巾能有效嫩实现枧器 入避碰和导髋。 4 第一章绪论 基于神经网络方法的机器人路径规划禹建丽等提出了一种基于神经网 络的机器人路径规划算法，研究了障碍物形状和位置已知情况下的机器人路径规 划算法，其能量函数的定义利用了神经网络结构，根据路径点位于障碍物内外的 不同位置选取不同的动态运动方程，规划出的路径达到了折线形的最短无碰路 径，计算简单，收敛速度快。 基于遗传算法的机器人路径规划遗传算法是目前机器人路径规划研究 中应用较多的一种方法，无论是单机器人静态工作空间，还是多机器人动态工作 空间，遗传算法及其派生算法都取得了良好的路径规划结果。 1 3 本论文工作及论文的组织安排 本论文是在导师的指导下完成的，主要工作包括： l 、基于虚拟视觉为a v a t a r 建立辅助传感器 虚拟人在虚拟环境中行走规划涉及到碰撞检测问题。本文首先研究了碰撞 检测常用方法，对碰撞检测技术进行分类，将其分为空间分割法和层次包围盒法 两大类，并对其进行解释；接着分析了在具体情况下如何适当地选取碰撞检测算 法来解决问题，并提供了一些原4 h 其次为了实现碰撞检测技术j 通过b s p 树方 式建立虚拟场景并对其进行管理；最后在b s p 树进行场景管理的环境中对a v a t a r 构造了三个辅助传感器包括对象传感器、目标位置传感器、障碍物传感器，它们 将作为a v a t a r 行走行为的传感器，以支持a v a t a r 在虚拟环境中的实时行走以避 免碰撞。 2 、按照已经建好的a v a t a r 模型实现a v a t a r 行走运动的控制 智能虚拟环境中a v a t a r 的行走运动控制问题及其路径规划避障问题。虚拟 环境是典型的交互应用，其a v a t a r 的行走运动控制首先要满足实时性的要求，即 能够对用户交互做出及时响应，其次，所生成的人体动画应有较强的真实感。因 此，本文深入研究和讨论运动学控制法，它是在实时性、动画真实感上都具有较 好特征的运动控制技术，并提出了相应的算法和控制系统结构解决a v a t a r 行走运 动控制问题。 3 、提高路径搜索速度并对其平滑以增强真实感 寻找到一种最适合本文使用的算法，实现了能够避开障碍物寻找到一条最 优( 或次优) 的路径。本文采用了a 半寻径策略并对其进行改进，通过x 寸o p e n 表的 5 浙江师范大学硕士学位论文 维护提高了搜索速度，由于这样规划出来的路径是直线连接而成的，如果直接沿 直线行走，在拐点处会造成凸出，导致动作很生硬，因此我们提出了对路径的优 化平滑，传统的方法是使用样条曲线，但是，样条曲线会偏离原始路径，并且导 数和积分的求取比较麻烦，我们提出了一种抛物拟台的方法进行优化，以克服样 条曲线的缺点，并使平滑后的路径符合易于积分、微分且逼近原始路径的特点。 全文共分为五章，具体内容安排如下： 第一章是绪论，在本章中讨论了a v a t a r 路径规划及碰撞检测的涵义，详细讨 论了选题的背景，国内外研究现状以及相关理论，介绍了本文所做的工作和论文 的结构安排。 第二章研究障碍物检测，首先场景建模，以b s p 对场景实行管理，给a v a t a r 设计辅助传感器，通过它虚拟人不时地感知周围的环境，避免碰撞。 第三章是对人体行走动画的研究。详细讨论了真实世界中人行走的细节，根 据b r u d e r l i n 对行走过程的分析，该文对其进行了简化，把行走过程的支撑期和 摆动期各分成两个阶段。并基于逆向运动学技术实现了人体行走动画的自动生 成。 第四章是路径规划算法的研究。分析当前最短路径的方法，定义本章做要解 决的问题，分析胁寻径算法的思想，对规划好的路径进行平滑，并提高路径搜索 的速度。 第五章是结论和展望，论述了前四章所做的工作，创新和不足同时对全文做 出了总结。 1 4 小结 本章是绪论部分，着重介绍了论文的研究背景、研究工作的意义以及国内 外研究现状，同时对论文的组织安排也做了说明。 第1 节简要介绍了本课题的来源与研究意义。 第2 节介绍了相关理论和国内外研究现状。 第3 节简要的介绍了论文所完成的主要研究内容和论文的内容组织。 本章是本文的开篇。 6 第二章碰撞检测分析及实现 第二章碰撞检测分析及实现 本章将讨论碰撞检测问题。碰撞检测主要用于两种情况下；检测应用程序 允许碰撞的任意两个物体之间的碰撞；或用于路径规划中，其中动画物体需要沿 着路径移动，并最大限度地保持不与其他物体碰撞。尽管有许多理论研究致力于 n 个独立运动物体的问题，虚拟场景中常见的情况仍然是一个或一些在静态环境 中运动的物体。 在虚拟环境中，由于用户的交互和物体的运动，物体间经常发生碰撞，为保 持视觉上的真实感，需要及时检测到这些碰撞并作出相应的反应。否则，物体间 会发生穿透现象，破坏虚拟环境的真实性和用户的沉浸感。 本文用大量篇幅对其进行探讨，主要原因是出于效率的考虑。在简单的仿真 中，每一步都必须实现碰撞检测，从而系统的运行代价随着场景的复杂性而急剧 增加。 2 1 碰撞检测技术概述 随着计算机图形学、仿真技术和硬件技术的发展，用高质量的计算机动画来 对现实世界进行模拟与再创造己成为可能。很多专家和学者都研究了在动画演示 与模拟中的一个很重要的问题物体之间的干涉和碰撞，并在理论和实际方面提 出了许多有重要价值的研究结果。图形移动时的碰撞检测问题在计算机图形学、 c a d c a m 、动态系统模拟、机器人学以及实时干涉布局等问题中都有着广泛的 应用。 碰撞问题牵涉到碰撞检测和碰撞响应两部分内容。由于碰撞响应问题属于力 学的研究领域，所以本文主要对碰撞检测问题的研究与发展过程作一个概述。碰 撞问题的具体应用很广泛，例如，虚拟环境应用中的飞行员和宇航员的培养与训 练、机器人的路径规划和学习、交互式动画系统、服装c a d 中衣物与人体躯干 的配合等。碰撞检测问题按运动物体所处的空间可分为二维平面碰撞检测和三维 空间碰撞检测。 关于平面碰撞检测问题的研究主要有3 个方面，包括可碰撞、可移动区域和 最初碰撞部位的检测。关于三维空间碰撞问题的研究一般有可碰撞和碰撞规避两 7 浙江师范大学硕士学位论文 个方面。 所谓可碰撞问题就是物体a 和b 在空间沿给定轨迹移动时是否发生碰撞。 可移动区域就是物体a 沿给定的规律运动，而不与物体b 发生碰撞的所有 可能运动的区域。 最初碰撞点的检测就是当物体a 以给定的运动规律运动，并将与物体b 发 生碰撞时，检测它们在最初发生碰撞时的接触部位。 碰撞规避就是两个或多个物体的无碰撞运动。 2 1 1 碰撞检测分类 碰撞检测的基本方法大致可以分为两类：空间分割、法【1 q 和层次包围盒法1 7 1 。 前者是将整个空间划分成体积相等的网格单元，场景中的每个物体对应在一个或 多个单元中，如果两个物体占据不同的网格单元，则说明两个物体没有相交，否 则两个物体做进一步的相交测试。常用的空间分割法有k - d 树，八叉树和b s p 树法等。层次包围盒方法的核心思想是用一个简单的包围盒将复杂的几何形体围 住，当两个物体做碰撞检测时，首先检测两者的包围盒是否相交，若不相交，则 说明两个物体未产生碰撞，否则再进一步对两个物体做检测。比较典型的包围盒 类型有沿坐标轴的包围盒a a b b ，包围球，方向包围盒o b b ，固定方向凸包f d h 等，这丽类算法都使用了层次结构模型，其目标都是尽可能地减少需要进行相交 测试的几何物体的数目。 能够实时地进行碰撞检测是一项开销很大的工作，所以对于简单的虚拟场 景实时碰撞检测一般可以实现，而对于比较复杂的虚拟场景实时碰撞检测却难 以实现。目前，大部分碰撞检测算法是针对虚拟场景的运动物体展开研究的，其 实时性和精确性难以得到统一。 2 1 2 选择适当的碰撞检测算法 进行算法选择需要考虑算法的性能，并适合我们的虚拟环境和使用的对象模 型，对于不同的环境和模型应该选用不同的碰撞检测算法。一般可参照下面的原 则： ( 1 ) 广义阶段( 选出不可能碰撞的物体对) ，广义阶段能使用下列的某一项 8 第二章碰撞检测分析及实现 或多项组合：游戏规则或场景；世界空间划分；局部空间划分；包围体( 球体、 a a b b 和o b b ) 和包围体层次。 ( 2 ) 狭义阶段( 应用精确的碰撞检测) ：多面体多砸体测试：l i n c a n n y 最近物体物貌跟踪；分割平面。 ( 3 ) 用于任意阶段的方法：包围体层次结构；局部空间的空间划分；z 缓 冲。 在整个处理过程中使用单一的划分方法( 比如：h u b b a r d 球树) ，或使用通 用的b s p 树划分方案( 既用于渲染又用于碰撞检测) 。 碰撞检测现在是一个非常活跃的研究领域，至今还没有出现通用的流行算 法。碰撞检测的许多研究着力于解决“n b o d y ”问题。即在最坏的假设下，所 有无约束物体都在场景中运动。然而，n 的数值巨大导致的复杂性并没有物体内 的复杂性重要。l i n 和g o t t s c h a l k 给出了一个关于其他表述的算法的全面综述。 包围体判定的基本原理是，检测包围体是否相交比检测物体相交快的多。但 是，如果加入了高昂的检测预算，这种优点就不存在了，因为包围体相交，而物 体本身未必相交。 碰撞检测的开销是场景中移动物体的数量和物体复杂度( 每个物体的平均表 面数) 的二次函数。对于标准的先广义后狭义的碰撞检测策略而言，这是显而易 见的。单阶段算法的复杂度是o ( 2 2 ) ，这时必须被执行的精度比较数是： n o v 1 ) 2 ，在这个处理中，精确的多面体碰撞检测的复杂度是o ( n 2 ) ，n 是 每个物体的平均表面数。 本课题采用的是基于虚拟感知器的b s p 碰撞检测，将在2 3 小节详细讨论。 2 2 场景管理 2 2 1 场景管理和碰撞检测的关系 碰撞检测是和场景管理息息相关的，碰撞检测问题的复杂度要取决于场景中 的活动物体的总数。假设场景中物体数目为n ，如果使用最笨的方法对所有物体 逐个进行比较的话，则需要进行n ( n - d 2 次比较，那么这种算法是o ( n 2 2 ) ，是 9 浙江师范大学硕七学位沦文 是很低效的。 有了高效的场景管理，才能有高效的碰撞检测。为了创建一个理想的碰撞检 测程序，最好在虚拟环境建立的同时就开始计划并创建它的框架。在项目的最后 加入碰撞检测是相当困难的。想在开发周期的末尾创建快速的碰撞检测将很有可 能会使整个项目被毁掉，因为我们不可能使它能高效地运行。三维虚拟环境中的 碰撞检测应该是精确、有效并且十分快速的。这些要求意味着碰撞检测将要与场 景的多边形管理紧紧地联系起来。这也意味着穷举法将无法工作，当你还在检测 一个物体的各多边形是否与场景中的其它多边形碰撞时，时间已经过去了。 要正确地显示虚拟场景，必须知道哪个多边形在前，哪个多边形在后，谁把 谁遮住了。这是计算机图形学中的隐藏面消除问题，z 缓存算法似乎可以解决隐 藏面消除问题了。但实际上z 缓存算法有其局限性，主要是效率比较差，如果场 景过于复杂，并且实时性能要求高的话，就不能使用了。这就是我们场景管理中 所要解决的问题。 场景 晦子房子 、 树 走廊 夕 家具墙 图2 1 用b s p 树描述场景 f i g u r e 2 1t h ed e s c r i p t i o no f h es c e n a r i ow i t ht h eb s p t l e 场景管理所要解决的，就是设计一种数据结构，用它来表达复杂的虚拟场景， 表达场景中物体的相互关系。有了这种数据结构，我们处理隐藏面消除问题和碰 撞检测的时候就会更简单并且更高效。 显然我们可以采用层次结构来表达场景，一个场景也可以用这种方式来组 织，如上图2 1 所示。显然上面的层次结构可以帮助我们判断物体和物体之间的 关系。比如说a v a t a r 在院子里行走时，要进行碰撞检测。我们可以沿这个场景 1 0 第二章碰撞检测分析及实现 的层次结构下溯，只需要处理左边的部分，整个右边部分所包含的物体和它们的 多边形都不用处理了。这样就把碰撞检测的计算机量大大地降低了。 这种层次结构实际上是对空间的一种划分。也就是把空间分成很多小块，最 终每块里只有一个物体或者物体的一部分。在层次结构的每一个结点上，都要包 含以下信息：这个结点的空间区域多大，在区域内有哪个( 些) 物体或者其部分， 指向具体物体三维模型数据结构的指针等。这样除了原来每个物体自己的三维模 型数据结构外，我们就有了另一个全局的数据结构，即场景的层次数据结构。两 者之间通过指针相连。 要形成这样的层次结构，需要进行预处理。也就是说，在把所有的模型放到 一块形成场景的时候，要进行计算，得出这么一个层次结构，然后进行实时计算 时使用。 层次结构中被人们研究得最多的就是树状结构了。目前场景管理用得最多的 层次结构是b s p 树。最早使用b s p 树的游戏就是大名鼎鼎的d o o m ，此后业 界最有名的三个游戏引擎系列q d a k e1 1 、u n r e a l 、和l i t ht e c h 都提供了对b s p 树的广泛支持。 2 2 2b s p 树及其在场景管理中的应用 为什么要用树来组织场景呢? 因为使用树结构来表达场景的话，可视性问题 和碰撞检测问题都最终归结为树的遍历和下溯，而这些操作都是o ( n ) 或者 o ( n l o g n ) 的，也就是效率比较高。这对实时画面处理非