EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

GPU-accelerated Certified Hausdorff Distance Between Triangle Meshes

Haopeng Fan, Min Tang, Leonardo Sacht, Qiang Zou, Ruofeng Tong, Peng Du

ACM Transactions on Graphics · 03.07.2026 · 45 (4) · 1-12

DOI: 10.1145/3811287 ↗

Kurz gefasst

Fachartikel in der Zeitschrift ACM Transactions on Graphics, online erschienen am 03.07.2026. Verfasst von Haopeng Fan und 5 weiteren Autor:innen. Die Arbeit nennt 25 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Computing the directed Hausdorff distance between two triangle meshes is a fundamental operation in geometry processing and simulation. While existing certified branch-and-bound (B&B) methods are efficient for well-separated geometry, they can become prohibitively expensive on large models under tight tolerances and near-zero distance configurations where pruning is limited. We present a GPU-accelerated certified B&B algorithm that explicitly maintains enclosing lower and upper bounds on the directed Hausdorff distance and terminates once their normalized gap, measured with respect to the bounding-box diagonal of the source mesh, meets a user-prescribed tolerance. To map the inherently prioritized search to SIMT (single-instruction, multiple-thread) hardware, we replace priority queues and recursion with a sorted, double-buffered wavefront pipeline built from bulk-parallel worklists for bound evaluation, culling, subdivision, and compaction. To mitigate loose bounds on thin primitives while preserving predictable stream behavior, we introduce a fixed-cardinality adaptive subdivision scheme that selectively applies double longest-edge bisection. To remain robust in deep-refinement regimes, we add a resource-aware deferral mechanism that enforces a device-capacity invariant by prioritizing candidates likely to be culled while postponing expensive ones. Finally, we improve numerical robustness under FP32 (single precision) via triangle-local coordinate transforms and other conservative numerical safeguards, and enhance coherence by spatially ordering the active set and traversing the BVH (bounding volume hierarchy) in triangle packets. Under the same stopping tolerance, experiments on an NVIDIA RTX 5090 show that our GPU solver remains numerically consistent with the FP64 CPU baseline, with normalized cross-platform deviation below 0.01% in over 99.9% of cases. Our method achieves millisecond-scale runtimes capable of supporting interactive frame rates, even on models with millions of triangles. Across the comparison set, it delivers throughput speedups of 836× on the Thingi10K/TetWild benchmark ( A → B ) and 709× on the Thingi10K/Decimation benchmark. Code and data for this paper are available at https://github.com/fhp-transient/gpu-hausdorff.

Zitieren

APA

Fan, H., Tang, M., Sacht, L., Zou, Q., Tong, R., & Du, P. (2026). GPU-accelerated Certified Hausdorff Distance Between Triangle Meshes. ACM Transactions on Graphics, 45(4), 1-12. https://doi.org/10.1145/3811287

Vancouver

Fan H, Tang M, Sacht L, Zou Q, Tong R, Du P. GPU-accelerated Certified Hausdorff Distance Between Triangle Meshes. ACM Transactions on Graphics. 2026;45(4):1-12. doi:10.1145/3811287

BibTeX
@article{Fan2026,
  author = {Fan, Haopeng and Tang, Min and Sacht, Leonardo and Zou, Qiang and Tong, Ruofeng and Du, Peng},
  title = {GPU-accelerated Certified Hausdorff Distance Between Triangle Meshes},
  journal = {ACM Transactions on Graphics},
  year = {2026},
  volume = {45},
  number = {4},
  pages = {1--12},
  doi = {10.1145/3811287}
}
Kostenlos starten →