bresenham演算法原理
1. 分別解釋直線生成演算法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：過各行、各列像素中心構造一組虛擬網格線，按直線從起點到終點的順序計算直線各垂直網格線的交點，然後確定該列像素中與此交點最近的像素。該演算法的優點在於可以採用增量計算，使得對於每一列，只要檢查一個誤差項的符號，就可以確定該列所求的像素。
大概就是這樣，預知詳細，可以參考圖形學的書籍
2. 關於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();
}
運行效果：
3. bresenham演算法的介紹
bresenham演算法是計算機圖形學中為了「顯示器（屏幕或列印機）系由像素構成」的這個特性而設計出來的演算法，使得在求直線各點的過程中全部以整數來運算，因而大幅度提升計算速度。
4. 畫圓為什麼要用Bresenham演算法
演算法引入的本意是解決像素填充的問題的
點和線這種東西在理論上都是沒有寬度的，但是要在屏幕上繪制的時候就要去填充像素以形成痕跡
一行上經常有2個以上的像素都被線所貫穿， 如何填充是個問題
而且像素填充本身是使用非常頻繁的需求，故而畫線的演算法效率是非常重要的，對整個系統影響巨大
Bresenham演算法是通過增量計算的方式快速判別下一個行或者列上的要填充的像素的位置，從計算上來說非常的節省，幾乎都是整數的演算法，速度非常的快
5. 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次；
6. 運動控制器2：GRBL的核心結構體block_t和BRESENHAM演算法
typedef struct {
第一部分：bresenham演算法需要的入口條件，包括運動方向，X,Y,Z各需要運動多少步，以及完成這個BLOCK需要運動多少步。
uint8_t direction_bits; //
uint32_t steps_x, steps_y, steps_z; //
int32_t step_event_count; //
Bresenham直線演算法是用來描繪由兩點所決定的直線的演算法，它會算出一條線段在 n 維光柵上最接近的點。這個演算法只會用到較為快速的整數加法、減法和位元移位，常用於繪制電腦畫面中的直線。是計算機圖形學中最先發展出來的演算法。
GRBL中，圓弧是用直線段來接近描述的，所以不需要考慮，直接的畫法通過下面的判斷器，X先走。
把縱軸的一個方格的一半作為基準，如果在基準點以上，則Y軸走一步，如果在下面，則X繼續走一步。而step_event_count為最終走的總步數，為X+Y總步數。
第二部分：
調度器用於計算加速度的內容，也就是說，BRESENHEM用到的是梯形加速度，我們需要計算梯形的各個表徵值。
float nominal_speed; // 勻速運動速度
float entry_speed; // 從一個BLOCK進入到這個BLOCK的速度
float max_entry_speed; // 最大的進入速度
float millimeters; // BLOCK運動的實際mm距離
uint8_t recalculate_flag; // 重新計算梯度的FLAG
uint8_t nominal_length_flag; // 是否進入了勻速的FLAG
第三部分：
實際梯形的各個參數計算
uint32_t initial_rate; // 梯形運動初始值
uint32_t final_rate; // 梯形運動結束
int32_t rate_delta; //計算加速度
uint32_t accelerate_until; // 加速度階段運動的距離
uint32_t decelerate_after; // 減速度階段運行的距離
uint32_t nominal_rate; // 勻速階段運行的距離
} block_t;
實際上，BLOCK的執行需要一定的時間，所以沒有執行完成的BLOCK需要列隊進行等待，所以需要用到調度器。
目前，3D列印機做開源的主要用到了Marlin固件，其實核心演算法就是GRBL,加入了兩軸材料擠出的步進電機軸，另外還用到了一個開源的溫控PID演算法，這個我們暫時用不上，不再考慮。
在找Marlin固件時發現了一個好的晶元，TC2100這顆IC賣出的價格在20元以上，而市面上用的1.5A電流的晶元大部分只賣到了4元左右，這顆IC的核心優勢就是細分數，看了一下資料，也用到了他們的專利演算法：一種新型的PWM演算法，淘寶上賣出的模塊價格在37元左右，其實還有不少的利潤空間，可惜拿貨估計有點麻煩，訂單小了估計都不好拿貨。
另外需要注意的是，初始化的參數是存放在EEPROM中的，GRBL也有一個EEPROM的函數，但是實際上我們定義了我們新的EEPROM函數，用到的是W24512,至於這一塊如何移植，後文再介紹。