Electrical audio signal processing systems and devices – Sound effects – Reverberators
Reexamination Certificate
1998-10-02
2004-06-15
Mei, Xu (Department: 2644)
Electrical audio signal processing systems and devices
Sound effects
Reverberators
C381S061000, C084S630000
Reexamination Certificate
active
06751322
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a system and a method for modeling acoustic reverberation at interactive rates, using pre-computed data structures to accelerate beam tracing and propagation path generation.
2. Description of Prior Art
Computer-aided acoustic modeling is an important tool for designing and simulating three-dimensional (3D) environments. For example, an architect may evaluate the acoustic properties of a proposed building design, or a factory designer may predict the sound levels of any machine at any position on a factory floor, using acoustic models.
Acoustic modeling can also be used to provide a more realistic immersive virtual environment. For example, modeled acoustics may be used to provide sound cues to assist a user's navigation through, and communication in, immersive virtual environments. More specifically, the voices of users sharing a virtual environment may be spatialized according to the each user's avatar location. For 3D video games, sounds may be spatialized to help a player navigate and localize competing participants.
The primary challenge in spatializing sound in such environments is computing the significant number of viable propagation paths from a sound source position to a listener's receiving location. Because sound generally travels between a source and a receiver along a large number of paths, via reflection, transmission, and diffraction, accurate acoustic simulation is extremely computationally expensive. To illustrate this point, consider the example of
FIG. 1
which shows a simple two-room environment, and just some of the possible propagation paths from a sound source S to a receiver R located in an adjacent room.
Prior acoustic modeling approaches can generally be classified into four types: image source methods; radiant exchange methods; ray tracing methods; and beam tracing. Beam tracing is the basis for the approach set forth in this application.
Beam tracing methods classify reflection paths originating from a source position by recursively tracing pyramidal beams (i.e., a set of rays) through space. More specifically, a set of pyramidal beams is constructed that completely covers the two-dimensional (2D) space of directions from the source. For each beam, polygons are considered for intersection in front-to-back order from the source. As intersecting polygons are detected, the original beam is “clipped” to remove the shadow region created by the intersecting polygon, a transmission beam is constructed matching the shadow region, and a reflection beam is constructed by mirroring the transmission beam over the intersecting polygon's plane. For example, as illustrated in
FIG. 2
, a reflection beam R
a
is constructed by mirroring a transmission beam over surface a, using S′ as a virtual beam source. Transmission beam T
a
is constructed matching the shadow region created by surface a.
A significant advantage of beam tracing over the image source method is that fewer virtual sources need be considered for environments with arbitrary geometry. Since each beam represents the region of space for which a corresponding virtual source (at the apex of the beam) is visible, high-order virtual sources must be considered only for reflections off polygons intersecting the beam. For instance, referring to
FIG. 3
, consider the virtual source S
a
which results from the reflection of the beam originating from S over polygon a. The corresponding reflection beam, R
a
, intersects exactly the set of polygons (c and d) for which second-order reflections are possible after specular reflection off polygon a. Other polygons (b, e, f, and g) need not be considered for second-order reflections after a, thus significantly pruning the recursion tree of virtual sources.
A significant disadvantage of conventional beam tracing techniques, however, is that the geometric operations which are required to trace a beam through a 3D environment (i.e., computing intersections, clipping, and mirroring) are computationally expensive. Because each beam may be reflected and/or obstructed by several surfaces, particularly in complex environments, it is difficult to perform the necessary geometric operations on beams efficiently, as they are recursively traced through the spatial environment. For acoustic modeling to be effective in immersive virtual environments, computations must be completed at interactive rates so that spatialized audio output can be updated as the user navigates through the environment.
Much prior work in virtual environment systems has focused on visualization (i.e., methods for rendering more realistic images or for increasing image refresh rates). For example, Heckbert and Hanrahan, “Beam Tracing Polygonal Objects,”
Computer Graphics
(SIGGRAPH '84), 18, 3, 119-127 describe a graphics illumination technique in which pyramidal beams, represented by their 2D polygonal cross-sections, are traced recursively from a viewpoint to a point light source using a pre-computed “light beam tree” data structure. Teller, “Visibility Computations in Densely Occluded Polyhedral Environments,” Ph.D. thesis, Computer Science Division (EECS), University of California, Berkeley, 1992, describes a beam tracing algorithm for computing a “potentially visible set” of polygons to render from a particular viewpoint in a computer graphics scene using cell adjacency and “stab tree” data structures.
On the other hand, relatively little attention has been directed to auralization (i.e., rendering realistic spatialized sound using acoustical modeling). Yet, improved acoustic modeling can help provide users with a completely immersive virtual experience, in which aural and visual cues are combined to support a more natural interaction in a virtual environment. Due to the computational complexity discussed above, however, prior acoustic modeling techniques, such as conventional beam tracing, have been unable to realize accurate acoustic auralization in complex environments at interactive rates. Furthermore, such techniques have essentially disregarded complex scattering phenomena, such as diffraction and diffuse reflection.
SUMMARY OF THE INVENTION
The acoustic modeling technique according to the present invention efficiently utilizes a combination of pre-computed data structures to accelerate evaluation of acoustic propagation paths so that sound can be modeled and auralized in real-time, even in complex environments. According to the present invention, an input spatial model is initially partitioned into convex polyhedra (cells). Pairs of neighboring cells which share a polygonal boundary(s) are linked to form a cell adjacency graph. For each sound source, convex pyramidal beams are traced through the spatial model via depth-first recursive traversal of the cell adjacency graph. At each cell boundary, the beam is split and trimmed into possibly several convex beams representing paths of transmission, specular reflection, diffuse reflection, and diffraction.
During depth-first traversal of the cell adjacency graph, a beam tree data structure is generated to represent the regions of space reached by each potential sequence of transmission, specular reflection, diffuse reflection, and diffraction events at cell boundaries. This beam tree data structure enables fast computation of propagation paths to an arbitrary receiver position. Using the beam tree data structure to trace paths from a source to a receiver, acceptable computation rates for updating an acoustic model can be achieved so as to be suitable for interactive environments.
REFERENCES:
patent: 5467401 (1995-11-01), Nagamitsu et al.
patent: 5525765 (1996-06-01), Freiheit
patent: 5862231 (1999-01-01), Tokuhisa
patent: 5876213 (1999-03-01), Matsumoto
patent: 5880390 (1999-03-01), Hagiwara
patent: 05046193 (1993-02-01), None
Teller, Seth Jared “Visibility Computations in Densely Occluded Polyhedral Envoronments”; Dissertation, 1992, pp. 1-151.
Fuchs, Henry et al “On Visible Surface Generation by a Priori Tree Structures”; 1980, p
Carlbom Ingrid B.
Elko Gary W.
Funkhouser Thomas A.
Pingali Sarma V.
Sondhi Man Mohan
LandOfFree
Acoustic modeling system and method using pre-computed data... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Acoustic modeling system and method using pre-computed data..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Acoustic modeling system and method using pre-computed data... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3318802