Two component texture map compression

• US 7,961,195 B1
• Filed: 11/16/2004
• Issued: 06/14/2011
• Est. Priority Date: 11/16/2004
• Status: Active Grant

• Current Assignee: NVIDIA Corporation
• Original Assignee: NVIDIA Corporation
• Inventors: Rogers, Douglas H., Donovan, Walter E., King, Gary C.
• Primary Examiner(s): Tung; Kee M
• Assistant Examiner(s): CRAWFORD, JACINTA M
• Application Number:
  US10/990,900
• Time in Patent Office: 2,401 Days
• Field of Search: 345/555, 345/582, 382/162, 382/254, 708/655
• US Class Current: 345/555
• CPC Class Codes: G06T 15/04 Texture mapping
• CPC Class Codes: G06T 9/00 Image coding bandwidth or redundancy reduction for static pictures H04N1/41; coding or decoding of static colour picture signals H04N1/64; methods or arrangements for coding, decoding, compressing or decompressing digital video signals H04N19/00

Abstract

Methods and systems for compressing and decompressing data are described. A first value of N+1 bits and a second value of N+1 bits are reduced to strings of N bits each. The first and second strings of N bits are stored in a particular order relative to one another in a compression block. The particular order in which the first and second strings of N bits are stored in the compression block is used to derive a bit value that is then used in combination with one of the strings of N bits to reconstruct that string as N+1 bits.

Claims

1. A method of compressing and decompressing data, said method comprising:

reducing a first multi-bit value comprising N+1 bits and a second multi-bit value comprising N+1 bits to respective first and second strings of N bits each;

storing said first and second strings of N bits in a particular order relative to one another in a memory-resident compression block; and

using said particular order in which said first and second strings of N bits are stored in said compression block to derive a first single-bit value, wherein said first single-bit value has one binary value if said first multi-bit value is stored before said second multi-bit value in said compression block and otherwise said first single-bit value has the other binary value, wherein said first single-bit value is appended as the least significant bit of one of said first and second strings of N bits to reconstruct said one of said first and second strings as N+1 bits.

2. The method of claim 1 wherein said storing further comprises:

determining the relative magnitude of said first and second multi-bit values;

determining the values of the least significant bits of said first and second multi-bit values; and

using said values of said least significant bits and said relative magnitude to determine said particular order for storing said first and second strings of N bits in said compression block.

3. The method of claim 2 further comprising:

determining which of said first and second strings of N bits in said compression block has the smaller magnitude; and

appending said first single-bit value to said one of said first and second strings having said smaller magnitude.

4. The method of claim 1 wherein N+1 is 9 and wherein said first and second strings of N bits are signed values normalized to the range of [−

1, 1] coded in 8 bits each, said 8 bits having a value in the range of [−

127, 127].

5. The method of claim 1 further comprising:

reducing a third multi-bit value comprising N+1 bits and a fourth multi-bit value comprising N+1 bits to respective third and fourth strings of N bits each;

storing said third and fourth strings of N bits in a particular order relative to one another in said compression block; and

using the particular order in which said third and fourth strings of N bits are stored in said compression block to derive a second single-bit value that is then used in combination with one of said third and fourth strings of N bits to reconstruct said one of said third and fourth strings as N+1 bits.

6. The method of claim 1 further comprising:

accessing a block of data comprising a plurality of data values;

determining said first multi-bit value and said second multi-bit value, said first multi-bit value and said second multi-bit value bounding said data values;

calculating a range of values by interpolating between said first and second multi-bit values;

indexing said first multi-bit value, said second multi-bit value and each value in said range of values with respective bit codes;

associating each of said data values in said block of data with a bit code selected from said respective bit codes; and

storing bit codes so selected in said compression block.

7. The method of claim 1 wherein said data comprise data for a normal map used in graphics processing.

8. The method of claim 1 wherein said data comprise spherical harmonic data.

9. The method of claim 1 further comprising reducing said first and second multi-bit values to N bits by truncating their least significant bits.

10. A computer system comprising:

a processor; and

a memory unit coupled to said processor, said memory unit containing instructions that when executed implement a method for compressing and decompressing data, said method comprising;

reducing a first multi-bit value comprising N+1 bits and a second multi-bit value comprising N+1 bits to respective first and second strings of N bits each;

storing said first and second strings of N bits in a particular order relative to one another in a memory-resident compression block; and

using said particular order in which said first and second strings of N bits are stored in said compression block to derive a first single-bit value, wherein said first single-bit value has one binary value if said first multi-bit value is stored before said second multi-bit value in said compression block and otherwise said first multi-bit value has the other binary value, wherein said first multi-bit value is appended as the least significant bit of one of said first and second strings of N bits to reconstruct said one of said first and second strings as N+1 bits.

11. The computer system of claim 10 wherein said storing of said method further comprises:

determining the relative magnitude of said first and second multi-bit values;

determining the values of the least significant bits of said first and second multi-bit values;

and using said values of said least significant bits and said relative magnitude to determine said particular order for storing said first and second strings of N bits in said compression block.

12. The computer system of claim 11 wherein said method further comprises:

determining which of said first and second strings of N bits in said compression block has the smaller magnitude; and

appending said first single-bit value to said one of said first and second strings having said smaller magnitude.

13. The computer system of claim 10 wherein N+1 is 9 and wherein said first and second strings of N bits are signed values normalized to the range of [−

1, 1] coded in 8 bits each, said 8 bits having a value in the range of [−

127, 127].

14. The computer system of claim 10 wherein said method further comprises:

reducing a third multi-bit value comprising N+1 bits and a fourth multi-bit value comprising N+1 bits to respective third and fourth strings of N bits each;

storing said third and fourth strings of N bits in a particular order relative to one another in said compression block; and

using the particular order in which said third and fourth strings of N bits are stored in said compression block to derive a second single-bit value that is then used in combination with one of said third and fourth strings of N bits to reconstruct said one of said third and fourth strings as N+1 bits.

15. The computer system of claim 10 wherein said method further comprises:

accessing a block of data comprising a plurality of data values;

determining said first multi-bit value and said second multi-bit value, said first multi-bit value and said second multi-bit value bounding said data values;

calculating a range of values by interpolating between said first and second multi-bit values;

indexing said first multi-bit value, said second multi-bit value and each value in said range of values with respective bit codes;

associating each of said data values in said block of data with a bit code selected from said respective bit codes; and

storing bit codes so selected in said compression block.

16. The computer system of claim 10 wherein said data comprise data for a normal map used in graphics processing.

17. The computer system of claim 10 wherein said data comprise spherical harmonic data.

18. The computer system of claim 10 wherein said method further comprises reducing said first and second multi-bit values to N bits by truncating their least significant bits.

19. A computer-readable memory unit having computer-readable program instructions stored therein for causing a computer system to perform a method comprising:

reducing a first multi-bit value comprising N+1 bits and a second multi-bit value comprising N+1 bits to respective first and second strings of N bits each;

storing said first and second strings of N bits in a particular order relative to one another in a memory-resident compression block; and

using said particular order in which said first and second strings of N bits are stored in said compression block to derive a first single-bit value, wherein said first single-bit value has one binary value if said first multi-bit value is stored before said second multi-bit value in said compression block and otherwise said first single-bit value has the other binary value, wherein said first single-bit value is appended as the least significant bit of one of said first and second strings of N bits to reconstruct said one of said first and second strings as N+1 bits.

20. The computer-readable memory unit of claim 19 wherein said computer-readable program instructions stored therein causes a computer system to perform said method wherein said storing further comprises:

determining the relative magnitude of said first and second multi-bit values;

determining the values of the least significant bits of said first and second multi-bit values; and

using said values of said least significant bits and said relative magnitude to determine said particular order for storing said first and second multi-bit values in said compression block.

21. The computer-readable memory unit of claim 20 wherein said computer-readable program instructions stored therein causes a computer system to perform said method further comprising:

determining which of said first and second strings of N bits in said compression block has the smaller magnitude; and

appending said first single-bit value to said one of said first and second strings having said smaller magnitude.

22. The computer-readable memory unit of claim 19 wherein N+1 is 9 and wherein said first and second strings of N bits are signed values normalized to the range of [−

1, 1] coded in 8 bits each, said 8 bits having a value in the range of [−

127, 127].

23. The computer-readable memory unit of claim 19 wherein said computer-readable program instructions stored therein causes a computer system to perform said method further comprising:

reducing a third multi-bit value comprising N+1 bits and a fourth multi-bit value comprising N+1 bits to respective third and fourth strings of N bits each;

storing said third and fourth strings of N bits in a particular order relative to one another in said compression block; and

using the particular order in which said third and fourth strings of N bits are stored in said compression block to derive a second single-bit value that is then used in combination with one of said third and fourth strings of N bits to reconstruct said one of said third and fourth strings as N+1 bits.

24. The computer-readable memory unit of claim 19 wherein said computer-readable program instructions stored therein causes a computer system to perform said method further comprising:

accessing a block of data comprising a plurality of data values;

determining said first multi-bit value and said second multi-bit value, said first multi-bit value and said second multi-bit value bounding said data values;

calculating a range of values by interpolating between said first and second multi-bit values;

indexing said first multi-bit value, said second multi-bit value and each value in said range of values with respective bit codes;

associating each of said data values in said block of data with a bit code selected from said respective bit codes; and

storing bit codes so selected in said compression block.

25. The computer-readable memory unit of claim 24 wherein said block of data comprise data for a normal map used in graphics processing.

26. The computer-readable memory unit of claim 24 wherein said block of data comprise spherical harmonic data.

27. The computer-readable memory unit of claim 19 wherein said computer-readable instructions stored therein causes a computer system to perform said method further comprising reducing said first and second multi-bit values to N bits by truncating their least significant bits.

28. A computer-readable memory unit having a block of compressed data stored therein for causing a functional change in the operation of a device, said block of compressed data comprising:

a first portion and a second portion for storing a first multi-bit value and a second multi-bit value comprising N bits each, said first and second multi-bit values stored in said block of compressed data in a particular order relative to one another; and

a first plurality of portions for storing bit codes for a first set of data values that are indexed to a first range of values that are interpolated from said first and second multi-bit values;

wherein said particular order in which said first and second multi-bit values of N bits are stored in said block of compressed data is used to derive a first single-bit value, wherein said first single-bit value has one binary value if said first multi-bit value is stored before said second multi-bit value in said compression block and otherwise said first single-bit value has the other binary value, wherein said first single-bit value is appended as the least significant bit to one of said first and second multi-bit values of N bits to create a value comprising N+1 bits.

29. The computer-readable memory unit of claim 28 wherein said first bit single-bit value is appended to said one of said first and second multi-bit values of N bits having a smaller relative magnitude.

30. The computer-readable memory unit of claim 28 wherein if said first portion of said block of compressed data contains a value that is smaller in magnitude than a value in said second portion then said first single-bit value has a first binary value, and if said first portion of said block of compressed data contains a value that is greater in magnitude than a value in said second portion then said first single-bit value has a second binary value.

31. The computer-readable memory unit of claim 28 further comprising:

a third portion and a fourth portion for storing a third multi-bit value and a fourth multi-bit value comprising N bits each, said third and fourth multi-bit values stored in a second particular order relative to one another; and

a second plurality of portions for storing bit codes for a second set of data values that are indexed to a second range of values that are interpolated from said third and fourth multi-bit values;

wherein said second particular order in which said third and fourth multi-bit values of N bits are stored in said block of compressed data is used to derive a second single-bit value that is then appended to one of said third and fourth multi-bit values of N bits to create a value comprising N+1 bits.

32. The computer-readable memory unit of claim 28 wherein N is 8 and wherein said first and second multi-bit values of N bits are signed values normalized to the range of [−

1, 1], said 8 bits having a value in the range of [−

127, 127].

33. The computer-readable memory unit of claim 28 wherein said block of compressed data comprise data for a normal map used in graphics processing.

34. The computer-readable memory unit of claim 28 wherein said block of compressed data comprise spherical harmonic data.

35. A method of compressing and decompressing data, said method comprising:

reading a first value in a compression block, wherein said first value is a signed value comprising N bits and normalized to the range of [−

1, 1], said N bits having a value substantially in the range of [−

2<sup>N−

1</sup>, 2<sup>N−

1</sup>−

1]; and

using said first value to identify a type of compression used to encode data in said compression block, wherein if said first value is −

2<sup>N−

1</sup> then a first type of compression is used and otherwise a second type of compression is used;

wherein according to said first type of compression said compression block comprises;

a portion for storing said first value; and

a plurality of portions for storing compressed data values; and

wherein according to said second type of compression said compression block comprises;

a first portion for storing said first value and a second portion for storing a second value, said first and second values stored in said compression block in a particular first order relative to one another, wherein said particular first order is used to derive a first bit value that is then appended to one of said first and second values to create a value comprising N+1 bits; and

a first plurality of portions for storing bit codes for a first set of data values that are indexed to a first range of values that are interpolated from said first and second values.

36. The method of claim 35 wherein according to said second type of compression said compression block further comprises:

a third portion for storing a third value and a fourth portion for storing a fourth value, said third and fourth values stored in said compression block in a particular second order relative to one another, wherein said particular second order is used to derive a second bit value that is then appended to one of said third and fourth values to create a value comprising N+1 bits;

and a second plurality of portions for storing bit codes for a second set of data values that are indexed to a second range of values that are interpolated from said third and fourth values.

37. The method of claim 35 wherein N is 8.