Precise Hausdorff distance computation for planar freeform curves using biarcs and depth buffer

We present a real-time algorithm for computing the precise Hausdorff Distance (HD) between two planar freeform curves. The algorithm is based on an effective technique that approximates each curve with a sequence of G ¹ biarcs within an arbitrary error bound. The distance map for the union of arcs is then given as the lower envelope of trimmed truncated circular cones, which can be rendered efficiently to the graphics hardware depth buffer. By sampling the distance map along the other curve, we can estimate a lower bound for the HD and eliminate many redundant curve segments using the lower bound. For the remaining curve segments, we read the distance map and detect the pixel(s) with the maximum distance. Checking a small neighborhood of the maximum-distance pixel, we can reduce the computation to considerably smaller subproblems, where we employ a multivariate equation solver for an accurate solution to the original problem. We demonstrate the effectiveness of the proposed approach using several experimental results.