Algorithm to calculate and display a ribbon on a 3D triangle mesh

Question

I am looking for an algorithm for the following problem:

Given:

1. A 3D triangle mesh. The mesh represents a part of the surface of the earth.

2. A polyline (a connected series of line segments) whose vertices are always on an edge or on a vertex of a triangle of the mesh. The polyline represents the centerline of a road on the surface of the earth.

I need to calculate and display the road i.e. add half of the road's width on each side of the center line, calculate the resulting vertices in the corresponding triangles of the mesh, fill the area of the road and outline the sides of the road.

What is the simplest and/or most effective strategy to do this? How do I store the data of the road most efficiently?

Answer 1

I see 2 options here:

1. render thick polyline with road texture

   While rendering polyline you need TBN matrix so use

   • polyline tangent as tangent
   • surface normal as normal
   • binormal=tangent x normal

   shift actual point p position to

   p0=p+d*binormal
   p1=p-d*binormal
   

   and render textured line (p0,p1). This approach is not precise match to surface mesh so you need to disable depth or use some sort of blending. Also on sharp turns it could miss some parts of a curve (in that case you can render rectangle or disc instead of line.

2. create the mesh by shifting polyline to sides by half road size

   This produces mesh accurate road fit, but due to your limitations the shape of the road can be very distorted without mesh re-triangulation in some cases. I see it like this:

   

   1. for each segment of road cast 2 lines shifted by half of road size (green,brown)
   2. find their intersection (aqua dots) with shared edge of mesh with the current road control point (red dot)
   3. obtain the average point (magenta dot) from the intersections and use that as road mesh vertex. In case one of the point is outside shared mesh ignore it. In case both intersections are outside shared edge find closest intersection with different edge.

   As you can see this can lead to serious road thickness distortions in some cases (big differences between intersection points, or one of the intersection points is outside surface mesh edge).

   If you need accurate road thickness then use the intersection of the casted lines as a road control point instead. To make it possible either use blending or disabling Depth while rendering or add this point to mesh of the surface by re-triangulating the surface mesh. Of coarse such action will also affect the road mesh and you need to iterate few times ...

   Another way is use of blended texture for road (like sprites) and compute the texture coordinate for the control points. If the road is too thick then thin it by shifting the texture coordinate ... To make this work you need to select the most far intersection point instead of average ... Compute the real half size of the road and from that compute texture coordinate.

   If you get rid of the limitation (for road mesh) that road vertex points are at surface mesh segments or vertexes then you can simply use the intersection of shifted lines alone. That will get rid of the thickness artifacts and simplify things a lot.