基本图形生成算法.ppt

《基本图形生成算法.ppt》由会员分享，可在线阅读，更多相关《基本图形生成算法.ppt（142页珍藏版）》请在三一办公上搜索。

1、计算机图形学,第四章 直线、圆、椭圆生成算法,图形的扫描转换（光栅化）：确定一个像素集合，用于显示一个图形的过程。步骤如下：1、确定有关像素2、用图形的颜色或其它属性，对像素进行写操作。对一维图形，不考虑线宽，则用一个像素宽的直线来显示图形。二维图形的光栅化，即区域的填充：确定像素集，填色或图案。任何图形的光栅化，必须显示在一个窗口内，否则不予显示。即确定一个图形的哪些部分在窗口内，哪些在窗口外，即裁剪。,计算机图形学,图形显示前需要：扫描转换+裁剪裁剪-扫描转换：最常用，节约计算时间。扫描转换-裁剪：算法简单；,计算机图形学,本章内容,扫描转换直线段 DDA算法 中点画线法 Bresenha

2、m画线算法圆弧、椭圆弧扫描转换 中点算法,计算机图形学,直线段的扫描转换算法,直线的扫描转换:确定最佳逼近于该直线的一组象素，并且按扫描线顺序，对这些象素进行写操作。三个常用算法：数值微分法（DDA）中点画线法Bresenham算法。,计算机图形学,数值微分法（）,假定直线的起点、终点分别为：（x0,y0),(x1,y1)，且都为整数。,(X i+1,Yi+k),(X i,Int(Yi+0.5),(X i,Yi),栅格交点表示象素点位置,。,。,。,。,计算机图形学,数值微分(DDA)法,基本思想已知过端点P0(x0,y0),P1(x1,y1)的直线段Ly=kx+b直线斜率为这种方法直观，但效

3、率太低，因为每一步需要一次浮点乘法和一次舍入运算。,计算机图形学,数值微分(DDA)法,计算yi+1=kxi+1+b=kxi+b+kx=yi+kx 当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)法,void DDALine(int x0,int y0,int x

4、1,int y1,int color)int x；float dx,dy,y,k;dx,=x1-x0,dy=y1-y0;k=dy/dx,y=y0;for(x=x0;xx1,x+)drawpixel(x,int(y+0.5),color);y=y+k;,计算机图形学,数值微分(DDA)法,例：画直线段P0(0,0)-P1(5,2)x int(y+0.5)y+0.5000+0.5100.4+0.5210.8+0.5311.2+0.5421.6+0.5522.0+0.5,计算机图形学,数值微分(DDA)法,缺点：在此算法中，y、k必须是float，且每一步都必须对y进行舍入取整，不利于硬件实现。,计

5、算机图形学,中点画线法,原理：,假定直线斜率0K1，且已确定点亮象素点P（Xp,Yp）,则下一个与直线最接近的像素只能是P1点或P2点。设M为中点，Q为交点现需确定下一个点亮的象素。,计算机图形学,中点画线法,当M在Q的下方-P2离直线更近更近-取P2。M在Q的上方-P1离直线更近更近-取P1M与Q重合，P1、P2任取一点。问题：如何判断M与Q点的关系？,计算机图形学,中点画线法,假设直线方程为：ax+by+c=0其中a=y0-y1,b=x1-x0,c=x0y1-x1y0由常识知：欲判断M点是在Q点上方还是在Q点下方，只需把M代入F(x,y),并检查它的符号。,计算机图形学,中点画线法,构造判

6、别式：d=F(M)=F(xp+1,yp+0.5)=a(xp+1)+b(yp+0.5)+c当d0，M在直线(Q点)上方，取右方P1；当d=0，选P1或P2均可，约定取P1；能否采用增量算法呢？,计算机图形学,中点画线法,若d0-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；增量为a,计算机图形学,中点画线法,若dM在直线下方-取P2;此时再下一个象素的判别式为 d2=F(xp+2,yp+1.5)=a(xp+2)+b(yp+1.5)+c=a(xp+1)+b(yp+0.

7、5)+c+a+b=d+a+b；增量为ab,计算机图形学,中点画线法,画线从(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来摆脱小数，提高效率。,计算机图形学,中点画线法,void Midpoint Line(int x0,int y0,int x1,int y1,int color)int a,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;dra

8、wpixel(x,y,color);while(xx1)if(d0)x+;y+;d+=d2;else x+;d+=d1;drawpixel(x,y,color);/*while*/*mid PointLine*/,计算机图形学,中点画线法,例：用中点画线法P0(0,0)P1(5,2)a=y0-y1=-2 b=x1-x0=5d0=2a+b=1 d1=2a=-4 d2=2(a+b)=6ixiyid1001210-33213431-15425,计算机图形学,Bresenham画线算法,在直线生成的算法中Bresenham算法是最有效的算法之一。令 k=y/x，就0k1的情况来说明Bresenham算

9、法。由DDA算法可知：yi+1=yi+k(1)由于k不一定是整数，由此式求出的yi也不一定是整数，因此要用坐标为（xi,yir）的象素来表示直线上的点，其中yir表示最靠近yi的整数。,计算机图形学,Bresenham画线算法,D=d+k k=y/x令d的值始终在0,1之间，当d=1就把它减掉，当d0.5的时候就选择(x+1,y+1)否则取下个像素点为(x+1,y),计算机图形学,程序如下：BresenhamLine(x0,y0,x1,y1,color)int x0,y0,x1,y1,color;int x,y,dx,dy;float k,e;int e;dx=x1-x0;dy=y1-y0;k

10、=dy/dx;e=-0.5;x=x0;y=y0;e=-dx;for(i=0;i=0)y+;e=e-1;/;e=e-2*dx;,Bresenham画线算法,计算机图形学,圆的扫描转换算法,下面仅以圆心在原点、半径R为整数的圆为例，讨论圆的生成算法。假设圆的方程为：X2+Y2=R2,计算机图形学,圆弧扫描算法,X2+Y2=R2Y=Sqrt(R2-X2)在一定范围内，每给定一X值，可得一Y值。当X取整数时，Y须取整。缺点：浮点运算，开方，取整，不均匀。,计算机图形学,角度DDA法,x=x0+Rcos y=y0+Rsindx=-Rsinddy=Rcosdxn+1=x n+dxy n+1=y n+dyx

11、n+1=x n+dx=x n-Rsind=x n-(y n-y 0)dy n+1=y n+dy=y n+Rcosd=y n+(x n-x 0)d显然，确定x,y的初值及d值后，即可以增量方式获得圆周上的坐标，然后取整可得象素坐标。但要采用浮点运算、乘法运算、取整运算。,计算机图形学,中点画圆法,利用圆的对称性，只须讨论1/8圆。第二个8分圆P为当前点亮象素，那么，下一个点亮的象素可能是P1（Xp+1，Yp）或P2（Xp+1，Yp+1)。,M,P1,P2,P（Xp，Yp）,计算机图形学,中点画圆法,构造函数：F（X，Y）=X2+Y2-R2；则 F（X，Y）=0（X，Y）在圆上；F（X，Y）0（X

12、，Y）在圆外。设M为P1、P2间的中点，M=(Xp+1,Yp-0.5),M,P1,P2,计算机图形学,中点画圆法,有如下结论：F（M）M在圆内-取P1 F（M）=0-M在圆外-取P2为此，可采用如下判别式：,M,P1,P2,计算机图形学,中点画圆法,d=F(M)=F(xp+1,yp-0.5)=(xp+1)2+(yp-0.5)2-R2 若d0,则P1 为下一个象素，那么再下一个象素的判别式为：d1=F(xp+2,yp-0.5)=(xp+2)2+(yp-0.5)2-R2=d+2xp+3 即d 的增量为 2xp+3.,M,P1,P2,计算机图形学,中点画圆法,若d=0,则P2 为下一个象素，那么再下

13、一个象素的判别式为：d1=F(xp+2,yp-1.5)=(xp+2)2+(yp-1.5)2-R2=d+（2xp+3）+（-2 yp+2）即d 的增量为 2(xp-yp)+5.d的初值:d0=F(1,R-0.5)=1+(R-0.5)2-R2=1.25-R,M,P1,P2,计算机图形学,中点画圆法,MidpointCircle(int r,int color)int x,y;float d;x=0;y=r;d=1.25-r;drawpixel(x,y,color);while(xy)if(d0)d+=2*x+3;x+elsed+=2*(x-y)+5;x+;y-;,计算机图形学,中点画圆法,为了进一

14、步提高算法的效率，可以将上面的算法中的浮点数改写成整数，将乘法运算改成加法运算，即仅用整数实现中点画圆法。使用e=d-0.25代替de0=1-R,计算机图形学,中点画圆法,上述算法能否再改进呢？注意到d的增量是x,y的线性函数，每当x递增1，则d的增量递增x=2每当y递减1，则d的增量递增y=2x初始值=3；y初始值=-2r+2见173页算法。,计算机图形学,Bresenham画圆算法,如果已经知道圆弧上的一点(x,y)，下一像素的选取有三种可能：正右方像素，右下角像素和正下方像素，分别用H,D和V表示，如下图所示。这三个像素的偏差的平方为：,计算机图形学,Bresenham画圆算法,计算机图

15、形学,Bresenham画圆算法,计算机图形学,生成圆弧的正负法,原理：,设圆的方程为F(x,y)=X2+Y2-R2=0;假设求得Pi的坐标为(xi,yi)；则当Pi在圆内时-F(xi,yi)向右-向圆外Pi在圆外时-F(xi,yi)0-向下-向圆内,计算机图形学,生成圆弧的正负法,即求得Pi点后选择下一个象素点Pi+1的规则为：当F(xi,yi)0 取xi+1=xi+1，yi+1=yi;当F(xi,yi)0 取xi+1=xi，yi+1=yi-1;这样用于表示圆弧的点均在圆弧附近，且使F(xi,yi)时正时负，故称正负法。快速计算的关键是F(xi,yi)的计算，能否采用增量算法？,计算机图形学

16、,生成圆弧的正负法,若F(xi,yi)已知，计算F(xi+1,yi+1)可分两种情况：1、F(xi,yi)0-xi+1=xi+1，yi+1=yi;-F(xi+1,yi+1)=(xi+1)2+(yi+1)2-R2-=(xi+1)2+yi2-R2=F(xi,yi)+2xi+12、F(xi,yi)0-xi+1=xi，yi+1=yi-1;-F(xi+1,yi+1)=(xi+1)2+(yi+1)2-R2-=xi2+(yi 1)2-R2=F(xi,yi)-2yi+13、初始值：略,计算机图形学,生成圆弧的多边形逼近法,圆的内接正多边形迫近法圆的等面积正多边形迫近法,计算机图形学,圆的内接正多边形逼近法,思

17、想：当一个正多边形的边数足够多时，该多边形可以和圆无限接近。即因此，在允许的误差范围内，可以用正多边形代替圆。设内接正n边形的顶点为Pi(xi,yi),Pi的幅角为i,每一条边对应的圆心角为a，则有xi=Rcos i yi=Rsin i,计算机图形学,圆的内接正多边形逼近法,内接正n边形代替圆计算多边形各顶点的递推公式 Xi+1 Rcos(a+i)=Yi+1 Rsin(a+i)Xi+1 cos a-sin a Xi=Yi+1 sin a cosa Yi因为:a是常数，sin a，cosa只在开始时计算一次所以，一个顶点只需4次乘法，共4n次乘法，外加直线段的中点算法的计算量。,计算机图形学,圆

18、的等面积正多边形逼近法,当用内接正多边形逼近圆时，其面积要小于圆的面积；而当用圆的外切正多边形逼近圆时，其面积则要大于圆的面积。为了使近似代替圆的正多边形和圆之间在面积上相等，只有使该正多边形和圆弧相交，称之为圆的等面积正多边形。,计算机图形学,圆的等面积正多边形逼近法,步骤：求多边形径长，从而求所有顶点坐标值由逼近误差值，确定边所对应的圆心角,计算机图形学,椭圆的扫描转换,F(x,y)=b2x2+a2y2-a2b2=0椭圆的对称性，只考虑第一象限椭圆弧生成，分上下两部分，以切线斜率为-1的点作为分界点。椭圆上一点处的法向：N(x,y)=(F)x i+(F)y j=2b2 x i+2a2 y

19、j,计算机图形学,在上半部分,法向量的y分量大在下半部分,法向量的x分量大,上半部分,下半部分,法向量两分量相等,M1,M2,在当前中点处，法向量（2b2(Xp+1)，2a2(Yp-0.5)的y分量比x分量大,即：b2(Xp+1)a2(Yp-0.5),而在下一中点，不等式改变方向，则说明椭圆弧从上部分转入下部分,计算机图形学,椭圆的中点画法,与圆弧中点算法类似：确定一个象素后，接着在两个候选象素的中点计算一个判别式的值，由判别式的符号确定更近的点先讨论椭圆弧的上部分设(Xp，Yp)已确定，则下一待选像素的中点是(Xp+1,Yp-0.5)d1=F(Xp+1,Yp-0.5)=b2(Xp+1)2+a

20、2(Yp-0.5)2-a2b2,计算机图形学,根据d1的符号来决定下一像素是取正右方的那个，还是右上方的那个。若d10，中点在椭圆内，取正右方象素，判别式更新为：d1=F(Xp+2,Yp-0.5)=d1+b2(2Xp+3)d1的增量为b2(2Xp+3)当d10，中点在椭圆外，取右下方象素，更新判别式：d1=F(Xp+2,Yp-1.5)=d1+b2(2Xp+3)+a2(-2Yp+2)d1的增量为b2(2Xp+3)+a2(-2Yp+2),计算机图形学,d1的初始条件：椭圆弧起点为(0，b)；第一个中点为(1,b-0.5)初始判别式：d10=F(1,b-0.5)=b*b+a*a(-b+0.25)转入

21、下一部分，下一象素可能是正下方或右下方，此时判别式要初始化。d2=F(Xp+0.5,Yp-1)=b2(Xp+0.5)2+a2(Yp-1)2-a2b2 若d2=0,取正下方像素，则d2=F(Xp+0.5,Yp-2)=d2+a2(-2Yp+3)下半部分弧的终止条件为 y=0,计算机图形学,区域填充算法,区域指已经表示成点阵形式的填充图形，它是象素的集合。区域填充指先将区域的一点赋予指定的颜色，然后将该颜色扩展到整个区域的过程。区域填充算法要求区域是连通的,计算机图形学,区域填充,表示方法：内点表示、边界表示内点表示枚举处区域内部的所有像素内部的所有像素着同一个颜色边界像素着与内部像素不同的颜色边界

22、表示枚举出边界上所有的像素边界上的所有像素着同一颜色内部像素着与边界像素不同的颜色,计算机图形学,边界填充算法,2.3 多边形的扫描转换与区域填充,多边形有两种重要的表示方法：顶点表示和点阵表示。多边形的扫描转换:把多边形的顶点表示转换为点阵表示。区域可采用内点表示和边界表示两种表示形式。区域填充:指先将区域的一点赋予指定的颜色，然后将该颜色扩展到整个区域的过程。,多边形类型,多边形分为凸多边形、凹多边形、含内环的多边形。,2.3.1多边形的扫描转换,扫描线算法基本思想：按扫描线顺序，计算扫描线与多边形的相交区间，再用要求的颜色显示这些区间的象素，即完成填充工作。对于一条扫描线填充过程可以分为

23、四个步骤：（1）求交（2）排序（3）配对（4）填色,一个多边形与若干扫描线,数据结构,活性边表(AET)：把与当前扫描线相交的边称为活性边，并把它们按与扫描线交点x坐标递增的顺序存放在一个链表中结点内容 x：当前扫描线与边的交点坐标x：从当前扫描线到下一条扫描线间x的增量ymax：该边所交的最高扫描线号ymax,新边表（NET）,存放在该扫描线第一次出现的边。若某边的较低端点为ymin，则该边就放在扫描线ymin的新边表中上图所示各条扫描线的新边表NET,假定当前扫描线与多边形某一条边的交点的x坐标为x，则下一条扫描线与该边的交点不要重计算，只要加一个增量x。设该边的直线方程为：ax+by+c

24、=0；若yyi，x=x i；则当y=y i+1时，其中 为常数,交点问题,扫描线与多边形的顶点或边界相交时，必须正确的交点的取舍。只需检查顶点的两条边的另外两个端点的y值。按这两个y值中大于交点y值的个数是0,1,2来决定。,算法过程,void polyfill(polygon,color)int color;多边形 polygon;for(各条扫描线i)初始化新边表头指针NET i；把y min=i 的边放进边表NET i;y=最低扫描线号；初始化活性边表AET为空；for(各条扫描线i),把新边表NET i 中的边结点用插入排序法插入AET表，使之按x坐标递增顺序排列；遍历AET表，把配对

25、交点区间(左闭右开)上的象素(x,y)，用drawpixel(x,y,color)改写象素颜色值；遍历AET表，把y max=i 的结点从AET表中删除，并把y max i 结点的x值递增x；若允许多边形的边自相交，则用冒泡排序法对AET表重新排序；/*polyfill*/,计算机图形学,边界标志算法,用软件实现时，扫描线算法与边界标志算法的执行速度几乎相同，但由于边界标志算法不必建立维护边表以及对它进行排序，所以边界标志算法更适合硬件实现，这时它的执行速度比有序边表算法快一至两个数量级。,计算机图形学,区域填充,区域填充要求区域是连通的连通性 4连通、8连通4连通：8连通,计算机图形学,区域

26、填充,4连通与8连通区域的区别连通性：4连通可看作8连通区域，但对边界有要求对边界的要求,计算机图形学,计算机图形学,A：适合于内点表示区域的填充算法设G为一内点表示的区域，(x,y)为区域内一点，old_color为G的原色。现取(x,y)为种子点对区域G进行填充：即先置像素(x,y)的颜色为new_color，然后逐步将整个区域G都置为同样的颜色。步骤如下：种子象素入栈，当栈非空时，执行如下三步操作：（1）栈顶象素出栈；（2）将出栈象素置成多边形色；（3）按上、下、左、右的顺序检查与出栈象素相邻的四个象素，若其中某个象素不在边界上且未置成多边形色，则把该象素入栈。,种子填充算法,计算机图形

27、学,种子填充算法,例：多边形由P0P1P2P3P4构成，P0(1,5)P1(5,5)P2(7,3)P3(7,1)P4(1,1)设种子点为（3，3），搜索的方向是上、下、左、右。依此类推，最后像素被选中并填充的次序如图中箭头所示,计算机图形学,种子填充算法,递归算法可实现如下,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,oldCol

28、or,newColor);FloodFill4(x-1,y,oldColor,newColor);FloodFill4(x+1,y,oldColor,newColor);/*end of FloodFill4()*/,计算机图形学,种子填充算法,边界表示的4连通区域,void BoundaryFill4(int x,int y,int boundaryColor,int newColor)int color;color=GetPixel(x,y);if(color!=boundaryColor)/*end of BoundaryFill4()*/,计算机图形学,该算法也可以填充有孔区域。缺点：

29、(1)有些象素会入栈多次，降低算法效率；栈结构占空间。(2)递归执行，算法简单，但效率不高，区域内每一象素都引起一次递归，进/出栈，费时费内存。改进算法，减少递归次数，提高效率。解决方法是用扫描线填充算法,种子填充算法,计算机图形学,二维裁剪,直线段裁剪直接求交算法Cohen-Sutherland算法中点分割算法参数化裁剪算法Liang-Barskey算法多边形裁剪 Sutlerland_Hodgman算法 Weiler-Athenton算法,计算机图形学,裁剪,裁剪：确定图形中哪些部分落在显示区之内，哪些落在显示区之外,以便只显示落在显示区内的那部分图形。这个选择过程称为裁剪。图形裁剪算法，

30、直接影响图形系统的效率。,计算机图形学,点的裁剪,图形裁剪中最基本的问题。假设窗口的左下角坐标为(xL,yB),右上角坐标为(xR,yT)，对于给定点P(x,y),则P点在窗口内的条件是要满足下列不等式：xL=x=xR并且yB=y=yT否则，P点就在窗口外。问题：对于任何多边形窗口，如何判别？,计算机图形学,直线段裁剪,直线段裁剪算法是复杂图形裁剪的基础。复杂的曲线可以通过折线段来近似，从而裁剪问题也可以化为直线段的裁剪问题。直接求交算法Cohen-Sutherland算法中点算法梁友栋barskey算法参数化裁剪算法,计算机图形学,直线段裁剪,裁剪线段与窗口的关系：(1)线段完全可见；(2)

31、显然不可见；(3)其它提高裁剪效率：快速判断情形(1)(2)，对于情形(3)，设法减少求交次数和每次求交时所需的计算量。,计算机图形学,直接求交算法,直线与窗口边都写成参数形式，求参数值。,计算机图形学,基本思想：对于每条线段P1P2分为三种情况处理分为三种情况处理:（1）若P1P2完全在窗口内，则显示该线段P1P2简称“取”之。（2）若P1P2明显在窗口外，则丢弃该线段，简称“弃”之。（3）若线段不满足“取”或“弃”的条件，则在交点处把线段分为两段。其中一段完全在窗口外，可弃之。然后对另一段重复上述处理,1001,0001,0101,Cohen-Sutherland裁剪,计算机图形学,Coh

32、en-Sutherland算法,将区域码的各位从右到左编号，则坐标区域与各位的关系为：上 下 右 左 X X X X任何位赋值为1，代表端点落在相应的位置上，否则该位为0。若端点在剪取矩形内，区域码为0000。如果端点落在矩形的左下角，则区域码为0101。,计算机图形学,Cohen-Sutherland算法,一旦给定所有的线段端点的区域码，就可以快速判断哪条直线完全在剪取窗口内，哪条直线完全在窗口外。所以得到一个规律：,计算机图形学,Cohen-Sutherland裁剪,若P1P2完全在窗口内code1=0,且code2=0,则“取”若P1P2明显在窗口外code1&code20，则“弃”在交

33、点处把线段分为两段。其中一段完全在窗口外，可弃之。然后对另一段重复上述处理。编码 线段裁剪,计算机图形学,Cohen-Sutherland裁剪,如何判定应该与窗口的哪条边求交呢？编码中对应位为1的边。计算线段P1(x1,y1)P2(x2,y2)与窗口边界的交点if(LEFT具体算法见p201,计算机图形学,Cohen-Sutherland直线裁剪算法小结,本算法的优点在于简单，易于实现。他可以简单的描述为将直线在窗口左边的部分删去，按左，右，下，上的顺序依次进行，处理之后，剩余部分就是可见的了。在这个算法中求交点是很重要的，他决定了算法的速度。另外，本算法对于其他形状的窗口未必同样有效。特点：

34、用编码方法可快速判断线段的完全可见和显然不可见。,计算机图形学,中点分割裁剪算法,基本思想：从P0点出发找出离P0最近的可见点，和从P1点出发找出离P1最近的可见点。这两个可见点的连线就是原线段的可见部分。与Cohen-Sutherland算法一样首先对线段端点进行编码，并把线段与窗口的关系分为三种情况，对前两种情况，进行一样的处理；对于第三种情况，用中点分割的方法求出线段与窗口的交点。A、B分别为距P0、P1最近的可见点，Pm为P0P1中点。,计算机图形学,中点分割算法-求线段与窗口的交点,从P0出发找距离P0最近可见点采用中点分割方法先求出P0P1的中点Pm,若P0Pm不是显然不可见的，并

35、且P0P1在窗口中有可见部分，则距P0最近的可见点一定落在P0Pm上，所以用P0Pm代替P0P1；否则取PmP1代替P0P1。再对新的P0P1求中点Pm。重复上述过程，直到PmP1长度小于给定的控制常数为止，此时Pm收敛于交点。从P1出发找距离P1最近可见点采用上面类似方法。,计算机图形学,中点分割裁剪算法,计算机图形学,对分辩率为2N*2N的显示器，上述二分过程至多进行N次。主要过程只用到加法和除法运算，适合硬件实现，它可以用左右移位来代替乘除法，这样就大大加快了速度。,中点分割裁剪算法,计算机图形学,设要裁剪的线段是P0P1。P0P1和窗口边界交于A,B,C,D四点，见图。算法的基本思想是

36、从A,B和P0三点中找出最靠近的P1点，图中要找的点是P0。从C,D和P1中找出最靠近P0的点。图中要找的点是C点。那么P0C就是P0P1线段上的可见部分。,梁友栋-Barsky算法,计算机图形学,梁友栋-Barsky算法,线段的参数表示x=x0+txy=y0+ty 0=t=1 x=x1-x0 y=y1-y0窗口边界的四条边分为两类：始边和终边。,计算机图形学,求出P0P1与两条始边的交点参数t0,t1,令tl=max(t0,t1,0)，则tL即为三者中离p1最近的 点的参数求出p0p1与两条终边的交点参数t2,t3,令tu=min(t2,t3,1)，则tU即为三者中离p0最近的 点的参数若t

37、u tl,则可见线段区间 tl,tu,t0,t1,t2,t3,0,1,梁友栋-Barsky算法：交点计算,计算机图形学,梁友栋-Barsky算法,始边和终边的确定及交点计算：令 QL=-x DL=x0-xL QR=x DR=xR-x0 QB=-y DB=y0-yB QT=y DT=yT-y0交点为 ti=Di/Qi i=L,R,B,TQi 0 ti为与终边交点参数Qi=0 Di 0 时,分析另一D,E,F,A,B,计算机图形学,梁友栋-Barsky算法,当Qi=0时 若Di 0 时,分析另一D,（如图中的EF就是这种情况，它使QL=0，DL0和QR=0，DR0。这时由于EF和x=xL及x=xR

38、平行，故不必去求出EF和x=xL及x=xR的交点，而让EF和y=yT及y=yB的交点决定直线段上的可见部分。）,E,F,A,B,计算机图形学,参数化算法(Cyrus-Beck),考虑凸多边形区域R和直线段P1P2P(t)=(P2-P1)*t+P1 设A是区域R的边界上一点，N是区域边界在A点的内法线向量,A,P2,R,N,P1,计算机图形学,参数化算法(Cyrus-Beck),则对于线段P1P2上任一点P(t)N(P(t)-A)外侧N(P(t)-A)0-内侧N(P(t)-A)=0-边界或其延长线上,A,P2,R,N,P1,计算机图形学,参数化算法(Cyrus-Beck),凸多边形的性质：点P(

39、t)在凸多边形内的充要条件是，对于凸多边形边界上任意一点A和该点处内法向N，都有N(P(t)-A)0,计算机图形学,参数化算法(Cyrus-Beck),k条边的多边形，可见线段参数区间的解:Ni(p(t)-Ai)=0,i=0,k,0t 1.即：Ni(P1-Ai)+Ni(P2-P1)t=0(1)式可得：令ti=Ni(P1-Ai)/Ni(P2-P1),计算机图形学,参数化算法(Cyrus-Beck),Ni(P2-P1)=0-平行于对应边。此时判断Ni(P1-Ai)若Ni(P1-Ai)P1 P2在多边形外侧-不可见，若Ni(P1-Ai)0-P1 P2在多边形内侧-继续其它边的判断,计算机图形学,参数

40、化算法(Cyrus-Beck),对于t值的选择：首先，要符合0t1；其次，对于凸窗口来说，每一个线段与其至多有两个交点，即有两个相应的t值。所以我们可以把计算出的t值分成两组：一组为下限组，是分布在线段起点一侧的；一组为上限组，是分布在线段终点一侧的。这样，只要找出下限组中的最大值及上限组中的最小值，就可确定线段了。分组的依据是：如果Ni(P2-P1)0，则计算出的值属于上限组如果Ni(P2-P1)0，则计算出的值属于下限组,计算机图形学,参数化算法(Cyrus-Beck),因此，线段可见的交点参数：tl=max0,maxti:Ni(P2-P1)0tu=min1,minti:Ni(P2-P1)

41、0若 tl=tu,tl，tu是可见线段的交点参数区间，否则，线段不可见。,计算机图形学,参数化算法的几何意义,下限组以Ni(P2-P1)0为特征，表示在该处沿P1P2方向前进将接近或进入多边形内侧。,上限组以Ni(P2-P1)0为特征，表示在该处沿P1P2方向前进将越来越远地离开多边形区域。,计算机图形学,参数化算法,当凸多边形是矩形窗口且矩形的边与坐标轴平行时，该算法退化为Liang-Barsky算法。,计算机图形学,非矩形窗口的线段裁剪,Cyrus-Beck扩充到凸多边形思考：凹多边形窗口的线段裁剪圆和曲线窗口的线段裁剪,计算机图形学,多边形裁剪,错觉：直线段裁剪的组合？新的问题：1）边界

42、不再封闭，需要用窗口边界的恰当部分来封闭它，如何确定其边界？,计算机图形学,多边形裁剪,2）一个凹多边形可能被裁剪成几个小的多边形，如何确定这些小多边形的边界？,计算机图形学,Sutherland-Hodgman算法,分割处理策略：将多边形关于矩形窗口的裁剪分解为多边形关于窗口四边所在直线的裁剪。流水线过程(左上右下)：前边的结果是后边的输入。,亦称逐边裁剪算法,计算机图形学,Sutherland-Hodgman算法,基本思想是一次用窗口的一条边裁剪多边形。考虑窗口的一条边以及延长线构成的裁剪线该线把平面分成两个部分:可见一侧；不可见一侧多边形的各条边的两端点S、P。它们与裁剪线的位置关系只有

43、四种,计算机图形学,Sutherland-Hodgman算法,情况（1）仅输出顶点P；情况（2）输出0个顶点；情况（3）输出线段SP与裁剪线的交点I；情况（4）输出线段SP与裁剪线的交点I和终点P,计算机图形学,Sutherland-Hodgman算法框图,处理线段SP过程子框图,计算机图形学,Sutherland-Hodgman算法,上述算法仅用一条裁剪边对多边形进行裁剪，得到一个顶点序列，作为下一条裁剪边处理过程的输入。对于每一条裁剪边，算法框图同上，只是判断点在窗口哪一侧以及求线段SP与裁剪边的交点算法应随之改变。,计算机图形学,Sutherland-Hodgeman算法,对凸多边形应用

44、本算法可以得到正确的结果，但是对凹多边形的裁剪将如图所示显示出一条多余的直线。这种情况在裁剪后的多边形有两个或者多个分离部分的时候出现。因为只有一个输出顶点表，所以表中最后一个顶点总是连着第一个顶点。解决这个问题有多种方法，一是把凹多边形分割成若干个凸多边形，然后分别处理各个凸多边形。二是修改本算法，沿着任何一个裁剪窗口边检查顶点表，正确的连接顶点对。再有就是Weiler-Atherton算法。,计算机图形学,Sutherland-Hodgman算法,思考：如何推广到任意凸多边形裁剪窗口？,计算机图形学,Weiler-Athenton算法,裁剪窗口为任意多边形（凸、凹、带内环）的情况：主多边形

45、：被裁剪多边形，记为A 裁剪多边形：裁剪窗口，记为B,计算机图形学,Weiler-Athenton算法,多边形顶点的排列顺序（使多边形区域位于有向边的左侧）外环：逆时针；内环：顺时针主多边形和裁剪多边形把二维平面分成两部分。内裁剪：AB外裁剪：A-B,裁剪结果区域的边界由A的部分边界和B的部分边界两部分构成，并且在交点处边界发生交替，即由A的边界转至B的边界，或由B的边界转至A的边界,计算机图形学,Weiler-Athenton算法,如果主多边形与裁剪多边形有交点，则交点成对出现，它们被分为如下两类：进点：主多边形边界由此进入裁剪多边形内 如，I1,I3,I5,I7,I9,I11出点：主多边形

46、边界由此离开裁剪多边形区域.如，I0,I2,I4,I6,I8,I10,计算机图形学,Weiler-Athenton算法,1）建顶点表；2）求交点；3）裁剪,1、建立主多边形和裁剪多边的顶点表2、求主多边形和裁剪多边形的交点，并将这些交点按顺序插入两多边形的顶点表中。在两多边表形顶点表中的相同交点间建立双向指针。3、裁剪:如果存在没有被跟踪过的交点，执行以下步骤：,计算机图形学,Weiler-Athenton算法,计算机图形学,Weiler-Athenton算法,(1)建立空的裁剪结果多边形的顶点表(2)选取任一没有被跟踪过的交点为始点，将其输出到结果多边形顶点表中(3)如果该交点为进点，跟踪主

47、多边形边边界；否则跟踪裁剪多边形边界(4)跟踪多边形边界，每遇到多边形顶点，将其输出到结果多边形顶点表中，直至遇到新的交点(5)将该交点输出到结果多边形顶点表中，并通过连接该交点的双向指针改变跟踪方向（如果上一步跟踪的是主多边形边界，现在改为跟踪裁剪多边形边界；如果上一步跟踪裁剪多边形边界，现在改为跟踪主多边形边界）(6)重复(4)、(5)直至回到起点取I7为起点，所得裁剪结果多边形I7I0q0I3I4I5I6I7。取I8为起点，所得裁剪结果多边形为I8I9I10I11I2q2I1I8。,计算机图形学,Weiler-Athenton算法,交点的奇异情况处理 1、与裁剪多边形的边重合的主多边形的

48、边不参与求交点；2、对于顶点落在裁剪多边形的边上的主多边形的边，如果落在该裁剪边的内侧，将该顶点算作交点；而如果这条边落在该裁剪边的外侧，将该顶点不看作交点,计算机图形学,反走样,用离散量表示连续量引起的失真现象称之为走样(aliasing)。光栅图形的走样现象阶梯状边界；图形细节失真；狭小图形遗失：动画序列中时隐时现，产生闪烁。,计算机图形学,走样现象举例,不光滑(阶梯状）的图形边界,例子：PaintBrush,计算机图形学,走样现象举例,图形细节失真,计算机图形学,走样现象举例,狭小图形的遗失与动态图形的闪烁,计算机图形学,反走样概念及方法,用于减少或消除走样现象的技术称为反走样(anti

49、aliasing)提高分辨率简单区域取样加权区域取样,计算机图形学,提高分辨率,把显示器分辨率提高一倍，直线经过两倍的象素，锯齿也增加一倍，但同时每个阶梯的宽度也减小了一倍，所以显示出的直线段看起来就平直光滑了一些。,计算机图形学,提高分辨率,方法简单，但代价非常大。显示器的水平、竖直分辩率各提高一倍，则显示器的点距减少一倍，帧缓存容量则增加到原来的4倍，而扫描转换同样大小的图元却要花4倍时间。而且它也只能减轻而不能消除锯齿问题另一种方法（软件方法）：用较高的分辨率的显示模式下计算，（对各自像属下计算，再求（非）加权平均的颜色值），在较低的分辨率模式下显示。只能减轻而不能消除锯齿问题。,计算机

50、图形学,软件方法1,把每个像素分为四个子像素，扫描转换算法求得各子像素的灰度值，然后对四像素的灰度值简单平均，作为该像素的灰度值。,计算机图形学,软件方法2,设分辨率为mn,把显示窗口分为(2m+1)(2n+1)个子像素，对每个子像素进行灰度值计算，然后根据权值表所规定的权值，对位于像素中心及四周的九个子像素加权平均，作为显示像素的颜色。设m=4,n=3,计算机图形学,简单区域取样,方法由来两点假设1、象素是数学上抽象的点，它的面积为0，它的亮度由覆盖该点的图形的亮度所决定；2、直线段是数学上抽象直线段，它的宽度为0。现实像素的面积不为0；直线段的宽度至少为1个像素；假设与现实的矛盾是导致混淆