article

The irregular Z-buffer: Hardware acceleration for irregular data structures

Authors:

Gregory S. Johnson,

Christopher A. Burns,

William R. MarkAuthors Info & Claims

ACM Transactions on Graphics (TOG), Volume 24, Issue 4

Pages 1462 - 1482

https://doi.org/10.1145/1095878.1095889

Published: 01 October 2005 Publication History

Abstract

The classical Z-buffer visibility algorithm samples a scene at regularly spaced points on an image plane. Previously, we introduced an extension of this algorithm called the irregular Z-buffer that permits sampling of the scene from arbitrary points on the image plane. These sample points are stored in a two-dimensional spatial data structure. Here we present a set of architectural enhancements to the classical Z-buffer acceleration hardware which supports efficient execution of the irregular Z-buffer. These enhancements enable efficient parallel construction and query of certain irregular data structures, including the grid of linked lists used by our algorithm. The enhancements include flexible atomic read-modify-write units located near the memory controller, an internal routing network between these units and the fragment processors, and a MIMD fragment processor design. We simulate the performance of this new architecture and demonstrate that it can be used to render high-quality shadows in geometrically complex scenes at interactive frame rates. We also discuss other uses of the irregular Z-buffer algorithm and the implications of our architectural changes in the design of chip-multiprocessors.

References

[1]

Ahn, J. H., Erez, M., and Dally, W. J. 2005. Scatter-add in data parallel architectures. In Proceedings of the 11th International Symposium on High-Performance Computer Architecture (HPCA-11 2005). 132--142.

[2]

Aila, T. and Laine, S. 2004. Alias-free shadow maps. In Proceedings of the Eurographics Symposium on Rendering 2004. Eurographics Association, Aire-la-Ville, Switzerland, 161--166.

[3]

Appel, A. 1968. Some techniques for shading machine renderings of solids. In Proceedings of the AFIPS Spring Joint Computer Conference. Vol. 32. 37--45.

[4]

Brown, P. and Werness, E. 2004. GL_NV_fragment_program2 extension specification. Go to the Web site http://oss.sgi.com/projects/ogle-sample/registry/NV/fragment-program2.txt.

[5]

Buck, I. 2005. Taking the plunge into GPU computing. In GPU Gems 2: Programming Techniques for High Performance Graphics and General-Purpose Computation. Addison-Wesley Professional, Reading, MA, 509--519.

[6]

Catmull, E. 1974. A subdivision algorithm for computer display of curved surfaces. Ph.D. dissertation. Department of Computer Science, University of Utah, Salt Lake City, UT.

[7]

Cook, R. L., Carpenter, L., and Catmull, E. 1987. The reyes image rendering architecture. In SIGGRAPH '87: Proceedings of the 14th Annual Conference on Computer Graphics and Interactive Techniques. ACM Press, New York, NY, 95--102.

[8]

Deering, M. and Naegle, D. 2002. The SAGE graphics architecture. In SIGGRAPH 2002: Proceedings of the 29th Annual Conference on Computer Graphics and Interactive Techniques. ACM Press, New York, NY, 683--692.

[9]

Eldridge, M., Igehy, H., and Hanrahan, P. 2000. Pomegranate: a fully scalable graphics architecture. In SIGGRAPH '00: Proceedings of the 27th Annual Conference on Computer Graphics and Interactive Techniques. ACM Press, New York, NY/Addison-Wesley Reading, MA, 443--454.

[10]

Fernando, R., Fernandez, S., Bala, K., and Greenberg, D. P. 2001. Adaptive shadow maps. In Proceedings of the 28th Annual Conference on Computer Graphics and Interactive Techniques (ACM SIGGRAPH 2001). ACM Press, New York, NY, 387--390.

[11]

Goris, A., Fredrickson, B., and Harold L. Baeverstad, J. 1987. A configurable pixel cache for fast image generation. IEEE Comput. Graph. Applic. 7, 3 (Mar.), 24--32.

[12]

Greene, N., Kass, M., and Miller, G. 1993. Hierarchical Z-buffer visibility. In SIGGRAPH '93: Proceedings of the 20th Annual Conference on Computer Graphics and Interactive Techniques. ACM Press, New York, NY, 231--238.

[13]

Hachisuka, T. 2005. GPU Gems 2: Programming Techniques for High Performance Graphics and General-Purpose Computation. Addison-Wesley Professional, Chapter High-Quality Global Illumination Rendering Using Rasterization, 615--633.

[14]

Johnson, G. S., Mark, W. R., and Burns, C. A. 2004. The irregular Z-buffer and its application to shadow mapping. Tech. rep. TR-04-09. Department of Computer Sciences, The University of Texas at Austin, Austin, TX.

[15]

Kapasi, U. J., Dally, W. J., Rixner, S., Mattson, P. R., Owens, J. D., and Khailany, B. 2000. Efficient conditional operations for data-parallel architectures. In MICRO 33: Proceedings of the 33rd Annual ACM/IEEE International Symposium on Microarchitecture. ACM Press, New York, NY, 159--170.

[16]

Kilgariff, E. and Fernando, R. 2005. The GeForce 6 series GPU architecture. In GPU Gems 2: Programming Techniques for High Performance Graphics and General-Purpose Computation. Addison-Wesley Professional, Reading, MA, 471--491.

[17]

Lefebvre, S., Hornus, S., and Neyret, F. 2004. All-purpose texture sprites. Tech. rep. 5209. INRIA, Rocquencourt, France.

[18]

Lefohn, A. E., Kniss, J., Strzodka, R., Sengupta, S., and Owens, J. D. 2005. Glift: Generic, efficient, random-access GPU data structures. ACM Trans. Graph. 24. To appear.

[19]

Lengyel, J. and Walter, B. 1995. The path-buffer. Tech. rep. PCG-95-4. Program of Computer Graphics, Cornell University, Ithaca, NY.

[20]

Lindholm, E., Kilgard, M., and Moreton, H. 2001. A user-programmable vertex engine. In Proceedings of the 28th Annual Conference on Computer Graphics and Interactive Techniques (ACM SIGGRAPH 2001). ACM Press, New York, NY, 149--158.

[21]

McCormack, J., McNamara, R., Gianos, C., Seiler, L., Jouppi, N. P., and Correll, K. 1998. Neon: A single-chip 3D workstation graphics accelerator. In Proceedings of the ACM SIGGRAPH/EUROGRAPHICS Workshop on Graphics Hardware. ACM Press, New York, NY, 123--132.

[22]

Micron Technology, Inc. 2003. Micron Technology 256 Mb (x32) GDDR3 SDRAM datasheet. Micron Technology, Inc., Boise, ID.

[23]

Olano, M. and Greer, T. 1997. Triangle scan conversion using 2D homogeneous coordinates. In Proceedings of the ACM SIGGRAPH/EUROGRAPHICS Workshop on Graphics Hardware. ACM Press, New York, NY, 89--95.

[24]

Pineda, J. 1988. A parallel algorithm for polygon rasterization. Comput. Graph. (SIGGRAPH '88 Proceedings) 22, 4 (Aug.), 17--20.

[25]

Purcell, T. J., Buck, I., Mark, W. R., and Hanrahan, P. 2002. Ray tracing on programmable graphics hardware. In SIGGRAPH '02: Proceedings of the 29th Annual Conference on Computer Graphics and Interactive Techniques. ACM Press, New York, NY, 703--712.

[26]

Purcell, T. J., Donner, C., Cammarano, M., Jensen, H. W., and Hanrahan, P. 2003. Photon mapping on programmable graphics hardware. In Proceedings of the ACM SIGGRAPH/EUROGRAPHICS Conference on Graphics Hardware. Eurographics Association, Aire-la-Ville, Switzerland, 41--50.

[27]

Reinhard, E., Smits, B., and Hansen, C. 2000. Dynamic acceleration structures for interactive ray tracing. In Proceedings of the 11th Eurographics Workshop on Rendering. Eurographics Association, Aire-la-Ville, Switzerland, 299--306.

[28]

Rixner, S. 2004. Memory controller optimizations for web servers. In Proceedings of the 37th Annual International Symposium on Microarchitecture. 355--366.

[29]

Sen, P., Cammarano, M., and Hanrahan, P. 2003. Shadow silhouette maps. ACM Trans. Graph. 22, 3, 521--526.

[30]

Stamminger, M. and Drettakis, G. 2002. Perspective shadow maps. In SIGGRAPH '02: Proceedings of the 29th Annual Conference on Computer Graphics and Interactive Techniques. ACM Press, New York, NY, 557--562.

[31]

Tabellion, E. and Lamorlette, A. 2004. An approximate global illumination system for computer generated films. ACM Trans. Graph. 23, 3, 469--476.

[32]

Triantos, N. 2005. Windowing system on a 3D pipeline. White paper. NVIDIA Corporation, Santa Clara, CA.

[33]

Vachharajani, M., Vachharajani, N., Penry, D. A., Blome, J., and August, D. I. 2004. The liberty simulation environment, version 1.0. Perform. Eval. Rev. (Special Issue on Tools for Architecture Research) 31, 4 (Mar.).

[34]

Van Dyke, J. M., Voorhies, D. A., James E. Margeson, I., and Montrym, J. 2004. System, method and article of manufacture for an interlock module in a computer graphics processing pipeline. Patent &num;6734861 NVIDIA Corporation, Santa Clara, CA.

[35]

Whitted, T. 1980. An improved illumination model for shaded display. Commun. ACM 23, 6 (June), 343--349.

[36]

Willmann, P., Brogioli, M., and Pai, V. S. 2004. Spinach: A Liberty-based simulator for programmable network interface architectures. In LCTES '04: Proceedings of the 2004 ACM SIGPLAN/SIGBED Conference on Languages, Compilers, and Tools. ACM Press, New York, NY, 20--29.

Cited By

Popescu VSacks ECui JAshok R(2024)Efficient and Robust From-Point VisibilityIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2023.329113830:8(5313-5327)Online publication date: 1-Aug-2024
https://dl.acm.org/doi/10.1109/TVCG.2023.3291138
Kobrtek JMilet TTóth MHerout A(2021)Comparison of Modern Omnidirectional Precise Shadowing Techniques Versus Ray TracingComputer Graphics Forum10.1111/cgf.1442541:1(106-121)Online publication date: 3-Dec-2021
https://doi.org/10.1111/cgf.14425
Vasilakis AVardis KPapaioannou G(2020)A Survey of Multifragment RenderingComputer Graphics Forum10.1111/cgf.1401939:2(623-642)Online publication date: 13-Jul-2020
https://doi.org/10.1111/cgf.14019
Show More Cited By

Index Terms

The irregular Z-buffer: Hardware acceleration for irregular data structures
1. Computing methodologies
  1. Computer graphics

Recommendations

An improved illumination model for shaded display

To accurately render a two-dimensional image of a three-dimensional scene, global illumination information that affects the intensity of each pixel of the image must be known at the time the intensity is calculated. In a simplified form, this ...
An improved illumination model for shaded display
SIGGRAPH '05: ACM SIGGRAPH 2005 Courses

To accurately render a two-dimensional image of a three-dimensional scene, global illumination information that affects the intensity of each pixel of the image must be known at the time the intensity is calculated. In a simplified form, this ...
An improved illumination model for shaded display

To accurately render a scene, global illumination information that affects the intensity of each pixel of the image must be known at the time the intensity is calculated. In a simplified form, this information is stored in a tree of “rays” extending ...

Comments

Information & Contributors

Information

Published In

cover image ACM Transactions on Graphics

ACM Transactions on Graphics Volume 24, Issue 4

October 2005

244 pages

ISSN:0730-0301

EISSN:1557-7368

DOI:10.1145/1095878

Issue’s Table of Contents

Copyright © 2005 ACM.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 October 2005

Published in TOG Volume 24, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

59
Total Citations
View Citations
1,259
Total Downloads

Downloads (Last 12 months)23
Downloads (Last 6 weeks)3

Reflects downloads up to 06 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Popescu VSacks ECui JAshok R(2024)Efficient and Robust From-Point VisibilityIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2023.329113830:8(5313-5327)Online publication date: 1-Aug-2024
https://dl.acm.org/doi/10.1109/TVCG.2023.3291138
Kobrtek JMilet TTóth MHerout A(2021)Comparison of Modern Omnidirectional Precise Shadowing Techniques Versus Ray TracingComputer Graphics Forum10.1111/cgf.1442541:1(106-121)Online publication date: 3-Dec-2021
https://doi.org/10.1111/cgf.14425
Vasilakis AVardis KPapaioannou G(2020)A Survey of Multifragment RenderingComputer Graphics Forum10.1111/cgf.1401939:2(623-642)Online publication date: 13-Jul-2020
https://doi.org/10.1111/cgf.14019
Usta BScandolo LBilleter MMarroquim REisemann E(2019)A practical and efficient approach for correct Z-Pass stencil shadow volumesProceedings of the Conference on High-Performance Graphics10.2312/hpg.20191195(45-49)Online publication date: 8-Jul-2019
https://dl.acm.org/doi/10.2312/hpg.20191195
Deves FMora FAveneau LGhazanfarpour DDachsbacher CJakob W(2018)Scalable real-time shadows using clustering and metric treesProceedings of the Eurographics Symposium on Rendering: Experimental Ideas & Implementations10.2312/sre.20181175(83-93)Online publication date: 1-Jul-2018
https://dl.acm.org/doi/10.2312/sre.20181175
Hunt WMara MNankervis A(2018)Hierarchical Visibility for Virtual RealityProceedings of the ACM on Computer Graphics and Interactive Techniques10.1145/32031911:1(1-18)Online publication date: 25-Jul-2018
https://dl.acm.org/doi/10.1145/3203191
Macedo MApolinário AEisemann EBateman S(2017)Euclidean Distance Transform Shadow MappingProceedings of the 43rd Graphics Interface Conference10.5555/3141475.3141510(171-180)Online publication date: 1-Jun-2017
https://dl.acm.org/doi/10.5555/3141475.3141510
He XXu X(2017)Physically Based Model for Multispectral Image Simulation of Earth Observation SensorsIEEE Journal of Selected Topics in Applied Earth Observations and Remote Sensing10.1109/JSTARS.2017.265867810:5(1897-1908)Online publication date: May-2017
https://doi.org/10.1109/JSTARS.2017.2658678
Mora FGerhards JAveneau LGhazanfarpour DManzke MEisemann EFiume E(2016)Deep partitioned shadow volumes using stackless and hybrid traversalsProceedings of the Eurographics Symposium on Rendering: Experimental Ideas & Implementations10.5555/3056507.3056522(73-83)Online publication date: 22-Jun-2016
https://dl.acm.org/doi/10.5555/3056507.3056522
Story JWyman C(2016)HFTSACM SIGGRAPH 2016 Talks10.1145/2897839.2927424(1-2)Online publication date: 24-Jul-2016
https://dl.acm.org/doi/10.1145/2897839.2927424
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents