CS 101.3

Spring 2002

Homework 1.5 – Mesh Simplification using quadric error metrics

This homework is the second half of the mesh simplification homework. You will need to alter your existing code to do simplification using quadric error metrics instead of edge length. You will need to still apply the consistency checks that you wrote last week in order to make sure that you have nice manifold output. There is a new base program available at:

http://www.cs.caltech.edu/courses/cs101.3/cs101_files/homework/hw1.5/QtViewStart1.5.tar.gz

Note that there is a new header file QuadricT.hh and there are added functions to the Decimator class and changes to the mesh traits in MyMesh.hh.

Please integrate these changes into your existing code (i.e., copy in the QuadricT.hh file and add the other changes to your existing files). I will also provide a version of the working function is_collapse_legal midway through next week, when all your programs are completed, but for now, this updated base program should give you a clear starting point to start working on this week’s assignment.

Same as last week, unzip the program and compile it with the command: acgmake.

Most of your changes will go into Deci.cc (the decimator class) – look for the comment “INSERT CODE”. However, you will also have to complete the QuadricT.hh file (again look for the INSERT CODE comment).

This homework consists of three sections:

1) Compute edge collapse priority based on quadrics.

2) Apply edge collapses using a priority queue based on vertices. Reposition the new vertex to the edge endpoint with the smallest cost or the midpoint of the edge.

3) Improve the user interface of the application using Qt
-Add some method to do sequential simplification of the mesh (ie a slider).
(You will also need to have this GUI event trigger the appropriate functions in your program).

Each of these requirements (1-3) is worth 33.3 points each (100 total). Your finished program will be tested on a variety of input (which will be available for you to test your program) and results will be compared against baseline results.

Please note that the QuadricT.hh file stores and computes quadrics in the way presented in the paper “Surface Simplification Using Quadric Error Metics” by Garland and Heckbert. It uses a 4x4 matrix to store the quadric – this method of storing the quadric is slightly different than the tuple representation given in class, but is equivalent. Please read the paper for details and consult with the TA if you have any questions.

For extra credit you can do either:

1) Apply vertex split in order to unsimplify the mesh (again you are welcome to explore using the vertex_split function provided in OpenMesh). (Worth 10 extra points)

2) Consider optimizing the position of the new vertex after an edge collapse as discussed in class and the Garland and Heckbert paper. (Worth 20 extra points)

Again you are welcome to use the existing functions provided in the OpenMesh datastructure (collapse & vertex split).