Copyright (c) Susan Laflin. August 1999.

This uses a form of spatial subdivision to improve the 
efficiency of the algorithm.  

O 	Input data in 3D is a curved surface represented as 
	patches forming a grid of uv-lines. 
I	Intermediate data include details of scan-grid and 
	coordinates of rectangles containing the patches.
S	Output data is visible segments of sides of patches.      
T 	The Transition Functions.
	PM	parallel projection on to z=0.
	IS 	intersections of recatngles and scan-grid.
	CT	test-point within triangle.
	DT	distance from z=0 plane.
	VT	visibility of each test-point.
M	Method or Strategy Function.

1. Sort patches against scan-grid.

For each patch, calculate the smallest rectangle which contains the corners. Compare this rectangle with the values defining the scan-grid and add this patch to the list of any grid-square it intersects.

2. Apply Visibility Test.

If only one patch intersects the grid-square, then the patch must be visible.

If more than one patch intersects the grid-square, then use the visibility test to decide which segments are visible. Select a number of equally-spaced test-points along each edge. Check each test-point against the other patches in that grid-square to decide whether it is visible or not.

To save time, the depth-test is carried out in terms of planes joining three of the corners of the patch. If the depth and containment tests show t hat the test-point is hidden by both the planes, then it is invisible. If it is hidden by one plane and in front of the other, then some arbitrary decision must be made. (Possibly to evaluate the curved surface at this point and test exactly).

Method concludes with each patch having a set of visible test-points, indicating the sections to be drawn, and a set of invisible ones which are not drawn. Either set may be empty.

Efficiency of Calculation.

During the visibility testing, each test-point is compared with a list of patches. Once a patch has been found which covers one test-point, it is likely to cover others. Consequently it is moved to the top of the list and is the first patch to be compared with the other test-points. This reduces the average number of tests to obtain a decision.

Size of Mesh for Scan-Grid.

This is very dependent on the particular image being processed. If a typical image contains 100-400 patches, it has been found that a scan-grid of 11x11 (121 squares) will often suffice. If some areas of the image are much more complex than others, it is possible to subdivide some of the grid-squares. One example which gave satisfactary results, chose to subdivide the any grid-square which contained more than 8 patches.