Parallel viewshed extraction on multiresolution terrains
Michael Selvaggio, Andrew Danner
Swarthmore College
The viewshed is the set of all points visible on a 2D grid of elevations T from a given viewpoint. We worked to parallelize existing viewshed algorithms by exploiting the processing power of the GPU using CUDA. We focused on modifying the multiresolution horizon-based viewshed algorithm so that it would work in parallel in the hopes of reducing runtime. Horizon based viewshed algorithms work by scanning the horizon in layers outward around the viewpoint, saving a copy of the horizon in totalHorizon which is continually updated. The multiresolution algorithm uses this algorithm, but adds an additional layer of abstraction: Given a block size b, it creates a grid T’ containing blocks that each represent b2 points on T. The algorithm then generates a viewshed for T’, marking each block in T as visible or invisible. Each point in a block marked invisible is guaranteed to be invisible in the viewshed of T. Thus, when computing the high resolution viewshed, the algorithm skips checking the visibility of any point guaranteed to be invisible, saving significant computation time.
We analyzed the most costly parts of this algorithm and chose to parallelize the functions ComputeVisibility() and MergeHorizons(). ComputeVisibility() computes the visibility of each point in a layer. We modified this function such that the visibility of each point in a layer could be computed simultaneously, without depending on the results of the other points in the layer. Furthermore, we restructured MergeHorizons(), the function that combines new horizons with totalHorizon, to divvy up its work among different threads on the GPU. Our version of ComputeVisibility() is about 4 times faster than the previous version, but our version of MergeHorizons() is about 5 times slower.
Overall, our algorithm is slower than the pre-existing algorithm, but we are still working to further optimize our work. Overhead communicating between the CPU and GPU has been costly, and we are developing workarounds for some of the inconvenient intricacies of CUDA. We have created an environment useful for future research and will continue work on speeding up this algorithm.
