Skip to topic
|
Skip to bottom
Jump:
TModeling
TModeling Web
TModeling Web Home
Changes
Notify
Index
Search
Webs
BioGeometry
Main
TModeling
TWiki
Edit
Attach
Printable
TModeling.StartHere
r1.1 - 23 Feb 2009 - 22:25 - Main.guest
topic end
Start of topic |
Skip to actions
%TOC% ---+ 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: <verbatim> 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 </verbatim> ---++ 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]]. <verbatim> sp2sp.exe -i .\upc\000168.upc -o .\168.spb </verbatim> | _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 <verbatim> sp_viewer.exe -i 168.spb </verbatim> <img src="%ATTACHURLPATH%/Tile_168.jpg" alt="Tile_168.jpg" width="1031" height="801" /> ---+++ 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* <verbatim> d:\OttawaDemo\upc\000147.upc d:\OttawaDemo\upc\000148.upc ... ... ... d:\OttawaDemo\upc\000228.upc d:\OttawaDemo\upc\000229.upc </verbatim> 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]] <verbatim> sp2sp.exe -lof -iupc -i d:\OttawaDemo\upc_files_square.txt -ospb -o d:\OttawaDemo\ottawa.spb </verbatim> 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]]. <verbatim> spfinalize.exe -i ottawa.spb -o ottawa55.spb -level 8 </verbatim> | _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 <verbatim> sp_viewer.exe -i ottawa55.spb </verbatim> <img src="%ATTACHURLPATH%/Ottawa_Square.JPG" alt="Ottawa_Square.JPG" width="1031" height="801" /> ---+++ 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. <verbatim> LOW - ground points (z-values remain unchanged) HIGH - non-ground points (z-values moved above bbox.zMax) </verbatim> _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. <verbatim> spground.exe -i ottawa55.spb -o o55_test.spb -tlength 30 </verbatim> | _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 <verbatim> sp_viewer.exe -i o55_test.spb </verbatim> <img src="%ATTACHURLPATH%/Ottawa_Ground2.JPG" alt="Ottawa_Ground2.JPG" width="1030" height="802" /> ---+++ 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. <verbatim> spfinalize.exe -i o55_test.spb -o o55_final.spb -level 8 </verbatim> | _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 <verbatim> sp_viewer.exe -i o55_final.spb </verbatim> ---+++ 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. <verbatim> spdelaunay2d.exe -i o55_final.spb -o o55_mesh.smb </verbatim> | _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. <verbatim> sm_pathviewer.exe -i o55_mesh.smb -zsplit 92.23 -zsub 163.0 </verbatim> ---+++ 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]]. <verbatim> smsimpall.exe -i o55_mesh.smb -o o55_compress_01.smb -buffsize 500000 -simprate 0.01 -mode 0 -retryrate 10 -zthres 92.23 </verbatim> | _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. <verbatim> sm_pathviewer.exe -i o55_compress_01.smb -zsplit 92.23 -zsub 163.0 </verbatim> <img src="%ATTACHURLPATH%/Ottawa_Compress2.JPG" alt="Ottawa_Compress2.JPG" width="1033" height="803" /> ---+++ 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 <x,y> 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]]. <verbatim> 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 </verbatim> | _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. <verbatim> sm_pathviewer.exe -i o55_planefit_1r.smb -zsplit 92.23 -zsub 163.0 </verbatim> 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. <verbatim> 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 </verbatim> | _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. <verbatim> sm_pathviewer.exe -i o55_filtered_1r.smb -zsplit 92.23 -zsub 163.0 </verbatim> _Note:_ Note the characteristic border around the outside caused by the 3-ring state machine in !RingFilt.exe <img src="%ATTACHURLPATH%/Ottawa_Filter2.JPG" alt="Ottawa_Filter2.JPG" width="1031" height="802" /> ---+++ 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]]. <verbatim> sm2sm.exe -i o55_filtered_1r.smb -o o55_filtered_01.smc -zsplit 92.23 -zsub 163.0 </verbatim> | _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. <verbatim> sm_pathviewer.exe -i o55_filtered_01.smc </verbatim> ---+++ 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]]. <verbatim> 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 </verbatim> | _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. <verbatim> sm_pathviewer.exe -i out_reorder.smb -path path.txt -zsplit 92.23 -zsub 163.0 </verbatim> <img src="%ATTACHURLPATH%/Path_Ontop.JPG" alt="Path_Ontop.JPG" width="1032" height="801" /> _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. <verbatim> 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 </verbatim> <img src="%ATTACHURLPATH%/Path_Dijkstra.JPG" alt="Path_Dijkstra.JPG" width="1031" height="802" /> ---+++ 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. <verbatim> 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 </verbatim> | _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 | <img src="%ATTACHURLPATH%/Ottawa_ASC.jpg" alt="Ottawa_ASC.jpg" width="1060" height="1042" /> --- -- Main.ShawnDB - 16 Dec 2008 * o55_mesh.jpg: <br /> * o55_reorder.jpg: <br /> * Ottawa_Filt_1r.jpg: <br /> * Ottawa_Square.JPG: <br /> * Ottawa_Ground2.JPG: <br /> * Ottawa_Compress2.JPG: <br /> * Ottawa_Filter2.JPG: <br /> * Path_Ontop.JPG: <br /> * Path_Dijkstra.JPG: <br />
to top
End of topic
Skip to action links
|
Back to top
Edit
|
Attach image or document
|
Printable version
|
Raw text
|
More topic actions
Revisions: | r1.1
|
Total page history
|
Backlinks
You are here:
TModeling
>
StartHere
to top
Copyright © 1999-2024 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki?
Send feedback