Title of Invention

DEVICE AND METHOD FOR CACHE EFFICIENT GRAPHICS RASTERIZATION AND AN APPARATUS THEREOF

Abstract A cache stores data for use in rasterizing graphics data. The size of the cache is equal to a selected tile size. A process performs the rasterization of the graphics image by subdividing the graphics image into a plurality of sub-blocks. The sub-blocks are processe, based on a block processing order, by further subdivising of the sub-blocks into tiles for those sub-blocks that have graphics image data. The tiles have a size equal to the selected tile size. Data, associated with a tile, is loaded into the cache, and the cache data is utilized to generate pixels for the associated tole of the graphics image.
Full Text FORM 2
THE PATENTS ACT, 1970
(39 of 1970)
&
THE PATENTS RULES, 2003
COMPLETE SPECIFICATION
(See section 10, rule 13)
'CACHE EFFICIENT RASTERIZATION OF GRAPHICS DATA"
QUALCOMM INCORPORATED
an American company of 5775 Morehouse Drive, San Diego, California 92121-1714, United States of America
The following specification particularly describes the invention and the manner in which it is to be performed.

WO 2006/026647

PCT/US2005/030931

-2-
CACHE EFFICIENT RASTERIZATION OF GRAPHICS
DATA
BACKGROUND
Field
[0001] The invention is directed towards a method and apparatus for cache efficient
rasterization of graphics data.
Background
[0002] To prepare a graphic for display or printing, graphics data is rasterized to
convert the graphics data into an array of pixels (bitmap) that is then used to display or print the graphics. Figure 1 shows a conceptual diagram of an environment 100 in which rasterization is performed. The environment 100 includes a micro-processing unit (MPU) 105, a storage device 110, a cache 115, a frame buffer 120, and an output device 125.
[0003] The MPU 105 may comprise a central processing unit (CPU) of a host computer
(e.g., desktop or laptop computer, server, gaming console, cellular telephone, etc.) or be part of a graphics device (e.g., graphics accelerator) dedicated specifically for graphics production or a digital signal processing (DSP) unit tailored to performing digital signal processing algorithms. The storage device 110 may comprise various forms of memory resources, such as a permanent storage device, a mass-storage device, a removable storage device, a volatile read-and-write memory, such as a random access memory
(RAM), etc.

WO 2006/026647 PCT/US2005/0J0931
-3-
[0004] The MPU 105 loads and executes program instructions of an application 130 to
produce streams of graphics data 132. Program instructions of the graphics application 130 and generated graphics data 132 are stored to and read from the storage device 110. The generated graphics data describes a graphic (text or images) to be displayed and can be in various forms, such as equations, coordinates of vectors, vector drawings, etc. Graphics data may include any of several types of data describing a graphic, such as color, texture, depth (z) data.
[0005] After the graphics data 132 is generated, the MPU 105 prepares the graphics
data for display by rasterizing the graphics data to produce a bitmap 135. During the rasterization process, the MPU 105 loads and analyzes the graphics data to produce the bitmap 135. For example, the MPU 105 may analyze depth (z) data to determine which elements of the graphic are visible and which elements of a graphic are occluded (blocked from view by other elements of the graphic). The MPU 105 may also analyze color and texture data to determine the color and texture components of the graphic. Such analysis determinations by the MPU 105 are reflected in the generated bitmap 135.
[0006] The generated bitmap 135 is stored in the frame buffer 120 and is used to
display or print an image on the output device 125 (e.g., a display monitor or printer). The frame buffer 120 is typically an area of memory in a memory resource (such as the storage device 110) used to store a bitmapped graphic while the graphic is being displayed or printed on the output device 125.
[0007] During the rasterization process discussed above, the MPU 105 transfers
graphics data to be rasterized from the storage device 110 to the cache 115 which the
MPU 105 can typically access in a significantly shorter time than it can access the storage device 110. The MPU 105 then loads the graphics data from the cache 115 and

WO 2006/026647 PCT/US2005/030931
rasterizes the graphics data to produce the bitmap 135. If the MPU later requires particular graphics data during the rasterization process, the MPU first determines if the particular graphics data is stored in the cache 115 since the access time to the cache 115 is shorter than to the storage device 110. A "cache hit" occurs if the particular graphics data exists in the cache, whereby the particular graphics data is then retrieved from the cache. A "cache miss" occurs if the particular graphics data does not exist in the cache, whereby the particular graphics data must then be transferred from the storage device 110 to the cache 115 which consumes more time and energy as compared to direct retrieval from the cache 115. As such, it is advantageous for graphics data to be retrieved directly from the cache 115 during the rasterization process as much as possible since this reduces the amount of time and energy needed. This is especially true when rasterization is being performed in a portable device (such as a laptop computer, cellular telephone, etc.) where battery power is at a premium.
[0008] Typically, however, the rasterization process is performed in an inefficient
manner where a large number of graphics data transfers from the storage device to the cache are needed. This is due to this fact that conventional methods of rasterization do not maximize the transfer of graphics data to the cache where most or all of the graphics data transferred to the cache is rasterized before further graphics data is needed from the storage device. Typically then, a significant portion of the graphics data that has been loaded to the cache is not processed and discarded and then replaced by other graphics data that has been loaded from the storage device.
[0009] As such, there is a need for techniques to rasterize graphics data in an efficient
manner where transfers of graphics data from the storage device to the cache are

WO 20(16/026647 PCT/US2005/030931
optimized so that a fewer number of graphics data transfers are needed. This would reduce the time and energy needed to perform the rasterization process.
SUMMARY
[0010] Graphics data, which describes an image, is processed for rasterization. A block
(pixel array) of graphics data is analyzed in a "Z" pattern order based on a binary search subdivision process to determine a rasterization order for sub-blocks (sub-pixel arrays) of the image. In some embodiments, the sides of the block and sub-blocks have a length (in terms of pixels) that is a power of 2. The technique determines an order of analysis for sub-blocks of the image using a recursive process (binary search subdivision process) that recursively divides sub-blocks into further sub-blocks until the sub-blocks match a predetermined tile size. The sides of each resulting sub-block also have a length (in terms of pixels) that is a power of 2. In some conditions, the technique then loads graphics data associated with a sub-block (having a size equal to the tile size) to a cache for rasterization. In some embodiments, pixels of block are rasterized in a "Z" pattern scanning order that is also based on a binary search subdivision process.
[0011] The tile size is determined based on the size of the cache. In some embodiments,
the tile is a square having sides with a length (in terms of pixels) that is a power of 2. In some conditions, the technique loads graphics data for a tile (sub-block) having a predetermined tile size to a cache for rasterization. In some embodiments, the cache size supports the tile size so that all graphics data associated with the tile can be concurrently stored to the cache. In some embodiments, the tile is rasterized from the cache before
other graphics data is loaded to the cache.

WO 2006/026647 PCT/US2005/030931
[0012] Methods of the present invention provide an efficient way to load graphics data
to a cache and rasterize the graphics data from the cache. Since the tile size is based on the cache size, most or all of the graphics data concurrently stored to the cache is rasterized before further graphics data is loaded to the cache from the storage device. As such, data transfers to the cache are optimized and the number of graphics data transfers to the cache is reduced. Also, the order of processing of the sub-blocks of an image is determined by a "Z" pattern order based on a binary search subdivision process which provides an efficient order of analysis and rasterization of the sub-blocks.
[0013] Further, the techniques provide for efficient processing of graphics data through
use of sub-blocks and tiles having sizes (in terms of pixels) that are a power of 2. As such, calculations required in the processing of the graphics data are simplified in that complex binary division operations are reduced and are mostly replaced by simple and
fast shift operations. The simplified shift operations may be used, for example, in the
recursive processes (binary search subdivision process) that recursively divides sub-blocks into further sub-blocks or when determining if a particular sub-block overlaps an image.
BRIEF DESCRIPTION OF THE DRAWINGS
[0014] The novel features of the invention are set forth in the appended claims.
However, for purpose of explanation, several embodiments of the invention are set forth
in the following figures.
[0015] Figure 1 shows a conceptual diagram of an environment in which rasterization
is performed.
[0016] Figure 2 is a flowchart for processing a graphics data stream for rasterization.

WO 2006/026647

PCT/DS2005/030931

[0017] Figures 3 A-B show conceptual diagrams of an example image as it is processed.
[0018] Figure 4 is a flowchart of a process for determining a size and position of a
bounding box enclosing an image to be displayed.
[0019] Figure 5 is a flowchart of a recursive process that analyzes and rasterizes blocks
of graphics data in an efficient "Z" pattern order.
[0020] Figures 6A-E show conceptual diagrams of an example image as it is processed
by the recursive processing technique of Figure 5.
[0021] Figure 7 is a flowchart of a recursive associating process mat analyzes and
specifies a scanning order for pixels of a block to be rasterized.
[0022] Figures 8A-C show "Z" pattern scanning orders 2 x 2,4 x 4, and 8x8 blocks.
[0023] Figure 9 presents a computer system 900 with which some embodiments of the
invention are implemented.
DETAILED DESCRIPTION
[0024] In the following description, numerous details are set forth for purpose of
explanation. However, one of ordinary skill in the art will realize that the invention may be practiced without the use of these specific details. In other instances, well-known structures and devices are shown in block diagram form in order not to obscure the description of the invention with unnecessary detail.
[0025] Graphics data, which describes an image, is processed for rasterization. The
technique analyzes a block (pixel array) of graphics data in a "Z" pattern order based on a binary search subdivision process to determine a rasterization order for sub-blocks (sub-pixel arrays) of the image. In some embodiments, the sides of the block and sub-blocks have a length (in terms of pixels) that is a power of 2. The technique determines

WO 2006/026647 PCT/US2005/030931
an order of analysis for sub-blocks of the image using a recursive processing technique (binary search subdivision process) that recursively divides sub-blocks into further sub-blocks until the sub-blocks match a predetermined tile size. The sides of each resulting
sub-block also have a length (in terms of pixels) that is a power of 2. In some conditions, the technique then loads graphics data associated with a sub-block (having a size equal to the tile size) to a cache for rasterization. In some embodiments, pixels associated with a block are rasterized in a "Z" pattern scanning order that is also based on a binary search subdivision process.
[0026] The tile size is determined based on the size of the cache. In some embodiments,
the tile is a square having sides with a length (in terms of pixels) that is a power of 2. In some conditions, the technique loads graphics data for a tile (sub-block) having a predetermined tile size to a cache for rasterization. In some embodiments, the cache size supports the tile size so that all graphics data associated with the tile can be concurrently stored to the cache. In some embodiments, the tile is rasterized using the cache data before other graphics data is loaded into the cache.
[0027] The techniques, disclosed herein, provide an efficient way to load graphics data
to a cache and rasterize the graphics data from the cache. Since the tile size is based on the cache size, most or all of the graphics data concurrently stored to the cache is rasterized before further graphics data is loaded to the cache from the storage device. As such, data transfers to the cache are optimized and the number of graphics data transfers to the cache is reduced. Also, the order of processing of the sub-blocks of an image is determined by a "Z" pattern order based on a binary search subdivision process which provides an efficient order of analysis and rasterization of the sub-blocks.

WO 2006/026647

PCT/US2005/030931

[0028] Further, the techniques provide for efficient processing of graphics data through
use of sub-blocks and tiles having sizes (in terms of pixels) that are a power of 2. As such, calculations required in the processing of the graphics data are simplified in that complex binary division operations are reduced and are mostly replaced by simple and fast shift operations. The simplified shift operations may be used, for example, in recursive processing (binary search subdivision process) that recursively divides sub-blocks into further sub-blocks or when determining if a particular sub-block overlaps an image.
[0029] The description of the invention below includes a general technique for
processing graphics data for rasterization, as discussed in Section I. The description also includes recursive processing that processes sub-blocks of an image according to a "Z" pattern order based on a binary search subdivision process, as discussed in Section EL The description further includes a recursive associating technique that specifies a scanning order for pixels of block according to a "Z" pattern order based on a binary search subdivision process, as discussed in Section HI.
[0030] Section I: Processing Graphics Data for Rasterization
[0031] Figure 2 is a flowchart of a general technique 200 for processing a graphics data
stream for rasterization. The general technique 200 analyzes an image (as described by graphics data) in a "Z" pattern order to determine a rasterization order for sub-blocks of the image. The general technique 200 is used in conjunction with an application that generates a graphics data stream, a storage device that stores the generated graphics
data, and a cache that temporarily stores portions of graphics data for rasterization. The general technique 200 is described in relation to Figures 3A-B. Figures 3A-B show

WO 2006/026647

PCT/US2005/030931

conceptual diagrams of an example image as it is processed by the general technique 200.
[0032] The process begins by determining (at 205) a tile size (pixel array size) based on
the size of a cache that will be used to temporarily store graphics data during processing of graphics data by the general technique 200. The tile size is correlated to the cache size and is determined so that the cache size can support the tile size (i.e., the cache size can concurrently store all data associated with a single tile). The tile size is determined by the amount of data required for each pixel of the tile (which varies depending on color quality, presence of texture data or depth data, etc.).
[0033] The tile size may also be adjusted/affected by the application generating the
graphics data and the size of triangle images used by the application to generate images. Typically, an application generates graphics data describing an image as a composite of multiple triangle images. The size of the triangle images used to compose an image varies depending on the application. In some embodiments, the determined tile size is reduced for applications using relatively small triangle images and increased for applications using relatively large triangle images.
[0034] In some embodiments, the tile is a square with sides having a length (as
measured in pixels) that is a power of 2 (2l), the tile comprising a 2*x 2l pixel array. As used herein, a tile refers to a pixel array of a predetermined size. However, as used herein, a tile may also refer to a sub-block of an image having a size (in terms of pixels) matching the predetermined size of the tile.
[0035] The general process 200 then receives (at 210) graphics data (from the graphics
data stream) for an a x a pixel array having a predetermined size. Figure 3A shows a conceptual diagram of an example image 310 of a received pixel array 305. In the

WO 2006/026647 PCT/US2005/030931
-11-
example of Figure 3A, the received pixel array 305 is a 32 x 32 array containing a
triangle image 310 to be displayed.
[0036] The process 200 then determines (at 220) a size and position of a bounding box
that encloses the image. In some embodiments, the bounding box is a square with sides
having a length (as measured in pixels) that is a power of 2. Figure 3B shows a
conceptual diagram of an example bounding box 315 enclosing the image 310. In the
example of Figure 3B, the bounding box 315 comprises a 16 x 16 pixel array (having
sides of 2k pixels, where k = 4). A process 400 for determining the size and position of
the bounding box 315 is discussed below in relation to Figure 4.
[0037] The process 200 then determines (at 225) whether the size (in terms of pixels) of
the bounding box is equal to the tile size (determined at step 205). If so, the process 200 loads (at 230) graphics data associated with the bounding box and describing an image within the bounding box from the storage device to the cache. The process then rasterizes (at 235) the image contained within the bounding box (as described by the associated graphics data loaded to the cache). The image of the bounding box can be rasterized without further data loads from the storage to the cache since the cache size supports the bounding box size. This is due to the fact that since the cache size supports the tile size, it also supports the bounding box size since it has been determined (at 225 - Yes) that the bounding box size is equal to the tile size. In some embodiments, the entire image of the bounding box is rasterized before more graphics data is loaded to the cache.
[0038] The process then determines (at 237) whether there is more graphics data in the
graphics data stream to be processed. If so, the process continues at step 210 where it receives graphics data for a next a x a pixel array. If not, the process ends.

WO 2006/026647

PCT/US2005/030931

[0039] If it is determined (at 225 - No) that the size of the bounding box is not equal to
the tile size, the process then sets (at 240) a current block as the bounding box. The process then calls (at 245) a recursive processing technique (as described below in relation to Figure 5) and passes the current block (bounding box) of graphics data to the recursive processing technique. The recursive processing technique analyzes and rasterizes sub-blocks of the current block in an efficient order. In some embodiments, the recursive processing technique processes sub-blocks of the current block according to a "Z" processing pattern based on a binary search subdivision process. The process then determines (at 237) whether there is more graphics data in the graphics data stream to be processed. If so, the process continues at step 210 where it receives graphics data for a next a x a pixel array. If not, the process ends.
[0040] Figure 4 is a flowchart of a process 400 for determining a size and position of a
bounding box enclosing an image to be displayed. The process 400 comprises step 220 of the general process 200. The process 400 is described in relation to Figure 3A-B. Although the process 400 relates to an image that is a triangle, one with knowledge in the arts will realize that the process 400 can be easily adapted to determine bounding
boxes enclosing images of other shapes or forms. Also, the process 400 assumes that the triangle image is specified by horizontal and vertical coordinates ((x1y1), x2y2), x3y3)) of the vertices of the triangle. One with knowledge in the arts will realize, however, that the triangle image may be specified in other ways.
[0041] In some embodiments, the bounding box is a square having the smallest size
possible to enclose the image but yet also has sides with a length (in terms of pixels) that are power of 2 (i.e., is the smallest square with sides that are a power of 2 that

WO 2006/026647 PCT/US2005/030931
-13-
encloses the image). The length of a side of the bounding box is expressed as 2 so that
the bounding box comprises a 2kx 2k pixel array.
[0042] The process 400 begins by identifying (at 405) the horizontal and vertical
coordinates of the vertices of the triangle image ((x1y1), x2y2), x3y3))- In some
embodiments, the horizontal and vertical coordinates are in terms of pixel coordinates
of the pixel array that contains the triangle image. An example of this step is shown in
Figure 3 A.
[0043] The process then determines (at 410) the minimum and maximum horizontal and
vertical coordinates of the identified vertices. In equation form, the process determines
the following:
[0044] xtlin=min(x1,x2,x3),
[0045] Xmax=max (x1,x2,x3)
[0046] jw = min (y1, y2,y3) and
[0047] y™ = max (y1, y2, y3).
[0048] For example, for the image 310 shown in Figure 3A, the process may determine
the following: xmin =x1, xmax=x3, ymin = Y3, and ymax,=y2.
[0049] The process then determines (at 415) the span (s) of the image. The span is the
longer of the horizontal length (as measured in pixels) or the vertical length (as measured in pixels) of the image. In equation form, span (s) is expressed as: s = max (Xmax - Xmin, Ymax – ymin). For example, for the image 310 shown in Figure 3A, the process would determine the following: s = max (x3-x1,y2-y3)As such, in the example of Figure 3A, the horizontal length of the image determines the span as it is longer than the vertical length of the image.

WO 2006/026647 PCT/US2005/030931
{0050] The process then determines (at 420) a number k such that: 2k-l value of k determines the size of the bounding box where the bounding box comprises a 2k x 2k pixel array and has a side of length 2k. For example, as shown in Figure 3B, the
value of k is determined to be 4 so that the sides of the bounding box 315 are 16 pixels
long (the bounding box 315 comprising a 16 x 16 pixel array).
[0051] The process then determines (at 425) the position of the bounding box. In some
embodiments, the process does so by determining a number xo such that:
10052] xo = 2t n;
[0053] x0 [0054] 2,(n+l)>xmin.
[0055] The process also determines a number yo such that:
[0056] y0 = 2X m;
[0057] yo [0058] 2t(m+l)>ymin
[0059] The process then identifies the four vertices of the bounding box with the
following coordinates:
[0060] (xo,y0);
[0061] (x0+2k,y0);
[0062] (x0,yQ + 2*); and
[0063] (x0+2k,yo+2k).
[0064] The vertices and position of the bounding box is determined so as to enclose the
entire triangle image (as shown in the example of Figure 3B). The process then ends.
[0065] Section II: Recursive Processing for Analyzing and Rasterizing Sub-Blocks
of an Image

WO 2006/026647 PCT/US2005/030931
-\S-
[0066] Figure 5 is a flowchart of a recursive processing technique 500 that analyzes
and rasterizes blocks of graphics data in an efficient "Z" pattern order. In some embodiments, the recursive processing technique selects sub-blocks of graphics data to analyze and possibly rasterize in a particular order using a binary search subdivision process. The technique 500 is used in conjunction with an application that generates graphics data, a storage device that stores the generated graphics data, and a cache that temporarily stores data used for rasterization. Figure 5 is described in relation to Figures 6A-E. Figure 5 shows conceptual diagrams of an example image (as described by a block of graphics data) as it is processed by the recursive processing technique 500.
[0067] The recursive processing technique is called by the general process 200 of
Figure 2 at step 245 and receives a current block (bounding box) having an image (as described by the graphics data associated with the current block) from the general process 200. Figure 6A shows a conceptual diagram of a current block 605 that comprises the bounding box 315 from Figure 3B. As shown in example of Figure 6A, the current block 605 comprises a 16 x 16 pixel array having a triangle image 610 for rasterization and display.
[0068] The recursive processing technique 500 begins by dividing (at 505) the current
block to produce sub-blocks, (i.e., by dividing the pixel array of the current block to produce sub-pixel arrays). In some embodiments, the current block is divided vertically in the middle and horizontally in the middle to produce four equal-sized sub-blocks. As discussed above in relation to Figure 2, the current block is a square having sides with a length (as measured in pixels) of a power of 2. As such, each sub-block will also be a square with sides having a length with a power of 2. In the example shown in Figure

WO 2006/026647 PCT/US2005/030931
6B, the current block is a 16 x 16 pixel array so that each produced sub-block is an 8 x 8 pixel array.
[0069] The technique then associates (at 507) a processing order with each produced
sub-block according to a "Z" pattern (as illustrated in Figure 6B). In other words, the sub-block (sub-block 1) in the upper left comer of the current block has an associated first position in the processing order, the sub-block (sub-block 2) in the upper right corner of the current block has an associated second position in the processing order, the sub-block (sub-block 3) in the lower left comer of the current block has an associated third position in the processing order, and the sub-block (sub-block 4) in the lower right comer of the current block has an associated fourth (last) position in the processing order. Statistically, this order of processing allows analysis and rasterization of pixels in a certain order for efficient cache utilization.
[0070] The technique 500 then selects (at 510) a current sub-block according to the
associated processing order. As such, through multiple iterations of the technique 500, sub-block 1 is selected and processed first, sub-block 2 is selected and processed second, sub-block 3 is selected and processed third, and sub-block 4 is selected and processed last.
[0071 ] The technique 500 then determines (515) whether the current sub-block overlaps
the image in the current block. In some embodiments, the technique does so by determining whether the current sub-block is completely within the image or intersects the image (i.e., the image is partially with in the sub-block and the sides of the image intersects with the sides of the sub-block). In some embodiments, the technique determines whether the current sub-block is completely within the image or the current sub-block intersects the image (i.e., whether the current sub-block has non-zero

WO 2006/026647 PCT/US2005/030931
-17-
intersection with the image) by performing the following steps. First, the technique
assumes that e1,e1, and e3 are equations for the edges/sides of the triangle and bi,t>2,b3,
and D4 are equations for the edges/sides of the current sub-block. The technique then
defines a number, Ey, as the number of vertices that belong to bj that gives non-negative
values when input into the edge equation of e1. The technique then determines whether
the following equation is true: E1,1 + E13 + E21 + E23 + E31 + E33 = 12. If so, the
current sub-block is folly contained in the image. If not, the current sub-block is not
fully contained in the image. The technique then determines if for some j the following
equations are true: E1j > 0, E2J > 0, E3j > 0, and at least one vertex that belongs to bj lies
within the bounding box defined by: [xmjn>*max] x [Ymin,Ymax]- If so, the current sub-block
intersects the image (i.e., has non-zero intersection with the image). If not, the current
sub-block does not intersect the image.
[0072] If the current sub-block does not overlap the image, the current sub-block is
disregarded and the technique then determines (at 520) whether there are more sub-blocks of the current block to be processed. If so, the technique continues at step 510 where a next current sub-block is selected according to the associated processing order. If not, the technique returns to the calling procedure. In the first iteration of the
technique 500, the calling procedure is the general technique 200 whereas in later
iterations, the calling procedure is the technique 500 itself.
[0073] If the technique 500 determines (at 515 - Yes) that the current sub-block
overlaps the image, the technique then proceeds to step 527. Note that in the example shown in Figure 6B, sub-block 1 does overlap the image 610. At step 527, the technique determines whether the size of the current sub-block is equal to the size of the tile (determined at step 205 of the general technique 200). If so, the technique 500 loads

WO 2006/026647 PCT/US2005/030931
(at 530) graphics data associated with the current sub-block (i.e., loads graphics data
describing a portion of the image overlapping the current sub-block) from the storage
device into the cache.
[0074] The technique then rasterizes (at 535) the current sub-block of the image (as
described by the associated graphics data loaded to the cache). The current sub-block can be rasterized without further data loads from the storage to the cache since the cache size supports the current sub-block size. This is due to the fact that since the cache size supports the tile size, it also supports the current sub-block size since it has been determined (at 527 - Yes) that the current sub-block size is equal to the tile size. In
some embodiments, the entire current sub-block is rasterized before more graphics data is loaded to the cache.
[0075] If the technique determines (at 527 - No) that the size of the current sub-block is
not equal to the size of the tile, the technique 500 (the calling procedure) recurses for
the current sub-block. The technique does so by setting (at 540) the current block as the current sub-block, calling itself (at 545) for the current block, and passing (at 545) the current block of graphics data to the called/recursed procedure. By recursing the
technique 500 for the current sub-block, the technique continues to divide (at 505) the
sub-block into further sub-blocks until the size of the tile is matched. When the size of
the tile is matched by a sub-block, the graphics data associated with the sub-block is
loaded to the cache and the sub-block is rasterized (at 530 and 535). When there are no
more sub-blocks of a current block to be processed, the technique returns (at 525) to the
calling procedure (the general technique 200 or the technique 500 itself).
[0076] For the example shown in Figure 6B, assume that the tile size is a 2 x 2 pixel
array so that the tile size does not match the sub-block size (an 8 x 8 pixel array). As

WO 2006/026647 PCT/US2005/030931
-19-
such, in the example shown in Figure 6B, for the first iteration of the technique 500, the technique would recurse (at 545) for sub-block 1. As shown in the example of Figure 6C, sub-block 1 is divided (at 505) into four 4x4 sub-blocks, the sub-blocks having an associated "Z" pattern processing order. Sub-block 1 would be the first sub-block to be selected (at 510) for analysis by the technique 500. Since sub-block 1 does not overlap the image 610, sub-block 1 would be disregarded and sub-block 2 would be selected (at
510) for analysis. Since sub-block 2 overlaps the image 610 but does not have a size equal to the tile size (since the sub-block size is 4 x 4 and the tile size is 2 x 2), the technique 500 recurses (at 545) again for sub-block 2.
[0077] As shown in the example of Figure 6D, sub-block 2 is divided (at 505) into four
2x2 sub-blocks, the sub-blocks having an associated "Z" pattern processing order. Sub-block 1 would be the first sub-block to be processed by the technique 500. Since sub-block 1 overlaps the image 610 and has a size equal to the tile size (since the sub-block size is 2 x 2 and the tile size is 2 x 2), the technique 500 loads (at 530) the graphics data associated with sub-block 1 to the cache and rasterizes (at 535) the sub-block. The technique then analyzes sub-block 2 and loads and rasterizes the graphics data associated with sub-block 2. The technique does the same for sub-block 3 and then sub-block 4.
[0078] After processing sub-block 4, the technique determines (at 520) that there are no
more sub-blocks of the current block (sub-block 2 of Figure 6C). As such, the technique returns (at 525) to the calling procedure (the technique 500) which has finished (at 545) processing sub-block 2 of Figure 6C. The technique then determines (at 520) that there are more sub-blocks (sub-blocks 3 and 4 of Figure 6C) of the current block (sub-block 1

WO 2006/026647 PCT/US2005/030931
of Figure 6B) to be processed. The technique then selects (at 510) sub-block 3 of Figure 6C for analysis.
[0079] The technique 500 continues in such a manner until each sub-block of Figure
6B is processed. During the processing of the sub-blocks, further sub-blocks are created recursively where some sub-blocks are loaded to the cache and rasterized while some are disregarded. Figure 6E illustrates an example rasterization order of sub-blocks of an image 610 that is produced by the technique 500. The number in a sub-block indicates the rasterization order of the sub-block relative to the other sub-blocks. The lines and dashed lines indicate a division of a sub-block into further sub-blocks where the dashed lines indicate a sub-block having the same size as the tile size.
[0080] Section in: "Z" Pattern Scanning Order
[0081] In some embodiments, the techniques of the present invention implement a "Z"
pattern order for scanning pixels of a block (pixel array) during rasterization of the block. For example, the "Z" pattern rasterization order may be used to scan an image within a bounding box (at step 235 of Figure 2), or to scan a sub-block of an image (at step 535 of Figure 5).
[0082] Figure 7 is a flowchart of a recursive associating technique 700 that analyzes
and specifies a scanning order for pixels of a block to be rasterized. The technique 700 can be applied to blocks having a size greater than 2x2. Pixels of 2 x 2 blocks are simply specified a "Z" scanning order (as shown in Figure 8A). The recursive associating technique 700 specifies a scanning order for pixels of a block using a binary search subdivision process that recursively divides sub-blocks of the block into further sub-blocks until the sub-blocks are 2 x 2 in size. The technique then specifies a "Z" scanning order (as shown in Figure 8A) for pixels of the 2x2 sub-block. The recursive

W () 2006/026647 PCT/US2005/030931
associating technique 700 is similar to the recursive processing technique 500 of Figure
5 where the tile size is equal to a 2 x 2 pixel array. Only those steps that differ from the
recursive processing technique 500 are discussed in detail here.
[0083] The recursive associating technique 700 begins by receiving (at 702) a current
block (pixel array) to be rasterized. In some embodiments, the block is a square with sides having a length (as measured in pixels) that is a power of 2. The block comprises a 21 x 2* pixel array. The technique then divides (at 705) the current block to produce four equal-sized sub-blocks, each sub-block having sides with a length (as measured in
pixels) that are a power of 2. The technique then associates (at 707) a processing order
with each produced sub-block according to a "Z" pattern (as illustrated in Figure 6B).
Note that this processing order is not the same as the scanning order specified for a
pixel: the processing order gives the order of analysis that the technique 700 follows to
determine the scanning order, whereas, the scanning order specified for a pixel gives the
order that the pixel will be scanned during rasterization.
[0084] The technique 700 then selects (at 710) a current sub-block according to the
associated processing order. The technique determines (at 715) whether the size of the current sub-block is 2 x 2 in size. If so, the technique 700 specifies (at 717) a "Z" pattern scanning order for pixels of the current sub-block. In other words, the pixel in the upper left comer of the current sub-block has an associated first position in the scanning order, the pixel in the upper right corner of the current sub-block has an associated second position in the scanning order, the pixel in the lower left corner of the
current sub-block has an associated third position in the scanning order, and the pixel in the lower left corner of the current sub-block has an associated fourth position in the scanning order.

WO 2006/026647 PCT/US2005/030931
[0085] The technique then determines (at 720) whether there are more sub-blocks of the
current block to be processed. If so, the technique continues at step 710 where a next current sub-block is selected according to the associated processing order. If not, the technique returns to a calling procedure.
[0086] If the technique determines (at 715 - No) that the size of the current sub-block is
not 2 x 2 in size, the technique 700 (the calling procedure) recurses for the current sub-block. The technique does so by setting (at 740) the current block as the current sub-block, calling itself (at 745) for the current block, and passing (at 745) the current block to the called/recursed procedure. By recursing the technique 700 for the current sub-block, the technique continues to divide (at 705) the sub-block into further sub-blocks until a 2 x 2 sub-block is reached. When a 2 x 2 sub-block is reached, a "Z" pattern scanning order for pixels of the sub-block is specified (at 717). When there are no more sub-blocks of a current block to be processed, the technique returns (at 725) to the calling procedure.
[0087] Figure 8A shows the "Z" pattern scanning order for a 2 x 2 pixel array. Figures
8B-C show examples of a scanning order produced by the technique 700. Figure 8B shows the resulting scanning order for a 4 x 4 block, and Figure 8C shows the resulting scanning order for a 16 x 16 block. The "Z" pattern scanning order for scanning pixel arrays statistically improves the texture mapping cache hit rate.
[0088] Figure 9 presents a computer system 900 with which some embodiments of the
invention are implemented. In some embodiments, the techniques of the present
invention are hard-coded into hardware devices dedicated specifically for graphics
production and/or implemented in computer executable instructions stored in a computer readable medium (software).

WO 2006/026647 PCT/US2005/030931
[0089] The computer system 900 includes a bus 905, a processor 910, a system memory
915, a read-only memory 920, a permanent storage device 925, input devices 930,
output devices 935, and an alternative processor 940.
[0090] The bus 905 collectively represents all system, peripheral, and chipset buses that
communicatively connect the numerous internal devices of the computer system 900. For instance, the bus 905 communicatively connects the processor 910 with the readonly memory 920, the system memory 915, and the permanent storage device 925.
[0091] The read-only-memory (ROM) 920 stores static data and instructions that are
needed by the processor 910 and other modules of the computer system. The permanent storage device 925, on the other hand, is read-and-write memory device. This device is a non-volatile memory unit that stores instruction and data even when the computer system 900 is off. Some embodiments of the invention use a mass-storage device (such as a magnetic or optical disk and its corresponding disk drive) as the permanent storage device 925. Other embodiments use a removable storage device (such as a floppy disk or zip® disk, and its corresponding disk drive) as the permanent storage device.
[0092] Like the permanent storage device 925, the system memory 915 is a read-and-
write memory device. However, unlike storage device 925, the system memory is a volatile read-and-write memory, such as a random access memory (RAM). The system memory stores some of the instructions and data that the processor needs at runtime.
[0093] In some embodiments, instructions and/or data needed to perform methods of
the present invention are stored in the system memory 915, the permanent storage device 925, the read-only memory 920, or any combination of the three. For example, the various memory units may contain instructions of an application and/or graphics

WO 2006/026647 PCT/US2005/030931
data generated by the application. In some embodiments, the system memory 915 and/or the permanent storage device 925 comprise a cache and/or buffer.
[0094] From these various memory units, the processor 910 retrieves instructions to
execute and data to process in order to perform the processes of the present invention. In some embodiments, the processor 910 uses an on-chip cache 912 to hold data recently accessed or produced by the processor 910. In some embodiments, the alternative processor 940 executes instructions and processes data to perform the processes of the present invention.
[0095] The bus 905 also connects to the input and output devices 930 and 935. The
input devices 930 enable a user to communicate information and select commands to
the computer system 900. The input devices 930 include alphanumeric keyboards and cursor-controllers. The output devices 935 print or display images generated by the computer system 900. The output devices include printers and display devices, such as cathode ray tubes (CRT) or liquid crystal displays (LCD).
[0096] Finally, as shown in Figure 9, the bus 905 also couples the computer system 900
to a network 965 through, for example, a network adapter (not shown). In this manner, the computer system 900 can be a part of a network of computers (such as a local area network ("LAN"), a wide area network ("WAN"), or an Intranet) or a network of networks (such as the Internet). Any or all of the components of the computer system 900 may be used in conjunction with the present invention. However, one of ordinary skill in the art would appreciate that any other system configuration may also be used in conjunction with the present invention.
[0097] While the invention has been described with reference to numerous specific
details, one of ordinary skill in the art will recognize that the invention can be embodied

WO 2006/026647 PCT/US2005/030931
-25-
in other specific forms without departing from the spirit of the invention. Thus, one of ordinary skill in the art would understand that the invention is not to be limited by the foregoing illustrative details, but rather is to be defined by the appended claims.
[0008] The various illustrative logical blocks, modules, and circuits described in
connection with the embodiments disclosed herein may be implemented or performed with a general purpose processor, a digital signal processor (DSP), an application specific integrated circuit (ASIC), a field programmable gate array (FPGA) or other programmable logic device, discrete gate or transistor logic, discrete hardware
components, or any combination thereof designed to perform the functions described
herein. A general purpose processor may be a microprocessor, but in the alternative, the
processor may be any conventional processor, controller, microcontroller, or state
machine. A processor may also be implemented as a combination of computing
devices, e.g., a combination of a DSP and a microprocessor, a plurality of
microprocessors, one or more microprocessors in conjunction with a DSP core, or any
other such configuration.
[0099] The steps of a method or algorithm described in connection with the
embodiments disclosed herein may be embodied directly in hardware, in a software module executed by a processor, or in a combination of the two. A software module may reside in RAM memory, flash memory, ROM memory, EPROM memory, EEPROM memory, registers, hard disk, a removable disk, a CD-ROM, or any other form of storage medium known in the art. An exemplary storage medium is coupled to the processor such the processor can read information from, and write information to, the storage medium. In the alternative, the storage medium may be integral to the processor. The processor and the storage medium may reside in an ASIC. The ASIC

WO 2006/026647 PCT/US2005/030931
-26-
may reside in a user terminal. In the alternative, the processor and the storage medium
may reside as discrete components in a user terminal.
[00100] The previous description of the disclosed embodiments is provided to enable any
person skilled in the art to make or use the present invention. Various modifications to these embodiments will be readily apparent to those skilled in the art, and the generic principles defined herein may be applied to other embodiments without departing from the spirit or scope of the invention. Thus, the present invention is not intended to be limited to the embodiments shown herein but is to be accorded the widest scope consistent with the principles and novel features disclosed herein.

WO 2006/026647 PCT/US2005/030931
CLAIMS
1. A device comprising:
cache for storing data, said cache size comprising a size equal to a tile size; and processor, coupled to said cache, for subdividing a graphics image into a
plurality of sub-blocks, for processing said sub-blocks, based on a block processing order, including subdividing said sub-blocks into a plurality of tiles for sub-blocks comprising graphics image data, said tiles comprising a size equal to said tile size, for loading data, associated with a tile, into said cache, and for utilizing said data in said cache to generate pixels for said associated tile of said graphics image.
2. The device as set forth in claim 1, said processor further comprising software for a) determining whether said sub-block overlaps said graphics image, b) determining whether said sub-block size equals said tile size if said sub-block overlaps said graphics image, c) subdividing said sub-block into additional sub-blocks if said sub-block overlaps said graphics image and said sub-block size equals said tile size, d) selecting one of said additional sub-blocks based on said block processing order, and repeat elements a, b, c, and d, until said sub-block size equals said tile size.
3. The device as set forth in claim 1, said processor further comprising software for determining a bounding box that encompasses said graphics image, and for sub-dividing said bounding box to generate said sub-blocks.

WO 2006/026647 PCT/US2005/030931
-28-
4. The device as set forth in claim 3, said processor further comprising
software for determining a bounding box size 2k x 2k, wherein K comprises an integer value.
5. The device as set forth in claim 1, wherein said tile size comprises 2k x 2k, wherein K comprises an integer value.
6. The device as set forth in claim 1, said processor further comprising software for assigning a pixel processing order to generate said pixels.
7. An apparatus for cache efficient graphics rasterization comprising:
means for selecting a tile size;
means for subdividing said graphics image into a plurality of sub-blocks;
means for processing said sub-blocks, based on a block processing order, including subdividing said sub-blocks into a plurality of tiles for sub-blocks comprising graphics image data, said tiles comprising said tile size;
means for loading data, associated with a tile, into said cache; and
means for utilizing said data in said cache to generate pixels for said associated tile of said graphics image.
8. The apparatus as set forth in claim 7, wherein the means for processing sub-blocks comprises:
a) means for determining whether said sub-block overlaps said graphics image;

WO 2006/026647 PCT/US2005/030931
b) means for determining whether said sub-block size equals said tile size if
said sub-block overlaps said graphics image;
c) means for subdividing said sub-block into additional sub-blocks if said sub-
block overlaps said graphics image and said sub-block size equals said tile size;
d) means for selecting one of said additional sub-blocks based on said block
processing order; and repeat elements a, b, c, and d, until said sub-block size equals said tile size.
9. The apparatus as set forth in claim 7, further comprising:
means for determining a bounding box that encompasses graphics image; and means for sub-dividing said bounding box to generate said sub-blocks.
10. The apparatus as set forth in claim 9, wherein means for determining a bounding box that encompasses graphics image comprises means for determining a bounding box size 2k x 2k, wherein K comprises an integer value.
11. The apparatus as set forth in claim 7, wherein said tile size comprises 2k x 2k, wherein K comprises an integer value.
12. The apparatus as set forth in claim 7, wherein means for utilizing said
data in said cache to generate pixels for said sub-blocks comprises assigning a pixel processing order to generate said pixels.

WO 2006/026647 PCT/US2005/030931
-30-
13. A method for cache efficient graphics rasterization comprising:
receiving a graphics image;
selecting a tile size;
subdividing said graphics image into a plurality of sub-blocks;
processing said sub-blocks, based on a block processing order, including subdividing said sub-blocks into a plurality of tiles for sub-blocks comprising graphics image data, said tiles comprising said tile size;
loading data, associated with a tile, into said cache; and
utilizing said data in said cache to generate pixels for said associated tile of said graphics image.
14. The method as set forth in claim 13, wherein processing sub-blocks
comprises:
a) determining whether said sub-block overlaps said graphics image;
b) determining whether said sub-block size equals said tile size if said sub-
block overlaps said graphics image;
c) subdividing said sub-block into additional sub-blocks if said sub-block
overlaps said graphics image and said sub-block size equals said tile size;
d) selecting one of said additional sub-blocks based on said block processing
order; and repeat elements a, b, c, and d, until said sub-block size equals said tile size.
15. The method as set forth in claim 13, further comprising:
determining a bounding box that encompasses graphics image; and

WO 2006/026647 PCT/US2005/03093J
-31-
sub-dividing said bounding box to generate said sub-blocks.
16. The method as set forth in claim 15, wherein determining a bounding box that encompasses graphics image comprises determining a bounding box size 2k x 2k, wherein K comprises an integer value.
17. The method as set forth in claim 13, wherein said tile size comprises 2k x 2k, wherein K comprises an integer value.
18. The method as set forth in claim 13 wherein utilizing said data in said cache to generate pixels for said sub-blocks comprises assigning a pixel processing
order to generate said pixels.
19. A computer readable media embodying a method for cache efficient
graphics rasterization, the method comprising:
receiving a graphics image;
selecting a tile size;
subdividing said graphics image into a plurality of sub-blocks;
processing said sub-blocks, based on a block processing order, including subdividing said sub-blocks into a plurality of tiles for sub-blocks comprising graphics image data, said tiles comprising said tile size;
loading data, associated with a tile, into said cache; and
utilizing said data in said cache to generate pixels for said associated tile of said graphics image.

WO 21)06/026647 PCT/US2005/030931
20. The computer readable media as set forth in claim 19, wherein
processing sub-blocks comprises:
a) determining whether said sub-block overlaps said graphics image;
b) determining whether said sub-block size equals said tile size if said sub-
block overlaps said graphics image;
c) subdividing said sub-block into additional sub-blocks if said sub-block
overlaps said graphics image and said sub-block size equals said tile size;
d) selecting one of said additional sub-blocks based on said block processing
order; and repeat elements a, b, c, and d, until said sub-block size
equals said tile size.
21. The computer readable media as set forth in claim 19, further
comprising:
determining a bounding box that encompasses graphics image; and sub-dividing said bounding box to generate said sub-blocks.
22. The computer readable media as set forth in claim 21, wherein
determining a bounding box that encompasses graphics image comprises determining a
bounding box size 2k x 2k, wherein K comprises an integer value.
23. The computer readable media as set forth in claim 19, wherein said tile
size comprises 2k x 2k, wherein K comprises an integer value.

WO 2006/026647

PCT/US2005/030931

24. The computer readable media as set forth in claim 20, wherein utilizing said data in said cache to generate pixels for said sub-blocks comprises assigning a pixel processing order to generate said pixels.

Dated this 6th day of March, 2007



-34-ABSTRACT
“CACHE EFFICIENT RASTERIZATION OF GRAPHICS DATA”
A cache stores data for use in rasterizing graphics data. The size of the cache is equal to a selected tile size. A processor performs the rasterization of the graphics image by subdividing the graphics image into a plurality of sub-blocks. The sub-blocks are processed, based on a block processing order, by further subdivision of the sub-blocks into tiles for those sub-blocks that have graphics image data. The tiles have a size equal to the selected tile size. Data, associated with a tile, is loaded into the cache, and the cache data is utilized to generate pixels for the associated tile of the graphics image.

Documents:

364-MUMNP-2007-ABSTRACT(23-6-2009).pdf

364-mumnp-2007-abstract(granted)-(16-9-2009).pdf

364-mumnp-2007-abstract.doc

364-mumnp-2007-abstract.pdf

364-MUMNP-2007-CANCELLED PAGES(23-6-2009).pdf

364-MUMNP-2007-CLAIMS(23-6-2009).pdf

364-mumnp-2007-claims(granted)-(16-9-2009).pdf

364-mumnp-2007-claims.doc

364-mumnp-2007-claims.pdf

364-MUMNP-2007-CORRESPONDENCE(1-6-2009).pdf

364-mumnp-2007-correspondence(16-9-2009).pdf

364-MUMNP-2007-CORRESPONDENCE(23-6-2009).pdf

364-MUMNP-2007-CORRESPONDENCE(9-4-2012).pdf

364-mumnp-2007-correspondence(ipo)-(14-10-2009).pdf

364-mumnp-2007-correspondence-received.pdf

364-mumnp-2007-description (complete).pdf

364-MUMNP-2007-DESCRIPTION(COMPLETE)-(23-6-2009).pdf

364-mumnp-2007-description(granted)-(16-9-2009).pdf

364-MUMNP-2007-DRAWING(23-6-2009).pdf

364-mumnp-2007-drawing(complete)-(12-3-2007).pdf

364-mumnp-2007-drawing(granted)-(16-9-2009).pdf

364-mumnp-2007-drawings.pdf

364-MUMNP-2007-FORM 1(23-6-2009).pdf

364-mumnp-2007-form 13(16-9-2009).pdf

364-mumnp-2007-form 2(23-6-2009).pdf

364-mumnp-2007-form 2(granted)-(16-9-2009).pdf

364-MUMNP-2007-FORM 2(TITLE PAGE)-(23-6-2009).pdf

364-mumnp-2007-form 2(title page)-(complete)-(12-3-2007).pdf

364-mumnp-2007-form 2(title page)-(granted)-(16-9-2009).pdf

364-MUMNP-2007-FORM 3(1-6-2009).pdf

364-mumnp-2007-form 3(13-7-2007).pdf

364-MUMNP-2007-FORM 3(23-6-2009).pdf

364-mumnp-2007-form-1.pdf

364-mumnp-2007-form-18.pdf

364-mumnp-2007-form-2.doc

364-mumnp-2007-form-2.pdf

364-mumnp-2007-form-26.pdf

364-mumnp-2007-form-3.pdf

364-mumnp-2007-form-5.pdf

364-mumnp-2007-form-pct-ib-304.pdf

364-mumnp-2007-form-pct-ib-311.pdf

364-mumnp-2007-form-pct-ipea-409.pdf

364-mumnp-2007-form-pct-ipea-416.pdf

364-mumnp-2007-form-pct-isa-220.pdf

364-mumnp-2007-form-pct-isa-237.pdf

364-mumnp-2007-form-pct-isa-seperate sheet-237.pdf

364-MUMNP-2007-GENERAL POWER OF ATTORNEY(9-4-2012).pdf

364-MUMNP-2007-OTHER DOCUMENT(23-6-2009).pdf

364-mumnp-2007-pct-search report.pdf

364-mumnp-2007-wo international publication report (12-3-2007).pdf

abstract1.jpg


Patent Number 236031
Indian Patent Application Number 364/MUMNP/2007
PG Journal Number 39/2009
Publication Date 25-Sep-2009
Grant Date 16-Sep-2009
Date of Filing 12-Mar-2007
Name of Patentee QUALCOMM INCORPORATED
Applicant Address 5775 Morehouse Drive, San Diego, California 92121-1714
Inventors:
# Inventor's Name Inventor's Address
1 BOURD, AlEXEI V 10310 Caminito Agadir, San Diego, CA 92131
2 ARSHAD, SHUAIB UDDIN 9555 Gold Coast Drive, #A-1, San Diego, CA 92126
PCT International Classification Number G06T1/60
PCT International Application Number PCT/US2005/030931
PCT International Filing date 2005-08-30
PCT Conventions:
# PCT Application Number Date of Convention Priority Country
1 10/930,408 2004-08-30 U.S.A.