COS 526: Advanced
Computer Graphics
Fall 2008

Assignment 2: Laplacian Surface Editing (due Thurs October 23)

Update: For this assignment, you may want to have a look at the course lecture notes on Laplacian editing or the first few pages of the star report by Sorkine.

In this assignment you will be working with meshes. You may use either as reference or as a starting point the base code for the mesh processing assignment for COS 426. The base code also supplies an OpenGL-based mesh viewer, which you may use to view meshes and/or modify to add your own visualizations; or you may use one of any other viewer you find. Finally, at that link above you will also see sources of models in those formats, and there are also many at Aim@Shape.

You should be able to implement the required features as command-line based programs, as in the first assignment. However, as an optional variation you may choose to implement an interactive application for viewing the results or progress of your algorithm, or for controlling your programs.

As in all assignments, you may also use any other source code as reference material, and also as library source, provided it doesn't directly solve the assigned problems. When you use other people's sources, please reference it in your writeup.

Part 1: Warmup - Mesh Class and Normals

Create a mesh class that can read and write models files in OBJ and OFF formats. In addition to the simplified description of the OBJ format described there, the full version supports normals and texture coordinates. Your implementation need not handle arbitrary meshes -- support only for triangle meshes is sufficient. In addition, your mesh class will need to support an adjacency matrix which allows you to find neighboring vertices for a given vertex. (The easiest way to do this is to simply record a list of neighbors for every vertex.) It is fine to start with the code given for COS426 (linked above) which reads and writes file in several formats (but does not yet support normals, colors and textures in OBJ.)

Compute the normals at every vertex, using each of these methods:

Traditional method. The normal at each vertex is given by the weighted average of the normals of the neighboring faces, where the weights are given by the relative areas of the faces.
Umbrella operator. Compute the Laplacian at each vertex v as the difference between v and the centroid of its neighbors.
Cotangent version. Weight the computation of the "centroid" by the cotangent of the supporting angles (see course notes or related papers).

To your normal computations to work, implement the following operations:

Offset mesh: add a small offset to each vertex, in the direction of the surface normal.
Random noise: same as offset above, but multiplied by a random number.
Optional: Modify the viewer to draw little line segments that show the normal at every vertex.
Optional: Color the vertices of the mesh according to the curvature intensity found by the laplacian calculation. Either (1) write out the mesh with material colors per vertex (OBJ format) and use a viewer that displays colored models, or (2) modify the given viewer from COS426 using OpenGL to show colors per vertex. (Hint for option 2: see the program "rayview" used for the ray tracing assignment.)

Part 2: Constructing the Laplacian Matrix

Set up the system of equations (in matrix form) so that you can convert from a mesh in Cartesian representation into the corresponding Laplacian represention, and back. To test this part, convert a mesh back and forth (setting one vertex to a known position on the way back) and compare the "before" and "after" versions.

For this part of the assignment you will probably want to find a matrix library that can solve systems of equations (or invert matrices). Some possibilities are:

Part 3: Applications

This is the fun part. Implement these applications:

Flattening for parameterization. Remove two neighboring triangles from a mesh. Set the coordinates for the 4 vertices to be the corners of a unit square (2D). Now map the remaining vertices to the interior of the square by setting the Laplacian to zero and solving for x and y coordinates of the remaining vertices. Draw the result. Try it for a couple meshes.
Optional variation: now use these (x,y) coordinates as texture coordinates, and draw the orinal mesh textured by some texture (e.g. a checkerboard). This will require you to either write the file into OBJ or some format that allows texture coordinates, and find a viewer that draws textured meshes, and/or to modify your own viewer.
Membrane / soapy meshes. Solve the same system used for flattening (Laplacian = 0) except in 3D. This creates meshes that look like soap bubbles, but with the structure of the original mesh.
Editing.On the command line specify (1) an "edit" vertex to be moved, (2) the amount to move it, in the normal direction, and (3) the size of the region of interest (ROI = the size of the neighborhood in the graph that is allowed to move, measured by number of edges not actual distance). Use Dijkstra's algorithm to determine which vertices are within the ROI. Set up a system of equations that calculates new positions for the vertices in the ROI, that attempt to match the new position of the edit vertex, the Laplacian of the original mesh, and the original positions of a few rings of vertices near the boundary of the ROI, all in a least-squares sense.
Optional variation: create an interactive version that allows the user to pick and drag a vertex using the mouse, and that dynamically updates the ROI.

Part 4: (optional) Art Contest

In your writeup you may note one or two example images from your program that you wish to submit to our "art contest". They may be technically cool, or weird, or beautiful. We'll review the art contest images in class.