Measuring the difference between two meshes

Computing the geometric difference between two 3D models is a quite common task in mesh processing. In our lab, many years ago (11 !), we developed and freely distributed the standard tool for such task, Metro, whose paper has been cited more than 500 times . While Metro is still a small open source standalone command line program available at our web site, its functionality have been integrated into MeshLab in the filter Sampling->Hausdorff Distance, and they can be used in a variety of ways.
So here is a short basic tutorial.

Start with a mesh (in the following the well known Stanford Happy Buddha (1087716 triangles). Aggressively simplify it in a significant way to just 50k tris (e.g. 1/20 of the original size). Reload the original mesh as a new layer. At this point you should have two approximation of the same shape well aligned in the same space. Toggling the visibility on and off of each mesh you should easily see the difference between the two meshes (tip: ctrl+click over the eye icon in the layers window turn off all the other layers).

Now you are ready to start the Hausdorff distance filter.  First of all remember that the Hausdorff Distance between two meshes is a the maximum between the two so-called one-sided Hausdorff distances (technically not they are not a distance):

These two measures are not symmetric (e.g. the results depends on what mesh you set as X or Y).
In the Hausdorff filters MeshLab computes only the one-sided version

leaving the task of getting the maximum of the two to the user.

Now on the practical side. MeshLab uses a sampling approach to compute the above formula taking a bunch of points over a mesh X and searching for each x the closest point y on a mesh Y. That means that the result is strongly affected on how many points do you take over X and there are a lot of option on for that. A common very simple approach is just to use the vertexes of the highest density mesh as sampling points (e.g. the original Buddha vertexes): to do this simply leave checked only the "vertex sampling" option in the filter dialog and be sure that the number of samples is greater or equal than the vertex number. After a few secs the filter ends writing down in the layers log windows the collected info. Something like:

: Hausdorff Distance computed

: Sample 543652

: min : 0.000000 max 0.001862

: mean : 0.000029 RMS : 0.000083

: Values w.r.t. BBox Diag (0.229031)

: min : 0.000000 max 0.008128

: mean : 0.000126 RMS : 0.000361

For sake of human readability the filter reports the values in the mesh units (whatever they are) and with respect to the diagonal of the bounding box of the mesh that is something you are always able to understand without knowing anything about the model units. For example in this case you can see that the maximum error between the two mesh is approximately 1% of the bbox diag, but on the average the two meshes are almost in the 1/10000 range.

The filter save in the all-purpose quality field of the vertexes of the sampled mesh the computed distance values. To better visualize the error you can simply convert these values (for the high resolution mesh) into colors using the Color->Colorize by quality filter that maps them in to a rather red-green-blue colormap. Usually given the non uniform distribution of the values you have to play a bit with the filter parameters clamping the mapping range to something meaningful (only a few points have the maximum so with a linear mapping of the values over the whole range will result into a almost uniform red mesh. Note that it is a red-green-blu map, so red is min and blue is max, so in our case red means zero error (good) and blue high error (bad).
The next image sequence report just a small detail of the one of the points with higher error. During the simplification we removed some topological noise, (the thin tubes connecting the two side of the hole)  from a Hausdorff point of view it is a rather large error: the points in the middle of the thin tubes has nothing in the simplified mesh that is close to them; so they bring up the maximum error significantly. Luckily enough they represent only a small portion of the whole mesh so the average error remains low.

Note that if you measure the other one-sided Hausdorff distance, that specific mesh portion will not denote any particular error, because in that case you sample the simplified mesh and for each point of the simplified mesh there are points of the original mesh that are quite close to them. In other words, in this case the simplified mesh is close to the original one, but the original one is not close to the simplified one.

Next post will discuss some remaining issues including the sampling of the surface, looking at all the taken samples and the found closest points and how to colorize the low resolution mesh...
Second part of the tutorial here.

Desktop Manifacturing

The January 2010 number of Make will contains a lot of stuff about Desktop Manufacturing, a field where MeshLab has always been useful as an all purpose repairing tooling (and it is often cited as a handy free stl viewer...). In particular in the "3D Fabbing state of the art" of Make, they refer MeshLab as a "really high quality free software". That's flattering :).