The Irregular Z-Buffer: Hardware Acceleration for Irregular Data Structures

Gregory S. Johnson, Juhyun Lee, Christopher A. Burns and William R. Mark

ACM Transactions on Graphics, October 2005.


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 highquality 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.

Paper -- final version (PDF, 14.1 MB)
Paper -- nearly final preprint (PDF, only 2.4 MB)
Movie (Quicktime, 12.0 MB)

BibTex Citation

 author = {Gregory S. Johnson and Juhyun Lee and Christopher A. Burns and William R. Mark},
 title = {The irregular Z-buffer: Hardware acceleration for irregular data structures},
 journal = {ACM Trans. Graph.},
 volume = {24},
 number = {4},
 year = {2005},
 issn = {0730-0301},
 pages = {1462--1482},
 doi = {},
 publisher = {ACM Press},
 address = {New York, NY, USA},