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.