Published in


Turing Award | A Closer Look Into Edwin Catmull’s PhD Thesis


Figure 1. Relationships between the various terms defined.

A General Algorithm for Displaying Curved Patches

The subdivision algorithm

Figure 2 (top). The grid-like dots are the sample points, while the lines represent the curved edges of the projected object. Recall that each sample point corresponds to a raster element, which is associated with an intensity value; Figure 2 (middle). The algorithm works by dividing the patch of sample points which the object covers into smaller sub-patches that cover a smaller set of sample points; Figure 2 (bottom). This process is continued until each sub-patch covers no more than a single sample point. Compute the intensity of each sub patch and write its value into the corresponding element of the frame buffer.
  1. How is the subdivision process terminated?
  2. What happens to patches which do not cover a sample point?
  3. What if a sub-patch intersects the edge of the screen or is behind the eye?
  4. How many times must a patch be sub-divided?
  5. What problems may result from discrete sampling?
Figure 3. A rectangular polygon approximation of a patch.

Sub-dividing a Cubic Curve

  • Consider the cubic: f(t) = a x t³ + b x t² + c x t +d. The problem is to determine f(t) when f(t-h) and f(t+h) are known,
  • where f(t+h) = a x (t+h)³ + b x (t+h)² + c x (t+h) x d, and f(t-h) = a x (t-h)³ + b x (t-h)² + c x (t-h) x d,
  • where f(t-h) + f(t+h) can be calculated to be 2 x f(t) + 2 x (h² x ( 3 x (a x t +b) ) ),
  • the midpoint is then f(t) = ( f(t-h) + f(t+h) )/ 2 — h² x ( 3 x (a x t +b) ).
  • Let g(t) = h² x ( 3 x (a x t +b) ) be the mid point at t,
  • then g(t-h) = h² x ( 3 x (a x (t-h) +b) ) and g(t+h) = h² x ( 3 x (a x (t+h) +b) ),
  • calculating g(t-h) + g(t+h) = 2 x g(t),
  • thus, g(t) = ( g(t-h) + g(t+h) ) /2 .
  • f(t) = ( f(t-h) + f(t+h) )/ 2 — ( g(t-h) + g(t+h) ) /2.

Extending Cubic Sub-division to Surfaces

  1. the midpoints of each of the edges (sides) of the patch,
  2. the midpoint of the patch itself.

The Hidden Surface Problem

Figure 4. The hidden surface problem. Any object being looked at by some observer should only display the parts in which the observer can see. The remaining parts of the object become useless in terms of what is required to be displayed.

A high-level description of the Z-buffer algorithm

Figure 5. The observer is at the negative z-axis looking towards the positive z-axis. Objects with smaller depth are closer and are stored into the final Z-buffer, which is then displayed on the screen.
  • Scanline algorithm: Works on a row-by-row basis rather than a polygon-by-polygon or pixel-by-pixel basis.
  • Warnock’s algorithm: Recursive subdivision of a screen until areas are obtained that are trivial to compute. Mostly used as a base for other algorithms, and is very parallel friendly.
  • Painter’s algorithm: Sorts all the polygons in a scene by their depth and then paints them in this order, farthest to closest. Mostly used for (simple) video games.
  • Ray tracing algorithm: Essentially geometric objects and physics done backwards. Imagine simply reversing the path that a light ray took to get to your eye, tracing it back to the source (or vice versa).

A high-level description of the modified Newell algorithm

  • Sort polygons into furthest minimum Z-order to nearest,
  • For each polygon, check other polygons it may overlap with,
  • See if any of the polygons are behind the polygon being tested,
  • If so, move this polygon behind it,
  • Split overlapping polygons into smaller pieces and repeat the above steps with each partition.

Intensity, Sampling, Rastering, and Aliasing


  • Calculate the intensity with the normal (orthogonal) to the surface,
  • Define some intensity function to calculate the intensity,
  • map the intensity values from some picture,
  • modify existing intensities for shadow or transparency

Sampling, Rastering, and Aliasing

Figure 6 (top). The sample is fast enough that the reconstructed signals will have the same frequency as the original signal; Figure 6 (bottom). The sample is too slow such that the reconstructed wave will appear to have a much lower frequency than the original. This is called an aliased signal.
Figure 7. The rendered image exhibits aliasing.
  • Pre-filtering: treats pixels as an area, and computes pixel colour based on the overlap of the scene’s objects with a pixel’s area
  • Post-filtering: renders the scene at higher resolution, and computes the pixel value by a (weighted) average of the subpixels (supersampling)

Concluding Remarks



Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store



AI Technology & Industry Review — | Newsletter: | Share My Research | Twitter: @Synced_Global