| January 11, 2011 11:00 PM PST | |
By Shawn Singh, Petros Faloutsos and Glenn Reinman
To address this, we propose a method of generating sequences of footsteps as navigation decisions. Our model is a simplification of the well-established inverted pendulum model used in biomechanics (Figure 1). When projected down to 2D, the trajectory of the character's center of mass can be approximated as a piecewise parabolic curve. Each parabola represents a single step, and the parameters that vary the shape of the parabola correspond directly to the different ways a character can step: the curvature, speed, and size of the step (Figure 2). The foot is located a fixed distance from the apex of each parabola, timed according to the speed of the step, and oriented according to the constraints described below.
Given a character's current footstep, the next step is constrained in several ways. First, a step cannot exceed a certain distance from the previous step. Similarly, the timing of the step must not be too slow, and not too fast. Second, each step maintains an interval of valid foot orientations. This interval is constrained by the previous step, and is also constrained by the parabolic trajectory of the current step (Figure 3). If the interval of valid foot orientations becomes invalid, that implies that the particular footstep is unnatural and thus that step is invalid. Third, we associate 5 small circles with the character: a circle associated with each shoulder, and a circle associated with each foot (Figure 4). This provides a good approximation of tight, dynamically changing bounds as a character proceeds through each step. If a footstep causes these bounds to collide with any other characters or obstacles, then that step is considered invalid.
Using this footstep model, we use a best-first search (for example the A* algorithm) to plan sequences of goal-oriented footsteps. As the search continues, any footstep choices that violate the constraints described above are pruned from the search space. This way, the character's footsteps will avoid collisions with other characters and will always be biomechanically valid. Furthermore, within this set of valid footsteps, the planner finds the sequence of steps that has minimal energy cost towards the goal. Minimizing energy corresponds to using steps that require less effort, and thus are more natural.
With this planner, characters can precisely navigate through tight and tricky situations such as doorways, crowds, and holes in the ground (Figures 5 and 6). Characters exhibit side-stepping, back-stepping, and even stopping in the appropriate situations.
The performance of planning footsteps for three benchmark scenes is shown in Table 1, using a single thread on a 2.66 GHz Intel® Core™2 Duo processor-based platform with 2GB memory running Windows* XP (service pack 2). The amortized cost of updating characters at 20 Hz is extremely low; it takes only a few milliseconds to plan a sequence of steps, but each sequence may take several seconds to actually execute.
Shawn Singh, University of California, Los Angeles.
Shawn is a PhD Candidate in computer graphics at UCLA under Professor Petros Faloutsos and Professor Glenn Reinman. His research includes pedestrian navigation in crowds as well as architectures for real-time ray tracing and photon mapping.
"On the Interface Between Steering and Animation for Autonomous Characters." S. Singh, M. Kapadia, G. Reinman, P. Faloutsos. In Workshop on Crowd Simulation, Computer Animation and Social Agents, 2010.
UCLA MAGiX lab: http://magix.ucla.edu/
Petros Faloutsos is an assistant professor at the Department of Computer Science at the University of California at Los Angeles. He received his PhD degree (2002) and his MSc degree in Computer Science from the University of Toronto, Canada and his BEng degree in Electrical Engineering from the National Technical University of Athens, Greece. Professor Faloutsos is the founder and the director of the graphics lab at the Department of Computer Science at UCLA. He is an associate editor for the Journal of The Visual Computer and has served as a Program Co-Chair for the ACM SIGGRAPH/Eurographics Symposium on Computer Animation 2005. He is a member of the ACM and the Technical Chamber of Greece.
Glenn Reinman is an associate professor in the Department of Computer Science at the University of California, Los Angeles. He received his Ph.D. and M.S. in Computer Science at the University of California, San Diego in 2001 and 1999 respectively. He received a B.S. in Computer Science and Engineering from the Massachusetts Institute of Technology in 1996. He is one of the thrust leaders at the Center for Domain Specific Computing established by NSF.
Download Article
Download Footstep Navigation [PDF 555KB]Abstract
Navigation is an essential ability of autonomous virtual characters. The standard approach is to model each character as a point-sized particle with a single collision radius, outputting a desired force or velocity vector to an animation system. In this project, we propose a more detailed, biomechanically inspired model of how a character can move, outputting footsteps to an animation system. Footstep-based navigation offers far more control and less ambiguity compared to the traditional vector-based navigation, and steps can be easily validated for correctness. The coarse-grain nature of footsteps makes it possible to plan sequences of steps, including foot orientation and timing, for hundreds of characters in real-time.Generating Intelligent Footsteps
The majority of academic and commercial navigation systems use a velocity or force vector as the steering decision that controls a character's movement. Unfortunately, vectors cannot indicate maneuvers such as side-steps, back-steps, or exact foot placement, and it is often unclear what animations should be used to follow a vector decision. Sometimes the vectors may even suggest actions that are not physically valid, such as steering into an obstacle or turning instantaneously.Figure 1. Two steps (red and green) of an inverted pendulum model of bipedal locomotion.
To address this, we propose a method of generating sequences of footsteps as navigation decisions. Our model is a simplification of the well-established inverted pendulum model used in biomechanics (Figure 1). When projected down to 2D, the trajectory of the character's center of mass can be approximated as a piecewise parabolic curve. Each parabola represents a single step, and the parameters that vary the shape of the parabola correspond directly to the different ways a character can step: the curvature, speed, and size of the step (Figure 2). The foot is located a fixed distance from the apex of each parabola, timed according to the speed of the step, and oriented according to the constraints described below.
Figure 2. Footstep model.
Given a character's current footstep, the next step is constrained in several ways. First, a step cannot exceed a certain distance from the previous step. Similarly, the timing of the step must not be too slow, and not too fast. Second, each step maintains an interval of valid foot orientations. This interval is constrained by the previous step, and is also constrained by the parabolic trajectory of the current step (Figure 3). If the interval of valid foot orientations becomes invalid, that implies that the particular footstep is unnatural and thus that step is invalid. Third, we associate 5 small circles with the character: a circle associated with each shoulder, and a circle associated with each foot (Figure 4). This provides a good approximation of tight, dynamically changing bounds as a character proceeds through each step. If a footstep causes these bounds to collide with any other characters or obstacles, then that step is considered invalid.
Figure 3. The interval of valid footsteps (blue and green) is constrained by the previous step (red) and the chosen trajectory.
Figure 4. Time-varying collision model (5 red circles)
Using this footstep model, we use a best-first search (for example the A* algorithm) to plan sequences of goal-oriented footsteps. As the search continues, any footstep choices that violate the constraints described above are pruned from the search space. This way, the character's footsteps will avoid collisions with other characters and will always be biomechanically valid. Furthermore, within this set of valid footsteps, the planner finds the sequence of steps that has minimal energy cost towards the goal. Minimizing energy corresponds to using steps that require less effort, and thus are more natural.
With this planner, characters can precisely navigate through tight and tricky situations such as doorways, crowds, and holes in the ground (Figures 5 and 6). Characters exhibit side-stepping, back-stepping, and even stopping in the appropriate situations.
Figure 5. The red pedestrian side-steps to let the yellow pedestrian pass through the narrow doorway.
Figure 6. More examples of navigating with footsteps. (a) Multiple pedestrians at a doorway. (b) A pedestrian stepping over holes in the floor. (c) Pedestrians packing through a bottleneck. (d) Two hundred characters navigating with footsteps in real-time.
The performance of planning footsteps for three benchmark scenes is shown in Table 1, using a single thread on a 2.66 GHz Intel® Core™2 Duo processor-based platform with 2GB memory running Windows* XP (service pack 2). The amortized cost of updating characters at 20 Hz is extremely low; it takes only a few milliseconds to plan a sequence of steps, but each sequence may take several seconds to actually execute.
Table 1. Performance of footstep navigation using a short-horizon planner.
About the Author
Shawn Singh, University of California, Los Angeles.
Shawn is a PhD Candidate in computer graphics at UCLA under Professor Petros Faloutsos and Professor Glenn Reinman. His research includes pedestrian navigation in crowds as well as architectures for real-time ray tracing and photon mapping.
Additional Resources
"Evaluating the Costs and Constraints Used to Make Footstep Decisions." S. Singh, M. Kapadia, G. Reinman, P. Faloutsos. UCLA Technical Report #100023, 2010."On the Interface Between Steering and Animation for Autonomous Characters." S. Singh, M. Kapadia, G. Reinman, P. Faloutsos. In Workshop on Crowd Simulation, Computer Animation and Social Agents, 2010.
UCLA MAGiX lab: http://magix.ucla.edu/
Advisors: Glenn Reinman & Petros Faloutsos
Petros Faloutsos is an assistant professor at the Department of Computer Science at the University of California at Los Angeles. He received his PhD degree (2002) and his MSc degree in Computer Science from the University of Toronto, Canada and his BEng degree in Electrical Engineering from the National Technical University of Athens, Greece. Professor Faloutsos is the founder and the director of the graphics lab at the Department of Computer Science at UCLA. He is an associate editor for the Journal of The Visual Computer and has served as a Program Co-Chair for the ACM SIGGRAPH/Eurographics Symposium on Computer Animation 2005. He is a member of the ACM and the Technical Chamber of Greece.
Glenn Reinman is an associate professor in the Department of Computer Science at the University of California, Los Angeles. He received his Ph.D. and M.S. in Computer Science at the University of California, San Diego in 2001 and 1999 respectively. He received a B.S. in Computer Science and Engineering from the Massachusetts Institute of Technology in 1996. He is one of the thrust leaders at the Center for Domain Specific Computing established by NSF.
For more complete information about compiler optimizations, see our Optimization Notice.
Comments (0) 
Trackbacks (1)
-
Twitter Trackbacks for
Footstep Navigation - Intel® Software Network
[intel.com]
on Topsy.com
January 26, 2011 5:05 PM PST
Leave a comment 
To obtain technical support, please go to Software Support.
