JPH03144867A - Method and device for plotting straight line - Google Patents

Abstract

PURPOSE:To improve plotting speed by deciding the number of dots to be generated on a next scan line from the accumulated result of the error from an ideal straight line and generating plural pieces of the dots at the same time on one scan line on the basis of the result of this. CONSTITUTION:The basic number N of the dots to be generated on one scan line is obtained by an arithmetic part 11 on the basis of the inclination of the ideal straight line to be generated to the scan line, and the error between the position of the generated dot and the ideal straight line is accumulated at every shift of the scan line, and from this accumulated result, it is decided whether the number (n) of the dots to be generated on the next scan line is either N or N+1, or either N or N-1. Then, the dots of the number corresponding to a decided result are generated at a time by the word width unit of a generating accumulator 12, and are stored in a bit map memory 3. Thus, the plotting speed can be improved.

Description

DETAILED DESCRIPTION OF THE INVENTION (Field of Industrial Application) The present invention relates to a method and apparatus for drawing straight lines in dot-type plotters, printers, displays, etc.

[Conventional technology]

When performing graphical processing using blocks, word processors, personal computers, etc., the graphic must be expressed as a dot pattern.

In the conventional method of forming a straight dot pattern on the dot pattern forming surface (which may be virtual) of such an apparatus, for example, the inclination angle d with respect to the X axis is 0''<
When forming a straight line with d<45°, as shown in Fig. 7, a point DI (XI +1.)'l) is moved by one point in the X-axis direction with respect to the determined dot D0(x,,y,). and X
Point D2 (XI
10t, y+ +1), and these points D+,
The error between Dz and the ideal straight line l is determined, the point with the smaller error is determined as a drawing point, and a dot is generated there. Thereafter, a dot pattern for representing the straight line 1 is formed in the same manner.

However, in the above method, calculations after the decimal point are difficult, so as an improved drawing method, r Bres
A method called enhara's line drawing algorithm j is widely known. Regarding this ``Bresenham's line drawing algorithm'', please refer to the magazine ``rpr
stated on the page.

[Problem to be solved by the invention]

Both the above-mentioned method and Bresenham's line drawing algorithm had the problem that calculations had to be made for each point in order to draw a line, which resulted in an enormous amount of drawing time. .

This means that, for example, when a microprocessor calculates Fti pixels and writes them to an image memory (bitmap memory), the microprocessor calculates a predetermined data bit width (for example, 8 bits on an 8-bit computer;
This is called the word width. ) Although data is written and read every 1 bit, the calculation of the drawing point is performed every 1 bits, resulting in extremely low efficiency. In particular, in the case of a straight line where the inclination of the dot pattern formation surface with respect to the X-axis or Y-axis is small, it is necessary to generate a large number of dots within one word width, resulting in a significantly poor efficiency.

Therefore, an object of the present invention is to provide a straight line drawing method and apparatus that improve drawing speed.

(Means for Solving the Problems) The present invention provides that, among the X-axis and Y-axis of the dot pattern forming surface,
If the scan line is set parallel to the axis with the smaller inclination to the straight line to be formed, the number n of dots to be generated on the same scan line is basically N and N+1 (
You can think of them as N and N-1. This was done based on the fact that there are only two types:

This fact will be explained using FIGS. 4 and 5.

Figure 4 shows a dot pattern for expressing a straight line with a slope of 3/IO, and the number of dots generated on the same horizontal scan line is 3 or 3, except for the areas near the starting point a and the ending point A. It is 4. Also, in Figure 5, the slope is 7/30.
This is a straight line dot pattern, and the number of dots generated on the same horizontal scan line is 4 or 5. In this way, the number of dots generated on the same scan line when drawing a straight line is N and N + 1 (where the smaller number is N), excluding the areas near the start and end points (where the larger number is N). For example, there are only two types: N and N-1).

Therefore, in the straight line drawing method of the present invention, as shown in FIG. 1, scan lines parallel to one side of the matrix of dot generation points constituting the dot pattern forming surface are sequentially shifted in a direction perpendicular to the scan lines. Then, a predetermined straight line pattern is formed on the dot pattern forming surface, and at this time, the basic number of dots to be generated on one scan line is determined based on the slope of the ideal straight line to be formed with respect to the scan line. N is calculated, the error between the position of the generated dot and the ideal straight line is accumulated for each shift of the scan line, and from the cumulative result, the number n of dots to be generated on the next scan line can be calculated as follows. It is determined whether it is N or N+1 or the above-mentioned N or N-1, and a number of dots according to the result of this determination are provided corresponding to a predetermined word width. The data is generated in a buffer register 104, and the contents of this buffer register 104 are transferred to a bitmap memory 106 provided corresponding to the matrix of the dot generation points.

At this time, it is preferable to set the basic number N of dots to be the integer part of the reciprocal of the slope Δy/Δx of the ideal straight line.

The linear drawing device of the present invention used in the above method includes: a bitmap memory 106 which has a bitmap corresponding to a matrix of dot generation points and is written and read in units of a predetermined word width; scan line shifting means 107 for shifting a scan line parallel to one side of the matrix of points in a direction perpendicular to the scan line; A basic dot number calculation means 101 that calculates the basic number N of dots to be generated; and an error between the position of the generated dots and the ideal straight line is accumulated for each shift of the scan line, and from the cumulative result, the following calculation is performed. A dot number determining means 102 for determining whether the number n of dots to be generated on a scan line is between N and N+1, or between N and N-1, and a bitmap memory. A buffer register 104 provided corresponding to the word width of 106, a dot generating means 103 for generating a number of dots in the buffer register 104 according to the determination result by the dot number determining means 102, and It has a transfer means 105 for transferring data to a virtual machine memory 106.

It is preferable that the basic dot number calculating means lO1 is such that the basic dot number N is the integer part of the reciprocal of the slope Δy/Δx of the ideal straight line.

[Effect]

In the present invention, first, the number N of dots to be generated on the same scan line is determined from the slope of the ideal straight line to be formed, and each time the scan line is shifted,
The errors between the positions of the dots that have already been generated and the ideal straight line to be formed are accumulated, and from the cumulative result, the number n of dots to be generated on the next scan line is determined by the number n of dots to be generated on the next scan line.
1, or between N and N-1.

Therefore, it is possible to generate a plurality of dots simultaneously on one scan line based on the determination result, which makes writing to the bitmap memory 106 performed in units of a predetermined word width more efficient. It works well and improves drawing speed.

〔Example〕

DESCRIPTION OF THE PREFERRED EMBODIMENTS The present invention will be described below with reference to embodiments and drawings.

FIG. 2 is a block diagram showing the configuration of a straight line drawing device according to an embodiment of the present invention.

This linear drawing device includes a central processing unit (CPU) 11, a ROM 2 in which a microprogram is stored, a bitmap memory 3, and a dot pattern forming surface corresponding to the bitmap, for example, in the Y-axis direction as shown in FIG. A counter 4 for determining the position, an accumulator for X-coordinate position determination (X-ACC) 5 for calculating the position of the dot pattern forming surface in the X-axis direction, a data bus 6, and an output device 7 such as a block. It has an interface (Ilo) 8 between it. Specifically, the CPU includes an arithmetic unit (ALU) 11 and an accumulator (ACC) 12 for dot generation, which has the function of a buffer register.

In the following explanation, the horizontal (X
A straight line is drawn on a dot pattern forming surface of 32 dots (in the axial direction) and 16 dots in the vertical direction (Y-axis direction). In the case of this embodiment, since the bitmap memory 3 is accessed 8 bits at a time, as shown in FIGS. 4 and 5,
The dot pattern formation surface of 32 x 16 dots is divided into four in the X-axis direction, with rows A, B, 0, and D arranged in the order of "oo".
.

Sixty-four addresses from O11 to "003F" are allocated in the bitmap memory 3 (see FIG. 6). In the example in Figure 4, from the starting point (0,0) to the ending point (
In the example shown in FIG. 5, a straight line is drawn from the starting point (0, O) to the ending point (30, 7).

Next, the straight line drawing method of this embodiment will be explained with reference to the flowchart of FIG. 3 showing the operation of the CPUI.

First, the calculation unit 11 calculates the slope of the straight line to be drawn by Δy/Δ
The basic number N of dots is calculated from x. In this embodiment, this basic number N of dots is obtained from the following equation.

N=INT(ΔX/Δy) −·−(1) That is, the integer part of the reciprocal of the slope of the straight line Δy/Δx becomes the basic number N of dots. In the example shown in Figure 4, 1 point of the straight line is 371O
Therefore, N is 3. Also, in the example in Figure 5, the slope is 7.
730, so N is 4.

Next, the starting point of the straight line is drawn, that is, dots are generated on the first scan line. In this example, the scan line is set parallel to the X axis of the dot pattern forming surface, and in the examples shown in FIGS. 4 and 5, the starting point a
is (0, O), the first scan line for dot generation is the y-0 scan line. This start point drawing and later end point drawing are based on the basic law that in the vicinity of the start point and the vicinity of the end point of a straight line, the number n of dots to be generated on the same scan line is either the basic dot number N or N+1 described above. does not hold, so it is necessary to do it separately.

Dots are generated on this first scan line until the y-coordinate of the ideal straight line 2 to be WI drawn is closer to the next scan line, that is, 7-0 in the example of FIGS. 4 and 5.
．． If Δχ/2Δy is not divisible, the number n that must be repeated until the number exceeds 5 is: n=INT(Δx/2Δy) +1−(2)Δχ/
If 2Δy is divisible, n-Δx/2Δy·−(2)′. In the example of FIG. 4, n=2, and in the example of FIG. 5, n=3.

Therefore, for example, in the example shown in Figure 4, (0,0) and (1,0
), a code "1100" is applied to the dot generation accumulator (ACC) 12 in FIG.
0000” and stores it in bitmap memory 3.
This dot generation accumulator (see Figure 6) is transferred to the address "oooo" where the starting point of the straight line exists (
When the LSB of the code generated in ACC) 12 reaches "°0", it means that the dot generation on that scan line has finished, so the counter 4 in Fig. 2
=3'+1, the scan line is shifted by one, and dots are generated on the next scan line.

In order to generate dots on scan lines after y-1, it is necessary to determine whether the number n of dots to be generated on that scan line is the basic number N or N+1.

When the basic number N of dots is defined as in equation (1) above,
It is the decimal part of ΔX/Δy that is accumulated as an error between the generated dot position and the ideal straight line l. Therefore, the calculation unit 11 adds the decimal part of ΔX/Δy every time the scan line is changed by l, and sets n=N until the value exceeds 1.0, and when it exceeds 1.0, So n=N
+1.

Specifically, when y=0.5, the value of is used as the initial value of the judgment variable E, and the error from the ideal straight line i is calculated as CC, -<ΔX/Δy) -N −・−(4)
, the error G is added to the above judgment variable every time the scan line is changed by one. Then, until this judgment variable E exceeds 1, the basic number N of dots is output as the number n of dots to be generated on that scan line, and E becomes 1.
When it exceeds n=N+1.

After E>1, the error G is G1G! -(ΔX/Δy)-N-1...-(5),
Every time the scan line is changed by one, the error Gt is added to the determination variable. Then, while E>1, N+1 is output as the number n of dots to be generated on the scan line, and when E becomes smaller than 1, the error G is set to G+
Return to

That is, while the judgment variable E is smaller than 1, G is added as an error to the judgment variable every time the scan line changes by 1 until the judgment variable E exceeds 1, and G is generated on the scan line. Let the number n of power dots be N
On the other hand, while the judgment variable E is larger than 1, G2 is added as an error to the judgment variable E every time the scan line changes l until the judgment variable E becomes less than 1. The number n of dots to be generated on the scan line continues to be determined as N+1.

According to this method, in the example of FIG. 4, the basic number of dots generated on the scan line of y=1 is 3, so the dot generation accumulator (AC
C) Generate code "0O111000" in bitmap memory 3 and write it to address "0004" of bitmap memory 3.
(See Figure 6). At this time, in the code generated by the dot generation accumulator (ACC) 12, the bit position f (3rd bit from the left on the y-1 scan line) at which "1" rises indicates the number of generated dots in the X-axis direction. X to accumulate and calculate its position
The coordinate position is determined using an accumulator (X-ACC) 5. That is, in this X-coordinate position determination accumulator (X-ACC) 5, the number of dots that have already been generated is accumulated, and the accumulated value is divided by the word width (8 in the case of this embodiment), and the remainder R is calculated. The next bit position is determined by the CPU 1 as the bit position at which "'1" in the dot generation accumulator (ACC) 12 rises.

As in the case of the scan line of y=o described above, this y
-i scan line as well, dot generation on this scan line ends when the LSB of the code generated in the dot generation accumulator (ACC) 12 turns on, so as shown in FIG. The counter 4 sets )'=)'+1 to shift the scan line, and then generates a dot on the y-2 scan line.

Since the determination variable E exceeds 1 when the scan line moves to y=2, the number of dots to be generated on the scan line at y=2 is 3+1=4. Therefore, "1" was set to 4 in the dot generation accumulator (ACC) 12.
In this case, "°1" determined by the X-coordinate position determining accumulator (X-ACC) 5
Since the rising bit position is the 3rd bit from the LSB, it is not possible to set up 4 "1 degrees". Therefore, the dot generation accumulator (ACC) 12 is
A code ``00000111'' consisting of ``1'' is generated and transferred to the address ``ooos'' of the bitmap memory 3, as shown in FIG. It is determined that the dot has moved in the X-axis direction and entered the area of column B, and the code "10000000" with only the remaining 1 bit set to "1°" is generated in the dot generation accumulator (ACC) 12, and this is Transfer to address "0009" of map memory 3.

And here, the achi emulator (ACC) for dot generation
Since the LSB of the code generated in 12 is O”°,
It is determined that straight line drawing on this scan line has been completed, and the process moves on to straight line drawing on the next scan line. At this time,
The error added to the determination variable E is G2.

When the scan line moves to y=3, the judgment variable E
is less than 1, the number n of generated dots is the basic number 3 of dots. Then, after generating dots at predetermined positions in the same manner as above, the scan line is further moved. At this time, the error added to the determination variable E is Gt.

Similarly, address “0” of bitmap memory 3 is
Dots are generated up to 026" and the end point drawing step is started.

This end point drawing step determines whether the generated dot position has reached the end point coordinates, and if it has reached the end point coordinates,
Regardless of the number n of dots to be generated on the scan line, this can be done by clipping the dot generation position at the end point coordinate position.

Through the above operations, a dot pattern for drawing a straight line on the dot pattern forming surface as shown in FIG. 4, for example, is stored in the bitmap memory 3.

As described above, in this embodiment, dots can be generated at once in word width units of the dot generation accumulator (ACC) 12, which functions as a buffer register, so that the arithmetic unit (ALU) of the CPU 1 1
1 improves calculation efficiency and improves drawing speed.

In addition, in the above-mentioned embodiment, the case where a straight line is drawn where the inclination angle d of the dot pattern formation surface with respect to the It can be drawn by the configuration of . In that case, a slope identifying means for identifying the slope of the straight line to be drawn is provided before the basic dot number calculation means 101 shown in FIG.
It is sufficient to provide a coordinate conversion means for appropriately converting the coordinates according to the slope of the straight line identified by the slope recognition means. For example, if the inclination angle d of the straight line to be drawn is 45°<d
In the case of <90°, x=y, y=
After performing coordinate transformation of x, dot generation and writing to bitmap memory are performed in the same procedure as in the above embodiment.
When reading and outputting from this bitmap memory,
The coordinate transformation means may perform the coordinate transformation of x=y, y""x again to restore the coordinate system to its original state. Alternatively, the coordinate system may be restored to its original state when writing to the bitmap memory. Similarly, if −45”<d<Oo, then y
=-y coordinate transformation, and -90@<d<
In the case of -45@, it is sufficient to perform coordinate transformation of χ=-y, y-x.

In addition, in the method of the above embodiment, d=0@ and d=90@
Although the straight line cannot be drawn (because the basic number N of dots cannot be calculated), even in that case, the straight line can be drawn by using the above-mentioned straight line slope identification means. For example, the slope of a straight line is determined by the slope identification means to be d=0.
Once you have identified that d = 90°, find the X coordinate or X coordinate of any point on that straight line, and based on that coordinate, It is sufficient to generate dots at all dot generation points between the starting point and the ending point.

The method and apparatus of the present invention can be applied to all types of dot plotters, printers, displays, etc.

In that case, the dot pattern forming surface does not need to actually exist, but may be a virtual concept developed in a bitmap memory.

Further, when the present invention is applied to a display device such as a liquid crystal display, each pixel of the display device can be regarded as one dot and the present invention can be applied.

〔Effect of the invention〕

According to the method and apparatus of the present invention, the processing speed for drawing straight lines can be made faster than in the conventional method. This effect is particularly noticeable for straight lines that have a small slope with respect to one axis, for which the processing speed has conventionally been extremely slow.

[Brief explanation of the drawing]

FIG. 1 is a block diagram showing the basic configuration of the present invention, FIG. 2 is a block diagram showing the configuration of a linear drawing device according to an embodiment of the present invention, and FIG. 3 is a flowchart showing the operation of the CPU in FIG. 4 and 5 are conceptual diagrams showing an example of straight line drawing, and FIG. 6 is an explanatory diagram showing the contents of the bitmap memory.
FIG. 7 is an explanatory diagram showing a conventional straight line drawing method. In addition, in the symbols used in the drawings, 1 ... CPU 3 ... Bit map memory ot 02 03 04 05 06 07 Counter X-coordinate position determination accumulator (X-ACC) Arithmetic unit (ALU ) Dot generation accumulator (ACC) Basic dot number calculation means Dot number judgment means Dot generation means Buffer register transfer means Bit map memory scan line shift means

Claims (4)

[Claims] (1) In a linear drawing method in which a straight line pattern of dots is formed on a dot pattern forming surface where dot generation points are arranged in a matrix, a scan line parallel to one side of the matrix of dot generation points is drawn perpendicular to the scan line. The linear pattern is formed by sequentially shifting the line pattern in the following directions, and at this time, the basic number N of dots to be generated on one scan line is determined based on the slope of the ideal straight line to be formed with respect to the scan line. , the error between the position of the generated dot and the ideal straight line is accumulated for each shift of the scan line, and from the cumulative result, the number n of dots to be generated on the next scan line is determined by the above N and N+1. or N or N-1, and the number of dots according to the result of this judgment is placed in a buffer register provided corresponding to a predetermined word width. A straight line drawing method characterized in that the contents of the buffer register are transferred to a bitmap memory provided corresponding to the matrix of dot generation points. (2) Claim 1 characterized in that the integer part of the reciprocal of the slope Δy/Δx of the ideal straight line is the basic number N of dots.
The straight line drawing method described. (3) A bitmap memory that has a bitmap corresponding to a matrix of dot generation points and that is written and read in units of a predetermined word width, and a scan line parallel to one side of the matrix of dot generation points. , a scan line shift means for shifting in a direction perpendicular to the scan line, and a basic dot number for determining the basic number N of dots to be generated on one scan line based on the slope of the ideal straight line to be formed with respect to the scan line. calculating means; accumulating the error between the position of the generated dot and the ideal straight line for each shift of the scan line; and from the cumulative result, calculating the number n of dots to be generated on the next scan line; dot number determining means for determining whether the number is N or N+1, or whether the number is N or N-1; and a buffer register provided corresponding to the word width of the bitmap memory. and dot generation means for generating a number of dots in the buffer register according to the determination result by the dot number determination means, and transfer means for transmitting the contents of the buffer register to the bitmap memory. A straight line drawing device. (4) The straight line drawing device according to claim 3, wherein the basic dot number calculation means sets the basic dot number N to be the integer part of the reciprocal of the slope Δy/Δx of the ideal straight line.