JPH0425983A - Graphic plotting device - Google Patents

Abstract

PURPOSE:To plot the thick line of a correct circular arc at high speed by dividing the circular arc into closed area parts capable of being represented by two straight lines and two monotonously decreasing curves, and painting out every closed area part by one line unit successively from an upper part to a lower part. CONSTITUTION:In the processing of a first partial arc ABCD, since the point of the maximum Y-coordinate is A, digital differentiation (DDA) generation is executed by making the circular arc AB a left-hand side and a segment AD a right-hand side. The initial value of Y is Y-coordinate of A. An interval between the point x1 on the circular arc of the left-hand side and the point x2 on the segment of the right-hand side is plotted in a horizontal line. This operation is continued until Y-coordinate generated by this DDA generation becomes the value of the point of the larger Y- coordinate between the point B and D. After the processing up to the point D is finished by the DDA generation, the DDA generation of the right-hand side is changed to the circular arc DC. After the DDA generation is executed up to the point B similarly to the above-mentioned operation, this time, the DDA generation of the left-hand side is changed to the segment BC. As for the partial arc ADFH and the partial arc EFHG too, plotting in the partial arc can be executed through the similar operation.

Description

[Detailed Description of the Invention] [Industrial Application Field] The present invention relates to a graphic drawing device for displaying or printing figures and characters on a display or printer, and in particular, relates to a graphic drawing device that displays or prints figures and characters on a display or printer, and in particular,
The present invention relates to a graphic drawing device having a function of drawing linear figures such as circular arcs with thick lines.

[Conventional technology]

In recent years, the display resolution of personal computers and workstations has been increasing year by year, and 1280
x1024 dots were becoming popular. This is 1 mm
It is about 5 dots per area.

Meanwhile, in the world of printers, higher resolution is progressing. Laser beam printers use 400 dpi (do
t per 1 nch), that is, the standard is about 16 dots per order. There is a trend toward higher resolution in order to display or print characters and figures more clearly, but on the other hand, the basic l-bot width lines feel very thin, so it is difficult to use line widths of 2 dots or more. Line figures with so-called thick lines are an essential feature.

Typical examples of thick lines include straight lines, circles, and arcs, and since straight lines are simpler than other shapes, high-speed drawing methods have been devised. In contrast to straight lines, the algorithm for including curves becomes complicated for circles and arcs. A conventional drawing method for circular arcs will be described below.

Conventional methods for drawing thick lines of circular arcs include a method using filling called seed fill, and a method using overwriting of circular arcs. The seed fill method first draws an outer circumferential arc and an inner circumferential arc, and then fills in the closed area formed by connecting the end points of both arcs with line segments. Seed fill is a method that takes a certain point within a closed area as a reference point, searches for boundary points in the vertical and horizontal directions from that point, and fills only within the boundary, that is, within the closed area. It is mainly applied to filling in arbitrary closed areas.

Seed fill is generally slow, but it is often used because it can draw accurately under certain conditions and can fill in any pattern. On the other hand, in overwriting circular arcs, a circular arc whose radius is shifted by l is drawn repeatedly by the number of dots of the line width. At this time, the single line of each arc is calculated so that it lies on the line segment connecting the end point of the outer circle and the center point of the circle. Since this method is based on a 1-bit wide arc, which is increasingly being implemented in hardware, it can be drawn at high speed.

[Problem to be solved by the invention]

The conventional thick line drawing as described above has the following problems.

First, there is a problem that seed fill cannot be applied when some figure has already been drawn in the memory to be drawn and this figure contains a border color. In other words, the outline of the arc is first drawn, but if the background image within this thick outline contains a border color, it may not be possible to search properly. It becomes impossible to distinguish between the true boundary color and the false boundary color. Furthermore, it is necessary to specify an internal reference point for the seed fill, and the process to obtain this point may become complicated.

For example, a point inside the outline of a 3-bit wide arc is at most 1 bit wide, and the procedure for finding the reference point changes depending on the angle of the arc, so this calculation takes time, and in the worst case, the end points are 2 bits wide. bit width, and it may be difficult to find internal points.

Furthermore, with a width of about 3 bits, the outer circumferential arc and the inner circumferential arc may touch in the middle, and the closed area may be divided at this point, making it impossible to draw correctly.

In the case of overwriting, a problem arises in that some points inside the thick line are left unpainted. This is because the coordinates of the coordinate plane to be drawn are based on discrete lattice planes. The discrete lattice planes are an essential problem with the rask scan method, in which one bit in memory corresponds to one pixel on the display. Therefore, even when drawing a thick line with a width of n dots, missing dots are prevented by performing drawing n+α times. However, predicting which dots will fall out and drawing α times requires complex calculations, and it has not been possible to fill the arc with a predetermined pattern.

The purpose of the present invention is to be able to accurately form the shape of the end point of an arc into a straight line, regardless of the presence or absence of a background, the thickness of the line, the length of the arc, etc. The purpose is to provide a graphic drawing device that can.

[Means to solve the problem]

For the above purpose, the figure drawing device of the present invention has a function of drawing an arc with a width of 2 bits or more formed by an outer circumference circle, an inner circumference circle, and two line segments on a memory defined by XY coordinates. A graphic drawing device comprising: dividing means for dividing the arc into a portion included in the left half of the circle and a portion included in the right half of the circle; and an arc included in the left half or an arc included in the right half of the circle. , coordinate generation means for calculating XY coordinates for each line along the outer circumferential circle, the inner circumferential circle, and the two line segments or a perpendicular line passing through the center of the circle;
The apparatus includes a drawing means for rewriting the contents of the memory corresponding to the two X coordinates on one line calculated by the coordinate generating means.

That is, the present invention divides an arc into closed area parts that can be expressed by two straight lines and two monotonically decreasing curves, and fills each closed area part sequentially from top to bottom line by line. 2 of the line segments to be drawn on the line of
Introducing new ideas such as finding the X coordinate of two end points and speeding up the X coordinate generation by using hardware called a digital differential analyzer, and drawing accurate thick lines of arcs at high speed. be able to.

〔Example〕

Next, a first embodiment of the present invention will be described in detail with reference to the drawings.

The first embodiment is a graphic drawing device that draws thick circular arcs.

FIG. 1 is a block diagram of the hardware configuration of this embodiment,
FIG. 2 is a process procedure for drawing an arc, FIG. 3 is an explanatory diagram of dividing an arc, and FIG. 4 is a diagram showing a specific example of drawing an arc.

First, the procedure for drawing an arc according to the present invention will be explained using FIG. The major steps are: ■ Calculation of the coordinates of the end points of the outline of the arc, ■ Processing of dividing the arc into the left semicircle and the right inner half, ■ Generation of the X coordinate of the intersection of the scan line and the outline, ■
Processing proceeds in the order of scan line drawing.

I will talk about ■. The arc information includes the radius, width (thickness), starting point angle, and ending point angle of the arc. The radius of the outer circumferential circle and the radius of the inner circumferential circle are determined from the radius and width of the circular arc, and the starting point coordinates and end point coordinates of the outer circumferential circle and the inner circumferential circle, respectively, are determined from the starting point angle and the end point angle. As for the radius of the outer and inner circles, the given radius is the center line of the arc, so the radius of the outer circle is the sum of half the width, and the radius of the inner circle is the radius of the half of the width. . The starting point and ending point can be easily calculated from their respective angles and radii.

The division in (2) is performed as follows. Check whether the arc straddles the left semicircle and the right semicircle using the starting point angle and ending point angle. Here, the first and fourth quadrants are right semicircles, and the second and third quadrants are left semicircles. Figure 3 shows the combination of arc divisions. The arc is divided into a maximum of three parts. The processes ``■'' and ``■'' are performed for each divided arc.

The coordinate generation in (2) will be explained. The filling process is ■
Since this is done by so-called scan line fill, which draws a horizontal line line by line, the coordinate generation involves changing the X coordinate one by one and finding the X coordinates of the two left and right sides at that time. First, the end point having the maximum X coordinate among the four end points that determine the divided circular arc is determined. This can be easily determined by the positions of the starting and ending quadrants.

For example, if the start point is in the first quadrant and the end point is in the fourth quadrant,
The maximum value of the X coordinate can be determined at the starting point of the outer circumferential circle. Since the line segment with this point as the end point, that is, the line segment and arc connecting the starting points of the outer circumferential circle and the inner circumferential circle, that is, the outer circumferential circle, is determined, by generating the coordinates of this line segment and arc for each line. The intersection with the scan line is calculated. This process is repeated until the end point of either the line segment or the arc is reached.

When the processing is completed to any end point, the processing is continued using that end point as the starting point of a new left side or right side.

In other words, when the coordinate generation reaches the end point, processing is continued by switching to the next line segment or circular arc.

The reason why the coordinates can be calculated through such simple processing is that the arc increases monotonically in the Y direction. In other words, it is divided in advance using the process (■) so that it increases monotonically.

(2) is a process of drawing the distance between the two X-Shobara obtained in (2). This is a simple straight line drawing, and since it is a horizontal line, it can be easily realized.

The above is an explanation of the arc drawing procedure of this embodiment. Next, the actual operation of the hardware will be described based on FIG. In FIG. 1, l is a register file, 2 is a control section, 3 is a left side DDA generation section, 4 is a right side DDA generation section, and 5
6 is an address calculation section, and 6 is a scan line drawing section.

Parameters such as the radius, width, starting point angle, and ending point angle of the circle are stored in register file 1. The contents of the register file 1 are controlled by the M unit 2, and the coordinates of the end points of the outline of the arc described above are calculated. Next, the arc is divided based on the starting point angle and end point angle of the arc, and among the line segments and the end points of the arc that form the outline of the divided arc, the line segment and the arc that include the end point with the maximum X coordinate are digitally calculated. An initial value of a differential analyzer (hereinafter abbreviated as DDA) is calculated.

The above processing is the operation of the control section 2. Furthermore, the control unit 2
The left-side DDA generation section 3 and the right-side DDA generation section 4 sequentially generate the X coordinates on each line segment and arc by inputting the DDA initial value generated in the above. The algorithm for generating DDA for straight lines and circular arcs is generally well known and has been implemented in hardware, so a detailed explanation will be omitted. The address calculation unit 5 inputs the output coordinates of the left-side DDA generation unit 3 and the right-side DDA generation unit 4 and performs preprocessing for drawing scan lines, that is, calculation of the starting point address and the number of dots to be drawn.
It is.

The scan line drawing unit 6 is basically a part that executes horizontal line drawing, and its hardware configuration is well known, so a description thereof will be omitted.

Now, the explanation above has focused on the algorithm and hardware operation. Here, further explanation will be given using a specific example based on FIG. As shown in Figure 4, the starting point is in the second quadrant and the ending point is in the third quadrant, and the arc BCE is clockwise.
Given G, it is divided into three subarcs. First, the first partial arc ABCD is processed. The point with the maximum X coordinate is A, so with the arc AB on the left side and the line segment AD on the right side, D
Performs DA generation. The initial value of Y is the point Al7) X coordinate.

DDA generation is a calculation that calculates the X coordinate on an arc or line segment when the X coordinate is subtracted by 1 based on the X coordinate. A horizontal line is drawn between the point X1 on the arc on the left side and the point X2 on the line segment on the right side. Note that in this case, X2 is the same as the X coordinate of point A. This continues until the X coordinate generated by this DDA generation reaches the value of point B or the point with the larger X coordinate.

Now, when the processing is completed to the point due to the occurrence of DDA,
Change the DDA generation on the right side to arc DC.

Similar to the above operation, when DDA generation is performed up to point B, the DDA generation on the left side is changed to line segment BC. In the manner described above, the processing of partial arc ABCD is completed. partial arc A
Regarding the D F H1 partial arc EFGH, the inside of the partial arc can be drawn using similar processing.

Next, a second embodiment of the present invention will be described with reference to the drawings. The second embodiment is a graphic drawing device that draws straight lines.

FIG. 5 is a diagram showing a specific example of straight line drawing.

The thick straight line is easier to process than the circular arc in the first embodiment, so it can be realized with the same hardware. A thick line is basically a rectangle, and the order of the four vertices can be determined by the starting and ending positions, so there is no need to divide it into multiple parts as in the case of a circular arc.

A specific example will be explained using FIG. The thick straight line is defined by rectangle PQR8. Compare the X coordinates of these four points,
Draw the point P with the maximum X coordinate.

Next, two line segments with point P as the end point are extracted.

In the case of a straight line, it cannot be determined by simple calculation which of point R and point Q is on the left side. Therefore, the DDA is generated unconditionally, and the left and right sides are identified by comparing the generated X coordinates. In addition, in the case of the circular arc of the first embodiment,
It is possible to easily determine whether the left side is an arc or a line segment. This means that the quadrant in which the starting point or ending point exists is given by the starting point angle or the ending point angle, and if the quadrant is known, it is possible to uniquely determine whether the left side is a line segment or an arc.

The subsequent processing is similar to the case of circular arcs, and when one DDA generation is completed, the information on the side is updated and continued.

〔Effect of the invention〕

As described above, according to the present invention, it is possible to create an arc of any width, angle, and length in an accurate shape and at high speed. Furthermore, regarding the fill pattern,
It is also obvious that this can be easily realized by calculating the pattern reference position of the scan line drawing portion and setting the drawing reference data to arbitrary data.

The present invention can be applied not only to circular arcs and circles, but also to straight lines as shown in the second embodiment. Furthermore, it can be easily inferred that a fan shape can be drawn when the radius of the inner circle is set to 0'', so the range of applications is wide.Also, in order to realize so-called line types such as broken lines and single-point button lines, This can be realized by generating a sequence of arcs using higher-level software and executing the arcs one by one using this graphic drawing system.

[Brief explanation of drawings]

Fig. 1 is a block diagram of the hardware configuration, Fig. 2 is the processing procedure for arc drawing, Fig. 3 is an explanatory diagram of arc division, Fig. 4 is a diagram showing a specific example of arc drawing, and Fig. 5 is a straight line. This is a specific example of drawing. In FIG. 1, 1...Register file, 2...Control unit, 3...Left side DDA generation unit, 4...
・Right side DDA generation section, 5...address calculation section,
6...Scan line drawing section. Agent Patent Attorney Shinyo Uchihara 4th father-in-law

Claims (1)

[Claims] A graphic drawing device having a function of drawing an arc with a width of 2 dots or more formed by an outer circumferential circle, an inner circumferential circle, and two line segments on a memory defined by XY coordinates,
dividing means for dividing a circle into a part included in the left half and a part included in the right half; and dividing means for dividing a circle into a part included in the left half and a part included in the right half; a coordinate generating means for calculating XY coordinates for each line along a vertical line passing through the center of two line segments or a circle, and a correspondence between two X coordinates on one line calculated by the coordinate generating means; 1. A graphic drawing device comprising: drawing means for rewriting the contents of a memory.