<p>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)</p>
<p>The second example is vague since it involves 3 triangles.</p>
<p>Given any <em>two</em> 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.</p>
<p>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.</p>
<hr />
<p>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)</p>
<hr />
<p>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.</p>

CC BY-SA 4.0
2021-11-24T05:47:10.327Z
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.
Makogan
CC BY-SA 4.0
2021-11-24T11:41:40.890Z
It  should be okay to talk about geometry even if the final solution doesn't use it.
pmw1234
CC BY-SA 4.0
2021-11-24T17:54:51.333Z
@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.
lightxbulb
CC BY-SA 4.0
2021-11-23T15:38:11.917Z
2021-11-24T11:50:03.190Z
2021-11-24T11:50:03.190Z
pmw1234
<p>Let the edge to be flipped be made up of <span class="math-container">$v_l, \, v_r$</span>. This edge needs to be part of 2 triangles (cannot be a boundary edge). Let the remaining vertices of the two triangles be <span class="math-container">$v_t, \, v_b$</span>. Now consider the triangles adjacent to the edges <span class="math-container">$e_1 = v_tv_l$</span>, <span class="math-container">$e_2 = v_lv_b$</span>, <span class="math-container">$e_3= v_bv_r$</span>, <span class="math-container">$e_4=v_rv_t$</span>. If the triangle adjacent to <span class="math-container">$e_1$</span> is the same as the one to <span class="math-container">$e_2$</span> disallow the flip (except for the boundary face). Similarly for <span class="math-container">$e_3$</span> and <span class="math-container">$e_4$</span>. 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.</p>

CC BY-SA 4.0
2021-11-24T07:00:51.420Z
Assuming the triangulation is manifold is a very sane thing to do : P
Makogan
CC BY-SA 4.0
2021-11-24T07:42:14.100Z
@Makogan It depends on the application.
lightxbulb
CC BY-SA 4.0
2021-11-24T06:29:10.250Z
2021-11-24T06:29:10.250Z
lightxbulb
<p>The existing answers and comment cover the main case I think for the iterative edge flip (CPU). So I am going to generalize a bit and describe what worked for me in the case of manifold parallel edge flip (I implemented that on the GPU). I include it because it seems that in 2024 meshes are big and most new implementations are going to be parallel for performance reasons.</p>
<p>We put restriction on the mesh to make it manifold. Assume you have a well behaved mesh isomorphic to a ball (no duplicate triangles, no duplicate vertices, every edge has two triangles touching, consistent orientation - basically no holes and can be brought back to an spherical mesh).</p>
<p>In that case, the criteria that preserve the manifold characteristics are:</p>
<ol>
<li><p>The criterion you gave. Flipping an edge should not create duplicate triangles. In your case we end up with two identical triangles.</p>
</li>
<li><p>In the parallel case, we also have to check for a diamond pattern with a cross inside (v0-v1-v2, v1-v0-v3, v4-v0-v2, v4-v3-v0) if you flip v1-v0 and v4-v0 then you have duplicate triangles, v2-v3-v0 is featured  twice.
<a href="https://i.sstatic.net/bZ1yVTPU.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/bZ1yVTPU.png" alt="enter image description here" /></a></p>
</li>
</ol>
<p>Now, I know you don't care about angles or mesh quality, but I will discuss it for the sake of completeness. For a good looking mesh we want to add:</p>
<ol start="3">
<li><p>The convexity criterion described in the other answers (the diamond made by the two triangles has no reflex angle, &gt;180 deg). Ignoring it should not break your mesh in the manifold sense I defined but it can create self intersections and visual artifacts, so it's better to include it.</p>
</li>
<li><p>Some criterion to check if flipping the edge improves our cost function. For instance we want to increase the min angle of the two triangles. (out of scope)</p>
</li>
</ol>
<p>I will update my answer if I run into more edge cases.</p>

CC BY-SA 4.0
2024-11-13T02:55:58.730Z
2024-11-13T19:17:43.130Z
2024-11-13T19:17:43.130Z
Etienne D
<p>I am trying to determine if and when flipping an edge is topologically valid.</p>
<p>The current criterion I have is that it is only valid if there is no edge connecting the opposite vertices of the edge.</p>
<p>I.e. consider these 2 drawings where the first allows for a valid edge flip but the second does not.</p>
<p><a href="https://i.sstatic.net/nKy3p.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/nKy3p.png" alt="enter image description here" /></a></p>
<p>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.</p>
<p>A possibly non inclusive set of restrictions on topological requirements of a half edge mesh:</p>
<p>All vertices are connected by either exactly 0 or exactly 1 edge (an edge flip can accidentally invalidate this).</p>
<p>All edges are contained in a face (the boundary face counts as a face).</p>
<p>There are no &quot;butterfly holes&quot;, (2 triangles that share a vertex but no edges and no other triangles containing that vertex).</p>
<p>2 triangles cannot share more than one edge between them.</p>
<p>etc...</p>
<p>The above are all examples of topological requirements, this is what we are trying to preserve.</p>

CC BY-SA 4.0
2021-10-31T07:33:22.187Z
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$.
lightxbulb
CC BY-SA 4.0
2021-10-31T07:44:28.797Z
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.
lightxbulb
CC BY-SA 4.0
2021-11-01T05:07:33.493Z
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.
Makogan
CC BY-SA 4.0
2021-11-01T09:30:45.460Z
How would 3D make the $\leq 180$ flip valid? Do you have a counterexample?
lightxbulb
CC BY-SA 4.0
2021-11-01T20:36:41.857Z
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.
Makogan
CC BY-SA 4.0
2021-11-01T21:16:07.597Z
You can't edge flip when the polygon is not situated in a plane. It doesn't make sense either, at least in the context I envision. What is the context in which you need these edge flips?
lightxbulb
CC BY-SA 4.0
2021-11-02T00:38:47.747Z
You can, whether it's a good or a abd idea depends on application, but you can do it as long as the flip doesn't damage the topology of the mesh.

Since most meshes are manifold, they are locally 2D euclidean, thus everything is "flat" locally. 

I need to flip the edges to fix some degenerate triangles (i.e. similar to making the mesh more Delauny like, but not quite the same). The primary issue is that I should only do this if flipping an edge won't break topology, which as described above it can. I need a check for when an edge flip is topologically valid.
Makogan
CC BY-SA 4.0
2021-11-02T01:16:50.617Z
Clearly if the two triangles don't lie in a single plane then the flip changes the surface (so I am assuming it's topologically invalid by your definition). If on the other hand the two triangles lie in a single plane then the convexity/180 degree criterion works. I think this covers all of the cases, unless you have some more formal definition of topologically valid edge flip.
lightxbulb
CC BY-SA 4.0
2021-11-02T01:26:05.003Z
Topologically valid means agnostic to geometry. I.e. it is a graph connectivity problem. Remember, for a topologist a mug and a donut are the same thing. 

So I could reword the question as, when does an edge flip lead to a mesh graph with invalid connections.

On criterion i found but doesn;t seem sufficient, and it;s the one presented oin the bottom on the image, is you cannot flip an edge in a butterfly where the ends of the butterfly are connected already (you get 2 vertices with 2 edges, which is not topologically valid).
Makogan
CC BY-SA 4.0
2021-11-02T09:10:42.683Z
Just off the top of my head: if you have two triangles sharing an edge, where any of the angles to the edge (in each triangle) is greater than $90$ degrees. Seems to work since each triangle is planar, and it disallows a flip for your second image.
lightxbulb
CC BY-SA 4.0
2021-11-23T09:12:13.370Z
Since you explicitly do not want geometric information (e.g. angles) you can try the criterion: as long as none of the remaining edges are shared by the same triangle. In you second example two edges are shared by a single triangle. If you were to split that triangle into two then the flip would be allowed.
lightxbulb
CC BY-SA 4.0
2021-11-23T10:46:48.697Z
Actually you should probably give a more precise definition of what you envision to be topologically valid. As currently I can flip the edge in the second image by "preserving the topology" in the same sense as in your first figure. So what topological invariant are you trying to preserve?
lightxbulb
CC BY-SA 4.0
2021-11-24T05:54:03.390Z
You cannot in teh second image, you will create a set of 2 vertices with 2 connecting edges.
Makogan
CC BY-SA 4.0
2021-11-24T06:19:30.787Z
I wasn't aware of this no more than 1 edge restriction. As to how this can be flipped (if that restriction was not in place): consider it in 3d and push the central vertex over to the left until the angle opens up (this is a smooth transformation thus the topology doesn't change), now flip. Everything is fine at this point. The criterion of an adjacent triangle not sharing two of the edges in the configuration to be flipped seems to work even with your requirements in mind though. Or at least it works in both of your examples.
lightxbulb
<mathematics><computational-geometry><geometry><half-edge>
Half Edge criterion to check if an edge flip is illegal?
Makogan
# Half Edge criterion to check if an edge flip is illegal?

(Asked by: username_0 on 2021-10-30)

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](https://i.sstatic.net/nKy3p.png)](https://i.sstatic.net/nKy3p.png)

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.

**Tags:** mathematics, computational-geometry, geometry, half-edge

> **Comments:**
> **username_1**: 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$.  
> **username_1**: 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.  
> **username_0**: 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.  
> **username_1**: How would 3D make the $\leq 180$ flip valid? Do you have a counterexample?  
> **username_0**: 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.  
> **username_1**: You can't edge flip when the polygon is not situated in a plane. It doesn't make sense either, at least in the context I envision. What is the context in which you need these edge flips?  
> **username_0**: You can, whether it's a good or a abd idea depends on application, but you can do it as long as the flip doesn't damage the topology of the mesh.  Since most meshes are manifold, they are locally 2D euclidean, thus everything is "flat" locally.   I need to flip the edges to fix some degenerate triangles (i.e. similar to making the mesh more Delauny like, but not quite the same). The primary issue is that I should only do this if flipping an edge won't break topology, which as described above it can. I need a check for when an edge flip is topologically valid.  
> **username_1**: Clearly if the two triangles don't lie in a single plane then the flip changes the surface (so I am assuming it's topologically invalid by your definition). If on the other hand the two triangles lie in a single plane then the convexity/180 degree criterion works. I think this covers all of the cases, unless you have some more formal definition of topologically valid edge flip.  
> **username_0**: Topologically valid means agnostic to geometry. I.e. it is a graph connectivity problem. Remember, for a topologist a mug and a donut are the same thing.   So I could reword the question as, when does an edge flip lead to a mesh graph with invalid connections.  On criterion i found but doesn;t seem sufficient, and it;s the one presented oin the bottom on the image, is you cannot flip an edge in a butterfly where the ends of the butterfly are connected already (you get 2 vertices with 2 edges, which is not topologically valid).  
> **username_1**: Just off the top of my head: if you have two triangles sharing an edge, where any of the angles to the edge (in each triangle) is greater than $90$ degrees. Seems to work since each triangle is planar, and it disallows a flip for your second image.  
> **username_1**: Since you explicitly do not want geometric information (e.g. angles) you can try the criterion: as long as none of the remaining edges are shared by the same triangle. In you second example two edges are shared by a single triangle. If you were to split that triangle into two then the flip would be allowed.  
> **username_1**: Actually you should probably give a more precise definition of what you envision to be topologically valid. As currently I can flip the edge in the second image by "preserving the topology" in the same sense as in your first figure. So what topological invariant are you trying to preserve?  
> **username_0**: You cannot in teh second image, you will create a set of 2 vertices with 2 connecting edges.  
> **username_1**: I wasn't aware of this no more than 1 edge restriction. As to how this can be flipped (if that restriction was not in place): consider it in 3d and push the central vertex over to the left until the angle opens up (this is a smooth transformation thus the topology doesn't change), now flip. Everything is fine at this point. The criterion of an adjacent triangle not sharing two of the edges in the configuration to be flipped seems to work even with your requirements in mind though. Or at least it works in both of your examples.  

---

## 3 answers

### Answer by username_2 on 2021-11-23. Score: 1

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.

> **Comments:**
> **username_0**: 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.  
> **username_2**: It  should be okay to talk about geometry even if the final solution doesn't use it.  
> **username_1**: @username_2 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.  

---

### Answer by username_1 on 2021-11-24. Score: 1

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.

> **Comments:**
> **username_0**: Assuming the triangulation is manifold is a very sane thing to do : P  
> **username_1**: @username_0 It depends on the application.  

---

### Answer by username_3 on 2024-11-13. Score: -2

The existing answers and comment cover the main case I think for the iterative edge flip (CPU). So I am going to generalize a bit and describe what worked for me in the case of manifold parallel edge flip (I implemented that on the GPU). I include it because it seems that in 2024 meshes are big and most new implementations are going to be parallel for performance reasons.

We put restriction on the mesh to make it manifold. Assume you have a well behaved mesh isomorphic to a ball (no duplicate triangles, no duplicate vertices, every edge has two triangles touching, consistent orientation - basically no holes and can be brought back to an spherical mesh).

In that case, the criteria that preserve the manifold characteristics are:

1. The criterion you gave. Flipping an edge should not create duplicate triangles. In your case we end up with two identical triangles.
2. In the parallel case, we also have to check for a diamond pattern with a cross inside (v0-v1-v2, v1-v0-v3, v4-v0-v2, v4-v3-v0) if you flip v1-v0 and v4-v0 then you have duplicate triangles, v2-v3-v0 is featured twice.
   [![enter image description here](https://i.sstatic.net/bZ1yVTPU.png)](https://i.sstatic.net/bZ1yVTPU.png)

Now, I know you don't care about angles or mesh quality, but I will discuss it for the sake of completeness. For a good looking mesh we want to add:

3. The convexity criterion described in the other answers (the diamond made by the two triangles has no reflex angle, >180 deg). Ignoring it should not break your mesh in the manifold sense I defined but it can create self intersections and visual artifacts, so it's better to include it.
4. Some criterion to check if flipping the edge improves our cost function. For instance we want to increase the min angle of the two triangles. (out of scope)

I will update my answer if I run into more edge cases.


---

