Fast and accurate Hausdorff distance calculation between meshes

V. Skala (Editors)
In: Journal of WSCG (Feb. 2005), 13:2(41-48)
Presented at The 13-th International Conference in Central Europe on Computer Graphics, Visualization and Computer Vision 2005 (WSCG'2005)
 

Abstract

Complex models generated e.g. with a laser range scanner often consist of several thousand or million triangles. For efficient rendering this high number of primitives has to be reduced. An important property of mesh reduction - or simplification - algorithms used for rendering is the control over the introduced geometric error. In general, the better this control is, the slower the simplification algorithm becomes. This is especially a problem for out-of-core simplification, since the processing time quickly reaches several hours for high-quality simplification.

In this paper we present a new efficient algorithm to measure the Hausdorff distance between two meshes by sampling the meshes only in regions of high distance. In addition to comparing two arbitrary meshes, this algorithm can also be applied to check the Hausdorff error between the simplified and original meshes during simplification. By using this information to accept or reject a simplification operation, this method allows fast simplification while guaranteeing a user-specified geometric error.

Keywords: Hausdorff error measurement, mesh comparison, mesh simplification

Download Paper

Download Paper

Bibtex

@ARTICLE{guthe-2005-fast,
      author = {Guthe, Michael and Borodin, Pavel and Klein, Reinhard},
      editor = {Skala, V.},
       pages = {41--48},
       title = {Fast and accurate Hausdorff distance calculation between meshes},
     journal = {Journal of WSCG},
      volume = {13},
      number = {2},
        year = {2005},
       month = feb,
   publisher = {UNION Agency-Science Press},
    keywords = {Hausdorff error measurement, mesh comparison, mesh simplification},
    abstract = {Complex models generated e.g. with a laser range scanner often consist of several thousand or
                million triangles. For efficient rendering this high number of primitives has to be reduced. An
                important property of mesh reduction - or simplification - algorithms used for rendering is the
                control over the introduced geometric error. In general, the better this control is, the slower the
                simplification algorithm becomes. This is especially a problem for out-of-core simplification, since
                the processing time quickly reaches several hours for high-quality simplification.
                
                In this paper we present a new efficient algorithm to measure the Hausdorff distance between two
                meshes by sampling the meshes only in regions of high distance. In addition to comparing two
                arbitrary meshes, this algorithm can also be applied to check the Hausdorff error between the
                simplified and original meshes during simplification. By using this information to accept or reject
                a simplification operation, this method allows fast simplification while guaranteeing a
                user-specified geometric error.},
        issn = {1213-6972},
  conference = {The 13-th International Conference in Central Europe on Computer Graphics, Visualization and
                Computer Vision 2005 (WSCG'2005)}
}