GPU-accelerated Hausdorff distance computation between dynamic deformable NURBS surfaces

We present a parallel GPU-accelerated algorithm for computing the directed Hausdorff distance from one NURBS surface to another, within a bound. We make use of axis-aligned bounding-box hierarchies that bound the NURBS surfaces to accelerate the computations. We dynamically construct as well as traverse the bounding-box hierarchies for the NURBS surfaces using operations that are optimized for the CPU. To compute the Hausdorff distance, we traverse this hierarchy after culling bounding-box pairs that do not contribute to the Hausdorff distance. Our contribution includes two-sided culling tests that can be performed in parallel using the GPU. The culling, based on the minimum and maximum distance ranges between the bounding boxes, eliminates bounding-box pairs from both surfaces that do not contribute to the Hausdorff distance simultaneously. We calculate accuracy bounds for our computed Hausdorff distance based on the curvature of the surfaces. Our algorithm runs in real-time with very small guaranteed error bounds for complex NURBS surfaces. Since we dynamically construct our bounding-box hierarchy, our algorithm can be used to interactively compute the Hausdorff distance for models made of dynamic deformable surfaces. (C) 2011 Elsevier Ltd. All rights reserved.