|The Free Span Buffer algorithm|
One of the problems to face when working in 3D graphics is the hidden
surface removal problem. With this name we mean the display of a scene
where nearer objects hide objects far away. This problem can be splitted
in two different subproblems: the priority problem (i.e. find out "what
is hiding what") and "how" the hiding is obtained.
In this text I won't address the first problem (may be I'll write
something in another note) and so I'll assume that there's an ordered
sequence of polygons p1,...,pn where pi hides pj if i>=j).
This means that for a general scene some additional hypotesis has been
take in account or that some other computation has be done as it's easy
to see that no such an ordering exists in general.
This simple example shows how it's impossible to find an ordering
for drawing polygons in a general scene.
Painter and z-buffer algorithms
A possible approach to the problem is called usually the "painter's
algorithm" and consists in drawing all the polygons starting from
the most far and ending with the nearest one. This algorithm is surely
simple but has the major drawback of computing a lot of information that
is thrown away. To see this consider that for every pixel of every
polygon you'll end up computing the textures, the lighting, the fogging
... and then a lot of these computed pixels will be overwritten later
but something nearer the camera.
A partial solution, that also allows to work with an unperfect ordering,
is the z-buffer algorithm that consists in keeping for every pixel a
depth value togheter with the color: when drawing a polygon a pixel is
actually computed and drawn only if the depth is smaller than the depth
of the pixel currently on the screen. Obviously with a z-buffer approach
it's best to draw near polygon first. The simplicity of the algorithm
makes it suitable of hardware implementation and the low cost of fast
memory made z-buffer to appear as available in hardware on most
video cards. Z-buffer solves at the same time the priority problem and
the rendering problem.