Victor is a graduate student in electrical and computer engineering with a minor in computer graphics at North Carolina State University. He previously worked as a consultant at Silicon Engineering in Santa Cruz, Calif., and as an IC designer at Intel. He can be reached at 1001 Japonica Court, Knightdale, NC 27545.
Over the past few years, windowing environments have become enormously popular. Intuitive graphical interfaces with pop-up menus are now expected of commercial software; successful products such as Apple's Macintosh, X Windows, and Microsoft Windows are thriving because they provide these features.
Windowing doesn't come for free, however. Many sophisticated algorithms are behind the creation of the illusion called a window. In this article I'll discuss clipping, one of the key algorithms, by examining Cohen-Sutherland's classic clipping algorithm and then implement -- and optimize -- it in C. The resulting algorithm will clip about 55 percent more lines per second than Cohen-Sutherland's original algorithm.
As it applies to computer graphics, "clipping" is a process of removing that portion of an object that cannot be seen through a bounding region (that is, a "window"). See Figure 1. Examples of clipping can be found everywhere in everyday life. If you look through the physical window of your house, for instance, you see only a small portion of the outside world. To create the same effect on a computer, decisions must be made as to which portion of the world is to be displayed and which is to be discarded (because the wall that surrounds the physical window conceals that portion of the world). Clipping is the process of removing the portion of the world that cannot be seen.
In computer-aided design (CAD) and other computer graphics applications, very large and complex databases are often created and manipulated. The space shuttle is one such example. When working on a tail section of a project like the space shuttle, engineers don't necessarily want to see the entire space shuttle on the screen. Consequently, the CAD program must be capable of cutting away, or clipping, the undesired sections of the shuttle while displaying only the tail section (appropriately scaled) on the screen.
Because the general topic of clipping is much too broad to cover in a single article, I'll focus on the clipping of line segments that are displayed in a rectangular window that is parallel to the display device axes. This covers most of the present windowing systems that use rectangular windows aligned with the monitor screen. Also, a very large class of physical objects can be drawn with lines.
To be able to manipulate line segments, you must first understand everything about them. How are line segments different from lines? How are lines and line segments described? How are line segments shortened or lengthened? I'll answer these questions in this section.
A "line," in analytic geometry, is a graph of a linear equation Ax + By + C = 0 where A, B are not zero. A line can also be described mathematically as shown in Table 1.2
Slope y-intercept form: y = mx + b Point-slope form: y-y1 = m * (x-x1) Two-point form: (y-y1)/(x-x1) = (y2-y1)/(x2-x1)
Note that the right side of the two-point form is the slope (m), making the two-point form equivalent to the point-slope form. There are several other ways to describe a line, but they are not as useful to this discussion. For our purposes, a line is a set of all points with coordinates (x,y) that satisfy a line equation (see Figure 2 ). A line extends infinitely and contains an infinite number of points. This infinity stuff is very troublesome, however. To draw an infinite number of points in a line would take infinitely long, no matter how quickly each point is drawn. Also, there are not many physical objects that contain lines of infinite length. In fact, any such object would have to be infinitely large.
A finite portion of a line is much more useful when dealing with realistic physical objects. Somehow, the boundaries of this finite portion, or segment, of a line must be specified. One convenient way to specify these boundaries is by using two points to indicate the end points of that line segment, and then by using the two-point form line equation. Therefore, a line segment is a set all points on a line between the end of points of that line segment (see Figure 3). There are other ways to define a line segment that are convenient to other applications.
Clipping shortens the line segment. To accomplish clipping, one or both end points of the line segment must be modified. New end points must then be calculated. These new end points must satisfy the line equation in that they must lie on the original line and be within the boundaries of the original line segment (again, see Figure 3 ). For example, if as in Figure 4 a line segment intersects X_RIGHT (the right window boundary), only the section P1-A should be displayed. The section A-P0 should be discarded. To accomplish this, point A must replace point P0 as the end point of the line segment. Somehow, the X and Y coordinates of point A must be computed.
The X-coordinate of the intersection point must be X_RIGHT, since the P0-P1 line segment intersects the right side of the window (whose line equation is x = X_RIGHT). Only the Y-coordinate is left to be determined. This can be done by solving the two-point form line equation for Y, and substituting X_RIGHT for X in that equation. The resulting equation (shown in Figure 4) is manageable and can be computed quickly. The result is a new end point of a shorter, clipped, line segment. This simple method can be extended to clip lines to the four boundaries of a rectangular window.
A straightforward way to perform line clipping is to find an intersection between the line to be clipped and every boundary of the window and to make sure that the intersection points are within the window limits. If the intersection points are all outside the window limits, then the line can be thrown away. In other words, you must choose the new end points very carefully -- between the "best" intersection points and the end points of the original line. This method would require an intersection calculation for all four window boundaries. But is this amount of computation really necessary? Couldn't conclusions be made as each intersection point (up to four of them) is found, to speed up the process? That is precisely what the Cohen-Sutherland algorithm does. The algorithm decides the fate of the line after an intersection with a single window boundary has been determined: it does this up to four times.
The Cohen-Sutherland line clipping algorithm, introduced in 1968, is powerful, simple, and compact. The first adaptation of the algorithm, implemented in C, is shown in Listing One (page 98). This version corresponds to the implementations that are found in literature (see endnotes 3, 4, 7, and 9). An "improved" version of the algorithm is shown in Listing Two (page 98). I will thoroughly explain the code shortly but, first, the method.
Cohen and Sutherland thought of the window boundaries as lines, not line segments. If these window boundaries were extended (lines are of infinite length), the world would be partitioned into nine regions that can be thought of as being within, above, below, to the right, or to the left of the window (see Figure 5). Each region can then be given a unique identifier, an outcode/ number. This identifier would be more useful if there were some logic behind it, especially if it allowed for quick rejection of line segments that are completely outside the window, or for quick acceptance of line segments that are completely within the window. Cohen and Sutherland suggested the following scheme:
Procedure clip_2d_cs is the main procedure of the algorithm. It is called to perform the actual clipping (read the comments for details about the calling conventions). Note the two integer variables, outcode0 and outcode1. These will be assigned to each end point, and will indicate which region an end point lies in.
The algorithm consists of a while loop, which is executed up to four times. The first step in the algorithm is to identify in which of the nine regions an end point of the line segment lies and to assign an appropriate outcode to it. For example, if an end point lies in a region that is above and to the left of the window, an outcode 1001 is assigned to it. This is exactly what the procedure outcodes does. Both end points of the line segment get outcodes assigned to them.
Two quick decisions can now be made about the line based on the outcodes. First, a line can be trivially rejected in four cases: If both end points are above the window; if both end points are below the window, if both end points are to the left of the window; and if both end points are to the right of the window. In these cases the line should not be drawn at all, as it lies completely outside the window. An easy and quick way to check for these four conditions is to perform the logical AND of the end point outcodes (see procedure reject_check). For example, if both end points are above the window, both outcodes will have Bit 0 set to a 1. A logical AND will produce a 1 in Bit 0, and the line is rejected.
The second decision that can be made quickly is the trivial acceptance if both end points are within the window. In this case, the outcodes of both end points will be 0000. The procedure accept_check checks both outcodes and accepts the line if both outcodes are 0000.
At this point the trivial cases have been taken care of, and the more complicated cases must be dealt with. Cohen and Sutherland took the divide-and-conquer approach to the problem. A series of simple adjustments, up to four, is made, and the line is checked for trivial rejection or acceptance after each adjustment. The simple adjustments are exactly like the one demonstrated in Figure 4. Basically, a line is shortened with respect to a single window bound ary during each iteration. After up to four iterations, because there are four window boundaries, the line segment has been clipped.
The best way to explain the algorithm is to walk through an example. In Figure 7 the progress of the clipping algorithm is shown one iteration at a time. Line segment end points are first encoded with outcodes. This line segment can't be trivially accepted because both end points are not within the window boundaries (both outcodes are not 0000). This line segment can't be trivially rejected either, because the logical AND of the end point outcodes is 0000. The algorithm then starts operating on P0 end point, because this end point is outside the window boundaries: Its outcode is not 0000. Because Bit 0 is set in the outcode of P0, P0 must be above the top window boundary. P0 can be moved to the intersection of the line segment with the line drawn through the top window boundary. This point will still be on the line segment and will be a bit closer to the window. This action eliminated the section of the line segment that was above the top window boundary and, therefore, could not possibly be seen through the window. The Y coordinate of the new end point is already known: Y_TOP (the top boundary of the window). The only calculation that remains is to compute the X coordinate. This is done by the method similar to that shown in Figure 4, only solving the equation for X, because it -- not Y -- is the unknown. The code for this is in the clip_2D_cs inside the if (outcode0 & 1) statement.
Next, because the end points have been moved, they are given new outcodes. Then the new line segment is checked once again for trivial rejection or acceptance. The outcode of P0 shows that P0 is to the right of the window. Therefore, P0 can be moved to the intersection of the right window boundary and the line segment. This action will cause the section of the line segment that is to the right of the window to be discarded (shown in step 2). The X coordinate of this intersection is known, but not the Y, so the algorithm calculates the Y coordinate.
Now that you understand the algorithm, I'll introduce several modifications to boost the algorithm performance. These modifications are shown in Listing Two. Benchmarks are summarized in the next section.
The first modification is to calculate the slope and the inverse slope only once. This modification comes from a simple idea -- the slope of a line before clipping should be equal to the slope of a line after it has been clipped.
The implementation is just as simple as the concept itself. After the first trivial rejection or acceptance has been completed, and failed, the calculation of the slope is inevitable. For half of the cases the slope must be calculated; for the other half the inverse of the slope must be calculated. That's right, if a line can be broken up, or subdivided, at the top or the bottom of the window, then the Y coordinate of the intersection is known and X must be computed. Therefore, in this case the inverse of the slope must be computed. If, however, a line can be subdivided at the left or right of the window, the slope must be calculated.
If you look at the code in Listing One, you will notice that all computations of *y0 or *x0 involve very similar calculations. In fact, all of them compute (*x1 - *x0) and (*y1 - *y0). Realizing that the result of these two computations will be used only in the slope or inverse slope calculations, which do not change, leads to the conclusion that these values need be computed only once. That is what you see in Listing Two. Two variables have been added, dx and dy, and these are computed only once.
A perfectly reasonable question to ask at this point is, "If we calculated the slope, can the inverse be quickly determined by dividing a one by the slope?" Ah, but there is a problem with this method. Remember the trouble with division by zero -- it leads to an answer that computers just can't deal with. In fact, Hearn and Baker4 missed this point in their implementation of the Cohen-Sutherland algorithm. Their implementation will not work for vertical lines. I hope this serves as sufficient warning for programmers everywhere -- check even the most trivial of cases!
The Cohen-Sutherland algorithm carefully avoids division by zero by calculating the slope inside the if statements. For example, if a line needs to be subdivided at the top of the window, that line cannot be horizontal. If it were, it would have been either trivially rejected or accepted, or it would be impossible for its outcodes to require subdivision at the top of the window. Also, wouldn't it be a bit difficult to subdivide a horizontal line at the top or the bottom of the window to begin with? The line is parallel to the top and bottom boundary (there is no intersection point).
The second speed improvement comes from several sources (see references 6, 3, and 7). Exercise 4.2 in Fundamentals of Interactive Computer Graphics contains a suggestion to encode only P0, the modified end point. This modification has the most dramatic speed improvement on the algorithm. It reduces the number of floating-point comparisons almost in half. Bravo!
This concept can be taken one step further by optimization fanatics like myself. After a line has been subdivided once, only 3 bits are needed for the outcodes. So, only three of the four boundary comparisons are needed. For example, if a line has just been subdivided at the top of the window, there is no need to compare that end point with the top of the window again. You can be assured that the new end point will not be above the window, because we just discarded that portion of the line. Therefore, the comparison with the top window boundary can be eliminated. This reduces the number of comparisons a bit more, but makes the code not quite as elegant as it once was. Well, performance versus elegance has its trade-offs....
The next improvement can be made by noticing another physical property. If a line is being clipped at the top boundary, it is physically impossible for the new top end point to be below the bottom boundary. In other words, the end point that was above the window can move only to one of the three middle regions (0001, 0000, 0010). It will never move below the window, so why check it? Therefore, we can remove yet another floating-point comparison. Now, if the line is being subdivided at the top or the bottom boundary, we need to check against and encode only the right and left boundary. And, if the line is being subdivided at the right or left boundary, we need to check against and encode only the top and bottom boundary.
Now, the number of comparisons, after the initial encoding, has been cut in half. Not bad. But is it possible to do more? Yes, of course. The last improvement is even more dramatic than any of the previous ones. This speed improvement comes from the physical properties described earlier as well. If you look at Figure 6 once again, you will notice that only 2 out of the possible 4 bits are ever set for any region. Why, then, should we do four comparisons? Couldn't we stop after the first 2 bits have been set, and not do the other 2 bits? Yes, we could definitely do that. For example, if we found that an end point is located above the window, we no longer have to check the region below the window. The same holds for left and right regions. This is the reasoning behind all of those mysterious if/else statements in the OUTCODES macro and in the body of the main loop. In the best case, only two floating-point comparisons are made. In the worst, still four are needed? The number of comparisons drops dramatically, especially for the trivial rejection case, from eight to four. Note, that trivial acceptance doesn't benefit at all. Newmann and Sproull6 used this technique in their implementation of the OUTCODES subroutine.
As promised, I pulled all of the C tricks from my bag of tricks. I converted the outcodes and swap_pts procedures to OUTCODES and SWAP_PTS macros. This eliminated stack data movement, resulting in further speed improvement. Therefore, the final routine does no procedure calls, and no parameter passing, at all. I had to add a couple of temporary variables that swap procedure used, however, to store the values during swapping.
There are several other small optimization steps that can be taken even further. You could calculate the slope (dy/dx) and then set a flag to indicate that the slope has already been computed. Then, if the need arises to use the slope in another if statement, that calculation can be avoided. This yields very small performance improvement. It would be beneficial for hardware implementations of the algorithm, however.
I used the Microsoft C, Version 5.0, compiler and set all performance enhancing switches that I could find, -Ox-FPi87. I set the -FPi87 switch, because I'm fortunate enough to have an 80287 math coprocessor in my 8 MHz, 1 wait state PC/AT. I also used the -W2 switch, requesting the compiler to find any stupid mistakes that I often make.
To compare the algorithms against one another I wrote a fairly involved, and long, program that will be available through the DDJ Forum or on CompuServe. For details see info at the end of this article. This program allows a large database of lines, specified by two end points in three dimensions, to be loaded from a disk file. Then, the user is able to choose from a menu of several line clipping algorithms. The program takes a time stamp before the clipping algorithm is run on the database and when the clipping has been completed. The time difference is then displayed on the screen. The user can run the chosen clipping algorithm as many times as they wish for improved timing accuracy. The window size can be easily modified, and the database can be rotated, scaled, and translated for added flexibility.
To generate the database of line end points, I wrote a short program, shown in Listing Three (page 100), that generates random end points in three dimensions. Yes, I realize that random data is not exactly the best way of benchmarking an algorithm, but I haven't seen a fair benchmark for line clipping yet. The most fair test, in my opinion, would be to generate a tight, paralleled-piped-shaped grid of interconnected points in three dimensions.
The benchmarks in Table 2 were done with the window dimensions set at 5 < X < 630, 3 < Y < 300. The values of the line end points varied from - 16K < (X, Y) <16K. One thousand lines were clipped 100 times. The resulting clipped lines were drawn in one case and not in the other, giving a true value of the line clipping overhead in the latter case.
Cohen-Sutherland 104 85 1,176 Cohen-Sutherland-Duvanenko 74 55 1,818
The algorithm modifications resulted in a 35.3 percent speed improvement for this sample of 1000 lines. This results in an incredible 54.6 percent more lines clipped per second than the first implementation of the Cohen-Sutherland algorithm!
Additional improvements can be developed to increase the performance further.10 Presently, a record of about 80 percent more lines clipped has been achieved. The number of comparisons is the biggest time consumer in the Cohen-Sutherland algorithm.8 If you think of some other improvements, let me know. I'd love to hear about your results and see the code.
_IMPROVING LINE SEGMENT CLIPPING_
by Victor J. Duvanenko, W.E. Robbins, and Ronald S. Gyurcsik
[LISTING ONE]
/* Created by Victor J. Duvanenko. Straight forward implementation of the
Cohen-Sutherland line clipping algorithm. */
#define BOOLEAN int
#define TRUE 1
#define FALSE 0
#define OK 0
#define NOT_OK -1
#define ACCEPT TRUE
#define REJECT FALSE
/* Clipping rectangle boundaries - accessable to all routines */
extern double
y_bottom,
y_top,
x_right,
x_left,
z_front,
z_back;
*/----------------------- Cohen-Sutherland 2D algorithm --------------------
Procedure that sets four bits, and outcode, to designate a region of
point existance relative to the clipping rectangle. For a full explanation
see Foley and Van Dam p.146 Fig. 4.5
Bit 0 - point is above window
Bit 1 - point is below window
Bit 2 - point is to right of window
Bit 3 - point is to left of window
The algorithm is border inclusive - border is included in the window.
--------------------------------------------------------------------------*/
static void outcodes( x, y, outcode )
double x, y;
int *outcode;
{
*outcode = 0;
if ( y > y_top ) *outcode |= 1;
if ( y < y_bottom ) *outcode |= 2;
if ( x > x_right ) *outcode |= 4;
if ( x < x_left ) *outcode |= 8;
}
/*------------------------------------------------------------------------
Procedure that checks for trivial rejects - if both end points are above,
below, to the right, or to the left of the window.
This procedure can be converted into a macro, for performance improvement.
--------------------------------------------------------------------------*/
static reject_check( outcode1, outcode2 )
int outcode1, outcode2;
{
if ( outcode1 & outcode2 )
return( TRUE );
return( FALSE );
}
/*------------------------------------------------------------------------
Procedure that checks for trivial accept - if both end points are within
the window. This procedure can also be replaced by a macro, for speed.
--------------------------------------------------------------------------*/
static accept_check( outcode1, outcode2 )
int outcode1, outcode2;
{
if (( !outcode1 ) && ( !outcode2 ))
return( TRUE );
return( FALSE );
}
/*------------------------------------------------------------------------
Procedure that exchanges the endpoints and their outcodes.
--------------------------------------------------------------------------*/
static void swap_pts( x0, y0, outcode0, x1, y1, outcode1 )
double *x0, *y0;
int *outcode0;
double *x1, *y1;
int *outcode1;
{
double tmp;
int tmp_i;
tmp = *x0; /* exchange the x's */
*x0 = *x1;
*x1 = tmp;
tmp = *y0; /* exchange the y's */
*y0 = *y1;
*y1 = tmp;
tmp_i = *outcode0; /* exchange the outcodes */
*outcode0 = *outcode1;
*outcode1 = tmp_i;
}
/*------------------------------------------------------------------------
Procedure that clips in 2D using Cohen-Sutherland algorithm. The algorithm
has been modified to separate the drawing function from clipping. This way
clipping is one of the pipelined processes. This procedure lets the calling
routine know whether the line has been accepted or rejected, so that the
caller knows whether to draw it, with possibly modified points, or not.
--------------------------------------------------------------------------*/
clip_2d_cs( x0, y0, x1, y1 )
double *x0, *y0; /* first end point */
double *x1, *y1; /* second end point */
{
int outcode0, outcode1;
/* Adjust end points until it's possible to trivially accept or reject */
while( TRUE ) /* one adjustment per iteration */
{
outcodes( *x0, *y0, &outcode0 );
outcodes( *x1, *y1, &outcode1 );
if ( reject_check( outcode0, outcode1 ))
return( REJECT );
if ( accept_check( outcode0, outcode1 ))
return( ACCEPT );
/* subdivide line since at most one endpoint is inside */
/* First, if P0 is inside window, exchange points P0 and P1 */
/* and their outcodes to guarantee that P0 is outside window */
if ( !outcode0 )
swap_pts( x0, y0, &outcode0, x1, y1, &outcode1 );
/* Now perform a subdivision, move P0 to the intersection point.
use the formulas y = y1 + slope * (x - x1)
x = x1 + (1/slope) * (y - y1)
Note that we don't have to worry about division by 0 in any of
these cases. If a line is horizontal, then if any of its end
points were above the window, it would have been trivially rejected.
So, the only case possible is that the end points are left or
right of the window (outcode0 & (4 or 8)). */
if ( outcode0 & 1 )
{ /* divide line at top of window */
*x0 += ( *x1 - *x0 ) * ( y_top - *y0 ) / ( *y1 - *y0 );
*y0 = y_top;
}
else if ( outcode0 & 2 )
{ /* divide line at bottom of window */
*x0 += ( *x1 - *x0 ) * ( y_bottom - *y0 ) / ( *y1 - *y0 );
*y0 = y_bottom;
}
else if ( outcode0 & 4 )
{ /* divide line at right edge of window */
*y0 += ( *y1 - *y0 ) * ( x_right - *x0 ) / ( *x1 - *x0 );
*x0 = x_right;
}
else if ( outcode0 & 8 )
{ /* divide line at left edge of window */
*y0 += ( *y1 - *y0 ) * ( x_left - *x0 ) / ( *x1 - *x0 );
*x0 = x_left;
}
}
}
/* ------------------------ END of 2D CS algorithm ------------------------ */
[LISTING TWO]
/* Created by Victor J. Duvanenko An improved implementation of the
Cohen-Sutherland line clipping algorithm. */
#define BOOLEAN int
#define TRUE 1
#define FALSE 0
#define OK 0
#define NOT_OK -1
#define ACCEPT TRUE
#define REJECT FALSE
/* Clipping rectangle boundaries - accessable to all routines */
extern double
y_bottom,
y_top,
x_right,
x_left,
z_front,
z_back;
/*------------- Cohen-Sutherland-Duvanenko 2D and 3D algorithms ---------- */
Procedure that sets four bits, and outcode, to designate a region of
point existance relative to the clipping rectangle. For a full explanation
see Foley and Van Dam p.146 Fig. 4.5
Bit 0 - point is above window
Bit 1 - point is below window
Bit 2 - point is to right of window
Bit 3 - point is to left of window
The algorithm is border inclusive - border is included in the window.
Defining the procedure as a macro removes the need to pass the data on
the stack - and gains additional speed.
Note, that top and bottom (and right and left) are mutually exclusive
areas. That's the reason for else's - reduces compares 4 down to 3.
--------------------------------------------------------------------------*/
#define OUTCODES_CSD( X, Y, OUTCODE ) \
( OUTCODE ) = 0; \
if ((Y) > y_top ) OUTCODE |= 1; \
else if ((Y) < y_bottom ) OUTCODE |= 2; \
if ((X) > x_right ) OUTCODE |= 4; \
else if ((X) < x_left ) OUTCODE |= 8;
/*------------------------------------------------------------------------
Procedure that exchanges the endpoints and their outcodes.
Defining the procedure as a macro removes the need to pass the data on
the stack - and gains additional speed.
--------------------------------------------------------------------------*/
#define SWAP_PTS_CSD( X0, Y0, OUTCODE0, X1, Y1, OUTCODE1 ) \
tmp = *X0; /* exchange the x's */ \
*X0 = *X1; \
*X1 = tmp; \
tmp = *Y0; /* exchange the y's */ \
*Y0 = *Y1; \
*Y1 = tmp; \
tmp_i = OUTCODE0; /* exchange the outcodes */ \
OUTCODE0 = OUTCODE1; \
OUTCODE1 = tmp_i;
/*------------------------------------------------------------------------
Procedure that clips in 2D using Cohen-Sutherland algorithm. The algorithm
has been modified to separate the drawing function from clipping. This way
clipping is one of the pipelined processes. This procedure lets the calling
routine know whether the line has been accepted or rejected, so that the
caller knows whether to draw it, with possibly modified points, or not.
--------------------------------------------------------------------------*/
clip_2d_csd( x0, y0, x1, y1 )
double *x0, *y0; /* first end point */
double *x1, *y1; /* second end point */
{
register unsigned outcode0, outcode1;
double dx, dy; /* change in x and change in y */
BOOLEAN intersect;
double tmp; /* needed for the SWAP procedure */
int tmp_i; /* needed for the SWAP procedure */
OUTCODES_CSD( *x0, *y0, outcode0 );
OUTCODES_CSD( *x1, *y1, outcode1 );
if ( outcode0 & outcode1 ) /* trivial reject */
return( REJECT );
if ( ! ( outcode0 | outcode1 )) /* trivial accept */
return( ACCEPT );
/* Calculate the subproducts of the slope only once. */
/* These must be calculated in all cases. */
dx = *x1 - *x0;
dy = *y1 - *y0;
intersect = FALSE;
/* Adjust end points until it's possible to trivially accept or reject */
while( TRUE ) /* one adjustment per iteration */
{
/* subdivide line since at most one endpoint is inside */
/* First, if P0 is inside window, exchange points P0 and P1 */
/* and their outcodes to guarantee that P0 is outside window */
if ( !outcode0 )
{
SWAP_PTS_CSD( x0, y0, outcode0, x1, y1, outcode1 );
intersect = TRUE; /* the line intersects the window */
}
/* Now perform a subdivision, move P0 to the intersection point.
use the formulas y = y1 + slope * (x - x1)
x = x1 + (1/slope) * (y - y1)
Note that we don't have to worry about division by 0 in any of
these cases. If a line is horizontal, then if any of its end
points were above the window, it would have been trivially rejected.
So, the only case possible is that the end points are left or
right of the window (outcode0 & (4 or 8)). */
if ( outcode0 & 1 )
{ /* divide line at top of window */
*x0 += dx * ( y_top - *y0 ) / dy;
*y0 = y_top;
outcode0 = 0;
if ( *x0 > x_right ) outcode0 |= 4;
else if ( *x0 < x_left ) outcode0 |= 8;
}
else if ( outcode0 & 2 )
{ /* divide line at bottom of window */
*x0 += dx * ( y_bottom - *y0 ) / dy;
*y0 = y_bottom;
outcode0 = 0;
if ( *x0 > x_right ) outcode0 |= 4;
else if ( *x0 < x_left ) outcode0 |= 8;
}
else if ( outcode0 & 4 )
{ /* divide line at right edge of window */
*y0 += dy * ( x_right - *x0 ) / dx;
*x0 = x_right;
outcode0 = 0;
if ( *y0 > y_top ) outcode0 |= 1;
else if ( *y0 < y_bottom ) outcode0 |= 2;
}
else if ( outcode0 & 8 )
{ /* divide line at left edge of window */
*y0 += dy * ( x_left - *x0 ) / dx;
*x0 = x_left;
outcode0 = 0;
if ( *y0 > y_top ) outcode0 |= 1;
else if ( *y0 < y_bottom ) outcode0 |= 2;
}
if ( outcode0 & outcode1 ) /* trivial reject */
return( REJECT );
if ( ! ( outcode0 | outcode1 )) /* trivial accept */
return( ACCEPT );
}
}
/* --------------------- END of 2D CSD algorithm ---------------------- */
[LISTING THREE]
/* Created by Victor J. Duvanenko Program that generates random 3D points,
that will be used for testing performance of line clipping algorithms. */
#include <stdio.h>
#include <stdlib.h>
#define BOOLEAN int
#define TRUE 1
#define FALSE 0
#define OK 0
#define NOT_OK -1
#define NUM_LINES 1000 /* generate this many lines */
#define ROUND(x) ((x) > 0.0 ? (int)((x) + 0.5) : (int)((x) - 0.5))
#define DEBUG FALSE /* en(dis)able debug sections */
/*------------------------------------------------------------------------
Procedure that generates any number of 3D points - randomly.
--------------------------------------------------------------------------*/
generate_vertex_data( num_points )
{
register i;
double x, y, z;
char *fname;
FILE *fp;
/* Fix the file name, since performance benchmarks are required. */
/* Therefore, user interaction should be completely eliminated. */
fname = "clip1.dat";
if (( fp = fopen( fname, "w" )) == NULL )
{
printf("Couldn't open file %s.\n", fname );
return( TRUE );
}
for( i = 0; i < num_points; i++ )
{
/* center the values around 0.0, so as to have an equal number */
/* of negative and positive values. */
x = (double)rand() / (double)RAND_MAX * 64000.0 - 32000.0;
y = (double)rand() / (double)RAND_MAX * 64000.0 - 32000.0;
z = (double)rand() / (double)RAND_MAX * 64000.0 - 32000.0;
fprintf( fp, "%12.2lf %12.2lf %12.2lf\n", x, y, z );
}
fclose( fp );
}
/*------------------------- MAIN ------------------------------------*/
main( argc, argv )
int argc;
char **argv;
{
generate_vertex_data( NUM_LINES << 1 );
return( 0 ); /* everything went fine */
}