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