Abstract:
A rasterizer, based on time-dependent edge equations, computes analytical visibility in order to render accurate motion blur. An oracle-based compression algorithm for the time intervals lowers the frame buffer requirements. High quality motion blurred scenes can be rendered using a rasterizer with rather low memory requirements. The resulting images may contain motion blur for both opaque and transparent objects.

Description:
CROSS-REFERENCE TO RELATED APPLICATIONS 
       [0001]    This application is a continuation of U.S. patent application Ser. No. 13/004,928, filed on Jan. 12, 2011. 
     
    
     BACKGROUND 
       [0002]    This relates to digital image processing and, particularly, depictions of motion blurring and compression techniques. 
         [0003]    Motion blur is generated when the shutter of the camera is open for a finite time, and some relative motion appears inside the field of view of the camera. It is an effect that is important for offline rendering for feature films, since the frame rate is rather low (˜24 frames per second). With motion blur in the rendered images, apparent jerkiness in the animation can be reduced or removed entirely. However, motion blur is also becoming an important visual effect for real-time rendering, e.g., for games. In order to get good performance, various rather crude approximations, that may or may not apply in all cases, are used. 
         [0004]    In general, motion blur rendering can be divided into two parts, namely, visibility determination and shading computations. Most solutions that converge to a correctly rendered image are based on point sampling. The more samples that are used the better image is obtained, and at the same time, the rendering cost goes up. In many cases, one can obtain reasonable results with rather few shader samples compared to the number of visibility samples. For example, RenderMan uses only a single shader sample for motion-blurred micro polygons. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0005]    Some embodiments are described with respect to the following figures: 
           [0006]      FIGS. 1 and 2  include depictions, at the top, of side surfaces rendered as patches with the corresponding depth function, plotted underneath; 
           [0007]      FIG. 3  depicts interval insertion over four cases; 
           [0008]      FIG. 4  depicts merging two depth functions with similar depth functions, showing results with and without compression; 
           [0009]      FIG. 5  is a flow chart for one embodiment; and 
           [0010]      FIG. 6  is a hardware depiction for one embodiment. 
       
    
    
     DETAILED DESCRIPTION 
       [0011]    The motion blur visibility problem may be solved analytically in order to avoid sampling noise. One embodiment involves rasterization of motion-blurred triangles with analytical visibility. However, a planar polygon with n number of vertices may be used. 
         [0012]    Assume that the entire transform matrix, including projection, for a vertex is called M. A vertex in homogeneous clip space is then obtained as |p=M  p ,| where  p  is the vertex in three-dimensional object space, and p is the resulting four-dimensional vertex in homogeneous clip space, i.e., before division by the w-component. To simplify the derivation, we use the following notation: {circumflex over (p)}=(p x , p y , p w ), which is a scaled and translated version of the point in camera space. This can be confirmed by looking at the definition of the projection matrix in OpenGL and DirectX. 
         [0013]    The standard (no motion) edge function, in homogeneous form, through two vertices, say {circumflex over (p)} 0  and {circumflex over (p)} 1 , is: 
         [0000]        e ( x,y,w )=( {circumflex over (p)}   1   ×{circumflex over (p)}   0 )·( x,y,w )= ax+by+cw.   (1)
 
         [0014]    A sampling point, (x,y,w), is inside the triangle if e i (x, y, w)≦0 for iε{0,1,2}, i.e. for the three edges of the triangle. Next, this is extended with a time dimension. 
         [0015]    Assume that the vertices move linearly from the beginning of a frame, at t=0, to the end for a frame, at t=1. At t=0, we denote the vertices as q i , and we call them r i  at t=1. Since there is no bar nor a hat on the vertices, all q i  and r i  are in homogeneous clip space. A linearly interpolated vertex is then given as: 
         [0000]        p   i ( t )=(1− t ) q   i   +tr   i ,  (2)
 
         [0000]    for a certain instant tε[0,1]. The coefficients of a time-dependent edge equation are given by: 
         [0000]      ( a,b,c )=( {circumflex over (p)}   1   ×{circumflex over (p)}   0 )=((1− t ) {circumflex over (q)}   1   +t{circumflex over (r)}   1 )×((1− t ) {circumflex over (q)}   0   +t{circumflex over (r)}   0 )= t   2   f+tg+h,   (3)
 
         [0000]      where: 
         [0000]        h={circumflex over (q)}   1   ×{circumflex over (q)}   0 , 
         [0000]        k={circumflex over (q)}   1   +{circumflex over (r)}   0   +{circumflex over (r)}   1   ×{circumflex over (q)}   0 , 
         [0000]        f=h−k+{circumflex over (r)}   1   ×{circumflex over (r)}   0 . 
         [0000]        g=− 2 h+k.   (4)
 
         [0000]    Each edge equation is now a function of time consisting of three functions: (a(t),b(t),c(t)), where, for example, a(t)=f x t 2 +g x t+h x . Finally, the entire time-dependent edge equation is: 
         [0000]        e ( x,y,t )= a ( t ) x+b ( t ) y+c ( t ),  (5)
 
         [0000]    where we have set w=1 since rasterization is done in screen space (x,y). 
         [0016]    For now, we assume that each pixel has a single sample point at (x 0 ,y 0 ). Extensions to multi-sampling and super-sampling just increase the sampling rate. If we consider a particular pixel, then (x 0 ,y 0 ) are constant. In this case, the time-dependent edge function becomes a function of time, t, alone: 
         [0000]        e ( x   0   ,y   0   ,t )= e ( t )= a ( t ) x   0   +b ( t ) y   0   +c ( t ).  (6)
 
         [0000]    This expression can be expanded using Equation 3: 
         [0000]    
       
         
           
               
             
               
                 
                   
                     
                       
                         
                           
                             e 
                              
                             
                               ( 
                               t 
                               ) 
                             
                           
                           = 
                           
                             
                               
                                 t 
                                 2 
                               
                                
                               
                                 ( 
                                 
                                   
                                     
                                       f 
                                       x 
                                     
                                      
                                     
                                       x 
                                       0 
                                     
                                   
                                   + 
                                   
                                     
                                       f 
                                       y 
                                     
                                      
                                     
                                       y 
                                       0 
                                     
                                   
                                   + 
                                   
                                     f 
                                     z 
                                   
                                 
                                 ) 
                               
                             
                             + 
                             
                               t 
                                
                               
                                 ( 
                                 
                                   
                                     
                                       g 
                                       x 
                                     
                                      
                                     
                                       x 
                                       0 
                                     
                                   
                                   + 
                                   
                                     
                                       g 
                                       y 
                                     
                                      
                                     
                                       y 
                                       0 
                                     
                                   
                                   + 
                                   
                                     g 
                                     z 
                                   
                                 
                                 ) 
                               
                             
                             + 
                             
                               ( 
                               
                                 
                                   
                                     h 
                                     x 
                                   
                                    
                                   
                                     x 
                                     0 
                                   
                                 
                                 + 
                                 
                                   
                                     h 
                                     y 
                                   
                                    
                                   
                                     y 
                                     0 
                                   
                                 
                                 + 
                                 
                                   h 
                                   z 
                                 
                               
                               ) 
                             
                           
                         
                       
                     
                     
                       
                         
                           
                             = 
                             
                               
                                 α 
                                  
                                 
                                     
                                 
                                  
                                 
                                   t 
                                   2 
                                 
                               
                               + 
                               
                                 β 
                                  
                                 
                                     
                                 
                                  
                                 t 
                               
                               + 
                               γ 
                             
                           
                           , 
                         
                       
                     
                   
                 
                 
                   
                     ( 
                     7 
                     ) 
                   
                 
               
             
           
         
       
     
         [0000]    where (α, β, γ) are constants for a certain sample point, (x 0 ,y 0 ). Hence, each edge equation is a quadratic function in t. Next, we introduce a binary inside-function, i(t), as: 
         [0000]    
       
         
           
             
               
                 
                   
                     i 
                      
                     
                       ( 
                       t 
                       ) 
                     
                   
                   = 
                   
                     { 
                     
                       
                         
                           
                             1 
                             , 
                             
                               
                                 when 
                                  
                                 
                                     
                                 
                                  
                                 
                                   e 
                                    
                                   
                                     ( 
                                     t 
                                     ) 
                                   
                                 
                               
                               ≤ 
                               0 
                             
                           
                         
                       
                       
                         
                           
                             0 
                             , 
                             elsewhere 
                             , 
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   8 
                   ) 
                 
               
             
           
         
       
     
         [0000]    i.e, i(t)=1 for all tε[0,1] when (x 0 ,y 0 ) is inside the corresponding time-dependent edge equation. Note that the inside functions, i k (t), can be computed analytically by solving the second-degree polynomial in Equation 7. 
         [0017]    For a moving triangle, we have three time-dependent edge functions, e k (t), where kε{0,1,2}. The point (x 0 ,y 0 ), will be inside the moving triangle when all inside functions are positive at the same time. This visibility function can be expressed as: 
         [0000]        v ( t )= i   0 ( t ) i   1 ( t ) i   2 ( t ),  (9)
 
         [0000]    i.e., the multiplication of all three inside functions. 
         [0018]    We derive the equation for the depth during the time span where the sample point, (x 0 ,y 0 ), is inside the moving triangle. Perspective-correct interpolation coordinates (u,v), can be used to interpolate any attribute per vertex. This is done as: 
         [0000]        s ( u,v )=(1− u−v ) p   0   +up   1   +vp   2 ,  (10)
 
         [0000]    where p k  are the attribute vectors at the three vertices, and s(u,v) is the interpolated attribute vector. Edge equations, e k , can be used to compute (u,v): 
         [0000]    
       
         
           
             
               
                 
                   
                     ( 
                     
                       u 
                       , 
                       v 
                     
                     ) 
                   
                   = 
                   
                     
                       1 
                       
                         
                           e 
                           0 
                         
                         + 
                         
                           e 
                           1 
                         
                         + 
                         
                           e 
                           2 
                         
                       
                     
                      
                     
                       
                         ( 
                         
                           
                             e 
                             1 
                           
                           , 
                           
                             e 
                             2 
                           
                         
                         ) 
                       
                       . 
                     
                   
                 
               
               
                 
                   ( 
                   11 
                   ) 
                 
               
             
           
         
       
     
         [0000]    Note that u, v, and all e k  are functions of (x 0 ,y 0 ), but this was left out to shorten notation. Equation 11 also holds when time-dependent edge equations are used. 
         [0019]    The depth buffer stores interpolated depth values. Assuming that p k (p x   k , p y   k , p z   k , p w   k ), kε{0,1,2}, are the triangle vertices in clip space (before division by w), one first uses Equation 10, and then computes the depth as d=s z /s w  for a particular fragment with perspective-correct barycentric coordinates, (u,v). 
         [0020]    When we turn from static triangles to moving triangles, p k  are functions of time (Equation 2), and so are the edge equations. Let us first take a look at one of the texture coordinates, u (see Equation 11): 
         [0000]    
       
         
           
               
             
               
                 
                   
                     
                       
                         
                           u 
                           = 
                           
                             
                               e 
                               1 
                             
                             
                               
                                 e 
                                 0 
                               
                               + 
                               
                                 e 
                                 1 
                               
                               + 
                               
                                 e 
                                 2 
                               
                             
                           
                         
                       
                     
                     
                       
                         
                           
                             = 
                             
                               
                                 
                                   
                                     α 
                                     1 
                                   
                                    
                                   
                                     t 
                                     2 
                                   
                                 
                                 + 
                                 
                                   
                                     β 
                                     1 
                                   
                                    
                                   t 
                                 
                                 + 
                                 
                                   γ 
                                   1 
                                 
                               
                               
                                 
                                   
                                     ( 
                                     
                                       
                                         α 
                                         0 
                                       
                                       + 
                                       
                                         α 
                                         1 
                                       
                                       + 
                                       
                                         α 
                                         2 
                                       
                                     
                                     ) 
                                   
                                    
                                   
                                     t 
                                     2 
                                   
                                 
                                 + 
                                 
                                   
                                     ( 
                                     
                                       
                                         β 
                                         0 
                                       
                                       + 
                                       
                                         β 
                                         1 
                                       
                                       + 
                                       
                                         β 
                                         2 
                                       
                                     
                                     ) 
                                   
                                    
                                   t 
                                 
                                 + 
                                 
                                   γ 
                                   0 
                                 
                                 + 
                                 
                                   γ 
                                   1 
                                 
                                 + 
                                 
                                   γ 
                                   2 
                                 
                               
                             
                           
                           , 
                         
                       
                     
                   
                 
                 
                   
                     ( 
                     12 
                     ) 
                   
                 
               
             
           
         
       
     
         [0000]    where the three time-dependent edge equations are: α k t 2 +β k t+γ k  (Equation 7). The texture coordinate, u, becomes a rational polynomial of degree two in t. The major difference, when compared to static triangles, is when the entire depth function is put together, 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       d 
                        
                       
                         ( 
                         t 
                         ) 
                       
                     
                     = 
                     
                       
                         
                           s 
                           z 
                         
                         
                           s 
                           w 
                         
                       
                       = 
                       
                         
                           
                             
                               ( 
                               
                                 1 
                                 - 
                                 u 
                                 - 
                                 v 
                               
                               ) 
                             
                              
                             
                               p 
                               z 
                               0 
                             
                           
                           + 
                           
                             up 
                             z 
                             1 
                           
                           + 
                           
                             vp 
                             z 
                             2 
                           
                         
                         
                           
                             
                               ( 
                               
                                 1 
                                 - 
                                 u 
                                 - 
                                 v 
                               
                               ) 
                             
                              
                             
                               p 
                               w 
                               0 
                             
                           
                           + 
                           
                             up 
                             w 
                             1 
                           
                           + 
                           
                             vp 
                             w 
                             2 
                           
                         
                       
                     
                   
                   , 
                 
               
               
                 
                   ( 
                   13 
                   ) 
                 
               
             
           
         
       
     
         [0000]    where all p z   i  and p w   i  are functions of time according to Equation 2, and u and v are functions of time (Equation 12) as well. When these expressions replacing the corresponding terms in Equation 13, we arrive at a cubic rational polynomial for the depth function for a certain sample point, (x 0 ,y 0 ): 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       d 
                        
                       
                         ( 
                         t 
                         ) 
                       
                     
                     = 
                     
                       
                         
                           
                             m 
                             3 
                           
                            
                           
                             t 
                             3 
                           
                         
                         + 
                         
                           
                             m 
                             2 
                           
                            
                           
                             t 
                             2 
                           
                         
                         + 
                         
                           
                             m 
                             1 
                           
                            
                           t 
                         
                         + 
                         
                           m 
                           0 
                         
                       
                       
                         
                           
                             n 
                             3 
                           
                            
                           
                             t 
                             3 
                           
                         
                         + 
                         
                           
                             n 
                             2 
                           
                            
                           
                             t 
                             2 
                           
                         
                         + 
                         
                           
                             n 
                             1 
                           
                            
                           t 
                         
                         + 
                         
                           n 
                           0 
                         
                       
                     
                   
                   , 
                 
               
               
                 
                   ( 
                   14 
                   ) 
                 
               
             
           
         
       
     
         [0021]    Two of the advantages of using d=s z /s w  include the fact that the depth is in the range [0,1] due to the way the projection matrix is set up and that depth buffer compression can therefore be implemented efficiently since the depth will be linear over a triangle. Also, d=s z  can be used, which will generate the same images, but the depth will now range between the near and the far plane: [Z near , Z far ]. This simplifies the depth function for moving triangles. It will still be a rational function in t with degree three in the numerator, but the degree in the denominator will be reduced to two, that is: 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       d 
                        
                       
                         ( 
                         t 
                         ) 
                       
                     
                     = 
                     
                       
                         
                           
                             m 
                             3 
                           
                            
                           
                             t 
                             3 
                           
                         
                         + 
                         
                           
                             m 
                             2 
                           
                            
                           
                             t 
                             2 
                           
                         
                         + 
                         
                           
                             m 
                             1 
                           
                            
                           t 
                         
                         + 
                         
                           m 
                           0 
                         
                       
                       
                         
                           
                             n 
                             2 
                           
                            
                           
                             t 
                             2 
                           
                         
                         + 
                         
                           
                             n 
                             1 
                           
                            
                           t 
                         
                         + 
                         
                           n 
                           0 
                         
                       
                     
                   
                   , 
                 
               
               
                 
                   ( 
                   15 
                   ) 
                 
               
             
           
         
       
     
         [0022]    In theory, the intersection of three inside functions of the visibility function can result in at most four disjoint time spans where the resulting function, v(t), is positive. This is because each inside function can consist of two disjoint positive parts. In practice, we have only encountered three intervals when you consider front-facing triangles for any value of t. Most commonly, only a single interval is generated for most triangles and samples, however. 
         [0023]    The term “interval” denotes a range in the time dimension, together with the color and depth for that time range. An interval is denoted by Δ. In practice, the third-degree rational depth function (Equation 15), is approximated by a linear function. The motivation for this is that the depth function rarely varies much beyond such an approximation within a pixel, and it makes computations much faster. In addition, we have good experiences with this approximation. 
         [0024]    Given the depth function approximation, each interval stores the following parameters: 
         [0000]        t   i   s : time at the beginning of the interval 
         [0000]        t   i   e : time at the end of the interval 
         [0000]        z   i : depth at the beginning of the interval 
         [0000]        k   i : slope of the depth function 
         [0000]        c   i : color of the interval  (16)
 
         [0025]    Our interval is analogous to a fragment in rendering without motion blur, and an example of an interval is shown in  FIGS. 1 and 2 . In  FIG. 1 , the sample point  22  is inside the moving triangle in two disjoint time intervals, as shown by the depth function below. In  FIG. 2 , the sample point  24  is inside in three disjoint time intervals. In general, all intervals belonging to a pixel are simply stored in an interval list in that pixel, similar to how order-independent transparency is done with DX11 using graphics processing units. A couple of optimizations that can be used for opaque rendering will be described below. As a triangle that covers a pixel is rendered, one or more intervals are added to that pixel&#39;s interval list. When rendering starts, each pixel is initialized with an interval with background color and depth equal to the far plane. 
         [0026]    Interval insertion is illustrated in  FIG. 3 . New intervals  26  are inserted into the existing interval list  28 . At  30 , clipping the interval  26  would result in the existing interval  28  and two intervals  26 , one on each side of interval  28 . At  32 , for intersections, the new interval is also added to the pixel&#39;s interval list. At  34  and  36 , optimizations valid only for opaque rendering with a LESS_EQUAL depth test are shown. 
         [0027]    Our approach is based on trying to keep the number of intervals stored per pixel small, and to facilitate compression when possible. When two intervals intersect, one can use clipping to create non-overlapping (in time) intervals. However, that can generate up to four intervals, which is undesirable. An intersection can also generate only two intervals, but in such cases, we also refrain from clipping since our compression mechanism works better with unclipped intervals. Note that using non-clipped intervals requires a slightly more complex resolve procedure. For opaque rendering, simple depth test optimizations can be included in this process as well, and this is shown in the bottom two illustrations  34  and  36  of  FIG. 3 , where we have assumed that a LESS_EQUAL depth test is used. It is, however, straightforward to adapt to any depth function. In the second illustration from the bottom, the interval  26  is clipped in time since it is occluded and because the clipping only generate one interval, i.e., it does not require more storage than simply storing the unclipped interval. 
         [0028]    Note that to facilitate depth testing, we keep the intervals sorted on t s   i  per pixel. This can be done during interval insertion using insertion sort, for example. 
         [0029]    A rasterization with compression sequence  40 , shown in  FIG. 5 , begins by rasterizing a triangle (block  42 ) and then the intervals are computed per sample or pixel (block  43 ). Then, using an oracle function and interval merging, temporal pixel compression may be done in some embodiments (block  44 ). If the image is done, the flow moves to the resolve pass. Otherwise, it iterates back to rasterizing another triangle in block  42 . 
         [0030]    After rendering all moving and non-moving triangles, as indicated in  FIG. 5  at block  42 , we have a list of possibly overlapping (in time) intervals, Δ i , per pixel. Recall that we keep the intervals sorted, i.e., t i   s ≦t s   i+1 , ∀i, since this is part of the interval insertion step described above. 
         [0031]    The resolve pass (blocks  46 ,  47  and  48 ) processes a pixel independently of other pixels, and sweeps the sorted intervals in a pixel from time t=0 to t=1. During the sweep, we maintain a list, called Active List, per pixel of all intervals overlapping the current time of the sweep, as indicated in block  46  of  FIG. 5 . For example, when the sweep starts, at t=0, the Active List is initialized to hold all intervals that overlap t=0. Note that the Active List is also kept sorted on depth. As an interval start-point, t i   s , or end-point, t i   e , or an intersection point between two intervals is encountered, the following action is taken:
   Interval-Start: insertion and sort (on depth) new interval into Active List.   Interval-End: remove interval from Active List.   Interval-Intersection: swap places of the intersecting intervals in the Active List to maintain depth order.   
 
         [0035]    Between each pair of encounters (the three cases above), the final color for that particular subspan in time is computed ( FIG. 5 , block  47 ). Each such color and subspan in time is temporarily put into a resolved interval, Δ k . Since intersection points are handled as part of the sweep, there will not be any intervals overlapping in depth in the Active List. As a consequence of that, the color of Δ k  for opaque rendering is simply the color of the nearest (in depth) interval in the Active List, again assuming that a LESS_EQUAL depth test is used. Each resolved interval&#39;s color, c k , is then integrated against the shutter response function, w(t), and added to the final color of the pixel. This can be expressed as: 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       c 
                       final 
                     
                     = 
                     
                       
                         ∑ 
                         
                           k 
                           = 
                           0 
                         
                         
                           n 
                           - 
                           1 
                         
                       
                        
                       
                         ( 
                         
                           
                             ∫ 
                             
                               t 
                               k 
                               t 
                             
                             
                               t 
                               k 
                               e 
                             
                           
                            
                           
                             
                               w 
                                
                               
                                 ( 
                                 t 
                                 ) 
                               
                             
                              
                             
                               c 
                               k 
                             
                              
                             
                                
                               t 
                             
                           
                         
                         ) 
                       
                     
                   
                   , 
                 
               
               
                 
                   ( 
                   17 
                   ) 
                 
               
             
           
         
       
     
         [0000]    for n disjoint intervals. If a box filter is used, the colors of all intervals are simply combined into one final color weighted by their duration in time. 
         [0036]    For the transparent resolve procedure, the only difference is that the color, c k , of the resolved interval, Δ k , is computed by blending the intervals in the Active List in back-to-front order based on the alpha component of each color. 
         [0037]    When there are many small triangles with a relatively high degree of motion blur, each pixel may need to store a large number of intervals, Δ i , in order to exactly represent the color of the pixel. We have observed up to a few hundred intervals per pixel in extreme cases. This is clearly not desirable for a rasterization-based algorithm due to the extra pressure on the memory subsystem, that is, increased memory bandwidth usage. The problem can be alleviated by using a tiling architecture, where the triangles are sorted into tiles (rectangular regions of pixels) by front-end pass, and per-pixel rendering done in a back-end pass. Tiles can be back-end processed in parallel by separate cores, since the rasterization and per-pixel work is independent at this point. However, a tiling architecture cannot solve the problem. Instead, we use lossy compression of intervals. 
         [0038]    Merging intervals are illustrated in the top part of  FIG. 4 . Since the intervals  38  have similar depth functions, they are merge candidates. Assume that a pixel can only “afford” to store four intervals, and that after rendering another motion blurred triangle, the pixel actually holds five intervals (top left in  FIG. 4 ). To be able to fit this into our frame buffer, we will need to compress this information into four intervals again. This is shown in the top right part of the figure, where the two intervals  38  with similar depth functions have been merged to a single interval. A similar type of compression has been used for deep shadow maps, but in their context, compression was only needed to be done once after the entire visibility function was known. Our goal is different since we may need to compress each pixel several times as more and more triangles are rendered to a pixel and, in addition, we compress not only depth, but may also take into account the colors, the actual depth functions, the extent of the intervals, etc. The bottom left graph illustrates pixel content after rendering many small moving triangles. The bottom right graph is a possible result using our compression algorithm. Finally, all sub-spans are blended together into a final per-sample color ( FIG. 5 , block  48 ). 
         [0039]    We use an oracle-based approach to attack this problem. Our oracle function is denoted: 
         [0000]        o   i,j   =O (Δ i ,Δ j ),  (18)
 
         [0000]    where the oracle function, O( ), operates on two intervals, Δ i  and Δ j , where i&lt;j. The task of the oracle is basically to compute an estimation on how appropriate it is to merge the two input intervals. Given an oracle function, O, we compute oracle function values, o i,j , for all i, and jε{i+1, i+2, i+3}. For transparent scenes with a high level of depth overlap, we have increased the search range up to +10, instead of +3. In the next step, the interval pair with the lowest o i,j  is merged. Depending on the implementation, this process may continue until the number of intervals per pixel falls in a desired range, or until there are no more appropriate merges possible. Next, we describe an oracle, for two intervals, that generates a lower value the more appropriate they are to merge. 
         [0040]    Our oracle function, O, may be described, for example, by the following formula, where i&lt;j: 
         [0000]      0(Δ i ,Δ j )= h   1 max( t   j   s   −t   i   e ,0)+ h   2   |  z     i   −z   j   |+h   3   |k   i   −k   j   |+h   4 ( t   i   e   −t   i   s   +t   j   e   −t   j   s )+ h   5 (| c   i,r   −c   j,r   |+|c   i,g   −c   j,g   |+|c   i,b   −c   j,b |).  (19)
 
         [0000]    The first term favors merging of intervals that are located close in time (even overlapping). The second term  z   i  is the depth at the end of Δ i , i.e.,  z   i =z i +k i k i (t i   e −t i   s ), and z j  is the depth at the beginning of the other interval, Δ j . See Equation 16 for definitions of the interval&#39;s parameters. The third term penalizes merging of intervals with different slopes. Hence, both the second and third terms attempt to detect if the depth functions are similar, and therefore, whether they are amenable for merging. The fourth term favors merging of short (in time) intervals, while the fifth favors merging of interval with similar colors. All h i  are used-specified constants. 
         [0041]    We will describe the merging of two intervals, Δ i  and Δ j , into a new interval, Δ′ i . The merge is described as: Δ′ i =merge(Δ i , Δ j ), i&lt;j, where the new parameters are: 
         [0000]    
       
      
       t′ 
       i 
       s 
       =t 
       i 
       s  
      
     
         [0000]        t′   i   e =max( t   i   e   ,t   j   e ) 
         [0000]        z′   i =(1−α) z   i +α( z   j   −k   j ( t   j   s   −t   i   s ))
 
         [0000]        k′   i =(1−α) k   i   +αk   j  
 
         [0000]        c′   i =(1−α) c   i   +αc   j ,  (20)
 
         [0000]    where α=(t j   e −t j   s )/(t i   e −t i   s +t j   e −t j   s ) is used to linearly blend parameters depending on the lengths (in time) of the intervals that are merged. As can be seen, the slope, k′ i  of the depth function, and the color, c′ i , are simply linear interpolations of the input intervals&#39; parameters. The depth, z′ i , is slightly more complex because we need to blend the depth at the same instant in time. Since we want the new depth at time t i   s , we compute the depth of Δ j &#39;s depth function at t i   s  and use that for blending. For future work, it would be interesting to investigate other approaches to depth merging, e.g., where the area under the depth function is kept constant after compression. An example of merging two intervals is shown in  FIG. 4 . 
         [0042]    The computer system  130 , shown in  FIG. 6 , may include a hard drive  134  and a removable media  136 , coupled by a bus  104  to a chipset core logic  110 . A keyboard and mouse  120 , or other conventional components, may be coupled to the chipset core logic via bus  108 . The core logic may couple to the graphics processor  112 , via a bus  105 , and the main or host processor  100  in one embodiment. The graphics processor  112  may also be coupled by a bus  106  to a frame buffer  114 . The frame buffer  114  may be coupled by a bus  107  to a display screen  118 . In one embodiment, a graphics processor  112  may be a multi-threaded, multi-core parallel processor using single instruction multiple data (SIMD) architecture. 
         [0043]    In the case of a software implementation, the pertinent code  139  may be stored in any suitable semiconductor, magnetic, or optical memory, including the main memory  132  (as indicated at  139 ) or any available memory within the graphics processor. Thus, in one embodiment, the code to perform the sequences of  FIG. 5  may be stored in a machine or computer readable medium, such as the memory  132  or the graphics processor  112 , and may be executed by the processor  100  or the graphics processor  112  in one embodiment. 
         [0044]      FIG. 5  is a flow chart. In some embodiments, the sequences depicted in this flow chart may be implemented in hardware, software, or firmware. In a software embodiment, a non-transitory computer readable medium, such as a semiconductor memory, a magnetic memory, or an optical memory may be used to store instructions and may be executed by a processor to implement the sequences shown in  FIG. 5 . 
         [0045]    The graphics processing techniques described herein may be implemented in various hardware architectures. For example, graphics functionality may be integrated within a chipset. Alternatively, a discrete graphics processor may be used. As still another embodiment, the graphics functions may be implemented by a general purpose processor, including a multicore processor. 
         [0046]    References throughout this specification to “one embodiment” or “an embodiment” mean that a particular feature, structure, or characteristic described in connection with the embodiment is included in at least one implementation encompassed within the present invention. Thus, appearances of the phrase “one embodiment” or “in an embodiment” are not necessarily referring to the same embodiment. Furthermore, the particular features, structures, or characteristics may be instituted in other suitable forms other than the particular embodiment illustrated and all such forms may be encompassed within the claims of the present application. 
         [0047]    While the present invention has been described with respect to a limited number of embodiments, those skilled in the art will appreciate numerous modifications and variations therefrom. It is intended that the appended claims cover all such modifications and variations as fall within the true spirit and scope of this present invention.