计算机图形学 CG04-6裁剪-7反走样 .ppt

1、4.6 裁剪算法裁剪算法进行图形的描述中总是尽可能全面地获取它的有关信息，而在进行图形显示与研究过程显示与研究过程中中往往对其中某些部分某些部分更感兴趣和需要。计算机内部存储的图形比较大，而屏幕显示只是图的一部分。裁剪概念裁剪概念 确定图形中哪些部分落在显示区之内，哪些落在显示区之外，以便只显示落在显示区内的那部分图形，这个选择处理过程称为裁剪裁剪。在进行裁剪时，画面中对应于屏幕显示的那部分区域称为窗口窗口。图形裁剪图形裁剪 图形裁剪图形裁剪就是决定画面中哪些点、线段或线段的一部分位于裁剪窗口之内，这些点、线段或线段的一部分被保留显示，而画面其它部分被裁去。裁剪算法有二维二维的和三维三维的，裁

2、剪对象可以是规则形体，也可以是不规则形体，其裁剪算法可以用硬件实现硬件实现，也可以用软软件实现件实现。图示(xL,yB)(xR,yT)(x,y)若xLxxR,yByyT成立，则点(x,y)在矩形窗口内裁剪与扫描转换裁剪与扫描转换由于在一个典型画面或图形中需要对大量的点或线段进行裁剪，裁剪算法的效率十分重要。先扫描转换再裁剪先扫描转换再裁剪:把各种图形扫描转换为点之后，再判断各点是否在窗内。简单但太费时。先裁剪再扫描转换先裁剪再扫描转换:有些图形组成部分全部在窗口外，可以完全排除，不必进行扫描转换。本节主要内容本节主要内容 线段裁剪线段裁剪 多边形裁剪多边形裁剪 字符裁剪字符裁剪 线段的裁剪线段

3、的裁剪当线段的两个端点均在裁剪区域内部，该线段上的点全在裁剪区域内。当线段的一个端点在区域内部，另一个端点在区域外部，要求线段与区域边界的交点，来得到区域内部的点。当线段的两个端点落在区域外部，不能直接确定该线段是否有裁剪区域内部的点。即该线段不一定全部在窗口外面。线段的裁剪常用的线段裁剪方法有三种：Cohen-Sutherland算法算法中点分割算法中点分割算法参数化方法参数化方法Cohen-Sutherland算法算法由Dan Cohen和Ivan SutherLand提出的，该算法的思想是对于每条线段P1P2分为三种情况处理：（1）若两端点P1P2完全在窗口内，则完全可见该线段P1P2。

4、否则进入下一步；（2）若线段P1P2明显在窗口外，即显然不可见，则丢弃该线段，否则进入下一步；（3）若线段既不满足(1)的条件，也不满足(2)的条件，则在交点处把线段分为两段。其中一段完全在窗口外，可弃之。然后对另一段重复上述处理。三种情况图示HFBAGCIJEKLDCohen-Sutherland算法算法为使计算机能够快速判断一条直线段与窗口属何种关系，采用四位数码四位数码来标识线段的端点与窗口区域的关系，然后进行裁剪的算法-Cohen-SutherLand算法。000010011000101000010010010101000110裁剪区域编码的含义编码的含义编码规则，从左起：第一位为 1

5、 表示线段端点位于窗口上侧，0 表示线段端点不位于窗口上侧;第二位为 1 表示线段端点位于窗口下侧，0 表示线段端点不位于窗口下侧;第三位为 1 表示线段端点位于窗口右侧，0 表示线段端点不位于窗口右侧;第四位为 1 表示线段端点位于窗口左侧，0 表示线段端点不位于窗口左侧。线段的编码00000000000000000000000001000100010100011000001000101010abcdefgCohen-SutherLand算法基本思想：若线段完全在窗口内部，则显示该线段，为“取”之；若线段明显在窗口外，丢弃该线段，为“弃”之；若线段即不满足“取”的条件，也不满足“弃”的条件，

6、则把线段分为两段，其中一段完全在窗口外，则“弃”之，然后对另一段线段重复上面的处理。图示的线段图示的线段根据Cohen-SutherLand算法思想，线段：a:(0000,0000)完全在窗口内部；取b:(0000,0000)完全在窗口内部；取c:(0000,0100)部分完全在窗口内部；处理d:(0100,0010)部分完全在窗口内部；处理e:(0000,0010)部分完全在窗口内部；处理f:(0001,0101)完全在窗口外部；弃g:(1000,1010)完全在窗口外部；弃裁剪一条线段时先求出P1P2所在的区号code1,code2。n若code1=0,且code2=0，则线段P1P2在窗

7、口内，应取之。n若按位与运算code1&code20，则说明两个端点同在窗口的上方、下方、左方或右方。可判断线段完全在窗口外，可弃之。n否则，按第三种情况处理。求出线段与窗口某边的交点，在交点处把线段一分为二，其中必有一段在窗口外，可弃之。在对另一段重复上述处理。边界求交边界求交在实现本算法时，不必把线段与每条窗口边界依次求交，只要按顺序检测到端点区按顺序检测到端点区位的某位编码不为位的某位编码不为0，才才把线段与对应的窗口边界进行求交求交。如何求交点判断直线和哪条边由交点，具体方法为：若编码&00010，端点与左边界有交点；若编码&00100，端点与右边界有交点；若编码&01000，端点与下

8、边界有交点；若编码&10000，端点与上边界有交点；本算法的特点：对显然不可见线段的快速判别 例1000011002468102468XYAB点A只与上边界相交，直接求交点。点B与右边界先求交点，然后该交点还是在外部，编码为0100，故还要与下边界求交点。算法实现#define LEFT 1#define RIGHT 2#define BOTTOM 4#define TOP 8#define XL 150#define XR 350#define YB 150#define YT 300编码encode(x,y,code)int x,y;int*code;int c;c=0;if(xXR)c=

9、c|RIGHT;if(yYT)c=c|TOP;*code=c;return;编码draw_ett()int x1,x2,y1,y2,x,y;int code1,code2,code;x1=50;y1=250;x2=400;y2=300;setcolor(1);line(x1,y1,x2,y2);encode(x1,y1,&code1);encode(x2,y2,&code2);while(code1!=0)|(code2!=0)if(code1&code2)!=0)return;code=code1;if(code1=0)code=code2;if(LEFT&code)!=0)x=XL;y=y

10、1+(y2-y1)*(XL-x1)/(x2-x1);else if(RIGHT&code)!=0)x=XR;y=y1+(y2-y1)*(XR-x1)/(x2-x1);Else if(BOTTOM&code)!=0)y=YB;x=x1+(x2-x1)*(YB-y1)/(y2-y1);Else if(TOP&code)!=0)y=YT;x=x1+(x2-x1)*(YT-y1)/(y2-y1);编码if(code=code1)x1=x;y1=y;encode(x,y,&code1);Else x2=x;y2=y;encode(x,y,&code2);动画演示：Cohen-Sutherland直线段裁

11、剪算法 中点分割法中点分割法与Cohen-Sutherland算法类似n首先对线段端点进行编码n并把线段与窗口的关系分为三种情况:全在、完全不在和线段与窗口有交线段与窗口有交对前两种情况，进行一样的处理n用中点分割的方法用中点分割的方法求出线段与窗口的交求出线段与窗口的交点点 中点分割法中点分割法(最远的可见点)即从P0点出发找出离P0最远的可见点（图中的B点）从P1点出发找出离P1最远的可见点（图中的A点）。这两个可见点的连线这两个可见点的连线AB就是原线段的可见部分就是原线段的可见部分。这两点求法类似，这里以P0点为例介绍。设要裁减的线段是P0P1。中点分割算法可分成两个平行的过程进行：从

12、P0出发找最远可见点的方法 若P1可见，则P1就是离P0最远的可见点。否则(P1不可见)(1)对两端点区号作按位与运算，若不为零，则P0P1全部不可见，弃之。否则(2)在中点Pm处把线段P0P1分为两段。从P0出发找最远可见点的方法最远的可见点；若P1Pm完全在窗口外，在P0Pm中找离P0最远的可见点。重复上述过程，直到线段长度小于给定的精度为止。这时分点即为所求点。若若P Pm m可见可见，把原问题转化为对PmP1求离P0最远的可见点。若若P Pm m不可见不可见:若P0Pm完全在窗口外，在P1Pm中找离P0中点分割法中点分割法(最近的可见点)设要裁减的线段是P0P1。中点分割算法可分成两个

13、平行的过程进行：即从P0点出发找出离P0最近的可见点（图中的A点）从P1点出发找出离P1最近的可见点（图中的B点）。这两个可见点的连线就是原这两个可见点的连线就是原线段的可见部分线段的可见部分。中点分割法中点分割法从P0出发找最近可见点最近可见点的方法是:先求P0P1的中点Pm，若P0Pm不能定为显然不可见显然不可见，则取P0Pm代替P0P1，否则取PmP1代替P0P1 再对新的P0P1求中点Pm。重复上述过程，直到P1Pm长度小于给定的精度为止。此时P0即为所求A点!动画演示：Cohen-Sutherland算法和中点分割算法的比较 参数法参数法(Cyrus-Beck算法算法)假定A是区域R

14、边界上的一点，N是区域边界在A点内法向量。线段P1P2用参数方程表示：P(t)=(P2-P1)t+P1 (0t1)参数法参数法对于线段上任意一点P(t),有三种可能性：NP(t)-A0，这时P(t)必在多边形内侧参数法参数法由凸多边形的性质知，P(t)在多边形内的充充要条件要条件是，对于凸多边形边界上任意一点A和该处内法量N，都有N(P(t)-A)0。即 NiP(t)-Ai0，(i=1,2,.,k)(0t1)Ni(P2-P1)t+P1-Ai0 Ni(P1-Ai)+Ni(P2-P1)t0参数法参数法当Ni(P2-P1)=0时，Ni(P2-P1)，即 P1P2与对应边平行，与其无交点。此时 当Ni

15、(P1-Ai)0时，t-ti当Ni(P1-Ai)0 tu=min1,min-ti:Ni(P2-P1)tu，则整条线段在区域外部。几何意义P204梁友栋-Barsky直线裁剪算法当凸多边形是矩形窗口时，参数算法可简化为Liang-Barsky算法。详细见课本P205四种算法比较CS与中点算法与中点算法在区码测试阶段能以位运算方式高效地进行，因而当大多数线段能简单地取舍时，效率较好。参数法参数法在多数线段需要进行裁剪时，效率更高。因只涉及参数运算，仅到必要时才进行坐标计算。LB算法算法只应能于矩形窗口，其效率比CB法更高。梁友栋-Barsky直线裁剪算法Sutherland-Cohen是最早最流行

16、的线段裁剪算法，该算法通过初始测试来减少要计算的交点的数目，从而加快了裁剪的速度。下面是另一种更快的裁剪算法，该算法是基於线段的参数化方程的分析。梁友栋-Barsky直线裁剪算法设要裁减的线段是P0P1。P0P1和窗口边界交于A,B,C,D四点，见图。算法的基本思想是从A,B和P0三点中找出最靠近的P1点，图中要找的点是P0。从C,D和P1中找出最靠近P0的点。图中要找的点是C点。那么P0C就是P0P1线段上的可见部分。线段的参数化方程如下：121211,1,0yyyxxxuyuyyxuxx其中x，y把窗口边界的四条边分成两类，一类称为始边，另一类称为终边。当x0（y0）时，称x=x1(y=y

17、1)为始边，x=x2(y=y2)为终边。当x0（yt0时，方程（4.38）中参数tt0,t1的线段就是P0P1的可见部分。当t0t1时，整个直线段为不可见。分析 对于点P(x,y)，如果在窗口内部，则满足：bottomtoprightleftyyyxxx分析将上式变形，有：bottomtoprightleftyyuyyxxuxx11这四个不等式可以表示成：4,3,2,1,kqupkk分析可以统一表示为形式：144133122111yYqypYyqypxXqxpXxqxptopbottomrightleft以此确定始边和终边，和求P0P1与它们的交点。分析易知交点的参数为 ,i=1,2,3,4

18、当pi0时，ti必是P0P1和终边的交点的参数。当pk=0时（k=1,2,3,4)，为平行于裁剪边界的直线；如满足qk0，这时由于EF和x=xL及x=xR平行，故不 必去求出EF和x=xL及x=xR的交点，而让EF和y=yT及y=yB的 交点决定直线段上的可见部分。iiipqt 当pk=0时0000000044332211qpqpqpqpAB直线EF直线0000000044332211qpqpqpqp144133122111yYqypYyqypxXqxpXxqxptopbottomrightleft 动画演示：梁友栋Barskey直线段裁剪算法 4.6.2多边形的裁剪利用线段的裁剪过程，来完成

19、多边形的裁剪。基本思想基本思想是依次用窗口的一条边裁剪多边形的每条边，当全部裁剪完毕时，得到的就是裁剪后的多边形。分析考虑窗口的一条边以及延长线构成的裁剪线该线把 平面分成两个部分:可见一侧；不可见一侧多边形的各条边的两端点S、P。它们与裁剪线的位 置关系只有四种可见一侧可见一侧可见一侧可见一侧SpSSSppp(1)(2)(3)(4)II分析对于情况（1）仅输出顶点P；情况（2）输出0个顶点；情况（3）输出线段SP与裁剪线的交点I；情况（4）输出线段SP与裁剪线的交点I和终点P上述算法仅用一条裁剪边对多边形进行裁剪，得到一个顶点序列，作为下一条裁剪边处理 过程的输入。对于每一条裁剪边，算法框图

20、同上，只是判 断点在窗口哪一侧以及求线段SP与裁剪边的 交点算法应随之改变。逐次裁剪多边形的流程p1p2p3p4p5p6p2p3p4p4p4p4p5p5p6p6p6I1I2I1I1I1I2I2I2I3I4I4I4I3I3I5I6I6I5I7I8字符裁剪字符裁剪当字符和文本部分在窗口内，部分在窗当字符和文本部分在窗口内，部分在窗口外时，就提出了字符裁剪问题。口外时，就提出了字符裁剪问题。字符裁剪的策略包括几种：串精度裁剪、字符裁剪的策略包括几种：串精度裁剪、字符精度裁剪以及笔划、像素精度裁剪。字符精度裁剪以及笔划、像素精度裁剪。定义定义各种图形在显示器上是用离各种图形在显示器上是用离散的像素来表

21、示的，这种用散的像素来表示的，这种用离散量表示连续量造成的失离散量表示连续量造成的失真，叫做真，叫做走样走样(混淆混淆 aliasing)用于减少或消除这种效果的用于减少或消除这种效果的技术，就称为技术，就称为反走样反走样(反混反混淆淆 antialising)。（1）不光滑（阶梯状）的图形边界）不光滑（阶梯状）的图形边界 （2）图形细节失真图形细节失真（小变大）（3）狭小图形遗失与动态图形的闪烁）狭小图形遗失与动态图形的闪烁 提高分辨率提高分辨率左图用中点算法扫描转换的一条直线左图用中点算法扫描转换的一条直线 右右图把显示器分辨率提高一倍后的结果图把显示器分辨率提高一倍后的结果简单简单，但是

22、不经济不经济的方法，而且它也只能只能减轻减轻而不能消除不能消除锯齿问题。提高分辨率提高分辨率折衷方案折衷方案:在较高分辨率下进行平均算法，在较低分辨率的显示器上显示。简单平均简单平均加权平均加权平均设分辨率为mn,把显示窗口分为(2m+1)(2n+1)个子像素，对每个子像素进行灰度值计算，然后根据权值表所规定的权值，对位于像素中心及四周的九个子像素加权平均，作为显示像素的颜色。设m=3,n=4实践证明上述两方案对于改进图形质量实践证明上述两方案对于改进图形质量都有较好的结果。都有较好的结果。简单的区域取样简单的区域取样简单的区域取样简单的区域取样缺点缺点：仍然会导致锯齿效应；沿理想直线方向的相

23、邻两个象素有时会有较大的灰度差 加权的区域取样加权的区域取样 相交区域对象素亮度的贡献依赖于相交区域对象素亮度的贡献依赖于该区域与象素中心的距离该区域与象素中心的距离 特点特点：接近理想直线的象素将被分配更多的灰度值；缩小直线上相邻象素的灰度差。n000,000,0FF,0FE,004,040,004,040,07F,0FC,044,044,044,044,044,044,044,044,048,03C,050,004,060,004,040,004,07F,0FC,040,004,000,000n000,000,03F,0FC,001,000,001,000,001,000,001,000,

24、001,000,001,000,001,000,001,000,001,000,001,000,001,000,0FF,0FE,000,000,000,000n001,000,001,000,001,000,001,000,001,000,0FF,0FE,001,000,002,080,002,080,002,040,004,040,004,020,008,010,010,018,020,00E,040,00416X16点阵三个汉字点阵三个汉字 示例出栈的情况02468102468XY(5,5)(4,5)(3,5)(2,5)(2,6)(3,4)(4,4)(5,4)(6,4)(6,5)(6,6)(5,6)(5,7)(3,3)(4,4)(5,6)(6,5)(5,4)区域填充与裁剪算法区域填充与裁剪算法一、实验教学目标与基本要求一、实验教学目标与基本要求1.掌握区域填充的基本算法原理；2.熟悉裁剪算法的基本原理；3.会使用字符的图形输出。二、实验课程内容二、实验课程内容 (4(4学时，记成绩学时，记成绩5 5分分)1.多边形的扫描线、边标志及扫描线种子填充算法(至少实现两种算法)；2.裁剪算法(至少实现一种算法)；3.(选做)在屏幕上输出矢量或点阵字符。第二次实 验