GPU Based Motion Path Matching And Crowd Simulation

Large scale crowd simulation has many applications in film effects, computer games, and so on, but if the number of agents in the crowd is very big, it can't realize the real-time simulation. So we think serial algorithm can't meet all kind of application for crowd simulation, especially large scale. In recent years, parallel compute ability of GPU develops very quickly, it takes advantage of the GPU's computing power. The agent in the crowd simulation is independent each other, so it is very suit to use parallel compute.This paper contained two research parts: one was the parallel motion path matching. Given a path, we selected the most suitable motion from the motion database, and then linked them together to become a continuous motion, making the Trajectories of this motion similar to the path. In this model, we would talk about establishing the motion database, generation of scene path, and give a detail description in the second chapter and third chapter, in these two chapters we would talk about how to capture motion, design motion, and using hardware accelerated algorithm of Voronoi diagram to divide the scene, getting the path. Finally we analyzed the procedure of matching, parallel compute method, compare the performance.Another part was the parallel crowd simulation system, making more than thousands agents walk along the path smoothly, and avoid the collision among the agents, also the obstacles. So we built a simple agent model, using three forces to simulate the feedback of agents to environment, such as path follow force, obstacle avoid force, agent collision avoid force. Base on this model, we established the parallel crowd simulation algorithm, the procedure contained the scene segment, neighbor query, update the velocity of each agent, we used the CUDA for GPU coding, accelerating the compute in crowd simulation, we got a good result.