Programming Project #1:
Surface Simplification

In this first project, you will be implementing a surface simplification system based on the Rossignac-Borrel algorithm discussed in class. The Rossignac-Borrel algorithm is an example of a vertex clustering algorithm. These methods follow a very simple framework:

1. Partition space into a set of cells.
2. Assign all vertices to the cells within which they fall.
3. Grade every vertex according to its importance.
4. Synthesize a representative vertex for each cluster.
5. Map all vertices within a single cell into their representative vertex.

What to Do

You should do the following:

• Create a program which will read an input model, simplify it via vertex clustering, and output an approximation. The resulting approximation should not contain any degenerate or duplicate triangles. File format details are provided below.
• Implement two different partitioning schemes: the uniform grids used by Rossignac & Borrel and another of your own choosing.
• Implement three different grading schemes. At least one should be different from those suggested by Rossignac & Borrel.
• Given these various partitioning and grading schemes, try to evaluate how well they work. You may use purely qualitative comparisons based on visual inspection of the models. Which choices perform the best? Which perform the worst? Explain why you think this is.

What to Turn In

You should turn in the following:

Please use the following process to hand in your project materials.

1. Package your files in a .tar or .zip archive.
2. Mail this archive to garland+p1@graphics.cs.uiuc.edu

File Format

Your program will read and write files in a restricted subset of the Wavefront OBJ file format. We'll call this the Simple Model Format (SMF). Each line of the file will contain either a vertex or a face definition. In general, an object file should have the following form:

v <x1> <y1> <z1>
v <x2> <y2> <z2>
.
.
.
v <xn> <yn> <zn>
f <u1> <v1> <w1>
f <u2> <v2> <w2>
.
.
.
f <um> <vm> <wm>

As a concrete example, the following defines a triangulated unit cube:

v 0 0 0
v 1 0 0
v 0 1 0
v 1 1 0
v 0 0 1
v 1 0 1
v 0 1 1
v 1 1 1
f 1 4 2
f 1 3 4
f 5 6 8
f 5 8 7
f 1 2 6
f 1 6 5
f 2 4 8
f 2 8 6
f 4 3 7
f 4 7 8
f 3 1 5
f 3 5 7

I am providing the following test models for you:

I have a simple application which will display SMF files and allow you to interact with them. It is available for the following platforms:

If you don't have a machine with a graphics accelerator, I suggest you try the Dell machines in 1265/1275 DCL. They are equipped with reasonably good graphics cards, and should be able to display the models used in the assignment without difficulty.

Collaboration and Code Sharing

The work you turn in should be the result of your own efforts. While you may discuss the assignment with others, I expect you to develop your own implementations. If you share ideas about implementation techniques (e.g., ideas for grading vertices) you should acknowledge those with whom you have shared these ideas.

You may use libraries or other code sources for non-essential parts of your implementation. For example, if you are programming in C++ and you have a library which implements a linked list class, feel free to use it. But you should implement the core functionality of the system yourself. Using a library which provides simplification facilities is not an acceptable means of completing the assignment.

Last modified: Wed Sep 22 13:26:12 CDT 1999