COS 526: Advanced
General | Syllabus | Assignments
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
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:
To your normal computations to work, implement the following
- 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
- 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
- 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
- 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
- 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.