Real-time simulation of crowds using voronoi diagrams

This source preferred by Wen Tang

Authors: Champagne, J. and Tang, W.


Start date: 12 June 2005

This data was imported from Scopus:

Authors: Champagne, J. and Tang, W.

Journal: Theory and Practice of Computer Graphics 2005, TPCG 2005 - Eurographics UK Chapter Proceedings

Pages: 195-201

ISBN: 9783905673562

In this paper, we present a novel approach for real-time simulation of crowds. Our method is to compute generalised 2D Voronoi diagrams on environment maps for the locations of agents in the crowds. The Voronoi diagrams are generated efficiently with graphics hardware by calculating the closest Voronoi site and the distance to that site using polygon scan conversion and the z-buffer depth comparison. Because Voronoi diagrams have unique features of spatial tessellations which give optimised partitions of space for locating the agents especially groups of agents in a virtual environment, agents in the same group are placed within the Voronoi region which encloses the nearest locations to the geometric centre of the group. Each group of agents within its own Voronoi region follows the geometric centre of the region that is moving on the paths of the maps. During the simulation, agents in groups move closely together and avoid collusions with other groups on the way. With carefully designed rules for collision response the algorithm can generate natural-looking group behaviors of large crowds in real-time. Each agent within a group only detects collisions with other agents of the group and with static obstacles in the environment. Efficiency of the simulation is also gained through such multi-level behavioral simulation approach. © The Eurographics Association 2005.

The data on this page was last updated at 04:57 on May 24, 2019.