Question

Assume that your task is to draw a polygon with coordinates (5,0), (10,5), (5,10), (0,5) with a solid color (R,G,B).

a) Describe the major steps in the “flood fill” polygon rendering algorithm.

b) Describe the major steps in the “scan line” polygon rendering algorithm.

c) Give one advantage of the “flood fill” versus the “scan line” algorithm.

d) Give one advantage of the “scan line” versus the “flood fill” algorithm.

Answer 1

a) major steps in the “flood fill” polygon rendering algorithm.

Flood fill, also called seed fill, is an algorithm that determines the area connected to a given node in a multi-dimensional array. It is used in the "bucket" fill tool of paint programs to fill connected, similarly-colored areas with a different color, and in games such as Go and Minesweeper for determining which pieces are cleared.
The algorithm looks for all nodes in the array that are connected to the start node by a path of the target color and changes them to the replacement color. There are many ways in which the flood-fill algorithm can be structured, but they all make use of a queue or stack data structure, explicitly or implicitly.
A method exists that uses essentially no memory for four-connected regions by pretending to be a painter trying to paint the region without painting themselves into a corner. This is also a method for solving mazes. The four pixels making the primary boundary are examined to see what action should be taken. The painter could find themselves in one of several conditions:
All four boundary pixels are filled.
Three of the boundary pixels are filled.
Two of the boundary pixels are filled.
One boundary pixel is filled.
Zero boundary pixels are filled.

b) major steps in the “scan line” polygon rendering algorithm.

The algorithm can be sped up by filling lines. Instead of pushing each potential future pixel coordinate on the stack, it inspects the neighbour lines (previous and next) to find adjacent segments that may be filled in a future pass; the coordinates (either the start or the end) of the line segment are pushed on the stack. In most cases this scanline algorithm is at least an order of magnitude faster than the per-pixel one.
To successfully fill in a polygon three main components will be used: Edge Buckets, an Edge Table and an Active List. These components will contain an edge’s information, hold all of the edges that compose the figure and maintain the current edges being used to fill in the polygon, respectively.
Major Steps
1. Create ET
    1. Process the vertices list in pairs, start with [numOfVertices-1] and [0].
    2. For each vertex pair, create an edge bucket
2. Sort ET by yMin
3. Process the ET
    1. Start on the scan line equal to theyMin of the first edge in the ET
    2. While the ET contains edges
        1. Check if any edges in the AL need to be removes (when yMax == current scan line)
            1. If an edge is removed from the AL, remove the associated the Edge Bucket from the Edge Table.
        2. If any edges have a yMin == current scan line, add them to the AL
        3. Sort the edges in AL by X
        4. Fill in the scan line between pairs of edges in AL
        5. Increment current scan line
        6. Increment all the X's in the AL edges based on their slope
            1. If the edge's slope is vertical, the bucket's x member is NOT incremented.

c) advantage of the “flood fill” versus the “scan line” algorithm.
Flood fill colors an entire area in an enclosed figure through interconnected pixels using a single color.
It is an easy way to fill color in the graphics. One just takes the shape and starts flood fill.
The algorithm works in a manner so as to give all the pixels inside the boundary the same color leaving the boundary and the pixels outside. Flood Fill is also sometimes referred to as Seed Fill as you plant a seed and more and more seeds are planted by the algorithm.
Each seed takes the responsibility of giving the same color to the pixel at which it is positioned. There are many variations of Flood Fill algorithm that are used depending upon requirements.

d) advantage of the “scan line” versus the “flood fill” algorithm.
The main advantage of this method is that sorting vertices along the normal of the scanning plane reduces the number of comparisons between edges.
Another advantage is that it is not necessary to translate the coordinates of all vertices from the main memory into the working memory—only vertices defining edges that intersect the current scan line need to be in active memory, and each vertex is read in only once.
The main memory is often very slow compared to the link between the central processing unit and cache memory, and thus avoiding re-accessing vertices in main memory can provide a substantial speedup.