Methods, systems, and computer readable media for fast geometric sound propagation using visibility computations

PRIORITY CLAIM

0001This application claims the benefit of U.S. Provisional Patent Application Ser. No. 61/419,781, filed Dec. 3, 2010, the disclosure of which is incorporated herein by reference in its entirety.

GOVERNMENT INTEREST

0002The presently disclosed subject matter was made with U.S. Government support under Grant No. W911NF-04-1-0088 awarded by Army Research Office, Grant Nos. 0636208, 0917040, and 0904990 awarded by National Science Foundation, and Grant No. WR91CRB-08-C-0137 awarded by U.S. Army. Thus, the U.S. Government has certain rights in the presently disclosed subject matter.

TECHNICAL FIELD

0003The subject matter disclosed herein relates generally to methods and systems for modeling sound propagation in a scene. More particularly, the subject matter disclosed herein relates to methods and systems for simulating sound propagation using geometric acoustic algorithms.

BACKGROUND

0004Sound rendering or auditory displays can augment graphical rendering and provide the user with an enhanced spatial sense of presence. Some of the driving applications of sound rendering include acoustic design of architectural models or outdoor scenes, walkthroughs of large CAD models with sounds of machine parts or moving people, urban scenes with traffic, training systems, computer games, etc. A key component in these applications is accurate computation of sound propagation paths, which takes into account the knowledge of sound sources, listener locations, the 3D model of the environment, and material absorption and scattering properties.

0005The propagation of sound in a medium is governed by the acoustic wave equation, a second-order partial differential equation. However, numerical methods that directly solve the acoustic wave equation can take tens of minutes even for simple rooms. Moreover, for numerical methods, the computation time grows as a fourth power of the maximum frequency simulated, and is proportional to the volume of the enclosed space. Hence they can only be used for small rooms and for low frequencies.

0006On the other hand, fast sound propagation methods are based on geometric acoustic (GA) algorithms, such as ray tracing or volumetric tracing. These geometric acoustics (GA) techniques are not as accurate as numerical methods in terms of solving the wave equation, and cannot easily model all kinds of propagation effects, but they allow simulation of early reflections at real-time rates. These methods work well in terms of handling specular reflections, and can take advantage of recent advances in real-time ray tracing methods and multi-core processors. However, current geometric propagation methods are either not fast enough for interactive applications or may not compute all propagation paths accurately. As a result, interactive applications such as computer games tend to use statically designed environment reverberation filters. Some games use ray tracing to estimate the size of a room and use this information to set parameters for a reverberation filter. Games also use precomputed visibility to determine if a source is out of line of sight from the listener. This is usually performed at a coarse level (i.e., visibility can be determined at a room-to-room level of detail using cell-and-portal visibility or ray shooting). If the source is not visible, a low-pass filter is usually applied to approximate diffraction effects. However the direction is the direct line from source to listener, which leads to very unnatural sound which seems to emanate from solid walls.

0007Accordingly, it would be desirable for an improved method and system for modeling sound propagation to allow for faster computation of sound propagation paths.

SUMMARY

0008In accordance with this disclosure, methods, systems and computer readable media for simulating sound propagation in a scene are provided. In one aspect, a method for simulating sound propagation is provided. The method can comprise defining a sound source position within a modeled scene having a given geometry, constructing a visibility tree for modeling sound propagation paths within the scene, using a from-region visibility technique (e.g., with occlusion culling) to model sound diffraction within the scene and reduce the size of the visibility tree, using a from-point visibility technique (e.g., a conservative from-point visibility technique which performs occlusion culling) to model specular sound reflections within the scene and reduce the size of the visibility tree, using the visibility tree to generate an impulse response for the scene, and using the impulse response to simulate sound propagation in the scene.

0009In another aspect, a non-transitory computer readable medium is provided, the computer readable medium having stored thereon executable instructions that when executed by the processor of a computer control the computer to perform steps comprising defining a sound source position within a modeled scene having a given geometry, constructing a visibility tree for modeling sound propagation paths within the scene, using a from-region visibility technique (e.g., with occlusion culling) to model sound diffraction within the scene and reduce the size of the visibility tree, using a from-point visibility technique (e.g., a conservative from-point visibility technique which performs occlusion culling) to model specular sound reflections within the scene and reduce the size of the visibility tree, using the visibility tree to generate an impulse response for the scene, and using the impulse response to simulate sound propagation in the scene.

0010In a further aspect, a system for simulating sound propagation is provided. The system can comprise a fast geometric sound simulator for defining a sound position within a modeled scene having a given geometry, for constructing a visibility tree for modeling sound propagation paths within the scene, for using a from-region visibility technique (e.g., with occlusion culling) to model sound diffraction within the scene and reduce the size of the visibility tree, for using a from-point visibility technique (e.g., a conservative from-point visibility technique which performs occlusion culling) to model specular sound reflections within the scene and reduce the size of the visibility tree, and for using the visibility tree to generate an impulse response for the model. The system can further comprise a sound source for generating an input sound to the scene, wherein the sound simulator uses the impulse response to simulate a response of the scene to the input sound.

0011The subject matter described herein for simulating sound propagation in a scene can be implemented in software in combination with hardware and/or firmware. In one exemplary implementation, the subject matter described herein can be implemented using a non-transitory computer readable medium having stored thereon executable instructions that when executed by the processor of the computer control the computer to perform steps. Exemplary computer readable media suitable for implementing the subject matter described herein include disk memory devices, chip memory devices, application specific integrated circuits, and programmable logic devices. In addition, a computer readable medium that implements the subject matter described herein may be located on a single device or computing platform or may be distributed across plural devices or computing platforms.

0012Although some of the aspects of the subject matter disclosed herein have been stated hereinabove, and which are achieved in whole or in part by the presently disclosed subject matter, other aspects will become evident as the description proceeds when taken in connection with the accompanying drawings as best described hereinbelow.

BRIEF DESCRIPTION OF THE DRAWINGS

0013The features and advantages of the present subject matter will be more readily understood from the following detailed description which should be read in conjunction with the accompanying drawings that are given merely by way of explanatory and non-limiting example, and in which:

0014<figref idref="DRAWINGS">FIG. 1</figref> is a block diagram illustrating an exemplary system for simulating sound propagation within the scene according to an embodiment of the presently disclosed subject matter;

0015<figref idref="DRAWINGS">FIGS. 2</figref><i>a</i>-<b>2</b><i>c </i>are schematic representations of three from-point visibility algorithms that can be used with the methods and systems of the presently disclosed subject matter;

0016<figref idref="DRAWINGS">FIGS. 3</figref><i>a</i>-<b>3</b><i>c </i>are schematic representations of three from-region visibility algorithms that can be used with the methods and systems of the presently disclosed subject matter;

0017<figref idref="DRAWINGS">FIG. 4</figref> is a schematic representation of view-frustum culling and back-face culling algorithms that can be used with the methods and systems of the presently disclosed subject matter;

0018<figref idref="DRAWINGS">FIG. 5</figref> is a block diagram illustrating an exemplary method for occluder selection according to an embodiment of the presently disclosed subject matter;

0019<figref idref="DRAWINGS">FIG. 6</figref> is a schematic representation of a frustum construction step for a point source that can be used with the methods and systems of the presently disclosed subject matter;

0020<figref idref="DRAWINGS">FIG. 7</figref> is a schematic representation of a frustum construction step for a line source that can be used with the methods and systems of the presently disclosed subject matter;

0021<figref idref="DRAWINGS">FIGS. 8 and 9</figref> are schematic representations of methods for occluder selection according to embodiments of the presently disclosed subject matter;

0022<figref idref="DRAWINGS">FIGS. 10</figref><i>a</i>-<b>10</b><i>d </i>are schematic representations of geometric sound propagation approaches that can be used with the methods and systems of the presently disclosed subject matter;

0023<figref idref="DRAWINGS">FIG. 11</figref> is a block diagram illustrating an exemplary method for simulating sound propagation within the scene according to an embodiment of the presently disclosed subject matter;

0024<figref idref="DRAWINGS">FIGS. 12</figref><i>a</i>-<b>12</b><i>c </i>are schematic representations of a scene modeled according to an embodiment of the presently disclosed subject matter;

0025<figref idref="DRAWINGS">FIG. 13</figref> illustrates a visibility tree that can be used with the methods and systems of the presently disclosed subject matter;

0026<figref idref="DRAWINGS">FIGS. 14</figref><i>a </i>and <b>14</b><i>b </i>are schematic representations of path validation approaches that can be used with the methods and systems of the presently disclosed subject matter;

0027<figref idref="DRAWINGS">FIG. 15</figref> is a graph comparing the potentially visible set of primitives computed by a beam tracer algorithm against an algorithm based on the methods and systems of the presently disclosed subject matter;

0028<figref idref="DRAWINGS">FIGS. 16</figref><i>a </i>and <b>16</b><i>b </i>are charts comparing an average amount of visible geometry returned by previous methods against the methods and systems of the presently disclosed subject matter; and

0029<figref idref="DRAWINGS">FIGS. 17</figref><i>a</i>-<b>17</b><i>d </i>are graphs of impulse responses computed for diffraction about a simple double wedge for increasing numbers of samples per edge.

DETAILED DESCRIPTION

0030The present subject matter provides methods, systems and computer readable media for simulating sound propagation in a scene. In one aspect illustrated in <figref idref="DRAWINGS">FIG. 1</figref>, an exemplary implementation of the subject matter described herein is provided. Referring to <figref idref="DRAWINGS">FIG. 1</figref>, a sound source <b>100</b> may be any suitable application that receives user input for sound to be generated. The sound source <b>100</b> may be a game or any other application for which it is desirable to generate a sound. A sound simulator <b>102</b> implements the subject matter described herein for fast geometric sound simulation. Sound simulator <b>102</b> receives model parameters and generates the impulse response of a model as described above. When sound simulator <b>102</b> receives the input sounds from sound source <b>100</b>, sound simulator <b>102</b> generates an output sound based on the fast computation method described below.

0031In addition to gaming, other applications of the subject matter described herein include architectural design and acoustic engineering for entertainment and other applications. In one implementation, sound simulator <b>102</b> may be implemented as middle-ware that resides between an application, such as sound source <b>100</b>, and the underlying hardware that executes sound simulator <b>102</b> and sound source <b>100</b>.

0032In one implementation, sound simulator <b>102</b> may be implemented using a non-transitory computer readable medium having stored thereon executable instructions that when executed by the processor of a computer control the computer to perform steps. Exemplary computer readable media for implementing the subject matter described herein include chip memory devices, disk memory devices, programmable logic devices, and application specific integrated circuits. In addition, a computer readable medium that implements the subject matter described herein may be located on a single device or computing platform or may be distributed across plural devices or computing platforms.

0033Regardless of the specific implementation, the present methods and systems can use visibility algorithms to accelerate GA methods used for computing specular reflections and edge diffraction. In particular, the methods and systems described herein can comprise two object-space visibility algorithms which can be used for fast GA computations. First, a point-based conservative visibility algorithm can improve the computation of specular reflections using an image-source method.

0034A second object-space visibility algorithm for fast GA computations can be an algorithm that computes visibility from a given edge in the model and is used to accelerate the performance of higher order finite-edge diffraction. In the context of geometric propagation, two main approaches exist for modeling edge diffraction: the Uniform Theory of Diffraction (UTD) and the Biot-Tolstoy-Medwin (BTM) model. UTD models diffraction around an infinite edge in terms of a single virtual point source on the edge. While this makes it fast enough to be useful in interactive applications, it is an approximate method and may only work well for models with very large edges in outdoor scenes. On the other hand, BTM models diffraction around finite edges in terms of many virtual point sources located along the edge. Although this makes the resulting approach more computationally intensive than UTD, it has been shown to be more accurate than UTD at low frequencies, where diffraction effects play an important role.

0035Significant time savings can be obtained through the use of these visibility algorithms on complex models.

Visibility Techniques

0036Visibility techniques have been studied in computer graphics, computational geometry, robotics and related areas for more than four decades. The basic goal of visibility algorithms is to compute a set of primitives that are visible from a given view-point or view-region. Visibility algorithms can be classified in different ways. One way is to classify them into from-point and from-region visibility. <figref idref="DRAWINGS">FIGS. 2</figref><i>a</i>-<b>2</b><i>c </i>show examples of from-point visibility where the circle S represents the view-point. From-point visibility is used in computer graphics for generating the final image from the eye-point based on rasterization or ray tracing. Other examples of applications of from-point visibility include hard shadow computation for point light sources.

0037<figref idref="DRAWINGS">FIGS. 3</figref><i>a</i>-<b>3</b><i>c </i>show examples of from-region visibility, where the rectangular region R with the arrows denotes a view-region. From-region visibility has been used in a variety of application such as computer graphics for global illumination (i.e., computing the multiple bounce response of light from light sources to the camera via reflections from primitives in the 3D model), interactive walkthroughs of complex 3D models (by prefetching a smaller set of potentially visible primitives from a region around the active camera position), and soft shadow computation from area light sources.

0038Given a view-point (v ∈ <img file="US2012249556A1_D0001.tif" />³, from-point) or a view-region (v ⊂ <img file="US2012249556A1_D0002.tif" />³, from-region), a set of geometry primitives (Π), and a viewing frustum (Φ), which is a set of infinitely many rays originating in v, the goal of visibility techniques is to compute a set of primitives π <u style="single">⊂</u> Π hit by rays in Φ. For example, in FIGS. <b>2</b><i>a</i>-<b>2</b><i>c, </i>the circle S corresponds to the viewpoint, and in <figref idref="DRAWINGS">FIGS. 3</figref><i>a</i>-<b>3</b><i>c, </i>the rectangle R corresponds to the view-region. The set of primitives is Π={P<b>1</b>, P<b>2</b>, P<b>3</b>, P<b>4</b>, P<b>5</b>, P<b>6</b>} and the region shaded in light gray bounded by two arrows is spanned by rays in Φ, the viewing frustum. In <figref idref="DRAWINGS">FIGS. 2</figref><i>a</i>-<b>2</b><i>c </i>the visible set of primitives π={P<b>1</b>, P<b>5</b>} and in <figref idref="DRAWINGS">FIGS. 3</figref><i>a</i>-<b>3</b><i>c </i>the visible set of primitives π={P<b>1</b>, P<b>3</b>, P<b>5</b>}. Note that the set it is called the potentially visible set (PVS). Depending on the properties of the computed PVS, visibility techniques can be further classified.

Object-Space Exact Visibility

0039Exact visibility techniques compute a PVS, π_exact, hit by every ray in Φ and every primitive in π_exactis hit by some ray in Φ. Since every ray in Φ is considered to compute visibility, these techniques are called object-space techniques. Moreover, these intersection computations are performed at the accuracy of the original model (e.g. IEEE 64-bit double precision arithmetic). The PVS computed by an object-space exact visibility algorithm is the smallest PVS which contains all the primitives visible from v. Many applications require exact visibility with object space precision. For example, accurate computation of soft shadows due to area light source in computer graphics requires the computation of exact visible area from all the points of the area light source to compute the contribution of the area light source at the point. Similarly, computing hard shadows due to a point light source requires accurate computation of visible portions of primitives from the point light source or aliasing artifacts may appear.

0040<figref idref="DRAWINGS">FIG. 2</figref><i>b </i>shows an example of exact from-point visibility. Primitives P<b>1</b>, P<b>3</b>, and P<b>5</b> block all the rays in the viewing frustum starting at the view-point from reaching the primitives P<b>2</b>, P<b>4</b>, and P<b>6</b>. Thus, the primitives P<b>2</b>, P<b>4</b>, and P<b>6</b> are marked as hidden. The two main approaches for computing exact from-point visibility are based on beam tracing. Beam tracing approaches shoot a beam from the view point and perform exact intersections of the beam with the primitives in the scene. As the beam hits the primitives, exact intersection and clipping computations are performed between the beam and the primitive. The portion of the beam which is not hit by any primitive so far is checked for intersections with the remaining primitives. Thus, the complexity of the shape of the beam may increase as more intersection computations are performed. In general, performing exact and robust intersection computations with the beam on complex 3D models is considered a hard problem.

0041Approaches based on Plücker coordinates perform constructive solid geometry (CSG) operations in Plücker space to compute exact visibility. Plücker space is a six-dimensional space with certain special properties. In this approach, the view frustum and the primitives are represented in Plücker space as CSG primitives and intersection computations are performed between the view-frustum and the primitives such that when the CSG intersection is transformed back into Euclidean space, it corresponds exactly to the visible primitives. The intersection between the view-frustum and primitives in Plücker space requires complex operations. Thus, these techniques can be used to perform exact from-point visibility computations, but can be expensive and susceptible to robustness problems.

0042<figref idref="DRAWINGS">FIG. 3</figref><i>b </i>shows an example of from-region exact visibility. Primitives P<b>1</b>, P<b>3</b>, P<b>4</b>, and P<b>5</b> are visible from the view-region. Note that no ray starting in the view region reaches P<b>2</b> and P<b>6</b>, and therefore they are marked as hidden from the view-region. Many complex data structures and algorithms have been proposed to compute exact from-region visibility, including aspect graphs, visibility complex, and performing CSG operations in Plücker space. These methods have high complexity—O(n⁹) for aspect graphs and O(n⁴) for the visibility complex, where n is the number of geometry primitives—and are too slow to be of practical use on complex models.

Object-Space Conservative Visibility

0043Conservative visibility techniques compute a PVS, π_conservative, hit by at least every ray in Φ. In addition, however, the PVS, π_conservative, may contain primitives which are not hit by any ray in Φ. Thus, π_{irconservative}is conservative in that it errs on the side of over-inclusion of primitives (i.e., π_conservative<u style="single">⊃</u> π_exact). Conservative from-point visibility algorithms are preferred for their computational efficiency and simplicity over exact algorithms. The two simple and widely used but highly conservative visibility techniques are view-frustum culling and back-face culling. They are used to trivially compute some of the hidden primitives. <figref idref="DRAWINGS">FIG. 4</figref> illustrates these methods. In view-frustum culling, the primitives completely outside the view-frustum are marked hidden. In back-face culling, the primitives which are facing away from the view-point or view-region are marked as hidden. Conservative visibility is preferred in many applications mainly due to its ease of implementation and good performance improvement.

0044The choice between a conservative or an exact object-space algorithm is decided by the application on the basis of the trade-off between the overhead of extra visible primitives due to the conservative algorithm vs. the time overhead of the exact algorithm.

0045<figref idref="DRAWINGS">FIG. 2</figref><i>c </i>shows an example of the PVS computed by a conservative from-point visibility algorithm referred to as “FastV.” In this algorithm, many small frusta are shot from the view-point and a frustum stops when it is entirely blocked by primitives. It is noted that primitive P<b>4</b>, which is not visible from the view-point, is still reported as potentially visible by the present conservative approach. Primitives P<b>2</b> and P<b>6</b> remain hidden from the view-point. Many other techniques have been developed for conservative from-point visibility computations. Many of these algorithms have been designed for special types of models, however, such as architectural models represented as cells and portals, 2.5D urban models, or scenes with large convex primitives. These methods are well suited when the target application of the visibility algorithms is limited to urban scenes or architectural models corresponding to buildings or indoor structures with no interior primitives or furniture. In contrast, the present FastV algorithm is general and can handle all kinds of scenes.

0046<figref idref="DRAWINGS">FIG. 3</figref><i>c </i>demonstrates a conservative from-region visibility algorithm. The basic idea is to construct shadow frusta SF (polyhedral beams contained within the umbrae between the view-region and primitives) for selected primitives. Typically, these primitives are selected by an occluder selection algorithm based on their effectiveness in removing hidden primitives. Primitives which are completely inside the shadow frusta SF are marked as hidden. In this regard, <figref idref="DRAWINGS">FIG. 3</figref><i>c </i>shows that only the primitive P<b>2</b> is completely inside shadow frusta SF<b>1</b> and SF<b>5</b> of primitives P<b>1</b> and P<b>5</b>, respectively. Also, it is noted that primitive P<b>6</b> is marked as potentially visible by the present approach even though there is no ray originating in the view-region which reaches P<b>6</b>.

0047Regarding occluder selection, one option can be to simply use every primitive in the scene as an occluder, and use an occlusion culling algorithm that handles occluder fusion. In an ideal scenario, such an approach would result in a PVS that is as close as possible to π_exactexact. However, the main issue with such an approach, which limits its practical application, is that the cost of occlusion culling is typically a function of the number of occluders. Most prior work on occluder selection uses heuristics based on distance, solid angles, or area of primitives. Although these methods compute a subset of Π to be used as occluders, they are unable to exploit the connectivity information of primitives to find any arbitrary set of connected triangles as occluders. If small occluders are combined into large occluders, the culling efficiency of the visibility algorithm can be improved.

0048Thus, the methods and system according to the present subject matter can use a from-region occluder selection algorithm which exploits the connectivity information between scene primitives whenever feasible. This approach is general and applicable to all kinds of models including “polygon soup” models. No assumptions are made about the model or the connectivity of the polygons (e.g., in one implementation, the models can be assumed to be triangulated, but this is not a restriction imposed by the present algorithm). If the model connectivity information is given or can be extracted, this algorithm can exploit that information to compute large occluders formed by connected sets of primitives.

0049One algorithm that can be used to compute the occluders from a given region is shown generally in <figref idref="DRAWINGS">FIG. 5</figref>. In a first step <b>212</b>, a query region R can be defined. Next, occluders can be chosen for query region R in a second step <b>214</b>. In a third step <b>216</b>, the occluders can be used to compute which primitives are hidden from R by the occluders. The set of primitives not hidden by the occluders can be defined as the potentially visible set for R in step <b>218</b>.

0050The present technique can be viewed as a generalization of the conservative from-point visibility technique used in the FastV algorithm discussed above. As discussed above, FastV computes from-point visibility by constructing a cubical box around the query point R, then subdividing each of its faces into multiple quad patches Q (where the number of quad patches can be user-specified), and then constructing frusta FR from each quad patch q ∈ Q and R (see <figref idref="DRAWINGS">FIG. 6</figref>). Each of these frusta can be used to compute which portions of the scene are visible from the query point that use the relevant patch as the viewport. Formally, for each q ∈ Q, the set of primitives p ∈ Π can be determined such that there exists a ray from R to some point on p which passes through q.

0051Given a frustum FR (defined by its corner rays), the FastV algorithm tries to compute a blocker for frustum FR. In the context of FastV, a blocker is defined as a connected set of triangles such that any convex combination of the corner rays of frustum FR intersects some triangle in the blocker. FastV traverses the scene hierarchy, and whenever a triangle T is found that intersects frustum FR, it uses the connectivity information associated with T to determine if some set of triangles connected to T can also be used as a blocker for frustum FR. It is possible that there may be no such triangles. Therefore, once the traversal is completed, FastV returns at most one blocker for frustum FR and zero or more connected sets of triangles in front of the blocker which do not completely block frustum FR.

0052Referring to <figref idref="DRAWINGS">FIG. 7</figref>, the frustum construction approach of FastV can be generalized to the from-region case (i.e., now R can be any convex region). A fattened oriented bounding box BB can be computed (where the amount of “fattening” can be user-specified) that encloses R and subdivide its faces into a user-specified number of quad patches Q. The next step is to determine the set of primitives p such that there exists at least one ray from some point r ∈ R to p which passes through q. Put another way, this step is intended to determine all points from which R is partially visible through q. This corresponds to the region in front of q and bounded by the set of separating planes constructed between R and q. Referring to <figref idref="DRAWINGS">FIG. 7</figref>, separating planes PL₁and PL₂can be constructed between R and Q, and the frustum bounded by these planes can be traced and oriented such that Q is in the interior of the frustum. In this arrangement, O is a blocker for the separating frustum, and is used as an occluder for R.

0053Note that the separating planes can be oriented such that Q lies in the positive half-space (interior) defined by each separating plane s ∈ S. A separating frustum FR bounded by S can be constructed. The separating frustum need not be pyramidal. Rather, it is defined as the intersection of half-spaces bounded by the separating planes. View frustum culling techniques can be used to cull Π to f to estimate the PVS of R. However, this approach may compute a PVS π such that there exist primitives p₁,p₂∈ π where p_ioccludes p₂from R, and the resulting PVS would be too conservative. Instead, FastV can be used to trace frustum FR as shown in <figref idref="DRAWINGS">FIG. 7</figref>. Those having skill in the art will recognize that if R is in fact a single point, the occluder selection algorithm reduces to FastV.

0054In one embodiment, all the rays that start on R and pass through q can be traced, and the set of primitives reached would approach π_exact. However, tracing f using FastV computes a subset of triangles visible from R through Q (i.e., computes π <u style="single">⊂</u>_exact). This subtle difference between the from-point and from-region case occurs because using FastV with a separating frustum for a region R is not guaranteed to find all geometry reachable by rays starting on R for a given frustum subdivision level, as is shown in <figref idref="DRAWINGS">FIG. 9</figref>. Therefore, after occluder selection, a conservative occlusion culling algorithm can be used to compute a superset of the exact PVS.

0055Tracing frustum FR using FastV can return a blocker for frustum FR. This blocker is a connected set of triangles such that any ray originating on R and passing through q intersects the blocker. Therefore, all blockers returned by FastV can be used as occluders. However, it is possible that FastV may be unable to find a blocker for frustum FR. In such a case, the connected sets of triangles computed by FastV during scene traversal can be used as occluders, as is shown in <figref idref="DRAWINGS">FIG. 8</figref>.

0056Given a set of occluders for R, the next step is to perform occlusion culling to compute the PVS of R. In one embodiment the umbra of an occluder o can be determined with respect to R. Unfortunately, the boundary of an exact umbra is bounded by curved surfaces. A common workaround is to compute a shadow frustum bounded by these curved surfaces and use it to determine a subset of triangles occluded by o (thus computing a superset of the exact PVS for R). The shadow frustum is bounded by the supporting planes between R and o and thus can be easily computed.

0057Although one particular algorithm is described above, any existing object-precision technique can be used for occlusion culling, as long as it guarantees that the resulting PVS is conservative. In the present implementation, a simple CPU-based frustum culling method can be used. For each occluder o, the shadow frustum SF of o from R can be computed, and all primitives behind o and completely contained in SF can be marked as occluded from R. Once all shadow frusta SF have been processed in this manner, the primitives not marked hidden are added to the PVS of R.

0058Although the above provided one method for identifying the PVS, it should be understood that many other algorithms have also been proposed for conservative from-region visibility. Several algorithms exist for performing occlusion culling with respect to shadow frusta, with different trade-offs and limitations. For example, some conservative algorithms operate in the dual space of rays, by dividing the scene into cells separated by portals and computing stabbing lines through portals.

Image-Space or Sample-Based Visibility

0059These approaches sample the set of rays in Φ and compute a PVS, π_sampling, which is hit by only the finite set of sampled rays. Note that since π_samplingis computed for only a finite subset of rays in Φ, π_sampling<u style="single">⊂</u> π_exact. The choice of sampled rays is governed by the application. Sampling-based methods are widely used in graphics applications due to their computational efficiency and are well supported by current GPUs. Typically, during image generation, an image of a given resolution, say 1K×1K pixels and only a constant number of rays per pixel are sampled to generate an image. Sampling based methods are extensively used in computer graphics for image generation. However, these methods can suffer from spatial and temporal aliasing issues and may require supersampling or other techniques (e.g. filters) to reduce aliasing artifacts.

0060An example of from-point sample-based visibility is shown in <figref idref="DRAWINGS">FIG. 2</figref><i>a</i>. Only a few rays are sampled and intersected with the geometric primitives to find the visible primitives. This could lead to spatial aliasing, as shown in <figref idref="DRAWINGS">FIG. 2</figref><i>a</i>. The primitive P<b>3</b> is marked as hidden because it lies between two sampled rays even though it is visible from the view-point. Despite their short comings sample-based methods are widely used in computer graphics. Efficient implementation of sample-based visibility algorithms can be achieved on current graphics processing units (GPUs). The z-buffer algorithm is a standard sample-based visibility algorithm that is supported by the rasterization hardware in GPUs. Moreover, advanced support for sample-based visibility, such as from-point occlusion queries are also supported in GPUs. Also, sample-based ray shooting techniques have been used in computer graphics.

0061An example of from-region sample-based visibility is shown in <figref idref="DRAWINGS">FIG. 3</figref><i>a</i>. Similar to from-point visibility, the sampling in from-region algorithms introduces spatial aliasing. In this case, the primitive P<b>4</b> is marked as hidden even though there exists at least one ray from the view-region that reaches the primitive P<b>4</b>. Despite this omission, these methods are fast compared to exact and conservative from-region visibility algorithms and can easily be applied to complex models.

0062These methods have at least one important limitation, though. They sample a finite set of rays originating inside the view-region and thus compute only a subset of the exact solution (i.e., approximate visibility). Therefore, these methods are limited to sampling based applications such as interactive graphical rendering, and may not provide sufficient accuracy for applications where an accurate from-region solution is needed.

Geometric Acoustics and Visibility

0063New geometric sound propagation algorithms can be based on object-space conservative from-point and from-region visibility techniques. The present geometric sound propagation algorithms are based on the image source method. As originally formulated, the image source method can mainly simulate specular reflections. The most common methods include the image source method, ray tracing, and approximate volume tracing. Of these methods, the image source method is the most accurate, since it is guaranteed to not miss any specular propagation paths between the source and the listener. GA methods are also used for modeling diffuse reflections. The two main techniques of doing so are based on path tracing and radiosity.

0064Although it is considered relatively more difficult to model diffraction using GA methods (because diffraction involves sound waves bending around objects), it is possible to extend these methods to handle edge diffraction by introducing line or edge image sources. As noted above, the two most commonly used geometric models of diffraction are the Uniform Theory of Diffraction (UTD) and the Biot-Tolstoy-Medwin (BTM) model. The UTD model assumes infinite diffracting edges, an assumption which may not be applicable in real-world scenes (e.g., indoor scenes). However, UTD has been used successfully in interactive applications. BTM, on the other hand, deals with finite diffracting edges, and therefore is more accurate than UTD. It is much more complicated, however, and has only recently been used (with several approximations) in interactive applications.

0065The choice of visibility algorithm depends on the target application. For instance, room acoustics software requires accurate modeling of early specular reflections and edge diffraction, therefore, exact or conservative object-space visibility algorithms are most suitable. Similarly, for entertainment applications like games it might be possible to use sample-based visibility algorithms as temporal and spatial aliasing issues can be hidden by applying heuristics which reduce the accuracy of the simulation.

0066Another example is that the cost of computing the diffraction paths and IRs for double or triple diffraction for finite-edge diffraction using the BTM model could be so high that it might be worth looking into exact visibility approaches to compute the smallest PVS from an edge and thus minimize the path validation steps. The exact visibility algorithms are relatively expensive and it is hard to implement them robustly in 3D. However, the savings in the size of the visible set may result in improved overall performance.

Sample-Based Approaches

0067Due to their simplicity and efficiency, sampling based approaches are very popular in geometric acoustics, but the acoustic space has to be sampled densely to produce a robust solution. Since the sampling based approaches discretely sample the acoustic space, they introduce statistical errors and may miss critical early reflection paths. Many techniques like ray tracing, ray-frustum tracing, and other sample-based techniques have been applied to compute early specular reflection.

0068In addition, sample-based from-region visibility algorithms have not been used to accelerate finite-edge diffraction. Some recent techniques for sample-based from-region algorithms can be applied on simple scenes, but the impact of sampling needs to be carefully analyzed.

Object-Space Exact Approaches

0069The size of the visibility tree computed by exact object-space algorithms is guaranteed to be optimal. This improves the time taken by the path validation step since the number of potential paths to validate is the smallest. However, performing exact visibility to compute the visibility tree is compute intensive and may require a long time. Such methods have been applied for early specular reflection for limited scenes with a cell-and-portal structure. Applying these algorithms for early specular reflections for general scenes is computationally expensive and requires a robust implementation.

0070One possibility is to apply recently developed beam tracing algorithms for early specular reflection. Like sample-based approaches, no known exact object-space from-region has been applied to improve the finite-edge diffraction computation. It is possible to apply aspect graphs, visibility complex to compute from-region visibility from a diffracting edge. However, the computational complexity of such methods—O(n⁹) for aspect graphs and O(n⁴) for the visibility complex, where n is the number of scene primitives—makes them impractical for even the simple scenes. Moreover, these are global visibility algorithms and compute visibility from all points in the scene; they cannot be used to compute visibility from a given list of diffracting edges.

Object-Space Conservative Approaches

0071Given the computational complexity of exact approaches and aliasing issues with sampling-based approaches, conservative approaches offer an interesting alternative. Conservative approaches have lower runtime complexity as compared to the exact approaches and do not suffer from the aliasing errors that are common in sample-based approaches. The PVS computed by conservative approaches is larger than that computed by exact or sample-based visibility approaches, however, and therefore the size of visibility tree will be larger. Thus, the path validation step will take longer since there are more paths to validate. <figref idref="DRAWINGS">FIGS. 10</figref><i>a</i>-<b>10</b><i>d </i>compare different image-source methods. Given a sound source S and primitives (Ta, Tb, Tc, Td, and Te) the image source method shown in <figref idref="DRAWINGS">FIG. 10</figref><i>a </i>creates image-sources of S against all primitives in the scene. The beam tracing method shown in <figref idref="DRAWINGS">FIG. 10</figref><i>b </i>computes image-sources for only exactly visible triangles, Tb and Tc in this case. The accelerated beam tracing approach shown in <figref idref="DRAWINGS">FIG. 10</figref><i>c </i>computes image-sources for all triangles inside the beam volume (i.e., Tb, Tc, Td, and Te in this case). The present approach is shown in <figref idref="DRAWINGS">FIG. 10</figref><i>d </i>and computes image-sources for triangles Tb, Tc, and Td.

0072The main difference between these methods is in terms of which image sources they choose to compute. A naïve image-source method computes image sources for all primitives in the scene. Beam tracing methods compute the image sources for exactly visible primitives from a source (or image source). Methods based on beam tracing, like accelerated beam tracing, compute image sources for every primitive inside the beam volume. The present approach, shown in <figref idref="DRAWINGS">FIG. 10</figref><i>d</i>, finds a conservative PVS from a source and computes the image sources for the primitives in the conservative PVS. The present approach is based on a conservative from-point and a conservative from-region algorithm to compute early specular reflection and finite-edge diffraction.

0073Accelerated Beam Tracing, a variant of beam tracing, has also been applied for early specular reflections. Regarding conservative visibility algorithms for finite-edge diffraction, only view-frustum culling has been applied and the present approach for reducing edge pairs for edge diffraction is the only known implementation which uses visibility algorithms for finite edge diffraction.

Sound Scattering

0074In the previous sections, discussion of accelerating early specular reflections and finite-edge diffraction by applying visibility techniques is presented. However, only modeling specular reflections and finite-edge diffraction is insufficient to accurately predict the acoustics of an environment. Sound scattering (i.e., interaction of sound waves with objects of size comparable to its wavelength), is important to accurately model room acoustics.

0075The geometric room acoustics can be generalized by an integral equation called the acoustic rendering equation (see Eq. 1 below).

0076The acoustic rendering equation can be seen as an extension of the rendering equation in computer graphics.

0000<maths id="MATH-US-00001" num="00001"><math overflow="scroll"><mtable><mtr><mtd><mrow><mrow><mi>L</mi><mo></mo><mrow><mo>(</mo><mrow><msup><mi>x</mi><mi>′</mi></msup><mo>,</mo><mi>ω</mi></mrow><mo>)</mo></mrow></mrow><mo>=</mo><mrow><mrow><msub><mi>L</mi><mn>0</mn></msub><mo></mo><mrow><mo>(</mo><mrow><msup><mi>x</mi><mi>′</mi></msup><mo>,</mo><mi>ω</mi></mrow><mo>)</mo></mrow></mrow><mo>+</mo><mrow><msub><mo>∫</mo><mi>S</mi></msub><mo></mo><mrow><mrow><mi>R</mi><mo></mo><mrow><mo>(</mo><mrow><mi>x</mi><mo>,</mo><msup><mi>x</mi><mi>′</mi></msup><mo>,</mo><mi>ω</mi></mrow><mo>)</mo></mrow></mrow><mo></mo><mrow><mi>L</mi><mo></mo><mrow><mo>(</mo><mrow><mi>x</mi><mo>,</mo><mfrac><mrow><msup><mi>x</mi><mi>′</mi></msup><mo>-</mo><mi>x</mi></mrow><mrow><mo>|</mo><mrow><msup><mi>x</mi><mi>′</mi></msup><mo>-</mo><mi>x</mi></mrow><mo>|</mo></mrow></mfrac></mrow><mo>)</mo></mrow></mrow><mo></mo><mrow><mo></mo><mi>x</mi></mrow></mrow></mrow></mrow></mrow></mtd><mtd><mrow><mo>(</mo><mn>1</mn><mo>)</mo></mrow></mtd></mtr></mtable></math></maths><img file="US2012249556A1_D0003.tif" />

0077where L is final outgoing radiance, L₀is emitted radiance, and R is the reflection kernel, which describes how radiance at point x influences radiance at point x′:

0000<br /><i>R</i>(<i>x, x</i>′,ω)=ρ(<i>x, x</i>′,ω)<i>G</i>(<i>x, x</i>′)<i>V</i>(<i>x, x</i>′)<i>P</i>(<i>x, x</i>′)   (2)

0078Here, r is the BRDF of the surface at x, G is the form factor between x and x′, V is the point-to-point visibility function, and P is a propagation term that takes into account the effect of propagation delays. The latter is unique to sound rendering as visual rendering algorithms neglect propagation delays due to the high speed of light. Also, depending on the BRDF (or scattering function) of a surface, different scattering properties of the surface (e.g., diffuse reflections) can be modeled.

0079Several methods have been developed to solve the acoustic rendering equation. Ray tracing is a popular geometric algorithm for acoustic modeling and can model specular and diffuse reflections easily. There has been much research in the computer graphics community to develop fast algorithms for ray tracing, such as by taking advantage of multi-core and many-core architectures, efficient scene hierarchies, and other acceleration techniques. Radiosity is another technique to model sound scattering. These algorithms operate by sampling the surface primitives and computing transfer operators which essentially encode the impulse response due to each sample at every other sample.

Visibility Acceleration

0080Solving the acoustic rendering equation requires the computation of visibility between two points, V(x,x′). The visibility between two points ban be computed by shooting a ray from one point in the direction of the other. Hierarchies to organize scene geometry can be used to accelerate ray shooting and efficient handle scenes with moving geometries. Another possibility is to use from-region visibility data structures, like visibility complex or aspect graphs, to efficiently compute visibility between two points. These visibility algorithms are computation and memory intensive for large scenes. However, for small scene used in room acoustics it is might be feasible to apply from-region visibility data structures to accelerate sound scattering computations.

Sound Propagation Using Geometric Acoustics

0081To simulate sound propagation using GA methods, a point sound source, a CAD model with acoustic material properties, diffracting edges, and a listener position can be used to compute an impulse response (IR) of the acoustic space for the source and listener position. The IRs can be used to derive various acoustic parameters of a room. In <figref idref="DRAWINGS">FIG. 12</figref><i>a</i>, a CAD model (shown in top down view) consists of specular planes A to H and diffracting edges <b>1</b> to <b>8</b>. The positions of source S and listener L are also shown.

0082To compute the IR, all the specular and diffraction propagation paths that reach the listener from the source can be computed. To do this, a two-step approach based on the image-source method can be used (see <figref idref="DRAWINGS">FIG. 11</figref>). In a first step <b>200</b>, inputs for the scene can be provided, such as scene geometry or source and listener positions. Based on these inputs, a second step <b>210</b> can comprise constructing a visibility tree VT(S,k) from source S up to a user-specified k orders of reflection, which can include the occluder selection steps discussed above with respect to <figref idref="DRAWINGS">FIG. 5</figref>. Note that only image sources for a source S (or image source) with respect to the triangles and/or edges that are visible to S need to be computed. If S is a point source, for instance, this can involve from-point visibility computation. For example, regarding the image source IS of the source S about plane G in <figref idref="DRAWINGS">FIG. 12</figref><i>b</i>, only the image sources of IS about planes D, E, and F need to be computed for second order specular reflection from IS. If S is a line or an edge source, however, from-region visibility computation can be performed. Specifically, a from-edge visibility computation can be performed, which computes a superset of all the primitives that can be visible from any point on the edge.

0083For example, second order diffraction about the line source LS in <figref idref="DRAWINGS">FIG. 12</figref><i>c </i>can only occur with edges <b>5</b>, <b>7</b>, and <b>8</b>. The visibility algorithms can be applied recursively for point and line image sources to construct the visibility tree. An example visibility tree for the configuration in <figref idref="DRAWINGS">FIGS. 12</figref><i>a</i>-<b>12</b><i>c </i>is shown in <figref idref="DRAWINGS">FIG. 13</figref>. Each path in VT(S,k) represents a potential path contributing to the IR. Each path consists of a sequence of (up to k) triangles and/or edges that a ray starting from S reflects and/or diffracts about as it reaches the listener at the position L. For example, S→G→E denote all specular paths from the source that bounces off planes G and then E. Similarly, S→<b>6</b>→<b>7</b> denote all diffraction paths from the source that hit edge <b>6</b> and then edge <b>7</b>.

0084To compute the final path from visibility tree, however, a listener position is required. Thus, in the second step, given a listener position L, a listener node can be attached to every node in the tree, and for each potential path in VT(S,k), it can be determined which of the propagation paths are valid. Thus, validating S→G→E→L means finding a specular path from source that bounces off plane G and then plane E and then reaches the listener (<figref idref="DRAWINGS">FIG. 14</figref><i>a</i>). Similarly, validating S→<b>6</b>→<b>7</b>→L means finding multiple paths from the source that hit edge <b>6</b> followed by edge <b>7</b> and then reach the listener (<figref idref="DRAWINGS">FIG. 14</figref><i>b</i>). It is possible that some of the paths are blocked by other primitives in the scene and may not contribute to the IR. The second step can be referred to as path validation.

Image Source Method

0085Alternatively, given a point source S and a listener L, ray shooting can be used to check if a direct path exists from S to L. The basic idea behind the image source method is as follows. For a specular reflector T (in the present case, a triangle), a specular path S→T→L exists if and only if a direct path exists from the image of S formed by T, to L, and this direct path also passes through T. In the absence of any visibility information, image sources need to be computed about every triangle in the scene. This process can be applied recursively to check for higher order specular paths from S to L, but the complexity can increase exponentially as a function of the number of reflections.

0086For a given source position, this process can be accelerated by applying from-point visibility techniques. It is noted that first order image sources only need to be computed about triangles visible to S. For a first-order image source S₁, second-order image sources only need to be computed for the triangles that are visible to S₁through T, and so on for higher order image sources.

BTM Based Finite-Edge Diffraction

0087Analogous to how specular reflection about a triangle is modeled by computing the image of the source with respect to the triangle, diffraction about an edge is modeled by computing the image of the source with respect to the edge. The key idea is that the image source from a point source S with respect to diffracting edge E is that edge E itself. This means that image sources can now be points or line segments. It is further noted that the image of a point or line source S_iabout a planar specular reflector T is obtained by reflecting S_iacross the plane of T.

0088For a given edge source, the basic approach described above can be accelerated by applying from-region visibility techniques. Note that second-order diffraction image sources for an edge source S_ineed to be computed for edges that are visible from S_i. Also, specular reflections of S_ineed to be computed from triangles that are visible from S_i.

Results

0089Table 1 below summarizes the present results on early specular Tracing (ABT) algorithm, which is another conservative from-point visibility algorithm. Specular reflection results using the present methods and systems were obtained on models of complexity ranging from 438 triangles to 212K triangles. The performance on three benchmarks is also tested, and the timings for constructing the visibility tree is compared using both the present approach and ABT.

0000<tables id="TABLE-US-00001" num="00001"><table frame="none" colsep="0" rowsep="0"><tgroup align="left" colsep="0" rowsep="0" cols="4"><colspec colname="1" colwidth="56pt" align="left" /><colspec colname="2" colwidth="56pt" align="center" /><colspec colname="3" colwidth="35pt" align="center" /><colspec colname="4" colwidth="70pt" align="center" /><thead><row><entry namest="1" nameend="4" rowsep="1">TABLE 1</entry></row><row><entry namest="1" nameend="4" align="center" rowsep="1" /></row><row><entry>Model</entry><entry>Triangles</entry><entry>Time (sec)</entry><entry>Speed Up (ABT)</entry></row><row><entry namest="1" nameend="4" align="center" rowsep="1" /></row></thead><tbody valign="top"><row><entry /></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="4"><colspec colname="1" colwidth="56pt" align="left" /><colspec colname="2" colwidth="56pt" align="center" /><colspec colname="3" colwidth="35pt" align="char" char="." /><colspec colname="4" colwidth="70pt" align="center" /><tbody valign="top"><row><entry>Room</entry><entry> 438</entry><entry>0.16</entry><entry>10.1</entry></row><row><entry>Regular Room</entry><entry>1190</entry><entry>0.93</entry><entry>22.2</entry></row><row><entry>Complex Room</entry><entry>5635</entry><entry>6.50</entry><entry>11.8</entry></row><row><entry>Sibenik Cathedral</entry><entry>78.2K</entry><entry>72.00</entry><entry>—</entry></row><row><entry>Trade Show</entry><entry> 212K</entry><entry>217.60</entry><entry>—</entry></row><row><entry namest="1" nameend="4" align="center" rowsep="1" /></row></tbody></tgroup></table></tables><br /> As can be seen from this data, which outlines the performance of sound propagation algorithms for three orders of reflection on a single core, a 10-20× speedup can be observed for the simple models over accelerated beam tracing (ABT).

0090Two additional complex benchmarks can be used with 80K and 212K triangles. It is believed that there is not any other implementation of the image source method that can handle models of such complexity in tractable time. The performance of the present visibility algorithm can also be compared with a fast beam tracing algorithm, with the size of the PVS computed by the present methods converging to within 1-10% of the exact from-point beam tracing PVS (see <figref idref="DRAWINGS">FIG. 15</figref>). Thus, in terms of performance, the application of the present methods and systems is about 5-8 times faster on a single CPU core on the tested model as compared to conventional methods.

0091Table 2 below highlights the results on finite-edge diffraction. The performance of the present visibility tree construction step (using from-region visibility) is compared against visibility tree construction using only view-frustum culling (as applied in the MATLAB Edge Diffraction toolbox). The time required to build the visibility tree is compared as well as the size of the tree constructed for each approach.

0000<tables id="TABLE-US-00002" num="00002"><table frame="none" colsep="0" rowsep="0" pgwide="1"><tgroup align="left" colsep="0" rowsep="0" cols="3"><colspec colname="offset" colwidth="91pt" align="left" /><colspec colname="1" colwidth="133pt" align="center" /><colspec colname="2" colwidth="49pt" align="center" /><thead><row><entry /><entry namest="offset" nameend="2" rowsep="1">TABLE 2</entry></row></thead><tbody valign="top"><row><entry /><entry namest="offset" nameend="2" align="center" rowsep="1" /></row><row><entry /><entry>Second order diffraction paths in tree</entry><entry>Path validation</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="7"><colspec colname="1" colwidth="28pt" align="left" /><colspec colname="2" colwidth="35pt" align="center" /><colspec colname="3" colwidth="28pt" align="center" /><colspec colname="4" colwidth="49pt" align="center" /><colspec colname="5" colwidth="35pt" align="center" /><colspec colname="6" colwidth="49pt" align="center" /><colspec colname="7" colwidth="49pt" align="center" /><tbody valign="top"><row><entry>Scene</entry><entry>Triangles</entry><entry>Edges</entry><entry>Present method</entry><entry>MATLAB</entry><entry>Size reduction</entry><entry>Speedup</entry></row><row><entry namest="1" nameend="7" align="center" rowsep="1" /></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="7"><colspec colname="1" colwidth="28pt" align="left" /><colspec colname="2" colwidth="35pt" align="char" char="." /><colspec colname="3" colwidth="28pt" align="char" char="." /><colspec colname="4" colwidth="49pt" align="char" char="." /><colspec colname="5" colwidth="35pt" align="char" char="." /><colspec colname="6" colwidth="49pt" align="char" char="." /><colspec colname="7" colwidth="49pt" align="char" char="." /><tbody valign="top"><row><entry>Factory</entry><entry>170</entry><entry>146</entry><entry>4424</entry><entry>12570</entry><entry>2.84</entry><entry>1.93</entry></row><row><entry>Room</entry><entry>876</entry><entry>652</entry><entry>43488</entry><entry>181314</entry><entry>4.17</entry><entry>3.23</entry></row><row><entry>House</entry><entry>1105</entry><entry>751</entry><entry>133751</entry><entry>393907</entry><entry>2.95</entry><entry>13.74</entry></row><row><entry namest="1" nameend="7" align="center" rowsep="1" /></row></tbody></tgroup></table></tables><br /> From these results, it can be seen that using from-region visibility to reduce second order diffraction paths between mutually invisible edges can have significant benefits. In addition, the speedup caused during path validation by this reduction in the size of the visibility tree is likewise significant.

0092Table 3 below shows the breakdown of time spent in each step of the present algorithm. Specifically, Table 3 shows both the time spent in constructing a visibility tree (averaged over multiple source positions) and the time taken to compute the final IR (averaged over multiple source and listener positions.

0000<tables id="TABLE-US-00003" num="00003"><table frame="none" colsep="0" rowsep="0"><tgroup align="left" colsep="0" rowsep="0" cols="4"><colspec colname="offset" colwidth="14pt" align="left" /><colspec colname="1" colwidth="49pt" align="left" /><colspec colname="2" colwidth="63pt" align="center" /><colspec colname="3" colwidth="91pt" align="center" /><thead><row><entry /><entry namest="offset" nameend="3" rowsep="1">TABLE 3</entry></row><row><entry /><entry namest="offset" nameend="3" align="center" rowsep="1" /></row><row><entry /><entry>Scene</entry><entry>Visibility Tree (ms)</entry><entry>IR Computation (s)</entry></row><row><entry /><entry namest="offset" nameend="3" align="center" rowsep="1" /></row></thead><tbody valign="top"><row><entry /></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="4"><colspec colname="offset" colwidth="14pt" align="left" /><colspec colname="1" colwidth="49pt" align="left" /><colspec colname="2" colwidth="63pt" align="char" char="." /><colspec colname="3" colwidth="91pt" align="char" char="." /><tbody valign="top"><row><entry /><entry>Factory</entry><entry>141.0</entry><entry>23.9</entry></row><row><entry /><entry>Room</entry><entry>747.6</entry><entry>10.4</entry></row><row><entry /><entry>House</entry><entry>1045.6</entry><entry>24.3</entry></row><row><entry /><entry namest="offset" nameend="3" align="center" rowsep="1" /></row></tbody></tgroup></table></tables><br /> It is evident from the table that the “costliest” step of the present algorithm is the final IR computation as the path validation for edge diffraction requires shooting mil lions of rays. Constructing the visibility tree is much faster by comparison. <figref idref="DRAWINGS">FIGS. 16</figref><i>a </i>and <b>16</b><i>b </i>show the average percentage of total triangles (and diffracting edges) visible from the diffracting edges in various benchmark scenes. These plots clearly show that even in simple scenes, which are typically used for interactive sound propagation, the use of visibility algorithms helps reduce the complexity of the visibility tree computed by the present algorithm by a factor of 2 to 4.

0093Regarding occluder Selection for from-region visibility, running times of the present occluder selection step per triangle is presented in in Table 4. The table further reports the average size of each occluder (in terms of the number of triangles) returned by the occluder selection algorithm.

0000<tables id="TABLE-US-00004" num="00004"><table frame="none" colsep="0" rowsep="0"><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="84pt" align="left" /><colspec colname="1" colwidth="133pt" align="center" /><thead><row><entry /><entry namest="offset" nameend="1" rowsep="1">TABLE 4</entry></row></thead><tbody valign="top"><row><entry /><entry namest="offset" nameend="1" align="center" rowsep="1" /></row><row><entry /><entry>Occluder Selection</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="4"><colspec colname="1" colwidth="42pt" align="left" /><colspec colname="2" colwidth="42pt" align="center" /><colspec colname="3" colwidth="42pt" align="center" /><colspec colname="4" colwidth="91pt" align="center" /><tbody valign="top"><row><entry>Scene</entry><entry>Triangles</entry><entry>Time (s)</entry><entry>Avg. triangles per occluder</entry></row><row><entry namest="1" nameend="4" align="center" rowsep="1" /></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="4"><colspec colname="1" colwidth="42pt" align="left" /><colspec colname="2" colwidth="42pt" align="center" /><colspec colname="3" colwidth="42pt" align="char" char="." /><colspec colname="4" colwidth="91pt" align="char" char="." /><tbody valign="top"><row><entry>Floor</entry><entry>7.3K</entry><entry>0.12</entry><entry>6.0</entry></row><row><entry>Building</entry><entry> 69K</entry><entry>1.3</entry><entry>3.0</entry></row><row><entry>Soda Hall</entry><entry>1.5M</entry><entry>14.8</entry><entry>6.7</entry></row><row><entry namest="1" nameend="4" align="center" rowsep="1" /></row></tbody></tgroup></table></tables><br /> This data demonstrates how the present occluder selection algorithm is able to effectively combine connected triangles into larger occluders. This results in larger occluders, which can potentially allow more triangles to be culled. Moreover, the computational cost of state-of-the-art from-region occlusion culling algorithms tends to increase with an increase in the number of occluders. The time required for such computations can be reduced by using fewer, larger occluders formed by connected sets of triangles, such as those selected by our algorithm.

0094Table 5 compares the total running time for from-region visibility (occluder selection and occlusion culling) and the resulting PVS sizes when our occlusion culling implementation is provided with occluders computed using three approaches: no occluder selection (i.e., using all primitives as occluders), area-ratio heuristics, and the present occluder selection algorithm based on tracing separating frusta.

0000<tables id="TABLE-US-00005" num="00005"><table frame="none" colsep="0" rowsep="0"><tgroup align="left" colsep="0" rowsep="0" cols="4"><colspec colname="offset" colwidth="63pt" align="left" /><colspec colname="1" colwidth="49pt" align="center" /><colspec colname="2" colwidth="49pt" align="center" /><colspec colname="3" colwidth="56pt" align="center" /><thead><row><entry /><entry namest="offset" nameend="3" rowsep="1">TABLE 5</entry></row></thead><tbody valign="top"><row><entry /><entry namest="offset" nameend="3" align="center" rowsep="1" /></row><row><entry /><entry /><entry /><entry>Tracing</entry></row><row><entry /><entry>No Occluder</entry><entry>Area Ratio</entry><entry>Separating</entry></row><row><entry /><entry>Selection</entry><entry>Heuristic</entry><entry>Frusta</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="8"><colspec colname="1" colwidth="28pt" align="left" /><colspec colname="2" colwidth="35pt" align="center" /><colspec colname="3" colwidth="21pt" align="center" /><colspec colname="4" colwidth="28pt" align="center" /><colspec colname="5" colwidth="21pt" align="center" /><colspec colname="6" colwidth="28pt" align="center" /><colspec colname="7" colwidth="28pt" align="center" /><colspec colname="8" colwidth="28pt" align="center" /><tbody valign="top"><row><entry /><entry /><entry>Time</entry><entry>PVS</entry><entry>Time</entry><entry>PVS</entry><entry>Time</entry><entry>PVS</entry></row><row><entry>Scene</entry><entry>Triangles</entry><entry>(ms)</entry><entry>Size</entry><entry>(ms)</entry><entry>Size</entry><entry>(ms)</entry><entry>Size</entry></row><row><entry namest="1" nameend="8" align="center" rowsep="1" /></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="8"><colspec colname="1" colwidth="28pt" align="left" /><colspec colname="2" colwidth="35pt" align="char" char="." /><colspec colname="3" colwidth="21pt" align="char" char="." /><colspec colname="4" colwidth="28pt" align="char" char="." /><colspec colname="5" colwidth="21pt" align="char" char="." /><colspec colname="6" colwidth="28pt" align="char" char="." /><colspec colname="7" colwidth="28pt" align="char" char="." /><colspec colname="8" colwidth="28pt" align="char" char="." /><tbody valign="top"><row><entry>Factory</entry><entry>170</entry><entry>15.2</entry><entry>64</entry><entry>14.9</entry><entry>64</entry><entry>11.5</entry><entry>69</entry></row><row><entry>Room</entry><entry>876</entry><entry>240</entry><entry>356</entry><entry>241.4</entry><entry>356</entry><entry>102</entry><entry>379</entry></row><row><entry>House</entry><entry>1150</entry><entry>192</entry><entry>209</entry><entry>112.2</entry><entry>261</entry><entry>90</entry><entry>350</entry></row><row><entry namest="1" nameend="8" align="center" rowsep="1" /></row></tbody></tgroup></table></tables><br /> This table shows that using the occluder selection algorithm discussed above can significantly reduce total time spent in visibility computation as compared to the other approaches, at the cost of a relatively small increase in PVS size. It is noted that when selecting occluders using the area-ratio heuristic, the area-ratio is evaluated for each primitive and all primitives whose scores are greater than or equal to the median score are chosen as occluders.

0095Regarding impulse responses, the methods and systems according to the present subject matter implement the line integral formulation of the BTM model for performing path validation and computing impulse responses. One parameter in the validation step is the number of samples each edge is divided into. A higher number of samples per edge results in more accurate evaluation of the BTM integral at a higher computational cost. <figref idref="DRAWINGS">FIGS. 17</figref><i>a </i>through <b>17</b><i>c </i>show impulse responses computed for diffraction about a simple double wedge for increasing numbers of samples per edge. Specifically, <figref idref="DRAWINGS">FIG. 17</figref><i>a </i>shows the impulse response with 1K samples per edge, <figref idref="DRAWINGS">FIG. 17</figref><i>b </i>shows the impulse response with 10K samples per edge, and <figref idref="DRAWINGS">FIG. 17</figref><i>c </i>shows the impulse response with 44K samples per edge. As can be seen from the figures, increasing the number of samples causes the IRs to converge to the reference IR computed by a reference method (MATLAB Edge Diffraction toolbox), which is shown in <figref idref="DRAWINGS">FIG. 17</figref><i>d </i>for comparison.

0096It is further noted that although the computational cost of the BTM model remains higher than that of the UTD model, those having skill in the art will recognize that the BTM model is more accurate than UTD model at low frequencies, where diffraction plays an important role. Furthermore, the UTD approach does not model the diffraction contributions in regions where the listener is in line-of-sight of the source, whereas the BTM approach does. At low frequencies, numerical methods can be used to capture diffraction effects, but the complexity scales with the volume of the scene, as opposed to BTM-based methods whose complexity scales with the number of diffracting edges. Moreover, combining a numerical acoustics algorithm with geometric acoustics techniques for high frequency simulations remains a challenging problem, whereas the BTM approach can easily be combined with the image source method to compute accurate diffraction effects.

0097The subject matter described herein for simulating sound propagation in a scene can be implemented using a non-transitory computer readable medium having stored thereon executable instructions that when executed by the processor of a computer control the computer to perform steps. Exemplary computer readable media suitable for implementing the subject matter described herein can include chip memory devices, disk memory devices, programmable logic devices, and application specific integrated circuits. In addition, a computer readable medium for implementing the subject matter described herein may be located on a single device or computing platform or may be distributed across plural devices or computing platforms.

0098The present subject matter can be embodied in other forms without departure from the spirit and essential characteristics thereof. The embodiments described therefore are to be considered in all respects as illustrative and not restrictive. Although the present subject matter has been described in terms of certain preferred embodiments, other embodiments that are apparent to those of ordinary skill in the art are also within the scope of the present subject matter.