Scan-Line Method: Hidden Surface Removal

The scan-line method is an image-space hidden surface removal algorithm that processes the scene one horizontal row of pixels (scan line) at a time, from the top to the bottom of the screen. 

Rather than processing each polygon completely and independently (as the Z-buffer does), the scan-line method intelligently processes all polygons together along each scan line, exploiting the fact that surfaces and their depth relationships change gradually and predictably from one scan line to the next. 

This approach makes excellent use of coherence and was historically the dominant method before hardware Z-buffers became universal.

What is the Scan-Line Method?

In a raster display, the screen consists of horizontal rows of pixels called scan lines (or raster lines). The scan-line method processes the scene row by row: for each scan line (fixed y-value), it determines which polygons intersect that scan line, computes their depth values at each pixel along the scan line, and determines which surface is visible at each pixel.

The algorithm is intimately tied to scan-line conversion (rasterization) the process of converting vector-based polygon descriptions into individual pixel colors. Hidden surface removal happens simultaneously as polygons are scan-converted, rather than as a separate post-projection step.

Key Data Structures

The scan-line method uses several important data structures to efficiently manage polygon processing across scan lines:

1. Edge Table (ET)

The Edge Table is a sorted array of all polygon edges in the scene. Each entry in the ET is indexed by the y-coordinate of the edge's lower vertex (the scan line where the edge first becomes active). Each entry stores:

• y_max: The y-coordinate of the top vertex of the edge (where the edge ends).
• x_min: The x-coordinate of the edge at y_min (where the edge starts).
• ΔX (x-increment): The change in x per scan line = 1/slope = Δx/Δy (how much x changes as y increases by 1).
• Depth information: Either a reference to the polygon's plane equation, or precomputed depth values for Z-comparison.

Edges are grouped (bucketed) by their lower y-coordinate so they can be efficiently added to the Active Edge Table as the scan line moves downward.

2. Active Edge Table (AET)

The Active Edge Table contains only the edges that are currently intersecting the current scan line. It is updated at each scan line:

• New edges are added from the ET when their lower y-coordinate matches the current scan line.
• Edges are removed when y exceeds their y_max (the edge ends above the current scan line).
• Edge x-coordinates are updated at each new scan line by adding ΔX.
• Entries are kept sorted by x-coordinate (left to right) for efficient scan-line processing.

3. Polygon Table (PT)

The Polygon Table stores information about each polygon in the scene:

• Plane equation coefficients (A, B, C, D) used to compute Z at any (x, y).
• Color or surface shading information.
• An active flag whether the polygon is currently being scanned.

The Scan-Line Algorithm Step by Step

1. Build the Edge Table (ET):
   For every non-horizontal edge of every polygon:
     Add an entry at y = y_min of the edge, storing y_max, x, ΔX,
     and a reference to the parent polygon.

2. Initialize:
   Active Edge Table (AET) = empty
   Current scan line y = y_min of entire scene

3. For each scan line y (from bottom to top, or top to bottom):
   a. Add to AET all edges in ET whose y_min = current y.
   b. Remove from AET all edges whose y_max < current y (edges that ended).
   c. Sort AET by x-coordinate (left to right).
   d. Process AET edges in pairs — each pair of consecutive edges
      defines a horizontal span between two polygon boundaries:
      - For each span between edges [x_left, x_right]:
        * Identify which polygons are active in this span.
        * For each pixel x in [x_left, x_right]:
          - Compute Z for each active polygon at (x, y).
          - The polygon with the smallest Z (closest) is visible.
          - Write that polygon's color to the frame buffer.
   e. Update x-coordinates for all edges in AET: x = x + ΔX.
   f. Move to next scan line: y = y + 1.

Depth Computation Along a Scan Line

For a polygon with plane equation Ax + By + Cz + D = 0:

z = -(Ax + By + D) / C

Along a fixed scan line (fixed y), as x increases by 1:

Δz = -A/C   (z changes by -A/C for each step in x)

This means that once the initial Z at the left edge of a span is computed (one division), subsequent Z-values across the entire span can be obtained by addition only the same incremental technique used in the Z-buffer.

Similarly, as the scan line moves up by 1 (y increments by 1), the starting Z at the left edge changes by:

Δz (per y step) = -B/C

This coherent, incremental approach makes depth computation extremely efficient.

Handling Surface Priority Along a Scan Line

In any span between two AET edge pairs, multiple polygons may be active (overlapping). Determining which one is closest at each pixel requires Z-comparison. 

The scan-line method handles this using a depth comparison at each pixel within the span, similar to Z-buffer, but only among the polygons known to be active on the current scan line.

If a span is covered by only one polygon (no overlap), no depth comparison is needed the single active polygon is directly visible at all pixels in that span.

Exploiting Coherence

The scan-line method's efficiency comes from exploiting several forms of coherence:

• Edge coherence: An edge active on scan line y is usually active on scan line y+1 too (until it reaches its y_max). Only a few edges enter or leave the AET at each scan line.
• Scan-line coherence: The ordering of edges along the AET changes very little from one scan line to the next (edges move slowly in x), reducing sorting work.
• Depth coherence: Z-values change linearly across a span (incremental computation by addition), and across scan lines, the starting Z at each edge also changes linearly.
• Span coherence: If a span is covered by only a single polygon, depth testing is unnecessary for that entire span.

Properties and Advantages

1. Efficient use of coherence: By processing all polygons together scan-line by scan-line, the method avoids redundant per-polygon, per-pixel computations.
2. Low memory footprint: Unlike the Z-buffer, the scan-line method does not require a full-resolution depth buffer. Only the current scan line's depth information needs to be maintained, making it suitable for memory-constrained environments.
3. Handles arbitrary polygon complexity: Works correctly for any set of planar polygons, including overlapping and interpenetrating ones.
4. Natural fit with rasterization: Scan-line processing is the natural loop structure for converting polygons to pixels, so HSR integrates cleanly into the rasterization process.

Limitations

1. Complexity of implementation: Managing the Edge Table, Active Edge Table, sorting, and coherence tracking is significantly more complex to implement correctly than the Z-buffer.
2. Less hardware-friendly: The scan-line method's sequential, highly interdependent nature (each scan line depends on the previous one's AET state) does not map as naturally to massively parallel GPU architectures as the Z-buffer does.
3. Per-span depth comparison overhead: In scenes with many overlapping transparent or complex polygons, per-pixel depth comparisons within spans can become expensive.

Conclusion

The scan-line method is a historically significant HSR algorithm that demonstrates how the careful exploitation of coherence can produce an efficient, memory-friendly visibility solution. 

By processing all polygons together across each scan line using Active Edge Tables and incremental depth computation, it avoids the memory cost of a full-resolution Z-buffer while still correctly resolving visibility for any set of planar polygons. 

Though largely supplanted by hardware Z-buffering in real-time rendering, the scan-line method remains important in software renderers, academic study, and certain specialized applications where its coherence-based approach offers specific advantages.