中点画线法算法原理：计算机图形学实验报告实验一贵州大学实验报告学院：计信学院专业：计科班级：计科101姓名罗琳学号1008060016实验组实验时间2013-3-27指导教师吴云成绩实验项目名称直线生成算法实验目的通过本实验，了解并掌握在光栅显示系统中直线的生成和显示算法，熟悉相关开发平台为后继实验打下基础实验要求实现DDA®线算法，中点画线算法和Bresenham画线算法，并比较实验原理数值微分法(DDA-DigitalDifferentialAnalyzer)算法原理：设直线两端点为：P1(x1,y1)及P0(x0,y0),则直线斜率为：直线方程为：当|k|<=1,x每增加1,y最多增加1(或增加小于1)当|k|>1,y每增加1,x最多增加1(或增加小于1)0101xxyyxykBkxyii11111||1iiiiiiiiykxBkxxBkxBkxyykxletxyykkyixiyi+1xi+111111||1iiiiiyyBByxkkkkkletyxxkk算法分析：:复杂度：加法+取整优点：避免了y=kx+b方程中的浮点乘法，比直接用点斜式画线快缺点：需浮点数加法及取整运算，不利于硬件实现。
设0中点算法用整数加法及比较代替了DDA中的浮点数加法及取整运算,效率大大提高假设直线的起点、终点分别为：(X0,Y0),(X1,Y1)，直线将二维空间划分为三个区域:直线方程: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值为:dnew=F(xi+2,yi+0.5)=a(xi+2)+b(yi+0.5)+c而dold=F(xi+1,yi+0.5)=a(xi+1)+b(yi+0.5)+cyxF(x,y)=0F(x,y)>0F(x,y)<0(x1,y1)(x0,y0)xPi=(xi,yi)MQP1p2ydnew=dold+a=dold-dy2.如由pi点确定是右上方P1点(d<0)，则新的中点M在x和y方向都增加1,新的d值为dnew=F(xi+2,yi+1.5)=a(xi+2)+b(yi+1.5)+c而dold=F(xi+1,yi+0.5)=a(xi+1)+b(yi+0.5)+cdnew=dold+a+b=dold-dy+dx在每一步中，根据前一次第二迭中计算出的d值的符号，在正右方和右上方的两个点中进行选择。
d的初始值:d0=F(x0+1,y0+0.5)=F(x0,y0)+a+b/2=a+b/2=-dy+dx/2F(x0,y0)=0，(x0,y0)在直线上为了消除d的分数,重新定义F(x,y)=2(ax+by+c)则每一步需要计算的dnew是简单的整数加法dy=y1-y0,dx=x1-x0d0=-2dy+dxdnew=dold-2*dy，当dold>=0dnew=dold-2(dy-dx)，当dold<0Bresenham画线算法：算法原理：与DDA#法相似，Bresenham画线算法也要在每列象素中找到与理想直线最逼近的象素点根据直线的斜率来确定变量在x或y方向递增一个单位另一个方向y或x的增量为0或1，它取决于实际直线与最接近网格点位置的距离这一距离称为误差算法的巧妙构思，使每次只需检查误差项(增量)的符号即可定义决策变量：d=d+k(0=0.5)实验内容实验源程序如下：voidCLineDlg::OnRadioPlus()//缺省选择{//TODO:AddyourcontrolnotificationhandlercodehereAlgorithm=0;//算法选择}voidCLineDlg::OnRadio(){//TODO:AddyourcontrolnotificationhandlercodehereAlgorithm=2;}voidCLineDlg::OnRadio1(){//TODO:AddyourcontrolnotificationhandlercodehereAlgorithm=1;}voidCLineDlg::OnLinedraw(){//TODO:AddyourcontrolnotificationhandlercodehereCWnd*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);inti,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));intx1,y1,x0,y0;UpdateData(true);x1=m_x1;x0=m_x0;y1=m_y1;y0=m_y0;switch(Algorithm){case0:{inta,b,d1,d2,d,x,y;floatdy,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(xSetPixel(x,y,RGB(0,255,0));}}else{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(xSetPixel(y,x,RGB(0,255,0));}}break;}case1:{floatdy,dx,m;dx=float(x1-x0);dy=float(y1-y0);m=dy/dx;if(m<=1){intx;floaty;y=float(y0);for(x=x0;x<=x1;x++){pControlDC->SetPixel(x,(int)(y+0.5),RGB(0,0,255));y=y+m;}}else{inty;floatx;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;}case2:{intx,y,dx,dy,e,i;floatd1y,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;}}}voidCLineDlg::OnDelete(){//TODO:AddyourcontrolnotificationhandlercodehereInvalidate();//清除作图区的线}实验结果1.DDA画线结果为：2.中点画线结果为：3.Bresenham画线结果为：4.点击清除结果为：指导教师意见签名:年月日。