第3章 基本图形的生成三精选PPT.ppt

《第3章 基本图形的生成三精选PPT.ppt》由会员分享，可在线阅读，更多相关《第3章 基本图形的生成三精选PPT.ppt（55页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第3章 基本图形的生成三第1页，本讲稿共55页裁剪2022/10/7内蒙古大学计算机图形学2裁剪：确定图形中哪些部分落在显示区之内，哪些落在显示区之外,以便只显示落在显示区内的那部分图形。这个选择过程称为裁剪裁剪。图形裁剪算法，直接影响图形系统的效率。第2页，本讲稿共55页点的裁剪2022/10/7内蒙古大学计算机图形学3图形裁剪中最基本的问题。假设窗口的左下角坐标为(xL,yB),右上角坐标为(xR,yT)，对于给定点P(x,y),则P点在窗口内的条件是要满足下列不等式：xL=x=xR并且yB=y=yT否则，P点就在窗口外。问题：对于任意多边形窗口，如问题：对于任意多边形窗口，如何判别？何判

2、别？(xL,yB)(xR,yT)第3页，本讲稿共55页直线段裁剪2022/10/7内蒙古大学计算机图形学4直线段裁剪算法是复杂图形裁剪的基础。复杂的曲线可以通过折线段来近似，从而裁剪问题也可以化为直线段的裁剪问题。直接求交算法Cohen-Sutherland算法中点算法梁友栋barskey算法参数化裁剪算法第4页，本讲稿共55页直接求交算法2022/10/7内蒙古大学计算机图形学5直线与窗口边都写成参数形式，求参数值。第5页，本讲稿共55页直线段裁剪2022/10/7内蒙古大学计算机图形学6裁剪线段与窗口的关系：(1)线段完全可见；(2)显然不可见；(3)其它提高裁剪效率：快速判断情形(1)(

3、2)，对于情形(3)，设法减少求交次数和每次求交时所需的计算量。第6页，本讲稿共55页Cohen-Sutherland裁剪2022/10/7内蒙古大学计算机图形学7基本思想：对于每条线段P1P2分为三种情况处理:（1）若P1P2完全在窗口内，则显示该线段P1P2。（2）若P1P2明显在窗口外，则丢弃该线段。（3）若线段不满足（1）或（2）的条件，则在交点处把线段分为两段。其中一段完全在窗口外，可弃之。然后对另一段重复上述处理。为快速判断，采用如下编码方法：第7页，本讲稿共55页Cohen-Sutherland裁剪2022/10/7内蒙古大学计算机图形学8 实现方法：将窗口边线两边沿长，得到九个

4、区域，每一个区域都用一个四位二进制数标识，直线的端点都按其所处区域赋予相应的区域码，用来标识出端点相对于裁剪矩形边界的位置。100100010101100000000100101000100110ABCD第8页，本讲稿共55页Cohen-Sutherland裁剪2022/10/7内蒙古大学计算机图形学9将区域码的各位从右到左编号，则坐标区域与各位的关系为：上 下 右 左 X X X X任何位赋值为1，代表端点落在相应的位置上，否则该位为0。若端点在剪取矩形内，区域码为0000。如果端点落在矩形的左下角，则区域码为0101。第9页，本讲稿共55页Cohen-SutherlandCohen-Sut

5、herland算法算法2022/10/7内蒙古大学计算机图形学10一旦给定所有的线段端点的区域码，就可以快速判断哪条直线完全在剪取窗口内，哪条直线完全在窗口外。所以得到一个规律：第10页，本讲稿共55页Cohen-Sutherland裁剪2022/10/7内蒙古大学计算机图形学11若P1P2完全在窗口内code1=0,且code2=0,则“取”若P1P2明显在窗口外code1&code20，则“弃”在交点处把线段分为两段。其中一段完全在窗口外，可弃之。然后对另一段重复上述处理。编码 线段裁剪第11页，本讲稿共55页Cohen-Sutherland裁剪2022/10/7内蒙古大学计算机图形学12

6、如何判定应该与窗口的哪条边求交呢？如何判定应该与窗口的哪条边求交呢？编码中对应位为1的边。计算线段P1(x1,y1)P2(x2,y2)与窗口边界的交点if(LEFT&code!=0)x=XL;y=y1+(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);第12页，本讲稿

7、共55页Cohen-Sutherland直线裁剪算法小结2022/10/7内蒙古大学计算机图形学13本算法的优点在于简单，易于实现。他可以简单的描述为将直线在窗口左边的部分删去，按左，右，下，上的顺序依次进行，处理之后，剩余部分就是可见的了。在这个算法中求交点是很重要的，他决定了算法的速度。另外，本算法对于其他形状的窗口未必同样有效。特点：用编码方法可快速判断线段的完全可见和显然不可见。第13页，本讲稿共55页非矩形窗口的线段裁剪2022/10/7内蒙古大学计算机图形学14Cyrus-Beck扩充到凸多边形思考：凹多边形窗口的线段裁剪圆和曲线窗口的线段裁剪第14页，本讲稿共55页多边形裁剪20

8、22/10/7内蒙古大学计算机图形学15错觉错觉：直线段裁剪的组合？新的问题新的问题：1）边界不再封闭，需要用窗口边界的恰当部分来封闭它，如何确定其边界？第15页，本讲稿共55页多边形裁剪2022/10/7内蒙古大学计算机图形学162）一个凹多边形可能被裁剪成几个小的多边形，如何确定这些小多边形的边界？第16页，本讲稿共55页Sutherland-Hodgman算法2022/10/7内蒙古大学计算机图形学17分割处理策略分割处理策略：将多边形关于矩形窗口的裁剪分解为多边形关于窗口四边所在直线的裁剪。流水线过程流水线过程(左上右下左上右下)：前边的结果是后边的输入。亦亦称逐边裁称逐边裁剪算法剪算

9、法第17页，本讲稿共55页Sutherland-Hodgman算法2022/10/7内蒙古大学计算机图形学18基本思想是一次用窗口的一条边裁剪多边形。考虑窗口的一条边以及延长线构成的裁剪线该线把平面分成两个部分:可见一侧；不可见一侧多边形的各条边的两端点S、P。它们与裁剪线的位置关系只有四种第18页，本讲稿共55页Sutherland-Hodgman算法2022/10/7内蒙古大学计算机图形学19情况（1）仅输出顶点P；情况（2）输出0个顶点；情况（3）输出线段SP与裁剪线的交点I；情况（4）输出线段SP与裁剪线的交点I和终点P第19页，本讲稿共55页Sutherland-Hodgman算法框

10、图2022/10/7内蒙古大学计算机图形学20 处理线段SP过程子框图第20页，本讲稿共55页Sutherland-Hodgman算法2022/10/7内蒙古大学计算机图形学21上述算法仅用一条裁剪边对多边形进行裁剪，得到一个顶点序列，作为下一条裁剪边处理过程的输入。对于每一条裁剪边，算法框图同上，只是判断点在窗口哪一侧以及求线段SP与裁剪边的交点算法应随之改变。第21页，本讲稿共55页Sutherland-Hodgeman算法2022/10/7内蒙古大学计算机图形学22对凸多边形应用本算法可以得到正确的结果，但是对凹多边形的裁剪将如图所示显示出一条多余的直线。这种情况在裁剪后的多边形有两个或

11、者多个分离部分的时候出现。因为只有一个输出顶点表，所以表中最后一个顶点总是连着第一个顶点。解决这个问题有多种方法，一是把凹多边形分割成若干个凸多边形，然后分别处理各个凸多边形。二是修改本算法，沿着任何一个裁剪窗口边检查顶点表，正确的连接顶点对。再有就是Weiler-Atherton算法。第22页，本讲稿共55页Sutherland-Hodgman算法2022/10/7内蒙古大学计算机图形学23思考：如何推广到任意凸多边形裁剪窗口？第23页，本讲稿共55页Weiler-Athenton算法2022/10/7内蒙古大学计算机图形学24裁剪窗口为任意多边形（裁剪窗口为任意多边形（凸、凹、带内环）的情

12、况：的情况：主多边形：被裁剪多边形，记为主多边形：被裁剪多边形，记为A 裁剪多边形：裁剪窗口，记为裁剪多边形：裁剪窗口，记为B 第24页，本讲稿共55页Weiler-Athenton算法2022/10/7内蒙古大学计算机图形学25多边形顶点的排列顺序（使多边形区域位于有向边的左侧）外环：逆时针；内环：顺时针主多边形和裁剪多边形把二维平面分成两部分。内裁剪内裁剪：AB外裁剪外裁剪：A-B裁剪结果区域的边界由A的部分边界和B的部分边界两部分构成，并且在交点处边界发生交替，即由A的边界转至B的边界，或由B的边界转至A的边界 第25页，本讲稿共55页Weiler-Athenton算法2022/10/7

13、内蒙古大学计算机图形学26如果主多边形与裁剪多边形有交点，则交点成对出现，它们如果主多边形与裁剪多边形有交点，则交点成对出现，它们被分为如下两类：被分为如下两类：进点：主多边形边界由此进入裁剪多边形内进点：主多边形边界由此进入裁剪多边形内 如，如，I1,I3,I5,I7,I9,I11出点：主多边形边界由出点：主多边形边界由此离开裁剪多边形区域此离开裁剪多边形区域.如，如，I0,I2,I4,I6,I8,I10 第26页，本讲稿共55页Weiler-Athenton算法2022/10/7内蒙古大学计算机图形学271）建顶点表；2）求交点；3）裁剪 1、建立主多边形和裁剪多边的顶点表2、求主多边形和

14、裁剪多边形的交点，并将这些交点按顺序插入两多边形的顶点表中。在两多边形顶点表中的相同交点间建立双向指针。3、裁剪:如果存在没有被跟踪过的交点，执行以下步骤：第27页，本讲稿共55页Weiler-Athenton算法2022/10/7内蒙古大学计算机图形学28第28页，本讲稿共55页Weiler-Athenton算法2022/10/7内蒙古大学计算机图形学29 (1)建立空的裁剪结果多边形的顶点表 (2)选取任一没有被跟踪过的交点为始点，将其输出到结果多边形顶点表中 (3)如果该交点为进点，跟踪主多边形边边界；否则跟踪裁剪多边形边界 (4)跟踪多边形边界，每遇到多边形顶点，将其输出到结果多边形顶

15、点表中，直至遇到新的交点 (5)将该交点输出到结果多边形顶点表中，并通过连接该交点的双向指针改变跟踪方向（如果上一步跟踪的是主多边形边界，现在改为跟踪裁剪多边形边界；如果上一步跟踪裁剪多边形边界，现在改为跟踪主多边形边界）(6)重复(4)、(5)直至回到起点取I7为起点，所得裁剪结果多边形I7I0q0I3I4I5I6I7。取I8为起点，所得裁剪结果多边形为I8I9I10I11I2q2I1I8。第29页，本讲稿共55页Weiler-Athenton算法2022/10/7内蒙古大学计算机图形学30交点的奇异情况处理交点的奇异情况处理 1、与裁剪多边形的边重合的主多边形的边不参与求交点；2、对于顶点

16、落在裁剪多边形的边上的主多边形的边，如果落在该裁剪边的内侧，将该顶点算作交点；而如果这条边落在该裁剪边的外侧，将该顶点不看作交点 第30页，本讲稿共55页2022/10/7内蒙古大学计算机图形学31字符裁剪字符裁剪 把把每每个个字字符符看看作作是是不不可可分分割割的的整整体体，对对每每一一个个字字符符串串就就可可用用逐逐字字裁裁剪剪的的方方法法，把把每每个个字字符符用用一一矩矩形形（字字符符框框）包包围围起起来来（见见图图），然然后后检检测测该该字字符符框框中中的的某某一一点点（如如顶顶点点或或中中心心点点）的的可可见见性性，把把该该点点与与窗窗口口进进行行比比较较，如如果果在在窗窗口口内内，

17、就就显显示示该该字字符符，否否则则就就舍舍弃弃不不显显示示，另另外外也也可可以以用用整整个个字字符符框框的的界界线线或或其其对对角角线线与与窗窗口口进进行行比比较较，当当字字符符框框或或对对角角线线完完全全在在窗窗口口内内时时才才显显示示该该字字符符，不不过过用用字字符符框框顶顶点点或或用用字字符符框框界界线线（或或对对角角线线）裁裁剪剪的的两两种种方方法法，只只有有当当窗窗口口边边与与字字符符框框界界线线平平行时才等效，否则必须以字符框界进行裁剪。行时才等效，否则必须以字符框界进行裁剪。第31页，本讲稿共55页2022/10/7内蒙古大学计算机图形学32裁裁剪剪字字符符串串的的一一种种粗粗略

18、略方方法法，是是把把一一个个字字符符串串作作为为不不可可分分割割的的整整体体来来处处理理，用用一一个个字字符符串串框框封封闭闭起起来来（见见图图），检检测测这这个个字字符符串串框框上上的的某某一一点点、界界线线的的对对角角线线或或者者界界线线本本身身的的可可见见性，若在窗口内，就显示整串字符，否则整串字符就不显示。性，若在窗口内，就显示整串字符，否则整串字符就不显示。第32页，本讲稿共55页反走样2022/10/7内蒙古大学计算机图形学33用离散量表示连续量引起的失真现象称之为走样走样(aliasing)。光栅图形的走样现象光栅图形的走样现象阶梯状边界；图形细节失真；狭小图形遗失：动画序列中时

19、隐时现，产生闪烁。第33页，本讲稿共55页走样现象举例2022/10/7内蒙古大学计算机图形学34不光滑不光滑(阶梯状）的图形边界阶梯状）的图形边界例子：PaintBrush第34页，本讲稿共55页走样现象举例2022/10/7内蒙古大学计算机图形学35图形细节失真图形细节失真第35页，本讲稿共55页走样现象举例2022/10/7内蒙古大学计算机图形学36狭小图形的遗失与动态图形的闪烁狭小图形的遗失与动态图形的闪烁第36页，本讲稿共55页反走样概念及方法2022/10/7内蒙古大学计算机图形学37用于减少或消除走样现象的技术称为反走样反走样(antialiasing)提高分辨率简单区域取样加权

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

21、的分辨率模式下显示。只能减轻而不能消除锯齿问题。第39页，本讲稿共55页软件方法12022/10/7内蒙古大学计算机图形学40把每个像素分为四个子像素，扫描转换算法求得各子像素的灰度值，然后对四像素的灰度值简单平均，作为该像素的灰度值。第40页，本讲稿共55页软件方法22022/10/7内蒙古大学计算机图形学41设分辨率为mn,把显示窗口分为(2m+1)(2n+1)个子像素，对每个子像素进行灰度值计算，然后根据权值表所规定的权值，对位于像素中心及四周的九个子像素加权平均，作为显示像素的颜色。设m=3,n=4第41页，本讲稿共55页简单区域取样2022/10/7内蒙古大学计算机图形学42方法由来

22、方法由来两点假设两点假设1、象素是数学上抽象的点，它的面积为、象素是数学上抽象的点，它的面积为0，它的亮度由覆盖该点的图形的亮度所决定；，它的亮度由覆盖该点的图形的亮度所决定；2、直线段是数学上抽象直线段，它的宽度为、直线段是数学上抽象直线段，它的宽度为0。现实现实像素的面积不为像素的面积不为0；直线段的宽度至少为直线段的宽度至少为1个像素；个像素；假设与现实的矛盾是导致混淆出现的原因之一假设与现实的矛盾是导致混淆出现的原因之一第42页，本讲稿共55页简单区域取样2022/10/7内蒙古大学计算机图形学43解决方法：改变直线段模型，由此产生算法解决方法：改变直线段模型，由此产生算法方法步骤：方

23、法步骤：1、将直线段看作具有一定宽度的狭长矩形；、将直线段看作具有一定宽度的狭长矩形；2、当直线段与某象素有交时，求出两者相交区域的面积；、当直线段与某象素有交时，求出两者相交区域的面积；3、根据相交区域的面积，确定该象素的亮度值、根据相交区域的面积，确定该象素的亮度值 第43页，本讲稿共55页简单区域取样2022/10/7内蒙古大学计算机图形学44基本思想：每个象素是一个具有一定面积的小区域，将直线段看作具有一定宽度的狭长矩形。当直线段与象素有交时，求出两者相交区域的面积，然后根据相交区域面积的大小确定该象素的亮度值。有宽度的线条轮廓 象素相交的五种情况及用于计算面积的量DD/mDm(1)(

24、2)(3)(4)(5)第44页，本讲稿共55页简单区域取样2022/10/7内蒙古大学计算机图形学45面积计算情况（5)阴影面积为：D2/2m；情况（4)阴影面积为：D-m/2；情况阴影面积为：1-D2/m 为了简化计算可以采用离散的方法第45页，本讲稿共55页简单区域取样2022/10/7内蒙古大学计算机图形学46求相交区域的近似面积的离散计算方法求相交区域的近似面积的离散计算方法 1、将屏幕象素分割成、将屏幕象素分割成n个更小的子象素；个更小的子象素；2、计算中心点落在直线段内的子象素的个数，记为、计算中心点落在直线段内的子象素的个数，记为k，3、k/n为线段与象素相交区域面积的近似值为线

25、段与象素相交区域面积的近似值 目的：简化计算n=16,k=3近似面积=3/16第46页，本讲稿共55页简单区域取样2022/10/7内蒙古大学计算机图形学47简单区域取样采用的是一个盒式滤波器，它是一个二维加权函数，以w表示。w=1 若在当前像素所代表的正方形上w=0 其它区域上直线条经过该像素时，该像素的灰度值可以通过在像素与直线条的相交区域上对w求积分获得。此时，面积值=体积值第47页，本讲稿共55页2022/10/7内蒙古大学计算机图形学48简单区域取样缺点：象素的亮度与相交区域的面积成正比，而与相交区域落在象素内的位置无关，这仍然会导致锯齿效应。直线条上沿理想直线方向的相邻两个象素有时

26、会有较大的灰度差。第48页，本讲稿共55页加权区域取样2022/10/7内蒙古大学计算机图形学49采用圆锥形滤波器，圆锥的底圆中心在当前像素，底圆半径为一个像素，锥高为1。当直线条经过该像素时，该像素的灰度值是在二者相交区域上对滤波器进行积分的积分值。第49页，本讲稿共55页加权区域取样2022/10/7内蒙古大学计算机图形学50特点：接近理想直线的像素将被分配更多的灰度值。相邻的两个像素的滤波器相交，有利于缩小直线条上相邻像素的灰度差。第50页，本讲稿共55页半色调技术2022/10/7内蒙古大学计算机图形学51简单区域取样和加权区域取样技术的前提是多级灰度，利用多级灰度来提高视觉分辨率。但

27、是，若只有两级灰度呢？能否使用上述技术呢？对于给定的分辨率，通过将几个像素组合成一个单元来获得多级灰度。例：在一个显示器中将四个像素组成一个单元，可产生5种光强。第51页，本讲稿共55页半色调技术2022/10/7内蒙古大学计算机图形学52可用如下矩阵来表示：它表示黑色像素填入22个位置中的次序，每一级灰度再添上一个黑色像素就得到下一级灰度。注意：1要尽量避免连成一条直线的花样。2花样是可以选择的。单元也可以是长方形，如 第52页，本讲稿共55页半色调技术2022/10/7内蒙古大学计算机图形学53一般来说，对于两级灰度显示器可能构成的灰度数等于单元中像素个数加1单元越大，灰度级别越高它是以牺牲空间分辨率为代价的。第53页，本讲稿共55页半色调技术2022/10/7内蒙古大学计算机图形学54例：灰度级别=4,每个单元=2*2若有m级灰度，nn个像素组成一个单元，则灰度级别数为nn(m-1)+1第54页，本讲稿共55页作业二：编程实现Cohen-Sutherland裁剪算法。2022/10/7内蒙古大学计算机图形学55第55页，本讲稿共55页