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

    $$\text{inside}(t, x, y) = \begin{cases} 1 & \text{if } (x, y) \text{ is inside triangle } t \\ 0 & \text{otherwise} \end{cases}$$

  • Discretize a function.

  • Rasterization is sampling a 2D indicator function.

• How to evaluate inside function?

  • Interior

    

    $$\vec{n} = (y_1 - y_0, x_0 - x_1)$$

  • $\vec{p}$ is "interior" means

    $$\vec{n} \cdot (\vec{p} - \vec{p_0}) \geq 0$$

  • Repeat for other edges. If all 3 tests pass, $\vec{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?

  1. Why under-sampling introduces aliasing?

  2. Why pre-filtering then sampling can do anti-aliasing?

• Fourier analysis:

  $$F(\omega) = \int_{-\infty}^{\infty} f(t) e^{-i \omega t} dt, \quad f(t) = \frac{1}{2\pi} \int_{-\infty}^{\infty} F(\omega) e^{i \omega t} d\omega.$$

• Under-sampling creates frequency overlap (aliasing).

  

  Samples erroneously represent high frequencies as low frequencies.

• Notice that

  $$\mathscr{F}[f(t) \cdot s(t)] = F(\omega) * S(\omega)$$

  and

  $$S(\omega) = \mathscr{F}\left[\sum_{n=-\infty}^{\infty} \delta(t - nT) \right] = \omega_s \sum_{k=-\infty}^{\infty} \delta(\omega - k \omega_s)$$

  where

  $$s(t) = \sum_{n=-\infty}^{\infty} \delta(t - nT), \quad \omega_s = \frac{2\pi}{T}$$

  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?

  1. Increase sampling rate (higher resolution displays).

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

  1. Take $N\times N$ samples per pixel (super-sampling).

  2. Average $N\times 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(n \log n)$.

• 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 $+\infty$.

  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.