Path: utzoo!utgpu!water!watmath!clyde!att!osu-cis!tut.cis.ohio-state.edu!mailrus!ames!amdahl!pyramid!prls!philabs!ttidca!sa
From: sa@ttidca.TTI.COM (Steve Alter)
Newsgroups: comp.graphics
Subject: Re: 2-D clipping
Keywords: integer algorithms
Message-ID: <3260@ttidca.TTI.COM>
Date: 5 Oct 88 21:22:17 GMT
References: <5760@utah-cs.UUCP>
Organization: Citicorp/TTI, Santa Monica
Lines: 181

In article <5760@utah-cs.UUCP> banks@utah-cs.UUCP (Michael J. Banks) writes:
} Can anyone direct me to an efficient integer algorithm for
} clipping lines to rectangles?

The following was written in Turbo Pascal 4.0 for IBM PC but should be
easily convertable to any other structured language.  What's actually
included below is the clipping routine plus an program that I used to
display an impressive test of the routine.

There is some floating point in the clipping routine (variables DX and
DY,) but that's only because the value wouldn't fit into an integer.
A long-integer would probably work just as well.

The algorithm was obtained from a college graphics course
(California State University, Northridge, course COMP 465.)

Procedure ClipLine takes the x and y coordinates of both endpoints of
a line, clips them to the rectangle specified by ClipLeft, ClipRight,
ClipTop and ClipBottom, then returns the new endpoints of the line in
the same four variables; they must be passed by reference (in C,
that's done by passing a pointer to the variables.)  The routine also
returns a boolean value that indicates whether or not *any* portion of
the line lies within the clipping rectangle.  If it comes back false,
there is nothing of that line to draw and the four coordinates come
back with garbage values.

The following describe the Pascal routines needed by the program
(shouldn't be too difficult to port)

	SetColor(n)		obvious
	Line(x1,y1, x2,y2)	obvious
	GetMaxX			function returns highest x-coordinate
	GetMaxY			function returns highest y-coordinate
	Round			round a float to nearest integer
	Rectangle(x1,y1, x2,y2)	obvious
	Readln			read a line of input but don't put it anywhere
				  (I use it as a "Type RETURN to continue")
	InitGraph               switch into specified graphics mode
	DirectVideo             esoterica related to displaying text on screen
				  (This one's a variable, not a routine)
	RestoreCrtMode		switch back to text display mode

Here's the principle behind this test program:

One way to test a clipping routine is to draw the full line in one
color and then draw the same line, after clipping, in another color on
top of the first one.  Do this for a *whole* *bunch* of different
lines and you should see a rectangle start to show itself.  This
rectangle will be in the second color, will be set against a
background of the first color, and the rectangle *is* the clipping
rectangle.  You've got to make sure that most or all of the tested
lines overlap at least one of the rectangle's borders to really give
the clipping routine a workout.

-- Steve Alter
...!{csun,psivax,pyramid,quad1,rdlvax,retix}!ttidca!alter  or  alter@tti.com
Citicorp/TTI, Santa Monica CA  (213) 452-9191 x2541
-----------------------------------------------------------------------------
PROGRAM TestClipLine;

USES Crt, Graph;

VAR
  ClipLeft, ClipRight, ClipTop, ClipBottom: Integer;

PROCEDURE ClipLine (VAR X1,Y1, X2,Y2: Integer; VAR Drawable: Boolean);
  CONST
    ToLeft = 1;  ToRight = 2;
    ToUp   = 4;  ToDown  = 8;

  FUNCTION Code (X,Y: Integer): Integer;
    VAR
      C: Integer;
    BEGIN
      C := 0;
      IF X < ClipLeft THEN C := ToLeft
      ELSE IF X > ClipRight THEN C := ToRight;
      IF Y < ClipTop THEN C := C OR ToUp
      ELSE IF Y > ClipBottom THEN C := C OR ToDown;
      Code := C;
    END;  (* Code *)

  VAR
    C1,C2,C, X,Y: Integer;
    DX,DY: Real;

  BEGIN  (* ClipLine *)
    C1 := Code(X1,Y1);  C2 := Code(X2,Y2);
    Drawable := True;
    WHILE Drawable AND ((C1 <> 0) OR (C2 <> 0)) DO
      IF (C1 AND C2) <> 0 THEN
        Drawable := False
      ELSE
        BEGIN
          IF C1 <> 0 THEN C := C1 ELSE C := C2;
          DX := X2-X1;  DY := Y2-Y1;
          IF (C AND ToLeft) <> 0 THEN
            BEGIN  { Crosses left edge }
              Y := Round(Y1 + DY*(ClipLeft-X1)/DX);
              X := ClipLeft;
            END
          ELSE IF (C AND ToRight) <> 0 THEN
            BEGIN  { Crosses right edge }
              Y := Round(Y1 + DY*(ClipRight-X1)/DX);
              X := ClipRight;
            END
          ELSE IF (C AND ToUp) <> 0 THEN
            BEGIN  { Crosses top edge }
              X := Round(X1 + DX*(ClipTop-Y1)/DY);
              Y := ClipTop;
            END
          ELSE IF (C AND ToDown) <> 0 THEN
            BEGIN  { Crosses bottom edge }
              X := Round(X1 + DX*(ClipBottom-Y1)/DY);
              Y := ClipBottom;
            END;
          IF C = C1 THEN
            BEGIN
              X1 := X; Y1 := Y; C1 := Code(X,Y);
            END
          ELSE
            BEGIN
              X2 := X; Y2 := Y; C2 := Code(X,Y);
            END;
        END;
  END;  (* ClipLine *)

PROCEDURE TestClipLine;
  PROCEDURE ClippedDraw (X1,Y1, X2,Y2: Integer);
    VAR
      Drawable: Boolean;
    BEGIN
      SetColor(3);
      Line(X1,Y1, X2,Y2);
      SetColor(1);
      ClipLine(X1,Y1, X2,Y2, Drawable);
      IF Drawable THEN
        Line(X1,Y1, X2,Y2);
    END;  (* ClippedDraw *)
  CONST
    Steps = 20;
  VAR
    I: Integer;
    X1,Y1, X2,Y2: Real;
  BEGIN
    ClipLeft := 100;  ClipRight := GetMaxX - 100;
    ClipTop := 80;    ClipBottom := GetMaxY - 80;
    X1 := 40;  X2 := GetMaxX - 120;
    Y1 := 40;  Y2 := GetMaxY - 100;
    FOR I := 0 TO Steps DO
      ClippedDraw(Round(X1),Round(Y1), Round(X2),Round(Y1+(Y2-Y1)*I/Steps));
    FOR I := 0 TO Steps DO
      ClippedDraw(Round(X1),Round(Y1), Round(X2-(X2-X1)*I/Steps),Round(Y2));
    FOR I := 0 TO Steps DO
      ClippedDraw(Round(X1),Round(Y2), Round(X1+(X2-X1)*I/Steps),Round(Y1));
    FOR I := 0 TO Steps DO
      ClippedDraw(Round(X1),Round(Y2), Round(X2),Round(Y1+(Y2-Y1)*I/Steps));
    FOR I := 0 TO Steps DO
      ClippedDraw(Round(X2),Round(Y2), Round(X1),Round(Y2-(Y2-Y1)*I/Steps));
    FOR I := 0 TO Steps DO
      ClippedDraw(Round(X2),Round(Y2), Round(X1+(X2-X1)*I/Steps),Round(Y1));
    FOR I := 0 TO Steps DO
      ClippedDraw(Round(X2),Round(Y1), Round(X2-(X2-X1)*I/Steps),Round(Y2));
    FOR I := 0 TO Steps DO
      ClippedDraw(Round(X2),Round(Y1), Round(X1),Round(Y2-(Y2-Y1)*I/Steps));
    SetColor(2); Rectangle(ClipLeft-2, ClipTop-2, ClipRight+2, ClipBottom+2);
    SetColor(2); Rectangle(ClipLeft-1, ClipTop-1, ClipRight+1, ClipBottom+1);
    Readln;
  END;  (* TestClipLine *)

VAR
  Driver, Mode: Integer;

BEGIN
  Driver := EGA;
  Mode := EGAHi;
  InitGraph(Driver, Mode, '');
  DirectVideo := False;
  TestClipLine;
  RestoreCrtMode;
END.