Clipping - Computer Graphics and Geometric Modeling - page 88

for each edge e of polygon do
begin
Determine the direction of e;

{ Used to tell in what order the bounding
lines of the clip region will be hit }

Find exit t values;
if t_out2 > 0 then find t_in2;
if t_in2 > t_out1
then { No visible segment }

begin
if 0 < t_out1 £ 1 then OutputVertex (turning vertex);

end

else

begin
if (0 < t_out1) and (t_in2 £ 1) then
begin

{ Part of segment is visible }

if 0 £ t_in2
then OutputVertex (appropriate side intersection)
else OutputVertex (startin g vertex);
if t_out1 £ 1
then OutputVertex (appropriate side intersection)
else OutputVertex (ending vertex);

end

end ;
if 0 < t_out2 £ 1 then OutputVertex (appropriate corner);
end ;

Algorithm 3.3.3.1. Overview of a Liang-Barsky polygon-clipping algorithm.

3.3.4 Maillot Polygon Clipping

The Maillot clipping algorithm ([Mail92]) clips arbitrary polygons against a rectan-
gular window. It uses the well-known Cohen-Sutherland clipping algorithm for seg-
ments as its basis and then finds the correct turning points for the clipped polygon
by maintaining an additional bit of information. As indicated earlier, it is speedy deter-
mination of turning points that is crucial for polygon clipping, and this algorithm
does it very efficiently. We shall use the same notation that was used in Section 3.2.1.
We also assume that the same encoding of points is used. This is very important; oth-
erwise, the tables Tcc and Cra below must be changed.
Let P be a polygon defined by the sequence of vertices p 0 , p 1 ,..., p n , p n+1 = p 0 .
Algorithm 3.3.4.1 gives a top-level description of the Maillot algorithm.
In addition to the Cohen-Sutherland trivial rejection cases, Maillot's algorithm
subjects all vertices of the polygon to one extra test, which he calls the “basic turning
point test.” This test checks for the case where the current point lies in one of the four