Research On Collision Detection And Avoid Algorithm Of Crowd Animations

Animation industry is an emerging industry ,it is seen as a creative industry, andis supported by more and more countries and city,particularly the group animation.For example,《Transformers》,《Kung Fu Panda》and other large, classical groupanimation are more and more attended by people. However, except the complex groupanimation scene design and eye-catching role modeling, collision avoidance betweenroles also becomes one of the core technology of production of group animation. Andnow because of the rapid development of computer technology and the favorite ofpeople for group animation, the collision detection problems become the focus ofresearch again. Now the problem of collision detection has become the researchfocus of the computer graphics, animation, groups of robot path planning, virtualsimulation and other fields.More and more people pay attention the mass movement of animals in nature,many people want to use computer technology to simulate this mass movement. Thefirst technique is to use key frames to generate the animation,it the improvement tothe hand-drawn animation techniques,but using this method not only consumes theanimators a lot of time to produce the animation and the animation is also simplemachinery、lack of independent. With the rapid development of computer technology,group animation techniques make the computer animation be a higher level. Thecombination of swarm intelligence algorithm and group animation technology onceagain improve the computer animation technology. Now more popular swarmintelligence algorithm has particle swarm optimization、ant colony optimization,、swarm algorithm. Particle Swarm Optimization (PSO algorithm) is the most widelyused.PSO algorithm is an optimization algorithm to simulate birds of prey behavior.PSO algorithm makes a metaphor of the optimization problem to a feeding birds inthe search space,, and called the "particles". It valuates the particles using the fitnessvalues.In addition to the properties of the speed , particles has the propertiesof size.Each particle can be able to know the fitness value of the previous step in addition to the direction of the velocity and the current fitness,and compare the two fitness,if thecurrent fitness is better than the fitness of the previous step,the particle gives up thefitness of the previous step and saves the current fitness value.Otherwise, it willrecord the fitness of the previous step, the optimal value of each "particle" saved ateach step is called "individual extremum pBest". There is also a leader for the entireflock, and this leader has the best fitness value of all "particles" in the currentgeneration, other "particles" will be close to the optimal solution in its leadership stepby step and called the "global the extremum gBest "saved by the current generation ofthe entire flock. "Particles"will update their own speed size, orientation, and otherattributes by tracking the two "extreme value".Group animation is different from the virtual scene, it has not very highrequirements for equipment and accuracy, which requires a simple and efficientalgorithm of collision detection between groups. Generally simple collision detectionalgorithm has the phenomenon that roles penetrates roles and obstacles.In this paper, we put forward a new collision detection algorithm - based onRMPSO collision detection algorithm for the above problems and the problems ofslow speed, the algorithm is divided into two stages: rude stage and the precise stage.The standard PSO algorithm has the shortcomings of ease to fall into early maturity,and poor diversity, this paper presents an improved RMPSO algorithm. The algorithmRMPSO increase the diversity of the population、improve the accuracy of thealgorithm and make PSO algorithm smarter. In order to avoid the roles penetrate theobstacles, this paper will divide obstacles into two major categories of static obstacles(scene) and dynamic obstacles (groups, roles). For static obstacles, the paper will takefollowing strategies: the role is as a particle, over the particles do two tangents ofobstacles, the particles move along the tangent. For more realistic, the particles shouldselecte the tangent near side their target location to move away, this article will take acertain algorithm so that it can along the near side of the target point to move. Fordynamic obstacles: to reduce the step methods, such as the two objects will collide,and this paper will suspend the movement for collision avoidance. This method notonly embodies the role of comity between the social form, and solves the problem ofcollision penetration.This paper will Simulate the algorithm based on HOOPS and ACIS platformusing C + + programming,save the path data of the roles, and ultimately generateanimation using Maya software. The experiments show that the improved RMPSOalgorithm has better performance than the standard PSO algorithm and the MPSO algorithm, especially in avoiding premature convergence and improving diversity ofthe group,and this paper uses the RMPSO algorithm in collision detection algorithm,and the generated animation shows that: based on RMPSO collision detectionalgorithm has a good performance.This paper compares the algorithm with thealgorithm based on PSO, experiments show that this algorithm can not only avoid thecollision between the groups, also increase computing speed.In summary, the main work and innovation is the following three points:(1) analysis advantages and disadvantages of several major swarm intelligencealgorithm, especially the advantages and disadvantages of the standard PSOalgorithm, and put forward a better diversity, faster RMPSO algorithm, andfinally using the experiments proves the RMPSO effectiveness andefficiency.(2) propose a new fast collision detection algorithm - based on the RMPSOcollision detection algorithm, and compare with based on the PSO collisiondetection algorithm, experiments prove efficiency and diversity of collisiondetection algorithm based on RMPSO.(3) propose a simple, intelligent collision avoidance algorithm and solve theindividual rather long detour to avoid the collision obstacle. Using thisalgorithm, the individual can move the near side to the goal.this algorithmmakes individuals more intelligent.(4) develop a collision detection system basing on .NET + HOOPS + the ACISplatform, and applly the based on RMPSO collision detection algorithm tothe specific scene, and save the data of the individual path, create groupanimation using the Maya software, the group animation shows thisalgorithm practicality, effectiveness, and efficiency ,this algorithm solves theslow of the speed and other issues.