Shortest path algorithms and simplification
We run the shortest path algorithms described in
http://www.cs.unc.edu/~verma/shortest_path.pdf on simplified meshes
and look at the effect of simplification on the length of these shortest paths.
We consider the mesh 055_mesh.smb at two different levels of simplification: 1% and 0.5%. We then run the Dijkstra's
and the
MMP algorithm with A-star heuristics on these meshes. Note that the source and target can shift a little after
simplification and thus cause minor changes in the length of the shortest paths.
The following is the output generated by
MMP algorithm on the 1% simplified mesh
- 01percent.JPG:
The length of this path is 276.429. Peak memory requirement was 64 mb and it took 4.7 seconds. The input mesh was ordered using Dijkstra's method iwth A-star heuristics. Reordering took 12 secs and had a peak memory usage of 294mb. The length of the Dijkstra's shortest path was 288.88.
The following is the output generated by
MMP algorithm on the 0.5% simplified mesh
- 005percent.JPG:
The length of this path is 281.83. Peak memory requirement was 28mb and it took 1.86 seconds. The input mesh was ordered using Dijkstra's method iwth A-star heuristics. Reordering took 3.2 secs and had a peak memory usage of 147mb. The length of the Dijkstra's shortest path was 291.087.
It can be noticed that the two paths are qualitatively and quantitavely very similar. However, it is possible that on simplification the shortest path changes qualitatively but their length will remain close.
--
VishalVerma - 17 Dec 2008
to top