spdelaunay2d
A small but powerful tool that can turn billions of points into one gigantic and seamless terrain using very little main memory by streaming the Delaunay computation.
Expects a finalized 2D point stream as input and produces a streaming Delaunay triangle mesh as output. The Delaunay triangulation is computed incrementally as points stream in using the standard "locate" and "update" approach.
We locate the triangle containing the next point by walking there. We start the walk at the triangle that was created last. This walk may fail if the walk leads us through an already finalized part of the triangulation. In this case we first restart from a triangle linked to the unfinalized cell that this point falls into. If this fails too we search brute force over all triangles.
We update the triangulation to reestablish the Delaunay property using the Bowyer-Watson method that deletes all violated triangles and reconnects the resulting horizon of edges to the new point.
The main new part is the concept of finalizing parts of the alreay computed Delaunay triangulation and outputting all finalized Delaunay triangles and their vertices in form of a streaming mesh.
A Delaunay triangle can be finalized when its circumcircle is completely inside the spatially finalized region. It is then guaranteed to persist and may already be output and deallocated. A vertex is output just before the first triangle that references it and is topologically finalized in the moment is has no more triangles. In this moment it can be deallocated. For this we keep a use_count with each such active vertex that at any time reflects the number of active triangles referencing it. As soon as this use_count goes down to zero the vertex may be finalized.
Example usage: (see also
spfinalize)
>> spfinalize -i ..\data\lidar_band.txt.gz -o ..\data\lidar_band.spb
>> spdelaunay -i ..\data\lidar_band.spb -o ..\data\lidar_band.smb
>> sm_viewer -i ..\data\lidar_band.smb (press )
the delaunay triangulator reads the finalized point stream and outputs the resulting triangulation in form of a streaming mesh.
Eften we will use the delaunay triangulator in a piped mode (i.e. ... | spdelaunay -ispb -osmb | ..) to create a temporary triangulation that is directly piped into another process that consumes it and discards the original. Here is an example:
>> spfinalize -i ..\data\lidar_band.txt.gz -ospb | spdelaunay2d -ispb -osmb | sm_viewer -ismb -every 100
>> spfinalize -i gilmer.files -ilas -lof -ospb | spdelaunay2d -ispb -osmb | sm_viewer -ismb -every 10000
>> spfinalize -i pt.files -itxt -listoffiles -parse sxyz -ospb | spdelaunay2d -ispb -osmb | sm_viewer -ismb -every 10000
You can also create "non-streaming output", but we really do not recommend this (only do that for smaller data sets).
>> spfinalize -i ..\data\lidar_band.txt.gz -ospb | spdelaunay2d -ispb -o lidar_band.off
>> more lidar_band.off
>> sm_viewer -i lidar_band.off
For more info:
>> spdelaunay2d -h
usage:
spdelaunay2d -i terrain.spa
spdelaunay2d -ispb -osma < terrainpoints.spb > mesh.sma
spdelaunay2d -i points.spb -o mesh.smb
spdelaunay2d -i points.spa -o mesh.sma
spdelaunay2d -ispb -o mesh.smb < lidar_data.spb
If you find bugs let us know.
--
JackSnoeyink - 01 Jun 2008
to top