# Approximating Geodesics in a half edge DS, how can I refine my mesh to get good approximations

Computer Graphics Asked by Makogan on August 27, 2021

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:

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

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?

As you pointed out, the problem here is the discretization/subdivision of the mesh. If your mesh was made of quadrilaterals instead of triangles, the obvious subdivision strategy would be to split each quadliteral into four equally sized smaller quadliterals:

$$hspace{2cm}$$ $$hspace{2cm}$$

For any two points $$P_1$$ and $$P_2$$, Dijkstra's algorithm would yield sets of shortest paths between these points $$P_1$$ and $$P_2$$. The more you refine the discretization with this subdivision strategy, the more shortest paths you'll find between the two points. However, intuitively it is clear that for every subdivision level $$linmathbb{N}$$ you could pick one of these shortest paths $$p_l$$ such that the sequence $$(p_l)_{linmathbb{N}}$$ converges to the actual geodesic between $$P_1$$ and $$P_2$$ (with respect to some norm that has to be specified, for example the supremum norm).

Unfortunately, the same is not true for the standard subdivision strategy of splitting a triangle into four smaller triangles, which you have proven with your example. I believe that, at its core, the problem is that there is no way to reach the center of the triangle with a straight line from each of its edges. This can be achieved by splitting a triangle in each subdivision step into 6 smaller triangles like this:

$$hspace{2cm}$$ $$hspace{2cm}$$

I do not have a proof that this subdivision is more useful to compute geodesics with Dijkstra's algorithm, but it seems quite likely to me. I would be very interested to see what your results look like with this subdivision strategy! However, no matter what you do, in the end you may or may not end up with sets of shortest paths instead of a single shortest path. In this case you will need some kind of heuristic or additional algorithm to decide which path resembles the true geodesic most closely.

Correct answer by user9485 on August 27, 2021

## Related Questions

### Is there an algorithm to bold an outline font?

2  Asked on December 23, 2021

### alternative to spherical harmonics to model radiance aproximation, optimized for real-time evaluation

0  Asked on December 14, 2021

### Transfer the texture between two different sets of uv

1  Asked on December 9, 2021

### How to retrieve data from Compute Shader to CPU?

0  Asked on November 15, 2021 by ethan-ma

### unwanted patterns in simplex noise

1  Asked on November 13, 2021 by sam-apostel

### Procedural generation of biological models

1  Asked on November 13, 2021 by daniel-cooke

### What method is used for baking grayscale curvature maps

1  Asked on November 10, 2021 by jummit

### Why are texture coordinates often called UVs?

2  Asked on August 27, 2021 by samanthaj

### Dynamic Ray-Triangle Intersection

1  Asked on August 27, 2021 by cemklkn

### Reducing artificial rings in mean curvature of mesh

1  Asked on August 27, 2021

### Fast and exact Geodesics on meshes, Backtracking confusion

1  Asked on August 27, 2021

### How to scale signed distance field fonts properly?

1  Asked on August 27, 2021 by endanke

### The ploygon width parallel to the x axis as a function of the y ordonate?

0  Asked on August 27, 2021 by hafid-boukhoulda

### Find the formulas of the middle point algorithm for drawing the parabola?

0  Asked on August 27, 2021 by mrjab

### Crystal ball rotation – I don’t get why the code works

0  Asked on August 27, 2021 by user13665

### Draw Line on Arbitrary Surface

0  Asked on August 27, 2021 by valentin-molina

### How to raytrace Bezier surfaces?

5  Asked on August 27, 2021 by luser-droog