bresenham演算法
A. 直線掃描演算法（個人總結，僅供參考）
直線掃描演算法主要包含三種演算法，DDA演算法、中點畫線演算法、Bresenham直線演算法。
這三種演算法都要事先要確定兩個端點（起點和終點），從起點開始每次走一步，每走一步畫一個點，直至到達終點。
這個前提也比較好理解，因為如果朝斜率大的方向走，可能沒走幾步就走完了，那畫出來的直線就是離散的。
以下我們只討論朝x方向移動的情況。（y方向的情況是一樣的）
DDA演算法實際上是根據 斜截式直線方程 來畫的。
但這么做實際上是比較消耗性能的，因為斜截式方程， 它涉及到了乘法運算 。因此我們需要通過 增量思想 對它進行優化。
這樣轉換後，我們就可以根據當前的位置來找到下一步的位置，且每次計算只需要進行一次 浮點的加法運算 ，一次四捨五入取整即可。
中點畫線演算法實際上是根據 一般式直線方程 來畫的。它是通過判斷中點在直線的下方還是上方，來決定下一步的坐標位置。
但這樣也是非常消耗性能的，把中點帶入F(x, y)中，會涉及到2個乘法，4個加法。我們依然可以通過增量的方式來對它進行優化。
這樣我們就優化到每次只需要一次 整數加法 即可，且還不需要四捨五入。因此它要更優於DDA演算法。
Breseham演算法是通過比較d(交點與交點下方最近的點的距離)來進行選擇的。d每次按照k的大小增加。
但這么做依舊和DDA演算法一樣，會涉及到浮點數k的加法。我們可以通過 換元的方式 對它進行下優化。
這樣就能使得每次進行一次或兩次的 整數加法運算 ，不需要四捨五入。效率高於DDA，低於中點畫線演算法。
但Bresenham演算法不依賴直線方程，使得它能有更寬泛的適用范圍。
B. bresenham演算法 和 dda 演算法哪個效果好
esenham演算法的特點是:
1,不必計算直線之斜率,因此不做除法;
2,不用浮點數,只用整數;
3,只做整數加減法和乘2運算,而乘2運算可以用硬體移位實現.
Bresenham演算法速度很快,並適於用硬體實現.
DDA演算法的特點:
浮點數運算
不易硬體實現
中點畫線法特點:
只有整數運算,不含乘除法
可用硬體實現
因(X0,Y0)在直線上,所以F(X0,Y
C. 用C實現Bresenham演算法生成直線和圓的程序(要求具體步驟有必要解述)
Bresenham演算法生成直線
假定直線從(x1,y1)到(x2,y2)，
令dx=x2-x1，dy=y2-y1
不妨設(dx,dy)在第一象限,並且直線的斜率不大於1
畫線過程中有三個循環變數
x,y,d
初值
x=x1,y=y1,d=2*dy-dx
循環，直到x==x2為止
{
如果d>=0,y++,d+=2*(dy-dx)
如果d<0 ,x++,d+=2*dy
}
如果(dx,dy)不在第一象限，要做變換，即先把第一象限的畫出來
如果斜率大於1，x,y交換
非常簡單的，很容易實現
圓的演算法：
int Bres(int x0,int y0,double r,int color)
{
int x,y,d;
x=0;
y=(int)r;
d=(int)(3-2*r);
while(x<y)
{
cirpot(x0,y0,x,y,color);
if(d<0)
d+=4*x+6;
else
{
d+=4*(x-y)+10;
y--;
}
x++;
}
if(x==y)
cirpot(x0,y0,x,y,color);
return(0);
}
int cirpot(int x0,int y0,int x,int y,int color)
{
setcolor(color);
putxicl((x0+x),(y0+y));
putxicl((x0+y),(y0+x));
putxicl((x0+y),(y0-x));
putxicl((x0+x),(y0-y));
putxicl((x0-x),(y0-y));
putxicl((x0-y),(y0-x));
putxicl((x0-y),(y0+x));
putxicl((x0-x),(y0+y));
setcolor(color);
return(0);
}
這是圓的演算法，你若要整個程序，把你的電郵給我，我給你發過去、
運行環境是Turboc 2.0
int Bresline(int x1,inty1,int x2,int y2,int color)
{
int color,itag;
int dx,dy,tx,ty,inc1,inc2,d,curx,cury;
setcolor(color);
putxicl(x1,y1);
if(x1==x2&&y1==y2)
{
setcolor(color);
return(1);
}
itag=0;
dx=abs(x2-x1);
dy=abs(y2-y1);
if(dx<dy)
{
itag=1;]
iswap(&x1,&y1);
iswap(&x2,&y2);
iswap(&dx,&dy);
}
tx=(x2-x1)>0? 1:-1;
ty=(y2-y1)>0? 1:-1;
curx=x1;
cury=y1;
inc1=2*dy;
inc2=2*(dy-dx);
d=inc1-dx;
while(curx!x2)
{
if(d<0)
{
d+=inc1;
}
else
{
cury+=ty;
d+=inc2;
}
if(itag)
setpixel(cury,curx);
else
setpixel(curx,cury);
curxd+=tx;
}
setcolor(color);
return(0);
}
iswap(int*a,int*b)
{
int tmp;
tmp=*a;
*a=*b;
*b=tmp;
}
這是直線的演算法：和圓的差不多，你可以參考一下：）
D. bresenham演算法的Bresenham改進演算法
原理:
上述bresenham 演算法在計算直線斜率與誤差項時用到了小數與除法，可以改用整數以避免除法。由於演算法中用到談旅好誤差含鉛項的符號，因此可以做如下替換：e'=2*e*dx.
以下是C++語言方式描述的，在MFC下的鎮兄核心繪圖代碼（畫圓的演算法）
{
CDC* pDC=GetDC();
int p,r,x,y,c,i;
r=50;
p=3-2*r;
c=RGB(0,0,0);
x=0;
y=r;
i=100;
for(;x<=y;)
{
pDC->SetPixel(x+i,y+i,c);
pDC->SetPixel(-x+i,-y+i,c);
pDC->SetPixel(-x+i,y+i,c);
pDC->SetPixel(x+i,-y+i,c);
pDC->SetPixel(y+i,x+i,c);
pDC->SetPixel(-y+i,x+i,c);
pDC->SetPixel(-y+i,-x+i,c);
pDC->SetPixel(y+i,-x+i,c);
if(p<0)p=p+4*x+6;
else {y--;p=p+4*(x-y)+10;}
x++;
}
}
E. 請問中點bresenham演算法畫圓與bresenham演算法畫圓有區別嗎
Bresenham演算法畫圓：
Bresenham演算法用來畫直線非常方便，但上次也說了，Bresenham演算法也可以用來顯示圓和其他曲線，只需要把直線方程改成圓方程或者其他曲線的方程就行，具體的推理過程就不演示了，大體跟直線的差不多！但由推算的結果可以看出，用Bresenham演算法來畫圓的確是不大明智的做法，要計算的步驟太多，計算速度比專門的畫圓方法慢很多！並且在斜率越大的地方像素的間距就越大，當然我們可以在畫某個像素之前先判斷一下這一點跟前面一點的連線的斜率，然後在適當的時候交換x、y的坐標，但這樣計算量必將增加！
直接給出Bresenham畫圓的代碼：
#include<gl/glut.h>
#include<math.h>
#include<stdio.h>
voiddraw_pixel(intix,intiy)
{
glBegin(GL_POINTS);
glVertex2i(ix,iy);
glEnd();
}
//intinlineround(constfloata){returnint(a+0.5);}
voidBresenham(intx1,inty1,intr,doublea,doubleb,doublec)/*圓心在（x1，y1），半徑為r的圓*/
{
glColor3f(a,b,c);
intdx=r;//intdy=abs(yEnd-y1);
//intp=2*dy-dx;
//inttwoDy=2*dy,twoDyMinusDx=2*dy-2*dx;
intx,y,d1,d2;
/*if(x1>xEnd)
{
x=xEnd;y=yEnd;
xEnd=x1;
}
else
{
x=x1;
y=y1;
}
*/
x=x1;
y=y1+r;
draw_pixel(x1,y1);
draw_pixel(x,y);//起始點裝入幀緩存,起始點是圓的最上面一點，然後按順時針來畫
while(x<=x1+dx)
{
d1=y1+sqrt(pow(r,2)-pow(x-x1,2));/*lower*/
x++;
d2=2*(y1+sqrt(pow(r,2)-pow(x-x1,2)))-2*d1-1;/*lower-upper*/
if(1)
{
y=d1;
draw_pixel(x,y);
draw_pixel(x,2*y1-y);
draw_pixel(2*x1-x,y);
draw_pixel(2*x1-x,2*y1-y);
}
else
{
y++;
//p+=twoDyMinusDx;
draw_pixel(x,y);
}
}
}
voiddisplay()
{
glClear(GL_COLOR_BUFFER_BIT);
Bresenham(250,250,200,0.0,0.0,1.0);
Bresenham(300,250,150,1.0,0.0,0.0);
Bresenham(200,250,150,0.0,1.0,0.0);
//Bresenham(250,300,150,0.8,0.4,0.3);
//Bresenham(250,200,150);
glFlush();
}
voidmyinit()
{
glClearColor(0.8,1.0,1.0,1.0);
//glColor3f(0.0,0.0,1.0);
glPointSize(1.0);
glMatrixMode(GL_PROJECTION);
glLoadIdentity();
gluOrtho2D(0.0,500.0,0.0,500.0);
}
voidmain(intargc,char**argv)
{
glutInit(&argc,argv);
glutInitDisplayMode(GLUT_SINGLE|GLUT_RGB);
glutInitWindowSize(500,500);
glutInitWindowPosition(200.0,200.0);
glutCreateWindow("CG_test_Bresenham_Circleexample");
glutDisplayFunc(display);
myinit();
glutMainLoop();
}
以下為程序運行效果：
中點畫圓：
用光柵畫圓的不足在上次已經用實例表示的很明白了，上次畫的那個圓怎麼都不能算滿意，雖然可以通過修改演算法來得到改善，但本來計算步驟就已經很多了，交換坐標重新計算將會大大增加計算機的就是負擔，為此我們採用另一種更加常用的畫圓演算法——中點畫圓演算法，之所以叫做「中點」畫圓演算法是由於它不是像Bresenham演算法那樣所繪像素不是（xk+1,yk）就是（xk+1,yk+1）,而是根據這兩個點的中點來判斷是（xk+1,yk）還是（xk+1,yk-1）更接近於圓！
對於給定的半徑r和圓心（x0,y0）,我們先計算圓心在原點（0,0）的點，然後將其平移到圓心（x0,y0）處即可，跟Bresenham演算法一樣，我們也可以藉助圓的高度對稱性來減少計算機的計算步驟，在這里我們可以先計算出八分之一圓的像素點，然後根據對稱性繪出其他點。這樣可以大大加快畫圓的速度！
跟光柵化方法一樣，我們還是採用步進的方法來逐點描繪，但這里的決策參數計算方式跟Bresenham不大一樣，設決策參數為p，則：
P=x2+y2-r2
對於任一個點（x，y），可以根據p的符號來判斷點是在圓內還是圓外還是在圓上，這里不多說，假設我們在（xk,yk）處繪制了一個像素，下一步需要確定的是（xk+1,yk）還是（xk+1,yk-1）更接近於圓，在此代入這兩個點的中點來求出決策參數：
Pk=（xk+1）2+（yk-1/2）2-r2
如果Pk<0,則yk上的像素更接近於圓，否則就是yk-1更接近於圓
同理可以推出Pk+1=Pk+2（xk+1）+（yk+12-yk2）-（yk+1-yk）+1
給出一個示例，這個圓比用Bresenham畫出來的好看多了：
#include<glglut.h>
classscreenPt
{
private:
intx,y;
public:
screenPt(){x=y=0;}
voidsetCoords(GLintxCoordValue,GLintyCoordValue)
{
x=xCoordValue;
y=yCoordValue;
}
GLintgetx()const
{
returnx;
}
GLintgety()const
{
returny;
}
voidincrementx(){x++;}
voiddecrementy(){y--;}
};
voiddraw_pixel(intxCoord,intyCoord)
{
glBegin(GL_POINTS);
glVertex2i(xCoord,yCoord);
glEnd();
}
voidcircleMidpoint(GLintxc,GLintyc,GLintradius)
{
screenPtcircPt;
GLintp=1-radius;
circPt.setCoords(0,radius);
voidcirclePlotPoints(GLint,GLint,screenPt);
circlePlotPoints(xc,yc,circPt);
while(circPt.getx()<circPt.gety())
{
circPt.incrementx();
if(p<0)
p+=2*circPt.getx()+1;
else
{
circPt.decrementy();
p+=2*(circPt.getx()-circPt.gety())+1;
}
circlePlotPoints(xc,yc,circPt);
}
}
voidcirclePlotPoints(GLintxc,GLintyc,screenPtcircPt)//描繪八分圓各點
{
draw_pixel(xc+circPt.getx(),yc+circPt.gety());
draw_pixel(xc-circPt.getx(),yc+circPt.gety());
draw_pixel(xc+circPt.getx(),yc-circPt.gety());
draw_pixel(xc-circPt.getx(),yc-circPt.gety());
draw_pixel(xc+circPt.gety(),yc+circPt.getx());
draw_pixel(xc-circPt.gety(),yc+circPt.getx());
draw_pixel(xc+circPt.gety(),yc-circPt.getx());
draw_pixel(xc-circPt.gety(),yc-circPt.getx());
}
voiddisplay()
{
//screenPtPt;
glClear(GL_COLOR_BUFFER_BIT);
circleMidpoint(250,250,200);
glFlush();
}
voidmyinit()
{
glClearColor(0.8,1.0,1.0,1.0);
glColor3f(0.0,0.0,1.0);
glPointSize(1.0);
glMatrixMode(GL_PROJECTION);
glLoadIdentity();
gluOrtho2D(0.0,500.0,0.0,500.0);
}
voidmain(intargc,char**argv)
{
glutInit(&argc,argv);
glutInitDisplayMode(GLUT_SINGLE|GLUT_RGB);
glutInitWindowSize(500,500);
glutInitWindowPosition(200.0,200.0);
glutCreateWindow("CG_test_中點畫圓example");
glutDisplayFunc(display);
myinit();
glutMainLoop();
}
運行效果：
F. bresenham演算法的介紹
bresenham演算法是計算機圖形學中為了「顯示器（屏幕或列印機）系由像素構成」的這個特性而設計出來的演算法，使得在求直線各點的過程中全部以整數來運算，因而大幅度提升計算速度。
G. Bresenham畫線演算法
基本上Bresenham畫線演算法的思路如下:
// 假設該線段位於第一象限內且斜率大於0小於1,設起點為(x1,y1),終點為(x2,y2).
// 根據對稱性,可推導至全象限內的線段.
1.畫起點(x1,y1).
2.准備畫下個點。x坐標增1，判斷如果達到終點，則完成。否則，由圖中可知,下個要畫的點要麼為當前點的右鄰接點,要麼是當前點的右上鄰接點.
2.1.如果線段ax+by+c=0與x=x1+1的交點的y坐標大於M點的y坐標的話,下個點為U(x1+1,y1+1)
2.2.否則,下個點為B(x1+1,y1+1)
3.畫點(U或者B).
4.跳回第2步.
5.結束.
這里需要細化的是怎麼判斷下個要畫的點為當前點的右鄰接點還是當前點的右上鄰接點.
設線段方程：ax+by+c=0(x1<x<x2,y1<y<y2)
令dx=x2-x1,dy=y2-y1
則：斜率-a/b = dy/dx.
從第一個點開始，我們有F(x,1,y1) = a*x1+b*y1+c=0
下面求線段ax+by+c=0與x=x1+1的交點:
由a*(x1+1)+b*y+c = 0, 求出交點坐標y=(-c-a(x1+1))/b
所以交點與M的y坐標差值Sub1 = (-c-a(x1+1))/b - (y1+0.5) = -a/b-0.5，即Sub1的處始值為-a/b-0.5。
則可得條件當 Sub1 = -a/b-0.5>0時候,即下個點為U.
反之,下個點為B.
代入a/b,則Sub1 = dy/dx-0.5.
因為是個循環中都要判斷Sub,所以得求出循環下的Sub表達式,我們可以求出Sub的差值的表達式.下面求x=x1+2時的Sub，即Sub2
1.如果下下個點是下個點的右上鄰接點，則
Sub2 = (-c-a(x1+2))/b - (y1+1.5) = -2a/b - 1.5
故Sub差值Dsub = Sub2 - Sub1 = -2a/b - 1.5 - (-a/b-0.5) = -a/b - 1.代入a/b得Dsub = dy/dx -1;
2.如果下下個點是下個點的右鄰接點，
Sub2 = (-c-a(x1+2))/b - (y1+0.5) = -2a/b - 0.5
故Sub差值Dsub = Sub2 - Sub1 = -2a/b - 0.5 - (-a/b-0.5) = -a/b. 代入a/b得Dsub = dy/dx;
於是，我們有了Sub的處始值Sub1 = -a/b-0.5 = dy/dx-0.5,又有了Sub的差值的表達式Dsub = dy/dx -1 （當Sub1 > 0）或 dy/dx（當Sub1 < 0）.細化工作完成。
於是pcode可以細化如下：
// Pcode for Bresenham Line
// By SoRoMan
x=x1;
y=y1;
dx = x2-x1;
dy = y2-y1;
Sub = dy/dx-0.5; // 賦初值，下個要畫的點與中點的差值
DrawPixel(x, y); // 畫起點
while(x<x2)
{
x++;
if(Sub > 0) // 下個要畫的點為當前點的右上鄰接點
{
Sub += dy/dx - 1; //下下個要畫的點與中點的差值
y++; // 右上鄰接點y需增1
}
else// 下個要畫的點為當前點的右鄰接點
{
Sub += dy/dx;
}
// 畫下個點
DrawPixel(x,y);
}
PS:一般優化：
為避免小數轉整數以及除法運算，由於Sub只是用來進行正負判斷，所以可以令Sub = 2*dx*Sub = 2dy-dx,則
相應的DSub = 2dy - 2dx或2dy.
思考1:如果Sub = 0時，會產生取兩個點都可以的問題。這個問題還沒深入。