Monday, March 23, 2009

On the subtle art of mesh cleaning


Most mesh processing algorithms usually require nice two-manifold, watertight, intersection free, well-shaped, clean meshes. Obviously in the real world this does not happen with a great frequency (apart in scientific papers). Common meshes are the most horrible mix of all the possible almost catastrophic degenerate situations.

MeshLab can help the tedious tasks of cleaning meshes in a variety of ways. Let's start with some simple examples involving vertices.
  1. Unreferenced Vertices. Very common issue. Your mesh has some vertices that are not referenced by any triangle. A variety of cause can create these situations (algorithms deleting faces in a non careful way can create them). This situation can be more dangerous than it seems, because they can bring in trash uninitialized data in algorithms that initialize vertex data performing face-based traversal (e.g. normals computations...).
    An easy way to look at the presence of these vertices is simply switching to a point based rendering mode (evenually turning the lighting off, because, by default, unreferenced vertices have null normals). As always happens, sometime this situation is not an error but could be a feature (think to point clouds).
  2. Duplicated vertices. Adjacent triangles does not share the vertices with the same coordinates. Sometimes it is an issue that come directly from some file formats (STL for example store triangles duplicating each vertex). This situation is easy to be detected:
    1. Smooth shading is the same of flat shading: the duplicated vertices do not allow the averagin of normals between adjacent faces that is necessary for smooth shading.
    2. Poor man version of Euler Characteristic does not work: instead of having:
      [face number] ~ 2 * [vertex number]
      you have:
      [face number] ~ 1/3 * [vertex number]
    Again this could be a feature and not an error. Sometimes, duplicating vertices can be used to impose sharp angles when you do not have simple techniques to store multiple normals for the same vertex.
The above cases can be cured, if necessary, by invoking in MeshLab the two filters, Remove Unreferenced Vertices and Remove Duplicated Vertices in the menu named: Filters->Cleaning and Repairing.