An Analysis Technique And An Algorithm For Line Clipping

An Analysis Technique and an Algorithm for Line Clipping Frank Devai School of Computing, Information Systems and Mathematics South Bank University, London, England

Abstract:

A mathematical model for the expectedtime analysis of line-clipping algorithms is proposed. Assuming that all clipping windows are equally likely, we demonstrate that the probability of a line segment being totally outside the window approaches the value of 8/9, provided that the line segments tend to be short and evenly distributed within a rectangle. Acceptance-rejection matrices are introduced for a machine-independent comparison of algorithms. A new line-clipping method, called QuickClip, is also proposed. QuickClip is not only simpler and more concise than the Cohen-Sutherland algorithm, the most widely used method in computer graphics, but also faster both in terms of machine-independent analysis and timing results on random line segments. Timing results also indicate that QuickClip is signi cantly faster than the Nicholl-Lee-Nicholl algorithm. The theoretical results generalise in three dimensions, with the important consequence that the average clipping volume is 1/27 of the volume of the model.

1 Introduction

The Cohen-Sutherland method is the most widely published line-clipping algorithm in the literature [1, 3, 9, 10, 13, 16, 17], and therefore probably the most often used method in practice. Several authors attempted to propose an alternative to this algorithm with a better running time, though at the expense of a longer program code [4, 5, 8, 12, 14, 18, 19]. One of our objectives is to propose an alternative that is not only faster, but also has a shorter program code, more straightforward, and easier to understand. Clipping is the extraction of the required portion of a two- or three-dimensional model, and belongs to the wider area of geometric intersection problems [6, 11, 15]. In the two-dimensional case the extracted portion of the model is usually a rectangle, called the window. Some authors concentrate on the reduction of the amount of intersection calculations with the boundary of the window [14, 18]. Applications like geographic information systems, the design of very large-scale integration (VLSI) cir-

cuits etc, clip many line segments repeatedly, and need an expected-time analysis. A surprising result of our analysis is that, on the average, almost 90% of the line segments are outside the window, and few intersect the boundary of the window. The Cohen-Sutherland algorithm uses a coding scheme to pre-process the line segment to be clipped. Nicholl, Lee and Nicholl [14] demonstrated that the coding scheme is a source of ineciency, proposed a signi cantly longer algorithm, and claim by a machine-independent comparison that their algorithm is faster. Sharma and Manohar [18] proposed another method, called the opposite-corner algorithm, and claim that it is faster than the Nicholl-Lee-Nicholl (NLN) algorithm on the assumption that the NLN algorithm is origin dependent. However, this assumption is wrong, the NLN algorithm is not origin dependent. The opposite-corner algorithm still needs longer code than the Cohen-Sutherland algorithm, and its claim for eciency is based on fewer intersection calculations. Unfortunately, no implementation details of acceptance and rejection tests are given. Day [5] also proposed a method that needs a longer code than the Cohen-Sutherland algorithm. Day's method is more ecient for trivial rejection, though less ecient for trivial acceptance [5]. Duvanenko et al [8] proposed an improvement to the Cohen-Sutherland algorithm that needs again a longer code, and that is reported to be particularly ecient if more than 60% of the line segments are inside the window. Cyrus and Beck [4] and Liang and Barsky [12] used a parametric representation of the input line segment. The Cyrus-Beck method is more general, and the Liang-Barsky algorithm is more ecient for rectangular windows. Timing results for 1000 randomly generated line segments are reported: the Liang-Barsky algorithm took 36% less time, ie, it was 1.56 times faster than the Cohen-Sutherland algorithm. Performance evaluations by other authors [5, 14, 18] do not corroborate Liang and Barsky's claim. The apparent reason for the inconclusive timing results is the use of ad hoc methods of performance eval-

uation. We propose a mathematical model for the expected-time analysis of the clipping problem. In Section 2 rst some assumptions are made, based on the statistical properties of large planar sets of line segments. Using the assumption that all clipping windows are equally likely to appear within a rectangle, we determine the size and the location of the average window. Finally requirements for ecient lineclipping algorithms are formulated. In Section 3 an improved variant of the CohenSutherland algorithm that does not need bit manipulation, and that does not have other implementation overheads like procedure calls is presented. Observing our eciency requirements, we also rearrange the order of acceptance and rejection tests to improve the overall performance. In Section 4 our proposed method, the QuickClip algorithm is presented. Eciency is traded for simplicity when the former is not crucial from the point of view of the overall performance. Improved acceptance-rejection tests and a virtual-window technique is introduced to achieve a shorter program code than the code for the Cohen-Sutherland method. In Section 5 QuickClip is compared with the Cohen-Sutherland and the NLN algorithms both in terms of operation counts and timing results. It is demonstrated in two dierent models of computation that QuickClip is faster than the Cohen-Sutherland method. Timing results also indicate that on the average QuickClip is signi cantly faster than both the Cohen-Sutherland and the NLN algorithms. Finally in Section 6 we summarise the methods, techniques and the ndings of this research.

is as follows:

In graphics applications the data base, called the model, is usually very large. For example, a design for a VLSI circuit may contain millions of transistors, each described by a number of rectangles. The designer almost always works with a small part of the circuit only. This is also the case, eg, with geographical data bases. Curves are usually approximated by a chain of line segments, and the appropriate part of the map or the VLSI design is displayed in a rectangular window with sides parallel to the coordinate axes. The individual line segments are very short compared not only to the size of the model, but also to the size of the window. Though small windows are probably more often used in practice, it will result in conservative estimates if we assume that windows with all sizes and positions are equally likely. Let us restrict ourselves to a model M with sides parallel to the coordinate axes, then the summary of our assumptions

m,1 m

2 Requirements for line clipping

1. the line segments are evenly distributed within the model, 2. the line segments are short compared to the size of the model and 3. all clipping windows are equally likely to appear within M . Let M be a rectangle determined by the diagonal with the endpoints (0; 0) and (m; n), where m; n > 0. Now we determine the size and the location of the average window. For simplicity let m and n be integers. All windows being equally likely is the same as if the endpoints of their diagonals were chosen uniformly, independently at random from M . Choosing a point uniformly at random from M can be done by choosing an x-coordinate uniformly at random from the interval [0; m] and then choosing a y-coordinate uniformly at random from the interval [0; n] independently of the x-coordinate. For simplifying the presentation, consider only windows with integer coordinates. Then the x-extents, the x-coordinates xL of the left-hand sides of the possible windows and the appropriate number of windows can be given by the following table.

x-extent xL number of windows 1 0; 1; 2; : : :; m , 1 m 2 0; 1; 2; : : :; m , 2 m,1 .. .

i .. .

.. . 0; 1; 2; : : :; m , i .. . 0; 1 0

.. .

m,i+1 .. . 2 1

The total number of windows with dierent xcoordinates is the sum of the third column of the table: m X

k=1

k = m(m2+ 1) :

The possible xL values for a window of x-extent i are 0; 1; 2; : : :; m , i. Let a be the average value of xL . Then m m X X,i

a = m(m2+ 1) j i=1 j =0

m , X
= m(m1+ 1) (m , i)2 + m , i : i=1

Pm (m , i)2 can be rewritten as Pm,1 i2, and it i=1 i=1 can by mathematical induction that Pn bei2demonstrated = n(n + 1)(2n + 1)=6, hence we obtain i=1

m , 1) + 3(m , 1) a = (m , 1)(26( m + 1) 2,1 m = 3(m + 1) = m 3, 1 : As m increases, a approaches m=3. We can make a similar argument for the y-dimension, then it follows

that the bottom-left corner of the average window approaches the point (m=3; n=3) if m and n get large. Now let c and d respectively be the x- and ydimensions of the average window. There are m , i +1 windows of x-extent i with dierent x-coordinates, therefore m X c = m(m2+ 1) (m , i + 1)i: i=1

The sum can be rewritten as follows. m X

m m X X 2

i=1

i=1

(m , i + 1)i = (m + 1)

P

i,

i=1

i:

P

m 2 Substituting m i=1 i = m(m + 1)=2 and i=1 i = m(m + 1)(2m + 1)=6, we obtain c = m + 1 , 2m3+ 1 = m 3+ 2 : With a similar reasoning for d we can conclude that the size of the average window approaches m=3 by n=3 if the dimensions m and n of the model get large. Using our rst and second assumptions this result means that about 8=9  89% of the line segments will be outside the average window, and therefore should be rejected; about 1=9  11% of the line segments will be inside, and very few line segments will intersect the boundary of the window. Then the requirements for clipping line segments in large databases | in decreasing order of importance | are as follows:  quick rejection of all the line segments outside  quick acceptance of those inside the window, and  fast intersection calculations with the boundary of the window.

3 The Cohen-Sutherland algorithm

The Cohen-Sutherland algorithm divides the plane into nine regions by the four straight lines containing the four sides of the window. A 4-bit code is assigned

1001

1000

1010

0001

0000

0010

0101

0100

0110

Figure 1: A coding scheme to each region such that each one of the bits indicates that the appropriate region is above, below, right or left to the window. For example, the code 1xxx, where x denotes either 1 or 0, corresponds to one of the three regions above the window, as shown in Figure 1. The middle region corresponding to the window is always assigned the code 0000. The subdivision is not explicitly maintained, only the codes for the two regions where the endpoints of the line segment to be clipped fall are calculated. If both codes are 0000, the line segment is trivially accepted, and if the logical AND of the two codes is nonzero, trivially rejected. If none of the above is the case, at least one endpoint must be outside the window. The codes will also indicate the side(s) of the window that potentially intersect(s) the line segment. Intersection calculation with one side of the window is performed in one iteration. The part of the line segment outside the window is discarded, the code for the new endpoint is recalculated, and the whole process is repeated until the line segment is either trivially accepted or rejected. Unfortunately, many of the C-codes for the CohenSutherland algorithm available in the literature [1, 10] are incorrect. In Foley et al [10] the bit elds for the endpoint codes are not initialised. Angel's implementation [1] falls into an in nite loop after an intersection calculation as the main loop of the code terminates only if the line segment is accepted. This is one reason why we present an implementation here. The more important reason, however, is that operation counts can only be considered with a particular implementation. For the implementation of the coding scheme bit manipulations [1, 2, 9, 10, 13, 16] and assembly code [2, 10] are recommended in the literature. Bit manipulations are expensive even in assembly code as no machine-code instructions for bit elds are available, and bit elds can only be selected by bit-wise

logical operations. Fortunately, no bit-manipulations are inherently required by the Cohen-Sutherland algorithm. With the coding scheme as above if one carefully checks for intersections with the top, bottom, right and left sides of the window in that order, the codes can be stored in integers, and the ordinary relation operations `' and `=' can be used for detecting intersections. Intersection with the top edge of the window can be detected by the condition: code  8. The CohenSutherland algorithm never attempts to do intersection calculations with more than one side of the window in one iteration. (Actually, it would not be possible, as after an intersection calculation the region code is no longer valid for the new endpoint.) Then intersection with the bottom edge can be detected by the condition: code  4, as intersection with the bottom edge will only be attempted if the code for the top edge was not set. Intersection with the right-hand side can be detected by the condition: code = 2. Note that no need for testing a condition for intersection with the left-hand side. A possible overhead with the usual implementations of the Cohen-Sutherland algorithm is the call to a procedure computing the endpoint codes. Foley et al [10] pass eight parameters, which can be a considerable overhead. To avoid all overheads associated with procedure calls, we use a macro de nition. This will also keep the C-code short, though it results in a slightly longer object code. The C-code for the improved Cohen-Sutherland method is given as Figure 2. The calculation of one endpoint code takes four comparisons in the worst case, which occurs in the left, middle, bottom and the bottom-left regions. Hence we could accept a line segment in 10 comparisons, as we need eight for the code calculations and two more for the comparison of code0 and code1 to the constant INSIDE. If the acceptance test fails, we need a further logical AND operation, and nally a comparison of the result to zero in an attempt to reject the line segment. A logical AND takes the same amount of time as a comparison on most computers, then one could argue that a rejection requires the time of 12 comparisons in the worst case. It is possible, however, that the logical AND sets a condition code if the result is zero, and the compiler takes advantage of that condition code. Therefore we need only one more, ie, a total of 11 comparisons to reject a line segment in the worst case. However, as eight times more line segments are rejected than accepted on the average, it is better to perform the rejection test rst. Then we can reject a

enum { INSIDE = 0, LEFT = 1, RIGHT = 2, BOTTOM = 4, TOP = 8 }; #define CompCode(x, if ( y > yT else if ( y else code = if ( x > xR else if ( x

y, code) { ) code = TOP; < yB ) code = BOTTOM; INSIDE; ) code |= RIGHT; < xL ) code |= LEFT;

\ \ \ \ \ }

void CSclip( float x0, float y0, float x1, float y1, float xL, float xR, float yB, float yT) { int code0, code1; float temp; CompCode (x0, y0, code0); CompCode (x1, y1, code1); for ( ; ; ) { if ( (code0 & code1) != 0 ) return; if ( (code0 | code1) == 0 ) break; if (code1 == INSIDE) { code1 = code0; code0 = INSIDE; temp = x0; x0 = x1; x1 = temp; temp = y0; y0 = y1; y1 = temp; } if (code1 >= TOP) { x1 = x0 + (yT-y0)*(x1-x0)/(y1-y0); y1 = yT; } else if (code1 >= BOTTOM) { x1 = x0 + (yB-y0)*(x1-x0)/(y1-y0); y1 = yB; } else if (code1 == RIGHT) { y1 = y0 + (xR-x0)*(y1-y0)/(x1-x0); x1 = xR; } else { y1 = y0 + (xL-x0)*(y1-y0)/(x1-x0); x1 = xL; } CompCode (x1, y1, code1); } /* output segment (x0, y0), (x1, y1) */ }

Figure 2: C-code for the Cohen-Sutherland method

line segment in the time of 9 comparisons, and could accept one in 11 comparisons in the worst case. As a nal improvement, the 11 comparisons are reduced to 10 by taking the logical OR of code0 and code1 before comparison, based on the same argument as given for the logical AND operation. Attempting rejection rst results in about 10% improvement on the average performance, ie, we take an average of 70/9 comparisons instead of 77/9 over the nine regions. Avoiding bit manipulations is also a signi cant improvement, but its contribution to the average performance is machine dependent.

4 The QuickClip method

Similarly to some other algorithms [5, 18] the QuickClip method will be presented rst for positivegradient line segments. However, we also propose an ecient new technique, called the virtual-window method, to re-use the code for negative-gradient line segments. This technique makes a shorter program code possible than the code required for other methods including the Cohen-Sutherland algorithm. Finally we will demonstrate that the virtual-window technique does not deteriorate average performance. Considering the requirements speci ed in Section 2, an ecient line clipping algorithm should begin with a rejection test followed by an acceptance test, and should be concluded with intersection calculations. Let (x0 ; y0 ) and (x1 ; y1) be the endpoints of a line segment, and let xL , xR , yB and yT represent the left, right, bottom and top sides of the window respectively. Then a straightforward algorithm without a coding scheme could be formulated as follows. Swap the endpoints if necessary such that x0  x1 and assume that y0  y1 ;

if x0 > xR or x1 < xL or y0 > yT or y1 < yB then reject the line segment elseif x0  xL and x1  xR and y0  yB and y1  yT then accept the line segment as being totally inside else determine intersections endif

However, we can also use the information obtained from the rejection and acceptance tests in the intersection calculations. Therefore we modify the code such that if the line segment fails any one of the four acceptance conditions, an intersection calculation is immediately performed, and the part of the line segment outside the window range is clipped away: Make x0  x1 and assume that y0  y1 ;

if x0 > xR or x1 < xL or y0 > yT or y1 < yB then reject the line segment else if x0 < xL then clip to the line x = xL; if y0 < yB then clip to the line y = yB ; if x1 > xR then clip to the line x = xR ; if y1 > yT then clip to the line y = yT endif The correctness of the above modi cations follows from the observation that, eg, if x0 < xL , we know from the rejection test that x1  xL must also hold. While clipping against the line x = xL if the intersection point is above yT , the line segment should be rejected. Similarly, while clipping against y = yB if the intersection point is beyond xR , the line segment should also be rejected. Note that rejection opportunities do not arise while clipping against the lines x = xR and y = yT . If we reach the end of the code, the line segment must be totally inside or clipped to the window. A C-code for the QuickClip method is given as Figure 3, though the details of the algorithm will be further discussed in pseudo-code. Some authors attempt to avoid the calculation of the above type `external intersections' which are not part of the result [10, 14]. This cannot make a signi cant improvement on the overall performance for two reasons. First, as we have seen earlier, intersection calculations are not often occur, and second, avoiding them (eg, by evaluating inequalities like (ytop , y1 )  (x2 , x1 ) < (xleft , x1 )  (y2 , y1) [14]) takes almost as much time as actually doing them. We can swap the endpoints of the line segment such that x0  x1 , then if y0 > y1 , a code segment similar to the code for the case of the positive gradient can be used. Another possibility is to re ect a negativegradient segment together with the window around the x-axis as shown in Figure 4. Then a line segment with a negative gradient will have a positive gradient after the re ection. Care should be taken, however, that yT should now assume the value of ,yB , and yB the value of ,yT . We assume that the evaluation of a logical expression stops as soon as it can be decided whether the result is TRUE or FALSE, which is guaranteed in the C language. Therefore if x0 > xR is TRUE, the rejection test given above immediately discards the line segment without evaluating the remaining three comparisons. Taking into consideration also the comparisons of x0 with x1 and y0 with y1 , we could reject a line segment in three comparisons. This can be reduced to two if we deal with the x- and y-coordinates separately.

y

void QuickClip ( float x0, float y0, float x1, float y1, float xL, float xR, float yB, float yT ) { enum { FALSE, TRUE } reflect; float t, u; if (x0 > x1) { if ( x1 > xR || x0 < xL ) return; t = x0; u = y0; x0 = x1; y0 = y1; x1 = t; y1 = u; } else if ( x0 > xR || x1 < xL ) return; if (y0 > y1) { if ( y1 > yT || y0 < yB ) return; reflect = TRUE; y0 = -y0; y1 = -y1; temp = yB; yB = -yT; yT = -temp; } else { if ( y0 > yT || y1 < yB ) return; reflect = FALSE; } if (x0 < xL) { if ((y0+=(xL-x0)*(y1-y0)/(x1-x0)) > yT) return; x0 = xL; } if (y0 < yB) { if ((x0+=(yB-y0)*(x1-x0)/(y1-y0)) > xR) return; y0 = yB; } if (x1 > xR) { y1 = y0 + (xR-x0)*(y1-y0)/(x1-x0); x1 = xR; } if (y1 > yT) { x1 = x0 + (yT-y0)*(x1-x0)/(y1-y0); y1 = yT; } if (reflect) { y0 = -y0; y1 = -y1; } /* output segment (x0, y0), (x1, y1) */ }

Figure 3: C-code for the QuickClip method

y0

@@ y

1

,y , , ,y 0

1

x yT := ,yB yB := ,yT

Figure 4: Clipping against a virtual window Nicholl et al [14] observed that one can reject a line segment in two comparisons, eg, if x0 > xR and also x1 > xR . The following code not only can reject a line segment in two comparisons but also determines the order of x0 and x1 as well as y0 and y1 .

if x0 > x1 then if x1 > xR or x0 < xL then return endif; swap x0 and x1 as well as y0 and y1 elseif x0 > xR or x1 < xL then return endif; if y0 > y1 then if y1 > yT or y0 < yB then return endif; re ect the line segment, set up virtual window elseif y0 > yT or y1 < yB then return endif;

clip the line segment, and re ect it back if necessary; It follows from our observations in Section 2 that the probabilities that a line segment is totally outside or totally inside the window approach the values of 8/9 or 1/9 respectively. Considering the nine regions shown in Figure 1, the above code takes two comparisons in the three regions to the right, three comparisons in the three regions to the left of the window, ve above, six below and nally 10 comparisons inside the window. Duvanenko et al [8] argue that their test requires only two comparisons if x0 is to the left, and x1 is to the right of the window, while the test by Nicholl et al [14] requires three comparisons in the same case. Such a situation, however, rarely occurs with the average window, and usually followed by the calculation of the intersection of the line segment and the boundary of the window, when an extra comparison is negligible. Note that, on the average, less than 6% of the input line segments will be clipped against a virtual window. Indeed, according to our assumptions about 1/3 will survive rejection in the x-dimension (and  1=6 will have their endpoints swapped). About 1/9 will survive rejection in the y-dimension as well, and half of the 1/9 which is  5:6% will be clipped against the virtual window. Setting up the virtual window, re ecting the line segment and re ecting it back impose

CS NLN QC CS NLN QC CS NLN QC

7 2 3 9 2 3 9 2 3

CS NLN QC CS NLN QC CS NLN QC

7 4 5 10 8 10 9 5 6

CS NLN QC CS NLN QC CS NLN QC

5 3 2 7 3 2 7 3 2

Figure 5: Numbers of comparisons seven extra assignments on less than 6% of all the line segments. The line segments clipped against a virtual window all are tested for acceptance, and may also be involved in intersection calculations. Therefore the loss of eciency due to the seven assignments is marginal, and can be traded for simplicity. If the window parameters are passed by value as in Figure 3, there is no need to restore the original window after using a virtual window. On the other hand, if the parameters are global or private to a window object, the clipping code does not even need to set up a virtual window; it only needs to choose between the original and the virtual ones, which are set by separate functions provided for changing the window parameters.

5 Performance evaluations

We have demonstrated in Section 3 that the CohenSutherland algorithm takes 10 comparisons in the middle region, and nine in the left, bottom and bottomleft regions. The best case for the C-code given in Figure 2 is the top-right corner, where the end-point codes take only two comparisons each, hence the total number of comparisons is ve, including one for the rejection test. In each one of the remaining four regions the Cohen-Sutherland method takes seven comparisons. The Nicholl-Lee-Nicholl algorithm [14] takes two comparisons in the three regions to the left, three comparisons in the three regions to the right of the window, four above, ve below and nally eight comparisons inside the window. In Section 4 we have provided the numbers of comparisons taken by QuickClip in all regions. The summary for the Cohen-Sutherland (CS) the Nicholl-Lee-Nicholl (NLN) and the QuickClip (QC) algorithms is given in Figure 5. It would be dicult to compare several algorithms,

all taking a dierent number of comparisons in nine regions of the plane. Therefore we introduce a 3-by-3 matrix, called an acceptance-rejection matrix for each method to represent the number of comparisons taken in the nine regions. As each region has the same area, the average number of comparisons taken by a particular method can be obtained as the average value of the elements of the matrix. The matrices for the CS, NLN and the QC methods respectively are 07 7 51 02 4 31 03 5 21 @ 9 10 7 A, @ 2 8 3 A and @ 3 10 2 A, 9 9 7 2 5 3 3 6 2 and the average number of comparisons are 70/9 = 7.778, 32/9 = 3.556 and 36/9 = 4. QuickClip takes fewer comparisons than the CohenSutherland algorithm in all but the middle region, where both takes the same. The two methods do the same intersection calculations, but the CohenSutherland algorithm also recalculates an endpoint code, and tests code1 up to three times. Therefore QuickClip is at least as fast as the Cohen-Sutherland method for any input. However, it follows from the acceptance-rejection matrices that QuickClip is 70/36 = 1.944 times faster on the average than the improved Cohen-Sutherland algorithm. The above model of computation is realistic if

oating-point operations take about the same time as integer ones. This is the case with contemporary machines, or if the input is given with integer coordinates, then only the multiplications and divisions of the intersection calculations are to be implemented in oating-point operations. Since apparently the Cohen-Sutherland algorithm was designed to reduce oating-point operations, for a fair comparison we use another model of computation, which takes into consideration only the oating point comparisons. For the other two algorithms the matrix is the same, but for the Cohen-Sutherland algorithm 0 6the6 oating 1 point 4 operations can be expressed as @ 8 8 6 A, which 8 8 6 gives an average of 60/9 = 6.667 comparisons, thus QuickClip is only 60/36 = 1.667 times faster. The acceptance-rejection matrices suggest that the NLN algorithm could be 36/32 = 1.125 times faster than QuickClip on the average. The NLN algorithm [14] is a collection of 10 procedures, such as leftcolumn that deals with the situations when the rst endpoint is in one of the regions denoted by the codes 1001, 0001 and 0101 in Figure 1, topleftcorner dealing with the region coded by 1001, centercolumn dealing with the three middle regions and so on. There are ve

more transformation procedures such as rotate90c, rotate180c etc. Both the NLN and the QuickClip method takes two comparisons in the best case. However, the NLN algorithm also has to assign and test a Boolean variable display. In addition, the second comparison of the NLN algorithm is performed within the procedure leftcolumn, which has the overhead of passing 8 numeric parameters and the Boolean variable display. Even if the better performance is not absorbed by a higher administration overhead, it is probably not worth having a signi cantly more complicated algorithm with a much longer program code for the promise of less than 13% improvement on speed. Actually timing results in Figure 6 indicate that the NLN algorithm is significantly slower. Several timing experiments were made on sets of random line segments. The program codes used for QuickClip and the CS algorithm were as they appear above. The NLN algorithm was translated to C-code by the author from the Pascal code given in the original paper [14]. The ve transformation procedures rotate90c, rotate180c etc were implemented as macros. The QuickClip method was signi cantly faster than both the CS and the NLN algorithm in each experiment. The results reported in Figure 6 correspond to the second model of computation, where the comparisons of input coordinates are more expensive than the comparisons of the endpoint codes of the CS algorithm. The line segments were generated as follows. One endpoint was chosen uniformly at random from a square of 10 by 10 units, and the other from a 1-by-1 unit square centred at the rst endpoint. The coordinates were represented by oating-point numbers, and the line segments were clipped against the average window. A 16-bit compiler, Borland's C++ version 3.1 was used on a machine with an Intel 75 MHz Pentium processor under MS-DOS 6.2. The time of passing the eight parameters x0 ; y0 ; x1 ; y1 ; xL ; xR ; yB and yT were deducted from the running time of each algorithm. Checking the assembly code revealed that the compiler kept code0 and code1 for the CS algorithm automatically in registers, while fetched the 32-bit oating point coordinates from memory.

6 Conclusions

One of the most important results of this research is that the average running time of line-clipping algorithms is determined by acceptance and rejection tests. We proposed a mathematical model based on geometric probabilities and acceptance-rejection matrices for a machine-independent comparison of algo-

rithms. Although the acceptance-rejection matrices are simpler than the model proposed by Nicholl, Lee and Nicholl [14], our model is able to predict the average performance of simple algorithms. On the other hand, no model can take into account all the operations determining the running time of more complicated algorithms such as the NLN method. Assuming that all clipping windows are equally likely in a scene represented by a rectangle with sides a and b, we demonstrated that the size of the average window is a=3 by b=3. In most applications the line segments to be clipped are signi cantly shorter than a=3 or b=3, therefore it is reasonable to assume that the line segments tend to be short. Then in the case of a uniform distribution it follows that nearly 89% of the line segments fall outside the window. Our derivation for the size of the average window generalises in three dimensions, consequently the average clipping volume is 1/27 of the volume of the model. The latter result is particularly important in virtual reality systems [7]. We also proposed a new line-clipping algorithm, called QuickClip, as an alternative to the CohenSutherland algorithm. QuickClip is not only faster, but also simpler, and can be implemented in a shorter program code. The improvements were made possible by two new techniques; an improved acceptancerejection test and a virtual-window technique. These techniques can be applied to improve existing lineclipping algorithms [5, 18] and possibly algorithms invented in the future. It is hoped that, beyond its practical signi cance, QuickClip helps to dispel the widely accepted belief [9, 14] that fast line-clipping algorithms inherently require a long program code.

References

[1] Angel, E. Computer Graphics. Addison-Wesley, Reading, Mass. 1990, 477 + xviii pp. [2] Blinn, J. F. A trip down the graphics pipeline: Line clipping. IEEE Computer Graphics & Applications 11,1 (1991) 98{105. [3] Burger, P., Gillies, D. Interactive Computer Graphics: Functional, Procedural and DeviceLevel Methods. Addison-Wesley, Wokingham, UK, 1989, 504 + xv pp. [4] Cyrus, M., Beck, J. Generalised two- and threedimensional clipping. Computers & Graphics 3,1 (1978) 23{28. [5] Day, J. D. A new two dimensional line clipping algorithm for small windows. Computer Graphics Forum 11,4 (Oct. 1992) 241{245.

30 25 20 msec

CS NLN

15

QC 10 5 0 100

200

300

400

500

600

700

Figure 6: Timing results by the number of line segments [6] Devai, F. On the complexity of some geometric intersection problems. Journal of Computing and Information 1 (1995) pp 333{352. [7] Devai, F. On the computational requirements of virtual reality systems. State of the Art Reports, Eurographics'97, Budapest, Hungary, 4{8 September 1997, 59{92. [8] Duvanenko, V. J., Gyurcsik, R. S., Robbins, W. E. Simple and ecient 2D and 3D span clipping algorithms. Computers & Graphics, 17,1 (1993) 39{54. [9] Foley, J. D., van Dam, A., Feiner, S. K., Hughes, J. F. Computer Graphics: Principles and Practice. (2nd ed) Addison-Wesley, Reading, Mass., 1990, 1174 + xxiii pp. [10] Foley, J. D. et al. Introduction to Computer Graphics. Addison-Wesley, Reading, Mass., 1994, 557 + xxviii pp. [11] Fung, K. Y., Nicholl, T. M., Tarjan, R. E., Van Wyk, C. J. Simpli ed linear-time Jordan sorting and polygon clipping. Information Processing Letters 35 (1990) 85{92. [12] Liang, Y.-D., Barsky, B. A. A new concept and method for line clipping. ACM Transactions on Graphics 3,1 (1984) 1{22.

[13] Newman, W. M. and Sproull, R. F. Principles of Interactive Computer Graphics. (2nd edition) McGraw-Hill Kogakusha Ltd., Tokyo, Japan, 1979, 541 + xviii pp. [14] Nicholl, T. M., Lee, D. T., Nicholl, R. A. An ecient new algorithm for 2-D line clipping: its development and analysis. Computer Graphics 21,4 (July 1987) 253{262. [15] Preparata, F. P., Shamos, M. I. Computational Geometry: An Introduction. Springer-Verlag, Berlin, 1985, 390 + xii pp. [16] Rogers, D. F. Procedural Elements for Computer Graphics. McGraw-Hill Book Company, New York, NY, 1985, 433 + xiii pp. [17] Salmon, R., Slater, M. Computer Graphics: Systems & Concepts. Addison-Wesley, Wokingham, UK, 1987, 702 + xvii pp. [18] Sharma, N. C., Manohar, S. Line clipping revisited: Two ecient algorithms based on simple geometric observations. Computers & Graphics 16,1 (1992) 51{54. [19] Slater, M., Barsky, B. A. 2D line and polygon clipping based on space subdivision. The Visual Computer 10 (1994) 407-422.