COS 426: Computer Graphics Spring 2014

Overview

In this assignment you will create a simple mesh processing program. The operations that you implement will mostly be filters that take an input mesh, process the mesh, and produce an output mesh.

Running the Program

The mesh processing program, meshpro, runs on the command line. It reads a mesh from a file (the first program argument) and writes a mesh to a file (the second program argument). In between, it processes the mesh using the filters specified by subsequent command line arguments. For example, to scale a mesh in.off by a factor of 1.1, and save the result in the mesh out.off, you would type:

% meshpro in.off out.off -scale 1.1 1.1 1.1

For each available mesh filter there may be one or more parameters -- e.g., -scale takes three factors (sx sy sz). To see the complete list of filters and their parameters, type:

% meshpro -help

If you specify more than one filter on the command line, they are applied in the order that they are found. For example,

% meshpro in.off out.off -scale 0.8 0.8 0.8 -rotate 0.5 0 0 0 0 0 1

would first scale the mesh by 0.8 in all three dimensions and then rotate the mesh by 0.5 radians around a line through the point (0,0,0) and with direction vector (0,0,1) -- i.e., the z-axis. Of course, you are welcome to create your own filters and add program arguments for them by editing meshpro.cpp. However, please do not change the program arguments for the filters already provided.

Implementing the Mesh Processing Operations

The assignment is worth 20 points. The following is a list of features that you may implement (listed roughly from easiest to hardest). The number in front of the feature corresponds to how many points the feature is worth. The features in bold face are required. The other ones are optional. Refer to the examples web page to see images of inputs and outputs for several of these filters.

• Analysis
  • (1) Compute average edge lengths: Compute the average length of edges attached to a vertex. This feature should be implemented first. To do it, you must design a data structure that allows O(K) access to edges attached to each vertex, where K is the number of edges attached to a vertex.
  • (1) Compute per-vertex normals: Compute the surface normal at a vertex. This feature should be implemented second. To do it, you must design a data structure that allows O(K) access to faces attached to each vertex, where K is the number of faces attached to a vertex. Then, to compute the normal for a vertex, you should take a weighted average of the normals for the attached faces, where the weights are determined by the areas of the faces. Store the resulting normal in the "normal" variable associated with the vertex. You can display the computed normals by hitting the 'N' key in meshview.
  • (3) Compute per-vertex Gaussian curvatures: Compute an estimate of the Gaussian curvature (the product of the principal curvautures) of the surface at a vertex. You can use a method based on the Gauss Bonet Theorem, which is described in [Akleman, 2006]. Store the resulting curvature values in the "curvature" variable associated with the for every vertex. You can display the computed curvatures by hitting the 'C' key in meshview.
• Warps
  • (1) Inflate: Move every vertex along its normal direction. The input parameter "factor" should be multiplied by the average length of the edges attached to the vertex to determine the displacement of each vertex along its normal direction. Note that factor can be negative, which means that the vertex should move in the direction opposite to the normal vector.
  • (1/2) Random noise: Add noise of a random amount and direction to the position of every vertex, where the input parameter "factor" should be multiplied by the average length of the edges attached to the vertex to determine its maximum displacement (i.e., displacement distances should be between 0 and "factor * vertex->AverageEdgeLength()."
  • (1/2) Fun: Warp a mesh using a non-linear mapping of your choice (examples are sine, bulge, swirl).
• Filters
  • (2) Smooth: Smooth the mesh by moving every vertex to a position determined by a weighted average of itself and its immediate neighbors (with weights determined by a Gaussian with sigma equal to the average length of edges attached to the vertex, normalized such that the weights sum to one).
  • (1) Sharpen: Accentuate details in the mesh by moving every vertex along the opposite of the vector determined by a weighted average of itself and its neighbors (with weights determined by a Gaussian with sigma equal to the average length of edges attached to the vertex, normalized such that the weights sum to one). This filter moves vertices by the vector exactly opposite from the one used for Smooth().
  • (1) Bilateral smoothing: Smooth the mesh using a bilateral filter as in [Jones et al, Siggraph 2003].
• Erosion
  • (3) Truncate: For every vertex, create a new vertex a parameter t [0-0.5] of the way along each of its N attached edges, and then "chop off" the pyramid whose base is formed by the new vertices and whose apex is the original vertex, creating new planar face(s) covering the hole. It is OK to assume that the input shape is convex for this feature.
  • (3) Bevel: For every edge, create a new face whose vertices are t [0-0.5] of the way along each of its attached edges. This requires first truncating all vertices by t, creating new vertices t [0-0.5] of the way along each of new edges, and then "chopping off" a prism for each of the original edges, creating new planar face(s) covering the holes. It is OK to assume that the input shape is convex for this feature.
• Remeshing
  • (2) Split faces: Split every face into K+1 faces (where K is the number of vertices on the face). Create a new vertex at the midpoint of every edge, remove the original face, create a new face connnecting all the new vertices, and create new triangular faces connecting each vertex of the original face with the new vertices associated with its adjacent edges.
  • (2) Star faces: Split every face into N triangles (where N is the number of vertices on the face). That is, create a new vertex at the centroid of the face, remove the original face, create N new triangular faces connecting the new vertex with each pair of adjacent vertices of the original face. Position the new vertex at a point that is offset from the centroid of the face along the normal vector by a distance equal to factor times the average edge length for the face.
  • (2) Split long edges: Iteratively split edges longer than max_edge_length. Note that every edge split produces a new vertex at the edge midpoint and replaces the two adjacent faces with four. Edges should be split repeatedly until there is none longer than the given threshold. Note: an extra point will be given if longer edges are split first (which produces better shaped faces). If you do this, note it in your writeup.
  • (4) Collapse short edges: Iteratively collapse edges shorter than min_edge_length. Note that every edge collapse merges two vertices into one and removes up to two faces (if the adjacent faces are triangles). Place the new vertex at the midpoint of the collapsed edge. Note: an extra point will be given if shorter edges are collapsed first (which produces better shaped faces). If you do this, note it in your writeup.
  • (4) Cluster vertices: Simplify the mesh by clustering vertices residing in the same cell of a grid defined by x, y, and z spacing parameters. All vertices within the same grid cell should be merged into a single vertex, that vertex should be placed at the centroid of the cluster vertices, and all edges and faces that collapse as a result of the vertex merging should be removed.
• Subdivision Surfaces
  • (2) Loop subdivision: Subdivide every face using the method in SplitFaces. Then, update the positions of all vertices according to the Loop subdivision weights. This only must work correctly for meshes with triangular faces.
  • (3) Catmull-Clark subdivision: Subdivide every N-sided face into N quads by creating a new vertex in the center of every face connected to new vertices at the center of every edge, and then update the positions of all vertices according to the Catmull-Clark subdivision weights. This only must work correctly for meshes with quadrilateral faces.
• Parametric Surfaces
  • (2) Bezier: Add new vertices and faces to the mesh representing uniform cubic Bezier patches. The control mesh file (specified after -bezier) should have M*N vertices representing control points arranged in a M by N array. The output file should contain the input mesh plus a fine triangular mesh with 4M * 4N vertices representing the cubic Bezier surface implied by the control points. That is, vertices at sixteen regular intervals of u and v on each 4x4 subset of the control mesh should be generated using the tensor product uniform cubic Bezier surface construction and connnected into triangles to form a polygonal approximation of the smooth Bezier surface.
  • (2) B-Spline: Add new vertices and faces to the mesh representing uniform cubic BSpline patches. The control mesh file (specified after -bspline) should have M*N vertices representing control points arranged in a M by N array. The output file should contain a fine triangular mesh with 4M * 4N vertices representing the cubic BSpline surface implied by the control points. That is, vertices at sixteen regular intervals of u and v on each 4x4 subset of the control mesh should be generated using the tensor product uniform cubic BSpline surface construction and connnected into triangles to form a polygonal approximation of the smooth BSpline surface.
• Procedural Modeling
  • (2) Surface of revolution: Add new vertices and faces to the mesh by sweeping a profile curve around an axis of revolution. The vertices representing the profile curve are provided in the passed mesh file (take the vertices of the mesh in order and ignore the faces). The axis of revolution and rotation angle step size are provided in the arguments. New vertices should be created by successively rotating the original vertices around the axis by the step size and new faces should be constructed by connecting adjacent vertices to create a surface of revolution.
  • (2) Surface sweep: Create new vertices and faces by sweeping a polygon along a curve. The vertices representing a cross-section polygon are provided in the first input mesh file, and the vertices representing the sweep centerline curve are provided in the second mesh file (for both, take the vertices of the meshes in order and ignore the faces). New vertices should be created by successively translating and rotating the vertices of the cross-section polygon to match the position and orientation of vertices/edges in the centerline, and new faces should be constructed by connecting adjacent vertices created during the sweep.
• Topological Fixup
  • (3) Fill holes: Create faces covering the holes of a mesh by connecting vertices on the boundary of every hole. You should completely cover the hole, while doing your best to produce well-shaped faces (e.g., by connecting closer vertices first).
  • (3) Fix cracks: Merge boundary vertices and edges within a specified distance (epsilon) of one another.
  • (4) Fix self-intersections: Insert edges at face-face intersections and discard the smaller part of the mesh "pinched" off by new edge loops. Note: this is hard.
• Boolean Operations
  • (5) Intersect: Compute the mesh enclosing the intersection of two meshes. This feature requires introducing edges at every face intersection and removing parts of the mesh that lie in the exterior of the solid object implied by either of the two meshes. See [Segal 1986] for details.
  • (5) Difference: compute the mesh enclosing the difference of two meshes. This feature requires introducing edges at every face intersection and removing parts of the mesh that lie in the interior of the solid object implied by the second mesh.
  • (5) Union: compute the mesh enclosing the union of two meshes. This feature requires introducing edges at every face intersection and removing parts of the mesh that lie in the interior of the solid object implied by both of the two meshes.
  • (4) Implement any of the boolean operations by rasterizing the meshes onto two voxel grids, then using max(), min(), or subtraction elementwise to compute the boolean operation, then extract the isosurface to produce the final mesh. Note that this method cannot be used to get credit for any of the other Boolean operations.
• Miscellaneous
  • (2) Crop: Crop the input mesh to the positive side of the plane. This feature requires clipping each polygon crossing the plane, and discarding any part of any face on the negative side of the plane.
  • (up to 3) Anything else: Implement any non-trivial mesh processing algorithm of your own choosing, and we will give you points according to the difficulty.

By implementing all the required features, you get 14 points. There are many ways to get more points:

• Implementing the optional features listed above;
• (1) Answering a nontrivial question on Piazza. Please copy the question and answer into your writeup.
• (1) Submitting a movie animating the results of applying one or more filters with continuously varying parameters (e.g. truncate);
• (1) Submitting one or more images or movies for the art contest; and
• (2) Winning the art contest.

It is possible to get more than 20 points for this assignment. Your final score will be calculated by adding your score on the required features (up to 14 points) and your bonus for winning the art contest (up to 2 points) to your score on the non-required features, where the value of non-required features incurs diminishing returns after the first 6 points: each successive point beyond 6 is worth 2/3 as much as the previous one. For example, if you get 12 of the 14 points for required features listed in bold and correctly implement optional features worth 10 more points, then your score is 19.1 (12 + 6 + 2/3 + (2/3)^2).

Getting Started

You should download the starter code from (cos426_assignment2.zip) as a starting point for the assignment. The zip file contains the correct directory structure for submissions, helpful source code, and a template writeup html file (see cos426_assignment2/README.txt in the zip file for details).

Compiling the code produces two executables: meshpro and meshview (or meshpro.exe and meshview.exe). meshpro is the program that processes mesh (just like imgpro from assignment #1), and meshview provides a way for you to visualize and process meshes interactively.

To implement the image processing features listed above, you should add code to the appropriate functions within src/R3Mesh.cpp, add commands to the Makefile to test them, and add sections to the writeup.html to present and discuss your results.

The starter code contains a skeleton class for representing and processing meshes (in R3Mesh.h and R3Mesh.cpp). It is able to read meshes in two simple mesh file formats: the RAY File Format (.ray) and the Object File Format (.off), the latter of which is commonly used for interchange between mesh processing programs. We provide several meshes that you can use to test your program in the "input/" directory of the zip file and at this web page sample meshes. However, you are not limited to these files -- you can find other .off files on the web.

The starter code also contains useful classes for manipulating 3D points, vectors, line segments, rays, lines, planes, boxes, and matrices in the R3 subdirectory, as well as the R2Image and R2 functions provided with Assignment 1.

Submitting

You should submit your solution using one zip file named cos426_assignment2.zip via CS dropbox at this submission link. The submitted zip file should have the following internal directory structure:

cos426_assignment2/

• writeup.html - your writeup (see the description below),
• Makefile - a Linux script that generates all the images in the output directory from the data in the input directory)
• src/ - the complete source code, including all the code for libraries, compilation, etc.
• input/ - all the input data for the commands in your Makefile
• output/ - all the output meshes and images referenced by your writeup
• art/ - all images submitted for the art contest (optional), and movie files submitted for the movie feature (optional).

The writeup.html file should be an HTML document demonstrating the effects of the features you have implemented and would like scored. For some features (e.g., curvature), you can simply show the input and output of your program. However, for features that take an input parameter (e.g., inflate), you should provide a series of images showing at least three settings of the input parameter to demonstrate that your code is working properly. You can start from the writeup.html provided with the distribution as a template -- simply add sections to that HTML file for the features you implement in the following format:

• the name of the feature on the top line,
• the input image and output image(s) on a second line,
• text listing the command(s) used to generate the output images on the following lines, and
• (optionally) comments about what to look for in your output (including possible problems in the implementation).

The src directory should have all code required to compile and link your program (including the files provided with the assignment), along with a Visual Studio Solution file and a Makefile to rebuild the code. We will not attempt to grade assignments that neither build in Visual Studio nor with GNU Make under Mac OS X.

The Makefile should be a script containing the commands that generate all the meshes in the output directory that demonstrate features of your program you would like scored. It should run without crashing when started in the cos426_assignment2/ directory (i.e., it should be possible to delete all the mesh files in the output directory and then run make to regenerate them).

We will test your code on Linux by running make in your src/ subdirectory, followed by make in the main assignment directory to create the output images. Please ensure that your code builds/runs in this way before submitting. Your Makefile should generate all the images in the output directory referenced by your writeup.

To save space, please submit images in .jpeg format (not .bmp or .ppm) and remove binaries and backup files from the src directory before submitting -- i.e., run make clean (under Linux or Mac OS) and execute "Clean Solution" on the "Build menu" in MS Visual Studio.

Note that you are expected to use good programming style at all times, including meaningful variable names, a comment or three describing what the code is doing, etc. Partial credit may not be assigned for code without comments.

FAQ

Answers to frequently asked questions:

• How can I view a mesh file interactively?
  The starter code provides source code for a program called meshview, which you can use to view a mesh file interactively. If you execute meshview input.off, a window will pop up showing the mesh. You can drag the cursor with the left mouse button down to rotate it, with SHIFT-left-button to scale it (or the middle mouse button), and CTRL-left-button to translate it. You can also type F in the window to toggle display of faces, E to toggle display of edges, V to toggle display of vertices, I to toggle display of vertex IDs, N to toggle display of normal vectors (not visible unless they have been computed), C to toggle display of curvature at vertices, and B to toggle display of the bounding box. You can write information to stdout about a particular point on a mesh (e.g., its position, its face index, etc.) by moving the mouse over the mesh and pressing the spacebar.

• How can I try some of the mesh processing operations interactively?
  You can also use meshview to try out some of your mesh processing operations. Clicking the right button will bring up a cadcading popup menu of commands that call functions from the R3Mesh to process the mesh being displayed. Using those commands, you can try out your implementations of the R3Mesh functions with immediate visual feedback.

• How can I create images showing my results for the writeup?
  You can create an image of a mesh interactivly using the F1 key or the "Save->Image" menu command in meshview. Each time you invoke one of these commands, a file will be written to "imageN.jpg", for N=1,2,etc. increasing each time an image is saved in the same session.

  You can also create an image of a mesh with a batch command (e.g., from your Makefile) using meshview meshfile -output_image imagefile.jpg -exit_immediately. A window will popup briefly, and then the program will save an image of the mesh as seen from the default camera view in the file with the given name.

• Is there an easier way to create the Makefile and HTML writeup for my examples?
  The starter code includes a Python script make.py and a data file writeup.txt that you can use to generate a Makefile/NMakefile and corresponding writeup (tested with Python 2.7.3). The format of writeup.txt is:
  
  name
login

feature 1 title
feature 1 implementation description
feature 1 meshpro argument, with %s for parameter substitution

feature 1 mesh input 1
comma separated list of parameter substitutions

feature 1 mesh input 2
comma separated list of parameter substitutions

=====

more features
...

=====
  
  Using this script is optional; you can do things however you like, provided your submission makes properly on Linux. Note that if you're a Windows user and want to use make.py to produce a Linux Makefile for submission, you will need to run the script on Linux or edit it to produce the Linux Makefile when run on Windows.

• Is it OK if my implementation operates only on meshes containing triangles (i.e., decomposes N-sided polygons into triangles before processing)?
  No. For some of the operations (e.g., truncate), it is important that you handle N-sided faces with N>3 (otherwise the result will depend on the topology of the triangulation, and you won't be able to produce the cool shapes shown in class).

• Is my implementation required to handle arbitrary meshes containing polygons with concavities, self-intersections, non-coplanar vertices, etc.?
  No. It is OK if your code works only for examples with convex planar faces containing vertices in counter-clockwise order in both the input and output.