In the prior art, a painted pattern has generally presented on a digital display by: drawing the boundary of a pattern to be painted; discriminating between the area inside of the boundary, which is to be painted, and the area outside thereof, which is not to be painted, in accordance with the data read out from a display memory; and then painting the area inside of the boundary. An example, of such a method is disclosed in Japanese Patent Unexamined Published Application No. 142585/81. This method is time-consuming since it requires that data be read out from the display memory in series. Further, the painting of a pattern by such a method, which largely depends on the contents already drawn on a display screen, may often be interfered with by another pattern.
Another known method for displaying a painted pattern is a scan conversion method. This method is described, for example, in "Principles of Interactive Computer Graphics", W. M. Newman et al, McGraw-Hill 2nd Edition, 1979, pp. 232-243. In this method, all the intersections between the pattern to be painted and the scan lines constituting a display screen are obtained, and the spaces between the odd-even paired intersections are painted. FIG. 2 illustrates a typical example thereof. This method effectively utilizes the geometrical nature of the pattern to be painted to enable the painting to be executed independently of the data stored in a display memory, resulting in its improved processing speed. It is essential to improvement of the scan conversion method to improve the efficiency in the calculation of intersections while retaining its high accuracy.
The present invention is directed to the scan conversion method, and introduces a new concept in generating a circular or elliptic arc in order to solve the problems of accuracy encountered in the past.
In the prior art, several efficient methods have been proposed for drawing a circle with a designated center and a designated radius (or an ellipse with a designated center and designated major and minor axes) with high accuracy without employing the calculation of functions such as trigonometric functions.
One of the methods involves moving a point incrementally from a starting point to a terminating point in order to obtain a desired line segment. The incremental movement of the point may, for example, take the form of a movement from one picture element (hereinafter referred to as a pel) to any one of the neighboring pels at the angular positions of 0, 90, 180, and 270 degrees. This combination is called "4-connected pels". The incremental movement may also be made from one pel to any one of those at the angular positions of 0, 45, 90, and at 45 degree intervals to 315 degrees. This combination is called "8-connected pels." In selecting the next pel to which the movement is to be made, a test is performed to select two or three neighboring pels as candidates. Then, the distances between each of the candidates and the actual line segment concerned are obtained and the pel with the smallest distance therebetween is finally selected. Such a method is described in "A Linear Algorithm for Incremental Digital Display of Circular Arcs" , J. E. Bresenham, Communications of the ACM, 20 (2), February 1977, pp. 100-106, for example. Although the basic concept of such a method may be applied for painting a circular or elliptic arc by the scan conversion method, such an application must be modified in order to eliminate some problems of accuracy as explained below.
For example, when a circle is generated with 4-connected pels, a series of points as shown in FIG. 3 are obtained. Now consider the case of painting using a series of points generated counterclockwise from a point x=r on the x-axis. As understood from FIG. 2, in the case of the scan conversion method, only one point is required to be generated at the intersection of each scan line and the curve concerned. Therefore, when a plurality of points are generated on one scan line at such an intersection, it is necessary to select one of them. For example, if the points displayed in the y-axis direction are selected, the points as shown in black in FIG. 4 are selected. (The points shown with double circles must be added in accordance with the sign of differential in the y-axis direction, so that an even number of points always exist on one scan line). It will be seen that this results in producing a distorted circle rather than a true circle. The more vertically depressed is an ellipse of the pattern to be displayed, the more significant effect would be produced (FIG. 6).
Considering the symmetry of a circle, assume that a series of points only in the first quadrant (quarter circle) are generated actually and the coordinates of the points in the other quadrants are obtained only by inverting the sign of the coordinates of those in the first quadrant. With this method, it is possible to obtain paired points immediately after the generation of each point and to paint the space between the paired points, resulting in the reduction of the processing time. This method enables the obtaining of a symmetrical pattern. However, the obtained circle would be depressed vertically (FIG. 5).
The foregoing method would not provide a good solution to the aforementioned problems and some other modification would be required to obtain a highly precise scan conversion of a circle or ellipse. The best method therefor would be to obtain a single point nearest to each of the intersections between a circle and each scan line, sequentially. However, in order to obtain such points directly from the equation of a circle, ##EQU1## it is necessary to calculate square roots.
Another known method for generating a circle conveniently is the DDA (Digital Differential Analyzer) method, which is described in the before mentioned "Principles of Interactive Computer Graphics", W. M. Newman et al, pp. 27-28, and referred to below briefly.
Referring to FIG. 7, assume a point p.sub.k (x.sub.k, y.sub.k) located on the circumference of a circle with a radius r has been obtained. The movement of the point by .DELTA..theta. from the point p.sub.k counterclockwise on the circle to point p.sub.k+1 (x.sub.k+1, y.sub.k+1) is expressed by the following formulae: ##EQU2## Assuming that .DELTA..theta. in the above formulae is a minute angle, cos .DELTA..theta.=1 and sin .DELTA..theta.=.DELTA..theta.. Further, assuming .DELTA..theta.=e=2.sup.-m (m is a positive integer), the following formulae are obtained: EQU x.sub.k+1 =x.sub.k -ey.sub.k [ 3] EQU y.sub.k+1 =y.sub.k +ex.sub.k [ 4]
wherein 2.sup.m-1 .ltoreq.r.ltoreq.2.sup.m. However, the x.sub.k in the above formulae (4) must be substituted for by x.sub.k+1 in order to prevent a diversion, and the following formulae are obtained. EQU x.sub.k+1 =x.sub.k -ey.sub.k [ 5] EQU y.sub.k+1 =y.sub.k +ex.sub.k+1 [ 6]
It has been ascertained that the values of a true circle can be obtained from the foregoing formulae [5] and (6).
It has already been proposed to apply the DDA method to the scan conversion method, as disclosed, for example, in Japanese Patent Unexamined Publication Application No. 206884/84. However, in this case, a plurality of points are generated at the intersection of a scan line and the curve concerned, resulting in the same problem as in the case of the above-mentioned incremental digital display. The above-mentioned Japanese Patent Unexamined Publication Application No. 206884/84 does not refer to such a problem.
As a consequence of the foregoing known difficulties in the prior art, it is in an object of the present invention to provide a method for generating a circular or elliptic arc, which is adapted for the scan conversion method without the necessity of calculating trigonometric functions and square roots.