Assignment 4: Polygon Mesh Processing (85 Points)
Due Date #1: Thursday 10/27/2022 at 11:59 PM
Due Date #2: Sunday 11/6/2022 at 11:59 PM
Click here to see the art contest results!
 Overview
 Mesh Traversal (20 Points)
 REQUIRED: face.getEdges() (6 Points)
 REQUIRED: vertex.getVertexNeighbors (7 Points)
 REQUIRED: vertex.getAttachedFaces (7 Points)
 Geometric Tasks (15 Points Required)
 Topological Tasks (5 Points Required)
 Mesh Creation Tasks (15 Points Required)
 Art Contest (5 Points)
 REQUIRED: face.getEdges() (6 Points)
 REQUIRED: vertex.getVertexNeighbors (7 Points)
 REQUIRED: vertex.getAttachedFaces (7 Points)
Overview
The most ubiquitous representation of 2D surfaces in 3D space is the polygon mesh. In this assignment, you will explore the halfedge data structure, which is the gold standard for traversing oriented manifold meshes. You will begin with some basic traversal tasks, which will then unlock some more advanced topological and geometric operations.
Scoring
This assignment is out of 85 points, but you can "choose your own adventure"; there are only 5 tasks that you are required to do, and then you can choose what other tasks to do, as long as you reach the minimum points in each category, and as long as you reach at least 85 points total. Assuming you've hit the minimum in each category, any extra points you get beyond the required 85 will be added as extra credit at a rate of 1 point, 4/5 points, 4/5^2 points, 4/5^3 points, etc.
As an example, let's suppose you did the required tasks (35 points), then inflate/deflate (10 points), then boundary cycles (5 Points), then topological subdivision (15 Points), then truncate (20 points), then the art contest (5 points). Each of these hits the minimum in each category, so no points lost there. But we have a total of 5 extra points. So the final score would be 85+1+4/5+(4/5)^{2}+(4/5)^{3}+(4/5)^{4}, or 88.3616
As another example, let's suppose you did all of the required tasks (35 points), then everything in the geometric tasks (35 points total), then surface of revolution (10 points) and truncate (20 points). This adds up to 100 points, but there is a 5 point deduction for not doing any of the topological tasks. So we start at 80/85, then we add the 20 points left over as extra credit at 1 + (4/5) + (4/5)^{2} + ... + (4/5)^{19} ≈ 4.94. So the total score would be 84.94
Deadlines
The first deadline will encompass all of the required tasks (face.getEdges(), vertex.getVertexNeighbors(), vertex.getAttachedFaces(), face.getArea(), vertex.getNormal())
Collaboration
You are allowed to work very closely with other students in the class in a "buddy" capacity, and even to look at each others' code as you're debugging. But I expect each student to submit their own code. Please indicate to me on your README who your buddies were.
Getting Started

Click here to download the repository of skeleton code for this assignment. If you have git installed on your computer, you can simply type
git clone recursive https://github.com/ursinuscs476f2022/HW4_PolygonMeshProcessing.git
NOTE: You will only need to edit
halfedgemesh.js
to complete all of the tasks in the assignment.  If you want to use any additional meshes, make sure they are .off files. If not, use meshlab to convert them.
Half Edge Objects
The three object subtypes for a half edge mesh are HEdge
(for a half edge), HFace
(for a face), and HVertex
(for a vertex). Their fields are as follows:

HVertex

HFace

Debugging GUI
The main file where you view the results of your ray tracer is MeshProcessing.html
. There are various menus here that you can use to test the different features that you implement.
Submission Instructions
You will submit yourhalfedge.js
code to Canvas when you are finished, along with screenshots and .off files for the art contest, if you choose to submit something. Please also submit a README.txt
file with both submissions with the following information:
 Your name
 The "buddies" you worked with (see collaboration above)
 A list of tasks that you implemented, and how many points you believe you earned.
 A description of your art contest submission if you have one, as well as:
 One of the two statements below
 "I consent to have my art contest submission posted publicly on the class web site. My name/pseudonym for public display is .
 "I do not wish to post my art contest submission publicly"
 One of the two statements below
 Approximately how many hours it took you to finish this assignment (I will not judge you for this at all...I am simply using it to gauge if the assignments are too easy or hard)
 Your overall impression of the assignment. Did you love it, hate it, or were you neutral? One word answers are fine, but if you have any suggestions for the future let me know.
 Any other concerns that you have.
Mesh Traversal
NOTE: You will have to finish these tasks before moving onto the geometric and topological tasks.
NOTE ALSO: The lighting will not look very good in this until you get the pervertex normals working, which requires some of the traversal functions in this section. To see the mesh better before then, you should click drawEdges
in Mesh Display Options
.
face.getEdges() (6 Points)
Given an HFace
class, return a list of the halfedges that have it as its face, in CCW order
Code To Write
You should fill in thegetEdges()
function of the HFace
class.
Tips
 A do while loop is a good choice for this task.
 With this and with all of the other tasks, you can assume that the halfedge mesh has been initialized properly, and that the
next
pointer points to any halfedge in CCW order.
Debugging GUI
If you visit theFace Tests
menu in MeshProcessing.html, you can test this function on a particular face when you click "showResult." This will display a magenta list of edges that were returned superimposed on the mesh, as shown below on box2402.off
:vertex.getVertexNeighbors() (7 Points)
Given an HVertex
class, return a list of vertices that are attached to it
Code To Write
You should fill in thegetVertexNeighbors()
function of the HVertex
class.
Tips
 A do while loop is a good choice for this task.
 As discussed in class, you will have to jump across a lot of pairs to make this work.
Debugging GUI
If you visit theVertex Tests
menu in MeshProcessing.html, you can test this function on a particular vertex when you click "showResult." This will display a cyan list of vertices (and the edges that attach them) returned from your function, superimposed on the mesh, as shown below (icosahedroncut.off
is a good small mesh to test this on which covers a lot of cases):vertex.getAttachedFaces() (7 Points)
Given an HVertex
class, return a list of faces that have this as a vertex
Code To Write
You should fill in thegetAttachedFaces()
function of the HVertex
class.
Tips
 This is incredibly similar to the last task, except when you're creating a list of faces, be sure to only add a face if it is not null (!(h.face === null)). Otherwise, you will run into some problems later with meshes that have boundaries.
Debugging GUI
If you visit theVertex Tests
menu in MeshProcessing.html, you can select this function from a dropdown menu and test it on a particular vertex when you click "showResult." This will display a cyan list of vertices (and the edges that attach them) returned from your function, superimposed on the mesh, as shown below:Geometric Tasks
NOTE: While you may need to perform topological traversals to help you with this task, the only variable that you will ever update is the position of a vertex, which is the only geometric property in the mesh.
face.getArea() (5 Points)
Given an HFace
class, return its area
Code To Write
You should fill in theface.getArea()
function of the HFace
class.
Tips
 Every face with N edges can be divided into N2 triangles.
 You can (and should) reuse your triangle area code from assignment 1
vertex.getNormal() (10 Points)
Given an HVertex
class, return a normal associated to it, which is the weighted average of the face normals attached to this vertex, weighted by the respective face areas.
Code To Write
You should fill in thegetNormal()
function of the HVertex
class. You should also fill in the getNormal()
function of HFace
as a helper function. For the face normals, you can assume that they are flat, so that you only need to compute the normal of a single triangle in the face if it has more than three edges.
Tips
 You should make use of your
vertex.getAttachedFaces()
function  Make sure your face (and subsequently vertex) normals are actually normalized. For the large meshes with many small triangles, if you just use the cross product, it will have a very small magnitude, and this will affect later tasks (particularly inflate/deflate).
Debugging GUI
You can display the normals you calculate by clicking drawNormals
in the Mesh Display Options
menu. Below shows a before and after on cow.off
(by default, the normals start off all pointing to the right)
Before 
After 
Furthermore, the BlinnPhong shading will look much better with the correct normals once you have them. Below is an example on homer.off
Before 
After 
Inflate/Deflate (10 Points)
Move each vertex of the mesh by some prespecified amount along its normal.
Code To Write
You should fill in theinflateDeflate()
function of the HEdgeMesh
class.
Tips
 You will have to loop through all of the vertices in the mesh, which are stored in a list
vertices
which is a property ofHEdgeMesh
(NOTE: The vertices are not stored in any particular order).  You should only update the
pos
field of eachHVertex
; the topology should remain fixed.  The
scaleAndAdd()
function ofvec3
will come in handy here. Click here to see the documentation.  Note that the normals change after you apply these operations, so they are not directly invertible. This means you should not expect to get the same result when you deflate after inflating, for instance.
Debugging GUI
You can display the result of this operation by clicking inflateDeflate
in the Geometric Tasks
menu. You can set the factor by which to inflate with the inflateFac
slider. A positive number inflates, and a negative number deflates. Depending on the dimensions of your mesh, you may have to adjust the dynamic range of this a lot (e.g. a mesh whose bounding box is [0, 1000] x [0, 1000] x [0, 1000] is much less affected by moving along the normal by a factor of 0.1 than a mesh whose bounding box is [0, 1] x [0, 1] x [0, 1])
Below is an example of running the function on bunny.off
with a factor of 0.005
Before 
After 
Below is an example of running the function on homer.off
with a factor of 0.005, which is actually a deflation. Notice how his fingers and mouth get thinner
Before 
After 
Laplacian Smooth/Sharpen (10 Points)
The "Laplacian," or the mean difference between a vertex and its neighbors, is a measure of curvature. If we change the vertices so that the Laplacian is smaller, then we are locally flattening the mesh, and if we do this everywhere, the mesh will be smoothed out. This is the "Laplacian smoothing" task. Conversely, if we make the Laplacian larger, we are sharpening the mesh.
To do the smoothing in code, move each vertex of the mesh along a vector which is the average of the vectors from the vertex to its neighbors. This is depicted by the green vector in the image below, which is the mean of the black vectors pointing from the vertex (red dot) to its neighbors (grey dots). When adding this vector to the vertex, it is smoothed, as it will move protrusions down towards a plane fit through its neighbors (the tip of the green arrow). When subtracting this vector, it moves away from this plane, and the mesh is sharpened.
Code To Write
You should fill in thelaplacianSmoothSharpen()
function of the HEdgeMesh
class.
Tips
 The
scaleAndAdd()
function ofvec3
will come in handy here as well.  To really do this correctly, you should create a new list of vertex positions and then copy them over at the end, so that neighboring vertex positions don't change as you're iterating.
Debugging GUI
You can display the result of this operation by clicking laplacianSmooth
and laplacianSharpen
in the Geometric Tasks
menu.
Below is an example of running 5 iterations of smooth on proftralie.off
Before 
After 5 Iterations of Smooth 
Below is an example of running a single iteration of sharpen on cow.off
Before 
After 1 Iteration of Sharpen 
Topological Tasks
Find Boundary Cycles (10 Points)
Return a list of boundary cycles on the mesh, where each boundary cycle is its own list of HEdge
objects, each with a null face.
Code To Write
You should fill in thegetBoundaryCycles()
function of the HEdgeMesh
class.
Tips
 You will need to loop through all of the edges in the mesh to find ones that have a face as null (
e.face === null
). You can access the list of edges as theedges
field ofHEdgeMesh
.  To make sure you don't accidentally repeat boundary cycles, you should add a variable to an edge which stores whether this edge has been checked yet, and initialize all of these variables to be "false." Note that you can add fields to objects dynamically in Javascript.
Debugging GUI
You can display the boundary cycles computed by your code by clicking the showBoundaries
checkbox in the Topological Tasks
menu
Below are a number of examples of boundaries for different meshes:




Genus of A Watertight Mesh (5 Points)
Return the genus of a watertight mesh, or 1 if the mesh is not watertight.
Code To Write
You should fill in thegetGenus()
function of the HEdgeMesh
class.
Tips
 Remember that there are actually two half edges for every actual edge in the mesh, so be sure not to double count them!

You should use your
getBoundaryCycles()
function to figure out if the mesh is watertight.
Debugging GUI
If you have the showBoundaries
checkbox checked, then the genus
field should update with the genus that you're computing for the mesh. You should check the following shapes below
Examples of Meshes of Genus 0




Examples of Meshes of Genus 1


Examples of Meshes of Higher Genus


Mesh Creation Tasks
In each task below, you will have to create a new HedgeMesh
object and to properly link together all of the vertices, edges, and faces. I have provided a simple example makeTriangle
that shows how to create a triangle from scratch with all of the right links. It makes use of the helper methods makeNextPrev
and linkEdges
, which you can also use to make your code more compact.
Surface of Revolution (10 Points)
Time to make some virtual pottery/glassware! Given a piecewise linear curve (a bunch of line segments attached to each other), create a quad mesh that is the result of rotating that curve around the yaxis. There should be a quad face in between each line segment and its rotated versions directly next to it. The animation below shows how to choose a piecewise linear curve and how to use it to create a surface of revolution in the interface.
Code To Write
You should fill in themakeSurfaceOfRevolution(points, NAngles)
function of the HEdgeMesh
class. points
is an array of 2element arrays for each point on the piecewise linear curve. The first element of each contains the xcoordinate, and the second element contains the ycoordinate. When you rotate them around the yaxis, the original xcoordinate should rotate in the XZ plane.
Topological Subdivision (15 Points)
Given a watertight triangle mesh, put a new vertex at the center of each edge, and use those vertices to subdivide each triangle face into 4 faces (this is similar to how the Sierpinski Triangle is formed). An example is shown below with an icosahedron as the starting mesh.
Hint
You'll be making a new mesh, but you can use the original mesh to store information as you go along. For instance, you can store vertices of the subdivided edges in the new mesh in the edge objects in the original mesh, so you can easily refer back to them.
Code To Write
You should fill in thesubdivideTopological()
method.
Original 
1 Subdivision 
2 Subdivisions 
Linear Subdivision (5 Points)
One you have completed topological subdivision, you can add some geometric refinement on top of that by changing the positions of the vertices. Recall that the centroid of a face is the mean of the vertex positions on the face. In the linear subdivision scheme, you should make the new position of each vertex be the mean of the centroids of each face to which it is attached.
Code To Write
You should fill in thesubdivideLinear()
method. This method should first make a call to subdivideTopological()
, and then it should update the vertex positions in that new mesh. Be sure not to copy over the new vertex positions until you have finished computing them for the entire mesh.
Original 
1 Subdivision 
6 Subdivisions 
Loop Subdivision (5 Points)
Linear subdivision is OK, but, as we discussed in class, it does not guarantee that meshes are C2 continuous, which means that the normals do not vary continuously in the limit surfaces, which in turn means that there may be strange discontinuities in lighting. A better scheme with C2 continuity is loop subdivision, in which different weights are used for different vertices. Click here to view some notes on this.
Code To Write
You should fill in thesubdivideLoop()
method. This method should first make a call to subdivideTopological()
, and then it should update the vertex positions in that new mesh. Be sure not to copy over the new vertex positions until you have finished computing them for the entire mesh.
Original 
1 Subdivision 
6 Subdivisions 
The difference with linear subdivision is sometimes subtle, but notice how this is slightly smoother in some places
Linear 
Loop 
Truncate (20 Points)
Truncate the mesh by slicing off the tips of each vertex by some amount. You can assume that the mesh is watertight, but you should not make any other assumptions about it (it does not have to be a triangle mesh!).
Example: Truncated iscosahedron (aka soccer ball)
Example: Truncated Cube
Example: Truncated Homer
Example: Truncated Hand
I displayed this one in meshlab because the normals are computed perface rather than pernormal, and that led to a more interesting artistic effect
Code To Write
You should fill in thetruncate(fac)
function of the HEdgeMesh
class. The parameter fac
is a number between 0 and 0.5 which determines how long to walk along each edge from the vertex before the cut. When fac is close to 0, then the cuts are made very close to the tips of the vertex. When fac is close to 0.5, then the cut is made close to halfway through the edge.
Art Contest Submission (5 Points)
Do some interesting combination of your techniques above, and save the result as an .off file using the saveOffFile
button in the menu. You should submit your .off files, along with screenshots. Feel free to submit multiple .off files, including interesting bugs!