Method and apparatus for generating texture

• US 6,288,730 B1
• Filed: 08/20/1999
• Issued: 09/11/2001
• Est. Priority Date: 08/20/1998
• Status: Expired due to Term

• Current Assignee: Apple Inc.
• Original Assignee: Apple Computer Incorporated (Apple Inc.)
• Inventors: Hong, Bo, Duluk, Jerome F. Jr., Rashid, Abbas, Mammen, Abraham, Grass, Joseph P., Hessel, Richard E.
• Primary Examiner(s): Tung, Kee M.
• Application Number:
  US09/378,408
• Time in Patent Office: 753 Days
• Field of Search: 345/430, 345/501, 345/506, 345/502, 345/503, 345/507-509, 345/513, 345/523, 345/521, 345/428, 345/568, 345/530, 345/566, 345/552, 345/536-538, 345/531, 345/557, 345/556
• US Class Current: 345/552
• CPC Class Codes: G06T 1/60 Memory management
• CPC Class Codes: G06T 11/001 Texturing; Colouring; Generation of texture or colour inpainting G06T5/77
• CPC Class Codes: G06T 11/40 Filling a planar surface by adding surface attributes, e.g. colour or texture
• CPC Class Codes: G06T 15/005 General purpose rendering architectures
• CPC Class Codes: G06T 15/04 Texture mapping
• CPC Class Codes: G06T 15/20 Perspective computation
• CPC Class Codes: G06T 15/30 Clipping
• CPC Class Codes: G06T 15/40 Hidden part removal
• CPC Class Codes: G06T 15/50 Lighting effects
• CPC Class Codes: G06T 15/80 Shading
• CPC Class Codes: G06T 15/83 Phong shading
• CPC Class Codes: G06T 15/87 Gouraud shading

Abstract

A deferred graphics pipeline processor comprising a texture unit and a texture memory associated with the texture unit. The texture unit applies texture maps stored in the texture memory, to pixel fragments. The textures are MIP-mapped and comprise a series of texture maps at different levels of detail, each map representing the appearance of the texture at a given distance from an eye point. The texture unit performs tri-linear interpolation from the texture maps to produce a texture value for a given pixel fragment that approximates the correct level of detail. The texture memory has texture data stored and accessed in a manner which reduces memory access conflicts and thus improves throughput of said texture unit.

Claims

1. A graphics pipeline processor comprising:

a texture unit generating texture values; and

a texture memory associated with and coupled to said texture unit;

said texture unit interpolating a plurality of MIP-mapped texture maps stored in said texture memory at different levels of detail to produce a texture value for a given pixel fragment that approximates the correct level of texture detail each of the levels of detail including an array of texels grouped into texel blocks and applying said interpolated texture value to pixel fragments;

each of the levels of detail including an array of texels grouped into texel blocks, each texture map representing the appearance of the texture at a given distance from an eye point;

a texel prefetch buffer storing prefetched texel blocks previously read from said texture memory; and

a prefetch tag memory storing tags corresponding to the prefetched texel blocks and used to determine which of the texel blocks are stored in the texel prefetch buffer in order to avoid re-reading a previously read one of the texel blocks from the texture memory;

said tags indicating whether a texel block is stored in the texel prefetch buffer and indicating the location of the texel block in the texel prefetch buffer, the prefetch buffer tag blocks checking a plurality of texture addresses against the stored tags thereby checking for a match, each tag comprising (1) the texture identifier;

(2) the level of detail indicator;

(3) the texture U-coordinate of the stored texel block; and

(4) the texture V-coordinate of the stored texel block;

said texture memory, said texel prefetch buffer, and said prefetch tag memory storing and accessing texture data so that memory access conflicts are reduced and throughput of said texture unit is increased.

2. A deferred graphics pipeline processor as in claim 1, wherein said tags are configured to allow the prefetched texel blocks to be independently prefetched from any texture map and any level of detail.

3. A deferred graphics pipeline processor as in claim 2, wherein said texel block prefetch independence is achieved by providing tags having:

(1) a texture identifier;

(2) a level of detail indicator;

(3) a texture U-coordinate of the stored texel block; and

(4) a texture V-coordinate of the stored texel block.

4. A deferred graphics pipeline processor as in claim 3, wherein said texture unit performing tri-linear interpolation from said texture maps to produce a texture value for a given pixel fragment that approximates the correct level of detail.

5. A texture device for a graphics rendering pipeline, the pipeline receiving a plurality of graphics primitives and generating a rendered image, at least some of the graphics primitives being rendered with at least one texture map, the texture device comprising:

logic receiving texture coordinates corresponding to a pixel fragment;

bank mapping logic translating each of the texture coordinates to a plurality of texture tile addresses, each of the texture tile addresses comprising;

(1) a texture identifier;

(2) a level of detail indicator;

(3) a texture U-coordinate of the stored texture element (texel) block; and

(4) a texture V-coordinate of the stored texel block;

a texture memory storing the texture maps, each of the texture maps being an array of texels, the texels grouped into texel blocks;

a texel prefetch buffer storing prefetched texel blocks, the prefetched texel blocks being the texel blocks read from the texture memory, the texel prefetch buffer organized into a plurality of banks, the number of the banks within the texel prefetch buffer being an integer multiple of the number of texels in the texel block, the texels in any of the prefetched texel blocks being stored in separate ones of said banks, the banks operating in parallel;

a plurality of prefetch buffer tag blocks storing tags, the tags each corresponding to one stored texel block, the tags indicating whether a texel block is stored in the texel prefetch buffer and indicating the location of the texel block in the texel prefetch buffer, the prefetch buffer tag blocks checking the plurality of texture tile addresses against the stored tags in one clock cycle thereby checking for a match, each tag comprising (1) the texture identifier;

(2) the level of detail indicator;

(3) the texture U-coordinate of the stored texel block; and

(4) the texture V-coordinate of the stored texel block; and

prefetch buffer control logic reading the stored texel blocks from the texture memory when the checking does not indicate a needed texel block is not in the texel prefetch buffer.

6. The texture device of claim 5, further comprising:

a plurality of miss queues storing the texture tile addresses that are checked by the prefetch buffer tag blocks and are not present in the prefetch buffer tag blocks;

the prefetch buffer control logic further comprising logic reading the miss queues to determine which tile addresses need to be used to read texel blocks from the texture memory; and

a texture memory management unit translating the texture tile addresses into memory addresses.

7. The texture device of claim 6, further comprising:

a texture array pointer table associating a plurality of texture array identifiers with a corresponding address in the texture memory, each of the texture array identifiers being the combination of the texture identifier and the level of detail; and

the texture memory management unit further comprising logic for reading the texture array pointer table.

8. The texture device of claim 7, wherein the texture array pointer table is stored in the texture memory.

9. The texture device of claim 6, wherein the texture memory management unit further comprises:

swirl logic translating the least significant bits of the texture tile addresses, to form a swirled address, such that the texel blocks in a square group of the texel blocks are sequentially addressed by the swirled address in a manner where each one of the texel blocks in the square group is spatially adjacent to the sequentially previous one of the texel blocks in the square group, except for the sequentially first of the texel blocks in the square group.

10. The texture device of claim 9, wherein the texture memory management unit further comprises:

a texture array pointer table associating a the combination of the texture identifier and the level of detail with a base address into texture memory; and

an adder circuit combining the base address with the swirled address to form a physical address.

11. The texture device of claim 5, further comprising:

a memory queue storing;

(1) a texel prefetch buffer read request comprising a line number of one of the texel blocks within the texel prefetch buffer, the read request being stored into the memory queue if the checking by the prefetch buffer tag blocks indicate the texel block is stored in the texel prefetch buffer; and

(2) a texel prefetch buffer write request comprising a line number in the texel prefetch buffer into which of one of the texel blocks is to be stored, the write request being stored into the memory queue if the checking by the prefetch buffer tag blocks indicate the texel block is not stored in the texel prefetch buffer.

12. The texture device of claim 5, further comprising:

logic reading a plurality of texels in parallel from the texel prefetch buffer; and

texture interpolator logic filtering the read plurality of texels to produce a texture value for the corresponding pixel fragment.

13. The texture device of claim 5, further comprising:

logic for pseudo-randomly selecting a subset of the plurality of banks in the texel prefetch buffer to store even numbered levels of detail for a particular texture map and a different subset of the plurality of banks in the texel prefetch buffer to store the odd numbered levels of detail for the particular texture map, the pseudo-random selection being based on the texture identifier.

14. The texture device of claim 5, further comprising:

a prioritization block prioritizing texture memory read requests from a plurality of sources.

15. The texture device of claim 5, further comprising:

one or more reorder logic blocks, the reorder logic blocks comprising;

(1) a memory control block receiving dispatched addresses and sequentially performing read operations on the texture memory using the dispatched addresses;

(2) a first level reorder queue storing a plurality of current addresses, each of the current addresses being equal to one of the dispatched addresses;

(3) a conflict queue storing stalled addresses, each of the stalled addresses being an address into texture memory that has its corresponding read operation postponed due to an address conflict;

(4) an in-order tag queue storing first tag information, each piece of first tag information corresponding to an address in the first level reorder queue;

(5) an out-of-order tag queue storing second tag information, each piece of second tag information corresponding to an address in the conflict queue;

(6) a conflict detection block comprising;

(6a) logic receiving a new address into texture memory, the new address being part of a sequence of addresses being received in a specific order;

(6b) logic detecting a memory conflict between the new address and any of the plurality of current addresses;

(6c) logic dispatching the new address to the memory control block if the conflict was not detected so as to make the new address into one of the dispatched addresses;

(6d) logic writing the new address into the first level reorder queue if the conflict is not detected so as to make the new address into one of the current addresses;

(6e) logic writing the new address into the conflict queue if the conflict is detected so as to make the new address into one of the stalled addresses;

(6f) logic writing new tag information corresponding to the new address into the in-order tag queue if the conflict is not detected;

(6g) logic writing the new tag information corresponding to the new address into the out-of-order tag queue if the conflict is detected; and

(6h) logic determining when the stalled addresses are dispatched to the memory control block; and

(7) logic reassembling data read from the texture memory into the specific order, the reassembling being done according to the first tag information and the second tag information.

16. A graphics rendering pipeline generating a rendered image from a plurality of graphics primitives, the pipeline comprising:

a hidden surface removal block determining, for each sample in the rendered image, a set of visible graphics primitives from the plurality of graphics primitives, the determining being done before any pixel coloring is done, wherein one or more of the samples from a single visible graphics primitive and within a pixel are grouped together in a visible fragment; and

a texture block generating texture values, the texture block comprising;

a texture memory storing texture maps, each texture map comprising a plurality of levels of detail, each of the level of detail being an array of texels, the texels grouped into texel blocks, each texel block being a two-by-two cluster of texels;

logic receiving texture coordinates corresponding to a visible fragment;

a texel prefetch buffer storing prefetched texel blocks, the prefetched texel blocks being the texel blocks read from the texture memory; and

a prefetch tag memory storing tags corresponding to the prefetched texel blocks, the tags used to determine which of the texel blocks are stored in the texel prefetch buffer in order to avoid re-reading a previously read one of the texel blocks from the texture memory, the tags configured to allow the prefetched texel blocks to be independently prefetched from any texture map and any level of detail, the independence being achieved by the tags being comprised of;

(1) a texture identifier;

(2) a level of detail indicator;

(3) a texture U-coordinate of the stored texel block; and

(4) a texture V-coordinate of the stored texel block.

17. The graphics rendering pipeline of claim 16, wherein the texture block further comprises:

bank mapping logic translating each of the received texture coordinates to a plurality of texture tile addresses, each of the texture tile addresses comprising;

(1) the texture identifier;

(2) the level of detail indicator;

(3) the texture U coordinate of the stored texel block; and

(4) the texture V coordinate of the stored texel block.

18. The graphics rendering pipeline of claim 16, wherein the texture block further comprises:

a plurality of miss queues storing the texture tile addresses that are checked by the prefetch buffer tag blocks and are not present in the prefetch buffer tag blocks;

the prefetch buffer control logic further comprising logic reading the miss queues to determine which tile addresses need to be used to read texel blocks from the texture memory; and

a texture memory management unit translating the texture tile addresses into memory addresses.

19. The graphics rendering pipeline of claim 18, wherein the texture block further comprises:

a texture array pointer table associating a plurality of texture array identifiers with a corresponding address in the texture memory, each of the texture array identifiers being the combination of the texture identifier and the level of detail; and

the texture memory management unit further comprising logic for reading the texture array pointer table.

20. The graphics rendering pipeline of claim 18, wherein the texture memory management unit further comprises:

swirl logic translating the least significant bits of the texture tile addresses, to form a swirled address, such that the texel blocks in a square group of the texel blocks are sequentially addressed by the swirled address in a manner where each one of the texel blocks in the square group is spatially adjacent to the sequentially previous one of the texel blocks in the square group, except for the sequentially first of the texel blocks in the square group.

21. The graphics rendering pipeline of claim 20, wherein the texture memory management unit further comprises:

a texture array pointer table associating a the combination of the texture identifier and the level of detail with a base address into texture memory; and

an adder circuit combining the base address with the swirled address to form a physical address.

22. The graphics rendering pipeline of claim 21, wherein the bits within the physical address that select a memory device from a plurality of devices are derived from the least significant bits of the U coordinate and the V coordinate.

23. The graphics rendering pipeline of claim 22, wherein the texture block further comprises:

logic performing a programmable mapping function of the bits within the physical address to (1) device bits selecting one or more memory devices from a plurality of memory devices; and

(2) bank bits selecting a memory bank within the selected memory device.

24. The graphics rendering pipeline of claim 23, wherein the texture block further comprises:

a prioritization block prioritizing texture memory read requests from a plurality of sources.

25. The graphics rendering pipeline of claim 16, wherein the texture block further comprises:

a memory queue storing;

(1) a texel prefetch buffer read request comprising a line number of one of the texel blocks within the texel prefetch buffer, the read request being stored into the memory queue if the checking by the prefetch buffer tag blocks indicate the texel block is stored in the texel prefetch buffer; and

(2) a texel prefetch buffer write request comprising a line number in the texel prefetch buffer into which of one of the texel blocks is to be stored, the write request being stored into the memory queue if the checking by the prefetch buffer tag blocks indicate the texel block is not stored in the texel prefetch buffer.

26. The graphics rendering pipeline of claim 16, wherein the texture block further comprises:

logic reading a plurality of texels in parallel from the texel prefetch buffer; and

texture interpolator logic filtering the read plurality of texels to produce a texture value for the corresponding pixel fragment.

27. The graphics rendering pipeline of claim 16, wherein the number of banks in the texel prefetch buffer is equal the number of texels filtered by the texture interpolator.

28. The graphics rendering pipeline of claim 16, wherein the texture block further comprises:

logic for pseudo-randomly selecting a subset of the plurality of banks in the texel prefetch buffer to store even numbered levels of detail for a particular texture map and a different subset of the plurality of banks in the texel prefetch buffer to store the odd numbered levels of detail for the particular texture map, the pseudo-random selection being based on the texture identifier.

29. A texture method for a graphics rendering pipeline, the pipeline receiving a plurality of graphics primitives and generating a rendered image, at least some of the graphics primitives being rendered with at least one texture map, the method comprising the steps:

storing the texture maps in a texture memory, each of the texture maps being an array of texels, the texels grouped into texel blocks;

receiving texture coordinates corresponding to a pixel fragment;

translating each of the texture coordinates to a plurality of texture tile addresses, each of the texture tile addresses comprising;

(1) a texture identifier;

(2) a level of detail indicator;

(3) a texture U-coordinate of the stored texture element (texel) block; and

(4) a texture V-coordinate of the stored texel block;

storing prefetched texel blocks in a texel prefetch buffer, the prefetched texel blocks being the texel blocks read from the texture memory, the texel prefetch buffer organized into a plurality of banks, the number of the banks within the texel prefetch buffer being an integer multiple of the number of texels in the texel block, the texels in any of the prefetched texel blocks being stored in separate ones of said banks, the banks operating in parallel;

storing tags in a plurality of prefetch buffer tag blocks, the tags each corresponding to one stored texel block, the tags indicating whether a texel block is stored in the texel prefetch buffer and indicating the location of the texel block in the texel prefetch buffer, the prefetch buffer tag blocks checking the plurality of texture tile addresses against the stored tags in one clock cycle thereby checking for a match, each tag comprising (1) the texture identifier;

(2) the level of detail indicator;

(3) the texture U-coordinate of the stored texel block; and

(4) the texture V-coordinate of the stored texel block; and

reading the stored texel blocks from the texture memory when the checking does not indicate a needed texel block is not in the texel prefetch buffer.

30. The method of claim 29, further comprising the steps:

storing the texture tile addresses that are checked by the prefetch buffer tag blocks and are not present in the prefetch buffer tag blocks into a plurality of miss queues;

reading the miss queues to determine which tile addresses need to be used to read texel blocks from the texture memory; and

translating the texture tile addresses into memory addresses.

31. The method of claim 30, further comprising the steps:

associating a plurality of texture array identifiers with a corresponding address in the texture memory, each of the texture array identifiers being the combination of the texture identifier and the level of detail;

reading the texture array pointer table,

reading a plurality of texels in parallel from the texel prefetch buffer; and

filtering the read plurality of texels to produce a texture value for the corresponding pixel fragment,

prioritizing texture memory read requests from a plurality of sources,

maintaining a list of current addresses, each of the current addresses being an address into the texture memory that has been dispatched to the texture memory as part of a memory read operation that has not yet completed;

maintaining a list of stalled addresses, each of the stalled addresses being an address into the texture memory that has its corresponding read operation postponed due to an address conflict;

maintaining a list of first tag information, each piece of first tag information corresponding to an address in the list of current addresses;

maintaining a list of second tag information, each piece of second tag information corresponding to an address in the list of stalled addresses;

receiving a new address into texture memory, the new address being part of a sequence of addresses being received in a specific order,

detecting the presence of a memory conflict between the new address and any of the current addresses;

if the conflict is not detected, dispatching the new address to perform a read operation from the texture memory;

if the conflict is not detected, adding the new address to the list of current;

if the conflict is detected, adding the new address to the list of stalled addresses;

if the conflict is not detected, adding the new tag information corresponding to the new address to the list of first tag information;

if the conflict is detected, adding the new tag information corresponding to the new address to the list of second tag information;

determining when the stalled addresses are dispatched to the memory control block; and

reassembling data read from the texture memory into the specific order, the reassembling being done according to the first tag information and the second tag information.

32. The method of claim 29, further comprising the step:

storing into a memory queue;

(1) a texel prefetch buffer read request comprising a line number of one of the texel blocks within the texel prefetch buffer, the read request being stored into the memory queue if the checking by the prefetch buffer tag blocks indicate the texel block is stored in the texel prefetch buffer; and

(2) a texel prefetch buffer write request comprising a line number in the texel prefetch buffer into which of one of the texel blocks is to be stored, the write request being stored into the memory queue if the checking by the prefetch buffer tag blocks indicate the texel block is not stored in the texel prefetch buffer.

33. In a graphics pipeline processor, a method for generating texture values associated with pixels or pixel fragments, said method comprising:

storing a plurality of texture maps in a texture memory, each of said plurality of texture maps including an array of texels grouped into texel blocks;

reading a texel block from said texture memory;

storing said read texel block in a texel prefetch buffer;

storing tags corresponding to the texel blocks in a prefetch tag memory;

said tags indicating whether a texel block is stored in the texel prefetch buffer and indicating the location of the texel block in the texel prefetch buffer, the prefetch buffer tag blocks checking a plurality of texture addresses against the stored tags thereby checking for a match, each tag comprising;

(1) the texture identifier;

(2) the level of detail indicator;

(3) the texture U-coordinate of the stored texel block; and

(4) the texture V-coordinate of the stored texel block;

querying said tags prior to reading said texture memory to determine which of the texel blocks requested to be read are already stored in the texel prefetch buffer;

retrieving said texel blocks preferentially from said texel prefetch buffer when so stored and from said texture memory when not so stored in order to avoid re-reading a previously read one of the texel blocks from said texture memory; and

processing said retrieved texel blocks to generate said texture value.

34. The method in claim 33, wherein said texture maps are stored in said texture memory at different levels of detail representing the appearance of the texture at a given distance from an eye point.

35. The method in claim 33, wherein said plurality of texture maps comprise a plurality of MIP-mapped texture maps;

and said processing includes interpolating said plurality of MIP-mapped texture maps to produce a texture value for a given pixel fragment that approximates the correct level of texture detail for the appearance of the texture at the distance or the pixel fragment from the eye point.

36. The method in claim 33, wherein said tags are configured to allow the prefetched texel blocks to be independently prefetched from any texture map and any level of detail.

37. In a graphics pipeline processor, a method for generating texture values associated with pixels or pixel fragments, said method comprising:

storing a plurality of texture maps in a texture memory, each of said plurality of texture maps including an array of texels grouped into texel blocks;

reading a texel block from said texture memory;

storing said read texel block in a texel prefetch buffer;

storing tags corresponding to the texel blocks in a prefetch tag memory;

querying said tags prior to reading said texture memory to determine which of the texel blocks requested to be read are already stored in the texel prefetch buffer;

retrieving said texel blocks preferentially from said texel prefetch buffer when so stored and from said texture memory when not so stored in order to avoid re-reading a previously read one of the texel blocks from said texture memory; and

processing said retrieved texel blocks to generate said texture value, wherein said tags are configured to allow the prefetched texel blocks to be independently prefetched from any texture map and any level of detail, said texel block prefetch independence being achieved by providing tags having;

(1) a texture identifier, (2) a level of detail indicator, (3) a texture U-coordinate of the stored texel block, and (4) a texture V-coordinate of the stored texel block.

38. In a graphics pipeline processor, a method for generating texture values associated with pixels or pixel fragments, said method comprising:

storing a plurality of MIP-mapped texture maps in a texture memory, each of said plurality of texture maps including an array of texels grouped into texel blocks;

reading a texel block from said texture memory;

storing said read texel block in a texel prefetch buffer;

storing tags corresponding to the texel blocks in a prefetch tag memory;

querying said tags prior to reading said texture memory to determine which of the texel blocks requested to be read are already stored in the texel prefetch buffer;

retrieving said texel blocks preferentially from said texel prefetch buffer when so stored and from said texture memory when not so stored in order to avoid re-reading a previously read one of the texel blocks from said texture memory; and

processing said retrieved texel blocks to generate said texture value, said processing including interpolating said plurality of MIP-mapped texture maps to produce a texture value for a given pixel fragment that approximates the correct level of texture detail for the appearance of the texture at the distance or the pixel fragment from the eye point;

said tags being configured to allow the prefetched texel blocks to be independently prefetched from any texture map and any level of detail; and

said texel block prefetch independence being achieved by providing tags having;

(1) a texture identifier;

(2) a level of detail indicator; and

(3) texture coordinates of the stored texel block.

39. The method in claim 38, wherein said texture coordinates comprise a texture U-coordinate of the stored texel block, and a texture V-coordinate of the stored texel block.