Fast and robust Hausdorff distance computation from triangle mesh to quad mesh in near-zero cases

Abstract

We present an algorithm that computes the one-sided Hausdorff distance from a triangle mesh to a quad mesh. Our algorithm is much more robust than previous ones in the sense that memory requirement is vastly reduced, by avoiding storing combinatorial pairs of each two input model's parts. Meanwhile, point projection via uniform grid greatly accelerates the algorithm. Experimental results show that even for cases where the Hausdorff distance is near zero, its precise computation is done in an interactive speed, while memory consumption is easily manageable.