GPU-accelerated terrain processing

This thesis extends Overdetermined Laplacian Partial Differential Equations (ODETLAP) for spatial data approximation and compression and parallelizes multiple observer siting on terrain, using General-Purpose Computing on Graphics Processing Units (GPGPU). Both ODETLAP compression and multiple observer siting use greedy algorithms that are parallelizable within iterations but sequential between iterations. They also demonstrate terrain-related research and applications that benefit from GPU acceleration and showcase the achievable speedups. ODETLAP approximation approximates a spatial dataset from scattered data points on a regular grid by solving an overdetermined system of linear equations that minimizes the absolute Laplacian of the approximation and the value errors of the data points. We show that ODETLAP approximation is a linear operator and is comparable in accuracy with natural neighbor interpolation and the multiquadric-biharmonic method. Using ODETLAP approximation to approximate spatial datasets, ODETLAP compression compresses a dataset as a set of known points and their values and decompresses it as an approximation from the known points. We implement ODETLAP approximation and compression using the CUSP library and the speedup is 8 times on a GPU. We design multiple algorithms to improve the accuracy of ODETLAP compression using a limited number of known points and use them to compress 2D terrain datasets and 3D MRI datasets. The results show that ODETLAP compression is 30% to 50% better in minimizing the maximum absolute error than JPEG 2000 for the terrain datasets and 40% to 60% better than JP3D for the MRI datasets. To further increase speed, we design a segmented ODETLAP compression algorithm and use it to compress larger 3D atmospheric and MRI datasets. The results show that the compressed size of the dataset is 60% that of JP3D for the same maximum absolute error. Multiple observer siting places multiple observer points above a terrain to maximize the total area visible from at least one observer. The algorithm first selects a set of highly visible points as tentative observers, and then iteratively selects observers to maximize the cumulative viewshed. We improve the time and space complexities of the algorithm and parallelize it using CUDA on a GPU and using OpenMP on multi-core CPUs. The speedup is up to 60 times on the GPU and 16 times on two CPUs with 16 cores.