Why always ask why?
Q: Why would ANYONE want to clip a line?
A: The correct response to this question is that they wouldn't. Clipping lines is a little like cutting hair. Nobody wants to do it, but the reality is that if you don't, you will soon be tripping over yourself and it won't be long before you crash face first into the ground. (End Metaphor and huge sentence)
Clipping a line is useful because if you don't, you will get line fragments showing up in places that you really would rather not have them. A line wrapping from the right edge of the screen to the left is an example, a more catastophic example is when you are double buffering and the line goes off the bottom of the screen. Hopefully, nothing important gets overwritten, but good old Murphy (of Murphy's laws) says that something VERY important will get destroyed. Because of this, we have to be careful about where we overwrite and how we do it.
In other words, we have to add a new structure and a new procedure:
In our implementation of this algorithm, we will have a byte for each endpoint of the line that holds the status of that point. We will use four bits of that byte, one for each possible state. These states are shown in green on the diagram (in binary). If the point is to the left of the clip area, then set bit #1. If the point is to the right of the clip area, then set bit #2. If the point is above the clip area, set bit #3. Finally, if the point is below the clip area, set bit #4. This ensures that if the point is inside of the clipping area the code is set to zero. If the point's code is above zero, then we have some clipping to do. Here is the code to generate status byte:
If we AND the two codes together, we find common sides of the box that the two points lie. If they both lie on the same side of the box, then a bit will still be set after the values are ANDed. For example with line F, the value 0101 AND 0001 = 0001. This means that the line is completely to the left of the bounding box and can be rejected.
Now we are correctly drawing a good portion of the lines. We just have to worry about lines like E, C, and D now. To handle lines like C and D, it is obvious that we have to clip the line somehow. Line E though, seems to be harder to classify. It turns out that if we apply the line clipping algorithm to line E and then test it again, it becomes a simple case. If we clip line E at point E1, then both points, when ANDed together will have the code of 0001... completely to the left. It can then be trivially rejected.
After all of this, we end up with a viewport that looks like the diagram on the right... Now we just need to discuss HOW lines are clipped.
First of all, the equation for a line is:
Where m is the slope and b is the Y-Intercept. In order to clip lines, we need to know both of these values. It is a good thing that they are easy to calculate! From a few articles back, you remember that m, the slope, is simply change in Y divided by the change in X:
b, the Y-Intercept, is calculated by rearranging the first equation slightly:
If we plug in values for X and Y (Either X1, Y1 or X2, Y2) and insert the equation for m in instead of m, then we get the following equation:
Okay, now we have all of the pieces of the equation... How do we put these to work for us? Well, there are two cases that we have to deal with: Clipping a line against a vertical line and clipping a line against a horizontal line. They are both the same equation, it is just that one has the X's swapped with the Y's.
The equation we want is one in which we can put a clipped X coordinate in and the corresponding Y coordinate will pop out. To do this, we plug our equation for m and for b into the first equation for Y:
Okay, okay... We're almost there! Here we can make a small mathematical optimization... combine the X and the X1 to remove a divide and a multiply... Finally, we get this:
So! To clip a point to a vertical line, we now just have to put the (X1, Y1)-(X2, Y2) coordinates of the line into this equation. Put the X value of the line into the equation and out pops the Y value... Presto!
We have two bytes, named OutCode0 and OutCode1, that hold the classifications of the endpoints. The first thing that happens is that they are evaluated and set to their appropriate values. Then a loop is entered. This loop continues until either the line falls within the clipping boundaries or it lies completely to one side of the boundaries. If it is all the way to one side, then it exits with this code:
With these lines:
Next, we clip the coordinate somehow. With these IF statements, we select a line to clip it against:
Okay, now we're to the point were we have a clipped point in a temporary variable. We just need to update the real variables and update the OutCode...
At this point, we simply loop back to the top with the updated coordinates and OutCode. If either of the points are still outside of the clipping boundary, then the process repeats itself until the line is entirely outside or entirely inside the box. Then, finally, the line is drawn (or not drawn).
We have our clipped line!
The kind of clipping that we are interrested in is not complex. We simply want to constrain the output of a line to a rectangle on the screen. Since the clipping box is something that doesn't change very much, it makes sense to make the box a globally available variable that is persistant between calls to the GraphPro routines...
TYPE
RectType = RECORD { A rectangle. }
X1, Y1, X2, Y2 : INTEGER;
END;
ScreenType = RECORD
Buffer : ScreenBufferPtr; { Pointer to the screen buffer }
DBuffer : BOOLEAN; { Are we in double buffer mode? }
YTable : ARRAY[0..199] OF WORD; { Y can range from 0 - 199 }
Width : WORD; { Width of the current screen }
Clip : RectType; { Current clipping boundaries }
END;
PROCEDURE SetClipBoundary(X1, Y1, X2, Y2 : INTEGER);
BEGIN
Screen.Clip.X1 := X1; Screen.Clip.Y1 := Y1; { Update global variables }
Screen.Clip.X2 := X2; Screen.Clip.Y2 := Y2;
END;
This is pretty simple stuff. Basically, we added a field to the ScreenType record that holds the dimensions of the clipping area. We also need a routine to copy variables from some source to the ScreenType record. This allows us a simple call to change all four extents of the clipping rectangle. For the full screen to be set as the clipping area for example, we would do this:
SetClipBoundary(0, 0, 319, 199);
This is nice and everything, but our routines will not magically start clipping themselves. To make use of these routines, we need to create some routines that take heed to the clipping boundaries.
The easiest primitive to clip is the single pixel. To check to see if it is inside of the bounds, we simply make sure that coordinates of the pixel fall within the boundaries of the clipping box. We require a statement that looks like this:
PROCEDURE SetPixelC(X, Y : INTEGER; Color : BYTE);
BEGIN
IF (X <= Screen.Clip.X2) AND (X >= Screen.Clip.X1) AND
(Y <= Screen.Clip.Y2) AND (Y >= Screen.Clip.Y1) THEN
SetPixel(X, Y, Color);
END;
This logic is easy to follow, and it converts into assembly very easily:
PROCEDURE SetPixelC(X, Y : INTEGER; Color : BYTE); ASSEMBLER;
ASM
mov CX, X
cmp CX, Screen.Clip.X1 { Clip the X coordinate }
jl @Clipped
cmp CX, Screen.Clip.X2
jg @Clipped
mov BX, Y
cmp BX, Screen.Clip.Y1 { Clip the Y coordinate }
jl @Clipped
cmp BX, Screen.Clip.Y2
jg @Clipped
push CX
push BX
push Color
call SetPixel { SetPixel(X, Y, Color) }
@Clipped:
END;
This works well. The only problem with it is the speed. Since a clipping routine has more work to do than the equivalent non-clipped routine, it will run slower. It doesn't have to run this slow though... Since the SetPixel routine is so short, it is much better if we replace the call to SetPixel with the actual code for SetPixel... This eliminates 3 pushes, a call, and a ret along with some other miscellaneous cycles:
PROCEDURE SetPixelC(X, Y : INTEGER; Color : BYTE); ASSEMBLER;
ASM
mov CX, X
cmp CX, Screen.Clip.X1 { Clip the X coordinate }
jl @Clipped
cmp CX, Screen.Clip.X2
jg @Clipped
mov BX, Y { Y is an index into the ScreenY array }
cmp BX, Screen.Clip.Y1 { Clip the Y coordinate }
jl @Clipped
cmp BX, Screen.Clip.Y2
jg @Clipped
les DI, Screen.Buffer
add DI, CX
add BX, BX { Multipy by two because each entry is a word }
add DI, DS:[BX+OFFSET Screen.YTable]
mov AL, Color
mov ES:[DI], AL
@Clipped:
END;
Because of the extra overhead required to check each coordinate against the clipping boundaries, this is about as fast as we can get it to go. From here, we travel on to clipping lines...
There are at least as many ways to clip a line as there are to skin a cat. All of the various ways have their individual merits and some are slightly faster than the one presented here. The Cohen-Sutherland line clipping algorithm is a standard algorithm used in many places. It is a fast, reliable, easy to understand routine. What else could you ask for?
As seen to the left, what we want to do is take the square viewport and clip the lines so that they fall inside of it. This can have a number of consequences. Lines such as A, F, and E should be ignored completely. Lines like B should be accepted with as little processing as possible. Lines like C and D though, need to be clipped before they can be drawn to the screen. The Cohen-Sutherland line clipping algorithm fills these requirements by classifying the endpoints of the line by which sector of the screen they fall into.
Code := 0;
IF X < Screen.Clip.X1 THEN Code := Code OR 1
ELSE IF X > Screen.Clip.X2 THEN Code := Code OR 2;
IF Y < Screen.Clip.Y1 THEN Code := Code OR 4
ELSE IF Y > Screen.Clip.Y2 THEN Code := Code OR 8;
This is simple enough (simple is good... good is fast!), but how do we decide which points to accept or reject? It turns out that for lines like B that are completely inside of the clipping box, it is simple to trivially accept the line. If both status bytes are zero, then the line is completely inside of the box. It is also simple to trivially reject lines like A and F that are outside of the window.
Here again, we get to talk about the famous equation for the line. We discussed this earlier, but a review won't hurt you... :)
How are we going to assemble all of this into a chunk of code now? Since the line routine is so long, we're going to make a routine that does all of the clipping and then calls the original line routine with the clipped coordinates. With our SetPixelC routine, it was profitable to insert all of the SetPixel code inline with the clipping code. Because the line clipping code is so much longer and the pixel clipping code though, the overhead of the call and the ret is insignifigant. Here is the LineC routine:
{ LineC - This procedure clips a line to the current clip boundaries and
then calls the Line procedure with the clipped coordinates. If the line
lies completely outside of the clip boundary, then the Line routine is not
called. This procedure uses the well known Cohen-Sutherland line clipping
algorithm to clip each coordinate. }
PROCEDURE LineC(X1, Y1, X2, Y2 : INTEGER; Color : BYTE);
CONST
CodeBottom = 1; CodeTop = 2; { BitFields for output codes }
CodeLeft = 4; CodeRight = 8;
FUNCTION CompOutCode(X, Y : INTEGER) : BYTE; { Nested function }
VAR Code : BYTE;
BEGIN
Code := 0;
IF Y > Screen.Clip.Y2 THEN Code := CodeBottom
ELSE IF Y < Screen.Clip.Y1 THEN Code := CodeTop;
IF X > Screen.Clip.X2 THEN Code := Code+CodeRight
ELSE IF X < Screen.Clip.X1 THEN Code := Code+CodeLeft;
CompOutCode := Code;
END;
VAR
OutCode0, { The code of the first endpoint }
OutCode1, { The code of the second endpoint }
OutCodeOut : BYTE;
X, Y : INTEGER;
BEGIN
OutCode0 := CompOutCode(X1, Y1); { Compute the original codes }
OutCode1 := CompOutCode(X2, Y2);
WHILE (OutCode0 <> 0) OR (OutCode1 <> 0) DO { While not Trivially Accepted }
BEGIN
IF (OutCode0 AND OutCode1) <> 0 THEN { Trivial Reject }
EXIT
ELSE
BEGIN { Failed both tests, so calculate the line segment to clip }
IF OutCode0 > 0 THEN
OutCodeOut := OutCode0 { Clip the first point }
ELSE
OutCodeOut := OutCode1; { Clip the last point }
IF (OutCodeOut AND CodeBottom) = CodeBottom THEN
BEGIN { Clip the line to the bottom of the viewport }
Y := Screen.Clip.Y2;
X := X1+LONGINT(X2-X1)*LONGINT(Y-Y1) DIV (Y2 - Y1);
END
ELSE IF (OutCodeOut AND CodeTop) = CodeTop THEN
BEGIN { Clip the line to the top of the viewport }
Y := Screen.Clip.Y1;
X := X1+LONGINT(X2-X1)*LONGINT(Y-Y1) DIV (Y2 - Y1);
END
ELSE IF (OutCodeOut AND CodeRight) = CodeRight THEN
BEGIN { Clip the line to the right edge of the viewport }
X := Screen.Clip.X2;
Y := Y1+LONGINT(Y2-Y1)*LONGINT(X-X1) DIV (X2-X1);
END
ELSE IF (OutCodeOut AND CodeLeft) = CodeLeft THEN
BEGIN { Clip the line to the left edge of the viewport }
X := Screen.Clip.X1;
Y := Y1+LONGINT(Y2-Y1)*LONGINT(X-X1) DIV (X2-X1);
END;
IF (OutCodeOut = OutCode0) THEN { Modify the first coordinate }
BEGIN
X1 := X; Y1 := Y; { Update temporary variables }
OutCode0 := CompOutCode(X1, Y1); { Recalculate the OutCode }
END
ELSE { Modify the second coordinate }
BEGIN
X2 := X; Y2 := Y; { Update temporary variables }
OutCode1 := CompOutCode(X2, Y2); { Recalculate the OutCode }
END;
END;
END;
Line(X1, Y1, X2, Y2, Color); { Draw the new line! }
END;
As you can see, this is a fairly long routine. We'll take it apart a little at a time to help explain it though. First of all, you see the familiar CompOutCode routine. This simply computes the Code for a coordinate. We covered this earlier.
IF (OutCode0 AND OutCode1) <> 0 THEN { Trivial Reject }
EXIT;
This piece of code does what we were talking about before: ANDing the two codes together. If a line is completely to one side of the bounding box, then it has no part that needs to be drawn and can be ignored. Because of this, we unceremoniously EXIT.
IF OutCode0 > 0 THEN
OutCodeOut := OutCode0 { Clip the first point }
ELSE
OutCodeOut := OutCode1; { Clip the last point }
we choose which point to mess with. If the first point is not inside of the bounding box yet, then it is chosen to be worked on. Otherwise, the second point is chosen. The variables X, Y, and OutCodeOut are working copies of the variables being modified. Because the previous chunk of code could select either coordinate to work on, we use these and assign them to the real variables later.
IF (OutCodeOut AND CodeBottom) = CodeBottom THEN
ELSE IF (OutCodeOut AND CodeTop) = CodeTop THEN
ELSE IF (OutCodeOut AND CodeRight) = CodeRight THEN
ELSE IF (OutCodeOut AND CodeLeft) = CodeLeft THEN
Here we just test the bit that corresponds to the side that needs to be clipped. When we find the part that needs to be clipped, then we perform the calculation on it (derived above). The results of the operation are assigned to the temporary X and Y variables.
IF (OutCodeOut = OutCode0) THEN { Modify the first coordinate }
BEGIN
X1 := X; Y1 := Y; { Update temporary variables }
OutCode0 := CompOutCode(X1, Y1); { Recalculate the OutCode }
END
ELSE { Modify the second coordinate }
BEGIN
X2 := X; Y2 := Y; { Update temporary variables }
OutCode1 := CompOutCode(X2, Y2); { Recalculate the OutCode }
END;
Note: At no time should the OutCode0 = OutCode1. If they did, the line would be trivially rejected when they were ANDed together. Because of this, the OutCodes become a good way to be able to tell the points apart from each other.
Example program time! This is just a short little program that demonstrates line clipping by setting the clip boundary to show lines being clipped. It generates random lines and draws them with both the nonclipping line procedure and the clipping line procedure (In a different color, of course). This shows where it clips... Notice that no light grey pixels ever appear outside of the white box.... :)
PROGRAM LineClippingExample;
USES GraphPro, CRT;
VAR
X1, Y1, X2, Y2 : INTEGER;
Font : FontType;
BEGIN
Randomize;
InitGraph; { Initialize the graphics }
LoadBIOSFont(Font, 16); { Get a 16 point font }
SetClipBoundary(80, 50, 240, 150); { Set the clipping boundary }
Line(80, 50, 240, 50, 15); { Draw the clipping boundary }
Line(80, 50, 80, 150, 15);
Line(240, 50, 240, 150, 15);
Line(80, 150, 240, 150, 15);
WriteG1(Font, 1, 1, 'Press any key to continue or ESC to quit', 7);
WriteG1(Font, 0, 0, 'Press any key to continue or ESC to quit', 15);
REPEAT
X1 := Random(320); Y1 := Random(200); { Generate random lines }
X2 := Random(320); Y2 := Random(200);
Line(X1, Y1, X2, Y2, 8); { Draw the line without clipping }
Linec(X1, Y1, X2, Y2, 7); { Draw the line with clipping }
UNTIL ReadKey = #27;
CloseGraph; { Deinit graphics }
END.