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.

3 Bresenham's Circle Algo

posted Jan 7, 2012, 10:40 PM by Neil Mathew   [ updated Jan 8, 2012, 7:40 AM ]


Explanation:


File:Bresenham circle.svg




The program should make use of basic concept of circle generation algorithm.

This algorithm does only integer arithmetic which makes it faster than floating point. 

We are creating only one octant i.e. from 90 to 45 degree.
We derive other seven octants of circle by symmetry property.

The circle is generated by considering center point as origin with radius ‘r’.
The algorithm calculates one new pixel per step.


One Octant (1/8 circle):

 (x,y) 

symmetry points:

(-x,y)    (x,-y)     (-x,-y)     (y,x)     (-y,x)      (y,-x)     (-y,-x)

(Plotting need not be counterclockwise in what I've done)

The above is assuming the origin is at centre.  (0+x,0+y) 
When a centre (xc,yc) is provided by the user, the points are:

(xc+x, yc+y)    (xc-x, yc+y)      ( xc+x , yc-y )      ( xc-x , yc-y )    
 
 
xc+ y , yc+x )       xc+ y  y c+x )       xc+ y  yc-x)       xc+ y  yc-x )

Caution:
The xc,yc being centre coordinates, they should not be rearranged 
such that the x and ys are together.

 (yc+y,xc+x) = WRONG
(xc+Y, yc+X) = RIGHT



Algo:

1. Input the radius of circle and store end points in (x0,y0) = (0,r).

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

3. Calculate the starting value for decision variable d=3-2r

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

if (di < 0)                                  
the next point is (xi+1,y)
di+1=di + 4xi + 6                     // another way to write: di+1=di + (4xi + 4) + 2 
else
the next point is (xi+1, yi-1)
di+1=di + 4(xi-yi) + 10            // another way to write: di+1=di + (4xi + 4) + 2 + ( - 4yi + 4)

5. repeat 4 while x<=y            //or write it as repeat until x>y



My Notes:

1. when decision variable d < 0, it means the next point is getting inside the circle.
    Therefore Y=y;

    when decision variable d > 0, it means the next point is getting outside the circle/
    There fore Y=y-1;

2. As compared to last time - Bresenham's Normal Line Algo, (but slightly different)
        the X is the regular inc one, while Y is the conditional dec one.

3. Also, in the algo, only one octant is made. Add symmetry points for the others too.



Reason behind the decision Variables


... 

1 DDA Line Algo

posted Jan 7, 2012, 9:48 PM by Neil Mathew   [ updated Jan 8, 2012, 3:01 AM ]





( DDA uses repeated addition )
( Use of floating point operations makes it slightly slower than Bresenham's Algo )


Explanation:

The program should make use of basic concept of DDA’s line generation algorithm.

The DDA is a scan conversion line algorithm based on calculating Dy and Dx. 

We sample the line at unit intervals in one co-ordinate and determine corresponding integer values nearest the line path for the other co-ordinate.1. 

We will consider a line with positive slope

>>If the slope is less than or equal to 1,we sample it at unit x intervals (Dx = 1) and compute each successive y value as 

yk+1 = yk + m

(Subscript k takes integer values starting from 1 for the first point and increases by 1 until the final end point is reached.
The value of m can be any real number between 0 and 1.2)

>>For lines with positive slope greater than 1, we reverse the roles of x and y. We sample at unit y intervals and calculate each succeeding x value as 

xk+1= xk + 1/m

>> For the above equation we are processing the line equation from the left end point to right end point.
 
If this processing is reversed , (negative Slope) so either we have

Dx = -1 and  yk+1 = yk - m  
Or
 Dy = -1 and xk+1= xk - 1/m




Program:

#define ROUND(a) ((int)(a+0.5))

Void lineDDA (int xa , int ya , int xb , int yb)
{

int dx = xb – xa;                       //Calculate Dy Dx (neg value possible)
int dy = yb – ya;

int steps , k ;
float xincr, yincr;


int x = xa, y = ya;                     //Print First pixel as initial pixel
Setpixel(ROUND(x),ROUND(y));


If(abs(dx) > abs(dy))                 //Steps = greater of Dx and Dy (abs values)
steps = abs(dx);

xincr = dx / (float) steps;           //Increment = (-)1 or [ (-) m (for y) or (-)1/m (for x) ]
yincr = dy / (float) steps;           // Implemented how: dx / dx = 1 or dy/dx = m


For(k=0; k<steps; k++)
{
x += xincrement;
y += yincrement;
Setpixel(ROUND(x),ROUND(y));
}

}


1-3 of 3