{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,3]],"date-time":"2026-07-03T08:18:36Z","timestamp":1783066716462,"version":"3.54.6"},"reference-count":27,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2026,7,3]],"date-time":"2026-07-03T00:00:00Z","timestamp":1783036800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-nc-nd\/4.0\/legalcode"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Graph."],"published-print":{"date-parts":[[2026,7,3]]},"abstract":"<jats:p>Computing the Hausdorff distance between triangle meshes with guaranteed accuracy is a computationally intensive task. Conventional Branch-and-Bound (B&amp;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.<\/jats:p>\n                  <jats:p>\n                    We introduce\n                    <jats:italic toggle=\"yes\">PQ-Free HD<\/jats:italic>\n                    , a parallel B&amp;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&amp;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.\n                  <\/jats:p>\n                  <jats:p>Evaluations demonstrate substantial speedups: a median of 71.7\u00d7 over the state-of-the-art CPU algorithm on general benchmarks, and exceeding 10,000\u00d7 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&amp;B-based geometric queries on GPUs. Code and data are available at https:\/\/github.com\/huzhihao2001\/pqfree-hd.<\/jats:p>","DOI":"10.1145\/3811324","type":"journal-article","created":{"date-parts":[[2026,7,3]],"date-time":"2026-07-03T07:05:51Z","timestamp":1783062351000},"page":"1-14","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["PQ-Free HD: Priority-Queue-Free Hausdorff Distance for Triangle Meshes on GPU"],"prefix":"10.1145","volume":"45","author":[{"ORCID":"https:\/\/orcid.org\/0009-0002-6041-550X","authenticated-orcid":false,"given":"Zhihao","family":"Hu","sequence":"first","affiliation":[{"name":"University of Science and Technology of China, HEFEI, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8395-4392","authenticated-orcid":false,"given":"Renjie","family":"Chen","sequence":"additional","affiliation":[{"name":"University of Science and Technology of China, HEFEI, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2026,7,3]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICME.2002.1035879"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cagd.2010.04.004"},{"key":"e_1_2_1_3_1","volume-title":"Simplification of surface mesh using Hausdorff envelope. Computer methods in applied mechanics and engineering 194, 48\u201349","author":"Borouchaki Houman","year":"2005","unstructured":"Houman Borouchaki and PJ Frey. 2005. Simplification of surface mesh using Hausdorff envelope. Computer methods in applied mechanics and engineering 194, 48\u201349 (2005), 4864\u20134884."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cad.2010.06.009"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cag.2019.05.019"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1111\/1467-8659.00236"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3680528.3687619"},{"key":"e_1_2_1_8_1","volume-title":"Interactive GPU-based Decimation of Large Meshes. In ACM SIGGRAPH 2023 Talks. 1\u20132.","author":"Gautron Pascal","year":"2023","unstructured":"Pascal Gautron and Christoph Kubisch. 2023. Interactive GPU-based Decimation of Large Meshes. In ACM SIGGRAPH 2023 Talks. 1\u20132."},{"key":"e_1_2_1_9_1","volume-title":"Proc. WSCG. 41\u201348","author":"Guthe Michael","year":"2005","unstructured":"Michael Guthe, Pavel Borodin, and Reinhard Klein. 2005. Fast and accurate Hausdorff distance calculation between meshes. In Proc. WSCG. 41\u201348."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.gmod.2012.05.002"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1002\/cpe.70321"},{"key":"e_1_2_1_12_1","volume-title":"Error-bounded and feature preserving surface remeshing with minimal angle improvement","author":"Hu Kaimo","year":"2016","unstructured":"Kaimo Hu, Dong-Ming Yan, David Bommes, Pierre Alliez, and Bedrich Benes. 2016. Error-bounded and feature preserving surface remeshing with minimal angle improvement. IEEE transactions on visualization and computer graphics 23, 12 (2016), 2560\u20132573."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3197517.3201353"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cagd.2018.03.017"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cag.2019.03.014"},{"key":"e_1_2_1_16_1","volume-title":"RTPD: penetration depth calculation using hardware-accelerated ray-tracing. The Visual Computer","author":"Kim YoungWoo","year":"2025","unstructured":"YoungWoo Kim, Sungmin Kwon, and Duksu Kim. 2025a. RTPD: penetration depth calculation using hardware-accelerated ray-tracing. The Visual Computer (2025), 1\u201315."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1111\/cgf.70229"},{"key":"e_1_2_1_18_1","volume-title":"ABC: A Big CAD Model Dataset For Geometric Deep Learning. In The IEEE Conference on Computer Vision and Pattern Recognition (CVPR).","author":"Koch Sebastian","year":"2019","unstructured":"Sebastian Koch, Albert Matveev, Zhongshi Jiang, Francis Williams, Alexey Artemov, Evgeny Burnaev, Marc Alexa, Denis Zorin, and Daniele Panozzo. 2019. ABC: A Big CAD Model Dataset For Geometric Deep Learning. In The IEEE Conference on Computer Vision and Pattern Recognition (CVPR)."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cad.2011.08.022"},{"key":"e_1_2_1_20_1","unstructured":"Facundo M\u00e9moli. 2007. On the use of Gromov-Hausdorff distances for shape comparison. (2007)."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1111\/cgf.15129"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2015.2408351"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1531326.1531380"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2025.3539729"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cagd.2024.102294"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1111\/cgf.14395"},{"key":"e_1_2_1_27_1","first-page":"3D","article-title":"Thingi10K","volume":"10","author":"Zhou Qingnan","year":"2016","unstructured":"Qingnan Zhou and Alec Jacobson. 2016. Thingi10K: A Dataset of 10,000 3D-Printing Models. arXiv preprint arXiv:1605.04797 (2016).","journal-title":"A Dataset of"}],"container-title":["ACM Transactions on Graphics"],"original-title":[],"language":"en","deposited":{"date-parts":[[2026,7,3]],"date-time":"2026-07-03T07:44:21Z","timestamp":1783064661000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3811324"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,7,3]]},"references-count":27,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2026,7,3]]}},"alternative-id":["10.1145\/3811324"],"URL":"https:\/\/doi.org\/10.1145\/3811324","relation":{},"ISSN":["0730-0301","1557-7368"],"issn-type":[{"value":"0730-0301","type":"print"},{"value":"1557-7368","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,7,3]]},"assertion":[{"value":"2026-01-20","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-03-27","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-07-03","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}