1
$\begingroup$

I am trying to determine if and when flipping an edge is topologically valid.

The current criterion I have is that it is only valid if there is no edge connecting the opposite vertices of the edge.

I.e. consider these 2 drawings where the first allows for a valid edge flip but the second does not.

enter image description here

To clarify what we mean by topological validity. Topology does not care about geometric information such as angles, the reason the second triangle does not allow for edge flips is, pick any edge between the face center and the other vertices a flip would create a set of 2 vertices with 2 edges in between them, this is wrong.

A possibly non inclusive set of restrictions on topological requirements of a half edge mesh:

All vertices are connected by either exactly 0 or exactly 1 edge (an edge flip can accidentally invalidate this).

All edges are contained in a face (the boundary face counts as a face).

There are no "butterfly holes", (2 triangles that share a vertex but no edges and no other triangles containing that vertex).

2 triangles cannot share more than one edge between them.

etc...

The above are all examples of topological requirements, this is what we are trying to preserve.

Improve this question
$\endgroup$
14
  • $\begingroup$ Name the vertices $v_u, v_d, v_l, v_r$ for up, down, left, right. The edge flip in the above would be swapping $v_l, v_r$ with $v_u, v_d$. That is, for triangles $v_u, v_l, v_r$ and $v_d, v_l, v_r$ sharing the edge $v_l, v_r$ the vertices not part of the edge must become edge vertices, which yields triangles $v_u, v_l, v_d$ and $v_d, v_r, v_u$. $\endgroup$
    – lightxbulb
    Oct 31, 2021 at 7:33
  • $\begingroup$ The issue with the second is that any 2 triangles there do not cover the convex set formed by their 4 vertices. You basically have outside angles $\leq 180$ for any of the configurations of 2 triangles sharing an edge. $\endgroup$
    – lightxbulb
    Oct 31, 2021 at 7:44
  • $\begingroup$ Take into account that these 2 are just examples, but a criterion should also work in 3D, where the angles could also be less than 180 without the edge flip being necessarily invalid. $\endgroup$
    – Makogan
    Nov 1, 2021 at 5:07
  • $\begingroup$ How would 3D make the $\leq 180$ flip valid? Do you have a counterexample? $\endgroup$
    – lightxbulb
    Nov 1, 2021 at 9:30
  • $\begingroup$ Imagine taking the top image in my example and folding it until the 2 triangles almost touch, i.e. the dihedral angle is really small. The outside angle is now < 180, but the edge flip is still topologically valid. $\endgroup$
    – Makogan
    Nov 1, 2021 at 20:36

2 Answers 2

Reset to default
1
$\begingroup$

Let the edge to be flipped be made up of $v_l, \, v_r$. This edge needs to be part of 2 triangles (cannot be a boundary edge). Let the remaining vertices of the two triangles be $v_t, \, v_b$. Now consider the triangles adjacent to the edges $e_1 = v_tv_l$, $e_2 = v_lv_b$, $e_3= v_bv_r$, $e_4=v_rv_t$. If the triangle adjacent to $e_1$ is the same as the one to $e_2$ disallow the flip (except for the boundary face). Similarly for $e_3$ and $e_4$. This is consistent with your criterion of the vertices not gaining an extra edge. I have assumed that your triangulation is manifold in order to guarantee that an edge is shared by at most 2 triangles.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Assuming the triangulation is manifold is a very sane thing to do : P $\endgroup$
    – Makogan
    Nov 24, 2021 at 7:00
  • $\begingroup$ @Makogan It depends on the application. $\endgroup$
    – lightxbulb
    Nov 24, 2021 at 7:42
1
$\begingroup$

Edge flipping is considered a local operation of 1 edge between the points making up two triangles. (see the book polygon mesh processing for references as to why this is the case)

The second example is vague since it involves 3 triangles.

Given any two triangles that share a single edge, an edge flip is topologically valid only when the triangles form a convex quadrilateral. To check that two triangles from a convex quad: Compute the interior angle between all the connected edges, if any of the angles is greater then 180 degrees then the resulting polygon is concave.

This will give some cases where the edge flip results in an edge collapse because the new edge coincides with an existing edge. To detect an edge collapse it is usually easiest to just calculate the area of the two resulting triangles and only accept edge flips that result in two triangles with some preset min area.

In other words, if an interior edge is flipped on a concave polygon formed by two triangles sharing a single edge then the flipped edge will cross at least one of the other edges. Meaning that some portion of the flipped edge will be exterior to the original quad. Meaning that the edge will lie on a different side of at least one of the original edges. So flip the edge and check that it doesn't cross another edge by any means you choose. (only the edges of the two triangles that share a common edge need be checked)

A better solution is to remesh the entire topology such that any valid flip is legal.(again flips are only valid on edges between two triangles, and it must always be a local operation). There are many excellent algorithms for this operation, and it creates a new mesh that can be processed through heavily pipelined tool sets.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Looking at angles and convexion is looking at geometry. As specified in the problem clarification we are looking for topological validity. Topology in this sense means the graph connectivity. $\endgroup$
    – Makogan
    Nov 24, 2021 at 5:47
  • $\begingroup$ It should be okay to talk about geometry even if the final solution doesn't use it. $\endgroup$
    – pmw1234
    Nov 24, 2021 at 11:41
  • $\begingroup$ @pmw1234 I guess the point is that the OP wants this to work for arbitrary geometry with a specific discrete topology (I don't mean the power set with discrete topology, I know it's confusing but the terms have multiple meanings) . Hence topologically valid. Albeit I do agree that the question wasn't clear enough initially, but figuring out the topological invariants to be preserved constituted most of the answer really. $\endgroup$
    – lightxbulb
    Nov 24, 2021 at 17:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.