{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,25]],"date-time":"2026-02-25T14:27:52Z","timestamp":1772029672641,"version":"3.50.1"},"reference-count":43,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2023,7,26]],"date-time":"2023-07-26T00:00:00Z","timestamp":1690329600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100012166","name":"National Key R&D Program of China","doi-asserted-by":"crossref","award":["2021YFB1715900"],"award-info":[{"award-number":["2021YFB1715900"]}],"id":[{"id":"10.13039\/501100012166","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["62002190"],"award-info":[{"award-number":["62002190"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["62272277"],"award-info":[{"award-number":["62272277"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["62072284"],"award-info":[{"award-number":["62072284"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100007129","name":"Natural Science Foundation of Shandong Province","doi-asserted-by":"publisher","award":["ZR2020MF036"],"award-info":[{"award-number":["ZR2020MF036"]}],"id":[{"id":"10.13039\/501100007129","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Graph."],"published-print":{"date-parts":[[2023,8]]},"abstract":"<jats:p>\n            Most of the existing point-to-mesh distance query solvers, such as Proximity Query Package (PQP), Embree and Fast Closest Point Query (FCPW), are based on bounding volume hierarchy (BVH). The hierarchical organizational structure enables one to eliminate the vast majority of triangles that do not help find the closest point. In this paper, we develop a totally different algorithmic paradigm, named\n            <jats:italic>P2M<\/jats:italic>\n            , to speed up point-to-mesh distance queries. Our original intention is to precompute a KD tree (KDT) of mesh vertices to approximately encode the geometry of a mesh surface containing vertices, edges and faces. However, it is very likely that the closest primitive to the query point is an edge\n            <jats:italic>e<\/jats:italic>\n            (resp., a face\n            <jats:italic>f<\/jats:italic>\n            ), but the KDT reports a mesh vertex \u03c5 instead. We call \u03c5 an\n            <jats:italic>interceptor<\/jats:italic>\n            of\n            <jats:italic>e<\/jats:italic>\n            (resp.,\n            <jats:italic>f<\/jats:italic>\n            ). The main contribution of this paper is to invent a simple yet effective interception inspection rule and an efficient flooding interception inspection algorithm for quickly finding out all the interception pairs. Once the KDT and the interception table are precomputed, the query stage proceeds by first searching the KDT and then looking up the interception table to retrieve the closest geometric primitive. Statistics show that our query algorithm runs many times faster than the state-of-the-art solvers.\n          <\/jats:p>","DOI":"10.1145\/3592439","type":"journal-article","created":{"date-parts":[[2023,7,26]],"date-time":"2023-07-26T14:29:21Z","timestamp":1690381761000},"page":"1-13","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":12,"title":["P2M: A Fast Solver for Querying Distance from Point to Mesh Surface"],"prefix":"10.1145","volume":"42","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4954-0780","authenticated-orcid":false,"given":"Chen","family":"Zong","sequence":"first","affiliation":[{"name":"Shandong University, Qingdao, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0008-2855-7405","authenticated-orcid":false,"given":"Jiacheng","family":"Xu","sequence":"additional","affiliation":[{"name":"Shandong University, Qingdao, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0007-0907-3731","authenticated-orcid":false,"given":"Jiantao","family":"Song","sequence":"additional","affiliation":[{"name":"Shandong University, Qingdao, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0835-3316","authenticated-orcid":false,"given":"Shuangmin","family":"Chen","sequence":"additional","affiliation":[{"name":"Qingdao University of Science and Technology, Qingdao, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8452-8723","authenticated-orcid":false,"given":"Shiqing","family":"Xin","sequence":"additional","affiliation":[{"name":"Shandong University, Qingdao, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2284-3952","authenticated-orcid":false,"given":"Wenping","family":"Wang","sequence":"additional","affiliation":[{"name":"Texas A&amp;M University, Texas, United States of America"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1231-3392","authenticated-orcid":false,"given":"Changhe","family":"Tu","sequence":"additional","affiliation":[{"name":"Shandong University, Qingdao, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,7,26]]},"reference":[{"key":"e_1_2_2_1_1","article-title":"A survey on nearest neighbor search methods","volume":"95","author":"Abbasifard Mohammad Reza","year":"2014","unstructured":"Mohammad Reza Abbasifard, Bijan Ghahremani, and Hassan Naderi. 2014. A survey on nearest neighbor search methods. International Journal of Computer Applications 95, 25 (2014).","journal-title":"International Journal of Computer Applications"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897839.2927450"},{"key":"e_1_2_2_3_1","volume-title":"Computer Graphics Forum","author":"Auer Stefan","unstructured":"Stefan Auer and R\u00fcdiger Westermann. 2013. A semi-Lagrangian closest point method for deforming surfaces. In Computer Graphics Forum, Vol. 32. Wiley Online Library, 207--214."},{"key":"e_1_2_2_4_1","volume-title":"Joseph SB Mitchell, and Ayellet Tal","author":"Barequet Gill","year":"1996","unstructured":"Gill Barequet, Bernard Chazelle, Leonidas J Guibas, Joseph SB Mitchell, and Ayellet Tal. 1996. BOXTREE: A hierarchical representation for surfaces in 3D. In Computer Graphics Forum, Vol. 15. Wiley Online Library, 387--396."},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/93597.98741"},{"key":"e_1_2_2_6_1","volume-title":"The X-tree: An index structure for high-dimensional data. In Very Large Data-Bases. 28--39.","author":"Berchtold Stefan","year":"1996","unstructured":"Stefan Berchtold, Daniel A Keim, and Hans-Peter Kriegel. 1996. The X-tree: An index structure for high-dimensional data. In Very Large Data-Bases. 28--39."},{"key":"e_1_2_2_7_1","unstructured":"CGAL. 2022. The Computational Geometry Algorithms Library. https:\/\/www.cgal.org\/."},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2007.70405"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2004.02.002"},{"key":"e_1_2_2_10_1","volume-title":"Computer Graphics Forum","author":"Ehmann Stephen A","unstructured":"Stephen A Ehmann and Ming C Lin. 2001. Accurate and fast proximity queries between polyhedra using convex surface decomposition. In Computer Graphics Forum, Vol. 20. Wiley Online Library, 500--511."},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/MCG.2006.17"},{"key":"e_1_2_2_12_1","unstructured":"Geogram. 2020. A programming library of geometric algorithms. http:\/\/alice.loria.fr\/software\/geogram\/doc\/html\/index.html."},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/237170.237244"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/2945.910820"},{"key":"e_1_2_2_15_1","first-page":"803","article-title":"Zonotopes as bounding volumes","volume":"3","author":"Guibas Leonidas J","year":"2003","unstructured":"Leonidas J Guibas, An Thanh Nguyen, and Li Zhang. 2003. Zonotopes as bounding volumes. In SODA, Vol. 3. 803--812.","journal-title":"SODA"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/602259.602266"},{"key":"e_1_2_2_17_1","unstructured":"Herman J Haverkort. 2004. Introduction to bounding volume hierarchies. Part of the PhD thesis Utrecht University (2004)."},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/166117.166119"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/2945.466717"},{"key":"e_1_2_2_20_1","volume-title":"Hilbert R-tree: An improved R-tree using fractals. Technical Report.","author":"Kamel Ibrahim","year":"1993","unstructured":"Ibrahim Kamel and Christos Faloutsos. 1993. Hilbert R-tree: An improved R-tree using fractals. Technical Report."},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/253262.253347"},{"key":"e_1_2_2_22_1","volume-title":"Computer Graphics Forum","author":"Kavan Ladislav","unstructured":"Ladislav Kavan and Ji\u0159\u00ed \u017d\u00e1ra. 2005. Fast collision detection for skeletally deformable models. In Computer Graphics Forum, Vol. 24. Blackwell Publishing, Inc Oxford, UK and Boston, USA, 363--372."},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/2945.675649"},{"key":"e_1_2_2_24_1","unstructured":"E. Scott Larsen Stefan Gottschalk Ming C. Lin and Dinesh Manocha. 1999. Fast Proximity Queries with Swept Sphere Volumes."},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cag.2006.02.011"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2019.2909204"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/TASE.2010.2066563"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1236246.1236289"},{"key":"e_1_2_2_29_1","article-title":"New Algorithms for Efficient High-Dimensional Nonparametric Classification","volume":"7","author":"Liu Ting","year":"2006","unstructured":"Ting Liu, Andrew W Moore, Alexander Gray, and Claire Cardie. 2006. New Algorithms for Efficient High-Dimensional Nonparametric Classification. Journal of Machine Learning Research 7, 6 (2006).","journal-title":"Journal of Machine Learning Research"},{"key":"e_1_2_2_30_1","volume-title":"A Survey on Bounding","author":"Meister Daniel","unstructured":"Daniel Meister, Shinji Ogaki, Carsten Benthin, Michael J Doyle, Michael Guthe, and Ji\u0159\u00ed Bittner. 2021. A Survey on Bounding Volume Hierarchies for Ray Tracing. In Computer Graphics Forum, Vol. 40. Wiley Online Library, 683--712."},{"key":"e_1_2_2_31_1","volume-title":"Grimsdale","author":"Palmer Ian J.","year":"1995","unstructured":"Ian J. Palmer and Richard L. Grimsdale. 1995. Collision detection for animation using sphere-trees. In Computer Graphics Forum, Vol. 14. Wiley Online Library, 105--116."},{"key":"e_1_2_2_32_1","volume-title":"The Study of Parallel Collision Detection Algorithms. In 2010 International Conference on Multimedia Technology. IEEE, 1--4.","author":"Ruipu Tan","year":"2010","unstructured":"Tan Ruipu, Zhao Wei, and Li Jing. 2010. The Study of Parallel Collision Detection Algorithms. In 2010 International Conference on Multimedia Technology. IEEE, 1--4."},{"key":"e_1_2_2_33_1","volume-title":"VLDB","volume":"2000","author":"Sakurai Yasushi","year":"2000","unstructured":"Yasushi Sakurai, Masatoshi Yoshikawa, Shunsuke Uemura, Haruhiko Kojima, et al. 2000. The A-tree: An index structure for high-dimensional spaces using relative approximation. In VLDB, Vol. 2000. Citeseer, 5--16."},{"key":"e_1_2_2_34_1","volume-title":"FCPW: Fastest Closest Points in the West. https:\/\/github.com\/rohan-sawhney\/fcpw.","author":"Sawhney Rohan","year":"2021","unstructured":"Rohan Sawhney. 2021. FCPW: Fastest Closest Points in the West. https:\/\/github.com\/rohan-sawhney\/fcpw."},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920994"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/2629697"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/1944745.1944756"},{"key":"e_1_2_2_38_1","unstructured":"Ingo Wald Will Usher Nathan Morrical Laura Lediaev and Valerio Pascucci. 2019. RTX Beyond Ray Tracing: Exploring the Use of Hardware Ray Tracing Cores for Tet-Mesh Point Location.. In High Performance Graphics (Short Papers). 7--13."},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1108\/RPJ-02-2012-0013"},{"key":"e_1_2_2_40_1","volume-title":"A review of collision detection for deformable objects. Computer Animation and Virtual Worlds","author":"Wang Monan","year":"2021","unstructured":"Monan Wang and Jiaqi Cao. 2021. A review of collision detection for deformable objects. Computer Animation and Virtual Worlds (2021), e1987."},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.5555\/645481.655573"},{"key":"e_1_2_2_42_1","first-page":"1","article-title":"BVH split strategies for fast distance queries","volume":"4","author":"Ytterlid Robin","year":"2015","unstructured":"Robin Ytterlid and Evan Shellshear. 2015. BVH split strategies for fast distance queries. Journal of Computer Graphics Techniques (JCGT) 4, 1 (2015), 1--25.","journal-title":"Journal of Computer Graphics Techniques (JCGT)"},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.48550\/ARXIV.1605.04797"}],"container-title":["ACM Transactions on Graphics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3592439","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3592439","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T17:48:59Z","timestamp":1750182539000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3592439"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,7,26]]},"references-count":43,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2023,8]]}},"alternative-id":["10.1145\/3592439"],"URL":"https:\/\/doi.org\/10.1145\/3592439","relation":{},"ISSN":["0730-0301","1557-7368"],"issn-type":[{"value":"0730-0301","type":"print"},{"value":"1557-7368","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,7,26]]},"assertion":[{"value":"2023-07-26","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}