Abstract:
Method and apparatus for rendering texture to an object to be displayed on a pixel screen display. This technique makes use of linear interpolation between perspectively correct texture address to calculate rates of change of individual texture addresses components to determine a selection of the correct LOD map to use and intermediate texture addresses for pixels of the object between the perspectively correct addresses. The method first determines perspectively correct texture address values associated with four corners of a predefined span or grid of pixels. Then, a linear interpolation technique is implemented to calculate a rate of change of texture address components in the screen x and y directions for pixels between the perspectively bound span corners. This linear interpolation technique is performed in both screen directions to thereby create a potentially unique level of detail value for each pixel, which is then used as an index to select the correct pre-filtered LOD texture map. When mapping an individually determined LOD value per pixel, the effect of producing undesirable artifacts that may appear if a single LOD for an entire span or polygon is used, is obviated.

Description:
FIELD OF THE INVENTION  
         [0001]    This invention relates to real-time computer image generation systems and, more particularly, to means and method for selecting effectively an appropriate level of detail (LOD) of stored information for representing an object to be displayed.  
         BACKGROUND OF THE INVENTION  
         [0002]    In certain real-time computer image generation systems, objects to be displayed are represented by convex polygons which may include texture information for rendering a more realistic image. The texture information is typically stored in a plurality of two-dimensional texture maps, with each texture map containing texture information at a predetermined level of detail (“LOD”) with each coarser LOD derived from a finer one by filtering as is known in the art. Further details regarding computer image generation and texturing, can be found in U.S. Pat. No. 4,727,365, U.S. Pat. No. 4,811,245 and U.S. Pat. No. 4,692,880 which are incorporated herein in their entirety by reference thereto.  
           [0003]    Selection of the most appropriate LOD for obtaining texture for polygons representing an object requires consideration of the apparent distance of the object from a viewpoint and the angle between a vector from the viewpoint to a pixel on the polygon and the normal vector of the polygon. These two factors determine the size of the projected pixel footprint in the texture space. As the polygon moves further away from the viewpoint the footprint will decrease in size, or as it moves closer it will increase in size on the polygon. Also the angle between the view ray and the polygon normal will give a measure of how “edge on” the polygon is. As the polygon becomes more edge on in a direction the footprint will grow in size along that dimension. When moving from screen pixel to screen pixel the texture coordinate rate of change will continue to change. This non-linear relationship is why perspective mapping in necessary. The u and v texture coordinates are not linear in screen space as soon as the polygon is not perpendicular to the viewer.  
           [0004]    Some prior art techniques had resolved to calculate an LOD value per polygon which only allowed one LOD of a map per polygon. Sometimes polygons are sub-divided (tesselated) to obtain more than one LOD per polygon. While this works well for pixels that project into polygons that are perpendicular to the viewer, texture mapping for perspective projections requires further incremental calculation techniques to generate accurate texture addresses on a per pixel basis. Such texture mapping techniques in perspective requires the calculation of texture address partial derivatives or delta values which are used to determine the appropriate LOD for texture mapping and described mathematically as:  
           ∂   u       ∂   x       ,       ∂   u       ∂   y       ,       ∂   v       ∂   x       ,       ∂   v       ∂   y                             
 
           [0005]    These values represent the rate of change of the U and V texture addresses with respect to one pixel change in the X or Y pixel directions on a computer display screen. Intuitively, the magnitude of each term describes the distance covered in the finest LOD level of the texture map by the projection of a pixel onto the surface of a textured polygon in the specified direction. In other words, when progressing from one pixel to the next neighboring pixel in screen X space, dU/dX is measure of how much U changes in the texture map. Another way to think of these terms is that the larger the magnitude of the term the more compressed the texture is in the specified direction. If a high frequency signal, such as a compressed texture address, is point sampled at a lower frequency, such as the pixel centers on the screen, aliasing can result. This aliasing produces undesirable visual anomalies such as scintillation or “texture swimming”, where the texture pattern appears to float around on the top of a polygon when in motion. By pre-filtering the texture images into multiple LODs the unwanted visual artifacts can be avoided. The above terms are used to select the texture image which has the appropriate amount of filtering applied on a pixel-by-pixel basis. The term with the largest rate of change should dominate the LOD selection criteria, otherwise the sampled texture in that direction may scintillate. This approach generally minimizes visual artifacts at the expense of blurring the resulting image in other directions. A simple maximum of all four gradient terms however, is not sufficient because the magnitude of the terms can change as the polygon rotates and effectively select a different LOD for the same pixel, depending on the orientation of the polygon. One approach for reducing this problem has been proposed as set forth by Paul Heckbert&#39;s Master&#39;s Thesis, University of California, Berkeley, June 1989 which sets forth an LOD calculation in accordance with equation (1) as follows:  
               LOD   Heckbert     =       log   2          [     max              [             (       ∂   u       ∂   x       )     2     +       (       ∂   v       ∂   x       )     2         ,           (       ∂   u       ∂   y       )     2     +       (       ∂   v       ∂   y       )     2           ]     ]               (   1   )                               
 
           [0006]    Techniques have been implemented to approximate such texture address partial derivatives, however, they have proven to be very computer resource intensive, requiring many floating point operations which are often difficult and impractical to implement in real-time, 3-D computer graphics applications.  
           [0007]    Thus, it would be highly desirable to provide a method for generating instantaneous texture address values used to calculate an LOD on a per pixel basis, in real-time, that requires minimum operations and results in a visually effective texture mapped perspective object.  
         SUMMARY OF THE INVENTION  
         [0008]    In accordance with the present invention, the rate of change of texture addresses when mapped to individual pixels of a polygon is used to obtain the correct level of detail (LOD) map from a set of pre-filtered maps. The method comprises a first determination of perspectively correct texture address values found at four corners of a predefined span or grid of pixels. Then, a linear interpolation technique is implemented to calculate a rate of change of texture addresses for pixels between the perspectively bound span corners. This linear interpolation technique is performed in both screen directions to thereby create a potentially unique level of detail value for each pixel. When mapping an individually determined LOD value per pixel, the effect of producing undesirable artifacts, such as “Shark teeth”, that may appear if a single LOD for an entire span is used, is virtually obviated.  
           [0009]    Each pixel of a span is assigned an independently interpolated value from the horizontal and vertical direction of the screen. Since the u and v gradients are monotonic, linear interpolation of the rate of change of each gradient will allow a LOD change in the u or v gradient direction at any pixel, and once the gradient has moved on to a new LOD, it will continue on in that LOD until it gets to the next LOD. Although the LOD assignments to pixels other than those at the corners of the span may represent a non-perspective correct interpolation within a span due to linear interpolation of a non-linear function, the resulting image to be displayed is acceptable generally to the human eye for most practical applications.  
           [0010]    The rate of change of a coordinate from a two dimensional texture map when applied to a rendered polygon (i.e. a polygon to be displayed) is approximated between regularly spaced perspectively correct address values (i.e. those obtained from pixels situated at the corners of a span) in order to determine the appropriate Level of Detail (LOD) for proper texture mapping. This allows a form of linear interpolation between small areas in screen space to be used without obtaining artifacts from linear interpolation and prevents the need of subdividing polygons to very small polygons, as an alternative, to avoid distortions to non-perspective correct mapping of textures and corresponding increased demand for computing resources. This method of the present invention reduces the hardware necessary to obtain an image that appears perspectively correct to the human eye.  
           [0011]    The various features of novelty which characterize the invention are pointed out with particularity in the claims annexed to and forming a part of the disclosure. For a better understanding of the invention, its operating advantages, and specific objects attained by its use, reference should be made to the drawings and descriptive matter in which there are illustrated and described preferred embodiments of the invention. 
       
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0012]    [0012]FIG. 1( a ) illustrates a pixel space defining screen coordinates (x,y) on a computer screen display.  
         [0013]    [0013]FIG. 1( b ) illustrates a texture space defining texture address coordinates (u,v) located on one or more pre-filtered texture maps indexed by a level of detail value.  
         [0014]    [0014]FIG. 2 illustrates a polygonal object located in pixel space to be rendered with texture.  
         [0015]    FIGS.  3 ( a ) and  3 ( b ) are flow charts illustrating the methodology for calculating LOD per pixel in the texture mapping method of the invention.  
         [0016]    [0016]FIG. 4 illustrates a scan of pixels bounded by associated perspective correct texture addresses.  
         [0017]    [0017]FIG. 5 illustrates a subsequent scan of pixels bounded by new associated perspective correct texture addresses.  
         [0018]    [0018]FIG. 6 illustrates conceptually a hardware architecture for implementing the algorithm of the invention texture mapping algorithm of the invention.  
         [0019]    [0019]FIG. 7 is a schematic diagram of a linear interpolator used for performing the interpolations required in the invention.  
     
    
     DETAILED DESCRIPTION OF THE INVENTION  
       [0020]    The present invention is directed to a method for discretely generating texture address partial derivatives or delta values which are used to determine the appropriate LOD for texture mapping on a per-pixel basis. The generated texture address partial derivatives can then substituted in the Heckbert equation (1) for determining the LOD for each pixel to be mapped.  
         [0021]    Particularly, in the method of the invention, a span of a predetermined number of pixels is defined in pixel (screen space). As described, the designators x and y represent the row (x) and column (y) designation of a pixel (picture element) from a plurality or matrix of pixels of a screen or display device. The pixels of the display device are typically rectangular or square and arranged in horizontal rows and vertical columns for convenience. In the preferred embodiment, the predefined span includes a grid of 4×4 pixels. Then, a perspectively correct determination of the texture value (u,v) is made at each of four corners of the span, three of the corners being immediately outside the span. As used herein, the designators u and v represent the row (u) and column (v) designation of a texel (texture element or cell) from a plurality of texels of a texture map at a particular LOD. Texels may also be square or rectangular and envisioned to be located in horizontal rows and vertical columns. Then, a linear interpolation technique is performed to approximate the texture values and partial derivatives of texture addresses of each pixel within the span that map to the polygon to be rendered.  
         [0022]    The invention will now be described in greater detail. FIG. 1( a ) represents a portion of a display device or screen  10 , having a plurality of square or rectangular pixels, several representative ones of which are designated by reference numeral  12  arranged in a matrix having rows and columns is shown. A pixel may be identified to be located in a row I and column J by specifying an X, Y coordinate pair corresponding to a predetermined reference designator, such as its center. For example, pixel  14  is found by designating location ( 3 ,  5 ) while pixel  16  is at ( 5 ,  3 ). Other convenient reference points, such as the corners of the pixel, may be used if desired for addressing purposes. Further, if a corner is selected as a reference designator for a pixel, then appropriate one-half pixel values may have to be considered to accommodate offset from the center of the pixel as is known in the art.  
         [0023]    Referring to FIG. 1( b ), a portion of a texture map  20  at a predetermined level of detail (LOD) having a plurality of square or rectangular texels or cells, several representative ones of which are designated by reference numeral  22  arranged in a matrix having rows and columns is shown. A texel may be identified to be located in a row U and column V by specifying a U, V coordinate pair corresponding to its upper left hand corner. For example, texel  24  is found by designating location ( 52 ,  41 ) while texel  26  is found by designating location ( 54 ,  42 ). Other convenient reference points, such as different corners or the center of the texel, may be used if desired for addressing purposes.  
         [0024]    [0024]FIG. 2 illustrates a screen display  25  providing a polygonal object  29  to be texture mapped with the object having vertices  28 . As is known, when mapping texture space to screen space, the texture address cannot be linearly interpolated, but, as shown in FIG. 2, if the U and V addresses and the range W at the vertices of the polygon are known along with the screen X,Y location of the vertices as is the case with a three dimension rendering system, then the U and V coordinates when divided by W become linear with respect to screen space. Thus, at a vertex, (S,T) can be found with equations 2(a) and 2(b) and linearly interpolated to any pixel in the screen. Likewise, 1/W can also be linearly interpolated to any pixel in the screen.  
           S=U/W   (2(a))  
           T=V/W   (2(b))  
         [0025]    where 1/W is the inverse range distance from an observer location to the object in pixel space. Now, as know in the art, with three vertices that are known to be in a plane and attribute data S,T, 1/W (W 1 ), a set of plane equations can be determined that specify S, T, W −1  as a function of screen X and Y as set forth in equations 3(a)-3(c) as follows:  
           S=Cos+X*Cxs+Y*Cys   3(a))  
           T=Cot+X*Cxt+Y*Cyt   3(b))  
           W   −1   =CoW   −1   +X*CxW   −1   +Y*CyW   −1   3(c))  
         [0026]    These plane equation coefficients (Co, Cx, Cy) for each of the polygon&#39;s values S, T, and 1/W can be determined because the X,Y position and attribute data (S, T, 1/W) is given at three points and can be used to form a plane in a three dimensional space. An equation of a plane can be written as Attribute(x,y)=Co+Cx*x+Cy*y, where the Co term defines the value at some origin, in this case it will be relative to the value at the upper left corner of the span containing the top-most vertex, and Cx, Cy define the change in the attribute for a step change in the x and y directions, respectively. When this function is evaluated at some x, y, it yields the magnitude of the attribute at that x, y location.  
         [0027]    When Δx 0 , Δx 1 , and Δx 2  are defined as the horizontal distances from the three vertices to a reference point (xref, yref) defined as the center of pixel in upper left corner of a span of pixels containing the top-most vertex, e.g., Δx 0 =(x 0 −x ref ) etc., and Δy 0 , Δy 1  and Δy 2  are defined as the vertical distances from the three vertices to the reference point (xref, yref), e.g., Δy 0 =(y 0 −y ref ) etc., then three equations with three unknowns are obtained. The following example shows the texture 1/W address components (represented as 1/W 0 , 1/W 1 , and 1/W 2 , at the three vertices). Using the supplied 1/W attribute data from the three vertices and the (x, y) locations of the vertices, the following three equations with three unknowns can be determined for 1/W.  
           C 0 1   /W+Cx   1   /W*Δx   0   +Cy   1   /W*Δy   0 =1 /W   0    
           C 0 1   /W+Cx   1   /W*Δx   1   +Cy   1   /W*Δy   1 =1 /W   1    
           C 0 1   /W+Cx   1   /W*Δx   2   +Cy   1   /W*Δy   2 =1 /W   2    
         [0028]    And by methods known in the art, the three equations with three unknowns can be solved and yield the following equations to represent the three unknowns in terms of given values.  
           Cx   1   /W =[( y 1 −-y 2)*1 /W   0 +( y 2 −y 0)*1 /W   1 +( y 0 −y 1)*1 /W   2   ]/[x   2 *( y 0 −y 1)+ x   1 *( y 2 −y 0)+ x   2 *( y 1 −y 2)] 
           Cy   1   /W =[( x 1 −x 2)*1/ W   0 +( x 2 −x 0)*1 /W   1 +( x 1 −x 0)*1 /W   2   ]/[x   2 *( y 0 −y 1)+ x   1 *( y 2 −y 0)+ x   2 *( y 1 −y 2)] 
           C 0 1   /W= 1 /W   0   −Cx   1   /W*x   0   −Cy   1   /W*y   0    
         [0029]    The coefficients for S and T are determined in the same manner with the attribute values per vertex are S and T respectively. Once the coefficients have been determined, S, T and W −1  can be interpolated to any (X,Y) pixel in the object. Then, substituting equations 3(a)-3(c) into equations 2(a) and 2(b), the U and V texture addresses can be perspective correctly determined from the following equations 3(d) and 3(e):  
             U   =       S   /     W     -   1         =       (     Cos   +     X   *   Cxs     +     Y   *   Cys       )       (       Cow     -   1       +     X   *     Cxw     -   1         +     Y   *     Cyw   1         )                 3(d)                               
 
             V   =       T   /     W     -   1         =       (     Cot   +     X   *   Cxt     +     Y   *   Cyt       )       (       Cow     -   1       +     X   *     Cxw     -   1         +     Y   *     Cyw   1         )                 3 (e)                               
 
         [0030]    The values of S, T, and W −1  can be determined using 3(a), 3(b), and 3(c), respectively. Then by performing a perspective divide per pixel as described in 3(d) and 3(e), any non-linear distortion artifacts can be eliminated while calculating texture addresses U and V.  
         [0031]    This address calculation uses large floating point resources and needs to be done for U and V on each clock that an address pair needs to be calculated.  
         [0032]    As will be described, the method of the invention calculates perspective correct values at predefined corners of a span to effectively tessellate the object polygons without any polygon overhead, and then linear interpolate the address within the span. This minimizes the hardware necessary to calculate the perspective correct values, and allows real-time interpolation of values within the span with fixed point math without any visual artifacts. To complete the texture map address calculation, a method of determining an LOD map to select was necessary.  
         [0033]    The method of the invention is now described with respect to the flow charts of FIGS.  3 ( a ) and  3 ( b ). In the method of the invention, the first step  100  is to pre-calculate the coefficients for S,T and W −1  for the particular polygon to be mapped as described above with respect to equations 3(a)-3(c). These values will be used to calculate perspectively correct texture map addresses (u,v) for each corner of a given span as described according to equations 3(d) and 3(e). Next, at step  150 , a span processor selects an n×n grid or span of pixels that includes one or more “lit” pixels of the object (polygon) to be textured. In the preferred embodiment, a 4×4 span of pixels  30  is chosen such as depicted in FIG. 4 which illustrates, e.g., lit pixels  38 ,  39  and  40 , corresponding to a portion of object  29  (FIG. 2) to be texture rendered.  
         [0034]    Each object pixel (x,y) in the pixel span will be mapped with texture information from a texture map having “u,v” orthogonal dimensions. For purposes of calculating the texture information for each pixel at the correct level of detail, texture address partials ∂u/∂x and ∂u/∂y (and ∂v/∂x and ∂v/∂y) are determined for each lit(x,y) pixel in the span.  
         [0035]    Referring back to FIG. 3( a ), at step  200 , the interpolation algorithm is invoked to individually determine the texture address partials  
           ∂   u       ∂   x       ,       ∂   u       ∂   y       ,       ∂   v       ∂   x       ,       ∂   v       ∂   y                             
 
         [0036]    and texture addresses u,v, for each lit pixel in the span whose LOD is to be determined in accordance with equation (1).  
         [0037]    [0037]FIG. 3( b ) illustrates the preferred algorithm for calculating the LOD value per pixel. As shown at step  205 , FIG. 3( b ), the precalculated coefficients S, T, and W for the given polygon object are first input to a span corner processor which invokes equations 3(a) through 3(e) to determine perspectively correct texture address values (u,v) at associated corners of the span, i.e., address values are calculated for pixels  31 - 34  shown in FIG. 4 associated with each corner of the span. For illustrative purposes, as shown in FIG. 4, each pixel x,y of the span is designated as having an address U r,q , with “q” indicating the pixel x-coordinate (column) of the span (e.g., q=0, 1, . . . , 4) and “r” indicating the pixel y coordinate (row) of the span (e.g., r=0, 1, . . . , 4). Although not shown, an identical map is generated for the corresponding v dimension of the texture address, depicted as addresses V r,q  with “q” indicating the pixel x-coordinate of the span (e.g., q=0, 1, . . . , 4) and “r” indicating the pixel y coordinate (e.g., r=0, 1, . . . , 4). Thus, span corner pixel  31  corresponds to texture address having u coordinate value U 0,0  (corresponding to pixel location ( 0 , 0 )). Pixel  33  is shown located outside the span and having texture address value U 40 . Likewise, pixel  32  is shown located outside the span and having texture address value U 01 , and pixel  34  is shown outside of the span having texture address value U 44 . Although not specifically shown, the description that follows for the case of calculating the ∂u/∂x and ∂u/∂y partial for each object pixel in the span readily applies to the ∂v/∂x and ∂v/∂y for each object pixel in the span. For the first span, four such texture address computations are performed, however, as will be described, as a pixel span slides across pixel space to render the object, each successive span will require the calculation of only two new perspective correct texture addresses corresponding to two new corner pixels.  
         [0038]    Referring back to FIG. 3( b ), at step  210 , the perspective correct addresses at the two pixel centers  31  and  33  (FIG. 4) are input to a left vertical address interpolator to determine a vertical change, DL, (in u and v dimensions) with respect to screen direction y for pixels located along the left column (column  0 ) of the span  30 . Similarly, the perspective correct addresses at the two pixel centers  32  and  34  are input to a right vertical address interpolator to determine a vertical change, DR, (in u and v dimensions) with respect to screen direction y for pixels along the right side of the span. From these DR and DL values, a texture address can be computed for each lit pixel in the span.  
         [0039]    From a pixel mask (not shown), information as to the object pixels to be lit for each span are input to a series of interpolators, for example, cyclical and in a pipelined fashion. Such information is made available by a state machine controller, such as one described in co-pending U.S. patent application No. ______ (Attorney Docket #11114), the contents and disclosure of which are incorporated by reference as if fully set forth herein. Thus, as indicated at step  212 , FIG. 3( b ), a decision is made as to whether a lit pixel resides in the first row of the span. If a lit pixel does exist in the first row of the span, then at step  214 , a computation is made to determine the right and left addresses, R0 and L0. As shown in FIG. 4, L0 is equal to the given perspective correct texture address value U00, and R0 is equal to the given perspective correct texture address value U04. Next, at step  216 , a determination is made as to whether the first pixel of the row is lit. If the first pixel of the row is lit, then a computation is made at step  218  to determine the horizontal texture address partial (U) calculated with respect to the x dimension (∂u/∂x) as shown in FIG. 4 as partial DR0, and, the horizontal texture address partial calculated with respect to the y dimension (∂u/∂y) as shown in FIG. 4 as partials DC0. Although not shown, vertical (V) texture address partials are calculated with respect to the x dimension to approximate the ∂v/∂x values for the subsequent pixel LOD calculation and with respect to the y dimension to approximate the ∂v/∂y values.  
         [0040]    To calculate the texture address partial with respect to the y dimension, i.e., DC0, for the first pixel of the first row of the span, an interpolation is performed such that DC0=DL/4. All texture address partials calculated with respect to the x dimension, DR0, (e.g., ∂u/∂x, ∂v/∂x) for a given row of a span are identical, and thus, for the first row, an interpolation is performed such that DR0=((R0−L0)/4), with DL, DR, R0 and L0 already computed. After calculating DC0 and DR0 for the first pixel of the first row, the algorithm proceeds to step  220 , FIG. 3( b ).  
         [0041]    If, at step  216 , it is determined that the first pixel of the first row is not to be texture mapped, then the process continues at step  220  where a determination is made as to whether the second pixel of the first row is lit. If the second pixel of the row is lit, then an interpolation is made at step  222  to determine the texture address partial with respect to the y dimension, i.e., DC1, for the second pixel of the first row of the span, calculated as DC1=DC0+((DR−DL)/4). If DR0 was not calculated in a previous step, then the DR0 calculation DR0=((R0−L0)/4) is performed, with DR, DL, R0 and L0 already computed. Additionally, at step  222 , the (u,v) texture address value is calculated, which for exemplary purposes, for the texture coordinate U 0,1  is calculated as U01=L0+((R0−L0)/4). After calculating DC1, DR0, and U01 (V01) for the second pixel of the first row, the algorithm proceeds to step  225 , FIG. 3( b ).  
         [0042]    If, at step  220 , it is determined that the second pixel of the first row is not to be texture mapped, then the process continues at step  225  where a determination is made as to whether the third pixel of the first row is lit. If the third pixel of the row is lit, then an interpolation is made at step  227  to determine the texture address partial with respect to the y dimension, i.e., DC2, for the third pixel of the first row of the span, calculated as DC2=DC0+((DR−DL)/2). If DR0 was not calculated in a previous step, then the DR0 calculation DR0=((R0−L0)/4) is performed, as above, with DR, DL, R0 and L0 already computed. Additionally, at step  227 , the (u,v) texture address value is calculated, which for exemplary purposes, for the texture coordinate U 0,2  is calculated as U02=L0+((R0−L0)/2). After calculating DC2, DR0, and U02 (V02) for the third pixel of the first row, the algorithm proceeds to step  228 , FIG. 3( b ).  
         [0043]    If, at step  225 , it is determined that the third pixel of the first row is not to be texture mapped, then the process continues at step  228  where a determination is made as to whether the fourth pixel of the first row is lit. If the fourth pixel of the row is lit, then an interpolation is made at step  230  to determine the texture address partial with respect to the y dimension, i.e., DC3, for the fourth pixel of the first row of the span, calculated as DC3=DR/4−((DR−DL)/4). If DR0 was not calculated in a previous step, then the DR0 calculation DR0=((R0−L0)/4) is performed, as above, with DR, DL, R0 and L0 already computed. Additionally, at step  230 , the (u,v) texture address value is calculated, which for exemplary purposes, for texture coordinate U 0,3  is calculated as U03=R0−((R0−L0)/4).  
         [0044]    It should be understood that for each of the texture address partials DC0-DC3 and DR0 calculated at steps  218 ,  222 ,  227  and  230 , concurrent operations are performed for calculating vertical (V) texture address partials with respect to the x dimension to approximate the ∂v/∂x and the ∂v/∂y values.  
         [0045]    If, at step  212 , FIG. 3( b ), the pixel mask indicates that no pixel is lit in the first row of the span, or, the interpolations are already performed for any lit pixel in the first row, then the algorithm proceeds to step  232 , to determine if a pixel is lit in the second row of the span. If a lit pixel does exist in the second row of the span, then at step  234 , a computation is made to determine the extreme right and left addresses, R1 and L1. As shown in FIG. 4, an interpolation is performed to calculate L1=U00+DL/4 (with U00 given), and R1=U04+DR/4 (with U04 given). Next, at step  236 , a determination is made as to whether the first pixel of the second row is lit. If the first pixel of the row is lit, then a computation is made at step  238  to determine the horizontal texture address partial (U) calculated with respect to the x dimension (∂u/∂x) as shown in FIG. 4 as partial DR1, and, the horizontal texture address partial calculated with respect to the y dimension (∂u/∂y) as shown in FIG. 4 as partials DC0. It should be understood that (V coordinate) texture address partials are also calculated with respect to the x dimension to approximate the ∂v/∂x values for the subsequent pixel LOD calculation and with respect to the y dimension to approximate the ∂v/∂y values.  
         [0046]    The texture address partial with respect to the y dimension, i.e., DC0, for the first pixel of the second row of the span is calculated as described above, i.e., DC0=DL/4. All texture address partials calculated with respect to the x dimension (∂u/∂x, ∂v/∂x) for each pixel of a given row are identical, and thus, for the second row, an interpolation is performed such that DR1=((R1−L1)/4), with DL, DR, R1 and L1 already computed. Additionally, at step  238 , the (u,v) texture address value is calculated, which for exemplary purposes, for the texture coordinate U 1,0  is calculated as U10=L1. After calculating DC0 and DR1, and U10 (V10) for the first pixel of the second row, the algorithm proceeds to step  240 , FIG. 3( b ).  
         [0047]    If, at step  236 , it is determined that the first pixel of the second row is not to be texture mapped, then the process also continues at step  240  to determine if the second pixel of the second row is lit. If the second pixel of the second row is lit, then an interpolation is made at step  242  to determine the texture address partial with respect to the y dimension, i.e., DC1, for the second pixel of the second row of the span, calculated as DC1=DC0+((DR−DL)/4). If DR1 was not calculated in a previous step, then the DR1 calculation DR1=((R1−L1)/4), is performed, with DR, DL, R0 and L0 already computed. Additionally, at step  242 , the (u,v) texture address value is calculated, which for exemplary purposes, for the texture coordinate U 1,1  is calculated as U11=L1+((R1−L1)/4). After calculating DC1, DR1, and U11 (V11) for the second pixel of the second row, the algorithm proceeds to step  245 , FIG. 3( b ).  
         [0048]    If, at step  240 , it is determined that the second pixel of the second row is not to be texture mapped, then the process continues at step  245  where a determination is made as to whether the third pixel of the second row is lit. If the third pixel of the second row is lit, then an interpolation is made at step  247  to determine the texture address partial with respect to the y dimension, i.e., DC2, for the third pixel of the second row of the span, calculated as DC2=DC0+((DR−DL)/2). If DR1 was not calculated in a previous step, then the DR1 calculation DR1=((R1−L1)/4) is performed, as above, with DR, DL, R0 and L0 already computed. Additionally, at step  247 , the (u,v) texture address value is calculated, which for exemplary purposes, for the texture coordinate U 1,2  is calculated as U12=L1+((R1−L1)/2). After calculating DC2, DR1, and U12 (V12) for the third pixel of the second row, the algorithm proceeds to step  248 , FIG. 3( b ).  
         [0049]    If, at step  245 , it is determined that the third pixel of the second row is not to be texture mapped, then the process continues at step  248  where a determination is made as to whether the fourth pixel of the second row is lit. If the fourth pixel of the second row is lit, then an interpolation is made at step  250  to determine the texture address partial with respect to the y dimension, i.e., DC3, for the fourth pixel of the second row of the span, calculated as DC3=DR/4−((DR−DL)/4). If DR1 was not calculated in a previous step, then the DR1 calculation DR1=((R1−L1)/4) is performed, as above, with DR, DL, R0 and L0 already computed. Additionally, at step  250 , the (u,v) texture address value is calculated, which for exemplary purposes, for texture coordinate U 1,3  is calculated as U13=R1—((R1—L1)/4).  
         [0050]    It should be understood that for each of the texture address partials DC0-DC3 and DR1 calculated at steps  238 ,  242 ,  247  and  250 , concurrent operations are performed for calculating vertical (V) texture address partials with respect to the x dimension to approximate the ∂v/∂x and with respect to the y pixel dimension to approximate the ∂v/∂y values for any lit pixel in the second row.  
         [0051]    If, at step  232 , FIG. 3( b ), the pixel mask indicates that no pixel is lit in the second row of the span, or, if interpolations have already been performed for any lit pixel in the second row, then the algorithm proceeds to step  252 , to determine if a pixel is lit in the third row of the span. Essentially, calculations made for the first and second row interpolations, are similarly made for each lit pixel in the third row of the span, however, for third row pixels, the texture address partials (approximating ∂u/∂x, ∂v/∂x) calculated with respect to the x dimension is DR2, and the texture address values are U 2,0 -U 2,3 . Thus, if pixels are lit in the third row of the span, then at step  254 , a computation is made to determine the extreme right and left addresses, R2 and L2 with R2=U04+DR/2 and L2=U00+DL/2. At steps  256  and  258 , FIG. 3( b ), if a first pixel of the third row is to be lit, the calculation for DC0 as described above, is made, and a calculation is made to determine DR2 which is DR2=((R2−L2)/4) with R2 and L2 already computed. Additionally, at step  258 , the (u,v) texture address value is calculated which for exemplary purposes, for texture coordinate U 2,0 , is calculated as U20=L2.  
         [0052]    Next, at steps  260  and  262 , FIG. 3( b ), if a second pixel of the third row is lit, the calculation for DC1 as described above, is made, and if DR2 was not calculated in a previous step, then the DR2 calculation DR2=((R2−L2)/4) is performed. Additionally, at step  262 , the (u,v) texture address value is calculated, which for lit pixel U 2,1 , is calculated as U21=L2+((R2−L2)/4).  
         [0053]    Next, at steps  265  and  267 , FIG. 3( b ), if a third pixel of the third row is lit, the calculation for DC2 as described above, is made, and if DR2 was not calculated in a previous step, the DR2 calculation DR2=((R2−L2)/4) is performed. Additionally, at step  267 , the (u,v) texture address value is calculated which for this lit pixel corresponds to texture coordinate U 2,2 , and is calculated as U22=L2+((R2−L2)/2). Finally, at steps  268  and  270 , FIG. 3( b ), if a fourth pixel of the third row is lit, the calculation for DC3 as described above, is made, and if DR2 was not calculated in a previous step, the DR2 calculation DR2=((R2−L2)/4) is performed. Additionally, at step  270 , the (u,v) texture address value is calculated which for exemplary purposes, is texture coordinate U 2,3 , and calculated as U23=R2−((R2−L2)/4).  
         [0054]    If, at step  252 , FIG. 3( b ), the pixel mask indicates that no pixel is lit in the third row of the span, or, if interpolations have already been performed for any lit pixel in the third row, then the algorithm proceeds to step  272 , to determine if a pixel is lit in the fourth row of the span. Essentially, calculations made for the first, second and third row interpolations, are similarly made for each lit pixel in the fourth row of the span, however, for fourth row pixels, the texture address partials calculated with respect to the x dimension (approximating ∂u/∂x, ∂v/∂x) is DR3, and the texture address values are U 3,0 -U 3,3 . Thus, if pixels are lit in the fourth row of the span, then at step  274 , a computation is made to determine the extreme right and left addresses, R3 and L3 with R3=U44−DR/4 and L3=U40−DL/4. At steps  276  and  278 , FIG. 3( b ), if a first pixel of the fourth row is to be lit, the calculation for DC0 as described above, is made, and a calculation is made to determine DR3 which is DR3=((R3−L3)/4) with R3 and L3 already computed. Additionally, at step  278 , the (u,v) texture address value is calculated which for exemplary purposes, for texture coordinate U 3,0 , is calculated as U30=L3.  
         [0055]    Next, at steps  280  and  282 , FIG. 3( b ), if a second pixel of the fourth row is lit, the calculation for DC1 as described above, is made, and if DR3 was not calculated in a previous step, then the DR3 calculation DR3=((R3−L3)/4) is performed. Additionally, at step  282 , the (u,v) texture address value is calculated, which for lit pixel U 3,1 , is calculated as U31=L3+((R3−L3)/4).  
         [0056]    Next, at steps  285  and  287 , FIG. 3( b ), if a third pixel of the fourth row is lit, the calculation for DC2 as described above, is made, and if DR3 was not calculated in a previous step, the DR3 calculation DR3=((R3−L3)/4) is performed. Additionally, at step  285 , the (u,v) texture address value is calculated which for this lit pixel corresponds to texture coordinate U 3,2 , and is calculated as U32=L3+((R3−L3)/2). Finally, at steps  288  and  290 , FIG. 3( b ), if a fourth pixel of the fourth row is lit, the calculation for DC3 as described above, is made, and if DR3 was not calculated in a previous step, the DR3 calculation is performed. Additionally, at step  290 , the (u,v) texture address value is calculated which for exemplary purposes, is texture coordinate U 3,3 , and calculated as U33=R3−((R3−L3)/4).  
         [0057]    It readily follows that the LOD index computations per pixel as described with respect to FIG. 3( b ), are employed to calculate the corresponding V dimension texture address partials (∂v/∂x, ∂v/∂y) and texture address coordinates V 0,0 -V 3,3 . It should be understood that the texture address partials computations provided is for exemplary purposes only, with the exact order of computation being a design choice and not necessary limited to the order shown. For example, as dictated by a particular hardware implementation, the individual terms  
           ∂   u       ∂   x       ,       ∂   u       ∂   y       ,       ∂   v       ∂   x       ,       ∂   v       ∂   y                             
 
         [0058]    of these equations can be computed discretely by subtracting the address of the current pixel from the texture address of the neighboring pixels below and to the right. While horizontal delta value ∂u/∂x=DR can be easily calculated by horizontal texture address interpolators, the calculation of the vertical terms, e.g., ∂u/∂y=DC0−DC3 require additional hardware as the texture address interpolator can process pixels one at a time in row major order and the texture address of a pixel immediately below the current pixel may not be readily available. A gate savings is realized however, by interpolating the values of vertical terms between the extreme left and right columns, as described herein, rather than computing them directly.  
         [0059]    From the foregoing interpolation algorithm  200  described herein with respect to FIG. 3( b ), it should be understood that only the pixels that are lit in the current span are the pixels whose partials are to be determined. Referring back to FIG. 3( a ), as indicated at step  300 , as each set of texture address partials corresponding to each lit pixel of the current span is determined, it is fed into a LOD calculator in a pipeline fashion, which generates the level of detail index “LOD” value for the lit pixel in accordance with the Heckbert equation (equation (1)). This LOD index will determine from which texture map the address (u, v) corresponding to the lit pixel will be mapped for display on the screen, as indicated at step  325 . In accordance with equation (1), an approximation may be made for each of the square root terms in accordance with the following relation shown in equation (4):  
                   a   2     +     b   2         =       max                   (          a        ,        b          )       +       min                   (          a        ,        b          )       2               (   4   )                               
 
         [0060]    where |a| represents the absolute value of “a” corresponding to the ∂u/∂x and ∂u/∂y values and |b| represents the absolute value of “b” corresponding to the ∂v/∂x and ∂v/∂y values. Although the algorithm  200  and the partial derivative approximations permits inaccuracies introduced by the linear interpolation, these are deemed to be negligible and imperceptible to the human eye for most practical applications.  
         [0061]    After the LOD index values are selected and the appropriate texture map selected for the object pixels to be texture mapped, the procedure returns to step  350 , FIG. 3( a ), to determine if all of the pixels of the object are mapped with texture. If not, successive spans are processed until the polygonal object is completely rendered with texture in accordance with the interpolation technique described herein. Thus, if all of the object pixels are not mapped with texture, the algorithm proceeds to step  375  where the span corner processor provides the n×n span of pixels to a location adjacent the previous generated span that has lit pixels. FIG. 5 illustrates this new span  30 ′ defined adjacent the first span  30  such that the values of the two previously calculated perspectively correct texture addresses, e.g., located at pixels  32  and  34 , are retained, thus necessitating the calculation of only two new perspectively correct texture address values associated with pixels at new corners of the new span  30 ′ as indicated at step  200 , FIG. 3( a ). The generation of the new span  30 ′ is less costly because all that is required is the computation of perspectively correct texture address values for only two corners of the new span, which, in certain hardware implementations may take six (6) machine clock cycles or less. FIG. 5 illustrates the calculation of two new perspectively correct texture address values for pixels  42  and  44  associated with new corners of span  30 ′. It is important to note that the span processor is always preprocessing spans while the interpolation process (step  200  to step  350 ) is being performed on the previous span. This allows an interpolation to happen per clock.  
         [0062]    While there are new spans left, the algorithm will proceed to step  200  where the interpolation algorithm described with respect to FIG. 3( b ) is again performed, for instance, to calculate texture address partials and addresses for new lit pixels of the perspective polygon to be texture mapped, e.g., pixels  47  and  48 , shown in FIG. 5.  
         [0063]    Returning again to step  325 , FIG. 3( a ), if it is determined that the object is completely mapped with texture information, the level of detail of which is determined on a per pixel basis as described herein, the algorithm terminates.  
         [0064]    There are many ways in hardware to implement the method of the invention. One embodiment is illustrated conceptually in FIG. 6 which shows a span processor  65  used to generate the n×n span of pixels for each iteration and to calculate each of the perspectively correct texture values for the associated corner pixels of each span based on information of the polygon to be rendered. The information generated by the span processor  65  includes the perspective correct texture address calculations U00, U04, U40, U44 at each of the left and right columns of the span. As shown in FIG. 6, these left and right perspective correct texture addresses are input via respective lines  66 ,  68  to an interpolator unit which includes first vertical interpolator unit  67  for calculating left side vertical delta values DL (for U,V dimensions) and left column texture addresses L0-L3, and a concurrently operating second vertical interpolator unit  69  for calculating right side vertical delta values DR (for U,V dimensions) and right column texture addresses R0-R3 summarized herein as follows:  
         [0065]    DL=U40−U00  
         [0066]    DR=U44−U04  
         [0067]    L0=U00  
         [0068]    L1=U00+DL/4  
         [0069]    L2=U00+DL/2  
         [0070]    L3=U40−DL/4  
         [0071]    R0=U04  
         [0072]    R1=U04+DR/4  
         [0073]    R2=U04+DR/2  
         [0074]    R3=U44 31  DR/4;  
         [0075]    These left and right side vertical delta values DL and DR and left and right column texture addresses for the pixel to be lit in each row of the span are then input via line  71  to a second interpolator unit having a horizontal address interpolator  70  and a column delta interpolator  72  which are both employed to calculate the texture address partials (Delta u, Delta v) with respect to both horizontal (x) and vertical (y) pixel dimensions, such as described herein. Particularly, the horizontal address interpolator  70  easily calculates the following texture address partial values for any lit pixel in a span row:  
         [0076]    DR0=((R0−L0)/4)  
         [0077]    DR1=((R1−L1)/4)  
         [0078]    DR2=((R2−L2)/4)  
         [0079]    DR3=((R3−L3)/4).  
         [0080]    The Column Delta Interpolator  72  calculates the following texture address partial values for any lit pixel in a span row:  
         [0081]    DC0=DL/4  
         [0082]    DC1=DC0+((DR−DL)/4)  
         [0083]    DC2=DC0+((DR−DL)/2)  
         [0084]    DC3=DR/4−((DR−DL)/4).  
         [0085]    As shown in FIG. 4, from the interpolated texture addresses L0-L3 and R0-R3, the individual texture address coordinates (U r,q ,V r,q ) for any pixel in the span to be mapped is computed by the horizontal address and column delta interpolators. Accordingly, a summary of the computations for the texture address coordinates U 0,0 -U 3,3  for lit pixel of the span  30  of FIG. 4 is provided as follows:  
         [0086]    U00=U00 (Given)  
         [0087]    U01=L0+((R0−L0)/4)  
         [0088]    U02=L0+((R0−L0)/2)  
         [0089]    U03=R0−((R0−L0)/4)  
         [0090]    U10=L1  
         [0091]    U11=L1+((R1−L1)/4)  
         [0092]    U12=L1+((R1−L1)/2)  
         [0093]    U13=R1−((R1−L1)/4)  
         [0094]    U20=L2  
         [0095]    U21=L2+((R2−L2)/4)  
         [0096]    U22=L2+((R2−L2)/2)  
         [0097]    U23=R2−((R2−L2)/4)  
         [0098]    U30=L3  
         [0099]    U31=L3+((R3−L3)/4)  
         [0100]    U32=L3+((R3−L3)/2)  
         [0101]    U33=R3−((R3−L3)/4)  
         [0102]    Thus, the horizontal delta values DR0-DR3 and the vertical delta values DC0-DC3 are input via respective lines  74 ,  76  to an LOD calculator  78  which approximates the LOD index value on a per pixel basis in accordance with equations 1 and 4. Each computed texture address value and its corresponding calculated LOD index value are input via respective lines  80  and  82  to a texture map lookup and application unit  85  which maps the texture information from the appropriate texture map  95 , based on the level of detail calculated for the pixel to be rendered, to each of the object pixels of the perspective polygon. The texture information is then forwarded to the computer screen display via line  90 .  
         [0103]    A hardware schematic of a simple linear interpolator  50  for performing the interpolations of the algorithms described herein is illustrated in FIG. 7. As shown in FIG. 7, the interpolator  50  includes inputs  51 - 54  for the left and right values if performing a horizontal interpolation, or the top and bottom values for a vertical interpolation. The left column addresses (L0-L3) and right column addresses (R0-R3) are examples of vertical interpolation. The column delta&#39;s (DC0-DC3) and the address interpolation (Ux0-Ux3) are examples of horizontal interpolations (x=0, . . . , 3). The input select signal  56  which controls the operation of multiplexer  61   b , the Invert signal  57  which controls the operation of both exclusive OR gate  59  and multiplexer  61   a , and the Force Zero signal  58  which controls the NOT/AND gate  60  are used to control the interpolators to create a value that is ¼, ½, ¾ of the value between the two end values. Additionally, the  61   b  multiplexer will select either a divide-by-four or divide-by-two logical shift of the difference between signals at inputs  53  and  54 . A truth table for the operation of the interpolator circuit  50  is shown in Table 1 as follows:  
                                                   Force           Sel   Invert   Zero   Output                   0   x   1   Left/Top       0   0   0   Left/Top + ((Right/Bottom -                   Left/Top)/4)       1   0   0   Left/Top + ((Right/Bottom -                   Left/Top)/2)       0   1   0   Right bottom - ((Right/Bottom -                   Left/Top)/4)                  
 
         [0104]    For instance, to calculate the address U10, the input L1 would be input, and the force zero signal  58  will be set to logic 1 to prevent influence of the signals  53  and  54  at the output of adder element  62 . To calculate U13, however, the invert signal  57  will be set to logic 1 to control the inverter  59  and mux  61   a  to enable subtraction of the term ((R1−L1)/4) from the value R1.  
         [0105]    The foregoing merely illustrates the principles of the present invention. Those skilled in the art will be able to devise various modifications, which although not explicitly described or shown herein, embody the principles of the invention and are thus within its spirit and scope.