PDA

View Full Version : Scan line conversion (rasterization)



Budric
11-12-2008, 12:26 PM
Hi, I have a question about the scanline conversion algorithm. I've been trying to understand it, but don't have a reference book so I'm going by some slides and bits of information here and there online.

The algorithm is usually listed as:
1. Add polygon edges to the Global Edge Table (GET)
2. Set y to the smallest y coordinate in the GET.
3. Initially, set the Active Edge Table (AET) to be empty.
4. Repeat until the AET and GET are empty:
4.1 Add edges from the GET to the AET in which ymin = y.
4.2 Remove edges from the AET in which ymax <= y.
4.3 Sort AET on x.
4.4 Fill pixels between pairs of intersections in the AET
4.5 For each edge in the AET, replace x with x + 1/m
4.6 Set y = y + 1 to move to the next scan line

It's step 4.2 that I have trouble with. You need this step here because if two edges meet on a scan line you ignore the edge that's ending and consider the edge that begins on the scan line - otherwise you get odd number of edges and you can't decide what's inside/outside properly. However the very last scan line would not be rendered because of this because the edges are ending on that scan line and would be removed by that part of the algorithm.

Any help? I've been searching google and various slides/course notes that present this algorithm are similar to the steps above.
Thanks.

_NK47
11-18-2008, 04:20 AM
there are few books that describe them.
Game Engine Design (David Eberly)
Computer Graphics - Principles and Practice

maybe you can find some snippets on the web.

nicolasbol
11-18-2008, 08:24 AM
You should take a look at Michael Abrash articles:

http://www.byte.com/abrash/

http://www.byte.com/abrash/chapters/gpbb38.pdf
http://www.byte.com/abrash/chapters/gpbb39.pdf