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.
--
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
spfinalize and then creating a mesh by using
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
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.
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, 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: order.exe -i 147.spb -o reordered147.txt -s 1.11 100.26 58.41 -n 300
example: spfinalize -i reordered147.txt -o finalized147.spb and then
spdelaunay2d -i finalized147.spb -o meshed147.sma
- Once we have the reordered mesh we run the fast marching algorithm, 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: fm -i meshed147.sma -o geodesic_directions.txt -s 1.11 100.26 58.41 -z 5 -grad
- The 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
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: sm_viewer -i meshed147.sma -path shortest_path.txt 1687*
*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:
For more information, go to
order and
fm, or contact
Vishal Verma.
--
ChristianStith - 18 Aug 2008