Generating Raster DEM from Mass Points via TIN Streaming

Martin Isenburg      Yuanxin (Leo) Liu      Jonathan Shewchuk      Jack Snoeyink      Tim Thirion

abstract:
It is difficult to generate raster Digital Elevation Models (DEMs) from terrain mass point data sets too large to fit into memory, such as those obtained by LIDAR. We describe prototype tools for streaming DEM generation that are based on Streaming Delaunay and that use memory and disk I/O very efficiently. From 500 million bare-earth LIDAR double precision points (11.2 GB) our tools can, in just over an hour on a standard laptop with two hard drives, produce a 50,394 x 30,500 raster DEM with 20 foot post spacing in 16 bit binary BIL format (3 GB), using less than 100 MB of main memory and less than 300 MB of temporary disk space.

main contributions:

  • a very fast method to generate gridded Digital Elevation Models (DEMs) from mass points
  • data-driven computation of interpolated elevation values
  • scalability to gigantic inputs and outputs (billions of points -> billions of raster points)
  • no special hardware required: we process tens of gigabytes on a household laptop
  • implementation available on request
  • the only way to make your laptop interpolate and raster 0.5 billion points onto a 50,394 x 30,500 grid while you are gone for a coffee

  • publication:

  • [ilsst-tin2dem-06.pdf] Martin Isenburg, Yuanxin Liu, Jonathan Shewchuk, Jack Snoeyink, Tim Thirion, Generating Raster DEM from Mass Points via TIN Streaming, GIScience'06 Conference Proceedings, pages 186-198, September 2006.
  • related publications:

  • [ilss-scdt-06.pdf] Martin Isenburg, Yuanxin Liu, Jonathan Shewchuk, Jack Snoeyink, Streaming Computation of Delaunay Triangulations, Proceedings of SIGGRAPH'06, pages 1049-1056, July 2006.
  • [ilss-lidar2iso-06.pdf] Martin Isenburg, Yuanxin Liu, Jack Snoeyink, Streaming Extraction of Elevation Contours from LIDAR points, draft, april 2006.
  • downloads: (updated on October 17th, 2007)

  • source code: sp_api.zip sm_api.zip sl_api.zip
  • slides: tin2dem.ppt (+ DivX codec for vids)
  • streaming delaunay demo: sd_demo.zip (11 MB)
  • lidar points to elevation contours demo: lidar2iso_demo.zip (47 MB)
  • You may use the binaries and source code for non-commerical purposes only.