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

摘要

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.