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

2 Asked on August 27, 2021 by b_cass_

1 Asked on August 27, 2021 by gusman

1 Asked on August 27, 2021 by imallett

compute shader deferred rendering fragment shader performance

1 Asked on August 27, 2021 by lightxbulb

1 Asked on August 27, 2021

2 Asked on August 27, 2021

1 Asked on August 27, 2021 by wdc

1 Asked on August 27, 2021

1 Asked on August 27, 2021 by andygeers

1 Asked on August 27, 2021 by calvin-godfrey

0 Asked on August 27, 2021

1 Asked on August 27, 2021 by natew

1 Asked on August 27, 2021 by wduk

1 Asked on August 27, 2021 by lenny-white

0 Asked on August 27, 2021

1 Asked on August 27, 2021

1 Asked on August 27, 2021 by kuba

Get help from others!

Recent Questions

Recent Answers

- haakon.io on Why fry rice before boiling?
- Jon Church on Why fry rice before boiling?
- Lex on Does Google Analytics track 404 page responses as valid page views?
- Joshua Engel on Why fry rice before boiling?
- Peter Machado on Why fry rice before boiling?

© 2022 AnswerBun.com. All rights reserved. Sites we Love: PCI Database, MenuIva, UKBizDB, Menu Kuliner, Sharing RPP, SolveDir