Abstract:
In an apparatus and method for performing perspective interpolation of texture coordinates in computer graphics, an incremental interpolation technique is used to calculate the pixel values along a display line from the associated texture map. The incremental technique is based on Bresenham&#39;s algorithm adapted for use with hyperbolae. On the basis of the parameters of the start and end pixels of a span along a display line, a set of interpolation test parameters is set and the texel coordinates for the current pixel are tested against these parameters to determine whether they are still valid for the next pixel. If they are not valid, the test parameters are updated and the texel coordinates are incremented and retested. This process is repeated until the correct texel is identified.

Description:
BACKGROUND OF THE INVENTION 
     1. Field of the Invention 
     The present invention relates to an image processing apparatus and method for performing texture mapping and similar operations, with particular application in 3-dimensional (&#34;3D&#34;) computer graphics. The invention has particular use in interpolating parameters such as texture coordinates in perspective view. 
     2. Description of Prior Art 
     Texture mapping is well known in the art of 3-dimensional image synthesis (see for example &#34;Computer Graphics Principles and Practice&#34; by Foley, van Dam, Feiner and Hughes, 2nd Edition, Addison-Wesley Publishing Company, ISBN 0-201-12110-7). 
     The process of texture mapping is useful for applying surface detail to 3D objects within an image to be displayed. A pre-stored image of the surface details is mapped onto the surface of an object in order to display the image. The surface image is known as a &#34;texture map&#34; or &#34;texture image&#34;, and is made up of individual elements called texels, residing in texture coordinate space (defined by the variables U,V). The texture map may represent, for example, a colour, transparency or shadow profile etc. Similar processes are known as &#34;bump mapping&#34; (representing surface normal variations) and &#34;environment mapping&#34; (representing image reflections), and it will be understood that the present disclosure, while referring simply to &#34;texture mapping&#34;, implicitly extends to include all such processes in which a surface property is modulated over the area of a surface primitive. 
     To perform texture mapping, the coordinates of a display pixel lying within an area representing the object are mapped into texture coordinates space, to define a corresponding texel or texels. The value for the pixel is then derived from the value of the texel(s). 
     It is known in the art that, in a perspective projection of a 3D object from object space to display space, linear changes in pixel position produce non-linear changes in each texel coordinate. Specifically, each texel coordinate is a hyperbolic function of pixel position. This is disclosed in, for example, &#34;Hyperbolic Interpolation&#34; by James F. Blinn in Jim Blinn&#39;s Corner, IEEE Computer Graphics and Applications, July 1992. Accordingly, to perform texture mapping with correct perspective, it has previously been necessary to evaluate two hyperbolic equations (one for each texel coordinate) every time a pixel value is determined. This is very time consuming, principally since each function evaluation requires a division operation (each requiring many cycles in a typical microprocessor), and accordingly two such divisions need to be performed for every pixel, while the number of pixels to be processed is typically thousands or even millions. 
     The divisions per pixel may be avoided if the object to be displayed lies in a plane of constant depth in viewing space. This is because, in this special case, texel coordinates are linearly related to pixel position. Accordingly, in a number of known systems, lines of constant depth along an object surface are defined so that rendering of the pixels corresponding to these constant depth lines can be carried out. This provides good results for limited classes of simple graphic objects, such as horizontal floors and vertical walls, in a limited system where the view direction is always parallel to the floor. However, constant-depth techniques are problematic in more general graphics, since lines of constant depth often do not correspond to lines or columns of pixels on the screen, making rendering complex. 
     In more generally useful graphic systems, therefore, the division per pixel has always been tolerated where perspectively-correct mapping is desired, or else correct perspective has been only approximated, to increase performance on a given hardware platform, for example by replacing the hyperbola with simple linear, piecewise linear or polynomial approximations, or by dividing the polygons to be rendered into smaller ones by tessellation. Particularly in animated sequences, however, mappings without correct perspective result in unnatural motion effects (&#34;swimming&#34;) limiting the utility of the system. 
     BRIEF SUMMARY OF THE INVENTION 
     It is an object of the invention to provide a new low-cost technique for texture mapping, and similar operations, with correct perspective. 
     According to a first aspect of the invention, there is provided a method of surface parameter mapping in which a surface parameter mapping coordinate value is assigned by testing whether the mapping coordinate value corresponding to a current pixel position is valid at a next pixel position. The values of two or more coordinates may be tested separately. If either coordinate value corresponding to a current pixel is not valid at a next pixel, according to a current decision criterion, that coordinate value is incremented or decremented until the correct value is reached. 
    
    
     In a second aspect, the invention provides a method of surface parameter interpolation in which an initial set of test parameters is set and a surface parameter value is assigned with reference to the test parameters, the test parameters being updated after each surface parameter value is assigned. The surface parameter may be a mapping coordinate indexing, for example, a texture map. 
     BRIEF DESCRIPTION OF THE DRAWINGS 
     Embodiments of the invention will now be described by way of example, in conjunction with the accompanying drawings, in which: 
     FIG. 1 is a block diagram showing the general arrangement of an image processing apparatus according to an embodiment of the invention. 
     FIG. 2 schematically illustrates the operations performed by the computer in an embodiment of the invention. 
     FIG. 3 schematically illustrates a triangular polygon to be rendered in the display image, and the data associated with each vertex of the polygon. 
     FIG. 4 shows the steps performed in texture mapping in an embodiment of the invention. 
     FIG. 5 shows the steps by which values of each pixel in a span are calculated at step 68 in FIG. 4 in an embodiment of the invention. 
     FIG. 6 schematically illustrates the method used in an embodiment of the invention for determining the correct texel value. 
    
    
     DETAILED DESCRIPTION OF EXEMPLARY EMBODIMENTS 
     FIG. 1 is a block diagram showing the general arrangement of an image processing apparatus according to a first embodiment. In the apparatus, there is provided a computer 2, which comprises a central processing unit (CPU) 4 connected to a memory 6 operable to store a program defining the sequence of operations of the CPU 4, and to store object and image data used in calculations by the CPU 4. 
     Coupled to an input port of the CPU 4 there is an input device 8, which may comprise, for example, a keyboard and/or a position sensitive input device such as a mouse, tracker-ball, or a digitizer tablet and stylus etc. 
     Also coupled to the CPU 4 is a frame buffer 10 which comprises a memory unit arranged to store image data relating to at least one image, for example by providing one (or several) memory location(s) per pixel of the image. The value stored in the frame buffer for each pixel defines the colour or intensity of that pixel in the image. 
     Images are generally two-dimensional arrays of pixels, and are conveniently described in terms of cartesian coordinates, so that the position of a given pixel can be described by a pair of x-y coordinates. This representation is convenient when, for example, the image is to be displayed on a raster scan display since the x coordinate maps to the distance along a line of the display, and the y coordinate maps to the number of the line. The frame buffer 10 has sufficient memory capacity to store at least one image. For example, for an image having a resolution of 1000×1000 pixels, the frame buffer 10 includes 10 6  pixel locations, each addressable directly or indirectly in terms of pixel coordinates x,y. 
     Coupled to the frame buffer 10 is a display unit 12 for displaying the image stored in the frame buffer 10 in a conventional manner. Also coupled to the frame buffer 10 is a video tape recorder (VTR) 14 or other image recording device, such as a paper printer or 35 mm film recorder. 
     Coupled to the memory 6 (typically via the CPU 4), and possibly also to the frame buffer 10, is a mass storage device 16, such as a hard disc drive, having a high data storage capacity. Also coupled to the memory 6 is a disc drive 18 which is operable to accept removable data storage media, such as a floppy disc 20, and to transfer data stored thereon to the memory 6. 
     The CPU 4, memory 6, frame buffer 10, display unit 12 and mass storage device 16 may be commercially available as a complete system, for example as a personal computer (PC) or a workstation such as the SparcStation available from Sun Microsystems. 
     Embodiments of the invention can be supplied commercially in the form of programs stored on a floppy disc 20 or other medium, or signals transmitted over a data link, so that the receiving hardware becomes re-configured into an apparatus embodying the invention. As will be seen, the invention allows technically better performance to be achieved than was hitherto possible with a given type of computer hardware. 
     The overall operation of the apparatus will now be described. 
     With reference to FIG. 2, the computer 2 performs a number of different operations at different times, executing corresponding stored programs within the memory 6, and therefore comprises (together with the memory 6) means 44 to 52 for performing such operations. These means are illustratively shown in FIG. 2 as separate, although in the present embodiment, all are performed by the CPU 4 in cooperation with the memory 6. It will be understood, however, that separate processors or dedicated logic circuits, operatively connected, could be provided to execute each function. 
     The embodiment may thus be considered as comprising, firstly, a definer and editor 44 arranged to define the shape of a two- or three-dimensional object and likewise, optionally, to edit the object. The definer/editor 44 is connected to the mass storage device 16 to enable an object, once defined, to be stored for subsequent use. The definer/editor 44 is also connected to the input device 8 to enable an operator to input and/or change the object. In the present embodiment, the data defining an object is data representing control points or vertices of a plurality of surfaces making up the object, which in the present embodiment are polygons. If a texture image is to be applied to the object, the definer/editor 44 is also used to assign a texture coordinate pair of the pre-stored texture image to each vertex of each polygon in the object. 
     Sorter 46 is provided for performing an initial operation of sorting the surfaces or regions of the object into an order which determines the order in which they will be drawn (i.e. rendered into the frame buffer 10) so as to draw last those regions which are intended to occlude others. The sorter 46 reads the object data defined by the definer/editor 44 and generates a corresponding sorted list of regions for subsequent use. 
     The appearance of the object on the two dimensional screen of the display unit 12, and consequently the image data stored in the frame buffer 10, is dependent upon the view direction from which the object is to be viewed. It may also be dependent upon the distance between the object and a notional viewpoint corresponding to the plane of the screen of the display unit 12. View controller 48 is therefore provided for enabling an operator to define a view direction, or a view direction and a distance (for example, by defining the coordinates of a viewpoint and/or view direction), via the input device 8. Rather than defining individual viewpoints one at a time, the input means 8 may be employed to define a trajectory of successive viewpoints or viewing directions, for example by specifying a direction of movement and speed. 
     Projector 50 is provided to perform a projection of each polygon within a given three dimensional object into the two dimensional viewing plane. 
     Each two dimensional viewing plane region projected by the projector 50 is then rendered, in the order previously defined by the sorter 46, by a renderer 52 which fills the region (that is, allocates an appropriate colour or grey scale value to each pixel location in the frame buffer 10 which lies within the region). In performing the rendering operation, the renderer 52 is arranged to test each region to determine which direction in the projected plane it is facing, since only regions which face outwardly of the object (&#34;forward facing&#34;) need to be rendered. In addition, the renderer 52 performs texture mapping before writing the pixel values into the frame buffer 10, as will now be described. 
     The renderer 52 receives data from the projector 50 defining each polygon in terms of its vertices. For each vertex, the renderer 52 receives data defining the pixel position within the 2-D raster display in terms of the x,y coordinates described previously, a value defining the reciprocal of the depth of the vertex in eye space (commonly known in the art as a 1/z value), and, if a texture map is to be applied to the polygon, the data defining the texel location of the vertex in terms of the two quantised texture map coordinates (which will hereinafter be referred to as U and V) defined by the definer/editor 44. This is illustrated schematically in FIG. 3 for a polygon having vertices A, B, C and D (with the values associated with each vertex having the suffix a, b, c or d accordingly). 
     The way in which the renderer 52 completes the texture mapping process to determine values for each pixel within the polygon will now be described with reference to FIG. 4. 
     At step 60, the renderer 52 reads the data described above for each vertex of the polygon. At step 62, this data is then used to calculate the following &#34;delta&#34; values (gradient with respect to y) for the left and right sides of the polygon: ##EQU1## where, Δx 1  is the delta value for the left-hand side of the polygon shown in FIG. 3, Δx r  is the delta value for the right-hand side of the polygon, x is the pixel position for a vertex along a given scan line, and y is the number of the scan line on which the vertex lies. 
     The left and right delta values are then used at step 64 to determine the start and end pixels on the scan line to be rendered. The y coordinate of the start and end pixels is given by the number of the scan line (that is, yi 1  =yi r  =ya+i, where i is the number of the scan line running from 0 at the scan line containing vertex A to yb-ya at the scan line containing vertex B; see FIG. 3), while the x coordinates are given by: 
     
         xi.sub.1 =xa+iΔx.sub.1 
    
     
         xi.sub.r =xa+iΔx.sub.r 
    
     where, xi 1  is the x coordinate of the start (left) pixel and xi r  is the x coordinate of the end (right) pixel. 
     In practice, the scan lines are dealt with sequentially, so that the values of iΔx 1  and iΔx r  are determined for each line simply by incrementing the previous value by Δx 1  or Δx r  as appropriate. 
     At step 66, the renderer 52 determines the U,V and 1/z values for the start and end pixels determined at step 64. Since 1/z varies linearly along the sides of the polygon between vertices, its value at the start and end pixels is determined from the vertex data read at step 60 using the following linear equations: ##EQU2## where, Ri 1  is the 1/z value at the start pixel on the ith scan line, Ri r  is the 1/z value at the end pixel on the ith scan line, Ra=1/Za, and Rb=1/Zb. 
     As is known to persons skilled in the art, for example from the Blinn reference above, the values of U and V should vary hyperbolically along the edges of the polygon between the vertices for correct perspective. Accordingly, the U and V values for the start and end pixels on a given scan line are calculated in this embodiment using the following hyperbolic equations: ##EQU3## where, Ui 1  is the U value at the start pixel, Ui r  is the U value at the end pixel, Vi 1  is the V value at the start pixel, Vi r  is the V value at the end pixel, Ra and Rb are as defined above, and q 1  and q r  are variables which vary linearly between 0 and 1 in accordance with the distance of the pixel along the left and right edges respectively of the polygon between the vertices, q 1  and q r  therefore being given by the following equations: ##EQU4## Referring again to FIG. 4, at step 68, the renderer 52 calculates the value of each pixel along a given scan line between the start pixel and the end pixel using the values calculated in step 66, and stores all of the values for the span of pixels, for example in the frame buffer 10. The manner in which this is performed is described below. 
     At step 70, a check is made as to whether the scan line just processed is the last scan line within the polygon. If it is not, steps 64 to 70 are repeated until all of the scan lines have been processed. The rendering of the polygon is then complete, and the process for that particular polygon ends at step 72, although of course it will be appreciated that the whole of the process shown in FIG. 4 can subsequently be repeated for other polygons. If the triangle to be rendered is the triangle ADC shown in FIG. 3, then the triangle may be split at vertex C (i.e. the middle vertex in the vertical direction) so that triangles ABC and BDC are rendered separately, in the conventional manner. 
     The way in which the renderer 52 performs step 68 in FIG. 4 will now be described with reference to FIG. 5. 
     At step 100, the renderer 52 sets the following interpolation test parameters on the basis of the parameters of the start and end pixels for the line calculated at step 66 in FIG. 4: ##EQU5## 
     If U r  -U 1  &gt;0 set: ##EQU6## and set: Sign delta U=1 else set: ##EQU7## and set: Sign delta U=-1 
     If V r  -V 1  &gt;0 set: ##EQU8## and set: Sign delta V=1 else set: ##EQU9## and set: Sign delta V=-1 
     The renderer 52 also sets the following test parameters: ##EQU10## where s, is the number of pixels along the scan line which lie within the polygon, s therefore being given by: 
     
         s=x.sub.r -x.sub.1 
    
     (Strictly, S is given by s=x r  -x 1  +1, but the term &#34;+1&#34; is ignored since it has a neglisible effect on the result.) 
     At step 100, the renderer 52 also initialises the first texel, this being defined by the texture space coordinates of the start pixel. Accordingly, the values of U and V which are used at step 100 to look up a texel value will be those previously calculated for the start pixel at step 66 in FIG. 4. 
     At step 102, the values of the texel are plotted to the pixel, which, in this embodiment is then stored, for example in the frame buffer 10. In performing step 102 for the first time, the pixel will be the start pixel on the scan line. In addition to storing the pixel value, the U,V values are also retained locally, for example in a register or cache within the CPU 4, for use in subsequent steps, as will now be described. 
     At step 104, a test is performed to determine whether the pixel just considered is the last pixel on the scan line segment that is to be subject to dithering. If the pixel is the last pixel, then the process terminates at step 106. If the pixel is not the last pixel, the process proceeds to consider the next pixel, as will now be described. 
     At step 108, a test is performed to determine whether the retained value of U is valid for the next pixel. This test is performed by determining whether D u   p ,t &lt;0. 
     If the value of D u   p ,t is negative, it is determined that the value of U is not valid for the next pixel, and the process proceeds via steps 110 to 116. At step 110, the test parameters previously set at step 100 are updated as follows: 
     
         D.sub.p,t.sup.u ←D.sub.p,t.sup.u +Δ.sub.t D.sub.p,t 
    
     
         Δ.sub.p.sup.u D.sub.p,t ←Δ.sub.p.sup.u D.sub.p,t +ΔΔD.sub.p,t 
    
     At step 112, the value of U, that is the value considered in the test previously carried out at step 108, is changed by 1, so that: 
     
         U←U+Sign delta U 
    
     where, the value of Sign delta U has been set to either 1 or -1 at step 100, in dependence upon the value of U r  -U 1  as described previously. 
     At step 114 the test performed in step 108 is repeated with the updated test parameters (set at step 110) to determine whether the new value of U, that is the value now changed by ±1, is the correct value for the pixel under consideration. If the value of U is now correct, the texel defined by the new value of U and the previous value of V is read at step 116. If the value of U is not correct, steps 110,112 and 114 are repeated until it is determined at step 114 that D u   p ,t is non-negative, indicating that the correct value of U has now been reached. 
     The process then proceeds to steps 118 to 126, in which the tests performed in steps 108 to 116 for U are repeated for V. More specifically, at step 118 it is tested whether D v   p ,t &lt;0, and if this is the case, steps 120 to 126 are performed, with the test parameters being updated in step 120 as follows: 
     
         D.sub.p,t.sup.v ←D.sub.p,t.sup.v +Δ.sub.t D.sub.p,t 
    
     
         Δ.sub.p.sup.v D.sub.p,t ←Δ.sub.p.sup.v D.sub.p,t +ΔΔD.sub.p,t 
    
     and the value of V being changed in step 122 as follows: 
     
         V←V+Sign delta V 
    
     When the correct value of V has been reached (i.e. when it is determined at step 124 that D v   p ,t is non-negative), the process proceeds to step 126 where the new texel is read (thereby negating any texel read at step 116). The test parameters are then updated at step 128 in order to consider the next pixel as follows: 
     
         D.sub.p,t.sup.u ←D.sub.p,t.sup.u +Δ.sub.p.sup.u D.sub.p,t 
    
     
         D.sub.p,t.sup.v ←D.sub.p,t.sup.v +Δ.sub.p.sup.v D.sub.p,t 
    
     
         Δ.sub.t D.sub.p,t ←Δ.sub.t D.sub.p,t +ΔΔD.sub.p,t 
    
     If in step 108 it is determined than the value of U is valid for the next pixel, the process proceeds directly to step 118, missing out step 110 to 116. Similarly, if it is determined at step 118 that the value of V is valid for the next pixel, the process proceeds directly to step 128. In this case, no new texel is read, so that at step 102, the previous (current) texel is plotted to the next pixel. 
     Steps 102 to 128 are then repeated until it is determined in step 104 that the pixel is the last one in the span, the process then terminating at step 106. 
     The reasons why the process described above generates the required texture coordinate values for pixels within a polygon will now be explained. 
     As explained previously, for correct perspective, the values of each texture coordinate U,V vary hyperbolically in relation to linear changes in display pixel position. Thus, considering the polygon previously described with respect to FIG. 3, U and V vary with the pixel position along a scan line as follows: ##EQU11## where, t is a quantised texture coordinate (i.e. either U or V), p is the pixel position along the scan line varying from 0 at the start pixel of the polygon segment to s at the end pixel of the polygon segment, and the final equation in α, β, γ and δ is the general equation for a hyperbola. 
     Differentiating, the slope of this hyperbola is: ##EQU12## 
     Since the denominator of this term is always positive (the values of Z being positive since only objects in front of the viewer are considered), the sign of the slope is always the sign of the numerator, i.e. the sign of (t r  -t 1 ), so that the hyperbola is either monotonically increasing or monotonically decreasing. 
     When moving from pixel to pixel from left to right across a scan line (i.e. p increasing), if the hyperbola has a positive slope, the candidate texture coordinate values at the next pixel position are those above or at the current value. Similarly, if the hyperbola has a negative slope, the candidate texture coordinate values at the next pixel position are those below or at the current value. 
     Considering as an example a hyperbola having a positive slope, having found the pixel/texel pair (p,t) closest to the hyperbola at pixel p (step 66 in FIG. 4), the values at the next pixel are (p+1,t), or (p+1,t+1) or (p+1,t+2) . . . etc. 
     Referring to FIG. 6, to determine which of these values is the correct one, the embodiment described above considers the height, h, of the midpoint (p+1,t+1/2) between (p+1,t) and (p+1,t+1) above the hyperbola. If h is positive, the appropriate texture coordinate value at the next pixel position remains as t; otherwise, it is t+1 or t+2 or t+3 . . . etc. 
     The value of h is given by the following: ##EQU13## 
     Multiplying through by twice the denominator of the second term, that is, by 2 Z r   s-(p+1)!+Z 1  (p+1)! does not affect the sign of h, and instead provides a more efficiently evaluated decision variable d p ,t as follows: 
     
         d.sub.p,t =Z.sub.1 (p+1)(1-2t.sub.r +2t)+Z.sub.r  (p-s+1)(2t-1)+t(2s-2p-2)! 
    
     If d p ,t is positive (tested at steps 108 and 118 in FIG. 5), the required texture coordinate value is t. Otherwise, t is incremented to t+1 (steps 112 and 122) and the decision re-evaluated by evaluating d(p,t+1) (steps 114 and 124). This process iterates until the decision variable becomes non-negative. 
     In the embodiment described above, d(p,t+1) is found by incrementing d(p,t) by Δ t  d p ,t (steps 110 and 120), as follows: ##EQU14## 
     Once the decision variable becomes non-negative, the appropriate texture coordinate value for the next pixel column has been found. The appropriate value at the column after that is found by repeating the iteration, starting with d(p+1,t), which is set at step 128 in FIG. 5. In the embodiment described above, d(p+1,t) is found by incrementing d(p,t) by Δ p  d p ,t, as follows: ##EQU15## The present embodiment also employs second differences (ΔΔ values) to increment the values of Δ t  d p ,t (step 128) and Δ p  d p ,t (steps 110 and 120), as follows: 
     For d p ,t &lt;0:new p value, p&#39;=p and new t value, t&#39;=t; so that: 
     
         Δ.sub.t (Δ.sub.t d.sub.p,t)=0 
    
     
         Δ.sub.t (Δ.sub.p d.sub.p,t)=2Z.sub.1 -2Z.sub.r 
    
     while for d p ,t &gt;0:p&#39;=p+1, and t&#39;=t; so that 
     
         Δ.sub.p (Δ.sub.t d.sub.p,t)=2Z.sub.1 -2Z.sub.r 
    
     
         Δ.sub.p (Δ.sub.p d.sub.p,t)=0 
    
     Accordingly Δ t  (Δ p  d p ,t)=Δ p  (Δ t  d p ,t), and these values are employed in the embodiment described above. 
     Therefore, when starting the interpolation along a scan line at the left hand edge of the polygon segment, the initial values for interpolation parameters are as follows: ##EQU16## Consideration of the above values for the case where the slope of the hyperbola is negative, will show that the terms are identical, with the exception that the terms Δ p  d p ,t and d p ,t differ by the sign of (t r  -t 1 ). Accordingly, as described previously, these values are set at step 100 of FIG. 5 on the basis of whether t r  -t 1  is less than zero (i.e. in dependence on whether the hyperbola has a positive slope or a negative slope). 
     In practice, when dealing with polygons and vertex data as described previously with respect to FIG. 3, it is efficient to divide the decision variable d p ,t by Z 1  Z r , giving a new decision variable D p ,t, since this assists in deriving the initial values from the vertex data. Accordingly, the parameters above then become as follows: ##EQU17## Consideration will show that these parameters are those which were set at step 100 in FIG. 5, with abs(t r  -t 1 ) being set at step 100 in dependence upon the value of t r  -t 1 . 
     In step 100, the initial test parameters are calculated using fixed point arithmetic, for example having 16 bits integer and 16 bits fractional parts. The person skilled in the art will recognise that this allows faster processing than is possible using floating point arithmetic. At the same time, however, the range of possible z values is very great. On the other hand, for the triangle ABC of FIG. 3 the units of Za, Zb, Zc are not important, provided the three values are in proportion. To obtain the best use of the fixed point resolution, the initialisation process uses 1/z values in units of Za, Zb, Zc (the product of the three vertex z values). In such units, the value 1/Za can be obtained simply by multiplying Zb and Zc. Similarly 1/Zb is the product ZaZc, and 1/Zc is the product ZaZb. As well as ensuring good use of the resolution of fixed point values, this choice of units avoids the need for three division operations, which are typically more time-consuming than multiplications. 
     Various modifications to the embodiment above can be made, as will now be described. 
     In the embodiment described above, at step 66 in FIG. 4, the U and V values for the start and end pixels of the span on the given scan line are determined by directly evaluating the appropriate hyperbolic equation (using a division operation). As an alternative, the values of U and V may be tracked down the edges of the polygon using similar interpolation algorithms to those detailed above. However, direct evaluation of the actual hyperbolic equation will generate the exact U and V values (to the precision of the machine), including fractional parts, thereby increasing accuracy during subsequent interpolation across the scan line segment. 
     At steps 110 to 114 and 120 to 124 in FIG. 5, the values of U and V are linearly incremented to find the correct values at the next pixel. However, it is possible to use other search techniques, such as &#34;binary chop&#34; techniques, which may converge faster. Often, the number of iterations around loop 110 to 114 (or loop 120 to 124) is the same as the number of iterations performed the previous time the process was performed (i.e. for the current pixel). Accordingly, the value of U (or V) may be changed by this number of iterations directly at step 112. 
     The present invention provides the advantage of increased speed in performing hyperbolic interpolation for texture mapping or similar operations. In previous systems, texture coordinate values along the span were calculated by evaluating the hyperbolic equations defining the relationship between pixel position and texture coordinates, which involved at least two division operations per pixel (typically costing about 50 cycles for each division alone). However, with the present invention, division operations per pixel are avoided. 
     The present invention exploits the pixel-space coherence that is found in many typical images to be rendered. That is, the texture coordinate from pixel to pixel does not usually change rapidly, and accordingly, the number of times that the loops 110 to 114 and 120 to 124 in FIG. 5 have to be performed is usually very small. Indeed, the maximum loop count for the U variable is equal to the number of texels in the U direction of the texture image while the maximum loop count for the V value is equal to the number of texels in the V direction. Accordingly, the invention provides particular advantages for texture maps that are of relatively small size, for example 128×128 texels, since the maximum loop count is then not large compared to the number of cycles required to perform the operations required in the prior art to evaluate the hyperbolic equation. 
     The skilled person will appreciate that the &#34;texture coordinates&#34; and &#34;texel values&#34; referred to above need not be limited to classic texture mapping where surface colour is modulated by the texel values, but also to other uses of the technique modulating reflectance, transparency, surface normal etc. 
     The invention is also applicable to the calculation of general parameter values across a projected surface, in addition to mapping coordinates such as U and V. For example, as described in the Blinn reference, it can also be desirable to interpolate between colour values specified at the polygon vertices, using a perspective correct (hyperbolic) interpolation function. 
     Also, the skilled person will appreciate that the pixels referred to above may be actual image output pixels as described above, but may alternatively be &#34;sub-pixels&#34; of a larger sub-pixel array, which are then filtered to provide fewer &#34;anti-aliased&#34; pixels for output. 
     It will be appreciated that these and further modifications and alterations might be made by those skilled in the art without departing from the spirit and scope of the invention.