<p>I implemented Djikstra's shortest path algorithm to approximate Geodesics on arbitrary meshes. Djikstra's works, but I noticed a problem inherent to the discretization of my meshes.</p>
<p>Consider the following figure squence:</p>
<p><a href="https://i.sstatic.net/T0yKn.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/T0yKn.png" alt="enter image description here" /></a>
<a href="https://i.sstatic.net/XS7Mu.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/XS7Mu.png" alt="enter image description here" /></a>
<a href="https://i.sstatic.net/5BIz1.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/5BIz1.png" alt="enter image description here" /></a></p>
<p>...</p>
<p><a href="https://i.sstatic.net/aQ0Qp.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/aQ0Qp.png" alt="enter image description here" /></a></p>
<p>This is my current refinement algorithm which is the easiest/standard face subdivision. Now consider the approximation of a geodesic in 2 points:</p>
<p><a href="https://i.sstatic.net/6aRG4.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/6aRG4.png" alt="enter image description here" /></a></p>
<p>The blue point is where I think the actual geodesic intersects that edge, which is quite far from where the approximated geodesic passes. However that path ISN'T wrong.</p>
<p>Consider a square grid. The distance between any 2 points in the grid is the manhattan distance  |x| + |y|.</p>
<p>So as far as Djikstra's is concerned, a path that goes all the way down and then to the left has the same length as a path that goes diagonally in a staircase pattern. Refining the mesh won't change the distance either. In other words, the limit of the shortest path found by Djikstra in a regular square grid as the size of the squares goes to 0 is NOT the straigtht line connecting 2 points.</p>
<p>Now the actual question, does anyone know of a way to subdivide my surface that is fairly straightforward but will actually converge to the geodesic?</p>

CC BY-SA 4.0
2020-07-21T15:45:10.203Z
The analytic path should be shorter, but the approximation might be longer
Makogan
CC BY-SA 4.0
2020-07-21T17:02:10.170Z
In this specific case there's just one, but in general there might be multiple, including infinite.
Makogan
CC BY-SA 4.0
2020-07-21T21:23:43.647Z
@Chris Consider the sphere, take the 2 poles, every single great circle connecting the 2 points is a geodesic path. Thus, there are infinitely many.

Different shapes have different properties but most shapes have at least one pair of points that are connected by an infinite amount of geodesics.
Makogan
CC BY-SA 4.0
2020-07-23T08:58:12.567Z
Modify your search to use the Euclidean distance between vertices (on the same face), it's possibly not as efficient but should give the correct results.
lightxbulb
CC BY-SA 4.0
2020-07-23T16:50:35.593Z
@lightxbulb My faces are triangles, so it's technically already doing that.
Makogan
CC BY-SA 4.0
2020-07-23T18:44:22.537Z
From my understanding if that was the case you would be getting the blue point. You already mentioned you use manhattan distance. I suggest using Euclidean distance.
lightxbulb
CC BY-SA 4.0
2020-07-23T23:29:25.253Z
@lightxbulb The easiest way to understand the problem is perhaps, look at the last image and try to come up with a shorter path in the generated grid than the green path.

You will notice that you can't find a shorter one. Then imagine you do one further subdivision step, you will notice that a newly detected path on that more refined grid is actually pretty close to the one on the last image, despite there being 3x more edges to pick from.
Makogan
CC BY-SA 4.0
2020-07-24T06:24:15.117Z
I think that if the method was using Euclidean distance then you would get a "staircase" path, so even without a further refinement you will be a lot closer to the blue point. I'll elaborate. You say: "The distance between any 2 points in the grid is the manhattan distance |x| + |y|" - this doesn't need to be the case. You can measure the Euclidean distance between the two points. Then you would get the path that you want for your geodesics. To be sure, measure the distance in the continuous space, not on the graph.
lightxbulb
<mathematics><computational-geometry><geometry><subdivision><tesselation>
Approximating Geodesics in a half edge DS, how can I refine my mesh to get good approximations
Makogan
# Approximating Geodesics in a half edge DS, how can I refine my mesh to get good approximations

(Asked by: username_0 on 2020-07-21)

I implemented Djikstra's shortest path algorithm to approximate Geodesics on arbitrary meshes. Djikstra's works, but I noticed a problem inherent to the discretization of my meshes.

Consider the following figure squence:

[![enter image description here](https://i.sstatic.net/T0yKn.png)](https://i.sstatic.net/T0yKn.png)
[![enter image description here](https://i.sstatic.net/XS7Mu.png)](https://i.sstatic.net/XS7Mu.png)
[![enter image description here](https://i.sstatic.net/5BIz1.png)](https://i.sstatic.net/5BIz1.png)

...

[![enter image description here](https://i.sstatic.net/aQ0Qp.png)](https://i.sstatic.net/aQ0Qp.png)

This is my current refinement algorithm which is the easiest/standard face subdivision. Now consider the approximation of a geodesic in 2 points:

[![enter image description here](https://i.sstatic.net/6aRG4.png)](https://i.sstatic.net/6aRG4.png)

The blue point is where I think the actual geodesic intersects that edge, which is quite far from where the approximated geodesic passes. However that path ISN'T wrong.

Consider a square grid. The distance between any 2 points in the grid is the manhattan distance |x| + |y|.

So as far as Djikstra's is concerned, a path that goes all the way down and then to the left has the same length as a path that goes diagonally in a staircase pattern. Refining the mesh won't change the distance either. In other words, the limit of the shortest path found by Djikstra in a regular square grid as the size of the squares goes to 0 is NOT the straigtht line connecting 2 points.

Now the actual question, does anyone know of a way to subdivide my surface that is fairly straightforward but will actually converge to the geodesic?

**Tags:** mathematics, computational-geometry, geometry, subdivision, tesselation

> **Comments:**
> **username_0**: The analytic path should be shorter, but the approximation might be longer  
> **username_0**: In this specific case there's just one, but in general there might be multiple, including infinite.  
> **username_0**: @Chris Consider the sphere, take the 2 poles, every single great circle connecting the 2 points is a geodesic path. Thus, there are infinitely many.  Different shapes have different properties but most shapes have at least one pair of points that are connected by an infinite amount of geodesics.  
> **username_1**: Modify your search to use the Euclidean distance between vertices (on the same face), it's possibly not as efficient but should give the correct results.  
> **username_0**: @username_1 My faces are triangles, so it's technically already doing that.  
> **username_1**: From my understanding if that was the case you would be getting the blue point. You already mentioned you use manhattan distance. I suggest using Euclidean distance.  
> **username_0**: @username_1 The easiest way to understand the problem is perhaps, look at the last image and try to come up with a shorter path in the generated grid than the green path.  You will notice that you can't find a shorter one. Then imagine you do one further subdivision step, you will notice that a newly detected path on that more refined grid is actually pretty close to the one on the last image, despite there being 3x more edges to pick from.  
> **username_1**: I think that if the method was using Euclidean distance then you would get a "staircase" path, so even without a further refinement you will be a lot closer to the blue point. I'll elaborate. You say: "The distance between any 2 points in the grid is the manhattan distance |x| + |y|" - this doesn't need to be the case. You can measure the Euclidean distance between the two points. Then you would get the path that you want for your geodesics. To be sure, measure the distance in the continuous space, not on the graph.  

---

## 0 answers

