Visible Surface Algorithms - Computer Graphics and Geometric Modeling - page 278

Assume that the viewport is [XMIN,XMAX]¥[YMIN,YMAX] .

{ The data record we need for each polygon in the world. }
polydata = record
integer y, { first scan line crossed by poly }

edgedata list edges; { each edge of polygon has an associated edgedata record }

real a, b, c, d; { ax + by + cz + d = 0 is plane equation for polygon }

color hue;

boolean active; { updated as the algorithm proceeds }

end ;

{ horizontal span endpoint record }
edgedata = record
polydata pointer polyP;

{ pointer to data for polygon to which edge belongs }

real x, { where the edge intersects the current scan line }

dx; { change in x from one scan line to the next }

integer dy; { the number of scan lines left to cross by the edge }

end ;

{ Global variables: }
polydata list activePolys; { the list of currently active polygons }
edgedata list activeEdges; { the list of currently active edges }
polydata list array buckets[YMIN..YMAX];
{ buckets[y] holds all polygons which "start" at scan line y }
real spanLeft, spanRight;

{ used by procedure ProcessActiveEdgeList }

procedure WatkinsAlgorithm ()
begin
integer y;

InitializeData ();

for y:=YMIN to YMAX do
begin

Add any polygons in buckets[y] to active polygon list activePolys;

Scan edges of polygons in activePolys and add those that start at y
to active edge list activeEdges;

Sort edges of activeEdges by increasing x;
(Sorting is needed because when the list gets updated below the ordering
is destroyed if edges cross.)

ProcessActiveEdgeList ();

UpdateActiveEdgeList ();

UpdateActivePolygonList ();

end

end ;

Algorithm 7.8.1. A Watkins visible surface algorithm.