计算机图形学第三章

,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第三章 光栅图形学,什么是光栅图形学？,光栅显示器 图形光栅化、,光栅化图形的处理,光栅显示器上显示的图形,称之为光栅图形。光栅显,示器可以看作是一个象素矩阵,在光栅显示器上显示,的任何一个图形,实际上.如何使光栅图形最完美地,逼近实际图形,便是光栅图形学要研究的内容。,光栅图形学的研究内容,直线段的,扫描转换,算法,圆弧的扫描转换算法,多边形的,扫描转换,与区域填充,字符,裁剪,反走样,消隐,3.1二维线画图元的生成,3.2二维填充图元的生成,3.3反混淆算法,所谓 图元的生成，是指完成图元的参数表示形式 （,由图形软件包的使用者指定）,到点阵表示形式,（光栅显示系统刷新时所需的表示形式）,的转换。通常也称扫描转换图元。,3.1二维线画图元的生成,1. 扫描转换直线段,DDA算法,中点画线法,Bresenham画线算法,2. 圆弧、椭圆弧扫描转换,中点算法,内接多边形迫近法,等面积多边形逼近法,3. 生成圆弧的正负法,4. 线画图元的属性控制,图形显示的几种方式,图形显示前需要：扫描转换+裁剪,裁剪-扫描转换：最常用，节约计算时间。,扫描转换-裁剪：算法简单；,扫描转换到画布-位块拷贝：算法简单，但耗时耗内存。常用于字符显示。,设备级显示算法，考虑运算方式、时间、次数等细节。,扫描转换直线段,直线的绘制要求：,1.直线要直；,2.直线上的点要准确，即无不定向性和断裂情况；,3.直线的亮度、色泽要均匀；,4.画线的速度要快；,5.要求不同直线可具有不同的色泽、亮度、线型等。,扫描转换直线段,直线基础,我们知道：直线的笛卡儿斜率截距方程为：y=mx+b,m-直线的斜率,b -直线于y轴的截距,给定线段的两个端点（x0,y0), (x1,y1)，可以计算斜率m,和截距b： m=(y1-y0)/(x1-x0),b=y1mx1= (x0y1-x1y0)/ (x1-x0),在x方向上，给定任意增量x，那么对应的y,的增量为y, 即y = mx,图形学直线的算法是以上面的直线方程、斜,率方程、截距方程和增量方程为基础,扫描转换直线段,扫描转换直线段,求与直线段充分接近的像素集,两点假设,直线段的宽度为1,直线段的斜率:,像素间均匀网格,整型坐标系,数值微分法（DDA-digital differential analyzer）,DDA算法是一种线段扫描转换算法，它是在,一个坐标轴上以单位间隔对线条取样，从而,确定另一个轴上最靠近线段路径的对应整数,值。,首先考虑斜率值m在（0，1）之间的直线。,扫描转换直线段,DDA（,digital differential analyzer）,算法,条件：,待扫描转换的直线段：,斜率：,直线方程：,直接求交算法：,划分区间x0,xn:,计算纵坐标：,取整：,批注：y=mx+b m=0.4 int取整,例：画直线段,x int(y+0.5) y+0.5,000,100.4+0.5,210.8+0.5,311.2+0.5,421.6+0.5,522.0+0.5,注：,网格点表示象素,扫描转换直线段,复杂度：乘法+加法+取整,DDA算法（增量算法）,复杂度：加法+取整,增量算法：在一个迭代算法中，如果每一步,的x、y值是用前一步的值加上一个增量来获,得，则称为增量算法。,DDA算法就是一个增量算法。,问题：,当,k,1时，会如何？,扫描转换直线段,中点画线算法,目标：消除DDA算法中的浮点运算,（,浮点数取整运算，不利于硬件实现； DDA算法，效率低）,条件：,同DDA算法,斜 率：,直线段的隐式方程（,(x0,y0)(x1,y1)两端点,）,F(x,y)=ax+by+c=0,式中 a=y,0,-y,1,b=x,1,-x,0,c=X,0,Y,1,-X,1,Y,0,扫描转换直线段,直线的正负划分性,直线上方的点：F(X，Y)0,直线下方的点：F(X，Y)0,扫描转换直线段,问题：判断距直线最近的下一个象素点,构造判别式：d=F(M)=F(Xp+1,Yp+0.5),由d0，d0可判定下一个象素，,P,P2,P1,要判定再下一个象素，分两种情形考虑：,1）若d0，取正右方象素P1，再下一个象素判定，由：d1=F(Xp+2,Yp+0.5)=a(Xp+2)+b(Yp+0.5)+c = d+a，,d的增量是a,2）若d0，取右上方象素P2，再下一个象素，,由：d2=F(Xp+2,Yp+1.5)=d+a+b,d的增量为a+b,P2,P,P1,扫描转换直线段,d的初始值,d,0,=F(X,0,+1,Y,0,+0.5)=F(X,0,Y,0,)+a+0.5,因(X,0,Y,0,)在直线上，F(X,0,，Y,0,)=0,所以，d,0,=a+0.5b,d的增量都是整数，只有初始值包含小数，可以用2d代替d, 2a改写成a+a。,算法中只有整数变量，不含乘除法，可用硬件实现。,扫描转换直线段,程序,Midpointline(x0,y0,x1,y1,color),int x0,y0,x1,y1,color;,int a,b,d1,d2,2,x,y;,a = y0-y1; b = x1 x0; d = 2 * a +b;,d1 = 2*a; d2 = 2*(a+b);,x = x0; y = y0;,PutPixel(x,y,color);,while (xx1), if (d0), x+; y+; d +=d2;,else x+; d +=d1;,PutPixel(x,y,color);,例：用中点画线法P0(0,0) P1(5,2),例：用中点画线法P0(0,0) P1(5,2),a=y0-y1=-2 b=x1-x0=5,d0=2a+b=1 d1=2a=-4 d2=2(a+b)=6,d3= 2a=-4 d4= 2(a+b)=6,d0=2(a+0.5b),若d0, 增量为2a,若d0，增量为2(ab),Xi yi d,0 0 1,1 0 -3 (1 -4),2 1 3 (-3 +6),3 1 -1 (3 -4),4 2 5 (-1 +6）,Bresenham画线算法,（构思巧妙，使得每次只需检,测误差项的符号就能决定直线上的下一个像素的位,置）,Bresenham算法是Bresenham提出的一种精确且有效的,光栅生成算法。,它用于显示线、圆和其它曲线的整数运算,它是目前最有效的线段生成算法,扫描转换直线段,过各行各列象素中心构造一组虚拟网格线。按直线从起点到终点的顺序计算直线与各垂直网格线的交点，然后根据误差项的符号确定该列象素中与此交点最近的象素。,设直线方程为：,，其中k=dy/dx。 因为直线的起始点在象素中心，所以误差项d的初值d00。,X下标每增加1，d的值相应递增直线的斜率值k，即ddk。一旦d1，就把它减去1，这样保证d在0、1之间。,当d0.5时，最接近于当前象素的右上方象素（ ）,而当d0.5时，更接近于右方象素（ ）。,为方便计算，令ed-0.5，,e的初值为-0.5，增量为k。,当e0时，取当前象素（xi，yi）的右上方象素（ ）；,而当e0时，更接近于右方象素（ ）。,可以改用整数以避免除法。由于算法中只用到误差项的符号，因此可作如下替换：,例：Line: P,0,(0, 0), P,1,(5,2) k=dy/dx=0.4,x y e,0 0 -0.5,1 0 -0.1,2 1 0.3,3 1 -0.3,4 2 0.1,5 2 -0.5 大于零，y加一，小于零，不变,void Bresenhamline (int x,0,int y,0,int x,1, int y,1,int color), int x, y, dx, dy;,float k, e;,dx = x,1,-x,0, dy = y,1,- y,0, k=dy/dx;,e=-0.5, x=x,0, y=y,0,;,for (i=0; i,dx; i+), drawpixel (x, y, color);,x=x+1，e=e+k;,if (e,0), y+, e=e-1;,最终，Bresenham算法也是每个象素，需一个整数算法，,其优点是可以用于其他二次曲线。,扫描转换圆弧,处理对象：圆心在原点的圆弧,假设圆的方程为：X,2,+ Y,2,= R,2,圆的八对称性,两种直接离散方法：,离散点:,离散角度:,开根，三角函数运算，计算量大，不可取。,方法1,X,2,+ Y,2,= R,2,Y = Sqrt(R,2,-X,2,),在一定范围内，每给定一,X值，可得一Y值。,当X取整数时，Y须取整。,缺点：浮点运算，开方，,取整，不均匀。,方法2:采用极坐标,x = Rcos,y = Rsin,dx=-Rsind,dy=Rcosd,x,n+1,=x,n,+dx,y,n+1,=y,n,+dy,x,n+1,= x,n,+dx= x,n,-Rsin d=x,n,-y,n,d,y,n+1,= y,n,+dy= y,n,+Rcosd=y,n,+ x,n,d,显然，确定x,y的初值及d值后，即可以增量方式获得圆周,上的坐标，然后取整可得象素坐标。但要采用浮点运算、乘,法运算、取整运算。,方法3：利用圆的对称性采用中点法（常,用方法）只须讨论1/8圆，一般采用第二个8,分圆,扫描转换圆弧,圆弧的正负划分性,圆弧外的点：F(X，Y)0,圆弧内的点：F(X，Y)0,扫描转换圆弧,生成圆弧的中点算法,考虑对象：,第二个八分圆，,第一象限的八分之一圆弧,P,P1,P2,扫描转换圆弧,问题：,与直线情形类似,圆弧的隐函数：,F(X,Y)=X,2,+Y,2,-R,2,=0,中点 M=(Xp+1,Yp-0.5),当F(M)0时，M在圆内，说明P1距离圆弧更,近，取P1；,当F(M)=0时，M在圆上；,当F(M)0时，M在圆外，说明P,2,距离圆弧更近，取P2。,P2,P1,P,构造判别式,d=F(M)=F(Xp+1,Yp-0.5)=(Xp+1),2,+(Yp-0.5),2,-R,2,1）,若d0，取P1，再下一个象素的判别式为： d1=F(Xp+2,Yp-0.5)=d+2Xp+3，,沿正右方向，d的增量为,2Xp+3,；,2）,若d0，取P2，再下一个象素的判别式为：,d2=F(Xp+2,Yp-1.5)=d+(2Xp+3)+(-2Yp+2),沿右下方向，d的增量为,2(Xp-Yp)+5,d的初始值(在第一个象素(0,R)处),d0=F(1, R-0.5)=1.25-R,算法中有浮点数，用e=d-0.25代替,扫描转换圆弧,所以：初始化运算d0 = 1.25 R 对应于 e 0= 1- R,判别式 d 0 对应于 e -0.25,又因为：e的初值e0为整数，运算过程中的分量也为整数，,故e始终为整数,所以： e -0.25 等价于 e 0,算法步骤：,1.输入圆的半径R。,2.计算初始值d=1.25-R、x=0、y=R。,3.绘制点(x,y)及其在八分圆中的另外七个对称,点。,4.判断d的符号。若d0，则先将d更新为,d+2x+3，再将(x,y)更新为(x+1,y)；否则先将d更,新为d+2(x-y)+5，再将(x,y)更新为(x+1,y-1)。,5.当xy时，重复步骤3和4。否则结束。,程序如下（,完全用整数实现,）：,MidpointCircle(r,color),Int r, color;,int x,y,d;,x = 0; y = r; d = 1-r;,putpixcel(x,y,color);,while( x y), if (d 0), d += 2*x+3; x+; ,else, d += 2*(x-y)+5;,x+ ; y-; ,putpixcel(x,y,color);,为了进一步提高算法的效率，可以将上面的,算法中的浮点数改写成整数，将乘法运算改,成加法运算，即仅用整数实现中点画圆法。,使用e=d-0.25代替d，(d = 1.25 R) e0=1-R,椭圆的扫描转换,与圆弧中点算法类似：确定一个象素后，接,着在两个候选象素的中点计算一个递推式的,值，由递推式的符号确定更近的点,椭圆的中点画法,与圆弧中点算法类似：确定一个象素后，接着在两个候选象素的中点计算一个判别式的值，由判别式的符号确定更近的点,先讨论椭圆弧的上部分,(Xp，Yp)中点(Xp+1,Yp-0.5),d1=F(Xp+1,Yp-0.5)= b,2(,Xp+1),2,+a,2(,Yp-0.5),2,-a,2,b,2,根据d1的符号来决定下一像素是取正右方的那个，还是右上方的那个。,若d10，中点在椭圆内，取正右方象素，判别式更新为：,d1=F(Xp+2,Yp-0.5)=d1+b,2,(2Xp+3),d1的增量为b,2,(2Xp+3),当d10，中点在椭圆外，取右下方象素，更新判别式：,d1=F(Xp+2,Yp-1.5)=d1+b,2,(2Xp+3)+a,2,(-2Yp+2),d1的增量为b,2,(2Xp+3)+a,2,(-2Yp+2),d1的初始条件：,椭圆弧起点为(0，b)，第一个中点为,(1,b-0.5),初始判别式,：d1,0,=F(1,b-0.5)=b*b+a*a(-b+0.25),转入下一部分，下一象素可能是一正下方或右下方，此时判别式要初始化。,d2 = F(Xp+0.5,Yp-1) =,b,2(,Xp+0.5),2,+a,2(,Yp-1),2,-a,2,b,2,若d2=0,则,d2 =,F(Xp+0.5,Yp-2) =,d2 +,a,2,(-2Yp+3),下半部分弧的终止条件为 y = 0,椭圆算法步骤：,1、d1的初始条件：椭圆弧起点为(0，b)；,2、第一个中点为(1,b-0.5),初始递推式：d1=F(1,b-0.5)=b*b+a*a(-b+0.25),3、进入上半部分，下一象素可能是正右方或右下方，此时递推式,要初始化。,d1 = F(Xp+0.5,Yp-1) = b,2,(Xp+0.5),2,+a,2,(Yp-1),2,-a,2,b,2,a、若d1=0,取右下方像素，则,d1 = F(Xp+2,Yp-1.5)=d2+b,2,(2Xp+3)+a,2,(-2Yp+2),4、直到a,2,Ypb,2,Xp,5、进入下半部分,6、下半部分弧的终止条件为y = 0,程序：MidpointEllipe(a,b, color),int a,b,color;, int x,y; float d1,d2;,x = 0; y = b;,d1 = b*b +a*a*(-b+0.25);,putpixel(x,y,color);,while( b*b*(x+1) a*a*(y-0.5), if (d10), if (d2 ymin;y ymax;y+),for(x = rect-xmin;x xmax;x+),PutPixel(x,y,color);,/*end of FillRectangle()*/,3.2.1扫描转换矩形（2/ 2）,问题：,矩形是简单的多边形，那么为什么要单独处理矩形？,比一般多边形可简化计算。,应用非常多，窗口系统。,共享边界如何处理？,原则：左闭右开，下闭上开,属于谁？,3.2.2 扫描转换多边形,多边形的表示方法,顶点表示,点阵表示,扫描转换多边形：将顶点表示形式转换成点阵表示形式,三种方法：,逐点判断法；扫描线算法；边缘填充法,。,void FillPolygonPbyP(Polygon *P,int polygonColor), int x,y;,for(y = ymin;y = ymax;y+),for(x = xmin;x = xmax;x+),if(IsInside(P,x,y),PutPixel(x,y,polygonColor);,else,PutPixel(x,y,backgroundColor);,/*end of FillPolygonPbyP()*/,#define MAX 100,Typedef struct int PolygonNum; / 多边形顶点个数,Point vertexcesMAX /多边形顶点数组, Polygon / 多边形结构,逐点判断法,逐点判断法,逐个判断绘图窗口内的像素：,如何判断点在多边形的内外关系？,1）射线法：,2）累计角度法,3）编码法；,逐点判断法,1）射线法,步骤：,从待判别点v发出射线,求交点个数k,K的奇偶性决定了点与多边形的内外关系,奇异情况处理,逐点判断法,2）累计角度法,步骤,从v点向多边形P顶点发出射线，形成,有向,角,计算有相交的和，得出结论,预处理,离散计算方法：编码方法,3）编码方法：,累计角度方法的离散方法,Step:,a.预处理，测试点在边上否？,b.V为中点作局部坐标系,对象限按逆,时针（或顺时针）编码；,c.顶点编码I,pi,，,d.边编码。,P,i,P,i+1,: P,i,P,i+1,=I,p,i+1,-I,p,i,e.计算 P,i,P,i+1,（其中P,n,P,n+1,= P,n,P,0,)：,若 为0, V在P外；若 为+/-4，V 在P内；,逐点判断法程序简单，,速度太慢，效率低。,P,0,P,1,P,2,v,逐点判断法,扫描线算法,扫描线算法,目标：利用相邻像素之间的连贯性，提高算法效率,处理对象：非自交多边形 （边与边之间除了顶点外无其它交点）,扫描线算法,基本原理,一条扫描线与多边形的边有偶数个交点,步骤,(对于每一条扫描线):,(1)求交点,(2)交点排序,(3)交点配对，填充区段。,扫描转换多边形(7/ 19),边的连贯性,第一类交点：新出现的边与扫描线的交点,第二类交点：位于同一条边上的后继交点,扫描转换多边形(8/ 19),交点的取整规则,要求：使生成的像素全部位于多边形之内,用于线画图元扫描转换的四舍五入原则导致部分像素位于多边形之外，从而不可用,假定非水平变与扫描线y=e,相交，交点的横坐标为x,规则如下,扫描线算法,规则1：,X为小数，即交点落于扫描线上两个相邻像素之间,(a)交点位于左边之上，向右取整,(b)交点位于右边之上，向左取整,规则,2,：,边界上象素的取舍问题，避免填充扩大化。,解决方法：,边界象素：规定落在右上边界的象素不予填充。,具体实现时，只要对扫描线与多边形的相交区间左闭右开,扫描线算法,规则3：,扫描线与多边形的顶点相交时，交点的取舍，保证交点正确配对。,解决方法：,检查两相邻边在扫描线的哪一侧。,只要检查顶点的两条边的另外两个端点的Y值，两个Y值中大于交点Y值的个数是0，1，2，来决定取0，1，2个交点。,扫描线算法,扫描线算法,1）,活性边：与当前扫描线相交的边。按交点x的增量顺序存放在一个链表中；该链表称作,活性,边表（AEL),。,算法所涉及的数据结构：,AEL,与,ET,的结点信息（p75）：,Y,max,: 所交边的最高扫描线号,X：当前扫描线与边的交点的x坐标,X：边的斜率的倒数,Nextage: 下一条边的指针,typedef struct int ymax;,float x,deltax;,Edge *nextEdge;,Edge;,扫描线算法,2）边的分类表,（ET）,按照边的下端点y坐标对非水平边进行分类的指针数组,下端点y坐标值等于i的边属于第i类,typedef struct int ymax;,float x,deltax;,Edge *nextEdge;,Edge;,边的分类表的作用是避免盲目求交。,当处理一条扫描线时，为了求出它,与多边形边的所有交点，必须将它,与所有的边进行求交测试。而实际,上只有某几条边与该扫描线有交点。,边的分类表正是用来排除不必要的,求求交测试的。,扫描线算法,1、建立ET；,2、将扫描线纵坐标y的初值置为ET中非空元素的最小序号，如在上图中，y=1；,3、置AEL为空；,4、执行下列步骤直至ET和AEL都为空,4.1、如ET中的第y类非空，则将其中的所有边取出并插入AEL中；,4.2、如果有新边插入AEL，则对AEL中各边排序；,4.3、对AEL中的边两两配对，（1和2为一对，3和4为一对，,），将每对边中x坐标按规则取整，获得有效的填充区段，再填充,4.4、将当前扫描线纵坐标y值递值1；,4.5、将AEL中满足y=ymax边删去（因为每条边被看作下闭上开的）；,4.6、对AEL中剩下的每一条边的x递增deltax，即x = x+deltax,边的连贯性,：某条边与当前扫描线相交，也可能与,下一条扫描线相交；,扫描线的连贯性,：当前扫描线与各边的交点顺序与,下一条扫描线与各边的交点顺序可能相同或类似；,区间连贯性,：同一区间上的像素取同一颜色属性,几个概念,边缘填充算法,求余运算,：假定A为一个正整数，则M的余定义为,A M, 记为 。计算机中取A为n位能表示的最大整数。即，,A=0xFFFFFFFF,由来,：光栅图形中，如果某区域已着上值为M的颜色值做偶数次求余运算，该区域颜色不变；而做奇数次求余运算，则该区域颜色变为值为 的颜色。这一规律应用于多边形扫描转换，就为边缘填充算法。,求余运算可用异或显示模式实现。,算法基本思想,：对于每条扫描线和每条多边形边的交点，将该扫描线上交点右方的所有象素取余。,算法1（以扫描线为中心的边缘填充算法）,1、将当前扫描线上的,所有象素着上 颜色；,2、求余：,for(i = 0;i = m; i+),在当前扫描线上，,从横坐标为Xi的交点,向右求余；,算法2（以边为中心的边缘填充算法）,1、将绘图窗口的背景色置为 ；,2、对多边形的每一条非水平边做：,从该边上的每个象素开始向右求余；,边缘填充算法,适合用于具有帧缓存的图形系统。处理后，按扫描线顺序读出帧缓存的内容，送入显示设备。,优点：算法简单,缺点：对于复杂图形，每一象素可能被访问多次，输入/输出的量比扫描线算法大得多。,3.2.3 区域填充,区域：,点阵表示的图形，像素集合,表示方法：,内点表示、边界表示,内点表示,枚举处区域内部的所有像素,内部的所有像素着同一个颜色,边界像素着与内部像素不同的颜色,边界表示,枚举出边界上所有的像素,边界上的所有像素着同一颜色,内部像素着与边界像素不同的颜色,区域填充(,种子填充法),区域填充 对区域重新着色的过程,将指定的颜色从,种子点,扩展到整个区域的过程,区域填充算法要求区域是连通的,连通性,4连通、8连通,4连通：,8连通,例子：PaintBrush,例子：PhotoShop,区域填充(,种子填充法),四连通区域指的是从区域内每一个象素，可以通过四个方向，即上、下、左、右移动的组合，在不越出区域的前提下，到达区域内的任意象素。,八连通区域指的是从区域内每一个象素，可以通过左、右、上、下、左上、右上、左下、右下八个方向的移动的组合来到达区域内的任意象素。,4连通与8连通区域的区别,连通性： 4连通可看作8连通区域，但对边界有要求,对边界的要求,区域填充(,种子填充法,),1）递归填充算法,内点表示的4连通区域,void FloodFill4(int x,int y,int oldColor,int newColor), if(GetPixel(x,y) = oldColor), PutPixel(x,y,newColor);,FloodFill4(x,y+1,oldColor,newColor);,FloodFill4(x,y-1,oldColor,newColor);,FloodFill4(x-1,y,oldColor,newColor);,FloodFill4(x+1,y,oldColor,newColor);,/*end of FloodFill4()*/,取(x,y)为种子点,区域填充(,种子填充法),区域填充(,种子填充法),边界表示的4连通区域,void BoundaryFill4(int x,int y,int oldColor,int newColor),int color;,color = GetPixel(x,y);,if(,color != boundaryColor) & (color != newColor),),PutPixel(x,y,newColor);,BoundaryFill4(x,y+1,oldColor,newColor);,BoundaryFill4(x,y-1,oldColor,newColor);,BoundaryFill4(x-1,y,oldColor,newColor);,BoundaryFill4(x+1,y,oldColor,newColor);,/*end of BoundaryFill4()*/,问题：,内点表示与边界表示的8连通区域？,缺点,：,(1) 有些象素会入栈多次，降低算法效率；栈结构占空间。,(2) 递归执行，算法简单，但效率不高，区域内每一象素都引起一次递归，进/出栈，费时费内存。,改进算法，减少递归次数，提高效率。,方法之一使用扫描线填充算法；,区域填充(,种子填充法),区域填充（扫描线算法),扫描线算法,目标：减少递归层次,适用于内点表示的4连通区域,基本过程：,当给定种子点时，首先填充种子点所在的扫描线上的位于给定区域的一个区段，然后确定与这一区段相通的上下两条扫描线上位于给定区域内的区段，并依次保存下来。反复这个过程，直到填充结束。,1、填充并确定种子区段 ；,2、初始化 ：将种子区段压入堆栈；,3、出栈：如果堆栈为空，则算法结束；否则取栈顶元素,（y,xLeft,xRight），以纵坐标为 y的扫描线为当前,扫描线，xLeft,xRight为搜索区间 ；,4、填充并确定新的区段 。,算法步骤,区域填充（扫描线算法）,区域填充（扫描线算法),像素中的序号标指它所在区段位于堆栈中的位置,3.2.4 字符的表示与输出,点阵字符,矢量字符,自学！,思考题,如何修改扫描线算法，使它能处理边自交的多边形？,3.3.1 混淆现象,3.3.2 反混淆方法,非加权区域采样,加权区域采样,3.3反混淆方法,3.3.1 混淆现象,混淆,：用离散量(像素)表示连续的量(图形)而引起的失真，叫混淆或叫,走样,(aliasing)。,光栅图形的混淆现象,阶梯状边界；,图形细节失真；,狭小图形遗失：动画序列中时隐时现，产生闪烁。,混淆现象（1/3）,不光滑(阶梯状）的图形边界,例子：PaintBrush,混淆现象（2/3）,图形细节失真,混淆现象（3/3）,狭小图形的遗失与动态图形的闪烁,反混淆方法,什么是反混淆,在图形显示过程中，用于减少或消除混淆现象的方法,1）提高分辨率方法,2）非加权区域采样,3）加权区域采样,反混淆方法,提高分辨率的反混淆方法,方法简单，但代价非常大。,显示器的水平、竖直分辩率各提高一倍，则显示器的点距减少一倍，,帧缓存容量则增加到原来的4倍，而扫描转换同样大小的图元却要花4倍,时间。,非加权区域采样方法,方法由来,两点假设,1、象素是数学上抽象的点，它的面积为0，它的亮度由覆盖该点的图形的亮度所决定；,2、直线段是数学上抽象直线段，它的宽度为0。,现实,像素的面积不为0；,直线段的宽度至少为1个像素；,假设与现实的矛盾是导致混淆出现的原因之一,非加权区域采样方法,解决方法：改变直线段模型，由此产生算法,方法步骤,：,1、将直线段看作具有一定宽度的狭长矩形；,2、当直线段与某象素有交时，求出两者相交区域的面积；,3、根据相交区域的面积，确定该象素的亮度值,方法性质：,非加权区域采样方法,1）直线段对一个像素亮度的贡献与两者相交区域的面积成,正比，从而和像素中心点距直线段的距离成反比(因为像,素中心点距直线段距离越远，相交区域的面积越小）；,2） 当直线段和某个像素不相交时，它对该像素的亮度无影响；,3） 相同面积的相交区域对像素的亮度贡献相同，而与这个相交,区域落在像素内位置无关。,关键：如何计算这个面积？,非加权区域采样方法,- 计算相交区域的面积,D,D.m,面积=(D*D)/2m,D,- - - - - -,m,面积=D m/2,像素实际显示的灰度值 = 所得面积 * 该像素的最大灰度值,面积=1-D*D/m,反混淆方法,求相交区域的近似面积的离散计算方法,1、将屏幕象素分割成n个更小的子象素；,2、计算中心点落在直线段内的子象素的个数，记为k，,3、k/n为线段与象素相交区域面积的近似值,目的：简化计算,n = 16, k = 3,近似面积 = 3/16,加权区域采样方法,改进,非加权区域采样方法的,第3条性质,：,相交区域对象素亮度的贡献,依赖于该区域与象素中心的距离,加权区域采样方法,权函数W(x,y),以象素A的中心为原点建立二维坐标系,w(x,y)反应了微面积元dA对整个象素亮度的贡献大小 ，与d成反比。,权性（为讨论方便而设）,位于(x,y)处的微面积元dA对像素的亮度的贡献为w(x,y) dA,加权区域采样方法,相交区域 对该象素的亮度贡献,特例： 时，,加权区域采样方法退化为,非加权区域采样方法,加权区域采样方法,实现步骤,1求直线段与象素的相交区域 ；,2计算的值 ；,3上面所得到的值介于0、1之间，用它乘象素的最大灰度值，即设该象素的显示灰度。,问题：计算量大,加权区域采样方法,离散计算方法,1将屏幕象素均匀分割成m个子象素 ，则每个子象素的面积为 ，计算每个子象素对原象素亮度的贡献，记为,将 保存在一张加权表中;,2求出所有中心落于直线段内的子象素，记为,3计算所有这些子象素对原象素亮度贡献之和,该值乘以象素的最大灰度值即为象素的显示灰度值.,加权表的取法,上机作业,1. 实现一个反混淆的算法。,