More Web Proxy on the site http://driver.im/

article

Precise Hausdorff distance computation between polygonal meshes

Authors:

Michael Bartoň,

Myung-Soo KimAuthors Info & Claims

Computer Aided Geometric Design, Volume 27, Issue 8

Pages 580 - 591

https://doi.org/10.1016/j.cagd.2010.04.004

Published: 01 November 2010 Publication History

Abstract

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 include simple cases where foot points of vertices are examined as well as more complicated cases where extreme distance evaluation is needed on the intersection curve of one mesh with the medial axis of the other mesh. No explicit reconstruction of the medial axis is conducted and only bisectors of pairs of primitives (i.e. vertex, edge, or face) are analytically constructed and intersected with the other mesh, yielding a set of conic segments. For each conic segment, the distance functions to all primitives are constructed and the maximum value of their low envelope function may correspond to a candidate point for the Hausdorff distance. The algorithm is fully implemented and several experimental results are also presented.

References

[1]

}}Alliez, P., Gotsman, C., 2003. Isotropic remeshing of surfaces: a local parametrization approach. In: Proc. Int. Meshing Roundtable, pp. 215-224.

[2]

}}Discrete geometric shapes: Matching, interpolation, and approximation. In: Sack, J.-R., Urrutia, J. (Eds.), Handbook of Computational Geometry, Elsevier Science B.V., North-Holland, Amsterdam.

[3]

}}Alt, H., Scharf, L., 2004. Computing the Hausdorff distance between sets of curves. In: Procs. of the 20th European Workshop on Computational Geometry (EWCG), Seville, Spain, pp. 233-236.

[4]

}}Computing the Hausdorff distance between curved objects. Internat. J. Comput. Geom. Appl. v18 i4. 307-320.

[5]

}}Computing the Hausdorff distance of geometric patterns and shapes. In: Aronov, B., Basu, S., Pach, J., Sharir, M. (Eds.), Algorithms Combin., vol. 25. Springer-Verlag, Berlin. pp. 65-76.

[6]

}}A linear time algorithm for the Hausdorff distance between convex polygons. Inform. Process. Lett. v17. 207-209.

[7]

}}Computing the minimum distance between Bézier curves. J. Comput. Appl. Math. v230 i1. 294-310.

[8]

}}Computing minimum distance between two implicit algebraic surfaces. Computer-Aided Design. v38 i10. 1053-1061.

[9]

}}Metro: Measuring error on simplified surfaces. Computer Graphics Forum. v17 i2. 167-174.

[10]

}}Eck, M., DeRose, T., Duchamp, T., Hoppey, H., Lounsbery, M., Stuetzle, W., 1995. Multiresolution analysis of arbitrary meshes. In: ACM SIGGRAPH '95, Los Angeles, CA, USA, pp. 173-182.

[11]

}}Hausdorff and minimal distances between parametric freeforms in R2 and R3. In: Chen, F., Jüttler, B. (Eds.), Lecture Notes in Comput. Sci., vol. 4975. Springer-Verlag. pp. 191-204.

[12]

}}Elber, G., Kim, M.-S., 1997. The bisector surface of freeform rational space curves. In: Proceedings of the Thirteenth Annual Symposium on Computational Geometry, Nice, pp. 473-474.

[13]

}}A fast procedure for computing the distance between complex objects in three-dimensional space. IEEE Trans. Robot. Automat. v4. 193-203.

[14]

}}Fast and accurate Hausdorff distance calculation between meshes. Journal of WSCG. v13. 41-48.

[15]

}}Hoschek, J., 1992. Bézier curves and surface patches on quadrics. In: Lyche, T., Schumaker, L. (Eds.), Mathematical Methods in Computer Aided Geometric Design II, pp. 331-342.

[16]

}}Johnson, D., 2005. Minimum distance queries for haptic rendering. PhD thesis, Computer Science Department, University of Utah.

[17]

}}Jüttler, B., 2000. Bounding the Hausdorff distance of implicitly defined and/or parametric curves. In: Mathematical Methods in CAGD, Oslo, pp. 1-10.

[18]

}}Minimum distance between a canal surface and a simple surface. Computer-Aided Design. v35 i10. 871-879.

[19]

}}Kim, Y.-J., Oh, Y.-T., Yoon, S.-H., Kim, M.-S., Elber, G., 2010. Precise Hausdorff distance computation for planar freeform curves using biarcs and depth buffer. The Visual Computer, the special issue of Computer Graphics International 2010, June 9-11, Singapore. in press; http://www.springerlink.com/content/f1102l09057k42g4/.

[20]

}}Lennerz, C., Schomer, E., 2002. Efficient distance computation for quadric curves and surfaces. In: Proc. of Geometric Modeling and Processing, pp. 60-69.

[21]

}}Lin, M., Canny, J., 1991. A fast algorithm for incremental distance calculation. In: IEEE Int. Conf. Robot. Automat., Sacramento, CA, pp. 1008-1014.

[22]

}}Efficient computation of the Hausdorff distance between polytopes by exterior random covering. Comput. Optim. Appl. v30. 161-194.

[23]

}}Manocha, D., Erikson, C., 1998. GAPS: General and automatic polygonal simplification. In: Proc. of ACM Symposium on Interactive 3D Graphics, pp. 79-88.

[24]

}}Spatial Tessellations: Concepts and Applications of Voronoi Diagrams. 2nd edition. Wiley Publ., New York.

[25]

}}Rabl, M., Jüttler, B., 2009. Fast distance computation using quadratically supported surfaces. In: Proc. of Computational Kinematics (CK 2009), pp. 141-148.

[26]

}}Davenport-Schinzel Sequences and Their Geometric Applications. Cambridge University Press, New York, NY, USA.

[27]

}}Interactive Hausdorff distance computation for general polygonal models. ACM Trans. Graphics (SIGGRAPH '09). v28 i3.

[28]

}}Cache-efficient layouts of bounding volume hierarchies. Computer Graphics Forum (Eurographics). v25 i3. 507-516.

Cited By

Zhao WZhou G(2024)Hausdorff distance between convex semialgebraic setsJournal of Global Optimization10.1007/s10898-023-01313-988:2(409-429)Online publication date: 1-Feb-2024
https://dl.acm.org/doi/10.1007/s10898-023-01313-9
Wang SXia YYou LZhang J(2022)PDE-based surface reconstruction in automotive styling designMultimedia Tools and Applications10.1007/s11042-022-13297-x82:1(1185-1202)Online publication date: 14-Jun-2022
https://dl.acm.org/doi/10.1007/s11042-022-13297-x
Fu KChen JLi JYu KHe JTang MZheng Y(2022)Automatic unstructured mesh generation approach for simulation of electronic packaging systemEngineering with Computers10.1007/s00366-022-01764-w39:5(3527-3559)Online publication date: 11-Dec-2022
https://dl.acm.org/doi/10.1007/s00366-022-01764-w
Show More Cited By

Precise Hausdorff distance computation between polygonal meshes
1. Computing methodologies
  1. Computer graphics
    1. Shape modeling
2. Theory of computation
  1. Randomness, geometry and discrete structures

Recommendations

Interactive Hausdorff distance computation for general polygonal models
SIGGRAPH '09: ACM SIGGRAPH 2009 papers

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 ...
Interactive Hausdorff distance computation for general polygonal models

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 ...
Fast and robust computation of the Hausdorff distance between triangle mesh and quad mesh for near-zero cases
Highlights
- Efficient algorithm for computing the two-sided Hausdorff distance between a triangle mesh and a quad mesh.
Graphical abstract
Two-sided Hausdorff Distance Computation Progress

Display Omitted

Abstract
We introduce an algorithm for computing the two-sided Hausdorff distance between a triangle mesh and a quad mesh, guaranteed to be within the given error bound, which can be machine precision-level small. The algorithm expands upon a ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Computer Aided Geometric Design

Computer Aided Geometric Design Volume 27, Issue 8

November, 2010

105 pages

ISSN:0167-8396

Issue’s Table of Contents

Copyright © Elsevier B.V. © 2010.

Publisher

Elsevier Science Publishers B. V.

Netherlands

Publication History

Published: 01 November 2010

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

16
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 21 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Zhao WZhou G(2024)Hausdorff distance between convex semialgebraic setsJournal of Global Optimization10.1007/s10898-023-01313-988:2(409-429)Online publication date: 1-Feb-2024
https://dl.acm.org/doi/10.1007/s10898-023-01313-9
Wang SXia YYou LZhang J(2022)PDE-based surface reconstruction in automotive styling designMultimedia Tools and Applications10.1007/s11042-022-13297-x82:1(1185-1202)Online publication date: 14-Jun-2022
https://dl.acm.org/doi/10.1007/s11042-022-13297-x
Fu KChen JLi JYu KHe JTang MZheng Y(2022)Automatic unstructured mesh generation approach for simulation of electronic packaging systemEngineering with Computers10.1007/s00366-022-01764-w39:5(3527-3559)Online publication date: 11-Dec-2022
https://dl.acm.org/doi/10.1007/s00366-022-01764-w
Augustin MRamesh VPrasad RGupta NKumar M(2021)Detection of inclusion by using 3D laser scanner in composite prepreg manufacturing technique using convolutional neural networksMachine Vision and Applications10.1007/s00138-021-01241-232:6Online publication date: 1-Nov-2021
https://dl.acm.org/doi/10.1007/s00138-021-01241-2
Yao PShi QHuang HZhang CKhurshid SPăsăreanu C(2020)Fast bit-vector satisfiabilityProceedings of the 29th ACM SIGSOFT International Symposium on Software Testing and Analysis10.1145/3395363.3397378(38-50)Online publication date: 18-Jul-2020
https://dl.acm.org/doi/10.1145/3395363.3397378
Wang BSchneider THu YAttene MPanozzo D(2020)Exact and efficient polyhedral envelope containment checkACM Transactions on Graphics10.1145/3386569.339242639:4(114:1-114:14)Online publication date: 12-Aug-2020
https://dl.acm.org/doi/10.1145/3386569.3392426
Ahmed Sherif MNgonga Ngomo A(2018)A systematic survey of point set distance measures for link discoverySemantic Web10.3233/SW-1702859:5(589-604)Online publication date: 1-Jan-2018
https://dl.acm.org/doi/10.3233/SW-170285
Hu YZhou QGao XJacobson AZorin DPanozzo D(2018)Tetrahedral meshing in the wildACM Transactions on Graphics10.1145/3197517.320135337:4(1-14)Online publication date: 30-Jul-2018
https://dl.acm.org/doi/10.1145/3197517.3201353
Zhang DHe FHan SZou LWu YChen Y(2017)An efficient approach to directly compute the exact Hausdorff distance for 3D point setsIntegrated Computer-Aided Engineering10.3233/ICA-17054424:3(261-277)Online publication date: 1-Jan-2017
https://dl.acm.org/doi/10.3233/ICA-170544
Shi LKong DWang SYin B(2017)Adaptive Geometry Images for RemeshingInternational Journal of Digital Multimedia Broadcasting10.1155/2017/27241842017Online publication date: 1-Jan-2017
https://dl.acm.org/doi/10.1155/2017/2724184
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents