Graphics Reference
In-Depth Information
wise it returns
false
. Of course, this algorithm is too slow. One needs to take
scan
line coherence
into account. This leads us to what are called
ordered edge list
fill algo-
rithms. They have the following general form:
for each
scan line
do
begin
Find all intersections of edges with the scan line;
Sort the intersections by increasing x;
Fill alternate segments;
end
;
For example, consider the scan line y4 in Figure 2.16. Notice how filling the alternate
segments [b,c] and [d,e] does in fact fill what we want. That this works is justified by
a parity type argument. An active edge list again helps. Algorithm 2.9.1.1 shows a
more detailed version.
linerec
=
record
real
x, dx;
integer
dy;
end
;
linerecs
=
linerec list
;
begin
linerecs array
[0.. ] edges; { the edges of the polygons }
linerecs
ael;
{ the active edge list }
integer
y;
Scan the polygon and set up the edges table;
ael :=
nil
;
for
y:=YMIN
to
YMAX
do
begin
Add all edges in edges [y] to ael;
if
ael π
nil then
begin
Sort ael by increasing x;
Fill pixels along y by scanning ael and filling alternate x segments;
Delete from ael edges for which dy = 0 ;
Update each x in ael by dx;
end
end
end
;
Algorithm 2.9.1.1.
An ordered edge list fill algorithm.
