How to compute the distance between two mesh surfaces

[flaminyu]

We need a tool to compute the distance between two triangulated mesh surfaces.
I ‘ve read many documents about the distance query and AABB tree ，only found how to get the distance from a point to a surface.
Is there any tool in CGAL could help me?

[janetournois]

Hi,
the Hausdorff Distance section in the Polygon Mesh Processing package probably contains what you need.

[pentacular]

The Hausdorff Distance looks like it does what you want, providing you can accept some tolerance.

[flaminyu]

@flaminyu You say "minimal distance" as if there were several distances and you want the smallest one. This is not clear. Do you mean the minimal distance between a point of the first mesh and a point of the second mesh?

Thanks for your reply. Maybe I didn't express my question clearly. We are working on the triangulated surface meshes. The minimal distance is the smallest distance between a triangulation of the first mesh and a triangulation of the second mesh.

Sorry for my poor English. I mean the shortest Euclidean distance between the two meshes.

[stla]

So you want what I said, I think: the smallest distance between one point on the first mesh and one point on the second mesh. This is the mathematical definition of the distance between two sets. I don't think this is possible because this smallest distance is not necessarily attained for two points which are vertices. An approximate way would be to randomly sample some points on the two meshes and take the smallest distance.

[MaelRL]

Not the best complexity, but with limited code to write:

• Prune the case of 0 distance using PMP::do_intersect
• Use https://stackoverflow.com/questions/24995935/closest-distance-vertices-of-two-meshes to find an upper bound on the distance
• Can tighten this bound by computing vertex-mesh distance (https://doc.cgal.org/latest/AABB_tree/classCGAL_1_1AABB__tree.html#abe3e1ab4a89de2623b6930324343b2fa)
• Use spatial searching with padding (based on the bound above) around the faces of the meshes and finally compute the distances between matched face pairs using CGAL::squared_distance(Triangle, Triangle).

[flaminyu]

Thank you for your reply， I will try it out.