Math @ Duke

Publications [#235531] of Pankaj K. Agarwal
Papers Published
 Beutel, A; Mølhave, T; Agarwal, PK, Natural neighbor interpolation based grid DEM construction using a GPU,
GIS: Proceedings of the ACM International Symposium on Advances in Geographic Information Systems
(2010),
pp. 172181 [doi]
(last updated on 2018/06/24)
Abstract: With modern LiDAR technology the amount of topographic data, in the form of massive point clouds, has increased dramatically. One of the most fundamental GIS tasks is to construct a grid digital elevation model (DEM) from these 3D point clouds. In this paper we present a simple yet very fast algorithm for constructing a grid DEM from massive point clouds using natural neighbor interpolation (NNI). We use a graphics processing unit (GPU) to significantly speed up the computation. To handle the large data sets and to deal with graphics hardware limitations clever blocking schemes are used to partition the point cloud. For example, using standard desktop computers and graphics hardware, we construct a highresolution grid with 150 million cells from two billion points in less than thirtyseven minutes. This is about onetenth of the time required for the same computer to perform a standard linear interpolation, which produces a much less smooth surface. © 2010 ACM.


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

