小白谈计算机图形学（一）如何画线
大家好，众所周知，计算机的图像显示是由一个一个像素组成，正如分子组成了世界，当像素合理分布，同样可以还原很多真实世界的场景。
如何画线 基本思想已知过端点p0(x0,y0)p_0(x_0,y_0)p0(x0,y0)和p1(x1,y1)p_1(x_1,y_1)p1(x1,y1)的直线:
y=kx+by=kx+by=kx+b
直观的做法是把每个xxx的值代入直线方程求出相应的yyy值。取像素点(x,int(y))(x, int(y))(x,int(y))作为当前点坐标。光栅直线算法属于图形学最底层的算法，因此要精益求精。
增量算法变乘法为加法，这里利用斜截式，首先yi+1=yi+kΔxy_{i+1}= y_i+ k\Delta xyi+1=yi+kΔx，当Δx=1\Delta x=1Δx=1时:
yi+1=yi+ky_{i+1}= y_i+ kyi+1=yi+k
同时该算法只能画∣k∣≤1|k| \leq1∣k∣≤1,超过则会出现离散的点，失真。可以采用：{yi+1=yi+k(︱k︱＜1，Δx=1）xi+1=xi+1k(︱k︱＞1，Δy=1） \left\{ \begin{aligned} y_{i+1} = y_i+k( ︱k︱＜1，\Delta x =1）\\ \\ x_{i+1} = x_i+\frac{1}{k}( ︱k︱＞1，\Delta y =1） \end{aligned} \right. ⎩⎪⎪⎪⎨⎪⎪⎪⎧yi+1=yi+k(︱k︱＜1，Δx=1）xi+1=xi+k1(︱k︱＞1，Δy=1） 优点：简单直观，迭代的算法
缺点：浮点运算，每步都需四舍五入取整。 中点画线法 中点画线引言
利用后一中点与前一中点的函数关系，采用了直线的一般式方程：
F(x,y)=y−y1−y0x1−x0x−bF(x,y)=y-\frac{y_1-y_0}{x_1-x_0}x-b F(x,y)=y−x1−x0y1−y0x−b
认为Δx>0\Delta x>0Δx>0,即：
F(x,y)=(Δx)y−(Δy)x−(Δx)bF(x,y)=(\Delta x)y-(\Delta y)x-(\Delta x)bF(x,y)=(Δx)y−(Δy)x−(Δx)b
直线方程将平面分为三个区域：
{F(x,y)=0(直线上的点)F(x,y)>0(直线上方的点)F(x,y)<0(直线下方的点) \left\{
\begin{aligned}
F(x, y) = 0(直线上的点)\\
F(x, y) > 0(直线上方的点)
\\
F(x, y) < 0(直线下方的点)
\end{aligned}
\right.
⎩⎪⎨⎪⎧F(x,y)=0(直线上的点)F(x,y)>0(直线上方的点)F(x,y)<0(直线下方的点)
当MMM在QQQ的下方，则说明PuP_uPu离直线近，应为下一个像素点；当MMM在QQQ的上方，应取PdP_dPd 为下一点。但是…每一个像素的计算量是4个加法，两个乘法。比DDA算法的计算量大多了，毫无可取之处！
根据上一次计算的ddd值判断接下来ddd值的变化
若d<0d<0d<0时，则取右上方像素pu(xi+1,yi+1)p_u(x_i+1, y_i+1)pu(xi+1,yi+1)。判断再下一像素，则要计算：
dnew=F(xi+2,yi+1.5)=a(xi+1)+b(yi+0.5)+c+a=F(xi+1,yi+0.5)+a+b=dold+a+b \begin{aligned} d_{new}&=F(x_i+2,y_i+1.5)\\ &=a(x_i+1)+b(y_i+0.5)+c+a\\ &=F(x_i+1,y_i+0.5)+a+b\\ &=d_{old}+a+b \end{aligned} dnew=F(xi+2,yi+1.5)=a(xi+1)+b(yi+0.5)+c+a=F(xi+1,yi+0.5)+a+b=dold+a+b 若d≥0d \geq 0d≥0情况，则取正右方像素(xi+1,yi)(x_i+1, y_i)(xi+1,yi), 判断下一个像素位置要计算：
dnew=F(xi+2,yi+0.5)=a(xi+1)+b(yi+0.5)+c+a=F(xi+1,yi+0.5)+a=dold+a \begin{aligned} d_{new}&=F(x_i+2,y_i+0.5)\\ &=a(x_i+1)+b(y_i+0.5)+c+a\\ &=F(x_i+1,y_i+0.5)+a\\ &=d_{old}+a \end{aligned} dnew=F(xi+2,yi+0.5)=a(xi+1)+b(yi+0.5)+c+a=F(xi+1,yi+0.5)+a=dold+a 迭代需要初始值d0d_0d0
d0=F(x0+1,y0+0.5)=a(x0+1)+b(y0+0.5)+c=a+0.5b \begin{aligned} d_0&=F(x_0+1,y_0+0.5) \\&=a(x_0+1)+b(y_0+0.5)+c \\&=a+0.5b \end{aligned} d0=F(x0+1,y0+0.5)=a(x0+1)+b(y0+0.5)+c=a+0.5b 由于我们只用ddd的符号，所以使用2d2d2d摆脱小数运算，更新后的公式为：
{d0=2a+bdold=dnew+2a+2b(d<0)dold=dnew+2a(d≥0) \left\{ \begin{aligned} &d_0= 2a+b\\ &d_{old}=d_{new}+2a+2b(d<0) \\ &d_{old}=d_{new}+2a(d \geq 0) \end{aligned} \right. ⎩⎪⎨⎪⎧d0=2a+bdold=dnew+2a+2b(d<0)dold=dnew+2a(d≥0) Bresenham画线法 Bresenham基本思路
采用增量计算，检查误差项的符号，就可以确定该列的所求像素。
直线的起始点在像素中心，所以误差项d的初值{d0＝0dnew=dold+kxi+1=xi+1(右移一格)yi+1={yi+1,d=d−1(d≥0.5)(上移一格)yi(d<0.5)(保持不动)\left\{ \begin{aligned} &d_0＝0\\ &d_{new}=d_{old}+k\\ &x_{i+1}= x_i+1(右移一格)\\ &y_{i+1}= \left\{ \begin{aligned} &y_i+1,d=d-1&(d\geq0.5)(上移一格)\\ \\ &y_{i}&(d < 0.5)(保持不动) \end{aligned} \right. \\ \end{aligned} \right. ⎩⎪⎪⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎧d0＝0dnew=dold+kxi+1=xi+1(右移一格)yi+1=⎩⎪⎨⎪⎧yi+1,d=d−1yi(d≥0.5)(上移一格)(d<0.5)(保持不动)
Bresenham画线改进
令e=d−0.5e=d-0.5e=d−0.5{e0=−0.5enew=eold+kxi+1=xi+1(右移一格)yi+1={yi+1,d=d−1(e≥0)(上移一格)yi(e<0)(保持不动)\left\{ \begin{aligned} &e_0=-0.5\\ &e_{new}=e_{old}+k\\ &x_{i+1}= x_i+1(右移一格)\\ &y_{i+1}= \left\{ \begin{aligned} &y_i+1,d=d-1&(e\geq0)(上移一格)\\ \\ &y_{i}&(e < 0)(保持不动) \end{aligned} \right. \\ \end{aligned} \right. ⎩⎪⎪⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎧e0=−0.5enew=eold+kxi+1=xi+1(右移一格)yi+1=⎩⎪⎨⎪⎧yi+1,d=d−1yi(e≥0)(上移一格)(e<0)(保持不动) e∗2e*2e∗2将e0e_0e0变为整数，由于p0(x0,y0),p1(x1,y1)p_0(x_0,y_0),p_1(x_1,y_1)p0(x0,y0),p1(x1,y1)皆为整数，故d∗Δxd* \Delta xd∗Δx即为斜率乘Δx\Delta xΔx即为Δy\Delta yΔy为整数，故第二步改进令：
e=e∗2∗Δxe=e*2*\Delta xe=e∗2∗Δx
判断eee的正负，更新后的公式为：
{e=−Δx(初始值)enew=eold+2Δy(初始值)xi+1=xi+1(右移一格)yi+1={yi+1,e=e−2Δx(e≥0)(上移一格)yi(e<0)(保持不动)\left\{ \begin{aligned} &e= -\Delta x(初始值)\\ &e_{new}= e_{old}+2\Delta y(初始值)\\ &x_{i+1}= x_{i}+1(右移一格)\\ &y_{i+1}= \left\{ \begin{aligned} &y_i+1,e=e-2\Delta x&(e\geq0)(上移一格)\\ \\ &y_{i}&(e < 0)(保持不动) \end{aligned} \right. \\ \end{aligned} \right. ⎩⎪⎪⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎧e=−Δx(初始值)enew=eold+2Δy(初始值)xi+1=xi+1(右移一格)yi+1=⎩⎪⎨⎪⎧yi+1,e=e−2Δxyi(e≥0)(上移一格)(e<0)(保持不动) 小结
想避免浮点运算，进行整数算法判断像素点位置，就必须判断符号，如中点画线法和Bresenhanm算法，判断大小不能搞成整数加法。
wuli放几张做好的图，大家康康c语言可以画图呀！
作者：liuyiming2019
