{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,6]],"date-time":"2026-02-06T22:35:47Z","timestamp":1770417347792,"version":"3.49.0"},"reference-count":35,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2021,7,19]],"date-time":"2021-07-19T00:00:00Z","timestamp":1626652800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Graph."],"published-print":{"date-parts":[[2021,8,31]]},"abstract":"<jats:p>In the context of geometric acoustic simulation, one of the more perceptually important yet difficult to simulate acoustic effects is diffraction, a phenomenon that allows sound to propagate around obstructions and corners. A significant bottleneck in real-time simulation of diffraction is the enumeration of high-order diffraction propagation paths in scenes with complex geometry (e.g. highly tessellated surfaces). To this end, we present a dynamic geometric diffraction approach that consists of an extensive mesh preprocessing pipeline and complementary runtime algorithm. The preprocessing module identifies a small subset of edges that are important for diffraction using a novel silhouette edge detection heuristic. It also extends these edges with planar diffraction geometry and precomputes a graph data structure encoding the visibility between the edges. The runtime module uses bidirectional path tracing against the diffraction geometry to probabilistically explore potential paths between sources and listeners, then evaluates the intensities for these paths using the Uniform Theory of Diffraction. It uses the edge visibility graph and the A* pathfinding algorithm to robustly and efficiently find additional high-order diffraction paths. We demonstrate how this technique can simulate 10th-order diffraction up to 568 times faster than the previous state of the art, and can efficiently handle large scenes with both high geometric complexity and high numbers of sources.<\/jats:p>","DOI":"10.1145\/3450626.3459751","type":"journal-article","created":{"date-parts":[[2021,7,20]],"date-time":"2021-07-20T00:04:26Z","timestamp":1626739466000},"page":"1-13","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":14,"title":["Fast diffraction pathfinding for dynamic sound propagation"],"prefix":"10.1145","volume":"40","author":[{"given":"Carl","family":"Schissler","sequence":"first","affiliation":[{"name":"Facebook Reality Labs Research"}]},{"given":"Gregor","family":"M\u00fcckl","sequence":"additional","affiliation":[{"name":"Facebook Reality Labs Research"}]},{"given":"Paul","family":"Calamia","sequence":"additional","affiliation":[{"name":"Facebook Reality Labs Research"}]}],"member":"320","published-online":{"date-parts":[[2021,7,19]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/ASPAA.2005.1540201"},{"key":"e_1_2_2_2_1","first-page":"1","article-title":"Interactive sound propagation with bidirectional path tracing","volume":"35","author":"Cao Chunxiao","year":"2016","unstructured":"Chunxiao Cao , Zhong Ren , Carl Schissler , Dinesh Manocha , and Kun Zhou . 2016 . Interactive sound propagation with bidirectional path tracing . ACM Transactions on Graphics (TOG) 35 , 6 (2016), 1 -- 11 . Chunxiao Cao, Zhong Ren, Carl Schissler, Dinesh Manocha, and Kun Zhou. 2016. Interactive sound propagation with bidirectional path tracing. ACM Transactions on Graphics (TOG) 35, 6 (2016), 1--11.","journal-title":"ACM Transactions on Graphics (TOG)"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2008.111"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/IISA.2015.7388078"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1023\/B:VISI.0000022288.19776.77"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1121\/1.1641020"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/258734.258849"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSSC.1968.300136"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1162\/pres.1996.5.3.290"},{"key":"e_1_2_2_11_1","volume-title":"Hash functions and triangular mesh reconstruction. Computers & geosciences 29, 6","author":"Hradek Jan","year":"2003","unstructured":"Jan Hradek , Martin Kucha\u0159 , and Vaclav Skala . 2003. Hash functions and triangular mesh reconstruction. Computers & geosciences 29, 6 ( 2003 ), 741--751. Jan Hradek, Martin Kucha\u0159, and Vaclav Skala. 2003. Hash functions and triangular mesh reconstruction. Computers & geosciences 29, 6 (2003), 741--751."},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1008653.1008659"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/PROC.1974.9651"},{"key":"e_1_2_2_14_1","volume-title":"Assessing the Plausibility of Virtual Acoustic Environments. Acta Acustica united with Acustica 98, 5","author":"Lindau Alexander","year":"2012","unstructured":"Alexander Lindau and Stefan Weinzierl . 2012. Assessing the Plausibility of Virtual Acoustic Environments. Acta Acustica united with Acustica 98, 5 ( 2012 ), 804--810. Alexander Lindau and Stefan Weinzierl. 2012. Assessing the Plausibility of Virtual Acoustic Environments. Acta Acustica united with Acustica 98, 5 (2012), 804--810."},{"key":"e_1_2_2_15_1","volume-title":"Open Research Content Archive (ORCA). (July","author":"Lumberyard Amazon","year":"2017","unstructured":"Amazon Lumberyard . 2017. Amazon Lumberyard Bistro , Open Research Content Archive (ORCA). (July 2017 ). http:\/\/developer.nvidia.com\/orca\/amazon-lumberyard-bistro Amazon Lumberyard. 2017. Amazon Lumberyard Bistro, Open Research Content Archive (ORCA). (July 2017). http:\/\/developer.nvidia.com\/orca\/amazon-lumberyard-bistro"},{"key":"e_1_2_2_16_1","volume-title":"Computer Graphics Archive. (July","author":"McGuire Morgan","year":"2017","unstructured":"Morgan McGuire . 2017. Computer Graphics Archive. (July 2017 ). https:\/\/casual-effects.com\/data Morgan McGuire. 2017. Computer Graphics Archive. (July 2017). https:\/\/casual-effects.com\/data"},{"key":"e_1_2_2_17_1","volume-title":"Proceedings of 20th International Congress on Acoustics, ICA. 1--7.","author":"Pelzer S\u00f6nke","year":"2010","unstructured":"S\u00f6nke Pelzer and Michael Vorl\u00e4nder . 2010 . Frequency-and time-dependent geometry for real-time auralizations . In Proceedings of 20th International Congress on Acoustics, ICA. 1--7. S\u00f6nke Pelzer and Michael Vorl\u00e4nder. 2010. Frequency-and time-dependent geometry for real-time auralizations. In Proceedings of 20th International Congress on Acoustics, ICA. 1--7."},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1121\/10.0002115"},{"key":"e_1_2_2_19_1","unstructured":"Alexander Pohl. 2014. Simulation of diffraction based on the uncertainty relation. (2014).  Alexander Pohl. 2014. Simulation of diffraction based on the uncertainty relation. (2014)."},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2601097.2601184"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1121\/1.4987164"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2018.2794098"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1121\/1.4926438"},{"key":"e_1_2_2_25_1","volume-title":"AES 41st International Conference: Audio for Games.","author":"Schissler Carl","year":"2011","unstructured":"Carl Schissler and Dinesh Manocha . 2011 . GSound: Interactive sound propagation for games . In AES 41st International Conference: Audio for Games. Carl Schissler and Dinesh Manocha. 2011. GSound: Interactive sound propagation for games. In AES 41st International Conference: Audio for Games."},{"key":"e_1_2_2_26_1","volume-title":"High-order diffraction and diffuse reflections for interactive sound propagation in large environments. ACM Transactions on Graphics (SIGGRAPH 2014) 33, 4","author":"Schissler Carl","year":"2014","unstructured":"Carl Schissler , Ravish Mehra , and Dinesh Manocha . 2014. High-order diffraction and diffuse reflections for interactive sound propagation in large environments. ACM Transactions on Graphics (SIGGRAPH 2014) 33, 4 ( 2014 ), 39. Carl Schissler, Ravish Mehra, and Dinesh Manocha. 2014. High-order diffraction and diffuse reflections for interactive sound propagation in large environments. ACM Transactions on Graphics (SIGGRAPH 2014) 33, 4 (2014), 39."},{"key":"e_1_2_2_27_1","volume-title":"Geometry reduction in room acoustics modeling. Acta Acustica united with Acustica 94, 3","author":"Siltanen Samuel","year":"2008","unstructured":"Samuel Siltanen , Tapio Lokki , Lauri Savioja , and Claus Lynge Christensen . 2008. Geometry reduction in room acoustics modeling. Acta Acustica united with Acustica 94, 3 ( 2008 ), 410--418. Samuel Siltanen, Tapio Lokki, Lauri Savioja, and Claus Lynge Christensen. 2008. Geometry reduction in room acoustics modeling. Acta Acustica united with Acustica 94, 3 (2008), 410--418."},{"key":"e_1_2_2_29_1","volume-title":"An energetic approach for the simulation of diffraction within ray tracing based on the uncertainty relation. Acta Acustica united with Acustica 96, 3","author":"Stephenson Uwe M","year":"2010","unstructured":"Uwe M Stephenson . 2010. An energetic approach for the simulation of diffraction within ray tracing based on the uncertainty relation. Acta Acustica united with Acustica 96, 3 ( 2010 ), 516--535. Uwe M Stephenson. 2010. An energetic approach for the simulation of diffraction within ray tracing based on the uncertainty relation. Acta Acustica united with Acustica 96, 3 (2010), 516--535."},{"key":"e_1_2_2_30_1","unstructured":"Julian Straub Thomas Whelan Lingni Ma Yufan Chen Erik Wijmans Simon Green Jakob J Engel Raul Mur-Artal Carl Ren Shobhit Verma etal 2019. The Replica dataset: A digital replica of indoor spaces. arXiv preprint arXiv:1906.05797 (2019).  Julian Straub Thomas Whelan Lingni Ma Yufan Chen Erik Wijmans Simon Green Jakob J Engel Raul Mur-Artal Carl Ren Shobhit Verma et al. 2019. The Replica dataset: A digital replica of indoor spaces. arXiv preprint arXiv:1906.05797 (2019)."},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1121\/1.428071"},{"key":"e_1_2_2_32_1","doi-asserted-by":"crossref","unstructured":"Micah Taylor Anish Chandak Zhimin Ren Christian Lauterbach and Dinesh Manocha. 2009. Fast edge-diffraction for sound propagation in complex virtual environments. In EAA auralization symposium. Citeseer 15--17.  Micah Taylor Anish Chandak Zhimin Ren Christian Lauterbach and Dinesh Manocha. 2009. Fast edge-diffraction for sound propagation in complex virtual environments. In EAA auralization symposium. Citeseer 15--17.","DOI":"10.1145\/1631272.1631311"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1121\/1.1340647"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/383259.383323"},{"key":"e_1_2_2_35_1","volume-title":"Robust Monte Carlo methods for light transport simulation","author":"Veach Eric","unstructured":"Eric Veach . 1997. Robust Monte Carlo methods for light transport simulation . Vol. 1610 . Stanford University PhD thesis. Eric Veach. 1997. Robust Monte Carlo methods for light transport simulation. Vol. 1610. Stanford University PhD thesis."},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/QoMEX.2016.7498973"},{"key":"e_1_2_2_37_1","first-page":"1","article-title":"Wave-ray coupling for interactive sound propagation in large complex scenes","volume":"32","author":"Yeh Hengchin","year":"2013","unstructured":"Hengchin Yeh , Ravish Mehra , Zhimin Ren , Lakulish Antani , Dinesh Manocha , and Ming Lin . 2013 . Wave-ray coupling for interactive sound propagation in large complex scenes . ACM Transactions on Graphics (TOG) 32 , 6 (2013), 1 -- 11 . Hengchin Yeh, Ravish Mehra, Zhimin Ren, Lakulish Antani, Dinesh Manocha, and Ming Lin. 2013. Wave-ray coupling for interactive sound propagation in large complex scenes. ACM Transactions on Graphics (TOG) 32, 6 (2013), 1--11.","journal-title":"ACM Transactions on Graphics (TOG)"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1121\/1.5040489"}],"container-title":["ACM Transactions on Graphics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3450626.3459751","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3450626.3459751","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:17:16Z","timestamp":1750191436000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3450626.3459751"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,7,19]]},"references-count":35,"aliases":["10.1145\/3476576.3476713"],"journal-issue":{"issue":"4","published-print":{"date-parts":[[2021,8,31]]}},"alternative-id":["10.1145\/3450626.3459751"],"URL":"https:\/\/doi.org\/10.1145\/3450626.3459751","relation":{},"ISSN":["0730-0301","1557-7368"],"issn-type":[{"value":"0730-0301","type":"print"},{"value":"1557-7368","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,7,19]]},"assertion":[{"value":"2021-07-19","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}