An efficient algorithm for the dot generation of arbitrary ellipses
Goro Koda, Kensuke Shimizu · Systems and Computers in Japan · 1986
Abstract This paper presents an algorithm which provides a high‐speed dot representation of an ellipse on the raster‐scan graphic display device. In the usual graphic display, straight‐lines and circles are used as the graphic primitives. In the three‐dimensional graphics, a projection on the two‐dimensional plane is often employed where a circle is in general projected as an ellipse. When a curve with rapidly varying curvature is to be represented, the approximation can be effected by a fewer number of components if ellipses are used instead of circles. From such viewpoints, an efficient generation algorithm for the ellipse is required. The ellipse considered in this paper need not have the long or short axis parallel to the coordinate axis. The lengths of the long and the short axis are arbitrary, and the correct dot generation is observed for an extremely oblong ellipse. The location of each dot is determined so that the deviation from the ellipse is small. Sometimes the past method does not work due to the fact that the ellipse is a two‐valued function. By contrast, this paper contains a simple scheme to convert the ellipse into a single‐valued function. To improve the speed of the algorithm, only addition‐subtraction and conditional test are used in the internal loop determining the dot location.