Algorithm Brezenhema and Xiaolin Wu's

 

Bresenham's line algorithm is an algorithm that determines the points of an n-dimensional raster that should be selected in order to form a close approximation to a straight line between two points. It is commonly used to draw lines on a computer screen, as it uses only integer addition, subtraction and bit shifting, all of which are very cheap operations in standard computer architectures. It is one of the earliest algorithms developed in the field of computer graphics. An extension to the original algorithm may be used for drawing circles.

While algorithms such as Wu's algorithm are also frequently used in modern computer graphics because they can support antialiasing, the speed and simplicity of Bresenham's line algorithm means that it is still important. The algorithm is used in hardware such as plotters and in the graphics chips of modern graphics cards. It can also be found in many software graphics libraries. Because the algorithm is very simple, it is often implemented in either thefirmware or thegraphics hardware of modern graphics cards.

 

Here is a bitmap. Look at this strip " / ". If you move closer to the monitor, you can see the pixel steps that are trying to pretend to be a vector line. I would like to tell about the algorithm Brezenhema and  Wu's. Which are an approximation of the vector segment in raster coordinates.

Take a segment and its initial coordinate x. By the X in the loop is added 1 towards the end of the segment. At each step, the error is calculated - the distance between the actual y-coordinate at that location and the nearest grid cell. If the error does not exceed half the height of the cell, it is filled. That's the whole algorithm.

This was the essence of the algorithm, in fact, it looks as follows. First, calculate the slope (y1 - y0) / (x1 - x0). Error value at the starting point of the interval (0,0) is taken as zero and the first cell is filled. The next step is added to the angular error rate, and its value is analyzed, if the error is less than 0.5, then filled in a cell (x0 + 1, y0), if more then filled cell (x0 + 1, y0 + 1) and the error value is subtracted from the unit . The picture below shows a yellow color to the line rasterization, green and red - the distance to the nearest cells. The angular coefficient equal to one-sixth, the first step of the error becomes equal to the slope, which is less than 0.5, and the mean ordinate remains the same. By the middle of the line crosses the line of the error, it subtracts from, and the new pixel is above. And so to the end of the segment.

If the projection of the segment on the x-axis is less than the projection on the y-axis, or the beginning and end of the segment are swapped, then the algorithm will not work. To avoid this, you need to check the direction of the vector and its slope, and then on the need to swap the coordinates of the line turning axis, and, ultimately, to reduce everything to some one or at least two cases. The main thing to remember while drawing axis return to the place.

To optimize the calculations used a trick with the multiplication of fractional variables dx = (x1 - x0). Then, at each step, the error will vary by dy = (y1 - y0) instead of the slope and dx instead of the unit. You can also change a little logic, "move" error so that the border was at the origin, and it was possible to check the sign of the error, it may be faster.

Code from Wikipedia altered under C #.

void BresenhamLine(int x0, int y0, int x1, int y1)
{
    var steep = Math.Abs(y1 - y0) > Math.Abs(x1 - x0); // Check the growth of the segment on the X axis and the Y-axis
    // Reflectible diagonal line, if the angle is too big
    if (steep)
    {
        Swap(ref x0, ref y0); // Shuffling the origin is moved to a separate function
        Swap(ref x1, ref y1);
    }
    // If the line does not grow from left to right, then change the start and end of the segment places
    if (x0 > x1)
    {
        Swap(ref x0, ref x1);
        Swap(ref y0, ref y1);
    }
    int dx = x1 - x0;
    int dy = Math.Abs(y1 - y0);
    int error = dx / 2; // It uses optimization multiplied by dx, to get rid of excess fractions
    int ystep = (y0 < y1) ? 1 : -1; // Choose the direction of growth of the Y coordinate
    int y = y0;
    for (int x = x0; x <= x1; x++)
    {
        DrawPoint(steep ? y : x, steep ? x : y); // Do not forget to return the coordinates back
        error -= dy;
        if (error < 0)
        {
            y += ystep;
            error += dx;
        }
    }
}

In Brezenhema algorithm is a modification to draw circles. There it works on a similar principle, in some ways even easier. Calculation goes for one octant, and all the other pieces of the circle drawn by symmetry.

Sample code: draw a circle in C #.

void BresenhamCircle(int x0, int y0, int radius)
{
    int x = radius;
    int y = 0;
    int radiusError = 1 - x;
    while (x >= y)
    {
        DrawPoint(x + x0, y + y0);
        DrawPoint(y + x0, x + y0);
        DrawPoint(-x + x0, y + y0);
        DrawPoint(-y + x0, x + y0);
        DrawPoint(-x + x0, -y + y0);
        DrawPoint(-y + x0, -x + y0);
        DrawPoint(x + x0, -y + y0);
        DrawPoint(y + x0, -x + y0);
        y++;
        if (radiusError < 0)
        {
            radiusError += 2 * y + 1;
        }
        else
        {
            x--;
            radiusError += 2 * (y - x + 1);
        }
    }
}

Xiaolin algorithm is for drawing smooth lines.

It is characterized by the fact that at each step of the calculation is carried out for the two closest to the line of pixels, and they are colored with different intensity, depending on the distance. Current intersection middle pixel intensity gives 100% if the pixel is within 0.9 pixel, the intensity will be 10%. In other words, one hundred percent of the intensity is divided between the pixels which limit vector line on both sides.

In the picture the red and green color shows the distance to the two adjacent pixels.  To calculate the error, you can use floating point and take the error value of the fractional part.

Sample code:

private void WuLine(int x0, int y0, int x1, int y1)
{
    var steep = Math.Abs(y1 - y0) > Math.Abs(x1 - x0);
    if (steep)
    {
        Swap(ref x0, ref y0);
        Swap(ref x1, ref y1);
    }
    if (x0 > x1)
    {
        Swap(ref x0, ref x1);
        Swap(ref y0, ref y1);
    }

    DrawPoint(steep, x0, y0, 1); // This function changes the coordinates of the machine, depending on the variable steep
    DrawPoint(steep, x1, y1, 1); // The last argument - the intensity expressed as a decimal
    float dx = x1 - x0;
    float dy = y1 - y0;
    float gradient = dy / dx;
    float y = y0 + gradient;
    for (var x = x0 + 1; x <= x1 - 1; x++)
    {
        DrawPoint(steep, x, (int)y, 1 - (y - (int)y));
        DrawPoint(steep, x, (int)y + 1, y - (int)y);
        y += gradient;
    }
}

If you are suddenly in the future will have to work with grids, consider briefly, because in fact you are working with pixels, although do not know this. Modifications of these algorithms can be used in games to find the cells before units on the map, calculating the area of a shot or defeat a beautiful arrangement of objects. Or you can just draw a line in the program on the links below.


Unity Web Player | Windows | Linux | Mac | GitHub

Left mouse button - Brezenhem,
Right click - Xiaolin Wu's
Space - clean,
Esc - exit.
For users of Linux: Make the file executable with BresenhamWu «chmod + x BresenhamWu» and run.

 

 

All data posted on the site represents accessible information that can be browsed and downloaded for free from the web.

http://habrahabr.ru/post/185086/

 

User replies

No replies yet