Method and system for evaluating derivatives in screen space using perspective corrected barycentric coordinates

[0002] 1. Field of the Invention

[0003] The present invention relates to computer graphics technology. More specifically, the present invention relates to the evaluation of derivatives in screen space during graphics processing.

[0004] 2. Related Art

[0005] Computer systems are extensively used to perform a wide variety of useful operations in modern society. Applications of computer systems can be found in virtually all fields and disciplines, including but not limited to business, industry, scientific research, education and entertainment. For instance, computer systems are used to analyze financial data, to control industrial machinery, to model chemical molecules, to deliver classroom presentations and to generate special effects for movies. Indeed, it has now come to the point where many of these operations have become so computationally intensive that they cannot be efficiently performed without the help of modern computer systems. As part of the process of performing such operations, computer systems typically utilize some type of display device, such as a cathode ray tube (CRT), a liquid crystal display (LCD) and the like, in order to display images and data which are recognizable to their users. As such, computer systems typically incorporate functionality for generating images and data which are subsequently output to the display device.

[0006] One technique for generating computer images and viewable data within a computer system is to utilize a graphics pipeline, which uses a series of interconnected functional blocks of circuitry, or “stages”, to render an image. Each stage performs a unique task during each clock cycle. As soon as one stage has completed its task on a point (e.g., a pixel), that stage can immediately proceed to work on the next one. It does not have to wait for the processing of a prior pixel to complete before it can begin processing the current pixel. More specifically, sets of graphics primitives (e.g., triangles) are specified within the computer system and are subsequently sent down the graphics pipeline. Each stage sequentially performs a different function or functions on the received graphics primitives and then passes that data onto the following stage. Eventually, the graphics pipeline manipulates the graphics primitives in order to produce the final pixel values of an image. Thus, a graphics pipeline enables different graphics data to be processed concurrently, thereby generating graphics images at a higher rate. It should be appreciated that the functionality of a typical prior art graphics pipeline is well known by those of ordinary skill in the art.

[0007] One typical operation that is performed during graphics processing is texture mapping. Moreover, texture mapping generally involves the determination of the level of detail (LOD) at each point (e.g., a pixel) of the object (e.g., a triangle primitive) being texture mapped. In the prior art, the LOD of a given pixel is computed using various local difference techniques. In particular, one prior art implementation computes the LOD at a given pixel using differences in texture coordinates S and T of several adjacent pixels. For example, a typical prior art LOD computation uses four adjacent pixels (e.g., the four pixels form a two-by-two grid, or quad, within the triangle primitive being processed) to determine an LOD value, which is then applied to all four of the pixels. In other words, the LOD value that results is merely an approximation and is inexact with respect to each individual pixel. In most cases, such prior art implementation is subject to artifacts because each LOD computation is biased towards a certain direction depending on the manner in which the differences are computed and the location of the pixels within the primitive. Thus, it would be advantageous to provide a method and system for computing the LOD that can yield more accurate results and minimize the artifacts described above.

[0008] Moreover, in the prior art, the LOD at any given pixel is dependent upon the texture coordinates of its neighboring pixels. More specifically, since the LOD value is based upon the differences in the texture coordinates of adjacent pixels, the computation of the LOD requires that the texture coordinates of the pixels involved be calculated first. Due to the requirement that texture coordinates must be computed prior to LOD computations, the level of parallel processing in the graphics pipeline is significantly restricted. As such, this prior art implementation of LOD computation adversely impacts the efficiency of the graphics pipeline and thus lowers the overall performance of the computer system. Therefore, it would be beneficial to provide a method and system for computing the LOD that does not require the texture coordinates of adjacent pixels be first calculated such that the efficiency of the graphics pipeline as well as the overall performance of the computer system can be enhanced.

[0009] In summary, it would be highly advantageous to provide a method and system for computing the LOD that can yield more accurate results and minimize the artifacts associated with the prior art as described above. Moreover, it would also be advantageous to provide a method and system for computing the LOD that does not require the texture coordinates of adjacent pixels be first calculated such that the efficiency of the graphics pipeline and the overall performance of the computer system can be enhanced.

[0010] Accordingly, the present invention provides a method and system for computing the LOD at each point directly without having to rely on approximations. Such direct computation of the LOD for individual pixels in accordance with the present invention allows the exact LOD values to be easily computed and eliminates the artifacts that are inherent in prior art implementations. Moreover, the present invention provides a method and system for computing the LOD that does not require the texture coordinates of adjacent pixels as inputs. Thus, the present invention enables a higher level of parallel processing in the graphics pipeline, thereby greatly enhancing the efficiency and performance of the graphics pipeline and the computer system as a whole. These and other advantages of the present invention not specifically mentioned above will become clear within discussions of the present invention presented herein.

[0011] More specifically, a currently preferred embodiment of the present invention provides a method for computing the LOD at individual pixels directly during texture mapping. In this embodiment, screen coordinates of a pixel and texture coordinates of vertices of the triangle enclosing the pixel are determined. Derivatives of texture coordinates at the pixel with respect to screen space are evaluated by interpolation using barycentric coordinates of the pixel. Then, using the derivatives of the texture coordinates and without relying on neighboring pixels' texture coordinates, the LOD at the pixel is computed, such that the LOD as computed is unbiased in any particular direction. Significantly, in accordance with the present invention, exact LOD values, rather than approximations based on local differences, are computed. This eliminates the artifacts that are inherent in prior art implementations such as those based on local differences techniques. This embodiment also enables a higher level of parallel processing by eliminating the need to compute texture coordinates prior to computing LOD, thereby enhancing system performance. Alternative embodiments of the present invention provide a computer system upon which the method of the present invention can be practiced. Moreover, in one embodiment, a triangular bilinear interpolator and a multiplier are included as part of the system hardware for performing the direct derivative computations in accordance with the present invention.

[0012] Yet another embodiment provides a method for computing derivatives of a function with respect to screen space, for any function that can be interpolated in eye space by perspective corrected barycentric coordinates for a point in screen space. The method of this embodiment can be used to evaluated any n^th-order derivative where n is a positive integer. In this embodiment, coordinates of a triangle's vertices in screen space are identified, where the triangle includes the point at which the derivatives are to be evaluated. Barycentric coordinates of the point, which specify a location of the point relative to the vertices of the triangle, are determined. Perspective correction factors for the point based on the coordinates of the vertices are also generated. The derivatives of the function are then expressed in interpolated form using the perspective correction factors, the barycentric coordinates of the point and values of the derivatives at the vertices. Finally, the derivatives are evaluated at the point using the interpolated equation such that the derivatives can be computed independently for that point without relying on data from neighboring points.

[0013] The accompanying drawings, which are incorporated in and form a part of this specification, illustrate embodiments of the invention and, together with the description, serve to explain the principles of the invention:

[0014] FIG. 1 is a schematic illustration of an exemplary computer system used in accordance with embodiments of the present invention.

[0015] FIG. 2 is a block diagram illustrating the configuration of a graphics sub-system in accordance with one embodiment of the present invention.

[0016] FIGS. 3A, 3B, 3C, 3D, 3E, 3F, and 3G are diagrams containing the mathematical proof that supports the validity of the derivative computation method and system in accordance with embodiments of the present invention.

[0017] FIG. 4 is a flow diagram illustrating steps for computing derivatives of a function with respect to screen space in accordance with one embodiment of the present invention.

[0018] FIG. 5 is a flow diagram illustrating steps for computing the level of detail (LOD) at a pixel in a triangle during texture mapping in accordance with one embodiment of the present invention.

[0019] Reference will now be made in detail to the preferred embodiments of the invention, examples of which are illustrated in the accompanying drawings. While the invention will be described in conjunction with the preferred embodiments, it will be understood that they are not intended to limit the invention to these embodiments. To the contrary, the invention is intended to cover alternatives, modifications and equivalents, which may be included within the spirit and scope of the invention as defined by the appended claims. Furthermore, in the following detailed description of the present invention, numerous specific details are set forth in order to provide a thorough understanding of the present invention. However, it will be obvious to one of ordinary skill in the art that the present invention may be practiced without these specific details. In other instances, well known methods, procedures, components, and circuits have not been described in detail as not to unnecessarily obscure aspects of the present invention.

[0020] Some portions of the detailed descriptions which follow are presented in terms of procedures, logic blocks, processing, and other symbolic representations of operations on data bits within a computer memory. These descriptions and representations are the means used by those skilled in the data processing arts to most effectively convey the substance of their work to others skilled in the art. In the present application, a procedure, logic block, process, etc., is conceived to be a self-consistent sequence of steps or instructions leading to a desired result. The steps are those requiring physical manipulations of physical quantities. Usually, though not necessarily, these quantities take the form of electrical or magnetic signals capable of being stored, transferred, combined, compared, and otherwise manipulated in a computer system. It has proved convenient at times, principally for reasons of common usage, to refer to these signals as bits, values, elements, symbols, characters, terms, numbers, or the like.

[0021] It should be borne in mind, however, that all of these and similar terms are to be associated with the appropriate physical quantities and are merely convenient labels applied to these quantities. Unless specifically stated otherwise as apparent from the following discussions, it is appreciated that throughout the present invention, discussions utilizing terms such as “identifying”, “determining”, “generating”, “expressing”, “computing” or the like, refer to the actions and processes of a computer system, or similar electronic computing device. The computer system or similar electronic computing device manipulates and transforms data represented as physical (electronic) quantities within the computer system's registers and memories into other data similarly represented as physical quantities within the computer system memories or registers or other such information storage, transmission, or display devices. The present invention is also well suited to the use of other computer systems such as, for-example, optical and mechanical computers.

[0022] FIG. 1 illustrates an exemplary computer system 100 used in accordance with embodiments of the present invention. Within the following discussions of the present invention, certain processes and steps are discussed that are realized, in certain embodiments, as a series of computer-readable and computer-executable instructions (e.g., processes 400 and 500 as illustrated in FIGS. 4 and 5, respectively) that reside, for example, in computer-usable media of computer system 100 and executed by processor(s) of computer system 100. When executed, the instructions cause computer system 100 to perform specific actions and exhibit specific behavior which is described in detail below. It is appreciated that system 100 of FIG. 1 is exemplary only and that the present invention can operate within a number of different computer systems including general purpose computer systems, embedded computer systems, and stand-alone computer systems specially adapted for graphics applications.

[0023] Computer system 100 of FIG. 1 includes an address/data bus 102 for communicating information, and a central processor unit (CPU) 104 coupled to bus 102 for processing information and instructions. Within the scope of the present invention, processor 104 can be a specialized processor that is optimized for performing graphics operations. Computer system 100 also includes data storage features such as a computer-usable volatile memory 106, (e.g., random access memory (RAM)) coupled to bus 102 for storing information and instructions for central processor unit 104, computer-usable non-volatile memory 108 (e.g., read only memory (ROM)) coupled to bus 102 for storing static information and instructions for central processor unit 104, and a data storage device 110 (e.g., a magnetic or optical disk and disk drive) coupled to bus 102 for storing information and instructions. Optionally, computer system 100 may also include a display device 112 coupled to bus 102 for displaying information (e.g., graphics images), an alphanumeric input device 114 having alphanumeric and function keys and coupled to bus 102 for communicating information and command selections to central processor unit 104, a cursor control device 116 coupled to bus 102 for communicating user input information and command selections to central processor unit 104, and also a signal input output communication device 118 (e.g., a modem) coupled to bus 102.

[0024] Display device 112 of FIG. 1, utilized with the present invention, may be a liquid crystal device (LCD), cathode ray tube (CRT), or other display device suitable for creating graphic images and alphanumeric characters recognizable to a user. Optional cursor control device 116 allows the computer user to dynamically signal the two dimensional movement of a visible symbol (cursor) on a display screen of display device 112. Many implementations of cursor control device 116 are known in the art including a trackball, mouse, touch pad or joystick. Alternatively, it will be appreciated that a cursor can be directed and/or activated via input from alphanumeric input device 114 using special keys and key sequence commands. The present invention is also well suited to directing a cursor by other means such as, for example, voice commands.

[0025] Computer system 100 of FIG. 1 also provides data and control signals via bus 102 to a graphics sub-system 120. Graphics sub-system 120 contains a graphics pipeline 122, which includes specialized hardware units for processing a series of display instructions found within a memory-stored display list to render graphics primitives. Graphics pipeline 122 supplies data and control signals to a frame buffer (not shown) that refreshes display device 112 for rendering images (including graphics images). Graphics sub-system 120 is coupled to display device 112 by an address/data bus 121, which enables them to communicate information. A more detailed discussion of the operation of specific features of graphics sub-system 120 of the present invention is found below with reference to FIGS. 2, 3, 4 and 5.

[0026] With reference next to FIG. 2, a block diagram illustrating the configuration of a graphics sub-system in accordance with one embodiment of the present invention is shown. As shown in FIG. 2, in one embodiment of the present invention, graphics sub-system 120 comprises a rasterizer 210. Within the scope of the present invention, rasterizer 210 traverses graphics primitives, such as triangles and lines, to generate information for the corresponding pixels, including their coordinates. Rasterizer 210 is generally coupled to various pipelines, each of which handles a certain aspect of graphics processing. For example, as illustrated in FIG. 2, rasterizer 210 is coupled to a color pipeline 240, a stencil z-buffer pipeline (s/z pipeline) 250 and a texture pipeline 260. In one embodiment, each of color pipeline 240, s/z pipeline 250 and texture pipeline 260 receives coordinates of pixels from rasterizer 210 for further processing according to commands from processor 104. Moreover, in one embodiment, each of color pipeline 240, s/z pipeline 250 and texture pipeline 260 is independently coupled to a bus 280 for communicating information therewith.

[0027] In embodiments of the present invention, graphics sub-system 120 includes a triangular bilinear interpolator (not shown) and a multiplier (not shown), which are used to perform derivative computations in accordance with the present invention, the details of which are described further below. the graphics art, it is appreciated that for any function f which can be interpolated in eye space from constants at the vertices of a triangle, the value of f for a location in the triangle (e.g., a point on or bounded by the edges of the triangle) in screen space can be calculated by interpolating such constants with perspective corrected barycentric coordinates. It is noted that the use of barycentric coordinates and applying perspective correction thereto is well known in the graphics art. Significantly, the present invention further appreciates that for such a function f, its derivative with respect to screen space coordinates can also be computed by interpolating constants at the vertices of the triangle in eye space and applying the perspective barycentric coordinates multiple times, where the exact number of times is dependent upon the order of the derivatives that are to be calculated. As a specific example, within the scope of the present invention, it is shown that the firstorder derivative of function f with respect to screen space coordinates can be computed by interpolating constants at the vertices of the triangle in eye space and applying the perspective barycentric coordinates twice. Likewise, as another example, it is shown within the scope of the present invention that the second-order derivative of function f with respect to screen space coordinates can be computed by interpolating constants at the vertices of the triangle in eye space and applying the perspective barycentric coordinates three times.

[0028] More generally, the present invention appreciates that any n^th-order derivative, where n is a positive integer, can be computed by interpolating constants at the vertices of the triangle in eye space and applying the perspective barycentric coordinates (n+l) times. A detailed mathematical proof that supports the validity of the derivative computation method and system in accordance with embodiments of the present invention is presented in FIGS. 3A, 3B, 3C, 3D, 3E, 3F, and 3G.

[0029] Based upon the foregoing discussion, the present invention further appreciates that the texture coordinates at a given point in screen space, typically denoted as S and T in the graphics art, are examples of functions with characteristics identical to function f described above. More specifically, the values of S and T for a given point in screen space can be evaluated by interpolating the S and T values at the vertices of a triangle, which encloses the point in question, with the perspective corrected barycentric coordinates. Thus, in accordance with the present invention, the first-order derivatives of S and T in screen space can be directly evaluated at a given point in screen space by applying the perspective correction factor twice to the interpolated derivatives from the vertices of the triangle. In a currently preferred embodiment, the computer system in accordance with the present invention includes a triangular bilinear interpolator and a multiplier for evaluating the derivatives of the texture coordinates.

[0030] In particular, the above described method and system for direct computation of derivatives of the texture coordinates can be advantageously applied to the determination of the level of detail (LOD) at each point (e.g., a pixel), a typical operation that is performed during texture mapping. Since the LOD at a given point is a function of the derivatives of the texture coordinates evaluated at that point, the LOD can readily be computed once the values of the derivatives of the texture coordinates are available. Importantly, by computing the derivatives of the texture coordinates as described above and then applying the results to determine the LOD at a given point, the present invention provides an exact value which accurately represents the proper LOD at the point in question. Furthermore, the LOD value so calculated is not biased towards any particular direction, irrespective of the particular orientation of the triangle being processed and the location of the pixel within the triangle. As such, the present invention completely eliminates from the resulting images those undesirable artifacts that results from the location of the samples used to compute local differences in the prior art. Rather, each pixel has its own independent and exact LOD value, which is not an approximation based on adjacent pixels. Thus, embodiments of the present invention provide a method and system for computing the LOD that yield superior results to those generated by prior art approaches.

[0031] Moreover, unlike the prior art, the computation of the LOD at a pixel is not dependent upon the differences in the texture coordinates of adjacent pixels according to the present invention, as the LOD are readily computed from the values of the derivatives of the texture coordinates at that pixel and the derivatives are directly evaluated as described above. Therefore, the computation of the texture coordinates and the LOD of a pixel can be performed in parallel. Likewise, since the computation of the LOD at a given pixel is not dependent upon the texture coordinates of its neighboring pixels, the LOD of neighboring pixels can also be computed in parallel. Thus, the restrictions imposed by the prior art approach on the level of parallel processing in the graphics pipeline is eliminated by applying the direct computation of the present invention. As such, the efficiency of the graphics pipeline as well as the overall performance of the computer system is significantly enhanced by implementing the direct computation of derivatives in accordance with the present invention.

[0032] Referring next to FIG. 4, a flow diagram 400 illustrating steps for computing derivatives of a function with respect to screen space in accordance with one embodiment of the present invention is shown. As described above, it is appreciated that the function whose derivatives are to be computed is capable of being interpolated in eye space by perspective corrected barycentric coordinates for a point in screen space.

[0033] Thus, referring to FIG. 4, in step 410, coordinates and values of the derivative (of the function) at the vertices of a triangle in screen space are identified, where the triangle includes the point at which the derivatives are to be evaluated.

[0034] With reference still to FIG. 4, in step 420, barycentric coordinates of the point in question are determined. It is appreciated that the barycentric coordinates specify a location of the point relative to the vertices of the triangle as described above and as defined in FIG. 3A.

[0035] Referring still to FIG. 4, in step 430, perspective correction factors for the point are generated based on the coordinates of the vertices, as described above and with reference to FIGS. 3A-3G.

[0036] With reference again to FIG. 4, in step 440, the derivatives of the function are expressed in interpolated form using the perspective correction factors generated in step 430, the barycentric coordinates of the point as determined in step 420 and values of the derivatives at the vertices. The interpolated form of the derivatives are illustrated in detail with reference to FIGS. 3A, 3B, 3C and 3D.

[0037] Referring still to FIG. 4, in step 450, the derivatives are evaluated at the point in question using the interpolated equation arrived at in step 440 such that the derivatives can be computed independently for that point without relying on data from neighboring points.

[0038] It is appreciated that process 400 has numerous applications within the graphics art. In one specific embodiment, the derivatives of the function with respect to screen space are first-order derivatives and are used to compute the level of detail (LOD) at the point at which the derivatives are evaluated. This embodiment is described further with reference to FIG. 5 below. In another embodiment, the derivatives of the function with respect to screen space are second-order derivatives and are used to compute the surface curvature at the point at which the derivatives are evaluated. It should further be appreciated that process 400 of FIG. 4 is not limited to the particular embodiments and applications described herein. Rather, process 400 is well suited for use in the computation of the n^th-order derivatives of the function with respect to screen space where n is any positive integer, which have different applicability in graphics processing that would be clear to one skilled in the graphics art. Such different applications of process 400 of FIG. 4 is within the scope and spirit of the present invention.

[0039] Referring next to FIG. 5, a flow diagram 500 illustrating steps for computing the level of detail (LOD) at a pixel in a triangle during texture mapping in accordance with one embodiment of the present invention is shown. In one embodiment, texture mapping is performed using texture pipeline 260 (FIG. 2) of graphics sub-system 120.

[0040] Thus, with reference to FIG. 5, in step 510, screen coordinates of the pixel and texture coordinates of vertices of the triangle that encloses the pixel are determined. It is appreciated that the determination of screen coordinates and texture coordinates are known in the art and thus not described in detail herein. In one embodiment, the texture coordinates of vertices of the triangle that encloses the pixel are provided as inputs.

[0041] Referring still to FIG. 5, in step 520, derivatives of texture coordinates are evaluated at the pixel with respect to screen space by interpolation using barycentric coordinates of the pixel. In one embodiment, process 400 of FIG. 4 as described above is used to perform step 520.

[0042] More specifically, in one embodiment, step 520 is implemented as follows: three constants specific to the triangle, each of which is computed based on a vertex of the triangle, are computed. Perspective correction factors for the pixel are then computed using the three constants. The derivatives of the texture coordinates are evaluated at the pixel with respect to screen space by interpolating the derivatives of the texture coordinates at the vertices using the perspective correction factors and the barycentric coordinates. In a currently preferred embodiment, step 520 includes a triangular bilinear interpolation and a multiplication

[0043] With reference again to FIG. 5, in step 530, the LOD at the pixel is computed using the derivatives of the texture coordinates as evaluated in step 520, where the LOD of the pixel is computed independent of texture coordinates of neighboring pixels, such that the LOD thus computed is unbiased in any particular direction. Significantly, such direct computation allows exact LOD values to be easily computed and eliminates the artifacts that are inherent in prior art implementations employing local difference techniques. This embodiment also enables a higher level of parallel processing by eliminating the prerequisite of computing texture coordinates before computing LOD, thereby enhancing system performance.

[0044] In one embodiment, the derivatives of the texture coordinates at the pixel with respect to screen space are first-order derivatives and the perspective correction factors are applied to the respective barycentric coordinates twice in the interpolation. Moreover, in one embodiment, the derivatives of the texture coordinates are applicable to computations in MIP-mapping, RIP-mapping and footprint assembly operations.

[0045] Importantly, as described above, embodiments of the present invention enable the computation of the texture coordinates and step 520 to be performed concurrently. Similarly, LOD computation for neighboring pixels can be performed in parallel. By computing the LOD without requiring the texture coordinates of adjacent pixels as inputs, embodiments of the present invention enable a higher level of parallel processing in the graphics pipeline, thereby greatly enhancing the efficiency and performance of the graphics pipeline and the computer system as a whole.

[0046] The preferred embodiment of the present invention, a method and system for evaluating derivatives in screen space using perspective corrected barycentric coordinates, is thus described. While the present invention has been described in particular embodiments, it should be appreciated that the present invention should not be construed as limited by such embodiments, but rather construed according to the below claims.