In this lab, you will implement the Loop subdivision scheme. All of the code you will write will be in the loopSubdivision function in the subdivision.js file. The implementation will be very similar to what we implemented in the exercise on Tuesday (subdividing an icosahedron to approximate a sphere). There are a few differences, however, since the Loop subdivision scheme (1) uses a different scheme to calculate the coordinates of vertices added on edges and (2) moves vertices in the original mesh using information about the surrounding vertices.

Part 1: Subdivide the mesh as in the exercise from Tuesday.

Please start by copying over what you had from the exercise on Tuesday for subdividing a sphere mesh. Place new edge vertices at the midpoints of the edge - do not normalize the coordinates like we did at the end of class since we don't want to place the edge vertices on the unit sphere in the Loop subdivision scheme.

Part 2: Compute coordinates of new vertices on edges (M status).

Now we will calculate the coordinates of the newly created edge vertices using the Loop subdivision scheme. Please refer to the left-most figure at the top of this lab description. The coordinates of the blue vertex $\vec{x}_e$ are:

$$ \vec{x}_e = \frac{3}{8}(\vec{x}_p + \vec{x}_q) + \frac{1}{8}(\vec{x}_r + \vec{x}_s). $$

How I suggest implementing this: There are many ways to implement this scheme, some of which involve setting up additional data structures to keep track of triangle-to-triangle, edge-to-triangle or triangle-to-edge adjacencies. We will not do that here since our meshes are always closed. We can actually calculate the coordinates of the blue vertex on the fly as we iterate through the edges of each triangle:

1. Retrieve the "opposite" vertex to the edge in the current triangle (see the notes). Let this opposite vertex be denoted by $o$ and has coordinates $\vec{x}_o$ (note: $o$ will either be $r$ or $s$ in the image above).
2. In the conditional block that treats the case when an edge has not been created (key is not in edgeMap, or !(key in edgeMap)), initialize the coordinates to the contributions from the edge endpoint: $\vec{x}_e = \frac{3}{8}(\vec{x}_p + \vec{x}_q)$.
3. After the if-else blocks, add the contributions from the "opposite" vertex: i.e. add $\frac{1}{8}\vec{x}_o$ (where $o$ is either $r$ or $s$ in the image above). Hint: the vertex to update is at the index edgeMap[key] + nVertices, assuming you added vertices similar to what was done in the exercise earlier in the week. The first time we encounter the edge, this adds the contribution from either $r$ or $s$; the next time, we will add the contribution from the other opposite vertex.

Before adding the contribution from the opposite vertex, you should see a pretty spiky-looking mesh at various levels of subdivision:

And after adding the contributions from the opposite vertices, it should look a bit less spiky:

Part 3: Compute the new location of existing vertices (E status).

Finally, this last stage involves updating the existing vertex coordinates to $\vec{p}_i^* = (1 - k\beta) \vec{p}_i + \sum_j\beta \vec{p}_j$. The star superscript denotes the updated location of vertex $i$. Be careful to always use the old vertex coordinates when calculating $\vec{p}_i^\ast$. It's a good idea to make a copy of the old vertices (const oldVertices = vertices.slice()) and use oldVertices when calculating $\vec{p}_i^*$.

Recall that this step requires the vertex-to-vertex (v2v) information. Please see the notes for a description of how to calculate this v2v data structure. When this works, you should see the following for the initial icosahedron mesh:

and the following for the Stanford Bunny mesh which I found here (the right-most picture has the edge visibility turned off):

Part 4: Memory used by a mesh after subdivision (also for E status, graded for effort).

For this part, we will work with the Stanford Bunny mesh ("bunny" option in the dropdown in your lab) which initially has 500 triangles ($n_t$) and 252 vertices ($n_v$). The number of edges $n_e$ is initially 750 for this mesh. Assuming that we only need to store the vertices (float), edges (integers), and triangles (integers), we will calculate the memory used by the mesh at various levels of subdivision.

Question 1: Assume that vertex coordinates (float) are always stored with a Float32, i.e. 4 bytes of memory. You may also assume that the indices for triangles and edges are unsigned 32-bit integers UInt32 (also 4 bytes). Please complete the table in the questions.md file by reporting the number of vertices, edges and triangles and the total memory consumed by the Stanford Bunny mesh at each level of subdivision (for 5 subdivisions). Note that $n_e$ is always equal to $n_e = \frac{3}{2}n_t$ for the meshes in this lab. Report the memory in MB (one million bytes), using 2-3 significant digits to represent the result.

Question 2: Using the data you found in Question 1, notice that $n_v \approx \frac{1}{2}n_t$. Assuming $n_v = \frac{1}{2}n_t$, is a 32-bit integer enough to represent indices after $s = 8$ subdivisions? What about $s = 16$? Please see this Wikipedia article about the maximum number that can be represented with integers. Hint: recall that the number of triangles quadruples at each subdivision, so $n_t = 4^s n_{t,0}$, where $n_{t,0}$ is the initial number of triangles ($n_{t,0} = 500$ for the Stanford Bunny).

Submission

The initial submission for the lab is due on Wednesday 10/25 at 11:59pm EDT. I will then provide feedback within 1 week so you can edit your submission.

When you and your partner are ready, please submit the assignment on replit. I will then make comments (directly on your repl) and enter your current grade status at the top of the index.html file.

Please also remember to submit your reflection for this week in this Google Form.

© Philip Claude Caplan, 2023 (Last updated: 2023-10-19)