Mesh Face Offset

[PetrVacek]

Hi. I am dealing with a mesh thickening based on face normal rather than on vertex normal. The goal is to achieve a better control over thickened structure to make it 3D printable. Using Dendro plugin is not an option thanks to the aim to deploy the code on ShapeDiver. I expect the input mesh to have around 15k faces. I also found this topic OffsetMesh needs more work but there’s been nothing new for two years.

The problem:

The approach:

1. get list of faces sharing one vertex (is there a faster way than C# MeshTopologyVertexList.ConnectedEdges method? It costs a lot of computation time…)
2. construct planes and calculate angle between each face normal and vertex normal
3. use trigonometry to calculate length of vertex normal vectors for each face normal vector
4. average these vectors to get resulting vertex vector lenght
5. move vertex, construct mesh using the same mesh topology

Promising, but…

I’ve found many promising approaches online but it’s beyond my skills to recreate them. (paper 1, paper 2, paper 3) Is there a better way to achieve my goal?
I’ve tried also:

• Kangaroo Face Offset (doesn’t work with a variable offset)
• WB Mesh Thicken (offset using vertex normal, not face normal)
• Dendro (computation time too long, resulting mesh too rough)
• moving each face plane by face normal vector, finding it’s intersecting point (problematic around flat areas of the mesh)

Could someone give me a hint, please?

MeshFaceOffset_PetrVacekGH.gh (25.0 KB)

[DanielPiker]

Hi @PetrVacek

It is geometrically impossible to have a parallel face-face offset for a general mesh with the same topology and vertices as the original.

The Face-face offset component in Kangaroo says in its description that it is for conical meshes, which are a special case where a face-face offset with the same topology is possible. Using it for other meshes will not work.

A set of 1 vector per vertex by which you can move them to get a mesh with parallel faces just does not exist for general meshes. So no sort of vector averaging approach will work.

In general if you offset the faces, when there are more than 3 faces around a vertex, the offset faces won’t all intersect in a common point, so the only way to have a parallel offset is to introduce new vertices and edges.
What’s worse, even when introducing these new vertices in the offset, the result is not uniquely determined by the offset distance and you sometimes have to choose between different possible topologies.

For instance, take a look at this example. In both cases the lower mesh is the same and the faces of the upper mesh are valid parallel and equal distance offsets, yet the topology is different.
face_face_offset_example.3dm (62.2 KB)

I did make a start on implementing the approach given in the paper below for creating the new vertices and choosing between the valid options. I’ll have another look tomorrow and see how much work it would be to turn it into something usable.

(PDF) Exact face-offsetting for polygonal meshes

[René_Corella]

Here’s an unrelated lazy quickie that doesn’t work either.

It could employ a more elegant system for sure (so that faces displaced with more coherence along ‘top and bottom’ or ‘interior’ regions for shapes like ‘0’ or ‘8’).

It could also just be ignored.

MeshFaceOffset_PetrVacekGH.gh (17.7 KB)

[PetrVacek]

Thank you @DanielPiker and @René_Corella and also @ThomasE for insights. Seems like it’s quite a complex problem to solve. I dig the approach shared by Thomas and did my own mods. How about this:

1. get list of faces sharing one vertex, compute their planes and move planes by face normal to a certain distance
2. get list of neighbour vertices of one vertex, construct vectors to all of them and find the average
3. average vertex normal and vertex “pseudo-normal” from previous step
4. intersect face planes and “pseudo-normal” line obtaining multiple points
5. calculate distances between vertex and intersection points
6. get weighed average (to get rid of extremes)
7. move vertex, construct the new mesh

Definitely not a perfect approacht, but it somehow works… What do you think about that?

MeshFaceOffset_PetrVacekGH_2.gh (42.8 KB)

[DanielPiker]

It seems a bit unclear to me what you are actually after.
You started by saying you want a face-face offset, and showed a diagram illustrating that you want constant face to face distances - ie parallel faces.
What you show above is another way of computing one normal per vertex and moving the out along this, which does not solve this problem.

To illustrate, take the example of trying to offset this red rectangular pyramid by moving the vertices.
We take planes offset by unit distance from each of the 2 big faces of the pyramid. We know that for the offset mesh to have constant face-face distance, the new top point must lie on both of these planes, i.e. it must be somewhere on the magenta intersection line.
We also take unit offset planes from the 2 small faces. By the same logic the point must also lie on their intersection - the green line.

So what you are trying to do boils down to finding a single vector you can move the top point along to get a single new point which somehow lies on both the green and the magenta lines… but this is clearly impossible as the lines do not intersect, so no such point exists.

You can use various weighting schemes to average the face normals to distribute the error, but there will be variations in face-face distance, so it is not a face-offset mesh. (depending what you want to do with this it might not matter though)

To get a true constant distance parallel face offset mesh though, you need 2 top points like this:

For purely convex vertices the solution is not too hard to find and there is only one possibility without self intersections. For the general case though, where the edges coming into the vertex are a mix of up/down folds, there can be many* different topological solutions, some of which will be self-intersecting and some of which are not. Finding a good one among these is the tricky bit.

*actually the number of possibilities increases as the Catalan number of connected faces -2. So for 3 faces there’s a single solution, for 4 there are 2, but they go up fast, For a vertex surrounded by 10 faces you’d need to check 1430 different possibilities if brute forcing it (I’m still trying to figure out if there’s a better way, perhaps using straight skeleton or motorcycle graph along the lines described here).