GPU Acceleration Techniques Integrated Into OneSAF

Region Based Visibility Line of Sight

Our previous GPU/CPU hybrid LOS system used the GPU to remove queries with definite line of sight. A conservative rasterization of the terrain and line segments representing LOS queries determined which queries passed above the terrain. Such queries had definite LOS and do not need further computation. This system reduced the workload of CPU which resolved the LOS of the non-culled queries using ray-casting. Our new region-based method layers on top of this system to further reduce both GPU and CPU workload by culling away queries between regions where there is no possible LOS.

A preprocess performs the spatial subdivision of the environment and the cell-to-cell visibility computations. Determining the visibility between two cells exactly is computationally intensive. Instead, our algorithm uses a conservative approximation that detects most cell pairs for which all LOS queries are blocked. Queries not resolved by the visibility table are tested using our previous GPU/CPU technique to ensure that the correct LOS result is always returned.

Figure 1: Visibility between cell 1 and cell 2. No visibility between cell 1 and cell 3.

Figure 2: After we determine the region for Entity A and Entity B we can look those two regions up in the visibility table. If there is possible visibility we can employ the visibility culling done in our previous LOS algorithm. Any LOS calls that are not culled by both techniques will default to an exact test on the CPU.

Figure 3: In this simulated urban environment the white square represents an entity. The green squares represent entities with LOS. The red squares represent entities without LOS.

Figure 4: This is a graphic representation of visibility between the selected region in white the non-visible regions in red, and the partially visible regions in green. No LOS queries are performed between the selected entity and entities in the red region.

©2003 Department of Computer Science, UNC Chapel Hill