banks@utah-cs.UUCP (Michael J. Banks) (10/04/88)
I have need of an algorithm to clip 2-D lines to a rectangle.
All of the references I have been able to find give algorithms
for clipping lines in "world coordinates" and rely on floating
point numbers.
Can anyone direct me to an efficient integer algorithm for
clipping lines to rectangles?
mike.
banks@cs.utah.edu (ARPA)
{ihnp4,decvax}!utah-cs!banks (UUCP)erik@cadnetix.COM (Erik Hyypia) (10/04/88)
In article <5760@utah-cs.UUCP> banks@utah-cs.UUCP (Michael J. Banks) writes: >I have need of an algorithm to clip 2-D lines to a rectangle. >All of the references I have been able to find give algorithms >for clipping lines in "world coordinates" and rely on floating >point numbers. > >Can anyone direct me to an efficient integer algorithm for >clipping lines to rectangles? Try the Cohen/Sutherland clipping algorithm, described in Principles of Interactive Computer Graphics, by Newman and Sproull, McGraw Hill. It is efficient at finding intersection points of lines which cross the rectangle boundries, and also at trivially rejecting lines which are wholly outside the clip region (good for operations like zooming in, where the majority of lines are rejected). We successfully implemented an integer version of this algorithm. (Corporate info, can't post it). Good luck, erik@cadnetix.COM (Erik Hyypia) <standard disclaimer, blah, blah>
sa@ttidca.TTI.COM (Steve Alter) (10/06/88)
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.
hst@mhres.mh.nl (Klaas Hemstra) (10/06/88)
Included is the source of a clip_line routine I wroten recently. The coordinates may be "int"egers or "long"s, and both positive and negative. Also the ranges to clip the coordinates in can be in the negative range of an int or long. I hope this is useful to you and maybe to others too, Klaas Hemstra File: clip_line.c --------------------------------------------------------------------------- /* This file contains routines to clip a line into a specified border */ /* */ /* Made By K.Hemstra it's in the Public Domain Use at your own risk */ /* All computations are done with integer arithmetic. /* The only restrictions are that the border to clip the line into can not */ /* have a height or width larger then the square root of the largest long, */ /* and for a line (x1,y1) - (x2,y2) to clip: abs(x2 - x1) * abs(y2 - y1), */ /* may not exceed the largest long. */ /* So for C-implementations with int = 16 bits and long = 32 bits the */ /* largest "clip"-box can be 32767x32767 coordinates. */ /* The border is defined by the two points (minx,miny) and (maxx,maxy) */ /* All comment if based on the following graph */ /* Above the border (minx,miny) *--------------------------* | | Left of the border | Within the border | Right of the border | | *--------------------------* (maxx,maxy) Below the border */ #typedef int COOR /* COORdinate type: This can be int or long. The routine will work ok in both cases. However it is best too choose "int" if the coordinates allow it, because "int"s are faster on some machines, specially 16-bits like MS-DOS. Note: For Turbo-C the #typedef will not work. Use "#define COOR int" instead, it works fine. */ COOR minx = 0,maxx = 719; /* initialized to hercules screen */ COOR miny = 0,maxy = 347; COOR imaxx = 719,imaxy = 347; /* This routine is should be called to initialize the border The clip_line routine will "clip" the line into (x1,y1) - (x2,y2) */ int set_clip_borders(x1,y1,x2,y2) COOR x1,y1,x2,y2; { minx = x1, miny = y1, maxx = x2, maxy = y2; imaxx = maxx - minx; imaxy = maxy - miny; } /* The clip_line routine */ int clip_line(x1,y1,x2,y2) COOR x1,y1,x2,y2; { if (clip_coordinates(&x1,&y1,&x2,&y2) != 0) { /* Here the machine specific line drawing routine is called */ draw_line(x1,y1,x2,y2); } } /* The clip_coordinates routine must be called with four addresses to COORdinates. These COORdinates are changed to fall into the range (minx,miny) - (maxx,maxy) If the line will not be within the defined border the returned integer value will be 1. */ int clip_coordinates(ix1,iy1,ix2,iy2) COOR *ix1,*iy1,*ix2,*iy2; { COOR x1,y1,x2,y2; long dx,dy,temp; long signdy; if (ix2 < ix1) /* Always make (x1,y1) the most left point */ x1 = *ix2 -minx, y1 = *iy2 -miny, x2 = *ix1 -minx, y2 = *iy1 -miny; else x1 = *ix1 -minx, y1 = *iy1 -miny, x2 = *ix2 -minx, y2 = *iy2 -miny; /* Now the coordinates x1,y1,x2,y2 are relatife to (0,0) */ /* which is the upper left corner of the border */ /* If line is completely left or right of the border */ if ((x2 < 0) || (x1 > imaxx)) return 1; /* If line is completely above or below the border */ if (((y1 < 0) && (y2 < 0)) || ((y1 > imaxy) && (y2 > imaxy))) return 1; /* Ok , the line is (maybe partly) in the border, work to do */ /* Ok, The line is partly above or below border (or both) */ dx = (x2 - x1); /* Distance between two x values */ dy = abs(y2 - y1); /* Distance between two y values */ signdy = (((y2 - y1) < 0) ? -1 : 1); /* sign of y2-y1 */ /* If y1 lies above border then correct */ if (y1 < 0) { x1 += ((long)dx * (long)(- y1)) / (long) dy; y1 = 0; } /* If y1 lies below border then correct */ if (y1 > imaxy) { x1 += ((long)dx * (long)(y1 - imaxy)) / (long) dy; y1 = imaxy; } /* If y2 lies above border then correct */ if (y2 < 0) { x2 -= ((long)dx * (long)(- y2)) / (long) dy; y2 = 0; } /* If y1 lies below border then correct */ if (y2 > imaxy) { x2 -= ((long)dx * (long)(y2 - imaxy)) / (long) dy; y2 = imaxy; } /* If x1 lies left of border then correct */ if (x1 < 0) { y1 += signdy * (((long)dy * (long)(- x1)) / (long) dx); x1 = 0; } /* If x2 lies right of border then correct */ if (x2 > imaxx) { y2 -= signdy * (((long)dy * (long)(x2 - imaxx)) / (long) dx); x2 = imaxx; } /* If line now is completely above or below the border */ if ((y1 < 0) || (y2 < 0) || (y1 > imaxy) || (y2 > imaxy)) return 1; *ix1 = x1+minx, *iy1 = y1+miny, *ix2 = x2+minx, *iy2 = y2+miny; return 0; } ----------------------------------End of file clip_line.c -- Klaas Hemstra (hst@mh.nl) | / / ,~~~ ~~/~~ uucp: ..{uunet!}mcvax!mh.nl!hst | /--/ `-, / ___ |_/ |__| Multihouse N.V., Gouda, the Netherlands | / / ___/ / --- | \ | |