随着人工智能、计算机图形学和软硬件技术的高速发展,计算机动画已经广泛应用于工程、科研、文娱等众多领域。中科院陆汝钤院士于90年代提出的全过程计算机辅助自动生成动画技术将人工智能技术和基于知识的方法引入动画生成的全过程,其目标是有一个适当的故事,以受限自然语言的形式输入计算机,基于情节库、场景库、动作库等知识库,将动画制作的全过程依靠计算机自动完成,最终生成3D动画。应用这一技术相继研发了第一版《天鹅》系统和基于先进的三维动画制作软、硬件的新版动画自动生成系统。运动规划是动画自动生成系统中的核心模块之一,它首先在定性层生成定性的动作描述序列,然后将定性描述通过定量层的动作计算转化为动画的定量描述,并在转换过程中处理一系列子问题。运动规划是底层动画实现的关键,所有的运动数据信息都要通过该模块生成。路径规划是运动规划定量层的一个重要的子问题,它的任务是在已知的动画三维空间中寻找一条由起始点到目标点的无碰撞路径。通过分类可以将动画中的路径规划问题细分,并使用智能的方法来得到合理的、真实的角色路径。本文详细描述了动画自动生成系统中的运动规划模块及其路径规划子模块的设计与实现。在运动规划部分,本文着重论述了系统中间语言的设计,其中动作定性描述语言以《天鹅》系统的定性规范语言为基础,通过综合分析多类动作,提取共同的关键属性和参数作为定性描述属性。动作定量描述语言肩负着向动画文件转换的任务,采用以角色为单位的关键帧序列进行结构化描述。对于动作库,本文通过三维动作捕捉技术(Motion Capture)对人体运动数据进行采集,生成动作的BVH格式文件后再转化到动作库中。运动规划的定量层——动作计算模块负责将动作的定性描述转化为定量描述,本文设计并实现了这一转化的完整流程。在动作计算中,动作库中的运动数据是利用动作捕捉系统采集生成的BVH格式数据,而最终动画是在Maya软件中展示的,但Maya并不支持BVH旋转数据的解读,而是使用Euler角来表达旋转信息,这就产生了一个运动数据跨平台转换问题。本文提出了一种算法来实现BVH运动数据在Maya中的转换,首先针对人体骨架的单个关节,利用矩阵等价的方法建立起BVH旋转与Euler旋转的关系,以求解对应的Euler角,然后将这一方法应用于整个骨架来实现动作的转换。在三维路径规划部分,本文设计了地形建模算法和障碍物建模算法分别对动画场景的三维空间进行划分,并以八叉树结构进行保存,由于地形和障碍物模型的物理表达形式差别很大,建模后可对两者进行统一的表达。八叉树不易表达场景的相邻结点,本文设计了邻域查找算法以进行八叉树中相邻结点的查询。在路径搜索时,首先设计一个场景图邻接表结构,这是一个动态结构,可表示八叉树结点的相邻关系,本文采用IDA*算法进行路径搜索,随着搜索范围的增加,邻接表结构随之扩大。针对不同的动画情节,本文将路径规划分为飞行类路径、爬行类路径和群体类路径三类问题,每类问题都对IDA*算法进行一定的调整,来生成与情节相符的路径。