Method and apparatus for rasterizing in a hierarchical tile order

• US 7,042,460 B2
• Filed: 03/07/2003
• Issued: 05/09/2006
• Est. Priority Date: 07/02/1998
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Millet, Timothy J., Hussain, Zahid S.
• Primary Examiner(s): Tung, Kee M.
• Application Number:
  US10/383,276
• Publication Number:
  US 20030142103A1
• Time in Patent Office: 1,159 Days
• Field of Search: 345/531, 345/545, 345/503, 345/564
• US Class Current: 345/545
• CPC Class Codes: G06T 11/40 Filling a planar surface by adding surface attributes, e.g. colour or texture
• CPC Class Codes: G09G 2360/122 Tiling
• CPC Class Codes: G09G 5/393 Arrangements for updating the contents of the bit-mapped memory

Abstract

A method and apparatus for efficiently rasterizing graphics is provided. The method is intended to be used in combination with a frame buffer that provides fast tile-based addressing. Within this environment, frame buffer memory locations are organized into a tile hierarchy. For this hierarchy, smaller low-level tiles combine to form larger mid-level tiles. Mid-level tiles combine to form high-level tiles. The tile hierarchy may be expanded to include more levels, or collapsed to included fewer levels. A graphics primitive is rasterized by selecting an starting vertex. The low-level tile that includes the starting vertex is then rasterized. The remaining low-level tiles that are included in the same mid-level tile as the starting vertex are then rasterized. Rasterization continues with the mid-level tiles that are included in the same high-level tile as the starting vertex. These mid-level tiles are rasterized by rasterizing their component low-level tiles. The rasterization process proceeds bottom-up completing at each lower level before completing at higher levels. In this way, the present invention provides a method for rasterizing graphics primitives that accesses memory tiles in an orderly fashion. This reduces page misses within the frame buffer and enhances graphics performance.

Claims

1. A method for rasterizing a primitive wherein pixels are stored in a tile-organized memory, the method comprising:

a) selecting a smaller tile from smaller tiles included in a larger tile, the selected smaller tile including a vertex of the primitive;

b) traversing the smaller tiles included in the larger tile, the traversal starting at the selected smaller tile and sequencing through each smaller tile that has one or more memory locations located within the primitive; and

c) rasterizing each smaller tile encountered during step (b),

wherein the larger tile is from larger tiles included in a still-larger tile and wherein the method further comprises;

d) traversing each larger tile in the still larger tile that has one or more memory locations located within the primitive; and

e) applying steps (a), (b), and (c) to each larger tile encountered during step (d);

wherein a tile comprises a store of two or more pixels, the tile being addressed using a fractional portion of an address used to access a single pixel, and wherein traversal of the smaller tile, the larger tile and the still-larger tile is performed in order and wherein the traversal excludes tiles that fall entirely outside of the primitive as determined by a rendering apparatus comprising;

three edge evaluators, each evaluator initialized with an x and y value from the selected small tile including the vertex of the primitive;

three adder trees, each adder tree re-computing a value received from a respective edge evaluator for each x and y location within the tile being rasterized, and

an AND function providing a set of values indicative of memory locations within a tile which includes the primitive.

2. A method for rasterizing a primitive wherein pixels are stored in a tile-organized memory, the method comprising:

a) selecting a smaller tile from smaller tiles included in a larger tile, the larger tile being included in a still-larger tile, the selected smaller tile including a vertex of the primitive;

b) traversing the smaller tiles included in the larger tile, the traversal starting at the selected smaller tile and sequencing through each smaller tile that has one or more memory locations located within the primitive; and

c) rasterizing each smaller tile encountered during step (b), wherein the smaller tiles included in the larger tile are arranged as a rectangle or square and the smaller tile, the larger tile and the still-larger tile are each traversed in respective order;

wherein a tile address accesses two or more pixels stored in the tile, and wherein traversal excludes tiles that fall entirely outside of the primitive as determined by a rendering apparatus comprising;

three edge evaluators, each evaluator initialized with an x and y value from the selected small tile including the vertex of the primitive;

three adder trees, each adder tree re-computing a value received from a respective edge evaluator for each x and y location within the tile being rasterized, and

an AND function providing a set of values indicative of memory locations within a tile which includes the primitive.

3. A method for rasterizing a primitive in a frame buffer, where the frame buffer is organized as a series of rectangular memory tiles, each memory tile containing two or more pixels, the method comprising:

a) traversing a set of memory tiles that include memory locations within the primitive, wherein the traversing starts in a memory tile including a vertex of the primitive;

b) accessing the memory tiles encountered during step (a) as respective sequences of smaller memory tiles; and

c) rasterizing smaller memory tiles within the sequences of smaller memory tiles, wherein the rasterizing the smaller memory tiles further comprises;

accessing the smaller memory tiles as respective sequences of still-smaller memory tiles; and

rasterizing the still-smaller memory tiles within the sequences of still-smaller memory tiles;

wherein rasterizing is performed hierarchically according to increasing tile size and wherein the traversing excludes tiles that fall entirely outside of the primitive as determined by a rendering apparatus comprising;

three edge evaluators, each evaluator initialized with an x and y value from the selected small tile including the vertex of the primitive;

three adder trees, each adder tree re-computing a value received from a respective edge evaluator for each x and y location within the tile being rasterized, and

an AND function providing a set of values indicative of memory locations within a tile which includes the primitive.

4. A new system for rasterizing graphics primitives in a frame buffer, the system comprising:

a frame buffer organized into memory tiles, the memory tiles each storing at least two pixels,

means for accessing at least one memory tile within the frame buffer using one address;

means for accessing memory tiles as sequences of smaller memory tiles; and

means for rasterizing the smaller memory tiles within the sequences of smaller memory tiles, the means for rasterizing further comprising means for accessing the smaller memory tiles as respective sequences of still-smaller memory tiles; and

means for rasterizing the still-smaller memory tiles within the sequences of still-smaller memory tiles;

wherein rasterizing is performed hierarchically according to increasing tile size such that tiles that fall entirely outside of the primitive are excluded as determined by a rendering apparatus comprising;

three edge evaluators, each evaluator initialized with an x and y value from the selected small tile including the vertex of the primitive;

three adder trees, each adder tree re-computing a value received from a respective edge evaluator for each x and y location within the tile being rasterized, and

an AND function providing a set of values indicative of memory locations within a tile which includes the primitive.