****************************************************************

  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:

>> 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 <p>)

the delaunay triangulator reads the finalized point stream and
outputs the resulting triangulation in form of a streaming mesh.

often 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 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 me (isenburg@cs.unc.edu) know.