（计算机应用技术专业论文）虚拟人全局路径规划技术研究.pdf

江苏大学硕士研究生毕业论文 摘要 受虚拟现实技术飞速发展的驱动和客观应用需求的牵引，虚拟人技术逐渐成 为虚拟现实技术的一个重要分支，虚拟人的路径规划问题作为该领域的一个重要 研究方向，已经成为新的研究热点。 本文主要针对虚拟人路径规划技术涉及到的环境地图建模方法和路径规划 算法进行了研究与探讨。 在使用栅格法建立虚拟环境地图中引入了层次包围盒技术，并对该技术在环 境地图创建中的具体应用进行优化处理。针对具体的应用环境，选择性地创建虚 拟环境中障碍物的包围盒，并将其映射到x - z 平面；另外，文中还研究了包围 盒的几何表示到基于栅格图的像素点表示的转换、处理工作。 提出了一种在橱格模型中规划路径时减少判断处理临近节点个数的方法，称 之为r g n ( r e d u c eg r i d sn e i g h b o r i n gn o d e s ) 优化方法。针对在栅格模型中规 划路径时，每规划一个节点均需对其八个临近节点进行判断处理这一缺点，根据 栅格模型及其中最短路径的特性提出了r g n 优化方法，该方法可以应用于所有 基于栅格模型的路径规划算法，并且可以扩展应用到高维栅格空间，文中对此给 出了数学模型及详细分析。 提出了一种在栅格模型中使用的、基于r g n 优化方法的路径规划算法，称 之为r b p p a ( r g n b a s e dp a t hp l a n n i n ga l g o r i t h m ) 算法。该方法综合了分层扩 展和d i j k s t r a 算法的思想，利用分层扩展的原理取消了d i j k s t r a 算法中每规划一 个节点后，在所有己扩展节点中选择与初始节点距离最短的节点这一步骤；并针 对栅格环境的特点，使用r g n 优化方法减少路径规划过程中判断处理的节点个 数。 最后，对将r b p p a 算法用于虚拟入的路径规划进行了分析讨论，并使用j a v a 开发了实验仿真系统。在该实验平台上实现了r b p p a 算法、d i j k s t r a 算法和基于 分层扩展的路径规划算法，通过比较各实验结果，验证了r b p p a 算法的正确性 和有效性；另外，该平台还实现了将r b p p a 算法用于虚拟人的路径规划、给定 不同的虚拟人物理参数时实验仿真，验证了将r b p p a 算法用于虚拟人路径规划 的可行性。 关键词：虚拟人，路径规划，栅格法，d i j k s t r a 算法，分层扩展，层 次包围盒 江苏大学硕士研究生毕业论文 a b s t r a c t w i t l lt h ei n - d e p t hd e v e l o p m e n to fv i r t u a lr e a l i t yt e c h n o l o g ya n dt h ei n c r e a s i n g r e q u i r e m e n tf o ri t , t h er e s e a r c h e so nv i r t u a lh u m a nt e c h n o l o g yh a v ea t t r a c t e dm o r e a n dm o r ea t t e n t i o n t h er e s e a r c ho nt h ep a t hp l a n n i n gi so n eo f t h ei m p o r t a n tt a s k si n t h es t u d yo f v i r t u a lh u m a n , g r a d u a l l yf o r m i n gan e wh o tr e s e a r c hf i e l d p a t hp l a n n i n gi nav i r t u a le n v i r o n m e n tr e q u i r e sam o d e lo rr e p r e s e n t a t i o no ft h e e n v i r o n m e n tk n o w na se n v i r o n m e n tm a p 1 1 1 em e t h o d sa b o u th o wt og e n e r a t et h e e n v i r o n m e n tm a pa n dt h ep a t hp l a n n i n ga l g o r i t h m sa r e t h et w o m o s ti m p o r t a n ta s p e c t s o fp a t hp l a n n i n gt e c h n o l o g y , w h i c ha l es y s t e m i c a l l ya n dd e e p l ys t u d i e di nt h i st h e s i s 1 1 坞m a i nw o r ka n dc o n t r i b u t i o n sa r es u m m a r i z e da sf o l l o w s ： f i r s t l y , c o n l t l l o nm e t h o d so nm o d e l i n go fv i r t u a le n v i r o n m e n ta n ds e a r c h i n g s t r a t e g ya r er e v i e w e d i nt h er e v i e w , t h ea d v a n t a g e sa n dd i s a d v a n t a g e so ft h o s e m e t h o d sa r el i s t e d g r i dm e t h o di sc h o s e nt og e n e r a t et h ee n v i r o n m e n tm a p ，a n d h i e r a r c h i c a lb o u n d i n gb o xt e c h n o l o g yi si n t r o d u c e dt or e d u c et h ec o m p l i c a t i o no ft h e e n v i r o n m e n tm a pg e n e r a t i o np r o c e s s t h e n , t h i st h e s i sp r e s e n t sas i m p l et e c h n i q u et os p e 娥 1 l po p t i m a lp a t hp l a n n i n g o ne u c l i d e a n - c o s t 鲥d sa n dl a t t i c e s ，w h i c hi sc a l l e dr g nm e t h o d g r i d sa n dt h e s h o r t e s tp a t h si nt h eg r i d sh a v et h e i rr e s p e c t i v ec h a r a c t e r i s t i c , w h i c hc a nb ee x p l o i t e d t oi m p r o v et h ee f f i c i e n c yo fp l a n n i n go n 鲥d s s or g nm e t h o di sp r o p o s e da n d p r o v e d ，w h i c hc a l lb eu s e dt oa n yp a t hp l a n n i n ga l g o f i t h mb a s e do ng r i dm a p a n dt h e i l s ea r e a so fr g nm e t h o dc a nb ee x p l o r e dt oh i g hd i m e n s i o n 西d 勰w e l l 碱sp a p e r a l s og i v e so u tt h ec o r r e s p o n d i n gm a t hm o d e l s t h i r d l y , ap a t hp l a r m i n ga l g o r i t h mf o rt h es p e c i a lc a s eo f n a v i g a t i o no n a2 dg r i d i sp r o p o s e di nt h et h e s i s ，w h i c hi sc a l l e da sr b p p a i tc o m b i n e st h er g nm e t h o dt o r e d u c et h en u m b e ro fn e i g h b o r i n gn o d e sc o n s i d e r e dd u r i n gan o d ee x p a n s i o ns t e p t h ea n a l y s i sa b o u th o wt ou s et h er b p p aa l g o r i t h mo nt h ep a t hp l a n n i n gf o rv i r t u a l h u m a ni sa l s op r e s e n t e di nt h ep a p e r f i n a l l y , as i m u l a t i o ns y s t e mi ss e tu p , w h i c hi sd e v e l o p e dt or u nt h e s ep a t h p l a n n i n ga l g o r i t h m s c o m p a r i n gt h es i m u l a t i o nr e s u l t so fr b p p aa n do t h e r ss h o w s t h a tt h er b p p ai sf e a s i b l ea n dm o r ee 币c i e n t k e yw o r d s ：v i r t u a lh u m a n , p a t hp l a n n i n g ，鲥dm e t h o d , d i j k s t r aa l g o r i t h m , e x p l o r i n g b yl a y e r , h i e r a r c h i c a lb o u n d i n gb o x 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保 留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借 阅。本人授权江苏大学可以将本学位论文的全部内容或部分内容编入有关数据库 进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 保密口，在 年解密后适用本授权书。 本学位论文属于 不保密匹了。 学位论文作者签名：鲍守 卅年占月脏同 指导教师签名： 滞s 玛 独创性声明 本人郑熏声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究 工作所取得的成果。除文中已经注明引用的内容以外，本论文不包含任何其他个 人或集体已经发表或撰写过的作品成果。对本文的研究做出重要贡献的个人和集 体，均己在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名：匀凶宁 日期：二叩7 车舌月f zr 江苏失学硕士研究生毕业论文 1 1 虚拟人概述 第一章绪论 虚拟现实技术( v i r t u a lr e a l i t y ，v r ) 是- - f l 直接来自于应用、涉及众多学 科的实用技术，自2 0 世纪8 0 年代初期出现以来，一直为科学界和工程界所关注。 它汇集了计算机图形学、多媒体技术、人工智能、人机交互技术、传感器技术、 高度并行的实时计算技术等多项关键技术，并随着这些技术的突破而迅速发展起 来。它是多媒体技术发展的最高境界，用户借助必要的设备( 如头盔，数据手套) ， 能够以自然的方式与虚拟环境( v i r t u a le n v i r o n m e n t ，v e ) 中的对象进行交互， 从而产生亲临相似真实环境的感受和体验。 随着虚拟现实技术的同趋成熟，人们已经不再满足于构建只有景色、建筑物 等一般视景信息的虚拟环境，迫切需要在虚拟环境中加入有生命的对象。所以， 人在虚拟环境中的建模与仿真研究已经越来越受到人们的重视，逐渐成为新的研 究热点。虚拟人( v i r t u a lh u m a n ，v 狮是完全由计算机生成的图形实体，用来模 拟现实世界中真人的行为和动作，是人在计算机生成空自j 中几何特性与行为特性 的逼真表示i lj i “。该技术的研究涉及到计算机图形学、运动学与动力学、多功能 感知、机器人学、人工智能、虚拟现实和心理学等多个研究领域【3 】，是一个交叉 应用学科。 虚拟人作为- - f q 新兴学科，在一些文献中还有其他的称谓，如双足关节人 ( b i p e d a l a r t i c u l a t e d f i g u r e s ) 【4 j 、关节人( a r t i c u l a t e d f i g u r e ) 5 1 、人形对象( h u m a n f i g u r e ) 【6 j 、类人对象( h u m a n - l i k ef i g u r e ) 1 7 1 等等，但是它们的实质都是对人的 模拟。另外，当虚拟人的行为完全由计算机程序控制时，我们称之为代j 里( a g e n t ) ， 即a g e n t 是具有自主行为的软件进程；虚拟人的行为也可以由虚拟环境的实际参 与者控制，此时虚拟人被称为真人的化身( a v a t a r ) s l 。 虚拟人有多种分类方法。1 9 9 6 年，n l a l m 跏p 惶出了将虚拟人分为如下四种 类型：分享型、引导型、自主型和交互感知型。但是，这种分类方法忽略了虚拟 人的面部动茴。n a d i a m a g n e n a t t h a l m 删【1 0 】于1 9 9 8 年提出了包括面部和身体运 动控制的虚拟人分类方法：化身虚拟人，弓i 导虚拟人，自主虚拟人和交互感知虚 拟人。2 0 0 0 年，a l f r e d ip i n a t “】根据虚拟人运动和行为控制信息的性质给出了一 种分类方法，该方法本质上与n a d i am a g n e n a tt h a h n f l n n 的方法一致。另外，根 据虚拟人的自治程度也可将其分为3 类【1 2 j ：引导型、程序控制型、自治型。 江苏大学硕士研究生毕业论文 在虚拟环境中，利用虚拟人来模拟真人的行为并对其性能进行评估，这在计 算机辅助测试、机械工程、军事、医学和空间探索等应用中变得越来越重要【1 3 1 。 它可以对计算机设计的车辆、工作空间、机械零件等在实际构造前进行人体工效 学评估；在人无法达到的环境中进行精密、甚至危险的试验；在军事上代替真人 接受各种训练，并对武器性能进行评估；在医学上代替真人接受外科手术治疗； 在空间探索中代替真人从事太空作业。另一方面，虚拟人作为我们自身在虚拟环 境中的表示与其它虚拟实体进行交互，它在虚拟环境中的真实体现不仅增强了人 与虚拟环境交互的自然性，而且提高了虚拟环境的逼真度和沉浸感，为创造适人 化虚拟空间奠定了坚实的理论基础。因此，虚拟人的研究不仅具有较高的理论价 值，更具有广泛的实际应用价值。 但是，受各学科研究发展的制约，目前对虚拟人的研究还主要集中在理论和 方法的研究【1 4 1 ，计算机动画和仿真是验证基本理论和方法的重要途径。虚拟人技 术的研究大致可以分为虚拟人的几何表示【1 5 1 - 2 0 1 、虚拟人的运动规划1 2 1 l 。【拥、虚拟 人的行为表达【2 7 1 。0 0 以及虚拟人的认知表达【3 l 】四个主要方面。其中，虚拟人的运动 规划又可分为虚拟人的导航运动、虚拟人自身的动画和虚拟人操作处理其他物体 三种类型。 虚拟人导航运动的关键在于，规划出虚拟人从目前所在位置到达某一个特定 位置的具体路线。这条路线必须是安全的，即虚拟人在移动过程中需要同时避开 与障碍物及其他虚拟人的碰撞。导航规划与传统意义上的运动规划最为接近，然 而，诸多因素加大了该问题的复杂性。虚拟人运动于其中的场景也许非常大，而 虚拟人的运动又必须实时地计算出来，为此，我们需要选定一种合适的数据结构 来保存环境信息，使得这种环境信息图便于路径规划。 虚拟人自身的动画主要研究虚拟人( 通常是关节型的) 在一定邻域内对人体 运动的模拟，所以关键是要规划出虚拟人自身内部的运动。另外，这种运动需要 和在虚拟环境中的航行路线相匹配。例如，虚拟人的跑步或行走动画需要首先规 划出虚拟人的跑步或行走时身体各部位的变化情况，具体实现该动画时，虚拟人 需要沿着事先规划好的航行路线移动，并做出相应的动作。 虚拟人操作处理其他物体的运动较为复杂，除了需要规划出虚拟人自身的动 画外，我们还需要规划出被操作对象与虚拟人间的位置关系以及被操作的对象相 对于虚拟人的运动。例如，虚拟人要充一杯咖啡，假设虚拟人就站在咖啡机旁边， 我们需要规划出虚拟人伸手拿咖啡杯，将咖啡杯充满等一系列动作。整个运动的 规划除了需要规划出虚拟人伸手拿咖啡杯时的身体动画、虚拟人拿起咖啡杯时手 部形状的变化，还需考虑手与咖啡杯接触的位置，咖啡杯被拿起后的运动等等。 2 江苏大学硕士研究生毕业论文 如果被操作对象是可变形的柔软物体，则还需考虑虚拟人手拿物体时，该物体受 力后的变形，以及随着该物体的变形虚拟人手的变化等等。 目前，研究者对虚拟人运动规划的研究主要集中在一定邻域内对人体运动的 模拟，即对虚拟人自身动画和虚拟人操作处理其他物体的研究，对虚拟人通过复 杂的障碍环境进行长距离的导航运动研究的还不是很多【3 2 1 1 3 3 ，原因在于这方面 的研究不仅涉及到人体的多种运动，而且还涉及到虚拟环境的表示、路径规划算 法等一系列问题。然而，赋予虚拟人这种运动能力不仅会增强其行为的自主性， 而且对建筑、遥控、空间探索、人员培训等领域都有重要的应用价值。 1 2 虚拟人路径规划技术的现状及发展 虚拟人的导航运动，即虚拟人的路径规划，需要在虚拟环境中寻找出一条从 初始位置到目标位置的符合一定性能要求的最优或次优路径，当虚拟人沿此路径 运动时不会与虚拟环境中的其他物体或虚拟人发生碰撞。该问题可以划分为三个 子任务：1 将虚拟环境描述为适合路径规划算法所利用的权值图：2 搜索出一条 满足一定性能要求的路径；3 控制虚拟人沿着规划出的路径运动。下面分别对这 三个模块的研究现状及方法进行介绍、分析。 1 2 1 环境地图建模 在虚拟环境中进行路径规划，首先需要将环境空间的描述由其原始形式通过 一系列处理转化为适合规划的内部模型，这个过程我们称之为环境地图的建模。 不同的环境建模方法均有其各自的优缺点，根据具体应用选择合适的环境建模方 法有利于减少路径规划过程中的搜索量及时空开销。对虚拟环境的建模基本上有 四种方法0 4 j ，下面分别进行介绍。 1 障碍物多边形表示法 障碍物的多边形表示方法将虚拟环境中任意形状的障碍物用近似的多边形 代替( 对于三维环境，则是使用多面体来代替环境中的障碍物) 。相对于其他的 环境建模方法而言，该方法明确指出了虚拟环境中应该避免的障碍物区域，比较 精确的摇述了虚拟环境。场景的复杂度和表示虚拟环境中障碍物的多边形个数k 及各多边形的顶点n 有关。 对应于该环境描述方法的典型路径规划算法是可视图法，使用该方法规划出 的最优路径存在虚拟人经过障碍物顶点时太靠近，甚至接触障碍物的缺点，切线 图和v o r o n o i 图对可视图方法进行了改进。这三种方法的介绍详见1 2 2 节。 江苏大学硕士研究生毕业论文 2 无障区域法 无障区域法将虚拟环境中的各自由区域表示为环境图中的节点，并根据各自 由区域间的连通关系，将各节点连接起来。该方法将虚拟环境表示为适合于路径 规划算法所利用的无向图，而对应的虚拟人的路径规划则转换为在该无向图中找 出从初始节点到目标节点的最优路径。 与该环境描述方法对应的路径规划算法是自由空间法。它可以使虚拟人经过 障碍物顶点时远离障碍物，但其缺点在于，构造自由空间的计算量非常大，且虚 拟人趋于沿自由空间的中央区域运动，因此，为了到达目标，虚拟人所走的路径 不是最短的。自由空| 日j 的构建方法详见1 2 2 节。 3 复合空间图 障碍物的多边形表示法和无障区域法均可理解为使用面向对象的方法描述 虚拟环境，它们分别给出了环境中障碍区域和自由区域的具体描述，而复合空间 图法则同时给出了这两个方面的信息。 复合空间图法是将虚拟环境分解成多个简单的区域，可以使用层次树或栅格 图来描述虚拟环境。 采用层次树描述虚拟环境时，首先是把虚拟环境空间分成几个较大的区域， 一般来说，二维空日j 分成4 个部分，采用四叉树来表示，如图1 1 ，三维空闯则 分成8 个部分，采用八叉树表示。划分得出的每个区域是下面的三种情况之一： 自由空自j ；障碍空间；混合空间，即既包括了障碍物区域，又包括了自由区域。 对于混合空间按照上述方法继续进行划分，直到一个预先设定好的精度为止。该 方法的主要缺点是计算区域之间的邻接关系时损失较大。 图1 1 层次树图 4 江苏大学硕士研究生毕业论文 使用栅格图描述虚拟环境通常称为栅格分解法。根据该方法描述虚拟环境的 精确情况，可以将其分为精确栅格分解法和近似栅格分解法。其中，近似栅格分 解法使用形状相对固定的规则栅格图来描述虚拟环境，是研究较为广泛的一种环 境表示方法，b a a d i 3 5 i 等把它用于虚拟人的研究，该方法的详细介绍见1 2 2 节。 4 路径图 路径图法是在一个固定环境中使用一组预定义的路径引导运动主体，在不同 环境中的运动则需要不同的路径集合。这种环境建模方法等同予人工指定实体的 运动路线，灵活性差，不适合于虚拟人的运动规划。 1 2 2 路径规划算法 对于虚拟人的路径规划问题，日自i 可参考的资料还不是很多，基本思想是将 传统的移动机器入路径规划的思想移植过来。移动机器人的路径规划算法有多种 分类方法，文献 3 6 1 中将其分为三大类：基于事例的学习规划方法、基于行为的 路径规划方法、基于环境模型的规划方法。依照环境信息豹获知情况，又可将其 分为环境信息完全已知的全局路径规划与环境信息部分未知或完全未知的局部 路径规划1 3 ”，全局路径规划又称静态或离线路径规划，局部路径规划又称动态或 在线路径规划口引。 虚拟人的全局路径规划主要采用基于环境模型的规划方法。首先，利用已知 的虚拟环境信息建立较为合理的环境图模型，再采用某种搜索算法寻找一条从起 始位置到目标位置的最优或近似最优的无碰撞路径。路径搜索算法的选择及路径 规划的复杂度依赖于环境模型的类型。 基于环境模型的路径规划算法主要有可视图法、自由空间法和栅格法，下面 分别进行介绍。 1 可视图法 可视图法的基本原理是使用多边形法描述虚拟环境，移动实体视为一点，将 移动实体、目标点和多边形障碍物各顶点进行组合连接，并僳证这些直线均不与 障碍物相交( 即直线是可视的) ，这就形成了一张图，称为可视图。由于任意两 直线的顶点都是可见的，从起点沿这些直线到达目标点的所有路径均是运动物体 的无碰路径。搜索最优路径的问题就转化为从起点到目标点经过这些可视直线的 最短距离问题。运用优化算法可删除一些不必要的连线以简化可视图，缩短搜索 时间。该方法的优点是概念直观，实现简单。利用该图，a 算法能够在o ( k + n l o g n ) 时间内进行最短欧氏距离搜索，其中k 是图中边的数量，n 是顶点的数量。 江苏大学硕士研究生毕业论文 但是，可视图的构造代价很高，在2 d 情况中，构造可见图的最大时间复杂 度是o ( n 2 ) ，s c h w a r t z 和s h a r i r 报告说在3 d 情况中，其运行时间复杂度会达到指 数级p 9 j 。并且该方法缺乏灵活性，不适用于圆形障碍物的路径规划问题，一旦虚 拟人的起点和目标点发生改变，就要重新构造可视图，算法的复杂性和障碍物的 数量成正比，且不是任何时候都可以获得最优路径。又因忽略移动实体的尺寸大 小，使得移动实体通过障碍物顶点时离障碍物太近甚至接触。 图1 2 ( a ) 切线图( b ) v o r o n o i 图 切线图法和v o r o n o i 图法对可视图法进行了改造【帅】。 切线图用障碍物的切线表示弧，即切线图中的节点对应于障碍物之间的无碰 公切线在障碍物边界上得切点，边对应切点之闯的连线，可以使用移动线和扫描 线相结合的方法构造切线图【4 ”。首先，采用“移动线算法”检测障碍物顶点之间的 所有公切线，然后利用一种“扫描线算法”测试已知公切线与障碍物之间是否存在 交叉点，如果存在，滤除这些公切线，剩下的公切线构成的图被称为切线图【4 2 l 。 构造切线图在最坏情况下的时间复杂度为o ( 【m + r 】n + m 2 l o g m ) ，其中n 表示障碍 物顶点数，m 表示n 个点构成的凸蘸线的条数，r 表示开凸曲线的滚动数。因此， 切线图比可视图有更少的边，具有构造的图结构简单、节省存储空间、规划速度 快等优点。但是移动实体必须几乎接近障碍物行走，如果控制过程中产生位置误 差，移动实体碰撞的可能性会很高。 v o r o n o i 图用尽可能远离障碍物和墙壁的路径表示弧，即这些弧上的点到附 近的两个或多个障碍物的边缘是等距离的。v o r o n o i 图的构造时间复杂度是 o ( n l o g n ) ，实时性较好，生成的路径相对比较安全，远离障碍物，并且路径比较 平滑，合理性也较好，采用这种控制方式时，即使产生位置误差，移动实体也不 会碰到障碍物。但是，该方法使得虚拟人从起始节点到目标节点的路径将会增长， 不能保证路径最优。 2 自由空间法 自由空间法把工作环境分成自由空间和障碍空间两部分，并运用构形空间障 碍( c o n f i g u r a t i o ns p a c eo b s t a c l e ) 的概念，根据运动对象的大小和姿态，将已知 的障碍物扩展，变换为扩展障碍( g r o w n o b s t a c l e ) ，与此同时，运动对象缩成 6 江苏大学硕士研究生毕业论文 为一个点。从而使原来物理空间中求运动对象的无碰路径规划变为构形空间中求 质点的运动轨迹问题，简化了问题的复杂性。自由空间法应用于虚拟人路径规划， 采用预先定义的如广义锥形和凸多边形等基本形状构造自由空间，并将自由空间 表示为连通图，通过搜索连通图来进行路径规划。 自由空间的构造方法是 4 3 1 ：从障碍物的一个顶点开始，依次作其它顶点的连 接线，删除不必要的连接线，使得连接线与障碍物边界所围成的每一个自由空间 都是面积最大的凸多边形；连接各连接线的中点形成的网络图即为虚拟人可自由 运动的路线。按照分自由空间方法的不同可以将其分为：凸区域法、三角形法、 广义锥法等等。 自由空间法能够用清晰的几何模型来描述构形空间，使得自由空间、障碍空 间一目了然，因而可以按任何性能指标来搜索和优化路径，且具有完备解。用某 种搜索策略在自由空间中找到一条路径，移动实体沿着障碍物之间的通道中心运 动。对于比较狭窄的空间区域，它能保证移动实体最大的允许误差，而避免与障 碍物碰撞。而且该方法比较灵活，起始点和目标点的改变不会造成连通图的重构。 但该方法最大的缺点是自由空间的计算量非常大，随构型空间维数的增长， 所需的计算时间成指数倍增长：同时，在构型空间中，随着障碍物的移动，构型 空间障碍的大小和形状等几何性质也随之变化，因而在线建立构型空间需要花费 大量的时间，算法的复杂程度与障碍物的多少成正比。 l e n g y e le l ：a 1 将构形空间障碍离散化 4 4 1 ，使用动态编程技术进行路径规划， 产生离散的单元格路径，他们的方法可以应用在实时虚拟环境中，而且适合在连 通的平面上规划路径。k u f f n e r 采用了相似的方法 4 5 1 ，但是使用d i j k s t r a 算法进行 路径规划的。国内学者卢晓军【4 6 j 提出了基于自由空间法的虚拟人行走规划方法。 3 栅格法 栅格法，即1 2 1 节中介绍的近似栅格分解法，是目蘸研究较为广泛的一种路 径规划方法，它将虚拟人工作环境离散化成一系列大小相等、具有二值信息的网 格单元( 例如可以用l 表示该网格单元被障碍物所覆盖，o 表示自由网格单元) ， 并通过优化算法完成路径搜索，场景的复杂度由栅格图中单元数量表示。 图1 3 是与图1 1 相同的虚拟环境的橱格法描述时得到的环境信息图。 7 江苏大学硕士研究生毕业论文 图1 3 栅格图 该方法以栅格单元为单位记录环境信息，虚拟环境被量化成具有一定分辨率 的栅格图，栅格单元的大小直接影响着环境信息存储量的大小和规划时间的长 短。栅格单元划分大了，环境信息存储量小，规划时间短，但分辨率下降，在密 集环境下发现路径的能力减弱；栅格单元划分小了，环境分辨率高，在密集环境 下发现路径的能力强，但环境信息存储量大，规划时间长【4 7 l 。所以栅格单元大小 的确定，是栅格法中的主要问题【4 s 】。可以根据具体应用的需求来确定栅格单元的 大小，例如本文第三章中对虚拟环境进行建模时，栅格的大小为虚拟人包围盒的 底面正方形。 栅格法有很多优点，它利用形状相对固定的网格单元来近似的覆盖环境空 间，每个栅格单元都有规则的边界，所以分解栅格过程简单，容易实现，并且可 以根据不同的要求来改变最小分辨率，有很强的适应性；只要搜索算法设计的适 当，并且栅格地图中存在从初始节点到目标节点的路径，一定能求得问题的最优 解；可以应用多种成熟的算法和技术，例如可以把栅格用树的结构表示，然后应 用深度优先或广度优先查找法进行搜索最优路径：也可以在栅格地图上应用遗传 算法、蚂蚁算法、人工势场法等其他智能搜索方法进行路径寻优。 但是，如果栅格单元大小选择不当则会影响解的质量，且当搜索空间较大时， 算法所需的存储空间会比较大。可以采用改进的栅格法弥补栅格法的不足，文献 【4 9 将改进栅格法与回归预测结合，该算法适用于具有静态和动态障碍物的路径 规划问题。对栅格的改进采用以障碍物为单位记录的信息量大大减少，克服了栅 格法中环境存储量大的问题。文献【5 0 】给出的结构基自由空间网络法综合了栅格 法和自由空间法的基本思想，依环境结构信息确定来解决自由空间分割过程中构 造想象边界的任意性问题，由此消除路径的不确定性。 8 江苏大学硕士研究生毕业论文 1 2 3 虚拟人动作描述 路径规划完成之后，虚拟人只需在沿着规划出来的路径移动过程中做出相应 的动作即可实现通过复杂环境进行长距离运动的虚拟人动画。多年来，研究者们 已经使用动力学和或反转运动学技术开发了多种成熟的虚拟人运动模型，将其 用到虚拟人动画中，我们需要给出虚拟人各种动作的具体描述。 虚拟人动作的描述可以使用编码的方式提前定义在v r m l 脚本中，但是这 种方法不允许用户改变虚拟人动作的名称，或者自定义一个新的基本动作。所以 我们需要一种虚拟人动画的描述语言，这种语言可以让用户自定义虚拟人的动 作。 虚拟人的动作描述涉及到运动学，机器人学，生物力学等多个学科，它的主 要困难在于人体动作的多样性，不规则性，逼真性等，而用户自定义虚拟人的动 作时，准确地表达动作以及确定许多低阶的参数都非常困难。 目前，已经存在了很多种虚拟人动作的描述语言。从i m p r o v 5 1 1 开始主要有： c m l 【5 2 1 ，a m l 5 3 1 ，p a r 5 4 1 ，s t e p 5 习等。其中c m l 中的虚拟人并不是基于v r m l 的，其语言建立在情景演算的基础上，在实现上依靠计算机图形仿真：a m l 中 主要动作由一个h a p 来描述，使用者只能改变有限的几个属性，在复合动作的更 改方面缺乏灵活性；p a r 提供了一种使用自然语言来描述动作的方法；s t e p 是 基于分布式逻辑程序设计语言d l p 开发的一种脚本语言，通过d l p 提供的处理 和转化能力控制虚拟人。 1 3 论文的主要工作 由前面的介绍可知，虚拟人路径规划技术在诸多领域都有非常高的应用价 值，对其研究具有重要的现实意义。本文首先对虚拟人路径规划的相关技术进行 了研究，包括：虚拟环境的建模方法、路径规划算法和虚拟人动作的描述，在此 基础上，提出了基于栅格模型的虚拟人全局路径规划，并进行了仿真实验。本文 的主要工作如下： 1 深入研究四种常用的虚拟环境建模方法，分析它们各自的优势与不足； 从算法的时间复杂度、规划出路径的特点等多个角度对现存的各种路径规划算法 进行深入的分析与研究，并详细探讨两种基于栅格模型的虚拟人路径规划算法， 对它们的基本原理及实现进行了细致的研究。 2 为解决对三维虚拟环境使用栅格法时，环境离散化非常耗时这一瓶颈问 题，提出将虚拟人高度范围内障碍物分布情况映射到x z 平面；为减小环境映 9 江苏大学硕士研究生毕业论文 射的复杂性，引入包围盒技术，并对该技术在此研究中的具体实现进行优化处理。 3 针对在栅格模型中规划路径时，每规划一个节点均需对其八个临近节点 进行判断处理这一缺点，根据栅格模型及其中最短路径的特性，提出了一种在栅 格模型中规划路径时减少判断处理临近节点个数的方法，称之为r g n 优化方法， 该方法可以应用于所有基于栅格图的路径规划算法；将该方法的应用扩展到高维 栅格空间，给出了统一的数学模型及分析。 4 在上述研究的基础上，提出了一种基于栅格模型的路径规划算法( r b p p a 算法) ，并使用j a v a 开发了仿真实验平台，对该算法进行实验验证。将该算法具 体应用到虚拟人的路径规划时，还需将虚拟人模型的物理参数考虑进去，文中对 此进行探讨。 1 4 论文的组织与安排 全文共分六章，组织如下： 第一章介绍了虚拟人技术和虚拟人路径规划相关技术的研究现状，指出本 文研究的意义，并概述了本文的主要研究工作和贡献。 第二章比较各种虚拟环境地图的建模方法的优缺点，讨论在栅格法描述虚 拟环境中引入包围盒技术需要进行的优化处理，重点介绍将障碍物包围盒的数学 表示转化为栅格图中像素点表示的处理过程。 第三章分析栅格模型及其中最短路径的特性，介绍在此基础上提出的r g n 优化方法，以及该方法到高维栅格空间的应用扩展。 第四章分析了两种基于栅格图的路径规划算法的具体实现，提出一种基于 r g n 优化方法、结合分层扩展与o i j k s t r a 算法的优点的路径规划算法，称为 r b p p a 算法，将该算法与上两种方法进行比较，并讨论了对r b p p a 算法进行双 向改进。 第五章对r b p p a 算法进行仿真实验，并对将该方法用于虚拟人的路径规划 进行分析。 第六章全面总结本文的研究工作和主要贡献，同时指出存在的问题和今后 研究的方向。 1 0 江苏大学硕士研究生毕业论丈 2 1 引言 第二章基于包围盒的环境地图建模 上一章中对虚拟人路径规划的相关技术进行了分类介绍和讨论。由上一章的 介绍我们可以知道，四种环境表示方法中，路径图法因其灵活性差不适合于虚拟 人的路径规划；障碍物多边形表示法和无障区域法分别给出了虚拟环境中障碍区 域和自由区域的精确描述，但是基于障碍物多边形表示法的可视图路径规划方法 缺乏灵活性，一旦虚拟人的起点和目标点发生改变，就要重新构造可视图，算法 的复杂性和障碍物的数量成正比，且不适用于圆形障碍物的路径规划问题；切线 图法、v o r o n o i 图法对可视图法进行了改进，但是使用切线图法进行路径规划， 虚拟人则必须几乎接近障碍物行走，使用v o r o n o i 图法可以使虚拟人尽可能的远 离障碍物，但是其行走路径却不是最优路径；自由空间法通过预处理构造各自由 空间节点，并根据各节点的连通性将虚拟环境表示为无向图，用某种搜索策略在 无向图中找到一条路径，连接各自由空间中心点即得虚拟人行走路经，该方法最 大的缺点是预处理构造自由空间的计算量大，虚拟人在各自由空间的中心白j 移 动，且不是任何时候都可以获得最优路径。 栅格法同时给出了虚拟环境中自由区域和障碍区域的信息，对于2 d 虚拟环 境，该方法将虚拟人工作环境离散化成一系列大小相等、具有二值信息的网格单 元，对于3 d 虚拟环境，则将环境离散化为大小相等的立方体。因此分解栅格过 程简单，容易实现，并且可以根据不同的要求来改变最小分辨率，有很强的适应 性，只要搜索算法设计的适当，并且栅格地图中存在从初始节点到目标节点的路 径，一定能求得问题的最优解，可以应用多种成熟的算法和技术。所以本文将它 用于虚拟人的全局路径规划。 使用栅格法进行路径规划，虚拟环境离散化的时间取决于其各维度上的分辨 率，有时比较耗时，是该方法的一个瓶颈问题。为了简化问题，我们将虚拟人高 度范围内的障碍物分布情况映射到离散为栅格图的x o z 平面( 只有虚拟人高度 范围内的障碍物会影响虚拟人的运动) ，每个栅格单元根据其是否被障碍物所覆 盖标记为障碍单元或自由单元。为了简化环境映射过程，本文将层次包围盒技术 引用到虚拟环境的建模中。本章首先介绍层次包围盒的相关知识，然后详细介绍 引入了包围盒技术的虚拟环境的建模方法。 江苏失学硕士研究生毕业论文 2 2 包围盒技术概述 2 2 1 包围盒的基本概念 包围盒技术是在1 9 7 6 年由c l a r k 提出的【5 6 1 ，基本思想是用一个简单的几何 形体( 即包围盒) 将虚拟场景中复杂的几何物体围住，通过构造树状层次结构可 以越来越逼近真实的物体。 包围盒虽然是我们虚拟出的实体，但必须是有效豹正则实体。一个有效的正 则实体必须是形状与位置和方向无关的刚性实体；必须外部封闭内部连同，没有 悬边和悬点：必须维数一定占有有限的空间；有明显的边界能区分内部区域和外 部区域。 除此之外简单性和紧密性是衡量包围盒优劣的两个标准。就简单性而言包围 盒的几何特性应该比被包围的物体简单尽量较少占用存储空间。包围盒的紧密性 决定包围体逼近物体的程度。紧密性可以用包围盒与物体之间的h a u s d o r f f 距离 来衡量。 固定有限点集彳= ( 岛，a 2 ，4 p ) 和口= ( 6 l ，6 2 ，也) 之间的h a 璐e d o r 行距离为1 5 7 1 ： h ( a ，b ) = m a x ( h ( a ，b ) ，h ( e ，爿) ) ( 2 1 ) 其中 即，召) = 呀卿扣一训，称为由彳到b 的有向h a u s e d o r f f 距离，| j l ( e 彳) 为b 中点到a 的最大距离。 对于包围盒的紧密性我们用r 来表示，口代表物体。g 是包围盒，b 和g 之 间的h a u s d o r f f 距离为： r = n l a x 6 曲p d i s t ( b ，g ) b b ，g g ( 2 2 ) 用d 来表示包围盒与物体之间的最大距离，则： d = m a x p 。 d i s t ( g ，h ) g ，h g ( 2 3 ) 通过包围盒和物体间的h a u s e d o r f f 距离我们就可以衡量出包围盒的紧密性。 2 2 2 几种包围盒类型 最常用的包围盒类型有：沿坐标轴的包围盒( a x i s - a l i g n e db o u n d i n gb o x e s ， a a b b ) 【5 8 】、包围球( s p h e r e ) f 5 9 1 、方向包围盒( o r i e n t e db o u n d i n gb o x ，o b b ) 脚l ，固定方向凸包包围盒( f i x e dd i r e c t i o nh u l l ，f d h ) 6 1 l 等，下面给出简单介 绍。 1 2 江苏大学硕士研究生毕业论文 1 沿坐标轴的包围盒a a b b 一个给定对象的a a b b 被定义为包含该对象且各边平行于坐标轴的最小六 面体。构造时根据物体的形状和状态取得坐标x ，y ，z 方向上的最大、最小值 就能确定包围盒最高和最低的边界点，所以a a b b 包围盒的边界总是与坐标轴 平行，它的平面与其相应的坐标平面相平行。a a b b 包围盒还可以用物体中心点 和三个方向上的跨度来表示： 包围盒a a b b i ( m i n x l , m i n y l , m i n z l ) ，( m a x x l , m a x y l , m a x z l ) ； 包围盒a a b b 2 ( x 0 ，y 0 ，z 0 ) ，0 e n g t h ，w i d t h , h e i g h t ) a a b b 包围盒具有建构简单快速、内存开销少的特点，能较好地适应可变形 物体实时更新层次树的需要。a a b b 的缺点是包围物体不够紧密，在一些情况时 将出现较大的空隙，例如对一个棒状与坐标平面呈4 5 0 角的物体。 2 包围球 。 给定对象的包围球是包含该对象的最小的球体。包围球的球心可以用物体顶 点坐标的最大值和最小值的一半来确定，再由球心与三个最大值坐标问的距离确 定球的半径。 与a a b b 包围盒类似，包围球的构造也十分简单，且只需要球心何半径即 可完全标示出一个球体，对于电脑绘图来说很容易节省存储空间，但是包围球的 紧密性也很差，尤其是对于狭长的物体，甚至要比a a b b 包围盒留下更多的空 隙。 3 方向包围盒o b b 给定对象的方向包围盒被定义为包含该对象且相对于坐标轴方向任意的最 小长方体。o b b 的构造稍微复杂一些，关键在于包围盒最佳方向的确定，最佳 方向必须保证在该方向上包围盒的尺寸最小。 o b b 包围盒最大的特点是方向的任意性，它能根据被包围的几何对象的形 状特点紧密的包围几何对象。大多数情况下其总体性能要优于a a b b 和包围球， 此外，当几何对象发生旋转运动后，只要对o b b 的基底进行