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.

@inproceedings{Funkhouser:1999:RAM,
   author = "Thomas A. Funkhouser and Patrick Min and Ingrid Carlbom",
   title = "Real-Time Acoustic Modeling for Distributed Virtual Environments",
   booktitle = "Proceedings of SIGGRAPH 99",
   year = "1999",
   month = aug,
   pages = "365--374"
}