Irregular Z-buffer
Encyclopedia
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.
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 GPU
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", provide 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.
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 anti-aliasing
, jittered sampling, and
environment mapping.
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 polygonPolygon
In geometry a polygon is a flat shape consisting of straight lines that are joined to form a closed chain orcircuit.A polygon is traditionally a plane figure that is bounded by a closed path, composed of a finite sequence of straight line segments...
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
Data structure
In computer science, a data structure is a particular way of storing and organizing data in a computer so that it can be used efficiently.Different kinds of data structures are suited to different kinds of applications, and some are highly specialized to specific tasks...
, 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
Kd-tree
In computer science, a k-d tree is a space-partitioning data structure for organizing points in a k-dimensional space. k-d trees are a useful data structure for several applications, such as searches involving a multidimensional search key...
, 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 GPU
Graphics processing unit
A graphics processing unit or GPU is a specialized circuit designed to rapidly manipulate and alter memory in such a way so as to accelerate the building of images in a frame buffer intended for output to a display...
hardware
Computer hardware
Personal computer hardware are component devices which are typically installed into or peripheral to a computer case to create a personal computer upon which system software is installed including a firmware interface such as a BIOS and an operating system which supports application software that...
, 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", provide 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 requiresvisibility calculations at arbitrary locations in the image plane. It has
been shown to be particularly adept at shadow mapping
Shadow mapping
Shadow mapping or projective shadowing is a process by which shadows are added to 3D computer graphics. This concept was introduced by Lance Williams in 1978, in a paper entitled "Casting curved shadows on curved surfaces"...
, an image space
algorithm for rendering hard shadows. In addition to shadow rendering,
potential applications include adaptive anti-aliasing
Anti-aliasing
In digital signal processing, spatial anti-aliasing is the technique of minimizing the distortion artifacts known as aliasing when representing a high-resolution image at a lower resolution...
, jittered sampling, and
environment mapping.