Compressed lossless texture representation and caching

ABSTRACT

A number of texture compression algorithms have been proposed to reduce texture storage size and bandwidth requirements. To deal with the requirement for random access, these algorithms usually divide the texture into tiles and apply a fixed rate compression scheme to each tile. Fixed rate schemes are by nature lossy, and cannot adapt to local changes in image complexity. Multiresolution schemes, a form of variable-rate coding, can adapt to varying image complexity but suffer from fragmentation and can only compress a limited class of images. On the other hand, several lossless image compression standards have been established. Lossless compression requires variable-rate coding, and more efficient lossy algorithms also use variable-rate coding. Unfortunately, these standards cannot be used directly as texture compression schemes since they do not allow random access.

We present a block-oriented lossless texture compression algorithm based on a simple variable-bitrate differencing scheme. A B-tree index enables both random access and efficient 0(1) memory allocation without external fragmentation. Textures in our test suite compressed to between 6% and 95% of their original sizes. We propose a cache architecture designed to support our compression scheme. Cycle-accurate simulation shows that this cache architecture consistently reduces the external bandwidth requirements as well as the storage size without significantly affecting latency.

References

1. {ASMW97} Anderson B., Stewart A., Macaulay R., Whitted T.: Accommodating memory latency in a low-cost rasterizer. In Proc. Graphics Hardware (1997), pp. 97--101.
2. {BAC96} Beers A. C., Agrawala M., Chaddha N.: Rendering from compressed textures. Proc. SIGGRAPH (1996), 373--378.
3. {Bar97} Barkans A. C.: High quality rendering using the Talisman architecture. In Proc. Graphics Hardware (1997), pp. 79--88.
4. {CH02} Carr N. A., Hart J. C.: Meshed atlases for real-time procedural solid texturing. ACM Trans. on Graphics 21, 2 (Apr. 2002), 106--131.
5. {CSE01} Christopoulos C., Skodras A., Ebrahimi T.: The JPEG 2000 still image coding system. IEEE Signal Processing Mag. 18 (Sept. 2001), 336--58.
6. {GA99} Goris A. C., Alcorn B. A.: Data structure for efficient retrieval of compressed texture data from a memory system. US Patent 6,243,081, 1999.
7. {HG97} Hakura Z. S., Gupta A.: The design and analysis of a cache architecture for texture mapping. In Proceedings of the 24th annual international symposium on Computer architecture (1997), ACM Press, pp. 108--120.
8. {IEH99} Igehy H., Eldridge M., Hanrahan P.: Parallel texture caching. In Proc. Graphics Hardware (1999), pp. 95--106.
9. {IEP98} Igehy H., Eldridge M., Proudfoot K.: Prefetching in a texture cache architecture. In Proc. Graphics Hardware (1998), pp. 133--142.
10. {INH99} Iourcha K., Nayak K., Hong Z.: System and method for fixed-rate block-based image compression with inferred pixels values. US Patent 5,956,431, 1999.
11. {JED05} JEDEC: DDR2 SDRAM Specification, 2005. Specification document, available from http://www.jedec.org/.
12. {Kap99} Kaplan S.: Compressed Cacheing and Modern Virtual Memory Simulation. PhD thesis, University of Texas at Austin, 1999.
13. {KE02} Kraus M., Ertl T.: Adaptive texture maps. In Proc. Graphics Hardware (2002), pp. 7--15.
14. {KGJ96} Kjelso M., Gooch M., Jones S.: Design and performance of a main memory hardware data compressor. In Proc. the Euromicro Conference (1996), pp. 422--430.
15. {KSKS96} Knittel G., Schilling A. G., Kugler A., Strasser W.: Hardware for superior texture performance. Computers & Graphics 20, 4 (July 1996), 475--481.
16. {LDN04} Lefebvre S., Darbon J., Neyret F.: Unified Texture Management for Arbitrary Meshes. Tech. Rep. RR-5210, INRIA, May 2004.
17. {LS97} Lengyel J., Snyder J.: Rendering with coherent layers. In Proc. SIGGRAPH (1997), pp. 233--242.
18. {LW99} Lekatsas H., Wolf W.: Random access decompression using binary arithmetic coding. In Data Compression Conference (1999), pp. 306--315.
19. {MM02} Ma V. C. H., McCool M. D.: Low latency photon mapping via block hashing. In Proc. Graphics Hardware (2002), pp. 89--98.
20. {PM93} Pennebaker W. B., Mitchell J. L.: JPEG still image data compression standard. Van Nostrand Reinhold, 1993.
21. {SAM05} Ström J., Akenine-Möller T.: iPACK-MAN: high-quality, low-complexity texture compression for mobile phones. In Proc. Graphics Hardware (2005), pp. 63--70.
22. {TK96} Torborg J., Kajiya J. T.: Talisman: Commodity realtime 3D graphics for the PC. In Proc. SIGGRAPH (1996), pp. 353--363.
23. {Wor96} World Wide Web Consortium: PNG (Portable Network Graphics) Specification Version 1.0, 1996. Specification document, available from http://www.w3.org/TR/REC-png.
24. {Yee04} Yee W. M.: Cache Design for a Hardware Accelerated Sparse Texture Storage System. Master's thesis, University of Waterloo, 2004.
25. {ZL77} Ziv J., Lempel A.: A universal algorithm for sequential data compression. IEEE Transactions on Information Theory 23, 3 (May 1977), 337--343.

Index Terms

• Computing methodologies

  • Computer graphics

    • Graphics systems and interfaces