Simulating Boids with Self Occlusion
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 computing-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. In this article we explored a method to estimate self-occlusion, that is, the possible occlusion caused by a boid in the view of other boids during flight. In this way we can reduce the number of neighbors considered in the computations by discarding boids that would be invisible due to the presence of other boids.
An important characteristic of this model is to determine the neighborhood of each boid. This is normally implemented using a “field of view” that can be described by a maximum viewing distance and viewing angle. Only boids inside this field of view are considered for computing the steering behaviors. We augment this concept of “field of view” to also consider occlusion in order to improve performance when simulating a large number of boids.
An important characteristic of this model is to determine the neighborhood of each boid. This is normally implemented using a “field of view” that can be described by a maximum viewing distance and viewing angle. Only boids inside this field of view are considered for computing the steering behaviors. We augment this concept of “field of view” to also consider occlusion in order to improve performance when simulating a large number of boids.
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. The technique employed in this work can be described as an approximate from-point visibility algorithm. In particular, we approximate visibility based on the volumetric representation of the scene. Instead of performing geometric visibility computations, we compute for each voxel the density of boids and approximate the visibility between regions by computing the volume opacity between them.
Publications:
Improving boids algorithm in GPU using estimated self-occlusion. SILVA, A ; LAGES, W. S. ; CHAIMOWICZ, L. . In: Proceedings of the VII Brazilian Symposium on Games and Digital Entertainment - Computing Track - Full Papers, 2008. p. 41-46.
Boids that see: Using self-occlusion for simulating large groups on GPUs. Silva, Alessandro; LAGES, W. S. ; CHAIMOWICZ, L. ACM Computers in Entertainment, v. 7, p. 51, 2009.
Improving boids algorithm in GPU using estimated self-occlusion. SILVA, A ; LAGES, W. S. ; CHAIMOWICZ, L. . In: Proceedings of the VII Brazilian Symposium on Games and Digital Entertainment - Computing Track - Full Papers, 2008. p. 41-46.
Boids that see: Using self-occlusion for simulating large groups on GPUs. Silva, Alessandro; LAGES, W. S. ; CHAIMOWICZ, L. ACM Computers in Entertainment, v. 7, p. 51, 2009.