CS 248 - Introduction to Computer Graphics

Autumn Quarter, 2001

Marc Levoy

Lecture notes for Thursday, October 18 (last half of class)

- Overview of 3D rendering pipeline
- Line drawing
- Polygon scan conversion
- Polygon scan conversion with supersampling/resampling

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

levoy@cs.stanford.edu

Last update: October 22, 2001 08:19:54 PM