GPU Acceleration Techniques Integrated Into OneSAF

Line of Sight

We have developed several algorithms for performing line-of-sight queries in simulator systems. Our first approach is a hybrid GPU/CPU algorithm. The GPU culls away queries that have definite line of sight using occlusion queries to determine that the entire entity-to-entity ray lies above the terrain while remaining conservative. Queries which do not pass this test are finalized with a CPU raycast test which may easily be parallelized. This algorithm has been successfully integrated into the OneSAF simulator being developed by SAIC.

Overview of GPU-CPU Hybrid LOS Algorithm

Quickly cull queries with definite LOS using the GPU

Hybrid approach to perform exact CPU ray-casting tests

Load balancing between CPU and GPU

Evaluate LOS query in 4-7 usec in urban terrains

Upto 200X speedup of LOS calls in OneSAF

Figure 1: Line of sight is a simple query that determines whether there is an unobstructed view of one entity from another. In this figure the entities on the left do have line of sight while those on the right do not.

Figure 2: A Minkowski sum is used when rendering the terrain to ensure that depth values generated conservatively bound the maximum height of the terrain

Figure 3: By batching LOS queries we are able to hide the latency of GPU occlusion queries and utilize the CPU and GPU simultaneously. While one batch is culled, the non-culled queries from the previous batch are processed by the CPU.

©2003 Department of Computer Science, UNC Chapel Hill