一、DDA
DDA算法是最简单的直线绘制算法。主要思想是利用直线的斜截式：\(y=kx+b\)
对于一条直线的绘制，往往会给定两个端点：\(P_A = (0,0)\)和\(P_B = (60,60)\)
然后调用函数：OLED_DrawLine(0, 0, 60, 60);
首先，我们来看一下绘制直线都可以用哪些方法。
确定了两个端点，那么两个端点之间的点如何确定？
第一个可以想到：知道了两个点，可以用两点式来确定直线方程，然后带入点不就行了！
calc line expression f(x) from two point
for x in range(x_start, x_end):
y = f(x)
draw(x, y)
这是一个方法，不过这个方法可能要反复进行复杂数学运算（毕竟不可能所有的直线都是：\(y=x、y=x+1、...\)这类吧，但凡带点乘除、浮点的，统统都是复杂运算）
这个方法貌似不可行，不仅要确定直线的表达式，还要进行多次复杂的浮点数乘法运算。还记得在之前的文章（将三角形重心坐标时）简单介绍过线性组合...
巧了，这里正好有两个点，妥妥的线性组合哇。
线性组合公式：\(P' = tP_A + (1-t)P_B, 其中 t \in [0,1]\)
for t in range(0, accu, x num):
(x, y) = tPa + (1-t)Pb
draw(x, y)
虽然不用先计算直线的表达式，但是需要2N次的浮点数乘法。有点得不偿失。
这个方法也不得行。
那么可不可以每次让\(P_A\)加上一个值，\(P_B\)减去一个值，然后利用迭代的思想，逐个求出每一个点呢？
答案是可以的。
不妨用下面的形式进行稍微改进：
知道两个点，那么必然会知道某一个方向的步进次数（如果你乐意，甚至可以随便选取一个方向，我们这里选\(x\)方向），那么另一个方向（\(y\)方向）的步长\(\delta\)就知道了，虽然说确定步长会涉及到浮点除法运算，但是毕竟只用计算一次，还是可以接受的。然后根据步进次数，\(y=y'+\delta\)，\(y'\)是上一个点的值（注意，虽然绘制到屏幕前要取整，但这里保存上一次值时保留取整前的。
calc y step value dy
y = y start
loop x num:
y += dy
draw(x, y)
可以很明显的察觉这个方法相比之前的暴力计算，计算量少了许多：整体来看，此方法用到一次浮点数除法，N次浮点数加法，相比N次浮点数乘法（暂且认为乘除是一样的，实际这种认为有失偏颇，毕竟大多时候能不用除法就不用）运算量降低了许多。
第三种方法便是DDA算法的前身。
但是DDA算法给出了更为明确的流程。
设当前点：\((x_i, y_i)\)
根据两个端点便可计算出\(\delta x\)和\(\delta y\)
则下一点：
\(x_{i+1} = x_i + \delta x\)
\(y_{i+1} = y_i + \delta y\)
根据前面提到的，需要一个方向的\(\Delta\)值为1，即每次步进一个像素
那么如何确定这个步进方向？
DDA算法给出明确的方法。
分别计算\(x\)和\(y\)方向上的差值\(\Delta x\)和\(\Delta y\)
- 如果\(\Delta x > \Delta y\)，说明\(x\)轴变化的大，所以把\(x\)方向作为主步进方向，即：\(\delta x = 1, \delta y = \frac{\Delta y}{\Delta x} = k\)
- 如果\(\Delta y > \Delta x\)，说明\(y\)轴变化的大，所以把\(y\)方向作为主步进方向，即：\(\delta y = 1, \delta x = \frac{\Delta x}{\Delta y} = \frac{1}{k}\)
仍然通过迭代的方式，即可求出每一个点。
可以看到，DDA算法去掉了浮点数乘法运算，仍需要多次浮点数加法运算和浮点数取整。因此还是有优化空间的。
二、Bresenham
Bresenham算法是一种基于误差判别式来生成直线的方法。
同样采用步进的思想，令每次最大变化方向的坐标步进一个像素单位（与DDA算法相同），另一个方向根据误差判别式的符号决定是否也要步进一个像素单位（与DDA算法不同）。
从Bresenham算法的思想描述中可以看出，本质上和DDA没有太大区别，只不过是另一个方向的步进值的确定产生了变化。
为什么在另一个方向上每次最大只步进一个像素？
这一点很好解释：
因为DDA算法和Bresenham算法都选取最大变化方向为主步进方向，这也就意味着，另一个方向的步进值无论是\(\delta y = \frac{\Delta y}{\Delta x}\)还是\(\delta x = \frac{\Delta x}{\Delta y}\)都必然小于等于1 。
另外，Bresenhan算法误差判别过程如下图所示。
那么，Bresenham算法和DDA算法区别在哪？就一个步进值么？
不是的，Bresenham算法和DDA算法的区别在于最后的光栅化过程（就是望屏幕上绘制的时候）。至于这个步进值的差异，不是很关键。
- DDA算法光栅化时，使用了一个浮点数转化宏：
#define FloatToInteger(fn) ((fn>0)?(fn+0.5):(fn-0.5)) - 而Bresenham算法光栅化时，使用的误差判别式
可以看到DDA始终于偏向选择无脑“步进”
如果Bresenham算法就到这，那也太low了：不仅没有去掉DDA算法中的浮点数加法运算，仅仅是为了让步进更丝滑而引入误差判别式，结果又引入了新的浮点数运算，图啥？
对此，改进版的Brehensam算法应运而生。
实际上，我没有去考证Bresenham在1965年发表Brehensam算法的论文，所以也不清楚那篇论文中就是改进后的。完了，不严谨了。
图片来自https://www.cnblogs.com/LiveForGame/p/11706904.html
\(d_1 = y - y_i = k(x_i + 1) + b - y_i\)
\(d_2 = y_{i+1} - y = (y_i + 1) - [k(x_i + 1) + b]\)
两式相减，得：\(d_1 - d_2 = 2k(x_i + 1) - 2y_i + 2b - 1\)
因为：\(k = \frac{\Delta y}{\Delta x}\)
所以：\(\Delta x (d_1 - d_2) = 2 \Delta y x_i + 2 \Delta y - 2y_i \Delta x + 2b \Delta x - \Delta x\)
又因为：\(\Delta y、\Delta x、b\)对于一条指向来说，是常量
所以：\(\Delta x (d_1 - d_2) = 2 \Delta y x_i - 2 \Delta x y_i + c\)
令：\(\Delta x (d_1 - d_2) = e_i\)，\(e_i\)称为误差测量参数
若\(e_i > 0\)，即：\(d_1 - d_2 > 0\)，则实际点更靠近右上方的点（应选用右上方的点）
若\(e_i < 0\)，即：\(d_1 - d_2 < 0\)，则实际点更靠近右侧的点（应选用右侧的点）
若\(e_i = 0\)，即：\(d_1 - d_2 = 0\)，则随缘。实际不容易遇到，毕竟\(d_1、d_2\)都是浮点数，相等太难了（这一点参考浮点数的编码方式就知道了）
现在通过判断\(e_i\)的符号就可以判断下一个点是否需要步进了。
那么，如何去掉判别时的浮点运算呢？即如何确定\(d_1\)和\(d_2\)的值？
不忙，继续推导。
当前点的误差测量参数：\(e_i = 2 \Delta y x_i - 2 \Delta x y_i + c\)
下一点的误差测量参数：\(e_{i+1} = 2 \Delta y x_{i+1} - 2 \Delta x y_{i+1} + c\)
两式相减，得：\(e_{i+1} - e_i = 2 \Delta y x_{i+1} - 2 \Delta x y_{i+1} - [2 \Delta y x_i - 2 \Delta x y_i]\)
整理，得：\(e_{i+1} - e_i = 2 \Delta y (x_{i+1} - x_i) - 2 \Delta x (y_{i+1} - y_i)\)
又因为：\(x_{i+1} - x_i = 1\)
所以：\(e_{i+1} - e_i = 2 \Delta y - 2 \Delta x (y_{i+1} - y_i)\)
所以：
当选择右侧的点时：\(e_{i+1} = e_i + 2 \Delta y\)
选择右上角的点时：\(e_{i+1} = e_i + 2 \Delta y - 2 \Delta x\)
可以发现，并不需要确定\(d_1\)和\(d_2\)的值。
根据\(e_i\)的符号可以递推出下一点的误差判别参数\(e_{i+1}\)，反过来根据这个新得到的误差判别参数，可以继续确定下下一点的误差判别参数...
递归，完美。
但是，初始的\(e_0\)怎么确定？
对于初始点：
因为：\(\Delta x (d_1 - d_2) = e_i\)，所以\(\frac{e_0}{\Delta x} = d_1 - d_2\)
又因为：\(d_1 - d_2 = 2k(x_0 + 1) - 2y_0 + 2b - 1 = 2kx_0 + 2k - 2y_0 + 2b - 1\)
又因为：\(y_0 = kx_0 + b\)
所以：\(d_1 - d_2 = 2(kx_0 + b) + 2k - 2y_0 - 1 = 2\frac{\Delta y}{\Delta x} - 1 = \frac{e_0}{\Delta x}\)
所以：\(e_0 = 2 \Delta y - \Delta x\)
好了，初始点有了，递推公式也有了，剩下的就是写程序了。
至此，改进版的Brehenham算法全部推导完成。
后面会附上Brehensam算法绘制直线的C语言程序，可能和这里的推导过程由出入，但算法的核心是一样的。
三、绘制图形
1. 绘制直线
对于水平直线和垂直直线，大可不必通过算法去求解，毕竟这两类直线只在一个方向有步进，而另一个方向步进值始终为0。因此，对于这两种情况，可以单独讨论。
/**
* @brief :画线(像素坐标，左上为基点，右下增)
* @note :--
* @param :xStart, 行起始坐标(0~127)
yStart, 列起始坐标(0~63)
xEnd , 行终止坐标(0~127)
yEnd , 列终止坐标(0~63)
* @return :void
*
* @date :2016/09/09
* @design :
**/
void OLED_DrawLine(uint32_t xStart, uint32_t yStart, uint32_t xEnd, uint32_t yEnd)
{
int8_t x_width; //x轴宽度
int8_t y_height;//y轴高度
int8_t x_inc; //x方向自增标记
int8_t y_inc; //y方向自增标记
int8_t rem; //current remainder
uint8_t start, end;
uint8_t i;
if(yStart == yEnd)//绘制水平线，horizon line
{
if(xStart > xEnd)
{
start = xEnd;
end = xStart;
}else{
start = xStart;
end = xEnd;
}
for(i=start; i<=end; i++){
OLED_DrawPixelPoint(i, yStart, 1);
}
}else if(xStart == xEnd){//绘制垂直线，vertical line
if(yStart > yEnd)
{
start = yEnd;
end = yStart;
}else{
start = yStart;
end = yEnd;
}
for(i=start; i<=end; i++){
OLED_DrawPixelPoint(xStart, i, 1);
}
}else{//绘制任意直线
x_width = xEnd - xStart;
y_height = yEnd - yStart;
if(x_width < 0) x_width = 0 - x_width;
if(y_height < 0) y_height = 0 - y_height;
x_inc = (xEnd > xStart) ? 1 : -1;
y_inc = (yEnd > yStart) ? 1 : -1;
if(x_width >= y_height)
{
rem = x_width/2;
for(; xStart!=xEnd; xStart+=x_inc)
{
OLED_DrawPixelPoint(xStart, yStart, 1);
rem += y_height;
if(rem >= x_width)
{
rem -= x_width;
yStart += y_inc;
}
}
}else{
rem = y_height/2;
for(; yStart!=yEnd; yStart+=y_inc)
{
OLED_DrawPixelPoint(xStart, yStart, 1);
rem += x_width;
if(rem >= y_height)
{
rem -= y_height;
xStart += x_inc;
}
}
}
}
}
2. 绘制圆
没有什么特别的，主要注意利用圆的八分对称性，可以减少数学运算的次数。
同时使用改进版本，避免了浮点运算。
/**
* @brief :八分对称法(像素坐标)
* @note :--画出给定点的八分对称点(画圆基础算法)
* @param :xc, 圆心行坐标
yc, 圆心列坐标
x , 给定点
y , 给定点
* @return :void
*
* @date :2017/01/02
* @design :
**/
static void Circle8Point(uint32_t xc, uint32_t yc, uint32_t x, uint32_t y)
{
//直角坐标系第一象限x轴开始，逆时针旋转！
OLED_DrawPixelPoint((xc+x), (yc+y), 1);//1
OLED_DrawPixelPoint((xc+y), (yc+x), 1);//2
OLED_DrawPixelPoint((xc-y), (yc+x), 1);//3
OLED_DrawPixelPoint((xc-x), (yc+y), 1);//4
OLED_DrawPixelPoint((xc-x), (yc-y), 1);//5
OLED_DrawPixelPoint((xc-y), (yc-x), 1);//6
OLED_DrawPixelPoint((xc+y), (yc-x), 1);//7
OLED_DrawPixelPoint((xc+x), (yc-y), 1);//8
}
/**
* @brief :改进画圆(像素坐标)
* @note :--避免浮点运算(轴上点不突进！)！
* @param :xc, 圆心行坐标
yc, 圆心列坐标
r , 半径
* @return :void
*
* @date :2017/01/02
* @design :
**/
void OLED_DrawCircle(uint32_t xc, uint32_t yc, uint32_t r)
{
uint32_t x, y;
int32_t d;//改进，避免浮点运算！
x = 0;
y = r;
d = 3-2*r;
Circle8Point(xc ,yc, x, y);
while(x < y)
{
if(d < 0)
{
d += 4*x+6;
}else{
d += 4*(x-y)+10;
--y;
}
++x;
Circle8Point(xc, yc, x, y);
}
}
3. 绘制椭圆
和圆绘制过程类似，同样利用了椭圆的对称性。
/**
* @brief :四分对称法(像素坐标)
* @note :--画出给定点的四分对称点(画椭圆基础算法)
* @param :xc, 椭圆中心行坐标
yc, 椭圆中心列坐标
x , 给定点
y , 给定点
* @return :void
*
* @date :2017/01/04
* @design :
**/
static void Ellipse4Point(uint32_t xc, uint32_t yc, uint32_t x, uint32_t y)
{
//直角坐标系第一象限开始，逆时针旋转！
OLED_DrawPixelPoint((xc+x), (yc+y), 1);//1
OLED_DrawPixelPoint((xc-x), (yc+y), 1);//2
OLED_DrawPixelPoint((xc-x), (yc-y), 1);//3
OLED_DrawPixelPoint((xc+x), (yc-y), 1);//4
}
/**
* @brief :画椭圆(像素坐标)
* @note :--
* @param :xc, 椭圆中心行坐标
yc, 椭圆中心列坐标
a , 半长轴长度
b , 半短轴长度
* @return :void
*
* @date :2017/01/04
* @design :
**/
void OLED_DrawEllipse(uint32_t xc, uint32_t yc, uint32_t a, uint32_t b)
{
int32_t x=0;
int32_t y=b;
int32_t b2=(int32_t)b;
float sqa=a*a;
float sqb=b*b;
float d=sqb+sqa*(-b2+0.25f);
Ellipse4Point(xc, yc, x, y);
while((sqb*(x+1)) < (sqa*(y-0.5f)))
{
if(d < 0)
{
d += sqb*(2*x+3);
}else{
d += sqb*(2*x+3)+sqa*(-2*y+2);
--y;
}
++x;
Ellipse4Point(xc, yc, x, y);
}
d = (b*(x+0.5))*2 + (a*(y-1))*2 - (a*b)*2;
while(y > 0)
{
if(d < 0)
{
d += sqb*(2*x+2)+sqa*(-2*y+3);
++x;
}else{
d += sqa*(-2*y+3);
}
--y;
Ellipse4Point(xc, yc, x, y);
}
}