In this assignment, you will explore shape representations in graphics by implementing a library for basic mesh editing. In particular, you will use a matrix-based framework to transform the vertices of a mesh using affine transformations.

Please click here to create your repository.

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 apply transformations to the 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 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 . Note that these 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 . 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. To do so, I recommend (but do not require!) that you extend your abstract base class Surface from A03. 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.

Regardless of what data structure you use for storing the mesh, you will find that using your class to store three-dimensional vectors from will be necessary here to store the vertex positions. For storing mesh topology, you may want to consider a variety of different data structures as we discussed in class (i.e. separated triangles, triangle-neighbor, or halfedge). You may pick any of the data structures in class, but please document in the README which data structure you used.

Part 3: Mesh Transformation

After storing the mesh in memory, you should provide the user functionality to transform the mesh using a sequence of transformations that you encode as matrix based operation. To do so, you should let the user interactively (from the command line) enter a sequence of operations. Your code must support the following commands:

  • Translation, entered as T followed by x y z, where are floats for the translation in each of coordinate axes.

  • Rotation, entered as R followed by x y z theta, where is an arbitrary vector to rotate around and is the CCW angle of rotation.

  • Scaling, entered as S followed by x y z, where , , and are floats for the amount to scale by in each of the coordinate axes.

  • Done, entered as D followed by nothing, to end the sequence of commands.

As you are reading all commands from the user, you should construct the matrix that expresses the combined sequence of transformations being applied in the sequence that they are entered. Next, you should transform all vertices of the input mesh using this sequence, treating each vertex as a 4-dimensional homogeneous coordinate with . You should only have to transform all vertices once for any sequence of transformations.

I recommend coding all of this by implementing a matrix class that includes an operator*() function for matrix-matrix multiplication as well as an operator*() that takes as input a three-dimensional vector and returns the three-dimensional vector that is the result of promoting. Most other matrix operations (like inverse or transpose) are not necessary yet, but you may want to consider implementing these for future assignments.

After transformation, you are required to write out a valid .obj file that has the transformed input mesh.

Part 4: Execution and Display

Your program, prog04, should take as input two parameters: (1) the input .obj filename and (2) an output .obj filename to write.

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. Note that you may discover than many freely available meshes are not watertight manifolds, which may cause undesirable effects when building your data structure.

Part 5: 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 6.6 on pg. 137 of the textbook.

  2. Exercise 6.8 on pg. 137-138 of the textbook.

  3. Exercise 12.1 on pg. 321 of the textbook.

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

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

Submission

  • You should use git to submit all source code files and a working CMakeLists.txt. Do not submit any build files, binary files, or otherwise. The expectation is that your code will be graded by cloning your repo and then executing:
$ mkdir build
$ cd build
$ cmake ..
$ make

Your code must compile on the CS lab machines, in particular we will test on cambridge. Code that does not compile in this way will be given an automatic zero. You will be given one “warning” for the first instance during the semester that it does not compile, but after a zero will occur. If you are working on a different environment, please log into cambridge and test your code before submitting.

  • Make sure that this build process produces an executable named prog04. You will need to edit CMakeLists.txt accordingly.

  • Please provide a README.md file that provides a text description of how to run your program and any command line parameters that you used. Also document any idiosyncrasies, behaviors, or bugs of note that you want us to be aware of.

  • To summarize, my expectation is that your repo will contain:

    1. A README.md file
    2. Answers to the written questions in a separate directory named written
    3. A CMakeLists.txt file
    4. All .cpp and .h files that you authored and are necessary to compile your code
    5. (Optionally) any other test scenes/images/objects

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 and storing it in a mesh data structure10
Allowing the user to enter in a sequence of transformations5
Correctly computing translation matrices5
Correctly computing rotation matrices5
Correctly computing scaling matrices5
Correctly computing the combined transformation matrices5
Using the combined transformation matrix to transform vertex positions10
Writing transformed mesh as an .obj output file5

50
Written Questions 20
Total 100


Extra Credit

Implementing features above and beyond the specification may result in extra credit, please be sure to document these in your README.

Extra credit features might include, but are not limited to, implementing more complex transformations (e.g. shearing), providing other operations to the mesh such as computing normals or surface area, or performing mesh smoothing and/or subdivision operations.