PS 2 - Triangle Mesh Processing

(Maks Ovsjanikov)

The goal of this practical session is to play with various methods for rigid shape registration (alignment) that we discussed during the first lecture.

        Examples of shapes before and after simplification (decimation)

0. Getting started

Files to download today


The zip package includes the following 3 directories:

(Simple) Exercise PART I: Mesh Statistics

Start by extending the given file process_mesh.m to calculate some basic statistics about the mesh that you are given. In particular, as you can see in the code, you are expected to compute the vector of degrees of all the vertices (i.e., given a mesh with nv vertices, compute a vector of size nv x 1 whose i^th element represents the degree of vertex i. The compute the Euler characteristic of the mesh and verify that all of the relations that we saw during the lecture hold. In particular, for a closed mesh without boundary we expect 2E=3F. The Euler characteristic for a torus should be 0 and for a shape with a spherical topology (e.g. a bunny) to be 2. Moreover the average degree across all vertices should be close to 6 (exactly 6 for a torus).

(BONUS) Exercise PART II: Mesh Simplification

Implement any of the mesh simplification algorithms that we discussed during the lecture. The simplest two possibilities are based on edge collapse and vertex removal. Please see the following paper, which discusses various simplification strategies. Note that you are not expected to provide an efficient implementation (which is, in general, very difficult to do with pure MATLAB code), or even a very accurate simplification method. Instead, try to implement a single step in simplification by either removing a vertex or performing an edge-collapse, while maintaining the right topology of the surface. To test your simplification step, please feel free to chose any criterion to prioritise which vertices to remove or which edges to collapse. For example, the simplest geometric criterion for edges is the length: simply collapse shortest edges first. When performing the collapse, you can remove one of the two vertices (pick arbitrarily) and then make sure that the triangulation remains valid. Validate your code by computing the Euler characteristic at each step.