A Fast Exact Viewshed Algorithm on GPU

We present a parallel GPU algorithm for computing viewshed using the radial-sweep approach, and we are considering the case of in-memory execution. We compared our algorithm with other three viewshed algorithms: sequential R3, sequential radial-sweep, and parallel GPU-based RI In our experiment, we used a grid of size (10801 x 10801), and our algorithm finished execution in 1.7 seconds and was more than 3.5x faster than GPU-based R3, over 6200x times faster than the standard sequential R3 algorithm, and 1627x times faster than the sequential CPU-based radial-sweep. Viewshed problem or visibility computing is concerned with finding all points or cells that are visible for a giving cell that is called the observer. Processing such a problem for a large grid is very time-consuming using CPU, mainly when producing results with the highest possible accuracy. Thus, in our work, we are proposing a new parallel algorithm for solving the viewshed problem. Our algorithm is based on the radialsweep algorithm, and it is designed to be used on the GPU. The algorithm design has overcome many challenges to enable the parallelization of the radial-sweep algorithm. Challenges such as minimizing the space required by intermediate results used by the algorithm, efficiently sorting the intermediate results, utilizing pre-allocated static data structures instead of dynamic data structures to be more suitable for GPUs, and dividing the problem into chunks to be processed in parallel while maintaining the accuracy of the results to be equivalent to its CPU sequential version.