When comparing the results of all the tests done of V-HACD decomposition algorithm, we found out that we needed a criteria that allowed us to quantify the quality of the results obtained.
We can think that the best decomposition is the one whose decomposed model is the closest to the original one. This distance relationship between two meshes, the mesh of the original model and the mesh of the all the decomposed parts merged, can be obtained calculating the Hausdorff distance (https://en.wikipedia.org/wiki/Hausdorff_distance).
In general terms, the Hausdorff Distance is the maximum distance of a set to the nearest point in the other set. As we have two sets (two meshes A and B) the Hausdorff distance is the maximum of the two distances (A to B and B to A). These two distances are not symmetric (quite often we say that the Hausdorff distance is oriented) so both of them need to be calculated.
H(A,B) = max\{h (A, B), h (B, A)\} \\[2mm]
with: \\[2mm]
h (A, B) = \max_{a \in A} \{ \min_{b \in B} \{ d(a,b)\} \} \\[2mm]Meshlab provides a Hausdorff distance calculation (a filter) so we decided to use it to calculate our quality parameter. For simplicity we used the python library Pymeshlab to automatize the quality calculation (see how to section for more details).
The Hausdorff filter provided by Pymeshlab basically selects a number of points a from the set A and searchs for each point a the closest point b of the set B. We can see how the result of the calculation depends strongly on the number of points used of the set A (which it will be called in the program the sampled mesh). It is a good criteria is to use as a number of sampling points the number of vertex of the sampling mesh (or higher).
Although both distances should be calculated, the most representative is the one whose sampling mesh has more density which it is normally the original mesh (in our case the original 3D model).
The Hausdorff filter from Pymeshlad provides the following values as a result:
- min: the minimum distance found between the two meshes
- max: the maximum distance found between the two meshes
- mean: the average distance found between the two meshes
- RMS: standard deviation.
- diag_mesh_0: diagonal of the mesh 0 (sampling mesh)
- diag_mesh_1: diagonal of the mesh 1 (target mesh)
- n_samples: Number of samples used for sampling the sampling mesh
In general terms the two values that are going to be more useful when defining a quality criteria are max and mean. On one side, the smaller value of max the closest are the two meshes so the better the descomposition has been. On the other side, the closest the mean is to zero the more points from target mesh are close to the sampling mesh so the overall error distribution is small.
It is important to take into account that, in order to be able to compare different 3D models we should normalize the values of max, min, mean (so that there are not dependant on the size). That is the reason we have diag_mesh_0 and diag_mesh_1 values. A good approach is to use diag_mesh_0 and then obtain the percentage, in this case we could set up a minimum percentage required to consider that the decomposition is well done.
The Hausdorff distance was obtained for the different tests done before. We focus specially in how this distance is affected by the variation in the model resolution and concavity. The following two graphics show precicely this relationship, focusing in the max and mean values (calculated as a percentage over the mesh diagonal as described in the former paragraph).
####Conclusions A quality criteria obtained from the max and mean values of the Hausdorff distance is a good way to validate the decomposition of our 3D model. In general terms we only need to focus in calculating the distance from our 3D model to the merged model. That is, our sample model is the original model and the target model is the decomposed one (the merge of all the pieces obtained). This is because our original model is normally more dense. However:
- The distance (max value) calculated using the merged mesh as the sample model (the other side of the Hausdorff distance) can be bigger than the other distance (from original model to merged) when our merged model is more dense than the original model. This is the case when using high resolution values and really small concavity values. Be careful when using the maximum of both distances (we have not done it in our tests although both values were calculated) because we can end up having big max distance values in cases where the decomposition is good but extremelly detailed.
- Although the Hausdorff distance can be considered as a global quality parameter, there will be always cases where a small max value does not mean a good decomposition. That is the case when using high beta values (see first tests section). In this case a beta = 0,1 has a max value (%) of 3,75 while for a beta = 0,5 it is of 3,49% but the decomposed model at beta = 0,5 has the cup handle wrong while at beta = 0,1 it is fine.