Abstract

Line is a very important primitive in computer graphics. In this paper we analyze and discussan algorithm that exploits the multi symmetry present in certain line segments during scan conversion. This feature is implemented with the simple technique of direct line equation; digital differentiation analyzer (DDA) algorithm and the floating-point operation free Bresenham's Algorithm. The benefit of exploiting this feature is clearly seen in the test results. Test results also show that by exploiting this feature, execution times of all these algorithms are very close, as the variations in these algorithms work for very small fraction of the line and the rest of the line is simply replicated from this pre-computation.

References

• Roy, P. A. , and Kaley, G. , Fundamentals of Computer Graphics, Schaum's Outline Series, International Edition.
• Graham,R. L. , Knuth, D. E. , Patashnik, O. , Concrete Mathematics, Addison-Wesley Publishing Company
• Bresenham, J. E. , Algorithm for computer control of a digital plotter. IBM Systems Journal 1965; 4(1): 25–30.
• Bresenham, J. E. , A Linear algorithm for incremental digital display of circular arcs. CACM 1977; 20(2): 100–6.
• Pitteway, M. L. V. , Algorithm for drawing ellipses or hyperbolae with a digital plotter. Computer Journal 1967; 10(3): 282–9.
• Van Aken Jr. , An efficient ellipse-drawing algorithm. CG&A 1984; 4(9): 24–35.
• Wu, X. and Rokne,J. G. , Double-Step Incremental Generation of Lines and Circles, Computer Vision, Graphics and Image Processing, 37: 331-334.
• Kappel, M. R. , An ellipse-drawing algorithm for faster displays. Fundamental algorithms for computer graphics, Springer, Berlin, 1985, pp. 257–280,.
• Van Aken Jr, Novak, M. , Curve-drawing algorithms for raster displays. ACM TOG 1985; 4(2): 147–69.
• Pang, A. T. , Line-drawing algorithms for parallel machines. IEEE Computer Graphics and Applications 1990; 10(5): 54–9.
• Wright, W. E. , Parallelization of Bresenham's line and circle algorithms. IEEE Computer Graphics and Applications 1990; 10(5): 60–7.
• Hasan, M. and Kashem, M. A. , An Efficient Line Drawing Algorithm, Proceedings of ICCIT'99, pp. 204-207.
• Karmakar, C. K. , Shams, S. M. S. , and Rahman, M. S. , Line Drawing Algorithm: A New Approach, SUST Studies, 2002, 4 (1): 65-69.
• Haque, A. , Rahman, M. S. , Bakht, M. , Kaykobad, M. , Drawing lines by uniform packing, International journal of Computers and Graphics, Elsevier, 30(1): 207-212, 2006
• Bond,C. ,A New Line Drawing Algorithm Based on Sample Rate Conversion, http://www. crbond. com/papers/newline. pdf, last visited on 07-12-2012.
• Kabir, M. H. , Hasan, I. , and Azfar, A. , An Improved Algorithm for Scan Converting a Line, Asian Journal of Information Technology 2005; 4 (9): 835-839
• Co-prime Integers, from Wikipedia, the free encyclopedia, http://en. wikipedia. org/wiki/Coprime_integers, last visited on 09-12-2012.
• Foley, J. D. , Andries van F, Steven, K. , Hughes J. F. , Computer graphics principles and practice, 2nd ed. in C, Fourth Indian Reprint, 2000, Addison Wesley Longman, Singapore