计算机图形学——直线光栅化
在数学上，理想的直线是没有宽度的、由无数个点构成的集合。当我们对直线进行光栅化时，只能在显示器所给定的有限个像素组成的矩阵中，确定最佳逼近该直线的一组像素，并且按扫描线顺序对这些像素进行写操作，这就是通常所说的直线的扫描转换。
问题定义：
输入：起点（X0，Y0），终点（Xn，Yn）
输出：最靠近直线的像素点的集合
![在这里插入图片描述]()
直线光栅化的要求：粗细一致，亮度均匀；连续不间断；高效。
方法一：数值微分法
根据直线的微分方程来画直线。
设直线的起点坐标是Ps（Xs，Ys），终点坐标为Pe（Xe，Ye），令Δx=Xe-Xs，Δy=Ye-Ys。
则要绘制的直线微分方程为：
对上面式子中用的微商用差商来代替，即得：
令Δm=max(|Δx|,|Δy|)，则对每一步，可得上述微分方程数值解的递推公式为:
在绘制之前需要确定x方向和y方向哪个是计长方向。对于任意直线，按照直线的斜率k=Δx/Δy可分两种情况来分析：
|k|>1，y方向为计长方向，这时Δm=|Δy|，增加或减少的步长Δy/Δm始终为1个单位。x方向的变化步长为Δx/Δm。
|k|<=1时，x 方向为计长方向。这时Δm=|Δx|,x方向的变化量Δx/Δm为1个单位，y方向的变化步长则为Δy/Δm。
通常情况下，直线的方向分为8个不同的区域，每个区域的处理方法有所不同：
方法二：中点画线法
为讨论方便，假设直线的斜率在0-1之间，若直线在x方向上增加一个光栅单位，则在y方向上的增量只能在0-1之间。
设P（x，y）是直线上的一点，与P点最近的网格点为（Xp，Yp），那么下一个与直线最近的像素只能是右方网格点Pb（Xi+1，yi）和Pt（Xi+1，Yi+1）两者之一。再以点M（Xi+1，Yi+0.5）表示Pb和Pt的中点，设Q是直线与垂直线X=Xi+1的交点。若Q在M上方，则Pt离直线较近，否则Pb做为下一个像素点。
设直线起点终点分别为（X0，Y0）、（X1，Y1），直线方程为：F（x，y）=ax+by+c=0
其中a=Y0-Y1，b=X1-X0，c=X0Y1-X1Y0
构造判别式：采用增量计算
d=F(M）=F（x+1，y+0.5）=a（x+1）+b（y+0.5）+c
在d>=0的情况下，取正右方像素Pb，
判断下一像素应计算
d1=a（x+2)+b(y+0.5)+c=d+a
在d<0的情况下，取右上方像素Pt
在判断下一像素应计算
d2=a(x+2)+b(y+1.5)=d+a+b
d的初始值d0=a+0.5b