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.ShortestPathsDemo
r1.1 - 31 Dec 2008 - 17:51 - Main.guest
topic end
Start of topic |
Skip to actions
%TOC% ---+Calculating Shortest Paths _Note: The interface to the shortest path computations have changed so [[tin_dist]] and [[sm_path]] are now the modules, but these remain the approaches implemented and their considerations._ -- Main.JackSnoeyink - 18 Dec 2008 We are currently considering two different approaches for computing shortest paths on a given terrain. The first approach involves simplifying the terrain and then computing shortest paths using an in-core method (Surazhsky et al. Siggraph 2005). In the second approach we solve the shortest path problem using streaming techniques. ---++ In Core Method The In Core method involves simplifying the mesh and then computing shortest paths on it using the libraries provided by Vitaly Surazhsky for shortest path computation using continuous MMP and continuous A-star algorithms. A wrapper code which removes triangles with long edges is used to remove such triangles which may occur after mesh simplification. This threshold edge length can be set using the "-l" command line option as follows: =GeoTest.exe mesh.obj -s source_index [-a Tol] [-t target_index] [-z scaling factor] [-l maximum edge length]= The "-a" option is used to compute approximate distances which are then used to compute exact shortest paths. In the absence of "-a" option exact distances are computed. This is more memory intensive than other approximate distance computation. The value of tolerance can vary from 0 to 1. ------ ---++ Streaming Method To solve this problem we sort the stream in the order of the Euclidean distance of the vertices in the stream from the source vertex. This step is performed so that a vertex does not appear much earlier in the stream than required by the algorithm. The output of this reordering module is a sequence of points. The reordered mesh is obtained by finalizing this sequence of points using [[http://wwwx.cs.unc.edu/Research/compgeom/twiki/bin/view.cgi/TModeling/Spfinalize][spfinalize]] and then creating a mesh by using [[http://wwwx.cs.unc.edu/Research/compgeom/twiki/bin/view.cgi/TModeling/Spdelaunay2d][spdelauanay2d]]. After reordering the stream, we compute approximate distance of each vertex in the terrain from the source vertex using fast marching method. Fast marching can also be used to compute the approximate direction of geodesics (originating at the source vertex) in every face of the terrain. The third module uses the geodesic directions computed in the fast marching module to compute approximate shortest path between the source and a given destination. ------ ---++++For Example An aerial view of the University of Utah. On the left, we have a streaming mesh view of the .sma file, with the vertices colored dark red to light gray in the order that they were rendered. On the right, the same file is shown, having been reordered and colored using [[http://wwwx.cs.unc.edu/Research/compgeom/twiki/bin/view.cgi/TModeling/Order][order]] distance algorithms. The points are now ordered (as can be seen by the change in color) based on their distance from the lower left vertex of the file. <img src="%ATTACHURL%/compare.bmp" width="700" height="300" /> ---------------------------- ---+++Usage _To run these programs yourself, copy these command lines into your Command Prompt window, substituting your own filename for original_file.sma. Use the blue lines if you don't know what paramaters to use._ * The command line options for the reordering module, [[http://wwwx.cs.unc.edu/Research/compgeom/twiki/bin/view.cgi/TModeling/Order][order]]: =order.exe -i original_file.spb= (*.spa works too) =-o reordered_file.txt -s source_x source_y source_z -n number_of_files_used_for_reordering= _example:_ %BLUE% order.exe -i 147.spb -o reordered147.txt -s 1.11 100.26 58.41 -n 300 %ENDCOLOR% * The reordered mesh is generated by feeding reordered_file.txt to [[http://wwwx.cs.unc.edu/Research/compgeom/twiki/bin/view.cgi/TModeling/Spfinalize][spfinalize]] followed by [[http://wwwx.cs.unc.edu/Research/compgeom/twiki/bin/view.cgi/TModeling/Spdelaunay2d][spdelaunay2d]]. _example:_ %BLUE% spfinalize -i reordered147.txt -o finalized147.spb %ENDCOLOR% and then %BLUE% spdelaunay2d -i finalized147.spb -o meshed147.sma %ENDCOLOR% * Once we have the reordered mesh we run the fast marching algorithm, [[http://wwwx.cs.unc.edu/Research/compgeom/twiki/bin/view.cgi/TModeling/Fm][fm]] , on it. =(to output distances) fm -i reordered_file.sma -o output.txt -s source_x source_y source_z= =(to output geodesic directions) fm -i reordered_file.sma -o output.txt -s source_x source_y source_z -z z_scaling_factor -grad= _example:_ %BLUE% fm -i meshed147.sma -o geodesic_directions.txt -s 1.11 100.26 58.41 -z 5 -grad %ENDCOLOR% * The [[http://wwwx.cs.unc.edu/Research/compgeom/twiki/bin/view.cgi/TModeling/Extract_path][path extraction]] module computes shortest paths on the terrain using the geodesic directions computed by the fast marching module =extract_path -i geodesic_directions.txt -o shortest_path.txt -s target_x target_y target_z -z z_scaling_factor= _example:_ &BLUE% extract_path -i geodesic_directions.txt -o shortest_path.txt -s 38.691 192.491 58.98 -z 5 %ENDCOLOR% The geodesic_directions.txt used above is the same as the output.txt produced by the fast marching module when it is run with -grad option. The z_scaling_factor here should be the same as the z-scaling factor used with the fast marching module. ------ ---++ Viewing shortest paths To view these paths we use a modified sm_viewer: =sm_viewer -i terrain.sma -path shortest_path.txt number_of_points_in_shortestpath.txt= _example:_ %BLUE% sm_viewer -i meshed147.sma -path shortest_path.txt 1687* %ENDCOLOR% _*Number of points in the shortest path (1687 in this case) is the last number displayed from extract_path in your Command Prompt window._ The shortestpath.txt used here is the output of the extract_path module or the GeoTest module, while the number_of_points_in_shortestpath.txt is printed when extract_path or Geotest finish their computation. Example: * A sample shortest path on the University of Utah mesh: <br /> <img src="%ATTACHURLPATH%/path.JPG" alt="sample path" width="600" height="450" /> -------------- For more information, go to [[http://wwwx.cs.unc.edu/Research/compgeom/twiki/bin/view.cgi/TModeling/Order][order]] and [[http://wwwx.cs.unc.edu/Research/compgeom/twiki/bin/view.cgi/TModeling/Fm][fm]], or contact [[Main.VishalVerma][Vishal Verma]]. -- Main.ChristianStith - 18 Aug 2008
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
>
ShortestPathsDemo
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