Line Clipping

by John P Scott

Line Clipping

Introduction

Simple approach to clipping

The Sutherland - Cohen clipping algorithm

Intersection of a line with a horizontal or vertical boundary

Exercise

Introduction

When rendering a visual image it is sometimes necessary to cut off the display at some boundary to prevent the image from overlapping some other piece of display. Clipping is the name given to the process of limiting the visual representation of a graphical object to a certain region on the display.

Even in the simplest of graphical systems clipping is required. The screen itself has a limited display space (its pixel map), and so any aspects of an image requiring co-ordinates outside this space must be clipped. The simplest form of clipping is to a rectangular boundary (called a Viewport), parallel to the X and Y axes. Figure 1 shows this scenario.

Figure 1

Simple approach to clipping

The task is to be able to efficiently compute the visible portion of any line so that it can be drawn directly. You may think that the easiest approach is to replace the PutPixel procedure by one which decides whether the pixel is in the visible area. Figure 2 shows the code for this approach. We assume that XMin, XMax, YMin and YMax are constants defining the visible boundary.

PROCEDURE ClipPixel(X, Y, Colour: Integer);
BEGIN
IF (X >= XMin) AND (X <= XMax) AND
   (Y >= YMin) AND (Y <= YMax) THEN
  PutPixel(X, Y, Col)
END;

Figure 2
This method works; you simply replace the call to PutPixel in all your algorithms by a call to ClipPixel. However, this method means that the clipping process is being performed at Pixel level, and thus the performance of the pixel drawing process is being slowed down. It also means that the algorithm is being asked to compute pixels which may never be drawn. For example the line joining P1 and P2 in Figure 1 would have all possible pixels calculated, only to have them rejected at the drawing stage. An efficient algorithm will determine only that portion of the line which is visible before calling the line drawing algorithm. This way there is no reduction in efficiency of the line drawing process, but there is the computational expense of calculating the visible portion of the line. Notice that a point which is on the boundary of a viewport is considered to be visible; this is true for all aspects of graphics.

The Sutherland - Cohen clipping algorithm

This algorithm uses an iterative process to calculate where a line crosses the Viewport boundaries, but uses a simple test to ensure that simple cases such as lines which cannot be visible and lines which are already totally visible require the minimum of processing. Figure 3 shows the basic scenario for this algorithm.

Figure 3
The display space is broken into 9 regions, and each region has a code indicating its status. For example the region which P1 is in has the code (Above, Left). Any point in the display space can be given a code. Table 1 shows the codes for points P1 to P7.

   Point   Code
   P1      ( Above, Left )
   P2      ( Above )
   P3      (   )
   P4      ( Right )
   P5      ( Below )
   P6      ( Left )
   P7      (   )

Table 1
The line joining P1 to P2 is not visible, and the codes for the lines can be used to show this. The two codes have 'Above' in common, and so the line is totally 'above' the Viewport. In general, if the codes for the end points of a line have a code element in common then the line can be rejected as it is totally outside the Viewport.

The line joining P3 and P7 is completely inside the Viewport, and again the codes for the two points can be used to show this. The two codes are both empty, and so the line is totally within the Viewport.

In general, if the codes for the end points of a line are both empty then the line can be drawn immediately as it is totally within the Viewport.

Coding a point is straightforward and Figure 4 gives the code for the process.

TYPE
  TCodeElement = (Left, Above, Right, Below);
  TCode = SET OF TCodeElement;

PROCEDURE CodePoint(P: TPoint; VAR Code: TCode);
BEGIN
IF P.X < XMin THEN
  Code := [Left]
ELSE
  IF P.X > XMax THEN
    Code := [Right]
  ELSE
    Code := []; {Empty set}
IF P.Y < YMin THEN
  Code := Code + [Above]
ELSE
  IF P.Y > YMax THEN
    Code := Code + [Below]
END;

Figure 4
The check for a line to be rejected is given in Figure 5. Code1 and Code2 are the codes for the endpoints of the line.

IF Code1*Code2 <> [] THEN
  {Reject the line}
ELSE
  {Further processing required}

Figure 5
Once the initial coding has been done the algorithm attempts to determine points at which the line cross the Viewport boundaries. For example the lines from P2 to P6 and P4 to P5 in Figure 3 both have similar code properties, but it is obvious from the drawing that one of the lines is not visible and the other has a portion which is visible.

There is no way to distinguish between the two cases without doing a further calculation.

The line from P2 to P6 must cross the above boundary and the left boundary. The line from P4 to P5 must cross the right boundary and the below boundary. The next stage of the algorithm calculates the boundary crossings for the endpoints and uses them to refine the line towards just is visible portion (if any).

For example, using the line from P2 to P6, P2 has the code (above) and so if we calculate where the line crosses the above boundary and replace point P2 by the crossing point, we have new line whose codes can be checked and the process continued. In this case the new point P2', has the code ( ). This means that the line now only crosses the left boundary (coming from P6). If we calculate the left boundary crossing and replace point P6 by the new point P6', we now have a point whose code is ( ) . Now both endpoints have the code ( ) and so the whole of the line from P2' to P6' is visible and can be drawn. Now let us look at the line from P4 to P5. P4 has the code ( right ) and so we calculate where the line crosses the right boundary. If we replace P4 by the new point P4', we see that this end point now has the code (below). The line now has both endpoints below, and so the algorithm can now reject the line completely.

Figure 6 gives the pseudo code for the solution to the algorithm. The following section shows how to compute the crossing point for a line crossing a horizontal or vertical boundary.

PROCEDURE ClipLine(P1, P2: TPoint);
VAR
  Code1, Code2: TCode;
BEGIN
CodePoint(P1, Code1);
CodePoint(P2, Code2);
WHILE  (Code1*Code2 = []) AND
       ((Code1 <> []) OR (Code2 <> []) DO
  BEGIN
  IF Code1 <> [] THEN
    BEGIN
         CalculateABoundaryCrossingForP1;
    ReplaceP1ByNewPoint;
    CodePoint(P1, Code1)
    END
  ELSE
    BEGIN
    CalculateABoundaryCrossingForP2;
    ReplaceP2ByNewPoint;
    CodePoint(P2, Code2)
    END
  END
IF (Code1 = []) AND (Code2 = []) THEN
  DrawLine(P1, P2)
END;

Figure 6

Intersection of a line with a horizontal or vertical boundary

The solution can be expressed mathematically using the principle of similar triangles. Figure 7 shows the basic relationship. Prev Page

Figure 7
From Figure 7 we can see that the point P (co-ordinate (X, Y)) lies on a horizontal and vertical boundary. The equation for the relationship is:

If we wish to determine the horizontal boundary crossing, we actually know the Y value (it is either YMin or YMax, depending on which horizontal boundary we are looking at) and so we can solve the equation for X:

If we wish to determine the vertical boundary crossing, we actually know the X value (it is either XMin or XMax, depending on which vertical boundary we are looking at) and so we can solve the equation for Y:

Notice that both equations have a multiplication and a division in them, and so require more complex processing than the line algorithm. However, the calculation can be optimised, and in the case of some systems there is a hardware/software function call provided to give the result of a multiply followed by a divide. For example, Microsoft Windows provides:

FUNCTION MulDiv(Number: Integer; Numerator: Integer;
                Denominator: Integer): Integer;

Exercise

1. Implement the Sutherland - Cohen clipping algorithm, using the mouse to input lines and clip them to a fixed viewport.

Copyright (C) 1995

JPS Graphics, **********************
All rights reserved

Comments to author: ********************