Streaming Modules
Most of our software tools for large data sets are modules that can be composed with pipes in Windows or UNIX (including Mac and Linux). Click any module name to see more on the module;
StreamingProcessingDemos will contain some detailed demo scripts for
OttawaData.
Versions & Installation
We have versions of these running on Windows (XP & Vista), MacOX, and Linux, all included in the SVN repository.
Because of the effort to keep multiple versions current, we decided to focus on the Windows XP versions on this page. Please let me know if posting other versions now will help you.
To install, unpackage the zip file. The glut32.dll is for OpenGL interfaces if you use any of the viewers; that should be with the executables. (You need not use the viewers to use the modules.) gzip.exe supports handling of gzipped input files.
File formats
Streaming formats add finalization tags to point streams and to point/triangle streams that make up a mesh. In brief, finalization means that we are not only told when a point appears in a stream, but also when no further points in a neighborhood will appear, which allows us to complete processing in the neighborhood, write out the results, and free up memory.
We started with streaming points in ascii and binary (spa and spb) that contain a header with bounding box and finalization information, followed by just xyz coordinates, and streaming meshes in ascii, binary, and compressed (sma, smb, smc) that contain a similar header, and an intermixed stream of vertices and triangles.
Single precision is supported by all tools, with some support for double precision and integer*32 and integer*64. UTM coordinates are often offset to stay in single precision.
Ascii spa format is useful for seeing the stored information, such as the bounding box, but is usually 10x larger and much slower than necessary. It also risks losing precision. Keep points in binary formats.
The tools under current development also handle auxiliary information with the xyz coordinates, and more flexible file parsing, so that they can support colors, normals, intensities, statistics, or classification information that can be produced or consumed by streaming modules. Mesh formats (smax, smbx) are implemented and point formats (spax, spbx) are to come.
Finally, there is some support for keeping the finalization header and parsing information separate from the data file, which allows us to keep data files in the original format (even as a list of files) so that no data needs to be duplicated. This mechanism is not fully exposed, however, because it is not yet stable.
Finalization philosophy
The key to streaming is finalization: data files typically tell only when data appears; we augment them with tags that tell when data will no longer be needed. For the lidar points, for example, we tag the last point in a region so that we know that we can perform any needed local processing on the region; for meshes we tag the last triangle using a vertex so that we know that we can free up the memory associated with the vertex. On large data sets we typically store less than 1/2% of the data during processing, which allows us to run computations like simplification or smoothing or classification on large data sets.
Notes on piping
These modules can be executed one at a time, reading from and writing to disk, but this is much slower. Ideally, you would read from one disk, write to another (to avoid seeks), and have many modules piping data in between. Because each module is designed to have a small memory footprint, and the operating system can handle parallelism, we have found that streaming algorithms outperform theoretically optimal algorithms even on data sets that are small enough to fit into memory because the streaming modules can overlap input and output with computation.
Stable modules
These modules are well-tested and should work fine as the basis for demos and valuation. They should work under all combinations of command line parameters
for Ascii binary and compressed files (e.g., spa, spb, sma, smb, smc). Please let me know of any bugs or difficulties.
Streaming Points
- spfinalize: Adds finalization tags to input points, to enable streaming them with a small memory footprint. We often use spfinalize to convert input into a stream, and then work with the finalized points.
- sp2sp: Point format conversion between ASCII and binary.
- sp_viewer: An OpenGL viewer for streaming points. Performs simplification for fast rendering; to rerender the full model from a file, press R and wait.
- 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.
Streaming Meshes
- sm2sm: Mesh format conversion between ASCII, binary, and compressed
- sm_viewer: An OpenGL viewer for streaming meshes. Performs simplification for fast rendering; to rerender the full model from a file, press R and wait.
- tin2dem: This program takes a streaming mesh as input and produces a raster grid in the specified format and resolution as output (currently supports output as *.jpg *.png and *.bil (with *.hdr and *.blw files). The jpg and png are typically for hillside shading or a false elevation coloring. The BIL writer supports 16 bit and 32 resolution integers that will usually hold an an elevation value in feet or meters.
- tin2iso: This program takes a streaming mesh as input and extracts contour lines (isoheight lines) at user-specified heights and outputs them in a streaming line format.
Streaming Lines
For drawing contour maps; sometimes useful with google earth output.
- sl_viewer: a simple OpenGL-based viewer for streaming lines
- sl2sl: converts one streaming line format to another. Useful to create tilings of lines and produce KML files that can be displayed in google earth.
- slsimp: reads streaming lines, and either removes all segments smaller than a given threshold (-length) or removes all "bumps" (i.e. a chain of two segments) whose area is smaller than a given threshold (-area).
- slclean: removes small connected components from a streaming line file. Operates like a filter.
Current development of modules
These modules are partially tested because they are new or under development.
May not work with all combinations of command line parameters or all file types, but we are polishing them to make that happen.
Streaming Points & Meshes
- smsimp Simplify a mesh using Garland & Heckbert's QuadricErrorMetric as described in ILS.
- smsimpall A better implementation of QuadricErrorMetric simplification by Catalin Constantin, which handles meshes with holes and classified points and produces fewer artifacts.
- RingFilt A filtering program that fits a surface to the one-ring or two-ring of triangles around each point and produces auxiliary information with statistics.
- classx: is used to generate fitting values for each point in mesh. For each point, it generates a 1-ring & 2-ring neighborhood around that point. Then it does a plane fitting algorithm using Linear Least squares and outputs the fitness values for each ring.
- spfilter: A filtering program that deals with horizontal planes. For a demo click here.
- spground: Classifies points as ground or non-ground for later filtering or simplification.
Shortest Paths
- tin_dist Computes distance from source to all vertices in the mesh. User select the algorithm from among Dijkstra, fast marching, and MMP.
- sm_path Computes shortest path from source to target in a mesh using A-star heuristic.
- reorder: Reorders a surface based on source and target points to reduce memory requirements for computing a path.
--
JackSnoeyink - 30 Nov 2008
to top