GCL学术成果：SIGGRAPH 2026-PQ-Free HD: 面向GPU三角网格的无优先队列豪斯多夫距离算法
近日，SIGGRAPH 2026 接收成果公布，来自中国科学技术大学数学科学学院GCL实验室的陈仁杰研究团队提出了用于高效计算三角网格豪斯多夫距离的GPU并行算法。
背景与问题
量化几何差异是计算机图形学中的基础问题。Hausdorff距离作为评估几何保真度的标准度量，能够严格捕捉最坏情况下的几何偏差，广泛应用于网格简化、重网格化、几何压缩和三维配准等精度关键型任务。
给定两个三角网格A和B，有向Hausdorff距离定义为A上任意点到B表面的最短距离的最大值。尽管公式简单，但对于现代密集镶嵌网格，精确评估在计算上是难以处理的——暴力方法无法随面数增加而扩展。
分支限界（Branch-and-Bound, B&B）框架是平衡计算效率与严格精度的主流范式。现有方法通过层次细分源几何并使用剪枝原语来收敛到有界区间。然而，所有现有方法都依赖全局优先级队列（PQ）进行最优优先调度和终止判断，这造成了根本性的串行瓶颈。在严格容差设置下（如近相同几何），剪枝效率降低导致细分任务组合爆炸，而PQ的频繁全局同步使得这些方法难以映射到GPU的并行架构，导致严重的线程竞争和低SM占用率。
解决方案 我们的核心洞察是：优先级队列的角色可以被解耦。我们发现，任何满足的"边际任务"在指定容差内已不再贡献收敛。通过将剪枝准则从严格的松弛为，这些边际任务可以被立即剪除，从而将算法的终止逻辑与调度顺序解耦——这是消除PQ依赖的关键。
基于这一洞察，PQ-Free HD将传统状态依赖的串行搜索转变为高吞吐量的异步批量处理范式：优先级队列被替换为无竞争环形缓冲区，任务在GPU上完全驻留处理，无需CPU协调。
为应对无PQ调度可能引发的任务膨胀问题，我们设计了三项配套机制：
● 分层GPU执行架构：宏观调度器采用批量深度优先搜索保证数据局部性；微观执行器使用融合协作核函数，将复杂任务处理映射到协作线程组，最小化寄存器压力。
● 紧凑过程化任务表示：利用中点细分的确定性，仅存储29字节描述符（源三角形索引、8位细分层级、96位路径码、三个32位最近三角形索引），执行时实时重建顶点坐标，实现83.9%内存缩减，支持固定140MB显存下的数百万任务并发。
● 几何鲁棒的级联剪枝流水线：在现有级联剪枝基础上新增两项关键测试，解决病态几何挑战（详见技术贡献）。
实验结果
我们在Thingi10K和ABC数据集上进行了广泛验证：
吞吐量优势随问题复杂度超线性增长。
应用：严格误差有界的GPU网格简化
我们已将 PQ-Free HD 作为快速验证验算器集成到 GPU 简化管线中：在每批边折叠时并行评估受影响区域，一旦发现违反用户指定的误差上限就立即回滚。这样可以实现在不超过用户指定Hausdorff 距离误差上界的情况下尽可能简化面数。
技术贡献
在这项工作中，我们的贡献主要包括：
-
无优先级队列的并行B&B范式：首次将全局PQ从Hausdorff距离B&B算法中完全移除，通过松弛剪枝准则解耦终止逻辑与调度顺序，在保持可证明收敛性的同时实现GPU原生大规模并行。
-
分层GPU执行架构：结合批量深度优先调度与融合协作核函数，解决无PQ范式下的任务膨胀与寄存器压力问题。
-
两项几何鲁棒剪枝策略：
● Influence Set Test：利用目标网格的共享拓扑邻域解决边界归属歧义；
● Plane Coverage Test：通过拓扑感知的区域生长验证平面覆盖，将CAD共面簇的指数级搜索转化为有界局部操作。
-
29字节过程化任务描述符：通过路径编码与实时顶点重建，实现83.9%内存缩减，突破VRAM对任务并发的限制。
-
可证明误差有界的 GPU 简化：利用 PQ‑Free HD 作为快速验证核，在边折叠过程中实时回滚超标操作，首次在 GPU 上实现严格 Hausdorff 距离约束的网格简化，将启发式简化变为可控的保真度流程。
论文发表
该工作已被计算机图形学顶会SIGGRAPH 2026接收，发表于ACM Transactions on Graphics。
论文原文
● 论文标题：PQ-Free HD: Priority-Queue-Free Hausdorff Distance for Triangle Meshes on GPU
● 作者：胡智豪，陈仁杰
● 单位：中国科学技术大学