（计算机软件与理论专业论文）动画自动生成系统中运动规划及其路径规划的研究与实现.pdf

摘要 摘要 随着人工智能、计算机图形学和软硬件技术的高速发展，计算机动画已经广 泛应用于工程、科研、文娱等众多领域。中科院陆汝钤院士于9 0 年代提出的全 过程计算机辅助自动生成动画技术将人工智能技术和基于知识的方法引入动画 生成的全过程，其目标是有一个适当的故事，以受限自然语言的形式输入计算机， 基于情节库、场景库、动作库等知识库，将动画制作的全过程依靠计算机自动完 成，最终生成3 d 动画。应用这一技术相继研发了第一版天鹅系统和基于先 进的三维动画制作软、硬件的新版动画自动生成系统。 运动规划是动画自动生成系统中的核心模块之一，它首先在定性层生成定性 的动作描述序列，然后将定性描述通过定量层的动作计算转化为动画的定量描 述，并在转换过程中处理一系列子问题。运动规划是底层动画实现的关键，所有 的运动数据信息都要通过该模块生成。路径规划是运动规划定量层的一个重要的 子问题，它的任务是在已知的动画三维空间中寻找一条由起始点到目标点的无碰 撞路径。通过分类可以将动画中的路径规划问题细分，并使用智能的方法来得到 合理的、真实的角色路径。本文详细描述了动画自动生成系统中的运动规划模块 及其路径规划子模块的设计与实现。 在运动规划部分，本文着重论述了系统中间语言的设计，其中动作定性描述 语言以天鹅系统的定性规范语言为基础，通过综合分析多类动作，提取共同 的关键属性和参数作为定性描述属性。动作定量描述语言肩负着向动画文件转换 的任务，采用以角色为单位的关键帧序列进行结构化描述。对于动作库，本文通 过三维动作捕捉技术( m o t i o nc a p t u r e ) 对人体运动数据进行采集，生成动作的 b v h 格式文件后再转化到动作库中。运动规划的定量层动作计算模块负责将 动作的定性描述转化为定量描述，本文设计并实现了这一转化的完整流程。 在动作计算中，动作库中的运动数据是利用动作捕捉系统采集生成的b v h 格 式数据，而最终动画是在m a y a 软件中展示的，但m a y a 并不支持b v h 旋转数据的 解读，而是使用e u l e r 角来表达旋转信息，这就产生了一个运动数据跨平台转换 问题。本文提出了一种算法来实现b v h 运动数据在m a y a 中的转换，首先针对人 体骨架的单个关节，利用矩阵等价的方法建立起b v h 旋转与e u l e r 旋转的关系， 以求解对应的e u l e r 角，然后将这一方法应用于整个骨架来实现动作的转换。 在三维路径规划部分，本文设计了地形建模算法和障碍物建模算法分别对动 画场景的三维空间进行划分，并以八叉树结构进行保存，由于地形和障碍物模型 的物理表达形式差别很大，建模后可对两者进行统一的表达。八叉树不易表达场 景的相邻结点，本文设计了邻域查找算法以进行八叉树中相邻结点的查询。在路 北京工业大学工学硕士学位论文 径搜索时，首先设计一个场景图邻接表结构，这是一个动态结构，可表示八叉树 结点的相邻关系，本文采用i d a * 算法进行路径搜索，随着搜索范围的增加，邻 接表结构随之扩大。针对不同的动画情节，本文将路径规划分为飞行类路径、爬 行类路径和群体类路径三类问题，每类问题都对i d a * 算法进行一定的调整，来 生成与情节相符的路径。 关键词动画自动生成；运动规划：动作转换；三维路径规划 a b s t r a c t a b s t r a c t a sa r t i f i c i a li n t e l l i g e n c e ，c o m p u t e rg r a p h i c sa n dc o m p u t e rs o f t w a r e a n dh a r d w a r et e c h n o l o g yr a p i d l yd e v e l o p s ，c o m p u t e ra n i m a t i o nh a sb e e n w i d e l ya p p l i e di ne n g i n e e r i n g ，s c i e n t i f i cr e s e a r c h ，e n t e r t a i n m e n t ，a n d o t h e rf i e l d s f u l l1 i r ec y c l ec o m p u t e ra i d e d a n i m a t i o ng e n e r a t i o n t e c h n o l o g y ，w h i c hw a sp r o p o s e db yp r o f r u q i a nl ui nt h e1 9 9 0 s ，i n t e g r a t e s a r t i f i c i a li n t e l li g e n c ea n dm e t h o d sb a s e do nk n o w l e d g ei n t ot h ew h o l e p r o c e s so fa n i m a t i o ng e n e r a t i o n t h et e c h n i q u er e c e i v e sa si n p u tap r o p e r s t o r yw r i t t e ni n s o m el i m i t e dn a t u r a ll a n g u a g ea n dg e n e r a t e s a3 d a n i m a t i o nc a r t o o na so u t p u t t h ew h o l ep r o c e s si sh a n d l e db yc o m p u t e rw i t h t h es u p p o r to fk n o w l e d g eb a s e s a p p l y i n gt h i st e c h n o l o g y ，s w a ns y s t e ma n d a u t o m a t i ca n i m a t i o ng e n e r a t i o ns y s t e mb a s e do ns o m ep o w e r f u l3 ds o f t w a r e a n dh a r d w a r ea r es u c c e s s i v e l yd e v e l o p e d m o t i o np l a n n i n g ，o n eo ft h ec o r em o d u l e si na n i m a t i o ns y s t e m ，f i r s t l y g e n e r a t e dq u a l i t a t i v ea c t i o nd e s c r i p t i o n ( a d l ) i nq u a l i t a t i v el a y e r s ， a f t e rw h i c hq u a l i t a t i v ed e s c r i p t i o ni s t r a n s f o r m e di n t oq u a n t i t a t i v e d e s c r i p t i o n ( c a l ) b ya c t i o n c a l c u l a t i o nm o d u l ew h i c ha l s op r o c e s s e s s p e c i f i cp r o b l e m si nt h ec a l c u l a t i o np r o c e d u r e m o t i o np l a n n i n gi st h ek e y o fa n i m a t i o ng e n e r a t i o n ，f o ra l la c t i o nd a t aa r ep r o v i d e db y t h i s m o d u l e p a t hp l a n n i n g ，a ni m p o r t a n ts u b p r o b l e mo fm o t i o np l a n n i n gi nt h e q u a n tit a tiv ela y e r ，c a ng e n e r a t ean o n c o l lisi o n ，r e a la n dr e a s o n a b le p a t hf r o ms t a r tp o i n tt oe n dp o i n ti n3 ds p a c eb yp a t hc l a s s i f i c a t i o na n d i n t e l l i g e n tm e t h o d t h i sp a p e rd e s i g n sa n dr e a l i z e sam o t i o np l a n n i n g s y s t e ma n dap a t hp l a n n i n gs u b s y s t e mi nt h ea u t o m a t i c a n i m a t i o ng e n e r a t i o n s y s t e m i nm o t i o np l a n n i n g ，w ef i r s tf o c u so nt h ed e s i g no fs y s t e ma n i m a t i o n i n t e r m e d i a t el a n g u a g e a c ti o na d lm a k e sar e f e r e n c et os w a ns y s t e ma d l s t a n d a r d ，a n dc o n t a i n sa c t i o nq u a l i t a t i v ea t t r i b u t e sw h i c ha r ee x t r a c t e d f r o mc o m p r e h e n s i v ea n dp r a c t i c a la c t i o na sk e ya t t r i b u t e sa n dp a r a m e t e r s a c t i o nc a lc o n t a i n st h er o l ea c t i o nk e y f r a m e sa su n i t ，a n di su s e df o r t h ef i n a la n i m a t i o ng e n e r a t i n g t h e nw ea c u q e s tb v hf o r m a tf il et h a t r e c o r d i n gr o l ea c t i o n sc a p t u r e db ym o t i o nc a p t u r e ，a n dt r a n s f o r mt h eb v h d a t ai n t oa c t i o nd a t a b a s e a tl a s t ，w ed e s i g na n dr e a li z e ac o m p l e t e i l l 北京工业大学工学硕士学位论文 p r o c e s so fa c t i o nc a l c u l a t i o nm o d u l e i nt h e q u a n t i t a t i v el a y e r t o t r a n s f o r mt h ea c t i o na d lt oc a l t h em o t i o ni n f o r m a t i o ni na c t i o nd a t a b a s ei sr e c o r d e db ym o t i o n c a p t u r es y s t e mi nb v hf o r m a t t h ef i n a l3 da n i m a t i o ni sr e n d e r e di nm a y a s y s t e m h o w e v e r ，m a y ad o e sn o ts u p p o r tb v hf o r m a tb u tr a t h e ru s e se u l e r a n g l e s t o r e p r e s e n tr o t a t i o n s ，w h i c h l e a dac r o s s p l a t f o r md a t a c o n v e r s i o np r o b l e m t h i sp a p e rp r e s e n t sat r a n s f o r m a t i o na l g o r i t h mt o r e a li z et h eb v hm o t i o nd a t ac o n v e r s i o ni nm a y a f i r s t l y ，f o rs i n g l eh u m a n s k e l e t a l j o i n t ，r o t a t i o n m a t r i c e se q u i v a l e n c yi s u s e dt ob u i l d c o r r e s d o n d e n c e sb e t w e e nb v ha n de u l e rr o t a t i o n s ，t h u se u l e ra n g l e sc a n b ec o m p u t e d t h e nt h em e t h o di sa p p l i e dt ot h ec o m p l e t e s k e l e t o nt o t r a n s f o r ma na c t i o n o nt h ep a t hp l a n n i n gp r o b l e mi n3 ds p a c e s ，w ep r o p o s et e r r a i nm o d e l i n g a l g o r i t h ma n do b s t a c l e sm o d e li n ga l g o r i t h mt or e s p e c t i v e l yp a r t i t i o nt h e s c e n ei n t os u b s p a c e sa n dp r e s e r v et h es u b s p a c e si n t oo c t r e es t r u c t u r e ， w h i c hc a np r e s e n tb o t ht e r r a i na n do b j e c tm o d e li nau n i f i e df o r m i nv i e w o ft h a tt h eo c t r e ei sn o te a s yt oe x p r e s st h ea d j a c e n tn o d e s ，w ed e s i g n an e i g h b o r h o o ds e a r c ha l g o r i t h m sf o rq u e r y i n gt h ea d j a c e n tn o d e s t of i n d ap a t hi nt h ea n i m a t i o ns c e n em o d e l ，w ef i r s ti n t r o d u c eas c e n eg r a p h a d j l i n ks t r u c t u r e ，w h i c hi sad y n a m i cs t r u c t u r et op r e s e r v et h ea d j a c e n c y r e l a t i o n s h i po ft h eo c t r e e a c c o r d i n gt ot h ed i f f e r e n ta n i m a t i o np l o t s ， w ep u tt h ep r o b l e mi n t o3c a t e g o r i e s ，w h i c ha r ef l y i n g p a t hp l a n n i n g ， w a l k i n gp a t hp l a n n i n ga n dg r o u p sp a t hp l a n n i n g i d a * a l g o r i t h mi sa d o p t e d i nt h i sp a p e r ，a n dw i l lb ea d j u s t e di ns p e c i f i cs c e n a r i ot og e n e r a t ea r i g h tp a t h k e y w o r d sa u t o m a t i cg e n e r a t i o no fc o m p u t e ra n i m a t i o n ；m o t i o np l a n n i n g ； m o t i o nt r a n s f o r m a t i o n ：3 dp a t hp l a n n i n g i v 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得北京工业大学或其它教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意。 签名：驾日期：如q 拿。! f 关于论文使用授权的说明 本人完全了解北京工业大学有关保留、使用学位论文的规定，i i - 学校有权 保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部 分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 签名：二圣牡? 师签名： 撇儡l i i ii i ：幽宰。“ 第l 章绪论 第1 章绪论 1 1 研究背景及研究意义 1 1 1 计算机动画的发展 计算机动画的研究起源于2 0 世纪6 0 年代，当时人们关注于二维动画的研究， 并提出了“关键帧动画技术 ，借助于计算机生成一系列关键帧的图形图像，并 自动插值计算中间帧。7 0 年到8 0 年代，二维计算机动画技术进一步发展，人们 研制出了交互式二维动画系统，并开始通过计算机辅助制作传统的卡通动画。 7 0 年代，随着计算机图形学技术和软硬件技术的快速发展，人们在二维动画 的研究基础上开始探索三维计算机动画技术，通过计算机模拟三维空间的实体， 构造几何模型并赋予材质、纹理、颜色等特征，然后对模型赋予运动、变形、位 置、路径，将各种造型置于动画场景之中，并设置灯光、摄像机的参数，最终生 成一系列可动态播放的运动图像。在研究过程中，计算机造型、真实感图形绘制、 动画控制等动画技术得到了长足的进步，使三维动画具有非常逼真的效果，关键 帧动画法、基于物体的动画法等动画制作方法也应运而生。 随着计算机动画的迅速发展，三维计算机动画技术广泛应用于电影电视、广 告制作、科研、教学、建筑装潢、游戏制作等诸多领域。像功夫熊猫、机器 人总动员这样的三维动画影片，以及赤壁等战争片的宏大作战场面，都借 助了三维计算机动画技术给人们带来了异乎寻常的视觉感受。利用计算机辅助制 作来提高动画、电影的生产效率与质量已成为一种趋势。 目前，动画技术的成熟推动了动画软件的发展，国际上涌现了许多优秀的动 画制作软件，其中影响较大的有美国的3 d m a x 、m a y a 、l i g h t w a v e ，法国的t d i e x p l o r e ，加拿大的a 1i a sw a v e f r o n t 、s o f t i m a g e 、s u m a t r a 。这些优秀的软件 迅速地应用了动画领域新的研究成果，如粒子系统、群体运动、变形技术、动力 学模型、关节运动等，使得软件具有强大的功能和各自的特色，并且不断推陈出 新，不断完善。随着o p e ng l 图形标准的普及和计算机硬件性价比的提高，商用 动画软件公司纷纷推出微机版本，进一步推动了计算机动画的应用和发展。 我国对于计算机动画的研究起步较晚，像大闹天宫这样的经典动画，都 是采用传统动画技巧手工绘制的。在1 9 9 0 年亚运会转播时，中央电视台首次采 用了通过三维计算机动画技术制作的节目片头。此后承担制作任务的中科院软件 所、北方工业大学c a d 中心、上海南方c a d 公司成为中国计算机动画研究的 先行者。1 9 9 2 年我国第一部完全用计算机编程技术实现的科教电影相似正 北京工业大学工学硕士学位论文 式放映。此后，科研机构、电视台制作中心、动画游戏制作公司等动画研究单位 日益增多，动画产量也有明显提高。2 0 0 0 年全国动画片产量为1 3 0 0 0 分钟，是 1 9 9 9 年6 5 0 0 分钟的一倍。2 0 0 3 年，我国的动漫产业年总收益超过电影行业。 然而当前国内的动画制作水平还不能满足国内市场的需求，缺少精品之作， 在动画的数量、质量和制作技艺上，都难以抗衡于日、美等国。此外，计算机动 画技术虽然能够在影视、动漫作品的后期制作上有效地提高生产效率和效果，但 并不能从本质上简化动画制作的工序，在动画制作的全过程中，人力资本占有绝 对比重，动画师的技术、工作量和效率决定了作品的成败。因此，人们希望通过 计算机的辅助，结合智能的方法进行动画制作，以提高整体的效率。 1 1 2 课题背景 计算机动画是计算机图形学与多学科相结合的产物，综合利用计算机、艺术、 数学、物理学、机器人学、生物学、心理学、人工智能、多媒体技术、虚拟现实 等学科知识，伴随计算机硬件和图形算法快速发展起来的一门高新技术。它的研 究课题十分广泛，包括人体动画、智能动画、虚拟现实、仿真模拟控制、多媒体 动画、模型研究等几大领域。 智能动画的研究将人工智能、人工生命等技术融入到动画制作之中，从而提 高动画制作的自动化程度和智能性，目前国内外已获得很多优秀的研究成果。 m u l t r a n 系统n 2 1 是一个翻译器，可将自然语言写的故事通过推导脚本、生成 角色动作、环境设置以及摄像机定位，来得到计算机动画。虚拟摄影师系统1 基于摄影知识表达，对虚拟环境中的事件产生实时摄像机规范说明。另外，b y m e 系统“3 在模拟足球比赛环境下，基于角色个性、情感状态和比赛情形可自动生成 丰富的角色语音和面部表情。美国宾州大学对基于指令的动画生成技术研究多 年，研制成功a n i m n l ( a n i m a t i o nf r o mn a t u r a ll a n g u a g ei n s t r u c t i o n s ) 系统哺1 ，用 以生成真实的动画来表现人执行自然语言指令说明的任务的过程。我国的涂晓嫒 博士研究的“人工鱼”系统将人工鱼作为自主智能体，模拟鱼的肌体、感官和 脑部，来自动适应虚拟的海洋环境，这一研究刺激了“人工生命 ( l i f ea r t i f i c i a l ) 学科的发展。 2 0 世纪9 0 年代，中科院数学所的陆汝钤院士提出了一种新的计算机动画技 术全过程计算机辅助动画自动生成技术口8 1 。这一技术涉及了智能动画、人 体动画等多个领域，将人工智能技术、图形学技术和电影艺术引入动画制作过程， 以形成一条动画生产全程自动化的技术路线。该技术将一个以受限自然语言形式 描述的童话故事输入到计算机中，首先对故事脚本做自然语言理解和故事情节理 解，然后将理解出的故事进行场景划分。再根据分场景剧本利用时间、空间规划 2 第1 章绪论 做角色、背景、动作设计。最后根据设计和规划的结果，结合事先准备的动画素 材库来生成完整的动画n 1 。这其间每一步都是在计算机辅助下自动完成的。 1 9 9 5 年，陆院士带领科研小组实现了应用该项技术的第一版动画系统天 鹅n 钔，运用该系统仅花费了两周时间就制作完成了一部十分钟的三维动画片 三兄弟，并在中央电视台播放。若基于传统的方法制作这一动画则至少需要 半年以上的时间。但天鹅系统仍然存在一些缺陷和不足，在动画模型方面仅 使用了基本的三维模型表达角色，缺乏真实的效果；在场景的环境、灯光、摄像 机的设置比较欠缺；一些智能算法一如自然语言理解和故事理解的实现方 案还不是很理想，需要进一步探索。 为了进一步深入研究这项技术，陆汝钤院士于2 0 0 3 年筹建了北京工业大学 动画项目组，在天鹅系统的基础上重新设计了全过程动画自动生成系统，重 点研究人物动画的自动生成技术。与前一版相比，我们使用了更强大的三维动画 硬件和软件作为底层支持，以实现逼真的动画效果。具体地，我们使用m a y a 作 为动画开发平台，通过m a y a 表现自动生成的动画；另外使用m o t i o nc a p t u r e 、 m o t i o n b u i i d e r l 获得真实的人体运动数据，应用到生成的动画中。此外，我们还 对人物模型、故事场景、摄像机等自动控制规划做了深入的研究。本文的研究内 容主要是运动规划和路径规划，运动规划可自动生成动画中角色运动的所有信 息，路径规划是运动规划的一个子系统，用于规划角色的运动路径。 2 0 0 7 年，项目组承担了国家科技支撑项目子课题基于语义理解的古代 建筑场景动画自动辅助生成技术研究，开始研制中国古代建筑搭建动画自动生成 系统( 简称古建系统) 。该课题将动画自动生成技术应用于古建筑领域，将受限 自然语言描写的古建筑形制脚本作为输入，通过计算机辅助自动生成古建筑搭建 过程的三维动画演示。古建系统的研究着重于对古代建筑知识进行总结，通过确 定建筑形制生成建筑模型信息，而运动规划则重点研究的是物体运动信息的自动 生成。这对于动画自动生成技术的研究具有极大的推动作用，一方面将领域知识 扩展到古建筑领域，另一方面推进了运动规划在物体动画方面的研究。 1 2 研究现状 1 2 i 运动规划的研究现状 在动画自动生成的过程中存在大量的运动规划问题。由于角色的运动表现形 式具有多样性，比如人物的关节运动，人脸表情变化，刚体2 运动，变形运动等 l 一款著名的三维动画应用处理软件，主要用于动作制作 2 在任何力的作用下体积和形状都不发生改变的物体叫做“刚体”( 鼬百db o d y ) 这里指非形变物体 3 北京工业大学工学硕士学位论文 等，对各种运动的控制方法各有不同。我们将这些形式各异的运动问题统称为运 动规划问题。而对运动规划的研究目标旨在降低用户对运动进行描述的复杂程 度，提高表现角色或物体运动的复杂性，最终使用户在较高的层次上完成对角色 运动过程的抽象描述阳3 。简单的讲，运动规划将简单、合理的故事情节赋予角色， 使角色的动作能够连贯、真实地展现故事内容。 由于运动的种类纷繁复杂，人们很难找到一种统一的标准对运动规划的技术 做一个准确的划分。我们可以从用户使用方法、动画语言描述和运动规划算法三 个方面进行简单的分类。 按用户使用方法划分，可分为运动的脚本控制和交互控制。脚本控制就是将 运动的流程事先按照一定的脚本格式定制好，即预制一套完整的运动过程描述， 整个运动过程都是通过脚本进行驱动的，无须人工干预。而交互控制则是用户通 过外部设备与运动规划系统进行通讯，运动通过事件触发来进行驱动，也就是说 由用户决定进行某种运动后发出指令，系统检测到相关事件后完成对应的运动过 程描述。常见的运动过程描述方法包括关键帧法、路径描述法和使用控制函数。 无论是脚本控制还是交互控制，都是用户从较高的层次上通过一定的动画语言与 运动过程进行的通讯。 采用动画语言进行运动过程描述，事实上就是以形式化的语言来描述运动过 程。w il h e l m s n 叩将运动过程描述划分为高级描述和低级描述。在高级描述中，用 户可以抽象地描述运动，而低级描述必须将运动的所有细节信息一一列数。相对 于高级描述而言，低级描述对运动的精准过程有十分重要的意义。通常需要将运 动的高级描述转换为低级描述。在动画自动生成系统中采用了相似的概念，通过 动画定性描述语言a d l 对动画中的信息进行定性表达，再由定量计算翻译为动画 的定量描述语言c a l 。a d l 就是对动画信息进行高级地、定性地抽象，而c a l 则 使用精确的定量信息表达动画中的运动。 按照运动规划算法还可以进行运动的划分，首先由于环境类型不同可以分为 静态、时变、可移动物体和带约束环境四类运动。静态环境中动画角色和障碍物 的几何结构都是已知的，可按动画角色类型进一步分为移动点、刚体或带关节角 色、单角色或多角色的运动。对于不同的问题，其表示方法、计算策略也层出不 穷。d e n a v i t 和h a r t e n b e r g 提出的正向运动学n 描述关节运动矩阵的方法，以及 g i r a r d 提出的反向运动学n 2 j 3 3 生成关节运动的方法，都广泛应用于关节动画的运 动问题。关于运动学对力学的局限性而无法逼真地模拟人体运动的问题， a m s t r o n g 提出了基于动力学分析的运动控制系统n 钔，来实现更加复杂真实的人 物动画。此外，w i t k i n 等人提出的时空约束n 5 1 是一种新的生成角色动画的方法， 基于动画特征( 时空约束) 描述和物理定律，构成约束的最优化问题，最终求解 得到符合物理规律的运动。对面部动画的研究，w a t e r s 提出了一个基于f a c i a l 4 第1 章绪论 a c t i o nc o d i n gs y s t e m 的脸部表情动画模拟方法n 制，通过参数控制面部肌肉的运 动。 随着运动规划研究的不断深入，有关智能化控制的运动规划问题开始成为热 点。“在未来的基于合成演员的动画系统中，运动将由人工智能、机器人技术等 自动生成【l 训。r i d s d a k e n 町等对任务规划有着深入的研究，任务规划采用基于规 则的运动分析方法研究面向目标的动画系统和运动描述方法，是一种高智能的动 画系统，能够实现路径规划、动力学分析、运动学分析等。在行为动画研究方面， j u s t i n ec a s s e l l 等实现了一个基于多a g e n t 的会话系统口们，该系统可根据用户的 语音语调、面部表情、肢体语言等综合分析，来完成与用户的感情交流。k a r ls m i s 建立了一个虚拟生物进化系统晗们，采用遗传算法模拟生物的形态和神经系统，生 成它们的运动和形态，并通过不同的进化函数仿真特定行为的进化过程。 1 2 2 路径规划的研究现状 无碰撞路径规划是机器人学中的一个经典问题，在计算机动画领域也引起了 人们的高度重视。在给定的运动空间中，用户给出动画角色的起点和终点描述， 考虑场景环境和角色本身的约束，路径规划算法就可以自动计算出角色的无碰撞 路径。对动画中的路径规划进行研究的必要性是显而易见的，在纷繁复杂的动画 场景中，运动的角色需要路径规划提供的运动路径来达到避开障碍物的目的。 路径规划问题广泛应用于众多领域，如地理信息系统、种植和工厂设备的布 局规划、机器人寻路、运输问题和超大规模集成问题等等。很多路径规划问题都 被抽象成经典的计算几何问题，如凸面体问题、v o r o n o i 图问题、三角划分、几 何最优化等，其中一个非常著名的问题是在图中计算最短路径。针对二维空间 的寻路，人们提出了许多多项式复杂度的算法，如简单多边形内与简单多边形外 的最短路径问题1 ，线段障碍物规划空间中的规划问题，凸多边形障碍物规划空 间中的最短路径问题口3 2 钔，单个与多个圆盘的最短路规划问题、钢琴搬家问题乜5 1 和横杆进城问题啪1 等等。 对三维空间中最短路径的求解，c a n n y 和r e i f 阱1 证明了这是一个n p 难的问 题，进而一些有效的近似算法随之产生啪1 。随着动画和游戏的快速发展，人们对 三维路径规划的研究和应用不断增强。在人工智能领域，有许多路径搜索算法， 如a 木算法啪1 、i d a * ( i t e r a t i v ed e e p e n i n ga 木) 一妇算法等，还有将遗传算法与一 般路径规划结合的方法。在虚拟现实领域，k a v r a k i 提出基于采样的 p r m ( p r o b a b i l i s t i er o a d m a p ) 算法口司来解决高维复杂环境的路径规划， r e y n o l d s 口3 1 通过分布式行为模型逼真地模拟了鸟群的飞行路径。在游戏领域，常 用分级寻径法来降低问题复杂性，将地图划分区域，并将入口抽象为点，区域内 北京工业大学工学硕士学位论文 部寻径后进行外部寻径，称为两级寻径法。h p a ( h i e r a r c h i c a lp a t h f i n d i n ga ) 算 法钔也是一种分级寻径法，但需要预先计算区域间距离，这种技术能够适应环境 的动态变化。 在动画自动生成系统中，路经规划是运动规划的一个子问题。天鹅系统 主要关注二维路径规划，而我们现在有了更先进的动画软、硬件的支持，希望把 自动技术向实用化推进，因此我们开始研究三维路径规划。 1 3 本课题的主要研究内容 本文以计算机辅助动画自动生成技术为背景，重点研究了动画自动生成系统 中的运动规划技术，并且将该技术扩展到古代建筑领域，对人物和物体的运动自 动生成技术进行了探讨，此外还对运动规划的子问题之一路径规划进行了研 究。最终本文设计并实现了动画自动生成系统中的运动规划系统及其路径规划子 系统。 在动画自动生成系统中，运动规划以动作为核心，由定性层和定量层两部分 组成。定性层的运动规划称为动作规划，它将场景中运动角色的动作进行组织， 并以动作的定性描述语言a d l 表达。定量层的运动规划称为动作计算，它将a d l 中的定性动作进行定量计算，并以动作的定量描述语言c a l 表达。在这一过程中 需要动作库的支持。本文对动作的定性和定量描述语言进行了设计。对于动作 a d l ，需要定义动作的定性属性，如运动主体、时间、位置、方向等，并对每个 属性定义其使用的参数，通过选择属性的参数进行组合，来表达动画中的动作。 对于动作c a l ，它表达的是a d l 描述的信息对应的全部量化数值信息，并且是运 动规划系统的最终输出结果。本文还研究了定量层的动作计算模块的处理流程和 相关的技术。动画自动生成系统使用的人体动作是通过三维动作捕捉技术 ( m o t i o nc a p t u r e ) 采集获得的b v h 运动数据，进一步转化到数据库中对动作计 算模块进行支持。 本文采用m a y a 作为底层动画开发平台，使用的人体运动数据是采集生成的 b v h 文件。在运动规划定量层将b v h 数据作为最终的运动数据直接应用于m a y a 时，产生了数据跨平台转换的问题。本文从对这一问题的分析入手，展开了对旋 转运动数据转换技术的研究，设计并实现了一种将b v h 运动数据在m a y a 中转换 的算法。 路径规划问题是本文的另一个研究重点。在动画自动生成系统中，路径规划 可计算出一条三维场景中的从起点到终点的路径，并且该路径不与场景中的障碍 物发生碰撞。路径规划包括场景建模和路径搜索两个内容。场景建模是对静态动 画场景信息的预处理，在对场景中的地形和障碍物建模时分别对场景进行划分， 6 第l 章绪论 并以八叉树结构表达空间划分信息。路径搜索以场景模型为基础，首先将八叉树 模型转换为场景图，再采用i d a * 算法进行图搜索。针对不同的动画情节，角色 的路径会有很大不同。本文设计三种路径，并且针对每种路径规划问题对i d a * 算法进行了应用，最终得到一个路径点序列。 1 4 本文结构 第1 章：绪论。首先介绍了计算机动画发展情况和本文的课题背景，然后概 述了运动规划和路径规划的研究现状，最后说明了本文的主要研究内容。 第2 章：运动规划的研究。首先简要地介绍了动画自动生成系统和运动规划 问题，运动规划分为定性层和定量层两部分。然后详细描述了运动规划的动作定 性和定量描述语言设计，接着说明了动作采集技术以及动作库的设计，最后介绍 了运动规划的定量层动作计算模块的处理流程和相关技术。 第3 章：定量层运动信息的跨平台转换。运动信息跨平台转换问题是运动规 划定量层的子问题之一。该章节首先分析了m a y a 中的动作变形问题。接着设计 并实现了一个将b v h 旋转数据转化为m a y a 识别的e u l e r 旋转数据的算法，用于 动作转换。然后通过对比实验证明了算法的正确性。最后对该算法的研究意义进 行了讨论。 第4 章：三维路径规划的研究。路径规划是运动规划定量层的一个重要子模 块。该章节首先将八叉树结构引入三维场景表达，并分别研究了场景中的地形建 模和障碍物建模的方法，然后对路径搜索采用的i d a * 算法进行了分析，并将i d a * 算法应用于不同情节的路径规划问题。最后介绍了路径规划与运动规划的接口设 计。 第5 章：系统实现及测试。首先对运动规划的系统设计、相关技术和动画语 言实现进行了介绍，并给出了测试实例和实验结果。然后对路径规划的演示平台 进行了介绍，并对演示平台进行了测试。 结论：对本文的工作进行了总结，阐述了本文研究的意义，对工作的不足进 行了分析，最后讨论了进一步的研究方向。 7 第2 章运动规划的研究 i i _ 第2 章运动规划的研究 2 1 动画自动生成系统 2 1 1 系统概述 全过程动画自动生成技术h 一1 将受限自然语言书写的故事作为输入，生成一 个3 d 动画片作为输出，整个自动生成的过程以知识库为支持。原天鹅系统 的整体结构是一个自顶向下逐步求精的过程，且涉及的动画研究领域十分广泛， 但缺少明确的层次划分和模块间的关系描述，并不容易进一步改进和完善。 按照原系统自顶向下逐步求精的思想，我们设计了新一版动画自动生成系 统，以受限自然语言为输入，通过系统模块处理后逐层细化，生成各层的动画信 息表达。图2 - 1 展示了新版动画自动生成系统的处理流程，系统分为4 个层次， 由1 3 个系统模块组成，全程有8 个知识库对动画自动生成进行支持。 2 1 2 系统动画语言 动画自动生成系统的模块是通过动画语言进行通信的，即系统将动画语言作 为模块的输入和输出。动画自动生成的全过程共使用到5 种动画语言： ( 1 ) 受限自然语言 计算机系统无法完整表达和理解自然语言，因此将语言限制在某几个特殊的 领域，如童话故事、古建筑形制描述等，分析总结出一组语法规则，称为受限自 然语言。它是自然语言的一个子集。 ( 2 ) g f 2 语言 故事理解后具有深层次含义故事信息的动画语言。以格框架树的形式表示分 析结果，定义为格框架树结构g f 2 ，包括角色、物体、环境和动作四个部分的说 明信息序列。 ( 3 ) a d l 语言 动画定性描述语言，在定性的层面上对动画进行描述和控制，属于高级动画 控制语言。用户在具备必须的领域知识后，可直接对a d l 动画描述进行设计和修 改。a d l 以定性语言描述动画情节，包括场景、角色、动作、摄像机等多方面信 息。它不仅可以作为计算机自动生成定性动画剧本的目标语言，还可以作为编程 语言供动画导演编写分场景剧本之用。 9 北京工业大学工学硕士学位论文 图2 - i 动画自动生成系统框图 ( 4 ) c a l 语言 动画定量描述语言，以定量信息的形式精确地描述和控制动画，属于低级动 画控制语言。用户很难直接提供c a l 进行动画控制，因为数据量庞大，数据信息 不宜修改，若出现错误会直接影响动画效果。c a l 的内容包括模型信息、运动曲 线、环境定位、摄像机定位等动画中的全部定量信息。 ( 5 ) m a y a 文件格式 m a y a 是一款强大的、被广泛使用的三维动画制作软件，也是新版动画自动生 成系统的底层动画制作平台。m a y a 的文件格式有两种，m a ( m a y a a s c i i ) 是以a s c i i 码表示的m a y a 文件，而m b ( m a y ab i n a r y ) 是以二进制编码表示的m a y a 文件。 由于m a 文件对程序员来说可读、可写、可修改，因此采用m a 作为动画自动生成 1 0 第2 章运动规划的研究 系统的最终动画输出文件格式。 这5 种语言中，g f 2 、a d l 、c a l 语言都采用x m ls c h e m a 口5 1 定义其语言规范， 并以x m l 啪1 文件作为动画语言的载体。x m l 是一种标记性语言，具有树形结构， 易于被应用程序加载和解析，被广泛地作为数据交换的公共语言。 2 1 3 系统构成 从层次划分上看，系统由4 个层次构成，包括故事理解层、定性层、定量层、 动画生成层，各层次间都是以动画语言作为数据交互的媒介，下面对各层的内容 进行简要地介绍。 ( 1 ) 故事理解层 故事理解层包括自然语言理解和故事理解两大模块，受限自然语言描述的动 画故事脚本是该层的输入。首先使用词法分析、语法分析、语义分析等技术进行 基于常识的自然语言理解，而后使用浅方法和深方法进行故事理解，得到包括故 事主题、角色、人物特征、故事发展线索等梗概和备用信息，最终生成格框架语 言g f 2 作为输出。这一过程需要词典、句法库的支持。 ( 2 ) 定性层 定性规划层对输入的g f 2 语言进行解析和扩展，生成具体的故事情节和角色 信息，进一步细化出场景、角色形象、角色动作和摄像机信息，并以定性的方式 进行描述。首先情节规划模块在情节库的支持下对g f 2 描述的故事大纲进行情节 展开，并通过基本人物规划模块获得故事中动画角色信息。然后定性场