There may be a picture or downloaded link is wrong, please check it to the original address. Http://dgame.yeah.net
============================================================================================================================================================================================================= ======
The ordinary Breshenham algorithm is very fast, but it is not very fine. The usual integer line can only draw on the integer coordinates, so I will have a ukah sawtooth. I saw a very good in Michael Abrash. Drop-like line painting and decide to change it with non-integer coordinates.
A WU straight line is not only better than a normal straight line, it also produces better animation. A normal straight line jumps from a location to the next position. However, a WU straight line is very leisurely drifting to the next position .
How did it work?
Let us think about a straight line that does this. What should I look like? Is there a lot of straight lines? How is the tail end? The straight line is a one-dimensional object, unlimited. It is not long. What is thick. The end of the line segment is not like, it is the tail. Such a straight line cannot be drawn to a pixel-based display device. In the computer graphics, it is usually assumed that the line segment is a pixel thick. This means This can be drawn. This means that he is so thin that there is no need to consider what the end should be like, because it is smaller than a pixel, can't draw. We must formulate when we design a new WU line. Similar assumptions. Because this new algorithm can handle the endpoint of non-integer coordinates, what can be done for a line smaller than a pixel long? Assume that the pixel is the center of their coordinates. The straight line is a pixel thick. The shape is not important. It can be better, if:. Two parallel line segments, endpoints are connected, can not distinguish one, one long line segment. Line of brightness / transparent can be defined
What is the final algorithm?
The final algorithm is relatively easy, but it is too slow in practical applications. But it is not really necessary, because its effect is almost the same as another faster approach. No matter what, I will clarify some basic things.
Imagine, you can enhance our pixels of the screen we draw on the line. The ideal line algorithm will calculate the precise area covered by each line, thereby increasing the brightness of those pixels. Such an algorithm is easy to write, in one more High resolution redraw screen's related parts, then draw lines to top, calculate the covered pixels or Calculating it Presetice.
However, this requires some accuracy. Let's look at the next method.
A more sensible algorithm
This algorithm rogs a pair of pixels across lines. A primary loop will draw a pair of pixels along the length of the straight line. The pixels of the endpoint will be calculated separately. Pixels: Imagine once, a close-up of the screen. Draw a painful Line. This almost horizontal line passes through the vertical pixel column. Each time you cross the pixel, the X coordinate is an integer, but the Y coordinates are non-integers. It is more close, a single leap point: in every leap point, We will consider the pixel pair of cross-riding straight lines. The brightness of the two pixels should be 1, the brightness of the central point is the brightness of the ideal straight line. The brightness of the pixels on the line must be proportional to (1-a) proportional, line down pixels The brightness must be proportional to (1-b). That is to say, the closer to the straight line should be brighter. The pixels like this along the straight line length, then you basically get a reverse straight line.
Draw an endpoint
The last thing is to paint endpoint. This is not handled, I still don't have completely correctly handles them. Here is a method I am using now. He is not ideal, but very close. You will notice that the straight line is almost vertically At almost horizontal, it has a careful failure. The anti-process is also. You will pay attention to this when the straight line moves over 45 degrees. Really close to the end: You can see a straight line of the straight line, with red Point to indicate. Blue point represents the center point of pixels. You can see that the vertices are not in the center of pixels. The correct brightness of the two pixels of the linear endpoint:. Extend the straight line (backward or forward) To the nearest integer X coordinate (P). Calculate this pixel pair as the brightness of the normal pixel pair of straight lines. Then, because the straight line is only covered by this pixel, the straight line will reduce its brightness. So Brightness should be multiplied in i. Therefore, when the whole line moves to the right, I will become smaller, so that this pixel is dimmed. Special situation
What will be less than a straight line of less than a pixel? Because it is too small to be precisely, you can paint it as a model. This is my own implementation method, I stretched the line to one Pixabine often, then lower their brightness. So a very short straight line looks very dark, when it grows, it will brighten, when he is a pixel, it will be drawn from normal.
Finally, some pseudo code
WU straight line fixed point calculation requires some functions: function trunc (x) returncture function Frac (x) Return Fractional Part of X end of function function infrac (x) Return 1 - (FRActional Part of X End of function
WU linear program: Procedure Wuline (fixpt x1, fixpt y1, fixpt x2, fixpt y2)
Variable Declerations:
FIXPT VARIABLES:
Grad, XD, YD, Length, XM, YM
XGAP, YGAP, XEND, YEND, XF, YF
Brighess1, brighers2
Integer Variables:
X, Y, IX1, IX2, IY1, IY2
Byte Variables:
C1, C2
Code Starts Here:
Width and Height of the Line
XD = (x2-x1)
YD = (Y2-Y1)
IF ABS (XD)> ABS (YD) THEN CHECK LINE GRADIENT
Horizontal (ISH) Lines
IF x1> x2 Then IF line is Back to Front
SWAP X1 and X2 TEN SWAP IT ROUND
SWAP Y1 and Y2
XD = (x2-x1) and recalc xd & yd
YD = (Y2-Y1)
END IF
Grad = yd / xd gradient of the line
END POINT 1
-----------
XEND = Trunc (x1 .5) Find nearest Integer X-Coordinate
Yend = Y1 GRAD * (XEND-X1) and corresponding y value
XGAP = INVFRAC (x1 .5) distance i
IX1 = int (xend) Calc Screen Coordinates
Iy1 = int (Yend)
Brightness1 = Invfrac (Yend) * xgap Calc The intence of the OtherBrightness2 = Frac (Yend) * xgap end point pixel pair.
C1 = Byte (Brightness1 * Maxpixelvalue) Calc Pixel Values
C2 = byte (Brightness2 * MaxpixelValue)
Drawpixel (IX1, IY1), C1 Draw The Pair of Pixels
Drawpixel (IX1, IY1 1), C2
YF = YEND GRAD CALC FIRST Y-INTERSECTION for
Main loop
END POINT 2
-----------
XEND = trunc (x2 .5) Find nearest Integer X-Coordinate
Yend = Y2 grad * (Xend-x2) and corresponding y value
XGAP = INVFRAC (x2-.5) distance i
IX2 = int (xend) Calc Screen Coordinates
Iy2 = int (Yend)
Brightness1 = Invfrac (Yend) * xgap coalc the intence of the first
Brightness2 = frac (Yend) * xgap end point pixel pair.
C1 = Byte (Brightness1 * Maxpixelvalue) Calc Pixel Values
C2 = byte (Brightness2 * MaxpixelValue)
Drawpixel (IX2, IY2), C1 Draw The Pair of Pixels
Drawpixel (IX2, IY2 1), C2
Main loop
---------
LOOP X from (ix1 1) to (ix2-1) main loop
Brightness1 = Invfrac (YF) Calc Pixel Brightnesses
Brightness2 = frac (yf)
C1 = Byte (Brightness1 * Maxpixelvalue) Calc Pixel Values
C2 = byte (Brightness2 * MaxpixelValue)
Drawpixel (X, INT (YF), C1 Draw the Pair of Pixels
Drawpixel (X, INT (YF) 1), C2
YF = yf grad update the y-coordinate
End of x loop end of loop
Else
Vertical (ISH) Lines
Handle The Vertical (ISH) Lines in The
Same Way As The Horizontal (ISH) Ones
But swap the roles of x and y
END IF
End of procedure
Here is the specific description of the algorithm described above. For convenience and speed, I use a fixed point here. In this case, it is obviously very convenient. First, I define some functions. Finally
It has proved to be really working, and it seems very wonderful, there is a Demo here.
This program draws a Newton's CRADLE in two resolutions to demonstrate that WU line can draw a small thing, and still look OK. You can see how smooth them move.
