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

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

Clearly this is wrong.

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

enter image description here

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

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.

enter image description here

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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