2

What are the graphic/mathematical algorithms I have to look for in order to achieve the red line in the following image?

enter image description here

Explaining it better: I need to plot two points on the mesh and then generate a straight line segment from one point to the next. This line segment would be formed by new vertices created on every single edge in its way.

I'm currently working with CGAL and Libigl, but none of them seem to have the solution. I have tried CGAL::Surface_mesh_shortest_path but it adds too much overhead (code runs very slowly) and the line would not be guaranteed to be straight depending on the mesh deformation.

Alexandre Severino
  • 1,563
  • 1
  • 16
  • 38
  • 1
    IANAE, but the basis for how I'd try and solve this is to look up algorithms for [projective texture mapping](https://en.wikipedia.org/wiki/Projective_texture_mapping). You don't care about the algorithm that computes the texture coordinates (u,v), but if you think for a second, the algorithm that computes the model-space coordinates (s,t) for the edges of a square texture is exactly what you're looking for. – dgnuff Jul 25 '18 at 22:59
  • 2
    What do you mean by *straight*? You seem to be looking for geodesics, which is exactly what `Surface_mesh_shortest_path` calculates. It won't get any straighter than this (assuming that you mean that the curve is straight in tangent space). Calculating geodesics on surfaces is a pretty hard task. That might be why it is so slow. But you will probably find some other implementations with the keyword; there are a few approximative algorithms, which are faster. – Nico Schertler Jul 26 '18 at 16:37
  • Don't you need a normal (perhaps perpendicular to the p0-p1 vector) to project the line with ? – beyond Aug 01 '18 at 12:47
  • If you do not need the coordinates, just to render the line instead why not use shaders? and if rendered fragment intersects (is nearby) some (half)plane or region recolor it to red ... similar to this [Analysis of a shader in VR](https://stackoverflow.com/a/45564968/2521214). In case you need also the polyline you can extract it from frame buffer ... or use compute shader and store it directly ... – Spektre Dec 13 '19 at 09:45

1 Answers1

0

Ignoring whatever you mean as "straight", here is one simple algorithm I can think of that would produce images to the one similar shown in the question. There is no guarantee of what is produced being the shortest path. I'm just spitballing here with no knowledge on the topic, there are probably better ways.

Pick 4 variables:

  1. The starting point
  2. The ending point
  3. The line's normal
  4. A marching constant

Let's calculate a few constants from the variables:

  1. Direction = ending point - starting point
  2. Increment vector = normalize(Direction) * marching constant.

Begin from the starting point and march towards your ending point by some constant, checking above and below your current position for where you are on the mesh. You use the line's normal to understand the "up" and "down" directions in order to perform intersection tests.

On each intersection test, if you do not intersect for both the up and down directions, then the normal you chose will not work for the given two points and mesh, and you'll have to try a different normal. If you do end up intersecting from one of the directions, you will need to add 2 points to your final line: a point on the calculated direction line closest to the start that lies on the triangle, and a point on the calculated direction line farthest from the start that lies on the triangle. If there's both an intersection on the up and down directions, choose the up direction to work with.

Example Traversal

Eli Davis
  • 415
  • 5
  • 6