Graphics Reference
In-Depth Information
{ Global variables }
real list
SBL; { an
ordered
list of
distinct
reals thought of as a stack}
bound pair list
LML; { a list of pairs of matching polygon bounds }
edge list
AEL; { a list of
nonhorizontal
edges ordered by x-intercept
with the current scan line}
polygon list
PL;
{ the finished output polygons are stored here as algorithm
progresses }
polygon list function
Vatti_Clip (
polygon
subjectP;
polygon
clipP)
{ The polygon subjectP is clipped against the polygon clipP.
The list of polygons which are the intersection of subjectP and clipP is returned to the
calling procedure. }
begin
real
yb, yt;
Initialize LML, SBL to empty;
{ Define LML and the initial SBL }
UpdateLMLandSBL (subjectP,
subject
);
{
subject
and
clip
specify a subject }
{ or clip polygon, respectively }
UpdateLMLandSBL (clipP,
clip
);
Initialize PL, AEL to empty;
yb := PopSBL ();
{ bottom of current scan beam }
repeat
AddNewBoundPairs (yb);
{ modifies AEL and SBL }
yt := PopSBL ();
{ top of current scan beam }
ProcessIntersections (yb,yt);
ProcessEdgesInAEL (yb,yt);
yb := yt;
until
Empty (SBL);
return
(PL);
end
;
Algorithm 3.3.5.1.
The Vatti polygon-clipping algorithm.
We introduce some more terminology. Some edges and vertices that one encoun-
ters or creates for the output polygons will belong to the bounds of the clipped
polygon, others will not. Let us call a vertex or an edge a
contributing
or
noncon-
tributing vertex
or
edge
depending on whether or not it belongs to the output poly-
gons. With regard to vertices, if a vertex is not a local minimum or maximum, then
it will be called a
left
or
right intermediate
vertex depending on whether it belongs to
a left or right bound, respectively. Because the overall algorithm proceeds by taking
