|
||||||||||||||||
|
Ph.D. ThesesGPU-Accelerated Terrain Processing
By Wenli Li
This thesis extends Overdetermined Laplacian Partial Differential Equations (ODETLAP) for spatial data approximation and compression, and optimizes multiple observer siting on terrain, accelerated by General-Purpose Computing on Graphics Processing Units (GPGPU). Both ODETLAP compression and multiple observer siting use greedy algorithms that are parallelizable within iterations but are sequential between iterations. They demonstrate terrain-related research and applications that benefit from GPU acceleration and the speedups that are achievable by GPU acceleration. ODETLAP approximation is for scattered data approximation on a grid. It works by solving an overdetermined system of linear equations that maximizes the smoothness of the approximation and minimizes the approximation error of data points. We showed that ODETLAP approximation is a linear operator and is comparable in accuracy with natural neighbor interpolation and the multiquadric-biharmonic method. ODETLAP compression is for the compression of spatial datasets using ODETLAP approximation. A dataset is compressed as a set of points and point values and decompressed as an ODETLAP approximation from them. We designed multiple algorithms to improve the accuracy of ODETLAP compression and compared its performance with JPEG 2000 and JP3D to show its advantage in minimizing the maximum error for 2D and 3D datasets. We implemented ODETLAP approximation using the CUSP library for GPU acceleration and achieved about 8 times speedup. Multiple observer siting is for the placement of multiple observer points above a terrain, to maximize the total area that is visible from at least one observer. The algorithm first selects a large set of observers as candidates, and then iteratively selects an observer that maximizes the total visible area from the candidates. We improved the time and space complexities of the algorithm and parallelized it for GPU acceleration using the CUDA API, achieving about 30 times speedup.
|
||||||||||||||||
Research
