Batch processing of primitives for use with a texture accumulation buffer

[0002] 1. Field of the Invention

[0003] This invention relates generally to the field of computer graphics and, more particularly, to high performance graphics systems for rendering graphical objects based on a decomposition of the graphical objects into primitives such as triangles, dots and lines.

[0004] 2. Description of the Related Art

[0005] A graphics system may be configured to receive a stream of graphics parameters defining primitives such as triangles, lines and dots from a host application executing on a host computer. For example, the graphics system may receive a stream of vertices defining triangles in a 3D coordinate space. The triangles represent a collection of 3D objects in the 3D world coordinate space. The graphics system may operate on the triangles to generate a video stream which represents the view of a virtual camera (or virtual observer) in the 3D world coordinate space. In particular, the graphics system may compute color values for each pixel that resides within each triangle (i.e. within the two-dimensional footprint of the triangle in screen space). This process of assigning color values to pixels (or samples) internal to triangles is referred to herein as triangle rasterization.

[0006] Triangle rasterization may include the application of one or more textures. In other words, the graphics system may store one or more texture maps in a texture memory and may modify the color of pixels using the one or more texture maps. For example, pixels residing internal to a given triangle comprising part of a wall may be textured with three texture maps, the first map giving the triangle the appearance of brick material, the second map for putting oil smudges on the brick-textured triangle, the third map for varying the level of illumination of pixels on the oil-smudged brick-textured triangle.

[0007] According to one conventional rasterization method, each pixel in a given triangle may be textured with all N textures (from the N corresponding texture maps) before proceeding to the next pixel (interior to the triangle) along a scan line or on the next scan line. In other words, a processor may compute color values for a pixel P₁by sequentially accessing a texel from texture map #1, a texel from texture map #2, . . . , a texel from texture map #N. Then after completing the computation of color values for pixel P_l, the processor may compute color values for the next pixel P_l+linterior to the triangle by sequentially accessing a texel from texture map #1, a texel from texture map #2, . . . , a texel from texture map #N. This method of texturing triangles is very inefficient in its use of texture memory as the frequency of cache misses and page misses is large.

[0008] Thus, there exists a need for a graphics system and method which could more efficiently apply multiple layers of texture to primitives.

[0009] A graphics system is configured to apply multiple layers of texture information to batches of graphics primitives (e.g. triangles, dots, lines, etc.). In one set of embodiments, the graphics system includes a hardware accelerator, a frame buffer, a video output processor and a texture memory. The texture memory may store multiple layers of texture information.

[0010] The hardware accelerator collects primitives into a batch that share a common set of texture layers to be applied. The batch is limited so that the total estimated size (e.g. fragment size or sample size) for the batch is less than or equal to a storage capacity of a texture accumulation buffer. In some embodiments, a fragment size estimate for the batch may be a sum of size estimates for the individual primitives. In other embodiments, the fragment size estimate for a batch may involve an incremental polygon area computation and/or an incremental polygon perimeter computation, especially for a batch of chained primitives (such as a strip or fan). The hardware accelerator stores samples (or fragments) corresponding to the batch primitives in the texture accumulation buffer between the application of successive texture layers.

[0011] Because the hardware accelerator operates on a batch of primitives, the large magnitude address jumps between texture layers in the address space of the texture memory may occur less often than if the hardware accelerator cycled through all texture layers per fragment per primitive. Thus, texture accesses to texture memory may be more efficient.

[0012] The foregoing, as well as other objects, features, and advantages of this invention may be more completely understood by reference to the following detailed description when read together with the accompanying drawings in which:

[0013] FIG. 1 illustrates one embodiment of a graphics system configured to perform 3D graphics computations for display of graphical object on a display device;

[0014] FIG. 2 is a block diagram for one embodiment of computer system 80;

[0015] FIG. 3 is a block diagram for one embodiment of a graphics system configured to generate one or more video streams in response to received graphics data;

[0016] FIG. 4 is a block diagram for one embodiment of media processor 14;

[0017] FIG. 5 is a block diagram for one embodiment of hardware accelerator 18;

[0018] FIG. 6 is a block diagram for one embodiment of video output processor 24;

[0019] FIG. 7 illustrates a portion of rendering space populated with samples and partitioned into fragments (i.e. bins) according to one set of embodiments;

[0020] FIG. 8 illustrates one set of embodiments of a method for applying multiple textures to primitives to generate displayable images; and

[0021] FIG. 9 illustrates one example of a chained sequence of primitives, i.e. a triangle strip; and

[0022] FIG. 10 illustrates an example of a primitive whose is significantly smaller than the number of fragments intersected by the primitive.

[0023] While the invention is susceptible to various modifications and alternative forms, specific embodiments thereof are shown by way of example in the drawings and will herein be described in detail. It should be understood, however, that the drawings and detailed description thereto are not intended to limit the invention to the particular form disclosed, but on the contrary, the intention is to cover all modifications, equivalents, and alternatives falling within the spirit and scope of the present invention as defined by the appended claims. Note, the headings are for organizational purposes only and are not meant to be used to limit or interpret the description or claims. Furthermore, note that the word “may” is used throughout this application in a permissive sense (i.e., having the potential to, being able to), not a mandatory sense (i.e., must).” The term “include”, and derivations thereof, mean “including, but not limited to”. The term “connected” means “directly or indirectly connected”, and the term “coupled” means “directly or indirectly connected”.

[0024] Computer System—FIG. 1

[0025] Referring now to FIG. 1, one embodiment of a computer system 80 that includes a graphics system is shown. The graphics system may be comprised in any of various systems, including a computer system, network PC, Internet appliance, a television, including HDTV systems and interactive television systems, personal digital assistants (PDAs), virtual reality systems, and other devices which display 2D and or 3D graphics, among others.

[0026] As shown, the computer system 80 comprises a system unit 82 and a video monitor or display device 84 coupled to the system unit 82. The display device 84 may be any of various types of display monitors or devices (e.g., a CRT, LCD, or gas-plasma display). Various input devices may be connected to the computer system, including a keyboard 86 and/or a mouse 88, or other input device (e.g., a trackball, digitizer, tablet, six-degree of freedom input device, head tracker, eye tracker, data glove, or body sensors). Application software may be executed by the computer system 80 to display graphical objects on display device 84.

[0027] Computer System Block Diagram—FIG. 2

[0028] Referring now to FIG. 2, a simplified block diagram illustrating the computer system of FIG. 1 is shown. Elements of the computer system that are not necessary for an understanding of the present invention are not shown for convenience. As shown, the computer system 80 includes a central processing unit (CPU) 102 coupled to a high-speed memory bus or system bus 104 also referred to as the host bus 104. A system memory 106 may also be coupled to high-speed bus 104.

[0029] Host processor 102 may comprise one or more processors of varying types, e.g., microprocessors, multi-processors and CPUs. The system memory 106 may comprise any combination of different types of memory subsystems, including random access memories, (e.g., static random access memories or “SRAMs,” synchronous dynamic random access memories or “SDRAMs,” and Rambus dynamic random access memories or “RDRAM,” among others) and mass storage devices. The system bus or host bus 104 may comprise one or more communication or host computer buses (for communication between host processors, CPUs, and memory subsystems) as well as specialized subsystem buses.

[0030] In FIG. 2, a graphics system 112 is coupled to the high-speed memory bus 104. The 3-D graphics system 112 may be coupled to the bus 104 by, for example, a crossbar switch or other bus connectivity logic. It is assumed that various other peripheral devices, or other buses, may be connected to the high-speed memory bus 104. It is noted that the graphics system may be coupled to one or more of the buses in computer system 80 and/or may be coupled to various types of buses. In addition, the graphics system may be coupled to a communication port and thereby directly receive graphics data from an external source, e.g., the Internet or a network. As shown in the figure, one or more display devices 84 may be connected to the graphics system 112 comprised in the computer system 80.

[0031] Host CPU 102 may transfer information to and from the graphics system 112 according to a programmed input/output (I/O) protocol over host bus 104. Alternately, graphics system 112 may access the memory subsystem 106 according to a direct memory access (DMA) protocol or through intelligent bus mastering.

[0032] A graphics application program conforming to an application programming interface (API) such as OpenGL or Java 3D may execute on host CPU 102 and generate commands and data that define a geometric primitive (graphics data) such as a polygon for output on display device 84. As defined by the particular graphics interface used, these primitives may have separate color properties for the front and back surfaces. Host processor 102 may transfer this graphics data to memory subsystem 106. Thereafter, the host processor 102 may operate to transfer the graphics data to the graphics system 112 over the host bus 104. In another embodiment, the graphics system 112 may read in geometry data arrays over the host bus 104 using DMA access cycles. In yet another embodiment, the graphics system 112 may be coupled to the system memory 106 through a direct port, such as the Advanced Graphics Port (AGP) promulgated by Intel Corporation.

[0033] The graphics system may receive graphics data from any of various sources, including the host CPU 102 and/or the system memory 106, other memory, or from an external source such as a network, e.g., the Internet, or from a broadcast medium, e.g., television, or from other sources.

[0034] Note while graphics system 112 is depicted as part of computer system 80, graphics system 112 may also be configured as a stand-alone device (e.g., with its own built-in display). Graphics system 112 may also be configured as a single chip device or as part of a system-on-a-chip or a multi-chip module. Additionally, in some embodiments, certain elements of the illustrated graphics system 112 may be implemented in software.

[0035] Graphics System—FIG. 3

[0036] Referring now to FIG. 3, a functional block diagram illustrating one embodiment of graphics system 112 is shown. Note that many other embodiments of graphics system 112 are possible and contemplated. Graphics system 112 may comprise one or more media processors 14, one or more hardware accelerators 18, one or more texture buffers 20, one or more frame buffers 22, and one or more video output processors 24. Graphics system 112 may also comprise one or more output devices such as digital-to-analog converters (DACs) 26, video encoders 28, flat-panel-display drivers (not shown), and/or video projectors (not shown). Media processor 14 and/or hardware accelerator 18 may be any suitable type of high performance processor (e.g., specialized graphics processors or calculation units, multimedia processors, DSPs, or general purpose processors).

[0037] In some embodiments, one or more of these components may be removed. For example, the texture buffer may not be included in an embodiment that does not provide texture mapping. In other embodiments, all or part of the functionality implemented in either or both of the media processor or the graphics accelerator may be implemented in software.

[0038] In some embodiments, media processor 14 and hardware accelerator 18 may be comprised within the same integrated circuit. In other embodiments, portions of media processor 14 and/or hardware accelerator 18 may be comprised within separate integrated circuits.

[0039] As shown, graphics system 112 may include an interface to a host bus such as host bus 104 in FIG. 2 to enable graphics system 112 to communicate with a host system such as computer system 80. More particularly, host bus 104 may allow a host processor to send commands to the graphics system 112. In one embodiment, host bus 104 may be a bi-directional bus.

[0040] Media Processor—FIG. 4

[0041] FIG. 4 shows one embodiment of media processor 14. As shown, media processor 14 operates as the interface between graphics system 112 and computer system 80 by controlling the transfer of data between graphics system 112 and computer system 80. In some embodiments, media processor 14 may also be configured to perform transform, lighting, and/or other general-purpose processing on graphical data.

[0042] Transformation refers to manipulating an object and includes translating the object (i.e., moving the object to a different location), scaling the object (i.e., stretching or shrinking), and rotating the object (e.g., in three-dimensional space, or “3-space”).

[0043] Lighting refers to calculating the illumination of the objects within the displayed image to determine what color and or brightness each individual object will have. Depending upon the shading algorithm being used (e.g., constant, Gourand, or Phong), lighting may be evaluated at a number of different locations. For example, if constant shading is used (i.e., each pixel of a polygon has the same lighting), then the lighting need only be calculated once per polygon. If Gourand shading is used, then the lighting is calculated once per vertex. Phong shading calculates the lighting on a per-pixel basis.

[0044] As illustrated, media processor 14 may be configured to receive graphical data via host interface 11. A graphics queue 148 may be included in media processor 14 to buffer a stream of data received via the accelerated port of host interface 11. The received graphics data may comprise one or more graphics primitives. As used herein, the term graphics primitive may include polygons, parametric surfaces, splines, NURBS (non-uniform rational B-splines), sub-divisions surfaces, fractals, volume primitives, voxels (i.e., three-dimensional pixels), and particle systems. In one embodiment, media processor 14 may also include a geometry data preprocessor 150 and one or more microprocessor units (MPUs) 152. MPUs 152 may be configured to perform vertex transform and lighting calculations and programmable functions and to send results to hardware accelerator 18. MPUs 152 may also have read/write access to texels (i.e. the smallest addressable unit of a texture map, which is used to “wallpaper” a three-dimensional object) and pixels in the hardware accelerator 18. Geometry data preprocessor 150 may be configured to decompress geometry, to convert and format vertex data, to dispatch vertices and instructions to the MPUs 152, and to send vertex and attribute tags or register data to hardware accelerator 18.

[0045] As shown, media processor 14 may have other possible interfaces, including an interface to a memory. For example, as shown, media processor 14 may include direct Rambus interface 156 to a direct Rambus DRAM (DRDRAM) 16. A memory such as DRDRAM 16 may be used for program and data storage for MPUs 152. DRDRAM 16 may also be used to store display lists and/or vertex texture maps.

[0046] Media processor 14 may also include interfaces to other functional components of graphics system 112. For example, media processor 14 may have an interface to another specialized processor such as hardware accelerator 18. In the illustrated embodiment, controller 160 includes an accelerated port path that allows media processor 14 to control hardware accelerator 18. Media processor 14 may also include a direct interface, such as bus interface unit (BIU) 154, which provides a direct port path to memory 16 and to hardware accelerator 18 and video output processor 24 via controller 160.

[0047] Hardware Accelerator—FIG. 5

[0048] One or more hardware accelerators 18 may be configured to receive graphics instructions and data from media processor 14 and then to perform a number of functions on the received data according to the received instructions. For example, hardware accelerator 18 may be configured to perform rasterization, 2D or 3D texturing, pixel transfers, imaging, fragment processing, clipping, depth cueing, transparency processing, set-up, and/or screen space rendering of various graphics primitives occurring within the graphics data.

[0049] Clipping refers to the elimination of graphics primitives or portions of graphics primitives that lie outside of a 3D view volume in world space. The 3D view volume may represent that portion of world space that is visible to a virtual observer (or virtual camera) situated in world space. For example, the view volume may be a solid truncated pyramid generated by a 2D view window and a viewpoint located in world space. The solid truncated pyramid may be imagined as the union of all rays emanating from the viewpoint and passing through the view window. The viewpoint may represent the world space location of the virtual observer. In most cases, primitives or portions of primitives that lie outside the 3D view volume are not currently visible and may be eliminated from further processing. Primitives or portions of primitives that lie inside the 3D view volume are candidates for projection onto the 2D view window.

[0050] Set-up refers to mapping primitives to a three-dimensional viewport. This involves translating and transforming the objects from their original “world-coordinate” system to the established viewport's coordinates. This creates the correct perspective for three-dimensional objects displayed on the screen.

[0051] Screen-space rendering refers to the calculation performed to generate the data used to form each pixel that will be displayed. For example, hardware accelerator 18 may calculate “samples.” Samples are points that have color information but no real area. Samples allow hardware accelerator 18 to “super-sample,” or calculate more than one sample per pixel. Super-sampling may result in a higher quality image.

[0052] Hardware accelerator 18 may also include several interfaces. For example, in the illustrated embodiment, hardware accelerator 18 has four interfaces. Hardware accelerator 18 has an interface 161 (referred to as the “North Interface”) to communicate with media processor 14. Hardware accelerator 18 may also be configured to receive commands from media processor 14 through this interface. Additionally, hardware accelerator 18 may include an interface 176 to bus 32. Bus 32 may connect hardware accelerator 18 to boot PROM 30 and/or video output processor 24. Boot PROM 30 may be configured to store system initialization data and/or control code for frame buffer 22. Hardware accelerator 18 may also include an interface to a texture memory 20. For example, hardware accelerator 18 may interface to texture memory 20 using an eight-way interleaved texel bus that allows hardware accelerator 18 to read from and write to texture memory 20. Hardware accelerator 18 may also interface to a frame buffer 22. For example, hardware accelerator 18 may be configured to read from and/or write to frame buffer 22 using a four-way interleaved pixel bus.

[0053] The vertex processor 162 may be configured to use the vertex tags received from the media processor 14 to perform ordered assembly of the vertex data from the MPUs 152. Vertices may be saved in and/or retrieved from a mesh buffer 164.

[0054] The render pipeline 166 may be configured to receive vertices and convert them to fragments. The render pipeline 166 may be configured to rasterize 2D window system primitives (e.g., dots, fonts, Bresenham lines, polygons, rectangles, fast fills, and BLITs (Bit Block Transfers, which move a rectangular block of bits from main memory into display memory, which may speed the display of moving objects on screen)) and 3D primitives (e.g., smooth and large dots, smooth and wide DDA (Digital Differential Analyzer) lines, triangles, polygons, and fast clear) into pixel fragments. The render pipeline 166 may be configured to handle full-screen size primitives, to calculate plane and edge slopes, and to interpolate data down to pixel tile resolution using interpolants or components such as r, g, b (i.e., red, green, and blue vertex color); r2, g2, b2 (i.e., red, green, and blue specular color from lit textures); a (alpha); and z, s, t, r, and w (texture components).

[0055] In embodiments using supersampling, the sample generator 174 may be configured to generate samples from the fragments output by the render pipeline 166 and to determine which samples are inside the rasterization edge. Sample positions may be defined in loadable tables to enable stochastic sampling patterns.

[0056] Hardware accelerator 18 may be configured to write textured fragments from 3D primitives to frame buffer 22. The render pipeline 166 may send pixel tiles defining r, s, t and w to the texture address unit 168. The texture address unit 168 may determine the set of neighboring texels that are addressed by the fragment(s), as well as the interpolation coefficients for the texture filter, and write texels to the texture memory 20. The texture memory 20 may be interleaved to obtain as many neighboring texels as possible in each clock. The texture filter 170 may perform bilinear, trilinear or quadlinear interpolation. The pixel transfer unit 182 may also scale and bias and/or lookup texels. The texture environment 180 may apply texels to samples produced by the sample generator 174. The texture environment 180 may also be used to perform geometric transformations on images (e.g., bilinear scale, rotate, flip) as well as to perform other image filtering operations on texture buffer image data (e.g., bicubic scale and convolutions).

[0057] In the illustrated embodiment, the pixel transfer MUX 178 controls the input to the pixel transfer unit 182. The pixel transfer unit 182 may selectively unpack pixel data received via north interface 161, select channels from either the frame buffer 22 or the texture memory 20, or select data received from the texture filter 170 or sample filter 172.

[0058] The pixel transfer unit 182 may be used to perform scale, bias, and/or color matrix operations, color lookup operations, histogram operations, accumulation operations, normalization operations, and/or min/max functions. Depending on the source of and operations performed on the processed data, the pixel transfer unit 182 may then output the data to the texture memory 20 (via the texture buffer MUX 186), the frame buffer 22 (via the texture environment unit 180 and the fragment processor 184), or to the host (via north interface 161). For example, in one embodiment, when the pixel transfer unit 182 receives pixel data from the host via the pixel transfer MUX 178, the pixel transfer unit 182 may be used to perform a scale and bias or color matrix operation, followed by a color lookup or histogram operation, followed by a min/max function. The pixel transfer unit 182 may then output data to either the texture memory 20 or the frame buffer 22.

[0059] Fragment processor 184 may be used to perform standard fragment processing operations such as the OpenGL fragment processing operations. For example, the fragment processor 184 may be configured to perform the following operations: fog, area pattern, scissor, alpha/color test, ownership test (WID), stencil test, depth test, alpha blends or logic ops (ROP), plane masking, buffer selection, pick hit/occlusion detection, and/or auxiliary clipping in order to accelerate overlapping windows.

[0060] Texture Memory 20

[0061] Texture memory 20 may include several SDRAMs. Texture memory 20 may be configured to store texture maps and image processing buffers for hardware accelerator 18. Texture memory 20 may have many different capacities (e.g., depending on the type of SDRAM included in texture memory 20). In some embodiments, each pair of SDRAMs may be independently row and column addressable.

[0062] Frame Buffer 22

[0063] Graphics system 112 may also include a frame buffer 22. In one embodiment, frame buffer 22 may include multiple 3DRAM64s. Frame buffer 22 may be configured as a display pixel buffer, an offscreen pixel buffer, and/or a supersample buffer. Furthermore, in one embodiment, certain portions of frame buffer 22 may be used as a display pixel buffer, while other portions may be used as an offscreen pixel buffer and supersample buffer.

[0064] Video Output Processor—FIG. 6

[0065] A video output processor 24 may also be included within graphics system 112. Video output processor 24 may buffer and process pixels output from frame buffer 22. For example, video output processor 24 may be configured to read bursts of pixels from frame buffer 22. Video output processor 24 may also be configured to perform double buffer selection (dbsel) if the frame buffer 22 is double-buffered, overlay transparency (using transparency/overlay unit 190), plane group extraction, gamma correction, psuedocolor or color lookup or bypass, and/or cursor generation. For example, in the illustrated embodiment, the output processor 24 includes WID (Window ID) lookup tables (WLUTs) 192 and gamma and color map lookup tables (GLUTs, CLUTs) 194. In one embodiment, frame buffer 22 may include multiple 3DRAM64s 201 that include the transparency overlay 190 and all or some of the WLUTs 192. Video output processor 24 may also be configured to support two video output streams to two displays using the two independent video raster timing generators 196. For example, one raster (e.g., 196A) may drive a 1280×1024 CRT while the other (e.g., 196B) may drive a NTSC or PAL device with encoded television video.

[0066] DAC 202 may operate as the final output stage of graphics system 112. The DAC 202 translates the digital pixel data received from GLUT/CLUTs/Cursor unit 194 into analog video signals that are then sent to a display device. In one embodiment, DAC 202 may be bypassed or omitted completely in order to output digital pixel data in lieu of analog video signals. This may be useful when a display device is based on a digital technology (e.g., an LCD-type display or a digital micro-mirror display).

[0067] DAC 202 may be a red-green-blue digital-to-analog converter configured to provide an analog video output to a display device such as a cathode ray tube (CRT) monitor. In one embodiment, RGB DAC 202 may be configured to provide a high resolution RGB analog video output at dot rates of 240 MHz. Similarly, encoder 200 may be configured to supply an encoded video signal to a display. For example, encoder 200 may provide encoded NTSC or PAL video to an S-Video or composite video television monitor or recording device.

[0068] In other embodiments, the video output processor 24 may output pixel data to other combinations of displays. For example, by outputting pixel data to two DACs 202 (instead of one DAC 202 and one encoder 200), video output processor 24 may drive two CRTs. Alternately, by using two encoders 200, video output processor 24 may supply appropriate video input to two television monitors. Generally, many different combinations of display devices may be supported by supplying the proper output device and/or converter for that display device.

[0069] Overall Processing Flow

[0070] Hardware accelerator 18 receives a stream of graphics data from media processor 14. The graphics data specifies primitives to be rendered such as triangles, lines and dots. For example, for a triangle, the graphics data may include vertex positions, vertex color vectors, and a specification of which texture layers are to be applied to the triangle. The graphics data may also include texture control parameters which determine how the specified texture layers are to be applied to a given primitive.

[0071] Hardware accelerator 18 may render the primitives in terms of samples. The samples may be stored in a sample area of frame buffer 22. The samples are then read from the sample area of frame buffer 22 and filtered by sample filter 22 to generate pixels. The pixels are stored in a pixel area of frame buffer 22. The pixel area may be double buffered. Video output processor 24 reads pixels from the pixel area of frame buffer 22 and generates a video signal from the pixels. The video signal is made available to one or more display devices (e.g. monitors and/or projectors).

[0072] The samples are computed at positions in a two-dimensional sample space (also referred to as rendering space). The sample space is partitioned into an array of bins (also referred to herein as fragments). The storage of samples in the sample area of frame buffer 22 may be organized according to bins (e.g. bin 300) as suggested by FIG. 7. Each bin contains one or more samples. The number of samples per bin may be a programmable parameter.

[0073] Texture Pipe and Multitexturing Support

[0074] As shown in FIG. 5, in one set of embodiments, hardware accelerator 18 includes texture address unit 168, texture filter 170, texture environment 180 and texture accumulation buffer (TAB) 181. These units are collectively referred to herein as the texture pipe as they each have a role in the process of applying texture information to primitives. Pixel transfer MUX 178 and pixel transfer unit 182 may participate in texture processing operations as well as other types of processing operations.

[0075] The hardware accelerator 18 supports the application of multiple layers of texture to primitives. The multiple layers of texture are stored in texture memory 20. Each layer may comprise multiple mipmap levels.

[0076] Vertex processor 162 may receive a stream of graphics data from media processor 14. The graphics data corresponds to primitives that are to be rendered. Primitives include graphical elements such as triangles, lines and dots. The graphics data associated with a given primitive may include geometric parameters, one or more color vectors, and texture parameters. The geometric parameters define the primitive geometrically. The texture parameters specify which texture layers are to be applied to the primitives as well as texture coordinates for the primitive with respect to the specified layers. In the case of a triangle, the geometric parameters may comprise vertex positions, and the one or more color vectors may be color vectors associated with the vertex positions.

[0077] In one set of embodiments, hardware accelerator 18 is configured to apply textures to a batch of primitives. Each primitive in the batch intersects one or more fragments (i.e. bins) in the rendering space. For example, the triangle of FIG. 7 intersects 11 fragments and the line of FIG. 7 intersects 13 fragments. Let N_Pdenote the number of fragments which intersect with a primitive P. The number N_Pis referred to herein as the fragment size of the primitive P.

[0078] Texture accumulation buffer 181 applies textures to the batch of primitives one texture layer at a time. Fragments corresponding to the primitives of the batch are stored in texture accumulation buffer between the application of successive texture layers. Thus, the sum of the fragment sizes N_Pof the primitives P in the batch may be limited to a value less than or equal to the fragment capacity of texture accumulation buffer 181. The fragment capacity of the TAB 181 is the maximum number of fragments that texture accumulation buffer 181 can hold.

[0079] Vertex processor 162 gathers a batch of primitives as follows. Starting from an initial state where the batch is empty, vertex processor 162 receives a first primitive P₀and associated texture data T₀from media processor 14 and generates an estimate E_P0for the fragment size N_P0of the first primitive P₀. Methods for generating the extimate E_P0will be discussed later. The estimate E_P0may be an upper bound for the fragment size N_P0. (An upper bound for X is any number U greater than or equal to X.)

[0080] Vertex processor 162 may add the estimate E_P0to a cumulative sum S according to the relation S=S+E_P0. The cumulative sum equals zero in the initial state. Vertex J processor 162 may add the first primitive P₀to the batch, i.e. store the first primitive in a batch buffer 163 as indicated in FIG. 5. Vertex processor may send the first primitive P₀downstream to render pipe 166 with a first texture layer indicator indicating a first of the texture layers to be applied to the first primitive P₀.

[0081] Vertex processor 162 receives a second primitive P₁and associated texture data T₁from media processor 14, and generates an estimate E_P1for the fragment size N_P1of the second primitive P₁. The texture data T₁specifies which texture layers are to be applied to the second primitive P₁. Vertex processor 162 determines if the texture layers specified for the second primitive P₁are the same as the texture layers specified for the first primitive P₀. This is the layer agreement test.

[0082] Vertex processor 162 may also perform a cumulative size test as follows. Vertex processor 162 may add the fragment size estimate E_P1of primitive P₁to the cumulative sum S according to the relation S=S+E_P1, and compare the updated cumulative sum to the fragment capacity N_TABof texture accumulation buffer 181. (It is noted that the layer agreement test and the cumulative size test may be performed sequentially or in parallel.)

[0083] If the layer agreement test and the cumulative size test both pass, i.e. if the two sets of layers are equal and the updated cumulative sum is less than or equal to the fragment capacity N_TAB, vertex processor 162 may add the second primitive P₁to the batch (i.e. append the second primitive to the batch list stored in the batch buffer), and send the second primitive P₁downstream to render pipe 166 with the first texture layer indicator.

[0084] More generally, vertex processor 162 receives a K^thprimitive P_Kand associated texture data T_Kfrom media processor 14, and generates an estimate E_PKfor the fragment size N_PKof the K^thprimitive P_K, where K is an integer index greater than or equal to one. The texture data T_Kspecifies which texture layers are to be applied to the K^thprimitive P_K. The texture data T_Kmay also comprise texture coordinate data for the specified texture layers. Vertex processor 162 determines if the texture layers specified for the K^thprimitive P_Kare the same as the texture layers specified for the first primitive P0 of the batch.

[0085] Vertex processor 162 may add the fragment size estimate E_PKto the cumulative sum S according to the relation S=S+E_PK, and compare the updated cumulative sum to the fragment capacity N_TABof texture accumulation buffer 181.

[0086] If the layer agreement test and the cumulative size test both pass, i.e. if the two sets of layers are equal and the updated cumulative sum is less than or equal to the fragment capacity N_TAB, vertex processor 162 may add the K^thprimitive P_Kto the batch (i.e. append the K^thprimitive P_Kto the batch list stored in the batch buffer), and send the K^thprimitive P_Kdownstream to render pipe 166 with the first texture layer indicator. Observe that the texture layers of the first primitive P₀set the standard for the whole batch and are referred to as the batch texture layers.

[0087] After adding the primitive P_Kto the batch and sending it to render pipe 166 with the first layer indicator, vertex processor 162 may receive and process the next primitive P_K+1.

[0088] It is noted that the layer agreement test and the cumulative size test may be performed sequentially or in parallel.

[0089] If either or both of the layer agreement test and the cumulative size test fails, vertex processor 162 may store the K^thprimitive P_Kin a temporary buffer TMP, reinitialize the cumulative sum to zero, and initiate a “finish up” procedure on the current batch. Note that the K^thprimitive P_Kis temporarily set aside (in the temporary buffer) and not added to the current batch. Thus, the current batch includes primitives P₀through P_K−1.

[0090] Vertex processor 162 performs the finish up procedure on the current batch as follows. Let L₀, L₁, L₂, . . . , L_M−1denote the batch texture layers, i.e. the texture layers specified by primitive P₀, where M is the number of batch texture layers. Texture layer L₀is the first texture layer referred to above. For each texture layer L_Iof the second and succeeding batch texture layers (i.e. for each value of the index I in the range 1, 2, . . . , M−1), vertex processor 162:

[0091] reads each primitive P_Jin the batch buffer, and

[0092] sends the primitive P_Jto render pipe 166 with a texture layer indicator

[0093] corresponding to texture layer L_I, where J runs through the range 0, 1, 2, . . . , K−1, where K is the number of primitives in the batch buffer.

[0094] In other words, vertex processor 162 cycles through the batch buffer (M−1) times. Each cycle corresponds to a different one of the second and succeeding batch texture layers. Note that each primitive of the batch will have been sent down to the render pipe with the first layer indicator corresponding to first layer L₀as it is added to the batch and thus prior to the finish up procedure.

[0095] After completing the finish up procedure on the current batch, vertex process 162 may flush the batch buffer, i.e. reinitialize the list of primitives stored in the batch buffer to the empty list, and restart a new batch with the primitive stored in the temporary buffer.

[0096] As described above, render pipe 162 may receive multiple versions of the batch primitives. Each version of a primitive includes or is associated with a texture layer indicator. The version corresponding to primitive P_Jand texture layer L_Iis denoted P_J/L_I. Render pipe 166 may receive the primitive versions in the order:

[0097] P₀/L₀, P₁/L₀, P₂/L₀, . . . , P_K−1/L₀,

[0098] P₀/L₁, P₁/L₁, P₂/L₁, . . . , P_K−1/L₁,

[0099] P₀/L₂, P₁/L₂, P₂/L₂, . . . , P_K−1/L₂,

[0100] P₀/L_M−1, P₁/L_M−1, P₂/L_M−1, . . . , P_K−1/L_M−1,

[0101] where M is the number of texture layers to be applied to the current batch. In response to the primitive versions P₀/L₀, P₁/L₀, P₂/L₀, . . . , P_K−1/L₀corresponding to the first layer L₀, render pipe 166 generates samples for the primitives, and the texture pipe applies texture values corresponding to layer L₀to the samples and stores the updated samples in texture accumulation buffer 181. In response to the primitive versions P₀/L_I, P₁/L_I, P₂/L_I, . . . , P_K−/L₁for any layer L₁beyond layer L₀, the texture pipe reads the samples from the texture accumulation buffer 181, applies texture values corresponding to layer L_Ito the samples, and stores the updated samples in texture accumulation buffer 181 once again.

[0102] In response to receiving version P_J/L₀corresponding to batch primitive P_Jand the first texture layer L₀, where J is any value in the range 0, 1, 2, . . . , K−1, render pipe 166 may determine a set of fragments (i.e. bins) which geometrically intersect the primitive P_J. For each intersecting fragment F_v, render pipe 166 may

[0103] (a) send the fragment F_vto sample generator and evaluator 174 for sample processing; and

[0104] (b) send a request to the texture pipe for a texture value t0_vcorresponding to first texture layer L₀and fragment F_v.

[0105] In response to receiving the fragment F_v, sample generator and evaluator 174:

[0106] (1) populates the fragment F_vwith sample positions S_vk;

[0107] (2) determines which of the sample positions S_vkreside interior to the primitive P_J;

[0108] (3) computes an initial color vector C0_vkfor each sample position S_vkinterior to the primitive P_J; and

[0109] (4) sends the fragment F_vincluding the sample color vectors C0_vkcorresponding to the interior sample positions S_vkto texture environment 180.

[0110] The initial color vectors C0_vkmay be computed based on a spatial interpolation of color. For example, in the case of a triangle, the initial color vectors may be interpolated from color vectors associated with the triangle vertices. The index v counts fragments. The index k occuring in the index pair vk counts samples within a given fragment F_v.

[0111] In response to request (b), the texture pipe accesses texture layer L₀stored in texture memory 20 to obtain texels, and performs filtering (e.g. bilinear or trilinear filtering) on the texels to generate the texture value t0_v. The “0” in the notation t0_vis a reminder that the texture value t0_vis derived from texture layer L₀. The “v” in the notation t0_vis a reminder that the texture value corresponds to fragment F_v.

[0112] Primitive version P_J/L₀may include texture coordinate data corresponding to primitive P_Jand texture layer L₀. Texture address unit 168 may receive the texture coordinate data and the fragment address of fragment F_vfrom render pipe 166, and responsively generate read addresses (in the address space of texture memory 20) for the texels from layer L₀which contribute to the computation of texture value t0_v.

[0113] Texture filter 170 uses the read addresses to access the texels from layer L₀and performs filtering (e.g. bilinear or trilinear filtering) on the texels to generate the texture pixel transfer unit 182 to texture environment 180.

[0114] Texture environment 180 receives (i) the initial color vectors C0_vkfor the interior sample positions S_vkof the intersecting fragment F_v, and (ii) the texture value t0_v. Interior sample positions S_vkare the sample positions in fragment F_vwhich fall inside the current primitive P_J. Texture environment 180 applies the texture value t0_vto the initial color vectors C0_vkof the interior sample positions S_vkto generate resultant color vectors R0_vk. For example, texture environment 180 may apply the texture value t0_vto each initial color vector C0_vkto generate the corresponding resultant color vector R0_vk. The resultant color vectors R0_vkfor the interior samples of fragment F_vare stored in TAB 181.

[0115] Any of a variety of mathematical formulas may be used by texture environment 180 to apply the texture values to the color vectors. Texture environment 180 may be programmable to employ different formulas at different times. Alternatively, texture environment 180 may employ a formula with fixed mathematical structure but programmable parameters. In one embodiment, texture environment 180 may comprise dedicated circuitry for implementing one or more texturing formulas.

[0116] In one set of embodiments, the initial color vector C0_vkcontains a transparency value in addition to red, green and blue color values (e.g. diffuse color values). Other per-sample attributes may be included as well.

[0117] Render pipe 166 and the texture pipe process each of the primitive versions P₀/L₀, P₁/L₀, P₂/L₀, . . . , P_K−1/L₀corresponding to texture layer L₀as described above for the generic member P_J/L₀. The fragments corresponding to each of the versions in this layer L₀group are stored in texture accumulation buffer 181. Because the cumulative sum of fragment sizes of the primitives in the batch is less than or equal to the fragment capacity of the texture accumulation buffer 181, the texture accumulation buffer 181 may advantageously avoid an overflow condition.

[0118] In response to receiving version P_J/L₁corresponding to batch primitive P_Jand the second texture layer L₁, render pipe 166 may determine a set of fragments (i.e. bins) which geometrically intersect the primitive P_J. For each intersecting fragment F_v, render pipe 166 may

[0119] (a) send an indication of the fragment F_vto texture environment 180; and

[0120] (b) send a request to the texture pipe for a texture value t1_vcorresponding to second texture layer L₁and fragment F_v.

[0121] In response to request (b), the texture pipe accesses texture layer L₁stored in texture memory 20 to obtain texels, and performs filtering (e.g. bilinear or trilinear filtering) on the texels to generate the texture value t1_v. The “1” in the notation t1_vis a reminder that the texture value t1_vis derived from texture layer L₁. The “v” in the notation t1_vis a reminder that the texture value corresponds to fragment F_v.

[0122] Primitive version P_J/L₁may include texture coordinate data corresponding to primitive P_Jand texture layer L₁. Texture address unit 168 may receive the texture coordinate data and the fragment address of fragment F_vfrom render pipe 166, and responsively generate read addresses (in the address space of texture memory 20) for the texels from layer L₁which contribute to the computation of texture value t1_v.

[0123] Texture filter 170 uses the read addresses to access the texels from layer L₁and performs filtering (e.g. bilinear or trilinear filtering) on the texels to generate the texture value t1_v. The texture value t1_vmay then be fed through pixel transfer MUX 178 and pixel transfer unit 182 to texture environment 180.

[0124] Texture environment 180 may read the color vectors R0_vkfor the interior sample positions S_vkof the intersecting fragment F_vfrom texture accumulation buffer 181, and receive the texture value t1_vgenerated by texture filter 170. Texture environment 180 applies the texture value t1_vto the color vectors R0_vkof the interior sample positions S_vkto generate resultant color vectors R1_vk. For example, texture environment 180 may apply the texture value t1_vto each color vector R0_vkto generate the corresponding resultant color vector R1_vk. The resultant color vectors R1_vkfor the interior samples of fragment F_vare then stored in TAB 181.

[0125] In some embodiments, texture environment 180 overwrites fragment F_vin TAB 181 with the updated color information, i.e. overwrites the color vectors R0_vkwith the updated color vectors R1_vk.

[0126] Render pipe 166 and the texture pipe process each of the primitive versions P₀/L₁, P₁/L₁, P₂/L₁, . . . , P_K−1/L₁corresponding to texture layer L₁as described above for the generic member P_J/L₁. The fragments corresponding to each of the versions in this layer L₁group are stored in texture accumulation buffer 181. Again, because the cumulative sum of fragment sizes of the primitives in the batch is less than or equal to the fragment capacity of the texture accumulation buffer 181, the texture accumulation buffer 181 may advantageously avoid an overflow condition.

[0127] Texture layers L₂, L₃, . . . , L_M−1(i.e. the third through last layers) may be applied to the batch primitives in the same fashion as the second layer L₁. This is illustrated by the following pseudo-code fragment for primitive version P_J/L_Icorresponding to primitive P_Jand layer L_I, where I is any integer in the range 1, 2, . . . , M−1.

[0128] For each fragment F_vintersecting the primitive P_J:

[0129] Texture pipe generates texture value tI_vfor fragment F_vby accessing and filtering appropriate texels from layer L₁of texture memory 20;

[0130] Texture environment reads fragment F_vfrom TAB 181;

[0131] Texture environment applies texture value tI_vto sample color vectors R(I−1)_vkcomprised within fragment F_vand corresponding to interior samples to obtain resultant sample color vectors RI_vk;

[0132] Texture environment stores resultant sample color vectors RI_vkin TAB 181.

[0133] Thus, texture layer L₀is applied to sample colors received from sample generator and evaluation unit, whereas layers L₁though L_M−1, are applied to sample colors received from TAB 181.

[0134] In the application of the last texture layer L_M−1, texture environment 180 may store the final sample color vectors R(M−1)_vkinto TAB 181 and send pointers to the fragments F_vto fragment processor 184 (i.e. pointers in the TAB address space). Fragment processor 184 may forward the fragments (including the final sample color vectors R(M−1)_vkto the sample area of frame buffer 22. Alternatively, texture environment 180 may send the final sample color vectors R(M−1)_vkdirectly to fragment processor 184 and thus storage of final sample color vectors R(M−1)_vkin TAB 181 may be avoided.

[0135] In general, the texture pipe processes all the batch primitives with respect to texture layer L_Ibefore proceeding to texture layer L_I+1. This strategy of processing fragments of the batch primitives in an inner loop and the texture layers as the outer loop significantly reduces thrashing of texture memory 20. The large magnitude address jump between texture layers may advantageously occur less often. Successive fragments within a texture layer corresponding to a given batch primitive induce relatively small address jumps in the texture memory address space because the fragments are spatially localized to a neighborhood defined by the primitive. Successive fragments within a texture layer corresponding to distinct primitives of a batch may induce address jumps which are small relative to the jumps between texture layers, especially if the distinct primitives are close to each other spatially. Thus, there may be a significantly decreased probability of encountering page misses and cache misses for the texture accesses to texture memory 20 associated with fragments of a batch relative to an alternate strategy of cycling through texture layers per primitive or per fragment per primitive.

[0136] It is noted that the processing methodology described in the embodiments above may be used for effects other than traditional texturing. For example, one of the texture layers may be interpreted as an illumination map which modulates the intensity of rendered samples and/or fragments. Thus, the texture layers stored in texture memory 20 should be broadly interpreted to include any of various types of image information usable to modify pixel or sample colors.

[0137] In one set of embodiments, hardware accelerator 18 is an application specific integrated circuit (ASIC) which is optimized for the sample and texture processing operations described herein. TAB 181 may be implemented as on-chip SRAM.

[0138] Multitexturing with Deferred Sample Generation

[0139] In a second set of embodiments, texture layers are applied to the batch primitives at fragment resolution (not at sample resolution), stored in TAB 181 at fragment resolution, and samples are generated for fragments after the penultimate texture layer (i.e. layer L_M−2) has completed. Thus, the generation of samples may operate in parallel with the application of the last texture layer L_M−1to the batch primitives at fragment resolution. The samples are generated at sample positions interior to the fragments. The final per-fragment color vectors resulting from the application of the last texture layer are applied to the samples to generate per-sample color vectors.

[0140] In response to version P_J/L₀corresponding to batch primitive P_Jand the first layer L₀, render pipe 166 may generate a single color vector C0_vfor each fragment F_vthat intersects the batch primitive P_J. Thus, color vector C0_vmay be referred to as a fragment color vector. Texture environment 180 receives the texture value t0_vcorresponding to layer L₀for each fragment F_vfrom texture filter 170, and applies the texture value t0_vto the corresponding fragment color vector C0_v. The resulting fragment color vector R0_vis stored into TAB 181.

[0141] When the fragments F_vcorresponding to all the primitives of the current batch have been processed with respect to the first layer L₀, i.e. the primitive versions P₀/L₀, P₁/L₀, P₂/L₀, . . . , P_K−1/L₀have been processed, texture environment 180 processes the primitive versions P₀/L₁, P₁/L₁, P₂/L₁, . . . , P_K−1/L₁with respect to second layer L₁as follows. Given the primitive version P_J/L₁corresponding to primitive P_Jand second layer L₁, texture environment 180 receives the texture value t1_vcorresponding to second texture layer L₁for each fragment F_vintersecting the primitive P_Jfrom texture filter 170, reads the fragment color vector R0_vcorresponding to fragment F_vfrom TAB 181, and applies the texture value t1_vto fragment color vector R0_vto generate resultant fragment color vector R1_v. The resultant fragment color vector R1_vis stored into TAB 181.

[0142] Texture layers L₂through L_M−1, are applied to the batch primitives at fragment resolution in a similar fashion to the second layer L₁. Let I be any integer in the range one through M−2. When the fragments F_vcorresponding to all the primitives of the current batch have been processed with respect to the layer L_I−1, i.e. the primitive versions P₀/L_I−1, P₁/L_I−1, P₂/L_I−1, . . . , P_K−1/L_I−1have been processed, texture environment 180 processes the primitive versions P₀/L_I, P₁/L_I, P₂/L_I, . . . , P_K−1/L_Iwith respect to layer L_Ias follows. Given primitive version P_J/L_Icorresponding to primitive P_Jand layer L_I, texture environment 180 receives the texture value tI_vcorresponding to layer L_Ifor each fragment F_vintersecting the primitive P_Jfrom texture filter 170, reads the fragment color vector R(I−1)_vcorresponding to fragment F_vfrom TAB 181, and applies the texture value tI_vto the fragment color vector R(I−1)_vto generate a resultant fragment color vector RI_v. The resultant fragment color vector RI_vis stored into TAB 181.

[0143] When the fragments F_vcorresponding to all the primitives of the current batch have been processed with respect to the penultimate layer L_M−2, i.e. the primitive versions P₀/L_M−2, P₁/L_M−2, P₂/L_M−2, . . . , P_K−1/L_M−2have been processed, texture environment 180 processes the primitive versions P₀/L_M−1, P₁/L_M−1, P₂/L_M−1, . . . , P_K−1/L_M−1with respect to the last layer L_M−1as follows. Given primitive version P_J/L_M−1, sample generation and evaluation unit 174:

[0144] (1) populates each fragment F_vintersecting the primitive P_Jwith sample positions S_vk;

[0145] (2) determines which of the sample positions S_vkreside interior to the primitive P_J, and sets a valid flag to indicate the interior or exterior status of each sample position S_vk;

[0146] (3) computes a z coordinate value for each interior sample position S_vkbased on a spatial interpolation of data associated with the primitive P_J(e.g., in the case of triangle, an interpolation of the z values at the triangle vertices);

[0147] (4) forwards the fragment F_vincluding the sample positions S_vkand corresponding z values and valid flags to texture environment 180.

[0148] Texture environment 180 reads the fragment color vector R(M−2)_vcorresponding to fragment F_vfrom TAB 181, receives texture value t(M−1)_vfrom texture filter 170, and applies the texture value t(M−1)_vto fragment color vector R(M−2)_vto obtain a resultant fragment color vector R(M−1)_v. The resultant fragment color vector R(M−1)_vmay then be assigned to all the interior samples of fragment F_v, i.e. to all sample positions S_vkwhich reside interior to fragment F_v. The fragment F_v(now including the final sample color vectors of the interior samples) may be forwarded to fragment processor 184. Fragment processor 184 may store the fragment in a sample area of frame buffer 22. Frame buffer 22 uses the z values of the samples in the fragment F_vto perform z buffering.

[0149] In the first set of embodiments described above, color is initially interpolated to sample resolution, and color is updated and stored in TAB 181 at sample resolution, although texture values are computed only at fragment resolution. In the second set of embodiments, color is initially interpolated to fragment resolution, and color is updated and stored in TAB at fragment resolution until the last texture layer is to be applied. At this last stage, samples are generated, the last texture layer is applied at fragment resolution, and the final per-fragment colors are assigned to all valid samples in their corresponding fragments.

[0150] FIG. 8 illustrates one set of embodiments of a method for rendering displayable images. In step 310, a processor (e.g. vertex processor 162) receives a stream of primitives. Each primitive in the stream specifies one or more texture layers among those stored in texture memory 20 which are to be applied to the primitive.

[0151] In step 320, the processor adds a first primitive P₀of the stream to a batch list, i.e. stores the first primitive in a batch buffer, and dispatches the first primitive P₀to a rasterization unit with a texture layer request corresponding to the first texture layer specified by the first primitive P₀. For example, the rasterization unit may include render pipe 166 and the texture pipe of hardware accelerator 18. In response to receiving the first primitive P₀with the first texture layer request, the rasterization unit applies textures from the first texture layer to fragments (or samples) associated with the first primitive P₀and stores the fragments (or samples) in texture accumulation buffer 181.

[0152] In step 330, the processor accesses the next primitive P_Jof the stream. In step 340, the processor determines if the primitive P_Jspecifies the same set of texture layers as the first primitive P₀. If primitive P_Jdoes specify the same set of texture layers as the first primitive P₀, the processor performs step 350. Otherwise, the processor performs step 345.

[0153] In step 350, the processor updates a cumulative sum S according to the relation S=S+SizeEst(P_J), where SizeEst(P_J) is an estimate for the size (e.g. the fragment size) of the primitive P_J. The estimate may be an upper bound for the size. Note that a number U is said to be an upper bound for X when the X is less than or equal to U.

[0154] In step 360, the processor compares the cumulative sum S to a size limit. The size limit may equal the storage capacity (measured in fragments or samples) of texture accumulation buffer 181. If the cumulative sum S is less than or equal to the size limit, the processor performs step 370. If the cumulative sum S is greater than the size limit, the processor performs step 345.

[0155] In step 370, the processor adds the primitive P_Jto the batch list, i.e. stores the primitive into the batch buffer, and dispatches the primitive P_Jto the rasterization unit with a texture layer request corresponding to the first texture layer specified by the first primitive P₀. In response to receiving the primitive P_Jwith the first texture layer request, the rasterization unit applies textures from the first texture layer to fragments (or samples) associated with the primitive P_Jand stores the fragments (or samples) in texture accumulation buffer 181. After step 370, the processor performs step 330.

[0156] As indicated above, the processor performs step 345 if the layer agreement test of step 340 fails or if the size limit test of step 360 fails. In step 345, the processor performs a “finish-up” procedure on the primitives of the batch. In the finish-up procedure, the processor cycles through the batch buffer repeatedly dispatching the primitives P₀, P₁, P₂, . . . , P_K−1, of the batch list to the rasterization unit. In each cycle, the processor dispatches the primitives with texture layer requests corresponding to one of the texture layers L_Ispecified by the first primitive. In the first cycle, the processor dispatches the primitives P₀, P₁, P₂, . . . , P_K−1with requests corresponding to the second texture layer specified by the first primitive. (The primitives are dispatched with first texture layer requests as they are being added to the batch list.) In the second cycle, the processor dispatches the primitives P₀, P₁, P₂, . . . , P_K−1, with requests corresponding to the third texture layer specified by the first primitive. The last cycle corresponds to the last texture layer specified by the first primitive.

[0157] In response to receiving primitive P_Jwith a texture layer request corresponding to texture layer L_I, the rasterization unit applies textures from the texture layer L_Ito fragments (or samples) associated with the primitive P_Jand stores the fragments (or samples) in texture accumulation buffer 181.

[0158] After step 345 is completed, the processor performs step 346. In step 346, the buffer list is reinitialized, the cumulative sum S is set to zero, and the primitive P_Jbecomes the first primitive of the new buffer list. After step 345, the processor performs step 320 again.

[0159] Size Estimation for Graphics Primitives

[0160] As described above, graphics system 112 may be configured to apply multiple texture layers to a batch of graphics primitives (such as triangles, dots, lines or polygons). Render pipe 166 identifies fragments that intersect batch primitives, and the texture pipe (including texture environment 180) applies the multiple layers of texture to the intersecting fragments or samples within the intersecting fragments. Texture environment 180 stores fragment or sample color information for the intersecting fragments in TAB 181 between the application of successive texture layers.

[0161] The storage capacity (i.e. size) of TAB 181 implies a limit on the size of a batch of primitives processed by the texture pipe. To prevent overflow of TAB 181, a cumulative sum of fragment sizes (or estimates of fragment sizes) of primitives in a batch may be limited to be less than or equal to the fragment capacity of TAB 181. The fragment size of a primitive is the number of fragments that geometrically intersect the primitive.

[0162] In some embodiments, TAB 181 may store multiple samples per fragment. In these embodiments, TAB 181 has a fragment capacity and a sample capacity. The sample capacity is equal to the fragment capacity times the number of samples allocated per fragment. In other embodiments, TAB 181 stores color information for fragments and not for samples. For example, TAB 181 may store a single RGB color vector per fragment.

[0163] In one embodiment, the storage capacity of TAB 181 is equal to 1024 entries. An entry may store color information for a fragment. Alternatively, an entry may store color information for a sample within a fragment. TAB 181 may have any desired storage capacity subject to the fundamental limitations of cost, die area, complexity, etc. Powers of two are favored for the TAB capacity.

[0164] Vertex processor 162 may generate a conservative size estimate for each received primitive, i.e. may report a value for each primitive which is greater than or equal to the actual number of fragments intersecting the primitive. Vertex processor 162 may implement any of a variety of size estimates. Typically the computational effort for a size estimate depends on the accuracy attained by the estimate. In other words, it is computationally more expensive to obtain a size estimate which stays close to the actual size of the primitive than an estimate which reports a generous upper bound for the actual size. Accurate estimates typically require more complex arithmetic hardware—more multipliers, adders and subtractors. Thus, the size estimate employed by vertex processor 162 may depend on the time budget (e.g. the number of clock cycles) allowed for the size estimate computation and/or the amount of die area allocated for the size estimation circuitry. The actual size of a primitive may be defined as the number of fragments which geometrically intersect with the primitive. For example, in FIG. 7, eleven fragments geometrically intersect with the given triangle. Thus, the actual size of the triangle is 11.

[0165] Much of the following discussion focuses on size estimation for triangles. However, the size estimation methodologies disclosed herein naturally generalize to other primitives such as polygons, lines and dots.

[0166] In one set of embodiments, vertex processor 162 may generate the size estimate for a current triangle as follows. Vertex processor 162 may compute the coordinates for an axis-aligned bounding box that minimally contains the current triangle. The term “axis-aligned” means that the bounding box has sides parallel to the coordinate axes of sample space. The coordinates of the minimal bounding box may be computed by determining the minimum and maximum of the horizontal and vertical coordinates of the triangle vertices:

[0167] X_min=min{X₁,X₂,X₃}

[0168] X_max=max{X₁,X₂,X₃}

[0169] Y_min=min{Y₁,Y₂,Y₃}

[0170] Y_max=max{Y₁,Y₂,Y₃},

[0171] where (X_i,Y_i) defines the i^thtriangle vertex.

[0172] Furthermore, vertex processor 162 may compute a width W and height H for the minimal bounding box according to the relations:

[0173] W=X_max−X_min

[0174] H=Y_max−Y_min.

[0175] The area of the triangle is (½)WH. Under the assumption that each fragment is a one-by-one square in sample space with edges having integer coordinates, a generic triangle may intersect a number of fragments which is significantly larger than its area (½)WH. For example, a right triangle with vertices at (0,0), (0,10) and (10,10) intersects 55 fragments instead of 50=(½)(10)(10) fragments. In one set of embodiments, this discrepancy is accounted for by computing an estimate E for the area (½)WH, adding a positive integer constant C_marginto the estimate E, and comparing the sum E+C_marginto the TAB fragment capacity. In one embodiment, the estimate E may be the area itself.

[0176] In one set of embodiments, the value of C_marginmay be the (Euclidean or Manhattan distance) perimeter of the triangle. The perimeter accounts for the partial fragments which are touched by the triangle along its edges.

[0177] More generally, the value of C_marginmay be chosen to be any upper bound for the discrepancy between the actual number of intersecting fragments and the triangle area for all possible triangles with actual number less than or equal to the TAB fragment capacity. The value C_marginmay be supplied by a user, system operator, system designer, etc.

[0178] In another set of embodiments, the values of W and H are increased by additive constants so that the new triangle area (½)(W+ΔW)(H+ΔH) is guaranteed to be greater than or equal to the number of intersecting fragments. Thus, vertex processor 162 may perform width and height adjustment according to the relations:

[0179] W=W+ΔW

[0180] H=H+ΔH,

[0181] where ΔW and ΔH are positive constants, and generate an estimate E for the new triangle area (½)WH, and compare the estimate E directly to the TAB fragment capacity.

[0182] In some embodiments, vertex processor 162 may implement the size comparison based on the following analysis. Let W and H be represented as binary words. Let α be the bit position of the leading one in the binary representation of W. The leading one is the one bit that occurs closest to the most significant bit position in the representation of W. Bit positions are counted starting from zero at the least significant bit and increase with each successively more significant bit. The following table gives several examples.

[0183] The table gives examples for eight-bit words. However, a wide variety of word lengths are contemplated for W and H.

[0184] It is a basic mathematical fact that W is less than or equal to 2^α+1. A similar statement may be made for height H. Let β be the bit position of the leading one in the binary representation of H. So H is less than or equal to 2^β+1.

[0185] It follows that the triangle area (½)WH is less than (½)(2^α+1)2^β+1)=2^α+β+1:

[0186] (½)WH<2^α+β+1.

[0187] In other words, 2^α+β+1is an upper bound for the area (½)WH. If the upper bound 2^α+β+1is less than or equal to the TAB fragment capacity N_TAB, the triangle area is automatically smaller than the TAB fragment capacity N_TAB:

[0188] (½)WH<2α+β+1≦N_TAB.

[0189] Let γ be the bit position of the leading one in the binary representation of N_TAB. Then 2^γ≦N_TAB. Because (½)WH<2^α+β+1and 2^γ≦N_TAB, the triangle area is guaranteed to be smaller than the TAB fragment capacity if:

[0190] 2^α+β+1≦2^γ.

[0191] However, the last inequality holds if and only if α+β+1≦γ, or equivalently, α+β<γ.

[0192] Thus, in one set of embodiments, vertex processor 162 may determine leading one positions α and β for width W and height H respectively, and perform the comparison α+β<γ. Observe that this comparison does not require any multipliers, and thus, may be performed quickly.

[0193] In one embodiment, N_TABis equal to a power of 2. In this case, N_TABexactly equals 2^γ.

[0194] In some embodiments, vertex processor 162 may generate upper bounds for W and H which utilize more information than merely the leading one positions α and β respectively. In other words, by creating mantissas of W and H and multiplying the mantissas, vertex processor 162 may more closely match the targeted inequality (½)WH<2^γ. This comes at the expense of the multipliers and barrel shifters needed to implement the refined computation. Let L represent the number of bits in the mantissa for W, and M the number of bits in the mantissa for H. As the numbers L and M increase the implementation cost increases but the estimation accuracy increases. Thus, the mantissa lengths L and M may be chosen to achieve an optimal tradeoff between cost and estimation accuracy. Various embodiments are contemplated with various values for mantissa lengths L and M.

[0195] Batching of Chained Primitives

[0196] It is very common to define “chained” graphics primitives, such as the OpenGL TriStrip, TriFan, etc. These primitives may share vertices. For example, a TriStrip might define five triangles from seven vertices as shown in FIG. 9. The seven vertices V₁-V₇define five triangles Δ₁through Δ₅in a contiguous strip. In general it takes N+2 vertices to define N triangles using a TriStrip or TriFan. The texture layers (and other properties, such as material propeties and color) may be common for all elements of a “chained” primitive such as a TriStrip.

[0197] Although it is possible to simply estimate the area of the strip by computing the sum of the estimated areas of the triangles:

[0198] A_strip=A₁+A₂+A₃+A₄+A₅,

[0199] this methodology may result in an inflated area estimate, i.e. an area estimate which is significantly larger than the actual area of the strip. The extra margin along “internal” edges is double counted (i.e. the margin along the edge v2v3 that is outside triangle Δ₁is inside Δ₂, and vice versa; this overcounting also holds true for edges v3v4, v4v5, v5v6). These pieces of double-counted area can add up over a longer strip to significantly inflate the estimated area for the strip. Texture processing efficiency is negatively impacted because batches don't fill up the TAB.

[0200] In one set of embodiments, a processor (such as vertex processor 162) may directly compute a running estimate of the strip's area instead of a running total of the individual triangle estimates. This approach avoids double counting the fragments along the “internal” edges.

[0201] In one embodiment, the running estimate of the strip's area may be computed as follows. A processor may determine a bounding box for the entire strip from vertex V1 through Vn as each new vertex vertex Vk is added, where n is a positive integer. Let Xk and Yk be the coordinates of vertex Vk. The coordinates Xmin, Xmax, Ymin and Ymax for the bounding box are defined by the relations:

[0202] Xmin=floor(min{X1, X2, . . . , Xn})

[0203] Xmax=cieling(max{X1, X2, . . . , Xn})

[0204] Ymin=floor(min{Y1, Y2, . . . , Yn})

[0205] Ymax=ceiling(max{Y1, Y2, . . . , Yn}).

[0206] Recall that floor(x) is the greatest integer which is less than or equal to x, and ceiling(x) is the smallest integer which is greater than or equal to x. These bounding box coordinates may be computed incrementally, i.e. as each vertex arrives. For example, the values Xmin and Xmax may be initialized based on the vertices V1, V2 and V3 of the first triangle in the strip by computing:

[0207] Xmin=floor(min{x1, x2, x3})

[0208] Xmax=ceiling(max{x1, x2, x3}).

[0209] Then, in response to receiving each vertex V_K, where K runs from four to n, the values Xmin and Xmax may be updated according to the relations:

[0210] Xmin=floor(min{Xk,Xmin})

[0211] Xmax=ceiling(max{Xk,Xmax}).

[0212] The values Ymin and Ymax may be similarly initialized and updated. As a new vertex is added, the new bounding box sides may be the same as the old sides, or, one or more sides may be pushed outwards by the new vertex. While the bounding box may overestimate the strip area by as much as a factor of two, this bounding box estimate is still better than using the sum of the individual triangle bounding boxes, each of which can be 2× overestimated, because the double-counting at the internal edges result in a greater total overestimate.

[0213] In another set of embodiments, the running estimate of the strip's area may be computed based on the equation for the area of a polygon. The area of a N-sided polygon with vertices V₁, V₂, V₃, . . . , V_Nis given by the expression: $\mathrm{PolyArea}=\frac{1}{2}\sum _{k=1}^n\left(x_k{y}_{k+1}-x_{k+1}{y}_k\right),$

[0214] where vertex V_k=(x_k,y_k), and where x_N+1=x₁and y_N+1=y₁. For example, for a six-sided polygon, the polygon area with vertices V1, V2, V3, V4, V5 and V6 is given by the expression:

[0215] ½*((X1*Y2−X2*Y1)

[0216] +(X2*Y3−X3*Y2)

[0217] +(X3*Y4−X4*Y3)

[0218] +(X4*Y5−X5*Y4)

[0219] +(X5*Y6−X6*Y5)

[0220] +(X6*Y1−X1*Y6)).

[0221] Observe that the area A(k) of a polygon generated by vertices V1 through Vk may be expressed as one-half the sum of a homogeneous term H(k) and a balance term B(k), i.e.:

[0222] A(k)=½(H(k)+B(k)),

[0223] where

[0224] $H\left(k\right)=\sum _{j=1}^{k-1}\left(x_j{y}_{j+1}-x_{j+1}{y}_j\right)\mathrm{and}$  B(k)=x_ky₁−x₁y_k.

[0225] The homogeneous term H(k) may be computed incrementally (i.e. as each new vertex arrives). In response to receiving the new vertex V_k+1=(x_k,y_k), the homogeneous term may be updated according to the recursive relation:

[0226] H(k+1)=H(k)+x_ky_k+1−x_k+1y_k.

[0227] The balance term B(k+1) for the new vertex is given by:

[0228] B(k+1)=x_k+1y₁−x₁y_k+1.

[0229] Thus, the updated polygon area A(k+1)=½(H(k+1)+B(k+1)) may be computed with four multiplies and four additions.

[0230] A processor (e.g. vertex processor 162) may initialize the homogenous term after receiving the first two vertices of a chain (e.g. a strip), i.e. vertices V1 and V2, by computing H(2)=(X1*Y2−X2*Y1). Then, for each succeeding vertex, the processor may update the homogeneous term as indicated above, compute the balance term, and compute the updated polygon area using the updated homogeneous term and balance term.

[0231] Note that a primitive (or chain of primitives) may intersect a number of fragments which is larger than the area of the primitive (or chain of primitives) as illustrated by FIG. 10. The triangle V1V2V3 intersects four fragments but has an area which is significantly smaller than four. In some embodiments, a fragment size estimate S for a chain of primitives may be obtained by adding the perimeter of the chain to the polygon area of the chain: S=Perimeter+PolyArea. Adding the perimeter accounts for fragments which are partially covered on the outside edges of the chain. Again, this perimeter computation may be performed incrementally (i.e. as each new vertex arrives). Let P(k) denote the perimeter of the chain defined by vertices V1, V2, V2, . . . , Vk. The perimeter P(k) may be represented as the sum of an first term G(k) and a second term R(k), i.e. P(k)=G(k)+R(k), where: $G\left(k\right)=\sum _{j=1}^{k-1}\mathrm{Length}\left(V_j{V}_{j+1}\right)$  R(k)=Length(V_kV₁).

[0232] The first term measures the length of the path V1, V2, V3, . . . , Vk. The second term measures the length of the return leg (i.e. the line segment) from vertex Vk to vertex V1 that completes the closed circuit around the polygonal chain. The term G(k) is referred to herein as the partial perimeter, and the term R(k) is referred to herein as the perimeter complement. The expression Length(AB) represents the length of the line segment spanning point A and point B.

[0233] In response to receiving a new vertex V_k+1, the processor may update the first term according to the recursive relation:

[0234] G(k+1)=G(k)+Length(V_kV_k+1).

[0235] In addition, the processor may compute the second term according to the relation:

[0236] R(k+1)=Length(V_k+1V₁),

[0237] and then update the chain perimeter according to the relation P(k+1)=G(k+1)+R(k+1).

[0238] In the method of FIG. 8, a processor (such as vertex processor 162) is configured to gather primitives into a batch until a sum of size estimates for the primitives exceeds the TAB fragment capacity. The first primitive which pushes the sum over the TAB fragment capacity gets saved for the next batch, and the current batch is processed (i.e. rendered and textured). However, as described above, the processor may compute an estimate for the fragment size of a chain of primtives (e.g. a strip or a fan) by methods which are more accurate than a sum of size estimates for each the primtives. These more accurate estimates may be computed incrementally as each vertex in a chain is received. Various embodiments are contemplated where step 350 and 360 are modified to operate with these more accurate estimates.

[0239] Thus, step 350 may be more generally described as updating a current size estimate (e.g. fragment size estimate) for the batch based on the new vertex corresponding to the new primitive P_J. And step 360 may be more generally described as comparing the updated fragment size estimate for the batch to the size limit (e.g. the TAB fragment capacity).

[0240] Although the embodiments above have been described in considerable detail, other versions are possible. Numerous variations and modifications will become apparent to those skilled in the art once the above disclosure is fully appreciated. It is intended that the following claims be interpreted to embrace all such variations and modifications. Note the headings used herein are for organizational purposes only and are not meant to limit the description provided herein or the claims attached hereto.