Clipping - Computer Graphics and Geometric Modeling - page 80

Figure 3.7. Liang-Barsky line-clipping example.

3.2.4 Nicholl-Lee-Nicholl Line Clipping

One of the problems common to both the Cohen-Sutherland and the Liang-Barsky
algorithm is that more intersections are computed than necessary. For example, con-
sider Figure 3.6 again where we are clipping line segment [ P 1 , P 2 ] against the window.
The Cohen-Sutherland algorithm will compute the intersection of the segment with
the top boundary at t 4 even though the segment is later rejected. The Liang-Barsky
algorithm will actually compute all the parameter values corresponding to the inter-
section of the line with the window. Avoiding many of these wasted computations is
what the Nicholl-Lee-Nicholl line-clipping algorithm ([NiLN87]) is all about. These
authors also make a detailed analysis of the deficiencies of the Cohen-Sutherland and
Liang-Barsky algorithms. Their final algorithm is much faster than either of these. It
is not really much more complicated conceptually, but involves many cases. We
describe one basic case below.
Assume that we want to clip a segment [ P 1 , P 2 ] against a window. The determi-
nation of the exact edges, if any, that one needs to intersect, reduces, using symme-
try, to an analysis of the three possible positions of P 1 shown in Figure 3.8. The cases
are

(1) P 1 is in the window (Figure 3.8(a)),
(2) P 1 is in a “corner region” (Figure 3.8(b)), or
(3) P 1 is in an “edge region” (Figure 3.8(c)).

For each of these cases one determines the regions with the property that no matter
where in the region the second point P 2 is, the segment will have to be intersected
with the same boundaries of the window. These regions are also indicated in Figure
3.8. As one can see, these regions are determined by drawing the rays from P 1 through
the four corners of the window. The following abbreviations were used:

T - ray intersects top boundary LT - ray intersects left and top boundary

L - ray intersects left boundary LR - ray intersects left and right boundary

B - ray intersects bottom boundary LB - ray intersects left and bottom boundary

R - ray intersects right boundary TR - ray intersects top and right boundary

TB - ray intersects top and bottom boundary