Method and Apparatus for Approximating a Signed Value Between Two Endpoint Values in a Three-Dimensional Image Rendering Device

1. Field of the Invention

The present invention relates to the field of computer controlled display systems, in particular, interpolation for use in rendering pixels for displaying 3-dimensional graphical images.

2. Description of the Related Art

As the processing capability of computer systems has grown, so have the ways of displaying data generated by the computer systems. Many vocations now use computer systems as a fundamental tool. For example, in the area of architectural design, 3-Dimensional graphical images (or 3-D images) of buildings or other structures are dynamically created and manipulated by a user. A computer system is able to capture and process data in order to display the 3-D image, in a time that is much faster than could be done manually. As computer hardware technology has advanced, so has the development of various methods, techniques and special purpose devices for rapidly displaying and manipulating 3-D images. An exemplary 3-D rendering system is described in co-pending application Ser. No. 07/811,570 now U.S. Pat. No. 5,345,541, entitled "Method and Apparatus For Simultaneously Rendering Multiple Scanlines", which is assigned to the assignee of the present application.

A 3-D image is represented in a computer system as a collection of graphical objects, e.g. polygons. Each of these polygons is spatially defined as a set of points. Associated with each point are pixel shading values. Identification of other points within the polygon is typically done by linear interpolation of the given set of points.

Performing the linear interpolation calculations for each point is very compute intensive. To minimize computation the rendering is typically done using a forward differencing calculation. Consider the case of interpolating to find pixel shading values across a row or span of an object. In forward differencing, a constant, say .DELTA.p is determined that is between each horizontal coordinate (e.g. using the formula .DELTA.p=P1-P0/Y1-Y0, where P1 and P0 are pixel shading values at endpoints Y1 and Y0 of an edge). Thus, when calculating pixel shading values across a row, the next pixel shading value may be determined by simply adding .DELTA.p to the previous pixel shading value.

The forward differencing technique i premised on the idea that it is desirable to minimize the number of complications that need to be performed. The tradeoff is that a larger amount of data must be moved and stored within the system (e.g. the pixel shading values for prior pixels and the corresponding interpolation constant for each pixel shading component)

With the maturation of semiconductor technology, the cost of circuitry to perform such division operations has decreased while the speed has increased. Thus, it has become viable to design system that utilize processing power and minimize memory requirements. This is especially desirable in the design of integrated circuits where memory can take p a sizable amount of valuable space. Thus, it would be desirable to provide a method and means where these linear interpolations may be directly performed in an efficient manner.

Direct linear interpolation (LIRP) is accomplished by performing the function:

The values A and B are the extreme/endpoint values. The value w is an interpolation weighting value in the range 0.ltoreq.w.ltoreq.1. The weighting value w specifies a linear "blend" of the values A and B. For generation of acceptable graphical images, the result of this expression must be A if w is zero and must be B if w is one. A level of error is acceptable between A and B when w is a positive fraction less than one.

It is important when performing this calculation that the result has the correct sign. One way for assuring that the result has the correct signs is to sign extend the hardware circuitry performing the calculation. Sign extension requires that each adder, multiplier; multiplexer, etc. be extended in high bits by replicating the sign to align with the sign bit of the result. Extended width operands, are wasteful in many instances. Thus it is desirable to provide an efficient and fast method and means for directing calculating the signed LIRP function without sign extension.

A method and apparatus for providing a correctly signed result of a Linear Interpolation (LIRP) function in a computer controlled display system, is disclosed. The method eliminates the need to sign extend any intermediate results when generating the interpolated result. Generally, the method requires the steps of: converting the endpoint value from decimal format to two's complement binary form; causing each end Joint value to be positive by adding a predetermined bias; performing the interpolation function to generate an interpolation bias; subtracting the bias from the interpolation result; converting the interpolation result from the two's complement form into the decimal format.

The bias that is added and subtracted is equal 2.sup.n-1, where n is the number of bits in the numeric format being used. Aiding and subtracting the bias is accomplished by simply inverting the high order (sign) bit of the respective values.

FIG. 1 illustrates a computer system as may be utilized by the preferred embodiment of the present invention.

FIG. 2 is a flowchart which outlines the steps for rendering a scene in the currently preferred embodiment of the present invention.

FIG. 3a is a schematic representation of a circuit for calculating an unsigned linear interpolation value as may be utilized by the preferred embodiment of the present invention.

FIG. 3b illustrates the bit positions of a weighting value w.

FIG. 4 is a flowchart which describes the steps for performing the signed linear interpolation of the currently preferred embodiment of the present invention.

FIG. 5 is a block diagram of the circuit of FIG. 3a modified to perform the signed linear interpolation of the currently preferred embodiment of the present invention.

A method and apparatus for performing a signed linear interpolation (LIRP) function in a computer controlled display system is described. In the following description, numerous specific details are set forth such as the rendering techniques implemented in order to provide a thorough understanding of the present invention. It will be apparent, however, to one skilled in the art that the present invention may be practiced without these specific details. In other instances, well-known circuits, control logic and coding techniques have not been shown in detail in order not to unnecessarily obscure the present invention.

The computer system of the preferred embodiment is described with reference to FIG. 1. The present invention may be implemented on a general purpose microcomputer, such as one of the members of the Apple.RTM. Macintosh.RTM. family, an IBM compatible Personal Computer, or one of several work-station or graphics computer devices which are presently commercially available. In any event, a computer system as may be utilized by the preferred embodiment generally comprises a bus or other communication means 101 for communicating information, a processing means 102 coupled with said bus 101 for processing information, a random access memory (RAM) or other storage device 103 (commonly referred to as a main memory) coupled with said bus 101 for storing information and instructions for said processor 102, a read only memory (ROM) or other static storage device 104 coupled with said bus 101 for storing static information and instructions for said processor 102, a data storage device 105, such as a magnetic disk and disk drive, coupled with said bus 101 for storing information and instructions, an alphanumeric input device 106 including alphanumeric and other keys coupled to said bus 101 for communicating information and command selections to said processor 102, a cursor control device 107, such as a mouse, track-ball, cursor control keys, etc., coupled to said bus 101 for communicating information and command selections to said processor 102 and for controlling cursor movement. Additionally, it is useful if the system includes a hardcopy device 108, such as a printer, for providing permanent copies of information. The hardcopy device 108 is coupled with the processor 102 through bus 101.

Also coupled to the computer system of the preferred embodiment is a frame buffer 109 which is further coupled to a display device 110. The display device is preferably capable of displaying color graphics images or high resolution monochrome images. The frame buffer 109 contains the pixel data for driving the display device 110. The display device 110 would be further coupled to a rendering device 111, also known as a graphics accelerator. Typically, such a rendering device 111 is coupled to the bus 101 for communication with the processor 102 and frame buffer 109. The preferred embodiment is implemented for use on a Macintosh computer available from Apple Computer, Inc. of Cupertino, Calif.

The linear interpolation circuit of the of the currently preferred embodiment of the present invention is implemented within the rendering device 111.

The preferred embodiment of the present invention utilizes a scanline approach to rendering. From a computer stem design standpoint, the principle advantages in utilizing a scanline approach are the reduction of bandwidth between the graphics accelerator and the host/frame buffer, reduced requirements for low latency communication between the graphics accelerator and the host/frame buffer, and increased coherence of the data transferred from the graphics accelerator and the host/frame buffer. Moreover, for a given desired performance of the combined computer system and graphics accelerator, these advantages reduce both the cost of the computer system without the graphics accelerator and the cost of the graphics accelerator itself.

The scanline rendering technique performed in the currently preferred embodiment is illustrated in the steps of the flowchart of FIG. 2. Referring to FIG. 2, the objects (triangles or quadrilaterals) representing the image to be generated are first sorted so as to identify the scanline on which an object first becomes active (i.e. displayed), step 201. The result of this sorting is a database that is termed the Object Activation List. As the scanlines are being rendered, the Object Activation List is queried to determine if any new objects appear on a scanline that is about to be rendered.

Once the Object Activation List is created rendering of the scanlines may begin. The first step is to generate an Active Object List for the scanline to be rendered, step 202. The Active Object List identifies the objects which are "active" or lie on the scanline(s) that is about to be rendered. Creation and maintenance of the Active Object List occurs by examining the Object Activation List for new objects to be added and eliminating objects that have been completely rendered. Determining tile objects that have been completely rendered is a simple matter of identifying objects with a bottom coordinate point that is "above" the scanline being rendered (as scanlines are rendered from top to bottom.

For each active object, a span of pixels on the horizontal coordinates of scanline being rendered must be identified, step 203. This process is termed vertical interpolation. In vertical interpolation, the horizontal coordinates of intersection points of two edges of the object with the scanlines being rendered are identified. The two intersection points define the endpoints for the span. Note that not only the spatial values need to be determined, but the pixel shading values associated with the intersections points must be calculated. In both instances, this is done by some type of interpolation (e.g. linear interpolation).

For each active object, the pixel shadings of the span of the object on the scanline being rendered are determined step 204. Again, this is done by interpolating for each point (pixel) on the span given the two extreme endpoints. This is termed horizontal interpolation. During this step, such things as Z-buffering, ambient shading, lighting and other effects may be performed to determine the ultimate pixel shading. After each of the objects has been rendered and other pixel shading functions performed, e.g. texture mapping, the rendered scanline is transferred to a system frame buffer, step 205.

Finally, a check to determine if the last scanline has been rendered, step 206. If the last scanline has not been rendered, the method continues at step 202 for the next scanline. Otherwise, the rendering of the image has been completed.

It should be noted that the foregoing description is not meant to limit the implementations in which the present invention may be utilized. For example, it would be apparent to one skilled in the art to use the present invention in graphical systems that do not do use the scanline method of rendering. Such implementations would not depart from the spirit and scope of the present invention.

From the foregoing description, it is clear that a LIRP function is performed continually through the rendering process. A technique for performing the LIRP function is described in co-pending application Ser. No. 07/811,829 now U.S. Pat. No. 5,345,541 entitled "Method and Apparatus For Approximating A Value Between Two Endpoint Values In A Three Dimensional Image Rendering Device", which is assigned to the assignee of the present invention. In the technique described, numerous intermediate results are generated. It is critical when performing these intermediate calculations that the result has the correct sign.

The equation for direct LIRP function is defined as:

The LIRP function requires a weighting value w. The weighting value w is a value between 0 and 1 that specifies a linear "blend" of the values A and B. The weighting value w can be unique for each interpolated value being calculated. Generally w will have a relationship between the end points A and B and the position of the point being interpolated relative to A and B. The result of this expression is A if w is zero, B if w is one, and a value between A and B when w is a positive fraction less than one.

The LIRP operates in fixed precision arithmetic. Implementing the LIRP operation in fixed precision arithmetic can be wasteful. If w is defined as a binary fraction between zero and one inclusive almost an entire bit of resolution is wasted. In the case where w has 4 bits, 7 encodable values between 1.001 and 1.111 will always be unused.

A more efficient approach to encoding w defines 0.1111 to be one and 0.0000 to be zero. All 16 encodable values where w has 4 bits are now useful. The LIRP equation now becomes:

If w=0.0000, the LIRP value will be 0.1111A. If w=0.1111, the LIRP value will be 0.1111B. However, in graphics applications it is known that in order to achieve high quality rendering, if w=0 or 0.0000, the LIRP value must be A and if w=1 or 0.1111, the LIRP value must be B. This is to achieve complete color saturation at the end points. A rounding factor is therefore added to the LIRP value to achieve saturation at both A and B. 0.0001 A is added if w<0.1000. 0.0001B is added if w>=0.1000. These rounding factors force saturation at both ends of the range of w, while tolerating some discrepancies to true linearity at some midpoints.

With the addition of this rounding factor, w no longer partitions the range between A and B quite uniformly. The partition between the LIRP values when w=0.0111 and when w=0.1000 can be up to twice as large as the partition between any other two neighboring values of w. The size of this partition is, however, no larger than the size of every partition when w is encoded in the standard way described above.

In describing a circuit to perform the LIRP equation, the fixed point version of the LIRP equation above is re-written using two's complement math as follows:

Replacing w with it's two's complement equivalent (!w is the bit inverse of w):

and rearranging terms:

The first term drops out in two's complement form, leaving only:

Not incidentally, this approach leads to a very regular (and thus compact and efficient) custom silicon layout. Converting to one bit multiplication's by summing for i=0 to n, where n is the number of bits-1 in w (4 for this example) and w.sub.n is the most significant bit of w gives:

This equation can be efficiently computed by using a selector for each bit w.sub.i to select between adding A or B (shifted appropriately by 2.sup.i-n).

Adding in the appropriate rounding factor to force saturation gives:

Adding the rounding factors to the circuit described above is simply done by adding one new selector at the least significant bit position.

Referring now to FIG. 3a, a circuit for linear interpolation is illustrated. The LIRP circuit is comprised essentially of 2 to 1 multiplexors, carry sum adders, and a 10 bit carry propagate adder. The LIRP circuit implements the logic described above where the bits of the Weighting Value w are used to select the output of the 2 to 1 multiplexors. The outputs of the multiplexors are added and the bit patterns are shifted appropriately to reflect the magnitude of the operands. As the circuit is somewhat repetitive, a description of a portion of the circuit will suffice.

A first input A 301 is provided as a first input to the multiplexer 303 and a second input B 302 is a second input to the multiplexer 303. The values of input A 301 and B 302 would typically be a pair of pixel shading values at some endpoint locations. A third input, i.e. a selector value, is the value which will determine whether the first input or the second input will be output from the multiplexer 303. The selector value to be provided to the multiplexor is a bit from the weighting value. For the multiplexor 303, the selection value is provided by the most significant bit of the Weighting Value w, in this case W9 331. This value is the additive saturation value needed in order to achieve full saturation at the extreme ends. In any event, it should be noted that if the selection value is a 1, the first input is output from the multiplexer, i.e. the bit pattern from B 302. If the selection value is 0 the second input is output from the multiplexer, i.e. the bit pattern from A 301.

The bit layout of the weighting value w is illustrated in FIG. 3b. As is typical in computer representations, e.g., binary representations, of numeric values, the least significant digit values are in the right most storage position. So for example, a digit W0 332 will be the least significant digit and a digit W1 333 is the second least significant digit. This continues from right to left storage locations unit W9 350, which is the most significant digit. Further illustrated in FIG. 3b are the digits of W coupled to corresponding multiplexors as described with respect to FIG. 3a.

Referring back to FIG. 3a, the output of the multiplexor 303 is coupled to a carry-in input 306 of carry-sum adder 305. It is also clear from FIG. 3a that the values A 301 and B 302 will be used as input to all the multiplexer devices.

A second multiplexer 304 also takes as input A 301 and B 302. The multiplexer 304 receives as input the least significant bit of the Weighting Value, in this case W0 332. The output of the multiplexor 304 is coupled to an operand input 306a of the carry-sum adder 305. An Unused input of carry-sum adder 305 is forced to zero (0). Alternatively, a carry-sum half adder could be utilized which has 2 inputs instead of 3.

The carry-sum adder 305 provides for the addition of the saturation value and of the lowest order set of bits in the multiplication (i.e. linear interpolation operation) it is performing. A carry out output 307 and a sum output 308 of the carry-saver adder 305 are coupled to an operand input A 312 and an operand input B 313, respectively, of carry-sum adder 314.

The multiplexor 309 takes as selector input the second least significant bit of the Weighting Value, in this case W1 333. The output of the multiplexor 309 is also an input to the carry-save adder 314.

The additive values cascade down the combination of multiplexors and carry-sum adder devices until multiplexer 317/carry-sum adder 318 are reached. In multiplexer 317, the input is the most significant bit of the weighting value, in this case W9 334. Again, input values A 301 and B 302 are inputs to the multiplexor 317.

The output of the multiplexor 317 is coupled to a carry-in input 319 of carry-sum adder 318. In accordance with the description of the circuit above, operand inputs A 320 and operand input B 321 of carry-sum adder 318 are coupled to the carry-out output and sum output, respectively, of a previous carry-sum adder (not illustrated). The carry-out output 323 and sum 324 of carry-sum adder 318 are coupled to an operand input B 326 and operand input A 325, respectively, of carry-propagate adder 322. The sum output 329 of the carry-propagate adder 322 will be the approximated linearly interpolated value.

As noted above with respect to the prior art, one technique for insuring a correct sign for a signed interpolated function, is to sign extend the devices used in carrying out the function. It is useful to discuss the effect of sign extension on the circuit of FIG. 3a. With respect to the Adders, if the result is M bits wide M is equal to (the number of bits in W)+the larger of {(number of bits in A}, number of bits in B)}. For the multiplexor, each multiplexor output is extended using the formula: m-n-(w-bit), where m is the width of the result, n is the width of the input, w-bit is the bit number f multiplexor selection. An exception is the w-bit value which should be zero (.phi.) for the rounding selection multiplexor. Referring to FIG. 3a, assuming n=10 and m=20, this would cause the output of multiplexors 303 and 304 to be.sub.i extended by 10 bits, the output of multiplexor 309 to be extended by 9 bits and the output of multiplexor 317 to be extended by 1 bit.

As is apparent, sign extension requires a larger and slower hardware implementation. In order to perform the signed LIRP function without sign extension, a bias is added to two's compliment representations of A and B and subsequently the bias is subtracted from the final result. Adding the bias has the effect of causing all calculations to be on positive numbers (i.e. an unsigned calculation). In this instance A is represented by a two's complement format binary number -2.sup.n <A<2.sup.n and B is represented by a two's complement format binary number -2.sup.n <B<2.sup.n. The bias is 2.sup.n-1. In two's complement format 0.times.200 200 through 0.times.3 ff represent the negative values: -2.sup.n-1 through -1. Likewise, in two's complement format 0.times.1 through 0.times.1 ff represent the positive values: 1 through 2.sup.n-1 -1. When the bias is added, the positive values become 0 through 2.sup.n -1 . Since all the inputs are positive, it is not necessary to sign extend the intermediate sums. Adding the bias is equivalent to simply inverting the high order (sign) bit. Subtracting the bias from the result is equivalent to simply inverting the high order (sign) bit. Thus, by simply adding three inverters to the circuit of FIG. 3a, signed LIRPS can be achieved.

It should be noted that adding and subtracting the bias has no effect on the final end result of the linear interpolation function. Assume a bias d is added to each of the operands:

So when the bias d is subtracted from the result we end up with the original interpolation function P=(1-w)P0+wP1.

The method for rendering a scanline is outlined in the steps of the flowchart of FIG. 4. Referring to FIG. 4, the endpoints values A and B, as well as the interpolation weights value W must be converted from decimal to a two's complement binary format, step 401. Note that this step may not be needed if the endpoint values A and B and interpolation weights value W are maintained in two's complement form. In any event, once the values are in the proper binary format, the necessary bias to make A and B positive values is added to A and B, step 402. This is done by inverting the high order (sign) bit of both A and B.

Next, the interpolation function is performed and an interpolation result obtained, step 403. Preferably, the interpolation function is performed utilizing the circuitry and technique described with reference to FIG. 3a. However, other circuitry or other techniques may be utilized without causing departure from the spirit and scope of the present invention. In any event, the bias is then subtracted from the interpolation result, step 404. This is accomplished by simply inverting the high order (sign) bit of the interpolation result. Conceptually this is true because we are merely performing the same function twice to get back to the same place, e.g. invert zero to get one and then invert one to get zero. Finally, the result in two's complement form is then converted back to it's decimal equivalent, step 405.

What follows is an example of performing the linear interpolation function in both decimal and binary. Consider an example where A=-6, B=6 and w=1/4. In decimal the interpolation function would be performed as follows: ##EQU1## The binary equivalent would be as follows: A=11111010 (2's complement form of -6)

B=000000110

w=0.01 (binary equivalent of 1/4)

1-w=0.11 (binary equivalent of 3/4)

when inverting the sign bit of A and B, the result is A=01111010 and B=10000110. Performing the calculations in binary: ##EQU2## Adding the two results yields: ##EQU3## When the high order bit is inverted, the result is 11111101, which is the 2's complement representation of the decimal number -3 (the expected result).

FIG. 5 illustrates in block diagram form, a circuit for carrying out the signed linear interpolation function of the present invention. The circuit adds inverters 501-503 to the circuitry illustrated in FIG. 3a. The input A 301 is coupled to the inverter 501, the input B 302 is coupled to the inverter B 302 and the sum 329 is coupled to the inverter 503. Each of the inverters 501, 502 and 503 will merely invert the high order sign bit of the respective inputs. Although not illustrated in FIG. 5, a means for converting the decimal values into two's complement form would be included. Such a means may be implemented by the software generating the signals.

While the currently preferred embodiment is utilized in a computer controlled display system, it would be apparent to one skilled in the art to utilize the present invention in other embodiments which perform a LIRP function.

Thus, a method and apparatus for performing signed linear interpolations is disclosed.