Progressive meshes, as described in [Hoppe 1996] provide a means for simplifying meshes through a series of simple operations: edge collapses. The order in which the collapses occur provide control over the quality of the result. One effective solution for choosing an order uses quadric error metrics, as described in [Garland 1997].

In this project, you will implement a mesh data structure that supports an edge collapse operation, and implements a progressive mesh using a quadric error metric for deciding the order of edge collapses.

You have the option of using OpenGL in C++ (with GLUT and GLUI), or Java (using GL4Java). These are both set up in the cereal lab.

Requirements

• Mesh representation
  • Read in a 3D mesh in OFF format (described here).
    (The skeleton code does this already.)

  • Re-position and re-scale the mesh so it's centered at the origin, and fits into an x-y-z aligned bounding cube of width 1. (It should fit on the screen nicely after you do this.)

  • Implement a mesh data structure (vertices, edges, polygons) that works with non-manifold geometry that allows for fast access of the quantities necessary to implement the rest of this assignment. (You will be replacing the mesh data structure in the skeleton code now: that's only a placeholder.)

• Mesh simplification
  • Implement a edge-collapse operation for your mesh data structure. In the worst case, it should operate in time proportional to the number of edges that touch the edge to be collapsed. Implement the reverse of this operation as well: replacing a collapsed edge.

  • Compute the quadric error metric for a potential edge collapse.

  • Create a priority queue of edge collapses, and apply them in order of increasing error, until no further simplification is possible. Keep track of this order, so they can be applied/unapplied later.

• Progressive mesh viewer
  • Draw the simplified mesh on the screen (using OpenGL); there should be a control for adjusting the target resolution of the mesh displayed on the screen. (Use whatever control you like; GUI or keyboard.)

Optional extensions

Here are just some ideas; feel free to add your own!

• Instead of edge collapses, implement the more general vertex pair contraction (see section 3 of [Garland 1997]), and allow for non-adjacent vertices to be considered for a pair contraction, they they are spatially nearby (sec. 3.2)
• Draw a constant-error ellipsoid as in Figure 11 in [Garland 1997]
• Implement a slower/more space intensive approach that does not suffer from the approximate solution, as described just before section 5.1 in [Garland 1997], and compare.
• Load/save a sequence of edge collapses into a file
• Experiment with alternative metrics (even simple ones such as dihedral angle, area, edge length, etc....)
• Look over this related paper by Hoppe that describes efficient implementation of progressive meshes: [Hoppe 1998].
• Provide smooth transitions between levels-of-detail (geomorphs)
• Implement a view-dependent progressive mesh [Hoppe 1997] (hard!)

Skeleton code

There are two versions of skeleton code; C++ and Java. You are welcome to work from either. They are located in the directory:
   ~decarlo/523/proj1
on the cereal machines. See the cereal lab machines page about using that lab.

Note: the Java code that reads in OFF files can't read in floating-point numbers in exponential notation; you'll have to fix it yourself (well, the example meshes on cereal don't have any numbers in this format, so you could always skip it). Sorry! Java programmers should be used to things not quite working right. :) If you do fix it, please send me any improvements you make, so I can change the skeleton code.

• C++
  • Has a 3D vector class in the include file Vec.h
  • Uses GLUT and GLUI to build the user interface (here is PDF documentation for GLUI)
• Java
  • Uses part of Java3D for its 3D vector class (here is documentation)
  • Interfaces with OpenGL using GL4Java (here is documentation)

Models

Several 3D models in OFF format are on the cereal machines in:
   ~decarlo/523/off

There are many more in the database for the Princeton Shape Benchmark, right here.

Work policy

You're allowed to talk about the assignment with other students in the class, but you can't give away a key idea. Furthermore, all code you write must be your own. No using or viewing code from other sources/people/etc...

The exception is in replacing parts of the skeleton code that are clearly not part of the requirements (i.e. a class that implements 3D vectors, a user interface toolkit, etc...). When in doubt, ask.

Handin

Use the handin program on the cereal lab machines. See the description here.

The name for this assignment is cs523-proj1.

Hand in the following:

• All the code and a Linux makefile to compile your assignments
• A file called README.TXT that contains (1) a description of your assignment (i.e. what approaches you took, which extra parts you did, what bugs you have), (2) instructions on how to use it (if it's not obvious from the GUI)
• A screen dump of your program displaying the mesh bunny.off (available on the cereal machines), simplified to 500 faces. Generate this screen dump using:
        xwd | xwdtopnm > screenshot.ppm
  (you'll need to click in your program window after you type this; it takes a picture of the window you click in).
  Use the program "xview" to view the resulting images, to make sure it came out ok.