Copyright (c) Susan Laflin. August 1999.

 
 O	Input data in 3D is a set of solids defined by 
	plane polygonal faces. 
 I	The intermediate data is a subset of faces and edges in 3D.
 S 	The output data is a set of edges in 2D, which will give 
	a drawing of the 3D object.
T	The transition functions used by the algorithm.
	PM  	A perspective transformation from viewpoint V. 
		(It is easy to modify the algorithm to work with 
		a parallel transformation if required). 
	IS  	Intersection of a line with a plane. 
	CT  	Does the point of intersection of line and plane 
		lie within a particular triangle ? 
	DT  	Perspective depth test. 
	VT  	Visibility test for perspective case to decide which 	
		faces can be eliminated from consideration.
M	Strategy Function or Overall Method.
 
         	1. Eliminate all invisible edges. 
         	2. Calculate the `Quantitative Invisibility' 
		of all remaining segments of the remaining edges.
         	3. Project into 2D and draw all line-segments with 
		a Q.I. of zero (i.e. all visible segments).
 
Now let us look at the method in a little more detail.

Eliminate Invisible Edges.

a) Apply VT to decide which faces are potentially-visible and which are invisible.

b) Consider the edges. These fall into three categories.

(i) An edge joining two invisible faces is itself invisible. This will be deleted from the list and ignored.

(ii) An edge joining two potentially-visible faces is called a `material edge' and will require further processing.

(iii) An edge joining a potentially-visible face and an invisible face is a special case of a `material edge' and is also called a `contour edge'.

At the end of this part of the method, we have a list of material edges and some of them are flagged because they are also contour edges. These are important because the `Quantitative Invisibility' (a count of the number of faces between that edge and the viewpoint) of a material edge remains constant UNTIL it crosses a contour edge.

Calculate Q.I.of Material Edges.

The method must be applied to each material edge in turn. Let us consider the edge P1P2, and work in the plane containing the triangle VP1P2, where V is the viewpoint. First consider the point P1 and calculate its Q.I. by searching along the line from V to P1 and counting the number of potentially visible faces which intersect this line between V and P1 (zero in the diagram). Next do the same for P2.

Now for each contour edge in the figure, test whether its intersection E with the plane VP1P2 lies inside the triangle VP1P2 or not. If it does lie within the triangle, then the point E' on the line P1P2, where the line VE intersects it, will be the point at which the Q.I. of the line P1P2 changes by +1 or -1. (The sign of the cross product of the contour edge and the edge P1P2 will determine whether it is positive or negative.) If all these intersection points lie outside the triangle, then the Q.I. of the line is unchanged.

At the end of this process, each segment of a material edge has a value of Q.I. associated with it.

Draw all Visible Segments.

The intermediate data is a set of edges and segments in 3D, with values of Q.I. associated with them. Those for which the Q.I. is zero are visible, and these need to be projected into 2D and then drawn. This produces a drawing of the object with hidden lines removed.