TY - GEN
T1 - Hybrid long-range collision avoidance for crowd simulation
AU - Golas, Abhinav
AU - Narain, Rahul
AU - Lin, Ming
PY - 2013/3/21
Y1 - 2013/3/21
N2 - Local collision avoidance algorithms in crowd simulation often ignore agents beyond a neighborhood of a certain size. This cutoff can result in sharp changes in trajectory when large groups of agents enter or exit these neighborhoods. In this work, we exploit the insight that exact collision avoidance is not necessary between agents at such large distances, and propose a novel algorithm for extending existing collision avoidance algorithms to perform approximate, long-range collision avoidance. Our formulation performs long-range collision avoidance for distant agent groups to efficiently compute trajectories that are smoother than those obtained with state-of-the-art techniques and at faster rates. Another issue often sidestepped in existing work is that discrete and continuum collision avoidance algorithms have different regions of applicability. For example, low-density crowds cannot be modeled as a continuum, while high-density crowds can be expensive to model using discrete methods. We formulate a hybrid technique for crowd simulation which can accurately and efficiently simulate crowds at any density with seamless transitions between continuum and discrete representations. Our approach blends results from continuum and discrete algorithms, based on local density and velocity variance. In addition to being robust across a variety of group scenarios, it is also highly efficient, running at interactive rates for thousands of agents on portable systems.
AB - Local collision avoidance algorithms in crowd simulation often ignore agents beyond a neighborhood of a certain size. This cutoff can result in sharp changes in trajectory when large groups of agents enter or exit these neighborhoods. In this work, we exploit the insight that exact collision avoidance is not necessary between agents at such large distances, and propose a novel algorithm for extending existing collision avoidance algorithms to perform approximate, long-range collision avoidance. Our formulation performs long-range collision avoidance for distant agent groups to efficiently compute trajectories that are smoother than those obtained with state-of-the-art techniques and at faster rates. Another issue often sidestepped in existing work is that discrete and continuum collision avoidance algorithms have different regions of applicability. For example, low-density crowds cannot be modeled as a continuum, while high-density crowds can be expensive to model using discrete methods. We formulate a hybrid technique for crowd simulation which can accurately and efficiently simulate crowds at any density with seamless transitions between continuum and discrete representations. Our approach blends results from continuum and discrete algorithms, based on local density and velocity variance. In addition to being robust across a variety of group scenarios, it is also highly efficient, running at interactive rates for thousands of agents on portable systems.
KW - Collision avoidance
KW - Crowd simulation
KW - Hybrid algorithms
KW - Lookahead
UR - http://www.scopus.com/inward/record.url?scp=84875903596&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84875903596&partnerID=8YFLogxK
U2 - 10.1145/2448196.2448200
DO - 10.1145/2448196.2448200
M3 - Conference contribution
AN - SCOPUS:84875903596
SN - 9781450319560
T3 - Proceedings of the Symposium on Interactive 3D Graphics
SP - 29
EP - 36
BT - Proceedings - I3D 2013
T2 - 17th ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games, I3D 2013
Y2 - 21 March 2013 through 23 March 2013
ER -