群体运动模拟中的控制与计算方法研究.pdf

群体运动模拟中的控制与计算方法研究.pdf

《群体运动模拟中的控制与计算方法研究.pdf》由会员分享，可在线阅读，更多相关《群体运动模拟中的控制与计算方法研究.pdf（75页珍藏版）》请在冰点文库上搜索。

分类号TP3密级UDC编号中国科学院研究生院中国科学院研究生院硕士学位论文硕士学位论文群体运动模拟中的控制与计算方法研究李李健健指导教师王兆其研究员指导教师王兆其研究员中国科学院计算技术研究所中国科学院计算技术研究所申请学位级别工学硕士申请学位级别工学硕士学科专业名称计算机应用技术学科专业名称计算机应用技术论文提交日期2010年4月论文提交日期2010年4月论文答辩日期2010年5月论文答辩日期2010年5月培养单位中国科学院计算技术研究所培养单位中国科学院计算技术研究所学位授予单位中国科学院研究生院学位授予单位中国科学院研究生院答辩委员会主席答辩委员会主席声声明明我声明本论文是我本人在导师指导下进行的研究工作及取得的研究成果。

尽我所知，除了文中特别加以标注和致谢的地方外，本论文中不包含其他人已经发表或撰写过的研究成果。

与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。

作者签名：

日期：

论文版权使用授权书论文版权使用授权书本人授权中国科学院计算技术研究所可以保留并向国家有关部门或机构送交本论文的复印件和电子文档，允许本论文被查阅和借阅，可以将本论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编本论文。

（保密论文在解密后适用本授权书。

）作者签名：

导师签名：

日期：

群体运动模拟中的控制与计算方法研究：

摘要I摘摘要要自从1987年Biod模型出现至今，在群体模拟技术方面涌现了丰富的研究成果，在应用领域也有很多闪光点，但是从群体运动模拟控制的灵活性和计算的高效性两方面来说，还不足以满足人们的期望和要求。

首先，现有的群体运动控制研究主要集中在群体运动的逼真性上，而针对影视特效和游戏动画制作领域，尚缺少直观、灵活、高效的高层编辑和控制技术，能够使得群体运动表现出特定的效果，从而恰到好处的表达设计者的创作意图。

其次，现有群体运动模拟方法大多计算复杂，较难实现大规模群体的模拟；在现有文献所涉及的模拟实例当中，模拟群体的最大规模为10万；而在实际生活中，规模几十万甚至百万的群体运动场景不断出现，如何解决其“可模拟”问题，并进一步提高模拟的效率，是本领域研究人员所关注的问题。

本文正是基于此研究背景，展开论文研究工作。

取得的主要研究成果如下：

1、提出了基于关键队形约束的群体运动控制方法、提出了基于关键队形约束的群体运动控制方法针对影视制作中对大规模群体运动控制的需求，提出一种基于关键队形约束的群体运动编辑与控制方法。

设计人员只需要输入群体关键队形轮廓与点阵采样参数，即可合成出流畅平滑的群体动画。

在整个过程只需要输入关键队形的轮廓信息，确定群体队形采样参数，后续工作由系统自动完成，手工交互量小，控制方式简单；提供了多模态的输入和输出方式，其中在输入方式上包括手动输入和图片输入，在输出方式上包括点阵数据文件、二维点阵排布、三维效果预览三种输出样式，使得编辑方式更为灵活。

制定了队形渐变的群体运动规则，在此基础上，提出了一种点阵配对算法，使得合成的群体动画更加平滑、流畅。

提出了一种点阵对应关系优劣评价方法，通过与随机配对、一一指定配对、贪心配对等方法的比较，对本文提出的方法进行了量化评价：

通过对比，本文方法实现的配对代价指标MapCost优于其他方法。

2、提出了面向连续群体模型的群体运动并行化模拟算法、提出了面向连续群体模型的群体运动并行化模拟算法随着群体规模的不断增大，在传统单核CPU计算平台上，计算速度逐渐成为群体运动模拟的主要瓶颈之一。

高性能并行计算平台的出现与普及，为大规模群体（5万）运动的快速模拟计算，以及超大规模群体（30万）运动的“可模拟”，提供了新的计算平台和实现手段。

群体运动模拟中的控制与计算方法研究：

摘要II已有的群体运动并行模拟相关工作都是针对基于agent模型来进行的。

与基于agent的模型相较而言，基于全局的群体运动模型的优势在于能够进行全局调控，能自然的处理全局路径规划和局部碰撞避免之间的矛盾，宏观的群体流向逼真自然，比较适用于大场景（5万）、大规模群体的仿真模拟计算。

但目前，针对基于全局模型的群体运动模拟计算的相关技术还比较少，尚缺乏成熟的算法与技术。

本文在对连续群体模型（全局模型的一种）分析的基础上，研究并提出了面向该模型的并行化模拟算法；该算法适用于具有区域分块特征的大场景，解决了大场景下大规模群体的运动模拟问题。

该算法具有以下优点：

1）本算法具有较好的加速效果，8个计算节点加速比达到7.21，16个计算节点加速比达到12.32；2）本算法有效地提升了参与模拟的群体规模，我们在67.24万平米的场景中模拟的群体规模可以高达100万。

3）该算法有效地减轻了管理结点的任务负载，具有很强的扩展性计算节点最多可扩展至300个。

在上述工作基础上，实现了基于连续群体模型的群体运动并行模拟原型系统，对超大规模人流（30-100万）疏散运动进行了成功模拟。

关键词关键词：

群体模拟，关键队形，群体运动控制，并行计算ResearchonControlandComputationMethodsinCrowdSimulation:

AbstractIIIResearchonControlandComputationMethodsinCrowdSimulationLiJian（ComputerApplicationTechnology）DirectedByWangZhaoqiSincethepresentofBiodmodelin1987,greatachievementsincrowdsimulationarebeingreached,andthistechnologygetsgoodperformanceinapplicationfield.Butitisstillinsufficienttomeetourexpectationsandrequirementsintheflexibilityofcontrolandtheefficiencyofcomputation.Ontheonehand,theexistingcrowdsimulationresearchesaremostfocusedontherealisticappearance.Thereisstillalackofintuitive,flexible,andefficienthigh-leveleditingandcontrolmethodtomakecrowdsimulationshowaspecificeffectinmovieproducing,andthustoexpressdesignerscreativity.Ontheotherhand,theexistingmethodsarecomplexincomputation.Soitisdifficulttoachievelarge-scalecrowdsimulation;amongtheexamplescitedinthepapers,thelargestcrowdconsistsof100,000agents.However,inreallife,thecrowdconsistinghundredsofthousands,evenmillionsagentsiscoming.Facedwithsuchamassivecrowdinavastenvironment,researcherspaygrowingattentiontothisissue,andmakeeffortstosolvetheBeAbletoSimulateproblem,andfurtherimprovetheefficiency.Besidesit,thisdissertationisresearchedcomprehensivelyandthoroughly.Themaincontributionsofthisdissertationarelistedasfollows:

1.Anovelkey-shapes-constrainedcrowdanimationmethodFocusonthedemandsofcontrollingvirtualcrowdinmovieproducing,anovelshape-constrainedcrowdanimationsystemisproposed.Crowdanimationcanbeachievedsimplybygivingthekeyshapesofcrowdandthesamplingparameters.1.Whatshouldbedonejustisinputtingthekeyshapesandthesamplingparameters.Thefollow-upworkisdoneautomatically.Itsinteractionisprettysimple.2.Aflexibleeditingmodeisintroducedinthisdissertation.Thismodecanofferamulti-modalIOmethod.TheinputtypeincludesManually-inputandImage-forminput,andtheoutputtypeincludesData-filesType,2D-displayedtypeand3D-displayedtype.3.Theruleofcrowdmotionduringkey-shapesisestablished.Then,thecorrespondencebetweentheirsamplepointsiscomputedbyournewmatchingalgorithm,whichmakestheanimationmorevisuallyplausible.4.Aquantitativeevaluationmethodforcorrespondenceispresented.Comparativetestsshowthatourmethodisbetterthanothers,suchasRandom-matching,Set-One-By-One-matchingandGreedy-matching,incorrespondencecostMapCost.2.AparallelsimulationalgorithmbasedoncontinuumcrowdmodelWiththeincreaseofcrowdscale,thecomputationspeedhasbecomethebottleneckforcrowdsimulationonthecomputingplatformswithsingle-coreCPU.Theappearanceandthepopularityoftheparallelcomputingsystemprovideanewandefficientmeanstofurtherimprovetheefficiencyofthelarge-scalecrowd（50,000agents）simulation,andtosolvetheBeAbletoSimulateproblemofthesuper-large-scalecrowd（300,000agents）simulation.Previousparallelsimulationstudieshavebeenagent-based,meaningthatmotioniscomputedseparatelyforeachindividual.Bycontrast,globally-basedmodelshavegreaterResearchonControlandComputationMethodsinCrowdSimulation:

AbstractVIcompetitiveadvantageinglobalcontrol,thustheyaregoodatreal-timeandhighefficiencydemand.Globally-basedmodelscanresolvethecontradictionbetweenglobalpathplanningandlocalcollisionavoidancenaturally.Theyaresuitableformassivecrowdanimationinavastenvironment.However,globally-control-basedparallelsimulationhasntbeenfullydevelopedyetbynow.Anditstilllackstheeffectivemethodsandalgorithms.Onthebasisoftheanalysisofcontinuumcrowdmodel（akindofglobally-basedmodels）,aparallelsimulationalgorithmbasedonthismodelisproposed.Thealgorithmisavailableformassive-crowdsimulationinavastenvironmentwithblock-partitioncharacteristics.Thealgorithmhasthefollowingfeatures:

1）ithasagoodparallelspeedup;thespeedupreaches7.21whenthesystemincludes8computingnodes,anditreaches11.32when16computingnodes.2）itcanenlargethescaleofcrowdparticipatinginsimulation.Inourexperiment,thescaleofcrowdisupto1millioninthe67,600-square-metersregion.3）Goodscalabilityoftheproposedalgorithmcanbeobtainedbyreducingthetaskloadofthemanagementnode.Thesystemcanbeextendedto300computingnodesinourexperiment.Onthebasisoftheabovework,aprototypesystemisimplemented,andsuccessestosimulatethelargescalecrowd（300,000-1,000,000agents）.Keywords:

crowdsimulation,thekeyshape,controlofcrowdmotion,parallelcomputation目录V目录目录第一章绪论.11.1研究背景.21.2研究目的及意义.41.3研究内容及主要贡献.51.4论文的组织.7第二章相关工作.92.1群体运动模型.92.1.1基于个体规则的模型.102.1.2基于物理力学的模型.102.1.3元胞自动机模型.112.1.4流体模型.122.1.5势能场模型.132.2基于约束的群体运动控制.142.2.1物体渐变.142.2.2基于外在约束的群体动画.152.3群体运动模拟中的并行计算技术.172.3.1面向鸟群模型的群体运动并行计算.172.3.2面向社会力模型的群体运动并行计算.18第三章基于关键队形约束的群体运动编辑与控制.213.1方法概述.213.2队形编辑与采样.223.3运动脚本合成.243.3.1点集配对.243.3.2后期处理.303.4对应关系评价方法.303.5实验结果与分析.313.5.1队形编辑与采样.31目录VI3.5.2配对效果对比实验.323.5.3合成动画.333.6本章小结.34第四章面向连续群体模型的群体运动并行计算方法.374.1连续群体模型.374.2并行模拟算法设计.394.2.1场景组织.404.2.2场景划分.414.2.3任务分配.424.2.4结构模式.434.2.5通信模式.464.2.6并行计算算法.474.3实验结果与分析.484.4小结.50第五章结束语.536.1全文工作总结.536.2下一步研究方向.54参考文献.55致谢.61作者简历.63图目录VII图目录图目录图1.1现实世界中的群体运动现象.1图1.2群体模拟技术的应用.2图1.3群体运动模拟在影视动漫、电子游戏中的应用.3图1.4群体运动模拟在公共安全领域的应用.4图1.5主要研究内容.6图2.1群体运动模型分类.9图2.2基于个体规则的方法Rey99.10图2.3基于物理学的模型.11图2.4使用元胞自动机模型模拟人群疏散过程YKN07.12图2.5流块模型模拟结果Che04.13图2.6连续群体模型模拟效果.13图2.7形状约束的三维群体动画XJ08.16图2.8GPU并行模拟ECS*04.17图3.1编辑与控制研究内容.21图3.2群组动画生成流程图.22图3.3队形编辑系统流程图.23图3.4手动输入基本阵型.23图3.5图片输入效果.24图3.6初始点阵与目标点阵对应关系的建立.25图3.7贪心筛选流程图.27图3.8贪心筛选算法.27图3.9交叉修正前后对比.28图3.10交叉修正算法.28图3.11队形变换出现的混乱效果.29图3.12相对位置修正前后对比.29图3.13多模态输出.31图3.14图片输出举例.32图3.15群体运动效果图1.34图3.16群体运动效果图2.34图4.1连续群体模型示意图.38图4.2连续群体模型模拟效果图.39图4.3串行模拟算法.39图4.4环境语义结构模型.40图目录VIII图4.5由环境语义生成离散网格.40图4.6块与块的连接JXM*09A.41图4.7场景分割算法举例.41图4.8任务分配示意图.42图4.9过渡块上agent分配方法.43图4.10Manager/Worker结构模式.44图4.11传统责任分配方式.44图4.12本章采用的责任分配方法.45图4.13系统通信策略.47图4.14并行模拟算法（计算节点）.47图4.15并行模拟算法（管理节点）.48图4.161万agent运动模拟三维效果图.48图4.17计算节点数与单帧计算时间曲线图.49图4.18加速比统计（5万人）.49图4.19群体规模与单帧计算时间曲线图.50表目录IX表目录表目录表3-1初始点阵阵列与目标点阵阵列的概率行列式.25表3-2对比试验结果统计.32表3-3对比试验结果.33表4-1本章方法与QuinnQMH03方法的对比.46图目录X第一章绪论1第一章第一章绪论绪论群体运动现象在现实生活中随处可见，例如体育场馆中的大量观众、购物场所内的密集人流（见图1.1（a）；动物世界中的群体运动现象也比比皆是，例如迁徙的鸟群、捕食的鱼群等（见图1.1（b）。

在计算机虚拟世界中对这些群体运动现象进行模拟，具有较强的理论意义和实用价值。

比如：

在公共安全领域，通过对紧急情况下人群运动的模拟与分析，可以对建筑物结构设计、公共场所应急预案的制定起到很好的指导作用；在游戏动画、影视特效领域，应用群体运动模拟技术可以生成的恢宏、生动的群组场面，极大增强作品的艺术表现力与视觉冲击力。

（a）（b）图1.1现实世界中的群体运动现象群体运动模拟主要关注三方面的问题：

模拟结果的逼真性、运动控制的灵活性和模拟计算的高效性。

模拟结果的逼真程度，与模拟所采用的群体运动模型有着很大的关系。

目前，围绕这个问题，各国研究人员在群体运动模型上进行了深入研究，已经取得了丰硕的成果。

在影视特效、游戏动画领域的应用中，群体的运动控制极为重要。

在这类应用中，为表达创作者的创作意图，往往需要对群体的运动进行高层的控制和编辑。

例如，在古代军事题材的影视作品中经常表现的大规模军阵变换场景的制作。

但目前尚缺乏有效的群体运动控制方式，能够通过简单的交互，有效的表达创作者的意图，并控制群体按照此意图进行运动。

模拟计算的高效性，则随着所模拟的群体规模的逐渐增大，而备受关注。

特别是在突发事件仿真、工程设计评估等公共安全领域，随着我国社会、经济发展进入关键阶段，主办和承办的各种大型活动越来越多，解决大规模（10万）群体模拟的快速计算问题已经成了当务之急。

第一章绪论2本文受北京市文化创意产业重点项目“数字化影视动漫特技拍摄与制作系统研发及原创作品应用”和科技部“世博科技”专项课题“2010年上海世博会人流疏导应急预案模拟关键技术研究与服务应用”等项目资助，以群体运动为研究对象，研究群体运动模拟中的控制和计算方法；提出了基于关键队形约束的群体运动编辑和控制方法、针对全局控制模型的并行化模拟计算方法；较好地解决了群体运动的灵活控制问题以及大规模群体运动的“可模拟”及“快速模拟”问题，为群体运动模拟在各个领域中的应用打下了基础。

1.1研究背景研究背景近年来，群体运动模拟技术一直是计算机图形学和虚拟现实领域的研究热点之一。

随着虚拟现实技术的发展及计算机硬件运算能力的提高，群体运动模拟技术的应用领域也越来越广泛。

图1.2群体模拟技术的应用巨大的应用前景和重要的学术价值吸引了来自业界和学术界的不同研究人员在群体运动模拟问题上展开深入研究，并取得了丰富的研究成果。

其中国外著名的研究机构包括：

华盛顿大学，宾夕法尼亚大学、纽约大学、首尔国立大学、洛桑联邦工业大学、特拉维夫大学等，国内主要是中科院计算所、浙江大学等。

群体运动模拟，一方面可以广泛的应用于数字娱乐领域，通过合成恢宏震撼的群组运动场景，极大地增强作品的表现力；另一方面，群体运动模拟还可以应用于公共安全领域，通过日常人流或紧急情况下人群流向的模拟与