Title-based digital differential analyzer rasterization

• US 6,636,218 B1
• Filed: 09/29/2000
• Issued: 10/21/2003
• Est. Priority Date: 06/30/2000
• Status: Expired due to Fees

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Nelson, Scott R.
• Primary Examiner(s): Razavi, Michael
• Assistant Examiner(s): YANG, RYAN R
• Application Number:
  US09/675,353
• Time in Patent Office: 1,117 Days
• Field of Search: 345/441, 345/419, 345/501, 345/443
• US Class Current: 345/441
• CPC Class Codes: G06T 11/40 Filling a planar surface by adding surface attributes, e.g. colour or texture
• CPC Class Codes: G06T 15/80 Shading

Abstract

A method, apparatus, and system are described for rasterizing a triangle. Pixel parameter values are interpolated by adding or subtracting a vertical delta and/or by adding or subtracting a horizontal delta within a 4×4 tile of 16 pixels.

Claims

1. A method of rasterization using a tile-based digital differential analyzer, comprising:

determining a step-down value for each primitive edge, each step-down value comprising a value by which a horizontal coordinate will change when stepping down the corresponding edge;

for each scan line, calculating a leftmost horizontal pixel sample coordinate and a rightmost horizontal pixel sample coordinate based on the step down value for the appropriate primitive edge; and

for each scan line region comprising at least one scan line on a raster display;

determining the rightmost tile based on corresponding rightmost horizontal coordinates for the scan line region; and

determining leftmost tile by;

determining the bottom-most of the leftmost horizontal coordinates for the scan line region; and

determining the tile number comprising the bottom-most of the leftmost horizontal coordinates for the scan line region.

2. The method of claim 1, wherein the bottom-most of the leftmost horizontal coordinates for the scan line region comprises the lowest leftmost horizontal coordinate in the scan line region.

3. The method of claim 1, wherein said determining the tile number comprising the bottom-most of the leftmost horizontal coordinates for the scan line region comprises:

determining binary coordinates comprising the bottom-most of the leftmost horizontal coordinates for the scan line region; and

zeroing out the lowest two bits of the binary coordinates.

4. The method of claim 1, wherein the determining the rightmost tile based on corresponding rightmost horizontal coordinates for the scan line region comprises:

determining the bottom-most of the rightmost horizontal coordinates for the scan line region; and

determining the tile number comprising the bottom-most of the rightmost horizontal coordinates for the scan line region.

5. The method of claim 4, wherein the bottom-most of the rightmost horizontal coordinates for the scan line region comprises the highest rightmost horizontal coordinate in the scan line region.

6. The method of claim 4, wherein the determining the tile number comprising the bottom-most of the rightmost horizontal coordinates for the scan line region comprises:

determining binary coordinates comprising the bottom-most of the rightmost horizontal coordinates for the scan line region; and

zeroing out the lowest two bits of the binary coordinates.

7. A system, comprising:

a memory comprising primitive data;

a setup processor coupled to the memory, the setup processor to access the primitive data in the memory to determine a step-down value for each edge of the primitive, the step-down value comprising a value by which the horizontal coordinate will change when stepping down the corresponding edge;

an edge interpolator coupled to the setup processor to calculate, for each scan line region, a leftmost horizontal coordinate and a rightmost horizontal coordinate based on the step down value for the appropriate primitive edge;

a left FIFO (first-in-first-out) unit coupled to the edge interpolator to store the leftmost horizontal coordinates for each scan line;

a right FIFO unit coupled to the edge interpolator to store rightmost horizontal coordinates for each scan line; and

a tile generator to access the left edge FIFO unit and the right edge FIFO unit to determine for each scan line region comprising at least one scan line;

the rightmost tile based on the rightmost horizontal coordinates corresponding to a given scan line region; and

the leftmost tile by;

determining the bottom-most of the leftmost horizontal coordinates for the scan line region; and

determining the tile number comprising the bottom-most of the leftmost horizontal coordinates for the scan line region.

8. The system of claim 7, wherein the tile generator determines the bottom-most of the leftmost horizontal coordinates for the scan line region by determining the lowest leftmost horizontal coordinate in the scan line region.

9. The system of claim 7, wherein the tile generator determines the tile number comprising the bottom-most of the leftmost horizontal coordinates for the scan line region by:

determining binary coordinates comprising the bottom-most of the leftmost horizontal coordinates for the scan line region; and

zeroing out the lowest two bits of the binary coordinates.

10. The system of claim 7, wherein the tile generator determining the rightmost tile based on corresponding rightmost horizontal coordinates for the scan line region by:

determining the bottom-most of the rightmost horizontal coordinates for the scan line region; and

determining the tile number comprising the bottom-most of the rightmost horizontal coordinates for the scan line region.

11. The system of claim 10, wherein the tile generator determines the bottom-most of the rightmost horizontal coordinates for the scan line region by determining the highest rightmost horizontal coordinate in the scan line region.

12. The system of claim 10, wherein the tile generator determines the tile number comprising the bottom-most of the rightmost horizontal coordinates for the scan line region by:

determining binary coordinates comprising the bottom-most of the rightmost horizontal coordinates for the scan line region; and

zeroing out the lowest two bits of the binary coordinates.

13. A machine-readable medium having stored thereon data representing sequences of instructions, the sequences of instructions which, when executed by a machine, cause the machine to:

determine a step-down value for each primitive edge, each step-down value comprising a value by which a horizontal coordinate will change when stepping down the corresponding edge;

for each scan line, calculate a leftmost horizontal pixel sample coordinate and a rightmost horizontal pixel sample coordinate based on the step down value for the appropriate primitive edge; and

for each scan line region comprising at least one scan line on a raster display;

determine the rightmost tile based on corresponding rightmost horizontal coordinates for the scan line region; and

determine leftmost tile by;

determine the bottom-most of the leftmost horizontal coordinates for the scan line region; and

determine the tile number comprising the bottom-most of the leftmost horizontal coordinates for the scan line region.

14. The machine-readable medium of claim 13, wherein the bottom-most of the leftmost horizontal coordinates for the scan line region comprises the lowest leftmost horizontal coordinate in the scan line region.

15. The machine-readable medium of claim 13, wherein the determining the tile number comprising the bottom-most of the leftmost horizontal coordinates for the scan line region comprises:

determining binary coordinates comprising the bottom-most of the leftmost horizontal coordinates for the scan line region; and

zeroing out the lowest two bits of the binary coordinates.

16. The machine-readable medium of claim 13, wherein the determining the rightmost tile based on corresponding rightmost horizontal coordinates for the scan line region comprises:

determining the bottom-most of the rightmost horizontal coordinates for the scan line region; and

determining the tile number comprising the bottom-most of the rightmost horizontal coordinates for the scan line region.

17. The machine-readable medium of claim 16, wherein the bottom-most of the rightmost horizontal coordinates for the scan line region comprises the highest rightmost horizontal coordinate in the scan line region.

18. The machine-readable medium of claim 16, wherein the determining the tile number comprising the bottom-most of the rightmost horizontal coordinates for the scan line region comprises:

determining binary coordinates comprising the bottom-most of the rightmost horizontal coordinates for the scan line region; and

zeroing out the lowest two bits of the binary coordinates.