EUVIMEDEUVIMED entdecken
Open Access · CC BY-NC-ND 4.0

PQ-Free HD: Priority-Queue-Free Hausdorff Distance for Triangle Meshes on GPU

Zhihao Hu, Renjie Chen

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

DOI: 10.1145/3811324 ↗

Kurz gefasst

Fachartikel in der Zeitschrift ACM Transactions on Graphics, online erschienen am 03.07.2026. Verfasst von Zhihao Hu und 1 weiteren Autor:innen. Die Arbeit nennt 27 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY-NC-ND 4.0).

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Computing the Hausdorff distance between triangle meshes with guaranteed accuracy is a computationally intensive task. Conventional Branch-and-Bound (B&B) approaches are fundamentally ill-suited for massive parallelism. Their reliance on a global priority queue (PQ) for both best-first scheduling and global termination checks creates a serial bottleneck that prevents scalable performance. We introduce PQ-Free HD , a parallel B&B framework that eliminates this dependency by decoupling the algorithm's termination logic from its scheduling order. This is achieved by relaxing the culling criterion, thereby replacing the priority queue with a contention-free ring buffer, which transforms the execution model from a state-dependent serial search into a high-throughput, asynchronous batch-processing paradigm. The framework consists of four key components: (1) a parallel priority-queue-free B&B paradigm; (2) a hierarchical GPU execution architecture combining batched depth-first scheduling with fused collaborative kernels; (3) a geometrically robust seven-stage culling pipeline featuring novel tests for challenging geometries; and (4) a compact 29-byte procedural task descriptor that achieves an 83.9% memory reduction. Evaluations demonstrate substantial speedups: a median of 71.7× over the state-of-the-art CPU algorithm on general benchmarks, and exceeding 10,000× on challenging CAD models with dense planar structures. The throughput advantage scales super-linearly with problem complexity. We showcase practical value by building a strictly Hausdorff-distance-bounded mesh simplification tool entirely on the GPU. Our work provides a new method for high-throughput, tolerance-controllable B&B-based geometric queries on GPUs. Code and data are available at https://github.com/huzhihao2001/pqfree-hd.

Zitieren

APA

Hu, Z., & Chen, R. (2026). PQ-Free HD: Priority-Queue-Free Hausdorff Distance for Triangle Meshes on GPU. ACM Transactions on Graphics, 45(4), 1-14. https://doi.org/10.1145/3811324

Vancouver

Hu Z, Chen R. PQ-Free HD: Priority-Queue-Free Hausdorff Distance for Triangle Meshes on GPU. ACM Transactions on Graphics. 2026;45(4):1-14. doi:10.1145/3811324

BibTeX
@article{Hu2026,
  author = {Hu, Zhihao and Chen, Renjie},
  title = {PQ-Free HD: Priority-Queue-Free Hausdorff Distance for Triangle Meshes on GPU},
  journal = {ACM Transactions on Graphics},
  year = {2026},
  volume = {45},
  number = {4},
  pages = {1--14},
  doi = {10.1145/3811324}
}
Kostenlos starten →