COS 426: Computer Graphics Spring 2013

Assignment 2: Mesh Processing

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.

Getting Started

Download the starter code code (cos426_assignment2.zip) and read README.txt.

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), while meshview provides a way for you to visualize and process meshes interactively.

The skeleton R3Mesh class 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 sample meshes that you can use to test your program. However, you are not limited to these files -- you should be able to find .off files on the web. For example, there is a zip file with 400 .off format files from the SHREC 2007 Watertight Benchmark here.

How the Program Works

The user interface for this assignment was kept as simple as possible, so you can concentrate on the mesh processing issues. The program 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

% meshpro -help

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

How to View a Mesh and Try Commands Interactively

Use meshview input.off to view a mesh file named input.off interactively. After a window pops up with the mesh, 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, B to toggle display of the bounding box, and F1 to dump a screenshot (in "imageN.jpg", for N=1,2,etc. increasing each time an image is dumped in the same session). You can display the position on a mesh (and the active face index) under the mouse cursor by moving the mouse over the mesh and pressing spacebar.

You can also use meshview to try out some of your mesh processing filters. 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.

You can use meshview meshfile -output_image imagefile.jpg -exit_immediately to create an image of a mesh you've created. A window will popup briefly, and then program will save an image of the mesh as seen from the default camera view. Please use this feature to make image files for your writeups (as is done by the top-level Makefile and NMakefile).

How to Make Your Writeup

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.

Feature List

The assignment is worth 20 points. The following is a list of features that you may implement (listed roughly from easiest to hardest within each group). 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) 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) 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) 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.
  • (3) 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
  • (4) 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.
  • (4) 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.
  • (4) 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.
  • (3) 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.
• 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) submitting one or more images or movies for the art contest (movies should be in .mpeg, .mov, .avi, or .gif format, animating the results of one or more filters with continuously varying parameters, e.g. the morph);
• (2) winning the art contest;
• (1) answering a nontrivial question on Piazza. Please copy the question and answer into your writeup if you do this.

It is possible to get more than 20 points. However, implementing more than 6 points worth of non-required features incurs diminishing returns: each successive point is worth 3/4 as much as the previous one. Thus, the adjusted extra credit score is computed according to the following formula:

Extra credit points cannot replace the required features (bold items). Your final score will be calculated by adding your score on the required features (up to 14 points) to your score on the optional features (up to 9 points, with diminishing returns past 6).

Notes / Hints

• Do the simplest features first!
• Look at the examples page.
• There are functions to manipulate 3D geometric primitives in R3.
• Save your art contest and output images in JPEG format (to save space).
• We have found that FFmpeg and MEncoder work well for converting a series of images to a video, or you can use ImageMagick to produce an animated GIF.
• The meshes we provide supply the vertices for each face in counterclockwise order.
• It is OK to handle only manifold meshes (ones where every edge has exactly two faces) comprised of convex, planar faces for all features except the ones aimed at topological fixup. Also, it is OK to triangulate the mesh before applying warp or filter operations. However, for the erosion and remeshing filters (e.g., truncate and bevel), 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). In these cases, it is OK if your code works only on inputs that produce convex planar faces in the output (e.g., use the platonic solids as inputs).

Submitting

This assignment is due Tuesday, March 12 at 11:59 PM. Please see these slides and the assignments page for general notes on submitting your assignments, including the late and collaboration policies.

Please submit a single .zip file named [your NetID]_cos426_assignment2.zip containing

• your writeup.html, containing links to all result images and a description of your implementation;
• your complete output/ and modified src/ directory trees. Please submit meshes in .off format and images in .jpg format. Remember to remove binaries and object files from the source tree (i.e., leaving only source code). To do this, run make clean or execute "Clean Solution" from the build menu in Visual Studio.

The Dropbox link to submit your assignment is here.

writeup.html should be an HTML document demonstrating the effects of the features you have implemented. For some features (e.g., Bezier), you can simply show the input and output of your program. However, for features that take an input parameter (e.g., Random Noise), you should provide a series of images showing at least three settings of the input parameter to demonstrate that your code is working properly. Also, for filters that can be run repeatedly (e.g., Smooth), you should show the results of multiple iterations (e.g., meshpro -smooth -smooth).

We remind you 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. 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.