GPU-Based Collision-Free Linear Trajectory Generation for Small Groups in Crowd Simulations

Year 2024, Volume: 27 Issue: 1, 407 - 417, 29.02.2024

Öner Barut

https://doi.org/10.2339/politeknik.1409006

Abstract

Crowd simulations, which are used to create virtual crowds in the computer environment and imitate their behavior, can also be used to create a crowd ambience in the background of a virtual scene. Even if is it to create a crowd ambiance in the background, the presence of individuals in groups rather than acting alone is an important element that will support this ambiance. In this study, a steering-free simulation model of real-time virtual human crowds that move together in small groups of 1-5 people, whose frequency of occurrence is compiled from real human crowds, in a formation according to the number of individuals in the group similar to real life, is proposed. In this new method, instead of creating separate collision-free and linear trajectories for each individual, a common trajectory is created for each group and all individuals in the group are ensured to move accordingly in the determined formation. The proposed method has innovations that enable creating groups with different numbers of individuals, adjusting the number of groups of each size according to the frequency of occurrence in the crowd, and determining the formation of individuals within the group according to the group size.

Keywords

Crowd simulation, small groups, steering-free, linear collision-free trajectory, ambient crowd

Kalabalık Benzetimlerinde Küçük Gruplar için GPU Tabanlı Çarpışmasız Doğrusal Gezinge Oluşturulması

Abstract

Bilgisayar ortamında sanal kalabalıklar oluşturmak ve bunların davranışlarını taklit etmek için kullanılan kalabalık benzetimleri, sanal bir sahnenin arka planında bir kalabalık ambiyansı oluşturmak için de kullanılabilmektedir. Arka planda bir kalabalık ambiyansı oluşturmak için de olsa bireylerin tek başlarına hareket etmeleri yerine gruplar halinde bulunması bu ambiyansı destekleyecek önemli bir unsurdur. Bu çalışmada, görülme sıklıkları gerçek insan kalabalıklarından derlenen 1-5 kişilik küçük gruplar halinde, gruptaki birey sayısına göre gerçek hayattakine benzer bir formasyonda yürüyerek birlikte hareket eden gerçek zamanlı sanal insan kalabalıklarının yönlendirmesiz bir benzetim modeli önerilmektedir. Bu yeni yöntemde her bir birey için ayrı ayrı çarpışmasız ve doğrusal gezingeler oluşturmak yerine her bir grup için ortak bir gezinge oluşturularak grup içerisindeki tüm bireylerin belirlenen formasyonda buna göre hareket etmeleri sağlanmaktadır. Önerilen yöntem, farklı birey sayılarına sahip gruplar oluşturmayı, her büyüklükteki grup sayısının kalabalık içinde görülme sıklığına göre ayarlanmasını ve grup içindeki bireylerin formasyonlarının grup büyüklüğüne göre belirlenebilmesini sağlayacak yeniliklere sahiptir.

Keywords

Kalabalık benzetimi, küçük gruplar, yönlendirmesiz, doğrusal çarpışmasız gezinge, ambiyans kabalığı

References

• [1] Yang, S., Li, T., Gong, X., Peng, B., & Hu, J., “A review on crowd simulation and modeling”, Graphical Models, 111: 101081, (2020)
• [2] Musse, S. R., Cassol, V. J., & Thalmann, D., “A history of crowd simulation: the past, evolution, and new perspectives”, The Visual Computer, 37: 3077-3092, (2021)
• [3] Van Toll, W., & Pettré, J., “Algorithms for microscopic crowd simulation: Advancements in the 2010s”, Computer Graphics Forum, 40: 731-754, (2021)
• [4] Pelechano, N., Allbeck, J. M., Kapadia, M., & Badler, N. I. “Simulating heterogeneous crowds with interactive behaviors”, A K Peters/CRC Press, 9781315370071, New York, (2016)
• [5] Beacco, A., Pelechano, N., & Andújar, C., “A survey of real‐time crowd rendering”, Computer Graphics Forum, 35: 32-50, (2016)
• [6] Dobbyn, S., Hamill, J., O'Conor, K., & O'Sullivan, C., “Geopostors: a real-time geometry/impostor crowd rendering system”, Symposium on Interactive 3D Graphics and Games, Washington, 95-102, (2005)
• [7] Ahn, J., Oh, S., & Wohn, K., “Optimized motion simplification for crowd animation”, Computer Animation and Virtual Worlds, 17: 155-165, (2006)
• [8] Toledo, L., De Gyves, O., & Rudomín, I., “Hierarchical level of detail for varied animated crowds”, The Visual Computer, 30: 949-961, (2014)
• [9] Kulpa, R., Olivierxs, A. H., Ondřej, J., & Pettré, J., “Imperceptible relaxation of collision avoidance constraints in virtual crowds”, ACM Transactions on Graphics, 30: 1-10, (2011)
• [10] Paris, S., Gerdelan, A., & O’Sullivan, C., “Ca-lod: Collision avoidance level of detail for scalable, controllable crowds”, 2nd International Workshop on Motion in Games, Zeist, 13-28, (2009)
• [11] Barut, Ö., Hacıömeroğlu, M., & Özcan, C., “Illusive crowd”, International Conference on Computer Animation and Social Agents, Houston, 1-4, (2014)
• [12] Barut, O., & Haciomeroglu, M., “Real-time collision-free linear trajectory generation on GPU for crowd simulations”, The Visual Computer, 31: 843-852, (2015)
• [13] Barut, O., Haciomeroglu, M., & Sezer, E. A., “Combining GPU-generated linear trajectory segments to create collision-free paths for real-time ambient crowds”, Graphical Models, 99: 31-45, (2018)
• [14] James, J., “The distribution of free-forming small group size”, American Sociological Review, 18: 569-570, (1953)
• [15] Aveni, A. F., “The not-so-lonely crowd: Friendship groups in collective behavior”, Sociometry, 40: 96-99, (1977)
• [16] Singh, H., Arter, R., Dodd, L., Langston, P., Lester, E., & Drury, J., “Modelling subgroup behaviour in crowd dynamics DEM simulation”, Applied Mathematical Modelling, 33: 4408-4423, (2009)
• [17] Moussaïd, M., Perozo, N., Garnier, S., Helbing, D., & Theraulaz, G., “The walking behaviour of pedestrian social groups and its impact on crowd Dynamics”, PLOS One, 5: 1-7, (2010)
• [18] Ge, W., Collins, R. T., & Ruback, R. B., “Vision-based analysis of small groups in pedestrian crowds”, IEEE Transactions on Pattern Analysis and Machine Intelligence, 34: 1003-1016, (2012)
• [19] Kapadia, M., & Badler, N. I., “Navigation and steering for autonomous virtual humans”, Wiley Interdisciplinary Reviews: Cognitive Science, 4, 263-272, (2013)
• [20] Reynolds, C. W., “Flocks, herds and schools: A distributed behavioral model”, Conference on Computer Graphics and Interactive Techniques, Anaheim, 25-34, (1987)
• [21] Reynolds, C. W., “Steering behaviors for autonomous characters”, Game Developers Conference, California, 763-782, (1999)
• [22] Helbing, D., & Molnar, P., “Social force model for pedestrian Dynamics”, Physical review E, 51: 4282-4286, (1995)
• [23] Helbing, D., Farkas, I., & Vicsek, T., “Simulating dynamical features of escape panic”, Nature, 407, 487-490, (2000)
• [24] Van den Berg, J., Lin, M., & Manocha, D., “Reciprocal velocity obstacles for real-time multi-agent navigation”, IEEE International Conference on Robotics and Automation, Pasadena, 1928-1935, (2008)
• [25] Van Den Berg, J., Guy, S. J., Lin, M., & Manocha, D., “Reciprocal n-body collision avoidance”, International Symposium of Robotics Research, Lucerne, 3-19, (2011)
• [26] Ondřej, J., Pettré, J., Olivier, A. H., & Donikian, S., “A synthetic-vision based steering approach for crowd simulation”, ACM SIGGRAPH, Los Angeles, 1-9, (2010)
• [27] Dutra, T. B., Marques, R., Cavalcante‐Neto, J. B., Vidal, C. A., & Pettré, J., “Gradient‐based steering for vision‐based crowd simulation algorithms”, Computer Graphics Forum, 36: 337-348, (2017)
• [28] Hughes, R. L., “A continuum theory for the flow of pedestrians”, Transportation Research Part B: Methodological, 36: 507-535, (2002)
• [29] Treuille, A., Cooper, S., & Popović, Z., “Continuum crowds”, ACM Transactions on Graphics, 25: 1160-1168, (2006)
• [30] Narain, R., Golas, A., Curtis, S., & Lin, M. C., “Aggregate dynamics for dense crowd simulation”, ACM SIGGRAPH Asia, Yokohama, 1-8, (2009)
• [31] Chenney, S., “Flow tiles”, Symposium on Computer Animation, Grenoble, 233-242, (2004)
• [32] Patil, S., Van Den Berg, J., Curtis, S., Lin, M. C., & Manocha, D., “Directing crowd simulations using navigation fields”, IEEE Transactions on Visualization and Computer Graphics, 17: 244-254, (2010)