第二章光栅图形学.ppt

《第二章光栅图形学.ppt》由会员分享，可在线阅读，更多相关《第二章光栅图形学.ppt（167页珍藏版）》请在三一文库上搜索。

1、计算机图形学 翁彬,第2章 光栅图形学,什么是光栅图形学？ 光栅显示器 图形光栅化、 光栅化图形的处理,光栅图形学的研究内容 2.1直线段的扫描转换算法 2.2圆弧的扫描转换算法 2.3多边形的扫描转换与区域填充 2.4字符 2.5裁剪 2.6反走样 2.7消隐,2.1 直线段的扫描转换算法,直线的扫描转换：确定最佳逼近于该直线的一组象素，并且按扫描线顺序，对这些象素进行写操作。 三个常用算法： 数值微分法（DDA） 中点画线法 Bresenham算法。,2.1.1 数值微分(DDA)法,基本思想 已知过端点 的直线段L： 直线斜率为 从 的左端点 开始，向 右端点步进。步长=1(个象素)，计

2、算相应的y坐标 ；取象素点(x, round(y)作为当前点的坐标。 这种方法直观，但效率太低，因为每一步需要一次浮点乘法、一次加法和一次舍入运算。,2.1.1 数值微分(DDA)法,作为最底层的光栅图形算法，在通常的CAD/图形系统中，会被大量应用，因此，哪怕节约一个加法或减法，也是很了不起的改进。 由此出发点，导致增量算法的思想。 增量算法：在一个迭代算法中，如果每一步的x、y值是用前一步的值加上一个增量来获得，则称为增量算法。,2.1.1 数值微分(DDA)法,计算 当 时; 即：当x每递增1，y递增k(即直线斜率)；,2.1.1 数值微分(DDA)法,例：画直线段 k = 0.4 x

3、y int(y+0.5) y+0.5 0 0 0 0 注：网格点表示象素,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 注：网格点表示象素,2.1.1 数值微分(DDA)法,void DDALine(int x0,int 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; x

4、x1, x+) drawpixel (x, int(y+0.5), color); y=y+k; ,2.1.1 数值微分(DDA)法,注意上述分析的算法仅适用于k 1的情形。在这种情况下，x每增加1, y最多增加1。 问题： 当 k 1时，会如何？(答案见下页),k 1 示意图,2.1.1 数值微分(DDA)法,当 k 1时，必须把x，y地位互换，y每增加1，x相应增加1/k。,2.1.1 数值微分(DDA)法,缺点： 在此算法中，y、k必须是float，且每一步都必须对y进行舍入取整，不利于硬件实现。,DDA算法小结,直线的显式方程（两点式） 象素是整数的（x每次增加1，取象素点(x, ro

5、und(y) ） 最简单算法 效率低 改进为增量算法（当x每递增1，y递增k ）,采用增量思想的DDA算法，每计算一个象素，只需计算一个加法，是否最优？ 如非最优，如何改进？ 目标：进一步将一个加法改为一个整数加法。 新思路 DDA算法采用两点式，可否采用其他的直线表示方式？,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离直线更近更近-取P1 M

6、与Q重合， P1、P2任取一点。,2.1.2 中点画线法,问题：如何判断M与Q点的关系？,2.1.2 中点画线法,假设直线方程为：F(x,y)=ax+by+c=0 其中a=y0-y1, b=x1-x0, c=x0y1-x1y0 由常识知： 欲判断M点是在Q点上方还是在Q点下方，只需把M代入F(x,y),并检查它的符号。,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

7、为下一个象素；,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； 增量为a d=a(xp+1)+b(yp+0.5)+c,2.1.2 中点画

8、线法,若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)+c,2.1.2 中点画线法,至此，至少新算法可以和DDA算法一样好。 能否再做改进？,2.1.2 中点画线法,能否实现整数运算？,2.1.2 中点画线法,画线从(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 的符号作判

9、断，为了只包含整数运算, 可以用2d代替d来摆脱小数，提高效率。 令 d0=2a+b, d1=2a, d2=2a+2b,我们有如下算法 。,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=y0-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+=

10、d1; drawpixel (x, y, color); /* while */ /* mid PointLine */,2.1.2 中点画线法,例：用中点画线法 i xi yi d 1 0 0 1 2 1 0 -3 3 2 1 3 4 3 1 -1 5 4 2 5,中点画线法小结,中点与交点位置来判断象素选取 引入直接的隐式方程F(x,y)=ax+by+c=0 但计算量大，故又改进为增量算法（此处，增量分两种情况） 为进一步提高效率，修改为全是整数计算的算法（ 2d代替d ，同时增量也做相应调整）,2.1.2 中点画线法,思考题：P55 2-2 用中点画线法扫描转换从点（1,0）到（4,7）

11、经过的直线段，并给出每一步的判别值。,DDA算法采用点斜式，中点法采用隐式表示。 中点法可以有整数算法。 其他表示可以推出整数算法吗？,2.1.3 Bresenham算法,基本思想 过各行各列象素中心构造一组虚拟网格线。按直线从起点到终点的顺序计算直线与各垂直网格线的交点，然后根据误差项的符号确定该列象素中与此交点最近的象素。,2.1.3 Bresenham算法,设直线方程为： ，其中k=dy/dx。 因为直线的起始点在象素中心，所以误差项d的初值d00。 X下标每增加1，d的值相应递增直线的斜率值k，即ddk。 当d0.5时，选择当前象素的右上方象素（ ），修改比较的基点为改点，即将d-1

12、而当d0.5时，选择当前象素的右方象素（ ），此时不改变基点 为方便计算，令ed-0.5， e的初值为-0.5，增量为k。 当e0时，取当前象素（xi，yi）的右上方象素（ ）； 而当e0时，更接近于右方象素（ ）。,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小于零则不变,2.1.3 Bresenham算法,void Bresenhamline (int x0,in

13、t 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算法,可以改用整数以避免除法。由于算法中只用到误差项的符号，因此可作如下替换：,2.1.3 Bresenham算法,void Bresenhamline (int x0,int y0,i

14、nt 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 (i=0; idx; i+) drawpixel (x, y, color);

15、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算法也是每个象素，需一个整数算法， 其优点是可以用于其他二次曲线。,2.2 圆弧的扫描转换算法,圆的特征：八对称性。只要扫描转换八分之一圆弧，就可以求出整个圆弧的象素集 中点画圆法 考虑中心在原点，半径为R 的第二个8分圆， 构造判别式（圆方程）,2.2 圆弧的扫描转换算法,若 d=0, 则应取P2为下一象素，而且下一象素的判别式

16、为 第 一个象素是（0,R），判别式d的初始值为,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) d+=2*x+3; else d+=2*(x-y)+5; y-; x+; circlepoints (x,y,color); ,2.2 圆弧的扫描转换算法,为了进一步提高算法的效率，可以将上面的算法中的浮点数改写成整数，将乘法运算改成加法运算，即仅用整数实现中点画圆法

17、。 如何改？,2.2 圆弧的扫描转换算法,使用e=d-0.25代替d e0=1-R,圆弧的中点扫描转换算法,利用圆八对称性 类似于直线的中点法 使用了圆的隐式方程 两种不同的增量（0时 ，0时） 为了改为整数算法 e=d-0.25代替d,小结,2.1 直线段的扫描转换算法 2.1.1 数值微分(DDA)法 2.1.2 中点画线法 2.1.3 Bresenham算法 2.2 圆弧的扫描转换算法,2.3 多边形的扫描转换与区域填充,多边形的表示方法 顶点表示 点阵表示 顶点表示：用多边形顶点的序列来刻划多边形。直观、几何意义强、占内存少；不能直接用于面着色。 点阵表示：用位于多边形内的象素的集合来

18、刻划多边形。失去了许多重要的几何信息；便于运用帧缓冲存储器表示图形，易于面着色。,2.3 多边形的扫描转换与区域填充,多边形的扫描转换：把多边形的顶点表示转换为点阵表示，也就是从多边形的给定边界出发，求出位于其内部的各个象素，并给帧缓冲器内的各个对应元素设置相应的灰度和颜色，通常称这种转换为多边形的扫描转换。,2.3 多边形的扫描转换与区域填充,区域指已经表示成点阵形式的填充图形，它是象素的集合。 区域填充指先将区域的一点赋予指定的颜色，然后将该颜色扩展到整个区域的过程。区域填充算法要求区域是连通的。,2.3 多边形的扫描转换与区域填充,区域表示方法：内点表示、边界表示 内点表示 枚举出区域内

19、部的所有像素 内部的所有像素着同一个颜色 边界像素着与内部像素不同的 颜色 边界表示 枚举出边界上所有的像素 边界上的所有像素着同一颜色 内部像素着与边界像素不同的颜色,多边形分为凸多边形、凹多边形、含内环的多边形。,逐点判断算法,逐点判断算法：逐个像素判别其是否位于多边形内部 判断一个点是否位于多边形内部：射线法 从当前像素发射一条射线，计算射线与多边形的交点个数 内部：奇数个交点 外部：偶数个交点,逐点判断算法,判断一点是否位于多边形内部？,逐点判断算法,算法描述 for(y=0; y=y_resolution; y+) for(x=0; x=x_resolution; x+) if(in

20、side(polygon, x, y) setpixel(framebuffer,x,y,polygon_color) else setpixel(framebuffer,x,y,background_color) ,逐点判断算法的不足,速度慢：几十万甚是几百万像素的多边形内外判断，大量的求交、乘除运算 没有考虑像素之间的联系 结论：逐点判断算法不可取！,2.3.1.1 扫描线算法,一个多边形与若干扫描线,2.3.1多边形的扫描转换,2.3.1.1 扫描线算法 基本思想： 按扫描线顺序，计算扫描线与多边形的相交区间，再用要求的颜色显示这些区间的象素，即完成填充工作。 对于一条扫描线填充过程可以

21、分为四个步骤： 求交 排序 配对 填色,多边形扫描转换算法,P0,P1,P2,P3,P4,P5,P6,P7,扫描转换示意图,相邻像素之间的连贯性,扫描线算法充分利用了相邻像素之间的连贯性，避免了对像素的逐点判断和求交运算，提高了算法效率 各种连贯性的定义 区域连贯性 扫描线连贯性 边的连贯性,区域连贯性,区域的连贯性是指多边形定义的区域内部相邻的像素具有相同的性质。例如具有相同的颜色,区域的连贯性,区域连贯性,两条扫描线之间的长方形区域被所处理的多边形分割成若干梯形(三角形可以看作退化梯形) 梯形的底边为扫描线，梯形的腰为多边形的边或窗口边缘,区域的连贯性,区域连贯性,梯形分为两类：多边形内部

22、和多边形外部 两类梯形在多边形内部相间排列(相邻的两个梯形必然有一个位于多边形内部，有一个在多边形外部),区域的连贯性,区域连贯性,推论：如果上述梯形属于多边形内(外)，那么该梯形内所有点的均属于多边形内(外)。 效率提高的根源：逐点判断区域判断,扫描线连贯性,区域连贯性在一条扫描线上的反映,扫描线的连贯性,扫描线连贯性,交点序列：扫描线与多边形的交点个数为偶数(1,2,3,4,5,6) 红色区间(1,2)、(3,4)、(5,6)位于多边形内部 其余绿色区间位于多边形外部 两类区间相间排列,扫描线的连贯性,扫描线连贯性,推论：如果上述交点区间属于多边形内(外)，那么该区间内所有点均属于多边形内

23、(外)。 效率提高的根源：逐点判断区间判断,边的连贯性,边的连贯性：直线的线性性质在光栅上的表现,边的连贯性,1 (x1,y1) 2 (x2,y2),11 (x11,y11) 22 (x22,y22),扫描线与边的交点,边的连贯性,相邻扫描线(y1=y11+1)与多边形的同一条边的交点存在如下关系： 当知道扫描线与一条边的一个交点之后，通过上述公式可以通过增量算法迅速求出其他交点,边的连贯性,边的连贯性,推论：边的连贯性是连接区域连贯性和扫描线连贯性的纽带。 扫描线连贯性“”边连贯性“”区域连贯性,2.3.1.1 扫描线算法,扫描线与多边形的顶点或边界相交时，必须进行正确的交点取舍。只需检查顶

24、点的两条边的另外两个端点的y值。按这两个y值中大于交点y值的个数是0,1,2来决定。,2.3.1.1 扫描线算法,数据结构 结点内容 x：当前扫描线与边的交点坐标 x：从当前扫描线到下一条扫描线间x的增量 ymax：该边所交的最高扫描线号ymax,2.3.1.1 扫描线算法,数据结构 新边表（NET）：存放在该扫描线第一次出现的边。若某边的较低端点为ymin，则该边就放在扫描线ymin的新边表中 上图所示各条扫描线的新边表NET,2.3.1.1 扫描线算法,数据结构 活性边表(AET)：把与当前扫描线相交的边称为活性边，并把它们按与扫描线交点x坐标递增的顺序存放在一个链表中,2.3.1.1 扫

25、描线算法,假定当前扫描线与多边形某一条边的交点的x坐标为x，则下一条扫描线与该边的交点不要重计算，只要加一个增量x。 设该边的直线方程为：ax+by+c=0； 若yyi，x=xi；则当y = yi+1时， 其中 为常数，并约定a=0时， 。,算法过程,void polyfill (polygon, color) int color; 多边形 polygon; for (各条扫描线i ) 初始化新边表头指针NET i； 把y min = i 的边放进边表NET i; y = 最低扫描线号； 初始化活性边表AET为空； for (各条扫描线i ) ,算法过程,把新边表NET i 中的边结点用插入排

26、序法插入AET表，使之按x坐标递增顺序排列； 遍历AET表，把配对交点区间(左闭右开)上的象素(x, y)，用drawpixel (x, y, color) 改写象素颜色值； i+; 遍历AET表，把y max= i 的结点从AET表中删除，并把y max i 结点的x值递增x； /* polyfill */,思考题,已知多边形P=(P0P1P2P3P4P5P6P0)；其各边坐标分别为 （2，5）（2，10）（9，6）（16，11）（16，4）（12，2）（7，2） 建立其新边表和活性边表,新边表,y=3,y=8,活动边表的例子,扫描线算法小结,建立新边表 按照扫描线顺序处理 每条扫描线构造活

27、性边表（x递增插入排序） 中间考虑交点取舍 根据当前活性边表选取像素进行填充（x方向） 从活性边表中删除y max= i 的结点,2.3.1.2边界标志算法,基本思想： 帧缓冲器中对多边形的每条边进行直线扫描转换，亦即对多边形边界所经过的象素打上标志。 填充。对每条与多边形相交的扫描线，按从左到右的顺序，逐个访问该扫描线上的象素。 取一个布尔变量inside来指示当前点的状态，若点在多边形内，则inside为真。若点在多边形外，则inside为假。 Inside 的初始值为假，每当当前访问象素为被打上标志的点，就把inside取反。对未打标志的点，inside不变。,边标志算法-例子,多边形P

28、0P1P2P3P4顶点坐标为（2,1）,(2,7),(8,5),(8,1),(6,4),以扫描线Y=3为例说明填充过程。开始时inside=0.,1）对于X=0，该像素未置成边界值，inside=0， 该点为背景色； 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，像素被置成边

29、界色，inside取反后为1，该点被置成多边形颜色； 8）对于X=8，像素被置成边界色，inside取反后为0，该点被置成背景色；,算法过程,void edgemark_fill(polydef, color) 多边形定义 polydef； int color; 对多边形polydef 每条边进行直线扫描转换； for (每条与多边形polydef相交的扫描线y ) inside = FALSE; for (扫描线上每个象素x ) if(象素 x 被打上边标志) inside = ! (inside); if(inside！= FALSE) drawpixel (x, y, color); e

30、lse drawpixel (x, y, background); ,2.3.1.2边界标志算法,用软件实现时，扫描线算法与边界标志算法的执行速度几乎相同， 但由于边界标志算法不必建立维护边表以及对它进行排序，所以边界标志算法更适合硬件实现，这时它的执行速度比有序边表算法快一至两个数量级。,2.3.2区域填充算法,区域指已经表示成点阵形式的填充图形，它是象素的集合。 区域填充指先将区域的一点赋予指定的颜色，然后将该颜色扩展到整个区域的过程。区域填充算法要求区域是连通的。,2.3.2区域填充算法,区域表示方法：内点表示、边界表示 内点表示 枚举出区域内部的所有像素 内部的所有像素着同一个颜色 边

31、界像素着与内部像素不同的 颜色 边界表示 枚举出边界上所有的像素 边界上的所有像素着同一颜色 内部像素着与边界像素不同的颜色,2.3.2区域填充算法,区域填充要求区域是连通的 连通性: 4连通、8连通 4连通： 8连通,2.3.2区域填充算法,4连通与8连通区域的区别 连通性： 4连通可看作8连通区域，但对边界有要求 对边界的要求,A：适合于内点表示区域的填充算法 设G为一内点表示的区域，(x,y)为区域内一点，oldcolor为G的原色。现取(x,y)为种子点对区域G进行填充：即先置像素(x,y)的颜色为newcolor，然后逐步将整个区域G都置为同样的颜色。 步骤如下： 种子象素入栈，当栈

32、非空时，执行如下三步操作： （1）栈顶象素出栈； （2）将出栈象素置成多边形色； （3）按上、下、左、右的顺序检查与出栈象素相邻的四个象素，若其中某个象素不在边界上且未置成多边形色，则把该象素入栈。,2.3.2.1区域填充的递归算法 （种子填充算法）,种子填充算法例子,多边形由P0P1P2P3P4构成，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

33、 y,int oldcolor,int newcolor) if(getpixel(x,y)=oldcolor) /属于区域内点oldcolor drawpixel(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 BoundaryFill

34、4(int x,int y,int boundarycolor,int newcolor) int color=getpixel(x,y); if(color!=newcolor ,该算法也可以填充有孔区域。 缺点： (1) 有些象素会入栈多次，降低算法效率；栈结构占空间。 (2) 递归执行，算法简单，但效率不高，区域内每一象素都引起一次递归，进/出栈，费时费内存。 改进算法，减少递归次数，提高效率。 解决方法是用扫描线填充算法,2.3.2.1区域填充的递归算法,2.3.2.2区域填充的扫描线算法,目标：减少递归层次 适用于内点表示的4连通区域 算法步骤： 首先填充种子点所在扫描线上的位于给定

35、区域的一个区段 然后确定与这一区段相连通的上、下两条扫描线上位于给定区域内的区段，并依次保存下来。 反复这个过程，直到填充结束。,2.3.2.2区域填充的扫描线算法,(1)初始化：堆栈置空。将种子点（x，y）入栈。 (2)出栈：若栈空则结束。否则取栈顶元素（x，y），以y作为当前扫描线。 (3)填充并确定种子点所在区段：从种子点（x，y）出发，沿当前扫描线向左、右两个方向填充，直到边界。分别标记区段的左、右端点坐标为xl和xr。 (4)并确定新的种子点：在区间xl，xr中检查与当前扫描线y上、下相邻的两条扫描线上的象素。若存在非边界、未填充的象素，则把每一区间的最右象素作为种子点压入堆栈，返回

36、第（2）步。 上述算法对于每一个待填充区段，只需压栈一次；因此，扫描线填充算法提高了区域填充的效率。,扫描线算法分析（举例分析）,该算法也可以填充有孔区域。,像素中的序号标指它所在区段位于堆栈中的位置,扫描线算法分析（举例分析）,扫描线算法分析（举例分析）,扫描线算法分析（举例分析）,多边形扫描转换与区域填充方法比较,联系：都是光栅图形面着色，用于真实感图形显示。可相互转换。 多边形的扫描转换转化为区域填充问题：当给定多边形内一点为种子点，并用Bresenham或DDA算法将多边形的边界表示成八连通区域后，则多边形的扫描转换转化为区域填充。 区域填充转化为多边形的扫描转换；若已知给定多边形的顶

37、点，则区域填充转化为多边形的扫描转换。,多边形扫描转换与区域填充方法比较,不同点： 1.基本思想不同；前者是顶点表示转换成点阵表示，后者只改变区域内填充颜色，没有改变表示方法。 2.对边界的要求不同 前者只要求扫描线与多边形边界交点个数为偶数。后者：区域封闭，防止递归填充跨界。 3.基本的条件不同 前者：从边界顶点信息出发。 后者：区域内种子点。,第二章 光栅图形学,2.1直线段的扫描转换算法 2.2圆弧的扫描转换算法 2.3多边形的扫描转换与区域填充 2.4字符 2.5裁剪 2.6反走样 2.7消隐,2.4 字符,字符指数字、字母、汉字等符号。 计算机中字符由一个数字编码唯一标识。 国际上最

38、流行的字符集：“美国信息交换用标准代码集”，简称ASCII码。它是用7位二进制数进行编码表示128个字符；包括字母、标点、运算符以及一些特殊符号。,汉字编码的国家标准字符集：GB231280。该字符集分为94个区，94个位，每个符号由一个区码和一个位码共同标识。区码和位码各用一个字节表示。 为了能够区分ASCII码与汉字编码，采用字节的最高位来标识：最高位为0表示ASCII码；最高位为1表示表示汉字编码。,字库：为了在显示器等输出设备上输出字符，系统中必须装备有相应的字库。字库中存储了每个字符的形状信息，字库分为矢量型和点阵型两种。,点阵字符: 每个字符由一个位图表示，该位为1表示字符的笔画经

39、过此位，对应于此位的象素应置为字符颜色。该位为0表示字符的笔画不经过此位，对应于此位的象素应置为背景颜色。,点阵字符 点阵字库中的位图表示,在实际应用中，有多种字体（如宋体、楷体等），每种字体又有多种大小型号，因此字库的存储空间是很庞大的。解决这个问题一般采用压缩技术。 点阵字符的显示分为两步。首先从字库中将它的位图检索出来。然后将检索到的位图写到帧缓冲器中。,矢量字符:记录字符的笔画信息，而不是整个位图，具有存储空间小，美观、变换方便等优点。对于字符的旋转、缩放等变换， 点阵字符的变换需要对表示字符位图中的每一象素进行； 矢量字符的变换只要对其笔画端点进行变换就可以了。矢量字符的显示也分为两

40、步。,显示：首先从字库中将它的字符信息。然后取出端点坐标，对其进行适当的几何变换，再根据各端点的标志显示出字符。 点阵字符 点阵字库中的位图表示 矢量轮廓字符,特点： 点阵字符：存储量大，易于显示 矢量字符：存储量小，美观，变换方便; 但 需要光栅化后才能显示。,字符属性,字体 宋体 仿宋体 楷体 黑体 隶书 字高 宋体 宋体 宋体 宋体 字宽 字倾斜角 倾斜 倾斜 对齐 (左对齐、中心对齐、右对齐) 字色 红色、绿色、蓝色,2.5 裁剪,裁剪：确定图形中哪些部分落在显示区之内，哪些落在显示区之外,以便只显示落在显示区内的那部分图形。这个选择过程称为裁剪。 在使用计算机处理图形信息时，计算机内

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

42、utherland裁剪,基本思想：对于每条线段P1P2分为三种情况处理分为三种情况处理: （1）若P1P2完全在窗口内，则显示该线段P1P2简称“取”之。 （2）若P1P2明显在窗口外，则丢弃该线段，简称“弃”之。 （3）若线段不满足“取”或 “弃”的条件，则在交点处把线段分为两段。其中一段完全在窗口外，可弃之。然后对另一段重复上述处理。,为快速判断，采用如下编码方法： 每个区域赋予4位编码,编码 线段裁剪,若P1P2完全在窗口内code1=0,且code2=0,则“取” 若P1P2明显在窗口外,code1&code20 （？），则“弃” 在交点处把线段分为两段。其中一段完全在窗口外，可弃之。

43、然后对另一段重复上述处理。,计算线段P1(x1,y1)P2(x2,y2)与窗口边界的交点 if(LEFT,示例,编码的思想在图形学中非常重要。 Sutherland：Coons奖, 图灵奖, IEEE 计算机先驱奖。,2.5.1.2 中点分割裁剪算法,基本思想： 与前一种Cohen-Sutherland算法一样首先对线段端点进行编码，并把线段与窗口的关系分为三种情况: 全在、完全不在和线段和窗口有交。对前两种情况，进行一样的处理。 对于第三种情况，用中点分割的方法求出线段与窗口的交点。,求线段与窗口的交点,A、B分别为距P0、P1最近的可见点，Pm为P0P1中点,从 出发找最近可见点的方法 先

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

45、形式写出裁剪条件： 可以统一表示为形式： 入边 出边,=0且 0，则线段完全在边界外， 0，则该线段平行于裁剪边界并且在窗口内。,当 0， 当 0,线段从裁剪边界延长线的内部延伸到外部。,对于每条直线，可以计算出参数u1和u2，它们定义了在裁剪矩形内的线段部分 u1的值由线段从外到内遇到的矩形边界所决定（p0）。对这些边界计算rk=qk/pk 。u2取1和各个rk值之中的最小值。,如果u1u2，则线段完全落在裁剪窗口之外，被舍弃。 否则裁剪线段由参数u的两个值u1,u2计算出来。,void LB_LineClip(x1,y1,x2,y2,XL,XR,YB,YT) float x1,y1,x2,

46、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, ,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;return TRUE; else if(q0) return FALSE;

47、 return TRUE; ,裁减的插曲： 汪嘉业的快速算法 80年代的裁减热：应道宁(工程图学研究所)、 汪国昭（图形图像研究所） 对三种算法比较: Cohen-Sutherland与中点法在区域码测试阶段能以位运算方式高效率地进行，因而当大多数线段能够简单的取舍时，效率较好。 梁友栋Barskey算法只能应用于矩形窗口的情形，但其效率比前两者要高，这是因为运算只涉及到参数，仅到必要时才进行坐标计算。,2.5.2 多边形裁剪,基本思想是一次用窗口的一条边裁剪多边形。 考虑窗口的一条边以及延长线构成的裁剪线 该线把平面分成两个部分:可见一侧；不可见一侧,多边形的各条边的两端点S、P。它们与裁剪线的位置关系只有四种,对于情况（1）仅输出顶点P,情况（2）输出0个顶点,情况（3）输出线段SP与裁剪线的交点I,情况（4）输出线段SP与裁剪线的交点I和终点P,上述算法仅用一条裁剪边对多边形进行裁剪，得到一个顶点序列，作为下一条裁剪边处理过程的输入。 对于每一条裁剪边，只是判断点在窗口哪一侧以及求线段SP与裁剪边的交点算法应随之改变。,示意图(5之1),p1,p2,p3,p4,p5,p6,p7,p8,p9,p10,r1,r2,示意图(5之2),示意图(5之3),示意图(5之4),示意图(5之5