Triangles - Fundamental Shape Primitives:

• Most basic polygon. Break up other polygons
• Unique properties. Guaranteed to be planar. Well-defined interior. Well-define method for interpolating values at vertices over triangle (barycentric interpolation)

What Pixel Values Approximate a Triangle:

• Input: position of triangle vertices projected on screen.
• Output: set of pixel values approximating triangle

Sampling

Evaluating a function at a point is sampling. We can discretize a function by sampling.

for (int x = 0; x < xmax; ++x)
    output[x] = f(x);

Sampling is a core idea in graphics. We sample time (1D), area (2D), direction (2D), volume (3D) ...

Rasterization As 2D Sampling

• Sample if each pixel center is inside triangle. Define binary function: inside (tri, x, y), x,y not necessarily integers

• Rasterization = Sampling a 2D indicator function

  for (int x = 0; x < xmax; ++x)
      for (int y = 0; y < ymax; ++y)
          image[x][y] = inside(tri, x+0.5, y+0.5);
  
  // Improve: Use a Bounding Box. 
  /*e.g.
  xmin = Minimum value of three point abscissa
  xmax = Maximum value of three point abscissa
  ymin = Minimum value of three point ordinates
  ymax = Maximum value of three point ordinates
  */
  for (int x = xmin; x < xmax; ++x)
      for (int y = ymin; y < ymax; ++y)
          image[x][y] = inside(tri, x+0.5, y+0.5);
  

• Evaluating inside (tri, x, y): Three Cross Products

  Edge cases (literally)

Sampling Artifacts (Errors/Mistakes/Inaccuracies) in Computer Graphics: Artifacts due to sampling - "Aliasing"

• Jaggies (Staircase Pattern)
• Moire Patterns in Imaging: Skip odd rows and columns
• Wagon Wheel Illusion (False Motion)

Behind the Aliasing Artifacts: Signals are changing too fast (high frequency), but sampled too slowly

Antialiasing Idea: Blurring (Pre-Filtering) Before Sampling

Note antialiased edges in rasterized triangle where pixel values take intermediate values.

Antialiasing

Fourier Transform: Represent a function as a weighted sum of sines and cosines. $\Large f(x)=\frac{A}{2}+\frac{2A\cos(t\omega)}{\pi}-\frac{2A\cos(3t\omega)}{3\pi}+...$

Fourier Transform Decomposes A Signal Into Frequencies

Undersampling Creates Frequency Aliases: High-frequency signal is insufficiently sampled, samples erroneously appear to be from a low-frequency signal. Two frequencies that are indistinguishable at a given sampling rate are called "aliases".

Filtering = Getting rid of certain frequency contents = Convolution (= Averaging)

Convolution Theorem: Convolution in the spatial domain is equal to multiplication in the frequency domain, and vice versa

• Option 1: Filter by convolution in the spatial domain

• Option 2:

  • Transform to frequency domain (Fourier transform)
  • Multiply by Fourier transform of convolution kernel
  • Transform back to spatial domain (inverse Fourier)

Box Filter: Averaging matrix. e.g. 3*3 box filter $\frac{1}{9}\begin{bmatrix}1&1&1\\1&1&1\\1&1&1\end{bmatrix}$

Sampling = Repeating Frequency Contents

Aliasing = Mixed Frequency Contents

Reduce Aliasing error:

• Increase sampling rate:

  • Essentially increasing the distance between replicas in the Fourier domain
  • Higher resolution displays, sensors, framebuffers...
  • But: costly & may need very high resolution

• Antialiasing:

  • Making Fourier contents "narrower" before repeating
  • i.e. Filtering out high frequencies before sampling

A Practical Pre-Filter: A 1 pixel-width box filter (low pass, blurring). Antialiasing by averaging values in pixel area:

• Convolve f(x,y) by a 1-pixel box-blur

  convolving = filtering = averaging

  Antialiasing by computing average pixel value: In rasterizing one triangle, the average value inside a pixel area of f(x,y) = inside(triangle,x,y) is equal to the area of the pixel covered by the triangle.

• Then sample at every pixel's center

  Antialiasing by supersampling (MSAA): Approximate the effect of the 1-pixel box filter by sampling multiple locations within a pixel and averaging their values:

Visibility / Occlusion

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)$ for n triangles). Can have unresolvable depth order:

Z-Buffer

This is the algorithm that eventually won. Idea:

• Store current min. z-value for each sample (pixel)

• Needs an additional buffer for depth values

  • frame buffer stores color values
  • depth buffer (z-buffer) stores depth

For simplicity we suppose z is always positive. (smaller z->closer, larger z->further)

Algorithm:

1. Initialize depth buffer to $\infty$

2. During rasterization:

   for (each triangle T)
       for (each sample (x,y,z) in T)
           if (z < zbuffer[x,y]){        // closest sample so far
               framebuffer[x,y]=rgb;    // update color
               zbuffer[x,y]=z;            // update depth
           }else{
               ;            // do nothing, this sample is occluded
           }
   

Complexity: O(n) for n triangles (assuming constant coverage)

Z-Buffer is the most important visibility algorithm, and implemented in hardware for all GPUs.