Interactive Hausdorff distance computation for general polygonal models

ABSTRACT

We present a simple algorithm to compute the Hausdorff distance between complicated, polygonal models at interactive rates. The algorithm requires no assumptions about the underlying topology and geometry. To avoid the high computational and implementation complexity of exact Hausdorff distance calculation, we approximate the Hausdorff distance within a user-specified error bound. The main ingredient of our approximation algorithm is a novel polygon subdivision scheme, called Voronoi subdivision, combined with culling between the models based on bounding volume hierarchy (BVH). This cross-culling method relies on tight yet simple computation of bounds on the Hausdorff distance, and it discards unnecessary polygon pairs from each of the input models alternatively based on the distance bounds. This algorithm can approximate the Hausdorff distance between polygonal models consisting of tens of thousands triangles with a small error bound in real-time, and outperforms the existing algorithm by more than an order of magnitude. We apply our Hausdorff distance algorithm to the measurement of shape similarity, and the computation of penetration depth for physically-based animation. In particular, the penetration depth computation using Hausdorff distance runs at highly interactive rates for complicated dynamics scene.

REFERENCES

• 1: Pankaj K. Agarwal , Sariel Har-Peled , Micha Sharir , Yusu Wang, Hausdorff distance under translation for points and balls, Proceedings of the nineteenth annual symposium on Computational geometry, June 08-10, 2003, San Diego, California, USA [doi>10.1145/777792.777835]
• 2: Marc Alexa , Johannes Behr , Daniel Cohen-Or , Shachar Fleishman , David Levin , Claudio T. Silva, Computing and Rendering Point Set Surfaces, IEEE Transactions on Visualization and Computer Graphics, v.9 n.1, p.3-15, January 2003 [doi>10.1109/TVCG.2003.1175093]
• 3: Alt, H., and Guibas, L. J. 2000. Discrete geometric shapes: Matching, interpolation, and approximation. In Handbook of Computational Geometry, J.-R. Sack and J. Urrutia, Eds. Elsevier Science Publishers B. V. North-Holland, Amsterdam, 121--153.
• 4: Alt, H., Behrends, B., and Blömer, J. 1995. Approximate matching of polygonal shapes. Ann. Math. Artif. Intell. 13, 251--266.
• 5: Alt, H., Brass, P., Godau, M., Knauer, C., and Wenk, C. 2003. Computing the Hausdorff distance of geometric patterns and shapes. In Discrete and Computational Geometry., vol. 25. 65--76.
• 6: Aspert, N., Santa-Cruz, D., and Ebrahimi, T. 2002. Mesh: Measuring errors between surfaces using the hausdorff distance. In Proceedings of the IEEE International Conference on Multi-media and Expo, 705--708.
• 7: Atallah, M. J. 1983. A linear time algorithm for the Hausdorff distance between convex polygons. Inf. Process. Lett. 17, 207--209.
• 8: L. Paul Chew , Michael T. Goodrich , Daniel P. Huttenlocher , Klara Kedem , Jon M. Kleinberg , Dina Kravets, Geometric pattern matching under Euclidean motion, Computational Geometry: Theory and Applications, v.7 n.1-2, p.113-124, Jan. 1997 [doi>10.1016/0925-7721(95)00047-X]
• 9: Cignoni, P., Rocchini, C., and Scopigno, R. 1998. Metro: Measuring error on simplified surfaces. Computer Graphics Forum 17, 2, 167--174.
• 10: Jonathan Cohen , Amitabh Varshney , Dinesh Manocha , Greg Turk , Hans Weber , Pankaj Agarwal , Frederick Brooks , William Wright, Simplification envelopes, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.119-128, August 1996 [doi>10.1145/237170.237220]
• 11: Ehmann, S., and Lin, M. C. 2001. Accurate and fast proximity queries between polyhedra using convex surface decomposition. Computer Graphics Forum (Proc. of Eurographics'2001) 20, 3, 500--510.
• 12: Fisher, S., and Lin, M. C. 2001. Fast penetration depth estimation for elastic bodies using deformed distance fields. Proc. of IEEE/RSJ International Conference on Intelligent Robots and Systems 2001.
• 13: Michael Garland , Paul S. Heckbert, Surface simplification using quadric error metrics, Proceedings of the 24th annual conference on Computer graphics and interactive techniques, p.209-216, August 1997 [doi>10.1145/258734.258849]
• 14: Godau, M. 1998. On the complexity of measuring the similarity between geometric objects in higher dimensions. PhD thesis, Freie Universität.
• 15: Michael T. Goodrich , Joseph S. B. Mitchell , Mark W. Orletsky, Approximate Geometric Pattern Matching Under Rigid Motions, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.21 n.4, p.371-379, April 1999 [doi>10.1109/34.761267]
• 16: Eran Guendelman , Robert Bridson , Ronald Fedkiw, Nonconvex rigid bodies with stacking, ACM SIGGRAPH 2003 Papers, July 27-31, 2003, San Diego, California
• 17: Guthe, M., Borodin, P., and Klein, R. 2005. Fast and accurate Hausdorff distance calculation between meshes. In International Conferences in Central Europe on Computer Graphics, Visualization and Computer Vision (WSCG), 41--48.
• 18: Hippmann, G. 2004. An algorithm for compliant contact between complexly shaped bodies. Multibody System Dynamics 12, 4.
• 19: Daniel P. Huttenlocher , Klara Kedem , Jon M. Kleinberg, On dynamic Voronoi diagrams and the minimum Hausdorff distance for point sets under Euclidean motion in the plane, Proceedings of the eighth annual symposium on Computational geometry, p.110-119, June 10-12, 1992, Berlin, Germany [doi>10.1145/142675.142700]
• 20: Huttenlocher, D. P., Kedem, K., and Sharir, M. 1993. The upper envelope of Voronoi surfaces and its applications. Discrete and Computational Geometry 9, 267--291.
• 21: D. P. Huttenlocher , G. A. Klanderman , W. A. Rucklidge, Comparing Images Using the Hausdorff Distance, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.15 n.9, p.850-863, September 1993 [doi>10.1109/34.232073]
• 22: Oliver Jesorsky , Klaus J. Kirchberg , Robert Frischholz, Robust Face Detection Using the Hausdorff Distance, Proceedings of the Third International Conference on Audio- and Video-Based Biometric Person Authentication, p.90-95, June 06-08, 2001
• 23: Lutz Kettner , Kurt Mehlhorn , Sylvain Pion , Stefan Schirra , Chee Yap, Classroom examples of robustness problems in geometric computations, Computational Geometry: Theory and Applications, v.40 n.1, p.61-78, May, 2008 [doi>10.1016/j.comgeo.2007.06.003]
• 24: Young J. Kim , Miguel A. Otaduy , Ming C. Lin , Dinesh Manocha, Fast penetration depth computation for physically-based animation, Proceedings of the 2002 ACM SIGGRAPH/Eurographics symposium on Computer animation, July 21-22, 2002, San Antonio, Texas [doi>10.1145/545261.545266]
• 25: Larsen, E., Gottschalk, S., Lin, M., and Manocha, D. 2000. Distance queries with rectangular swept sphere volumes. Proc. of IEEE Int. Conference on Robotics and Automation.
• 26: Lin, M., and Manocha, D. 2003. Collision and proximity queries. In Handbook of Discrete and Computational Geometry.
• 27: Bernardo Llanas, Efficient Computation of the Hausdorff Distance Between Polytopes by Exterior Random Covering, Computational Optimization and Applications, v.30 n.2, p.161-194, February 2005 [doi>10.1007/s10589-005-4560-z]
• 28: Mario A. Lopez , Shlomo Reisner, Hausdorff approximation of 3D convex polytopes, Information Processing Letters, v.107 n.2, p.76-82, July, 2008 [doi>10.1016/j.ipl.2008.01.010]
• 29: David Luebke , Benjamin Watson , Jonathan D. Cohen , Martin Reddy , Amitabh Varshney, Level of Detail for 3D Graphics, Elsevier Science Inc., New York, NY, 2002
• 30: Matthew Moore , Jane Wilhelms, Collision detection and response for computer animationr3, Proceedings of the 15th annual conference on Computer graphics and interactive techniques, p.289-298, June 1988
• 31: NVIDIA. 2009. PhysX. http://www.nvidia.com.
• 32: Stephane Redon, Fast continuous collision detection and handling for desktop virtual prototyping, Virtual Reality, v.8 n.1, p.63-70, June 2004 [doi>10.1007/s10055-004-0138-9]
• 33: Rucklidge, W. J. 1996. Lower bounds for the complexity of the graph of the Hausdorff distance as a function of transformation. Discrete and Computational Geometry 16, 2.
• 34: Tang, M., and Kim, Y. J. 2009. Deriving upper and lower bounds of Hausdorff distance for polygonal models. Tech. rep. CSE-TR-2009-01, Ewha Womans University, Seoul, Korea.
• 35: Gokul Varadhan , Dinesh Manocha, Accurate Minkowski Sum Approximation of Polyhedral Models, Proceedings of the Computer Graphics and Applications, 12th Pacific Conference, p.392-401, October 06-08, 2004
• 36: Ingo Wald , Solomon Boulos , Peter Shirley, Ray tracing deformable scenes using dynamic bounding volume hierarchies, ACM Transactions on Graphics (TOG), v.26 n.1, p.6-es, January 2007 [doi>10.1145/1189762.1206075]
• 37: Liangjun Zhang , Young J. Kim , Gokul Varadhan , Dinesh Manocha, Generalized penetration depth computation, Computer-Aided Design, v.39 n.8, p.625-638, August, 2007 [doi>10.1016/j.cad.2007.05.012]
• 38: Zitová, B., and Flusser, J. 2003. Image registration methods: a survey. Image and Vision Computing 21, 11, 977--1000.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Geometric algorithms, languages, and systems

Keywords:
Hausdorff distance, dynamics simulation, penetration depth, shape similarity