• Overview
• Mesh Traversal
  • REQUIRED: face.getEdges() (6 Points)
  • REQUIRED: vertex.getVertexNeighbors (7 Points)
  • REQUIRED: vertex.getAttachedFaces (7 Points)
• Geometric Tasks
  • REQUIRED: face.getArea() (5 Points)
  • REQUIRED: vertex.getNormal() (10 Points)
  • Inflate/Deflate (10 Points)
  • Laplacian Smooth/Sharpen (10 Points)
• Topological Tasks
  • Find Boundary Cycles (10 Points)
  • Genus of A Watertight Mesh (5 Points)
• Mesh Creation Tasks
  • Surface of Revolution (10 Points)
  • Topological Subdivision (15 Points)
  • Linear Subdivision (5 Points)
  • Loop Subdivision (5 Points)
  • Truncate (20 Points)
• Remeshing Tasks
  • Edge Collapse (10 Points)
  • Edge Flip (10 Points)
  • Random Mesh Simplification (5 Points)
  • Quadric Mesh Simplification (15 Points)
• Art Contest (5 Points)

Overview

The most ubiquitous representation of 2D surfaces in 3D space is the polygon mesh. In this assignment, you will explore the half-edge 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 70 points, split into two parts. The first half is on 5 required tasks. In the second "choose your own adventure" part, you can choose whatever other tasks you want to do, as long as you reach 35 points among them. Assuming you've hit 35, any extra credit points you earn will be applied at a discounted rate of 1 point, 1/2 points, 1/4 points, 1/8 points, etc.

Deadlines

The first deadline will encompass all of the required tasks (face.getEdges(), vertex.getVertexNeighbors(), vertex.getAttachedFaces(), face.getArea(), vertex.getNormal())

The second deadline will be for the tasks you've chosen.

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

1. 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/ursinusgraphics/HW4_PolygonMeshProcessing.git

   NOTE: You will only need to edit halfedgemesh.js to complete all of the tasks in the assignment.

2. 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:

HEdge HVertex head: A pointer to the vertex at the head of this half-edge HFace face: A pointer to the face to the left of this half-edge HEdge pair: A pointer to the opposite half-edge HEdge prev: A pointer to the previous half-edge in CCW order HEdge next: A pointer to the next half-edge in CCW order

HVertex vec3 pos: The position of the vertex (the only geometric property in the whole data structure) vec3 color: The color of the vertex (you can safely ignore this) HEdge h: A pointer to any half-edge that has this vertex as its tail.

HFace HEdge h: A pointer to any half-edge that has this face as its left face.

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 your halfedge.js code to Canvas when you are finished, along with screenshots and .off files for the art contest, if you choose to submit something.

---

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 per-vertex 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 half-edges that have it as its face, in CCW order

Code To Write

You should fill in the getEdges() function of the HFace class.

Debugging GUI

If you visit the Face 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 the getVertexNeighbors() function of the HVertex class.

Debugging GUI

If you visit the Vertex 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 the getAttachedFaces() function of the HVertex class.

Debugging GUI

If you visit the Vertex 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 the face.getArea() function of the HFace class.

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. Be sure to normalize this vector before you return it. Otherwise, you may have problems on later tasks

Code To Write

You should fill in the getNormal() 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.

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 Blinn-Phong 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 pre-specified amount along its normal.

Code To Write

You should fill in the inflateDeflate() function of the HEdgeMesh class.

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 the laplacianSmoothSharpen() function of the HEdgeMesh class.

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 the getBoundaryCycles() function of the HEdgeMesh class.

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:

icosahedroncut.off	proftralie.off

bunny.off	dinopet.off

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 the getGenus() function of the HEdgeMesh class.

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

box2402.off	octopus.off
sphere1024.off	homer.off

Examples of Meshes of Genus 1

torus32x32.off	teapot.off

Examples of Meshes of Higher Genus

genustwo.off	genusthree.off

---

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 y-axis. 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 the makeSurfaceOfRevolution(points, NAngles) function of the HEdgeMesh class. points is an array of 2-element arrays for each point on the piecewise linear curve. The first element of each contains the x-coordinate, and the second element contains the y-coordinate. When you rotate them around the y-axis, the original x-coordinate 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 the subdivideTopological() 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 the subdivideLinear() 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 the subdivideLoop() 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, particularly around the fingertips

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 per-face rather than per-normal, and that led to a more interesting artistic effect

Code To Write

You should fill in the truncate(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.

---

Remeshing Tasks

Edge Collapse (10 Points)

Coming soon...

Edge Flip (10 Points)

Coming soon...

Random Mesh Simplification (5 Points)

Coming soon...

Quadric Mesh Simplification (15 Points)

Coming soon...

---

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!