-->
Bresenham’s Line Algorithm -MASTER GUIDE

Bresenham’s Line Algorithm -MASTER GUIDE

 Bresenham’s Line Algorithm

 This is an accurate and efficient raster line-generating algorithm. This algorithm scan converts lines using only incremental integer calculations. Fig:1 illustrates section of a display screen where straight line segments are to be drawn. The vertical axes show-scanline 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. Starting from the left endpoint shown in fig 1: we need to determine at the next sample position whether to plot the pixel at position (11, 11) or the one at (11, 12).


To illustrate Bresenham's approach, 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 endpoint(x0, y0) 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. Assuming we have determined that the pixel at (xk, yk) is to be displayed, we next need to decide which pixel to plot in column xk+1. Our choices are the pixels at positions (xk+l, yk) and (xk +l, yk+l).

At sampling position xk+l, we label vertical pixel separations from theFig-3 mathematical line path as d1and d2 (Fig. 2). They coordinate on the mathematical line at pixel column position xk+l is calculated as y=m(xk+1) + b 
then, d1= y - yk=m(xk+1) + b - yk 
and d2= (yk + 1) – y = yk + 1 - m(xk+1) - b 

calculate d1-d2 
(d1-d2 )=2 m(xk+1) - 2yk + 2b – 1 ➡(I)

If (d1-d2) < 0 then yk+1= yk 
If (d1-d2) > 0 then yk+1 = yk+ 1 

In the equation (I) substitute ∆y/ ∆x for m multiply throughout by ∆x and call it as pk (Decision Parameter).

(d1-d2) = 2 ∆𝑦 ∆𝑥 . (xk+1) - 2yk + 2b – 1 
∆x (d1-d2) = 2 ∆yxk– 2∆x yk+ C 

Therefore, pk= 2 ∆yxk– 2∆x yk+ C  ➡(II) 
where C is a constant and is equal to 2∆y + 2∆xb - ∆x 

The sign of pk is the same as the sign of dl –d2, since ∆x>0for our example. Parameter C is
constant and has the value 2∆y + 2∆xb - ∆x, which is independent of pixel position. If the
pixel at yk is closer to the line path than the pixel at yk+ 1 (that is, d1<d2), then decision
parameter pkis negative. In that case, we plot the lower pixel i.e., (xk+l, yk); otherwise, we
plot the upper pixel i.e., (xk +l, yk +l).

At step k + 1, the decision parameter is evaluated from equation (II) as 
pk+1 = 2 ∆yxk+1 – 2∆x yk+1 + C ➡(III) 
(III) – (II) gives 
            pk+1 - pk= 2 ∆y(xk+1 - xk) - 2∆x(yk+1 - yk) 
But, xk+1 =xk+ 1. So, 
pk+1 = pk+ 2 ∆y - 2∆x(yk+1 - yk)

where the term (yk+1 - yk) is either 0 or 1, depending on the sign of parameter pk. The term (yk+1 - yk) will be 0 if pk is negative or it will be 1 if pk is positive.

Therefore, if pk< 0, pk+1 = pk+ 2∆y 
         if pk> 0, pk+1 = pk+ 2∆y - 2∆x   

This recursive calculation of decision parameters is performed at each integer x-position, starting at the left coordinate endpoint of the line. The first parameter, p0 is evaluated from equation II at the starting pixel position (x0, y0) and with m evaluated as ∆𝑦 ∆𝑥 ,

                        p0 = 2 ∆yx0 – 2∆x y0 + C , we know that C = 2∆y + 2∆xb - ∆x 
                        p0 = 2 ∆yx0 – 2∆x y0 + 2∆y + 2∆xb - ∆x ➡(IV) 
we also know that y0 = mx0 + b, so b= y0 - mx0 = y0 –( ∆𝑦 ∆𝑥 ) x0 
Substituting this for b in equation (IV) we get , 
p0 = 2 ∆yx0 – 2∆x y0 + 2∆y + 2∆x (y0 – ∆𝑦 ∆𝑥 x0) - ∆x 
On Solving, we get, 
p0 = 2∆y - ∆x➡ (V)

Summary of Bresenham's Line-Drawing Algorithm for | m|<1

1. Input the two line endpoints and store the left endpoint in (x0, y0) and right
endpoint in (x1, y1)
2. Plot the pixel at (x0, y0)
3. Calculate constants ∆x, ∆y, 2∆y, 2∆y - 2∆x and obtain the starting value for the
decision parameter as p0 = 2∆y - ∆x
4. At each xkalong the line, starting at k = 0, perform the following test:
If pk< 0, the next point to plot is (xk+l, yk)and
pk+1 = pk+ 2∆y
Otherwise, the next point to plot is (xk +l, yk +l) and
pk+1 = pk+ 2∆y - 2∆x
5. Increment k.
6. Repeat while xk<x

Algorithm

void lineBres (int xa, int ya , int xb, int yb)
{
    int dx = abs( xa- xb ) , dy= abs (ya- yb):
    int p = 2 * dy- dx ;
    inttwoDy= 2 * dy,twoDyDx= 2 * (dy - dx);
    intx , y, xEnd;
    /*Determine which point to use as start, which asend * /
    if(xa>xb )
    {
        x = xb;
        y= yb;
        xEnd= xa;
       }
    else
    {
        x = xa;
        y= ya;
        xEnd= xb;
    }
    setPixel (x, y);
    while (x <xEnd)
    {
        x++;
        if (p <0)
            {
                setPixel(x,y); 
                p = p +twoDy; 
            }
         else 
        {
             y++; setPixel(x,y); 
                p=p+twoDyDx; 
        
    }
}

0 Response to "Bresenham’s Line Algorithm -MASTER GUIDE"

Post a Comment

Iklan Atas Artikel

Iklan Tengah Artikel 1

Iklan Tengah Artikel 2

Iklan Bawah Artikel