CG Class 24, Mon 2018-11-19

4.1   Clipping

1. Many of these algorithms were developed for HW w/o floating point, where even integer multiplication was expensive.
2. Efficiency is now less important in most cases (unless you're implementing in HW).
3. The idea of clipping with a 6-stage pipeline is important.
4. Jim Clark, a prof at Stanford, made a 12-stage pipeline using 12 copies of the same chip, and then left Stanford to found SGI.
   1. Later he bankrolled Netscape and 2 other companies.
   2. More recently he had the world's 4th largest yacht.

4.2   Polygon rendering

1. My note on Bresenham Line and Circle Drawing. Jack Bresenham, then at IBM invented these very fast ways to draw lines and circles with only integer addition and subtraction. My note gives step-by-step derivations by transforming slow and clear programs to fast and obscure programs.
2. My note on Two polygon filling algorithms.

4.3   Visibility methods

Here's my summary of problems with the main methods:

1. Painters:
   1. The painter's algorithm is tricky when faces are close in Z.
   2. Sorting the faces is hard and maybe impossible. Then you must split some faces.
   3. However sometimes some objects are always in front of some other objects. Then you can render the background before the foreground.
2. Z-buffer:
   1. Subpixel objects randomly appear and disappear (aliasing).
   2. Artifacts occur when objects are closer than their Z-extent across one pixel.
   3. This happens on the edge where two faces meet.
3. BSP tree:
   1. In 3D, many faces must be split to build the tree.
4. The scanline algorithm can feed data straight to the video D/A. That was popular decades ago before frame buffers existed. It became popular again when frame buffers are the slowest part of the pipeline.
5. A real implementation, with a moving foreground and fixed background, might combine techniques.
6. References: wikipedia.