计算机图形学（一）绘制直线(C++)

1. 数值微分法DDA（Digital Differential Analyzer）

基本思想：先对一个方向的坐标取单位步长的变化,然后计算另一方向坐标相应的变化值。
当一条直线的斜率不为0时，它可以用方程y=kx+b来表示，假定直线的起点和终点分别为（x1,y1),(x2,y2)，且都为整数，那么k = （y2-y1)/(x2-x1);

由k的大小确定取单位步长的方向：
① |k|<1，取增长单位步长方向为x轴（Δx=1），y的增量大小为
$y_{i+1}=k(x_i+1)+b= y_i+k$yi+1​=k(xi​+1)+b=yi​+k
②|k|>1,则取增长单位步长方向为y轴（Δy=1），可得如下x的增量方程：
$x_{i+1}=x_i+\frac1k$xi+1​=xi​+k1​
③若开始的端点在终点右方，则有
Δx = -1时 $y_{i+1}=k(x_i-1)+b= y_i-k$yi+1​=k(xi​−1)+b=yi​−k
Δy = -1时 $x_{i+1}=x_i-\frac1k$xi+1​=xi​−k1​

实例：绘制从A（11，7）到B（3，2）的直线
k =(y2-y1)/(x2-x1)=0.625,增量方向为x轴，且起点在终点右侧，Δx=-1，y的改变量Δy=-0.625

$i$i	$x_i$xi​	$y_i$yi​	坐标(四舍五入)
0	$x_0 = 11$x0​=11	$y_0 = 7$y0​=7	(11,7)
1	$x_1 = 10$x1​=10	$y_1 = 6.375$y1​=6.375	(10,6)
2	$x_2 = 9$x2​=9	$y_2 = 5.75$y2​=5.75	(9,6)
3	$x_3 = 8$x3​=8	$y_3 = 5.125$y3​=5.125	(8,5)
4	$x_4 = 7$x4​=7	$y_4 = 4.5$y4​=4.5	(7,5)
……	……	……	……

在C++，MFC中实现代码如下

void Draw(CDC *pCD，int x1,int y1,int x2,int y2,COLORREF color)
{
	//该程序考虑到了k范围不同，以及k不存在时的情况
	int dx,dy,n,k;
	double xinc,yinc,x,y;
	dx = x2-x1;
	dy = y2-y1;
	if(abs(dx)-abs(dy)>0) //比较两参数的绝对值哪一个大，哪一个就作为步长参数（n），
							此参数将作为沿直线所画出点的数目
		n = abs(dx);
	else
		n = abs(dy);
	xinc = (double)dx/n;
	yinc = (double)dy/n;
	x = x1;
	y = y1;
	for(k = 0;k<n;k++)
	{
		pCD->SetPixel(floor(x + 0.5),floor(y + 0.5),color);
		x+=xinc;
		y+=yinc;
	}
}

2. 中点画线法

基本思想：假设直线的起点和终点分别为（x1，y1）和（x2，y2），则方程为：$ax+by+c=0$ax+by+c=0其中a=y1-y2, b=x2-x1, c=x1y2-x2y1
且

构造判别式：中点M(xi+1,yi+0.5)，如下图所示
d=F(M)=F(xi+1,yi+0.5) =a(xi+1)+b(yi+0.5)+c
当d<0，M在直线(Q点)下方，取右上方P1；
当d>0，M在直线(Q点)上方，取右方P2；
当d=0，选P1或P2均可，约定取P2；

①若d>0,即M在直线上方，取P2。再下一个象素的判别式为
d1=F(xi+2, yi+0.5）= a(xi +1)+b(yi +0.5)+c +a =d+a； 增量为a。
②若d<0,即M在直线下方，取P1.再下一个象素的判别式为
d2= F(xi+2, yi+1.5)= a(xi +1)+b(yi +0.5)+c +a +b =d+a+b ； 增量为a＋b
③d的初始值（第一个象素应取左端点(x1,y1)）
d0= F(x0+1, y0+0.5)= F(x0, y0) +a +0.5b= a +0.5b

注：由于0.5b很有可能出现小数，不易于计算，此处我们都去增量大两倍，d1 = 2a;d2 = 2(a+b);d0=2a+b.

实例：绘制从A（11，7）到B（3，2）的直线

取B为起点，A为终点，计算相关参量：
a = y1 –y2 = 2 - 7 = -5；
b = x2-x1 = 11 – 3 = 8；
d0 = 2a+b = -2
d1 = 2a = -10
d2 = 2*(a+b) = 6

$i$i	$x_i$xi​	$y_i$yi​	$d_i$di​	坐标
0	3	2	-2	(3,2)
1	4	3	4	(4,3)
2	5	3	-6	(5,3)
3	6	4	0	(6,4)
4	7	4	-10	(7,4)
……	……	……	……	……

在C++，MFC中实现代码如下

void DrawM(CDC *pCD,int x1,int y1,int x2,int y2,COLORREF color)
{          
	int a,b,d1,d2,d,x,y;
	int minX = min(x1,x2);
	int maxX = max(x1,x2);
	int minY = min(y1,y2);
	int maxY = max(y1,y2);	
	x = minX;
	y = minY;
	a = y1-y2;
	b = x2-x1;
	pCD->SetPixel(x,y,color);
	if(b==0)	//斜率不存在
	{
		for(int i =minY;i<=maxY;i++)
			pCD->SetPixel(x,i,color);
		return;
	}
	double m =double(y1-y2)/(x1-x2);
	if(a==0)      //斜率为0
		for(int i =minX;i<=maxX;i++)
			pCD->SetPixel(i,y,color);
	else if(m>=1)    //斜率大于1，取y轴为增长单位长度方向
	{
		d=a+2*b;d1=2*(a+b),d2=2*b;
		while (y<maxY)  
		{  
			if (d>0) 
			{   
				x++;
				y++;
				d+=d1;
			}  
			else 
			{  
				y++;
				d+=d2;
			}  
			pCD->SetPixel(x,y,color);
		 }	
	}
	else if(m>0&&m<1)//斜率大于0小于1，取x轴为增长单位长度方向
	{
		d=a+a+b;
		d1=a+a;
		d2=a+b+a+b;
		while(x<maxX)
		{
			if(d<0)
			{
				x++;
				y++;
				d+=d2;
			}
			else
			{
				x++;
				d += d1;
			}
			pCD->SetPixel(x,y,color);
		}	
	}
	else if(m<0&&m>-1)//斜率大于-1小于0，取x轴为增长单位长度方向
	{
		d=2*a-b;d1=2*a-2*b,d2=2*a;
		while(x<maxX)
		{
			if(d<0){
				x++;
				y--;
				d+=d2;
			}
			else{
				x++;
				d += d1;
			}
			pCD->SetPixel(x,y,color);
		}	
	}
	else if(m<=-1)//斜率小于-1，取y轴为增长单位长度方向
	{
		d=a-2*b;
		d1=-2*b,
		d2=2*(a-b);
		while(y>minY)
		{
			if(d<=0)
			{
				x++;
				y--;
				d+=d2;
			}
			else{
				y--;
				d+=d1;
			}
			pCD->SetPixel(x,y,color);
		}
	}
}

3. Bresenham画线算法

基本思想：过各行、各列像素中心构造一组虚拟网格线，按直线从起点到终点的顺序计算直线与各垂直网格线的交点，然后确定该列像素中与此交点最近的像素.
如图所示，先假设直线的斜率在0～1之间。设Pi-1是已选定的离直线最近的象素，现在要决定下一个象素是Ti还是Si:
若s<t，则Si比较靠近直线，应选Si；
若s>＝t，则应选Ti。
在此不再详细阐述，有兴趣请自行查阅资料。