Polygons Part 2

Pattern Fills

We have now examined how the edge list is generated and how the current edge list is maintained with two pointers L and R. Let us examine how the procedure fill might be coded as follows:

procedure fill(l,          {leftmost current active edge}
               r:integer); {rightmost}
var
  numpairs : integer; {# of edge pairs in current list}
  i,j:integer;        {counters}
begin
  numpairs := (r-l+1) div 2;
  j := l;
  for i := 1 to numpairs do
    begin
      hline(round(x[j],scanheight,round(x[j+1])));
      j := j + 2;
    end
end

If we would like to do some kind of pattern fill, all we need to do is modify the above routine. The question is, what kind of modification is necessary?

To do a polygon fill, we need some fill pattern which is usually stored in a two-dimensional array. The size of the array depends on the graphics system. That is, are we working in B/W or color. How many bits are allocated per pixel? What size are we going to allow for the pattern?

For purposes of discussion, we will assume an array that is 8x8 with a depth of 8 bits (i.e. 8-bits per pixel). In order to do a fill, we will assume that row 0 of this table will always map to rows 0,8,16,... in the frame buffer. Row 1 will always map to 1,9,17,... ans so on. The same thing will be done with columns and all of this will be done using modulo arithmetic. The algorithm now becomes:

procedure fill(l,          {leftmost current active edge}
               r:integer); {rightmost}
var
  numpairs : integer;   {# of edge pairs in current list}
  i,j,k:integer;        {counters}
  row,
  col:integer;
begin
  numpairs := (r-l+1) div 2;
  row := scanheight mod 8;
  j := l;
  for i := 1 to numpairs do
    begin
      for k := round(x[j]) to round(x[j+1]) do
        begin
          col := k mod 8;
          plot_pixel(k,scanheight,pattern[row,col])
        end;
      j := j + 2;
    end
end

This algorithm can be optimized. How?

Also, ideally this algorithm would probably be implemented in assembly language. An interesting project would be to see how efficient this program can be made in C versus how efficient this program can be made in Assembly.

Douglas J. Ryan/ryand@tardis.pacificu.edu