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

Procedure CheckForSegIntersections ( ref boolean intersected; ref real xint)
if two segments in the activeEdges list intersect at an x-coordinate xint with

spanLeft < xint < spanRight
then intersected := true
else

begin
intersected := false ;
if two segments in activeEdges touch at spanLeft
then xint := spanRight
else xint := spanLeft;

end ;

polydata function MinActiveZvaluePolygon ( real x, y);
{ Scan active polygon list and return the data for the one with minimum zvalue at
(x,y). The z values are determine by the equation z = -(a*x + b*y + d)/c where
a,b,c, and d are the coefficients of the planes of the polygons. }

color function LastVisiblePolygonColor ()
{ Checking for intersections is where we may have to do a lot of work }
begin
real stack spanStack;
boolean intersected;

real xint;

Reset stack of spans spanStack to empty;
repeat forever
CheckForSegIntersections (intersected,xint);
if intersected
then
begin
{ There was an intersection. Push current spanRight,
divide the span, and process the left half [spanLeft,xint] }
Push (spanright,spanStack);
spanRight := xint;

{LC} end

else

begin
segcol := ColorOf (MinActiveZvaluePolygon (xint,y));

if Empty (spanStack) then return (segcol);

Display ([spanLeft,spanRight],segcol);

{LD} spanLeft := spanRight;

spanRight := Pop (spanStack);

end

end
end ; { LastVisiblePolygonColor }

Algorithm 7.8.1. Continued