贵州大学实验报告 学院：
计信学院 专业：
计科 班级：
计科 101 姓名 罗琳 学号 1008060016 实验组 实验时间 2013-3-27 指导教师 吴云 成绩 实验项目名称 直线生成算法 实验目的 通过本实验，了解并掌握在光栅显示系统中直线的生成和显示算法，熟悉相关开发平台。为后继实验打下基础。
实验要求 实现 DDA 画线算法，中点画线算法和 Bresenham 画线算法，并比较 实验原理 数值微分法(DDA-Digital Differential Analyzer)算法原理：
设直线两端点为:P1(x1,y1)及 P0(x0,y0), 则直线斜率为：
直线方程为：
当 | k |<=1，x 每增加 1，y 最多增加 1(或增加小于 1)。
当 | k |>1 ,y 每增加 1,x 最多增加 1(或增加小于 1)。
0 10 1x xy yxykB kx yi i 1 1111| | 1i i i ii ii iy kx B k x x B kx B k xy y k xlet xy y k k y i x i y i +1 x i +1 11111| | 1i iii iy y B B yxk k k k klet yx x kk
算法分析：
：
复杂度：加法+取整 优点：避免了 y=kx+b 方程中的浮点乘法,比直接用点斜式画线快。
缺点：需浮点数加法及取整运算,不利于硬件实现。
中点画线法 算法原理：
设 0 中点算法用整数加法及比较代替了DDA 中的浮点数加法及取整运算,效率大大提高。假设直线的起点、终点分别为：（X 0 ,Y 0),(X 1 ,Y 1)，直线将二维空间划分为三个区域: 直线方程: F(x,y)=ax+by+c=0 其中: a=-(y1-y0)，b=(x1-x0)，c=-B(x1-x0)如 F(x,y)=0, 则(x,y)在直线上 如 F(x,y)<0, 则(x,y)在直线下方 如 F(x,y)>0, 则(x,y)在直线上方 因此，可将中点 M 的坐标(Xp+1,Yp+0.5)代入直线方程，并判断其符号即可确定象素点的选取。 定义决策变量: d= F(xi+1,yi+0.5)=a(xi+1)+b(yi+0.5)+c 如果 d>0,则M在理想直线上方,选正右方P2点； 如果 d<0,则 M 在理想直线下方,选右上方 P1 点； 如果 d=0,则 M 在理想直线上,选 P1/ P2 点。 由于 d 是 xi 和 yi 的线性函数，可采用增量计算提高运算效率。 1.如由 pi 点确定在是正右方 P2 点(d>0).，则新的中点 M 仅在 x 方向加 1,新的 d 值为: d new =F(xi+2,yi+0.5)=a(xi+2)+b(yi+0.5)+c 而 d old =F(xi+1,yi+0.5)=a(xi+1)+b(yi+0.5)+c y x F(x,y)=0F(x,y)>0F(x,y)<0(x1,y1)(x0,y0)x Pi=(xi, yi)M Q P1 p2 y d new =d old +a= d old-dy 2.如由 pi 点确定是右上方 P1 点(d<0)，则新的中点 M 在 x 和 y 方向都增加 1,新的 d 值为 d new =F(xi+2,yi+1.5)=a(xi+2)+b(yi+1.5)+c 而 d old =F(xi+1,yi+0.5)=a(xi+1)+b(yi+0.5)+c d new =d old +a+b= d old-dy+dx 在每一步中,根据前一次第二迭中计算出的 d 值的符号,在正右方和右上方的两个点中进行选择。d 的初始值: d0=F(x0+1,y0+0.5)=F(x0,y0)+a+b/2=a+b/2=-dy+dx/2 F(x0,y0)=0，(x0,y0)在直线上。 为了消除 d 的分数,重新定义 F(x,y)=2(ax+by+c)则每一步需要计算的 d new 是简单的整数加法 dy=y1-y0，dx=x1-x0 d0=-2dy+dx d new =d old-2*dy，当 d old >=0 d new =d old-2(dy-dx)，当 d old <0 Bresenham 画线算法 ： 算法原理： 与 DDA 算法相 似，Bresenham 画线算法也要在每列象素中找到与理想直线最逼近的象素点。 根 据 直 线的斜率来确定变量在 x 或 y 方向递增一个单位。另一个方向 y 或 x 的增量为 0 或 1，它取决于实际直线与最接近网格点位置的距离。这一距离称为误差。算法的巧妙构思，使每次只需检查误差项（增量）的符号即可。 定义决策变量： d = d+k(0 当 d>1 时,让 d=d-1,以保证 0<=d<1，d 0 =0 令 e = d-0.5(0 实验内容 实验源程序如下： void CLineDlg::OnRadioPlus()//缺省选择 { // TODO: Add your control notification handler code here Algorithm=0;//算法选择 } void CLineDlg::OnRadio(){ // TODO: Add your control notification handler code here Algorithm=2;} void CLineDlg::OnRadio1(){ // TODO: Add your control notification handler code here Algorithm=1;} void CLineDlg::OnLinedraw(){ // TODO: Add your control notification handler code here CWnd* pWnd=GetDlgItem(IDC_STATIC);CDC* pControlDC=pWnd->GetDC();pWnd->Invalidate();pWnd->UpdateWindow();pControlDC->SetViewportOrg(0,0);pControlDC->MoveTo(0,0);pControlDC->LineTo(0,335);pControlDC->MoveTo(0,0);pControlDC->LineTo(400,0);int i,j;for(i=0;i<=400;i+=10)for(j=0;j<=335;j++)pControlDC->SetPixel(i,j,RGB(200,200,200));for(i=0;i<=335;i+=10)for(j=0;j<=400;j++)pControlDC->SetPixel(j,i,RGB(200,200,200));int x1,y1,x0,y0;UpdateData(true); x1=m_x1;x0=m_x0;y1=m_y1;y0=m_y0;switch(Algorithm){ case 0: { int a,b,d1,d2,d,x,y;float dy,dx,m;dx=float(x1-x0);dy=float(y1-y0);m=dy/dx;if(m<=1){ a=y0-y1;b=x1-x0;d=2*a+b;d1=2*a;d2=2*(a+b);x=x0;y=y0;pControlDC->SetPixel(x,y,RGB(0,255,0));while(x a=x0-x1;b=y1-y0;d=2*a+b;d1=2*a;d2=2*(a+b);x=y0;y=x0;pControlDC->SetPixel(x,y,RGB(0,255,0));while(x } } else { int y;float x;x=float(x0);for(y=y0;y<=y1;y++){ pControlDC->SetPixel((int)(x+0.5),y,RGB(0,0,255));x=x+1/m;} } break;} case 2: { int x,y,dx,dy,e,i;float d1y,d1x,m;d1x=float(x1-x0);d1y=float(y1-y0);m=d1y/d1x;if(m<=1){ dx=x1-x0;dy=y1-y0;e=-dx;x=x0;y=y0;for(i=0;i<=dx;i++){ pControlDC->SetPixel(x,y,RGB(255,0,0)); x++;e=e+2*dy;if(e>=0){y++;e=e-2*dx;} } } else { dx=y1-y0;dy=x1-x0;e=-dy;x=y0;y=x0;for(i=0;i<=dx;i++){ pControlDC->SetPixel(y,x,RGB(255,0,0));x++;e=e+2*dy;if(e>=0){y++;e=e-2*dx;} } } break;} } } void CLineDlg::OnDelete(){ // TODO: Add your control notification handler code here Invalidate();//清除作图区的线 } 实验结果 1.DDA 画线结果为： 2.中点画线结果为： 3.Bresenham 画线结果为： 4.点击清除结果为： 实验总结 通过实验更加熟悉 MFC 的运用，对 DDA、中点算法和 Bresenham 算法原理有了更加清楚的了解。它们各自有自己的特点，Bresenham 算法不用计算斜率，所以不做除法；DDA 算法是浮点数运算，不易硬件实现；中点画线法只有整数运算，不含乘除法。因为基础知识不扎实，实验过程中遇到不少问题。明白要多动手实践才能学好。 指导教师意见 签名： 年 月 日
