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

• The reordered mesh is generated by feeding reordered_file.txt to spfinalize followed by spdelaunay2d.

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
to top