CODEWITHSUNDEEP
algorithm3dgeometrymesh
Vasily Mitch
Vasily Mitch

Reputation: 367

Mesh with minimal area between two polylines

I have two polylines v and u with n and m vertices respectively in 3D. I want to connect v[0] to u[0], v[n-1] to u[m-1] and also the inner vertices somehow to obtain a triangle mesh strip with minimal surface area.

My naïve solution is to get the near-optimal initial mesh by subsequent addition of the smallest diagonal and then switch diagonal in every quadrilateral if it produces smaller area until this is no longer possible.

image

But I am afraid I can end in local minimum and not global. What are the better options to achieve a minimal mesh?

Upvotes: 1

Views: 476

Answers (1)

Nico Schertler
Nico Schertler

Reputation: 32607

This can be solved with a Dynamic Program.

Let's visualize the problem as a table, where the columns represent the vertices of the first polyline and the rows represent the vertices of the second polyline:

    0  1  2  3  ... n-1   -> v
 0 
 1
 2
...
m-1

Every cell represents an edge between the polylines. You start at (0, 0) and want to find a path to (n-1, m-1) by taking either (+1, 0) or (0, +1) steps. Every step that you make has a cost (the area of the resulting triangle) and you want to find the path that results in the minimum cost.

So you can iteratively (just in the style of dynamic programming) calculate the cost that is necessary to reach any cell (by comparing the resulting cost of the two possible incoming directions). Remember the direction that you chose and you will have a complete path of minimum cost in the end. The overall runtime will be O(n * m).

If you know that your vertices are more or less nicely distributed, you can restrict the calculation of the table to a few entries near the diagonal. This could get the runtime down to O(k * max(n, m)), where k is the variable radius around the diagonal. But you may miss the optimal solution if the assumption of a nice vertex distribution does not hold.

You could also employ an A*-like strategy where you calculate a cell only when you think it could belong to the minimum path (with the help of some heuristic).

Upvotes: 2

Related Questions