Rasterization algorithms

CS 248 - Introduction to Computer Graphics
Autumn Quarter, 2001
Marc Levoy
Lecture notes for Thursday, October 18 (last half of class)

Table of contents:

• Overview of 3D rendering pipeline
• Line drawing
  1. Assumptions
  2. Brute force algorithm
  3. DDA algorithm
  4. Bresenham algorithm
  5. What do real workstations use?
• Polygon scan conversion
  1. Assumptions
  2. Algorithm
  3. Which pixels to fill?
• Polygon scan conversion with supersampling/resampling
  1. 1 scan conversion to a supersampling grid
  2. s scan conversions with shifted centers
  3. Handling multiple polygons

In class, I asssumed no bow-tie, self-intersecting, or degenerate polygons. In fact, the algorithm that follows, which is taken from section 3.6 in the textbook, does handle these cases naturally. As mentioned in handout #7, you will need to handle them in project #2. By the way, handling these case by decomposing them into triangles is not allowed, at least for the project.

In class, I mistakenly said that, in order to handle self-intersecting polygons, this algorithm would need to be modified to create events at the intersection between two edges. This is not true. The algorithm handles this case naturally. I apologize for the error.

Note also that step 3.2 (remove edges) should be performed before step 3.3 (fill the scanline) in the algorithm, despite the physical order in which they appear in the list above. (Previous versions of these notes, and previous editions of the textbook, had filling performed before removing edges. That order was incorrect.)

Finally, the suggested code for updating the X-coordinate in step 3.5 is an integer-only solution, lifted from Bresenhham's algorithm. If you're willing to use floating-point arithmetic, then the increment becomes just the (floating-point) slope, with no if-test necessary.

In last year's project #2, we required students to rasterize their polygons such that they meshed perfectly. This year, we do not require this. Therefore, to save time in class, I didn't cover these meshing rules. They are included here to completeness. you can ignore these rules, at least for the project.

Algorithm 2 is also known as "accumulation buffer antialiasing". It is the algorithm we have asked you to implement in project #2.
If you want to learn more about this algorithm and some of the neat things it can be used for, read Haeberli, P., Akeley, K., The Accumulation Buffer: Hardware Support for High-Quality Rendering, Computer Graphics (Proc. SIGGRAPH), 24:4, pp. 309-318, 1990.

I didn't have time to cover this last page in class. However, the idea is simple, and understanding it is important for your project. If you're having trouble, the TAs will cover this concept in the help session on Friday, and I'll cover it briefly in class next Tuesday (October 23).