OpenMesh, decimation, Lindstrom-Turk

Question

In my application I'm working with a lot of triangle meshes, and sometime I need to reduce number of triangles in them (colapse some edges). For mesh handling I use openmesh (openmesh.org) since it's modern (C++), but mainly because it does not drag enormous amount of dependencies with it (depends only on c++ std and any modern compiller can handle it (I need to be crossplatform Linux/Windows/Mac OSX)).

Now I need to reduce (decimate in openmesh terminology) some meshes, but I need to preserve borders. (the meshes in question were originaly grid (512x512), but at the center of them some convave elements were extruded/added, it's crucial that after reduction the outer edges of grid still form rectangle)

I dont see any way to decimate them in openmesh and preserve volume/outline, all the OpenMesh::Decimater::Mod* decimation modules use quadric as their base.

In GTS (GNU Triangulated Surface Library) there is implemented Lindstrom-Turk reduction with is ideal for my needs (I'v done some dirty wraper to test if it is what I want) and it works, but with GTS there are problems - it's not multithread save (I'm reducing many meshes over multiple threads) and with GTS it's not possible since it uses global variables inside library to disable/enable some stuff while reducing mesh :/) (and it's also drag whole glib as it's dependencies)

There is also CGAL and it also has Lindstrom-Turk implemented, but it's drag whole boost and other dependencies with itself :/

Is there any decimator module for openmesh that does decimation with border/volume preservation ? (I'v searched, but found none :/)

Answer 1

As far as I understand, by "mesh borders" you mean mesh edges that form only a single mesh face (like outer edges of a 512x512 grid in your example), as opposed to a more common case when each mesh edge is shared between 2 or more mesh faces.

In OpenMesh there is actually a pretty easy way of telling the OpenMesh::Decimater module to preserve these edges as-is. Even better, it is not dependent on a type of the decimation module you actually use. The actual mesh data structure (i.e. OpenMesh::TriMesh_ArrayKernelT<>) has a feature called "vertex locking". It is essentially a way of telling the OpenMesh not to touch a particular set of vertices no matter what during decimation.

Here is a code snippet straight out from the official documentation, altered a bit for C++11:

using Mesh = OpenMesh::TriMesh_ArrayKernelT<>;

void protectMeshBoundariesFromDecimation(Mesh& mesh) {
   mesh.request_vertex_status();

   for (const auto& halfEdgeHandle : mesh.halfedges()) {
      if (mesh.is_boundary(halfEdgeHandle) ) {
         mesh.status(mesh.to_vertex_handle(halfEdgeHandle)).set_locked(true);
         mesh.status(mesh.from_vertex_handle(halfEdgeHandle)).set_locked(true);
      }
   }
}

If you want to read full docs on that matter and the link above does not work anymore, in the docs contents tree go to OpenMesh -> OpenMesh Documentation -> OpenMesh Tools Documentation -> Mesh Decimation Framework.

Essentially this loops over all half-edges (not edges!) of your mesh and "locks" vertices that form half-edges that have no pair (no second half-edge). Thanks to the nature of the half-edge data structures that OpenMesh uses this has O(n) complexity for a mesh of n edges.

If you are not familiar with the specifics of half-edge data structures, I would advise to read through the excellent "Using and understanding OpenMesh" introductory section of the OpenMesh docs.