Min Tang
Young J. Kim
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.
Supplemental Material
Available for Download
1) SIG09.avi papers video (encoded in DivX 6.8 codecs) 2) CSE-TR-2009-01 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
- 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 Scholar
Digital Library
- 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
- 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
- Alt, H., Behrends, B., and Blömer, J. 1995. Approximate matching of polygonal shapes. Ann. Math. Artif. Intell. 13, 251--266.Google ScholarCross Ref
- 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
- 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
- Atallah, M. J. 1983. A linear time algorithm for the Hausdorff distance between convex polygons. Inf. Process. Lett. 17, 207--209.Google ScholarCross Ref
- 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
- Cignoni, P., Rocchini, C., and Scopigno, R. 1998. Metro: Measuring error on simplified surfaces. Computer Graphics Forum 17, 2, 167--174.Google ScholarCross Ref
- 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
- 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
- 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
- Garland, M., and Heckbert, P. S. 1997. Surface simplification using quadric error metrics. In Proc. of ACM SIGGRAPH, 209--216. Google ScholarDigital Library
- Godau, M. 1998. On the complexity of measuring the similarity between geometric objects in higher dimensions. PhD thesis, Freie Universität.Google Scholar
- 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
- 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
- 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
- Hippmann, G. 2004. An algorithm for compliant contact between complexly shaped bodies. Multibody System Dynamics 12, 4.Google ScholarCross Ref
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- Lin, M., and Manocha, D. 2003. Collision and proximity queries. In Handbook of Discrete and Computational Geometry.Google Scholar
- 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
- Lopez, M. A., and Reisner, S. 2008. Hausdorff approximation of 3D convex polytopes. Inf. Process. Lett. 107, 2, 76--82. Google ScholarDigital Library
- 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
- 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
- NVIDIA. 2009. PhysX. http://www.nvidia.com.Google Scholar
- Redon, S. 2004. Fast continuous collision detection and handling for desktop virtual prototyping. Virtual Real. 8, 1, 63--70. Google ScholarDigital Library
- 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
- 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
- Varadhan, G., and Manocha, D. 2004. Accurate Minkowski sum approximation of polyhedral models. In Pacific Graphics, 392--401. Google ScholarDigital Library
- 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
- 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
- Zitová, B., and Flusser, J. 2003. Image registration methods: a survey. Image and Vision Computing 21, 11, 977--1000.Google ScholarCross Ref
Index Terms
- Interactive Hausdorff distance computation for general polygonal models
Recommendations
Interactive Hausdorff distance computation for general polygonal models
SIGGRAPH '09: ACM SIGGRAPH 2009 papersWe 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 ...
Precise Hausdorff distance computation between polygonal meshes
We present an exact algorithm for computing the precise Hausdorff distance between two general polyhedra represented as triangular meshes. The locus of candidate points, events where the Hausdorff distance may occur, is fully classified. These events ...
Hausdorff distance under translation for points and balls
SCG '03: Proceedings of the nineteenth annual symposium on Computational geometryWe study the shape matching problem under the Hausdorff distance and its variants. Specifically, we consider two sets A,B of balls in Rd, d=2,3, and wish to find a translation t that minimizes the Hausdorff distance between A+t, the set of all balls in ...
Comments