Natural neighbor interpolation based grid DEM construction using a GPU


Journal Article

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 high-resolution grid with 150 million cells from two billion points in less than thirty-seven minutes. This is about one-tenth of the time required for the same computer to perform a standard linear interpolation, which produces a much less smooth surface. © 2010 ACM.

Full Text

Duke Authors

Cited Authors

  • Beutel, A; Mølhave, T; Agarwal, PK

Published Date

  • December 31, 2010

Published In

  • Gis: Proceedings of the Acm International Symposium on Advances in Geographic Information Systems

Start / End Page

  • 172 - 181

Digital Object Identifier (DOI)

  • 10.1145/1869790.1869817

Citation Source

  • Scopus