COS 426: Computer Graphics Spring 2019

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.

Collaboration

As with all assignments, you are strongly encouraged to collaborate with another student. The collaboration policy in COS 426 is relatively relaxed compared to what you might be used to. Please see the website for more details.

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 (or python -m http.server for Python V3.0 and up) 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' or the loading and interactions will be very slow.
• Image capture. Pressing the 'I' key 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'.
• Object download. Pressing the 'O' key 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 coursejs/guiConfig.js.

How to Program the Filters

To implement the mesh processing features below, you only need to edit the files js/mesh.js (for mesh traversal functions) and js/filters.js (for most of the rest).

Before starting to edit those files, we recommend you look through js/meshUtils.js, which contains an implementation of a mesh data structure and numerous functions for accessing and modifying a mesh's vertices, edges, and faces. 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.

three.js

This assignment uses three.js. It is okay to use the methods provided (e.g. Euler for rotation). However, it is encouraged to implement the filters without these three.js features (if you have time), by thinking through the geometry and performing the mathematical operations directly.

The provided mesh data structure makes use of many three.js classes. However, the most important one for this assignment is Vector3, which implements a vector in 3D space. It would be useful to familiarize yourself with its API so that you can leverage it in your own mesh processing operations.

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. Some features are required (indicated by each item), and the rest are optional. Refer to the examples web page for example output images as well as some implementation hints.

Note that each operation 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 propagate selection to the subdivided faces. (Just copy that attribute to the new faces.) For simplicity, you can assume all polygons are planar and convex during the implementation (but not necessarily triangular, of course). Assume faces share each edge with one (no more, no less) of its neighboring faces.

This assignment relies heavily on the "halfedge" mesh data structure. You can also read about it in Section 3.1 of the Botsch 2007 reading. (Links to these notes and readings are on the Syllabus page.)

• [REQUIRED] (0.5x3 = 1.5) Transformations

  Implement the following basic transformations in js/filters.js. Each transformation is worth 0.5 points.

  • Translation: This is already implemented as an example. Translates all selected vertices in (x,y,z).
  • Rotation: Applied on selected vertices. Rotate about the x, y and z axes (in that order). Hint: You may use three.js's Euler class to represent and apply rotations.
  • Scale: Applied on selected vertices. Scale distance of each vertex from the origin by a given factor.
• [REQUIRED] (0.25x8 = 2.0) Traversal

  Implement the mesh traversal operations in js/mesh.js. Each operation is worth 0.25 points.

  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 further below, and all rely on the half-edge data structure. One example function verticesOnFace has been provided for you as an example, and it returns a list of the vertices that are adjacent to the face (f) that is the argument to the function.

  • 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).
  • edgesOnVertex should return all edges pointing away from input vertex
  • facesOnVertex should return all faces which the input vertex is assigned to
  • verticesOnEdge should return the vertices incident to the input edge
  • facesOnEdge should return the faces which the input edge lies between
  • edgeBetweenVertices should return the edge incident to the input vertices
• Analysis (js/mesh.js)
  • [REQUIRED] (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.
  • [REQUIRED] (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.
  • [REQUIRED] (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 (js/filters.js)
  • [REQUIRED] (1.0) Twist: Applied on selected vertices. Rotate each vertex around the Y axis in an amount proportional to Y multiplied by the GUI slider value.
  • [REQUIRED] (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 (js/filters.js)
  • [REQUIRED] (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).
  • [REQUIRED] (1.5) Uniform Laplacian Smoothing: Smooth the mesh by moving every vertex towards the uniform average of its immediate neighbors. The process should repeat itself iterations times. In each iteration, move the vertex along the vector that connect it to its average, scaled according to delta. You can, but don't have to normalize the weights to sum to 1, since this can be controlled through the delta variable. You may want to scale the mesh after every iteration so that the radius of the bounding box is not effected by the process (espcially if the weights are not normalized). Note that large deltas will cause instabilities, yielding extreme artifacts on the mesh. The smaller the delta, the better the smoothing, but also more iterations are required.
  • [REQUIRED] (1.0) Uniform Sharpening: Applied on selected vertices. Accentuate details in the mesh by moving every vertex along the opposite of the vector described in Uniform Smooth. The parameters used also behave the same.
  • (1.5) Curvature-flow Laplacian Smoothing: Smooth the mesh by moving every vertex towards the weighted average of itself and its immediate neighbors, using the cotangent weights as explained in the meshes lecture (and will be repeated in the 3/1 precept). This is activated by ticking the curvature_flow checkbox. The iteration and delta parameters should have the same behavior. Note that this method works only on triangles, so be sure to triangulate the mesh first, if it is not already.
  • (1.0) Scale-Dependent Smoothing: Make the smoothing process agnostic to tessellation resolution (no matter what type of smoothing is used). This is done by scaling the offset vector differently for every vertex. Calculate the area of all adjacent faces to every vertex (A_v) and the average of that size across all vertices (A). Scale every offset vector by A/A_v.
  • (3.0) Implicit Smoothing: Perform impicit smoothing, as described by Desbrun et al. [1999]. Given the Laplacian L, scaled according to the pervious configuration choices, and the matrix of the coordinates of all vertices V (of size n X 3), explicit smoothing performs the iteration V_new = V + L*V. The required implicit smoothing operation computes the inverse problem. i.e. it looks for a vertex configuration that when sharpened, will yield the current one. in other words, it searches for V_new such that V = V_new - L*V_new. This technique eliminates the risk of causing instabilities, and hence allows for arbitrarily large deltas, at the cost of performing less iterations due to computation time. Finding V_new requires solving a linear system. We recommend using the math.lup algorithm found in math.js, which is already linked to the framework.
  • (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 (js/filters.js)

  (Hint: see js/meshUtils.js for useful helper functions for modifying mesh topologies.)

  • [REQUIRED] (0.5) Triangulate: Applied on selected faces. Replace each face with a set of triangles. Hint: an easy way to do this is repeatedly call the splitFaceMakeEdge function in meshUtils.js.
  • [REQUIRED] (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.
  • (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 (js/filters.js)
  • [REQUIRED] (1.5) 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.
  • [REQUIRED] (1.5) 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.5) 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.5) 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. The value of non-required features incurs diminishing returns after the first 5 points. For sums of non-required features (n>6), each point over 5 will accrue a value of 3/4 the previous point.
  
  Your final score is based on the following factors:

  • r: your score on the required features (up to R = 16 points)
  • n: your score on the non-required features (value diminishes when n > N = 4) .
  • a: your participation in the art contest (1 point for participating, 1.5 for being selected for gallery, 2 for winning). You can make use of customFilter()
  • d: diminishing return factor (d = 4/5 in this assignment)
  Final score will be rounded to the nearest 0.5. The formula in javascript is:
  Math.round((Math.min(R, r) + Math.min(N, n) + d * (1 - Math.pow(d, Math.max(n - N, 0))) / (1 - d) + a) * 2.0) / 2.0
  
  Score Calculator: Compute!

  my score on the required features
  my score on the non-required features
  my score on the art contest
  total score

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 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 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.

• Smoothing operations take a while, requiring thousands of iterations for the explicit version, and dozens of seconds for the implicit solution. Is that OK?
  Yes. These operations can take a while, but can also be very fast when properly implemented. You do not need to optimize your runtime, as long as it is not completely unbearable.