Note: The description became a little longer than expected. Do you know a readable implementation of this algorithm using this mesh? Please let me know!
I'm trying to implement Catmull-Clark subdivision using Matlab, because later on the results have to be compared with some other stuff already implemented in Matlab. First try was with a Vertex-Face mesh, the algorithm works but it is not very efficient, since you need neighbouring information for edges and faces. Therefore, I'm now using a half-edge mesh. See also
_Designing a Data Structure for Polyhedral Surfaces_, by Lutz Kettner (PDF link on that page).
My problem lies in finding the Twin HalfEdges, I'm just not sure how to do this. Below I'm describing my thoughts on the implementation, trying to keep it concise.
Half-Edge mesh (using indices to Vertices/HalfEdges/Faces):
HalfEdge (HeadVertex (or TailVertex, which one should I use), Next, Face, Twin).
To keep it simple for now, assume that every face is a quadrilateral. The actual mesh is a list of Vertices, HalfEdges and Faces. The new mesh will consist of NewVertices, NewHalfEdges and NewFaces, like this (note: Number_... is the number of ...):
NumberNewVertices: Number_Faces + Number_HalfEdges/2 + Number_Vertices
NumberNewHalfEdges: 4 * 4 * NumberFaces
NumberNewfaces: 4 * NumberFaces
Find the FacePoint (centroid) of each Face:
--> Just average the x,y,z values of the vertices, save as a NewVertex.
Find the EdgePoint of each HalfEdge:
--> To prevent duplicates (each HalfEdge has a Twin which would result in the same HalfEdge)
--> Only calculate EdgePoints of the HalfEdge which has the lowest index of the Pair.
Update old Vertices
Ok, now all the new Vertices are calculated (however, their Outgoing_HalfEdge is still unknown). Next step to save the new HalfEdges and Faces. This is the part causing me problems!
Loop through each old Face, there are 4 new Faces to be created
(because of the quadrilateral assumption)
First create the 4 new HalfEdges per New Face, starting at the FacePoint to the Edgepoint
Next a new HalfEdge from the EdgePoint to an Updated Vertex
Another new one from the Updated Vertex to the next EdgePoint
Finally the fourth new HalfEdge from the EdgePoint back to the FacePoint.
The HeadVertex of each new HalfEdge is known, the Next HalfEdge too. The Face is also known (since it is the new face you're creating!). Only the Twin HalfEdge is unknown, how should I know this?
By the way, while looping through the Vertices of the new Face, assign the Outgoing_HalfEdge to the Vertices. This is probably the place to find out which HalfEdge is the Twin.
Finally, after the 4 new HalfEdges are created, save the Face with the HalfVertex index the last newly created HalfVertex.
I hope this is clear, if needed I can post my (obviously not-yet-finished) Matlab code.
Edit: Thanks for moving my thread. I posted a link to the source code in a comment, please notice that this implementation considers general polygonal meshes, so not only quadrilateral meshes.
Furthermore, the twins of new HalfEdges 1 and 4 (red numbers in each new Face) are rather easy to find if you consider an old quadrilateral face divided into 4 new Faces (green numbers):
So, how to find the Twins of the 2- and 3 HalfEdges?