Pipelining streaming points, triangles, and lines

3DPVT submission by Martin Isenburg, Yuanxin (Leo) Liu, and Jack Snoeyink.

This paper emphasizes the pipeline processing capability going from points to contour maps and getting rapid visualizations thanks to finalization. -- JackSnoeyink - 15 Mar 2006

Points to DEM conversion

GIScience submission by Martin Isenburg, Peter Lindstrom, Yuanxin (Leo) Liu, Jonathan Shewchuk, and Jack Snoeyink.

"spatial streaming" and "topological streaming" allows us to pipeline the processing of large data sets through computers with far less memory than the data set size. We can now take 500million bare-earth LIDAR points, compute a TIN, then turn it into a raster DEM in just over an hour on a laptop.

-- JackSnoeyink - 07 Mar 2006

Streaming points

Siggraph submission by Martin Isenburg, Yuanxin (Leo) Liu, Jonathan Shewchuk, and Jack Snoeyink.

Martin pointed out that the key to streaming is finalization: if you know when you are done with something, then you can write it as output and free up its memory. Thus, to stream meshes, we output triangles as soon as the vertices are available, and finalize vertices as soon as all of their triangles have been output. To stream points we can finize regions of space in which no more points will appear. This allows algorithms that compute local properties (such as the Delaunay triangulation's empty circles) to finalize their output.

Martin implemented this using a grid / adaptive quadtree for the regions, and incremental Delaunay as the construction algorithm. We assume that we know (or do two passes over the data to compute) a bounding box and the numbers of points in grid cells. We then have a finalizer that buffers points in grid cells, sprinkling a few ahead (a la BRIO http://www.cs.ucdavis.edu/~amenta/pubs/brio.pdf). When the last point is seen in a cell, then the points buffered there are sent to the Delaunay triangulator, along with a tag that the cell is finalized. The Delaunay inserts the points, and finalizes the region--outputting all triangles whose circumcircles no longer touch unfinalized space. Circles block on unfinalized regions that they touch; when a region is finalized, it finds new blocking regions for all circumcircles that were blocking on it.

We can do 500 million points (12GB) in under an hour with under 100 MB of memory on a laptop, producing a 1 billion triangle streaming mesh (24 GB). (brief AVI video)

-- JackSnoeyink - 07 Feb 2006

Older ideas...

The idea of streaming computation, as outlined in StreamingCompression, is that the data structure be organized so that a large mesh structure can be accessed seamlessly by a fixed traversal while keeping only a small boundary between the visited and unvisited portions in memory at any time.

A common way to construct a terrain model from irregularly sampled data points is to compute the DelaunayTessellation. I would like to be able to do this without first reading all the data into memory, and produce the output in a streaming format.

-- JackSnoeyink - 03 Feb 2005

One simple idea to do this is to process a queue of events sorted by their y coordinates: an event can either be a site to be inserted or the lowest point of a Delaunay circle. When it is a site event, do the incremental update; otherwise, declare the triangle corresponding to the Delaunay circle as "completed" and gives it to the streaming encoder, since it will be no longer in conflict with any sites not processed.

The events we are processing here are exactly those used by Fortune's sweep line Voronoi algorithm, but he maintains the Voronoi of point sites and a sweep line, which reduces the structural change during processing but is more complicated to implement.

Are there are other "growing boundaries" other than a horizontal line that allow us to certify the completion of Delaunay circles?

-- YuanxinLiu - 08 Feb 2005

Fortune's sweep algorithm should be more work than we need to do -- we don't need to compare circles to see which the sweep passes first; it is enough to just drop batches of circles that have been passed.

-- JackSnoeyink - 08 Feb 2005

Please visit StreamingCompression to find Martin's compressor and paper on streaming.

-- JackSnoeyink - 23 Feb 2005