Streaming Computation of Delaunay Triangulations

Martin Isenburg      Yuanxin (Leo) Liu      Jonathan Shewchuk      Jack Snoeyink

abstract:
We demonstrate how algorithms to compute Delaunay triangulations for large, well-distributed data sets in 2D and 3D can be greatly accelerated by exploiting the natural spatial coherence in a stream of points. We introduce spatial finalization for point streams: we partition the bounding box into regions, and augment the stream of input points with finalization tags that indicate when a point is the last in its region. By extending an incremental algorithm for Delaunay triangulation to use finalization tags and produce streaming mesh output, we compute a billion-triangle terrain representation for the Neuse River system from 11.2 GB of LIDAR data in 48 minutes using only 70 MB of memory on a laptop.

main contributions:

  • streaming, out-of-core, I/O and memory efficient Delaunay triangulation in 2D and 3D
  • spatial finalization of points (without global reordering)
  • scalability to gigantic inputs and outputs (billions of points -> billions of triangles)
  • data-driven computation: points are processed from any (reasonably coherent) input order
  • computations avoid use of slow external memory (i.e. the disk is used exclusively for input and output)
  • no special hardware required: we process tens of gigabytes on a household laptop
  • fastest triangulation code available, even for small data sets (faster than Triangle and Pyramid)
  • streaming mesh output for immediate consumption by another stream processing module
  • implementation available on request (built upon exact arithmetic)
  • the only way to make your laptop turn 0.5 billion points into 1 billion triangles while you are gone for a coffee

  • building upon Streaming Delaunay:
    We describe how to put our streaming Delaunay triangulator to good use and extract high-resolution iso-contour elevation lines from densely spaced points that sample the elevation of a terrain (e.g. LIDAR or IFSAR data) using significantly less memory than the processed input points and the produced output lines. By keeping point, mesh, and line data in streaming formats containing ``finalization tags,'' we connect individual batch operations into a streaming processing pipeline that instantly begins producing final iso-contour output.

    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.
  • [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.
  • [ilss-lidar2iso-06.pdf] Martin Isenburg, Yuanxin Liu, Jack Snoeyink, Streaming Extraction of Elevation Contours from LIDAR points, draft, april 2006.
  • download: (updated on july 13th, 2007)

  • source code and streaming point API: sp_api.zip (16 MB) README_2D.TXT README_3D.TXT
  • video: sd_video.avi (40 MB) (+ DivX codec)
  • slides: sd.ppt (6 MB) (+ 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.

    acknowlegements:
    Special thanks go to Kevin Yi of Duke's STREAM project for providing us literally overnight ftp access to the 12 GB of point data of the Neuse River Basin. Their project takes an alternate approach based on I/O efficient external memory algorithms to process large terrains.