Scan Line Algorithm:-

A scan line method of hidden surface removal is an another approach of image space method. It is an extension of the scan line algorithm for filling polygon interiors. Here, the algorithm deals with more than one surfaces. As each scan line is processed, it examines all polygon surfaces intersecting that line to determine which are visible. It then does the depth calculation and finds which polygon is nearest to the view plane. Finally, it enters the intensity value of the nearest polygon at that position into the frame buffer.

The scan line algorithm maintains the edge list in the edge table(ET). The AET(Active Edge Table) contains only edges that cross the current scan Line, sorted in order of increasing x. The scan line method of hidden surface removal also stores a flag for each surface that is set on or off to indicate whether a position along a scan line is inside or outside of the surface. Scan lines are processed from left to right. At the leftmost boundary of a surface, the surface flag is turned ON; and at the rightmost boundary, it is turned OFF.

The figure (f) illustrates the scan line method for hidden surface removal. As shown in the Fig. (f), the active edge list for scan line 1 contains the information for edges AD, BC, EH and FG. for the positions along this scan line between edges AD and BC, only the flag for surface S1 is ON. Therefore, no depth calculations are necessary, and intensity information for surface S1 is entered into the frame buffer. Similarly, between edges EH and FG, only the flag for surface S2 is ON and during that portion of scan line the intensity information for surface S2, is entered into the frame buffer.

For scan line 2 in the figure (f), the active edge list contains edges AD, EH, BC and FG. Along the scan line 2 from edge AD to edge EH, only the flag for surfaces S1 is ON. However, between edges EH and BC, the flags for both surfaces are ON. In this portion of scan line 2, the depth calculations are necessary. Here we have assumed that the depth of S1 is less than the depth of S2 and hence the intensities of surface S1 are loaded into the frame buffer. Then, for edge BC to edge FG portion of scan line 2 intensities of surface S2 are entered into the frame buffer because during that portion only flag for S2 is ON.

To implement this algorithm along with AET we are required to maintain a polygon table (PT) that contains at least the following information for each polygon, in addition to ID.

1. The coefficient of the plane equation.

2. Shading or colour information for the polygon.

3. A in-out Boolean flag, initialized to false and used during scan line processing.

Fig. (g) Shows the ET, PT and AET for the scan line algorithm.