## Due Date

Mon Feb 29th, 11:59pm

## Overview

In this project you will explore a subset of the geometric topics covered in lecture. You will tesselate Bezier patches, manipulate half-edge meshes, implement Loop subdivision, and write shaders for your own meshes! When you are finished, you will have a tool that allows you to load and edit basic COLLADA mesh files that are now used by many major modeling packages and real time graphics engines. For the last part of the assignment, you'll be creating your own COLLADA file using free software like Blender!

### Project Parts

- Part 1: Fun with Bezier Surfaces (20 points)
- Part 2: Average normals for half-edge meshes (10 points)
- Part 3: Edge flip (10 points)
- Part 4: Edge split (10 points)
- Part 5: Upsampling via Loop Subdivision (20 points)
- Part 6: Fun with Shaders (20 points)
- Part 7: Design your own mesh (10+ points)
**NEW**: Website guidelines and deliverables for each part

As with the first assignment, all your deliverables should be documented in the *website/index.html* webpage. Your art competition submission should be saved in the root directory as *competition.png*.

### Quick links

- How to build and submit
- Half-edge data structure details and implementation
- halfEdgeMesh.h file on GitHub, which includes a huge comment documenting the half-edge data structure
- Modeling tips for designing your own mesh

## Getting set up

You can either download the zipped assignment straight to your computer or clone it from GitHub using the command

```
git clone https://github.com/CS184-sp16/asst2_geomenagerie.git
```

Please consult this article on how to build and submit assignments for CS 184.

A debugging note: Check out this page on how to set up *gdb* to work with recent OS X releases. Please use *gdb* to debug, particularly if you get a seg fault that you can't track! Turn on debug symbols by toggling this line at the top of the *CMakeLists.txt* file in the root directory:

```
option(BUILD_DEBUG "Build with debug settings" ON)
```

You'll have to rerun *cmake* to update the Makefiles after doing this.

## Using the GUI

When you have successfully built your code, you will get an executable named `meshedit`

in the build directory. The `meshedit`

executable takes exactly one argument from the command line. You may load a single COLLADA file by specifying its path. For example, to load the example file *dae/quadball.dae* from your build directory:

`./meshedit ../dae/quadball.dae`

After Part 1, you will be able to load Bezier surfaces by running a command such as:

`./meshedit ../bez/teapot.bez`

When you first run the application, you will see a picture of a mesh made of triangles. The starter code that you must modify is drawing this mesh. The editor already supports some basic functionality, like moving vertices around in space, which you can do by just clicking and dragging on a vertex. You can also rotate the camera by right-clicking and dragging (or dragging on the background), and zoom in and out using the scroll wheel or multi-touch scrolling on a trackpad. Hitting the spacebar will reset the view. As you move the cursor around the screen, you'll notice that mesh elements (faces, edges, and vertices) under the cursor get highlighted. Clicking on one of these elements will display some information about the element and its associated data.

In this assignment, you will add additional functionality to the program that allows you to modify the mesh in a variety of ways. Each of these methods is exposed through the viewer. There will be two basic types of operations:

- Local flip and split operations, which modify the mesh in a small neighborhood around the currently selected mesh element.
- Loop subdivision, which refines and smooths the entire mesh.

Each operation will be executed with a key press (A table of all the keyboard controls in the `meshedit`

application is provided in the appendix).

Command | Key |
---|---|

Flip the currently selected edge | F |

Split the currently selected edge | S |

Subdivide the mesh | U |

Note that each COLLADA file may contain multiple mesh objects; more generally, a COLLADA file describes a **scene graph** (much like SVG) that is a hierarchical representation of all objects in the scene (meshes, cameras, lights, etc.), as well as their coordinate transformations. Global resampling methods will be run on whichever mesh is currently selected.

## Getting Acquainted with the Starter Code

Before you start, here is some basic information on the structure of the starter code. Your code for all parts except shading will be contained inside *student_code.cpp*. (For shading, you'll have to edit the *shader/frag* file.)

For Bezier patches, you'll be filling in member functions of the `BezierPatch`

class, declared in *bezierPatch.**. We have put dummy definitions for all the Bezier patch functions you need to modify inside *student_code.cpp*, where you'll be writing your code. You may additionally need to add member variables to the class definition in *bezierPatch.h*.

For half-edge meshes, you'll be filling in member functions of the `HalfedgeMesh`

class, declared in *halfEdgeMesh.**. We have put dummy definitions for all the half-edge functions you need to modify inside *student_code.cpp*, where you'll be writing your code.

For shaders, you'll be editing the *shader/frag* file.

Before you attempt parts 2-5 (the half-edge sections), you'll want to quickly consult these lecture slides as a half-edge refresher and then read this in-depth article with more detail about the half-edge data structure and its implementation in the starter code.

## Part 1: Fun with Bezier Surfaces

We'll begin with a warmup problem to introduce you to working with triangle meshes before jumping into the half-edge data structure. The goal for this part is to tessellate a Bezier surface into triangles. The input Bezier surface is represented by 16 control points in 3D space. These points are stored as a 4x4 `Vector3D`

array called `controlPoints`

, which can be accessed from inside the `BezierPatch`

class. You need to tessellate the given Bezier surface uniformly on a 8x8 grid in parameter space, which should produce 8x8x2=128 triangles. You'll want to consult this slide for the proper formula to evaluate each point, remembering the definition of Bernstein polynomials as well.

To implement this, you may need to add some member variables to the `BezierPatch`

class (by modifying *bezierPatch.h*). The `BezierPatch::preprocess`

function allows you to do some precomputation. For example, you might initialize your own member variables here based on the 16 control points. The `BezierPatch::addTriangle`

function (defined inside *bezierPatch.cpp*) helps you add triangles to the output mesh. If your implementation is correct, you will be able to see a teapot by passing `bez/teapot.bez`

as the input argument.

These are the functions inside *student_code.cpp* that you will need to modify:

`Bezier::preprocess`

`Bezier::evaluate`

`Bezier::add2mesh`

## Part 2: Average normals for half-edge meshes

Next, we move on to working with the full half-edge data structure. Again, read this article before you start working with the `HalfedgeMesh`

class in this and subsequent parts of the assignment. Make sure you understand the code given for a `printNeighborPositions`

function in particular.

In this part, you will implement the `Vertex::normal`

function inside *student_code.cpp*. This function returns the area-weighted average normal vector at a vertex. This slide depicts this graphically.

In order to compute this value, you will want to use a `HalfedgeIter`

to point to the `Halfedge`

you are currently keeping track of. A `HalfedgeIter`

(analogously `VertexIter`

, `EdgeIter`

, and `FaceIter`

) is essentially a pointer to a `Halfedge`

(respectively `Vertex`

, `Edge`

, and `Face`

), in the sense that you will use `->`

to dereference its member functions. Also, you can test whether two different iterators point to the same object using `==`

, and you can assign one iterator to point to the same thing as another using `=`

(this will NOT make the pointed-to objects have the same value, just as with pointers!).

**Caveat**: For this part only, you're implementing a `const`

member function, which means you need to use `HalfedgeCIter`

s instead of `HalfedgeIter`

s. These merely promise not to change the values of the things they point to.

The relevant member functions for this task are `Vertex::halfedge()`

, `Halfedge::next()`

and `Halfedge::twin()`

. You will also need the public member variable `Vector3D Vertex::position`

.

How you might use these to begin implementing this function:

```
Vector3D n(0,0,0); // initialize a vector to store your normal sum
HalfedgeCIter h = halfedge(); // Since we're in a Vertex, this returns a halfedge
// pointing _away_ from that vertex
h = h->twin(); // Bump over to the halfedge pointing _toward_ the vertex.
// Now h->next() will be another edge on the same face,
// sharing the central vertex.
```

At this point, you should

- Save a copy of
`h`

's value in another`HalfedgeCIter h_orig`

. - Start a
`while`

loop that ends when`h == h_orig`

. - Inside each loop iteration:
- Accumulate area-weighted normal of the current face in the variable
`n`

. You can do this by using the cross product of triangle edges (since the cross product of two vectors has a norm equal to twice the area of the triangley the define, so these vectors are already area weighted!). We've defined the cross product for you, so don't re-implement it yourself! - Once you've added in the area-weighted normal, you should advance
`h`

to the halfedge for the next face by using the`next()`

and`twin()`

functions.

- Accumulate area-weighted normal of the current face in the variable
- After the loop concludes, return the re-normalized unit vector
`n.unit()`

.

If you are still feeling confused about how to use iterators, reread the halfedge article or take a look at the extensive comment at the top of the `halfEdgeMesh.h`

file.

## Part 3: Edge Flip

Now you should be a little more comfortable traversing the half-edge pointers. In this task, you will implement a more substantial method: a local remeshing operation that "flips" an edge, implemented inside the method `HalfedgeMesh::flipEdge`

in file *student_code.cpp*.

More precisely, suppose we have a pair of triangles $(a,b,c)$ and $(c,b,d)$. After flipping the edge $(b,c)$, we should now have triangles $(a,d,c)$ and $(a,b,d)$:

Your solution should:

- Never flip boundary edges (just return immediately if either neighboring face is a boundary loop). Every object has a useful
`boundary()`

function that can tell you if it is or is not on the boundary. - Perform only a constant amount of work -- the cost of flipping a single edge should
**not**be proportional to the size of the mesh! - Not add or delete any elements. Since there are the same number of mesh elements before and after the flip, you should only need to reassign pointers.

The biggest challenge in properly implementing this operation (as well as split) is making sure that all the pointers still point to the right place in the modified mesh. An easy recipe for ensuring that all pointers are still valid after any general remeshing operation is:

- Draw a picture and/or write down a list of all the elements (vertices, edges, faces, halfedges) that will be needed from the original mesh.
- Draw a picture and/or write down a list of all the elements that should appear in the modified mesh.
- Allocate any new elements that are needed in the modified mesh, but do not appear in the original mesh (only relevant for the next part).
- For every element in the "modified" picture, set
**all**of its pointers -- even if they didn't change. For instance, for each halfedge, make sure to set`next`

,`twin`

,`vertex`

,`edge`

, and`face`

to the correct values in the new (modified) picture. For each vertex, edge, and face, make sure to set its`halfedge`

pointer. A convenience method`Halfedge::setNeighbors()`

has been created for the purpose of setting all pointers inside a halfedge at once.

The reason for setting all the pointers (and not just the ones that changed) is that it is very easy to miss a pointer, causing your code to fail. Once the code is **working**, you can remove these unnecessary assignments if you wish.

*Tip:* you can check which other objects in the mesh point to a given object by using the debug functions `check_for`

inside `HalfEdgeMesh`

. There's more information about these functions at the bottom of the halfedge documentation article.

## Part 4: Edge Split

This time, you will make a different local modification to the mesh in the neighborhood of an edge, called a **split**. In particular, suppose we have a pair of triangles $(a,b,c)$ and $(c,b,d)$. The edge $(b,c)$ is split by inserting a new vertex m at its midpoint and connecting it to the opposite vertices $a$ and $d$, yielding four triangles:

This task is a bit tricker than "flip" because there are more pointers to keep track of, and you will have to allocate new mesh elements this time (e.g., two new triangles, three edges, some halfedges...). Your implementation should:

- Ignore requests to split boundary edges, unless you are trying for extra credit (just return immediately if either neighboring face is a boundary loop). Note that splitting a boundary edge
**does**make sense, but flipping a boundary edge**does not**make sense. - Assign the position of the new vertex to the midpoint of the original edge, i.e., the average of its two endpoints (see
`Vertex::position`

). - Perform only a constant amount of work -- the cost of splitting a single edge should
**not**be proportional to the size of the mesh! - Allocate only as many new elements as needed; there should be no "orphaned" elements that are not connected to the rest of the mesh.

To obtain a correct implementation, you might try following the same "recipe" given in the previous task (though clever, clean, and simple alternatives are of course always welcome). To verify that your implementation works correctly, try flipping some edges that you've split, and splitting some edges that you flipped.

*Extra credit:*support edge split for edges on the boundary. For this, you will need to carefully read the section about the "virtual boundary face" in the halfedge article. In this case, you will split the edge in half but only split the face that is non-boundary into two. Give screenshot examples if you do this.

## Part 5: Upsampling via Loop Subdivision

Now, we can leverage the previous two parts to make implementing the mesh topology changes in Loop subdivision very simple! In this task, you will implement the whole Loop subdivision process inside the `MeshResampler::upsample`

in *student_code.cpp*.

Loop subdivision is somewhat analogous to upsampling using some interpolation method in image processing: we may have a low-resolution polygon mesh that we wish to upsample for display, simulation, etc. Simply splitting each polygon into smaller pieces doesn't help, because it does nothing to alleviate blocky silhouettes or chunky features. Instead, we need an upsampling scheme that nicely interpolates or approximates the original data. Polygon meshes are quite a bit trickier than images, however, since our sample points are generally at *irregular* locations, i.e., they are no longer found at regular intervals on a grid.

Loop subdivision consists of two basic steps:

- Change the mesh topology: split each triangle into four by connecting edge midpoints (sometimes called "4-1 subdivision").
- Update vertex positions as a weighted average of neighboring positions.

4-1 subdivision does this to each triangle:

And the following picture depicts the correct weighting for the new averaged vertex positions:

Written out, the new position of an old vertex is

```
(1 - n*u) * original_position + u * neighbor_position_sum
```

where `n`

is the number of neighboring vertices, `u`

is a constant as depicted in the figure above, `original_position`

is the vertex's original position, and `neighbor_position_sum`

is the sum of all neighboring vertices' positions.

The position for a newly created vertex v that splits an edge AB connecting vertices A and B and is flanked by opposite vertices C and D across the two faces connected to AB in the original mesh will be

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

If we repeatedly apply these two steps, we will converge to a smoothed approximation of our original mesh. In this task you will implement Loop subdivision, leveraging the split and flip operations to handle the topology changes. In particular, you can achieve a 4-1 subdivision by applying the following strategy:

- Split every edge of the mesh in any order whatsoever.
- Flip any new edge that touches a new vertex and an old vertex.
*Note*: Every original edge will now be represented by 2 edges, you*should not*flip these edges, because they are always already along the boundary of the 4 way divided triangles. In the diagrams below, you should only flip the blue edges that connect an old and new vertex, but you should not flip any of the black new edges.

The following pictures (courtesy Denis Zorin) illustrate this idea:

##### Implementation Walkthrough

For Loop subdivision, we have also provided some additional data members that will make it easy to keep track of the data you need to update the connectivity and vertex positions. In particular:

`Vertex::newPosition`

can be used as temporary storage for the new position (computed via the weighted average above). Note that you should*not*change the value of`Vertex::position`

until*all*the new vertex positions have been computed -- otherwise, you are taking averages of values that have already been averaged!- Likewise,
`Edge::newPosition`

can be used to store the position of the vertices that will ultimately be inserted at edge midpoints. Again, these values should be computed from the original values (before subdivision), and applied to the new vertices only at the very end. The`Edge::newPosition`

value will be used for the position of the vertex that will appear along the old edge after the edge is split. We precompute the position of the new vertex before splitting the edges and allocating the new vertices because it is easier to traverse the simpler original mesh to find the positions for the weighted average that determines the positions of the new vertices. `Vertex::isNew`

can be used to flag whether a vertex was part of the original mesh, or is a vertex newly inserted by subdivision (at an edge midpoint).`Edge::isNew`

likewise flags whether an edge is a piece of an edge in the original mesh, or is an entirely new edge created during the subdivision step.

Given this setup, we strongly suggest that it will be easiest to implement subdivision according to the following "recipe" (though you are of course welcome to try doing things a different way!). The basic strategy is to *first* compute the new vertex positions (storing the results in the `newPosition`

members of both vertices and edges), and only *then* update the connectivity. Doing it this way will be much easier, since traversal of the original (coarse) connectivity is much simpler than traversing the new (fine) connectivity. In more detail:

- Mark all vertices as belonging to the original mesh by setting
`Vertex::isNew`

to`false`

for all vertices in the mesh. - Compute updated positions for all vertices in the original mesh using the vertex subdivision rule, and store them in
`Vertex::newPosition`

. - Compute new positions associated with the vertices that will be inserted at edge midpoints, and store them in
`Edge::newPosition`

. - Split every edge in the mesh, being careful about how the loop is written. In particular, you should make sure to iterate only over edges of the original mesh. Otherwise, you will keep splitting edges that you just created!
- Flip any new edge that connects an old and new vertex.
- Finally, copy the new vertex positions (
`Vertex::newPosition`

) into the usual vertex positions (`Vertex::position`

).

If you made the requested modification to the return value of `HalfedgeMesh::splitEdge()`

(see above), then an edge split will now return an iterator to the newly inserted vertex, and the halfedge of this vertex will point along the edge of the original mesh. This iterator is useful because it can be used to (i) flag the vertex returned by the split operation as a new vertex, and (ii) flag each outgoing edge as either being new or part of the original mesh. (In other words, Step 3 is a great time to set the members `isNew`

for vertices and edges created by the split. It is also a good time to copy the `newPosition`

field from the edge being split into the `newPosition`

field of the newly inserted vertex.)

You might try implementing this algorithm in stages, e.g., *first* see if you can correctly update the connectivity, *then* worry about getting the vertex positions right. Some examples below illustrate the correct behavior of the algorithm.

**Possible Extra Credit Extensions:**

*Support surfaces with boundary.*To do this, you will first need to make sure your edge split operation appropriately handles boundary edges (you do not need to change your edge flip function). You will also need to use a different weighted average for boundary vertices; see Boier-Martin et al, "A Survey of Subdivision-Based Tools for Surface Modeling" for more information.*Implement additional subdivision schemes.*There are many alternatives to Loop subdivision. Triangle subdivision schemes include Butterfly and modified Butterfly (which are interpolating rather than approximating) and Sqrt(3) (which refines the mesh at a "slower" rate); the most popular subdivision scheme for quadrilateral meshes is Catmull-Clark. There are also special subdivision schemes for handling meshes with high degree vertices, e.g., extraordinary vertices, called polar subdivision.

## Part 6: Fun with Shaders

For this part, you will implement Phong shading and environment map reflection shading. Take a look at these slides to review the basic concepts and variables used in shading equations.

The necessary variables for you to compute shader values are already defined in the shader file. In the *meshedit* program, you can press 0-9 to switch between different shading effects. Initially only shader #0 is implemented as reference. Shader #1 and #2 are the two shading effects you will need to implement. Shaders #3-#9 are for extra credit. You can try your own shading there -- be creative!

For both shader #2 and #3, you'll need to figure out the reflection direction of a given input direction. The figure below shows you how to do this.

Suppose the blue arrow in the figure is the normal direction $\vec{n}$ of a surface point. The reflection direction $\vec{o}$ of the input direction $\vec{i}$ shown in red can be obtained by $\vec{o} = 2(\vec{i}\cdot \vec{n})\vec{n} - \vec{i}$.

### Tips on Environment Mapping

First compute the reflection direction in $(x, y, z)$ coordinates. Then, figure out $(\theta,\ \phi)$ in spherical coordinates as shown in the figure below.

Once you have $\theta$ and $\phi$, simply use $(\ \theta/(2\pi),\ \ \phi/\pi\ )$ as texture coordinates to access environment texture.

In *shader/frag*, a macro called `USE_AUTO_MIPMAP`

is defined as 0 by default. If you want to enable auto mipmap to antialias, set the macro to be 1. However, when you enable it, you will see a seam on the object due to angle wrap.

### GLSL Tutorials

Here is a short tutorial on GLSL. It should have everything you need to know about this part of the assignment. If you want to try some really fancy shaders for extra credits or learn more about GLSL, please refer to this link.

*Extra Credit:*Create your own shading using shaders #3-9. Some interesting shading effects include bump mapping, 3D texture mapping, Perlin Noise to make marble...

### Reference Images

#### Phong Shading

#### Environment Map Reflection Shading

Here is a list of functions you will need to modify inside *shader/frag*:

`shadePhong`

`shadeEnvmapReflection`

If you want write any additional shaders to try for extra credit, you will append those functions to the same file.

Some examples are here:

#### Bump Mapping

#### 3D Texture Mapping

## Part 7: Design your own mesh!

For this part, we'd like you to design your own COLLADA *.dae* file format mesh using the free program Blender. Our suggestion for a baseline starting point is to design a humanoid mesh with a head, two arms, and two legs. We've created a Blender video tutorial and a modeling tips article to guide you through the basics of making a simple humanoid mesh.

Once you make your mesh, you should load it into *meshedit* and use what you've implemented! Subdivide it to smooth and use your custom shaders from part 6.

Here are some examples of Weilun's mesh-man before and after subdivision and also with the environment map applied:

*Open Ended Extra Credit:*Make a super cool or super detailed mesh! Write fancy shaders and apply them to your mesh. Implement additional geometric operations and demonstrate them on your mesh. The sky is the limit! Describe anything you do beyond the ordinary in detail in your writeup.

### Art competition ideas

You'll submit your favorite screenshot of your mesh as **competition.png** in your root project directory. Here are some suggestions...

- Add additional detail to your mesh - fingers, facial features.
- Google "box modeling" (images and videos) to get inspired.
- Investigate additional functionality in Blender to design an alternative shape.
- Programmatically generate a mesh that approximates a 3D fractal or other complex shape.
- Write a super cool custom shader that makes your mesh look awesome.

## Website writeup

The goals of your write-up are for you to (a) think about and articulate what you've built and learned in your own words, (b) have a write-up of the project to take away from the class. Your write-up should include:

- An overview of the project, your approach to the various parts, what problems you encountered and how you solved them. Strive for clarity and succinctness.
- On each part, make sure to include the results described in the Deliverables section for each Part. If you failed to generate any results correctly, provide a brief explanation of why.
- The last Part is where you have the opportunity to be creative and individual, so be sure to provide a good description of what you were going for and how you implemented it.
- Clearly indicate any extra credit items you completed, and provide a good write-up and illustration.

The writeup is our main method of evaluating your work, so it is important to spend the time to do it correctly. Plan ahead to allocate time for the writeup well before the deadline.

## Friendly advice from your GSIs

- Start early. Once again, this is a multi-part assignment, and you should manage your time appropriately. Remember that pernicious bugs can sap your time like no other, and always keep in mind Hofstadter's Law.
- Parts 1 and 2 should be straightforward to code once you understand the concepts.
- Parts 3 and 4 will be trickier to write correctly, since they involve pointers (exposed to you as iterators). Make sure you test these parts
*together*on a few meshes -- alternately flip and split edges at least ten times in nearby and far apart regions of the mesh as a first test. Obviously, correct behavior does not imply correct code, but*in*correct behavior does imply incorrect code :) - In Part 6 you'll have to use the GLSL shader language. The syntax is very similar to C, but you might be tripped up by the small differences. It is a language designed for writing shaders, so there should be a way to do most mathematical operations you'll want to do fairly elegantly.
- Part 7 involves learning how to use a 3D modeling tool. Weilun's step-by-step directions will help, but it will be another new experience. We recommend getting started early in case you have questions. A good first milestone would be creating a simple box mesh in Blender and loading it into the
*meshedit*application as a*.dae*file. This doesn't depend on any other part of the assignment, so you can do it anytime (perhaps as a nice from chasing pointers...). - Allocate time for your writeup before the deadline. Again, it's our main method of evaluating your work, so submitting something you patched together at the last minute is not in your best interest.

## Submission Instructions

As with the first assignment, log in to an instructional machine, navigate to the root directory of your project, and run

```
zip -r hw2.zip .
submit hw2
```

This indicates you have succeeded:

```
Looking for files to turn in....
Submitting hw2.zip.
The files you have submitted are:
./hw2.zip
Is this correct? [yes/no] yes
Copying submission of assignment hw2....
Submission complete.
```

There are more detailed instructions (including how you can use *scp* to copy your files onto the s349 machines) here.

## Appendix

### Keyboard Controls

Command | Key |
---|---|

Flip the selected edge | F |

Split the selected edge | S |

Upsample the current mesh | U |

Toggle information overlay | I |

Select the next halfedge | N |

Select the twin halfedge | T |

Switch to GLSL shaders | W |

Switch between GLSL shaders | 0-9 |

Toggle using area-averaged normals | Q |

Recompile shaders | R |

Reset camera to default position | SPACE |

Edit a vertex position | (click and drag on vertex) |

Rotate camera | (click and drag on background, or right click) |