<p>No one answered so I will. The solution is to do the subdivision in 2 passes, first generating new triangles as I showed in the question.</p>

<p>Then on the second pass you flip them.</p>

<p><a href="https://i.sstatic.net/75X6y.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/75X6y.png" alt="enter image description here"></a></p>

<p>As described there:
<a href="https://github.com/cmu462/Scotty3D/wiki/Loop-Subdivision" rel="nofollow noreferrer">https://github.com/cmu462/Scotty3D/wiki/Loop-Subdivision</a></p>

CC BY-SA 4.0
2020-02-13T02:37:45.817Z
2020-02-13T02:37:45.817Z
Makogan
<p>Assume we have a mesh represented as a half edge datastructure.</p>
<p>We want to subdivide faces without introducing unnecessary vertices (i.e the new number of vertices must be exactly V + E where V is the old number of vertices and E is the old number of edges).</p>
<p>This is what a single subdivided triangle looks like:
<a href="https://i.sstatic.net/MYmhk.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/MYmhk.png" alt="enter image description here" /></a></p>
<p>If I naively try to iterate over every edge and reconnect faces I get the following sequence
<a href="https://i.sstatic.net/Jgn94.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/Jgn94.png" alt="enter image description here" /></a>
<a href="https://i.sstatic.net/D4SZe.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/D4SZe.png" alt="enter image description here" /></a>
<a href="https://i.sstatic.net/04SMi.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/04SMi.png" alt="enter image description here" /></a></p>
<p>Clearly this is wrong.</p>
<p>If instead I iterate over the faces I get the following pattern:</p>
<p><a href="https://i.sstatic.net/vWp6b.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/vWp6b.png" alt="enter image description here" /></a></p>
<p>This is happening because at every step I am trying to to:</p>
<ul>
<li>Focus on only one simplex at a time,</li>
<li>Maintain the connectivity information of the mesh in a valid state (every edge has &lt;2 faces, vertices only exist at the end of edges, faces only have 3 Half edges...), like for example, I am avoiding getting into this state:</li>
</ul>
<p><a href="https://i.sstatic.net/4SexY.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/4SexY.png" alt="enter image description here" /></a></p>
<p>Any suggestions?</p>

<computational-geometry><mesh><geometry>
How to subdivide faces with a half edge DS?
Makogan
# How to subdivide faces with a half edge DS?

(Asked by: username_0 on 2020-02-04)

Assume we have a mesh represented as a half edge datastructure.

We want to subdivide faces without introducing unnecessary vertices (i.e the new number of vertices must be exactly V + E where V is the old number of vertices and E is the old number of edges).

This is what a single subdivided triangle looks like:
[![enter image description here](https://i.sstatic.net/MYmhk.png)](https://i.sstatic.net/MYmhk.png)

If I naively try to iterate over every edge and reconnect faces I get the following sequence
[![enter image description here](https://i.sstatic.net/Jgn94.png)](https://i.sstatic.net/Jgn94.png)
[![enter image description here](https://i.sstatic.net/D4SZe.png)](https://i.sstatic.net/D4SZe.png)
[![enter image description here](https://i.sstatic.net/04SMi.png)](https://i.sstatic.net/04SMi.png)

Clearly this is wrong.

If instead I iterate over the faces I get the following pattern:

[![enter image description here](https://i.sstatic.net/vWp6b.png)](https://i.sstatic.net/vWp6b.png)

This is happening because at every step I am trying to to:

* Focus on only one simplex at a time,
* Maintain the connectivity information of the mesh in a valid state (every edge has <2 faces, vertices only exist at the end of edges, faces only have 3 Half edges...), like for example, I am avoiding getting into this state:

[![enter image description here](https://i.sstatic.net/4SexY.png)](https://i.sstatic.net/4SexY.png)

Any suggestions?

**Tags:** computational-geometry, mesh, geometry


---

## 1 answers

### Answer by username_0 on 2020-02-13. Score: 2 | Accepted answer

No one answered so I will. The solution is to do the subdivision in 2 passes, first generating new triangles as I showed in the question.

Then on the second pass you flip them.

[![enter image description here](https://i.sstatic.net/75X6y.png)](https://i.sstatic.net/75X6y.png)

As described there:
<https://github.com/cmu462/Scotty3D/wiki/Loop-Subdivision>


---

