Parallel algorithm for multi-viewpoint viewshed analysis on the GPU grounded in target cluster segmentation
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 mu...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Taylor & Francis Group
2024-12-01
|
| Series: | International Journal of Digital Earth |
| Subjects: | |
| Online Access: | https://www.tandfonline.com/doi/10.1080/17538947.2024.2308707 |
| _version_ | 1827373797903171584 |
|---|---|
| author | Tianren Xiao Jiqiu Deng Chengfeng Wen Qiqi Gu |
| author_facet | Tianren Xiao Jiqiu Deng Chengfeng Wen Qiqi Gu |
| author_sort | Tianren Xiao |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-03-08T11:21:40Z |
| format | Article |
| id | doaj.art-a1e41c1cfb1842b392e3f8cbe069007e |
| institution | Directory Open Access Journal |
| issn | 1753-8947 1753-8955 |
| language | English |
| last_indexed | 2024-03-08T11:21:40Z |
| publishDate | 2024-12-01 |
| publisher | Taylor & Francis Group |
| record_format | Article |
| series | International Journal of Digital Earth |
| spelling | doaj.art-a1e41c1cfb1842b392e3f8cbe069007e2024-01-26T07:52:15ZengTaylor & Francis GroupInternational Journal of Digital Earth1753-89471753-89552024-12-0117110.1080/17538947.2024.2308707Parallel algorithm for multi-viewpoint viewshed analysis on the GPU grounded in target cluster segmentationTianren Xiao0Jiqiu Deng1Chengfeng Wen2Qiqi Gu3Key Laboratory of Metallogenic Prediction of Nonferrous Metals and Geological Environment Monitoring, Central South University, Ministry of Education, Changsha, People’s Republic of ChinaKey Laboratory of Metallogenic Prediction of Nonferrous Metals and Geological Environment Monitoring, Central South University, Ministry of Education, Changsha, People’s Republic of ChinaKey Laboratory of Metallogenic Prediction of Nonferrous Metals and Geological Environment Monitoring, Central South University, Ministry of Education, Changsha, People’s Republic of ChinaKey Laboratory of Metallogenic Prediction of Nonferrous Metals and Geological Environment Monitoring, Central South University, Ministry of Education, Changsha, People’s Republic of ChinaABSTRACTViewshed 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.https://www.tandfonline.com/doi/10.1080/17538947.2024.2308707shadow mapuniform grid divisionK-meansfragment shaderGPU rendering pipeline |
| spellingShingle | Tianren Xiao Jiqiu Deng Chengfeng Wen Qiqi Gu Parallel algorithm for multi-viewpoint viewshed analysis on the GPU grounded in target cluster segmentation International Journal of Digital Earth shadow map uniform grid division K-means fragment shader GPU rendering pipeline |
| title | Parallel algorithm for multi-viewpoint viewshed analysis on the GPU grounded in target cluster segmentation |
| title_full | Parallel algorithm for multi-viewpoint viewshed analysis on the GPU grounded in target cluster segmentation |
| title_fullStr | Parallel algorithm for multi-viewpoint viewshed analysis on the GPU grounded in target cluster segmentation |
| title_full_unstemmed | Parallel algorithm for multi-viewpoint viewshed analysis on the GPU grounded in target cluster segmentation |
| title_short | Parallel algorithm for multi-viewpoint viewshed analysis on the GPU grounded in target cluster segmentation |
| title_sort | parallel algorithm for multi viewpoint viewshed analysis on the gpu grounded in target cluster segmentation |
| topic | shadow map uniform grid division K-means fragment shader GPU rendering pipeline |
| url | https://www.tandfonline.com/doi/10.1080/17538947.2024.2308707 |
| work_keys_str_mv | AT tianrenxiao parallelalgorithmformultiviewpointviewshedanalysisonthegpugroundedintargetclustersegmentation AT jiqiudeng parallelalgorithmformultiviewpointviewshedanalysisonthegpugroundedintargetclustersegmentation AT chengfengwen parallelalgorithmformultiviewpointviewshedanalysisonthegpugroundedintargetclustersegmentation AT qiqigu parallelalgorithmformultiviewpointviewshedanalysisonthegpugroundedintargetclustersegmentation |