Method and apparatus for rasterizing in a hierarchical tile order

A method for rasterizing a primitive in a frame buffer, where the frame buffer is organized as a series of memory tiles, the method comprising:

• a) traversing a set of memory tiles that include memory locations within the primitive;
• b) determining which memory locations included in the still smaller memory tiles are included in the primitive, further comprising:
• i) calculating the value of a respective edge function for an x and y value within the still smaller memory tiles using one edge evaluator for each edge of the primitive;
• and
• ii) recalculating the edge function of the edge evaluator for each memory location within the still smaller memory level tiles using one adder tree for each edge evaluator;
• and
• c) accessing the memory tiles encountered during (b) as respective sequences of smaller memory tiles;
• and
• d) rasterizing smaller memory tiles within the sequences of smaller memory tiles so that rasterization is first performed on a smaller memory tile that includes a vertex of the primitive.

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

• means for accessing groups of memory locations in the frame buffer as memory tiles;
• 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 so that rasterization is first performed on a smaller memory tile that includes a vertex of a graphics primitive;
• further comprising:
• means for determining which memory locations included in the still smaller memory tiles are included in the primitive, further comprising:
• one edge evaluator for each edge of the primitive, each edge evaluator configured to calculate the value of a respective edge function for an x and y value within the still smaller memory tiles.

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

• means for accessing groups of memory locations in the frame buffer as memory tiles;
• 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 so that rasterization is first performed on a smaller memory tile that includes a vertex of a graphics primitive, wherein the means for rasterizing smaller memory tiles further comprises:
• 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 the means for rasterizing still smaller memory tiles further comprises:
• means for determining which memory locations included in the still smaller memory tiles are included in the primitive;
• and
• means for selecting still smaller memory tiles within the sequences of still smaller memory tiles for rasterization, wherein the means for determining which memory
• locations included in the still smaller memory tiles are included in the primitive further comprises:
• one edge evaluator for each edge of the primitive, each edge evaluator configured to calculate the value of a respective edge function for an x and y value within the still smaller memory tiles;
• and
• one adder tree for each edge evaluator, the adder tree for an edge evaluator configured to recalculate the edge function of the edge evaluator for each memory location within the still smaller memory level tiles.

An article of manufacture, comprising:

• a machine-readable medium having stored thereon instructions to:
• select a smaller tile from smaller tiles included in a larger tile, the selected smaller tile including a vertex of the primitive;
• traverse 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;
• determine which memory locations included in the still smaller memory tiles are located within the primitive, where the determination:
• i) calculating the value of a respective edge function for an x and y value within the still smaller memory tiles using one edge evaluator for each edge of the primitive;
• and
• ii) recalculating the edge function of the edge evaluator for each memory location within the still smaller memory level tiles using one adder tree for each edge evaluator;
• and
• rasterize each smaller tile encountered during the traversal.

An article of manufacture, comprising:

• a machine-readable medium having stored thereon instructions to:
• traverse a set of memory tiles that include memory locations within the primitive;
• determine which memory locations included in the still smaller memory tiles are located within the primitive, where the determination comprises:
• i) calculating the value of a respective edge function for an x and y value within the still smaller memory tiles using one edge evaluator for each edge of the primitive;
• and
• ii) recalculating the edge function of the edge evaluator for each memory location within the still smaller memory level tiles using one adder tree for each edge evaluator;
• access the memory tiles encountered during the traversal of the set of memory tiles as respective sequences of smaller memory tiles;
• and
• rasterize smaller memory tiles within the sequences of smaller memory tiles so that rasterization is first performed on a smaller memory tile that includes a vertex of the primitive.