Viewshed GPU

Viewshed identifies the cells in an input raster that can be seen from one or more view points.

  • The raster stands for a DEM file. Each cell represents a point in the map, which holds a value of elevation. The whole raster can be considered as an elevation matrix.
  • A ray is created from the view point to a cell. Traverse all the cells to create rays. Do the visibility analysis for all the cells passed by one ray.

The problem can be divided into two layered components, matrix traversal and ray traversal. Both components can be implemented in parallel (CUDA) or sequential (iteration). There are four combinations for the respective algorithm.

Four Algorithms

Sequential Matrix Traversal, Sequential Ray Traversal (SMSR)

 // Iteration, traverse all the cells except the observer point itself
 For each ray created between observer point and each cell in matrix
     // Iteration, traverse from the nearest to the furthest to the observer point
     For each cell passed by one ray {
         // Get the elevation angle of the line between observer point and cell
         getAngle(cell);
         If (this angle > the maximum angle of the cells nearer to observer) { 
             visibility[cell] = true;
             maximum angle = this angle;
         }
     }

Parallel Matrix Traversal, Sequential Ray Traversal (PMSR)

 // Parallel, traverse all the cells except the observer point itself
 Each thread in GPU creates one ray between observer point and one cell in matrix
     // Iteration, traverse from the nearest to the furthest to the observer point
     For each cell passed by one ray {
         // Get the elevation angle of the line between observer point and cell
         getAngle(cell);
         If (this angle > the maximum angle of the cells nearer to observer) { 
             visibility[cell] = true;
             maximum angle = this angle;
         }
     }

The PMSR's “sequential ray traversal” algorithm is based on the NVIDIA SDK's “lineOfSight” project.

Sequential Matrix Traversal, Parallel Ray Traversal (SMPR)

 // Iteration, traverse all the cells except the observer point itself
 For each ray created between observer point and each cell in matrix {
     // Parallel
     Calculate the angles of all the cells passed by one ray
    
     // Parallel, scan from the nearest to the furthest to the observer point
     // Put the maximum angle ever scanned to each element of the array
     Perform a max-scan on the calculated angles of the cells passed by one ray
 
     // Parallel
     // If angle_array[i] == max-scan_array[i], the cell is visible
     Compare each element in the same position of angle array and its max-scan array
 }

The SMPR's “parallel ray traversal” algorithm is based on the NVIDIA SDK's “lineOfSight” project.

Parallel Matrix Traversal, Parallel Ray Traversal (PMPR)

 // Parallel, traverse all the cells passed by all the rays
 Calculate the angles of all the cells passed by all the rays

 // Parallel, traverse all the rays 
 // For each ray, scan from the nearest to the furthest to the observer point
 // For each ray, put the maximum angle ever scanned to each element of the array
 For all the rays, perform a max-scan on the calculated angles of the cells passed by each ray

 // Parallel, traverse all the rays
 // For each ray, if angle_array[i] == max-scan_array[i], the cell is visible
 For all the rays, compare each element in the same position of angle array and its max-scan array of each ray

Tests

Test Cases

Results

Unit: milliseconds

SMSR PMSR SMPR PMPR
Origin Center Origin Center Origin Center Origin Center
DEM1 4.482 2.325 0.16 0.112 107.4 107.995 0.64 0.336
DEM2 9064.689454941.27588 11.742 5.521 17804.205117931.92389206.0273 2258.4771
DEM3 4931812.5 2488116.25 5325.481 2703.309 Out of MemOut of MemOut of MemOut of Mem