The primary challenge in acoustic modeling is computation of reverberation paths from a sound's source position to a listener's receiving position. As sound may travel from source to receiver via a multitude of reflection, transmission, and diffraction paths, accurate simulation is extremely compute intensive. Prior approaches to acoustic simulation have used the image source method, whose computational complexity grows with O(n^r) (for n surfaces and r reflections), or ray tracing methods, which are prone to sampling error and require lots of computation to trace many rays. Due to the computational complexity of these methods, interactive acoustic simulation has generally been considered impractical.
I will describe data structures and algorithms we have developed to enable interactive simulation of acoustic effects in large 3D virtual environments. Our approach is to precompute and store a spatial data structure that can be later used during an interactive session for evaluation of reverberation paths. The data structure is a ``beam tree'' that maps the convex pyramidal beam-shaped paths of significant transmission and specular reflection from a source point through 3D space. The beam tree is generated by: 1) partitioning 3D space into convex polyhedral regions, 2) computing the convex polygonal boundaries between regions, and 3) recursively splitting and tracing convex polyhedral beams from a source point through region boundaries (e.g., reflecting beams at opaque boundaries). The precomputed beam tree data structure can be used to compute specular reflection and transmission paths from a source position to any point in space at interactive rates. The lengths and directions of computed reveration paths may be used to spatialize audio source signals to a receiver moving under interactive control by a user.
This is joint work with Gopal Pingali, Gary Elko, Mohan Sondhi, Jim
West, Ingrid Carlbom, and Mike Gatlin at Bell Laboratories.