# 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

• PS2.zip: Mesh data and an basic template code.

## Instructions

The zip package includes the following 3 directories:
• data: This directory contains several files, which represent different triangle meshes on which you can test your implementation. Each file has the extension .off, which is one of the standard file formats for representing triangle mesh data. Please take a look at one of the files to see the structure of the data. The format is given as follows: the first line contains the header OFF The next line contains nv nf 0, which stand for, respectively, number of vertices, number of faces, and number of quads (0 in our case). After this line, you will see nv lines which represent the X,Y,Z coordinates of the points. After that, there are nf lines that represent the indices of the vertices in the triangles as follows: 3 v1 v2 v3 . For example a line 3 10 0 2, says that there is a triangle with vertices 10, 0 and 2, where the numbering of the vertices is given according to the first list (starting with 0).
• external This directory contains two files that will be useful in handling the triangle meshes. The first: read_off_shape allows you to read the triangle mesh from an 'off' file, into a MATLAB data-structure. The second: plot_mesh allows you to visualize a triangle mesh using MATLAB's internal trimesh command.
• code . You should use this directory to store and organize your code. By default it only contains one file: process_mesh.m which will help you to get started with your implementation.

## (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.