Graphics Reference
In-Depth Information
number of subdivisions required depends on the precision used. For 32-bit integers,
there will be less than 32 subdivisions.
Maillot presents a C implementation of his algorithm in [Mail92]. Our version of
this algorithm is Algorithm 3.3.4.2 below. The main difference is that we tried to be
as clear as possible by using extra auxiliary functions and procedures. To be efficient,
however, all these calls should be eliminated and the code put inline.
As mentioned earlier, Maillot's algorithm uses the Cohen-Sutherland clipping
algorithm. One can use the implementation in Section 3.2.1 for this except that the
extended encoding function (ExtendedCsCode) shown in Algorithm 3.3.4.3 should be
{ Constants }
MAXSIZE = 1000; { maximum size of pnt2d array }
NOSEGM = 0; { segment was rejected }
SEGM = 1; { segment is at least partially visible }
CLIP = 2; { segment was clipped }
TWOBITS = $10; { flag for 2-bit code }
{ Two lookup tables for finding turning point.
Tcc is used to compute a correct offset.
Cra gives an index into the clipRegion array for turning point coordinates. }
integer array
[0..15] Tcc = (0, -3, -6,1,3,0,1,0,6,1,0,0,1,0,0,0);
integer array
[0..15] Cra = (-1, -1, -1,3, -1, -1,2, -1, -1,1, -1, -1,0, -1, -1, -1);
pnt2d
=
record
real
x, y;
end
;
pnt2ds
=
pnt2d array
[0..MAXSIZE];
{ Global variables }
{ The clipping region [xmin,xmax]¥[ymin,ymax] bounds listed in order:
(xmin,ymin),(xmax,ymin),(xmin,ymax),(xmax,ymax) }
array
[0..3]
of pnt2d
clipRegion;
pnt2d
startPt; { start point of segment }
integer
startC; { code for start point }
integer
startC0;{ saves startC for next call to CS_EndClip }
pnt2d
endPt; { endpoint of segment }
integer
endC;
{ code for endpoint }
integer
aC;
{ used by procedure TwoBitEndPoint }
Algorithm 3.3.4.2.
The Maillot polygon-clipping algorithm.
