Section II: Triangle Meshes and Half-Edge Data Structure

Important Note:

• In Section II, you will be working extensively with the half-edge data structure, as well as the provided HalfedgeMesh class, which implements the data structure.
• Before diving into this section, we recommend that you read this introduction to half-edge data structure to reinforce your understanding of it from Lecture 8.
• We also highly, highly recommend that you carefully read through this primer on how to navigate meshes using the HalfedgeMesh class. The primer will help you get familiar with the provided HalfedgeMesh class quickly and present many examples, complete with code, that you may find very helpful for this section!
• Finally, we encourage you to read and understand the documentation at the beginning of halfedgeMesh.h, which provides supplementary information to the primer.

In Section I, you have implemented Bezier surfaces, which are parametric surfaces defined by a 2D grid of control points. As discussed in lecture, we can also represent surfaces using triangle meshes. While Bezier surfaces are better at representing smooth surfaces than triangle meshes and require less memory, Bezier surfaces are much more difficult to render directly. (Can you reason why this is the case?) In fact, Bezier surfaces are often converted into triangle meshes before being rendered to screen.

As a result, triangle meshes are sometimes the preferred way to represent 3D geometric models in computer graphics. One way to store a triangle mesh is as a list of vertices and a list of triangles indexing the vertices, illustrated in this lecture slide. Unfortunately, such simple data structure does not allow for meaningful traversal of meshes required by many geometry processing tasks. For example, to find all triangles neighbouring a given triangle, we must iterate through the entire list of triangles, which can be prohibitively expensive if the mesh has millions of triangles.

To help answer the neighbouring triangle query and many others more efficiently, the half-edge data structure explicitly stores the connectivity information among mesh elements, i.e., vertices, edges, and faces. Throughout this section, you will use the half-edge data structure to implement a few commonly used geometric operations; and we hope you will get to appreciate the simplicity and flexibility of this data structure.

Part 3: Area-Weighted Vertex Normals

Relevant lecture: 8

In Part 3, you will implement area-weighted normal vectors at vertices. Recall from lecture that these vertex normals can be used for Phong shading, which provides better shading for smooth surfaces than flat shading (image credit: Wikipedia).

To get started, take a look at the Vertex class defined in halfedgeMesh.h, along with the very helpful comments within the class. In short, a Vertex object encapsulates a single mesh vertex and has member variables such as the following (the list is not exhaustive):

• Vector3D position: The 3D coordinate of this vertex.
• HalfedgeIter& halfedge: A reference to the half-edge rooted at this vertex.
• HalfedgeCIter halfedge: The same half-edge as above, except this variable is const (i.e., constant) and cannot be modified.

To compute an area-weighted normal at a given vertex, you should use the half-edge data structure to iterate through faces (triangles) incident to the vertex, i.e., faces that have the given vertex as one of its vertices. For each such face, you weight its normal by its area. Finally, you normalize the sum of all area-weighted normals.

You need to implement this part in Vertex::normal() in student_code.cpp. This function takes no input and outputs the area-weighted vertex normal. Since normal() is a member function of the Vertex class, you have access to the class member variables, such as Vector3D position, within the function. To understand how to iterate through faces incident to a vertex, you may find the example printNeighborPositions(...) in this primer helpful. (Hint: A face in the half-edge data structure only points to its associated half-edge. To compute the area and normal of a face, what you really need are its three vertices instead of the face itself. A normal of a face is defined as a vector perpendicular to the surface at a given point. The cross product of two vectors along the face would return a third vector perpendicular to the two vectors.)

Implementation Notes

For Part 3 only, you are implementing a const (i.e., constant) member function, which requires that no code within this function modifies any member variables. This just means that you should use HalfedgeCIter and not HalfedgeIter in Vertex::normal().

For more information on the differences between Halfedge *, HalfedgeIter, and HalfedgeCIter, check out this short article on Iterators vs Pointers.

You may also find this CGL Vector Documentation helpful for implementing any operations between vectors.

Sanity Check

To check if your implementation is likely correct, you can run meshedit with a COLLADA mesh file (.dae). Once the model is loaded, press Q to toggle the area-averaged normals, which calls Vertex::normal() you have implemented, and the shading of the model should become smoother and no longer flat. Refer back here for a list of controls for Section I Part 2 and onwards.

For example, you can run the following command:

./meshedit ../dae/teapot.dae

After you press Q, the shading of the teapot should look smooth like the image below. If your shading differs from the image, your implementation of Vertex::normal() is likely incorrect. One common mistake is that the computed normals point towards the interior of the model, as opposed to the exterior required by computer graphics. The oppositely oriented normals lead to very dark shading, which can be fixed by reversing the normals.

Functions to Modify: Part 3

• Vertex::normal()

For Your Write-Up: Part 3

For Homework 2, you can use your native screenshotting systems (there is no hotkey for screenshotting).

• Briefly explain how you implemented the area-weighted vertex normals.
• Show screenshots of dae/teapot.dae (not .bez) comparing teapot shading with and without vertex normals. Use Q to toggle default flat shading and Phong shading.

Part 4: Edge Flip

Relevant lecture: 8

In Part 4, you will implement a local remeshing operation on an edge, called a flip. Given a pair of triangles $(a,b,c)$ and $(c,b,d)$, a flip operation on their shared edge $(b,c)$ converts the original pair of triangles into a new pair $(a,d,c)$ and $(a,b,d)$, as shown below:

You need to implement this part in HalfedgeMesh::flipEdge(...) in student_code.cpp. This function takes as input an EdgeIter to an edge that needs to be flipped, e.g., edge $(b,c)$ above, and outputs an EdgeIter to the now flipped edge, e.g., edge $(a,d)$ above.

Mesh Pointer Recommendations

To properly implement any remeshing operations, you need to take extra care to make sure that, in the modified mesh, all pointers of all mesh elements still point to the right elements. A mesh element is a half-edge, vertex, edge, or face. Here is a refresher on what each mesh element points to. We recommend that you perform the following steps to ensure that all pointers of all elements are still valid after remeshing operations, such as edge flips in this part or edge splits in the next part:

1. Draw a simple mesh, such as the pair of triangles $(a,b,c)$ and $(c,b,d)$ above, and write down a list of all elements, i.e., half-edges, vertices, edges, and faces, in this mesh.
2. Draw the mesh after the remeshing operation and again write down a list of all elements in the now modified mesh.
3. If the remeshing operation adds new elements in the modified mesh, create these new elements. An edge flip does not add new elements, but an edge split in Part 5 does.
4. For every element in the modified mesh, set all of its pointers to the correct element in the modified mesh, even if the element being pointed to has not changed:
   • For each vertex, edge, and face, set its halfedge pointer.
   • For each half-edge, set its next, twin, vertex, edge, and face pointer to the correct element. You can use Halfedge::setNeighbors(...) to set all pointers of a half-edge at once.
   • We recommend setting all pointers of all elements in the modified mesh, not just the ones that have changed, because it is very easy to miss a pointer and get errors that are very difficult to debug. Once you are sure that your implementation works, you can remove the unnecessary pointer assignments if you wish.

Your implementation of HalfedgeMesh::flipEdge(...) should do the following:

• Never flip a boundary edge. The function should simply return immediately if either neighbouring face of the edge is on a boundary loop. Every mesh element has a useful isBoundary() function that returns true if the element is on the boundary.
• Perform only a constant amount of work. The cost of flipping a single edge should not be proportional to the mesh size.
• Do not add or delete any mesh elements. There should be exactly the same number of elements before and after the edge flip. You only need to reassign pointers.

Implementation Notes

Given any mesh element, you can use the provided check_for(...) debugging function to check which other elements in the mesh point to it. For example, you can use this function to confirm if an element is pointed to by the right number of other elements. Please read the Debugging Aid section in this primer on the HalfedgeMesh class for more information.

Sanity Check

After loading a model from a .dae file, you can click to select an edge and press F to flip it. Refer back here for a list of controls for Section I Part 2 and onwards. Sometimes, your implementation may seem to work when you flip an edge only once. We recommend that you flip an edge a few more times to be more certain that your code really works as expected. Part 6 will require you to have a working implementation of edge flips. There should be no holes in your mesh created by an edge flip. Note that you may reach a degenerate case where one triangle looks much darker than the others, this is ok.

Functions to Modify: Part 4

• HalfedgeMesh::flipEdge(...)

For Your Write-Up: Part 4

For Homework 2, you can use your native screenshotting systems (there is no hotkey for screenshotting).

• Briefly explain how you implemented the edge flip operation and describe any interesting implementation / debugging tricks you have used.
• Show screenshots of the teapot before and after some edge flips.
• Write about your eventful debugging journey, if you have experienced one.

Part 5: Edge Split

Relevant lecture: 8

In Part 5, you will implement a different local remeshing operation on an edge, called a split. Given a pair of triangles $(a,b,c)$ and $(c,b,d)$, a split operation on their shared edge $(b,c)$ inserts a new vertex $m$ at its midpoint and connects the new vertex to each opposing vertex $a$ and $d$, yielding four triangles as shown below:

You need to implement this part in HalfedgeMesh::splitEdge(...) in student_code.cpp. This function takes as input an EdgeIter to an edge that needs to be split, e.g., edge $(b,c)$ above, and outputs a VertexIter to the newly inserted vertex, e.g., vertex $m$ above.

Because an edge split adds new mesh elements, e.g., a new vertex, two new triangles, three new edges, and etc, you will have more pointers to keep track of and may find that an edge split is a little trickier to implement than an edge flip. We encourage you to again follow our recommendation in Part 4 to ensure that all pointers of all mesh elements point to the right elements in the modified mesh.

Your implementation of HalfedgeMesh::splitEdge(...) should do the following:

• Ignore requests to split boundary edges, unless you are trying for extra credit. The function can simply return immediately if either neighbouring face of the edge is on a boundary loop. Note that splitting a boundary edge does make sense, but flipping a boundary edge does not make sense. (Can you reason why this is the case?)
• Assign the position of the new vertex to the midpoint of the original edge. Remember from Part 3 that the Vertex class has a member variable Vector3D position.
• Perform only a constant amount of work. The cost of splitting a single edge should not be proportional to the mesh size.
• Create only as many new elements as needed. The mesh should not have any elements that is not connected to the rest of the mesh.

Extra Credit (2 pts): Support edge splits for boundary edges. For this, you will need to carefully read the paragraphs on virtual boundary face right before the Iterating Over Mesh Entities section in this primer on the HalfedgeMesh class. In short, you will split the edge in half, but only split in half the face that is non-boundary.

Sanity Check

After loading a model from a .dae file, you can click to select an edge and press S to split it. Refer back here for a list of controls for Section I Part 2 and onwards. To verify that your implementation is likely correct, you can flip some edges that you have split and then split some edges that you have flipped. You can also alternate between flipping and splitting edges many times in mesh regions that are nearby and far apart; and check if the mesh changes correctly. Part 6 will require you to have a working implementation of edge splits.

Functions to Modify: Part 5

• HalfedgeMesh::splitEdge(...)

For Your Write-Up: Part 5

For Homework 2, you can use your native screenshotting systems (there is no hotkey for screenshotting).

• Briefly explain how you implemented the edge split operation and describe any interesting implementation / debugging tricks you have used.
• Show screenshots of a mesh before and after some edge splits.
• Show screenshots of a mesh before and after a combination of both edge splits and edge flips.
• Write about your eventful debugging journey, if you have experienced one.
• If you have implemented support for boundary edges, show screenshots of your implementation properly handling split operations on boundary edges.

Part 6: Loop Subdivision for Mesh Upsampling

Relevant lecture: 8

Sometimes, we may wish to convert a coarse polygon mesh into a higher-resolution one for better display, more accurate simulation, and etc. Such conversion requires an upsampling algorithm that nicely interpolates or approximates the original mesh data.

Unfortunately, the techniques we have learned to upsample 2D images, such as bilinear filtering in Lecture 5, do not easily translate to upsampling 3D meshes. Among many reasons, a mesh often has vertices at irregular locations, as opposed to on a regular grid like an image. (Can you think of other reasons?)

In Part 6, you will implement a mesh upsampling method, called loop subdivision. In short, loop subdivision upsamples a mesh by (1) subdividing each of its triangles into four smaller triangles and (2) updating vertices of subdivided mesh based on some weighting scheme.

You need to implement these two steps of loop subdivision, outlined in more details below, in MeshResampler::upsample(...) in student_code.cpp. This function has no outputs and takes as input a reference to a HalfedgeMesh that will be subdivided.

A single loop subdivision consists of the following two steps. If we repeatedly apply these two steps, we will converge to a smooth approximation of our original mesh.

1. Subdivide each triangle in the mesh into four by connecting edge midpoints, as shown below. This is called a 4-1 subdivision. To perform 4-1 subdivisions over the entire mesh, you can use the edge flip and edge split operation you have implemented. Specifically, you can do the following: (1) Split every existing edge of the mesh in any order. (2) Flip any new edge that connects an old vertex and a new vertex.

   Important Note: After (1), every original edge will now be represented by 2 edges. You should not flip these edges because they are already along the boundary of the 4-way subdivided triangles. In the figure above, you should only flip blue edges that connect an old vertex and new vertex. You should not flip any black new edges.

2. Update vertex positions as weighted average of neighboring vertex positions. Each new vertex position can be calculated from the original vertex positions as seen in the figure below.

   The figure below shows the weights we use to (1) compute the position of a newly added vertex or to (2) update the position of an existing vertex. The new vertex and old vertex are depicted as the white circle in their respective mesh.

   

   (1) The position of a new vertex splitting the shared edge $(A, B)$ between a pair of triangle $(A, C, B)$ and $(A, B, D)$ is

   3/8 * (A + B) + 1/8 * (C + D)
   

   (2) The updated position of an old vertex is

   (1 - n * u) * original_position + u * original_neighbor_position_sum
   

   where n is the vertex degree, i.e., number of edges incident to the vertex, u is the constant shown in the figure, original_position is the original position of the old vertex, and original_neighbor_position_sum is the sum of all original positions of the neighboring vertices. Look here for an example of degree-6 vertex.

Implementation Notes

While you can implement loop subdivision exactly as described, we actually recommend that you update vertex positions before performing 4-1 subdivisions over the entire mesh. More specifically, you may want to follow the steps below:

• Step A: Compute the positions of both new and old vertices using the original mesh. We want to perform these computations before subdivision because traversing a coarse mesh is much easier than traversing a subdivided mesh with more elements.
• Step B: Subdivide the original mesh via edge splits and flips as described.
• Step C: Update all vertex positions in the subdivided mesh using the values already computed.

If you choose to follow our recommendation, you may consider using the following member variables of the Vertex and Edge class to facilitate your implementation:

• Vector3D Vertex::newPosition temporarily stores the updated position of a new or old vertex, computed using the weighted average described above.
• Vector3D Edge::newPosition temporarily stores the position of the vertex that will ultimately be inserted at the edge midpoint.
• bool Vertex::isNew flags whether a vertex exists in the original mesh or is a new vertex inserted at an edge midpoint by subdivision.
• bool Edge::isNew flags whether an edge exists in the original mesh or is a new edge added by subdivision.

Important Note: While computing the updated vertex positions in Step A, you should not change the value of Vector3D Vertex::position because the weighted average is based on vertex positions in the original mesh. (Please take a moment to understand why.) You will, however, need to update Vertex::position in Step C.

Examples below illustrate the correct behavior of the loop subdivision algorithm:

Extra Credit (2 pts): Support meshes with boundary. You will first need to make sure that your edge split function appropriately handles boundary edges. You do not need to change your edge flip function. You will also need a different weighted average for boundary vertices. See “A Survey of Subdivision-Based Tools for Surface Modeling” for more information.

Extra Credit (3 pts): Implement additional subdivision schemes. There exist many alternatives to loop subdivision. Triangle subdivision schemes include the modified Butterfly scheme and $\sqrt{3}$-Subdivision. One of the most popular subdivision schemes for quadrilateral meshes is Catmull-Clark. There are also special subdivision schemes, such as polar subdivision for handling meshes with vertices of high degree.

Functions to Modify: Part 6

• MeshResampler::upsample(...)

For Your Write-Up: Part 6

For Homework 2, you can use your native screenshotting systems (there is no hotkey for screenshotting).

• Briefly explain how you implemented the loop subdivision and describe any interesting implementation / debugging tricks you have used.
• Take some notes, as well as some screenshots, of your observations on how meshes behave after loop subdivision. What happens to sharp corners and edges? Can you reduce this effect by pre-splitting some edges?
• Load dae/cube.dae. Perform several iterations of loop subdivision on the cube. Notice that the cube becomes slightly asymmetric after repeated subdivisions. Can you pre-process the cube with edge flips and splits so that the cube subdivides symmetrically? Document these effects and explain why they occur. Also explain how your pre-processing helps alleviate the effects.
• If you have implemented any extra credit extensions, explain what you did and document how they work with screenshots.