Project 1 Optimization of GIS applications

Objective

Geographic information systems (GIS) are computer systems for managing, analyzing, and displaying geographic information and data. GIS can show many different kinds of data on one map. This enables users to more easily see, analyze, and understand geographic patterns and relationships.

In Geographic Information System, Viewshed Analysis deals with identifying the viewshed, the area that is visible (on the base terrain surface) from a given location. The analysis uses the elevation value of each cell of the digital elevation model (DEM) to determine visibility to or from a particular cell. A viewshed is created from a DEM by using an algorithm that estimates the difference of elevation from one cell (the viewpoint cell) to the next (the target cell). To determine the visibility of a target cell, each cell between the viewpoint cell and target cell is examined for line of sight. Where cells of higher value are between the viewpoint and target cells the line of sight is blocked. If the line of sight is blocked then the target cell is determined to not be part of the viewshed. If it is not blocked then it is included in the viewshed.

The Marching Cubes algorithm is a method for creating a 3D surface mesh from a set of scalar values defined on a 3D grid. The algorithm was developed in 1987 by William E. Lorensen and Harvey E. Cline.This algorithm can generate 3D terrain models from digital elevation data. By converting elevation data into a 3D grid, the algorithm can be applied to generate a surface mesh that accurately represents the terrain.The resulting 3D terrain models can be used in visualization of landscapes and terrain features, flood modeling and analysis, terrain analysis for planning and development, urban planning etc. The Marching Cubes algorithm works by dividing the volume into small cubes, each of which is then classified based on the scalar values at its eight corners. For example, if the scalar values at the corners of a cube are all above a certain threshold, the cube is classified as "solid"; if they are all below the threshold, the cube is classified as "empty"; and if some corners have values above the threshold and some have values below, the cube is classified as "ambiguous". Once each cube has been classified, a surface is generated by connecting the vertices of each cube that lie on the edges where the cube transitions from "solid" to "empty" or from "empty" to "solid". This results in a set of triangles that approximate the surface of the object defined by the scalar values.

1. Implement Viewshed Analysis Algorithms (R3 and R2)
2. Implement Cube Marching Algorithm for Contour Generation
3. Implement various optimization techiques to enhance the performance of R3, R2 and Cube Marching algorithms.
4. Design suitable GUI which help user to select DEM image and other parameters and displays results.

Evaluation Guidelines:

• Implementation: Implementation of Viewshed Analysis Algorithms (R2 and R3) with various GPU optimizations along with GUI.
  main
|-kernels
|-dataset
|-evaluation
• Project Report: Design a detailed report documenting the algorithms, the optimizations used for CUDA kernel operations and experimental results for collection of DEM images.
• Project Presentation: Design a detailed presentation describing the algorithms and experimental observations

Reference Papers

1. Franklin, Wm Randolph, Clark K. Ray, and Shashank Mehta. "Geometric algorithms for siting of air defense missile batteries." Research Project for Battle 2756 (1994).
2. Gao, Yong, et al. "Optimization for viewshed analysis on GPU." 2011 19th International Conference on Geoinformatics. IEEE, 2011.
3. Lorensen, William E., and Harvey E. Cline. "Marching cubes: A high resolution 3D surface construction algorithm." ACM siggraph computer graphics 21.4 (1987): 163-169.