{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,18]],"date-time":"2026-09-18T08:36:37Z","timestamp":1789720597755,"version":"4.0.1"},"reference-count":25,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2016,7,11]],"date-time":"2016-07-11T00:00:00Z","timestamp":1468195200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Hong Kong Research Grants Council","award":["HKU718712"],"award-info":[{"award-number":["HKU718712"]}]},{"name":"European Commission Horizon 2020","award":["691215"],"award-info":[{"award-number":["691215"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Graph."],"published-print":{"date-parts":[[2016,7,11]]},"abstract":"<jats:p>Computing discrete geodesic distance over triangle meshes is one of the fundamental problems in computational geometry and computer graphics. In this problem, an effective window pruning strategy can significantly affect the actual running time. Due to its importance, we conduct an in-depth study of window pruning operations in this paper, and produce an exhaustive list of scenarios where one window can make another window partially or completely redundant. To identify a maximal number of redundant windows using such pairwise cross checking, we propose a set of procedures to synchronize local window propagation within the same triangle by simultaneously propagating a collection of windows from one triangle edge to its two opposite edges. On the basis of such synchronized window propagation, we design a new geodesic computation algorithm based on a triangle-oriented region growing scheme. Our geodesic algorithm can remove most of the redundant windows at the earliest possible stage, thus significantly reducing computational cost and memory usage at later stages. In addition, by adopting triangles instead of windows as the primitive in propagation management, our algorithm significantly cuts down the data management overhead. As a result, it runs 4--15 times faster than MMP and ICH algorithms, 2-4 times faster than FWP-MMP and FWP-CH algorithms, and also incurs the least memory usage.<\/jats:p>","DOI":"10.1145\/2897824.2925930","type":"journal-article","created":{"date-parts":[[2016,7,11]],"date-time":"2016-07-11T12:04:33Z","timestamp":1468238673000},"page":"1-13","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":61,"title":["Fast and exact discrete geodesic computation based on triangle-oriented wavefront propagation"],"prefix":"10.1145","volume":"35","author":[{"given":"Yipeng","family":"Qin","sequence":"first","affiliation":[{"name":"Bournemouth University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Xiaoguang","family":"Han","sequence":"additional","affiliation":[{"name":"The University of Hong Kong"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Hongchuan","family":"Yu","sequence":"additional","affiliation":[{"name":"Bournemouth University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yizhou","family":"Yu","sequence":"additional","affiliation":[{"name":"The University of Hong Kong"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jianjun","family":"Zhang","sequence":"additional","affiliation":[{"name":"Bournemouth University"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2016,7,11]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2008.213"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2011.05.006"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0508601103"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/98524.98601"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2516971.2516977"},{"key":"e_1_2_2_6_1","doi-asserted-by":"crossref","unstructured":"Kimmel R. and Sethian J. A. 1998. Computing geodesic paths on manifolds. In Proc. Natl. Acad. Sci. USA 8431--8435.  Kimmel R. and Sethian J. A. 1998. Computing geodesic paths on manifolds. In Proc. Natl. Acad. Sci. USA 8431--8435.","DOI":"10.1073\/pnas.95.15.8431"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2010.221"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2816795.2818076"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cad.2012.11.005"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/511920.511936"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/S003613990342877X"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/0216045"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11263-006-6859-3"},{"key":"e_1_2_2_14_1","doi-asserted-by":"crossref","unstructured":"Schreiber Y. and Sharir M. 2009. An optimal-time algorithm for shortest paths on a convex polytope in three dimensions. In Twentieth Anniversary Volume:. Springer 1--80.  Schreiber Y. and Sharir M. 2009. An optimal-time algorithm for shortest paths on a convex polytope in three dimensions. In Twentieth Anniversary Volume: . Springer 1--80.","DOI":"10.1007\/978-0-387-87363-3_27"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.93.4.1591"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1073204.1073228"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559755.1559761"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2159616.2159622"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2015.2407404"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcp.2005.08.005"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00371-015-1071-5"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2461466.2461488"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2508363.2508379"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2534161"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2461912.2461946"}],"container-title":["ACM Transactions on Graphics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2897824.2925930","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2897824.2925930","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T00:55:04Z","timestamp":1750208104000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2897824.2925930"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,7,11]]},"references-count":25,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2016,7,11]]}},"alternative-id":["10.1145\/2897824.2925930"],"URL":"https:\/\/doi.org\/10.1145\/2897824.2925930","relation":{},"ISSN":["0730-0301","1557-7368"],"issn-type":[{"value":"0730-0301","type":"print"},{"value":"1557-7368","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,7,11]]},"assertion":[{"value":"2016-07-11","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}