Spring 2017

Assignment 2: Modeling

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 to 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 the 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 choose a model and change the display settings of the model -- try it. Below that is a collection of controls. Click on the 'Transformations' folder to open it, and choose the top item -- Translation. Try adjusting the x-translation by pulling that slider around. It should move the model on the x-axis shown in red. Try adjusting adding 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 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 or vertex of the cube it becomes 'selected'. If you click it again, it becomes 'deselected'. By clicking on multiple items, you can select them all at once. The 'Delete' button in the History GUI will delete that selection operation. Click the top face of the cube and then try translating it in X.
• Display. This folder on the side should be pretty self-explanatory. Try it out. When loading high-polygon models (such as the cheetah, bunny, armadillo, ...) make sure to unselected 'show labels' and 'show halfedges' or the loading and interactions will be very slow.
• 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 by adding the file extension '.png'.
• Pressing the 'O' key. This downloads an 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 guiConfig.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 each operataion mentions whether it should be applied on the selected items (if there are any) or to the whole mesh (if no items are selected or if there is no mention or what it should be applied to). See the example implementation for translation and the beginning of each method for how to do this. 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 briefly near the end of the Polygonal Meshes lecture on 2/23, and extensively during precept 3/1. You can also read about it in Section 3.1 of the Botsch 2007 reading. (Links to these notes and readings are on the Lecture notes page.)

• Transformations
  • (0.0) Translation: This is already implemented as an example. Translates all selected vertices in (x,y,z).
  • (1.0) Rotation: Applied on selected vertices. Rotate about the x, y and z axes (in that order).
  • (0.5) Scale: Applied on selected vertices. 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, and rely on the half-edge data structure. 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.
• Warps
  • (0.5) Twist: Applied on selected vertices. Rotate each vertex around the Y axis in an amount proportional to Y multiplied by the GUI slider value.
  • (1.0) Inflate: Applied on selected vertices. 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: Applied on selected vertices. 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: Applied on selected vertices. 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: Applied on selected vertices. 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().
  • (2.0) Bilateral Smooth: Smooth the mesh using a bilateral filter as in [Jones et al, Siggraph 2003].
  • (2.0) Curvature: Compute an estimate of the per-vertex 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 shown by selecting vert colors in the Display Settings.
• Topology
  • (0.5) Triangulate: Applied on selected faces. Replace each face with a set of triangles. Hint: the easy way to do this is repeatedly call the splitFaceMakeEdge function in mesh.js.
  • (2.0) Truncate: Applied on selected vertices. 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: Applied on selected faces. 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: Applied on selected vertices. For every edge, create a new face whose vertices are t [0-1] of the way towards the face centroid. This requires first truncating all vertices by t, creating new vertices t [0-1] of the way towards each face centroid, 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 Topology: Applied on selected faces. 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: Applied on selected faces. First perform triangle subdivision described above. Next, update the positions of all vertices according to the Loop subdivision weights.
  • (1.0) Quad Topology: Applied on selected faces. 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 submit to the art gallery (which yields one point). 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 score on the non-required features and submitting to the art gallery, calculated as follows.

Beyond 4 points, the value of each additional non-required feature incurs diminishing returns, counting 2/3 as much as the previous point. (For example, if you implement 6 points of non-required features, this will count as 4 + 2/3 + 4/9 = 5.1 points.)

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 to edit those files, 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

The Dropbox link to submit your assignment is 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 most features that take an input parameter (e.g., rotation, scale), you should provide a series of images showing at least two settings of the input parameters to demonstrate that your code is working properly. (No need to show inputs for the default models in the obj folder.)

You should start from the the example writeup.html provided. At the top of that file is a list of features that you might implement with links to the section where you can describe them. Please remove any features that you do not implement, but otherwise leave this header section intact. 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 collaboration policy posted on the main assignments page.

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.