Copyright (c) Susan Laflin. August 1999.

 
O 	Input data in 3D is a set of polygons forming the 
	surface of the object.
I	Intermediate data is the set of potentially-visible 
	polygons in 3D.
S	The output data is a set of sample-scans in 2D and 
	the colour in which each is to be drawn.
T	The transition functions to be used by the algorithm:
	PM 	parallel projection onto the plane of the screen.
	IS 	intersections of pairs of lines.
	CT 	not used.
	DT 	depth = distance from screen.
	VT	visibility test depends on distance from screen.
M	consider the screen, scan-line by scan-line and use the 
	position and colour of the polygons to decide on the colour 
	of each section of the scan-line in turn.
 

The visible faces of a number of objects are represented by the closed polygons P1, P2, ... , Pn in 3D and their orthogonal projections into 2D are shown in the figure. The object is to decide which of the overlapping polygons is closest to the screen and hence which colour should be used to shade various areas on the screen.

The second figure shows a horizontal plane through the scan-line currently under consideration. The polygons which intersect this plane are represented by the lines P1 etc. The scan-line is split up into `sample scans' along which no change in colour is possible. The end of such a scan occurs at orthogonal projection onto the scan-line of each end of a line Pi. In addition, if two polygons intersect each other, the projection of their point of intersection within the plane will also give the end of a sample scan.

Once the line has been split into sample scans, that part of the scan line must be coloured to match the closest polygon (i.e. the one with the greatest priority which is also the one with the smallest z-values).

Another form of output from this algorithm gives a grey-scale picture where the grey-level at each pixel is proportional to the distance z from the nearest surface.

This works in terms of scan lines with the pixel-colour at each point along the line calculated and output. If there is enough storage to hold a copy of the entire screen, instead of just one line across it, we may use a `Z-buffer' algorithm, in which the z value corresponding to each pixel is used to decide on the colour of that pixel. The polygons may be added in any order, but the z-value is used to decide whether a pixel should be changed or not as the next polygon is added. Again coherence may be used to reduce the number of tests needed.