Exploiting scanline coherence for front-to-back visible surface determination

Sumedh Barde worked on this. 
 The HTML version version is available  here 
 The report is available here 

Here is an abstract:

In practice, for a large class of situations, image space algorithms
turn out to be superior in execution time, although object space
algorithms often tend to be intellectually stimulating.  This should
not come as a surprise to computer science theoreticians --- bucketing
based sorting methods are faster than `optimal' heapsort.  It is to
this we turn our attention to.

In the back to front display, also known as the painter's algorithm,
one paints the faces on the screen, one by one, in back to front
order, i.e. the furthest face first. Every successive face thus
overwrites the faces painted before it, if at all its projection
intersects the projections of the latter.

The advantage of this method is its simplicity. On the other hand,
notice that for those pixels which belong to the projections of more
than one face, this method paints those pixels those many times,
whereas one would want it to be painted only once -- with the colour
of the nearest face containing it. This constitutes the major
disadvantage.

In front-to-back display, one paints the faces in front to back order
i.e. nearest face first.  A face is painted however, only in the
regions of the screen which are as yet untouched by any face. Thus
each pixel is painted at most once, unlike the back to front
approach. On the other hand, in its crudest form, painting each object
would involve checking {\em every} pixel (contained in its projection)
to see if it is already lit or unlit. 

Gordon and Chen describe a method of the front-to-back display of faces
and establish the competitive nature of this technique.  The
efficiency is achieved because, simply speaking, a group of visible
pixels are painted together; if a pixel belonging to some face is
visible, it is very likely that the pixel adjacent to it is also
visible. There are, of course, a few pixels on a single scanline that
do not have this property.

We further develop this theme.  We argue that if we have, inductively,
solved the visible surface problem on a single scan line, it is
unlikely that the next scan line is likely to be too different.  Can
we determine how different the next scan line is efficiently?  We
answer this affirmatively.