计算机图形学（二）——实验二：直线的生成算法
实验二：直线的生成算法
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算法