Graduate students will explore shape and surface representation by implementing a program that computes a subdivision surface of a triangle mesh. In particular, they will implement Loop subdivision, named after Charles Loop, that happens to be one of the most common subdivision techniques. Subdivision surfaces allow one to represent smooth shapes by specifying a coarse triangle mesh, and have been used in numerous applications in movies and games.

Objectives

This assignment is designed to teach students advanced concepts with shape representation in computer graphics. Thus, students will:

  • Understand triangle mesh file formats, specifically by implementing a basic file parser that reads and writes files the Wavefront .obj format.
  • Understand triangle mesh data structures, implemented through a data structure that stores triangle meshes internally so that one can compute subdivision surfaces.
  • Implement and understand the framework of subdivision surfaces, allowing one to refine a triangle mesh to produce a smoother, higher resolution triangle mesh.
  • Learn the basics of open source geometry tools for shape modeling, specifically MeshLab.

Part 1: Triangle Mesh File Formats

Your code will implement a basic reader and writer for Wavefront .obj files, as discussed in class. You need only to support reading lines that begin with v (for a mesh vertex), f (for a mesh face) and comments (that start with #).

Lines that are vertices will follow the form v x y z, where x, y, and z are three floats representing the \((x,y,z)\) position of the mesh vertex.

Lines that are faces will follow the form f v1 v2 ... vk where v1, v2, through vk are integer indices that refer to specific mesh vertices \(\{v_1, v_2, \ldots, v_k\}\). Note that this indices begin counting with 1 instead of 0! Also, while the .obj standard supports polygonal faces of arbitrary vertices, your code need only support loading triangles (and thus you can assume that \(k = 3\). You can either skip or report an error if an .obj file has more than 3 vertices for a given face.

You should also implement methods to write the .obj file from your internal data structure, as described next.

Part 2: Storing Triangle Meshes in Memory

After parsing the .obj file, you should create an internal data structure to store the triangle mesh. You cannot use an external library for this, but you can pick whatever mesh data structure you prefer for this task.

You may find that using your class to store three-dimensional vectors from from A03G will be useful here to store the vertex positions.

Additionally, you will need to store the mesh topology in the form of triangle indices. At a minimum, your mesh data structure should support a sufficient number of operations to access adjacency information for completing the task of the assignment. You may also want to consider making this class a subset of your abstract Surface from A03G. But, in this assignment you will not be required to render triangle surfaces using your own code, so the functionality for processing ray hits will not be necessary.

Part 3: Subdivision

Loop subdivision applies a simple rule to recursively refine a triangle mesh. The idea is described in detail in Charles Loop’s MS Thesis, Chapter 3. You will also find Section 4.2 of the 1999 SIGGRAPH Course on Subdivision by Zorin et al. to be a good summary of the algorithm.

One way to think about subdivision is that it is a mesh operation that proceeds in two steps:

  1. Construct a new mesh whose topology is derived from the input.

  2. Compute new vertex positions in the updated topology by on weighted sums of positions of the input.

For Loop subdivision, the new mesh topology is constructed by adding a new vertex for every edge in the mesh, and then connecting these new vertices to the original ones to create four new triangles for every input triangle. Considering a triangle with vertices \(\{v_a, v_b, v_c\}\), you will create four new triangles with vertices \(\{v'_a, v_{ab}, v_{ac}\}\), \(\{v'_b, v_{bc}, v_{ab}\}\), \(\{v'_c, v_{ac}, v_{bc}\}\), and \(\{v_{ab}, v_{bc}, v_{ac}\}\).

Of course, we want to maintain the manifold topology of the input, so an adjacent triangle will share the new vertices. For example, consider a triangle \(\{v_d, v_c, v_b\}\), that shares edge \(bc\) with \(\{v_a, v_b, v_c\}\). In the output mesh, \(v'_b\), \(v_{bc}\), and \(v'_c\) should all be shared new vertices.

In addition, your newly created mesh should preserve the orientation of the input mesh, and produce a consistently oriented triangle mesh. You may assume that the input triangle mesh is consistently ordered, but you are required to make sure that the output mesh you produce is consistently ordered.

After ensuring your new mesh has the correct topology, you will compute positions for all of the newly created vertices. All new vertices are placed using a weighted average of neighboring vertices. The new edge vertices, e.g. \(v_{ab}\), are placed using a weighted sum of their endpoints as well as two vertices of the opposite triangles. The updated positions of the original vertices, e.g. \(v'_a\), are placed using a weighted sum of all adjacent vertices.

The original algorithm proposes weights based on a uniform scheme with a \(\cos()\) factor for weights, but typically one uses the simplified scheme due to Joe Warren. See Figure 4.3 of the SIGGRAPH Course. Please document in your README what weighting scheme you used. While weights would differ if boundary edges exist, you need only implement the cases where the input triangle mesh has a manifold topology without boundary (and thus, it has well-defined neighborhoods).

Part 4: Execution and Display

Your program, prog04, should take as input three parameters: (1) the input .obj filename, (2) an output .obj filename to write, and (3) a non-negative integer, \(i\), for the number of iterations of Loop subdivision to run. Note that the number of triangles in a Loop subdivided mesh grow by a factor of four for each iteration, and thus a mesh with \(n\) triangles will end up having a \(4^{i}n\) triangles for \(i\) iterations. Therefore, when debugging, it helps to keep \(i\) fairly low as the number of output triangles can grow quickly.

For debugging purposes, you can use the freely available, open-source, cross platform program, MeshLab to display your triangle meshes. There are also a variety of online .obj viewers that work in your browser, but you might have trouble using them to view both the mesh and the newly created edges.

While we have include a variety of sample .obj files in your repository, you may want to try out models you can find online too. You may discover than many freely available meshes are not watertight manifolds, so be careful when testing since you may find cases that are tricky to handle.

Part 4: Written Questions

Please answer the following written questions. You are not required to typeset these questions in any particular format, but you may want to take the opportunity to include images (either photographed hand-drawings or produced using an image editing tool).

Most questions should able to be answered in 100 words or less of text.

Please create a commit a separate directory in your repo called written and post all files (text answers and written) to this directory.

  1. Imagine that you have additional data other than position stored on the vertices of a mesh (such as texture coordinates). How might you assign values for texture coordinates to the newly created vertices when performing subdivision?

  2. Exercise 12.4 on pg. 321 of the textbook.

  3. The valence of a vertex in a mesh is equal to the number of adjacent vertices (or, equivalently, the number of edges adjacent to it). Loop subdivision creates two types of vertices, one vertex for each original vertex (call these “V” vertices) and one vertex for each original edge (call these “E” vertices). What are the valences of “V” and “E” vertices?

  4. In a triangle mesh, vertices with valences other than six are called extraordinary vertices. Given an input mesh with \(k\) extraordinary vertices, how many extraordinary vertices will there be in a Loop subdivision of it?

  5. Explain the type of artifact caused by seams at discontinuous regions in a texture coordinate function.

Grading

Deductions

Reason Value
Program does not compile. (First instance across all assignments will receive a warning with a chance to resubmit, but subsequence non-compiling assignments will receive the full penalty) -100
Program crashes due to bugs -10 each bug at grader's discretion to fix


Point Breakdown of Features

Requirement Value
Consistent modular coding style 10
External documentation (README.md), Providing a working CMakeLists.txt 5
Class documentation, Internal documentation (Block and Inline). Wherever applicable / for all files 15
Expected output / behavior based on the assignment specification, including

Parsing the .obj file10
Writing .obj output files5
Implementing topological subdivision15
Producing a consistently ordered mesh5
Properly computing new vertex locations for both edge vertices and updated original vertices10
Allowing the user to vary parameters from the command line5

 50
Written Questions 20
Total 100