“A beam tracing approach to acoustic modeling for interactive virtual environments” by Funkhouser, Carlbom, Elko, Pingali, Sondhi, et al. …

Virtual environment research has focused on interactive image generation and has largely ignored acoustic modeling for spatialization of sound. Yet, realistic auditory cues can complement and enhance visual cues to aid navigation, comprehension, and sense of presence in virtual environments. A primary challenge in acoustic modeling is computation of reverberation paths from sound sources fast enough for real-time auralization. We have developed a system that uses precomputed spatial subdivision and “beam tree” data structures to enable real-time acoustic modeling and auralization in interactive virtual environments. The spatial subdivision is a partition of 3D space into convex polyhedral regions (cells) represented as a cell adjacency graph. A beam tracing algorithm recursively traces pyramidal beams through the spatial subdivision to construct a beam tree data structure representing the regions of space reachable by each potential sequence of transmission and specular reflection events at cell boundaries. From these precomputed data structures, we can generate high-order specular reflection and transmission paths at interactive rates to spatialize fixed sound sources in real-time as the user moves through a virtual environment. Unlike previous acoustic modeling work, our beam tracing method: 1) supports evaluation of reverberation paths at interactive rates, 2) scales to compute high-order reflections and large environments, and 3) extends naturally to compute paths of diffraction and diffuse reflection efficiently. We are using this system to develop interactive applications in which a user experiences a virtual environment immersively via simultaneous auralization and visualization.

1. Ahnert, Wolfgang. EARS Auralization Software. J. Audio Eng. Soc., 41, 11, November, 1993,894-904.
2. Allen, J.B., Berkley, D.A. Image Method for Efficiently Simulating Small-Room Acoustics, J. Acoust. Soc. Am., 65, 4, April, 1979, 943-951.
3. Amanatides, J. Ray Tracing with Cones. Computer Graphics (SIGGRAPH 84). 18, 3,129-135.
4. Arvo, J. and D. Kirk. A Survey of Ray Tracing Acceleration Techniques. in An Introduction to Ray Tracing, Andrew Glassner editor, Academic Press, San Diego, CA, 1989.
5. Baumgart, Bruce G. Winged Edge Polyhedlvn Representation. Ph.D. Thesis, Computer Science Department, Stanford University, 1972.
6. Borish, Jeffrey. Extension of the Image Model to Arbitrary Polyhedra. J. Acoust. Soc.Am., 75, 6, June, 1984, 1827-1836.
7. Bose Modeler, Bose Corporation, Framingham, MA. http://www.bose.com.
8. CATT-Acoustic, CATT, Gothenburg, Sweden, http://www.netg.se/catt.
9. Chuang, J.H. and S.A. Cheng. Computing caustic effects by backward beam tracing. The Visual Computer, 11, 3, 1995, 156-166.
10. Cook, Robert, L., Thomas Porter, and Loren Carpenter. Distributed Ray Tracing. Computer Graphics (SIGGRAPH 84). 18, 3,137-146.
11. D’Antonio, Peter, and John Konnert. The Directional Scattering Coefficient: Experimental Determination. J, Audio Eng. Soc., 40, 12, December, 1992,997- 1017.
12. Dadoun, N., D.G. Kirkpatrick, and J.R Walsh. Hierarchical Approaches to Hidden Surface Intersection Testing. Graphics Intelface ’82, Toronto, Canada, May, 1982, 49-56.
13. Dadoun, N., D.G. Kirkpatrick, and J.R Walsh. The Geometry of Beam Tracing. P~vceedings of the Symposium on Computational Geometry, Baltimore, June, 1985, 55-71.
14. Durlach, N.I., R.W. Pew, W.A. Aviles, RA. DiZio, and D.L. Zeltzer. Virtual Envilvnment Technology for Training (VETT). Report No. 7661, Bolt, Beranek, and Newmann, Cambridge, MA, 1992.
15. Durlach, N.I, and A.S. Mavor, editors, VirtuaIReality Scientific and Technological Challenges, National Research Council Report, National Academy Press, Washington, D.C., 1995.
16. Fortune, Steve. Algorithms for Prediction of Indoor Radio Propagation. Technical Memorandum, Document #11274-960117-03TM, Bell Laboratories, 1996. A partial version of this paper appears in Applied Computational Geometry, Towards Geometric Engineering, proceedings of the FCRC ’96 Workshop in conjunction with WACG ’96, Philadelphia, PA, May, 1996, 157-166.
17. Foster, S.H., E.M. Wenzel, and R.M. Taylor. Real-time Synthesis of Complex Acoustic Environments. P~vceedings of the IEEE Workshop on Applications of Signal P~vcessing to Audio andAcoustics, New Paltz, NY, 1991.
18. Fuchs, H. Kedem, Z., and Naylor, B. On Visible Surface Generation by a Priori Tree Structures. Computer Graphics (Proc. SIGGRAPH ’80), 124-133.
19. Fujomoto, Akira. Turbo Beam Tracing – A Physically Accurate Lighting Simulation Environment. Knowledge Based Image Computing Systems, May, 1988, 1-5.
20. Ghazanfarpour, G. and J. Marc Hasenfratz. A Beam Tracing with Precise Antialiasing for Polyhedral Scenes. Computer & Graphics, 22, 1, 1998.
21. Goral, Cindy M., Kenneth E. Torrance, Donald R Greenberg, and Bennett Battaile. Modeling the Interaction of Light Between Diffuse Surfaces. Computer Graphics (Proc. SIGGRAPH ’84), 18, 3, July, 1984, 213-222.
22. Haines, Eric A. Beams O’ Light: Confessions of a Hacker. Frontiers in Rendering Course Notes, SIGGRAPH’ 91, 1991.
23. Heckbert, Paul, and Pat Hanrahan. Beam Tracing Polygonal Objects. Computer Graphics (SIGGRAPH 84), 18, 3, 119-127.
24. Heckbert, Paul. Adaptive Radiosity Textures for Bidirectional Ray Tracing. Computer Graphics (SIGGRAPH 90), 24, 4, 145-154.
25. Heinz, R. Binaural Room Simulation Based on an Image Source Model with Addition of Statistical Methods to Include the Diffuse Sound Scattering of Walls and to Predict the Reverberant Tail J. Applied Acoustics, 38, 2-4,1993,145-160.
26. Hodgson, M. Evidence of Diffuse Surface Reflections in Rooms. J. Acoust. Soc. Am., 89, 1991,765-771.
27. Jones, C.B. A New Approach to the ‘Hidden Line’ Problem. The Computer Journal, 14, 3 (August 1971), 232-237.
28. Kajiya, James T. The Rendering Equation. Computer Graphics (SIGGRAPH 86), 143-150.
29. Keller, Joseph B. Geometrical Theory of Diffraction. Journal of the Optical Society of America, 52, 2, February, 1962,116-130.
30. Kleiner, Mendel, Bengt-Inge Dalenback, and Peter Svensson. Auralization- An Overview. J. Audio Eng. Soc., 41, 11, November, 1993, 861-875.
31. Kreuzgruber, R, R Unterberger, and R. Gahleitner. A Ray Splitting Model for Indoor Radio Propagation Associated with Complex Geometries. P~vceedings of the 1993 43rd IEEE Vehicular Technology Conference, 1993,227-230.
32. Kristiansen, U.R., A. Krokstad, and T. Follestad. Extending the Image Method to Higher-Order Reflections. J. Applied Acoustics, 38, 2-4, 1993,195-206.
33. Krockstadt, U.R. Calculating the Acoustical Room Response by the Use of a Ray Tracing Technique, J. Sound and Vibrations, 8, 18, 1968.
34. Kuttruff, Heinrich Room Acoustics, 3rd Edition, Elsevier Science, London, England, 1991.
35. Lehnert, Hilmar. Systematic Errors of the Ray-Tracing Algorithm. J. Applied Acoustics, 38, 2-4, 1993, 207-221.
36. Lewers, T. A Combined Beam Tracing and Radiant Exchange Computer Model of Room Acoustics. J. Applied Acoustics, 38, 2-4, 1993,161-178.
37. McGrath, David, and Andrew Reilly. Convolution Processing for Realistic Reverberation. The 98th Convention of the Audio Engineering Society, February, 1995.
38. Monks, Michael, Byong Mok Oh, and Julie Dorsey. Acoustic Simulation and Visualization using a New Unified Beam Tracing and Image Source Approach. Meeting of the Audio Engineering Society, November, 1996.
39. Moore, G.R. An Applvach to the Analysis of Sound in Auditoria. Ph.D. Thesis, Cambridge, UK, 1984.
40. Naylor, G.M. ODEON – Another Hybrid Room Acoustical Model. J. Applied Acoustics, 38, 2-4, 1993, 131-144.
41. Naylor, B.F. Constructing Good Partitioning Trees. Graphics Intelface ’93, Toronto, CA, May, 1993.
42. Rajkumar, A., B.F. Naylor, and L. Rogers. Predicting RF Coverage in Large Environments using Ray-Beam Tracing and Partitioning Tree Represented Geometry. Wireless Networks, 1995.
43. Rindel, J.H. Modelling the Angle-Dependent Pressure Reflection Factor. J. Applied Acoustics, 38, 2-4, 1993, 223-234.
44. Sequin, Carlo, and Eliot Smyrl. Parameterized Ray Tracing. Computer Graphics (SIGGRAPH 89), 23, 3,307-314.
45. Smits, Brian, James R. Arvo, and David H. Salesin. An Importance-Driven Radiosity Algorithm. Computer Graphics (SIGGRAPH 92), 26, 2,273-282.
46. Stephenson, U., and U. Kristiansen. Pyramidal Beam Tracing and Time Dependent Radiosity. Fifteenth International Congress on Acoustics, Tapir, June, 1995, 657-660.
47. Stettner, Adam, and Donald R Greenberg. Computer Graphics Visualization for Acoustic Simulation. Computer Graphics (SIGGRAPH 89), 23, 3,195-206.
48. Takala, Tapio, and James Hahn. Sound Rendering. Computer Graphics (SIG- GRAPH 92), 26, 2, 211-220.
49. Teller, Seth J., and Carlo H. S6quin, Visibility Preprocessing for Interactive Walkthroughs. Computer Graphics (SIGGRAPH 91), 25, 4, 61-69.
50. Teller, Seth J. Computing the Antiumbra Cast by an Area Light Source. Computer Graphics (P1vc. SIGGRAPH ’92), 26, 2 (August 1992), 139-148.
51. Teller, Seth J. Visibility Computations in Densely Occluded Polyhedral Envi~vnments. Ph.D. thesis, Computer Science Division (EECS), University of California, Berkeley, 1992. Also available as UC Berkeley technical report UCB/CSD-92-708.
52. Tsingos, Nicolas, and Jean-Dominique Gascuel. A General Model for Simulation of Room Acoustics Based On Hierarchical Radiosity. Technical Sketches, SIGGRAPH 97 Visual P1vceedings, 1997.
53. Tsingos, Nicolas, and Jean-DominiqueGascuel. Soundtracks for Computer Animation: Sound Rendering in Dynamic Environments with Occlusions. Graphics Intelface ’97, Kelowna, May 21-23, 1997, 9-16.
54. Veach, Eric, and Leonidas J. Guibas. Metropolis Light Transport. Computer Graphics (SIGGRAPH 97), 65-76.
55. Vian, J.P. and D. van Maercke. Calculation of the Room Response Using a Ray Tracing Method. P~vceedings of the ICA Symposium on Acoustics and Theater Planning for the Pelforming Arts, Vancouver, CA, 1986, 74-78.
56. Vorlander, M. International Round Robin on Room Acoustical Computer Simulations. P~vceedings of the 15th International Congress of Acoustics, Trondheim, Norway, June, 1995.
57. Walsh, John R, and Norm Dadoun. What Are We Waiting for? The Development of Godot, II. presented at the 103 rd Meeting of the Acoustical Society of America, Chicago, April, 1982.
58. Ward, William C., Gary, W. Elko, Robert A. Kubli, and W. Craig McDougald. The New Varechoic chamber at AT&T Bell Labs. P~vceeding of Wallace Clement Sabine Centennial Symposium, Acoustical Society of America, New York, June, 1994, 343-346.
59. Watt, Mark. Light-Water Interaction Using Backward Beam Tracing. Computer Graphics (SIGGRAPH 90), 24, 377-385.
60. Weiler, K. and R Atherton. Hidden Surface Removal Using Polygon Area Sorting. Computer Graphics (SIGGRAPH 77), 11, 2,214-222.
61. Whitted, Turner. An Improved Illumination Model for Shaded Display. Communications oftheACM, 23, 6, June, 1980, 343-349.