Lec 5. Rasterization
约 654 字大约 2 分钟
2025-10-31
What is screen?
- Discrete grid of pixels.
What is rasterize?
- Drawing onto the screen.
Rasterizing a triangle
Triangles: fundamental shape primitives.
Some unique properties.
Guaranteed to be planar.
Well-defined interior.
Well-defined method for interpolating values at vertices over triangle (barycentric interpolation).
What pixel values approximate the triangle?

Input: position of triangle vertices projected onto screen.
Output: set of pixel values approximating triangle.
Assume display pixels emit square of light.
Sampling
Evaluating a function at a point.
inside(t,x,y)={10if (x,y) is inside triangle totherwise
Discretize a function.
Rasterization is sampling a 2D indicator function.
How to evaluate inside function?
Interior

n=(y1−y0,x0−x1)
p is "interior" means
n⋅(p−p0)≥0
Repeat for other edges. If all 3 tests pass, p is inside triangle.
No need to check all pixels.
Use bounding box of triangle.

Hierarchical rasterization.

Incremental triangle traversal.

difficult for hardware optimization.
Anti-aliasing
Aliasing: when sending the sampled signal directly to display.

Theory
Nyquist–Shannon sampling theorem: higher frequencies need faster sampling rate.

Behind the aliasing artifacts: signals are changing too fast (high frequency), but sampling rate is too low.
Anti-aliasing idea: blurring (pre-filtering) before sampling.

Filter out frequencies above Nyquist frequency. Pixel values take intermediate values.
Why?
Why under-sampling introduces aliasing?
Why pre-filtering then sampling can do anti-aliasing?
Fourier analysis:
F(ω)=∫−∞∞f(t)e−iωtdt,f(t)=2π1∫−∞∞F(ω)eiωtdω.
Under-sampling creates frequency overlap (aliasing).

Samples erroneously represent high frequencies as low frequencies.
Notice that
F[f(t)⋅s(t)]=F(ω)∗S(ω)
and
S(ω)=F[n=−∞∑∞δ(t−nT)]=ωsk=−∞∑∞δ(ω−kωs)
where
s(t)=n=−∞∑∞δ(t−nT),ωs=T2π
is the sampling function.
Sampling is repeating the spectrum at multiples of sampling frequency.

If the original signal contains frequencies above Nyquist frequency, the repeated spectra overlap, causing aliasing.

How to reduce aliasing?
Increase sampling rate (higher resolution displays).
Anti-aliasing, make fourier contents "narrower" before sampling (repeating spectra).

Practical anti-aliasing
A practical pre-filter
Filtering in the frequency domain: multiply a low-pass filter.
Equivalently, convolve with a kernel in spatial domain.
Convolve by a 1-pixel box-blur, then sample at pixel centers.

MSAA: Multi-Sample Anti-Aliasing
Take N×N samples per pixel (super-sampling).
Average N×N samples "inside" the pixel.

Z-Buffering
Painter's algorithm
Inspired by how painters paint.
Paint from back to front, overwrite in the framebuffer.
Requires sorting in depth: O(nlogn).
Unresolvable depth order (cyclic overlap).

Z-Buffer
Store current minimum z-value for each sample (pixel).
Frame buffer stores color, depth buffer stores depth.
For simplicity we suppose z is always positive (larger z means further away).
Initialize depth buffer to +∞.
for (each triangle t) { for (each pixel p in bounding box of t) { if (inside(t, p)) { if (z < z_buffer[p]) { z_buffer[p] = z; frame_buffer[p] = color of t; } } } }No sorting required, O(n) for n triangles.
Most important visibility algorithm, implemented in hardware for all GPUs.