Homework Structure

This assignment has 7 parts, divided into 3 sections, and is worth a total of 90 possible points. Some parts require only a few lines of code, while others are more substantial.

Section I: Bezier Curves and Surfaces

Part	Name	Points
1	Bezier curves with 1D de Casteljau subdivision	13
2	Bezier surfaces with separable 1D de Casteljau	15

Section II: Triangle Meshes and Half-Edge Data Structure

Part	Name	Points
3	Area-weighted vertex normals	12
4	Edge flip	12
5	Edge split	20
6	Loop subdivision for mesh upsampling	25

Section III: Potential Extra Credit - Art Competition: Model something Creative

You will also need to reference our Deliverables, specifically to review our write-up rubric.

Getting Started

As in Homework 1, you should accept this assignment from GitHub Classroom, and clone the generated repo (not the class skeleton). Make sure you enable GitHub Pages for your assignment.

$ git clone <YOUR_PRIVATE_REPO>

Please consult the article that discusses how to build assignments for more information on how to setup and build the assignment.

We recommend that you accumulate deliverables into your write-up as you work through each part this assignment. We have included write-up instructions at the end of each part of this assignment, as well as a compilation of all write-up instructions at the end.

Also, we have created a website template for Homework 2 docs/index.html which contain all write-up questions and some template HTML codes (e.g. including figures). Please feel free to use it for your submission.

Running the Executable

The general command for running the executable meshedit is the following:

./meshedit <PATH_TO_FILE>

Note that meshedit expects different file formats for different parts of this assignment, as detailed in the table below:

Part / Section	Expected File Format
Section I Part 1	Bezier Curves (.bzc)
Section I Part 2	Bezier Surfaces (.bez)
All Parts in Section II and III	COLLADA Mesh Files (.dae)

As an example, for Section I Part 1, you must load a Bezier curve as the following:

./meshedit ../bzc/curve1.bzc

Using the Graphical User Interface (GUI)

The following details how to use the GUI provided by the executable meshedit. You may want to skim through them on your first read-through; and read them in more details when you have implemented parts of this assignment and are ready to use the GUI.

Section I Part 1

When you run meshedit with a Bezier curve (.bzc) for Section I Part I, you will see control points rendered on screen, as shown below.

Control points rendered on a screen for a Bezier curve.

For this part only, the GUI is different. Below is the full specification on keyboard controls.

Key	Action
`E`	Perform one call to `BezierCurve::evaluateStep(...)` and cycle through levels
`C`	Toggle whether or not the fully evaluated Bezier curve is drawn to the screen

To verify your implementation is correct, you can repeatedly press E to cycle through each level of the de Casteljau subdivision. You can press C to toggle the Bezier curve to check if it is generated correctly based on the control points.

You can also use your mouse to:

Click and drag the control points to move them and see how your Bezier curve, along with all intermediate control points, changes accordingly.
Scroll to move the evaluated point along the Bezier curve and see how the intermediate control points move along with it. This is essentially varying $t$ between 0.0 and 1.0.

Section I Part 2 and Onwards

When you run meshedit from Section I Part 2 and onwards, you will see a triangle mesh rendered on screen, as shown below.

Triangle mesh on a teapot.

As you hover the cursor around the screen, you will notice that mesh elements (half-edges, vertices, edges,, and faces) under the cursor are highlighted in purple or white, such as an edge in the image above. You can click on one of these elements to select it and the GUI will display some information about the element and its associated data.

Below is the full specification on keyboard controls.

Key	Action
`Q`	Toggle using vertex normals (Part 3)
`F`	Flip the selected edge (Part 4)
`S`	Split the selected edge (Part 5)
`L`	Upsample the current mesh (Part 6)
`N`	Select the next half-edge
`T`	Select the twin half-edge
`W`	Toggle wireframe
`I`	Toggle information overlay
`SPACE`	Reset camera to default position
`0` - `9`	Switch between GLSL shaders
`R`	Recompile shaders

You can also use your mouse to:

Click and drag a vertex to change its position.
Click and drag background or right click and drag anywhere to rotate the camera.
Scroll to adjust the camera zoom.

You will implement area-weighted vertex normals (Q), local edge flip (F), local edge split (S), and loop subdivision (L) in Part 3, Part 4, Part 5, and Part 6, respectively. Therefore, these four key commands will do nothing until you have completed their respective part.

Starter Code Structure

Before you start, here is some basic information on starter code structure.

For Bezier curves and surfaces (Section I), you will be filling in member functions of the BezierCurve and BezierPatch classes, defined in bezierCurve.h and bezierPatch.h.

For triangle meshes (Section II), you will be filling in member functions of the Vertex, HalfedgeMesh, and MeshResampler class, defined in halfEdgeMesh.h.

We have put dummy definitions for all the functions you will need to modify within student_code.cpp. You will implement all parts of this assignment in this file!

Additional Debugging Utilities

To make sure edge splitting and flipping produce consistent meshes, feel free to refer to the following debug assertions.

#define ASSERT(a) if (!a) {printf("%s:%i:Assertion failed: %s \n Terminating program due to failed assertion. \n", __FILE__, __LINE__,#a ); exit(1);}
namespace Debug
{
	static bool is_closed(std::vector<HalfedgeIter>& a_halfedges) {
		ASSERT(a_halfedges.size() > 1);
		for (int i = 0; i < a_halfedges.size() - 1; i++) {
			auto it = a_halfedges[i];
			if (it->next() != a_halfedges[i + 1]) {
				return false;
			}
		}
		if (a_halfedges[a_halfedges.size() - 1]->next() != a_halfedges[0]) {
			return false;
		}
		return true;
	}
// make sure that all the half edges form a closed surface
#define CHECK_CLOSED(...) ASSERT(Debug::is_closed(std::vector<HalfedgeIter>{__VA_ARGS__}))
	static bool is_face_of(FaceIter a_face, std::vector<HalfedgeIter>& a_halfedges) {
		for (auto i : a_halfedges) { // check ptr from edge to face
			if (i->face() != a_face) {
				return false;
			}
		}
		auto it = a_face->halfedge(); // check ptr from face to edges
		do {
			if (std::find(a_halfedges.begin(), a_halfedges.end(), it) == a_halfedges.end()) {
				return false;
			}
			it = it->next();
		} while (it != a_face->halfedge());
		return true;
	}
// make sure that the face consist of the half edges
#define CHECK_FACE(face, ...) ASSERT(Debug::is_face_of(face, std::vector<HalfedgeIter>{__VA_ARGS__}))
	static bool is_vertex_of(VertexIter a_vertex, std::vector<HalfedgeIter> a_halfedges) {
		ASSERT(a_halfedges.size() > 0)
		for (auto i : a_halfedges) { // check ptr from edge to vertex
			if (i->vertex() != a_vertex) {
				return false;
			}
		}
		auto it = a_vertex->halfedge();
		do {
			auto f = std::find(a_halfedges.begin(), a_halfedges.end(), it);
			if (f != a_halfedges.end()) {
				a_halfedges.erase(f); // remove found edge
			}
			it = it->twin()->next();
		} while (it != a_vertex->halfedge());
		return a_halfedges.size() == 0;
	}
// make sure that the vertex is connected to the half edges
#define CHECK_VERTEX(vertex, ...) ASSERT(Debug::is_vertex_of(vertex, std::vector<HalfedgeIter>{__VA_ARGS__}))
}

An example of using the debug assertions:

VertexIter HalfedgeMesh::splitEdge(EdgeIter e0)
{
	HalfedgeIter h0, h1, h2, h3, h4, h5, h6, h7, h8, h9;
	VertexIter v0, v1, v2, v3;
	EdgeIter e1, e2, e3, e4;
	FaceIter f0, f1;
	...
	...
	// sanity check
	// check that half edges are closed
	CHECK_CLOSED(h3, hb, h5)
	CHECK_CLOSED(h4, hy, ha)
	// check that faces are made of the given half edges
	CHECK_FACE(f1, h3, hb, h5)
	CHECK_FACE(f0, hz, h0, h1)
	// check that vertices are connected to the given half edges
	CHECK_VERTEX(v0, h7, hx, h4)
	CHECK_VERTEX(vx, h0, hb, ha, hc)
}

Write-Up

We recommend working on your write-up for the assignment as you go. Reference our website tips and advice section for information on best practices.

For each part, we’ll include the relevant write-up desired, which is pulled directly from our Homework 2 Deliverables page. When performing your final checks, please compare against the Deliverables page for the full rubric.

As a reminder, you are primarily graded on your write-up submission. Having a public website is a requirement, and can serve as a portfolio for you to show off your amazing graphics work in future years, but will not be utilized while grading, so please make sure to check that your PDF catches all images and updates that you’ve made to your website.