Determination of Sound Source Obstruction in Virtual Scenes

ULRICH REITER, OLIVER BAUM, HELGE DRUMM, MICHAEL SCHULDT
Institute of Media Technology
Technische Universität Ilmenau
Helmholtzplatz 2, 98693 Ilmenau
GERMANY
http://www.imt.tu-ilmenau.de/     http://www.iavas.de/

Abstract: - This paper deals with an important aspect of user immersion in interactive virtual environments. Problems with virtual objects located between sound sources and listener in virtual scenes are discussed. Three different methods of detecting sound source obstruction in dependence on the listener’s (virtual) location are presented. Their advantages and drawbacks are evaluated. An outlook to further research necessities is given.

Key-Words: - Interactive Virtual Scenes, Sound Source Obstruction, Hardware Accelerated Processing

1   Introduction
The IAVAS (Interactive Audio Visual Application Systems) project currently under development at the Institute of Media Technology at Technische Universität Ilmenau aims at integrating and dominating the whole chain of production for interactive application systems, from recording and/or modeling the audiovisual content, storing and transmitting it, to the reproduction at the user’s side. Special focus is drawn on aspects of user interaction, which allows for new ways of delivering content according to the user’s needs [1].
	     One of the major tasks in the development and generation of new virtual sceneries (e.g. for computer games, TV shows or for special effects in the movies) is scene realism. A high level of (visual) scene realism can be achieved by using special graphics functions as supplied by many of today’s modern graphic cards. But when complete immersion of the user is necessary, scene realism has to be extended to the area of acoustics, too. The visual and the acoustical impression delivered to the user have to be at least coherent in order to allow for a realistic impression of a scenery.
     In a conventional scene as  produced for TV or cinema, a scriptwriter defines both the plot (the temporal run of the things happening) and the viewpoint (viewer’s angle, distance, etc.) at the scenery. In contrast, interactivity calls for new ways of media production. If we want to allow the user to move freely inside a scenery, we need to deliver more (geometrical, textural, auditive, etc.) information about it. One way to realize this is to create a detailed virtual scenery consisting of natural and/or synthetic objects. 
     These objects then need to be related to each other in order to form one consistent scene. Relationships between objects can have temporal, geometrical or logical qualities. Several ways of defining these relationships exist, one of them is using the Virtual Reality Modeling Language (VRML). VRML describes the relationships between objects in a virtual three-dimensional world using a hierarchical data structure called scene graph. Its elements are called nodes. The scene graph contains all information necessary to render the scene on a player device. In VRML97, basic functionality for audio rendering is contained in two nodes called Sound and AudioClip [2].

2   Consequences of User Interaction
As the user can move freely inside the virtual scenery, an important task of virtual acoustics is to ensure that only those sound sources are rendered audible that could be heard if the user was located in a real (and not virtual) environment. That means that if there is an object located between the sound source and the user’s position, this has to be determined in order to perform changes on the sound source’s audibility. In other words, the user should be ‘listening with the ears of the camera’. 
     Because there should be no limit to the number of sound sources that might be arranged by the author of a virtual scene, an algorithm has to be found to quickly do the calculus necessary to detect the obstruction of sound sources in real time. At the same time, the algorithm must be able to identify the object to which the detected polygon belongs. The latter is important in order to determine the acoustical characteristics of the obstructing object.
     The actual audio rendering, i.e. the process of applying attenuation to a source, as well as the positioning of the sources in the virtual scene plus the virtual acoustics calculus itself can be performed by dedicated audio hardware. Some modern sound cards offer on-board digital signal processors (DSPs) for these tasks. The DSPs and their functionalities can be accessed using a software development kit (SDK) made available by the manufacturer of the card.
     Finally, the same sound card can be used to reproduce the audio. Here, a 5.1 loudspeaker arrangement according to the SSF recommendations came to use [4]. 

3   Determination of Obstruction
In the following, three approaches to the problem of obstruction of sound sources will be presented and evaluated. 

3.1	Determination of Obstruction Using Computer Graphics Methods
Here, the model of an acoustical equivalent to a beam of light is used to determine obstruction: for every sound source, the intersections of the sound beam with all polygons of the scenery are examined. It is necessary that the scene is completely triangulated. With this premise, concave polygons can be avoided, which otherwise must be treated separately [5].

Fig.1: Obstruction of a sound source by a polygon	

     Every polygon P consists of three vertices V0, V1, V2. The sound source’s location is PQ, the listener’s is PH (see fig. 1). The equation of PHPQ is
     (1)	,
with being the position vector of PH. The plane E containing the three vertices V0, V1, V2 is described by its normal vector
     (2)	.
From the listener’s point of view, the sound source is obstructed if P is intersected by PHPQ. To verify this, the intersection S is calculated by inserting (1) into (2).
     If PQ is located in front of E, that means , then P cannot obstruct the sound source. A subsequent test must determine if S is located inside the boundaries of the polygon P. This is done by expressing the vector as a linear combination of vectors and :
     (3)	
S is located inside P if  (see fig. 2). The solution to the linear system of equations which determines  and  can be simplified by projecting P onto one of the coordinate planes. From this, we get a linear system of equations with two equations and the two unknown  and  .

Fig.2: Parametrical description of intersection S 
          (from [5]) 	
     In the case of obstruction detected, we still need to determine the object to which the polygon belongs in order to set the attenuation coefficient according to the object’s acoustic characteristics. This task is performed by the scene management, from which also the vertex coordinates for the considered polygon come from.
    The realization of this algorithm is very challenging, as we may not assume a scene to be completely triangulated. On another note, accessing the vertex coordinates of an object is quite difficult. Methods that do not require the scene to be completely triangulated will be presented in the next subsections.

3.2    Determination of Obstruction by OpenGL Selection
The graphic library OpenGL presents a method (‘Selection’) with which a certain area of a window can be scanned for objects. It was originally implemented to allow user interaction with objects (so called ‘mouse picking’), but selection can also be used to verify obstruction. 
     Selection is an OpenGL rendermode that can be activated with a glRenderMode(GL_SELECTION) function call. In contrast to the normal rendermode (GL_RENDER), the frame buffer is not altered. The application gets a feedback about objects being  encountered in the defined viewing volume, but the picture presented to the user remains the same. Each object inside a volume defined by the current model view- and projection-matrix and delimitated by the clipping planes produces a hit and thus an entry (‘hit record’) in the selection buffer. This entry comprises the minimum and maximum z-values of the object and the current value of the name stack, with which the object can be identified.
     In order to use select mode for the detection of obstruction, the sound sources have to be represented by visible objects (e.g. spheres). By doing so, the sound sources generate hit records and their z-values (from the listener’s point of view) can be determined. These visible objects can be drawn in select mode so they do not disturb the visual structure of the scene. Then, the camera is pointed successively to each sound source (gluLookat()) and the obstruction test is executed. Only acoustically meaningful objects (objects which have acoustical properties) are drawn and they are assigned a unique value on the name stack. The viewing volume should be centered to the middle of the viewport (i.e. the OpenGL window) to ensure that there is an intersection with the sound source.
     After terminating selection mode, the selection buffer is evaluated. The attenuation coefficients of all objects between listener and current sound source are combined additively and an obstruction value is set.
     In short, the algorithm has to perform the following steps:
1.	assign integers to the name stack for acoustically relevant objects
2.	create the select buffer
3.	activate selection mode
4.	init name stack
5.	construct pick-matrix (middle of viewport)
6.	construct perspective transformation matrix
7.	perform camera transformation, alignment to sound source
8.	draw relevant objects of the scene, fill the name stack
9.	draw sound source object
10.	terminate selection mode
11.	evaluate select buffer
-	accumulate acoustical attenuation for all objects with z-values smaller than z-value of sound source
-	set obstruction value
This method allows using the OpenGL hardware (graphics card) for the geometrical calculus and therefore only burdens the CPU very little. A drawback is the loss of graphic performance due to the rendering of (not visible) sound sources. The latter may or may not present a problem depending on the visual complexity of the scene and the graphic card’s overall processing power.

3.3    Determination of Obstruction using BSpheres
The two methods presented until now only detect obstruction in an absolute way. They do not take account of the successive increase of attenuation when the object slowly moves into the sound propagation path. The method presented in this subsection allows to make a statement on the degree of obstruction, meaning whether the sound source is obstructed by lateral zones of the object or by its center. The amount of attenuation applied to the sound source in order to create a realistic impression then should be lower or higher, respectively.
     Here, we do not look at objects on a polygonal basis anymore, but at the bounding spheres (BSpheres) surrounding them. A BSphere is the smallest sphere possible including all vertices of the object (see fig. 3). Therefore, the necessary description of an obstructing object is reduced to the center coordinates of its BSphere and its radius.
	
Fig.3: Determination of obstruction using BSpheres	

     Fig. 3 also shows that there is obstruction if M is in between PH and PQ and d < r. Both conditions can be verified using the OpenGL selection method presented in the previous subsection, replacing the object itself with its BSphere. If there is an intersection of BSphere and viewing volume, both conditions are fulfilled. The degree of obstruction v for the respective object can be calculated from 
     (4)	.
Therefore it is necessary to determine the distance from the BSphere’s center point M to the tangent PHPQ . This can be achieved by inserting the position vector  into the cross product representation of PHPQ  which is
     (5)	,
with  being the position vector of PH and  the normalized direction vector of the tangent. Thus, d is:
     (6)	.
     By multiplication of v with the attenuation coefficient resulting from the acoustical characteristics of the object, the overall attenuation caused by obstruction can be determined. Attenuation starts at d = r (0 %) and has its maximum at d = 0 (100 %). If there is more than one acoustically relevant object located in the sound propagation path, again attenuation coefficients of all objects between listener and current sound source are accumulated and an obstruction value total is set. The algorithm has to be repeated for every sound source, and every obstructing BSphere has its own distance d from center M to tangent PHPQ .
     The advantages of this method are
-	use of existing OpenGL hardware acceleration
-	more realistic simulation of progressive obstruction
-	gain in performance due to the fact that only BSpheres and not the objects themselves have to be processed in order to detect obstruction.
     On the other hand, the scene management must offer support for BSpheres, and equ. (6) has to be determined for every obstruction occurring in the scenery. Another drawback is that the objects are registered in a fairly inaccurate way, because BSpheres are per se always bigger than the original object’s dimensions they represent. This might lead to the algorithm assuming obstruction although the sound source is still entirely visible. Still, in most cases the error introduced is negligible. Only if the object’s extension into one dimension is much bigger than into the other two, i.e. the BSphere’s volume is only partly filled by the object, the effect is obvious.

4   Conclusions
The methods described here allow for the detection of obstruction of sound sources in virtual environments. Two of the presented methods rely on hardware acceleration commonly available on today’s graphic cards by using special OpenGL methods originally developed for enhanced visual representations and are especially appropriate if processing load is an issue. When using BSpheres, even progressive obstruction can be simulated with few CPU load.
     While the determination of obstruction by the OpenGL selection method has been verified in an OpenVRML interactive virtual 3D application, the same still has to be done for the BSpheres method. Unfortunately, the scene management of OpenVRML regarding BSpheres is still faulty, so completely wrong and not plausible values for its size were displayed. 
     Because the IAVAS project concentrates on MPEG-4 as an environment for the representation of virtual scenes, the methods described here will be integrated into an experimental MPEG-4 player.

Acknowledgements
The authors wish to thank the Thuringian Ministry of Science, Research, and Art that is founding the IAVAS project assigned to the Institute of Media Technology.

References:
[1]  U. Kühhirt, H. Drumm, U. Reiter, M. Rittermann, Application Systems for MPEG-4, to be published at IEEE Int. Symposium on Consumer Electronics 2002, Erfurt / Germany, Sept. 23rd-26th, 2002
[2] VRML97 specifications, ISO/IEC 14772-1:1997, http://www.vrml.org/Specifications/VRML97/index.html
[3] J.-M. Jot, Perceptual and Statistical Models for Virtual Audio Environments, SIGGRAPH Audio Rendering Campfire, May 2001
[4] Recommended Practice SSF - 01 - /E3 (01/00), Listening Conditions and Reproduction Arrangements for Multichannel Stereophony, Surround Sound Forum (SSF), http://www.vdt.de/
[5] D. Badouel, An Efficient Ray-Polygon Intersection, in Graphic Gems I, Academic Press, Boston, 1990, pp. 390-393, see also
     http://graphics.stanford.edu/courses/cs348b-98/gg/intersect.html