LAStools' BLAST extension: Triangulating billions of LiDAR points





The interactive transcript could not be loaded.


Rating is available when the video has been rented.
This feature is not available right now. Please try again later.
Published on Aug 9, 2012

In this academic video from 2006, you hear me describe the technology behind LAStools's efficient BLAST extension that can seamlessly compute gigantic Delaunay triangulations from billions of LiDAR points using very little main memory. The blast2dem.exe module immediately rasters these gigantic TINs into equally massive DEMs and avoids storing these huge triangulations temporarily to disk.

Here is a visualization of our software as it triangulates half a billion terrain points. Less than 100,000 triangles - only those rendered here - are in memory at any time. We immediately output any triangle that is guaranteed to be in the final triangulation, We derive such guarantees from "spatial finalization tags" that we add to the points in a pre-process. These "finalization tags" tells us which areas are free of future points. We implement this in form of an evolving quadtree. Only blue quadtree cells may receive future points.

Standard algorithms need over 36 GB of memory to Delaunay triangulate half a billion points. This exceeds the main memory of most computers - even with compressed data structures. External memory algorithms store data structures that are currently not in use to disk. To avoid thrashing they globally sort the points into a coherent order in a pre-processing step.

Here is such an algorithm operating on Hilbert curve ordered points. 36 Gigabytes of data structure are created and eventually paged out to disk. No results are produced until the end when the 36 GB of temporary data are read from disk and the triangulation is output.

In contrast, our algorithm starts outputting final triangles immediately and then reuses the memory they occupied. Therefore it does not store any data temporarily to disk. Our spatial finalization tags guarantee us that no future point will fall into these red circum-circles; the corresponding triangles can safely be output. Only those triangles whose circum-circles intersect unfinalized space need to be kept in memory.

Our pipeline consists of two simultaneously running processes. The finalizer adds spatial finalization tags to the input points and pipes the result to the triangulator. Our incremental Delaunay triangulator inserts points with the standard locate and update approach. In addition it finds, outputs, and de-allocates triangles whenever a cell's finalization tag is read.

Our streaming pipeline turns 11 GB of double-precision points in 48 minutes into a one-billion-triangle terrain using only 70 MB of memory and no temporary disk space. This is an order of magnitude faster than previous approaches.

Underscoring the scalability of our approach: here we triangulate a 3 by 3 tiling of the Neuse River Basin, that is 4.5 billion points, more than can be counted with 32 bits, in under 7 hours on a failry old Dell Inspiron 6000 laptop (from July 2005) using only 166 MB of memory and no temporary disk space.


When autoplay is enabled, a suggested video will automatically play next.

Up next

to add this to Watch Later

Add to

Loading playlists...