The major hidden surface removal algorithms are described in most computer graphics textbooks and are classified in a highly relevant paper by Sutherland et al. (1974).  In this paper algorithms are characterized as to whether they operate primarily in object space or image (screen) space and the different uses of 'coherence' that the algorithms employ.  Coherence is a term used to describe the process where geometrical units, such as areas or scan line segments, instead of single points are operated on by the hidden surface removal algorithm.
 
There appear to be two popular approaches to hidden surface removal.  These are scan line based systems and Z-buffer based systems. Other approaches to hidden surface removal such as area subdivision (Warnock, 1969), or depth list schemes (Newell et al., 1972) are not particularly popular now or are reserved for special-purpose applications such as flight simulation.
 
The Z-buffer algorithm

We start by considering the easier of the two approaches - the Z-buffer renderer.  The Z-buffer algorithm, developed by Catmull(1975), is as ubiquitous in computer graphics as the Phong reflection model and interpolator, and the combination of these represents the most popular rendering option.  Using Sutherland's classification scheme (Sutherland et al., 1974) it is an algorithm that operates in image or screen space.
 
Pixels in the interior of a polygon are shaded, using an incremental shading scheme, and their depth is evaluated by interpolatio from the z values of the polygon vertices after the viewing transformation has been applied.  Thus we can imagine a three-dimensional screen space, where the (x, y) values are pixel coordinates and the z value is the interpolated viewing space depth.
 
The Z-buffer algorithm is equivalent, for each point (X, y), to a search through the associated z values of each interior polygon point to find that point with the minimum z value.  This search is conveniently implemented by using a Z-buffer that holds for a current point (x, y) the smallest z value so far encountered.  During the processing of a polygon we either write the intensity of a point (x, y) into the frame buffer or not, depending on whether the depth z, of the current point is less than the depth so far encountered as recorded in the Z-buffer.
 
The overwhelming advantage of the Z-buffer algorithm is its simplicity of implementation.  Its main disadvantage is the amount of  memory required for the Z-buffer.  The size of the Z-buffer depends on the accuracy to which the depth value of each point (x, y) is to be stored, which is a function of scene complexity. 20-32 bits are usually deemed sufficient and the scene has to be scaled to this fixed range of z so that accuracy within the scene is maximized.  Note that for frame buffers smaller than 24 bits per pixel, say, the Z-buffer will in fact be larger than the frame buffer.  In the past Z-buffers have tended to be part of the main memory of the host processor, but now graphics terminals are available with dedicated Z-buffers and this represents the best solution.
 
The Z-buffer imposes no constraints on database organization (other than those required by the shading interpolation) and in its simplest form can be driven on a polygon-by-polygon basis, with polygons being presented in any convenient order.
 
In principle, for each polygon we compute:

    (1)   the (x, y) value of the interior pixels,

    (2)   the z depth for each point (x, y), and

    (3)   the intensity I for each point (x, y)
 
Thus  we have three concurrent bilinear interpolation processes and a triple nested loop. The z values and intensities I are available at each vertex and the interpolation scheme for z and I is distributed between the two inner loops of the algorithm.
 
An extended version of the by-polygon algorithm with Z-buffer hidden surface removal is as follows:

For (all x, y) do
   Z-Buffer [x, y] = maximum-depth

for (each polygon) do
   {construct an edge list from the polygon edges
   (that is, for each edge, calculate the values of x, z and I for each
   scan line by interpolation and store them in the edge list)}
   for y = ymin to ymax do

for {each segment in EdgeList[y]) do
   {get Xleft, Xright, Zleft, Zright, Ileft, Iright)

   for x = Xleft to Xright do
      {linearly interpolate z and I between
      Zleft, Zright and Ileft, Iright respectively}
      if z < Z-Buffer[x, y] then
         {Z-Buffer[x, y]  = z
          frame-buffer[x, y] = I}
 
The structure of the algorithm reveals the major inefficiency of the method in that shading calculations are performed on hidden pixels which are then either ignored or subsequently overwritten.  The extent of this duplication will be a function of the overall order in which the polygons in the scene are examined.  If preprocessing is possible, so that those polygons nearest the view point are processed first, considerable savings can be made.
 
If Phong interpolation is used then the final reflection model calculations, which are a function of the interpolated normal, should also appear within the innermost loop; that is, interpolate N rather than I, and replace the last line with:

        frame-buffer[x, y]  = ShadingFunction (N)

Scan line Z-buffer

There is a variation of the Z-buffer algorithm for use with scan line based renderers, known (not surprisingly) as a scan line Z-buffer.  This is simply a Z-buffer which is only one pixel high, and is used to solve the hidden surface problem for a given scan line.  It is re-initialized for each new scan line.  Its chief advantage lies in the small amount of memory it requires relative to a full-blown Z-buffer; in fact it is very common to see a scan line Z-buffer based program running on systems which do not have sufficient memory to support a full Z-buffer.

Spanning hidden surface removal

A spanning hidden surface removal algorithm attempts, for each scan line, to find 'spans' across which shading can be performed.  The hidden surface removal problem is thus solved by dividing the scan line into lengths over which a single surface is dominant.  This means that shading calculations are performed only once per pixel, removing the basic inefficiency inherent in the Z-buffer method.  Set against this is the problem that spans do not necessarily correspond to polygon segments, making it harder to perform incremental shading calculations (the start values must be calculated at an arbitrary point along a polygon segment, rather than being set to the values at the left-hand edge).  The other major drawback is in the increase in complexity of the algorithm itself, as will be seen.
 
It is generally claimed that spanning algorithms are more efficient than Z-buffer based algorithms, except for very large numbers of polygons (Foley and Van Dam, 1982; Sutherland et al., 1974).  However, since extremely complex scenes are now becoming the norm, it is becoming clear that, overall, the Z buffer is more efficient, unless a very complex shading function is being used.

A spanning scan line algorithm
 
The basic idea, as has been mentioned, is that, rather than solving the hidden surface problem on a pixel-by-pixel basis using incremental z calculation, the spanning scan line algorithm uses spans along the scan line over which there is no depth conflict.  The hidden surface removal process uses coherence in x and deals in units of many pixels.  The processing implication is that a sort in x is required for each scan line and the spans have to be evaluated.
 
The easiest way to see how a scan line algorithm works is to consider the situation in three-dimensional screen space (xs,ys,zs). A  scan line algorithm effectively moves a scan line plane, that is a plane parallel to the (x,y,z,) plane, down the y, axis.  This plane intersects objects in the scene and reduces the hidden surface problem to two-dimensional space (xs,zs).  Here the intersections of the scan line plane with object polygons become lines (see the figure below).

                                                                       

Note that the precise orientation of this plane, with respect to the objects in world coordinates, depends on the transformations used.  If a perspective transformation is employed then the objects would be distorted in three-dimensional screen space.  These line segments are then compared to solve the hidden surface problem by considering 'spans'.  A span is that part of a line segment that is contained between the edge intersections of all active polygons.  A span can be considered a coherence unit within the extent of which the hidden surface removal problem is 'constant' and can be solved by depth comparisons at either end of the span.  Note that a more complicated approach has to be taken if penetrating polygons are allowed.
 
It can be seen from this geometric overview that the first stage in a spanning scan line algorithm is to sort the polygon edges by y, vertex values.  This results in an active edge list which is updated as the scan line moves down the y, axis.  If penetrating polygons are not allowed, then each edge intersection with the current scan line specifies a point on the scan line where 'something is changing', and so these collectively define all the span boundary points.
 
By going through the active edge list in order, it is possible to generate a set of line segments, each of which represents the intersection of the scan line plane with a polygon.  These are then sorted in order of increasing xs.

 Within a span the hidden surface problem is resolved by
 considering depths along one of the span boundaries.

The innermost loop then processes each span in the current scan line.  Active line segments are clipped against span boundaries and are thus subdivided by these boundaries.  The depth of each subdivided segment is then evaluated at one of the span boundaries and hidden surface removal is effected by searching within a span for the closest subdivided segment.  This process is shown in the figure above.

In pseudo-code the algorithm is:

for {each polygon}
   {Generate and bucket sort in ys the polygon edge information.)

for {each scanline}
   for {each active polygon)
     {Determine the segment or intersection of the scan plane and polygon.
      Sort these active segments in xs.
     Update the rate of change per scan line of the shading parameters. }

{Generate the span boundaries.}
   for {each span}
      {Clip active segments to span boundaries.
       Evaluate the depth for all clipped segments at one of the span boundaries.
       Solve the hidden surface problem for the span by finding the segment with minimum zs.
       Shade the visible clipped line segment.
       Update the shading parameters for all other line segments by the rate of change per pixel times the span width. }

Note that integrating shading information is far more cumbersome than with the Z-buffer.  Records of values at the end of clipped line segments have to be kept and updated.  This places another scene complexity overhead (together with the overhead of the absolute number of polygons) on the efficiency and memory requirements of the process.
 
Comparative Points

From an ease of implementation point of view the Z-buffer is best.  It has significant memory requirements, particularly for high resolution frame buffers.  However, it places no upwards limit on the complexity of scenes, an advantage that is now becoming increasingly important.  It renders scenes one object at a time and for each object one polygon at a time. This is both a natural and a convenient order as far as database considerations are concerned.
 
An important restriction it places on the type of object that can be rendered by a Z-buffer is that it cannot deal with transparent objects without costly modification.  A partially transparent polygon may:

 (1)   be completely covered by an opaque nearer polygon, in which case there is no problem, or

 (2)   be the nearest polygon, in which case a list of all polygons behind it must be maintained so that an appropriate combination of the transparent polygon and the next nearest can be computed (the next nearest polygon is not of course known until all polygons are processed).

Compared with scan line algorithms, anti-aliasing solutions, particularly hardware implementations, are more difficult.

Cook et al. (1987) point out that a Z-buffer has an extremely important 'system' advantage.  It provides a 'back door' in that it can combine point samples with point samples from other algorithms that have other capabilities such as radiosity or ray tracing.
 
If memory requirements are too prodigious then a scan line Z- buffer is the next best solution.  Unless a renderer is to work efficiently on simple scenes, it is doubtful whether it is worth contemplating the large increase in complexity that a spanning scan linealgorithm demands.
 
Historically there has been a shift in research away from hidden surface problems to realistic image synthesis.  This has been motivated by the easy availability of high spatial and colour resolution terminals.  All the 'classic' hidden surface removal algorithms were developed prior to the advent of shading complexities and it looks as if the Z-buffer will be the most popular survivor for conventional rendering.