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,至于这一块如何移植，后文再介绍。