Ottawa Demo
Preliminaries
Goal
We were given a 5x5 set of tiles of
OttawaData, consisting of 905 megabytes of point cloud data captured by NEPTEC. The data is very irregularly sampled; we show that it can be processed in this form, compressing it by a factor of 1000, and running shortest paths on the resulting surface representation.
File Formats:
We work with the following file formats for points and surfaces:
File Format | Description |
.UPC | input data in format provided by NGA |
.spa | Streaming Point (ASCII), human readable |
.spb | Streaming Point (Binary) |
.sma | Streaming mesh (ASCII), human readable |
.smb | Streaming Mesh (Binary) |
.smc | Streaming Mesh (Compressed Binary) |
Test Machine Info
Our software works on 32 & 64-bit windows, Macs, and Unix.
Our test machine was:
Dell Precision WorkStation T3400
- CPU => Intel Core Duo (2 cores @ 3.0Ghz each)
- Memory => 4 GB (@ 800 Mhz)
- OS => Microsoft Windows XP, SP2 (64-bit)
- Display => Nvidia Quadro FX 570
- Drives
C:\ => mounted on DISK0, 116+ GB capacity
D:\ => mounted on DISK1, 232+ GB capacity
E:\ => mounted on DISK0, 116+ GB capacity
F:\ => mounted on CD-ROM
Step by step
1. Convert individual UPC tiles into SPB format (Point Cloud).
This step converts a single tile from the Ottawa Data set in UPC format into our own SPB (Streaming Point Binary) format.
Note: This step took about 2/10th's of a second. For documentation and other options, see
sp2sp and
sp_viewer.
sp2sp.exe -i .\upc\000168.upc -o .\168.spb
Input File: | 000168.upc | 85 MB | 85,440,952 bytes |
Output File: | 168.spb | 28 MB | 28,776,980 bytes |
Note: To view the resulting point cloud tile, use this command
sp_viewer.exe -i 168.spb
2. Merge all UPC Tiles into a single SPB file (Point Cloud).
Assume we have created a plain text file containing the 25 names of all the UPC files corresponding to the 5x5 square of interest named upc_files_square.txt
upc_square_files.txt
d:\OttawaDemo\upc\000147.upc
d:\OttawaDemo\upc\000148.upc
...
...
...
d:\OttawaDemo\upc\000228.upc
d:\OttawaDemo\upc\000229.upc
Then we can merge all 25 upc files into one .spb file as follows.
This step took about 48 seconds on our machine. For documentation and other options, see
sp2sp
sp2sp.exe -lof -iupc -i d:\OttawaDemo\upc_files_square.txt -ospb -o d:\OttawaDemo\ottawa.spb
We also have a suite of MATLAB scripts that can operate on all UPC files in a directory, an extract data in .rawf (raw float) formats.
Output File: | ottawa.spb | 74 M pts | 934 MB | 934,151,264 bytes |
3. Spatially finalize raw point cloud data.
This virtually bin's points into geographic neighborhoods using a Quad Tree Data structure.
Note: This step took about 1/2 minutes (25 seconds) on our machine. For documentation and other options, see
spfinalize and
sp_viewer.
spfinalize.exe -i ottawa.spb -o ottawa55.spb -level 8
Input File: | ottawa.spb | 77 M pts | 934 MB | 934,151,264 bytes |
Output File: | ottawa55.spb | 77 M pts | 937 MB | 937,248,944 bytes |
Memory Used: | | | 15MB | 1.7% |
Note: To view the resulting point cloud, use this command
sp_viewer.exe -i ottawa55.spb
4. identify non-ground features or apply other filters.
This finds and marks non-ground features by moving their z-values above
the original bounding box's max z-value. IE it essentially separates points
into two groups.
LOW - ground points (z-values remain unchanged)
HIGH - non-ground points (z-values moved above bbox.zMax)
Note: The displayed value of zSplit can be used as the threshold by later modules to separate the two groups (LOW & HIGH)
Note: This step took about 1 1/2 minutes (83 seconds) in isolation. For documentation and other options, see
spground or
GridFilter.
spground.exe -i ottawa55.spb -o o55_test.spb -tlength 30
Input File: | ottawa55.spb | 77 M pts | 937 MB | 937,248,944 bytes |
Output File: | o55_test.spb | 77 M pts | 937 MB | 937,314,128 bytes |
Memory Used: | | | 270MB | 30% |
z zplit: | 92.23 | | | |
z sub: | 163.00 | | | |
Note: To view the resulting 2 layer point cloud, use this command
sp_viewer.exe -i o55_test.spb
5. Spatially Finalize points again
The spground filter can partially destroy the spatial coherence of the original point cloud,
Restore coherency by spatially finalizing the points again.
Note: This step took about 19 seconds on our machine.
spfinalize.exe -i o55_test.spb -o o55_final.spb -level 8
Input File: | o55_test.spb | 77 M pts | 937 MB | 937,314,128 bytes |
Output File: | o55_final.spb | 77 M pts | 937 MB | 937,248,944 bytes |
Note: To view the resulting file, use this command
sp_viewer.exe -i o55_final.spb
6. Triangulate Point Cloud to form TIN (Triangulated Irregular Network)
Uses Delaunay triangulation on the point cloud to generate a triangulated mesh.
Note: Point cloud must be spatially finalized for this to work properly.
Note: This step took about 2+ minutes (129.5 seconds) in isolation. For documentation and other options, see
spdelaunay2d and
sm_pathviewer.
We recommend that the output be piped directly to simplification; there is no reason to create the large intermediate file, except for interest.
spdelaunay2d.exe -i o55_final.spb -o o55_mesh.smb
Input File: | o55_final.spb | 74 M pts | 937 MB | 937,248,944 bytes |
Output File: | o55_mesh.smb | 130 M tri | 2.36 GB | 2,364,655,421 bytes |
Memory Used: | | | 15MB | 0.6% |
Note: For smaller examples, you can view the resulting mesh use the following command. We don't recommend it with the entire 5x5 until after the next step of simplification.
sm_pathviewer.exe -i o55_mesh.smb -zsplit 92.23 -zsub 163.0
7. Reduce Triangle Mesh
Compression is accomplished via the Quadric Error Metric (QEM), a priority heap, and edge contraction.
A Quad Edge data structure is used for building the surface.
Note: This is a lossy compression technique.
Note: The code won't allow an edge contraction to occur if a triangle
in the new contracted 1-ring would flip orientation from CCW to CW, IE become twisted off the manifold.
This test in the 1-ring isn't sufficient to catch all potential twisting
problems. Given an interior hole with a triangular ear in the current edge's 1-ring that is being tested. Any farther away vertex belonging to the same hole protruding
into the ear being tested can potentially cause problems.
Delta shaped interior holes are the simplest shape that can potentially cause this problem.
Solving this correctly would require finding all potential problem points by walking all edges of each hole (big performance hit and may still not catch all cases in our streaming architecture), triangulating holes (including the infinite exterior face, hard to do in a streaming architecture), and/or an additional spatial location data structure (find all potential problem points in a bounding box or disc surrounding the triangle under consideration, requires covering bounding box to be spatially finalized for test to work correctly).
Note: Optionally uses a threshold value to separate points into
2 groups (LOW, HIGH) while compressing.
This won't allow an edge contraction to occur
if the 2 edge vertices belong to 2 different groups (HIGH & LOW).
You should use the same threshold value that came from step 4.
Note: This is the time-consuming step, taking about 17.5 minutes (1051 seconds). For documentation and other options, see
smsimp and
sm_pathviewer.
smsimpall.exe -i o55_mesh.smb -o o55_compress_01.smb -buffsize 500000 -simprate 0.01 -mode 0 -retryrate 10 -zthres 92.23
Original UPC: | 5x5 tiles | 74 M pts | 2.77 GB | 2,773,581,424 bytes |
Input File: | o55_mesh.smb | 130 M tri | 2.36 GB | 2,364,655,421 bytes |
Output File: | o55_compress_01.smb | 1.38 M tri | 26 MB | 26,054,753 bytes |
Memory Used: | | | 406MB | 19.8% |
Compression vs UPC | 26/2773 | 0.9% | 106 to 1 |
Compression vs input | 26/2360 | 1.1% | 91 to 1 |
Compression vs SPB | 26/905 | 2.99% | 36 to 1 |
Note: To view the simplified mesh use the following command.
sm_pathviewer.exe -i o55_compress_01.smb -zsplit 92.23 -zsub 163.0
8. Cleanup outliers via filtering (Optional)
Uses filtering in small neighborhoods (1-rings, 2-rings) around each vertex to remove spikes and outliers.
This first filter is a planar best-fit variance filter
- For each point, get all the neighbors in it's 1-ring
- Try to fit the best plane to all the points using linear least squares
- Best fit z-val computed by substituting into resulting plane equation
- Compute the distance from the plane for the center point and it's neighbors
- Compute the variance in these distances
- Remove outliers (more than 3 sigma intervals) by replacing by the best-fit z-value
Note: This step took about 16 seconds. For documentation and other options, see
RingFilt.
ringfilt -ismb -i o55_compress_01.smb -osmb -o o55_planefit_1r.smb -sigmin 0.0 -sigmax 3.0 -fl1r -replace -zsplit 92.23 -zsub 163.0
Input File: | o55_compress_01.smb | | 26.0 MB | 26,004,325 bytes |
Output File: | o55_planefit_1r.smb | 1.43 M tri | 26.0 MB | 25,983,953 bytes |
Memory Used: | | | 12.1MB | 0.6% |
Note: To view the filtered mesh use the following command.
sm_pathviewer.exe -i o55_planefit_1r.smb -zsplit 92.23 -zsub 163.0
This Second filter is a simple height averaging variance filter
- For each point, get all the neighbors in it's 1-ring
- Compute average height (best-fit z-val)
- Compute the variance from average height for each point
- Remove outliers (more than 3 sigma intervals) by replacing by the best-fit z-value
Note: This step took about 16 seconds.
ringfilt -ismb -i o55_planefit_1r.smb -osmb -o o55_filtered_1r.smb -sigmin 0.0 -sigmax 3.0 -f1r -replace -zsplit 92.23 -zsub 163.0
Input File: | o55_planefit_1r.smb | 1.43 M tri | 26.0 MB | 25,983,953 bytes |
Output File: | o55_filtered_1r.smb | 1.43 M tri | 26.0 MB | 25,969,077 bytes |
Memory Used: | | | 13.6MB | 0.7% |
Note: To view the filtered mesh use the following command.
sm_pathviewer.exe -i o55_filtered_1r.smb -zsplit 92.23 -zsub 163.0
Note: Note the characteristic border around the outside caused by the 3-ring state machine in RingFilt.exe
9. Storage in compressed mesh format (Optional)
Converts from .SMB format to .SMC format.
Uses binary compression and the parallelogram rule to achieve an additional 10-fold compression with only a small loss in precision.
Note: This step takes about 4 seconds. For documentation and other options, see
sm2sm and
sm_pathviewer.
sm2sm.exe -i o55_filtered_1r.smb -o o55_filtered_01.smc -zsplit 92.23 -zsub 163.0
Original UPC: | 5x5 tiles | 74 M pts | 2.77 GB | 2,773,581,424 bytes |
Input File: | o55_compress_01.smb | 1.38 M tri | 25.9 MB | 25,969,077 bytes |
Output File: | o55_compress_01.smc | 1.38 M tri | 2.62 MB | 2,624,364 bytes |
Memory Used: | | | 5MB | 5% |
Compression vs UPC | 2.54/2773 | 0.1% | 1056 to 1 |
Compression vs input | 2.54/25.9 | 10.1% | 9.9 to 1 |
Compression vs SPB | 2.54/905 | .28% | 356 to 1 |
Note: To view the compressed mesh use the following command.
sm_pathviewer.exe -i o55_filtered_01.smc
10. Find shortest path
Finds shortest path from source to destination using MMP algorithm with A* heuristic.
Note: This step took about 11 seconds on the test machine. For documentation and other options, see
sm_path.
sm_path.exe -i o55_filtered_1r.smb -s 0.0 0.0 0.0 -t 310.0 50.0 -10.0 -path path.txt
-exact -reorder_prune out_reorder.smb
Input File: | o55_filtered_1r.smb | 25.5 MB | 25,969,077 bytes |
Memory Used: | | 312MB | 1223% |
Note: To view the path and reordered mesh use the following command.
sm_pathviewer.exe -i out_reorder.smb -path path.txt -zsplit 92.23 -zsub 163.0
Note: Here is a similar path built using Dijkstra's method. This took 1 second to compute.
Note: Notice the somewhat jagged appearance of the path caused by only allowing the path on triangle edges.
sm_path.exe -i o55_filtered_1r.smb -s 0.0 0.0 0.0 -t 310.0 50.0 -10.0 -path dijk_path.txt
sm_pathviewer.exe -i out_reorder.smb -path dijk_path.txt -zsplit 92.23 -zsub 163.0
11. Rasterize TIN to DEM (Optional)
Converts TIN to DEM using variety of interpolation techniques
(linear, matrix subdivision based on meshless wavelets, quintic, etc.)
Note: Can generate DEM's in ESRI ASC compatible format or .BIL format
Note: To view the DEM you will need to use a tool like FreeView or LandSerf.
Note: This step took about 1 second on the test machine, reading and writing to/from same disk.
sm2sm.exe -i o55_compress_01.smb -osmb -zsplit 92.23 -zsub 163.0 | tin2dem.exe -lin -ncols 400 -nrows 400 -ulxmap 0 -ulymap 0 -xdim 1.0 -ydim 1.0 -ismb -oasc -o o55_zsub_01.asc
Input File: | o55_zsub_01.smb | 25 MB | 25,122,013 bytes |
Output File: | o55_zsub_01.asc | 2.46 MB | 1,603,986 bytes |
--
ShawnDB - 16 Dec 2008
- o55_mesh.jpg:
- o55_reorder.jpg:
- Ottawa_Filt_1r.jpg:
- Ottawa_Square.JPG:
- Ottawa_Ground2.JPG:
- Ottawa_Compress2.JPG:
- Ottawa_Filter2.JPG:
- Path_Ontop.JPG:
- Path_Dijkstra.JPG:
to top