COS 526 - Advanced Computer Graphics

Fall 2003

Programming Assignment 1: Progressive Meshes

Overview

For this assignment, you will implement a mesh simplification system based on the techniques described by Hoppe 96 and Garland 97. Your program must be able to perform a series of simplifications based on the edge collapse operation, then reconstruct a mesh at any desired level of detail via vertex splits.

I. Mesh Decimation (50%)

1. Begin with code to read in a 3D mesh in ".off" format (documentation) and display it in an OpenGL viewer. If you already have code to do something similar, feel free to adapt and use it. Otherwise, you should start with one of the following pieces of support code:
   • The support code from CS 426, Spring 2003, Assignment 3. This reads models in .ray format instead of .off, but it should be very easy to adapt the code.
   • The support code from CS 526, Fall 2002, Assignment 1. Contains C++ classes for things like 2D/3D geometry, vectors, basic Open GL graphics, etc.
   • The Princeton Shape Benchmark utility code. This contains a simpler, easier-to-understand viewer that has fewer features but might be easier to adapt. It reads .off files directly.
2. Write code to build up a mesh connectivity data structure of your choice. Use it to write an "Edge Collapse" function. A single edge collapse should take O(1) time (or, at worst, O(d), where d is the maximum degree of the vertices being collapsed). Try to make your data structure robust for non-manifolds.
3. Write code to compute the quadric error metric for a candidate edge collapse. Use it to create a priority queue of edge collapses, and apply them in order until the mesh can't be simplified any more. The Garland 97 paper and Diego Nehab's notes on quadric error metrics may be useful.
4. Adapt your code to place the vertex resulting from an edge collapse at the location that minimizes the error quadric.

II. Progressive Meshes (30%)

1. Write out the edge collapses to a file, in a format of your choosing.
2. Adapt your viewer to read in this file and perform vertex splits in the correct order. Include an interactive control (doesn't have to be anything fancy - keyboard control is fine) over the target resolution of the displayed mesh. The Hoppe 96 paper may be a useful reference.

III. Further extensions (20%)

Implement one of the following (additional options may be implemented for additional credit).

1. Implement a visualization of the error quadrics as ellipsoids.
2. Implement geomorphs for smooth transitions between levels of detail.
3. Augment your system to perform "pair collapses" in addition to simple edge collapses. Experiment with models with many separate components and show that your program joins them into one over the course of simplification.
4. Experiment with different error metrics. For example, implement a system that tries to preserve high-frequency detail at the expense of greater low-frequency deformation in areas with less detail.
5. Implement a view-dependent progressive mesh viewer based on Hoppe 97. (Extra credit for this one!)

Models

Submitting

Please submit your source code together with a writeup (as plain text or HTML) that contains a description of the options you implemented as well as results. At a minimum, you should include a screenshot of the bunny model (from here) simplified to 500 faces.

Please put your code and writeup in a .zip or .tar.gz file and attach it in an email to smr@cs.princeton.edu, with "CS526" in the subject line. Please see the general notes on submitting your assignments, as well as the late policy and the collaboration policy.