|
COS 526 - Advanced Computer Graphics
|
Fall 2004
|
Programming Assignment 1: Progressive Meshes
Due Thursday, Oct. 7
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.
0. Starter code
Download the starter code
and get it to compile. You'll need to install the GLUT library, as well.
Now, download a few sample meshes
(in ".off" format, documented
here)
and start the provided mesh viewer on one of them. The model file should be
provided on the command line or, under some systems, you might be able to
drag 'n drop the model file on the executable.
The mouse/key functions are as follows:
- Left mouse button: rotate
- Middle mouse button (or left and right held together): translate
- Right mouse button: zoom
- Space bar: reset to the initial view
- 'e' key: toggle drawing mesh edges
- 'q' or 'Esc' key: quit
If you have existing mesh viewing code, feel free to use that instead.
1. Mesh Decimation (60%)
- 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.
When you collapse an edge, be sure to remove any degenerate faces that are
produced. For example, in the example at right (available as
testpatch.off), collapsing
the edge between v0 and v1 will cause faces X and Y
to be degenerate (i.e., have two vertices that are really the same point).
In addition, you should remove any "fins" (pairs of mirror-image polygons)
produced by the collapse. In this example, you should remove faces
Z and W.
- 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.
- Adapt your code to place the vertex resulting from an edge collapse at
the location that minimizes the error quadric.
2. Progressive Meshes (20%)
- Store data about the edge collapses in a data structure of your choice.
The Hoppe 96 paper may be a useful reference.
- Adapt the viewer to include an interactive control over the resolution
of the displayed mesh. This doesn't have to be fancy - a simple keyboard
control where '+' and '-' increase/decrease polygon count by 20% is fine.
3. Bells 'n whistles (10%)
Implement one of the following (additional options may be implemented for
additional credit).
- Write out the edge collapses to a file, in a format of your choosing,
then adapt your viewer to read just the base mesh and edge collapses,
instead of the original mesh.
- Implement a visualization of the error quadrics as ellipsoids (hint:
glutSolidSphere draws a sphere - how should you scale it to make
it an ellipsoid of the right shape?)
- Implement geomorphs for smooth transitions between levels of detail.
- 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.
- 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.
- Implement a view-dependent progressive mesh viewer based on
Hoppe 97. (Extra credit for this one!)
4. Writeup and analysis (10%)
Please submit your source code together with a writeup (as plain text,
HTML, or PDF) that contains a description of the design decisions you made,
options you implemented, and results. At a minimum, you should include
a screenshot of the bunny model
(from here) decimated to 500 faces,
together with information about how long it took to simplify.
Models
There is a large database
of models in .off format that you can work with. For starters, though,
there is a smaller collection of models here.
Hints
- The choice of mesh data structure is critical - think through your
algorithms before settling on a final choice. An indexed face set plus
a vertex-to-face adjacency list can lead to relatively simple, though
perhaps slightly inefficient, algorithms, while winged-edge or half-edge,
despite their greater efficiency, can lead to complex algorithms
with lots of special cases, especially since you need to reject edge collapses
that would result in non-manifold topology.
- If you use C++, take advantage of the STL container classes - depending
on your needs, using a vector, list, set,
priority_queue, or pair might make your life a bit easier.
Keep in mind the cost of performing each operation on each data structure
(e.g., insert and erase are O(n) for a
vector, but push_back and pop_back are amortized
constant time).
Submitting
Please make your writeup and code accessible via the web, and send the URL
to smr@princeton.edu with "COS526" in the subject line. Please
see the general notes on submitting
your assignments, as well as the
late policy and the
collaboration policy.
Last update
28-Nov-2018 11:36:09
smr at princeton edu