Mesh decimation (aka simplification) in matlab

weblog/

I'd forgotten that I'd discovered that matlab has a built-in function for triangle mesh simplification: `reduce_patch`. Here's a little comparison between this method and the ones I've wrapped up in gptoolbox.

Input mesh

Given an input mesh with vertices `V` and faces `F` (this elephant has 14732 faces):

Built-in matlab reduce patch

We can decimate the mesh to 1000 faces using pure built-in matlab:

``````[mF,mV] = reducepatch(F,V,1000);
``````

Notice that it's a rather adaptive remeshing. There aren't (m)any options for controlling `reducepatch`, just the `'fast'` flag, but in this case it will produce an identical output.

Libigl's decimate

Libigl has a framework for edge-collapse decimation on manifold meshes and a default setting for regular meshing:

``````[iV,iF] = decimate_libigl(V,F,1000);
``````

CGAL's decimation

I have a wrapper for CGAL's decimation algorithms. These can result in a regular remeshing with 1000 faces:

``````[c1V,c1F] = decimate_cgal(V,F,1000/size(F,1));
``````

``````[c2V,c2F] = decimate_cgal(V,F,1000/size(F,1),'Adaptive',true);
``````

CGAL has a fairly general interface for an edge-collapser, but these are the only metrics provided by default from CGAL.

Timing

Suppose my original elephant had 3.7 million faces instead of just 14K, how do these methods measure up when reducing to 1000 faces:

Method Time
reducepatch 64.4s
libigl 74.56s
cgal (regular) 117.7s
My qslim wrapper is currently very silly. It's calling `qslim` as an executable and then reading in the entire collapse log and conducting the collapse within matlab (the second time is for reading the log, the third for conducting the collapse).
None of these methods guarantee that the result is self-intersection free. I've noticed that qslim and matlab will create non-manifold meshes from manifold inputs. The current libigl implementation should not creative non-manifold output, but assumes the input is a closed surface. For casual decimation, it seems like matlab's `reducepatch` and libigl's `decimate_libigl` are the best bets for speedy adaptive and regular meshing respectively. Conveniently they also require the least in terms of dependencies.