计算机图形学第二讲-光栅图形学

第二讲光栅图形学光栅图形学部分重要概念直线的生成圆的扫描转换多边形的扫描转换字符的显示方法裁剪反走样消隐光栅扫描式显示器是一种画点设备，可看作是一个点阵单元发生器，并可控制每个点阵单元的亮度。每个可寻址的点阵单元称为一个像素（pixel）。显示器在水平和垂直方向上能够寻址的像素数称为分辨率。光栅图显示器特征部分重要概念区域充填光栅化（扫描转化）确定最佳逼近图形的像素集合，并用指定属性写像素的过程称为图形的扫描转化或光栅化。确定二维图形内部区域对应的像素集，并用指定的属性或图案进行显示的过程。部分重要概念走样和反走样裁剪消隐（消除隐藏线和隐藏面）确定一个图形的哪些部分在窗口内，必须显示；哪些部分落在窗口之外，不该显示的过程称为裁剪。因像素逼近误差，使图形产生畸变（台阶、锯齿）的现象称之为走样。用于减少或消除走样的技术称为反走样。为了提高图形的真实性，必须把隐藏的部分从图中删除，习惯上称为消除隐藏线和隐藏面，或简称消隐。直线段的扫描转换算法•直线的扫描转换:确定最佳逼近于该直线的一组象素，并且按扫描线顺序，对这些象素进行写操作。•在介绍三个常用算法前，先介绍一种最容易想到的算法：直接计算法！0直接计算法假定直线的起点、终点分别为：（x0,y0),(x1,y1)，且都为整数。计算出斜率k=(y1-y0)/(x1-x0),在Y轴的截距b=y0-k*x0y=k*x+b(Xi+1,kXi+1+b)(Xi,Yi)(Xi,Yi)栅格交点表示象素点位置。。。。直接计算法这样一来，只要给定x的值，根据解析式立即可以计算出对应的y值，然后输出(x,round(y)).这种方法直观，但效率太低，因为每一步需要一次浮点乘法、一次浮点加法和一次舍入运算。(Xi+1,kXi+1+b)(Xi,Yi)(Xi,Yi)。。。。直线的生成直线段扫描转换算法：•数值微分法DDA算法•中点画线法•Bresenham画线算法1数值微分法（ＤＤＡ）假定直线的起点、终点分别为：（x0,y0),(x1,y1)，且都为整数。(Xi+1,Yi+k)(Xi,Int(Yi+0.5))(Xi,Yi)。。。。数值微分(DDA)法•基本思想已知过端点P0(x0,y0),P1(x1,y1)的直线段Ly=kx+b直线斜率为考虑当x从xixi+1时y的变化规律：设x=xi+1-xixi+1=xi+x0101xxyyk数值微分(DDA)法计算yi+1=kxi+1+b=k(xi+x)+b=kxi+b+kx=yi+kx当x=1;yi+1=yi+k•即：当x每递增1，y递增k(即直线斜率)；•注意上述分析的算法仅适用于k≤1的情形。在这种情况下，x每增加1,y最多增加1。•当k1时，必须把x，y地位互换数值微分(DDA)法•增量算法：在一个迭代算法中，如果每一步的x、y值是用前一步的值加上一个增量来获得，则称为增量算法。•DDA算法就是一个增量算法。数值微分(DDA)法voidDDALine(intx0,inty0,intx1,inty1,intcolor)intx；floatdx,dy,y,k;dx,=x1-x0,dy=y1-y0;k=dy/dx,y=y0;for(x=x0;xx1,x++)drawpixel(x,int(y+0.5),color);y=y+k;数值微分(DDA)法•例：画直线段P0(0,0)--P1(5,2)k=0.4xyint(y+0.5)00010.4020.8131.2141.6252.02012345321Line:P0(0,0)--P1(5,2)数值微分(DDA)法•缺点：在此算法中，y、k必须是float，且每一步都必须对y进行舍入取整，不利于硬件实现。2中点画线法•原理：假定直线斜率0K1，且已确定点亮象素点P（Xp,Yp）,则下一个与直线最接近的像素只能是P1点或P2点。设M为中点，Q为交点现需确定下一个点亮的象素。P=(xp,yp)QP2P1中点画线法–当M在Q的下方-P2离直线更近更近-取P2。–M在Q的上方-P1离直线更近更近-取P1–M与Q重合，P1、P2任取一点。–问题：如何判断M与Q点的关系？P=(xp,yp)QP2P1中点画线法由常识知：若y=kx+b;F(x,y)=y-kx-b;则有点在直线下方点在直线上方点在直线上面0,0,0,yxFyxFyxFP=(xp,yp)QP2P1中点画线法假设直线方程为：ax+by+c=0通过两点不能唯一确定a,b,c,取a=y0-y1,b=x1-x0,c=x0y1-x1y0，F(x,y)=ax+by+c;则有∴欲判断M点是在Q点上方还是在Q点下方，只需把M代入F(x,y),并检查它的符号。点在直线下方点在直线上方点在直线上面0,0,0,yxFyxFyxFP=(xp,yp)QP2P1中点画线法构造判别式：d=F(M)=F(xp+1,yp+0.5)=a(xp+1)+b(yp+0.5)+c当d0，M在直线(Q点)下方，取右上方P2；当d0，M在直线(Q点)上方，取右方P1；当d=0，选P1或P2均可，约定取P1；能否采用增量算法呢？P=(xp,yp)QP2P1中点画线法若d0----M在直线上方-取P1;此时再下一个象素的判别式为d1=F(xp+2,yp+0.5)=a(xp+2)+b(yp+0.5)+c=a(xp+1)+b(yp+0.5)+c+a=d+a；增量为aP=(xp,yp)QP2P1中点画线法•若d0------M在直线下方-取P2;•此时再下一个象素的判别式为d2=F(xp+2,yp+1.5)=a(xp+2)+b(yp+1.5)+c=a(xp+1)+b(yp+0.5)+c+a+b=d+a+b；增量为a＋bP=(xp,yp)QP2P1中点画线法•画线从(x0,y0)开始，d的初值d0=F(x0+1,y0+0.5)=a(x0+1)+b(y0+0.5)+c=F(x0,y0)+a+0.5b=a+0.5b由于只用d的符号作判断，为了只包含整数运算,可以用2d代替d来摆脱小数，提高效率。中点画线法voidMidpointLine(intx0,inty0,intx1,inty1,intcolor){inta,b,d1,d2,d,x,y;a=y0-y1,b=x1-x0,d=2*a+b;d1=2*a,d2=2*(a+b);x=x0,y=y0;drawpixel(x,y,color);while(xx1){if(d0){x++;y++;d+=d2;}else{x++;d+=d1;}drawpixel(x,y,color);}/*while*/}/*midPointLine*/中点画线法•例：用中点画线法P0(0,0)P1(5,2)a=y0-y1=-2b=x1-x0=5d0=2a+b=1d1=2a=-4d2=2(a+b)=6ixiyid1001210-33213431-15425012345321斜率不在[0,1]的直线的处理•设起点和终点分别为(x0,y0)和(x1,y1)•若k1•则(y0,x0)和(y1,x1)所确定的直线斜率k€[0,1]，适用于前面讨论的情形。•对(y0,x0)和(y1,x1)所确定的直线进行扫描转换，每确定一组(x,y)，输出(y,x)。(x0,y0)(y1,x1)(x1,y1)(y0,x0)斜率不在[0,1]的直线的处理•若-1k0•先对(x0,-y0)和(x1,-y1)所确定的•直线进行扫描转换，•每确定一组(x,y)，输出(x,-y)。(x0,y0)(x1,-y1)(x1,y1)(x0,-y0)斜率不在[0,1]的直线的处理•若k-1•对(-y0,x0)和(-y1,x1)所确定的直线进行扫描转换，每确定一组(x,y)，输出(y,-x)。(x0,y0)(x1,-y1)(x1,y1)(x,-y0)(-y0,x0)(-y1,x1)图5-8改进的Brensemham算法绘制直线的原理ddddkkkkk3Bresenham算法(教材上介绍的)假定直线段的0≤k≤1基本原理：Bresenham算法原理0.5)(d0.5)(d1111iiiiiyyyxx误差项d的计算•d初=0，•每走一步：d=d+k•一旦y方向上走了一步，d=d-1算法步骤：1.输入直线的两端点P0(x0,y0)和P1(x1,y1)。2.计算初始值△x、△y、d=0、x=x0、y=y0。3.绘制点(x,y)。4.d更新为d+k，判断d的值。若d0.5，则(x,y)更新为(x+1,y+1)，同时将d更新为d-1；否则(x,y)更新为(x+1,y)。5.当直线没有画完时，重复步骤3和4。否则结束。改进1：令e=d-0.50)(e0)(e1111iiiiiyyyxx•e初=-0.5，•每走一步有e=e+k。•if(e0)thene=e-10.5)(d0.5)(d1111iiiiiyyyxx算法步骤为：1.输入直线的两端点P0(x0,y0)和P1(x1,y1)。2.计算初始值△x、△y、e=-0.5、x=x0、y=y0。3.绘制点(x,y)。4.e更新为e+k，判断e的符号。若e0，则(x,y)更新为(x+1,y+1)，同时将e更新为e-1；否则(x,y)更新为(x+1,y)。5.当直线没有画完时，重复步骤3和4。否则结束。改进2：用2e△x来替换e•e初=-△x，•每走一步有e=e+2△y。•if(e0)thene=e-2△xe=e+ke=e+△y/△x△xe=△xe+△ye=-0.52e=-1算法步骤：1.输入直线的两端点P0(x0,y0)和P1(x1,y1)。2.计算初始值△x、△y、e=-△x、x=x0、y=y0。3.绘制点(x,y)。4.e更新为e+2△y，判断e的符号。若e0，则(x,y)更新为(x+1,y+1)，同时将e更新为e-2△x；否则(x,y)更新为(x+1,y)。5.当直线没有画完时，重复步骤3和4。否则结束。Bresenham画线算法BresenhamLine(x0,y0,x1,y1,color){intx0,y0,x1,y1,color;intx,y,dx,dy,e;dx=x1-x0;dy=y1-y0;e=-dx;x=x0;y=y0;for(i=0;i=dx;i++){drawpixel(x,y,color);x++;e=e+2*dy;if(e=0){e=e-2*dx;y++;}}}举例：用Bresenham方法扫描转换连接两点P0（0,0）和P1（5,2）的直线段。•xyee0=-5;dx=5;dy=2•00-1•103(-7)•21-3•311(-9)•42-5•52-1Bresenham算法Bresenham画线算法在直线生成的算法中Bresenham算法是最有效的算法之一。令k=Δy/Δx，就0≤k≤1的情况来说明Bresenham算法。由DDA算法可知：yi+1=yi+k(1)由于k不一定是整数，由此式求出的yi也不一定是整数，因此要用坐标为（xi,yir）的象素来表示直线上的点，其中yir表示最靠近yi的整数。实验报告1：•名称：直线的扫描转换•目的要求：理解和掌握直线扫描转换的三种算法，并在某种开发环境下将其具体实现。•实验步骤：（要写出实际实现的程序和结果，切忌将书上或笔记上的程序照搬）•要有实验总结。基本要求•理解图形的扫描转换的含义；•掌握DDA、MIDPoint、Bresenham画线算法。（算法的原理、代码表示、特点等）•能够编程处理任意直线。课堂测试（一）奇数列：•解释下列名词：光栅化、区域填充、裁剪•请说明中点划线法的基本思想•根据中点划线法用C语言完成下列函数2012/2/29//SetPixel为已有函数，描画点(x,y)voidSetPixel(intx,inty,intcolor);voidMidpointLin