“Real-time acoustic modeling for distributed virtual environments” by Funkhouser, Min and Carlbom

Realistic acoustic modeling is essential for spatializing sound in distributed virtual environments where multiple networked users move around and interact visually and aurally in a shared virtual world. Unfortunately, current methods for computing accurate acoustical models are not fast enough for real-time auralization of sounds for simultaneously moving sources and receivers. In this paper, we present three new beam tracing algorithms that greatly accelerate computation of reverberation paths in a distributed virtual environment by taking advantage of the fact that sounds can only be generated or heard at the positions of “avatars” representing the users. The priority-driven beam tracing algorithm performs a best first search of a cell adjacency graph, and thus enables new termination criteria with which all early reflection paths can be found very efficiently. The bidirectional beam tracing algorithm combines sets of beams traced from pairs of avatar locations to find reverberation paths between them while requiring significantly less computation than previous unidirectional algorithms. The amortized beam tracing algorithm computes beams emanating from box-shaped regions of space containing predicted avatar locations and re-uses those beams multiple times to compute reflections paths as each avatar moves inside the box. Cumulatively, these algorithms enable speedups of approximately two orders of magnitude over previous methods. They are incorporated into a time-critical multiprocessing system that allocates its computational resources dynamically in order to compute the highest priority reverberation paths between moving avatar locations in real-time with graceful degradation and adaptive refinement.

1. Allen, J.B., and D.A. Berkley, Image Method for Efficiently Simulating Small-Room Acoustics, J. Acoust. Soc. Am., 65, 4, Apr 1979, 943-950.
2. Arvo, James. Backward Ray Tracing. Developments in Ray Tracing Course Notes, SIGGRAPH 86, 1986.
3. Begault, Durand, 3D Sound for Virtual Reality and Multimedia, Academic Press, 1994.
4. Blanchard, C., S. Gurgess, Y. Harvill, J. Lanier, A. Lasko, M. Oberman, and M. Teitel, Reality Built for Two: A Virtual Reality Tool. ACM SIGGRAPH Special Issue on 1990 Symposium on Interactive 3D Graphics, (Snowbird, Utah), 1990, 35-36.
5. Borish, Jeffrey. Extension of the Image Model to Arbitrary Polyhedra. J. Acoust. Soc. Am., 75, 6, June, 1984, 1827-1836.
6. Briere, Normand, and Pierre Poulin, Hierarchical View-Dependent Structures for Interactive Scene Manipulation, Computer Graphics (SIGGRAPH 96), 83-90.
7. Chattopadhyay, Sudeb, and Akira Fujimoto, Bi-directional Ray Tracing, Computer Graphics 1987 (Proceedings of CG International ‘ 87), Springer-Verlag, Tokyo, 1987, 335-343.
8. Dadoun, N., D.G. Kirkpatrick, and J.E Walsh. The Geometry of Beam Tracing. Proceedings of the Symposium on Computational Geometry, Baltimore, June, 1985, 55-61.
9. Davison, B. Neutron Transport Theory. Oxford University Press, London, 1957.
10. Drettakis, George, and Francois Sillion. Interactive Update of Global Illumination Using a Line-Space Hierarchy. Computer Graphics (SIGGRAPH 97), 1997, 57-64.
11. Durlach, N.I., R.W. Pew, W.A. Aviles, EA. DiZio, and D.L. Zeltzer. Virtual Environment Technology for Training (VETT). Report No. 7661, Bolt, Beranek, and Newmann, Cambridge, MA, 1992.
12. Durlach, N.I, and A.S. Mavor, editors, Virtual Reality Scientific and Technological Challenges, National Research Council Report, National Academy Press, Washington, D.C., 1995.
13. Foster, S.H., E.M. Wenzel, and R.M. Taylor. Real-time Synthesis of Complex Acoustic Environments. Proc. IEEE Workshop on Applications of Signal Processing to Audio and Acoustics, 1991.
14. Funkhouser, Thomas A., Ingrid Carlbom, Gary Elko, Gopal Pingali, Mohan Sondhi, and Jim West A Beam Tracing Approach to Acoustic Modeling for Interactive Virtual Environments. Computer Graphics (SIGGRAPH ’98), Orlando, FL, July, 1998, 21-32.
15. Hart, EE., N.J. Nilsson, and B. Raphael, A Formal Basis for the Heuristic Determination of Minimum Cost Paths, IEEE Transactions on SSC, Vol. 4, 1968.
16. Hartman, Jed, Josie Werneck, VRML 2.0 Handbook, Addison-Wesley, ISBN 0-201-47944-3, August 1996.
17. Hartmann, W.M., Listening in a Room and the Precedence Effect, Binaural and Spatial Hearing in Real and Virtual Environments, edited by Robert H. Gilkey and Timothy R. Anderson, Lawrence Erlbaum Associates, 1997.
18. Heckbert, Paul, and Pat Hanrahan. Beam Tracing Polygonal Objects. Computer Graphics (SIGGRAPH 84), 18, 3,119-127.
19. Heckbert, Paul. Adaptive Radiosity Textures for Bidirectional Ray Tracing. Computer Graphics (SIGGRAPH 90), 24, 4, 145-154.
20. Immel, David S., Michael F. Cohen, and Donald E Greenberg. A Radiosity Method for Non-Diffuse Environments. Computer Graphics (SIGGRAPH 85), 19, 3,133-142.
21. Kleiner, Mendel, Bengt-Inge Dalenback, and Peter Svensson. Auralization – An Overview. J. Audio Eng. Soc., 41, 11, Nov 1993, 861- 875.
22. Krockstadt, U.R. Calculating the Acoustical Room Response by the Use of a Ray Tracing Technique, J. Sound and Vibrations, 8, 18, 1968.
23. Kuttruff, Heinrich Room Acoustics, 3rd Edition, Elsevier Science, London, England, 1991.
24. Lafortune, E.E, and Y.D. Willems, Bi-directional path tracing, CompuGraphics, Alvor, Portugal, 1993, 145-153.
25. Lewins, Jeffery. Importance, The Adjoint Function: The Physical Basis of Variational and Perturbation Theory in Transport and Diffusion Problems. Pergamon Press, New York, 1965.
26. Moore, G.R. An Approach to the Analysis of Sound in Auditoria. Ph.D. Thesis, Cambridge, UK, 1984.
27. Quake, id Software, Mesquite, TX, 1996.
28. Smits, Brian, James R. Arvo, and David H. Salesin. An Importance- Driven Radiosity Algorithm. Computer Graphics (SIGGRAPH 92), 26, 2, 273-282.
29. Sony Corporation, Community Place Browser Manual, 1996.
30. Teller, Seth., and Carlo S6quin, Visibility Preprocessing for Interactive Walkthroughs, Computer Graphics (SIGGRAPH 91), 25, 4, 61- 69.
31. Teller, Seth Computing the Antiumbra Cast by an Area Light Source. Computer Graphics (SIGGRAPH 92), 26, 2, 139-148.
32. Teller, Seth Visibility Computations in Densely Occluded Polyhedral Environments. Ph.D. thesis, Computer Science Division (EECS), University of California, Berkeley, 1992. Also available as UC Berkeley technical report UCB/CSD-92-708.
33. Tsingos, Nicolas, and Jean-Dominique Gascuel. A General Model for Simulation of Room Acoustics Based On Hierarchical Radiosity. Technical Sketches, SIGGRAPH 97 Visual Proceedings, 1997.
34. Veach, Eric, and Leonidas Guibas, Bidirectional Estimators for Light Transport, Fifth Eurographics Workshop on Rendering, Darmstadt, Germany, June, 1994, 147-162.
35. Zyda, Michael J., David Pratt, John Falby, Chuck Lombardo, and Kristen Kelleher, The Software Required for the Computer Generation of Virtual Environments. Presence, 2, 2 (March 1993), 130-140.