An Efficient Line Algorithm

A N EFFICIENT LINE ALGORITHM A . T. M. ShafiquI Khalid’

M. KaykobadZ

‘Ascent Solutions Inc. 9009 Miamisburg Springboro Pike Dayton, OH45342, USA [email protected] 2Dept. of Computer Science & Engineering Bangladesh University of Engineering & Technology Dhaka-1000, BANGLADESH

ABSTRACT

devices may not appear to be perfectly straight, the line accuracy has been claimed to improve in proportion to the display resolution. One of the most important characteristics of this algorithm is that it requires lesser number of comparisons thanthat of Bresenham. Some algorithm speed up the line drawing process by calculating few pixels using symmetry property of line and double step technique[6]. Proposed algorithm can effectively used for further improvement of those algorithm as it improve basic pixel calculating prccess.

We present a new algorithm for drawing lines in a raster device in which a suitable data structure has been chosen to avoid comparisons that are required, for example, in Bresenham’s algorithm. Experimental results as well as clock cycles calculated theoretically suggest that this new algorithm outperforms the ones currently existing in the literature in terms of computational time. Our experimental results also suggest that quality of the line does not deteriorate even when high resolution raster devices are used.

2. 1.

INTRODUCTION

As in the case of Bresenham’s algorithm we assume that the line to be drawn always makes a non-negative angle not exceeding 45 degrees with the x-axis. Other cases can be dealt with using routine transformations. The main feature of the algorithm is that it does not require comparisons before putting a pixel on as is done in Bresenham’s and other algorithms. This results in a drastic reduction of computational time. This has become possible observing the fact that even raster devices having very high resolutions do not require calculations based on 4-byte words. As in other algorithms x-values will be incremented by one whereas yvalues will be represented as an integer, the leftmost 2 bytes of which will contain the y-coordinate of the pixel and the rightmost 2 bytes wiU represent the fractional increment part, which when sufficiently accumulated will cause the value of the leftmost part automatically changed, and will always contain the right value for scan conversion without requiring any comparison. In order that the computed y coordinate is represented by the closest pixel a half is added to the y-value so that integer portion becomes closest to the computed y-value. The pseudocode of the algorithm is given in the following:

Line drawing is one of the most fundamental activities in computer graphics. There are many M e r e n t line drawing algorithms used in computer graphics. Application of inefficient algorithms may cause drawing to require unacceptably large amount of time thus making the graphics presentation boring. This is why algorithms used in computer graphics must be computationally very efficient. As a result computer graphics algorithms are quite often found to avoid, for example, floating point operations or more costly division and multiplication operations as in Bresenham’s line algorithm. As a line is drawn by lighting only a finite number of pixels with integer coordinates, it is not possible to produce a theoretical line exactly in a raster device. In order that a line drawn on a raster device simulates a theoretical line as closely as possible, a set of pixels, which represent the real line as closely as possible, are only switched on. Assuming that line to be drawn makes an angle between 0 and 45 degrees with the x-axis, it can be easily said that in between successive pixels only two kinds of movements will be available: sideways- keeping y-value fixed x-value is increased or diagonal - both x and y values are increased by 1. This is essentially what is done both in Bresenham’s or recently introduced recursive bisection algorithms.

Procedure N e w L i n e ( x 1 , y1,

Existing algorithms for line drawing can be classified as incremental, nonincremental, or they may differ in the order of setting the pixels that represent the line [1,3,4]. Borges[2] considered the problem of line drawing, where coordinates of endpoints need not necessarily be integers, and developed some rules that can rescue from round-off errors. Rankin[5] has developed a recursive bisection line algorithm based on the fractal definition of the line, and showed that recursive nature of the algorithm results in fewer decisions being made in comparison with other algorithms. This resulted in this algorithm’s faster execution particularly with lines near to horizontal, diagonal or vertical. Although the algorithm does not produce a palindrome and on low resolution

0-7803-3636-4197 $10.00 0 1997 IEEE

THE NEW ALGORITHM

1280

22,

y2)

// X I , y l , 5 2 , y2 are respectively coordinates of the first and second end points of the line which makes a nonnegative angle not larger than 45 degrees with the x-axis.// inc = (Leftshift(y2-yl ,l6))/(x2-x1) yl = 2 k - 1 Y h = Y1

//variable y is a 2k bit number partitioned i n t o / / t w o ports

// yr

the lower k bits and yh t h e upper k bits. f o r x = X I to 2 2 do putpixel( 2 , y h ) y = y -k inc

endfor end NevLine

In order t o compare this algorithm with that of Bresenham’s we present the pseudocode of Bresenham’s algorithm in the following:

Procedure Bresenham(x1, y1,

XZ,

yz )

//XI, yl, x2, yz are respectively coordinates of the first and second end points of the line which makes a nonnegative angle not larger than 4 5 degrees with the x-axis.//

-

dx = ~2 XI d y = Y Z YI p = Leftshift(dy,f) t=p-dx q=t-dx Y = Y1 for x = X I to 2 2 do putpixel(x, y) if t 0 then y = y f l t = t + q else t = t f p endif endfor end Bresenham

It can be easily seen from the Bresenham’s algorithm that in the for-loop in addition to putpixel it requires one comparison (which also necessitates one jump operation), and one to two additions. On the other hand in the NewLine algorithm for-loop contains only a single addition operation in addition to the putpixel operation. Bresenham’s algorithm, in addition, requires 4 addition operations, one assignment and one shift operations, where as our algorithm has an overhead of a single integer division, two assignment and a shift operations. Considering the number of clock cycles required by each of these primitive operations time complexity of these two algorithms has been analyzed in the following section. 3.

PERFORMANCE ANALYSIS

Analyzing the assembly codes(1NTEL 386-DX) for both the algorithm we find clock cycle requirement for both the algorithm. Expression for proposed algorithm is 27dx+59 for Brazenham 46dx+5dy+62 clock cycle to calculate all pixel position of a line having dx horizontal and dy vertical movement.

1

proposed algorithm

dx= x2

- XI

100

I 3.6 ~

400 500 600 700 1000

I 400 I 5.76 11 4 1171 22 7 28 1 33 6 39 5 44 5 51.2 56 3

:bP3 13.8 17.2 20.6 24.1 27.5 30.9 34.3

Brezenham algorithm dy = ~2 - YI 600 700 800 5.98 6.04 6.15 11.7 11.9 12.1 17.6 17.9 18.2 23.4 23.8 24.2 29.3 29.8 30.3 34.9 35.6 36.1 40.9 41.7 42.5 46.0 46.8 47.6 52.9 53.8 58.8 60.0

900 6.26 12.4 18.5 24.6 30.9 36.8 43.2

-

From the above table it is clear that the Bresenham algorithm takes on the average 50% to 80% more computational time than the NewLine algorithm, where the first figure corresponds to the case of lines with slope 0.1, and the last figure to the case of lines with slope 0.9. We have also checked the computational time of the recursive bisection algorithm which takes more time than the Bresenham algorithm for lines with slope closer to 45 degrees, but for lines with angles closer t o 0 degree its computation time on the average is marginally better, approximately lo%, than the Bresenham’s. This shows that the NewLine algorithm is faster than the recursive bisection algorithm also. As our algorithm improve basic conversion(pixe1 position calculation) it is expected that it will improve all the algorithms that require those type calculation.

4.

CONCLUSION

From the above analysis it i s clear that performance of the Bresenham algorithm depends on the values of dy, and it takes time 50% to 80% more than that of the NewLine algorithm. Assembly code for the NewLine is smaller in length than that of the Bresenham’s code. So memory requirements for the NewLine is allso less. Hardware implementation for the NewLine will be much cheaper than the other algorithms. Only drawback of the proposed algorithm is in its single division operation. Since higher precision division operation is not required here, divider can be implemented by a very simple hardware. There are some other algorithms[5-61 that apply the technique used by Braxenham but calculate comparative fewer pixels. Our proposed technique can efficiently be used for the improvement of those algorithms.

REFERENCES [l] J.E. Bresenham. a Algorithm for computer control of a digital plotter.” IBM Systems Journal, vol. 4, no. 1, pp. 25-30, 1965.

The following table shows time requirements for both the algorithms while implementing in MASM assembly codes. Algorithms have been applied on each set of data 65536 times excluding putpixel overhead. If putpixel overhead is counted then some constant time will be added t o both the cases. From the experimental results and the complexity analysis it can be concluded that the Newline algorithm is always better Bresenham algorithm in terms of computation time.

Line algorithms for raster displays [2] Rudolf Borges. rescued from round-off Errors”. Computers and Graphics, vol. 15, no. 2, pp. 155-160, 1991. [3] C.M.A. Castle and M.L.V. Pitteway. An application of Euclid’s algorithm to drawing straight lines, In Fundamental Algornthms for Computer Graphics”. NATO AS1 series F: Computers and System Sciences,

In the table second column shows time requirement for the NewLine algorithm which is independent of dy. Other columns show time requirements for Bresenham algorithm that depends on dy for a given value of dx.

[4] W.M. Newman and R.F. Sproull. ‘‘ Principles for interactive computer graphics”. 3rd edn., McGraw-]Kill, NEW, pp. 22-27, 1981.

Springer-Verlag, 1985.

1281

[5] John R. Rankin. “ Recursive bisection line algorithm, Computers and Graphics”. vol. 15, no. 1, pp. 1-8, 1991. [6] I. G. Rokne, Brian Wyvile, Xiaolin Wu. Fast line scan conversion”. ACM transaction on grapgics vol. 9, no. 4, pp. 377-388, 1990.

1282