Sem 4‎ > ‎CG LAB‎ > ‎0 Algorithms‎ > ‎

2 Bresenham's Line Algo

posted Jan 8, 2012, 4:48 AM by Neil Mathew   [ updated Jan 8, 2012, 5:26 AM ]


[Normal]

Explanation: 
 

Here, Normal means when the slope is less than 1 ( 0 < m < 1 ). 

That means, dx is greater than dy. Therefore, x has a regular increase. 
And with every regular increase of x, y is determined by the the closest pixel. 

Unlike DDA Algo, the values of x and y are chosen rather than a repeated addition.

 
Algo (Normal) :

1. Input the starting and ending points and store the starting points in (x0,y0) .

2. Load (x0,y0) into frame buffer and plot the first print.

3. Calculate the constants Δx, Δy, 2Δy, 2Δy-2Δx and obtain starting value of decision parameter.

Δx = x2- x1
Δy = y2-y1

dT= 2(Δy- Δx)
dS= 2(Δy)

d= 2Δy -   Δx

4. At each xi along the starting i=0 perform 

if di < 0 
the next point is (xi+1,yi)
di+1= di +2Δy //+dS

otherwise
the next point is (xi+1,yi +1)                                                                          
di+1= di +2Δy-2Δx //+dT 

5. Repeat step 4 Δx times.


My Notes:

1. T is used to represent the the upper pixel while
    S is used to represent the lower pixel.

2. d is the decision variable which tells me which pixel should be chosen, T or S.
    if d < 0, Negative, it is LOWER, S. (Y=y as X inc by 1)
    if d >=0, Positive, it is UPPER, T.  (Y=y+1 as X inc by 1)

3. Accordingly, if d<0, d+=dS
                        d>=0, d+=dT
    to determine the next decision variable. 

4. Usually, dT is negative as it is the upper One, and dS is positive, S being the Lower one.


[General]

Explanation:  

This uses the same concept however,  General means it works for any slope.

Steps:

1. Initialize:

x=x0;
y=x0;

dx=abs(x2-x1)
dy=abs(y2-y1)

Sx=sign(x2-x1)
Sy=sign(y2-y1)


2. Determine 

IF dy > dx then, // Slope > 1

steps=dy;
flag=1;

//Swap values of dx and dy - To save code rather than create everything again just for specific dx dy
t=dx; dx=dy; dy=t;

else

steps=dx;
flag=0;             //flag=0, dx > dy (same as Normal)

END IF

Pk= 2dy-dx;   //Pk decision variable
setpixel(x,y);

for(i=1 to steps)

while ( Pk>0 )

IF flag=1 then
Xi+1=Xi+Sx
else                  // You should understand and KNOW flag=0
Yi+1=Yi + Sy    // When Pk>0 +dT X=X+1 Y=Y+1 (Conditional Inc one)
 
END IF

Pk=Pk-2dx       // + dT is 2dy-2dx, So, the remaining +2dy (+dS) is given below in parts. (dT=dS-dx)

END WHILE


IF flag=1 then
Yi+1=Yi+1
else
Xi+1=Xi+1        // if the Pk<=0, while not included. if flag=0, +dS & Y=Y X=X+1 (Regular Inc one)

END IF

Pk=Pk+2dy

Setpixel(x,y);

NEXT(i);
FINISH          // used in Algos for end of For loop   






The Reason behind Decision Variable, dS, dT



Based on above diagram:

If (BlueLine < Midpoint)
   Plot_East_Pixel();
Else
   Plot_Northeast_Pixel();


What if we came up with an equation, given a line and a point, that will tell us if 
the line is above or below that line?  Let's play with the line equation.
y= dy/dx x + B

dx *y = dy* x + B *dx                (rewritten)

0 = dy* x - dx* y + B*dx                     (rewritten again)


Notice that the left side of this equation equals zero on the line.  

It can be shown that for any point x, y above the line, the right side of the equation becomes a negative number, and any point x,y below the line becomes positive.  

Or, in other words, if we define a line function F:
F( x, y) = 2 * dy* x - 2 * dx * y + 2 * B * dx

Then for any point (x,y) that represents a midpoint between the next East or 
Northeast pixel, 
F(x,y) < 0,    when     BlueLine < Midpoint
F(x,y) > 0,    when     BlueLine > Midpoint


Note also that I changed the equation to include a factor of 2.  This will be 
explained in a moment; but realize for now that this factor does not change the 
results of the equation; positive numbers remain positive, and negative numbers 
remain negative.

Using The Line Function

For the first midpoint, given by (x1+1, y1+1/2), we can use our equation F(x,y) to 
determine if the second pixel (after x1,y1) to light up should be (x1+1, y1) or (x1+1, y1+1). 

Next, look at the line function on (x1, y1):
F(x1, y1) = 2* dy * x1- 2 * dx* y1+ 2* B* dx = 0

therefore
F(x1+1, y1+1/2) = 2*dy*x1 + 2*dy – 2*dx*y1 – dx + 2*B*dx

d0 = F(x1+1, y1+1/2) = 2*dy – dx

We call this value d0 (for "decision variable – initial value")

Now, for the next midpoint, we either evaluate F(x1+2, y1+1/2) or F(x1+2, y1+3/2), 
depending on whether we chose the East or Northeast pixel for the first midpoint, respectively.  


As it turns out, we can exploit the nature of our Line Function F(x,y) because of 
the relationship between successive midpoints. 

Let's calculate the difference in the Line Function between midpoints, 
depending on our previous pixel choice:

incE = F(Mx+1, My) – F(Mx,My)   = 2*dy                  (E pixel) (dS)
incNE = F(Mx+1, My+1) – F(Mx, My) = 2*dy – 2*dx   (NE pixel)  (dT)

To clarify; each time we make a decision on the choice of East or Northeast, we 
must make a new calculation based on the new midpoint.  

As shown above, an 
East choice means the x-component of the midpoint increases but the y component does not.  

So now, all we really have to do is calculate the initial value of d0 and loop through the pixels, recalculating the value of F(x,y).   

The beauty of this is that all of the values incE, incNE, and d0 are constant integers.



Speaking of which, remember that factor of two we introduced to F(x,y)?  That 
was added because each midpoint falls halfway between two pixels, and simply 
by multiplying both sides of that equation by 2, we can get an equation that uses
only integers.  How sweet.