第二章光栅图形学ppt课件

1、计算机图形学福建师范大学计算机图形学翁彬计算机图形学福建师范大学第2章 光栅图形学计算机图形学福建师范大学 什么是光栅图形学？ 光栅显示器 图形光栅化、 光栅化图形的处理 计算机图形学福建师范大学光栅图形学的研究内容光栅图形学的研究内容2.1直线段的扫描转换算法直线段的扫描转换算法2.2圆弧的扫描转换算法圆弧的扫描转换算法2.3多边形的扫描转换与区域填充多边形的扫描转换与区域填充2.4字符字符2.5裁剪裁剪2.6反走样反走样2.7消隐消隐计算机图形学福建师范大学2.1 直线段的扫描转换算法直线的扫描转换：确定最佳逼近于该直线直线的扫描转换：确定最佳逼近于该直线的一组象素，并且按扫描线顺序，对这

2、些的一组象素，并且按扫描线顺序，对这些象素进行写操作。象素进行写操作。三个常用算法：三个常用算法：数值微分法数值微分法DDA）中点画线法中点画线法Bresenham算法。算法。计算机图形学福建师范大学2.1.1 数值微分(DDA)法 基本思想 已知过端点 的直线段L： 直线斜率为 从 的左端点 开场，向 右端点步进。步长=1(个象素)，计算相应的y坐标 ；取象素点(x, round(y)作为当前点的坐标。 这种方法直观，但效率太低，因为每一步需要一次浮点乘法、一次加法和一次舍入运算。0101xxyyk),(),(111000yxPyxPbkxyx0 xxbkxy计算机图形学福建师范大学2.1.

3、1 数值微分(DDA)法 作为最底层的光栅图形算法，在通常的CAD/图形系统中，会被大量应用，因此，哪怕节约一个加法或减法，也是很了不起的改进。 由此出发点，导致增量算法的思想。 增量算法：在一个迭代算法中，如果每一步的x、y值是用前一步的值加上一个增量来获得，则称为增量算法。计算机图形学福建师范大学2.1.1 数值微分(DDA)法 计算 当 时; 即：当x每递增1，y递增k(即直线斜率)； xkyxkbkxbkxyiiii 111xkyyii1计算机图形学福建师范大学2.1.1 数值微分(DDA)法 例：画直线段 k = 0.4 x y int(y+0.5) y+0.5 0 0 0 0 注：

4、网格点表示象素)2 , 5()0 , 0(10PP0 1 2 3 4 5321Line: P0(0, 0)- P1(5, 2)计算机图形学福建师范大学2.1.1 数值微分(DDA)法 例：画直线段 x int(y+0.5) y+0.5 0 0 0 1 0 0.4+0.5 2 1 0.8+0.5 3 1 1.2+0.5 4 2 1.6+0.5 5 2 2.0+0.5 注：网格点表示象素0 1 2 3 4 5321Line: P0(0, 0)- P1(5, 2)2 , 5()0 , 0(10PP计算机图形学福建师范大学2.1.1 数值微分(DDA)法 void DDALine(int x0,int

5、 y0,int x1,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; 计算机图形学福建师范大学2.1.1 数值微分(DDA)法 注意上述分析的算法仅适用于k 1的情形。在这种情况下，x每增加1, y最多增加1。 问题： 当 k 1时，会如何？(答案见下页) 0 1 2 3 4 5321Line: P0(0, 0)- P1(5, 2)k DDA算法采用两点式，可否采用

6、其他的直线表示方式？计算机图形学福建师范大学2.1.2 中点画线法基本思想当前象素点为(xp, yp) 。下一个象素点为P1 或P2 。设M=(xp+1, yp+0.5)，为p1与p2之中点，Q为理想直线与x=xp+1垂线的交点。将Q与M的y坐标进行比较。当M在Q的下方- P2离直线更近更近-取P2 。M在Q的上方- P1离直线更近更近-取P1M与Q重合， P1、P2任取一点。P=(xp,yp)QP2P1计算机图形学福建师范大学2.1.2 中点画线法问题：如何判断M与Q点的关系？P=(xp,yp)QP2P1计算机图形学福建师范大学2.1.2 中点画线法 假设直线方程为：F(x,y)=ax+by

7、+c=0 其中a=y0-y1, b=x1-x0, c=x0y1-x1y0 由常识知： 欲判断M点是在Q点上方还是在Q点下方，只需把M代入F(x,y),并检查它的符号。点在直线下方点在直线上方点在直线上面0,0,0,yxFyxFyxFP=(xp,yp)QP2P1计算机图形学福建师范大学2.1.2 中点画线法构造判别式:d=F(M)=F(xp+1,yp+0.5) =a(xp+1)+b(yp+0.5)+c 其中a=y0-y1, b=x1-x0, c=x0y1-x1y0当d0，M在L(Q点)上方，取右方P1为下一个象素；当d=0，选P1或P2均可，约定取P1为下一个象素；P=(xp,yp)QP2P1计

8、算机图形学福建师范大学2.1.2 中点画线法 但这样做，每一个象素的计算量是4个加法，两个乘法。 d=a(xp+1)+b(yp+0.5)+c计算机图形学福建师范大学2.1.2 中点画线法 如果也采用增量算法呢？计算机图形学福建师范大学2.1.2 中点画线法 d是xp, yp的线性函数，因此可采用增量计算，提高运算效率。 d=a(xp+1)+b(yp+0.5)+c计算机图形学福建师范大学2.1.2 中点画线法若当前象素处于d0情况，则取正右方象素P1 (xp+1, yp ), 要判下一个象素位置，应计算 d1=F(xp+2, yp+0.5) =a(xp+2)+b(yp+0.5)+c=d+a； 增

9、量为ad=a(xp+1)+b(yp+0.5)+cP=(xp,yp)QP2P1计算机图形学福建师范大学2.1.2 中点画线法若d0时，则取右上方象素P2 (xp+1, yp+1)。要判断再下一象素，则要计算 d2= F(xp+2, yp+1.5) =a(xp+2)+b(yp+1.5)+c=d+a+b ； 增量为ab d=a(xp+1)+b(yp+0.5)+cP=(xp,yp)QP2P1计算机图形学福建师范大学2.1.2 中点画线法 至此，至少新算法可以和DDA算法一样好。 能否再做改进？计算机图形学福建师范大学2.1.2 中点画线法 能否实现整数运算？计算机图形学福建师范大学2.1.2 中点画线

10、法 画线从(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来摆脱小数，提高效率。 令 d0=2a+b, d1=2a, d2=2a+2b,我们有如下算法 。P=(xp,yp)QP2P1计算机图形学福建师范大学2.1.2 中点画线法void Midpoint Line (int x0,int y0,int x1, int y1,int color) int a, b, d1, d2, d, x, y; a=y

11、0-y1, b=x1-x0, d=2*a+b; d1=2*a, d2=2* (a+b); x=x0, y=y0; drawpixel(x, y, color); while (xx1) if (d0) x+, y+, d+=d2; else x+, d+=d1; drawpixel (x, y, color); /* while */ /* mid PointLine */计算机图形学福建师范大学2.1.2 中点画线法 例：用中点画线法 ixiyid 1 001 2 10-3 3 213 4 31-1 5 4250 1 2 3 4 5321)2 , 5()0 , 0(10PP5, 20110

12、xxbyya, 6)(2, 42, 12210badadbad计算机图形学福建师范大学中点画线法小结 中点与交点位置来判断象素选取 引入直接的隐式方程F(x,y)=ax+by+c=0 但计算量大，故又改进为增量算法此处，增量分两种情况） 为进一步提高效率，修改为全是整数计算的算法（ 2d代替d ，同时增量也做相应调整）计算机图形学福建师范大学2.1.2 中点画线法思考题：P55 2-2 用中点画线法扫描转换从点1,0到4,7经过的直线段，并给出每一步的判别值。计算机图形学福建师范大学 DDA算法采用点斜式，中点法采用隐式表示。 中点法可以有整数算法。 其他表示可以推出整数算法吗？计算机图形学福

13、建师范大学2.1.3 Bresenham算法基本思想过各行各列象素中心构造一组虚拟网格线。按直线从起点到终点的顺序计算直线与各垂直网格线的交点，然后根据误差项的符号确定该列象素中与此交点最近的象素。dddd计算机图形学福建师范大学2.1.3 Bresenham算法设直线方程为： ，其中k=dy/dx。 因为直线的起始点在象素中心，所以误差项d的初值d00。X下标每增加1，d的值相应递增直线的斜率值k，即ddk。当d0.5时，选择当前象素的右上方象素（ ），修改比较的基点为改点，即将d-1而当d0.5时，选择当前象素的右方象素（ ），此时不改变基点为方便计算，令ed-0.5，e的初值为-0.5，

14、增量为k。当e0时，取当前象素xi，yi的右上方象素（ ）；而当e0时，更接近于右方象素（ ）。kyxxkyyiiiii)(111,1iiyxiiyx,11,1iiyxiiyx,1计算机图形学福建师范大学2.1.3 Bresenham算法例：Line: P0(0, 0), P1(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 e每次加k，若e大于零则y加1且e减1， 若e小于零则不变0 1 2 3 4 5321计算机图形学福建师范大学2.1.3 Bresenham算法 void Bresenh

15、amline (int x0,int y0,int x1, int y1,int color) int x, y, dx, dy; float k, e; dx = x1-x0, dy = y1- y0, k=dy/dx; e=-0.5, x=x0, y=y0; for (i=0; idx; i+) drawpixel (x, y, color); x=x+1，e=e+k; if (e0) y+, e=e-1; 计算机图形学福建师范大学2.1.3 Bresenham算法 可以改用整数以避免除法。由于算法中只用到误差项的符号，因此可作如下替换： dxee*2计算机图形学福建师范大学2.1.3 B

16、resenham算法 void Bresenhamline (int x0,int y0,int x1, int y1,int color) int x, y, dx, dy,e; dx = x1-x0, dy = y1- y0; e=- dx, x=x0, y=y0; for (i=0; idx; i+) drawpixel (x, y, color); x=x+1，e=e+2*dy; if (e0) y+, e=e-2*dx; int x, y, dx, dy;float k, e;dx = x1-x0, dy = y1- y0; k=dy/dx,e=-0.5;x=x0, y=y0;for

17、 (i=0; idx; i+) drawpixel (x, y, color); x=x+1，e=e+k; if (e0) y+, e=e-1; 计算机图形学福建师范大学2.1.3 Bresenham算法 y每次增k 误差项每次也增k （同DDA算法） 经过 交点 与 基点 的距离 d 来判断 为了用正负号判断， ed-0.5 为了变为整数算法 最终，Bresenham算法也是每个象素，需一个整数算法， 其优点是可以用于其他二次曲线。dxee*2计算机图形学福建师范大学2.2 圆弧的扫描转换算法 圆的特征：八对称性。只要扫描转换八分圆的特征：八对称性。只要扫描转换八分之一圆弧，就可以求出整个圆

18、弧的象素集之一圆弧，就可以求出整个圆弧的象素集 中点画圆法中点画圆法 考虑中心在原点，半径为考虑中心在原点，半径为R 的第二个的第二个8分圆，分圆， 构造判别式圆方程）构造判别式圆方程）222)5 . 0() 1()5 . 0, 1()(RyxyxFMFdppppP=(xp,yp)P1P2M计算机图形学福建师范大学2.2 圆弧的扫描转换算法假设 d=0, 则应取P2为下一象素，而且下一象素的判别式为 第 一个象素是0,R），判别式d的初始值为32) 5 . 0()2() 5 . 0, 2(222pppppxdRyxyxFd5)( 2) 5 . 1() 2() 5 . 1, 2(222ppppp

19、pyxdRyxyxFdRRFd25. 1)5 . 0, 1 (0计算机图形学福建师范大学2.2 圆弧的扫描转换算法 MidPointCircle(int r int color) int x,y; float d; x=0; y=r; d=1.25-r; circlepoints (x,y,color); /显示圆弧上的八个对称点 while(x=y) if(d0时 ，0时） 为了改为整数算法 e=d-0.25代替d计算机图形学福建师范大学小结 2.1 直线段的扫描转换算法 2.1.1 数值微分(DDA)法 2.1.2 中点画线法 2.1.3 Bresenham算法 2.2 圆弧的扫描转换算法

20、计算机图形学福建师范大学2.3 多边形的扫描转换与区域填充 多边形的表示方法多边形的表示方法 顶点表示顶点表示 点阵表示点阵表示 顶点表示：用多边形顶点的序列来刻划顶点表示：用多边形顶点的序列来刻划多边形。直观、几何意义强、占内存少；多边形。直观、几何意义强、占内存少；不能直接用于面着色。不能直接用于面着色。 点阵表示：用位于多边形内的象素的集点阵表示：用位于多边形内的象素的集合来刻划多边形。失去了许多重要的几合来刻划多边形。失去了许多重要的几何信息；便于运用帧缓冲存储器表示图何信息；便于运用帧缓冲存储器表示图形，易于面着色。形，易于面着色。计算机图形学福建师范大学2.3 多边形的扫描转换与区

21、域填充 多边形的扫描转换：把多边形的顶点表多边形的扫描转换：把多边形的顶点表示转换为点阵表示，也就是从多边形的示转换为点阵表示，也就是从多边形的给定边界出发，求出位于其内部的各个给定边界出发，求出位于其内部的各个象素，并给帧缓冲器内的各个对应元素象素，并给帧缓冲器内的各个对应元素设置相应的灰度和颜色，通常称这种转设置相应的灰度和颜色，通常称这种转换为多边形的扫描转换。换为多边形的扫描转换。计算机图形学福建师范大学2.3 多边形的扫描转换与区域填充 区域指已经表示成点阵形式的填充图形，区域指已经表示成点阵形式的填充图形，它是象素的集合。它是象素的集合。 区域填充指先将区域的一点赋予指定的区域填充

22、指先将区域的一点赋予指定的颜色，然后将该颜色扩展到整个区域的颜色，然后将该颜色扩展到整个区域的过程。区域填充算法要求区域是连通的。过程。区域填充算法要求区域是连通的。计算机图形学福建师范大学2.3 多边形的扫描转换与区域填充 区域表示方法：内点表示、边界表示区域表示方法：内点表示、边界表示 内点表示内点表示 枚举出区域内部的所有像素枚举出区域内部的所有像素 内部的所有像素着同一个颜色内部的所有像素着同一个颜色 边界像素着与内部像素不同的边界像素着与内部像素不同的 颜色颜色 边界表示边界表示 枚举出边界上所有的像素枚举出边界上所有的像素 边界上的所有像素着同一颜色边界上的所有像素着同一颜色 内部

23、像素着与边界像素不同的颜色内部像素着与边界像素不同的颜色计算机图形学福建师范大学 多边形分为凸多边形、凹多边形、含内环的多边形。计算机图形学福建师范大学逐点判断算法 逐点判断算法：逐个像素判别其是否位于多边形内部 判断一个点是否位于多边形内部：射线法 从当前像素发射一条射线，计算射线与多边形的交点个数 内部：奇数个交点 外部：偶数个交点计算机图形学福建师范大学逐点判断算法判断一点是否位于多边形内部？计算机图形学福建师范大学逐点判断算法 算法描述 for(y=0; y=y_resolution; y+) for(x=0; x i 结点的x值递增x； /* polyfill */计算机图形学福建师

24、范大学思考题 已知多边形P=(P0P1P2P3P4P5P6P0)；其各边坐标分别为 （2，5）（2，10）（9，6）（16，11）（16，4）（12，2）（7，2） 建立其新边表和活性边表计算机图形学福建师范大学新边表计算机图形学福建师范大学y=3y=8活动边表的例子计算机图形学福建师范大学扫描线算法小结 建立新边表 按照扫描线顺序处理 每条扫描线构造活性边表x递增插入排序） 中间考虑交点取舍 根据当前活性边表选取像素进行填充x方向） 从活性边表中删除y max= i 的结点计算机图形学福建师范大学2.3.1.2边界标志算法 基本思想： 帧缓冲器中对多边形的每条边进行直线扫描转换，亦即对多边形

25、边界所经过的象素打上标志。 填充。对每条与多边形相交的扫描线，按从左到右的顺序，逐个访问该扫描线上的象素。 取一个布尔变量inside来指示当前点的状态，若点在多边形内，则inside为真。若点在多边形外，则inside为假。 Inside 的初始值为假，每当当前访问象素为被打上标志的点，就把inside取反。对未打标志的点，inside不变。计算机图形学福建师范大学边标志算法-例子多边形P0P1P2P3P4顶点坐标为2,1）,(2,7),(8,5),(8,1),(6,4),以扫描线Y=3为例说明填充过程。开始时inside=0.1对于X=0，该像素未置成边界值，inside=0，该点为背景色

26、；2对于X=1，同上；3对于X=2，该像素已置成边界色，inside取反后为1，该点被置成多边形颜色；4对于X=3，4，像素未置成边界色，由于inside=1，所以点被置成多边形颜色；5对于X=5，像素被置成边界色，inside取反后为0，该点被置成背景色；6对于X=6，像素未置成边界色，由于inside=0，所以点被置成背景色；7对于X=7，像素被置成边界色，inside取反后为1，该点被置成多边形颜色；8对于X=8，像素被置成边界色，inside取反后为0，该点被置成背景色；计算机图形学福建师范大学算法过程void edgemark_fill(polydef, color)多边形定义 po

27、lydef； int color; 对多边形polydef 每条边进行直线扫描转换； for (每条与多边形polydef相交的扫描线y ) inside = FALSE; for (扫描线上每个象素x ) if(象素 x 被打上边标志) inside = ! (inside); if(inside！= FALSE) drawpixel (x, y, color); else drawpixel (x, y, background); 计算机图形学福建师范大学2.3.1.2边界标志算法 用软件实现时，扫描线算法与边界标志算法的执行速度几乎相同， 但由于边界标志算法不必建立维护边表以及对它进行排

28、序，所以边界标志算法更适合硬件实现，这时它的执行速度比有序边表算法快一至两个数量级。计算机图形学福建师范大学2.3.2区域填充算法 区域指已经表示成点阵形式的填充图形，区域指已经表示成点阵形式的填充图形，它是象素的集合。它是象素的集合。 区域填充指先将区域的一点赋予指定的区域填充指先将区域的一点赋予指定的颜色，然后将该颜色扩展到整个区域的颜色，然后将该颜色扩展到整个区域的过程。区域填充算法要求区域是连通的。过程。区域填充算法要求区域是连通的。计算机图形学福建师范大学2.3.2区域填充算法 区域表示方法：内点表示、边界表示区域表示方法：内点表示、边界表示 内点表示内点表示 枚举出区域内部的所有像

29、素枚举出区域内部的所有像素 内部的所有像素着同一个颜色内部的所有像素着同一个颜色 边界像素着与内部像素不同的边界像素着与内部像素不同的 颜色颜色 边界表示边界表示 枚举出边界上所有的像素枚举出边界上所有的像素 边界上的所有像素着同一颜色边界上的所有像素着同一颜色 内部像素着与边界像素不同的颜色内部像素着与边界像素不同的颜色表示内点表示边界点计算机图形学福建师范大学2.3.2区域填充算法 区域填充要求区域是连通的区域填充要求区域是连通的 连通性连通性: 4: 4连通、连通、8 8连通连通 4 4连通：连通： 8 8连通连通计算机图形学福建师范大学2.3.2区域填充算法 4 4连通与连通与8 8连

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

31、置成多边形色，则把该象素入栈。2.3.2.1区域填充的递归算法（种子填充算法）计算机图形学福建师范大学种子填充算法例子 多 边 形 由 P 0 P 1 P 2 P 3 P 4 构 成 ，P0(1,5)P1(5,5)P2(7,3)P3(7,1)P4(1,1) 设种子点为3，3），搜索的方向是上、下、左、右。依此类推，最后像素被选中并填充的次序如图中箭头所示 计算机图形学福建师范大学2.3.2.1区域填充的递归算法 内点表示的内点表示的4连通区域的递归填充算法连通区域的递归填充算法: void FloodFill4(int x,int y,int oldcolor,int newcolor) if

32、(getpixel(x,y)=oldcolor) /属于区域内点属于区域内点oldcolordrawpixel(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); 计算机图形学福建师范大学2.3.2.1区域填充的递归算法 边界表示的边界表示的4连通区域的递归填充算法连通区域的递归填充算法: void BoundaryFill4(in

33、t x,int y,int boundarycolor,int newcolor) int color=getpixel(x,y);if(color!=newcolor & color!=boundarycolor)drawpixel(x,y,newcolor);BoundaryFill4 (x,y+1, boundarycolor,newcolor);BoundaryFill4 (x,y-1, boundarycolor,newcolor);BoundaryFill4 (x-1,y, boundarycolor,newcolor);BoundaryFill4 (x+1,y, boun

34、darycolor,newcolor); 计算机图形学福建师范大学 该算法也可以填充有孔区域。该算法也可以填充有孔区域。 缺陷：缺陷： (1) (1) 有些象素会入栈多次，降低算法效率；栈有些象素会入栈多次，降低算法效率；栈结构占空间。结构占空间。 (2) (2) 递归执行，算法简单，但效率不高，区域递归执行，算法简单，但效率不高，区域内每一象素都引起一次递归，进内每一象素都引起一次递归，进/ /出栈，费时出栈，费时费内存。费内存。 改进算法，减少递归次数，提高效率。改进算法，减少递归次数，提高效率。解决方法是用扫描线填充算法解决方法是用扫描线填充算法2.3.2.1区域填充的递归算法计算机图形

35、学福建师范大学2.3.2.2区域填充的扫描线算法 目的：减少递归层次 适用于内点表示的4连通区域 算法步骤： 首先填充种子点所在扫描线上的位于给定区域的一个区段 然后确定与这一区段相连通的上、下两条扫描线上位于给定区域内的区段，并依次保存下来。 反复这个过程，直到填充结束。计算机图形学福建师范大学2.3.2.2区域填充的扫描线算法 (1)初始化：堆栈置空。将种子点x，y入栈。 (2)出栈：若栈空则结束。否则取栈顶元素x，y），以y作为当前扫描线。 (3)填充并确定种子点所在区段：从种子点x，y出发，沿当前扫描线向左、右两个方向填充，直到边界。分别标记区段的左、右端点坐标为xl和xr。 (4)并

36、确定新的种子点：在区间xl，xr中检查与当前扫描线y上、下相邻的两条扫描线上的象素。若存在非边界、未填充的象素，则把每一区间的最右象素作为种子点压入堆栈，返回第2步。 上述算法对于每一个待填充区段，只需压栈一次；因此，扫描线填充算法提高了区域填充的效率。计算机图形学福建师范大学扫描线算法分析举例分析） 该算法也可以填充有孔区域。 像素中的序号标指它所在区段位于堆栈中的位置计算机图形学福建师范大学扫描线算法分析举例分析）计算机图形学福建师范大学扫描线算法分析举例分析）计算机图形学福建师范大学扫描线算法分析举例分析）计算机图形学福建师范大学多边形扫描转换与区域填充方法比较联络：都是光栅图形面着色，

37、用于真实感图形显示。可相互转换。多边形的扫描转换转化为区域填充问题：当给定多边形内一点为种子点，并用Bresenham或DDA算法将多边形的边界表示成八连通区域后，则多边形的扫描转换转化为区域填充。区域填充转化为多边形的扫描转换；若已知给定多边形的顶点，则区域填充转化为多边形的扫描转换。 计算机图形学福建师范大学多边形扫描转换与区域填充方法比较 不同点： 1.基本思想不同；前者是顶点表示转换成点阵表示，后者只改变区域内填充颜色，没有改变表示方法。 2.对边界的要求不同 前者只要求扫描线与多边形边界交点个数为偶数。后者：区域封闭，防止递归填充跨界。 3.基本的条件不同 前者：从边界顶点信息出发。

38、 后者：区域内种子点。计算机图形学福建师范大学第二章 光栅图形学 2.1直线段的扫描转换算法 2.2圆弧的扫描转换算法 2.3多边形的扫描转换与区域填充 2.4字符 2.5裁剪 2.6反走样 2.7消隐计算机图形学福建师范大学2.4 字符 字符指数字、字母、汉字等符号。 计算机中字符由一个数字编码唯一标识。 国际上最流行的字符集：“美国信息交换用标准代码集”，简称ASCII码。它是用7位二进制数进行编码表示128个字符；包括字母、标点、运算符以及一些特殊符号。计算机图形学福建师范大学 汉字编码的国家标准字符集：GB231280。该字符集分为94个区，94个位，每个符号由一个区码和一个位码共同标

39、识。区码和位码各用一个字节表示。 为了能够区分ASCII码与汉字编码，采用字节的最高位来标识：最高位为0表示ASCII码；最高位为1表示表示汉字编码。计算机图形学福建师范大学 字库：为了在显示器等输出设备上输出字符，系统中必须装备有相应的字库。字库中存储了每个字符的形状信息，字库分为矢量型和点阵型两种。计算机图形学福建师范大学 点阵字符点阵字符: 每个字符由一个位图表示，该位每个字符由一个位图表示，该位为为1表示字符的笔画经过此位，对应于此位表示字符的笔画经过此位，对应于此位的象素应置为字符颜色。该位为的象素应置为字符颜色。该位为0表示字符表示字符的笔画不经过此位，对应于此位的象素应的笔画不经

40、过此位，对应于此位的象素应置为背景颜色。置为背景颜色。计算机图形学福建师范大学 点阵字符 点阵字库中的位图表示1111110001010101010101010111110001010101010101011111110000000000计算机图形学福建师范大学 在实际应用中，有多种字体如宋体、楷体等），每种字体又有多种大小型号，因此字库的存储空间是很庞大的。解决这个问题一般采用压缩技术。 点阵字符的显示分为两步。首先从字库中将它的位图检索出来。然后将检索到的位图写到帧缓冲器中。计算机图形学福建师范大学 矢量字符矢量字符:记录字符的笔画信息，而不是整记录字符的笔画信息，而不是整个位图，具有存储

41、空间小，美观、变换方个位图，具有存储空间小，美观、变换方便等优点。对于字符的旋转、缩放等变换，便等优点。对于字符的旋转、缩放等变换， 点阵字符的变换需要对表示字符位图中的点阵字符的变换需要对表示字符位图中的每一象素进行；每一象素进行； 矢量字符的变换只要对其笔画端点进行变矢量字符的变换只要对其笔画端点进行变换就可以了。矢量字符的显示也分为两步。换就可以了。矢量字符的显示也分为两步。 计算机图形学福建师范大学 显示：首先从字库中将它的字符信息。然后取出端点坐标，对其进行适当的几何变换，再根据各端点的标志显示出字符。 点阵字符 点阵字库中的位图表示 矢量轮廓字符111111000101010101

42、0101010111110001010101010101011111110000000000计算机图形学福建师范大学 特点： 点阵字符：存储量大，易于显示 矢量字符：存储量小，美观，变换方便; 但需要光栅化后才能显示。计算机图形学福建师范大学字符属性字符属性字体 宋体 仿宋体 楷体 黑体 隶书字高 宋体 宋体 宋体 宋体字宽字倾斜角倾斜 倾斜对齐 (左对齐、中心对齐、右对齐)字色 红色、绿色、蓝色 大 海 大 海 大 海 大 海计算机图形学福建师范大学2.5 裁剪 裁剪：确定图形中哪些部分落在显示区之内，哪些落在显示区之外,以便只显示落在显示区内的那部分图形。这个选择过程称为裁剪。 在使用计算

43、机处理图形信息时，计算机内部存储的图形往往比较大，而屏幕显示的只是图的一部分。计算机图形学福建师范大学 问：为什么要裁减，直接处理呢？即：在绘制写帧缓存时再处理？ 计算机图形学福建师范大学 最简单的裁剪方法是把各种图形扫描转换为点之后，再判断各点是否在窗内。但那样太费时，一般不可取。这是因为有些图形组成部分全部在窗口外，可以完全排除，不必进行扫描转换。所以一般采用先裁剪再扫描转换的方法。计算机图形学福建师范大学2.5.1直线段裁剪 直线段裁剪算法是复杂图元裁剪的基础。复杂的曲线可以通过折线段来近似，从而裁剪问题也可以化为直线段的裁剪问题。 2.5.1.1Cohen-Sutherland 2.5

44、.1.2中点分割算法 2.5.1.3梁友栋Barskey算法。计算机图形学福建师范大学2.5.1.1 Cohen-Sutherland裁剪基本思想：对于每条线段P1P2分为三种情况处理分为三种情况处理:（1若P1P2完全在窗口内，则显示该线段P1P2简称“取之。（2若P1P2明显在窗口外，则丢弃该线段，简称“弃之。（3若线段不满足“取或 “弃的条件，则在交点处把线段分为两段。其中一段完全在窗口外，可弃之。然后对另一段重复上述处理。计算机图形学福建师范大学 为快速判断，采用如下编码方法： 每个区域赋予4位编码otheryyCotheryyCbt0101minmaxotherxxCotherxxC

45、lr0101minmaxlrbtCCCC计算机图形学福建师范大学 编码 线段裁剪100110001010000100000010010101000110P1P2P3P4计算机图形学福建师范大学若P1P2完全在窗口内code1=0,且code2=0,那么“取”若P1P2明显在窗口外,code1&code20 （？），那么“弃” 在交点处把线段分为两段。其中一段完全在窗口外，可弃之。然后对另一段重复上述处理。 计算机图形学福建师范大学 计算线段P1(x1,y1)P2(x2,y2)与窗口边界的交点if(LEFT&code !=0)x=XL;y=y1+(y2-y1)*(XL-x1)/(

46、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);计算机图形学福建师范大学 例如计算机图形学福建师范大学 编码的思想在图形学中非常重要。 Sutherland：Coons奖, 图灵奖, IEEE 计算机先驱奖。计算机图形学福建师范大学2.5.1.2 中点分割裁剪

47、算法 基本思想： 与前一种Cohen-Sutherland算法一样首先对线段端点进行编码，并把线段与窗口的关系分为三种情况: 全在、完全不在和线段和窗口有交。对前两种情况，进行一样的处理。 对于第三种情况，用中点分割的方法求出线段与窗口的交点。计算机图形学福建师范大学求线段与窗口的交点 A、B分别为距P0、P1最近的可见点，Pm为P0P1中点P0P1PmAB计算机图形学福建师范大学 从 出发找最近可见点的方法 先求出 的中点 假设 不是显然不可见的，并且 在窗口中有可见部分，则距 最近的可见点一定落在 上，所以用 替代 ；0P10PPmPmPP0mPP00PmPP0mPP010PP计算机图形学

48、福建师范大学否则取 替代再对新的 求中点 。重复上述过程，直到 长度小于给定的控制常数为止，此时 收敛于交点。从 出发找最近可见点采用上面类似方法。10PP1PPm10PPmP1PPmmP1P计算机图形学福建师范大学 问：算法为什么可行？会不会无限循环、不断二分？计算机图形学福建师范大学2.5.1.3梁友栋Barsky算法 梁-Barsky算法的几何含义：入边、出边与端点计算机图形学福建师范大学 * 写入图形学教科书的唯一中国人的算 法 * Communication of ACM的论文 梁有栋教授的二三事 Liang-Barsky算法 几何连续理论：叶、马、郑 从几何学与纤维缠绕理论到基因工

49、程计算机图形学福建师范大学 参数化形式写出裁剪条件： 可以统一表示为形式： 入边 出边YTyuyYBXRxuxXL11kkqup 144113122111yYTqypYByqypxXRqxpXLxqxp计算机图形学福建师范大学 =0且 0，则线段完全在边界外， 0，则该线段平行于裁剪边界并且在窗口内。kpkqkq计算机图形学福建师范大学当 0，当 0,线段从裁剪边界延长线的内部延伸到外部。kpkpkp计算机图形学福建师范大学 对于每条直线，可以计算出参数u1和u2，它们定义了在裁剪矩形内的线段部分 u1的值由线段从外到内遇到的矩形边界所决定p0）。对这些边界计算rk=qk/pk 。u2取1和各

50、个rk值之中的最小值。计算机图形学福建师范大学如果u1u2，则线段完全落在裁剪窗口之外，被舍弃。否则裁剪线段由参数u的两个值u1,u2计算出来。计算机图形学福建师范大学void LB_LineClip(x1,y1,x2,y2,XL,XR,YB,YT)float x1,y1,x2,y2,XL,XR,YB,YT;float dx,dy,u1,u2;u1=0;u2=1 ;dx =x2-x1;dy =y2-y1; if(ClipT(-dx,x1-XL,&u1,&u2) if(ClipT(dx,XR-x1, &u1,&u2)if(ClipT(-dy,y1-YB, &

51、;u1,&u2) if(ClipT(dy,YT-y1, &u1,&u2) displayline(x1+u1*dx,y1+u1*dy, x1+u2*dx,y1+u2*dy)return; 计算机图形学福建师范大学bool ClipT(p,q,u1,u2)float p,q,*u1,*u2; float r;if(p*u2) return FALSE;else if(r*u1) *u1=r; return TRUE; 。/下页计算机图形学福建师范大学else if(p0) r=p/q;if(r*u1)return FALSE;else if(r*u2) *u2=r;ret

52、urn TRUE; else if(q0) return FALSE; return TRUE;计算机图形学福建师范大学 裁减的插曲： 汪嘉业的快速算法 80年代的裁减热：应道宁(工程图学研究所)、 汪国昭图形图像研究所） 对三种算法比较: Cohen-Sutherland与中点法在区域码测试阶段能以位运算方式高效率地进行，因而当大多数线段能够简单的取舍时，效率较好。 梁友栋Barskey算法只能应用于矩形窗口的情形，但其效率比前两者要高，这是因为运算只涉及到参数，仅到必要时才进行坐标计算。计算机图形学福建师范大学2.5.2 多边形裁剪 基本思想是一次用窗口的一条边裁剪多边形。 考虑窗口的一条

53、边以及延长线构成的裁剪线 该线把平面分成两个部分:可见一侧；不可见一侧计算机图形学福建师范大学 多边形的各条边的两端点S、P。它们与裁剪线的位置关系只有四种可见一侧可见一侧可见一侧可见一侧SpSSSppp(1)(2)(3)(4)对于情况1仅输出顶点P情况2输出0个顶点情况3输出线段SP与裁剪线的交点I情况4输出线段SP与裁剪线的交点I和终点P计算机图形学福建师范大学上述算法仅用一条裁剪边对多边形进行裁剪，得到一个顶点序列，作为下一条裁剪边处理过程的输入。对于每一条裁剪边，只是判断点在窗口哪一侧以及求线段SP与裁剪边的交点算法应随之改变。计算机图形学福建师范大学 示意图(5之1)p1p2p3p4

54、p5p6p7p8p9p10r1r2计算机图形学福建师范大学 示意图(5之2)计算机图形学福建师范大学 示意图(5之3)计算机图形学福建师范大学 示意图(5之4)计算机图形学福建师范大学 示意图(5之5)计算机图形学福建师范大学 其他窗口的裁剪 圆域窗口裁剪：潜望镜、. 恣意(凸)多边形裁剪：个性化电脑显示器定制，计算机图形学福建师范大学2.5.3 字符裁剪 串精度:将包围字串的外接矩形对窗口作裁剪 字符精度:将包围字的外接矩形对窗口作裁剪 以及笔画象素精度:将笔划分解成直线段对窗口作裁剪 待裁剪字符串 串精度裁剪 字符精度裁剪 象素精度裁剪STRINGSTRING2STRING2RINGSTRING2STRINGSTRING2计算机图形学福建师范大学 用离散量表示连续量引起的失真现象称之为走样(alias