Points2Grid: A Local Gridding Method for DEM Generation from Lidar Point Cloud Data

Points2Grid is a robust and scalable tool for gridding lidar point cloud data to generate Digital Elevation Models (DEMs). Points2Grid uses a local gridding method to compute grid cell elevation using a neighborhood defined around each cell based on a search radius provided by the user (see image below). Points2Grid offers two processing modes - in-core and out-of-core - to allow it to handle generation of rasters larger than available memory.

Points2Grid is used as the default DEM generation algorithm for the OpenTopography point cloud processing system, and thus been tested through thousands of DEM generation jobs. The local gridding approach employed by Points2Grid is most effective in situations where lidar shot densities exceed the resolution of the grid to be produced from these data.

Points2Grid has been confirmed to compile on Linux, Solaris, and Mac OSX. Use the CRREL fork of P2G below to compile on Windows. Note that an older, no longer supported, version of P2G is currently available as a Windows GUI-based tool: winP2G Utility

Version 1.0.1 of Points2Grid offers the following features:

  • Reads input point clouds in ASCII and LAS formats
  • Outputs grids in Arc ASCII and GRD ASCII formats
  • DEM products including min, max, mean, and idw values
  • Output of point count values for every grid cell
  • User defined search radius and grid resolution
  • Null filling, using a configurable moving window, to fill cells that have null values
  • In-core and out-of-core processing modes to enable generation of grids larger than available memory. The user can define the threshold at which the code switches to out-of-core, based on the memory resources of their machine.

Licensing:

Points2Grid is open source and offered under a 4-clause BSD license.

Source Code Implementations:

  • The original Points2Grid can be downloaded from OpenTopography’s GitHub space at https://github.com/OpenTopography/points2grid
  • The most up-to-date and actively developed version of Points2Grid is the US Army Corps Cold Regions Research and Engineering Lab (CRREL) fork available here: https://github.com/CRREL/points2grid/.
  • The lidar2dems open source utility incorporates P2G for the generation of Digital Terrain Models (DTM), Digtial Surface Models (DSM), and Canopy Height Models (CHM).
  • The P2G algorithm has been integrated directly into the Point Data Abstraction Library (PDAL) as writers.gdal, which enables you to use P2G as part of larger point cloud processing workflows using PDAL, generating raster formats supported by GDAL.

Dependencies:

curl (P2G has been tested to work with version 7.20.0 of libcurl)

liblas (P2G has been tested to work with version 1.2.1 of liblas)

Please direct all feedback to info@opentopography.org

image

Figure above: Illustration of P2G local gridding algorithm and of the geometry of the search radius and DEM. Black dots are actual lidar returns. Red dots in lower left panel have elevations shown. Plus symbols indicate locations of DEM nodes at which elevation is estimated. Each red circle represents a local bin for a particular DEM node. The annotation below indicates the search area and search radii as a function of grid cell area. The DEM values are computed by applying simple mathematical functions on 707 all points that fall within the local bin. Units are arbitrary, but typically are meters. We typically set search radius = grid resolution * sqrt(2) / 2 as shown in the lower left, or search radius = grid resolution as shown in the upper right.

Documentation & Training:

Related Publications:

  • Arrowsmith, J R., and Zielke, O., Tectonic geomorphology of the San Andreas Fault zone from high resolution topography: an example from the Cholame segment, Geomorphology; special issue on high resolution topography, doi:10.1016j.geomorph.2009.01.002, 2009.
  • Kim, H., Arrowsmith, J.R, Crosby, C.J., Jaeger-Frank, E., Nandigam, V., Memon, A., Conner, J., Badden, S.B., and Baru, c., 2006, An efficient implementation of a local binning algorithm for digital elevation model generation of LiDAR-ALSM datasets, Eos (Transactions, American Geophysical Union), Fall Meeting, 2006, Abstract G53C-0921.
  • Krishnan, S., Baru, C., Crosby, C.J., 2010, Evaluation of MapReduce for Gridding LIDAR Data, Proceedings of 2nd IEEE International Conference on Cloud Computing Technology and Science, pp. 33-40.