View source for Irregular z-buffer

The '''irregular z-buffer''' is an algorithm designed to solve the [[visibility problem]] in real-time 3-d computer graphics. It is related to the classical [[z-buffer]] in that it maintains a depth value for each image sample and uses these to determine which geometric elements of a scene are visible. The key difference, however, between the classical z-buffer and the irregular z-buffer is that the latter allows arbitrary placement of image samples in the [[image plane]], whereas the former requires samples to be arranged in a regular grid.

These depth samples are explicitly stored in a two-dimensional spatial data structure. During [[rasterization]], triangles are projected onto the image plane as usual, and the data structure is queried to determine which samples overlap each projected triangle. Finally, for each overlapping sample, the standard z-compare and (conditional) frame buffer update are performed.

==Implementation==

The classical rasterization algorithm projects each [[polygon]] onto the image plane, and determines which sample points from a regularly spaced set lie inside the projected polygon. Since the locations of these samples (i.e. pixels) are implicit, this determination can be made by testing the edges against the implicit grid of sample points. If, however the locations of the sample points are irregularly spaced and cannot be computed from a formula, then this approach does not work. The irregular z-buffer solves this problem by storing sample locations explicitly in a two-dimensional spatial [[data structure]], and later querying this structure to determine which samples lie within a projected triangle. This latter step is referred to as "irregular rasterization". 
 
Although the particular data structure used may vary from implementation to implementation, the two studied approaches are the [[kd-tree]], and a grid of linked lists. A balanced kd-tree implementation has the advantage that it guarantees O(log(N)) access. Its chief disadvantage is that parallel construction of the kd-tree may be difficult, and traversal requires expensive branch instructions. The grid of lists has the advantage that it can be implemented more effectively on [[Graphics processing unit|GPU]] [[Computer hardware|hardware]], which is designed primarily for the classical z-buffer.

With the appearance of [[CUDA]], the programmability of current graphics hardware has been drastically improved. The Master Thesis, "Fast Triangle Rasterization using irregular Z-buffer on CUDA" (see External Links), provides a complete description to an irregular z-buffer based shadow mapping software implementation on CUDA. The rendering system is running completely on GPUs. It is capable of generating [[aliasing]]-free shadows at a throughput of dozens of million triangles per second.

==Applications==

The irregular z-buffer can be used for any application which requires visibility calculations at arbitrary locations in the image plane. It has been shown to be particularly adept at [[shadow mapping]], an image space algorithm for rendering hard shadows. In addition to shadow rendering, potential applications include adaptive [[Spatial anti-aliasing|anti-aliasing]], jittered sampling, and [[environment mapping]].

==See also==
*[[HyperZ]]

==External links==
*[https://web.archive.org/web/20081029150619/http://www.tacc.utexas.edu/~cburns/papers/izb-tog.pdf The Irregular Z-Buffer: Hardware Acceleration for Irregular Data Structures]
*[http://www.billmark.com/papers/ism-TR/TR04-09.pdf The Irregular Z-Buffer And Its Application to Shadow Mapping]
*[https://users.aalto.fi/~laines9/publications/aila2004egsr_paper.pdf Alias-Free Shadow Maps]
*[http://publications.lib.chalmers.se/records/fulltext/123790.pdf Fast Triangle Rasterization using irregular Z-buffer on CUDA]

[[Category:3D rendering]]