Bresenham's line algorithm

The Bresenham algorithm is an algorithm in computer graphics for drawing ( grids ) of straight lines or circles on raster displays. For line algorithms there is a separate review article, here is the concrete implementation is more explained.

The algorithm was established in 1962, developed by Jack Bresenham, then a programmer at IBM. The special feature of his algorithm is that it minimizes rounding errors that result from the discretization of continuous coordinates, and at the same time is easy to implement, requires only the addition of integers as a complex operation, and thus without multiplication, division, and floating point numbers.

By a slight expansion of the original algorithm can be, designed for straight lines, also be used for the grid of channels. Even the square terms occurring in the circuit, can be recursively without any multiplication of the respective preceding term derived by, where the term does not count as multiplication, as it is implemented in hardware or assembler level as a simple shift operation and the term in the end can be completely avoided.

Based on the above properties, the significance of Bresenham algorithm is unbroken to this day, and he comes in, among other plotters in the graphic chips of modern graphics cards and, in many graphics libraries for use. He is so simple that it is used not only in the firmware of these devices, but can be implemented in graphics chips directly in hardware.

The name " Bresenham " is now also used for a whole family of algorithms that were originally developed by others later, however. In the wake of Bresenham and with a related approach See further reading below.

• 3.1 BASIC implementation
• 3.2 C implementation
• 3.3 Compact variant

• 4.1 Derivation of the error term initialization
• 4.2 Drawing of incomplete octants
• 4.3 ellipses 4.3.1 Compact variant

Approach

The version presented here is a very practical approach and was first released by Pitteway and verified by van Aken. Below the variant is compared and shown that the solutions are equivalent to the original formulation of Bresenham.

To understand the algorithm, we limited according to the first octant, ie, a line with a slope between 0 and 1 of. Let and with. For other octants you have later case distinctions on the sign of and and the turnabout by and meet.

The algorithm then runs so that you can in the "fast" direction ( here the positive direction) always takes a step and, depending on the pitch every now and then an additional step in the "slower" direction (here). One uses this an error variable that the (smaller) value gets subtracted in step in direction. When below the zero value, a step is due and added to the (larger) value for the error variables. These repeated " cross " subtractions and additions solve the slope of the triangle division on in elementary computing steps.

In addition, this error term must be previously initialized sense. This purpose we consider the case of where you like in the middle ( after the half ) to have a step. So initialized with you. ( Whether this is a whole number rounded up or down, hardly plays a role. )

Mathematically, the linear equation

Dissolved in

And the zero is replaced by the error term. A step by 1 in direction ( variable) causes a reduction in the error term. If the error term it gets below zero, it is increased by a step of 1 in direction ( variable) at a time, which makes the condition after the error term definitely come back positive, or at least brings to zero.

The original approach Bresenham (see below) is way longer geometrically before, which (except for the error term ), an additional factor of 2 is carried in its Iterationsformeln on both sides and also the Fehlergliedinitialisierung is otherwise derived.

Easy to implement

A first implementation is not very elegant, the principle of the algorithm demonstrates very good.

REM Bresenham algorithm for a line in the first octant in pseudo -Basic   dx = xend xstart   dy = yend - ystart   REM in the first octant must be 0 < dy < = dx be     REM initializations   x = xstart   y = ystart   SetPixel x, y   error = dx / 2     REM pixel loop: always a step in the direction of fast, now and again in a slow   WHILE x < xend      REM step in fast direction      x = x 1      error = error dy -      IF error < 0 THEN         REM step in slow direction         y = y 1         error = error dx      END IF      SetPixel x, y   WEND Compared with the original formulation Bresenham

REM quasi- Bresenham algorithm REM original Bresenham   dx = dx = xstart xend xend xstart   dy = dy = yend - ystart yend - ystart                                         d = 2 * dy - dx                                       DO = 2 * dy                                       DNO = 2 * (dy - dx)     x = x = xstart xstart   y = y = ystart ystart   SetPixel x, y SetPixel x, y   error = dx / 2 errors = d     WHILE x < xend WHILE x < xend      x = x 1 x = x 1      error = error dy -      IF error < 0 THEN IF error < = 0 THEN                                             error = error DO                                          ELSE         y = y 1 y = y 1         error = error dx error = error DNO      END IF END IF      SetPixel x, y SetPixel x, y   WEND WEND Apart from the accommodation to the BASIC dialect used, the following differences in the original formulation must be observed:

• The error term is used with the opposite sign.
• The error term is queried for its sign, before it is updated, by the additional initialization with the Dy term is necessary.
• The error term is added to the factor of 2, so that during the initialization no division takes place by 2, but the step variable for error updates twice as large.

Taking into account the differences in the formulation, it is found that both formulations operate identically, and are thus equivalent.

More elegant implementations

An elegant formulated examples follow the first of the source code of a BASIC program and then a subroutine in C, which do not need explicitly make the case distinction in eight octants.

The algorithm will be valid for all octants. The sign of the coordinate distance and the possible reversal of the roles of X and Y must be considered. If one were to take this case distinctions within the innermost loop, so in high numbers, which would reduce the speed of the calculations significantly. An efficient solution is trying to work through all these case distinctions in the initialization phase of the proceedings before the main inner loop, so that within the inner loop must continue to take place, only one query for the Bresenham error term.

This formulation leads (as already Stockton indirectly suggested ) various abstractions one: First step into the fast direction now as a parallel step is considered ( parallel to a coordinate axis ), and if additionally carried a step in the slow direction, is that at a diagonal step. Then you can determine variable values ​​in the initialization that determine those cases, the step sizes in the two coordinate directions in advance and thus achieve the generalization for the eight octants. For example, in a parallel step, the step size in the direction perpendicular thereto precisely zero. Second, if we include the error term continues as in the first octant, with absolute values ​​of the distances. In the innermost loop, the step in the fast direction is no longer carried out first, but updated first, the error term, and only thereafter the step size is added to the previous coordinate, depending on whether a parallel or a diagonal step has to be carried out:

BASIC implementation

REM Bresenham algorithm for a line in any octant in pseudo -Basic   dx = xend xstart   dy = yend - ystart     REM initializations   adx = ABS (dx ): ady = ABS (dy ) ' absolute magnitudes of distances   sdx = SGN (dx ): sdy = SGN (dy ) ' Signum distances     IF adx > ady THEN     ' X is fast direction     pdx = sdx: PDY = 0 ' pd. is parallel step     ddx = sdx: ddy = sdy 'dd. is diagonal stride     it = ady el = adx ' error steps fast, slow   ELSE     'Y is fast direction     pdx = 0: PDY = sdy ' pd. is parallel step     ddx = sdx: ddy = sdy 'dd. is diagonal stride     it = adx: el = ady ' error steps fast, slow   END IF     x = xstart   y = ystart   SetPixel x, y   errors = el / 2     REM pixel loop: always a step in the direction of fast, now and again in a slow   FOR i = 1 TO el ' el are also number of pixel to draw to      REM update error term      error = error - it      IF error < 0 THEN         positive ( > = 0) make errors = errors el ' error term again         REM step in slow direction         x = x ddx: y = y ddy ' diagonal stride      ELSE         REM step in fast direction         x = x pdx: y = y PDY ' parallel step      END IF      SetPixel x, y   NEXT C implementation

In this implementation, use is made of the signum function.

/ * Signum function * / int sgn ( int x ) {    return ( x > 0)? 1: (x <0)? -1: 0; }   void gbham (int xstart, ystart int, int xend, int yend ) / * ------------------------------------------------ --------------   * Bresenham algorithm: draw lines on raster devices   *   * Input parameters:   * Int xstart, ystart = coordinates of the starting point   * Int xend, yend = coordinates of the end point   *   * Output:   * Void SetPixel (int x, int y) set a pixel in the image   * ( It is assumed in this or similar form )   * ------------------------------------------------- --------------   * / {      int x, y, t, dx, dy, incx, incy, pdx, PDY, ddx, ddy, it, el, err;   / * Distance in two dimensions calculated * /     dx = xend - xstart;     dy = yend - ystart;   / * Sign of the increment determine * /     incx = sgn ( dx);     incy = sgn ( dy);     if ( dx <0) dx = - dx;     if ( dy <0) dy = - dy;   / * Determine which distance is greater * /     if ( dx > dy)     {        / * X is fast direction * /        pdx = incx; PDY = 0; / * Pd. is parallel step * /        ddx = incx; ddy = incy; / * Dd. is diagonal stride * /        it = dy; el = dx; / * Error steps fast, slow * /     else }     {        / * Y is fast direction * /        pdx = 0; PDY = incy; / * Pd. is parallel step * /        ddx = incx; ddy = incy; / * Dd. is diagonal stride * /        it = dx; el = dy; / * Error steps fast, slow * /     }   / * Initialization before loop start * /     x = xstart;     y = ystart;     err = el / 2;     SetPixel (x, y);   / * Compute pixel * /     for ( t = 0; t < el, t) / t * counts the pixels, el is also number * /     {        / * Update error term * /        err - = it;        if ( err <0)        {            / * Error term positive again make * / (> = 0)            err = el;            / * Step in slow direction, diagonal stride * /            x = ddx;            y = ddy;        else }        {            / * Step in fast direction parallel step * /            x = pdx;            y = PDY;        }        SetPixel (x, y);     } } / * Gbham () * / Compact variant

The Bresenham algorithm can be implemented in a simple variant in C:

Void line (int x0, int y0, int x1, int y1) {    int dx = abs (x1 - x0 ), sx = x0 < x1? 1: -1;    int dy = abs (y1 - y0 ), sy = y0 < y1? 1: -1;    int err = dx dy, e2; / * Error value e_xy * /      for (; ;) { / * loop * /      setPixel ( x0, y0 );      if ( x0 == x1 && y0 == y1) break;      e2 = 2 * err;      if ( e2 > dy) { err = dy; x0 = sx; } / * E_xy e_x > 0 * /      if ( e2 < dx) { err = dx; y0 = sy; } / * E_xy e_y <0 * /    } } The error term is in this case for both the slow and the fast direction used as step detection. The four quadrants are covered by the Vorzeicheninkrement (sx, sy). The error term of the accumulation triggers when exceeding the threshold value of the conditional step, simultaneously, in contrast to the original version in both directions: positive and negative error values ​​for x for the y -axis. The example shows thus elegantly the xy symmetry of the Bresenham algorithm.

Circle variant of the algorithm

The approach for the circular variant of the Bresenham algorithm also not due to Bresenham himself, he is similar to the method of Horn from the review article, see also Pitteway and van Aken below. It is accordingly of the circle equation. Consider, first again only the first octant. Here one would like to draw a curve that starts at the point ( r, 0) and then continues upward to the left up to the angle of 45 °.

The "fast" direction is the direction here. It always takes a step in the positive direction, and from time to time one must also a step in the "slow", making negative direction.

The constant square calculations (see equation of a circle ), or possibly even trigonometric or square root operations are avoided by dissolving again into individual steps and recursive calculation of the terms from the respective preceding.

Mathematics: From the equation of a circle to get to the transformed equation

Which must not be calculated explicitly,

Which must also not be included as a separate variable, but only the difference of one step to the next will be added to the error term. Again, the zero in the equation is replaced by the error term.

In addition, one must then when setting the pixel still add add the center coordinates. These constant fixed-point additions limit the performance but not a noticeable, since one saves squaring or even root contractions in the innermost loop.

With the approach of the circle equation ensures that the coordinates of a maximum of 1 pixel, the digitization error deviate from the ideal curve. The initialization of the error term will now cause the first step in the slow direction takes place when the real circular curve has come to a half pixel in the slow coordinate inward. Details for calculation below, it runs on, an initialization of the error term with the radius r out.

The formulation is shown here again just for the first octant, and again the other octants result from change of sign in and and of roles of and. The extension to the full circle, as it is suitable for graphic display, but not for plotter is attached in comments.

REM Bresenham algorithm for eighth circle in pseudo -Basic   SEM are given r, xmittel, ymean   REM initializations for the first octant   x = r   y = 0   errors = r   REM " fast" direction is y here!   SetPixel xmittel x, y ymean     REM pixel loop: always a step in the direction of fast, now and again in a slow   WHILE y

Void grid circle (int x0, int y0, int radius)    {      int f = 1 - radius;      ddF_x int = 0;      int ddF_y = -2 * radius;      int x = 0;      int y = radius;        setPixel ( x0, y0 radius);      setPixel ( x0, y0 - radius);      setPixel ( x0 radius, y0 );      setPixel ( x0 - radius, y0 );        while ( x < y)      {        if ( f > = 0)        {          y -;          ddF_y = 2;          f = ddF_y;        }        x ;        ddF_x = 2;        f = ddF_x 1;          setPixel ( x0 x, y0 y);        setPixel ( x0 - x, y0 y);        setPixel ( x0 x, y0 - y);        setPixel ( x0 - x, y0 - y);        setPixel ( x0 y, y0 x);        setPixel ( x0 - y, y0 x);        setPixel ( x0 y, y0 - x);        setPixel ( x0 - y, y0 - x);      }    } Derivation of the error term initialization

The point of intersection at which the line circuit has come to 1/2 pixel to the inside, one calculated according to the equation of a circle:

On demand point (x1, y1) should apply: so the result is:

As to this point, no x - step to have taken place, the error term is

Initialize, where y1 ² is by rounding to r.

For example, in the image above: r = 11, y1 = 3 ( rounded down), error term at y = y1 = 3, 1 3 5 = 9, error term at y = 4 1 3 5 7 = 16 If the error term is initialized with r = 11, the first sign change and becoming the first x - step actually takes place during the transition from y1 to y1 1.

Drawing of incomplete octants

The above implementations always draw only complete octants or circles. If you want to draw only a certain arc of an angle to an angle, you have the so- implement that one - and - coordinates of these endpoints calculated in advance, and one must inevitably fall back on trigonometry or root account (see a Heron process). Then you can run the Bresenham algorithm on the complete octant or circle and sets the pixel but only if they fall within the desired range. After completion of this curve segment can cancel the algorithm prematurely.

Ellipses

For ellipses, there are again several possible approaches. One can at axis-parallel ellipses from the corresponding equation

Specify out and then proceed similarly as above the circle where and are the two semi-axis lengths.

But you can also by scaling the subscribed - and values ​​(and possibly horizontal or vertical line extensions) produce on the basis of the circle algorithm such axis-parallel ellipses. In this case, to use the circuit with the algorithm of the smaller axis of the ellipse as the radius in the other direction, and adds a value to the one in turn may be determined by increasing the Bresenham line algorithm from the pole to the equator. Since the ellipse must be stretched in the longer axis direction, is then reacted not only individual pixels, but may need a line (albeit a simple, horizontal or vertical ) from the previous point to the next draw.

A general ellipse can win parallel to the axis of such a by the complete graph additionally subjected to shear. Return to use an additional Bresenham line algorithm to determine the offset into one of the axial directions, and include increasing it at each coordinate to be drawn.

Compact variant

As in the algorithm for the line can also be formulated in the circle variant xy - symmetric. So this way, a continuous quarter circle will be drawn, which is helpful in ellipses.

Void ellipse (int xm, ym int, int a, int b ) {     int dx = 0, dy = b; / * In the first quadrant from top left to bottom right * /     long a2 = a * a, b2 = b * b;     Long err = b2 (2 * b-1) * a2, e2; / * Error in step 1 * /       do {         setPixel (xm dx, y m dy); / * I. quadrant * /         setPixel (xm - dx, ym dy ); / * II quadrant * /         setPixel (xm - dx, dy - ym ); / * III. Quadrant * /         setPixel (xm dx, ym- dy); / * IV quadrant * /           e2 = 2 * err;         if ( e2 < (2 * dx 1) * b2 ) { dx ; err = (2 * dx 1) * b2; }         if ( E2 > - (2 * dy -1) * A2) { dy -; err - = (2 * dy -1) * A2; }     } While (dy > = 0);       while ( dx Head of the ellipse complete * /         setPixel (xm - dx, ym );     } } The algorithm always test it a diagonal step and corrects this a large deviation. However, the steps of forming in the next quadrants and always then when the flat ellipse ( b = 1), terminated prematurely. In these cases, a supplement is necessary. The error variable must be the way the 3-fold range of values ​​( number of digits, bits) of radius ( semi-axes ) have ( about 64 -bit or floating point).