Real-time Simulation of Crowds Using Voronoi Diagrams (English)

in EG UK Theory and Practice of Computer Graphics ; 195-201
EG UK Theory and Practice of Computer Graphics
The Eurographics Association , Postfach 8043, 38621 Goslar, Germany; 2005

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.

How to get this document?
Download
Commercial Copyright fee: €14.50 Basic fee: €4.00 Total price: €18.50
Academic Copyright fee: €4.50 Basic fee: €2.00 Total price: €6.50

Document information


Table of contents conference proceedings

The table of contents of the conference proceedings is generated automatically, so it can be incomplete, although all articles are available in the TIB.

11
Keyframing Particles of Physically Based Systems
Dingle, Brent M. / Keyser, John | 2005
19
Real-Time Animation of Particles and Seaweeds in Underwater Scenes
Coulais, Y. / Ghazanfarpour, D. / Terraz, O. / Thon, S. | 2005
27
Implementing an Improved Stereoscopic Camera Model
Froner, Barbara / Holliman, Nick | 2005
35
A Psychologically-Based Simulation of Human Behaviour
Rymill, Stephen J. / Dodgson, Neil A. | 2005
43
An Efficient Caching Technique for Rendering Translucent Materials
Keng, Shih-Ling / Lee, Wang-Yeh / Chuang, Jung-Hong | 2005
51
Implementing FastMap on the GPU: Considerations on General-Purpose Computation on Graphics Hardware
Reina, G. / T.Ertl | 2005
59
Selective Parallel Rendering for High-Fidelity Graphics
Debattista, K. / Sundstedt, V. / Pereira, F. / Chalmers, A. | 2005
67
Virtual Sculpting Using Implicit Surfaces with Scattered Data Interpolation
K. Zhang / R. A. Noble / McDermott, R. J. / Wilson, A. | 2005
75
Integrating Abstract and Physical Molecular Model Interaction
Thorne, Dave / Pettifer, Steve / Attwood, Terri | 2005
83
Perceptually-Oriented Interest Management In Large-Scale Networked Virtual Environments
Dunwell, I. / Whelan, J. C. | 2005
91
Perceptual Level of Detail for Efficient Ray Tracing of Complex Scenes
Yang, X. / Chalmers, A. | 2005
97
Cost Prediction Maps for Global Illumination
Gillibrand, Richard / Debattista, Kurt / Chalmers, Alan | 2005
105
Towards Realism in Facial Image Prototyping: Results of a Wavelet MRF Method
Tiddeman, Bernard / Stirrat, Michael / Perrett, David | 2005
113
Perlin Noise and 2D Second-Order Tensor Field Visualization
Liu, J. / Perrin, J. / Turner, M. / Hewitt, W. T. | 2005
119
Simulating the Cumulative Effects of Multiple Impacts using 'Fracture Maps'
Clifton, T. | 2005
125
Arachnid Simulation: Scaling Arbitrary Surfaces
Cenydd, L. ap / Teahan, W. | 2005
133
Visualization of Smoothed Particle Hydrodynamics for Astrophysics
Walker, Rick / Kenny, Peter / Miao, Jingqi | 2005
139
Fast Simulation of Facial Tissue Deformations Using Mass-Spring Chain Algorithm
Duysak, A. / Zhang, J. J. | 2005
147
Simulation and Visualization of a large scale Real Time Multi-Robot system
Al-Hudhud, G. / Ayesh, A. / Istance, H. | 2005
155
The Data Surface Interaction Paradigm
Lindell, Rikard / Larsson, Thomas | 2005
163
Augmented Reality Scenarios for Guitar Learning
Liarokapis, F. | 2005
171
skML a Markup Language for Distributed Collaborative Visualization
Duce, D. A. / Sagar, M. | 2005
179
Click and Brush: A Novel Way of Finding Correlations and Relationships in Visualizations
Wright, Michael A. E. / Roberts, Jonathan C. | 2005
187
Freehand 3D Curve Recognition and Oversketching
Han, Li / Amicis, Raffaele De / Conti, Giuseppe | 2005
195
Real-time Simulation of Crowds Using Voronoi Diagrams
Champagne, J. / Tang, W. | 2005
203
VRECKO: Virtual Reality Framework
Flasar, Jan / Pokluda, Ludek / Olejek, Radek / Kolcárek, Pavel / Sochor, Jirí | 2005
209
Ubiquitous Virtual Reality: Accessing Shared Virtual Environments through Videoconferencing Technology
Pfeiffer, Thies / Weber, Matthias / Jung, Bernhard | 2005

Similar titles