Remeshing with a limited set of triangles

Hey !

I'd like to simplify a meshed surface in flat triangles, with the least triangle variations possible listed in a custom set.

Firstly, I thinked about equilateral ones : tried the MeshMachine & Kangaroo springs (surfaces too relaxed), temembered the Lobel Frame, gave a go with Marching Cubes algorithm (too sharp output) ...

These solutions are great when fidelity to the surface is the top priority, mine is the strict use of a limited set of triangles. I read some posts but couldn't find anything really suitable.

Does anybody have another idea ? I might not have fed Google with the good terms. I feel I'll end up Csharping it x)

Thanks in advance for any support, i'll be glad to receive it.

Have a nice day !

Replies to This Discussion

Permalink Reply by Daniel Piker on February 23, 2016 at 10:12am

Hi Mac,

One simple way to approach this is to group the edges by length, and shrink/expand each edge towards the average of its group. Clearly a fixed number of edge lengths leads to a fixed number of triangles.

Here's a mesh before this clustering:

and after:

In general this won't lead to a very smooth mesh, but you can get strict edge lengths.

I attached the definition for this below. There is a slider for how strongly vertices try and keep near their original locations - by adjusting this you can vary the priority of exact edge lengths vs closeness to the original shape.

This is just a start though - there's lots more work that could be done along this direction.

For instance, instead of fixing the target lengths once at the start, the groupings could be adjusted iteratively using something like K-Means clustering.

Slightly more involved would be to make a custom goal which adjusts whole triangles instead of edges.

It is sometimes helpful to think of triangle shapes as points in a three dimensional space, where the coordinates correspond to edge lengths. However, you need to also account for the fact that a 3,4,5 triangle is the same as a 4,5,3 triangle, and so on.

Attachments:

EdgeLengthCluster.gh, 19 KB

Permalink Reply by Mac Gros on February 26, 2016 at 9:06am

Hey,

This is a good start, results are quite heterogeneous depending on the mesh resolution, the quality of the meshing (thx meshmachine to improve that bit) and of course the number of desired length. I continued using Kangaroo, that's a very good way to approximate such a problem.

I concur with you on the dynamic K-mean thing, haven't implemented it yet.

What I tried :
Interpolate a curve (1-manifold, that's easier) mathematically, ended up kangarooing it and that works like a charm. 100% match.
With this bit I can have clean naked edges for my surface, in order to start a meshing on a good base. I populate the surface with an optimum number of points then I Delaunay them before using anchors and springs to tend to the solution.

I also tried to Galapagos it, I tried =D

My feelings ? Gosh, that is hard. I'm a bit out of my depth, some topology knowledge wouldn't be superfluous. That seems to be a very few explored problem, as you said there's still lots more work that could be done.

Attachments: