绘制算法
直线绘制
这些算法都是迭代形的，我没有在GPU上见到过实现。
DDA 数值微分法
计算直线的斜率，排除斜率为零和不存在的直线额外处理，其他的|k|大于1的时候，使用y作为迭代，每次y+1，x+k，迭代得到每一个点的位置。
当$|k| >=1$则递推公式如下：
$$
y_{i+1} = y_{i} + 1;
x_{i+1} = x{i} + k;
$$
实则通项公式如下：
$$
y_{i} = y_{0} + i
x_{i} = x_{0} + i k
$$
当$|k| <1$则交换x和y。这里不赘述。
这里所讲述的是斜率大于零的算法，小于零需要修改为减少索引。
中点画线法
为了解决数值微分法中乘法的性能开销，中点画线法以迭代的思想，将delta放大，实现了没有乘除法的直线绘制算法。
对于点$(x_0, y_0)$ 到$(x_1,y_1)$，如果$|k|<1$我们首先计算x方向上的偏移一单位的中点的值，如果该值大于函数值，那么说明我们需要移动x，否则我们需要移动x和y。
另函数方程为：$f(x,y)=ax+by+c$，那么$d = f(x+1,y+0.5)$。
$$
d_i = a(x+1)+b(y+0.5)+c
$$
当$d_i >= 0$说明应该移动x，那么下一个点为$(x+1,y)$。下一个中点差为$f(x+2,y+0.5)$
$$
d_{i+1} = d_i + a
$$
当$d_i < 0$说明应该同时移动x和y，那么下一个点为$(x+1, y+1)$，下一个中点差为$f(x+2, y+1.5)$
$$
d_{i+1} = d_i + a + b
$$
Bresenham
Bresenham算法的思想试比较直线上下两个点到直线的距离。另直线为（先不考虑斜率不存在的情况）：
$$
f(x) = kx + b
$$
离散后的点列定义为：
$$
(x_i, y_i)
$$
请注意，$f(x_i) != y_i$。
那么对下距离$d_1$和上距离$d_2$的定义分别为：
$$
d_1 = f(x) - y_{i-1}
$$
$$
d_2 = y_{i-1} + 1 - f(x)
$$
我们只需要判断两个距离的差值，即可判断$x_i, y_i$的选择了。
定义差量距离$d$：
$$
d = d1 - d2
$$
$$
= f(x) - y_{i-1} - y_{i-1} - 1 + f(x)
$$
$$
= 2f(x) - 2y_{i-1} - 1
$$
$$
= 2(k(x_{i-1}+1) + b) - 2y_{i-1} - 1
$$
当$d>0$时，说明我们应该选择上面的点，也就是说：
$$
y_i = y_{i-1} + 1
$$
当$d<=0$时，我们应该选择下面的点，也就是说：
$$
y_i = y_{i-1}
$$
所以我们需要判断$d$的情况，首先我们计算$k$和$b$的值，其中$(x_e, y_e)$为终点位置$(x_s, y_s)$为起点位置：
$$
k = \frac{dy}{dx}
$$
带入，计算$d$得到：
$$
d = 2(\frac{dy}{dx}(x_{i-1}+1) + b) - 2y_{i-1} - 1
$$
当$dx>0$的时候，两边乘以$dx$对结果$d$的正负无关，另$p = dx$
$$
p_i = 2(x_{i-1}dy + dy + bdx) - 2y_{i-1}dx - dx
$$
当$i=1$时，我们计算的迭代起点，此时：
$$
p_1 = 2d_y(x_sdy + dy + bdx) + 2y_sdx - dx
$$
其中$b = y_s - \frac{y_e-y_s}{x_e-x_s}x_s$带入得到：
$$
= 2dy -dx
$$
然后我们计算$p_{i+1} - p_{i}$
$$
\Delta{p} = p_{i+1} - p_i
$$
这里需要保留b的形式。
$$
p_i = 2(x_{i-1}dy + dy + bdx) - 2y_{i-1}dx - dx
$$
进一步得到：
$$
\Delta{p} = 2(x_{i} - x_{i-1})dy - 2(y_{i} - y_{i-1})dx
$$
进一步，当$p_i>0$时，$(x_{i} = x_{i-1}+1, y_{i} = y_{i-1}+1)$：
$$
p_{i+1} = p_{i} + 2dy-2dx
$$
当$p_i<=0$时，$(x_{i+1} = x_i +1, y_{i+1} = y_i)$
$$
p_{i+1} = p_{i} + 2dy
$$