Abstract:
A system and method for rendering flows and volumes includes the steps of generating a preintegrated table, the preintegrated table having a plurality of entries, each of the plurality of entries having color information and opacity information, generating illustrative effects based on the plurality of entries of the preintegrated table and displaying the illustrative effects.

Description:
CROSS REFERENCE TO RELATED APPLICATION  
       [0001]     This application claims priority to U.S. Provisional Application 60/812,317 entitled SYSTEM AND METHOD FOR RENDERING FLOWS AND VOLUMES, filed on Jun. 9, 2006, the entirety of which is herein incorporated by reference. 
     
    
     BACKGROUND OF THE INVENTION  
       [0002]     1. Field of the Invention  
         [0003]     The preset invention generally relates to systems and method for rendering flows and volumes.  
         [0004]     2. Description of the Known Technology  
         [0005]     Flow simulations are used in different areas of science for various applications: from studying the flow around experimental aircrafts to analyzing cloud formation by air flow simulation. One critical, but difficult stage in the simulation process is analysis. Visualization is a key method for analyzing the simulation results and for providing meaningful feedback. As computational capabilities have increased in power and decreased in cost, the visualization community has faced significant challenges as the size, dimensionality and complexity of the simulation data has increased. Particularly, the simple step up from two-dimensional flow simulations to three-dimensional has rendered many existing flow visualizations techniques difficult to use. These techniques, when applied to three-dimensional flow data, tend to produce cluttered and hard-to-understand images.  
         [0006]     In recent works, we have seen the dramatic use of illustrative techniques applied to three dimensional flow datasets. The usage of these illustrative effects has been very effective in removing the usual clutter associated with three-dimensional flow visualizations. However, the approach has been limited to regular rectangular grids because the data was being converted to three-dimensional textures and rendered using hardware accelerated texture-based volume rendering.  
         [0007]     Flow visualization has received a lot of attention during past years, resulting in development of various techniques: vector glyphs, line integral convolution, texture advection and stream tracing (particle tracing, streamlines, and streaklines). While many of these techniques are effective for two-dimensional flows, the density of their representation often severely limits their effectiveness for three-dimensional flows, particularly in viscous flows and those containing boundary layers.  
         [0008]     Illustration has also been considered as a viable approach to improve the understanding of flow volumes, showing the potential of applying volume illustration techniques to scalar flow volumes and streamlines. One recent achievement in computer graphics and visualization is the ability to render datasets interactively by utilizing the graphic processing units (“GPUs”) on personal computer (“PC”) graphics cards. A number of works have been focused on extending the existing techniques onto the GPUs.  
         [0009]     Flow simulations very often produce regions in the volume that have finer grained detail than others. This is particularly true of viscous simulations or those that have boundary layer properties. For instance, we can be interested in the overall flow around an aircraft, but the particular details at the aircraft boundary are very important and need to be tracked. One common method for generating these simulations is by exploiting the positive aspects of non-regular grids. These grids allow small cells to be clustered in the boundary layer, and provide transitional cells to the far field where there is less need for fine grain detail and structure. Visualizing these grids, however, require methods that operate directly on the unstructured cells, rather than relying on resampling. Visualization techniques that operate on non-regular grids do not map directly to GPU textures. With general availability of graphics hardware acceleration, the respective works took advantage of GPU capabilities in the algorithm&#39;s implementation. The pre-integrated approach has improved the algorithm by using high-precision frame buffer blending].  
         [0010]     However, these previous systems are limited to applying these techniques to uniform grids. Unstructured grids have emerged as a common basis for computing flow simulations. Therefore, there is a need for a system and method for applying and extending the flow illustration approach to tetrahedral meshes using pre-integrated GPU-accelerated raycasting.  
       SUMMARY OF THE INVENTION  
       [0011]     In overcoming the enumerated drawbacks of the prior art, one embodiment of the present invention includes a general purpose computer having a processor and a display device. The processor of the general purpose computer has processor executable instructions for configuring the processor to generate a preintegrated table, the preintegrated table having a plurality of entries, each of the plurality of entries having color information and opacity information, generate illustrative effects based on the plurality of entries of the preintegrated table, and display the illustrative effects on the display device.  
         [0012]     Further objects, features and advantages of this invention will become readily apparent to persons skilled in the art after a review of the following description, with reference to the drawings and claims that are appended to and form a part of this specification. 
     
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0013]     The patent or application file contains at least one color drawing executed in color. Copies of this patent or patent application publication with color drawings will be provided by the Office upon request and payment of the necessary fee.  
         [0014]      FIG. 1  illustrates a ray traversal for a tetrahedral raycaster a information gathered from a current tetrahedron;  
         [0015]      FIG. 2A-2F  illustrate a gradient enhancement for a cylinder dataset;  
         [0016]      FIG. 3  illustrates an example of an opacity transfer function used in silhouette calculations;  
         [0017]      FIGS. 4A-4D  illustrate masked silhouettes for the cylinder dataset;  
         [0018]      FIGS. 5A and 5B  illustrate a curvature-based illustration for the cylinder dataset with two different p&#39;s;  
         [0019]      FIGS. 6A and 6B  illustrate banding of the scalar value of the cylinder dataset;  
         [0020]      FIGS. 7A and 7B  illustrate a volume rendering and gradient enhancement for the Bluntfin dataset, respectively;  
         [0021]      FIGS. 8A-8E  illustrate the effects for the Combustion Chamber dataset;  
         [0022]      FIGS. 9A and 9B  illustrates a shock dataset;  
         [0023]      FIG. 10  is a block diagram of a Schlieren system;  
         [0024]      FIG. 11  is a block diagram of a shadowgraph system; and  
         [0025]      FIG. 12  is a block diagram of a general purpose computer capable of executing a method for rendering flows and volumes. 
     
    
     DETAILED DESCRIPTION OF THE INVENTION  
       [0026]     One embodiment of the present invention is based on pre-integrated volume rendering. This technique has been very useful in both texture-based volume rendering and tetrahedral mesh rendering. In this section, an overview of the hardware-accelerated raycasting algorithm and of the pre-integration method is produced. Next, described is the modifications introduced in these approaches to generate illustrative effects and show how they help gain insight into flow data.  
         [0027]     Hardware-accelerated pre-integrated volume rendering precomputes the ray integral for each rendering primitive using the ray entry and exit point values (s (f) , s (b) ), the thickness of the primitive l, and stores these in the table texture. During the rendering step, for each ray, the s (f) , S (b) ), l) values are extracted and used as indices for pre-integration table lookup. The implementation of volume rendering on regular grids using a two-dimensional pre-integration table, because the thickness of their rendering primitive (volume “slabs”) is constant.  
         [0028]     Referring to  FIG. 1 , when raycasting tetrahedral meshes the pre-integration can be performed using three-dimensional pre-integrated tables, since the sample opacity depends on the thickness of the corresponding ray segment; i.e. the distance l between entry point (p (f) ) and exit point (p (b) ) for the current tetrahedron, as well as the values at these points s (f)  and s (b)  respectively.  
         [0029]     The key difference for the illustrative effects described is the modification of this pre-integrated table. Described is a method showing how this modification is performed to obtain different effects. It is important to mention that, since most of the illustration techniques presented here is based on the gradient of the input data, gradient estimation is a major issue. Barycentric interpolation is utilized to estimate the gradient, obtaining good results despite the fact that the gradients thus obtained are constant within a tetrahedron. This is expected for datasets with good resolution where regions of interest are high-sampled. The illustrative effects introduced are accomplished either by modifying the shader or the pre-integrated table. The pre-integrated table is calculated from a transfer function indexed by a computed view-dependent value, e.g. view dependent gradient magnitude. This approach for silhouetting is described below.  
         [0030]     Additionally, we introduce a different approach for illustrative effects based on gradient enhancement, silhouetting, curvature enhancement and banding by using the computed view-dependent value to modify the entries of the pre-integrated table calculated from a classic transfer function indexed by the input data. For that, a scaling mask m, which depends on the illustrative effect, is computed as described below and used to scale the extinction coefficient linearly to modify the associated color C{hacek over ( )} (m) (s (f) ; s (b) ; l) and opacity α(s (f) ; s (b) ; l) stored at each entry (s (f) ; s (b) ; l) of the pre-integrated table. The masked opacity α (m) (s (f) ; s (b) ; l) and the masked associated color C{hacek over ( )} (m) (s (f) ; s (b) ; l) are obtained with Equations 1 and 2 respectively.  
                 α     (   m   )       ⁡     (       s     (   f   )       ,     s     (   b   )       ,   l     )       =     1   -       ⅇ     (     m   ⁢           ⁢     log   ⁡     (     1   -     α   ⁡     (       s     (   f   )       ,     s     (   b   )       ,   l     )         )         )       .               (   1   )                     C   ~       (   m   )       ⁡     (       s     (   f   )       ,     s     (   b   )       ,   l     )       =           α     (   m   )       ⁡     (       s     (   f   )       ,     s     (   b   )       ,   l     )         α   ⁡     (       s     (   f   )       ,     s     (   b   )       ,   l     )         ⁢         C   ~     ⁡     (       s     (   f   )       ,     s     (   b   )       ,   l     )       .               (   2   )             
 
         [0031]     An illustrative effect can be achieved by masking the entries of the pre-integrated table using view-dependent gradient magnitudes. While not as accurate as the full gradient magnitude enhancement, it tends to highlight parts of essential high-gradient dataset features. Since the pre-integrated table is conveniently indexed by s (f) , s (b)  and l, for every entry in the table we can calculate view-dependent gradient magnitude and arbitrarily modify the color/opacity based on the value (e.g. gradient magnitude iso-lines, low gradient magnitude sample cull, negative gradient magnitude sample cull). For instance, given the approximated view-dependent gradient magnitude (s (b) −s (f) )/l, the mask m could be defined as  
                 ω   ⁡     (              s     (   f   )       -     s     (   b   )         l          )       p     ,           (   3   )             
 
 where ω is an artificial used-defined opacity scaling factor and ρ is a scalar that controls how much the gradient magnitude affects the opacity of the pre-integrated table entry.  FIGS. 2A-2E  show the result of using this illustration technique on the Cylinder dataset. Notice that the same transfer function is used in all cases.  FIGS. 2A-2C  show volume rendering without illustration, gradient enhancement and gradient enhancement with highlighting of the surface, respectively.  FIGS. 2D-2F  gradient enhancement with different values of ρ. 
 
         [0032]     A similar approach can be used for contour enhancement. As was originally presented in the work by Ebert and Rheingans, the contour/silhouette information can be extracted from the dataset by calculating φ=&lt;n;v &gt;, where n is the normalized gradient vector, v is the view vector and &lt;·, ·&gt;is the scalar product. A one-dimensional opacity transfer function α(φ) is then used to highlight areas where φ is close to 0 (the graph of an example of such function is shown in  FIG. 3 ).  
         [0033]     This filter shows only the samples where v and n are near orthogonal, which corresponds to a contour line of a surface, and works also rather well in volumes, where the normal vector n is approximated by 3D gradient vectors calculated from the original scalar field. These illustrative effects are shown in  FIGS. 8A-8E .  FIGS. 8A-8E  show no illustration, banding, gradient enhancement, mixed silhouettes and volume rendering, and masked silhouettes, respectively.  
         [0034]     Another way of obtaining gradient-based contours/silhouettes is by masking the entries of the pre-integrated table similarly to the view-dependent gradient enhancement effect. The mask m is obtained using the following formula 
 
g(∥∇f∥)·(1−|φ|) p ,   (4) 
 
 where ∇f is the gradient and g(·) is a windowing function (usually a linear function clamped to [0;1]) used to restrict the detection of contours to the interfaces between different materials. Results obtained for the Cylinder dataset with this technique are shown in  FIGS. 4A-4D .  FIGS. 4A-4D  show silhouettes, mixed silhouettes and surface rendering, top view of the silhouettes, top view of mixed silhouettes and volume rendering, respectively. 
 
         [0035]     Curvature-based illustration is obtained by estimating the curvature for the segment between s (f)  and s (b)  as ∥(n (b) −n (f) )=ll∥. The mask m used in this case is given by  
                 ω   (                n   →       (   f   )       -       n   →       (   b   )              l     )     p     .           (   5   )             
 
  FIGS. 5A and 5B  show visual results of this illustrative effect for the cylinder dataset with two different p&#39;s. 
 
         [0036]     Banding is achieved by scaling the entries of the pre-integrated table with the mask:  
                 (       1   +     sin   ⁡     (       o   o     ⁢   π   ⁢           ⁢   k     )         2     )     p     .           (   6   )             
 
 where o o  is the value to mask (e.g. scalar value, gradient magnitude).  FIGS. 6A and 6B  show mixed banding and volume rendering and banding with lower p, respectively. 
 
         [0037]     The implementation of our single-pass raycaster is modified to include the illustration techniques described above. As before, the data structure holding the tetrahedral mesh is stored in a set of textures used by the shader to calculate, for each iteration of the ray integral computation, the current tetrahedron and its entry and exit points. As in previous work the values at these points are interpolated from the values stored at the vertices of the tetrahedron using barycentric coordinates. The values obtained and the distance between the points are used to fetch the contribution of the ray segment to the ray integral from the pre-integrated table modified by our techniques. Also implemented may be the logarithmic sampling.  
         [0038]     Two other ways of rendering include the Schlieren and shadowgraph photographic processes. As shown in  FIG. 10 , the Schlieren photographic process uses an optical system  10  to capture density gradient variations in inhomogeneous media. When illuminated with a light source  12  that is made parallel by a first lens  14 , the optical in homogeneities refract the light rays in proportion to the gradients of the refractive index projected by a second lens  16  on the xy-plane  18 , which is orthogonal to the light direction. This refraction produces a two-dimensional displacement of the light ray (Equation 7), and the Schlieren knife edge apparatus  19  is able to measure this displacement&#39;s projection in a specific one dimensional direction on the xy-plane  18 , called the knife edge angle, which is the main parameter of the process. Therefore, in classic Schlieren photographs, darker regions correspond to negative displacement, brighter regions correspond to positive displacement, and the knife-edge angle is usually chosen to provide the best visualization of particular features. Extensions of Schlieren techniques include using a circular cutoff that visualizes the displacement vector&#39;s magnitude, and color Schlieren photographs, that essentially create a “color-wheel” visualization of the displacement. Schlieren techniques have been developed for regular datasets, as well as unstructured datasets.  
               ɛ   →     =       (       ɛ   x     ,     ɛ   y       )     =     k   ⁡     (         ∫     z   0       z   1       ⁢         ∂   ρ       ∂   x       ⁢           ⁢     ⅆ   z         ,       ∫     z   0       z   1       ⁢         ∂   ρ       ∂   y       ⁢           ⁢     ⅆ   z           )                 (   7   )             
 
         [0039]     As shown in  FIG. 11 , the shadowgraph observation setup  20  is simpler, since it only contains a light source  22  made parallel by a lens  24 , which is projected onto a screen  26 . Due to in homogeneities in the test area, refraction within the affected region displaces the light ray before it reaches the screen, changing the luminance distribution on the screen. Note that this luminance shift only occurs when the displacement vector e along the x or y axes changes. Thus, the resulting luminance map value can be approximated by the following:  
             L   =         ∫     z   0       z   1       ⁢       (         ∂     ɛ   x         ∂   x       +       ∂     ɛ   y         ∂   y         )     ⁢           ⁢     ⅆ   z         =       ∫     z   0       z   1       ⁢       (         ∂     ρ   2         ∂     x   2         +       ∂     ρ   2         ∂     y   2           )     ⁢           ⁢     ⅆ   z                   (   8   )             
 
         [0040]     Interactive Schlieren computer visualizations of three-dimensional flows have not been produced, although some commercial packages incorrectly refer to boundary enhancement as Schlieren results. We have extended our texture-based volume rendering system to simulate and enhance the Schlieren and shadowgraph techniques. The Schlieren integral is calculated using two rendering passes. In the first pass, slice rendering performs the integration of the separate components of the displacement vector e and stores them in the R and G components of a floating-point pixel buffer. Since the classic Schlieren setup places the light source directly behind the test area, we use front-to-back slicing to integrate along the light path. Note that this integral of positive and negative displacements allows them to cancel out their effects as in the experimental Schlieren system. For visualization of two-dimensional datasets and single slice visualization, only a single slice is rendered in this pass. The second pass transforms the displacement vector map to the actual image, scaling the resulting color by the sensitivity coefficient, s, according to the particular Schlieren method we want to simulate: knife-angle cutoff (Equation 9, where k is a normal to the knife edge), or circular cutoff:  
             I   =     s   ⁢       (     1   +     (       ɛ   →     ·     k   →       )       )     2               (   9   )               I   =     s   ⁢          ɛ   →                    (   10   )             
 
         [0041]     The shadowgraph integral (Equation 7) is computed analogously, except that the value of L is scalar. Therefore, during the second rendering pass, the calculations simplify to the following:  
             I   =     s   ⁢       (     1   +   L     )     2               (   11   )             
 
         [0042]     The most obvious and important limitation of the classic Schlieren photographic approach is that the experimental apparatus does not allow flexible control over which portion of the data is photographed: it always covers the entire test area, thus lacking the ability to focus on a particular location. There is active research in physics to extend the classic Schlieren approach and construct more complicated apparatuses to overcome these limitations. Our Schlieren renderer, however, allows us to easily filter the data according to the value or location, using regular transfer functions and distance-based transfer functions during the first pass, thus overcoming these obstacles and producing improved Schlieren images.  
         [0043]     Depending on the illustration technique applied to the data, modifications to the raycaster can be introduced either in the pre-integrated table computation or in the shader. These modifications are described in the following.  
         [0044]     Gradient enhancement: As described above, view dependent gradient enhancement is achieved by scaling each entry of the pre-integrated table using Equations 7 and 8 and the mask given by Equation 9. Therefore, the only modification to the raycaster is introduced after computing the pre-integrated table, where a function that scales the opacity of each entry of the table is called.  
         [0045]     Silhouettes: A pre-integrated table is calculated as usual but instead of using the interpolated values s (f)  and s (b)  at the entry and exit points respectively to perform the color and opacity fetch, a pre-integrated table indexed by (φ (f) ;φ (b) ; l). The shader is then modified to calculate and use (φ (f) ; φ (b) ; l) as indices to the pre-integrated table lookup. Since the gradient is constant within a tetrahedron, we take the gradient of the current tetrahedron as φ (f)  and the gradient of the next intersected tetrahedron as φ (b) . Alternatively, gradients can be pre-computed at the vertices, interpolate them on the face (in the shader stage), normalize them, and then project them onto the view direction to obtain more accurate results.  
         [0046]     Masked silhouettes: Another approach we used to generate silhouettes from the gradient information is simply masking the color and opacity stored in the pre-integrated table, as done for the gradient enhancement. For that we use the mask given by Equation 4. However, since scan only be calculated in the fragment shader, the masking takes places during rendering using Equations 1 and 2.  
         [0047]     Curvature-based: As in the case of gradient-based masked contour effects (masked silhouettes) the mask in this case can be calculated only during rendering. Therefore, we follow the same approach and modify the shader to use Equations 1 and 2 to apply the mask given by Equation 5.  
         [0048]     Banding: Banding is achieved by masking the entries of the pre-integrated table using the mask given by Equation 6. As in the case of gradient enhancement, this process occurs right after computing the pre-integrated table. Thus, no modification is introduced into the rendering process.  
         [0049]     Referring to  FIG. 12 , a system  30  for executing the methods discussed in the previous paragraphs is shown. The system  30 , includes a general purpose computer  32 , a display  34  and at least one input device such as a keyboard  36  and/or a mouse  38 . The general purpose computer  32  may include a graphics processing unit such as an NVidia GeForce 7800 gtx (512 MB) graphics card. The general purpose computer  32  is configured to execute the methods described in the previous paragraphs. As such, any visual displays created by the methods discussed in the previous paragraphs are displayed on the display  34 .  
         [0050]     Table 1 shows the performance results for the illustration techniques presented. We notice that the performance change is depreciable even for datasets with millions of tetrahedra.  
                                                           TABLE 1                           Performance in frames per second for the test       datasets with the illustration techniques presented.                Bluntfin   Comb.   Cylinder   Shock                    Num. tetrahedra   187395   215040   624960   1923048       Vol. rendering   6.69   4.74   5.09   2.88       Grad. enhance.   6.56   4.68   5.12   2.99       Curvature-based   6.92   5.26   4.96   2.51       Banding   6.56   4.68   5.12   2.24       Silhouettes   6.74   5.02   4.98   2.94       Masked silh.   6.21   4.99   5.05   2.78                  
 
 Also, we can see that, although the Cylinder dataset is larger than the Combustion Chamber dataset, the performance is almost the same. This is probably due to the projected size in pixels of the volume and the early ray termination included in the fragment shader which causes a decrease in the processing time when the opacity is increased. It is worth mentioning, that for the performance measurements we employed the transfer functions used to generate the figures included in this paper. 
 
         [0051]     From the set of figures shown above, we can see that flow structures can be extracted from the data using the illustrative effects described. It is important to notice that this is not true for each and every dataset, as depicted in  FIGS. 7A and 7B , which illustrate a volume rendering and gradient enhancement for the Bluntfin dataset, respectively. However, for the case of the Cylinder ( FIGS. 2-6 ), Combustion Chamber ( FIGS. 8A and 8B ) and Shock ( FIGS. 9A and 9B ) dataset, flow structures were extracted by applying illustrative effects without needing to spend much time in finding a proper transfer function, as is generally needed with normal volume rendering.  
         [0052]     Volume illustration applied to flow datasets helps gain insight into the structures contained in the flow data. The problem of employing illustration techniques was approached only for flow datasets on regular grids. However, there are a significant number of simulations that are computed on unstructured grids. Previous work took a shortcut to skirt this problem by resampling the parts of the flow datasets onto a regular grid.  
         [0053]     Applying illustrative effects directly to tetrahedral grids makes the investigation of such datasets easier. Although we have shown how these effects can be applied to such grids, there are still issues to be solved, such as a semiautomatic setting of the parameters used for each technique, and the removing of artifacts that arise due to the constant gradient within each tetrahedron.  
         [0054]     As a person skilled in the art will readily appreciate, the above description is meant as an illustration of implementation of the principles of this invention. This description is not intended to limit the scope or application of this invention in that the invention is susceptible to modification, variation and change, without departing from the spirit of this invention, as defined in the following claims.