How to subdivide faces with a half edge DS? 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:

If I naively try to iterate over every edge and reconnect faces I get the following sequence



Clearly this is wrong.
If instead I iterate over the faces I get the following pattern:

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 &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:


Any suggestions?
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.



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