网站首页  词典首页

请输入您要查询的论文：

　

标题 群体动画路径规划方法研究
范文 董哲++蔡琼++胡洁



摘 要：传统动画制作软件大多采用关键帧技术进行创作，所创作的群体动画在真实性和智能性上存在一定不足。为使群体动画产生逼真的运动路径，采用碰撞检测和碰撞避免的方法模拟群体运动，并基于微粒群算法提出一种群体动画路径自动规划方法。仿真实验结果表明，该方法能够改变群体动画运动路径，快速有效地生成群体动画。
关键词：群体动画；微粒群算法；路径规划
DOIDOI：10.11907/rjdk.151601
中图分类号：TP301
文献标识码：A 文章编号文章编号：16727800（2015）009003004
0 引言
人们经常观察到自然界的群体运动现象，比如蚂蚁搬家、一群蜜蜂来到花丛中采蜜、候鸟迁徙、羊群遭遇危险集体窜逃等。这些群体运动中的单个个体看上去行为自由、表现随机且不受周围环境干扰；但反观由单个个体组成的整体，它们却能够朝着共同的目标方向前进，而且在前进过程中维持相对的距离，个体与个体之间有很好的交互性。群体动画[1]是群体行为动画的简称，是群体智能的一种应用表现，主要用来研究和模拟群体与环境之间以及群体中个体之间的互动行为。多媒体数字处理技术和计算机图形学技术的飞速发展，以及计算机硬件成本的不断降低，推动了群体动画技术的发展和应用。
群体动画是动漫产业中的一个特殊成员，它具有大规模的群体数量、逼真的群体仿真效果，以及创作难度大且成本相对较高等特点。群体动画在游戏、娱乐、教育、军事模拟、虚拟现实等多个领域发挥着重要作用。Chenney借助于势场和能量场提出了一种称作流动条目的技术，用来代表和设计流动场，并且提供了大城市街道上人群模拟的应用实例。而WeiShao等在深入研究自主人体行为控制后，提出了一种新的模拟人群运动的控制方法，将自主行
人的感知模块分为静态感知序列图和动态感知序列图两个部分，并通过发放射线的方法感知外界环境，最后对车站人群运动进行模拟实验，验证了该方法的有效性。
群智能算法起初针对群体运动，为了能够更好地模拟群体运动，使得在群体动画中产生出更加逼真的运动路径。本文对微粒群算法进行研究和改进，并将其应用于群体动画的路径规划中。
1 基本特征和基本规则
目前，关于群体行为还没有一个严格的定义，但人们对群体行为的特点已达成共识：①简单性。单个个体的智能程度相对简单；②自组织性。通过每个个体的独立行为表现出群体行为的整体特性，群体中的单个个体运动看起来是随机的，但就整个群体而言，却是整体一致的；③鲁棒性。单个个体的行为变化对整个群体的行为不会产生特别大的影响。
由于追求的是整个群体效应，如果要对整个群体动画进行模拟实验，单一个体运动时，会受到自身群体中其它单个个体运动路线的干扰，所以制作群体动画时应该充分考虑如下规则：①群体中的单一个体应该有属于自己的运动区域，一旦剩余的单独个体进入此运动区域，那么单一个体本能地会保持固有距离，以保持单一个体的运动区域不被其他个体侵占，从而避免个体之间相互干扰带来的碰撞；②从整体性来看，整个群体中的个体与其它个体应该朝同一个方向、同一个目标运动，具有统一性；③比较大的群体而言，应当细分成几个比较小的群体，而且每一个小的群体通过自身条件判断应该与相邻的比较小的群体重新组建成一个比较大的群体。
2 群体动画中的关键问题
对群体动画的模拟需要注意以下两个关键问题：
（1）加大运动路径逼真程度。在群体动画中使个体运动轨迹既符合各自运动的独立性又能合乎群体运动规律，进而能够产生逼真的运动路径，这是检测判断群体运动真实性的标准[2]，在产生运动路径时，如何避免个体间的相互碰撞至关重要。
（2）提高群体运动速度。不能因为某一个体的速度而限制整体的运动速度，为更加强调群体的智能性，很大程度上增加了计算量，进而影响了动画创作的实时性，影响了动画的生成速度。
3 微粒群算法
微粒群算法是一种群智能优化算法，通过对环境的适应性进行评估，将群体中的一些个体移动到较好区域，强调群体效果模型。在人工生命模型开发和应用中，群体智能很多优点的实现都需要借助粒子群算法的思想。在研究过程中，如果需要将整个群体中的某些成员描述为没有重量、没有体积，而且还要描述这些成员的运动方向及运动速度等，就需要引入“粒子”概念代替这些描述。针对上述问题，使用微粒来表示某一个隐含的解，这意味着每一个微粒存在一个通过优化函数决定的适应值，并且可以自定义速度，通过计算速度差值选择偏离的路线。设置pbest为单个个体的极限值，表示微粒刚刚经过的最优化解；使用gbest为全局极限值，表示所有种群当前的最优解，通过这两个极值来更新其位置和速度，使实验的微粒可以跟踪当前的最优微粒，找到自己的区域，并且落在最优位置上。不断循环这一过程，最终达到预期目的，找到最优解。
在整个求解过程中，应该首先明确局部和全局在整个搜索过程中所占比例，提出一种带有权重的改进微粒群算法，其方程如下：
vij（t+1）=wvij（t）+c1r1j（t）[pij（t）-xij（t）]+c2r2j（t）[pgj（t）-xij（t）]（1）
xij（t+1）=xij（t）+vij（t+1）（2）
其中，j=1，2，...，n； i=1，2，.....s； t表示迭代次数，w为惯性权重，如果w的值比较小，则局部的收敛能力会比较强，收敛速度可能会慢些，一旦w值逐渐增大，则会导致全局收敛能力比较强，而且收敛的速度也会变得很快。式（1）中，定义两个加速常数C1和C2，微粒能够通过自身条件判断寻找更合适的位置；为了使群体多样化，可以设定两个随机函数a1、a2；微粒根据自身的环境适应性以及与其它邻近微粒之间的信息交流动态地调整自身速度，最终全部在最优点上降落。由于粒子的速度没有可控性，Vij设置在固定值内。
4 路径规划
本文改变算法中的步骤和参数，并将修改的参数应用到路径规划中，使其生成效果更加真实的路径，为群体动画中的角色找到一条最好的运动路径，是群体动画模拟研究中的关键。
4.1 碰撞检测
关于碰撞的例子生活中较常见，比如汽车发生正面碰撞，发动机能够吸收冲击力下沉脱出发动机舱，提升车辆应对冲击时的安全性能。针对碰撞情况，采用相应的防范措施必不可少。
碰撞检测算法的种类很多，主要有如下几类：基于空间剖分的碰撞检测法、基于特征的碰撞检测法和基于包围盒碰撞检测法[3]。
由于本文探讨的是单一粒子运动情形，不需要外部干扰，采用基于包围盒碰撞检测方法，使用圆柱体的包围盒，使得碰撞检测过程更加简便。检测过程中主要对距离进行计算。包围障碍物圆柱体的圆心位置用position[k]表示，粒子新变化后的新位置用y[k]表示，其中y为k维向量，粒子的运动过程是随机的，粒子与障碍物之间设置一个距离值为d，如式（3）所示：
d=∑ki=1（x[i]-position[i]）2（3）
受实验条件限制，本文实验系统设置为3维，所以令k值为3，针对碰撞设定一个碰撞条件：粒子与障碍物之间的距离小于粒子半径与障碍物半径之和。很明显，当粒子半径或者障碍物半径足够大时，粒子飞不过去，必然会发生碰撞。相应地，粒子相互之间的碰撞检测条件：两个粒子的半径之和大于飞跃障碍物的空间，公式如下：
d=∑ki=1（x1[i]-x2[i]）2（4）
个体在运动过程中难免会发生穿透现象，针对个体的运动步长进行调整，则不会看到穿透现象。由图1可知，根据粒子群算法得到下一个粒子将要落入的位置A′，粒子一开始在点A处，连接A到A′的距离，可以看到在点A′的位置上，A′O的距离已经大于圆的半径，也即粒子和障碍物之间的距离相对大一些，不满足碰撞条件，则不会发生碰撞；但是通过AA′的虚线连线可以明显地看到发生碰撞，那么仅仅对步长作出调整在某些阶段可以使粒子不会发生穿透。然而，在大多情况下如果步长限制过小是不科学的，甚至会发生某些异常情况。本文通过对两个夹角大小的检测来避免发生穿透。
从图1可以看出，当β>α时，粒子可以穿透到障碍物的另一侧，当β<α时，粒子不能穿透到障碍物的另一侧。实验中，为看到明显的检测变化，可以设置另外一个点A″，如果按照之前设定的检测方法和条件来判断，粒子会穿透过去，不会产生规避，如此进行下去会增大失误率，不能带来高效的探测效果。对本实验的碰撞方法性能进行分析，设算法时间复杂度为O（n2）。实验模拟中，为了达到更好的效果将粒子数目设定在55左右，当障碍物的数量小于35时，可以看到非常真实的仿真效果，基本上能够达到理想实验效果。
图1 夹角大小比较
f（x）=没有发生穿透，AA″发生穿透，AA″≥AB（5）
4.2 碰撞避免
碰撞避免的策略虽有多种，但从根本上无非是等待和转向两种，其它碰撞避免策略都是在这两种策略上进行深化或者改进得到。（1）等待法。顾名思义，就是等待另一运动个体先行通过，该方法适用于追尾碰撞和侧面碰撞。在追尾碰撞时，后一障碍物可以先停止运动，等待前一障碍物运动到出口位置或者目标点再继续运动；在侧面碰撞时，其中一个障碍物可以等待另一障碍物运动过碰撞点后再按照先前运动方向继续运动。（2） 转向法。正面碰撞时，在未来某一时点必然相撞，可以计算出一旦无碰撞，则向该方向运动；追尾碰撞时，如果前一障碍物运动速度过慢，而后面障碍物运动速度过快，使用等待法不切合实际，后一障碍物可以转向另一无碰撞方向运动；侧面碰撞时可以通过该方法转向任一无碰撞方向来避免。
为了提升动画的真实美感，借鉴上述两种碰撞避免方法。可看到图1中存在两条边界切线，试想粒子如果在边界线外绕过则不会发生碰撞，为了不让粒子发生穿透，则需要改变运动粒子的方向，可以设定为粒子连着边界线移动。
将点A定为起点， G定为终点，如果AA2与AG的夹角大于AA1与AG之间的夹角，通过在AA1上改变下一个定点位置，如果AA1与AG之间的夹角大于AA2与AG两条线之间的夹角，则应该在AA2上改变下一个定点位置。可通过缩小步长的策略来解决粒子与粒子之间的碰撞，一旦启动停止模式，所有粒子都会静止。通过对大规模粒子进行路径研究，具体示例变化如图2所示，从左至右依次为初始化效果，中间为运行多代后的效果，最右边为自由运动路线，可以看出该方法的效果。
4.3 分散和聚集行为运动
群体的分散运动在大自然中随处可见，比如当羊群受到攻击时四处逃窜。微粒群算法作为群体算法的一种，对群体分散运动路径规划的研究具有重要价值[4]，本文主要对算法中计算适应度值（app）的方法作出修改。
图2 粒子运动轨迹
app=（x-gx）2+（y-gy）2+（z-gz）2 （6）
其中，（x，y，z）表示离子的当前位置，分散时的初始起点用坐标点（gx，gy，gz）表示。根据公式可以计算出粒子的确切位置以及运行速度，粒子可以定向移到很远。分散行为的算法应用如下：
进行初始化，首先设定起点位置，并设定粒子个数、群体的迭代次数，以及粒子最初轴线的范围加速常数c1、c2等。
while（当前迭代次数未达到提前设定的最大次数）{
Step1：选择每个粒子的目标位置，计算每个粒子新位置的app值，对每个粒子进行计算，若粒子的app值优于原来的个体极限值pbest，那么设置当前app值为个体的极限值pbest；Step2：由粒子的个体极限值pbest的计算结果找出全局极值；Step3：更新微粒速度并将更新后的速度值限制在最大设定值内；Step4：采取碰撞检测方法，若发生碰撞情形，则实行相应的避免策略；Step5：重新设定原来的位置和速度；}
聚集行为是一种普遍存在的生物运动行为，聚集算法同样采用微粒群方法。由于聚集行为与分散行为是两个相对层面，因此可以使用一种对立的计算公式，设定一个警示值h，让最终的落点成为中心，以警示值h为半径，所有落入该半径内的点都可为静止状态，并且通过改变app值，使得粒子分散开来，防止集中在某一点上，同样，参数坐标值设定如下：
app=（x-gx）2+（y-gy）2+（z-gz）-rand（h）（7）
4.4 仿真实验
借助于Visual Studio 2008和ACIS等平台，同时采
用HOOPs框架模型，将路径规划产生的数据导入Maya 软件中，根据变化的场景和不同的动画效果来完成仿真实验模拟。实验结果如图3所示，图3（a）是通过读取数据生成的路径曲线图，图3（b）是动画与场景相互融合的图形，图3（c）是最终生成的动画效果。
图3 仿真效果
5 结语
本文对群体动画路径规划方法进行了研究，并对微粒群算法的系列参数作出了调整。实验结果表明，改进后的方法相对于传统的基于关键帧技术的方法而言，能够更好地提高群体动画的生成效率，进一步提高真实程度。后续研究中，将进一步研究其它群体算法优势，以找出更有效的方法运用于群体动画中。
参考文献参考文献：
[1] 涂晓媛.人工鱼计算机动画的人工生命方法[M].北京：清华大学出版社，2001：610.
[2] 魏丽.群体动画中路径自动规划方法研究[J].计算机工程与应用，2012（25）：8387.
[3] 张淑军，班晓娟，陈勇，等.基于记忆的人工鱼认知模型[J].计算机工程，2007（19）：56.
[4] 郑慧杰，刘弘，郑向伟.基于改进群搜索优化算法的群体路径规划方法[J].计算机应用，2012（8）：1013.
责任编辑（责任编辑：陈福时）
随便看

　

科学优质学术资源、百科知识分享平台，免费提供知识科普、生活经验分享、中外学术论文、各类范文、学术文献、教学资料、学术期刊、会议、报纸、杂志、工具书等各类资源检索、在线阅读和软件app下载服务。

　

Copyright © 2004-2023 puapp.net All Rights Reserved
更新时间：2025/2/11 4:24:27