Search for twins when implementing the Catmull-Clark division using the Half-Edge mesh

Question

Note. The description has become a little longer than expected. Do you know a readable implementation of this algorithm using this grid? Please let me know!

---

I am trying to implement the Catmull-Clark division using Matlab, because later the results should be compared with some other materials implemented in Matlab. The first attempt was with the Vertex-Face grid, the algorithm works, but it is not very efficient, since you need neighboring information for edges and faces. Therefore, I now use a semi-cross mesh . See also Designing a data structure for polyhedral surfaces, Lutz Kettner (PDF link on this page).

My problem is finding Twin HalfEdges , I just don't know how to do this. Below I describe my thoughts on implementation, trying to keep it concise.

---

Half-screen grid (using indexes to vertices / half-elements / faces):

Vertex (x,y,z,Outgoing_HalfEdge) HalfEdge (HeadVertex (or TailVertex, which one should I use), Next, Face, Twin). Face (HalfEdge) 

To keep it simple, suppose each face is quadrilateral. The actual grid is a list of Vertices, HalfEdges and Faces. The new grid will consist of NewVertices, NewHalfEdges and NewFaces, like this (note: The number _... is the number ... ):

 NumberNewVertices: Number_Faces + Number_HalfEdges/2 + Number_Vertices NumberNewHalfEdges: 4 * 4 * NumberFaces NumberNewfaces: 4 * NumberFaces 

Catmull-Clark:

 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 

So, now all new vertices are calculated (however, their Outgoing_HalfEdge is still unknown). The next step is to save the new HalfEdges and Faces. This is the part that causes 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. 

HeadVertex of each new HalfEdge, Next HalfEdge is known . The face is also known (because it is the new face that you create!). Only Twin HalfEdge is unknown, how can I find out?

By the way, when going through the vertices of a new face, assign Outgoing_HalfEdge vertices. This is probably the place to find out which HalfEdge is Twin.

Finally, after creating 4 new HalfEdges, save the Face with the HalfVertex index of the last recently created HalfVertex.

---

Hope this is clear, if necessary, I can publish my (obviously not yet finished) Matlab code.

---

Change Thank you for moving my thread. I posted a link to the source code in a comment, note that this implementation considers common polygonal meshes, so not only quadrangular meshes.

In addition, the twins of the new HalfEdges 1 and 4 (red numbers in each new face) are pretty easy to find if you think the old quadrangular face is divided into 4 new faces (green numbers):

So, how to find Gemini 2- and 3 HalfEdges?

Answer 1

It seems like the conceptual problem is that you are trying to add in half one at a time, and then wonder how they add up. Edges, however, are a real unit of modification, so you should always add them to pairs.

To implement the (one-pass) algorithm, I will annotate each of the model elements using a “newly created” flag that indicates whether the element was created as a result of the algorithm. The top-level loop is designed to iterate over unmodified faces.

• First make sure that each of the original edges of the face has been split. In doing so, create a list of each “new” vertex pointing to a face; these are midpoints. - a. To break an edge, we first define the corresponding half-cross. Create a new vertex. We insert a new pair of half-edges into each linked list, adjusting the end points to a new vertex. Mark all four half-edges, both new and new peaks.

• The first stop of the split face is different from the rest. Create a new vertex V to be in the middle of the old face, and select the new vertex W incident to the face. We will connect them as follows. Suppose the linked list of edges next to W looks like ..aWb.. Create a new pair of half edges c and d . Replace W in the linked list with WcVdW to create the list "..aWcVdWb ..". This creates a “floating edge” in the middle of the face. However, the data structure ensures that we have a linked list of half edges that represent the inner perimeter of the polygon. Mark the vertex W and the half edges c and d as new.

• Now for each remaining new vertex we will create a new pair of half edges, but this time each pair will also create a new face. Select the previous sequence ..cVdWb.. related lists. Since the entire source edge has been split, this list extends to ..cVdWbXeYf.. X is the old peak, and Y is the new one. Create a new pair of half edges g and g that connect the vertices V and Y Extract the VdWbXeY sequence from the linked list and add g to it to create a new [VdWbXeYg] face. Add half edge h to connect V and Y on the old face to make ..cVhYf.. Mark the new face as new. If there are no more peaks, we are done. If not, match the names ..cVhYf.. and ..cVdWb.. for iteration.

The designation looks rather unpleasant, but conceptually its quite easy. Each of the three steps adds half the ribs in pairs; in step 1, dividing the edge in steps 2 and 3, adding them. Each of these additions keeps the incidence invariants of the multifaceted representation intact, which means that you improve the locality of code modification.