Mumbai university > Comp > SEM 4 > Computer Graphics

Marks: 10M

Year: May 2014

1. Boundary fill algorithm and flood fill algorithm is defined at pixel level.

2. Scan line fill algorithm is defined at geometric level i.e. coordinates, edges, vertices etc.

3. The algorithm starts with first scan line and proceeds line by line to the last scan line.

4. It checks whether every pixel on that scan line satisfies inside point test or not i.e. it checks which points on that scan line are inside the polygon.

5. This method avoids the need for seed point.

6. Consider this example of convex polygon to explain this algorithm.

1. As shown in figure 12, algorithm begins with first scan line i.e. Ymax and proceed line by line towards the last scan line i.e. Ymin.

2. Here we are considering only the first and line scan and not individual edges.

3. For each edge of polygon we are storing 5 attributes along with the slope.

4. For AB we are storing:

   • Xmax: X2

   • Xmin: X1

   • Ymax: Y2

   • Ymin: Y1

5. Likewise we find for AD, CD and BC.

1. In this we have to select only those edges which are getting intersected by scan line.

2. For this we are using Ymax of particular edge to find out whether it is intersecting by scan line or not

3. Now sort the Ymax array.

1. So from the table we can find out that edge AB and BC are intersection of scan line.

2. Every time we are decreasing the scan line by 1, from Ymax to Ymin of polygon. Refer figure13

1. Now we have to find the corresponding X value for the intersection point.

   Slope (m) = DY/DX = Change in Y / Change in X.

   = Ynew – Yold / Xnew – Xold

   = 1 / Xnew – Xold

   Xnew – Xold = 1 / m

   Therefore, Xnew = Xold + 1/m.

2. Like this we are finding intersecting of scan line with every edge of polygon.

3. Once we have found the intersecting points with both edges i.e. selected edges like AB and BC, then join these two intersecting points by solid line and continue.

4. Again decrease Y by 1 and find out new intersection points for those edges till one of the edges gets over i.e. the scan line goes below Ymin of one edge.

1. In this case edge BC gets over earlier, so discard edge BC and select next edge from sorted table, which is CD and continue the process.

2. The process continues till scan line reaches to Ymin of the polygon.