Scan-line method of visible surface

The scan-line method is an image-space method that extends the polygon scan-fill algorithm. Visibility is decided one scan line at a time, from top to bottom, for all polygons that cross that scan line.

Data structures

• Edge table: each edge's end points, slope and the polygon it belongs to.
• Polygon table: plane coefficients, colour, and an in/out flag for each polygon.
• Active edge list: the edges crossed by the current scan line, sorted by x.

Algorithm

for each scan line y (top to bottom):
    update the active edge list (add/delete edges, update x)
    sort the intersections by x
    for each span between successive intersections:
        - flip the in/out flag of the polygon whose edge is crossed
        - if only one polygon flag is "in":  fill the span with its colour
        - if several flags are "in":  compute the depth of each polygon
              (z = (-Ax - By - D)/C) in the span; fill with the
              nearest polygon's colour
        - if none is "in": use the background colour

Example. Two overlapping polygons S1 and S2 (S1 is in front). The scan line crosses edges at a < b < c < d; S1 covers a to c and S2 covers b to d.

 scan line y:   a=========c              S1 flag IN from a to c
                     b=========d         S2 flag IN from b to d

 a-b : only S1 is IN       -> colour S1
 b-c : S1 and S2 are IN    -> compare depths, S1 nearer -> colour S1
 c-d : only S2 is IN       -> colour S2

For non-intersecting surfaces, the depth needs to be computed only once, at the start of the overlap. If surfaces intersect, the span is split at the intersection point. Coherence between successive scan lines (edge intersections change very little from one scan line to the next) speeds up the method.