Real-time collision-free linear trajectory generation on GPU for crowd simulations


VISUAL COMPUTER, vol.31, pp.843-852, 2015 (SCI-Expanded) identifier identifier

  • Publication Type: Article / Article
  • Volume: 31
  • Publication Date: 2015
  • Doi Number: 10.1007/s00371-015-1105-z
  • Journal Name: VISUAL COMPUTER
  • Journal Indexes: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Page Numbers: pp.843-852
  • Hacettepe University Affiliated: Yes


Crowd simulations are mostly employed to compose a background in the current scene. For such ambient crowds, it might be unnecessary to perform complex steering calculations. In this study, a steering-free crowd simulation which eliminates the computational cost arising from expensive steering maneuvers is presented. For this purpose, agents are assigned a linear trajectory that is guaranteed to be collision free before entering the simulation. These trajectories are calculated using readily available rendering pipeline of the GPU. To that end, existing agents' bounding discs are rendered in a spatio-temporal manner as each one forms a straight 3D tube and a projection from a selected initial position is captured. Using the blank areas (holes) in this image, it is possible to determine a suitable constant velocity (a goal position and a speed). In experiments, we not only assess three different methods to choose one of the candidate solutions, but also compare our approach with an existing work. Test results reveal that our technique gives better results in both populating an empty environment with agents quicker and reaching a higher maximum number of agents than the existing method.