Cascading Upper Bounds for Triangle Soup Pompeiu-Hausdorff Distance

Sacht, Leonardo; Jacobson, Alec

Cascading Upper Bounds for Triangle Soup Pompeiu-Hausdorff Distance

Files

v43i5_02_cgf15129.pdf (14.8 MB)

paper1044_supp.pdf (158.39 KB)

Date

2024

Authors

Sacht, Leonardo
Jacobson, Alec

Publisher

The Eurographics Association and John Wiley & Sons Ltd.

Abstract

We propose a new method to accurately approximate the Pompeiu-Hausdorff distance from a triangle soup A to another triangle soup B up to a given tolerance. Based on lower and upper bound computations, we discard triangles from A that do not contain the maximizer of the distance to B and subdivide the others for further processing. In contrast to previous methods, we use four upper bounds instead of only one, three of which newly proposed by us. Many triangles are discarded using the simpler bounds, while the most difficult cases are dealt with by the other bounds. Exhaustive testing determines the best ordering of the four upper bounds. A collection of experiments shows that our method is faster than all previous accurate methods in the literature.

CCS Concepts: Computing methodologies → Computer graphics; Mathematics of computing → Mathematical optimization

        @article{10.1111:cgf.15129
,
journal = {Computer Graphics Forum},
title = {{Cascading Upper Bounds for Triangle Soup Pompeiu-Hausdorff Distance
}},
author = {Sacht, Leonardo and 
Jacobson, Alec
},
year = {2024
},
publisher = {The Eurographics Association and John Wiley & Sons Ltd.
},
ISSN = {1467-8659
},
DOI = {10.1111/cgf.15129
}
}