Crowd SimulationsOutlineSlide 3Animation - BasicsSlide 5Walk CycleDigression - Eadweard MuybridgeWalk Cycle - AnalysisWalk Cycle - AlternativesSlide 10Crowd Simulation ModelsAgent Based SimulationsSlide 13FlockingBoids - ContinuedBoids OnlineSlide 17Helbing’s Social Force ModelSocial Force Model – Pedestrian AvoidanceHelbing - ContinuedSlide 21Reciprocal Velocity ObstaclesRVO: Planning In Velocity SpaceSlide 24Slide 25Slide 26Slide 27Slide 28Slide 29Slide 30Slide 31Slide 32VideosVideosRelated data-structuresRoadmapsVideoSlide 38Rendering CrowdsImpostersQuestionsCrowd SimulationsGuest Instructor - Stephen J. GuyOutlineAnimation basicsKey framingSimulation LoopHow to move one manWalk CycleIKHow to move one thousandCrowd ModelsCollision AvoidanceData StructuresRenderingOutlineAnimation basicsKey framingSimulation LoopHow to move one manWalk CycleIKHow to move one thousandCrowd ModelsCollision AvoidanceRenderingAnimation - BasicsComp 768 Preview…Goal: Illusion of continuous motionDivide into several small time-steps (length T)Show new image at each time-stepNeeds to happened at least ~12/second (more is better)Advance TUpdate StateDraw PictureOutlineAnimation basicsKey framingSimulation LoopHow to move one manWalk CycleIKHow to move one thousandCrowd ModelsCollision AvoidanceData StructuresRenderingWalk CycleSimply Translating a character to its goal is unrealisticWalk Cycle: A looping series of positionswhich represent a character walking (or running or galloping)Shifting the animation provides the illusion of walkingInplace Shifted w/ TimeDigression - Eadweard Muybridge 19th Century English PhotograyherUsed multiple cameras to capture motionInvented Zoopraxiscope (spinning wheel of still images) to animate imagesWalk Cycle - AnalysisPros:Simple to implementCaptures the basics of human movementCons:Walks must cycleCan’t handle changes in stride lengthCan’t handle jumpsMust be animated by handWalk Cycle - AlternativesInverse KinematicsUsing math to figure out where to place the rest of the body to get the feet moving forwardMotion CaptureRecord data of real humans walkingMotion Clips FSM of different motionsOutlineAnimation basicsKey framingSimulation LoopHow to move one manWalk CycleIKHow to move one thousandCrowd ModelsCollision AvoidanceData StructuresRenderingCrowd Simulation ModelsSimplest model – Agent Based:Capture Global Behavior w/ many interacting autonomous agentsEach person is represented by one agentChooses next state based on goal and neighborsPioneered by Craig ReynoldsWon 1998 (Technical) Academy AwardAdvance TGather NeighborsDraw AgentUpdate StatesFor Each AgentAgent Based SimulationsFlocking Craig ReylondsSIGGRAPH1987Social Forces ModelDirk HelbingPhysics Review B 1995Nature 2000Reciprocal Velocity ObstaclesVan den BergI3D 2008Agent Based SimulationsFlocking Craig ReylondsSIGGRAPH1987Social Forces ModelDirk HelbingPhysics Review B 1995Nature 2000Reciprocal Velocity ObstaclesVan den BergI3D 2008FlockingSeminal work in multi-agent movementAssign simple force to each agentUsed in Lion KingBatman ReturnsSeparation Alignment CohesionBoids - ContinuedNew forces can be added to incorporate more behaviorsAvoiding ObstaclesCollision AvoidanceBe Creative!Boids OnlineVisit: http://www.red3d.com/cwr/boids/And: http://www.red3d.com/cwr/steer/Unaligned.htmlAgent Based SimulationsFlocking Craig ReylondsSIGGRAPH1987Social Forces ModelDirk HelbingPhysics Review B 1995Nature 2000Reciprocal Velocity ObstaclesVan den BergI3D 2008Helbing’s Social Force ModelVery similar to boid modelTreats all agents as physical obstaclesSolves a = F/m where F is “social force”:Fij – Pedestrian AvoidanceFiW – Obstacle (Wall) AvoidanceDesired VelocityCurrent VelocityAvoiding Other PedestriansAvoiding WallsSocial Force Model – Pedestrian Avoidancerij – dij  Edge-to-edge distancenij – Vector pointing away from agentAi*e[(rij-dij)/Bi]  Repulsive force which is exponential increasing with distanceg(x)  x if agents are colliding, 0 otherwisetij – Vector pointing tangential to agentVtji – Tangential velocity differenceFiW is very similarCollision AvoidanceNon-penetration Sliding ForceHelbing - ContinuedNoticed arching Also observed in real crowdsKilled or injured people whoexperienced too much force (1,600 N/m) – became unresponsive obstaclesNoticed Faster-is-slower effectAgent Based SimulationsFlocking Craig ReylondsSIGGRAPH1987Social Forces ModelDirk HelbingPhysics Review B 1995Nature 2000Reciprocal Velocity ObstaclesVan den BergI3D 2008Reciprocal Velocity ObstaclesApplied ideas from robotics to crowd simulationsBasic idea:Given n agents with velocities, find velocities will cause collisionsAvoid them!Planning is performed in velocity spaceRVOAB(vB, vA) = {v’A | 2v’A – vA  VOAB(vB)}23RVO: Planning In Velocity Space24RVO: Planning In Velocity SpaceRA + RB25RVO: Planning In Velocity Space(VA + VB)/2RVO: Planning In Velocity Space2627RVO: Planning In Velocity Space28RVO: Planning In Velocity SpaceRVO: Planning In Velocity Space2930RVO: Planning In Velocity SpaceRVO: Planning In Velocity Space31RVO: Planning In Velocity Space32Videos12 Agents in a CircleVideos1,000 agent’s in a circleRelated data-structuresKD-treesAllowing efficient gathering of nearby neighbors O(log n)Roadmaps & A*Allows global navigation around obstaclesRoadmaps1. Create roadmap in free space 2. Find visible source nodes3. Graph Search to find path to DestinationA* is very popular graph search algorithm 36Video1,000 people leaving Sitterson HallUses RVO, Roadmaps, A* and Kd-TreesOutlineAnimation basicsKey framingSimulation LoopHow to move one manWalk CycleIKHow to move one thousandCrowd ModelsCollision AvoidanceData StructuresRenderingRendering CrowdsTraditional OpenGL pipeline can be too slow for 1000s of agentsView Culling helps, but often not enoughNeed Level-of-Detail techniquesUse models with more polygons up close, less when far awayImposters40Replace Far