Hexagonal storage scheme for interleaved frame buffers and textures

ABSTRACT

This paper presents a storage scheme which statically assigns pixel/texel coordinates to multiple memory banks in order to minimize frame buffer and texture memory access load imbalance. In this scheme, the pixels stored in a particular memory bank are placed at the center and the vertices of hexagons packed in the frame buffer By making these hexagons close to regular so that the pixel placement is uniform and isotropic, frame buffer and texture memory accesses are evenly distributed over the memory banks. The analysis of memory access patterns in rendering typical 3D graphics scenes shows that the hexagonal storage scheme can reduce rendering performance degradation due to bank conflicts by an average of 10% compared to the traditional rectangular storage scheme.

REFERENCES

• 1: {AMH02} Akenine-Möller T., Haines E.: Real-Time Rendering (second edition). A K Peters, Ltd., 2002.
• 2: J. H. Conway , N. J. A. Sloane , E. Bannai, Sphere-packings, lattices, and groups, Springer-Verlag New York, Inc., New York, NY, 1987
• 3: {Dee93} Deering M. F.: Data complexity for virtual reality: where do all the triangles go? In IEEE Virtual Reality Annual International Symposium (1993), pp. 357--363.
• 4: Henry Fuchs, Distributing a visible surface algorithm over multiple processors, Proceedings of the 1977 annual conference, p.449-451, January 1977 [doi>10.1145/800179.810237]
• 5: James D. Foley , Andries van Dam , Steven K. Feiner , John F. Hughes, Computer graphics: principles and practice (2nd ed.), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 6: Andrew S. Glassner, Principles of Digital Image Synthesis, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1994
• 7: D. T. Harper, III, A Multiaccess Frame Buffer Architecture, IEEE Transactions on Computers, v.43 n.5, p.618-622, May 1994 [doi>10.1109/12.280810 ]
• 8: Ziyad S. Hakura , Anoop Gupta, The design and analysis of a cache architecture for texture mapping, Proceedings of the 24th annual international symposium on Computer architecture, p.108-120, June 01-04, 1997, Denver, Colorado, United States
• 9: Homan Igehy , Matthew Eldridge , Pat Hanrahan, Parallel texture caching, Proceedings of the ACM SIGGRAPH/EUROGRAPHICS workshop on Graphics hardware, p.95-106, August 08-09, 1999, Los Angeles, California, United States [doi>10.1145/311534.311583]
• 10: Homan Igehy , Matthew Eldridge , Kekoa Proudfoot, Prefetching in a texture cache architecture, Proceedings of the ACM SIGGRAPH/EUROGRAPHICS workshop on Graphics hardware, p.133-ff., August 31-September 01, 1998, Lisbon, Portugal [doi>10.1145/285305.285321]
• 11: Steven Molnar , Michael Cox , David Ellsworth , Henry Fuchs, A Sorting Classification of Parallel Rendering, IEEE Computer Graphics and Applications, v.14 n.4, p.23-32, July 1994 [doi>10.1109/38.291528 ]
• 12: Joel McCormack , Robert McNamara, Tiled polygon traversal using half-plane edge functions, Proceedings of the ACM SIGGRAPH/EUROGRAPHICS workshop on Graphics hardware, p.15-21, August 21-22, 2000, Interlaken, Switzerland [doi>10.1145/346876.346882]
• 13: Carl Mueller, The sort-first rendering architecture for high-performance graphics, Proceedings of the 1995 symposium on Interactive 3D graphics, p.75-ff., April 09-12, 1995, Monterey, California, United States [doi>10.1145/199404.199417]
• 14: Michael D. McCool , Chris Wales , Kevin Moule, Incremental and hierarchical Hilbert order edge equation polygon rasterizatione, Proceedings of the ACM SIGGRAPH/EUROGRAPHICS workshop on Graphics hardware, p.65-72, August 2001, Los Angeles, California, United States [doi>10.1145/383507.383528]
• 15: Satoshi Nishimura , Tosiyasu L. Kunii, VC-1: a scalable graphics computer with virtual local frame buffers, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.365-372, August 1996 [doi>10.1145/237170.237275]
• 16: Frederic I. Parke, Simulation and expected performance analysis of multiple processor Z-buffer systems, ACM SIGGRAPH Computer Graphics, v.14 n.3, p.48-56, July 1980
• 17: Michael Potmesil , Eric M. Hoffert, The pixel machine: a parallel image computer, ACM SIGGRAPH Computer Graphics, v.23 n.3, p.69-78, July 1989
• 18: Hexagonal Raster for Computer Graphic, Proceedings of the International Conference on Information Visualisation, p.69, July 19-21, 2000
• 19: Bin Wei, Comments on "A Multiaccess Frame Buffer Architecture", IEEE Transactions on Computers, v.45 n.7, p.862, July 1996 [doi>10.1109/12.508324 ]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.1 Hardware architecture