interests

computer graphics

mesh simplification

In computer graphics you often got polygonal models called meshes. These meshes may consist of thousands or millions of polygons (mostly triangles) to model a surface. Often this amount of data isn't desirable because it consumes a lot of disk space and slows down the rendering process dramatically. A (automatic) reduction of the model that produces a mesh very similar to the original but with much less polygons is needed. This reduction is called (beside other optimizations) mesh simplification.

ClusPartRed

abstract

In the past 10-20 years different approaches to simplify triangle meshes have been developed. Those algorithms can be divided in two groups. The first group of techniques reaches a good approximation of the mesh by trying to minimize the global error of the reduction. Unfortunally that requires the presence of the whole model in main memory. The maximum size of the mesh is limited by the available amount of RAM. The second group of techniques does not have this restriction. The input mesh is treated as a triangle stream, requiring only little main memory. The maximum model size is nearly unlimited. Unfortunally those algorithms do only local reduction error minimization resulting in less qualitative approximations than the techniques of the first group produce.

In this diploma thesis the extension of a well known representative of the first group - the QSlim algorithm by Michael Garland - will be presented with the intent to produce high quality approximations of nearly unlimited large triangle meshes independent from the available amount of main memory.

You can download the full text of "Externe Vereinfachung großer Polygongitter" (in german, gzipped pdf, 7135 KB) here.

For an example of an approximation of a small model have a look at the following picture:

Stanford bunny original 69,451 triangles (left) and simplified with ClusPartRed to 6,909 triangles (right). Click image to enlarge.

A short summary of the main idea of ClusPartRed including some visual results can be found in the foils (in german, gzipped pdf, 2649 KB) of my talk given at the weekly research seminar on the 19th of June 2002.

links to important mesh simplification researchers