Parallel algorithm for multi-viewpoint viewshed analysis on the GPU grounded in target cluster segmentation

Abstract

ABSTRACTViewshed analysis is a significant method for GIS spatial analysis. The needed computational resources rise sharply with the increase in the number of viewpoints, making viewshed analysis inefficient in multi-viewpoint scenes. Building on the shadow map algorithm, a parallel algorithm for multi-viewpoint viewshed analysis based on target cluster segmentation for large-scale, multi-viewpoint complex three-dimensional scenes was proposed. Target cluster segmentation was achieved using uniform grid division and K-means spatial clustering, and visibility was determined by comparing the depths. The customized graphics processing unit (GPU) rendering pipeline was adopted to execute the algorithm efficiently and in parallel. The experimental results indicated that the efficiency of the proposed algorithm improves by 6.252%, 8.280%, and 9.047% on average for viewshed analysis with 150, 300, and 600 viewpoints, respectively, compared to the algorithm based solely on shadow map. It is also able to eliminate the majority of shadow acne, thus clearly improving accuracy. The algorithm is compatible with the terrain and features while fully utilizing the parallel computational capability of the GPU and avoiding the interpolation of the digital elevation model (DEM). It significantly improves the efficiency of analysis in large-scale and multi-viewpoint scenes.

Keywords

• shadow map
• uniform grid division
• K-means
• fragment shader
• GPU rendering pipeline