计算机图形学（二）——实验二：直线的生成算法

2.1实验目的

（1）理解基本图形元素光栅化的基本原理
（2）掌握一种基本图形元素光栅化算法
（3）了解DDA算法、中点画线法、Bresenham算法
（4）掌握VC++中CDC类的用法

2.2实验内容

（1）类的编写
（2）完成DDA算法、中点画线法、Bresenham算法

2.3算法思路

数值微分法（DDA法）：首先根据直线的斜率确定是以X方向步进还是以Y方向步进，然后沿着步进方向每步进一个点（象素），就沿另一个坐标变量k，k是直线的斜率，因为是对点阵设备输出的，所以需要对每次计算出来的一对坐标进行圆整。
Bresenham算法：将光栅设备的各行各列象素中心连接起来构造一组虚拟网格线。按直线从起点到终点的顺序计算直线与各垂直方向网格线的交点，然后确定该列象素中与此交点最近的象素。
中点画线算法：假定直线斜率k在0~1之间，当前象素点为（xp,yp），则下一个象素点有两种可选择点P1（xp+1,yp）或P2（xp+1,yp+1）。若P1与P2的中点（xp+1,yp+0.5）称为M，Q为理想直线与x=xp+1垂线的交点。当M在Q的下方时，则取P2应为下一个象素点；当M在Q的上方时，则取P1为下一个象素点。

2.4流程图

（1）数值微分法（DDA法）：
（2）中点画线算法：
（3）Bresenham算法：

2.5实验步骤

（1）数值微分法（DDA法）：
从起点开始朝终点方向画点(x, y)，在x轴或y轴上走一个单位长（沿x轴还是y轴取决于直线的倾斜角），由直线的倾斜程度（斜率或斜率的倒数）决定另一坐标的增量，获得下一点的坐标，将x或y四舍五入，得(x, y)，若(x, y)不是终点则继续。
（2）中点画线算法：
从起点开始朝终点方向画点(x, y)，当前象素点为（xp,yp），则下一个象素点有两种可选择点P1（xp+1,yp）或P2（xp+1,yp+1），若P1与P2的中点（xp+1,yp+0.5）称为M，Q为理想直线与x=xp+1垂线的交点。当M在Q的下方时，则取P2应为下一个象素点；当M在Q的上方时，则取P1为下一个象素点，得(x, y)，若(x, y)不是终点则继续。
（3）Bresenham算法：
从起点开始朝终点方向画点(x, y)。准备画下一个点，X坐标加1，判断如果达到终点，则完成，否则找下一个点。要画的点要么为当前点的右邻接点，要么是当前点的右上邻接点。如果线段ax+by+c=0与x=x1+1的交点y坐标大于(y+*y+1))/2则选右上那个点，否则选右下那个点，得(x, y)。

2.6实验代码

（1）数值微分法（DDA法）：

/
//DDA直线生成算法
/
void CLiHuchenView::OnDdaline() 
{
	// TODO: Add your command handler code here
	CDC *pDC=GetDC();//获取设备指针
	int xa=100,ya=300,xb=300,yb=200,c=RGB(255,0,0);//定义直线的两端点，直线颜色红色
	int x,y;//定义变量x，y
	float dx,dy,k;//定义增量dx，dy和斜率k
	dx=(float)(xb-xa),dy=(float)(yb-ya);//直线两端点之差为增量
	k=dy/dx;//直线斜率
	y=ya;//将第一个点纵坐标赋给y
	//k值判断
	if(abs(k)<1)
	{
		for(x=xa;x<=xb;x++)//从x左端向右端点步进
		{
			pDC->SetPixel(x,int(y+0.5),c);//添加光栅点
			y=y+k;//y增加k的单位
		}
	}
	if(abs(k)>=1)
	{
		for(y=ya;y<=yb;y++)
		{
			pDC->SetPixel(int(x+0.5),y,c);//添加光栅点
			x=x+1/k;//x增加1/k的单位
		}
	}
	ReleaseDC(pDC);//指针释放
}

（2）中点画线算法：

/
//中点直线生成算法
/
void CLiHuchenView::OnMidpointline() 
{
	// TODO: Add your command handler code here
	CDC *pDC=GetDC();//获取设备指针
	int xa=300,ya=200,xb=450,yb=300,c=RGB(0,255,0);//定义直线的两端点，直线颜色绿色
	float a,b,d1,d2,d,x,y;//定义直线方程系数a,b,中点带入直线的值d，增量d1，d2，变量x，y
	a=ya-yb;b=xb-xa;d=2*a+b;//计算a，b，d
	d1=2*a;d2=2*(a+b);计算增量d1，d2
	x=xa,y=ya;//赋初值
	pDC->SetPixel(x,y,c);添加光栅点
	while(x<xb)
	{
		//判断d
		if(d<0)
		{
			x++,y++,d+=d2;
		}
		else
		{
			x++,d+=d1;
		}
		pDC->SetPixel(x,y,c);添加光栅点
	}
	ReleaseDC(pDC);//指针释放
}

（3）Bresenham算法：

/
//Bresenham直线生成算法
/
void CLiHuchenView::OnBresenhamline() 
{
	// TODO: Add your command handler code here
	CDC *pDC=GetDC();//获取设备指针
	int x1=100,y1=200,x2=300,y2=100,c=RGB(0,0,255);//定义直线的两端点，直线颜色蓝色
	int i,s1,s2,interchange;//定义变量
	float x,y,deltax,deltay,f,temp;//定义变量x，y；增量dx，dy
	x=x1;y=y1;//赋初值
	deltax=abs(x2-x1);deltay=abs(y2-y1);//直线两端点之差为增量
	if(x2-x1>=0){ s1=1;}else {s1=-1;}//判断s1正负前进
	if(y2-y1>=0) {s2=1;}else {s2=-1;}//判断s2正负前进
	//判断dy和dx的大小
	if(deltay>deltax)
	{
		//交换dy和dx
		temp=deltax;
		deltax=deltay;
		deltay=temp;
		interchange=1;//设置交换
	}
	else {interchange=0;}
	f=2*deltay-deltax;//计算误差初值
	pDC->SetPixel(x,y,c);添加光栅点
	for(i=1;i<=deltax;i++)
	{
		if(f>=0)
		{
			if(interchange==1) x+=s1;
			else y+=s2;
			pDC->SetPixel(x,y,c);添加光栅点
			f=f-2*deltax;
		}
		else
		{
			if(interchange==1)  y+=s2;
			else x+=s1;
			f=f+2*deltay;
		}
	}
	ReleaseDC(pDC);//指针释放
}

2.7实验结果展示

红色：数值微分法（DDA法）
绿色：中点画线算法
蓝色：Bresenham算法