Graphics Reference
In-Depth Information
Figure 2.16.
Scan converting a polygon.
Step 1.
Associate a “bucket” to each scan line and initialize it to empty.
Step 2.
Find the largest y value for each edge and put the edge into the correspon-
ding scan line's bucket.
Step 3.
For each edge
e
maintain the following information:
x
- initially the x-coordinate of the highest point of the edge
e
(in general
the x-coordinate x
e
of the intersection of
e
with the current scan line)
dx
- change in x from line to line (the reciprocal of the slope of the line)
dy
- initially the number of scan lines crossed by
e
Step 4.
Initialize the active edge list to empty. Set y to the height of the top scan line.
Step 5.
Add any edges in the bucket for y to the active edge list.
Step 6.
For each edge in the active edge list draw (x,y), change the x to x + dx, and
decrement dy. If dy becomes 0, then remove that edge from the list.
Step 7.
Decrement y. If y is 0, then quit; otherwise, go back to Step 5.
In Figure 2.16, when we reach scan line y1, the edges
AB
and
BC
will be added to the
active edge list. At scan line y2 nothing special happens. When we get to scan line y3,
the edges
CD
and
DE
will be added to the list. Finally, at scan line y5 there are only
the two edges
BC
and
CD
on the list and they will now be removed.
To avoid having fixed bucket sizes and limiting the amount of data for each scan
line, one stores pointers only and stores all information sequentially in an array. Alter-
natively, one can use a
linked
list to be able to add and delete easily.
A problem related to scan converting lists of edges which is of more practical
importance is scan converting
solid
polygons. This leads to polygon based fill algo-
rithms. The pixel-based analog was already discussed earlier in Section 2.4.
Assume that XMIN, XMAX, YMIN, and YMAX are the minimum and maximum
values for the x- and y-coordinates of pixels. The basic idea here is the following:
for
i:=YMIN
to
YMAX
do
for
j:=XMIN
to
XMAX
do
if
Inside (polygon,j,i)
then
Draw (j,i);
The Boolean-valued function “Inside” counts the intersections of the line from (j,i) to
(-•,i) with the polygon. If this number is odd, then the function returns
true
, other-
