System and method of generating interactive computer graphic images incorporating three dimensional textures

• US 5,490,240 A
• Filed: 07/09/1993
• Issued: 02/06/1996
• Est. Priority Date: 07/09/1993
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Silicon Graphics Incorporated (Graphics Properties Holdings, Inc.)
• Inventors: Drebin, Robert A., Buchner, Gregory C., Foran, James L., Montrym, John S.
• Primary Examiner(s): Herndon, Heather R.
• Assistant Examiner(s): VO, CLIFF N
• Application Number:
  US08/088,716
• Time in Patent Office: 942 Days
• Field of Search: 395/130, 395/125, 395/126, 395/128, 395/129, 395/132, 395/131
• US Class Current: 345/587
• CPC Class Codes: G06T 15/04 Texture mapping

Abstract

A system and method of interactively generating computer graphic images for incorporating three dimensional textures. The method of the present invention includes defining an orientation of a polygon relative to a plurality of three dimensional (3D) texture data sets, determining a level of detail of a pixel associated with the polygon, and selecting a first 3D texture data set and a second 3D texture data set from the plurality of 3D texture data sets in accordance with the pixel level of detail. The method also includes mapping the pixel to a first position within the first 3D texture data set and to a second position within the second 3D texture data set in accordance with the orientation, and generating a display value for the pixel in accordance with the mapping of the pixel to the first and second positions.

Claims

1. An apparatus for interactively generating computer graphic images incorporating three dimensional textures, comprising:

polygon orientation defining means for defining an orientation of a polygon relative to a plurality of three dimensional (3D) texture data sets, each of the 3D texture data sets being at a distinct level of detail;

level of detail determining means for determining a level of detail of a pixel associated with said polygon;

texture data set selecting means for selecting a first 3D texture data set and a second 3D texture data set from said plurality of 3D texture data sets in accordance with said pixel level of detail such that said first 3D texture data set represents a magnification of said pixel, and said second 3D texture data set represents a minification of said pixel;

pixel mapping means for mapping said pixel to a first position within said first 3D texture data set and a second position within said second 3D texture data set in accordance with said orientation; and

pixel value generating means for generating a display value for said pixel in accordance with said mapping of said pixel to said first and second positions.

2. The apparatus of claim 1 in which dimensions of said 3D texture data sets are scaled to a predetermined range, said polygon orientation defining means comprising means for assigning three texture coordinates to each vertex of said polygon, each of said texture coordinates being within said predetermined range such that said polygon is similarly oriented relative to all of said 3D texture data sets.

3. The apparatus of claim 1, wherein said pixel mapping means comprises means for calculating scaled object-space three dimensional texture coordinates (S ,T, U) for the pixel for each of said first and second 3D texture data sets in accordance with:

space="preserve" listing-type="equation">S=(S/w)/(1/w)

space="preserve" listing-type="equation">T=(T/w)/(1/w)

space="preserve" listing-type="equation">U=(U/w)/(1/w)

wherein S/w, T/w, and U/w represent scaled screen-space three dimensional texture coordinates and 1/w represents a perspective correction term.

4. The apparatus of claim 1, wherein said pixel value generating means comprises:

texel identifying means for identifying N texels of said first 3D texture data set surrounding said first position, and for identifying N texels of said second 3D texture data set surrounding said second position;

intermediate pixel value producing means for producing a first intermediate pixel value as a function of values associated with said identified texels of said first 3D texture data set, and for producing a second intermediate pixel value as a function of values associated with said identified texels of said second 3D texture data set; and

display value producing means for producing said display value for said pixel as a function of said first and second intermediate pixel values.

5. The apparatus of claim 4, wherein said display value producing means comprises means for interpolating among said first and second intermediate pixel values to thereby produce said display value.

6. The apparatus of claim 4 in which each of said values associated with said identified texels of said first and second 3D texture data sets represents an image attribute, wherein said intermediate pixel value producing means comprises means for interpolating among said values associated with said identified texels of said first 3D texture data set to thereby produce said first intermediate pixel value, and for interpolating among said values associated with said identified texels of said second 3D texture data set to thereby produce said second intermediate pixel value.

7. The apparatus of claim 4, further comprising a table having a plurality of indexed entries, a distinct image attribute being stored in each of said indexed entries, each of said values associated with said identified texels of said first and second 3D texture data sets representing an index to said table, said intermediate pixel value producing means comprising:

means for interpolating among said values associated with said identified texels of said first 3D texture data set to produce a first interpolated index to said table, and for interpolating among said values associated with said identified texels of said second 3D texture data set to produce a second interpolated index to said table; and

means for accessing said table using said first and second interpolated indices and for extracting image attributes from said table in accordance with said table accesses to thereby produce said first and second intermediate pixel values, said first and second intermediate pixel values being respectively set equal to said extracted image attributes.

8. The apparatus of claim 4, further comprising a table having a plurality of indexed entries, a distinct image attribute being stored in each of said indexed entries, each of said values associated with said identified texels of said first and second 3D texture data sets representing an index to said table, said intermediate pixel value producing means comprising:

means for accessing said table using said values associated with said identified texels of said first and second 3D texture data sets and for extracting image attributes from said table in accordance with said table accesses; and

means for interpolating among said extracted image attributes to thereby produce said first and second intermediate pixel values.

9. A method of interactively generating computer graphic images incorporating three dimensional textures, comprising the steps of:

(a) defining an orientation of a polygon relative to a plurality of three dimensional (3D) texture data sets, each of the 3D texture data sets being at a distinct level of detail;

(b) determining a level of detail of a pixel associated with said polygon;

(c) selecting a first 3D texture data set and a second 3D texture data set from said plurality of 3D texture data sets in accordance with said pixel level of detail such that said first 3D texture data set represents a magnification of said pixel, and said second 3D texture data set represents a minification of said pixel;

(d) mapping said pixel to a first position within said first 3D texture data set and a second position within said second 3D texture data set in accordance with said orientation; and

(e) generating a display value for said pixel in accordance with said mapping of said pixel to said first and second positions.

10. The method of claim 9 in which dimensions of said 3D texture data sets are scaled to a predetermined range, step (a) comprising the step of assigning three texture coordinates to each vertex of said polygon, each of said texture coordinates corresponding to a respective dimension of said 3D texture data sets and being within said predetermined range such that said polygon is similarly oriented relative to all of said 3D texture data sets.

11. The method of claim 9, wherein step (d) comprises the step of calculating scaled object-space three dimensional texture coordinates (S,T,U) for the pixel for each of said first and second 3D texture data sets in accordance with:

space="preserve" listing-type="equation">S=(S/w)/(1/w)

space="preserve" listing-type="equation">T=(T/w)/(1/w)

space="preserve" listing-type="equation">U=(U/w)/(1/w)

wherein S/w, T/w, and U/w represent scaled screen-space three dimensional texture coordinates and 1/w represents a perspective correction term.

12. The method of claim 9, wherein step (e) comprises the steps of:

(i) identifying N texels of said first 3D texture data set surrounding said first position, and N texels of said second 3D texture data set surrounding said second position;

(ii) producing a first intermediate pixel value as a function of values associated with said identified texels of said first 3D texture data set, and a second intermediate pixel value as a function of values associated with said identified texels of said second 3D texture data set; and

(iii) producing said display value for said pixel as a function of said first and second intermediate pixel values.

13. The method of claim 12, wherein step (iii) comprises the step of interpolating among said first and second intermediate pixel values to thereby produce said display value.

14. The method of claim 12 in which each of said values associated with said identified texels of said first and second 3D texture data sets represents an image attribute, wherein step (ii) comprises the steps of:

interpolating among said values associated with said identified texels of said first 3D texture data set to thereby produce said first intermediate pixel value; and

interpolating among said values associated with said identified texels of said second 3D texture data set to thereby produce said second intermediate pixel value.

15. The method of claim 12 in which a table having a plurality of indexed entries is defined, a distinct image attribute being stored in each of said indexed entries, each of said values associated with said identified texels of said first and second 3D texture data sets representing an index to said table, wherein step (ii) comprises the steps of:

interpolating among said values associated with said identified texels of said first 3D texture data set to produce a first interpolated index to said table, and among said values associated with said identified texels of said second 3D texture data set to produce a second interpolated index to said table; and

accessing said table using said first and second interpolated indices and extracting image attributes from said table in accordance with said table accesses to thereby produce said first and second intermediate pixel values, said first and second intermediate pixel values being respectively set equal to said extracted image attributes.

16. The method of claim 12, in which a table having a plurality of indexed entries is defined, a distinct image attribute being stored in each of said indexed entries, each of said values associated with said identified texels of said first and second 3D texture data sets representing an index to said table, wherein step (ii) comprises the steps of:

accessing said table using said values associated with said identified texels of said first and second 3D texture data sets and extracting image attributes from said table in accordance with said table accesses; and

interpolating among said extracted image attributes to thereby produce said first and second intermediate pixel values.

17. An apparatus for interactively generating computer graphic images incorporating three dimensional textures, comprising:

a storage device for storing a three dimensional (3D) texture data set, said storage device comprising N memory banks each storing a predetermined portion of said 3D texture data set;

polygon orientation defining means for defining an orientation of a polygon relative to said 3D texture data set;

pixel mapping means for mapping a pixel associated with said polygon to an object-space position within said 3D texture data set in accordance with said orientation;

texel identifying means for identifying N texels of said 3D texture data set surrounding said object-space position;

linear address generating means for generating linear addresses from object-space addresses associated with said identified texels;

means for obtaining N values associated with said identified texels by accessing said storage device using said linear addresses, one of said values being obtained from each of said memory banks; and

pixel value generating means for generating a value for said pixel as a function of said values associated with said identified texels.

18. The apparatus of claim 17 in which said 3D texture data set is from a collection of images having varying levels of detail, dimensions of said images having said varying levels of detail being scaled to a predetermined range, said polygon orientation defining means comprising means for assigning three of texture coordinates to each vertex of said polygon, each of said texture coordinates corresponding to a respective dimension of images in said 3D texture data set and being within said predetermined range such that said polygon is similarly oriented relative to all of said images.

19. The apparatus of claim 17, wherein said pixel mapping means comprises means for calculating scaled object-space three dimensional texture coordinates (S, T, U) for the pixel in accordance with:

space="preserve" listing-type="equation">S=(S/w)/(1/w)

space="preserve" listing-type="equation">T=(T/w)/(1/w)

space="preserve" listing-type="equation">U=(U/w)/(1/w)

wherein S/w, T/w, and U/w represent scaled screen-space three dimensional texture coordinates and 1/w represents a perspective correction term.

20. The apparatus of claim 17 in which each of said values associated with said identified texels represents an image attribute, wherein said pixel value generating means comprises means for interpolating among said values associated with said identified texels to thereby produce said pixel value.

21. The apparatus of claim 17, further comprising a table having a plurality of indexed entries, a distinct image attribute being stored in each of said indexed entries, each of said values associated with said identified texels representing an index to said table, said pixel value generating means comprising:

means for interpolating among said values associated with said identified texels to produce an interpolated index to said table; and

means for accessing said table using said interpolated index and for extracting an image attribute from said table in accordance with said table access to thereby produce said pixel value, said pixel value being set equal to said extracted image attribute.

22. The apparatus of claim 17, further comprising a table having a plurality of indexed entries, a distinct image attribute being stored in each of said indexed entries, said values associated with said identified texels representing indices to said table, said pixel value generating means comprising:

means for accessing said table using said values associated with said identified texels and for extracting image attributes from said table in accordance with said table access; and

means for interpolating among said extracted image attributes to thereby produce said pixel value.

23. A method of interactively generating computer graphic images incorporating three dimensional textures, comprising the steps of:

(a) storing a three dimensional (3D) texture data set in a storage device comprising N memory banks each storing a predetermined portion of said 3D texture data set;

(b) defining an orientation of a polygon relative to said 3D texture data set;

(c) mapping a pixel associated with said polygon to an object-space position within said 3D texture data set in accordance with said orientation;

(d) identifying N texels of said 3D texture data set surrounding said object-space position;

(e) generating linear addresses from object-space addresses associated with said identified texels;

(f) obtaining N values associated with said identified texels by accessing said storage device using said linear addresses, one of said values being obtained from each of said memory banks; and

(g) generating a value for said pixel as a function of said values associated with said identified texels.

24. The method of claim 23 in which said 3D texture data set is from a collection of images having varying levels of detail, dimensions of said images having said varying levels of detail being scaled to a predetermined range, step (b) comprising the step of assigning three texture coordinates to each vertex of said polygon, each of said texture coordinates corresponding to a respective dimension of images in said 3D texture data set and being within said predetermined range such that said polygon is similarly oriented relative to all of said images.

25. The method of claim 23, wherein step (c) comprises the step of calculating scaled object-space three dimensional texture coordinates (S, T, U) for the pixel in accordance with:

space="preserve" listing-type="equation">S=(S/w)/(1/w)

space="preserve" listing-type="equation">T=(T/w)/(1/w)

space="preserve" listing-type="equation">U=(U/w)/(1/w)

wherein S/w, T/w, and U/w represent scaled screen-space three dimensional texture coordinates and 1/w represents a perspective correction term.

26. The method of claim 23 in which each of said values associated with said identified texels represents an image attribute, wherein step (g) comprises the step of interpolating among said values associated with said identified texels to thereby produce said pixel value.

27. The method of claim 23 in which a table having a plurality of indexed entries is defined, a distinct image attribute being stored in each of said indexed entries, each of said values associated with said identified texels representing an index to said table, wherein step (g) comprises the steps of:

interpolating among said values associated with said identified texels to produce an interpolated index to said table; and

accessing said table using said interpolated index and extracting an image attribute from said table in accordance with said table access to thereby produce said pixel value, said pixel value being set equal to said extracted image attribute.

28. The method of claim 23 in which a table having a plurality of indexed entries is defined, a distinct image attribute being stored in each of said indexed entries, said values associated with said identified texels representing indices to said table, wherein step (g) comprises the steps of:

accessing said table using said values associated with said identified texels and extracting image attributes from said table in accordance with said table access; and

interpolating among said extracted image attributes to thereby produce said pixel value.

29. An apparatus for interactively generating computer graphic images incorporating three dimensional textures, comprising:

polygon orientation defining means for defining an orientation of a polygon relative to a three dimensional (3D) texture data set;

pixel mapping means, coupled to said polygon orientation defining means, for mapping a pixel associated with said polygon to a position within said 3D texture data set in accordance with said orientation;

storage means for storing a plurality of entries, a distinct image attribute being stored in each of said entries;

texel identifying means for identifying N texels of said 3D texture data set surrounding said position, each of said texels being associated with a value representing an address to said storage means;

means for interpolating among values associated with said identified texels to produce an interpolated address to said storage means; and

means for extracting an image attribute from said storage means using said interpolated address to thereby produce a value for said pixel, said pixel value being set equal to said extracted image attribute.