1
$\begingroup$

I would like to be able to insert random faces into a half edge, assuming the new face does not share any edge with more than one existing face.

There is one scenario which is proving quite difficult to implement. Hourglass/umbrella non manifold edges.

Imagine something like this: enter image description here

Say the top triangle was present and we are adding the new triangle. What we want is to attach the half edges in the boundary in such a way that they form a single non crossing chain. Without having to do any geometry measurements, only topological (i.e. connections).

This would be the result in this case:

enter image description here

it is suprisingly hard to do this in the general case and I keep running into configurations where the insertion fails, for example this one (The yellow dots are the vertices of a tentative new triangle).

enter image description here

I was hoping someone knows of a resource that talks about how to insert new faces into an existing half edge that covers these cases.

Improve this question
$\endgroup$
3
  • $\begingroup$ You mark the triangle with 3 yellow verts to show this is the intended result as opposed to the near-zero area triangle that goes across the hourglass choke-point? This is your visual bias, but you can play around with the mesh and see that, at least locally if you take just a few triangles around the hourglass hole, you can move verts in such a way that you produce a manifold mesh by starting with red and blue triangles: i.imgur.com/vIO2dMy.png - so it seems the "topological" solution you request isn't possible... $\endgroup$ Commented Jul 10 at 18:06
  • $\begingroup$ ...but you could for each vertex see the triangles it can create and sort them by area and try to create the biggest area triangles or maybe sort by relative difference between sides and choose the triangles that are the closest to equilateral shape. $\endgroup$ Commented Jul 10 at 18:07
  • $\begingroup$ @MarkusvonBroady I just answered the question. There is a topological solution for this problem. $\endgroup$ Commented Jul 10 at 19:07

1 Answer 1

Reset to default
0
$\begingroup$

The topological solution to this problem is as follows. Before inserting the triangle, for each vertices that will make up the new triangle, find ALL half edge pairs that are on the boundary, each pair consisting of an incoming and an outgoing half edge.

Then, for each edge in the inner winding of the new triangle, remove it from its respective groups (i.e. one outgoing and one incoming member of two different pairs).

Then, look at any newly introduced half edges, and insert them appropriately into the incomplete pairs. So for example if the triangle fits into a wedge hole, then a single half edge on the outer border of the triangle is now a boundary edge. This boundary edge must now find two pairs, which are no incomplete and insert itself as the incoming edge in one and the outgoing pair in the other.

After this some pairs will be fully empty and must be pruned. For the surviving pairs, attach their next and prev pointers.

Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.