Specification
The Bresenham Line Drawing Algorithm
Figure 2
Given two endpoints (Ax, Ay) and (Bx, By), we can chose the start point (xk, yk). The choice is purely arbitrary, it can be either of (Ax, Ay) and (Bx, By) points. From this start point or pixel, we have eight possible choices for the next pixel in the line, since each pixel is surrounded by 8 other pixels (except border pixels). We need to isolate these eight choices into only two choices. If we restrict the slope m for now to 0 <= m <=1 and assume Ax < Bx, we know that we can simply step in x one pixel at a time to the right and determine what y value to choose next. Given (xk, yk), the next ideal pixel (the closest to the real line) will be (xk+1, y)
where y = m*(xk+1) + b
But we must choose between (xk+1, yk) or (xk+1, yk+1) as shown in figure 2. These pixels represent the one just to the right and the one to the right and one up pixel, respectively.
To find the best "next pixel", first we must find the distances (d1 and d2) to the two available choices from the ideal location (of the real line). Distance between pixel-to-right and ideal pixel is:
d1 = y - yk…………. (6)
and the distance between pixel-to-right-and-up and ideal pixel is: d2 = (yk +1) - y……….. (7)
So we can simply choose subsequent pixels based on the following:
if (d1<=d2) then choose pixel-to-right: ( xk+1, yk )
if (d1>d2) then choose pixel-to-right-and-up: ( xk+1, yk+1 )
if (d1>d2) then choose pixel-to-right-and-up: ( xk+1, yk+1 )
In order to develop a fast way of doing this, we will not be comparing these values in such a manner; instead we will create a decision variable that can be used to quickly determine which point to use.
Instead of comparing the two values to each other, we can simply evaluate d1-d2 and test the sign to determine which to choose. If d1 > d2 then d1-d2 will be strictly positive, and if d1-d2 is strictly positive, we will choose pixel-to-right-and-up. If d1-d2 is negative or zero, we will choose pixel-to-right. In addition to this optimization, this Algorithm suggests to optimize more. If we evaluate d1-d2 as follows:
d1-d2 = y - yk - (yk+1 - y) = y - yk - yk+1 + y
and now substitute using
y = m*xk+1 + b, we get
d1-d2 = m*xk+1 + b - yk - yk - 1 + m*xk+1 + b = 2*m*xk+1 - 2*yk + 2*b - 1
The last equation can be reduced by the slope m and substituting as follows:
m = ∆y/∆x
where ∆y = abs(By - Ay) and ∆x = abs(Bx - Ax),
so now we have
d1-d2 = 2*(∆y/∆x)*xk+1 - 2*yk + 2*b - 1
or if we expand the first term (multiply), then:
d1-d2 = 2*(∆y/∆x)*(xk +1) - 2*yk + 2*b - 1
d1-d2 = 2*(∆y/∆x)*xk + 2*(∆y/∆x) - 2*yk + 2*b - 1
This last equation can be simplified by creating a new decision variable
Pk = ∆x * (d1-d2).
This ∆x will remove the divisions (all integer operations for faster and efficient computing) and will still keep the same sign for the decision because ∆x variable is always positive (∆x = abs (Bx - Ax) -> absolute value).
If we now evaluate a new decision variable Pk, we get:
Pk = ∆x * (2*(∆y/∆x)*xk + 2*(∆y/∆x) - 2*yk + 2*b - 1 )
or further: Pk = 2*∆y*xk + 2*∆y - 2*∆x*yk + 2*∆x*b - ∆x
If we now rearrange the terms in the last equation, we get:
Pk = 2*∆y*xk - 2*∆x*yk + 2*∆y + 2*∆x*b - ∆x
or
Pk = 2*∆y*xk - 2*∆x*yk + c
Where c is always constant value (it depends only on the input endpoints) and is equal to 2*∆y + ∆x*(2*b - 1)
Using described approach, decision variable can be computed very efficiently, but it still requires evaluation of Pk for each point (pixel) along a line. Since line entity is linear in its nature, Pk change will be linear as well; therefore we can evaluate subsequent Pk values incrementally by finding a constant change in Pk for each subsequent pixel. By evaluating an incremental change of the decision function
P = ∆P = Pk+1 - Pkwe can evaluate by substitution ∆P as follows:
Pk+1 - Pk = 2*∆y*xk+1 - 2*∆x*yk+1 + c - 2*∆y*xk + 2*∆x*yk - c
= 2*∆y*xk+1 - 2*∆y*xk - 2*∆x*yk+1 + 2*∆x*yk
= 2*∆y*(xk+1 - xk) - 2*∆x*(yk+1 - yk)
Since we are processing pixel one by one in the x direction, the change in the x direction is (xk+1 - xk) = 1, so if we substitute this into our ∆P derivation, we get:
Pk+1 - Pk = 2*∆y - 2*∆x*(yk+1 - yk)
For the y direction, there are two possibilities; the term (yk+1 - yk) can be only 0 or 1, depending on Pk. If we choose pixel-to-right or pixel-to-right-and-up, so now our ∆P derivation looks like:
Pk+1 - Pk = 2*∆y - 2*∆x*(0) = 2*∆y
Pk+1= Pk +2*∆y
if pixel-to-right is chosen.
Pk+1 - Pk= 2*∆y - 2*∆x*(1) = 2*∆y - 2*∆x
if pixel-to-right-and-up is chosen.
The only remaining thing is to decide what the initial value of P0 is. This can be decided by evaluating equation Pk = 2*∆y*xk - 2*∆x*yk + 2*∆y + ∆x*(2*b - 1),
so for zero (k = 0, xk = 0 and yk = 0), we get:
P0 = 2*∆y*x0 - 2*∆x*y0 + 2*∆y + ∆x*(2*b - 1)
From line equation at the starting pixel y0 = m*x0 + b we get term for b intercept b = y0 - m*x0. Substituting b and slope m = ∆y/∆x into equation P0 we get:
P0 = 2*∆y*x0 - 2*∆x*y0 + 2*∆y + ∆x*(2*(y0 - (∆y/∆x)*x0) - 1)
= 2*∆y*x0 - 2*∆x*y0 + 2*∆y + 2*∆x*(y0 - (∆y/∆x)*x0) - ∆x
= 2*∆y*x0 - 2*∆x*y0 + 2*∆y + 2*∆x*y0 - 2*∆y*x0 - ∆x
P0 = 2*∆y - ∆x
Bresenham's Line Algorithm
Begin {Bresenham for lines with slope between 0 and 1}
a := ABS(xend - xstart);
b := ABS(yend - ystart);
d := 2*b - a;
Incr1 := 2*(b-a);
Incr2 := 2*b;
If xstart > xend Then Begin
x := xend;
y := yend
End
Else Begin
x := xstart;
y := ystart
End;
For I := 0 to a Do Begin
Plot(x,y);
x := x + 1;
If d ³ 0 Then Begin
y := y + 1;
d := d + incr1
End
Else
d := d + incr2
End {For Loop}
End; {Bresenham}
Advantages:
This is faster method then DDA because here we have to do only integer calculation.
Disadvantages:
Accumulation of error every time due to rounding in equation.
Source code in C.
#include<graphics.h>
#include<stdlib.h>
#include<stdio.h>
#include<conio.h>
#include<dos.h>
#include<math.h>
void line_solid(int, int, int, int);
void line_dot(int, int, int, int);
void das(int, int, int, int);
void dashdot(int, int, int, int);
//void line_solidt(int, int, int, int);
void main()
{
//Request autodetection
int gdriver = DETECT,gmode,errorcode;
int xmax,ymax,x1,y1,x2,y2,l;
//Initialize graphics and local variables
A:
initgraph(&gdriver,&gmode,"C:\\TC\\BGI");
//Read result of initialization
errorcode=graphresult();
if(errorcode!=grOk) //Error occured
{
printf("Graphics error : %s\n",grapherrormsg(errorcode));
printf("Press any key to halt.");
getch();
exit(1);
}
setcolor(2);
xmax=getmaxx();
ymax=getmaxy();
line_solid((xmax/2)+1,65,(xmax/2)+1,ymax);
line_solid(0,(ymax/2)+57,xmax,(ymax/2)+57);
gotoxy(1,1);
printf("0:Exit 1:Solid 2:Dot 3:Dash 4:DashDot 5:Thick");
gotoxy(1,3);
printf("Enter value for first point (x1,y1) : ");
gotoxy(1,4);
printf("Enter value for second point (x2,y2) : ");
rectangle(0,65,xmax,ymax);
setviewport(1,57,xmax-1,ymax-1,1);
gotoxy(1,2);
printf("Which line you want : ");
gotoxy(23,2);
scanf("%d",&l);
if(l==0)
exit(0);
if(l!=1&&l!=2&&l!=3&&l!=4&&l!=5)
{
gotoxy(45,2);
printf("Enter valid choice");
getch();
clrscr();
goto A;
}
gotoxy(40,3);
printf("(");
gotoxy(45,3);
printf(",");
gotoxy(50,3);
printf(")");
gotoxy(40,4);
printf("(");
gotoxy(45,4);
printf(",");
gotoxy(50,4);
printf(")");
gotoxy(41,3);
scanf("%d",&x1);
gotoxy(46,3);
scanf("%d",&y1);
gotoxy(41,4);
scanf("%d",&x2);
gotoxy(46,4);
scanf("%d",&y2);
if(l==1) line_solid((xmax/2)+x1,(ymax/2)+y1,(xmax/2)+x2,(ymax/2)+y2);
else if(l==2) line_dot((xmax/2)+x1,(ymax/2)+y1,(xmax/2)+x2,(ymax/2)+y2);
else if(l==3) das((xmax/2)+x1,(ymax/2)+y1,(xmax/2)+x2,(ymax/2)+y2);
else if(l==4) dashdot((xmax/2)+x1,(ymax/2)+y1,(xmax/2)+x2,(ymax/2)+y2);
//else if(l==5) line_solidt((xmax/2)+x1,(ymax/2)+y1,(xmax/2)+x2,(ymax/2)+y2);
getch();
goto A;
}
void line_solid(int x1, int y1, int x2, int y2)
{
int dx=abs(x1-x2),dy=abs(y1-y2);
int p=2*dy-dx,m=2*dx-dy;
int twoDy=2*dy,twoDyDx=2*(dy-dx),twoDxDy=2*(dx-dy),twoDx=2*dx;
int x,y,xEnd,yEnd,i;
if(dx>=dy)
{
if(x1>x2)
{
x=x2;
y=y2;
xEnd=x1;
}
else
{
x=x1;
y=y1;
xEnd=x2;
}
putpixel(x,y,1);
while(x<xEnd)
{
x++;
if(p<0)
{
p+=twoDy;
}
else
{
y++;
p+=twoDyDx;
}
putpixel(x,y,15);
}
}
else if(dx<dy)
{
if(x1==x2)
{
i=min(y1,y2);
yEnd=max(y1,y2);
while(i<=yEnd)
{
i=i+1;
putpixel(x1,i,15);
}
}
else
{
if(y1>y2)
{
x=x2;
y=y2;
yEnd=y1;
}
else
{
x=x1;
y=y1;
yEnd=y2;
}
putpixel(x,y,1);
while(y<=yEnd)
{
y++;
if(m<0)
{
m+=twoDx;
}
else
{
x++;
m+=twoDxDy;
}
putpixel(x,y,1);
}
}
}
}
void line_dot(int x1, int y1, int x2, int y2)
{
int dx=abs(x1-x2),dy=abs(y1-y2);
int p=2*dy-dx,m=2*dx-dy;
int twoDy=2*dy,twoDyDx=2*(dy-dx),twoDxDy=2*(dx-dy),twoDx=2*dx;
int x,y,xEnd,yEnd,i,k=0;
if(dx>=dy)
{
if(x1>x2)
{
x=x2;
y=y2;
xEnd=x1;
}
else
{
x=x1;
y=y1;
xEnd=x2;
}
putpixel(x,y,1);
while(x<xEnd)
{
x++,k++;
if(p<0)
{
p+=twoDy;
}
else
{
y++;
p+=twoDyDx;
}
if(k%2==0)
{
putpixel(x,y,15);
} }
}
else if(dx<dy)
{
if(x1==x2)
{
i=min(y1,y2);
yEnd=max(y1,y2);
while(i<=yEnd)
{
i=i+1;
putpixel(x1,i,15);
}
}
else
{
if(y1>y2)
{
x=x2;
y=y2;
yEnd=y1;
}
else
{
x=x1;
y=y1;
yEnd=y2;
}
putpixel(x,y,1);
while(y<=yEnd)
{
y++,k++;
if(m<0)
{
m+=twoDx;
}
else
{
x++;
m+=twoDxDy;
}
if(k%2==0)
{
putpixel(x,y,15);
}
}
}
}
}
void das(int x1, int y1, int x2, int y2)
{
int dx=abs(x1-x2),dy=abs(y1-y2);
int p=2*dy-dx,m=2*dx-dy;
int twoDy=2*dy,twoDyDx=2*(dy-dx),twoDxDy=2*(dx-dy),twoDx=2*dx;
int x,y,xEnd,yEnd,i,k=0;
if(dx>=dy)
{
if(x1>x2)
{
x=x2;
y=y2;
xEnd=x1;
}
else
{
x=x1;
y=y1;
xEnd=x2;
}
putpixel(x,y,1);
while(x<xEnd)
{
x++,k++;
if(p<0)
{
p+=twoDy;
}
else
{
y++;
p+=twoDyDx;
}
if(k%5!=0)
{
putpixel(x,y,15);
}
}
}
else if(dx<dy)
{
if(x1==x2)
{
i=min(y1,y2);
yEnd=max(y1,y2);
while(i<=yEnd)
{
i=i+1;
putpixel(x1,i,15);
}
}
else
{
if(y1>y2)
{
x=x2;
y=y2;
yEnd=y1;
}
else
{
x=x1;
y=y1;
yEnd=y2;
}
putpixel(x,y,15);
while(y<=yEnd)
{
y++,k++;
if(m<0)
{
m+=twoDx;
}
else
{
x++;
m+=twoDxDy;
}
if(k%5!=0)
{
putpixel(x,y,15);
}
}
}
}
}
void dashdot(int x1, int y1, int x2, int y2)
{
int dx=abs(x1-x2),dy=abs(y1-y2);
int p=2*dy-dx,m=2*dx-dy;
int twoDy=2*dy,twoDyDx=2*(dy-dx),twoDxDy=2*(dx-dy),twoDx=2*dx;
int x,y,xEnd,yEnd,i,k=0,j=0;
if(dx>=dy)
{
if(x1>x2)
{
x=x2;
y=y2;
xEnd=x1;
}
else
{
x=x1;
y=y1;
xEnd=x2;
}
putpixel(x,y,1);
while(x<xEnd)
{
x++,k++,i++;
if(p<0)
{
p+=twoDy;
}
else
{
y++;
p+=twoDyDx;
}
if(j%5==0 || k%7==0)
{
putpixel(x,y,15);
}
else if(k%2==0)
{
putpixel(x,y,15);
}
/*else if(k%=0)
{
putpixel(x,y,15);
} */
}
}
else if(dx<dy)
{
if(x1==x2)
{
i=min(y1,y2);
yEnd=max(y1,y2);
while(i<=yEnd)
{
i=i+1;
putpixel(x1,i,15);
}
}
else
{
if(y1>y2)
{
x=x2;
y=y2;
yEnd=y1;
}
else
{
x=x1;
y=y1;
yEnd=y2;
}
putpixel(x,y,1);
while(y<=yEnd)
{
y++,k++;
if(m<0)
{
m+=twoDx;
}
else
{
x++;
m+=twoDxDy;
}
if(k%2==0)
{
putpixel(x,y,15);
}
}
}
}
}
No comments:
Post a Comment