Boids that see: Using self-occlusion for simulating large groups on GPUs

Abstract

Behavioral models have been used in the entertainment industry to increase the realism in the simulation of large groups of individuals. Unfortunately, the classical models can be very compute-intensive when very large groups are considered, reducing its applicability in games and other interactive systems. In this article we explore both search space reduction and parallelism to improve the performance of Reynold's Boids model. We propose a methodology that considers self-occlusion (visibility culling) to reduce the number of neighbors and we take advantage the parallelism present in common graphics processor units (GPUs) to allow the simulation of very large groups. We performed different GPU implementations (GPGPU and CUDA); the results show that visibility culling allows significant gains in performance without affecting the model's overall behavior.

References

1. Breitbart, J. 2008. Case studies on GPU usage and data structure design. Master's thesis, Universität Kassel.
2. Chiara, R. D., Erra, U., Scarano, V., and Tatafiore, M. 2004. Massive simulation using GPU of a distributed behavioral model of a flock with obstacle avoidance. In Vision Modeling and Visualization (VMV), 233--240.
3. Cohen-Or, D., Chrysanthou, Y., and Silva, C. 2003. A survey of visibility for walkthrough applications. IEEE Trans. Visualization and Computer Graphics 9, 3 (July--Sept.), 412--431.
4. Courty, N. and Musse, S.R. 2005. Simulation of large crowds in emergency situations including gaseous phenomena. In Proceedings of the Computer Graphics International (CGI'05). IEEE, 206--212.
5. Drone, S. 2007. Real-time particle systems on the GPU in dynamic environments. In Proceedings of the International Conference on Computer Graphics and Interactive Techniques (SIGGRAPH'07). ACM, New York, 80--96.
6. Halfhill, T. 2008. Parallel Processing With Cuda. Microprocessor. In Proceedings of the 2008 Symposium on Interactive 3D Graphics and Games, 89--97.
7. Harris, M. and Buck, I. 2005. GPU Gems 2 -- Programming Techniques for High-Performance Graphics and General- Purpose Computation. Addison Wesley, 547--555.
8. Klosowski, J. T. and Silva, C. T. 2000. The prioritized layered projection algorithm for visible set estimation. IEEE Trans. Visualization and Computer Graphics 6, 2, 108--123.
9. Kolb, A., Latta, L., and Rezk-Salama, C. 2004. Hardware based simulation and collision detection for large particle systems. In Proceedings of the ACM SIGGRAPH/EUROGRAPHICS Conference on Graphics Hardware ACM, New York, 123--131.
10. Marcolino, L. S. and Chaimowicz, L. 2008. No robot left behind: Coordination to overcome local minima in swarm navigation. In Proceedings of the IEEE International Conference on Robotics and Automation, 1904--1909.
11. Mark, W. R., Glanville, R. S., Akeley, K., and Kilgard, M. J. 2003. Cg: A system for programming graphics hardware in a C-like language. In Proceedings of the International Conference on Computer Graphics and Interactive Techniques. ACM, New York, 896--907.
12. nVidia. 2008. nVidia CUDA programming guide 2.1.
13. nVidia Corp. 2007. nVidia CUDA computer unified device architecture programming guide. http://developer.nvidia.com/cuda.
14. Owens, J.D., Luebke, D., Govindaraju, N., Harris, M., Rger, J., Lefohn, A.E., and Purcell, T.J. 2007. A survey of general-purpose computation on graphics hardware. Computer Graphics Forum 26, 1, 80--113.
15. Passos, E., Joselli, M., Zamith, M., Rocha, J., Clua, E., Montenegro, A., Conci, A., and Feijó, B. 2008. Supermassive crowd simulation on GPU based on emergent behavior. In Proceedings of the Seventh Brazilian Symposium on Computer Games and Digital Entertainment (SBGames'08), Sociedade Brasileira de Computação, SBC, 70--75.
16. Quinn, M.J., Metoyer, R., and Hunter-Zaworski, K. 2003. Parallel implementation of the social forces model. In Proceedings of the Second International Conference in Pedestrian and Evacuation Dynamics, 63--74.
17. Reeves, W.T. 1983. Particle systems—A technique for modeling a class of fuzzy objects. ACM Trans. Graphics 2, 2, 91--108.
18. Reynolds, C.W. 2006. Big fast crowds on ps3. In Proceedings of the 2006 ACM SIGGRAPH Symposium on Videogames (Sandbox '06). ACM, New York, 113--121.
19. Reynolds, C.W. 1987. Flocks, herds and schools: A distributed behavioral model. In Proceedings of the 14th Annual Conference on Computer Graphics and interactive Techniques, 25--34.
20. Shao, W. and Terzopoulos, D. 2005. Autonomous pedestrians. In Proceedings of the 2005 ACM SIGGRAPH/Eurographics Symposium on Computer Animation (SCA'05), ACM, New York, 19--28.
21. Shreiner, D., Woo, M., Neider, J., and Davis, T. 2005. OpenGL(R) Programming Guide: The Official Guide to Learning OpenGL(R), Vers. 2 (5th ed.), Addison-Wesley, Reading, MA.
22. Sillion, F.X. 1995. A unified hierarchical algorithm for global illumination with scattering volumes and object clusters. IEEE Trans. Visualization Computer Graphics 1, 3, 240--254.
23. Thalmann, D. and Musse, S. 2007. Crowd Simulation, Springer, Berlin.
24. Terzopoulos, D., Tu, X., and Grzeszczuk, R. 1994. Artificial fishes: Autonomous locomotion, perception, behavior, and learning in a simulated physical world. Artificial Life 1, 4, 327--351.
25. Treuille, A., Cooper, S., and Popovi'c, Z. 2006. Continuum crowds. ACM Trans. Graphics 25, 3, 1160--1168.

Index Terms

• Applied computing

  • Computers in other domains

    • Personal computers and PC applications

      • Computer games

• Computing methodologies

  • Computer graphics

    • Graphics systems and interfaces

      • Graphics processors

  • Parallel computing methodologies

• Information systems

  • Information systems applications

    • Multimedia information systems

      • Massively multiplayer online games

• Software and its engineering

  • Software organization and properties

    • Contextual software domains

      • Virtual worlds software

        • Interactive games

• Theory of computation

  • Theory and algorithms for application domains

    • Algorithmic game theory and mechanism design