# Fast and exact Geodesics on meshes, Backtracking confusion

Computer Graphics Asked on August 27, 2021

The following is an excerpt from a 2005 paper on geodesics on triangular meshes, taken from section 3.5 In this case $$p$$ is a point on some arbitrary face in a mesh, $$p’$$ is a point on one of the 3 edges in the triangle and $$D(p’)$$ is the geodesic distance to that point.

I am very confused as to how this minimization is achieved. The paper doesn’t go into detail, so I assume it’s trivial, but I am not seeing the solution of the top of my head.

Given an arbitrary interval (segment) the shortest point to it is either the orthogonal projection of the point $$p$$ onto the segment or one of the end points of the segment (depending on where $$p$$ is located with respect to the segment).

However, this is not necessarily the point that minimizes the expression $$||p – p’|| + D(p’)$$ or in other words, $$p’$$ is not, in general, the orthogonal projection of $$p$$ onto the segment.

The only algorithm I have is to naively check epsilon offsets along the segment and picking the shortest one. There has to be a better way than that.

I have drawn a diagram on Geogebra to show the problem: $$overline{BA}$$ is the segment, $$C$$ is the point we are looking to minimize the distance from. $$D$$ is the frontier point, which is the orthogonal projection of the Geodesic source (the source point of all geodesics in the mesh), $$E$$ is the orthogonal projection of $$C$$ onto $$overline{BA}$$. Clearly the optimal point is somewhere between $$E$$ and $$D$$ but I don’t know how to find it.

The solution I found to this problem is to ALWAYS intersect the edge. In other words the distance to the geodesic source $$v$$ from a point $$p$$ is $$||v-p'|| + ||p - p'||$$ where $$p'$$ is the intersection of the line $$overline{vp}$$ with the current edge. In cases where $$p'$$ is "behind" $$p$$ with respect to $$v$$ we set the distance to the edge to be infinity.

The above seems to work in the simple tests I have generated at minimum.

Correct answer by Makogan on August 27, 2021

## Related Questions

### Why does opengl use 4d matrices for everything?

3  Asked on August 27, 2021 by yoris

### How can i wrap the earth image around a 3D Sphere using OpenGL, GLFW, GLAD, GLM?

2  Asked on August 27, 2021 by b_cass_

### Defining “inside” and “outside” of a 3D space

2  Asked on August 27, 2021 by avatrin

### Using Bresenham’s circle algorithm (or another alternative algorithm) to draw an arc

1  Asked on August 27, 2021 by gusman

### Performance of Compute Shaders vs. Fragment Shaders for Deferred Rendering

1  Asked on August 27, 2021 by imallett

### Which perspective projection matrix to use

1  Asked on August 27, 2021 by nixcc

### Perspective correct interpolation z-buffer

1  Asked on August 27, 2021 by lightxbulb

### How is orthographic projection used in computer graphics technically classified as a projection?

1  Asked on August 27, 2021

### Why negate z when constructing projection matrix OpenGL

2  Asked on August 27, 2021

### UV partial derivatives of a cylinder shape primitive

1  Asked on August 27, 2021 by wdc

### OpenGL Framebuffer with multiple Depthbuffers inside

1  Asked on August 27, 2021

### Efficiently generating mesh for self-generated voxel grid

1  Asked on August 27, 2021 by andygeers

### How do you apply a normal map to a 3d mesh?

1  Asked on August 27, 2021 by calvin-godfrey

### What’s a good research topic in Computer Graphics?

0  Asked on August 27, 2021

### When unsetting a VAO, should you also unbind the associated VBOs?

1  Asked on August 27, 2021 by natew

### Reading from buffer versus calculating on the fly performance

1  Asked on August 27, 2021 by wduk

### How are textures projected onto 3d models in texture painting applications

1  Asked on August 27, 2021 by lenny-white

### Conditionals and branching in shaders

0  Asked on August 27, 2021

### Does atomic functions on same memory location cause an performance issue?

1  Asked on August 27, 2021

### Phong model: why no multiplication by N dot L in specular term?

1  Asked on August 27, 2021 by kuba

### Ask a Question

Get help from others!