“Interactive Hausdorff distance computation for general polygonal models” by Tang, Lee and Kim

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.

1. Agarwal, P. K., S. Har-Peled, Sharir, M., and Wang, Y. 2003. Hausdorff distance under translation for points, disks, and balls. In Proc. 19th Annu. ACM Sympos. Comput. Geom., 282–291. Google ScholarDigital Library
2. Alexa, M., Behr, J., Cohen-Or, D., Fleishman, S., Levin, D., and Silva, C. T. 2003. Computing and rendering point set surfaces. IEEE Transactions on Visualization and Computer Graphics 9, 1, 3–15. Google ScholarDigital Library
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.Google Scholar
4. Alt, H., Behrends, B., and Blömer, J. 1995. Approximate matching of polygonal shapes. Ann. Math. Artif. Intell. 13, 251–266.Google ScholarCross Ref
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.Google Scholar
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.Google Scholar
7. Atallah, M. J. 1983. A linear time algorithm for the Hausdorff distance between convex polygons. Inf. Process. Lett. 17, 207–209.Google ScholarCross Ref
8. Chew, L. P., Goodrich, M. T., Huttenlocher, D. P., Kedem, K., Kleinberg, J. M., and Kravets, D. 1997. Geometric pattern matching under Euclidean motion. Computational Geometry: Theory and Applications 7, 113–124. Google ScholarDigital Library
9. Cignoni, P., Rocchini, C., and Scopigno, R. 1998. Metro: Measuring error on simplified surfaces. Computer Graphics Forum 17, 2, 167–174.Google Scholar
10. Cohen, J., Varshney, A., Manocha, D., Turk, G., Weber, H., Agarwal, P., Brooks, F., and Wright, W. 1996. Simplification envelopes. In Proc. of ACM Siggraph’96, 119–128. Google ScholarDigital Library
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.Google Scholar
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.Google Scholar
13. Garland, M., and Heckbert, P. S. 1997. Surface simplification using quadric error metrics. In Proc. of ACM SIGGRAPH, 209–216. Google ScholarDigital Library
14. Godau, M. 1998. On the complexity of measuring the similarity between geometric objects in higher dimensions. PhD thesis, Freie Universität.Google Scholar
15. Goodrich, M. T., Mitchell, J. S. B., and Orletsky, M. W. 1999. Approximate geometric pattern matching under rigid motions. IEEE Transactions on Pattern Analysis and Machine Intelligence 21, 37–9. Google ScholarDigital Library
16. Guendelman, E., Bridson, R., and Fedkiw, R. 2003. Nonconvex rigid bodies with stacking. In ACM SIGGRAPH, ACM, New York, NY, USA, 871–878. Google ScholarDigital Library
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.Google Scholar
18. Hippmann, G. 2004. An algorithm for compliant contact between complexly shaped bodies. Multibody System Dynamics 12, 4.Google ScholarCross Ref
19. Huttenlocher, D. P., Kedem, K., and Kleinberg, J. M. 1992. On dynamic Voronoi diagrams and the minimum Hausdorff distance for point sets under Euclidean motion in the plane. In ACM Symposium on Computational Geometry, 110–119. Google ScholarDigital Library
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.Google ScholarDigital Library
21. Huttenlocher, D. P., Klanderman, G. A., and Rucklidge, W. J. 1993. Comparing images using the Hausdorff distance. IEEE Trans. Pattern Anal. Mach. Intell. 15, 850–863. Google ScholarDigital Library
22. Jesorsky, O., Kirchberg, K., Frischholz, R., et al. 2001. Robust face detection using the Hausdorff distance. Lecture Notes in Computer Science, 90–95. Google ScholarDigital Library
23. Kettner, L., Mehlhorn, K., Pion, S., Schirra, S., and Yap, C. 2008. Classroom examples of robustness problems in geometric computations. Comput. Geom. Theory Appl. 40, 1, 61–78. Google ScholarDigital Library
24. Kim, Y. J., Otaduy, M. A., Lin, M. C., and Manocha, D. 2002. Fast penetration depth computation for physically-based animation. Proc. of ACM Symposium on Computer Animation. Google ScholarDigital Library
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.Google Scholar
26. Lin, M., and Manocha, D. 2003. Collision and proximity queries. In Handbook of Discrete and Computational Geometry.Google Scholar
27. Llanas, B. 2005. Efficient computation of the Hausdorff distance between polytopes by exterior random covering. Comput. Optim. Appl. 30, 2, 161–194. Google ScholarDigital Library
28. Lopez, M. A., and Reisner, S. 2008. Hausdorff approximation of 3D convex polytopes. Inf. Process. Lett. 107, 2, 76–82. Google ScholarDigital Library
29. Luebke, D., Watson, B., Cohen, J., Reddy, M., and Varshney, A. 2002. Level of detail for 3D graphics. Elsevier Science Inc. New York, NY, USA. Google ScholarDigital Library
30. Moore, M., and Wilhelms, J. 1988. Collision detection and response for computer animation. In Computer Graphics (SIGGRAPH ’88 Proceedings), J. Dill, Ed., vol. 22, 289–298. Google ScholarDigital Library
31. NVIDIA. 2009. PhysX. http://www.nvidia.com.Google Scholar
32. Redon, S. 2004. Fast continuous collision detection and handling for desktop virtual prototyping. Virtual Real. 8, 1, 63–70. Google ScholarDigital Library
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.Google ScholarDigital Library
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.Google Scholar
35. Varadhan, G., and Manocha, D. 2004. Accurate Minkowski sum approximation of polyhedral models. In Pacific Graphics, 392–401. Google ScholarDigital Library
36. Wald, I., Boulos, S., and Shirley, P. 2007. Ray tracing deformable scenes using dynamic bounding volume hierarchies. ACM Trans. Graph. 26, 1, 6. Google ScholarDigital Library
37. Zhang, L., Kim, Y. J., Varadhan, G., and Manocha, D. 2007. Generalized penetration depth computation. Computer-Aided Design 39, 8, 625–638. Google ScholarDigital Library
38. Zitová, B., and Flusser, J. 2003. Image registration methods: a survey. Image and Vision Computing 21, 11, 977–1000.Google ScholarCross Ref