bresenham演算法演算法思想

Ⅰ 畫圓為什麼要用Bresenham演算法

演算法引入的本意是解決像素填充的問題的
點和線這種東西在理論上都是沒有寬度的，但是要在屏幕上繪制的時候就要去填充像素以形成痕跡
一行上經常有2個以上的像素都被線所貫穿， 如何填充是個問題

而且像素填充本身是使用非常頻繁的需求，故而畫線的演算法效率是非常重要的，對整個系統影響巨大

Bresenham演算法是通過增量計算的方式快速判別下一個行或者列上的要填充的像素的位置，從計算上來說非常的節省，幾乎都是整數的演算法，速度非常的快

Ⅱ 以圓的Bresenham生成演算法為例,圖解矢量圖形和光柵圖形的區別

有電子藝術圖像被分為兩種核心類型：光柵圖像（也稱為「點陣圖」）和矢量圖像。簡而言之，光柵圖像由連接的點組成，矢量是由連接的線組成的圖像。這兩種格式彼此完全不同，但當適當地用於所需的最終輸出方法時，它們彼此形成對比和互補。光柵圖像通過掃描源圖稿或使用照片編輯或繪圖程序（如Corel、PhotoPAINT或Adobe PhotoShop）「繪畫」來創建，而矢量圖像是通過使用CorelDRAW或Adobe Illustrator等矢量插圖程序繪制的過程來創建的。

一、Bresenham演算法原理

由Bresenham提出的一種精確而有效的光柵線生成演算法，可用於顯示線、圓和其他曲線的整數增量運算。它是目前最有效的線段生成演算法。

推導：

設線段端點：(,),(,),∆x和∆y為水平和垂直偏移量,m為斜率

當|m| <= 1時,對於給定的x增量∆x

當|m| >= 1時,對於給定的y增量∆y，

（當 0<m < 1）

假設已經確定了要顯示的像素，那麼，需要確定下一點是繪制在，

還是。

根據直線的方程，直線上處的y坐標為：

將m帶入d1 – d2中，並變換得：

其中，為演算法中第k步的決策參數，c為一常量，其值為。

那麼：

若，即,有

若, 即,有

同理，可求得第k+1步的決策參數

因此，有如下遞推關系：

因為0<m<1 因此，帶入上式得：

其中，的值取決於的值：

當時，，

當時， ，

Bresenham演算法描述 (0 < m < 1)

演算法從線段的起始端點開始，反復計算每個點的決策參數並繪制像素。

起始端點處的決策參數為：

演算法：

1、輸入線段的兩個端點，並將左端點存儲在中；

2、將裝入幀緩沖器，畫出第一個點；

3、計算常量∆x，∆y，2∆y 和2∆y – 2∆x，並得到決策參數的第一個值：

4、從k = 0開始，在沿線的每個處，進行下列檢測：

若，下一個待畫點是，且

若 ，下一個待畫點是，且

5、重復步驟4，共∆x次。

————————————————

版權聲明：本文為CSDN博主「地澤萬物」的原創文章，遵循CC 4.0 BY-SA版權協議，轉載請附上原文出處鏈接及本聲明。

原文鏈接：https://blog.csdn.net/qq_41883085/article/details/102706471

Ⅲ Bresenham直線演演算法的演算方法

Bresenham直線演算法描繪的直線。假設我們需要由 (x0, y0) 這一點，繪畫一直線至右下角的另一點(x1, y1)，x,y分別代表其水平及垂直坐標，並且 x1 - x0 > y1 - y0。在此我們使用電腦系統常用的坐標系，即x坐標值沿x軸向右增長，y坐標值沿y軸向下增長。
因此x及y之值分別向右及向下增加，而兩點之水平距離為x1 − x0且垂直距離為y1-y0。由此得之，該線的斜率必定介乎於1至0之間。而此演算法之目的，就是找出在x0與x1之間，第x行相對應的第y列，從而得出一像素點，使得該像素點的位置最接近原本的線。
對於由(x0, y0)及(x1, y1)兩點所組成之直線，公式如下：
因此，對於每一點的x，其y的值是
因為x及y皆為整數，但並非每一點x所對應的y皆為整數，故此沒有必要去計算每一點x所對應之y值。反之由於此線之斜率介乎於1至0之間，故此我們只需要找出當x到達那一個數值時，會使y上升1，若x尚未到此值，則y不變。至於如何找出相關的x值，則需依靠斜率。斜率之計算方法為m = (y1 − y0) / (x1 − x0)。由於此值不變，故可於運算前預先計算，減少運算次數。
要實行此演算法，我們需計算每一像素點與該線之間的誤差。於上述例子中，誤差應為每一點x中，其相對的像素點之y值與該線實際之y值的差距。每當x的值增加1，誤差的值就會增加m。每當誤差的值超出0.5，線就會比較靠近下一個映像點，因此y的值便會加1，且誤差減1。
下列偽代碼是這演算法的簡單表達（其中的plot(x,y)繪畫該點，abs返回的是絕對值）。雖然用了代價較高的浮點運算，但很容易就可以改用整數運算（詳見最佳化一節）：
function line(x0, x1, y0, y1)
int deltax := x1 - x0
int deltay := y1 - y0
real error := 0
real deltaerr := deltay / deltax // 假設 deltax != 0 （非垂直線），
// 注意：需保留除法運算結果的小數部分
int y := y0
for x from x0 to x1
plot(x,y)
error := error + deltaerr
if abs(error) ≥ 0.5 then
y := y + 1
error := error - 1.0

Ⅳ 直線bresenham演算法基於什麼思路

通過各行、各列像素中心構造一組虛擬網格線，按直線從起點到終點的

順序計算直線各垂直網格線的交點，然後確定該列像素中與此交點最近

的像素。

Ⅳ 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時，會產生取兩個點都可以的問題。這個問題還沒深入。

Ⅵ 關於Bresenham演算法的求助

今天一下子遇到三個類似的問題，所以我這篇東西就連續復制粘貼了三遍：

（下面的坐標本來是有下標的，但復制過來就變沒了，你可能看的有點暈）

Bresenham演算法是Bresenham提出的一種光柵線生成演算法！

DDA演算法表面上看起來很有效，並且代碼也比較容易實現，但是顯示每個像素都需要進行一次浮點數加法運算，而Bresenham演算法的最大優點是不需要進行浮點數運算！這是一種精確而有效的光柵線生成演算法，該演算法僅使用增量整數計算，計算速度比DDA要快，另外，Bresenham演算法還可用於顯示圓和其他曲線，這里暫時只顯示直線！

與DDA一樣，我們假設線段的兩個端點坐標是整數值（x0,y0）（xEnd,yEnd）,且斜率m滿足0<=m>=1!坐標軸的垂直軸表示掃描線位置，水平軸標識像素列，假設以單位x間隔取樣，需要確定下一個每次取樣時兩個可能的像素位置中的哪一個更接近於線路徑！

從給定線段的左端點（x0,y0）開始,逐步處理每個後繼列（x位置），並在其掃描線y值最接近線段的像素處描出一點，假如已經確定要顯示的像素在（xk,yk），那麼下一步就要確定在列xk+1=xk+1上繪制哪個像素，是在位置(xk+1,yk)還是在(xk+1,yk+1)

在取樣位置xk+1，我們使用dlower和pper來標識兩個像素與數學上線路徑的垂直偏移（就是通過這兩個值來比較哪個點離線上的點最近，以下推導過程你可能看得有點暈，但都是為了推出後續的點而已，你可以結合下面例子程序中的Bresenham函數來看），在像素列xk+1處的直線上的y坐標根據直線方程可計算得：

y=m(xk+1)+b

那麼可求得：

dlower=y-yk=m(xk+1)+b-yk

pper=(yk+1)-y=yk+1-m(xk+1)-b

令斜率m=dy/dx,引入決策參數Pk，定義為：

Pk=dx(dlower-pper)

=2dx*xk-2dy*yk+c

C是一個常數，值為2dx+dx(2b-1)

由此可以計算得到

pk+1=Pk+2dy-2dx(yk+1-yk)

其中yk+1-yk取0還是取1取決於參數Pk的符號，Pk為負時取0，Pk非負時取1！

而Pk為負時，下一個要繪制的點就是（xk+1,yk）且pk+1=Pk+2dy

Pk為非負時則下一個要繪制的點就是（xk+1,yk+1）且pk+1=Pk+2dy-2dx

至此，Bresenham演算法介紹完畢，以下為某個示例：

#include<gl/glut.h>

#include<math.h>

#include<stdio.h>

voiddraw_pixel(intix,intiy)

{

glBegin(GL_POINTS);

glVertex2i(ix,iy);

glEnd();

}

voidBresenham(intx1,inty1,intxEnd,intyEnd)

{

intdx=abs(xEnd-x1),dy=abs(yEnd-y1);

intp=2*dy-dx;

inttwoDy=2*dy,twoDyMinusDx=2*dy-2*dx;

intx,y;

if(x1>xEnd)

{

x=xEnd;y=yEnd;

xEnd=x1;

}

else

{

x=x1;

y=y1;

}

draw_pixel(x,y);

while(x<xEnd)

{

x++;

if(p<0)

p+=twoDy;

else

{

y++;

p+=twoDyMinusDx;

draw_pixel(x,y);

}

}

}

voiddisplay()

{

glClear(GL_COLOR_BUFFER_BIT);

Bresenham(0,0,400,400);

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_Lineexample");

glutDisplayFunc(display);

myinit();

glutMainLoop();

}

運行效果：

Ⅶ 分別解釋直線生成演算法DDA法、中點畫線法和Bresenham法的基本原理

DDA稱為數值微分畫線演算法，是直線生成演算法中最簡單的一種。原理相當簡單，就是最直觀的根據斜率的偏移程度，決定是以x為步進方向還是以y為步進方向。然後在相應的步進方向上，步進變數每次增加一個像素，而另一個相關坐標變數則為Yk_1=Yk+m（以x為步進變數為例，m為斜率）
假定直線斜率k在0~1之間，當前象素點為（xp,yp），則下一個象素點有兩種可選擇點P1（xp+1,yp）或P2（xp+1,yp+1）。若P1與P2的中點（xp+1,yp+0.5）稱為M，Q為理想直線與x=xp+1垂線的交點。當M在Q的下方時，則取P2應為下一個象素點；當M在Q的上方時，則取P1為下一個象素點。這就是中點畫線法的基本原理

Bresenham：過各行、各列像素中心構造一組虛擬網格線，按直線從起點到終點的順序計算直線各垂直網格線的交點，然後確定該列像素中與此交點最近的像素。該演算法的優點在於可以採用增量計算，使得對於每一列，只要檢查一個誤差項的符號，就可以確定該列所求的像素。

大概就是這樣，預知詳細，可以參考圖形學的書籍

Ⅷ bresenham演算法的演算法

void IntegerBresenhamlin(int x0,int y0,int x1,int y1,int color)
{
int x,y,dx,dy,unitx,unity,fabs_dx,fabs_dy,e;
unsigned char i;
dx=x1-x0;
dy=y1-y0;
fabs_dx = (int)fabs(dx);
fabs_dy = (int)fabs(dy);
unitx = dx / fabs_dx ;
unity = dy / fabs_dy ;
x=x0;
y=y0;
if( fabs_dx> fabs_dy )
{
e=-fabs_dx;
for(i=0;i<=fabs_dx;i++)
{
drawpixel(x,y,color);
x+=unitx,e=e+2*fabs_dy;
if(e>=0)
{
y+=unity;e=e-2*fabs_dx;
}
} // for end
}
else
{
e-=fabs_dy;
for(i=0;i<=fabs_dy;i++)
{
drawpixel(x,y,color);
y+=unity,e=e+2*fabs_dx;
if(e>=0)
{
x+=unitx;e=e-2*fabs_dy;
}
} // for end
}// if end
} //:~

Ⅸ bresenham演算法的介紹

bresenham演算法是計算機圖形學中為了「顯示器（屏幕或列印機）系由像素構成」的這個特性而設計出來的演算法，使得在求直線各點的過程中全部以整數來運算，因而大幅度提升計算速度。

Ⅹ dda法生成直線的基本原理是什麼為什麼說Bersenham畫圓的演算法效率較高

DDA演算法主要是根據直線公式y = kx + b來推導出來的，其關鍵之處在於如何設定單位步進，即一個方向的步進為單位步進，另一個方向的步進必然是小於1。演算法的具體思路如下：
1. 輸入直線的起點、終點；
2. 計算x方向的間距：△X和y方向的間距：△Y。
3. 確定單位步進，取MaxSteps = max（△X，△Y）; 若△X>=△Y，則X方向的步進為單位步進，X方向步進一個單位，Y方向步進△Y/MaxSteps;否則相反。
4. 設置第一個點的像素值
5. 令循環初始值為1，循環次數為MaxSteps，定義變數x,y，執行以下計算：
a. x增加一個單位步進，y增加一個單位步進
b. 設置位置為（x,y）的像素值

Bresenham演算法是DDA演算法畫線演算法的一種改進演算法。本質上它也是採取了步進的思想。不過它比DDA演算法作了優化，避免了步進時浮點數運算，同時為選取符合直線方程的點提供了一個好思路。首先通過直線的斜率確定了在x方向進行單位步進還是y方向進行單位步進：當斜率k的絕對值|k|<1時，在x方向進行單位步進；當斜率k的絕對值|k|>1時，在y方向進行單位步進。
1. 輸入線段的起點和終點。
2. 判斷線段的斜率是否存在（即起點和終點的x坐標是否相同），若相同，即斜率不存在，
只需計算y方向的單位步進（△Y+1次），x方向的坐標保持不變即可繪制直線。
3. 計算線段的斜率k，分為下面幾種情況處理
a. k等於0，即線段平行於x軸，即程序只需計算x方向的單位步進，y方向的值不變
b. |k|等於1，即線段的x方向的單位步進和y方向的單位步進一樣，皆為1。直接循環△X次計算x和y坐標。
4. 根據輸入的起點和終點的x、y坐標值的大小決定x方向和y方向的單位步進是1還是-1
6. 畫出第一個點。
7. 若|k| <1，設m =0,計算P0，如果Pm>0，下一個要繪制的點為（Xm+單位步進，Ym），
Pm+1 = Pm -2*△Y;
否則要繪制的點為（Xm+單位步進，Ym+單位步進）
Pm+1 = Pm+2*△X-2*△Y；
8. 重復執行第七步△X-1次；
9. 若|k| <1，設m =0,計算Q0，如果Qm>0，下一個要繪制的點為（Xm，Ym+單位步進），
Pm+1 = Pm -2*△X;
否則要繪制的點為（Xm+單位步進，Ym+單位步進）
Pm+1 = Pm+2*△Y-2*△X；
10. 重復執行第9步△Y-1次；