Hierarchical tile-based rasterization algorithm

• US 20110234609A1
• Filed: 11/03/2006
• Published: 09/29/2011
• Est. Priority Date: 11/03/2006
• Status: Active Grant

• Current Assignee: Vivante Corporation (Verisilicon Microelectronics (Shanghai) Co. Ltd.)
• Original Assignee: Giquila Corp.
• Inventors: Chen, Ming, Cai, Mike, Garritsen, Frido
• Granted Patent: US 8,139,058 B2
• Time in Patent Office: Days
• US Class Current: 345/581
• CPC Class Codes: G06T 11/40 Filling a planar surface by adding surface attributes, e.g. colour or texture

Abstract

A hierarchical tile-based rasterization method is disclosed. The inventive rasterization algorithm rasterizes pixels in hierarchical rectangles or blocks. The method includes: walking a plurality of tiles of pixels and determining if each tile is valid; breaking each valid tile into a plurality of subtiles and determining if each subtile is valid; breaking each valid subtile into a plurality of quads and determining if each quad is valid; and rendering pixels for each valid quad. These hierarchical levels of block validations are performed in parallel. The inventive rasterization algorithm is further implemented in hardware for better performance.

Claims

1. A hierarchical memory localized triangle rasterization method, comprising the steps of:

(a) walking a plurality of tiles of pixels and determining if each tile is valid;

(b) breaking each valid tile into a plurality of subtiles and determining if each subtile is valid;

(c) breaking each valid subtile into a plurality of quads and determining if each quad is valid; and

(d) rendering pixels for each valid quad, wherein steps (a) through (d) are performed in parallel.

2. The method of claim 1, wherein the breaking step (b) comprises:

(b1) breaking each valid tile into the plurality of subtiles;

(b2) walking the plurality of subtiles; and

(b3) determining if each subtile is valid.

3. The method of claim 2, wherein the walking of the plurality of subtiles is performed in a same manner as the walking of the plurality of tiles.

4. The method of claim 1, wherein the breaking step (c) comprises:

(c1) breaking each valid subtile into the plurality of quads;

(c2) walking the plurality of quads; and

(c3) determining if each quad is valid.

5. The method of claim 4, wherein the walking of the plurality of quads is performed in a same manner as the walking of the plurality of tiles and a walking of the plurality of subtiles.

6. The method of claim 1, wherein validation of a block, wherein the block comprises a tile, a subtile, or a quad, comprises:

checking if a pixel in the block is found in an area of the screen where pixels belonging to the inside of the triangle are present using edge equations;

checking four corners of the block against three edges of the triangle and returning a combined result;

determining if the block contains any pixels inside the triangle, based on the combined result; and

determining that the block is valid, if the block contains at least one pixel inside the triangle.

7. The method of claim 6, further comprising:

abandoning the block, if the block does not contain at least one valid pixel inside the triangle.

8. A hierarchical memory localized rasterization method, comprising the steps of:

(a) inputting an initial point for a primitive;

(b) determining if the primitive is a line or a triangle; and

(c) if the polygon is a triangle, rasterizing the triangle in a hierarchical manner, comprising;

(c1) walking a plurality of tiles of pixels and determining if each tile is valid;

(c2) breaking each valid tile into a plurality of subtiles and determining if each subtile is valid;

(c3) breaking each valid subtile into a plurality of quads and determining if each quad is valid; and

(c4) rendering pixels for each valid quad, wherein steps (c1) through (c4) are performed in parallel.

9. The method of claim 8, wherein the breaking step (c2) comprises:

(c2i) breaking each valid tile into the plurality of subtiles;

(c2ii) walking the plurality of subtiles; and

(c2iii) determining if each subtile is valid.

10. The method of claim 9, wherein the walking of the plurality of subtiles is performed in a same manner as the walking of the plurality of tiles.

11. The method of claim 8, wherein the breaking step (c3) comprises:

(c3i) breaking each valid subtile into the plurality of quads;

(c3ii) walking the plurality of quads; and

(c3iii) determining if each quad is valid.

12. The method of claim 11, wherein the walking of the plurality of quads is performed in a same manner as the walking of the plurality of tiles and a walking of the plurality of subtiles.

13. The method of claim 8, wherein validation of a block, wherein the block comprises a tile, a subtile, or a quad, comprises:

checking if a pixel in the block is found in an area of the screen where pixels belonging to the inside of the triangle are present using edge equations;

checking four corners of the block against three edges of the triangle and returning a combined result;

determining if the block contains any pixels inside the triangle, based on the combined result; and

determining that the block is valid, if the block contains at least one valid pixel inside the triangle.

14. The method of claim 13, further comprising:

abandoning the block, if the block does not contain at least one valid pixel inside the triangle.

15. The method of claim 8, further comprising:

(d) if the primitive is a line, computing pixels for each quad of pixels for the line; and

(e) rendering pixels for each valid quad.

16. A method for validation of a block of pixels in a hierarchical memory localized triangle rasterization method, comprising the steps of:

(a) checking if a pixel in the block is found in an area of the screen where pixels belonging to the inside of the triangle are present using edge equations;

(b) checking four corners of the block against three edges of the triangle and returning a combined result;

(c) determining if the block contains any pixels inside the triangle, based on the combined result; and

(d) determining that the block is valid, if the block contains at least one valid pixel inside the triangle.

17. The method of claim 16, further comprising:

(e) abandoning the block, if the block does not contain at least one pixel inside the triangle.

18. The method of claim 16, wherein the steps (a) through (d) are performed to validate a plurality of tiles of pixels, a plurality of subtiles, and a plurality of quads,

wherein a valid tile is broken into the plurality of subtiles, wherein a valid subtile is broken into the plurality of quads,

wherein the validation of the plurality of tiles, the plurality of subtiles, and the plurality of quads are performed in parallel.