Implementing a Fast Distance Computation between Triangle Meshes

Measuring the similarity between two geometric models is an important problem in diverse fields, including computer graphics, computer games, and geometric modeling. For example, they can be used in terms of benchmarks to determine the variance of a processed geometry from a given ground-truth model.

One such similarity measure is the Hausdorff distance. Given two compact subsets A, B of a metric space, the one-sided Hausdorff distance between A and B is defined as the distance between an element a from A and an element b from B, where a is chosen to maximize the distance and b is chosen to minimize it. Intuitively speaking, the Hausdorff distance measures the maximum deviation between two models.

The project consists of implementing the algorithm for interactive Hausdorff distance computation presented by Tang, Lee, and Kim. While it provides an approximation to the Hausdorff distance - as already present in the CGAL framework - it ensures the computed measure to be within a user-specified error bound. Thereby, the user can obtain as good results as necessary for the applications at hand within a fast and efficient pipeline.