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.