Site Search


Geometric Features

Figure 1

The extensive use of CAD systems in mechanical design today, results in a large quantity of three dimensional digital models of industrial parts available on the Internet. This requires fast algorithms for computing geometric features of CAD-constructed three dimensional bodies.
The Hausdorff distance is a useful measure of the similarity between geometric objects. There are many applications that benefit from an efficient computation of the Hausdorff distance in shape matching, geometric search and more. As a result, Hausdorff distance computation has attracted considerable research attention in computer graphics, computational geometry, and geometric modeling.

Dr. Hanniel's research, which was conducted in collaboration with UC Berkeley, focused on parallel algorithms that use strong graphical processors (GPUs). GPUs are common today on desktop computers and are a powerful computational tool. GPU algorithms enable to improve the computation time by performing a large number of operations simultaneously.

Figure 1: The projected distances (in red) from a plane to a NURBS surface, were computed in parallel on the GPU. The computed Hausdorff distance (in yellow) is the maximal of these distances.

Several methods of computations were tested, and their advantages and limitations were compared. In particular algorithms based on hierarchical data structures were compared to algorithms based on sampling and numerical iterations. The first were found to be very efficient for large Hausdorff distances, however, their efficiency reduces as the distance gets smaller. The second, on the other hand, were not sensitive to the position of the inputs, but the stability of the methods was dependent on different numeric parameters.

Related Publications:

  • I. Hanniel, A. Krishnamurthy and S. McMains, "Computing the Hausdorff Distance between NURBS Surfaces using Numerical Iteration on the GPU", to appear.
  • A. Krishnamurthy , S. McMains and I. Hanniel, "GPU-Accelerated Hausdorff Distance Computation Between Dynamic Deformable NURBS Surfaces", CAD Journal, Volume 43, Number 11, 2011. 1370-1379.