6502's cornerFree Span Buffer [1]

Who am I
Small ones
My blog
Write me

Versione italiana 

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.

Cyclic overlap
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.