Abstract:
Binning polygons in a three-dimensional graphics system includes constructing a first bounding box around a first-level polygon, the first bounding box including tiles that contain the first-level polygon, subdividing the first-level polygon into second-level polygons if the first bounding box exceeds a predetermined size, and constructing bounding boxes around each second-level polygon. The second bounding box includes fewer tiles than the first bounding box.

Description:
TECHNICAL FIELD  
         [0001]    This application relates to a polygon (e.g., triangle) binning process for use in a tile-based rendering system.  
         BACKGROUND  
         [0002]    A virtual 3D model (or simply “3D model”) is comprised of polygons, such as triangles, which represent the skin of the 3D model. A rasterization engine draws polygons from the 3D model onto a two-dimensional (2D) surface, such as a computer screen. Typical rasterization engines draw the entire frame buffer at once. A more efficient method is to break up the frame buffer into individual subsections (tiles) and to render them individually. Each tile includes one or more polygons or, more typically, a portion of one or more polygons.  
           [0003]    To reduce the amount of tiles that each polygon is assigned to, a polygon binning process may be used. A polygon binning process excludes tiles that do not include any polygons or portions thereof prior to rasterization. The binning process also accomplishes some rasterization setup by identifying which polygons are contained by each tile. By doing this, the amount of processing that must be performed by the rasterization engine is reduced. 
       
    
    
     DESCRIPTION OF THE DRAWINGS  
       [0004]    [0004]FIG. 1 is a view of a 3D model.  
         [0005]    [0005]FIG. 2 is a view of polygons that make up the 3D model.  
         [0006]    [0006]FIG. 3 is a flowchart of a polygon binning process.  
         [0007]    [0007]FIG. 4 is a block diagram of tiles in a frame buffer, a polygon contained in the tiles, and a bounding box.  
         [0008]    [0008]FIG. 5 is a view of sub-polygons derived from the polygon of FIG. 4 and a bounding box of one of the sub-polygons.  
         [0009]    [0009]FIG. 6 is a view of lower-level sub-polygons derived from the sub-polygon of FIG. 5 and the bounding boxes of these sub-polygons.  
         [0010]    [0010]FIG. 7 is a view of computer hardware on which the process of FIG. 3 may be implemented. 
     
    
       [0011]    Like reference numerals in different figures indicate like elements.  
       DESCRIPTION  
       [0012]    [0012]FIG. 1 shows a 3D model  10 , which is rendered from 3D data. As shown in FIG. 2, 3D model  10  is comprised of interconnecting polygons  12 . Polygons  12  are triangles in this embodiment; however, other types of polygons may be used. Polygons  12  define the “skin” surface of 3D model  10 .  
         [0013]    The animation of 3D model  10  is defined by a sequence of frames, which constitute snapshots of the 3D model at different points in time. Each frame contains information about the position of the 3D model in 3D space at a particular point in time. Data (i.e., polygons) for each frame of the animation is stored in frame buffer memory. The frame buffer can be subdivided into smaller portions called tiles. The frame buffer stores the polygons in these tiles which, in this context, are rectangular (e.g., square) portions of memory. One or more polygons may occupy a single tile or, alternatively, a single polygon may occupy several tiles. The latter is assumed in the description of the polygon binning process that follows.  
         [0014]    Current tiling processes may overestimate the number of tiles to which a polygon belongs. Improving the accuracy of this estimation reduces needless computations. The processes describe herein demonstrate such an improvement.  
         [0015]    Referring to FIG. 3, a process  14  is shown for drawing polygons on a 2D computer screen. Process  14  includes a polygon binning process  16 , which reduces the number of tiles that a polygon is assigned to in a frame buffer.  
         [0016]    The frame buffer is divided into individual tiles prior to binning. For example, a typical frame buffer might be 512×512 pixels. A typical size of a tile might be 32×32 pixels, yielding a partitioning of 16×16 tiles.  
         [0017]    Process  14  obtains ( 20 ) polygons from a 3D animation sequence. The polygons may be obtained from a single frame of the 3D animation. Process  14  assigns ( 22 ) polygons from the frame to tiles in a frame buffer. FIG. 4 shows an example of a polygon  24  and tiles  26  in the frame buffer. As shown, polygon  24  extends over a number of tiles in the frame buffer.  
         [0018]    When assigning polygons to tiles in the frame buffer, process  14  performs polygon binning process  16 . Polygon binning process  16  includes constructing ( 30 ) a bounding box  32  around polygon  24  (FIG. 4) in the frame buffer. The bounding box may be a rectangle that is just large enough to encompass the entirety of polygon  24  without including excess tiles along either the X-axis or the Y-axis. Process  16  marks ( 34 ) the tiles of the frame buffer that are within bounding box  32 . Marking the tiles in this manner distinguishes tiles inside the bounding box from tiles outside the bounding box.  
         [0019]    Process  16  determines ( 36 ) if the size of the bounding box exceeds a predetermined threshold, e.g., if the X-dimension of the bounding box exceeds a threshold and/or the Y-dimension of the bounding box exceeds the same, or a different, threshold. If the size of the bounding box exceeds the threshold ( 36 ), process  16  subdivides ( 38 ) the polygon into lower-level sub-polygons. What is meant by “lower-level” here is that, combined, the sub-polygons make up the undivided “parent” polygon and that each of the sub-polygons is smaller in area than its parent polygon.  
         [0020]    Process  16  subdivides ( 38 ) polygon  24  by obtaining the mid-points of each edge  40 ,  42  and  44  of the polygon. Process  16  connects the mid-points of each edge to produce four new sub-polygons  46 ,  48 ,  50  and  52  (FIG. 5). Process  16  selects one of these sub-polygons  52  and constructs ( 54 ) a lower level bounding box  56  around sub-polygon  52 . Bounding box  56  around sub-polygon  52  is constructed in the same manner as bounding box  32  around polygon  24 . As shown, a sum of all tiles included in the lower-level bounding box comprises fewer tiles than the parent-level bounding box. Process  16  unmarks ( 58 ) tiles that were within bounding box  32  but not within bounding box  56 . An example of a tile that is unmarked is tile  60  (FIGS. 4 and 5). As described below, only the tiles that are marked are eventually rasterized onto the 2D surface.  
         [0021]    Process  16  determines ( 62 ) if there are any sub-polygons remaining from the subdivision performed in block  38  that have not yet been processed. If so, process  16  selects one of the remaining sub-polygons and performs blocks  54 ,  58  and  62  on the selected sub-polygon. Process  16  repeats this until all of the sub-polygons have been processed.  
         [0022]    Process  16  determines ( 36 ) if the size of a bounding box around a sub-polygon (e.g.,  52 ) exceeds the predetermined threshold. This may be done during or after processing of the sub-polygons. If the size of the bounding box exceeds the predetermined threshold, process  16  selects each of the sub-polygons, in turn, and performs blocks  38 ,  54 ,  58  and  62  on the selected sub-polygons. This process results in lower-level sub-polygons  64  (FIG. 6) and is repeated until the size(s) of the bounding box(es) for the resulting sub-polygons do not exceed the predetermined threshold. Reducing the sizes of the bounding boxes reduces the number of tiles to which a polygon is assigned, and thus reduces the number of tiles that need to be rasterized when the image is displayed.  
         [0023]    Once the polygon binning process ( 16 ) has been completed, process  14  implements a tile clipping process to remove unused tiles and rasterizes ( 66 ) the tiles containing the polygons on a 2D surface. Process  14  excludes the unmarked tiles, meaning that the unmarked tiles are not rasterized. Process  14  rasterizes only those tiles that are marked, which correspond to a polygon or portion(s) thereof.  
         [0024]    [0024]FIG. 7 shows a computer  70  for performing process  14 . Computer  70  includes a processor  72 , a memory  74 , a storage medium  76  (e.g., a hard disk), and a 3D graphics processor  78  for processing 3D data (see view  80 ). Storage medium  76  stores 3D data  83  that defines the 3D model, and machine-executable instructions  82 , which are executed by processor  72  out of memory  74  to perform process  14  on 3D data  83 .  
         [0025]    Process  14 , however, is not limited to use with the hardware and software of FIG. 7; it may find applicability in any computing or processing environment. Process  14  may be implemented in hardware, software, or a combination of the two. For example, process  14  may be implemented using circuitry, such as one or more of programmable logic (e.g., an ASIC—Application-Specific Integrated Circuit), logic gates (e.g., AND, OR, NAND gates), a processing device (e.g., a microprocessor, controller), and a memory.  
         [0026]    Process  14  may be implemented in computer programs executing on programmable computers that each includes a processor, a storage medium readable by the processor (including volatile and non-volatile memory and/or storage elements), at least one input device, and one or more output devices. Program code may be applied to data entered using an input device, such as a mouse or a keyboard, to perform process  14  and to generate output information.  
         [0027]    Each such program may be implemented in a high level procedural or object-oriented programming language to communicate with a computer system. However, the programs can be implemented in assembly or machine language. The language may be a compiled or an interpreted language.  
         [0028]    Each computer program may be stored on an article of manufacture, such as a storage medium (e.g., CD-ROM, hard disk, or magnetic diskette) or device (e.g., computer peripheral), that is readable by a general or special purpose programmable computer for configuring and operating the computer when the storage medium or device is read by the computer to perform process  14 . Process  14  may also be implemented as a machine-readable storage medium, configured with a computer program, where, upon execution, instructions in the computer program cause a machine to operate in accordance with process  14 .  
         [0029]    Other embodiments not described herein are also within the scope of the following claims. For example, the blocks of FIG. 3 may be rearranged and/or executed out of order to produce a similar result. The processes described herein may be implemented on full-size machines or hand-held devices.