计算机图形学基础教程——第2章1

清华大学计算机科学与技术系计算机图形学基础第二章光栅图形学•什么是光栅图形学？光栅显示器－图形光栅化、光栅化图形的处理清华大学计算机科学与技术系计算机图形学基础•光栅图形学的研究内容–直线段的扫描转换算法–圆弧的扫描转换算法–多边形的扫描转换与区域填充–字符–裁剪–反走样–消隐清华大学计算机科学与技术系计算机图形学基础2.1直线段的扫描转换算法•直线的扫描转换:确定最佳逼近于该直线的一组象素，并且按扫描线顺序，对这些象素进行写操作。•三个常用算法：数值微分法（DDA）中点画线法Bresenham算法。012345321Line:P0(0,0)--P1(5,2)清华大学计算机科学与技术系计算机图形学基础2.1.1数值微分(DDA)法•基本思想已知过端点的直线段L：直线斜率为从的左端点开始，向右端点步进。步长=1(个象素)，计算相应的y坐标；取象素点(x,round(y))作为当前点的坐标。0101xxyyk),(),,(111000yxPyxPbkxyx0xxbkxy清华大学计算机科学与技术系计算机图形学基础–作为最底层的光栅图形算法，在通常的CAD/图形系统中，会被大量应用，因此，哪怕节约一个加法或减法，也是很了不起的改进。–由此出发点，导致增量算法的思想。清华大学计算机科学与技术系计算机图形学基础计算当时;即：当x每递增1，y递增k(即直线斜率)；xkyxkbkxbkxyiiii111xkyyii1清华大学计算机科学与技术系计算机图形学基础例：画直线段xint(y+0.5)y+0.5000100.4+0.5210.8+0.5311.2+0.5421.6+0.5522.0+0.5注：网格点表示象素012345321Line:P0(0,0)--P1(5,2))2,5()0,0(10PP清华大学计算机科学与技术系计算机图形学基础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;清华大学计算机科学与技术系计算机图形学基础•问题：当k1时，会如何？清华大学计算机科学与技术系计算机图形学基础注意上述分析的算法仅适用于k≤1的情形。在这种情况下，x每增加1,y最多增加1。当k1时，必须把x，y地位互换k1示意图012345321Line:P0(0,0)--P1(5,2)清华大学计算机科学与技术系计算机图形学基础2.1.2中点画线法采用增量思想的DDA算法，每计算一个象素，只需计算一个加法，是否最优？如非最优，如何改进？目标：进一步将一个加法改为一个整数加法。新思路－DDA算法采用点斜式，可否采用其他的直线表示方式？清华大学计算机科学与技术系计算机图形学基础•基本思想当前象素点为(xp,yp)。下一个象素点为P1或P2。设M=(xp+1,yp+0.5)，为p1与p2之中点，Q为理想直线与x=xp+1垂线的交点。将Q与M的y坐标进行比较。–当M在Q的下方，则P2应为下一个象素点；–M在Q的上方，应取P1为下一点。P=(xp,yp)QP2P1清华大学计算机科学与技术系计算机图形学基础构造判别式:d=F(M)=F(xp+1,yp+0.5)=a(xp+1)+b(yp+0.5)+c其中a=y0-y1,b=x1-x0,c=x0y1-x1y0当d0，M在L(Q点)下方，取右上方P2为下一个象素；当d0，M在L(Q点)上方，取右方P1为下一个象素；当d=0，选P1或P2均可，约定取P1为下一个象素；清华大学计算机科学与技术系计算机图形学基础但这样做，每一个象素的计算量是4个加法，两个乘法。“山穷水尽疑无路”如果也采用增量算法呢？d是xp,yp的线性函数，因此可采用增量计算，提高运算效率。清华大学计算机科学与技术系计算机图形学基础•若当前象素处于d0情况，则取正右方象素P1(xp+1,yp),要判下一个象素位置，应计算d1=F(xp+2,yp+0.5)=a(xp+2)+b(yp+0.5)=d+a；增量为a•若d0时，则取右上方象素P2(xp+1,yp+1)。要判断再下一象素，则要计算d2=F(xp+2,yp+1.5)=a(xp+2)+b(yp+1.5)+c=d+a+b；增量为a＋b清华大学计算机科学与技术系计算机图形学基础•至此，至少新算法可以和DDA算法一样好。•能否再做改进？•能否实现整数运算？清华大学计算机科学与技术系计算机图形学基础•画线从(x0,y0)开始，d的初值d0=F(x0+1,y0+0.5)=F(x0,y0)+a+0.5b=a+0.5b。可以用2d代替d来摆脱小数，提高效率。令d0=2a+b,d1=2a,d2=2a+2b,我们有如下算法。清华大学计算机科学与技术系计算机图形学基础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*/清华大学计算机科学与技术系计算机图形学基础例：用中点画线法ixiyid1001210-33213431-15425012345321)2,5()0,0(10PP5,20110xxbyya,6)(2,42,12210badadbad清华大学计算机科学与技术系计算机图形学基础2.1.3Bresenham算法•基本思想–DDA算法采用点斜式，中点法采用隐式表示。–中点法可以有整数算法。–其他表示可以推出整数算法吗？清华大学计算机科学与技术系计算机图形学基础–过各行各列象素中心构造一组虚拟网格线。按直线从起点到终点的顺序计算直线与各垂直网格线的交点，然后根据误差项的符号确定该列象素中与此交点最近的象素。dddd清华大学计算机科学与技术系计算机图形学基础设直线方程为：，其中k=dy/dx。因为直线的起始点在象素中心，所以误差项d的初值d0＝0。X下标每增加1，d的值相应递增直线的斜率值k，即d＝d＋k。一旦d≥1，就把它减去1，这样保证d在0、1之间。–当d≥0.5时，最接近于当前象素的右上方象素（）–而当d0.5时，更接近于右方象素（）。为方便计算，令e＝d-0.5，e的初值为-0.5，增量为k。–当e≥0时，取当前象素（xi，yi）的右上方象素（）；–而当e0时，更接近于右方象素（）。kyxxkyyiiiii)(1111,iiyxiiyx,111,iiyxiiyx,1清华大学计算机科学与技术系计算机图形学基础可以改用整数以避免除法。由于算法中只用到误差项的符号，因此可作如下替换：例：Line:P0(0,0),P1(5,2)k=dy/dx=0.4xye00-0.510-0.1210.331-0.3420.152-0.5大于零，y加一，小于零，不变dxee**2'012345321清华大学计算机科学与技术系计算机图形学基础voidBresenhamline(intx0,inty0,intx1,inty1,intcolor){intx,y,dx,dy;floatk,e;dx=x1-x0,dy=y1-y0,k=dy/dx;e=-0.5,x=x0,y=y0;for(i=0;idx;i++){drawpixel(x,y,color);x=x+1，e=e+k;if(e0){y++,e=e-1;}}}清华大学计算机科学与技术系计算机图形学基础•最终，Bresenham算法也是每个象素，需一个整数算法，其优点是可以用于其他二次曲线。至此，直线光栅化是否终结？清华大学计算机科学与技术系计算机图形学基础新方法：BRDC:binaryrepresentationofdisplacementcodeforlineMiaoLF,LiuXG,PengQS,BaoHJCOMPUTERS&GRAPHICS-UK26(3):401-408JUN2002清华大学计算机科学与技术系计算机图形学基础2.2圆弧的扫描转换算法•圆的特征:八对称性。只要扫描转换八分之一圆弧，就可以求出整个圆弧的象素集•中点画圆法考虑中心在原点，半径为R的第二个8分圆，–构造判别式（圆方程）222)5.0()1()5.0,1()(RyxyxFMFdppppP=(xp,yp)P1P2M清华大学计算机科学与技术系计算机图形学基础若d0,则取P1为下一象素，而且再下一象素的判别式为若d=0,则应取P2为下一象素，而且下一象素的判别式为第一个象素是（0,R），判别式d的初始值为32)5.0()2()5.0,2('222pppppxdRyxyxFd5)(2)5.1()2()5.1,2('222ppppppyxdRyxyxFdRRFd25.1)5.0,1(0清华大学计算机科学与技术系计算机图形学基础•为了进一步提高算法的效率，可以将上面的算法中的浮点数改写成整数，将乘法运算改成加法运算，即仅用整数实现中点画圆法。•使用e=d-0.25代替d•e0=1-R清华大学计算机科学与技术系计算机图形学基础算法过程MidPointCircle(intrintcolor){intx,y;floatd;x=0;y=r;d=1.25-r;circlepoints(x,y,color);//显示圆弧上的八个对称点while(x=y){if(d0)d+=2*x+3;else{d+=2*(x-y)+5;y--;}x++;circlepoints(x,y,color);}}清华大学计算机科学与技术系计算机图形学基础2.3多边形的扫描转换与区域填充•多边形有两种重要的表示方法：顶点表示和点阵表示。•多边形的扫描转换:把多边形的顶点表示转换为点阵表示。•区域可采用内点表示和边界表示两种表示形式。•区域填充:指先将区域的一点赋予指定的颜色，然后将该颜色扩展到整个区域的过程。清华大学计算机科学与技术系计算机图形学基础•多边形分为凸多边形、凹多边形、含内环的多边形。清华大学计算机科学与技术系计算机图形学基础2.3.1多边形的扫描转换•2.3.1.1扫描线算法–基本思想：•按扫描线顺序，计算扫描线与多边形的相交区间，再用要求的颜色显示这些区间的象素，即完成填充工作。–对于一条扫描线填充过程可以分为四个步骤：•求交•排序•配对•填色清华大学计算机科学与技术系计算机图形学基础一个多边形与若干扫描线0112233445566778891011P2(5,1)EP3(11,3)DP4(11,8)GFCBP5(5,5)P6(2,7)AP1(2,2)清华大学计算机科学与技术系计算机图形学基础•数据结构–活性边表(AET)：把与当前扫描线相交的边称为活性边，并把它们按与扫描线交点x坐标递增的顺序存放在一个链表中结点内容x：当前扫描线与边的交点坐标△x：从当前扫描线到下一条扫描线间x的增量ymax：该边所交的最高扫描线号ymax2073.5-1.57P6P1P5P6AB7281108P4P5P3P4CD△xymax△xymax△xymax△xymax清华大学计算机科学与技术系计算机图形学基础新边表（NET）：–存放在该扫描线第一次出现的边。若某边的较低端点为ymin，则该边就放在扫描线ymin的新边表中上图所示各条扫描线的新边表NET76P4P5P5P6543210P1P2P2P385-3253320711085285-1.57