Yi Zhuang spent the summer of 2006 at Bowdoin as a Kibbe Undergraduate Research Fellow. He worked with Professor Laura Toma on I/O-efficient visibility computation on grid terrains.
The goal of the project was the computation of one of the basic visibility problems: the viewshed (or visibility map) of an observer, that is, the set of points on the terrain that are visible to the observer. Two points on the terrain are called visible if the segment between the two points does not intersect the terrain. On grid terrains the viewshed is represented as a binary grid, that is, a grid where each cell is labeled as visible or not.
The viewshed computation has many practical applications and helps answer questions such as: How to situate infrastructure, such as pipelines and highways, in out-of-the way places that do not destroy the quality of natural scenery? Where to site transmission towers to avoid spatial gaps in reception? How to characterize regions under surveillance (or not under surveillance)? GRASS, the open source GIS, provides a module for the viewshed computation named r.los.
As technology develops, the amount of data we have about our globe increases rapidly. For example, NASA’s Shuttle Radar Topography Mission (SRTM) acquired 30m terrain data in 2002, in total about 10 terrabytes of data. When working with massive data, only a fraction of the data can be held in the main memory of a computer, while the rest resides on disk. But, accessing the disk is several orders of magnitude slower than accessing internal memory; thus, when processing very large datasets, the transfer of data between main memory and disk, rather than the internal memory computation, is usually the performance bottleneck.
This project developed a simple and practical algorithm for viewshed computation on very large grids. Two approaches are known for the viewshed computation: Given a viewpoint V, the straightforward approach iterates through all the cells that could intersect the segment VW, for every cell W on the grid. This algorithm has been improved using plane sweeping, a technique frequently used in geometric algorithms. However, none of these two algorithms is designed to be efficient on large datasets. Our experiments showed that both algorithms break down (become extremely slow) when dealing with datasets that exceed main memory capacity.
This project proposes a new, I/O-efficient algorithm for viewshed computation on very large terrains. Given a viewpoint v, the main idea of the new algorithm is to partition the grid into small strips (sectors) around v, and find the viewshed of v in each strip, recursively. When a strip becomes small enough to fit in internal memory, the recursion stops and the whole strip is loaded in memory and solved. Once the algorithm is finished looking at each strip individually, it can piece together the results to solve the problem as a whole. The most difficult part of the algorithm is the process by which the grid is divided into small strips that fit into main memory—some cells, especially the ones close to the observer, may fall into many strips and need to be included in all the corresponding sub-problems. This would cause a single cell to be processed many times, significantly decreasing the efficiency of the algorithm. In this project, we found a way to remove such cells (cells that span multiple strips) out of the sub-problems.
During summer 2006, the aforementioned algorithms were implemented and an experimental analysis was performed to compare efficiency of the various approaches, including the r.los module in GRASS. The I/O-efficient algorithm significantly outperforms all other approaches on large inputs; it runs faster and can handle much larger data sets—it handled a 4GB grid in a few hours on a low-cost machine. The results were presented at ALENEX 2007.
A PDF of the paper is available from the conference website:
Proceedings of the Ninth Workshop on Algorithm Engineering and Experiments
Computing Visibility on Terrains in External Memory »