System and a method for determining approximate set of visible objects in beam tracing

Abstract

A computer-implemented method for acoustic beam tracing in a three dimensional space, wherein a set of beams is a representation of a physical wave phenomenon. The method comprises receiving information regarding a beam and objects potentially intersecting the beam; executing beam-triangle intersection tests; dividing the beam into partial beams; executing beam-triangle intersection tests, with respect to the partial beams; dividing the partial beams into smaller partial beams; approximating the smaller partial beams with rays; creating delimited smaller partial beams; and applying merging of the delimited smaller partial beams.

We claim: 
     
         1 . A computer-implemented method for acoustic beam tracing in a three dimensional space, wherein a set of beams is a representation of a physical wave phenomenon, the method comprising the steps of:
 a) receiving information regarding a beam and objects potentially intersecting the beam, wherein information regarding potentially intersecting objects is input as a representation of a scene composed of objects;   b) executing beam-triangle intersection tests, with respect to the beam and the objects to discard, and discarding the objects which do not intersect the beam   c) dividing the beam into partial beams;   d) executing beam-triangle intersection tests, with respect to the partial beams and the objects and discarding the objects which do not intersect the partial beams;   e) dividing the partial beams into smaller partial beams;   f) approximating the smaller partial beams with rays, wherein the ray approximating the smaller partial beam has a beginning at the same point as a beginning of that smaller partial beam;   g) for each ray, finding a closest object by checking all the objects intersecting with the smaller partial beam which is approximated with that ray in step (f) and selecting the object which is located closest to the beginning of the ray as the closest object;   h) creating delimited smaller partial beams by delimiting the smaller partial beams with the closest object for the ray approximating that smaller partial beam;   i) applying merging of the delimited smaller partial beams.   
     
     
         2 . The method according to  claim 1  wherein the representation of a scene is a scene tree. 
     
     
         3 . The method according to  claim 1  further comprising providing data for parallel processing partial beams and respective objects in relation to the partial beams. 
     
     
         4 . The method according to  claim 1  wherein the object located closest to the beginning of a ray approximating this particular smaller partial beam is determined based on a ray-triangle intersection test. 
     
     
         5 . The method according to  claim 4  wherein the ray-triangle intersection test is the Ingo Wald's test. 
     
     
         6 . The method according to  claim 4  wherein the ray-triangle intersection tests are executed in parallel with a use of SSE or AVX instructions. 
     
     
         7 . The method according to  claim 1  wherein the merging of smaller partial beams is executed for smaller partial beams delimited by matching objects. 
     
     
         8 . The method according to  claim 1  wherein the matching objects are the same object or two different objects located on the same plane and having the same material. 
     
     
         9 . The method according to  claim 1  wherein the set of beams is a representation of a sound wave. 
     
     
         10 . The method according to  claim 1 , wherein the beams originate from a volumetric source. 
     
     
         11 . The method according to  claim 1 , wherein the beams originate from a directional source. 
     
     
         12 . The method according to  claim 1 , further comprising creating groups of smaller partial beam parts delimited by compatible limiting surfaces. 
     
     
         13 . A system for acoustic beam tracing in a three dimensional space, wherein a set of beams is a representation of a physical wave phenomenon, the system comprising:
 a hierarchical model memory for storing a scene representation;   a dedicated signal processor for performing intersection tests of ray-triangle and beam-triangle type; and   a controller, coupled via a bus to the processor, configured to execute the steps of:   a) receiving information regarding a beam and objects potentially intersecting the beam, wherein information regarding potentially intersecting objects is input as a representation of a scene composed of objects;   b) executing beam-triangle intersection tests, with respect to the beam and the objects, and discarding the objects which do not intersect the beam;   c) dividing the beam into partial beams;   d) executing beam-triangle intersection tests, with respect to the partial beams and the objects and discarding the objects which do not intersect the partial beams;   e) dividing the partial beams into smaller partial beams;   f) approximating the smaller partial beams with rays, wherein the ray approximating the smaller partial beam has a beginning at the same point as a beginning of that smaller partial beam;   g) for each ray, finding a closest object, by checking all the objects intersecting with the smaller partial beam which is approximated with that ray in step (f) and selecting the object which is located closest to the beginning of the ray as the closest object;   h) creating delimited smaller partial beams by delimiting the smaller partial beams with the closest object for the ray approximating that smaller partial beam;   i) applying merging of the delimited smaller partial beams.