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

迷南。 2023-02-17 08:49 20阅读 0赞

# 实验二：直线的生成算法 #

## 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法）：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5nemlsaGM_size_16_color_FFFFFF_t_70]（2）中点画线算法：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5nemlsaGM_size_16_color_FFFFFF_t_70 1]（3）Bresenham算法：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5nemlsaGM_size_16_color_FFFFFF_t_70 2]

## 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实验结果展示 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5nemlsaGM_size_16_color_FFFFFF_t_70 3]红色：数值微分法（DDA法）  
绿色：中点画线算法  
蓝色：Bresenham算法

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5nemlsaGM_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200613102001379.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5nemlsaGM=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5nemlsaGM_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200613102022690.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5nemlsaGM=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5nemlsaGM_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200613102041902.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5nemlsaGM=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5nemlsaGM_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200613102316128.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5nemlsaGM=,size_16,color_FFFFFF,t_70