Patent Abstract:
The texture coordinates (u,v) of a point Q&#39; are determined by: (1) determining the modified texture coordinates (u&#39;,v&#39;)=(u/z,v/z) by linear interpolation, where z is a world coordinate; (2) determining 1/z by linear interpolation; and (3) dividing (u&#39;,v&#39;) by 1/z. The division is replaced with multiplying (u&#39;,v&#39;) by the inverse of 1/z. The inverse is obtained using a lookup table (LUT). The LUT stores inverses of a few values. Linear interpolation is applied to the LUT output to increase the inverse value accuracy.

Full Description:
BACKGROUND OF THE INVENTION 
     The present invention relates to computers, and more particularly to determining texture coordinates in compute graphics. 
     Textures are used in computer graphics to make computer-generated images appear more realistic. A texture consists of a number of texture elements (&#34;texels&#34;). Each texel has a value corresponding to color, intensity, or some other image parameter. Texel values are used to modify the color, intensity, or other parameters of corresponding pixels in the computer image. See, for example, M. Segal et al., &#34;Fast Shadows and Lighting Effects Using Texture Mapping&#34;, Computer Graphics, 26, 2, July 1992, pages 249-252, incorporated herein by reference. 
     In the computer, texels are identified by texture coordinates. Thus, finding a proper texel for a pixel involves determining the texel&#39;s texture coordinates. It is desirable to provide small and inexpensive circuits for determining the texture coordinates. 
     SUMMARY 
     The present invention provides circuits and methods for determining texture coordinates. In some embodiments, the circuits are small and inexpensive. 
     In some embodiments, besides the texture coordinates, a computer system uses world coordinates and screen coordinates. The world coordinates (x,y,z) are used to represent objects whose images are to be displayed on a computer screen. The screen coordinates (x&#39;,y&#39;) identify pixels on the screen. The world and screen coordinates are chosen so that a point having world coordinates (x,y,z) will be represented on the screen as a point with screen coordinates x&#39;=x/z, y&#39;=y/z. 
     The object surface to be represented on the screen is divided into polygons whose vertices have known world and texture coordinates. The screen coordinates (x&#39;,y&#39;) of the vertex images are set to (x/z, y/z) as described above. Then straight-line segments are drawn that interconnect the vertex images. Then individual points on different segments are connected by other straight-line segments to fill the polygons. See, for example, P. Burger and D. Gillies, &#34;Interactive Computer Graphics&#34; (1989), pages 76-110 incorporated herein by reference; J. D. Foley et al., &#34;Computer Graphics: Principles and Practice&#34; (1996), pages 72-104 incorporated herein by reference. 
     For each image point Q&#39; having (possibly unknown) texture coordinates (u,v), let us introduce modified texture coordinates (u&#39;,v&#39;): u&#39;=u/z, v&#39;=v/z, where z is the world coordinate of a point Q whose image is Q&#39;. The images of the vertices have known texture coordinates (u,v), and therefore their modified texture coordinates (u&#39;,v&#39;) can be determined. Suppose a point Q&#39; having screen coordinates (x&#39;,y&#39;) lies in a segment with end points Q 1  &#39;, Q 2  &#39;. Suppose the point Q 1  &#39; has screen coordinates (x 1  &#39;,y 1  &#39;) and modified texture coordinates (u 1  &#39;,v 1  &#39;), and the point Q 2  &#39; has screen coordinates (x 2  &#39;,y 2  &#39;) and modified texture coordinates (u 2  &#39;,v 2  &#39;). Then we find the modified texture coordinates (u&#39;,v&#39;) of Q&#39; by linear interpolation: 
     
         (u&#39;,v&#39;)=(1-t)(u.sub.1 &#39;,v.sub.1 &#39;)+t(u.sub.2 &#39;,v.sub.2 &#39;) 
    
     where t is such that 
     
         (x&#39;,y&#39;)=(1-t)(x.sub.1 &#39;,y.sub.1 &#39;)+t(x.sub.2 &#39;,y.sub.2 &#39;) 
    
     We find the texture coordinates of Q&#39; by dividing (u&#39;,v&#39;) by 1/z where z is the world coordinate of a point Q whose image is Q&#39;. 1/z is determined by linear interpolation. 
     In some embodiments, the division by 1/z is implemented as a multiplication by the inverse of 1/z (that is, multiplication by z (which may be unknown)). To speed up determining the inverse of 1/z, a lookup table is provided that stores the inverses of some values. To make the texture coordinates circuit smaller and less expensive, the lookup table is made small. Thus, the lookup table contains fairly few inverse values (32 inverse values in some embodiments). To improve accuracy, the inverse values not contained in the lookup table are determined by linear interpolation. 
     Once the texture coordinates are determined, the texel values are applied to the pixel to improve the image quality. 
     Other features and advantages of the invention are described below. The invention is defined by the appended claims. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     FIGS. 1 and 2 illustrate an object and its image on a screen. 
     FIG. 3 is a block diagram of a circuit generating texture coordinates for the images of FIGS. 1 and 2. 
     FIG. 4 is a detailed block diagram of a portion of the circuit of FIG. 3. 
     FIG. 5 illustrates bit processing by a circuit which is a portion of the circuit of FIG. 4. 
    
    
     DESCRIPTION OF PREFERRED EMBODIMENTS 
     FIGS. 1 and 2 illustrate displaying an object on a computer screen 110. The viewpoint is shown at O. The object is to be displayed so that it would appear to the viewer to be at a position 120. The image on screen 110 is a perspective projection of the object (or part of the object) onto the screen 110 with the center of projection being at the viewpoint O. 
     The object includes a straight-line segment with end points Q 1 , Q 2 . The point Q 1  is to be displayed at point Q 1  &#39; of screen 110. The point Q 2  is to be displayed at point Q 2  &#39; of the screen. The segment interconnecting the points Q 1 , Q 2  is to be displayed as a segment interconnecting the points Q 1  &#39;, Q 2  &#39;. 
     Object 120 is to be displayed with a texture. Points Q 1 , Q 2  have known texture coordinates (u 1 ,v 1 ) and (u 2 ,v 2 ) respectively. Clearly, Q 1  &#39; and Q 2  &#39; have the same texture coordinates as Q 1  and Q 2  respectively. For any other point Q&#39; in the segment Q 1  &#39;Q 2  &#39;, texture coordinates (u,v) are determined as described below. 
     The world coordinate system is chosen to be a Cartesian system xyz having the origin at the viewpoint O. The x and y axes are parallel to screen 110. The z axis is perpendicular to the screen. Screen 110 is located in the plane z=1. The screen has a Cartesian screen coordinate system x&#39;y&#39; with the origin at the intersection O&#39; of the screen with the z axis. It can be shown that for any point Q on object 120, if the point Q has world coordinates (x,y,z) then the image of the point Q has screen coordinates x&#39;=x/z, y&#39;=y/z. 
     Denote the world coordinates of points Q 1  and Q 2  by (x 1 ,y 1 ,z 1 ) and (x 2 ,y 2 ,z 2 ) respectively. Then the point Q 1  &#39; has screen coordinates (x 1  &#39;,y 1  &#39;)=(x 1  /z 1 ,y 1  /z 1 ) and the point Q 2  &#39; has screen coordinates (x 2  &#39;,y 2  &#39;)=(x 2  /z 2 ,y 2  /z 2 ). 
     The screen coordinates of the pixels in the image Q 1  &#39;Q 2  &#39; are determined using known scan conversion techniques. Some scan conversion techniques are described in J. D. Foley et al., &#34;Computer Graphics: Principles and Practice&#34; (1996), pages 72-81 incorporated herein by reference. Given the screen coordinates (x&#39;,y&#39;) of the pixel Q&#39;, the texture coordinates (u,v) of Q&#39; are generated by the circuitry of FIG. 3 as follows. 
     Circuit 310 receives the screen coordinates x&#39;,y&#39;,x 1  &#39;,y 1  &#39;,x 2  &#39;,y 2  &#39;, and generates a line parameter t such that: 
     
         (x&#39;,y&#39;)=(1-t)(x.sub.1 &#39;,y.sub.1 &#39;)+t(x.sub.2 &#39;,y.sub.2 &#39;)  (1) 
    
     The equality (1) may be only approximate because, among other things, the pixels in the segment Q 1  &#39;Q 2  &#39; are a discrete approximation of a straight-line segment. In some embodiments, t is generated as in the following pseudocode: 
     If x 1  &#39;≠x 2  &#39;, then t=(x&#39;-x 1  &#39;)/(x 2  &#39;-x 1  &#39;) else t=(y&#39;-y 1  &#39;)/(y 2  &#39;-y 1  &#39;) 
     Circuit 310 also generates the signal 1-t. 
     Circuit 320 receives t, 1-t and also receives the following signals: 
     u 1  &#39;=u 1  /z 1 , 
     v 1  &#39;=v 2  /z 1 , 
     u 2  &#39;=u 2  /z 2 , 
     u 2  &#39;=v 2  /z 2 . 
     Circuit 320 generates modified texture coordinates u&#39;,v&#39; as follows: 
     
         (u&#39;,v&#39;)=(1-t)(u.sub.1 &#39;,v.sub.1 &#39;)+t(u.sub.2 &#39;,v.sub.2 &#39;)  (2) 
    
     Circuit 330 receives the signals t, 1-t, 1/z 1 , 1/z 2  and generates a signal w&#39; as follows: 
     
         w&#39;=(1-t)(1/z.sub.1)+t(1/z.sub.2).                          (3) 
    
     Circuit 340 receives u&#39;, v&#39; and w&#39; and generates the texture coordinates (u,v) using the formulas: 
     
         u=u&#39;/w&#39;, 
    
     
         v=v&#39;/w&#39;.                                                   (4) 
    
     FIG. 4 is a detailed block diagram of circuit 340. To speed up the division by w&#39;, circuit 340 uses a lookup table (LUT) 410 to store the values 1/w&#39;. To reduce the circuit cost and area, LUT 410 is made fairly small. In some embodiments, LUT 410 includes only 32 entries 1/w i . To determine 1/w more accurately, circuit 340 performs linear interpolation thus at least partially compensating for the small size of LUT 410. 
     LUT 410 stores the values of 1/w only for w in a predetermined interval, for example, in the interval  0.5, 1!. Normalize logic 420 normalizes the signal w&#39; to produce a value in that interval, as described below. 
     LUT 410 stores thirty-two 19-bit entries. The input to LUT 410 is a 5-bit integer index i=0, 1, 2, . . . 31. In response to the index i, LUT 410 produces a 19-bit signal 1/w i  where w i  is in the interval  0.5, 1!. In some embodiments, the interval  0.5, 1! is divided into 32 equal parts, and the values w i  are the end points of these parts. More particularly: 
     
         w.sub.i =(32+i)/64                                         (5) 
    
     LUT 410 stores the values LUT(i)=1/w i  =64/(32+i). Each of these values is represented in a fixed point form in 19 bits. In some embodiments, LUT 410 stores the integer values LUT(i)=64/(32+i)*(2 19  -1). These values give better accuracy in the linear interpolation of 1/w&#39;. LUT 410 for this embodiment is described in Appendix A below in the hardware description language Verilog®. Verilog® is described, for example, in D. E. Thomas, J. P. Moorby, &#34;The Verilog® Hardware Description Language&#34; (1991) hereby incorporated herein by reference. LUT 410 of Appendix A is implemented by combinational logic. 
     Operation of normalize logic 420 is illustrated in FIG. 5. Values w&#39; are represented in 24 bits in a fixed point form. The binary point is presumed to be before the most significant bit 23. Normalize logic 420 determines the position of the most significant &#34;1&#34; in w&#39;. The normalization operation is a left shift of w&#39; so that the most significant &#34;1&#34; gets into the most significant bit position 23 Normalizer 420 determines the number k of the most significant zeros in w&#39;. This number k is provided to barrel shifter 430 (FIG. 4) to perform denormalization at the output of circuit 340. In FIG. 5, k=4 since the most significant &#34;1&#34; is in bit position 19. 
     The five bits following the most significant &#34;1&#34; (bits w&#39; 18:14! in the example of FIG. 5) form the index i provided to LUT 410. The remaining less significant bits of w&#39; (bits w&#39; 13:0! in the example of FIG. 5) form the most significant bits of 18-bit signal Δ provided to multiplier 440 to perform linear interpolation. The remaining k bits of Δ are set to 0. 
     Let w n  denote the normalized w&#39;, i.e. w n  is w&#39; shifted left by k bits. Thus, w n  is in the interval  0.5, 1!. w n  =w i  +Δ r , where: 
     i is the index provided by normalize logic 420, and w i  is defined by equation (5) above, and 
     Δ r  =0.000000Δ. 
     Using linear interpolation, we obtain: 
     
         1/w.sub.n =1/w.sub.i +Δr(1/w.sub.i -1/w.sub.i+1)/(w.sub.i -w.sub.i+1)(6) 
    
     where w i+1  =1 for i=31. 
     Equation (6) implies: 
     
         1/w.sub.n =1/w.sub.i -Δ.sub.r /(w.sub.i w.sub.i+1)   (7) 
    
     LUT 450 stores the values 1/(w i  w i+1 ) for each i. LUT 450 receives the index i from normalize logic 420. In some embodiments, LUT 450 is a combinational circuit. The LUT 450 output 1/(w i  w i+1 ) is provided to multiplier 440. Multiplier 440 also receives the signal Δ as described above. Multiplier 440 generates the signal Δ r  /(w i  w i+1 ). This signal is provided to subtractor 454. Subtractor 454 also receives the 19-bit signal 1/w i  from LUT 410. Subtractor 454 performs the subtraction of the equation (7) and thus generates the signal 1/w n . This signal is provided to multipliers 460, 464. Multiplier 460 receives u&#39; and generates u&#39;*(1/w n ). Multiplier 464 receives v&#39; and generates v&#39;*(1/w n ) The outputs of the two multipliers are connected to barrel shifter 430. Shifter 430 shifts u&#39;*(1/w n ) and v&#39;*(1/w n ) left by k bits and thus generates the respective texture coordinates u, v. 
     In some embodiments, the texture coordinates u, v are used to access the texture for a texel value. In some embodiments, the texture coordinates u, v are used to determine the &#34;MIP map&#34;, which is a possibly pre-filtered texture. Then the texel value is provided by the MIP map, or by adjacent MIP maps. See U.S. patent application &#34;Determining the Level of Detail for Texture Mapping in Computer Graphics&#34;, Ser. No. 08/749,859, filed by Sang-Gil Choi on Nov. 15, 1996 and hereby incorporated herein by reference. 
     Appendix B is a source code for a program simulating one embodiment of circuit 340. The program is written in the programming language C. 
     Since the inputs of the circuit of FIG. 3 include modified texture coordinates (u 1  &#39;,v 1  &#39;), (u 2  &#39;,v 2  &#39;) of points Q 1  &#39;, Q 2  &#39; and not the texture coordinates themselves, the texture coordinates of points Q 1  &#39;, Q 2  &#39; need not be known. For example, in some embodiments, Q 1  &#39; is a point in a segment Q 3  &#39;, Q 4  &#39;. Points Q 3  &#39;, Q 4  &#39; are vertices with known texture coordinates. The modified texture coordinates of Q 1  &#39; are determined from the modified texture coordinates of Q 3  &#39;, Q 4  &#39;, using the linear interpolation technique of equation (2) above. The value 1/z is determined from the 1/z coordinates of points Q 3 , Q 4  using the linear interpolation technique of equation (3). 
     The above embodiments illustrate but do not limit the invention. In particular, the invention is not limited by the number of bits in any particular signal or by the number of entries in any lookup table. The invention is defined by the appended claims. 
     
         ______________________________________APPENDIX A______________________________________/****************************************************\// This is VerilogHDL code file for//Look up table part of integer divider.\****************************************************//* PAL for division */module pla.sub.-- lut (index, out); parameter DELAY = 1;            // Delay time input  4:0! index; output   18:0! out; reg  18:0! out; always @(index) begincase(index)     // synopsys parallel.sub.-- case    5&#39;b00000 : # DELAY out = 19&#39;h7ffff;    5&#39;b00001 : # DELAY out = 19&#39;h7c1f0;    5&#39;b00010 : # DELAY out = 19&#39;h78787;    5&#39;b00011 : # DELAY out = 19&#39;h75075;    5&#39;b00100 : # DELAY out = 19&#39;h71c71;    5&#39;b00101 : # DELAY out = 19&#39;h6eb3e;    5&#39;b00110 : # DELAY out = 19&#39;h6bca1;    5&#39;b00111 : # DELAY out = 19&#39;h69069;    5&#39;b01000 : # DELAY out = 19&#39;h66666;    5&#39;b01001 : # DELAY out = 19&#39;h63e70;    5&#39;b01010 : # DELAY out = 19&#39;h61861;    5&#39;b01011 : # DELAY out = 19&#39;h5f417;    5&#39;b01100 : # DELAY out = 19&#39;h5d174;    5&#39;b01101 : # DELAY out = 19&#39;h5b05b;    5&#39;b01110 : # DELAY out = 19&#39;h590b2;    5&#39;b01111 : # DELAY out = 19&#39;h57262;    5&#39;b10000 : # DELAY out = 19&#39;h55555;    5&#39;b10001 : # DELAY out = 19&#39;h53978;    5&#39;b10010 : # DELAY out = 19&#39;h51eb8;    5&#39;b10011 : # DELAY out = 19&#39;h50505;    5&#39;b10100 : # DELAY out = 19&#39;h4ec4e;    5&#39;b10101 : # DELAY out = 19&#39;h4d487;    5&#39;b10110 : # DELAY out = 19&#39;h4bda1;    5&#39;b10111 : # DELAY out = 19&#39;h4a790;    5&#39;b11000 : # DELAY out = 19&#39;h49249;    5&#39;b11001 : # DELAY out = 19&#39;h47dc1;    5&#39;b11010 : # DELAY out = 19&#39;h469ee;    5&#39;b11011 : # DELAY out = 19&#39;h456c7;    5&#39;b11100 : # DELAY out = 19&#39;h44444;    5&#39;b11101 : # DELAY out = 19&#39;h4325c;    5&#39;b11110 : # DELAY out = 19&#39;h42108;    5&#39;b11111 : # DELAY out = 19&#39;h41041;endcase endendmodule______________________________________APPENDIX B______________________________________/***************************************************// This is C code file// for divider of integer. (32 entry)*****************************************************/int LUT 33!;int global.sub.-- fixed;main()void Down.sub.-- load.sub.-- lut();int Interpolate.sub.-- lut();float a, data;int i;int nbitsx;int result.sub.-- div;int fixed.sub.-- data;float result.sub.-- data;int startx, endx;float float.sub.-- fixed.sub.-- data;long long ll.sub.-- result.sub.-- div;Down.sub.-- load.sub.-- lut(); /* Compose of Look-Up Table *//* Find the number of bits effective */for(i=64; i&lt;65535; i++){fixed.sub.-- data = (int) (16777215.0 / i);nbitsx = Find.sub.-- nbitsx(fixed.sub.-- data);result.sub.-- div = Interpolate.sub.-- lut(nbitsx,global.sub.-- fixed);ll.sub.-- result.sub.-- div = (long long)result.sub.-- div * (longlong)fixed.sub.-- data;ll.sub.-- result.sub.-- div &gt;&gt;= nbitsx;result.sub.-- div = (int)ll.sub.-- result.sub.-- div;float.sub.-- fixed.sub.-- data = (-16777215.0 + result.sub.-- div) /16777215.0;printf(&#34;Input %d :: Relative Err is %f \n&#34;, i,float.sub.-- fixed.sub.-- data);}}int Interpolate.sub.-- lut(nbitsx, global.sub.-- fixed)int nbitsx, global.sub.-- fixed;{int delta, lut1, lut2, index;unsigned int sublut12;float a;index = (global.sub.-- fixed &gt;&gt; 18) &amp; 0x1f;delta = global.sub.-- fixed &amp; 0x3ffff;lut1 = LUT index!;lut2 = LUT index + 1!;sublut12 = lut1 - lut2;sublut12 &amp;= 0x3fff;sublut12 *= delta;sublut12 &gt;&gt;= 18;lut1 -= sublut12;/**lut1 &gt;&gt;= nbitsx;**/lut1 = (int)lut1;return(lut1);}int Find.sub.-- nbitsx(fixed.sub.-- data)int fixed.sub.-- data;{int i, nbitsx;int tmp.sub.-- fixed.sub.-- data=fixed.sub.-- data;for(i=1 ; i&lt;= 24; i++){     if(tmp.sub.-- fixed.sub.-- data &amp;0x1) nbitsx =i;     tmp.sub.-- fixed.sub.-- data &gt;&gt;= 1;}global.sub.-- fixed = fixed.sub.-- data &lt;&lt; (24 - nbitsx);return (nbitsx-6);}void Down.sub.-- load.sub.-- lut(){LUT 0!      = 0x7ffff;LUT 1!      = 0x7c1f0;LUT 2!      = 0x78787;LUT 3!      = 0x75075;LUT 4!      = 0x71c71;LUT 5!      = 0x6eb3e;LUT 6!      = 0x6bca1;LUT 7!      = 0x69069;LUT 8!      = 0x66666;LUT 9!      = 0x63e70;LUT 10!     = 0x61861;LUT 11!     = 0x5f417;LUT 12!     = 0x5d174;LUT 13!     = 0x5b05b;LUT 14!     = 0x590b2;LUT 15!     = 0x57262;LUT 16!     = 0x55555;LUT 17!     = 0x53978;LUT 18!     = 0x51eb8;LUT 19!     = 0x50505;LUT 20!     = 0x4ec4e;LUT 21!     = 0x4d487;LUT 22!     = 0x4bda1;LUT 23!     = 0x4a790;LUT 24!     = 0x49249;LUT 25!     = 0x47dc1;LUT 26!     = 0x469ee;LUT 27!     = 0x456c7;LUT 28!     = 0x44444;LUT 29!     = 0x4325c;LUT 30!     = 0x42108;LUT 31!     = 0x41041;LUT 32!     = 0x40000;}______________________________________

Technology Classification (CPC): 6