Featured

# Scan Line Algorithm

Scan Line Algorithm

Scan line algorithm is an example of image space algorithm.  Rather than looking for one polygon surface we deal with multiple surfaces.  As each scan line is processed, all polygon surfaces intersecting that line are examined to determine which are visible.

We set two tables in this algorithm, one is edge table which contains coordinate end points for line in scene, inverse slope of each line (i.e 1/m) and pointers into polygon table to identify the polygon for each edge.

The other table polygon table contains coefficients of plane equation for each surface, intensity information for each surface and pointers into edges.

The edges which intersect the given scan line are made as active edge and sorted in an active edge list.  The active edge list contains edges that cross current scan line and sort them in increasing order of x.

A flag is also used for each surface.  Flag is set to on if position along scan line is inside the surface and set to off if it is outside.  Scan lines are processed from left to right.  At the leftmost boundary of surface, flag is turned on and at the rightmost boundary it is turned off.
Across each scan line, depth calculations are made for each overlapping surface to determine which is nearest to the view plane.  When visible surface is determined, intensity value for that position is stored in refresh buffer consider the following figure :->

Scan line 1 intersects edges AB, BC, EH and FG.  Scan line for positions between edge AB and BC flag for surface S1 is on therefore no depth calculations are necessary and intensity information for S1 is stored in refresh buffer.  Similarly between edges EH and FG, only flag for surface S2 is on.  In the remaining  areas for scan line 1 intensity value is set to background intensity.

Along scan line 2 from edge AD to EH, only flag for S2 is on.  But between edges EH and BC, flags for both surfaces are off.  Hence in this interval, depth calculations must be made using plane coefficients for two surfaces.  If the depth of S1 is lies above the S then intensities for S1 are loaded in refresh buffer.

For S2 between edges BC and FG for scan line 2, flag for S2 is set to off and intensities for S2 are stored until edge FG is passed through scan line 3, there is no need to calculate depth between edges FG and BC.