Department of Computer Science, UNC Chapel Hill

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