Fast Line-of-Sight Computations in Complex Environments

We present an algorithm and implementation for solving the line of sight (point-to-point visibility) problem for simulations with many moving entities. This problem arises in military simulations and can bottleneck such systems. We employ the concept of region based visibility to precompute visibility for the environment. The simulation environment is segmented into regions and a visibility map is constructed for each region. The visibility map indicates portions of the environment that are definitely blocked from any point within a region. Once this computation is performed an entity needs only to perform line of sight ray-cast tests for entities in the unblocked part of its region’s visibility map. Using our implementation on an existing simulation dataset we achieved a three times speedup. 1