An Efficient Algorithm for Generating Slanted Ellipse Using Simultaneous Recurrences

Munetoshi NUMADA  Hiroyasu KOSHIMIZU  Yasuyo HATANO  Takayuki FUJIWARA  Takuma FUNAHASHI  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E94-A   No.6   pp.1458-1463
Publication Date: 2011/06/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E94.A.1458
Print ISSN: 0916-8508
Type of Manuscript: PAPER
Category: Computer Graphics
ellipse generation,  simultaneous recurrence,  three-term-recurrence,  

Full Text: PDF(754KB)>>
Buy this Article

Thus far, there have been many reports and publications on the algorithm for the efficient generation of a circle or an ellipse by the parametric method. In this parametric method, we compute a trigonometric function only at the time of setting the initial condition for generating graphics incrementally using the recurrence formula consisting of the arithmetical operations of addition, subtraction, and multiplication in the main loop. This means that the key to the faster generation of a circle or an ellipse is to reduce the number of multiplication operations. In the conventional methods, the numbers of multiplication operations required to generate a single point each for a circle and an ellipse are three and four, respectively. However, in this paper, we propose a method that makes it possible to generate a slanted ellipse by performing only two multiplication operations per point. The key to this is to use simultaneous recurrences. The proposed method allows a simpler initial setup than any of the conventional methods, thus performing the computation more efficiently. In addition, the new method proposed here causes no theoretical errors, with the rounding error being similar to or less than that of any conventional method.