本文選題：群體動(dòng)畫　切入點(diǎn)：搜索優(yōu)化算法　出處：《山東師范大學(xué)》2013年碩士論文　論文類型：學(xué)位論文

【摘要】：計(jì)算機(jī)圖形學(xué)是在研究物理規(guī)律、實(shí)證方法、認(rèn)知原則的基礎(chǔ)上，利用不同的數(shù)學(xué)算法對二維或三維圖形數(shù)據(jù)的處理，生成科學(xué)數(shù)據(jù)的可視化表現(xiàn)。它專注于可視化圖形內(nèi)容以及數(shù)字合成技術(shù)功能，是計(jì)算機(jī)應(yīng)用程序和計(jì)算機(jī)科學(xué)研究領(lǐng)域的分支。計(jì)算機(jī)圖形學(xué)經(jīng)過近40年的發(fā)展，，已進(jìn)入一個(gè)成熟的發(fā)展階段，在各種各樣的在計(jì)算機(jī)輔助設(shè)計(jì)和加工的電影和電視動(dòng)畫，軍事模擬，醫(yī)學(xué)圖像處理，地質(zhì)，氣象，財(cái)務(wù)和電磁場可視化范圍應(yīng)用。計(jì)算機(jī)圖形學(xué)已經(jīng)成功實(shí)施在這些領(lǐng)域，尤其是在快速發(fā)展的動(dòng)漫產(chǎn)業(yè)。目前，大多數(shù)動(dòng)畫制作采用傳統(tǒng)的關(guān)鍵幀技術(shù)，雖然動(dòng)畫制作師創(chuàng)作了大量的優(yōu)秀作品，但是隨著應(yīng)用領(lǐng)域的拓展、規(guī)模的擴(kuò)大、人們需求的提高，基于關(guān)鍵幀技術(shù)的不足日漸明顯，傳統(tǒng)動(dòng)畫制作技術(shù)中動(dòng)畫角色的每個(gè)動(dòng)作和移動(dòng)細(xì)節(jié)都由動(dòng)畫制作師控制，隨著動(dòng)畫時(shí)間的加長、角色數(shù)量的增多、場景復(fù)雜度的提高，動(dòng)畫師的勞動(dòng)量顯著增加，同時(shí)，由于在群體運(yùn)動(dòng)中的個(gè)體存在相互影響，群體運(yùn)動(dòng)具有個(gè)體特征和群體特征，模擬群體動(dòng)畫性能和真實(shí)感的提高，對動(dòng)畫制作師來說是非常具有挑戰(zhàn)性的。 群搜索優(yōu)化算法是群體智能算法中一個(gè)新興優(yōu)化算法。模擬算法來自對群居動(dòng)物如鳥類、魚類、獅子等覓食行為的模擬。在發(fā)現(xiàn)者-加入者模型基礎(chǔ)上，該算法還利用游蕩者策略，避免陷入局部極值。同時(shí)，該算法利用動(dòng)物視覺搜索機(jī)制，擴(kuò)大搜索的范圍。該算法實(shí)現(xiàn)簡單，在處理高維問題中具有較好的全局搜索能力。但是它存在大部分尋優(yōu)算法共同的問題：容易陷入局部最優(yōu)點(diǎn)，影響算法的收斂性，降低了算法的優(yōu)化性能。 本文針對傳統(tǒng)群體動(dòng)畫制作中存在的局限問題，對群搜索優(yōu)化算法進(jìn)行相應(yīng)算法改進(jìn)，使其在處理高維函數(shù)問題中表現(xiàn)出較好的全局搜索能力，同時(shí)在處理低維問題也能表現(xiàn)出優(yōu)越的性能，并將其應(yīng)用到群體動(dòng)畫中，增強(qiáng)算法的應(yīng)用性與動(dòng)畫的真實(shí)性。本文的主要?jiǎng)?chuàng)新工作及其相關(guān)應(yīng)用有以下4個(gè)方面： 1.提出一種改進(jìn)的群搜索優(yōu)化算法 通過在收斂策略、群體智能性上對群搜索優(yōu)化算法進(jìn)行改進(jìn)，在群體最優(yōu)陷入停滯時(shí)引入差分進(jìn)化算法，并根據(jù)算法自身特點(diǎn)，將差分計(jì)劃算法進(jìn)行變異，使其擺脫局部極值點(diǎn)的束縛，同時(shí)引入模擬退火機(jī)制，提高全局搜索能力。 2.將改進(jìn)的群搜索優(yōu)化算法應(yīng)用人群三維動(dòng)畫中 以VS2003+ACIS為平臺(tái)，在WindowsXP操作系統(tǒng)下構(gòu)建仿真系統(tǒng)，利用改進(jìn)的群搜索優(yōu)化算法模擬群體動(dòng)畫中的人群對穿現(xiàn)象。碰撞避免貫穿于整個(gè)群體動(dòng)畫過程中，群體智能行在群體個(gè)體與障礙物之間以及群體個(gè)體成員之間，都表現(xiàn)出較好性能。同時(shí)，將該仿真實(shí)驗(yàn)運(yùn)用到Maya三維動(dòng)畫制作中，該算法在應(yīng)用中產(chǎn)生較好的動(dòng)畫效果。 3.提出一種基于步長搜索的改進(jìn)群搜索算法的群體路徑規(guī)劃方法 該方法首先針對群搜索優(yōu)化算法的局限性進(jìn)行改進(jìn)，引入模擬退火算法，放棄視覺搜索模式而采用步長搜索，使群搜索算法高效簡單、易于實(shí)現(xiàn)。同時(shí)，為避免路徑長、環(huán)境復(fù)雜，單純使用算法規(guī)劃起點(diǎn)到目標(biāo)點(diǎn)之間的路徑造成計(jì)算量大、耗時(shí)長等問題，引入多線程和路徑隨機(jī)拼接技術(shù)進(jìn)行分層次路徑規(guī)劃。在外層全局路徑規(guī)劃中利用A*算法進(jìn)行規(guī)劃實(shí)施，在內(nèi)層路徑規(guī)劃中利用改進(jìn)的群搜索優(yōu)化算法，通過多線程并行運(yùn)行，實(shí)現(xiàn)在柵格區(qū)域間的內(nèi)層并行路徑規(guī)劃。針對傳統(tǒng)路徑拼接技術(shù)容易出現(xiàn)“拉長線”、“聚集”和“跳躍”現(xiàn)象，本文采用隨機(jī)路徑拼接技術(shù)，將柵格區(qū)域內(nèi)的路徑進(jìn)行有效拼接，進(jìn)而規(guī)劃出整體路徑。 4.將基于改進(jìn)群搜索算法的群體路徑規(guī)劃方法應(yīng)用到化工廠逃生規(guī)劃中 疏散是人們在遇到危險(xiǎn)時(shí)，迅速逃離現(xiàn)場的行為。將基于改進(jìn)群搜索算法的群體路徑規(guī)劃方法應(yīng)用到化工廠逃生中，不僅能夠較真實(shí)的模擬化工廠發(fā)生危險(xiǎn)時(shí)人群逃生的路徑，而且在計(jì)算速度、模擬效果上都有較好的應(yīng)用。
[Abstract]:Computer graphics is in the study of physical laws, empirical methods, based on cognitive principles, processing of 2D or 3D graphics data using different mathematical algorithms, visualization of scientific data generation. It focuses on the visual content and function of digital synthesis technology, is a branch of the field of computer applications and computer science computer. Graphics after nearly 40 years of development, has entered a mature stage of development, in a variety of computer aided design and processing in the film and television animation, military simulation, medical image processing, geological, meteorological, financial and electromagnetic field visualization application. Computer graphics has been successfully applied in these areas, especially in the the rapid development of the animation industry. At present, most of the traditional animation key frame technology, although the animators created a lot of excellent The show works, but with the application development, the expansion of the scale, people demand increase, lack of key frame based technology becomes more and more apparent, all motion details of traditional animation animation technology in the role by the animators, with longer animation time, increased number of characters, increase the complexity of the scene the amount of labor, the animators increased significantly, at the same time, due to the mass movement of individuals have mutual influence, population movement has the individual characteristics and group characteristics, simulation and realistic performance of group animation to improve, animators is very challenging.
Group search optimization algorithm is a new optimization algorithm of swarm intelligence algorithm. Simulation algorithm from the fish to the social animal, such as birds, lions and other simulation foraging behavior. In the discovery - join based on the model, the algorithm also uses the rogue strategy to avoid falling into local extreme value. At the same time, the algorithm uses the animal visual search the mechanism, expand the scope of the search. The algorithm is simple and has better overall in dealing with high dimensional problems in search ability. But it is common problem of most of the optimization algorithm is easy to fall into local minima, affect the convergence of the algorithm, reduces the optimization performance of the algorithm.
Aiming at the limitations of the traditional group animation, the corresponding algorithm of improved group search optimization algorithm in the high-dimensional function problem showed better global search ability, and exhibits superior performance in low dimensional problems, and its application to the group animation, augmented reality of the application of the algorithm animation. The main innovation of this paper and its application has the following 4 aspects:
1. an improved group search optimization algorithm is proposed
The convergence strategy, group intelligence on the group search optimization algorithm, the optimal population differential evolution algorithm is introduced into stagnation, and according to the algorithm's characteristics, differential planning algorithm variation, to get rid of the shackles of local extremum, and introduces the simulated annealing mechanism to improve the global search ability.
2. application of improved group search optimization algorithm in 3D animation of crowd
To VS2003+ACIS as a platform to build a simulation system under the WindowsXP operating system, using swarm optimization algorithm simulating in groupanimation people to wear phenomenon. The improved collision avoidance throughout the animation of the whole group in the process of swarm intelligence between individuals and groups of obstacles and the group of individual members, show good performance. At the same time, the simulation experiment applied to the Maya animation, this algorithm has better animation application.
3. a method of group path planning based on improved group search algorithm based on step length search
Firstly, considering the limitation of the group search optimization algorithm was improved by simulated annealing algorithm, give up visual search mode by step search, the group search algorithm is efficient and simple, easy to implement. At the same time, in order to avoid the long path, the environment is complex, simply use the algorithm starting point to the path between the target point caused by the large amount of calculation. Time is too long, hierarchical path planning to introduce random splicing technology of multi thread and path planning. The implementation of A* algorithm using in the outer layer of the global path planning, using the improved group search optimization algorithm in the inner path planning, running parallel through multi thread, realize the inner regional grid in parallel for the traditional path planning. Path splicing technology of "long line", "gathering" and "jump" phenomenon, this paper uses a random path splicing technology, the path in the region into the grid The line can be stitching effectively, and then the whole path is planned.
4. the method of group path planning based on improved group search algorithm is applied to the escape planning of chemical plant
Is the evacuation of people in the face of danger, quickly fled the scene. The behavior will be based on improved group escape path planning method of group search algorithm is applied to the chemical plant, chemical plant can not only route simulation real danger crowd escape, but also in the speed of calculation, simulation results have good application.

【學(xué)位授予單位】：山東師范大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2013
【分類號】：TP391.41;TP18

【參考文獻(xiàn)】

相關(guān)期刊論文 前10條

1 楊毅;劉亞辰;劉明陽;付夢印;;一種基于凸殼的智能服務(wù)機(jī)器人路徑規(guī)劃算法[J];北京理工大學(xué)學(xué)報(bào);2011年01期

2 胡中華;趙敏;;基于人工蜂群算法的機(jī)器人路徑規(guī)劃[J];電焊機(jī);2009年04期

3 楊維,李歧強(qiáng);粒子群優(yōu)化算法綜述[J];中國工程科學(xué);2004年05期

4 劉鋒;覃廣;李麗娟;;快速群搜索優(yōu)化算法及其應(yīng)用研究[J];工程力學(xué);2010年07期

5 劉鋒;覃廣;李麗娟;;快速被動(dòng)群搜索優(yōu)化算法及其在空間結(jié)構(gòu)中的應(yīng)用[J];工程設(shè)計(jì)學(xué)報(bào);2010年06期

6 任鳳鳴;王春;李麗娟;;多目標(biāo)群搜索優(yōu)化算法及其在結(jié)構(gòu)設(shè)計(jì)中的應(yīng)用[J];廣西大學(xué)學(xué)報(bào)(自然科學(xué)版);2010年02期

7 李曉娜;孫立博;秦文虎;;虛擬人群仿真的路徑規(guī)劃新算法[J];東南大學(xué)學(xué)報(bào)(自然科學(xué)版);2011年02期

8 張雯栶;滕少華;李麗娟;;改進(jìn)的群搜索優(yōu)化算法[J];計(jì)算機(jī)工程與應(yīng)用;2009年04期

9 鄭向偉;劉弘;;多目標(biāo)進(jìn)化算法研究進(jìn)展[J];計(jì)算機(jī)科學(xué);2007年07期

10 鄭小霞;錢鋒;;一種改進(jìn)的微粒群優(yōu)化算法[J];計(jì)算機(jī)工程;2006年15期

相關(guān)博士學(xué)位論文 前1條

1 王鑫;數(shù)據(jù)驅(qū)動(dòng)的人群動(dòng)畫仿真技術(shù)研究[D];浙江大學(xué);2009年

相關(guān)碩士學(xué)位論文 前4條

1 黃鶴;部分環(huán)境信息已知的智能機(jī)器人路徑規(guī)劃方法研究[D];南京理工大學(xué);2005年

2 黃晟盛;群組動(dòng)畫運(yùn)動(dòng)控制的研究及應(yīng)用[D];浙江大學(xué);2006年

3 吳磊;使用骨骼蒙皮動(dòng)畫技術(shù)制作人物動(dòng)畫[D];浙江大學(xué);2007年

4 王妍;動(dòng)畫自動(dòng)生成系統(tǒng)中運(yùn)動(dòng)規(guī)劃及其路徑規(guī)劃的研究與實(shí)現(xiàn)[D];北京工業(yè)大學(xué);2009年

本文編號：1600498