“Fast diffraction pathfinding for dynamic sound propagation” by Schissler, Mückl and Calamia

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.

1. Paul T Calamia and U Peter Svensson. 2005. Edge subdivision for fast diffraction calculations. In IEEE Workshop on Applications of Signal Processing to Audio and Acoustics, 2005. IEEE, 187–190.Google ScholarCross Ref
2. 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.Google ScholarDigital Library
3. Anish Chandak, Christian Lauterbach, Micah Taylor, Zhimin Ren, and Dinesh Manocha. 2008. Ad-frustum: Adaptive frustum tracing for interactive sound propagation. IEEE Transactions on Visualization and Computer Graphics 14, 6 (2008), 1707–1722.Google ScholarDigital Library
4. Brent Cowan and Bill Kapralos. 2015. Interactive rate acoustical occlusion/diffraction modeling for 2D virtual environments & games. In 2015 6th International Conference on Information, Intelligence, Systems and Applications (IISA). IEEE, 1–6.Google ScholarCross Ref
5. Pedro F Felzenszwalb and Daniel P Huttenlocher. 2004. Efficient graph-based image segmentation. International journal of computer vision 59, 2 (2004), 167–181.Google ScholarDigital Library
6. Thomas Funkhouser, Nicolas Tsingos, Ingrid Carlbom, Gary Elko, Mohan Sondhi, James E West, Gopal Pingali, Patrick Min, and Addy Ngan. 2004. A beam tracing method for interactive architectural acoustics. The Journal of the acoustical society of America 115, 2 (2004), 739–756.Google ScholarCross Ref
7. Michael Garland and Paul S Heckbert. 1997. Surface simplification using quadric error metrics. In Proceedings of the 24th annual conference on Computer graphics and interactive techniques. 209–216.Google ScholarDigital Library
8. Iliyan Georgiev. 2012. Implementing vertex connection and merging. Technical Report. Saarland University (2012).Google Scholar
9. Peter E Hart, Nils J Nilsson, and Bertram Raphael. 1968. A formal basis for the heuristic determination of minimum cost paths. IEEE transactions on Systems Science and Cybernetics 4, 2 (1968), 100–107.Google ScholarCross Ref
10. Claudia Hendrix and Woodrow Barfield. 1996. The sense of presence within auditory virtual environments. Presence: Teleoperators & Virtual Environments 5, 3 (1996), 290–301.Google ScholarDigital Library
11. Jan Hradek, Martin Kuchař, and Vaclav Skala. 2003. Hash functions and triangular mesh reconstruction. Computers & geosciences 29, 6 (2003), 741–751.Google Scholar
12. Chris Joslin and Nadia Magnenat-Thalmann. 2003. Significant facet retrieval for realtime 3d sound rendering in complex virtual environments. In Proceedings of the ACM symposium on Virtual reality software and technology. 15–21.Google ScholarDigital Library
13. Robert G Kouyoumjian and Prabhakar H Pathak. 1974. A uniform geometrical theory of diffraction for an edge in a perfectly conducting surface. Proc. IEEE 62, 11 (1974), 1448–1461.Google ScholarCross Ref
14. Alexander Lindau and Stefan Weinzierl. 2012. Assessing the Plausibility of Virtual Acoustic Environments. Acta Acustica united with Acustica 98, 5 (2012), 804–810.Google Scholar
15. Amazon Lumberyard. 2017. Amazon Lumberyard Bistro, Open Research Content Archive (ORCA). (July 2017). http://developer.nvidia.com/orca/amazon-lumberyard-bistroGoogle Scholar
16. Morgan McGuire. 2017. Computer Graphics Archive. (July 2017). https://casual-effects.com/dataGoogle Scholar
17. Sönke Pelzer and Michael Vorländer. 2010. Frequency-and time-dependent geometry for real-time auralizations. In Proceedings of 20th International Congress on Acoustics, ICA. 1–7.Google Scholar
18. Louis Pisha, Siddharth Atre, John Burnett, and Shahrokh Yadegari. 2020. Approximate diffraction modeling for real-time sound propagation simulation. The Journal of the Acoustical Society of America 148, 4 (2020), 1922–1933.Google ScholarCross Ref
19. Alexander Pohl. 2014. Simulation of diffraction based on the uncertainty relation. (2014).Google Scholar
20. Nikunj Raghuvanshi and John Snyder. 2014. Parametric wave field coding for pre-computed sound propagation. ACM Transactions on Graphics (TOG) 33, 4 (2014), 1–11.Google ScholarDigital Library
21. Nikunj Raghuvanshi, John Tennant, and John Snyder. 2017. Triton: Practical pre-computed sound propagation for games and virtual reality. The Journal of the Acoustical Society of America 141, 5 (2017), 3455–3455.Google ScholarCross Ref
22. Atul Rungta, Carl Schissler, Nicholas Rewkowski, Ravish Mehra, and Dinesh Manocha. 2018. Diffraction kernels for interactive sound propagation in dynamic environments. IEEE transactions on visualization and computer graphics 24, 4 (2018), 1613–1622.Google ScholarDigital Library
23. Lauri Savioja and U Peter Svensson. 2015. Overview of geometrical room acoustic modeling techniques. The Journal of the Acoustical Society of America 138, 2 (2015), 708–730.Google ScholarCross Ref
24. Carl Schissler. 2017. Efficient Interactive Sound Propagation in Dynamic Environments. PhD thesis, UNC Chapel Hill.Google Scholar
25. Carl Schissler and Dinesh Manocha. 2011. GSound: Interactive sound propagation for games. In AES 41st International Conference: Audio for Games.Google Scholar
26. 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.Google Scholar
27. 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.Google Scholar
28. Uwe M Stephenson. 2004. Beugungssimulation ohne Rechenzeitexplosion: die Methode der quantisierten Pyramidenstrahlen. PhD thesis, RWTH Aachen.Google Scholar
29. 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.Google Scholar
30. 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).Google Scholar
31. U Peter Svensson, Roger I Fred, and John Vanderkooy. 1999. An analytic secondary source model of edge diffraction impulse responses. The Journal of the Acoustical Society of America 106, 5 (1999), 2331–2344.Google ScholarCross Ref
32. 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.Google Scholar
33. Rendell R Torres, U Peter Svensson, and Mendel Kleiner. 2001. Computation of edge diffraction for more accurate room acoustics auralization. The Journal of the Acoustical Society of America 109, 2 (2001), 600–610.Google ScholarCross Ref
34. Nicolas Tsingos, Thomas Funkhouser, Addy Ngan, and Ingrid Carlbom. 2001. Modeling acoustics in virtual environments using the Uniform Theory of Diffraction. In Proceedings of the 28th annual conference on Computer graphics and interactive techniques. ACM, 545–552.Google ScholarDigital Library
35. Eric Veach. 1997. Robust Monte Carlo methods for light transport simulation. Vol. 1610. Stanford University PhD thesis.Google ScholarDigital Library
36. Stephan Werner, Florian Klein, Thomas Mayenfels, and Karlheinz Brandenburg. 2016. A summary on acoustic room divergence and its effect on externalization of auditory events. In 2016 Eighth International Conference on Quality of Multimedia Experience (QoMEX). IEEE, 1–6.Google ScholarCross Ref
37. 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.Google ScholarDigital Library
38. Markus Zaunschirm, Christian Schörkhuber, and Robert Höldrich. 2018. Binaural rendering of ambisonic signals by head-related impulse response time alignment and a diffuseness constraint. The Journal of the Acoustical Society of America 143, 6 (2018), 3616–3627.Google ScholarCross Ref