CS780 2004 0303

An Event-Driven Approach toHuman Crowd Simulationwith Example Motions: 

An Event-Driven Approach to Human Crowd Simulation with Example Motions Sung Yong SHIN Computer Science Division Korea Advanced Institute of Science & Technology March 27, 2003

Slide2: 

Dohan Kim Ph.D. Candidate, Computer Graphics Lab., CS Div., KAIST http://cg.kaist.ac.kr/

OUTLINE: 

Motivation Basic Idea Related Work Overview Initializer Behavior Generation Motion Generation Results Conclusion OUTLINE

1. Motivation: 

1. Motivation Crowd Scenes Commonplace in computer games and feature films Evolving from the interactions among individual members and their interactions with the environment Highly dynamic and complex An Event-driven Approach to Human Crowd Simulation with Example Motions

Why example motions?: 

To generate realistic motions efficiently. How? Motion capture and reuse. On–line motion blending. [Park et al. 2002] Why example motions?

Why “Event – driven” ?: 

Why not employing a fixed–time advancing scheme? Well, …… Some well–known characteristics of crowds : Members clustered together very closely. Living creatures to actively interact with each other and also with the environment.  Adaptive correcting behaviors to dynamically changing situations even during a time step !!! Why “Event – driven” ?

2. Basic Idea: 

2. Basic Idea Event-driven approach Guided by the external events reflecting the scenario, the behavior of a crowd evolves as intended, while adding variations due to the internal events. Live-captured motion clips

3. Related Work: 

3. Related Work Non-human creatures : reactive behaviors Dynamic spatial partitioning [Reynolds 1987] Synthetic visions [Tu and Terzopoulos 1994] Pedestrian dynamics : Pedestrian crowd modelling Similar to gases and fluids [Henderson 1974] Individual pedestrian dynamics [Gipps and Markiso 1985; Helbing 1992, 1995, 2000]

3. Related Work (cont.): 

3. Related Work (cont.) Behavioral rules Behavioral model of groups: Border Collies and Olympic bicycle racing [Brogan et al. 1997] ViCrowd [Musse and Thalmann 2001] Improv [Perlin and Goldberg 1996] Real-world systems Based on pedestrian dynamics together with procedural rules AntZ, The Lord of the Rings Plug-ins to MayaTM and SoftimageTM

4. Overview: 

Script parser Motion Generator Event Scheduler External Event Generator Internal Event Generator Scenario Behavior Generator Example motions Event handler Initializer 4. Overview

5. Initializer: 

Script Parser Scenario behavioral rules external Events Event Handler Event Scheduler 5. Initializer External Event Generator

6. Behavior Generation: 

6. Behavior Generation Script Parser behavioral rules Event Handler Internal Event Generator Event Scheduler External Event Generator Motion Generatior External event Event Candidate Internal Event Motion specification

Event-Driven Paradigm: 

Event-Driven Paradigm External events Internal events (candidate)

Internal Event Prediction: 

Internal Event Prediction Predicting two candidate internal events for a crowd member A candidate resetting event A candidate colliding event Why candidates?

Space Subdivision: 

Space Subdivision

Time-Varying Bounds: 

Time-Varying Bounds Assumptions - moving trajectories unknown - bounded acceleration Time – varying bounds Uncertainty in future facilitating interactions r

Slide17: 

Registration of Time-varying Bounds (C(sk)) R(sk) C(sk) sk ℓ 2ℓ A time-varying bound sk is said to be registered in a subspace C(sk) if the center of sk was contained in C(sk) at its most recent event time. C(sk), R(sk), and R(sk) 3ℓ

Slide18: 

Candidate Resetting Event Generation (C(sk)) R(sk) C(sk) Sk = {all time-varying bounds registered in (R(sk)).

Slide19: 

Candidate Colliding Event Generation

Event Handling: 

Event Handling Deriving the reactions to events Updating the internal status Behavioral rules + external information

How to Handle External Events: 

How to Handle External Events Controlling the global flow of crowd simulation Drawing the reactions from behavioral rules Prescribing motion specifications Creating new candidate internal events

How to Handle Internal Events: 

How to Handle Internal Events Local interactions among crowd members Interaction with the environment Adding details to crowd behaviors A force field model of pedestrian dynamics

Slide23: 

Force Field Model avoiding force braking force driving force

Slide24: 

Driving Force global velocity control local velocity adjustment route goal

Braking Force: 

0 0 Braking Force

Avoiding Force: 

0 Avoiding Force

Resetting Event Handling: 

- resetting the time-varying bound sk to its initial size - probing the position xk(t) and velocity vk(t) to re-initialize the time-varying bound sk making registration change if needed. new location old location Resetting Event Handling

Colliding Event Handling: 

identify the neighbors and nearby objects compute the force exerted on each of colliding members reset the time-varying bounds Colliding Event Handling

7. Motion Generation: 

Example motions Parameterization Motion Blending Weight Computation Time Warping Posture Blending Motion Retargeting Motion Specifications Target Motion 7. Motion Generation

7. Motion Generation: 

7. Motion Generation

8. Results: 

8. Results

9. Conclusion: 

9. Conclusion Event-driven approach Locomotive behaviors Collision detection + Pedestrian dynamics Future work Scripting system (scenario + behavioral rules) Sophisticated behavioral rules Generalization to other types of motions

Paper List: 

Paper List Non-human Creatures C. Niederberger and M. Gross. Hierarchical and Heterogeneous Reactive Agents for Real-Time Applications. Computer Graphics Forum 22(3), 2003. C. W. Reynolds. Flocks, herds, and schools: A distributed behavioral model, In Proc. of SIGGRAPH 87: 25-34, 1987. Tu, Xiaoyuan, and D. Terzopoulos, Artificial Fishes: Physics, Locomotion, Perception, Behavior. In Proc. of SIGGRAPH 94: 43-50, 1994. Behavioral Models C. W. Reynolds. Steering Behaviors for Autonomous Characters. in Conference Proceedings of the 1999 Game Developers Conference: 763-782, 1999. S. R. Musse, D. Thalmann. Hierarchical Model for Real Time Simulation of Virtual Human Crowds. IEEE Transactions on Visualization and Computer Graphics 7(2): 152-164, 2001. H. Noser and D. Thalmann. The Animation of Autonomous Actors Based on Production Rules. In Proc. Computer Animation 96, 1996.

Paper List (cont.): 

Paper List (cont.) Scripting systems K. Perlin and A. Goldberg. Improv: A system for scripting interactive actors in virtual worlds. In Proc. of SIGGRAPH 96: 205-216, 1996. S. Vosinakis and T. Panayiotopoulos. A Task Definition Language for Virtual Agents. In Proc. of the International Conference in Central Europe on Computer Graphics, Visualization and Computer Vision (WSCG), 2003. Cognitive models J. Funge, X. Tu, and D. Terzopoulos. Cognitive Modeling: Knowledge, Reasoning and Planning for intelligent Characters. In Proc. of SIGGRAPH 99: 29-38, 1999. N. I. Badler and D. M. Chi and S. Chopra-Khullar. Virtual Human Animation Based on Movement Observation and Cognitive Behavior Models, In Proc. of Computer Animation Conf.: 128-137, 1999.

Paper List (cont.): 

Paper List (cont.) System Architectures B. M. Blumberg and T. A. Galyean. Multi-Level Direction of Autonomous Creatures for Real-Time Virtual Environments, In Proc. of SIGGRAPH 95: 47-54, 1995. S. Goldenstein, M. Karavelas, D. Metaxas, L. Guibas, E. Aaron, and A. Goswami. Scalable nonlinear dynamical systems for agent steeing and crowd simulation. Computers and Graphics 25(6): 983-998, 2001. J. Cremer, J. Kearney, and Y. Paperlis, HCSM: Framework for Behavior and Scenario Control in Virtual Environments, ACM Transactions on Modeling and Computer Simulation 5(3): 242-267, 1995. Collision detection J. D. Cohen, M. C. Lin, D. Manocha, and M. K. Ponamgi, I-COLLIDE: An Interactive and Exact Collision Detection System for Large-Scale Environments. In Proc. of Symposium on Interactive 3D Graphics: 189-196, 1995. P. M. Hubbard. Collision Detection for Interactive graphics applications. IEEE Transactions on Visualization and Computer Graphics, 1(3): 218-230, 1995. H. K. Kim, L. J. Guibas, and S. Y. Shin, Efficient Collision Detection among Moving Spheres with Unknown Trajectories, CS-TR-2000-159, 2000.

Paper List (cont.): 

Paper List (cont.) Interactions D. Thalmann, S. R. Muss, F. Garat. Guiding and Interacting with Virtual Crowds. In Proc. of EUROGRAPHICS Workshop on Animation and Simulation: 23-34, 1999. Craig Reynolds. Interaction with Groups of Autonomous Characters. In Proc. of Game Developers Conference 2000: 449-460, 2001. B. Ulicny and D. Thalmann. Towards Interactive Real-Time Crowd Behavior Simulation. Computer Graphics Forum 21(4): 767-773, 2002 Dynamic Simulation J. Hodgins, W. Wooten, D. Brogan, and J. O’Brien. Animating Human Athletics, In Proc. of SIGGRAPH 95: 71-78, 1995. D. C. Brogan, R. A. Metoyer, and J. K. Hodgins. Dynamically simulated characters in virtual environments. IEEE Computer Graphics and Applications 18(5): 58-69, 1998.

Paper List (cont.): 

Paper List (cont.) Pedestrian Dynamics D. Helbing, P. Molnar, I. Farkas, and K. Bolay, Self-organizing pedestrian movement. Environment and Planning B: Planning and Design 28(3), 2001. C. Burstedde, K. Klauck, A. Schadschneider, and J. Zittartz. Simulation of pedestrian dynamics using a 2-dimensional cellular automation. Physica A. 2001. Rendering F. Tecchia, C. Loscos, and Y. Chrysanthou. Visualizing Crowds in Real-Time, Computer Graphics Forum Volume 21(4), 2002. M. Wand and W. Straber. “Multi-Resolution Rendering of Complex Animated Scenes”. Computer Graphics Forum Volume 21(3), 2002.