第6章 从顶点到片元

1、从顶点到片元湖北工业大学计算机学院 计算机图形学二维裁剪直线段裁剪直线段裁剪直接求交算法Cohen-Sutherland算法中点分割算法参数化裁剪算法Liang-Barskey算法多边形裁剪多边形裁剪 Sutlerland_Hodgman算法 Weiler-Athenton算法 湖北工业大学计算机学院 计算机图形学裁剪 裁剪：确定图形中哪些部分落在显示区之内，哪些落在显示区之外,以便只显示落在显示区内的那部分图形。这个选择过程称为裁剪裁剪。 图形裁剪算法，直接影响图形系统的效率。湖北工业大学计算机学院 计算机图形学点的裁剪 图形裁剪中最基本的问题。 假设窗口的左下角坐标为(xL,yB),右上角

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

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

4、学计算机学院 计算机图形学 实现方法： 将窗口边线两边沿长，得到九个区域，每一个区域都用一个四位二进制数标识，直线的端点都按其所处区域赋予相应的区域码，用来标识出端点相对于裁剪矩形边界的位置。100100010101100000000100101000100110ABCDCohen-Sutherland裁剪Cohen-Sutherland算法 将区域码的各位从右到左编号，则坐标区域与各位的关系为： 上 下 右 左 X X X X任何位赋值为1，代表端点落在相应的位置上，否则该位为0。若端点在剪取矩形内，区域码为0000。如果端点落在矩形的左下角，则区域码为0101。Cohen-Sutherla

5、nd算法一旦给定所有的线段端点的区域码，就可以快速判断哪条直线完全在剪取窗口内，哪条直线完全在窗口外。所以得到一个规律：湖北工业大学计算机学院 计算机图形学Cohen-Sutherland裁剪若P1P2完全在窗口内code1=0,且code2=0,则“取”若P1P2明显在窗口外code1&code20，则“弃” 在交点处把线段分为两段。其中一段完全在窗口外，可弃之。然后对另一段重复上述处理。 编码 线段裁剪100110001010000100000010010101000110P1P2P3P4湖北工业大学计算机学院 计算机图形学Cohen-Sutherland裁剪如何判定应该与窗口的哪

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-

7、y1)/(y2-y1);具体算法见p37湖北工业大学计算机学院 计算机图形学Cohen-Sutherland直线裁剪算法小结 本算法的优点在于简单，易于实现。他可以简单的描述为将直线在窗口左边的部分删去，按左，右，下，上的顺序依次进行，处理之后，剩余部分就是可见的了。在这个算法中求交点是很重要的，他决定了算法的速度。另外，本算法对于其他形状的窗口未必同样有效。 特点：用编码方法可快速判断线段的完全可见和显然不可见。湖北工业大学计算机学院 计算机图形学中点分割裁剪算法 基本思想：从P0点出发找出离P0最近的可见点，和从P1点出发找出离P1最近的可见点。这两个可见点的连线就是原线段的可见部分。 与

8、Cohen-Sutherland算法一样首先对线段端点进行编码，并把线段与窗口的关系分为三种情况，对前两种情况，进行一样的处理；对于第三种情况，用中点分割的方法求出线段与窗口的交点。A、B分别为距P0 、 P1最近的可见点，Pm为P0P1中点。 P0P1PmAB湖北工业大学计算机学院 计算机图形学中点分割算法-求线段与窗口的交点 从P0出发找距离P0最近可见点采用中点分割方法先求出P0P1的中点Pm,若P0Pm不是显然不可见的，并且P0P1在窗口中有可见部分，则距P0最近的可见点一定落在P0Pm上，所以用P0Pm代替P0P1；否则取PmP1代替P0P1。再对新的P0P1求中点Pm。重复上述过程

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

10、靠近P0的点。图中要找的点是C点。那么P0C就是P0P1线段上的可见部分。梁友栋-Barsky算法湖北工业大学计算机学院 计算机图形学梁友栋-Barsky算法 线段的参数表示x=x0+txy=y0+ty 0=t tl,则可见线段区间 tl , tut0t1t2t301梁友栋-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为与终边

11、交点参数Qi =0 Di 0 时, 分析另一D, EFAB湖北工业大学计算机学院 计算机图形学梁友栋-Barsky算法当Qi =0时 若Di 0 时,线段不可见（如图中AB，有QR=0，DR0 时, 分析另一D, （如图中的EF就是这种情况，它使QL=0，DL0和QR=0，DR0。这时由于EF和x=xL及x=xR平行，故不必去求出EF和x=xL及x=xR的交点，而让EF和y=yT及y=yB的交点决定直线段上的可见部分。） EFAB湖北工业大学计算机学院 计算机图形学Sutherland-Hodgman算法 分割处理策略分割处理策略：将多边形关于矩形窗口的裁剪分解为多边形关于窗口四边所在直线的裁

12、剪。 流水线过程流水线过程(左上右下左上右下)：前边的结果是后边的输入。亦称亦称逐边裁逐边裁剪算法剪算法湖北工业大学计算机学院 计算机图形学Sutherland-Hodgman算法 基本思想是一次用窗口的一条边裁剪多边形。 考虑窗口的一条边以及延长线构成的裁剪线该线把平面分成两个部分:可见一侧；不可见一侧 多边形的各条边的两端点S、P。它们与裁剪线的位置关系只有四种可见一侧可见一侧可见一侧可见一侧SpSSSppp(1)(2)(3)(4)湖北工业大学计算机学院 计算机图形学Sutherland-Hodgman算法 情况（1）仅输出顶点P； 情况（2）输出0个顶点； 情况（3）输出线段SP与裁剪线

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

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

15、（裁剪窗口为任意多边形（凸、凹、带内环）的情况：的情况： 主多边形：被裁剪多边形，记为主多边形：被裁剪多边形，记为A 裁剪多边形：裁剪窗口，记为裁剪多边形：裁剪窗口，记为B 湖北工业大学计算机学院 计算机图形学Weiler-Athenton算法多边形顶点的排列顺序（使多边形区域位于有向边的左侧 ）外环：逆时针 ；内环：顺时针 主多边形和裁剪多边形把二维平面分成两部分。 内裁剪内裁剪：AB 外裁剪外裁剪：A-B裁剪结果区域的边界由A的部分边界和B的部分边界两部分构成，并且在交点处边界发生交替，即由A的边界转至B的边界，或由B的边界转至A的边界 湖北工业大学计算机学院 计算机图形学Weiler-A

16、thenton算法 如果主多边形与裁剪多边形有交点，则如果主多边形与裁剪多边形有交点，则交点成对出交点成对出现，现，它们被分为如下两类：它们被分为如下两类： 进点进点：主多边形边界由此进入裁剪多边形内：主多边形边界由此进入裁剪多边形内 如，如，I1,I3, I5, I7, I9, I11 出点出点：主多边形边界由：主多边形边界由此离开裁剪多边形区域此离开裁剪多边形区域. 如，如， I0,I2, I4, I6, I8, I10 湖北工业大学计算机学院 计算机图形学Weiler-Athenton算法1）建顶点表；2）求交点；3）裁剪 1、建立主多边形和裁剪多边的顶点表2、求主多边形和裁剪多边形的交

17、点，并将这些交点按顺序插入两多边形的顶点表中。在两多边表形顶点表中的相同交点间建立双向指针 。3、裁剪: 如果存在没有被跟踪过的交点，执行以下步骤： 湖北工业大学计算机学院 计算机图形学Weiler-Athenton算法湖北工业大学计算机学院 计算机图形学Weiler-Athenton算法 (1)建立空的裁剪结果多边形的顶点表 (2)选取任一没有被跟踪过的交点为始点，将其输出到结果多边形顶点表中 (3)如果该交点为进点，跟踪主多边形边边界；否则跟踪裁剪多边形边界 (4) 跟踪多边形边界，每遇到多边形顶点，将其输出到结果多边形顶点表中，直至遇到新的交点 (5)将该交点输出到结果多边形顶点表中，并

18、通过连接该交点的双向指针改变跟踪方向（如果上一步跟踪的是主多边形边界，现在改为跟踪裁剪多边形边界；如果上一步跟踪裁剪多边形边界，现在改为跟踪主多边形边界） (6)重复(4)、(5)直至回到起点取I7为起点，所得裁剪结果多边形I7I0q0I3I4I5I6I7。取I8为起点，所得裁剪结果多边形为I8I9I10I11I2q2I1I8。湖北工业大学计算机学院 计算机图形学Weiler-Athenton算法交点的奇异情况处理交点的奇异情况处理 1、与裁剪多边形的边重合的主多边形的边不参与求交点；2、对于顶点落在裁剪多边形的边上的主多边形的边，如果落在该裁剪边的内侧，将该顶点算作交点；而如果这条边落在该裁

19、剪边的外侧，将该顶点不看作交点 湖北工业大学计算机学院 计算机图形学反走样 用离散量表示连续量引起的失真现象称之为走样走样(aliasing) 。光栅图形的走样现象光栅图形的走样现象 阶梯状边界； 图形细节失真； 狭小图形遗失：动画序列中时隐时现，产生闪烁。湖北工业大学计算机学院 计算机图形学走样现象举例 不光滑不光滑(阶梯状）的图形边界阶梯状）的图形边界例子：PaintBrush湖北工业大学计算机学院 计算机图形学走样现象举例 图形细节失真图形细节失真湖北工业大学计算机学院 计算机图形学走样现象举例 狭小图形的遗失与动态图形的闪烁狭小图形的遗失与动态图形的闪烁湖北工业大学计算机学院 计算机图

20、形学反走样概念及方法 用于减少或消除走样现象的技术称为反反走样走样(antialiasing) 提高分辨率 简单区域取样 加权区域取样湖北工业大学计算机学院 计算机图形学提高分辨率 把显示器分辨率提高一倍，直线经过两倍的象素，锯齿也增加一倍，但同时每个阶梯的宽度也减小了一倍，所以显示出的直线段看起来就平直光滑了一些。湖北工业大学计算机学院 计算机图形学提高分辨率 方法简单，但代价非常大。显示器的水平、竖直分辩率各提高一倍，则显示器的点距减少一倍，帧缓存容量则增加到原来的4倍，而扫描转换同样大小的图元却要花4倍时间。 而且它也只能减轻而不能消除锯齿问题另一种方法（软件方法）：用较高的分辨率的显示

21、模式下计算，（对各自像属下计算，再求（非）加权平均的颜色值），在较低的分辨率模式下显示。只能减轻而不能消除锯齿问题。湖北工业大学计算机学院 计算机图形学软件方法1 把每个像素分为四个子像素，扫描转换算法求得各子像素的灰度值，然后对四像素的灰度值简单平均，作为该像素的灰度值。湖北工业大学计算机学院 计算机图形学软件方法2 设 分 辨 率 为 m n , 把 显 示 窗 口 分 为(2m+1)(2n+1)个子像素，对每个子像素进行灰度值计算，然后根据权值表所规定的权值，对位于像素中心及四周的九个子像素加权平均，作为显示像素的颜色。 设m=4,n=3湖北工业大学计算机学院 计算机图形学简单区域取样

22、方法由来方法由来 两点假设两点假设1、象素是数学上抽象的点，它的面积为、象素是数学上抽象的点，它的面积为0，它的亮度由，它的亮度由覆盖该点的图形的亮度所决定；覆盖该点的图形的亮度所决定；2、直线段是数学上抽象直线段，它的宽度为、直线段是数学上抽象直线段，它的宽度为0。 现实现实 像素的面积不为像素的面积不为0； 直线段的宽度至少为直线段的宽度至少为1个像素；个像素； 假设与现实的矛盾是导致混淆出现的原因之一假设与现实的矛盾是导致混淆出现的原因之一湖北工业大学计算机学院 计算机图形学简单区域取样 解决方法：改变直线段模型，由此产生算法解决方法：改变直线段模型，由此产生算法 方法步骤方法步骤：1、

23、将直线段看作具有一定宽度的狭长矩形；、将直线段看作具有一定宽度的狭长矩形；2、当直线段与某象素有交时，求出两者相交区域的面积；、当直线段与某象素有交时，求出两者相交区域的面积；3、根据相交区域的面积，确定该象素的亮度值、根据相交区域的面积，确定该象素的亮度值 湖北工业大学计算机学院 计算机图形学简单区域取样 基本思想：每个象素是一个具有一定面积的小区域，将直线段看作具有一定宽度的狭长矩形。当直线段与象素有交时，求出两者相交区域的面积，然后根据相交区域面积的大小确定该象素的亮度值。 有宽度的线条轮廓 象素相交的五种情况及用于计算面积的量0112233445567891011DD/mDm(1)(2

24、)(3)(4)(5)湖北工业大学计算机学院 计算机图形学简单区域取样 面积计算情况（5)阴影面积为：D2/2m；情况（4)阴影面积为：D - m/2；情况阴影面积为：1 - D2/m 为了简化计算可以采用离散的方法湖北工业大学计算机学院 计算机图形学简单区域取样 求相交区域的近似面积的离散计算方法求相交区域的近似面积的离散计算方法 1、将屏幕象素分割成、将屏幕象素分割成n个更小的子象素；个更小的子象素；2、计算中心点落在直线段内的子象素的个数，记为、计算中心点落在直线段内的子象素的个数，记为k，3、k/n为线段与象素相交区域面积的近似值为线段与象素相交区域面积的近似值 目的：简化计算n = 1

25、6, k = 3近似面积 = 3/16湖北工业大学计算机学院 计算机图形学简单区域取样 简单区域取样采用的是一个盒式滤波器，它是一个二维加权函数，以w表示。 w =1 若在当前像素所代表的正方形上 w =0 其它区域上 直线条经过该像素时，该像素的灰度值可以通过在像素与直线条的相交区域上对w求积分获得。 此时，面积值=体积值简单区域取样 缺点： 象素的亮度与相交区域的面积成正比，而与相交区域落在象素内的位置无关，这仍然会导致锯齿效应。 直线条上沿理想直线方向的相邻两个象素有时会有较大的灰度差。边缘填充算法求余运算求余运算：假定A为一个正整数，则M的余定义为A M, 记为 。计算机中取A为n位能

26、表示的最大整数。即，A=0 xFFFFFFFFA=0 xFFFFFFFF由来由来：光栅图形中，如果某区域已着上值为M的颜色值做偶数次求余运算，该区域颜色不变；而做奇数次求余运算，则该区域颜色变为值为 的颜色。这一规律应用于多边形扫描转换，就为边缘填充算法。算法基本思想算法基本思想：对于每条扫描线和每条多边形边的交点，将该扫描线上交点右方的所有象素取余。MM1、将当前扫描线上的 所有象素着上 颜色；2、求余：for(i = 0;i = m; i+)在当前扫描线上， 从横坐标为Xi的交 点向右求余； M算法1（以扫描线为中心的边缘填充算法）1、将绘图窗口的背景色置为 ；2、对多边形的每一条非水平边

27、做：从该边上的每个象素开始向右求余；M算法2（以边为中心的边缘填充算法）算法2（以边为中心的边缘填充算法）边缘填充算法 适合用于具有帧缓存的图形系统。处理后，按扫描线顺序读出帧缓存的内容，送入显示设备。 优点：算法简单 缺点：对于复杂图形，每一象素可能被访问多次，输入/输出的量比有序边表算法大得多。 引入栅栏，以减少填充算法访问象素的次数。 栅栏：与扫描线垂直的直线，通常过一顶点，且把多边形分为左右二半。 基本思想：扫描线与多边形的边求交，将交点与栅栏之间的象素取补。 减少了象素重复访问数目，但不彻底。栅栏填充算法1. 对多边形的每一条边进行扫描转换，即对多边形边界所经过的象素作一个边界标志。

28、2.填充。对每条与多边形相交的扫描线，按从左到右的顺序，逐个访问该扫描线上的象素。取一个布尔变量inside来指示当前点的状态，若点在多边形内，则inside为真。若点在多边形外，则inside为假。Inside 的初始值为假，每当当前访问象素为被打上标志的点，就把inside取反。对未打标志的点，inside不变。边界标志算法边界标志算法:算法过程void edgemark_fill(polydef, color)多边形定义 polydef； int color; 对多边形polydef 每条边进行直线扫描转换； inside = FALSE; for (每条与多边形polydef相交的扫描

29、线y ) for (扫描线上每个象素x ) if(象素 x 被打上边标志) inside = ! (inside); if(inside！= FALSE) drawpixel (x, y, color); else drawpixel (x, y, background); 边界标志算法 用软件实现时，扫描线算法与边界标志算法的执行速度几乎相同， 但由于边界标志算法不必建立维护边表以及对它进行排序，所以边界标志算法更适合硬件实现，这时它的执行速度比有序边表算法快一至两个数量级。边界标志算法 思考：如何处理边界的交点个数使其成为偶数？区域填充算法 区域区域指已经表示成点阵形式的填充图形，它是象素

30、的集合。 区域填充区域填充指先将区域的一点赋予指定的颜色，然后将该颜色扩展到整个区域的过程。区域填充算法要求区域是连通的区域填充 表示方法：表示方法：内点表示、边界表示 内点表示内点表示枚举处区域内部的所有像素内部的所有像素着同一个颜色边界像素着与内部像素不同的颜色 边界表示边界表示枚举出边界上所有的像素边界上的所有像素着同一颜色内部像素着与边界像素不同的颜色区域填充区域填充要求区域是连通的区域填充要求区域是连通的 连通性连通性 4连通、8连通 4 4连通：连通： 8 8连通连通区域填充 4 4连通与连通与8 8连通区域的区别连通区域的区别连通性：连通性： 4 4连通可看作连通可看作8 8连通

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

32、4构 成 ，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,oldColor,newColor); FloodFill4(x-1,y,oldColor,newColor); FloodFill4(x+1,y,oldColor,newColor); /*end of FloodF