Parallel viewshed analysis on a PC cluster system using triple-based irregular partition scheme

详细信息    查看全文

• 作者：Xiao-Dong Song ; Guo-An Tang ; Xue-Jun Liu ; Wan-Feng Dou…
• 关键词：Viewshed analysis ; Digital elevation model ; Parallel computing ; Scan ; line filling algorithms ; Triples
• 刊名：Earth Science Informatics
• 出版年：2016
• 出版时间：November 2016
• 年：2016
• 卷：9
• 期：4
• 页码：511-523
• 全文大小：2,980 KB
• 刊物类别：Earth and Environmental Science
• 刊物主题：Earth sciences
  Computer Applications in Geosciences
  Geosciences
  Simulation and Modeling
  
• 出版者：Springer Berlin Heidelberg
• ISSN：1865-0481
• 卷排序：9

文摘

Using digital elevation models (DEMs), viewshed analysis algorithms determine the visibility of each point on the terrain at a given location in space. As a data-parallel algorithm, real-time viewshed analysis from grid DEM poses a practical challenge to personal computer (PC) users, particularly when dealing with higher resolution and accuracy of large terrain data. Therefore, this paper presents a universal domain decomposition algorithm based on an equal-area strategy for the parallel viewshed analysis on a PC cluster system. The approach uses a scan-line filling method for data partitioning of the irregular bounding polygon of the terrain. The terrain data are divided into sectors of the same area that are connected by the viewpoint and the region vertices, ignoring the null value (or NODATA) points. Furthermore, each sector is assigned to one processor and is organized in the form of triples composed of location and elevation at one point. An index of triples is built to store all of the locations of terminal vertices row-by-row and thus the random access of any point is achieved by using the offsets in each row. Two commonly applied viewshed algorithms, namely, “reference plane” and “Xdraw” algorithms are employed to verify the performance. In addition, two experiments focus on evaluating the efficiency performance and comparing traditional implementation, respectively. Experimental results demonstrate a significant performance improvement compared with the sequential computing method. The memory usage gradually decreases as the number of processors increases. Based on the equal-area decomposition, partitions in terms of sectors can guarantee a suitable load balance. Additional benefits of the proposed solution also include high storage efficiency and program portability.