CN1450498A

CN1450498A - Quick line drawing method

Info

Publication number: CN1450498A
Application number: CN 02106279
Authority: CN
Inventors: 吕忠晏; 姚若坛
Original assignee: Silicon Integrated Systems Corp
Current assignee: Silicon Integrated Systems Corp
Priority date: 2002-04-08
Filing date: 2002-04-08
Publication date: 2003-10-22
Anticipated expiration: 2022-04-08
Also published as: CN1236403C

Abstract

The invention is a method for drawing line quickly, at first, receives a starting position and an ending position. Following that, decides a continuous point value according to the two positions, and decides an object pel position and a drawing pel position. If the second axis coordinates value of the drawing pel position isn't equal to the second axis coordinate value of the object pel position, along the first axis of the drawing pel position decides the pel position of continuous point value by the drawing pel position. Finally, draw pels in the correspondent pel positions continuously.

Description

Quick line drawing method

Technical field

Present invention is directed to a kind of quick line drawing method, and be particularly to a kind of characteristic that cooperates the memory body access, decision simultaneously and a plurality of pixels of drafting, and then the quick line drawing method that quickens setting-out speed.

Background technology

Computer image display device now, as display, system is made of the grid of the little luminous point (pixel) of rule usually, and wherein, each grid can be lighted luminous with color (color and luster) and intensity (brightness) independently.One of them the most basic problem is to decide the collection of pixels which can the best image image in computer graphics, and is assigned to these color of pixel and intensity, to such an extent as to make straight line and edge perfection to draw on computer monitor.

Pixel in Figure 1A, 1B and the 1C display screens and the relation between the memory body access.Figure 1A is that a synoptic diagram is that coordinate is that (X, pixel P y) are stored in the relevant position in the display buffer working storage (DisplayBuffer) in the display screens 10.Yet the operation of memory body is not can only pixel information of access, and the pixel information of one number of access simultaneously.For instance, with each pixel is that true color (True Color) display of 32 bits is an example, for having the wide memory body bus-bar of 128 bit bus-bars, a data transmission (block (Block) 20) can comprise four pixel informations (21,22,23 and 24), shown in Figure 1B.That is to say that per four pixels are that a district determines by group 20 is a memory body access unit, shown in Fig. 1 C.

In the pixel of drawing on the computer monitor on first step system decision display at straight line or edge haply near this line.Foremost is Bu Li gentry Chinese algorithm (Bresenham ' sAlgorithm).Before this algorithm of explanation, must define some relevant nouns earlier.X-master (major) linear system is flatly to stretch." main shaft " of this line is with reference to the X-axle, and " inferior (minor) axle " is with reference to the y-axle.What more vertically stretch in the same manner, is the X-main line." main shaft " of this line is with reference to the Y-axle, and " secondary axes " are with reference to the X-axle.

Fig. 2 is X-master's integer Bu Li gentry Chinese setting-out algorithm example.In Bu Li gentry Chinese algorithm, use integer mathematics to carry out setting-out, do not carry out division arithmetic and do not make decimally.Bu Li gentry Chinese algorithm has good correctness and accuracy, therefore, on can mathematics the perfect line that draws.

Suppose that X-principal series are drawn to P2 (10,3), as shown in Figure 3A by the pixel P1 in the display buffer working storage 11 (1,1).Just there is the pixel of three blocks (first block 31, second block 32, with the 3rd block 33) to need the memory body access, shown in Fig. 3 B.Fig. 3 C shows the order of carrying out setting-out according to Bu Li gentry Chinese algorithm.In the process of setting-out, need ten to draw point operation, i.e. this setting-out must spend ten processing cycles.Therefore, though a memory body access can be handled four pixel informations, because the method for the Bu Li gentry Chinese once can only be drawn a point, therefore, the efficient of setting-out can not satisfy.

Summary of the invention

In view of this, fundamental purpose of the present invention can cooperate the characteristic of memory body access for providing a kind of improvement known drawing technique, decision simultaneously and a plurality of pixels of drafting, and then the quick line drawing method that quickens setting-out speed

In order to reach above-mentioned purpose of the present invention, can reach by a kind of quick line drawing method provided by the present invention.According to the embodiment of the invention, at first, receive a position, a starting point and an end point position.Then, according to initial point position and end point determining positions one continuous point value, and determine a target pixel location and to draw location of pixels.If it is unequal in the second axial coordinate value of target pixel location to draw the second axial coordinate value of location of pixels, be the location of pixels of continuous point value by drawing location of pixels decision number along first direction of principal axis of drawing location of pixels.

At last, draw the pixel of respective pixel position respectively continuously.

In addition, if draw the second axial coordinate value that the second axial coordinate value of location of pixels is equal to target pixel location, then determine a location of pixels by drawing location of pixels, and draw the pixel of corresponding this location of pixels along first direction of principal axis of drawing location of pixels.

In addition, if the first axial coordinate value of location of pixels is then abandoned this location of pixels greater than the first axial coordinate value of end point position.And if draw the first axial coordinate value that pixel firmly puts the first axial coordinate value, then ends drawing operation greater than the end point position

According to the embodiment of the invention, can determine again that more target pixel location is along the location of pixels of first direction of principal axis of drawing location of pixels by the continuous point value of drawing location of pixels, and determine to draw location of pixels again according to this location of pixels.

By quick line drawing method provided by the present invention, can cooperate the characteristic of memory body access, determine simultaneously and a plurality of pixels of drafting, and then quicken the usefulness of whole setting-out.

Description of drawings

Pixel in Figure 1A display screens is stored in the synoptic diagram of display buffer working storage;

Figure 1B shows four pixel information squares that comprise in the big data transmission;

The display buffer working storage that it is a block that Fig. 1 C system shows four pixel groups;

Fig. 2 is X-master's integer Bu Li gentry Chinese setting-out algorithm example;

Fig. 3 A system shows by pixel P1 (1,1) draws X-main line example to P2 (10,3);

Fig. 3 B is three blocks of memory body access among the displayed map 3A;

Fig. 3 C shows the order of drawing Fig. 3 A middle conductor according to Bu Li gentry Chinese algorithm;

Fig. 4 is the process flow diagram of demonstration according to the quick line drawing method of the embodiment of the invention;

Fig. 5 is Fig. 3 A middle conductor is drawn in demonstration according to the quick line drawing method of the embodiment of the invention a order.

Symbol description: 10-screen: 11-display buffer working storage; The 20-block; 21,22,23,24-pixel information; 31-first block; 32-second block; 33-the 3rd district determines; S100, S102 ..., the S122-operation steps.

Embodiment

Fig. 4 is the process flow diagram of demonstration according to the quick line drawing method of the embodiment of the invention.With reference to figure 4, the embodiment of the invention will be described in more detail in down.

In the embodiment of the invention, utilize two functions " Draw-Point " and " Draw-Span " to come non-productive operation and explanation, function " Draw-Point " is only in order to writing down a locations of pixels, and function " Draw-SPan " be in order to write down the location of pixels of an extended distance.The setting-out flow process comprises that step is as follows: at first, must decision will draw which pixel; Then, write down these locations of pixels; Form the memory body requirement according to record again; At last, allow the memory body requirement, come the pixel information in the update displayed buffer register.Note be do not show among Fig. 4 the memory body access (as, memory body requires) operation part.

At first, (X1 is y1) with (x2, y2) (S100) for the two-end-point coordinate of reception X-main line.Then, in step 5102, carry out the initial setting of some parameters.Wherein, present X and Y are initially set X1 and x2 respectively; Dx and Dy are calculated and be expressed as respectively to the difference of X and y coordinate; Dx partly represents that with Q when the y coordinate figure between two graphical pointvs of front and back changed, the Q value was the pixel number that can determine continuously or draw at least divided by the integer of Dy; In addition, at this moment, the initial value of mistake and E (Sum of Error) is-Dx, and two constant K 1 are defined as 2Dy and 2QDy respectively with K2.

After E, K1 and K2 had set, whether whether setting-out had arrived repeated test x coordinate at that time in the X coordinate (S104) of end points, promptly complete.When at that time X coordinate greater than the X coordinate time of end points (X＞X2) (step S104 not), then finish whole setting-out operation (S122).

And X coordinate that ought be at that time is smaller or equal to X coordinate time (X＜=X2) (step S104 is) of end points, whether then wrong and E is tested is nonnegative value (S106), when wrong and E are positive number (step S106 is), Y and E are respectively with (Y+1) and (E-2Dx) renewal (S108).What note is, when wrong among the step S106 and E are judged as positive number, promptly represent the next one will change between the y coordinate figure of the pixel of drafting and the y coordinate figure at that time.

Then, whether the value of checking (X+Q-1) is promptly checked once decision or is drawn the x axle border whether Q pixel can surpass end points less than X2 (S110).When once decision or Q pixel of drafting surpass the X-axis border of end points (step S110 is), then can directly draw the X coordinate and be Q pixel (S112) by X to X+Q-1.On the contrary, if once decision or when drawing Q pixel and surpassing the x axle border of end points (step S110 not), then draw the X coordinate and be pixel (S114) by X to x2.And after pixel painted, x and wrong and E upgraded (S116) with x+Q and E+K2 respectively.

On the other hand, when wrong and E are negative (step S106 denys), (x Y) goes up drawn (S118) at coordinate to have only a pixel.Afterwards, x upgrades (S120) with x+1 and E+K1 respectively with wrong and E.

Next, draw X-main line example to P2 (10,3) by pixel P1 (1,1) among Fig. 3 A, will apply mechanically the embodiment of the invention and describe, its sequence of operation and related parameter values will be shown among Fig. 5.

For drawing this X main line, two-end-point is P1 (1,1) and P2 (10,3).At this moment, the value of Dx be 9 and the value of Dy be 2; Dx is 4 to be expressed as Q divided by the smallest positive integral value of Dy; Constant K 1 is respectively 4 and 16 with the value of K2.In the time of at the beginning, the value of mistake and E is-9.Because E is a negative value, the coordinate of point (1,1) is recorded and E is updated to-5.At this moment, E still is a negative value, and then the coordinate of point (2,1) is recorded, and in the same manner, the coordinate of point (3,1) also is recorded.Because point (3,1) is last that comprises in the block of point (0,1), (1,1), (2,1) and (3,1), a memory body requires can be allowed to upgrade color of pixel, in order to graphical pointv (1,1), (2,1) and (3,1).

Now, E be 3 and E be positive number, then Y increases by 1.Then, (X+Q-1) further tested whether be less than or equal to X2 (X2=10), in order to judge whether to be terminal point near line segment.The result tests success, and a succession of point (4,2), (5,2), (6,2) are recorded with (7,2).Block of pixel data in the display buffer working storage can be upgraded by a memory body requires, and therefore, a memory body requires to be allowed to.And E is 1 now, and still also makes Y increase by 1 again for positive number.Because value (X+Q-1) greater than x2, has only three points (8,3), (9,3) to be recorded with (10,3), and memory body requirement is allowed to the terminal point to line segment.

Comparison diagram 3C and Fig. 5 apply mechanically after the embodiment of the invention, the step of whole setting-out operation, and can be reduced by 10 operation stepss is 5 operation stepss, the usefulness of significantly promoting setting-out.

Generally speaking, except last terminal point, when the y coordinate figure between two graphical pointvs of front and back changes, can determine or draw Q pixel number continuously at least.Therefore,, can cooperate the characteristic of memory body access, determine simultaneously and a plurality of pixels of drafting, and then quicken the usefulness of whole setting-out by quick line drawing method provided by the present invention.

Though the present invention discloses as above with preferred embodiment; right its is not in order to qualification the present invention, any those who are familiar with this art, without departing from the spirit and scope of the present invention; when can doing a little change and retouching, so protection scope of the present invention defines and is as the criterion when looking the claim scope.

Claims

1. a quick line drawing method comprises the following steps:

Receive a position, a starting point and an end point position;

According to this initial point position and end point determining positions one continuous point value;

Determine an object pixel according to putting;

Determine one to draw location of pixels; And

If this second axial coordinate value of drawing location of pixels is unequal in the second axial coordinate value of this target pixel location, drawing location of pixels decision number along this first direction of principal axis of drawing location of pixels by this is the location of pixels of this continuous point value.

2. quick line drawing method as claimed in claim 1 is characterized in that: more comprise the continuous drafting pixel of corresponding these location of pixels respectively.

3. quick line drawing method as claimed in claim 1 is characterized in that: more comprise if the first axial coordinate value of this draftings location of pixels greater than the first axial coordinate value of this end point position, then ends drawing is operated.

4. quick line drawing method as claimed in claim 1 is characterized in that: more comprise if the first axial coordinate value of this location of pixels greater than the first axial coordinate value of this end point position, is then abandoned this location of pixels.

5. quick line drawing method as claimed in claim 1 is characterized in that: more comprise determining this target pixel location for along first direction of principal axis of this drafting location of pixels location of pixels by this continuous point value of this drafting location of pixels again.

6. quick line drawing method as claimed in claim 1 is characterized in that: more comprise according to determining this drafting location of pixels along first direction of principal axis of this drafting location of pixels again by the location of pixels of this continuous point value of this drafting location of pixels.

7. quick line drawing method as claimed in claim 1, it is characterized in that: more comprise if the second axial coordinate value of this drafting location of pixels is equal to the second axial coordinate value of this target pixel location, determine a location of pixels by this drafting pixel location along first direction of principal axis of this drafting location of pixels.

8. quick line drawing method as claimed in claim 7 is characterized in that: more comprise draw mutually should location of pixels pixel.

9. quick line drawing method as claimed in claim 7 is characterized in that: more comprise determining this target pixel location to be this location of pixels again.

10. quick line drawing method as claimed in claim 7 is characterized in that: more comprise according to this location of pixels determining this drafting location of pixels again.