Page  00000001 Real-Time Acoustics Simulation using Mesh-Tracing Bert Schiettecatte, Axel Nackaerts, Bart De Moor Department Elektrotechniek-ESAT, Katholieke Universiteit Leuven email: {bert.schiettecatte I axel.nackaerts I bart.demoor} @esat.kuleuven.ac.be Abstract A number of techniques have been presented recently to simulate or predict the acoustics of a room. Among these we can find reverberation algorithms based on waveguide meshes and acoustic ray-tracing. Both approaches have disadvantages, such as an excessive amount of computation required (resulting in only off-line simulations) or aliasing phenomena caused by non-uniform speed of sound distribution of the travelling waves. This paper presents a novel approach to simulating acoustics in real-time which solves the problems mentioned or significantly improves the quality of existing mesh-based reverberation algorithms. 1. Introduction Given a 3D description of a room, there are several ways to simulate its acoustics. One of the approaches to model the room is to build a 3D mesh consisting of digital waveguides (Smith 1992, Smith 1997, Murphy 2000, Savioja 1995, Savioja 1997, Savioja 1994, Van Duyne 1993). The waveguides in the mesh can be arranged in several ways, rectangular being the simplest arrangement. All these arrangements have the same problem: there is a certain regularity in the mesh. Because of this regularity, propagation errors in the mesh (speed of sound errors) occur in a predictable way, resulting in distortions. There have been attempts to reduce these errors (Savioja 2000, Fontana 2001) but the authors feel that there must be a simple way to solve this fundamental problem. Another way to simulate room acoustics, is to use a technique similar to ray-tracing, a 3D rendering approach used in computer graphics. Audio raytracing (Kleiner 1993) suffers from other problems: a low-frequency travelling wave cannot be represented by a simple ray. This type of simplification only works with light. There have been variations on raytracing such as beam-tracing (Funkhouser 2003), to model sound propagation. All these techniques have problems, either in accuracy, or in computational load. The classic ray-tracing algorithm cannot be run easily at run time and requires varying computational power, depending on the number of rays active. In this paper, we will try to solve some of the problems of waveguide mesh propagation and raytracing, by introducing an algorithm that converts a waveguide mesh into an impulse response database. 2. Meshes and Ray-Tracing The simplest of all meshes is the rectangular mesh. In this mesh, every vertex is a junction where the unit delay lines meet. The edges between vertices are the unit delay lines. A sound can be 'injected' into the mesh by passing its samples one-by-one into a junction. At every sample tick in time, samples are passed through the delay lines. There is an example of a 2D mesh below in Figure 1. For 3D meshes we need to add 4 delay lines to the junction (2 delay lines going up, 2 delay lines going down). I L I\ Figure 1. 2D rectangular waveguide mesh. The problem with the rectangular waveguide mesh is clear: a wave traveling from the source to the listener does not travel at the same speed in all directions. This can be seen easily by examining Figure 2 below. Figure 2. 2D rectangular waveguide mesh diagonal propagation error. This propagation error can be reduced by randomizing the mesh, a strategy we apply in the new algorithm which is introduced by this paper. Before turning to our new algorithm, we quickly review acoustic ray-tracing: a variation of ray-tracing used in

Page  00000002 3D graphics. In graphics, ray-tracing is a rendering approach where rays of light depart from the camera into the scene and intersect objects, creating pixels for the resulting rendering. In acoustic ray-tracing (the classic algorithm without any modifications), rays of sound leave the source and travel to the listener by bouncing off objects and walls in the 2D or 3D scene. This is illustrated by Figure 3. / Y Figure 3. Ray-tracing in a 2D plane with omnidirectional source (S) and listener (L), direct path, 1st and 2nd order reflections off the walls. A nice property of acoustic ray-tracing is that it can be made real-time using special datastructures such as a beam-tree. Acoustic ray-tracing also allows to model diffraction. Its close relation to ray-tracing for computer graphics exposes some analogies between sound and graphics. Because ray-tracing only depends on ray-surface intersection calculations, it is relatively easy to implement and has computational complexity that grows sublinearly with the number of surfaces in the model. Also, paths of specular reflection, diffuse reflection, diffraction and refraction can be sampled for each ray-surface intersection. This allows us to model arbitrary types of indirect reverberation. The main disadvantage of ray-tracing is that the continuous space of rays is sampled by a discrete number of paths, resulting in aliasing and errors in the impulse response. To minimize these errors, raytracing systems generate large numbers of samples, resulting in large amounts of computation. Perhaps the biggest disadvantage of ray-tracing is that it assumes a fixed listener, making it impossible to use this algorithm in an application where the listener is continuously moving. 3. Hybrid Technique To solve the problems of the techniques discussed, and to explore a new way of simulating room acoustics, we present a hybrid algorithm that uses elements of both acoustic ray-tracing and waveguide mesh propagation. We call this algorithm the mesh-tracing algorithm. It consists of 3 parts: room preprocessing, impulse response calculation, and real-time reverberation. The algorithm takes a 3D description of a room and fills the room with vertices from a uniform random distribution. Delaunay triangulation is then applied to the resulting 3D model (in the 2D case using triangles, in the 3D case using tetrahedra). The resulting triangulation is then repeatedly traversed in a breadth-first fashion to build impulse responses for all [source, listener] pairs in the 3D model. Using this database, real-time reverberation can be carried out easily using a fast convolution algorithm. We include figures for the algorithm below for the 2D mesh case. We start with a 2D mesh consisting of the 4 vertices of a rectangle (see Figure 4). The first part of the algorithm can be described using the following step-by-step procedure: Figure 4. Example 2D representation. 1. Take a 3D description of the room to simulate (collection of 3D vertices). 2. Fill the room with 3D vertices from a uniform random distribution. 3. Apply Delaunay triangulation to the resulting 3D scene: this connects the random vertices and vertices describing the room. The result of this procedure is a randomized waveguide mesh such as depicted in Figure 5. i\ I,-^ ^ /i \ / /ir ' - n i '; II \ | \ - " / I K-. /y 7r': ^3< Figure 5. 2D representation after filling with random points and applying Delaunay triangulation. The second part involves the calculation of the impulse responses for all vertex pairs [source (S), listener (L)] from the Delaunay triangulation (T). The impulse responses are calculated in a parallel fashion: 1. Put all vertices from T into a set D. 2. If D is empty, go to step 7. Else, select and remove a source vertex S from the set D and insert it into the queue Q. 3. Dequeue a vertex V from Q.

Page  00000003 4. Enqueue each vertex W which can be reached from V. 5. For each vertex W, calculate the incoming power by applying a propagation function F to the vertices V and W. Store the incoming power in a list Wpower locally associated with W. 6. If Q is empty, go to step 2. Else, go to step 3. 7. End. The propagation function F depicted in Figure 6 is a function which distributes outgoing power from a vertex V among all vertices W which can be reached from V and which lie beyond the line L perpendicular to the edge through which we reached vertex V. Vertices lying before the line L receive an incoming power of 0 and are not considered in the future - they are not part of the traveling wave passing through vertex V in the direction of the vertices W. The goal of the function is to distribute power such that there is no power loss. The function tries to mimic the behaviour of a traveling wave in the mesh and has great influence on the resulting impulse responses. The edge E corresponds to the direction of the traveling wave. When the second part is finished, every vertex in the triangulation has a list of waves (and their power) associated with it. This list represents the impulse response. Real-time reverberation using the supplied 3D room description can now be accomplished in the last part by applying real-time convolution on an input sound and the impulse response found in the database given a [source, listener] pair. Note that this algorithm doesn't use any optimizations which could be done: not every vertex in the triangulation can be a useful source or listener vertex. We could also use psycho-acoustics easily with the resulting database or remove contributions to the impulse responses which are below a certain treshold. Further research will indicate whether we can apply some knowledge from (McGrath 1999, Rocchesso 2001a and 2001b). Another advantage of the algorithm we introduced is that it allows us to refine or simplify the waveguide mesh at important locations. Refinement or simplification can be done by inserting or removing random vertices and applying local Delaunay triangulation. Such geometrical simplifications come down to model reduction. By simplifying or enhancing the mesh we have control over the computational process required to describe a certain area. Our algorithm has great advantages to classic room simulation algorithms and offers an extra level of information which can be used to speed up realtime reverberation or carry out psycho-acoustic experiments. We finally note that our algorithm can easily support a moving listener. We will use Voronoi diagrams, the duality to Delaunay triangulation, to select the correct impulse response given an area in which the listener is currently located. 4. Conclusions In this paper, we introduced a new algorithm for pre-computing impulse responses for room acoustics simulation. The algorithm uses Delaunay triangulation on a 3D description of the room and a collection of uniform random vertices within the room, to create a randomized 3D waveguide mesh. This waveguide mesh is then repeatedly traversed in a breadth-first fashion to build the impulse responses for all [source, listener] pairs in the mesh. These impulse responses can then be used to perform realtime reverberation using a fast convolution algorithm. 5. Acknowledgements Bert Schiettecatte is supported by a research grant from the N.F.W.O. Axel Nackaerts is a research assistant at the Katholieke Universiteit Leuven, Belgium. Dr. Bart De Moor is a full professor at the Katholieke Universiteit Leuven, Belgium. Research supported by GOA-Mefisto 666, several PhD/postdoc Figure 6. Propagation function F for normal vertices. There is a special case of the propagation function F which is applied when the vertex V is a vertex at the edge of the mesh (see Figure 7): such a vertex would be part of a 'wall' in a 3D mesh or would be part of the hull of a 2D mesh. In this case, power is distributed among vertices W lying before the line L (perpendicular to the edge E indicating the direction of the traveling wave). Figure 7. Propagation function F for a vertex V part of a wall or hull.

Page  00000004 & fellow grants (Research Council KUL), PhD/postdoc grants, projects, G.0240.99 (FWO, multilinear algebra), G.0407.02 (FWO, support vector machines), G.0197.02 (FWO, power islands), G.0141.03 (FWO, Identification and cryptography), G.0491.03 (FWO, control for intensive care glycemia), G.0120.03 (FWO, QIT), research communities (FWO, ICCoS, ANMMM). Bil. Int. Collaboration Hungary/ Poland (AWI); PhD Grants, Soft4s (softsensors) (IWT), DWTC (IUAP IV-02 (1996-2001) and IUAP V-22 (2002-2006), PODO-II (CP/40: TMS and Sustainibility); CAGE (EU); ERNSI (EU); Eureka 2063-IMPACT (EU); Eureka 2419-FliTE (EU); Contract/Research agreements with Data4s, Electrabel, Elia, LMS, IPCOS, VIB; Savioja, L. and Vailimaiki V. (2000, March). Reducing the dispersion error in the digital waveguide mesh using interpolation and frequency-warping techniques. IEEE Trans. On Speech and Audio Processing 8(2), 184-194. Savioja, L; Rinne, T.J. and Takala, T. (1994) Simulation of Room Acoustics with a 3-D Finite Difference Mesh. Proc. ICMC, Arhus. Smith J.O., Rocchesso D. (1997, December) Aspects of Digital Waveguide Networks for Acoustic Modeling Applications. Smith, J.O. III. (1992) Physical Modeling Using Digital Waveguides. Computer Music Journal, volume 16, number 4, pages 74-91. Van Duyne, S.A. and Smith J.O. (1993). Physical modeling with the 2-D digital waveguide mesh. In Proc. Int. Computer Music Conf., Tokyo, Japan, pp. 40-47. ICMA. Van Duyne S.A., Smith J.O. The Tetrahedral Digital Waveguide Mesh. References Fontana, F., Savioja, L, and Vailimaiki V. (2001, September). A Modified Rectangular Waveguide Mesh Structure with Interpolated Input and Output Points. In Proc. Int. Computer Music Conf., Havana, Cuba, pp. 87-90. ICMA. Funkhouser T., Tsingos N., Carlbom I., Elko G., Sondhi M., West J.E., Pingali G., Min P. and Ngan A. (2003). A Beam Tracing Method for Interactive Architectural Acoustics. Accepted for publication in the Journal of the Acoustical Society of America. Kleiner M., Dalenback B.I., and Svensson P. (1993, November). Auralization- An Overview. J. Audio Eng. Soc., 41, 11, 861-875. McGrath, R., Wildmann T., and Fersntrom M. (1999). Listening to rooms and objects. In Proc. Conference on Spatial Sound Reproduction, Rovaniemi, Finland, pp. 512-522. AES. Murphy, D.T. and Howard D.M. (2000, December). 2-d digital waveguide mesh topologies in room acoustics modelling. In Proc. Conf. On Digital Audio Effects (DAFX-00), Verona, Italy, pp. 211-216. COST-G6. Rocchesso, D. and Ottaviani L. (2001a). Acoustic cues for 3-d shape information. In Proc. of the 2001 Int. Conf. on Auditory Display. Rocchesso, D. and Ottaviani L. (2001b). Can one hear the volume of a shape? In 2001 IEEE Workshop on Applications of Signal Processing to Audio and Acoustics. Savioja, L., Backman J., Jiirvinen A., and Takala T. (1995, June). Waveguide mesh method for low-frequency simulation of room acoustics. In Proc. 15th Int. Conf. on Acoustics (ICA-95), pp. 637-640. Savioja, L. and Vailimaiki V. (1997, April). Improved discrete-time modeling of multi-dimensional wave propagation using the interpolated digital waveguide mesh. In Proc. Int. Conf. on Acoustics, Speech and Signal Processing, Munich (Germany), pp. 459-462.