CS 248 - Introduction to Computer Graphics
Autumn Quarter, 2004
Marc Levoy
Lecture notes for Thursday, October 14
The algorithm that follows, which is taken from section 3.6 in the textbook, handles self-intersecting (e.g. bow-tie) or degenerate polygons naturally, even polygons with holes. As mentioned in handout #7, you will need to handle the first two types in project #2, but not the third. By the way, handling these cases by decomposing them into triangles is not allowed, at least for the project.
Note 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.)
Also, 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 general, a polygon rasterizer should fill only and all sample positions that fall inside polygon edges. In previous versions of project #2, we also required students to rasterize their polygons such that they meshed perfectly, i.e. with no holes or doubly-drawn pixels. To satisfy this requirement, care must be taken when sample positions coincide with polygon edges or vertices, as discussed above. This year, we do not require this. Thus, you can ignore these rules, at least for the project.