计算机图形学(直线的扫描转换I)

计算机图形学第3章基本光栅图形算法1直线的扫描转换2圆的扫描转换3多边形的扫描转换4区域填充5字符的生成6光栅图形的反走样算法22014-2015-1:CG:SCUEC本章内容直线的扫描转换生成直线算法的基本要求基本增量算法中点法Bresenham算法3直线扫描转换的定义2014-2015-1:CG:SCUEC所画的直线是离散的像素集合只有画水平线,垂直线,及正方形对角线时,像素点集的位置才是准确的A(x1,y1)、B(x2,y2)、在计算机显示器上画一条直线和在纸上画一条直线有什么本质的区别?显示器是一个有限的像素矩阵4直线扫描转换的定义2014-2015-1:CG:SCUEC直线扫描转换的定义在计算机显示器上画一条直线，只能在显示器所给定的有限个像素组成的点阵中，选择能最佳地逼近于该直线的一组像素，并对这些像素按指定的属性进行写操作。这就是通常所说的用显示器绘制直线，即直线的扫描转换。直线扫描转换的主要工作：快速找出像素点阵中距直线最近的网格点，用这些网格点对应的像素表示该直线。2014-2015-1:CG:SCUEC5给定一个写像素函数DrawPixel（x,y,color),能不能直接用数学公式生成直线？A(x0,y0)B(x1,y1)voidDirectLine(intx0,inty0,intx1,inty1,intcolor)intx；floatdx,dy,b,k;dx=x1-x0,dy=y1-y0;k=dy/dx,b=y0-k*x0;for(x=x0;xx1;x++)DrawPixel(x,int(k*x+b),color);生成直线算法的基本要求62014-2015-1:CG:SCUECoxyk1(xi,yi)(xi+1,yi+1)数学公式生成直线的讨论：–生成的直线可能不直–算法复杂度高，运算速度慢生成直线算法的基本要求7生成直线算法的基本要求生成的直线要直直线的端点要准确，保证绘制无定向性直线的亮度、色泽要均匀，避免在视觉上造成一段亮一段暗的感觉画线的速度要尽可能的快–有可能产生隔行显示2014-2015-1:CG:SCUEC问题直接用直线方程y=kx+b来生成直线，之所以算法复杂度高，是因为在迭代过程中每次都要用到浮点数的乘法运算，那是否可以去掉浮点数的乘法运算呢？基本增量算法8最基本的增量算法是DDA算法数值微分分析器(DigitalDifferentialAnalyzer)DDA算法的本质是用数值方法解直线的微分方程基本思想：如果在一个迭代算法中，每一步的x值和y值都可以由前一步的的值加一个增量得到，那么这种算法就称为增量算法。2014-2015-1:CG:SCUEC生成直线的DDA算法设直线的起点坐标为(x0,y0)，终点坐标为(x1,y1)，令x=x1–x0，y=y1-y0，则直线微分方程为:,dxdyxydtdt该方程的数值解的递推公式为xi+1=xi+xt(t表示步长）yi+1=yi+yt92014-2015-1:CG:SCUEC如果取t=1/x，我们有：xi+1=xi+1yi+1=yi+k即x方向每次增加1，y方向增加k(直线的斜率)；生成直线的DDA算法voidDDALine1(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;102014-2015-1:CG:SCUECDDA算法画线举例例：用DDA法画线)2,5()0,0(10PP012345321Line:P0(0,0)－P1(5,2)xy+0.5int(y+0.5)00.5010.4+0.5020.8+0.5131.2+0.5141.6+0.5252.0+0.52注：网格点表示象素112014-2015-1:CG:SCUEC讨论：根直接用数学公式画直线相比，算法效率有较大提高。还是有可能造成隔行显示DDA算法的分析oxyoxy(xi,yi)(xi+1,yi+1)(xi,yi)(xi+1,yi+1)122014-2015-1:CG:SCUEC为了解决隔行显示的问题，分成两种情况考虑：首先考虑直线斜率的绝对值小于1的情况，这时|x|≥|y|0，我们取t=1/|x|，DDA数值解的递推公式为:xi+1=xi+1，yi+1=yi+k其次考虑直线斜率的绝对值大于1的情况，这时0|x|≤|y|，我们取t=1/|y|，DDA数值解的递推公式为:xi+1=xi+1/k，yi+1=yi+1综合起来，取步长t=min{1/|x|,1/|y|}即根据斜率k的偏移程度，决定是以x为步进方向还是以y为步进方向。然后在相应的步进方向上，步进变量每次增加一个像素，而另一个相关坐标变量则为yi+1=yi+k（以x为步进变量为例xi+1=xi+1）DDA算法的改进132014-2015-1:CG:SCUECDDA算法的进一步改进讨论：如果直线段的两个端点不是整数怎么办？142014-2015-1:CG:SCUECvoidDDALine(floatxs,floatys,floatxe,floatye,intcolor){intn,ix,iy,idx,idy;intFlag;//插补方向标记intLength;//插补长度floatx,y,dx,dy;dx=xe-xs;dy=ye-ys;if(fabs(dy)=fabs(dx)){//X方向长，|斜率|=1Length=abs(Round(xe)-Round(xs));Flag=1;//最大的插补长度和方向标记ix=Round(xs);//初始X点idx=sign(dx);//X方向单位增量y=ys+dy/dx*((float)(ix)-xs);//初始Y点修正dy=dy/fabs(dx);//Y方向增量(斜率)}完整的DDA算法描述152014-2015-1:CG:SCUECelse{//Y方向长，|斜率|1Length=abs(Round(ye)-Round(ys));Flag=0;iy=Round(ys);//初始Y点idy=sign(dy);//Y方向单位增量x=xs+dx/dy*((float)(iy)-ys);//初始X点修正dx=dx/fabs(dy);//X方向增量(斜率的倒数)}if(Flag){//X方向单位增量for(n=0;n=Length;n++){//X方向插补过程DrawPixel(ix,Round(y),color);ix+=idx;y+=dy;}//Endoffor}//Endofifelse{//Y方向斜率增量for(n=0;n=Length;n++){//Y方向插补过程DrawPixel(Round(x),iy,color);iy+=idy;x+=dx;}//Endoffor}//Endofelse}//Finish162014-2015-1:CG:SCUEC首点校正对逼近的影响172014-2015-1:CG:SCUECDDA算法优缺点用DDA算法计算象素位置，可消除直线方程中的乘法，在x和y方向使用合适的增量可逐步沿直线推出各象素的位置，比直接画线算法快。但算法中的斜率k与y坐标必须用浮点数表示，每一步运算必须对y进行舍入取整，取整操作和浮点运算释放耗时，并且算法中还存在除法运算，不利于在硬件中实现。思考：如何消除DDA算法中的除法运算？如何消除DDA算法中的取整操作和浮点运算？182014-2015-1:CG:SCUEC生成直线的中点法基本原理：方便起见，假设直线斜小于1设P=(x,y)是直线上的一点(用Δ表示)，与(x,y)最近的像素为(xi,yi)(用实心小圆点表示)，则下一个与直线最近的点只能是正右方或右上方的点PB(xi+1,yi)和PT(xi+1,yi+1)之一（用小空心圆表示）中点法每步迭代涉及的像素和中点示意图MPTPBP=(x,y)Q－设M=(xi+1,yi+0.5)，为PB与PT之中点，Q为理想直线与x=xi+1垂线的交点。将Q与M的y坐标进行比较，当M在Q的下方，则PT离直线近，下一个象素点应取PT；M在Q的上方，则PB离直线更近，下一个象素点应取PT。19(xi,yi)2014-2015-1:CG:SCUEC中点法的具体实现设直线的起点和终点分别为(xs,ys)和(xe,ye),直线方程为:其中0),(cbyaxyxFseesseseayybxxcxyyxF(x,y)=0,F(x,y)0,F(x,y)0,分别表示点(x,y)在直线上、直线上方和直线下方()(1,0.5)(1)(0.5)iiiiidFMFxyaxbyc要判断点M在直线上，上方还是下方可将M代入下面的判别式判断其正负即可202014-2015-1:CG:SCUECdi0，Q在M上方，取PT为下一像素di0，取PB为下一像素di=0，可在两个点中任取一个，约定取下方的点PBMP=(x,y)QPTPB思考：这样做，每一个像素的计算量是多少？21中点法的具体实现答案：每一个像素的计算量是4个加法，两个乘法。比DDA算还要坏，“山穷水尽疑无路了吗？”2014-2015-1:CG:SCUEC若di0，取右上方像素PT，下一个像素应取哪个，应计算如下的判别式1()(2,1.5)(2)(1.5)(1)(0.5)iTiiiiiiidFMFxyaxbycaxbycabdab判别式的增量计算22是xi,yi的线性函数，因此可采用增量计算，提高运算效率()(1,0.5)(1)(0.5)iiiiidFMFxyaxbyc(xi,yi)MPTMTP=(x,y)2014-2015-1:CG:SCUEC若di≥0，取正右方像素PB，下一个像素应取哪个，应计算如下的判别式1()(2,0.5)(2)(0.5)(1)(0.5)iBiiiiiiidFMFxyaxbycaxbycada判别式的增量计算23()(1,0.5)(1)(0.5)iiiiidFMFxyaxbyc(xi,yi)MMBP=(x,y)PB2014-2015-1:CG:SCUEC判别式di的初始值d0的计算0()(1,0.5)(1)(0.5)0.5()0.50.5SssssssssdFMFxyaxbycaxbycabFxyabab判别式的增量计算24MS(xs,ys)2014-2015-1:CG:SCUEC至此，至少新算法可以和DDA算法一样好，能否再做改进？022dabxy当d0时，22ddady当d0时，2222ddabdxy由于在实际应用中只关心d的符号，因此可在算法实现中以2d的正负代替d的正负，这样可以简化掉d的初始值中的小数。具体做法如下：中点法的改进2014-2015-1:CG:SCUEC552)2,5()0,0(10PP10102,5yyyxxx0002124,2()6geltdxydydxy例：用中点法画线ixiyid0001110-32213331-14425012345321Line:P0(0,0)－P1(5,2)中点法画线举例26具体实现2014-2015-1:CG:SCUEC计算机图形学结束课堂练习28用中点法扫描转换一条连接两点(0，0)和(8，5)的直线段012345678321452014-2015-1:CG:SCUE