# 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

- DEM file with 50 columns and 30 rows

View Point: Origin (0,0) and Center (25,15) - DEM file with 600 columns and 400 rows

View Point: Origin (0,0) and Center (300,200) - DEM file with 4996 columns and 3088 rows

View Point: Origin (0,0) and Center (2498,1544)

#### 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.68945 | 4941.27588 | 11.742 | 5.521 | 17804.2051 | 17931.9238 | 9206.0273 | 2258.4771 |

DEM3 | 4931812.5 | 2488116.25 | 5325.481 | 2703.309 | Out of Mem | Out of Mem | Out of Mem | Out of Mem |