Undergraduate students will explore shape representations in graphics by implementing a fundamental operation used in computer graphics: mesh smoothing (sometimes called mesh fairing). In particular, they will implement Laplacian smoothing, a technique that iteratively updates vertex positions based on their neighborhoods. Laplacian smoothing has a deep connection to signal processing, in particular smoothing kernels that we discussed earlier in class. For more information about that, you might find A signal processing approach to fair surface design, by Gabriel Taubin, an interesting read. Luckily, we will not need such complex machinery to implement it.

Objectives

This assignment is designed to teach students concepts with shape representation in computer graphics. Specifically, 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 smooth mesh surfaces.
  • Implement and understand the concept of Laplacian smoothing, allowing one to update the positions of vertices based on neighborhood information.
  • 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. Specifically, you must implement the triangle-neighbor structure as described in Chapter 12 of the textbook.

You may find that using your class to store three-dimensional vectors from from A03UG will be useful here to store the vertex positions. For storing mesh topology, your data structure should follow convention of the textbook. Each mesh vertex will store a pointer to one of its adjacent triangles while each triangle will store pointers to all three of its triangle neighbors. Doing so will require you to compute this information from the input triangle mesh as you read it in. If done correctly, you should be able to perform the appropriate adjacency query required in the next step.

You may also want to consider making this class a subset of your abstract Surface from A03UG. 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: Laplacian Smoothing

The basic algorithm for Laplacian smoothing creates a new vertex position for each vertex in the input mesh by computing both the average position of all of its edge neighbors and taking a step from the original position of the vertex towards this new position. Specifically, let \({\bf x}_i\) by the position of vertex \(i\). One will compute the updated position \({\bf x}'_i\) as:

\[\Delta {\bf x}_i = \frac{1}{N} \sum_{j} ({\bf x}_j - {\bf x}_i)\] \[{\bf x}'_i = {\bf x}_i + \lambda \Delta {\bf x}_i\]

In the above, \(\Delta {\bf x}_i\) is called the Laplacian, and it is based on a weighted sum of the edge vectors to the positions \({\bf x}_j\) for all adjacent vertices \(j\). \(\Delta {\bf x}_i\) plays a role that is very similar to a stencil we saw for image processing. In particular, if \(i\) had exactly four neighbors, it would add them up with weights:

\[\frac{1}{4} \begin{bmatrix} 0 & 1 & 0 \\ 1 & -4 & 1 \\ 0 & 1 & 0 \end{bmatrix}\]

The parameter \(\lambda\) plays a role of controlling the rate of smoothing. In the case where \(\lambda = 1\), one can see that \({\bf x}'_i\) will precisely be the average position of all of its neighbors, \(\frac{1}{N} \sum_{j} {\bf x}_j\), since the \({\bf x}_i\) terms cancel. Typically, one uses smaller steps to help smooth more gracefully, and thus \(0 < \lambda < 1\) is a useful range.

To enumerate all adjacent vertex positions \({\bf x}_j\), you can use the TriangleOfVertex() method described in the textbook to access all vertices \(j\) adjacent to vertex \(i\). Doing so will count each vertex \(j\) twice, as each is shared by two adjacent triangles. This is OK to double count each of them, as the \(N\) you will compute will actually be double what the true value for \(N\) is.

Additionally, Laplacian smoothing is usually done in multiple iterations. Your code must support producing new positions for all vertices by iteratively applying this operator. At each iteration, all vertex positions should be computed from the previous iterations locations (thus, you should be careful not to use intermediate positions as your are applying the smoothing to each vertex).

Part 4: Execution and Display

Your program, prog04, should take as input four parameters: (1) the input .obj filename, (2) an output .obj filename to write, (3) a non-negative integer, \(I\), for the number of iterations of smoothing, and (4) a float value, \(\lambda\), to control the rate of smoothing.

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 not find them as easy to use.

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, which may cause undesirable effects when building your data structure or computing the smoothing operator. Your code needs to only support smoothing manifold meshes without boundary.

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. Exercise 12.1 on pg. 321 of the textbook.

  2. How do triangle strips help store a mesh more efficiently?

  3. Explain what is different about object partitioning schemes and space partitioning schemes when constructing spatial data structures for acceleration.

  4. Imagine that you have additional data other than position stored on the vertices of a mesh (such as colors). How might you update them when performing Laplacian smoothing?

  5. Frequently, textures are generated procedurally instead of storing them in an image. Write pseudocode for the function that you would use to create an infinitely big checkerboard texture (hint: see Section 11.5.1)

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 file into a triangle-neighbor structure10
Writing smoothed mesh as an .obj output file5
Correctly enumerating all neighboring vertices10
Properly computing new vertex locations10
Correctly allowing iterative application of the operator5
Allowing the user to vary parameters from the command line10

 50
Written Questions 20
Total 100