Graphics Reference
In-Depth Information
For triangles with some large edges, iterating over the bounding box is a poor
strategy because
n
2
n
for large
n
. In this case, other strategies can be more
efficient. We now describe some of these briefly. Although we will not explore
these strategies further, they make great projects for learning about hardware-
aware algorithms and primary visibility computation.
15.6.6.1 Hierarchical Rasterization
Since the bounding-box rasterizer is efficient for small triangles and is easy to
implement, a natural algorithmic approach is to recursively apply the bounding-
box algorithm at increasingly fine resolution. This strategy is called
hierarchical
rasterization
[Gre96].
Begin by dividing the entire image along a very coarse grid, such as into 16
×
16 macro-pixels that cover the entire screen. Apply a conservative variation of the
bounding-box algorithm to these. Then subdivide the coarse grid and recursively
apply the rasterization algorithm within all of the macro cells that overlapped the
bounding box.
The algorithm could recur until the macro-pixels were actually a single pixel.
However, at some point, we are able to perform a large number of tests either with
Single Instruction Multiple Data (SIMD) operations or by using bitmasks packed
into integers, so it may not always be a good idea to choose a single pixel as the
base case. This is similar to the argument that you shouldn't quicksort all the way
down to a length 1 array; for small problem sizes, the constant factors affect the
performance more than the asymptotic bound.
For a given precision, one can precompute all the possible ways that a line
passes through a tile of samples. These can be stored as bitmasks and indexed by
the line's intercept points with the tile [FFR83, SW83]. For each line, using one
bit to encode whether the sample is in the positive half-plane of the line allows
an 8
8 pattern to fit in a single unsigned 64-bit integer. The bitwise AND of
the patterns for the three line aligns defining the triangle gives the coverage mask
for all 64 samples. One can use this trick to cull whole tiles efficiently, as well
as avoiding per-sample visibility tests. (Kautz et al. [KLA04] extended this to
a clever algorithm for rasterizing triangles onto hemispheres, which occurs fre-
quently when sampling indirect illumination.) Furthermore, one can process mul-
tiple tiles simultaneously on a parallel processor. This is similar to the way that
many GPUs rasterize today.
×
15.6.6.2 Chunking/Tiling Rasterization
A
chunking rasterizer,
a.k.a. a
tiling rasterizer,
subdivides the image into rectan-
gular tiles, as if performing the first iteration of hierarchical rasterization. Instead
of rasterizing a single triangle and performing recursive subdivision of the image,
it takes
all
triangles in the scene and bins them according to which tiles they touch.
A single triangle may appear in multiple bins.
The tiling rasterizer then uses some other method to rasterize within each tile.
One good choice is to make the tiles 8
8 or some other size at which brute-force
SIMD rasterization by a lookup table is feasible.
Working with small areas of the screen is a way to combine some of the best
aspects of rasterization and ray casting. It maintains both triangle list and buffer
memory coherence. It also allows triangle-level sorting so that visibility can be
performed analytically instead of using a depth buffer. That allows both more
×
