【计算机图形学】图元的扫描转换之直线的扫描转换

相关资料来源于网络，侵删歉。

---

直线的扫描转换

定义：直线的扫描转换是指在二维栅格上计算位于该直线上或充分靠近它的一串像素坐标(光栅化)，并以此像素集近似替代原连续直线段在屏幕上显示的过程。直线由两个端点坐标确定。

要求
1.观感好,像素分布均匀    
2.误差小,像素尽可能接近数学理想坐标 
3.速度快，避免乘除法和浮点数运算

前提
线的宽度是一个像素
线的端点是整数坐标
直线斜率|k|<=1

原理
按直线从起点到终点的顺序计算直线与各垂直光栅网格线的交点，然后确定每列像素中与此交点最近的像素。

---

基本增量算法（DDA）

已知过端点，的直线段L：。从直线左端点开始，x每次递增1个单位，对计算。显示坐标为的像素。这种方法直观，但效率太低，因为每一步需要用浮点计算一次乘法、一次加法和一次取整运算。我们对此稍微改进，去掉其中的乘法。由于，所以每次x递增一个单位，y就加上一个k。（如果线的斜率在1和-1之间（包括1和-1），则每一列上必定只有一个像素被显示；若线的斜率在此范围之外，则每一行上必定只有一个像素被显示。如果|k|>1，我们将x和y的角色互换，即y每次增加一个单位，x变化的增量为1/m。）

实现（这里只给出基础算法，具体的请详见DDA算法[待编写]）

/*
	基本增量算法
	适用于直线斜率k在[-1,1]的情况。
*/
void Line(int x0,int y0,int x1,int y1,int color){
	int x;
	double dy=y1-y0;
	double dx=x1-x0;
	double k=dy/dx;
	double y=y0;
	for(x=x0;x<=x1;x++){
		WritePixel(x,floor(y+0.5),color);
		y+=m;
	}
}

上述程序的缺点是：对y值取整需要发费时间，且y和k是浮点数，存在浮点运算。

---

中点线算法

假定直线斜率0<k<1，且已确定点亮像素点,则下一个与直线最接近的像素可能是其右边的第一个像素E(称为东像素)，也可能是其右上方的第一个像素NE(称为东北像素) 。假设Q是直线与栅格线的交点，M为E和NE的中点。

当M在Q的上方时，Q离E更近，取E；
当M在Q的下方时，Q离NE更近，取NE；
当M与Q重合时，NE或E任取。（如果总是重合，应该总是取NE或E中的其一）

下面需要判断Q与M的关系：
设直线方程为F(x,y)=ax+by+c=0，
当F(x0,y0)>0，(x0, y0)在直线的上方
当F(x0,y0)<0，(x0, y0)在直线的下方
当F(x0,y0)=0，(x0, y0)在直线上

那么由已知点P推出M点带入直线方程根据符号即可判断，F(xM,yM)=F(xP+1,yP+0.5)。
但效率不高，因为存在浮点数乘法运算。下面我们由增量算法对此改进。