BRESERHAM'S LINE DRAWING ALGORITHM

Bresenham's Line Algorithm

Bresenham's Line Algorithm An accurate and efficient raster line-generating algorithm, developed by Bresen- ham, scan converts lines using only incrementa1 integer calculations that can be adapted to display circles and other curves. Figures 3-5 and 3-6 illustrate sections of a display screen where straight line segments are to be drawn. The vertical axes show-scan-line positions, and the horizontal axes identify pixel columns. Sampling at unit x intervals in these examples, we need to decide which of two possible pixel positions is closer to the line path at each sample step.

To illustrate ~Gsenharn'sa pproach, we- first consider the scan-conversion process for lines with positive slope less than 1. Pixel positions along a line path are then determined by sampling at unit x intervals. Starting from the left end- point (x, yo) of a given line, we step to each successive column (x position) and plot the pixel whose scan-line y value is closest to the line path. Figure 3-7 demonstrates the Mh step in this process. Assuming we have determined that the pixel at (xk,y k) is to be displayed, we next need to decide which pixel to plot in column xk+,. Our choices are the pixels at positions &+l, ykl and (xk+l,y k+l). At sampling position xk+l, we label vertical pixel separations from the mathematical line path as d, and d2 (Fig. 3-8). They coordinate on the mathemati- cal line at pixel column position rk+li s calculated as -

A decision parameter pk for the kth step in the line algorithm can be ob- tained by rearranging Eq. 3-11 so that it involves only integer calculations. We ac- complish this by substituting m = AyIAx, where Ay and Ax are the vertical and horizontal separations of the endpoint positions,and defining: The sign of p, is the same as the sign of dl - d,, since dr > 0 for our example. Pa- ri.meter cis constant and has the value 2Ay + Ax(2b - l), which is independent

 ALGORITHM(Summerized Steps)

1. Input the twoline endpoints and store the left endpoint in (xo,y o)
2. Load (xo,y d into the frame buffer; that is, plot the first point.
 3. Calculate constants Ax, hy, 2Ay, and 2Ay - ZAr, and obtain the start- ing value for the decision parameter as po = 2Ay - AX
4. At each xk along the line, starting at k = 0, perform the following test: If Pr < 0, the next point to plot is (g + I, yd and P~+I = Pk + ~AY Otherwise, the next point to plot is (xi + I, yr + 1) and pk+, = pk + 2Ay - 2Ax
 5. Kepeat step 4 Ax times.

program code

void lineares (int xa, i:it ya, int xb, int yb) ( int dx = abs (xa - xbl, dy = abs (ya - yb): int p = 2 * dy - dx; int twoDy = 2 ' dy, twoDyDx = 2 ' ldy - Ax); int x, y, xEnd: /' Determine which point to use as start, which as end */ if :xa > xb) ( x = xb; Y = yb; xEnd = xa; ) ! else I x = xa; Y = ya; xEnd = xb; 1 setpixel (x, y); while (x < xEnd) ( x++; if lp < 0) $3 += twoDy; else [ y++; g += twoDyDx; ) setpixel (x, y);

 Bresenham's algorithm

thanks for visiting