We present and study existing digital differential analyzer (DDA) algorithms for circle generation, including an improved two-step DDA algorithm which can be implemented solely in terms of elementary shifts, addition, and subtraction. 1. Introduction Digital interpolation algorithms are widely used in machine tools with numerical control, graphics displays and plotters, and manipulation robots. Circles and circular arcs frequently appear in computer graphics, computer-controlled printing, and automated control; see [1]. One of most popular methods for generation of circles and arcs is known as digital differential analyzer (DDA). Digital circular interpolators (or angular sweep generators) based on DDA approach are widely used [2–6]. There are many papers where characteristics research results of such interpolators are systematized [7, 8]. In this paper a new improved two-step algorithm for DDA circle generation is presented. In paper [9] the idea of applying a Nystrom two-step scheme to circle generation appeared for the first time. Our next paper [10] developed theoretical and geometric aspects of this method. In the present paper we focus on practical and experimental issues. Moreover, here we consider circles of arbitrary radius , while in [9, 10] we assumed . The accuracy of this method is higher than the accuracy of other known algorithms. Because of its simplicity (it uses only elementary shift, addition, and subtraction); this method can also be used in numerical control, planning mechanisms, and so forth. 2. DDA Algorithms The general class of DDA algorithms for circles generation is based on obvious trigonometric transformations describing rotation of vector in the coordinate plane - (Figure 1); Advantages of DDA algorithms include simplicity and high speed in generating circle point coordinate , . Figure 1: Rotation of vector in the coordinate plane - . Substituting , where is an integer (usually ), we rewrite (1) as which, obviously, can be expressed by a rotation matrix : To avoid expensive computation of trigonometric functions DDA algorithms use simpler (cheaper) expressions instead of and . For example, by replacing trigonometric functions by truncated Taylor series one gets so-called simultaneous DDA algorithms [3]. The determinant of the rotation matrix is 1. Matrices of DDA algorithms have different determinants and only approximately. The closer it equals 1 the more accurate is the corresponding circular interpolator [2]. Approximating and , we obtain the simplest (and least accurate) DDA algorithm [2, 11]: Much more accurate
References
[1]
W. Wang and C. Wang, “Difference method for generation of circular arcs and ellipses,” Computer-Aided Design, vol. 21, no. 1, pp. 33–37, 1989.
[2]
N. Matsushiro, “A new digital differential analyzer for circle generation,” IEICE Transactions on Information and Systems, vol. E81-D, no. 2, pp. 239–242, 1998.
[3]
I. Chami, “A high precision digital differential analyzer for circular interpolation,” Tishreen University Journal, vol. 29, no. 1, 2007.
[4]
H. Hama and T. Okumoto, “Fast transform into polar coordinate by generalized DDA,” Journal of the Institute of Television Engineers of Japan, vol. 47, no. 1, pp. 97–100, 1993.
[5]
X. Y. Fan, Y. H. Guo, and S. C. Li, “New digital differential analyzer interpolation algorithm,” Advanced Science Letters, vol. 6, no. 1, pp. 692–695, 2012.
[6]
X. L. Yan, W. L. Wang, and N. Xue, “Research and simulation of an efficient circular interpolation algorithm,” Advanced Materials Research, vol. 542-543, pp. 1204–1208, 2012.
[7]
O. Masory and Y. Koren, “Reference-word circular interpolators for CNC systems,” Journal of Engineering for Industry, vol. 104, no. 4, pp. 400–405, 1982.
[8]
Y. Katayama, H. Harasaki, and M. Yano, “Parallel algorithm of three dimensional digital differential analyzer,” in Proceedings of the Annual Convention ITE Japan, pp. 185–186, 1993.
[9]
L. V. Moroz, “A method for studying characteristics of digital sine-cosine generators,” Information Extraction and Processing, vol. 36, no. 112, pp. 84–90, 2012 (Ukrainian).
[10]
J. L. Cie？liński and L. V. Moroz, “Fast exact digital differential analyzer for circle generation,” http://arxiv.org/abs/1304.4974.
[11]
W. M. Newman and R. F. Sproull, Principles of Interactive Computer Graphics, McGraw-Hill, 1979.
[12]
F. S. Lim, Y. S. Wong, and M. Rahman, “Circular interpolators for numerical control: a comparison of the modified DDA techniques and an LSI interpolator,” Computers in Industry, vol. 18, no. 1, pp. 41–52, 1992.
[13]
R. F. Eschenbach and B. M. Oliver, “An efficient coordinate rotation algorithm,” IEEE Transactions on Computers, vol. 27, no. 12, pp. 1178–1180, 1978.
[14]
H. Hasegawa and Y. Okada, “Apparatus and method for controlling a moving vehicle utilizing a digital differential analysis circuit,” US Patent 5379353, 1995.
[15]
C. Pokorny Computer Graphics, An Object Oriented Approach to the Art and Science, Franklin, Beedle & Associates Publishing, 1994.
[16]
J. L. Cie？liński and B. Ratkiewicz, “On simulations of the classical harmonic oscillator equation by difference equations,” Advances in Difference Equations, vol. 2006, Article ID 40171, 2006.
[17]
J. L. Cie？liński, “On the exact discretization of the classical harmonic oscillator equation,” Journal of Difference Equations and Applications, vol. 17, no. 11, pp. 1673–1694, 2011.
