Fast and robust computation of the Hausdorff distance between triangle mesh and quad mesh for near-zero cases. (June 2019)

• Record Type: Journal Article
• Authors: Kang, Yunku; Yoon, Seung-Hyun; Kyung, Min-Ho; Kim, Myung-Soo
• Is Part Of: Computers & graphics. Volume 81(2019)
• Page Start: 61
• Page End: 72
• Publication Date: 2019-06
• Subjects: Hausdorff distance -- Shape matching -- Quad mesh; Computer graphics -- Periodicals; 006.6
• DOI: 10.1016/j.cag.2019.03.014
• Languages: English
• ISSNs: 0097-8493

Abstract

Highlights: Efficient algorithm for computing the two-sided Hausdorff distance between a triangle mesh and a quad mesh. Specialized algorithm for handling the cases of near-zero Hausdorff distance in an interactive speed. Guarantee on the approximation error of the Hausdorff distance to be within an arbitrarily given error bound, which can be machine precision-level small. Graphical abstract: Two-sided Hausdorff Distance Computation Progress Abstract: We introduce an algorithm for computing the two-sided Hausdorff distance between a triangle mesh and a quad mesh, guaranteed to be within the given error bound, which can be machine precision-level small. The algorithm expands upon a recent breakthrough that only calculates the one-sided Hausdorff distance from the triangle mesh to the quad mesh using what is called "matching" and "upper bounding" of candidate pieces. We complete the algorithm by accomplishing the computation of the one-sided Hausdorff distance in the opposite direction: from the quad mesh to the triangle mesh. We split each quad into two triangular pieces to simplify the breakdown of matching cases and provide additional matching methods for new cases. By fusing the two one-sided computation algorithms, one can compute the two-sided Hausdorff distance that, for instance, can properly evaluate a quad mesh approximation of a triangle mesh. Experimental results show that our algorithm can handle near-zero Hausdorff distance, which has always been known to be a much difficult task, in an interactive time. Moreover, the improvement in efficiency of the two-sided Hausdorff distance computation over the successive execution of the two one-sided computations is addressed.