计算机图形学课件

1、 计算机图形学计算机图形学教学要求 了解图形系统的框架及其涉及的软件、硬件技术； 了解图形学的基本问题，掌握图形学的基本概念、方法与算法； 对与图形相关的应用及当前的研究热点有一个初步认识； 具有一定实践体会和相关的编程能力。 本课程的主要内容 绪论 光栅图形学l扫描转换、裁减、反走样、消影 几何造型l曲线曲面造型、实体造型 真实感图形学lPhong模型、光线跟踪、辐射度算法 指导实验主要参考书目 孙家广，计算机图形学（第三版），清华大学出版社，1999。 唐泽圣，计算机图形学基础，清华大学出版社，1995 Donald Hearn, M. Pauline Baker ,“Computer G

2、raphics (C Version)”, Prentice Hall , 1997. James D. Foley, Andries van Dam etc., “Introduction to Computer Graphics”, Addison-Wesley, 1996 唐荣锡，计算机图形学教程（修订版），科学出版社，2000 计算机辅助设计与图形学学报 中国图形图像学报成绩评定办法 作业、考勤、实验：20% 笔试：80%第第1章章 引言引言提出问题提出问题什么是计算机图形学？计算机图形学研究的对象是什么？计算机图形处理系统的构造？1.1 计算机图形学及其相关概念计算机图形学及其相关概

3、念 什么是计算机图形学？计算机图形学？（Computer Graphics）计算机图形学计算机图形学是研究怎样利用计算机来显示、生成和处理图形的原理、方法和技术的一门学科。IEEE定义：Computer graphics is the art or science of producing graphical images with the aid of computer. 3D虚拟影像摄影系统 协同工作摄影机 面部表演捕捉还原系统 计算机图形学与传统理论计算机图形学与传统理论 ： 交叉、界线模糊、相互渗透交叉、界线模糊、相互渗透 CAGD（计算几何） 逼近论（计算数学） 微分几何 形态学 混

4、沌学 小波理论 计算机图形学的研究对象计算机图形学的研究对象图形图形通常意义下的图形通常意义下的图形：能够在人的视觉系统中形成视觉印象的客观对象都称为图形。计算机图形学中所研究的图形计算机图形学中所研究的图形从客观世界物体中抽象出来的带有颜色及形状信息的图和形。 图形的表示图形的表示点阵法点阵法是用具有颜色信息的点阵来表示图形的一种方法，它强调图形由哪些点组成，并具有什么灰度或色彩。 参数法参数法是以计算机中所记录图形的形状参数与属性参数来表示图形的一种方法。 通常把参数法描述的图形叫做图形（图形（Graphics） 把点阵法描述的图形叫做图像（图像（Image）endend 与计算机图形学相

5、关的学科与计算机图形学相关的学科 计算机图形学计算机图形学试图从非图象形式的数据描述来生成（逼真的）图象。 数字图象处理数字图象处理旨在对图象进行各种加工以改善图象的视觉效果。 计算机视觉计算机视觉是研究用计算机来模拟生物外显或宏观视觉功能的科学和技术。 endend特征数据、结构数据计算机图形学计算机视觉图象信号数字图象处理图1-1 图形图象处理相关学科间的关系 酝酿期（酝酿期（50年代）年代）1950年，美国MIT的旋风1号(Whirlwind I)计算机配备了阴极射线管(CRT)来显示一些简单的图形，不具备人-机交互功能1.2 计算机图形学的发展计算机图形学的发展1.2.1计算机图形学的

6、确立计算机图形学的确立 萌芽期（萌芽期（60年代）年代）1962年，美国MIT林肯实验室的Ivan.E.Sutherland发表了一篇题为Sketchpad：一个人机通信的图形系统的博士论文，其中首次使用了“Computer Graphics” 提出图形学的概念，成就提出图形学的概念，成就“图形学之父图形学之父”的英名的英名 获获“图灵图灵”奖奖 IEEE 计算机杰出成就奖计算机杰出成就奖 Coons奖奖 发展期（发展期（70年代）年代） 普及期（普及期（80年代）年代） 出现了带有光栅图形显示器的个人计算机和工作站 提高增强期（提高增强期（90年代）年代） 总体特征总体特征：技术发展、需求驱

7、动技术发展、需求驱动 1.3 计算机图形学的应用计算机图形学的应用 CAD/CAM 可视化与可视计算l海量的数据的图形表示l1986年，美国科学基金会（NSF）专门召开了一次研讨会，会上提出了“科学计算可视化（Visualization in Scientific omputing）” 科学计算可视化广泛应用于医学、 流体力学、有限元分析、气象分 析当中l在医学领域：机械手术和远程手 术，医用CT扫描数据的三维重建， 基于CT数据的人体内漫游 计算机动画 二维动画 图象变形 形状混合 三维动画 关键帧动画 变形物体的动画 过程动画 关节动画与人体动画 基于视频(Video)的动画虚拟现实4图形

8、设备图形设备 图形显示设备l图形输出包括图形的显示和图形的绘制，图图形显示形显示指的是在屏幕上输出图形l图形绘制图形绘制通常指把图形画在纸上，也称硬拷贝，打印机和绘图仪是两种最常用的硬拷贝设备 彩色CRT显示器lCRT（CRT CathodeRay Tube，阴极射线管）l组成 电子枪 聚焦系统 加速系统 磁偏转系统CRT显示器的简易结构图l工作原理 高速的电子束由电子枪发出，经过聚焦系统、加速系统和磁偏转系统就会到达荧光屏的特定位置。由于荧光物质在高速电子的轰击下会发生电子跃迁，即电子吸收到能量从低能态变为高能态。由于高能态很不稳定，在很短的时间内荧光物质的电子会从高能态重新回到低能态，这时

9、将发出荧光，屏幕上的那一点就会亮了 要保持显示一幅稳定的画面，必须不断地发射电子束 电平控制器电平控制器是用来控制电子束的强弱的，当加上正电压时，电子束就会大量通过，将会在屏幕上形成较亮的点，当控制电平加上负电压时，依据所加电压的大小，电子束被部分或全部阻截，通过的电子很少，屏幕上的点也就比较暗 聚焦系统聚焦系统是一个电透镜，能使众多的电子聚集于一点 加速阳极加速阳极使电子达到轰击激发荧光屏应有的速度。最后由磁偏转系统来达到指定位置 电子束要到达屏幕的边缘时，偏转角度就会增大。到达屏幕最边缘的偏转角度被称为最大偏转角 CRT显示器屏幕越大整个显象管就越长l刷新频率 刷新一次是指电子束从上到下扫

10、描一次的过程 刷新频率高到一定值后，图象才能稳定显示 隔行扫描与逐行扫描电子束扫描过程示意图扫描线水平回扫0123456垂直回扫l彩色彩色CRT显示器显示器显示彩色的原理 彩色CRT显示器的荧光屏上涂有三种荧光物质，它们分别能发红、绿、兰三种颜色的光。而电子枪也发出三束电子束来激发这三种物质，中间通过一个控制栅格来决定三束电子到达的位置 三束电子经过荫罩的选择，分别到达三个荧光点的位置。通过控制三个电子束的强弱就能控制屏幕上点的颜色荫罩兰红绿兰红绿电子枪屏幕荧光点荫罩式彩色CRT显色原理endend LCD显示器显示器lCRT固有的物理结构限制了它向更广的显示领域发展 屏幕的加大必然导致显象管

11、的加长，显示器的体积必然要加大，在使用时候就会受到空间的限制 CRT显示器是利用电子枪发射电子束来产生图像，容易受电磁波干扰 长期电磁辐射会对人们健康产生不良影响lLCD显示器的优点 外观小巧精致，厚度只有15cm左右。 不会产生CRT那样的因为刷新频率低而出现的闪烁现象 工作电压低，功耗小，节约能源 没有电磁辐射，对人体健康没有任何影响索尼公司的两款LCD外形lLCD显示器基本原理 液晶是一种介于液体和固体之间的特殊物质，它具有液体的流态性质和固体的光学性质。当液晶受到电压的影响时，就会改变它的物理性质而发生形变，此时通过它的光的折射角度就会发生变化，而产生色彩 液晶屏幕后面有一个背光，这个

12、光源先穿过第一层偏光板，再来到液晶体上，而当光线透过液晶体时，就会产生光线的色泽改变，从液晶体射出来的光线，还得必须经过一块彩色滤光片以及第二块偏光板 液晶显示有主动式和被动式两种 被动式液晶屏幕有STN（Super TN超扭曲向列LCD）和DSTN（Double layer Super TN双层超扭曲向列LCD）等 最流行的主动式液晶屏幕是TFT（Thin Film Transistor薄膜晶体管） 主动式液晶显示器使用了FET场效晶体管以及共通电极，这样可以让液晶体在下一次的电压改变前一直保持电位状态。这样主动式液晶显示器就不会产生在被动式液晶显示器中常见的鬼影、或是画面延迟的残像等lLC

13、D显示器的基本指标 可视角度 视线与屏幕中心法向成一定角度时，人们就不能清晰地看到屏幕图象，而那个能看到清晰图象的最大角度被我们称为可视角度。一般所说的可视角度是指左右两边的最大角度相加。工业上有CR10（Contrast Ratio）、CR5两种标准来判断液晶显示器的可视角度 点距与分辨率 液晶屏幕的点距就是两个液晶颗粒（光点）之间的距离，一般0.280.32mm就能得到较好的显示效果 通常所说的液晶显示器的分辨率是指其真实分辨率，表示水平方向的像素点数与垂直方向的像素点数的乘积endend第一章 小结 1、计算机图形学的概念、计算机图形学的概念 什么是计算机图形学、图形的种类、相关的学科

14、2、计算机图形学的发展、应用、计算机图形学的发展、应用 3、图形显示设备、图形显示设备 CRT、LCD第二章 光栅图形学光栅图形学的研究内容:直线段的扫描转换直线段的扫描转换算法算法圆弧的扫描转换算法圆弧的扫描转换算法多边形的扫描转换与区域填充多边形的扫描转换与区域填充字符字符裁剪裁剪反走样反走样消隐消隐图形的生成：图形的生成：是在指定的输出设备上，根据坐标描述构造二维几何图形。图形的扫描转换图形的扫描转换：在光栅显示器等数字设备上确定一个最佳逼近于图形的象素集的过程。 光栅图形显示器可以看作一个像素的矩阵矩阵 确定最佳逼近图形的像素集合，并用指定属性写像素的过程称为图形的扫描转换扫描转换/光

15、栅化光栅化 二维图形的光栅化必须确定区域对应的像素集，并用指定的属性或图案显示，称为区域填充区域填充 确定图形的哪部分需要显示，哪部分不需要显示的过程称为裁剪裁剪 因像素逼近误差导致图形产生畸变的现象称为走样走样 用于减少或消除走样的技术称为反走样反走样 删除图形中隐藏的部分称为消隐消隐2.1 直线的扫描转换直线的扫描转换 直线的绘制要求：直线的绘制要求： 1.直线要直 2.直线的端点要准确，即无定向性和断裂情况 3.直线的亮度、色泽要均匀 4.画线的速度要快 5.要求直线具有不同的色泽、亮度、线型等2.1.1 数值微分(DDA)法 基本思想 已知过端点 的直线段L： 直线斜率为 从 的左端点

16、 开始，向 右端点步进。步长=1(个象素)，计算相应的y坐标 ；取象素点(x, round(y)作为当前点的坐标。0101xxyyk),(),(111000yxPyxPbkxyx0 xxbkxyl作为最底层的光栅图形算法，在通常的CAD/图形系统中，会被大量应用，因此，哪怕节约一个加法或减法，也是很了不起的改进。l由此出发点，导致增量算法的思想。计算当 时;即：当x每递增1，y递增k(即直线斜率)； xkyxkbkxbkxyiiii 111xkyyii1例：画直线段x int(y+0.5) y+0.5000100.4+0.5210.8+0.5311.2+0.5421.6+0.5522.0+0.

17、5注：网格点表示象素0 1 2 3 4 5321Line: P0(0, 0)- P1(5, 2)2 , 5()0 , 0(10PPvoid 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; xx1, x+) drawpixel (x, int(y+0.5), color); y=y+k; 问题： 当 k 1时，会如何？(答案见下页)注意上述分析的算法仅适用于k 1的情形。在这种情况下，x每增加1, y最多

18、增加1。当 k 1时，必须把x，y地位互换 k DDA算法采用两点式，可否采用其他的直线表示方式？2.1.2 中点画线算法中点画线算法直线的方程该直线方程将平面分为三个区域： 对于直线上的点，F(x,y)=0； 对于直线上方的点，F(x,y)0； 对于直线下方的点，F(x,y)0。 , 0),(0101xxyyxykbkxyyxF其中基本原理基本原理：假定0k1，x是最大位移方向判别式判别式： ) 1(5 . 0)5 . 0, 1(),(bxkyyxFyxFdiiiiMM则有：但这样做，每一个象素的计算量是3个加法，一个乘法。)0( )0( 1dydyyd0(xi,yi)(xi+1,yi+0.

19、5)(xi+2,yi+1.5)如果也采用增量算法呢？误差项的递推误差项的递推d=0(xi,yi)(xi+1,yi+0.5)(xi+2,yi+0.5) ) 1(5 . 0),(bxkyyxFdiiMM初始值初始值d的计算的计算kkbkxybxkyyxFd5 . 0 5 . 0 ) 1(5 . 0 )5 . 0, 1(00000000k1时中点画线算法的算法步骤算法步骤为：1.输入直线的两端点P0(x0,y0)和P1(x1,y1)。2.计算初始值x、y、d=0.5-k、x=x0、y=y0；3.绘制点(x,y)。判断d的符号；若d0，则(x,y)更新为(x+1,y+1)，d更新为d+1-k；否则(x

20、,y)更新为(x+1,y)，d更新为d-k。4.当直线没有画完时，重复步骤3。否则结束。思考一：能否再做改进？ 思考二：能否实现整数运算？改进改进：用2dx代替d1.输入直线的两端点P0(x0,y0)和P1(x1,y1)。2.计算初始值x、y、d=x-2y、x=x0、y=y0。3.绘制点(x,y)。判断d的符号。若d0.5，则(x,y)更新为(x+1,y+1)，同时将d更新为d-1；否则(x,y)更新为(x+1,y)。5.当直线没有画完时，重复步骤3和4。否则结束。 能改进么？改进改进1：令e=d-0.50)(e 0)(e 1111iiiiiyyyxx e初=-0.5， 每走一步有e=e+k。

21、 if (e0) then e=e-1算法步骤算法步骤为：1.输入直线的两端点P0(x0,y0)和P1(x1,y1)。2.计算初始值x、y、e=-0.5、x=x0、y=y0。3.绘制点(x,y)。4.e更新为e+k，判断e的符号。若e0，则(x,y)更新为(x+1,y+1)，同时将e更新为e-1；否则(x,y)更新为(x+1,y)。5.当直线没有画完时，重复步骤3和4。否则结束。Bresenham画线算法 void Bresenhamline(int x0,y0,int x1,y1,int color) int x,y,dx,dy; float k, e; dx = x1-x0, dy=y1-

22、y0, k= dy/dx; e=-0.5, x=x0, y=y0; for (i=0; i=0) y+, e=e-1; 还能改进么？改进改进2：用2ex来替换e e初=-x， 每走一步有e=e+2y。 if (e0) then e=e-2x算法步骤算法步骤：1.输入直线的两端点P0(x0,y0)和P1(x1,y1)。2.计算初始值x、y、e=-x、x=x0、y=y0。3.绘制点(x,y)。4.e更新为e+2y，判断e的符号。若e0，则(x,y)更新为(x+1,y+1)，同时将e更新为e-2x；否则(x,y)更新为(x+1,y)。5.当直线没有画完时，重复步骤3和4。否则结束。Bresenham

23、画线算法的改进 void Bresenhamline(int x0,y0,int x1,y1,int color) int x,y,dx,dy，e; float k,e; dx = x1-x0,dy=y1-y0, e=-dx; k= dy/dx; e=-0.5, x=x0,y=y0; for (i=0;i=0) y+,e=e-1; e=e-2*dx; 蓝色蓝色为原算法中的语句；为原算法中的语句；红色红色为改进算法中的语句为改进算法中的语句 最终，Bresenham算法也是每个象素，需一个整数算法， 其优点是可以用于其他二次曲线。新方法：BRDC: binary representation o

24、f displacement code for lineMiao LF, Liu XG, Peng QS, Bao HJCOMPUTERS & GRAPHICS-UK 26 (3): 401-408 JUN 20022.2 圆的扫描转换圆的扫描转换解决的问题：解决的问题：绘出圆心在原点，半径为整数R的圆x2+y2=R22.2.1 八分法画圆八分法画圆八分法画圆八分法画圆(x,y)yy=-xy=x(y,x)(-y,x)(-x,y)(-x,-y)(-y,-x)(y,-x)(x,-y)解决问题解决问题：2.2.2 简单方程产生圆弧简单方程产生圆弧算法原理算法原理：利用其函数方程，直接离散计算 圆的函

25、数方程为： 222Ryx122111 x0,R2() iiiixxyroundRx圆的极坐标方程为： sincosRyRx)sin( )cos()( 11111iiiiiiRroundyRroundx为一固定角度步长2.2.3 中点中点Bresenham画圆画圆构造函数F(x,y)=x2-y2-R2。 对于圆上的点，有F(x,y)=0； 对于圆外的点，F(x,y)0； 而对于圆内的点，F(x,y)0时，下一点取Pd(xi +1,yi-1)。M的坐标为：M(xi +1,yi-0.5)当F(xM,yM)0时，取Pd(xi +1,yi-1)当F(xM,yM)=0时，约定取Pu。构造判别式构造判别式：

26、222)5 . 0() 1()5 . 0, 1(),(RyxyxFyxFdiiiiMM误差项的递推误差项的递推d0： (a) d0： 5)(2 )22()32()5 . 0() 1( )5 . 1()2( )5 . 1, 2(222222iiiiiiiiiiyxdyxRyxRyxyxFd(b) d0的情况Pxixi+2xi+1yi-1yiyi-2判别式的初始值判别式的初始值RRRRFd25. 1 )5 . 0(1 )5 . 0, 1 (220算法步骤算法步骤：1.输入圆的半径R。2.计算初始值d=1.25-R、x=0、y=R。3.绘制点(x,y)及其在八分圆中的另外七个对称点。4.判断d的符号

27、。若d0，则先将d更新为d+2x+3，再将(x,y)更新为(x+1,y)；否则先将d更新为d+2(x-y)+5，再将(x,y)更新为(x+1,y-1)。5.当xy时，重复步骤3和4。否则结束。改进：改进：用d-0.25代替d算法步骤算法步骤：1.输入圆的半径R。2.计算初始值d=1-R、x=0、y=R。3.绘制点(x,y)及其在八分圆中的另外七个对称点。4.判断d的符号。若d0，则先将d更新为d+2x+3，再将(x,y)更新为(x+1,y)；否则先将d更新为d+2(x-y)+5，再将(x,y)更新为(x+1,y-1)。5.当x0； 对于椭圆内的点，F(x,y)0，取Pd(xi+1,yi-1)误

28、差项的递推误差项的递推d10：(a) d0： )22() 32( )22() 32()5 . 0() 1( )5 . 1()2()5 . 1, 2(221222222222222221iiiiiiiiiiyaxbdyaxbbayaxbbayaxbyxFd(b) d0的情况Pxixi+2xi+1yi-1yiyi-2判别式的初始值判别式的初始值 )25. 0( )5 . 0()5 . 0, 1 (222222210babbababbFd再来推导椭圆弧下半部分的绘制公式原理原理判别式判别式 2222222) 1()5 . 0() 1, 5 . 0(bayaxbyxFdiiii若d20，取Pl(xi,

29、yi-1)若d20，取Pr(xi+1,yi-1)误差项的递推误差项的递推d20：)y(ad )y(aba)(ya)(xb ba)(ya)(xb),yF(xdiiiiiiii323215 . 025 . 025 . 0 2222222222222222(a) d0的情况Pxiyi-2xi+1yiyi-1xi+2d20： ) 32()22( ) 32()22() 1()5 . 0( )2()5 . 1()2, 5 . 1(222222222222222222iiiiiiiiiiyaxbdyaxbbayaxbbayaxbyxFd(b) d=0的情况Pxixi+2xi+1yi-1yiyi-2注意注意：

30、 上半部分的终止判别 下半部分误差项的初值 算法步骤算法步骤：1.输入椭圆的长半轴a和短半轴b。2.计算初始值d=b2+a2(-b+0.25)、x=0、y=b。3.绘制点(x,y)及其在四分象限上的另外三个对称点。4.判断d的符号。若d0，则先将d更新为d+b2(2x+3)，再将(x,y)更新为(x+1,y)；否则先将d更新为d+b2(2x+3)+a2(-2y+2)，再将(x,y)更新为(x+1,y-1)。5.当b2(x+1)0时，重复步骤7和8。否则结束。2.3 多边形的扫描转换与区域填充多边形的扫描转换与区域填充多边形的扫描转换多边形的扫描转换主要是通过确定穿越区域的扫描线的覆盖区间来填充

31、，区域填充区域填充是从给定的位置开始涂描直到指定的边界条件为止。2.3.1 多边形的扫描转换多边形的扫描转换 多边形有两种重要的表示方法：顶点顶点表示和点阵点阵表示。 多边形的扫描转换多边形的扫描转换: :把多边形的顶点表示转换为点阵表示。 区域可采用内点表示和边界表示两种表示形式。 区域填充区域填充:指先将区域的一点赋予指定的颜色，然后将该颜色扩展到整个区域的过程。1. 什么是多边形的扫描转换 多边形分为凸多边形、凹多边形、含内环的多边形。2. x-扫描线算法基本思想基本思想算法步骤算法步骤：(1)确定多边形所占有的最大扫描线数，得到多边形顶点的最小和最大y值（ymin和ymax）。(2)从

32、y=ymin到y=ymax，每次用一条扫描线进行填充。(3)对一条扫描线填充的过程可分为四个步骤：a.求交b.排序c.交点配对d.区间填色存在问题：存在问题：当扫描线与多边形顶点相交时，交点的取舍问题。解决： 当扫描线与多边形的顶点相交时，若共享顶点的两条边分别落在扫描线的两边，交点只算一个；若共享顶点的两条边在扫描线的同一边，这时交点作为零个或两个。 0111102223. 改进的有效边表算法（改进的有效边表算法（Y连贯性算法）连贯性算法）改进原理改进原理： 处理一条扫描线时，仅对有效边求交 利用扫描线的连贯性 利用多边形边的连贯性1234567891011123-1/3353/485-1/

33、2891/21122/5712-1795桶p3p2p3p4p5p4p5p6p2p1p0p1p0p6x|yminymax 1/k next(c) 边表6xy213 4 5 6 7 8 9111234567891011121012p1p3p4p5(a) 多边形P0P1P2P3P4P5P6P0p2p0p6有效边（有效边（Active Edge）：指与当前扫描线相交的多边形的边，也称为活性边。有效边表（有效边表（Active Edge Table, AET）：把有效边按与扫描线交点x坐标递增的顺序存放在一个链表中，此链表称为有效边表。有效边表的每个结点： x ymax 1/k next边表（边表（Ed

34、ge Table）边表的构造：(1)首先构造一个纵向链表，链表的长度为多边形所占有的最大扫描线数，链表的每个结点，称为一个桶，则对应多边形覆盖的每一条扫描线。(2)将每条边的信息链入与该边最小y坐标（ymin ）相对应的桶处。也就是说，若某边的较低端点为ymin，则该边就放在相应的扫描线桶中。(3)每条边的数据形成一个结点，内容包括：该扫描线与该边的初始交点x（即较低端点的x值），1/k，以及该边的最大y值ymax。x|ymin ymax 1/k NEXT(4)同一桶中若干条边按X|ymin由小到大排序，若X|ymin 相等，则按照1/k由小到大排序。解决顶点交点计为解决顶点交点计为1时的情形

35、时的情形：xy213 4 5 6 7 8 9111234567891011121012p1p3p4p5(a) 多边形P0P1P2P3P4P5P6P0p2p0p61234567891011123-1/3353/485-1/2891/21122/5712-1795桶p3p2p3p4p5p4p5p6p2p1p0p1p0p6x|yminymax1/knext(c) 边表6算法步骤算法步骤：(1)初始化：构造边表，AET表置空；(2)将第一个不空的ET表中的边与AET表合并；(3)由AET表中取出交点对进行填充。填充之后删除y=ymax的边；(4)yi+1=yi+1,根据xi+1=xi+1/k计算并修改

36、AET表，同时合并ET表中y=yi+1桶中的边，按次序插入到AET表中，形成新的AET表；(5)AET表不为空则转(3)，否则结束。2.3.2 2.3.2 区域填充区域填充区域区域是指已经表示成点阵形式的填充图形，它是像素集合。4-邻接点邻接点和8-邻接点邻接点4-连通区域连通区域和8-连通区域连通区域把位于给定区域的边界上的象素一一列举出来的方法称为边界表示法边界表示法。边界填充算法边界填充算法（Boundary-fill Algorithm）。枚举出给定区域内所有象素的表示方法称为内点表示内点表示。泛填充算法（泛填充算法（Flood-fill Algorithm）1. 边界填充算法算法的输

37、入：种子点坐标(x,y)，填充色和边界颜色。栈结构实现4-连通边界填充算法连通边界填充算法的算法步骤算法步骤为：种子象素入栈；当栈非空时重复执行如下三步操作：(1)栈顶象素出栈；(2)将出栈象素置成填充色；(3)检查出栈象素的4-邻接点，若其中某个象素点不是边界色且未置成多边形色，则把该象素入栈。栈结构实现8-连通边界填充算法连通边界填充算法的算法步骤算法步骤为：种子象素入栈；当栈非空时重复执行如下三步操作：(1)栈顶象素出栈；(2)将出栈象素置成填充色；(3)检查出栈象素的8-邻接点，若其中某个象素点不是边界色且未置成多边形色，则把该象素入栈。特点特点： 可以用于填充带有内孔的平面区域。 把

38、太多的象素压入堆栈改进改进通过沿扫描线填充水平象素段，来代替处理4-邻接点和8-邻接点。沿扫描线填充水平象素段的4-连通边界填充算法步骤连通边界填充算法步骤：种子象素入栈；当栈非空时作如下三步操作：(1)栈顶象素出栈；(2)填充出栈象素所在扫描行的连续象素段，直到遇到边界象素为止，即每出栈一个象素，就对包含该象素的整个扫描线区间进行填充；(3)在区间中检查与当前扫描线相邻的上下两条扫描线的有关象素是否全为边界象素或已填充的象素，若存在非边界、未填充边界的象素，则把每一区间的最右象素取作种子象素入栈。2. 泛填充算法算法的输入：种子点坐标(x,y)，填充色和内部点的颜色。算法原理算法原理：算法从

39、指定的种子(x,y)开始，用所希望的填充颜色赋给所有当前为给定内部颜色的象素点。4-连通泛填充连通泛填充算法步骤算法步骤如下：种子象素入栈；当栈非空时重复执行如下三步操作：(1)栈顶象素出栈；(2)将出栈象素置成填充色；(3)检查出栈象素的4-邻接点，若其中某个象素点是给定内部点的颜色且未置成新的填充色，则把该象素入栈。内点表示的4连通区域的递归填充算法:void FloodFill4(int x,int y,int oldcolor,int newcolor) if(getpixel(x,y)=oldcolor) /属于区域内点oldcolordrawpixel(x,y,newcolor);

40、FloodFill4(x,y+1,oldcolor,newcolor);FloodFill4(x,y-1,oldcolor,newcolor);FloodFill4(x-1,y,oldcolor,newcolor);FloodFill4(x+1,y,oldcolor,newcolor); 注意注意：当以边界表示时，4-连通边界填充算法只能填充4-连通区域，8-连通边界填充算法也只能填充8-连通区域。当以内点表示时，8-连通泛填充算法可以填充8-连通区域也可以填充4-连通区域，当然4-连通泛填充算法还是只能填充4-连通区域。2.4 2.4 字符处理字符处理ASCII码：码：“美国信息交换用标准代

41、码集”(American Standard Code for Information Interchange)，简称ASCII码。它是用7位二进制数进行编码表示128个字符；包括字母、标点、运算符以及一些特殊符号。国际码：国际码：“中华人民共和国国家标准信息交换编码，简称为国际码，代号GB231280，是汉字编码的国家标准字符集。该字符集分为94个区，94个位，每个符号由一个区码和一个位码共同标识。区码和位码各用一个字节表示。为了能够区分为了能够区分ASCII码与汉字编码，采用字节的最高位来标识：最高位码与汉字编码，采用字节的最高位来标识：最高位为为0表示表示ASCII码；最高位为码；最高位为

42、1表示表示汉字编码。表示表示汉字编码。字库字库：为了在显示器等输出设备上输出字符，系统中必须装备有相应的字库。字库中存储了每个字符的形状信息，字库分为矢量型矢量型和点阵型点阵型两种。字库中储存了每个字符的图形信息。2.4.1 2.4.1 点阵字符点阵字符在点阵表示中，每个字符由一个点阵位图点阵位图来表示显示时显示时：形成字符的象素图案字符的象素图案存储空间庞大，存储空间庞大，可采用轮廓字型法压缩可采用轮廓字型法压缩黑白段压缩黑白段压缩1111110001010101010101010111110001010101010101011111110000000000点阵字库中的位图表示 矢量轮廓字符

43、2.4.2 2.4.2 矢量字符矢量字符矢量字符采用直线和曲线段来描述字符形状，矢量字符库中记录的是笔划笔划信息信息。显示时显示时：解释字符的每个笔划信息存储空间小，方便变换 特点：l点阵字符：存储量大，易于显示l矢量字符：存储量小，美观，变换方便; 但需要光栅化后才能显示。字符属性字符属性l字体字体 宋体 仿宋体 楷体 黑体 隶书l字高字高 宋体 宋体 宋体 宋体l字宽字宽l字倾斜角字倾斜角 倾斜 倾斜l对齐对齐 (左对齐、中心对齐、右对齐)l字色字色 红色红色、绿色绿色、蓝色蓝色 大海 大海 大海 大海补充：补充： 属性处理属性处理当前属性值表当前属性值表1. 线型处理实心段和中间空白段的

44、长度（象素数目）可用象素模象素模板板(pixel mask，例如（例如（16*16） )指定。存在问题存在问题：如何保持任何方向的划线长度近似地相等解决解决可根据线的斜率来调整实心段和中间空白段的象素数目。2. 线刷子和方刷子处理线宽线刷子：垂直刷子、水平刷子线刷子：垂直刷子、水平刷子特点特点 实现简单、效率高。 斜线与水平(或垂直)线不一样粗。 当线宽为偶数个象素时，线的中心将偏移半个象素。 利用线刷子生成线的始末端总是水平或垂直的，看起来不太自然。解决解决：添加“线帽（line cap）” 当比较接近水平的线与比较接近垂直的线汇合时，汇合处外角将有缺口解决解决：斜角连接（miter joi

45、n）、圆连接（round join）、斜切连接（bevel join）方刷子方刷子特点特点： 方刷子绘制的线条（斜线）比用线刷子所绘制的线条要粗一些 方刷子绘制的斜线与水平（或垂直）线不一样粗 方刷子绘制的线条自然地带有一个“方线帽”3. 其它线宽处理方式 区域填充区域填充 改变刷子形状改变刷子形状： 2.5 裁裁 剪剪 裁剪：确定图形中哪些部分落在显示区之内，哪些落在显示区之外,以便只显示落在显示区内的那部分图形。这个选择过程称为裁剪裁剪。 在使用计算机处理图形信息时，计算机内部存储的图形往往比较大，而屏幕显示的只是图的一部分。2.5.1 直线段裁剪 Cohen-SutherlandCohe

46、n-Sutherland法（区域法（区域编码法）编码法） 中点分割裁剪算法中点分割裁剪算法 梁友栋梁友栋-Barskey-Barskey裁剪算法裁剪算法Cohen-SutherlandCohen-Sutherland法（区域编码法）法（区域编码法） 对每条线段对每条线段P1P2的处理可的处理可分为三种情况分为三种情况（1） P1P2完全处于窗口之内，完全处于窗口之内，则显示该线段则显示该线段（2） P1P2完全处于窗口之外，完全处于窗口之外，则丢弃该线段则丢弃该线段（3）若线段不满足以上两种情）若线段不满足以上两种情况，况，则在交点处把线段分为两段，则在交点处把线段分为两段，其中一段完全处于窗

47、口外，丢弃其中一段完全处于窗口外，丢弃之，之，然后对另一段重复上述处理然后对另一段重复上述处理P P1 1P P2 2P P3 3P P4 4 为了快速判断直线与窗口的关系，对窗口可采取编码方法，为了快速判断直线与窗口的关系，对窗口可采取编码方法，将二维平面分成将二维平面分成9个区域，每个区域赋予个区域，每个区域赋予4位编码位编码CtCbCrCl02&1codecode101010100110011010001000000000000001000101010101010001001001100100100010则说明该线段完全在窗口外则说明该线段完全在窗口外判断条件：判断条件：02&1code

48、code则说明该线段可能与窗口有交点则说明该线段可能与窗口有交点中点分割裁剪算法中点分割裁剪算法 在区域编码的基础上进行改进，完全在窗口内和完全在窗口外采用之前的处理方法，对不完全在窗口内： 寻找距离寻找距离P0P1最近的可见点最近的可见点P P3 3P P4 4P P1 1P P2 2P Pm m 设要裁剪的线段是设要裁剪的线段是P P0 0P P1 1。 P P0 0P P1 1和窗口边界交于和窗口边界交于A,B,C,DA,B,C,D四点，见四点，见图。算法的基本思想是从图。算法的基本思想是从A,BA,B和和P P0 0三点中找出最靠近的三点中找出最靠近的P P1 1点，图中要点，图中要找

49、的点是找的点是P P0 0。从。从C,DC,D和和P P1 1中找出最中找出最靠近靠近P P0 0的点。图中要找的点是的点。图中要找的点是C C点。点。那么那么P P0 0C C就是就是P P0 0P P1 1线段上的可见部线段上的可见部分。分。梁友栋梁友栋-Barskey-Barskey裁剪算法裁剪算法 线段的线段的参数表示参数表示x=x0+txy=y0+ty 0=t tl,则可见线段区间 tl , tut0t1t2t301始边和终边的确定及交点计算：令 QL= - x DL= x0-xL QR= x DR= xR-x0 QB= - y DB= y0-yB QT= y DT= yT-y0交点

50、为 ti= Di / Qi i=L,R,B,TQi 0 ti为与终边交点参数Qi =0 Di 0 时, 分析另一D, EFAB当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二 多边形的裁剪 错觉错觉：直线段裁剪的组合？ 新的问题新的问题：1）边界不再封闭，需要用窗口边界的恰当部分来封闭它，如何确定其边界？ Sutherland-

51、Hodgman算法（逐边裁剪算法逐边裁剪算法） 分割处理策略分割处理策略：将多边形关于矩形窗口的裁剪分解为多边形关于窗口四边所在直线的裁剪。 流水线过程流水线过程(左上右下左上右下)：前边的结果是后边的输入。亦称亦称逐边裁逐边裁剪算法剪算法Sutherland-Hodgman算法 基本思想是一次用窗口的一条边裁剪多边形。 考虑窗口的一条边以及延长线构成的裁剪线该线把平面分成两个部分:可见一侧；不可见一侧 多边形的各条边的两端点S、P。它们与裁剪线的位置关系只有四种可见一侧可见一侧可见一侧可见一侧SpSSSppp(1)(2)(3)(4)Sutherland-Hodgman算法 情况（1）仅输出顶

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

53、如图所示显示出一条多余的直线。这种情况在裁剪后的多边形有两个或者多个分离部分的时候出现。因为只有一个输出顶点表，所以表中最后一个顶点总是连着第一个顶点。 解决这个问题有多种方法，一是把凹多边形分割成若干个凸多边形，然后分别处理各个凸多边形。二是修改本算法，沿着任何一个裁剪窗口边检查顶点表，正确的连接顶点对。再有就是Weiler-Atherton算法。2.双边裁剪法（Weiler-Atherton算法）裁剪窗口为任意多边形（裁剪窗口为任意多边形（凸、凹、带内环）的情况：的情况：l主多边形：被裁剪多边形，记为主多边形：被裁剪多边形，记为Ps l裁剪多边形：裁剪窗口，记为裁剪多边形：裁剪窗口，记为P

54、cl同时设每一多边形按顺时针方向排列，则右边为多同时设每一多边形按顺时针方向排列，则右边为多边形的内部（内环相反）边形的内部（内环相反）l算法首先沿算法首先沿Ps任一点出发，跟踪检测任一点出发，跟踪检测Ps的每一条边，的每一条边，当当Ps与与Pc相交时：相交时： 1.若若Ps的边进入的边进入Pc，则继续沿，则继续沿Ps的边往下处理，同时输出该线的边往下处理，同时输出该线段；段； 2.若若Ps的边是的边是Pc出来，则从此点出来，则从此点（前交点）开始，沿着窗口边（前交点）开始，沿着窗口边框向右检测框向右检测Ps的边，即用的边，即用Pc的的有效边框去裁剪有效边框去裁剪Ps的边，找到的边，找到Ps与

55、与Pc最靠近前交点的新交点，最靠近前交点的新交点，同时输出由前交点到此新交点同时输出由前交点到此新交点之间窗边上的线段；之间窗边上的线段； 3.返回前交点，再沿返回前交点，再沿Ps处理各条处理各条边，直到处理完所有边，直到处理完所有Ps的边，的边，返回起点为止。返回起点为止。起点起点2 21 13 34 45 56 67 78 89 9101011111313PcPcPsPsP P1 1P P6 6P P5 5P P4 4P P3 3P P2 2Q Q1 1P P8 8P P7 7Q Q6 6Q Q5 5Q Q4 4Q Q3 3Q Q2 22.6 2.6 反走样反走样用离散量表示连续量引起的失

56、真，就叫做走样（走样（Liasing）。走样现象走样现象： 一是光栅图形产生的阶梯形 一是图形中包含相对微小的物体时，这些物体在静态图形中容易被丢弃或忽略，在动画序列中时隐时现，产生闪烁用于减少或消除这种效果的技术，称为反走样反走样（antialiasing）。常用的反走样方法有：提高分辨率、区域采样和加权区域采样提高分辨率、区域采样和加权区域采样如：阶梯程度小一倍，但存储空间大阶梯程度小一倍，但存储空间大4倍，扫描时间大倍，扫描时间大2倍倍过取样（过取样（supersampling），或后滤波后滤波区域取样（区域取样（area sampling），或前滤波前滤波2.6.1 过取样过取样简单过

57、取样：简单过取样：将屏幕看成是比实际所具有的更细的网格来增加取样率，将屏幕看成是比实际所具有的更细的网格来增加取样率，而后沿这种更细网格使用取样点来确定每个屏幕象素的合适亮度等级。例：而后沿这种更细网格使用取样点来确定每个屏幕象素的合适亮度等级。例：对于直线段的灰度显示，可以将每个象素分成一定数目的子象素并统计沿对于直线段的灰度显示，可以将每个象素分成一定数目的子象素并统计沿线路径的子象素数目，将每个象素的亮度等级设置为正比于这个子象素数线路径的子象素数目，将每个象素的亮度等级设置为正比于这个子象素数目的值。目的值。 2.6.2 2.6.2 简单的区域取样简单的区域取样当直线段与像素有交时，求

58、出两者相交区域的面积，当直线段与像素有交时，求出两者相交区域的面积，然后根据相交区域面积的大小确定该像素的灰度值。然后根据相交区域面积的大小确定该像素的灰度值。如何计算直线段与象素相交区域的面积？（d d）（e e）（a a）的面积为）的面积为D D2 2/2k/2k（b b）的面积为）的面积为D-k/2D-k/2（c c）（）（d d）（）（e e）的面积可由（）的面积可由（a a）（）（b b）推出）推出也可以利用一种求相交区域的近似面积的离散计算方法：(1)将屏幕象素分割成n个更小的子象素，(2)计算中心落在直线段内的子象素的个数m，(3)m/n为线段与象素相交区域面积的近似值。特点特点

59、： 直线段对一个象素亮度的贡献与两者重叠区域的面积成正比 相同面积的重叠区域对象素的贡献相同 非加权区域采样方法有两个缺缺点：l象素的亮度与相交区域的面积成正比，而与相交区域落在象素内的位置无关，这仍然会导致锯齿效应。l直线条上沿理想直线方向的相邻两个象素有时会有较大的灰度差。2.6.3 2.6.3 加权区域取样加权区域取样加权区域取样原理加权区域取样原理l使相交区域对象素亮度的贡献依赖于该区域与象素中心的距离l当直线经过该象素时，该象素的亮度F是在两者相交区域A上对滤波器（函数w）进行积分的积分值。222221),(yxeyxw),(AdAyxwF 可采用离散计算方法l如：我们将屏幕划分为n

60、=33个子象素，加权表可以取作特点特点： 接近理想直线的象素将被分配更多的灰度值； 相邻两个象素的滤波器相交，有利于缩小直线条上相邻象素的灰度差。121242121161987654321wwwwwwwww2.7消隐 物体的消隐物体的消隐或隐藏线面的消除隐藏线面的消除：在给定视点和视线方向后，决定场景中哪些物体的表面是可见的，哪些是被遮挡不可见的。物体的消隐或隐藏线面的消除。 经过消隐得到的投影图称为物体的真实图形。 按消隐对象分类l线消隐 消隐对象是物体上的边，消除的是物体上不可见的边。 l面消隐 消隐对象是物体上的面，消除的是物体上不可见的面。 深度缓冲器算法、A缓冲器算法、区间扫描线算法