Accelerating Line-of-Sight queries for Terrain Processing using Region Based Visibility

We present an efficient algorithm for line-of-sight (LOS) compu-tations in modeling and simulation applications. LOS queries are solved by performing point-to-point visibility computations in com-plex environments with moving entities. Our approach divides the environment into regions and uses region based visibility calcula-tions to compute region-to-region visibility as a visibility table for each region. This table indicates portions of the environment that are definitely blocked from any point within a region. When an-swering an LOS query we examine visibility tables of the regions containing the endpoints. If the portions of the environment con-taining the endpoints are blocked from each other according to the RBV computation then we do not need to perform a ray cast test. We have implemented our algorithm and have demonstrated its per-formance on terrain and urban environments. We observe more than three times speedup based on our region based visibility implemen-tation