COS 426: Computer Graphics Spring 2015

Overview

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

Getting Started

As in the previous assignment, the mesh processing program has two modes: (1) an interactive mode where you can enable/disable various filters, adjust parameters to these filters, and see the result right away; and (2) a batch mode where all the filters and parameters are fixed. Each version runs in a web page, and for the batch mode the filters and parameters are specified in the URL. This section of the instructions are analogous those of the previous assignment, so by now this should be very familiar.

To get started, download this zip file and unzip it on your computer. Change to the subdirectory cos426-assign2 and run the command python -m SimpleHTTPServer which will launch a web server on your computer, rooted at this directory. (See previous assignment description about why we do this instead of opening the files directly.)

Once you have started the local web server, direct your browser to http://localhost:8000. You should see the web page for Assignment 2 showing a cube. Click and drag near the cube (not on it) and you will see that this is a 3D viewer. In the upper right corner is a GUI, and the top two controls let you change the size of the rending window and choose a picture -- try it. Below that is a collection of controls. Click on the TRANSFORMATIONS folder to open it, and choose the top item -- Translate X. Try adjusting the x-translation by pulling that slider around. It should move the model on the x-axis shown in orange. Try adjusting a rotation slider, and you should see a warning that that feature is not implemented yet. You will be implementing that feature as part of the assignment. Click ok on the warning box.

Using your favorite text/code editor, edit the file ls js/student.js in that directory and fill in your name and NetID. Reload the web page in your browser, and now your information should appear above the image.

New GUI features in this Assignment

This GUI has several new features:

• Selection. Notice if you click on a face of the cube it becomes 'selected' and if you click it again it becomes 'deselected' and that you can select multiple faces at once. The Deselect All button in the GUI deselects all faces. Click the top face of the cube and try translating it in X. Now try selecting another face. Notice that once you start editing selected faces you cannot change the selection. Reload the page and try it again, but this time selecting several faces.
• Apply. This button accepts all the current GUI settings (transformations, editing, etc.) and makes the resulting mesh 'current'. It also resets the GUI. For example, try translating one or more faces and clicking Apply. Now the edited mesh is the starting point for new operations.
• Back to Last Apply. This is like an undo button. If you have changed any of the GUI settings from their defaults, it will go back to the defaults. Otherwise, it will go back to the state at the time of the previous Apply. This is essentially a crude "undo stack".
• DISPLAY OPTIONS. This folder at the bottom should be pretty self-explanatory. Try it out.
• Pressing the 'I' key. This captures an image of the current rendering. (In different browsers you may get slightly different behavior. In Chrome it should force a download while in some other browsers it may open in a different window or tab.) It should be a PNG file; you may need to rename it adding the file extension '.png'.
• Pressing the 'O' key. This downloads and OBJ file representing the current 3D model so you can get back to it later. Later you could move it in the 'obj' directory calling it 'custom.obj' (overwriting the one in there already) and then load it by selecting that menu item in the GUI. Some browsers may cache these obj files so you may need to clear your browser cache to get the new object. Or you can add it under a new name by editing the list of obj files in gui.js.

Implementing the Mesh Processing Filters

The assignment is worth 20 points. The following is a list of features that you may implement. The number in front of the feature corresponds to how many points the feature is worth for the full implementation. Partial or partially-correct solutions will receive partial credit. The features in bold face are required. The other ones are optional. Refer to the examples web page for example output images as well as some implementation hints.

Note that the bold operations in the Transformations and Topology sections as well as triangle and quad subdivision should either apply to selected faces (if there are any) or to the whole mesh (if no faces are selected). These operations should apply to all vertices adjacent to a selected face. See the example implementation for translation for how to do this. Operations in the other sections should ignore selection and modify the entire mesh. Also, the triangulation and subdivision operations should propagage selection to the subdivided faces. (Just copy that attribute to the new faces.)

This assignment relies heavily on the "halfedge" mesh data structure, which was discussed near the end of the Polygonal Meshes lecture on 2/24, and extensively during precept 2/25. You can also read about it in Section 3.1 of the Botsch 2007 reading. Links to these notes and readings on the Syllabus.

• Transformations
  • (0.0) Translation: This is already implemented as an example. Translates all vertices in (x,y,z).
  • (1.0) Rotation: Rotate about the x, y and z axes (in that order).
  • (0.5) Scale: Scale distance of each vertex from the origin by a given factor.
• Analysis
  • (1.5) Traversal: Implement the mesh traversal operations in meshStudent.js. These operations list vertices, edges or faces adjacent to a given vertex or a face. They are used by many of the operations that you will implement below. One example function verticesOnFace provided for you as an example, and it returns the vertices that are adjacent to the face (f) that is the argument to the function. Likewise:
    • edgesOnFace should return an array of edges that are adjacent to the face argument (f).
    • facesOnFace should return an array of faces that are adjacent to the face argument (f).
    • verticesOnVertex should return an array of vertices that are adjacent to the vertex argument (v).
    • ...etc.
  • (0.5) Face area: Compute the areas of faces in the mesh. The easy way to do this is to make a function to compute the area of a triangle. For each face, create triangles that cover the face, and sum the areas of the triangles. Store the resulting area in the "area" property of the faces.
  • (0.5) Per-vertex normals: Compute the surface normal at a vertex as a weighted average of the normals for the adjacent faces, where the weights are proportional to the areas of the faces (but the weights must sum to 1.0). Store the resulting normal in the "normal" property of the vertex. You can display the computed normals by using the appropriate checkbox in the Gui.
  • (0.5) Average edge lengths: Compute the average length of edges attached to a vertex. You can visualize this by scaling the normal stored at each vertex by this value, and displaying the normals.
  • (2.0) 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" property of the vertex. In addition, set the color of the vertex to visualize the curvature values. The color mapping can be done however you like but if you want some ideas check out "rainbow color map" or think about how to map curvature values to hue (from HSL or HSV). This feature is triggered by a checkbox in the FILTERS folder of the GUI.
• Warps
  • (0.5) Twist around Y: Rotate each vertex around the Y axis in an amount proportional to Y multiplied by the GUI slider value.
  • (1.0) Inflate: Move every vertex along its normal direction. The Gui parameter "value" should be multiplied by the average length of the edges attached to the vertex to determine the displacement distance. Note that "value" can be negative, which means that the vertex should move in the direction opposite to the normal vector.
  • (1.0) Wacky: Warp a mesh using a non-linear mapping of your choice (examples are sine, bulge, swirl).
• Filters
  • (1.0) Noise: Offset each vertex in the direction of its normal scaled by a random value between 1 and -1 multiplied by two other factors: the average edge lengths at that vertex and the slider value (between 0 and 1).
  • (1.5) 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 1).
  • (1.0) 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 as described for the Smooth filter above). This filter moves vertices by the vector exactly opposite from the one used for Smooth().
  • (1.0) Bilateral smooth: Smooth the mesh using a bilateral filter as in [Jones et al, Siggraph 2003].
• Topology
  • (0.5) Triangulate: Replace each face with a set of triangles. Hint: the easy way to do this is repeatedly call the splitFace function in mesh.js.
  • (2.0) 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.
  • (2.0) Extrude: For each face, duplicate its vertices and stitch the face to the mesh such that each edge of the original becomes a quad. Push the face in the direction of its normal scaled by the GUI parameter. See the examples page for how it should look.
  • (2.0) 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.
  • (1.0) Split long edges: Iteratively split the longest edge in the mesh until a number of splits have occurred that is a fraction of the number of edges in the mesh set by the GUI parameter. Note that every edge split produces a new vertex at the edge midpoint and replaces the two adjacent faces with four.
• Subdivision Surfaces
  • (1.0) Triangle subdivision: First ensure the mesh is a triangle mesh by calling the triangulate code implemented above. Next subdivide each triangle into four in the pattern used for Loop subdivision. This method introduces midpoints on all edges, but does not move any existing geometry.
  • (1.0) Loop subdivision: First perform triangle subdivision described above. Next, update the positions of all vertices according to the Loop subdivision weights.
  • (1.0) Quad 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 midpoint of every edge. This method does not alter the geometry of the shape, only the topology.
  • (1.0) Catmull-Clark subdivision: First perform quad subdivision described above. Next update the positions of all vertices according to the Catmull-Clark subdivision weights.

  The translation filter is already implemented for you as an example. By implementing all the required features (in bold), you get 16 points. Full credit for this assignment is 20 points, so to complement the required features you may choose from the optional features listed above and participate in the art contest (which yields one point for participation and two for winning). 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 16 points)
  • your participation in the art contest (up to 2 points)
  • your score on the non-required features, calculated as follows.

  The value of non-required features incurs diminishing returns after the first 4 points. For sums of non-required features (n>4), each point over 4 will accrue a value of 2/3 the previous point.

How to Program the Filters

To implement the features listed above, you only need to edit the files js/meshStudent.js (for mesh traversal functions) and js/filters.js (for most of the rest). Before starting on that, we recommend you take a quick look at the file js/mesh.js because it has some important helper code relating to vertices, edges, and meshes. You are welcome to look at any of the other files, but it should not be necessary and some of them have some pretty byzantine javascript magic.

Submitting

You should submit your solution via CS dropbox here. The submitted zip file should preserve the directory structure of the skeleton code we provided in the zip file above.

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., sharpen), you can simply show the input and output of your program. (No need to show inputs for the default images in the images folder.) However, for features that take an input parameter (e.g., blur), you should provide a series of images showing at least two settings of the input parameter to demonstrate that your code is working properly.

You should start from the the example writeup.html provided. At the top of that file are a list of features that you might implement, linking to the section where you talk about them. Please remove any features that you do not implement, but otherwise leave this header section in tact. When you include an image, also include a link to the batch.html command that creates that image, as in the last assignment. To save space, please submit images in png format.

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. We have mostly tried to conform to the idiomatic JS style conventions.

Hints

As in the last assignment:

• Do the simplest operations first! Note, however, there are some dependencies, for example you need to handle mesh traversal before the other analysis and filtering operations.
• Look at the example page.
• Post a message to Piazza if you have questions.
• Take note of the late policy and the collaboration policy.

FAQ

Here are some answers to frequently asked questions. Check back here occasionally, as we may add FAQs to this list:

• 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 manifold, closed meshes (e.g. no holes) with convex, planar faces containing vertices in counter-clockwise order.