单击此处编辑母版标题样式,,单击此处编辑母版文本样式,,第二级,,第三级,,第四级,,第五级,,*,华中理工大学计算机学院 陆枫 99-7,*,计算机图形学,,教学要求,了解图形系统的框架及其涉及的软件、硬件技术；,,了解图形学的基本问题，掌握图形学的基本概念、方法与算法；,,对与图形相关的应用及当前的研究热点有一个初步认识；,,具有一定实践体会和相关的编程能力本课程的主要内容,绪论,,光栅图形学,,扫描转换、裁减、反走样、消影,,几何造型,,曲线曲面造型、实体造型,,真实感图形学,,Phong,模型、光线跟踪、辐射度算法,,指导实验,,主要参考书目,孙家广，计算机图形学（第三版），清华大学出版社，1999唐泽圣，计算机图形学基础，清华大学出版社，1995,,Donald Hearn, M. Pauline Baker ,,“,Computer Graphics (C Version),”,, Prentice Hall , 1997.,,James D. Foley, Andries van Dam etc.,,“,Introduction to Computer Graphics,”,, Addison-Wesley, 1996,,,唐荣锡，计算机图形学教程（修订版），科学出版社，2000,,计算机辅助设计与图形学学报,,中国图形图像学报,成绩评定办法,作业、考勤、实验：,20%,,笔试,：,8,0%,第1章 引言,提出问题,什么是计算机图形学？,,计算机图形学研究的对象是什么？,,计算机图形处理系统的构造？,1.1 计算机图形学及其相关概念,什么是,计算机图形学？,（,Computer Graphics）,,计算机图形学,是研究怎样利用计算机来显示、生成和处理图形的原理、方法和技术的一门学科。
IEEE,定义：,Computer graphics,is the art or science of producing graphical images with the aid of computer,.,,,,,,3D,虚拟影像摄影系统,,协同工作摄影机,,面部表演捕捉还原系统,计算机图形学与传统理论,：,,,交叉、界线模糊、相互渗透,,,CAGD（,计算几何）,,逼近论（计算数学）,,微分几何,,形态学,,混沌学,,小波理论,计算机图形学的研究对象——图形,,通常意义下的图形,：,,能够在人的视觉系统中形成视觉印象的客观对象都称为图形计算机图形学中所研究的图形,,从客观世界物体中抽象出来的带有颜色及形状信息的图和形图形的表示,,点阵法,是用具有颜色信息的点阵来表示图形的一种方法，它强调图形由哪些点组成，并具有什么灰度或色彩参数法,是以计算机中所记录图形的形状参数与属性参数来表示图形的一种方法通常把参数法描述的图形叫做,图形（,Graphics）,,把点阵法描述的图形叫做,图像（,Image）,end,与计算机图形学相关的学科,,,计算机图形学,试图从非图象形式的数据描述来生成（逼真的）图象。
数字图象处理,旨在对图象进行各种加工以改善图象的视觉效果计算机视觉,是研究用计算机来模拟生物外显或宏观视觉功能的科学和技术end,酝酿期（50年代）,,1950年，美国,MIT,的旋风1号(,Whirlwind I),计算机配备了阴极射线管(,CRT),来显示一些简单的图形，不具备人,-,机交互功能,1.2 计算机图形学的发展,1.2.1计算机图形学的确立,萌芽期（60年代）,,1962,年，美国,MIT,林肯实验室的,Ivan.E.Sutherland,发表了一篇题为",Sketchpad：,一个人－机通信的图形系统"的博士论文，其中首次使用了“,Computer Graphics”,,提出图形学的概念，成就“图形学之父”的英名,,获“图灵”奖,,,IEEE,计算机杰出成就奖,,,Coons,奖,,发展期（70年代）,,普及期（80年代）,,出现了带有光栅图形显示器的个人计算机和工作站,,提高增强期（90年代）,,总体特征,：,技术发展、需求驱动,,1.3 计算机图形学的应用,CAD/CAM,,可视化与可视计算,,海量的数据的图形表示,,1986,年，美国科学基金会（,NSF,）专门召开了一次研讨会，会上提出了“科学计算可视化（,Visualization in Scientific omputing,）”,,科学计算可视化广泛应用于医学、,,流体力学、有限元分析、气象分,,析当中,,在医学领域：机械手术和远程手,,术，医用,CT,扫描数据的三维重建，,,基于,CT,数据的人体内漫游,,,计算机动画,,二维动画,,图象变形,,形状混合,,三维动画,,关键帧动画,,变形物体的动画,,过程动画,,关节动画与人体动画,,基于视频,(Video),的动画,,虚拟现实,4,图形设备,图形显示设备,,,图形输出包括图形的显示和图形的绘制，,图形显示,指的是在屏幕上输出图形,,,图形绘制,通常指把图形画在纸上，也称硬拷贝，打印机和绘图仪是两种最常用的硬拷贝设备,,彩色,CRT,显示器,,,CRT,（,CRT Cathode,－,Ray Tube,，阴极射线管）,,组成,,电子枪,,聚焦系统,,加速系统,,磁偏转系统,,CRT,显示器的简易结构图,,工作原理,,高速的电子束由,电子枪,发出，经过,聚焦系统,、,加速系统,和,磁偏转系统,就会到达荧光屏的特定位置。
由于荧光物质在高速电子的轰击下会发生电子跃迁，即电子吸收到能量从低能态变为高能态由于高能态很不稳定，在很短的时间内荧光物质的电子会从高能态重新回到低能态，这时将发出荧光，屏幕上的那一点就会亮了,,,要保持显示一幅稳定的画面，必须不断地发射电子束,,电平控制器,是用来控制电子束的强弱的，当加上正电压时，电子束就会大量通过，将会在屏幕上形成较亮的点，当控制电平加上负电压时，依据所加电压的大小，电子束被部分或全部阻截，通过的电子很少，屏幕上的点也就比较暗,,,聚焦系统,是一个电透镜，能使众多的电子聚集于一点,,,加速阳极,使电子达到轰击激发荧光屏应有的速度最后由磁偏转系统来达到指定位置,,电子束要到达屏幕的边缘时，偏转角度就会增大到达屏幕最边缘的偏转角度被称为,最大偏转角,,CRT,显示器屏幕越大整个显象管就越长,,刷新频率,,刷新,一次是指电子束从上到下扫描一次的过程,,刷新频率高到一定值后，图象才能稳定显示,,隔行扫描与逐行扫描,电子束扫描过程示意图,,彩色,CRT,显示器,显示彩色的原理,,彩色,CRT,显示器的荧光屏上涂有三种荧光物质，它们分别能发红、绿、兰三种颜色的光而电子枪也发出三束电子束来激发这三种物质，中间通过一个控制栅格来决定三束电子到达的位置,,,三束电子经过荫罩的选择，分别到达三个荧光点的位置。
通过控制三个电子束的强弱就能控制屏幕上点的颜色,荫罩式彩色,CRT,显色原理,end,,LCD,显示器,,CRT,固有的物理结构限制了它向更广的显示领域发展,,屏幕的加大必然导致显象管的加长，显示器的体积必然要加大，在使用时候就会受到空间的限制,,CRT,显示器是利用电子枪发射电子束来产生图像，容易受电磁波干扰,,长期电磁辐射会对人们健康产生不良影响,,LCD,显示器的优点,,外观小巧精致，厚度只有,1~5cm,左右不会产生,CRT,那样的因为刷新频率低而出现的闪烁现象,,,工作电压低，功耗小，节约能源,,,没有电磁辐射，对人体健康没有任何影响,索尼公司的两款,LCD,外形,,LCD,显示器基本原理,,液晶是一种介于液体和固体之间的特殊物质，它具有液体的流态性质和固体的光学性质当液晶受到电压的影响时，就会改变它的物理性质而发生形变，此时通过它的光的折射角度就会发生变化，而产生色彩,,液晶屏幕后面有一个背光，这个光源先穿过第一层偏光板，再来到液晶体上，而当光线透过液晶体时，就会产生光线的色泽改变，从液晶体射出来的光线，还得必须经过一块彩色滤光片以及第二块偏光板,,液晶显示有主动式和被动式两种,,被动式液晶屏幕有,STN,（,Super TN,超扭曲向列,LCD,）和,DSTN,（,Double layer Super TN,双层超扭曲向列,LCD,）等,,最流行的主动式液晶屏幕是,TFT,（,Thin Film Transistor,薄膜晶体管）,,主动式液晶显示器使用了,FET,场效晶体管以及共通电极，这样可以让液晶体在下一次的电压改变前一直保持电位状态。
这样主动式液晶显示器就不会产生在被动式液晶显示器中常见的鬼影、或是画面延迟的残像等,,LCD,显示器的基本指标,,可视角度,,视线与屏幕中心法向成一定角度时，人们就不能清晰地看到屏幕图象，而那个能看到清晰图象的最大角度被我们称为可视角度一般所说的可视角度是指左右两边的最大角度相加工业上有,CR10,（,Contrast Ratio,）、,CR5,两种标准来判断液晶显示器的可视角度,,点距与分辨率,,液晶屏幕的点距就是两个液晶颗粒（光点）之间的距离，一般,0.28~0.32mm,就能得到较好的显示效果,,通常所说的液晶显示器的分辨率是指其真实分辨率，表示水平方向的像素点数与垂直方向的像素点数的乘积,,end,第一章 小结,1,、计算机图形学的概念,,什么是,计算机图形学,、,图形的种类,、,相关的学科,,2,、计算机图形学的发展、应用,,3,、图形显示设备,,CRT,、,LCD,,第二章 光栅图形学,光栅图形学的研究内容,:,,,直线段的扫描转换,算法,,圆弧的扫描转换算法,,多边形的扫描转换与区域填充,,字符,,裁剪,,反走样,,消隐,图形的生成：,是在指定的输出设备上，根据坐标描述构造二维几何图形。
图形的扫描转换,：,在光栅显示器等数字设备上确定一个最佳逼近于图形的象素集的过程光栅图形显示器可以看作一个像素的,矩阵,,确定最佳逼近图形的像素集合，并用指定属性写像素的过程称为图形的,扫描转换,/,光栅化,,二维图形的光栅化必须确定区域对应的像素集，并用指定的属性或图案显示，称为,区域填充,,确定图形的哪部分需要显示，哪部分不需要显示的过程称为,裁剪,,因像素逼近误差导致图形产生畸变的现象称为,走样,,用于减少或消除走样的技术称为,反走样,,删除图形中隐藏的部分称为,消隐,2.1,直线的扫描转换,,直线的绘制要求：,,1.直线要直,,2.直线的端点要准确，即无定向性和断裂情况,,3.直线的亮度、色泽要均匀,,4.画线的速度要快,,5.要求直线具有不同的色泽、亮度、线型等,2.1.1,数值微分,(DDA),法,基本思想,,,已知过端点 的直线段,L,：,,直线斜率为,,,,从 的左端点 开始，向 右端点步进步长,=1(,个象素,),，计算相应的,y,坐标 ；取象素点,(x, round(y)),作为当前点的坐标。
作为最底层的光栅图形算法，在通常的,CAD/,图形系统中，会被大量应用，因此，哪怕节约一个加法或减法，也是很了不起的改进由此出发点，导致增量算法的思想计算,,,,当 时,;,,即：当,x,每递增,1,，,y,递增,k(,即直线斜率,),；,,,,,,,,例：画直线段,,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,,注：,网格点表示象素,,void DDALine(int x,0,,int y,0,,int x,1,,int y,1,,int color),,,,,,int x,；,,,float dx, dy, y, k;,,d,x,, = x,1,-x,0,, d,y,=y,1,-y,0,;,,k=dy/dx, y=y,0,;,,for (x=x,0,; x,,x,1,, x++),,,,drawpixel (x, int(y+0.5), color);,,y=y+k;,,,,,,,,问题：,,当,,k,,,,1,时，会如何？,(,答案见下页,),,注意上述分析的算法仅适用于,,k,,,≤,1,的情形。
在这种情况下，,x,每增加,1, y,最多增加,1,当,,k,,,,1,时，必须把,x,，,y,地位互换,,,,,,,,k,,<1,示意图,特点,：,,增量算法,,直观、易实现,,不利于用硬件实现,,思考：,,采用增量思想的,DDA,算法，每计算一个象素，只需计算一个加法，是否最优？,,,如非最优，如何改进？,2.1.2,中点画线法,,,,目标：进一步将一个加法改为一个整数加法新思路－,> DDA,算法采用两点式，可否采用其他的直线表示方式？,2.1.2,中点画线算法,直线的方程,该直线方程将平面分为三个区域：,,对于直线上的点，,F(x,y)=0；,,对于直线上方的点，,F(x,y)>0；,,对于直线下方的点，,F(x,y)<0基本原理,：,,假定0≤,k≤1，x,是最大位移方向,判别式,：,则有：,,,,,,,,,但这样做，每一个象素的计算量是,3,个加法，一个乘法如果也采用增量算法呢？,误差项的递推,,d<0：,误差项的递推,,d≥0：,初始值,d,的计算,0≤,k≤1,时中点画线算法的,算法步骤,为,：,,1.输入直线的两端点,P,0,(x,0,,y,0,),和,P,1,(x,1,,y,1,)。
2.,计算初始值△,x、△y、d=0.5-k、x=x,0,、y=y,0,；,,3.,绘制点(,x,y)判断,d,的符号；,,若,d<0，,则(,x,y),更新为(,x+1,y+1)，d,更新为,d+1-k；,,否则(,x,y),更新为(,x+1,y)，d,更新为,d-k4.,当直线没有画完时，重复步骤3否则结束思考一：能否再做改进？,,思考二：能否实现整数运算？,改进,：用2,d△x,代替,d,,1.,输入直线的两端点,P,0,(x,0,,y,0,),和,P,1,(x,1,,y,1,)2.,计算初始值△,x、△y、,d=△x-2△y,、x=x,0,、y=y,0,3.,绘制点(,x,y)判断,d,的符号若,d<0，,则(,x,y),更新为(,x+1,y+1)，d,更新为,,,d+2△x-2△y,；,,否则(,x,y),更新为(,x+1,y), d,更新为,d-2△y,4.,当直线没有画完时，重复步骤3否则结束作业：参考,DDA,代码写出中点画线算法的代码,,,,,对比：,,DDA,算法采用点斜式，中点法采用隐式表示中点法可以有整数算法思考：其,他表示可以推出整数算法吗？,,,2.1.3,改进的,Bresenham,算法,假定直线段的0≤,k≤1,,基本原理,：,误差项的计算,,d,初,=0，,,每走一步：,d=d+k,,一旦,y,方向上走了一步，,d=d-1,,算法步骤,：,,1.输入直线的两端点,P,0,(x,0,,y,0,),和,P,1,(x,1,,y,1,)。
2.,计算初始值△,x、△y、d=0、x=x,0,、y=y,0,3.,绘制点(,x,y)4.d,更新为,d+k，,判断,d,的符号若,d>0.5，,则(,x,y),更新为(,x+1,y+1)，,同时将,d,更新为,d-1；,否则(,x,y),更新为(,x+1,y)5.,当直线没有画完时，重复步骤3和4否则结束能改进么？,改进1,：令,e=d-0.5,e,初,=-0.5，,,每走一步有,e=e+kif (e>0) then e=e-1,算法步骤,为：,,1.输入直线的两端点,P,0,(x,0,,y,0,),和,P,1,(x,1,,y,1,)2.,计算初始值△,x、△y、,e=-0.5,、x=x,0,、y=y,0,3.,绘制点(,x,y)4.,e,更新为,e+k,，,判断,e,的符号若,e,>0，,则(,x,y),更新为(,x+1,y+1)，,同时将,e,更新为,e-1,；,否则(,x,y),更新为(,x+1,y)5.,当直线没有画完时，重复步骤3和4否则结束Bresenham,画线算法,void Bresenhamline(int x,0,,y,0,,int x,1,,y,1,,int color),,{,,int x,y,dx,dy;,,float k, e;,,dx = x,1,-x,0,, dy=y,1,-y,0,, k= dy/dx;,,e=-0.5, x=x,0,, y=y,0,;,,for (i=0; i<= dx; i++),,{,,drawpixel( x, y, color);,,x=x+1; e=e+k;,,if(e>=0),,{y++, e=e-1;},,},,},还能改进么？,改进2,：用2,e△x,来替换,e,,e,初,=-△,x，,,每走一步有,e=e+2△y。
if (e>0) then e=e-2△x,算法步骤,：,,1.输入直线的两端点,P,0,(x,0,,y,0,),和,P,1,(x,1,,y,1,)2.,计算初始值△,x、△y、,e=-△x,、x=x,0,、y=y,0,3.,绘制点(,x,y)4.e,更新为,e+2△y,，,判断,e,的符号若,e>0，,则(,x,y),更新为(,x+1,y+1)，,同时将,e,更新为,e-2△x,；,否则(,x,y),更新为(,x+1,y)5.,当直线没有画完时，重复步骤3和4否则结束Bresenham,画线算法的改进,void Bresenhamline(int x,0,,y,0,,int x,1,,y,1,,int color),,{,,int x,y,dx,dy,，,e,;,,,float k,e;,,dx = x,1,-x,0,,dy=y,1,-y,0,,,e=-dx;,,k= dy/dx,;,,e=-0.5,, x=x,0,,y=y,0,;,,for (i=0;i<= dx; i++),,{,,drawpixel(x,y,color);,,x=x+1;,e=e+k,;,e=e+2*dy,;,,if(e>=0),,{y++,,e=e-1,;,e=e-2*dx;},,},,},蓝色,为原算法中的语句；,,红色,为改进算法中的语句,,最终，,Bresenham,算法也是每个象素，需一个整数算法，,,其优点是可以用于其他二次曲线。
新方法：,,,BRDC: binary representation of displacement code for line,,Miao LF, Liu XG, Peng QS, Bao HJ,,COMPUTERS & GRAPHICS-UK,,26 (3): 401-408 JUN 2002,2.2,圆的扫描转换,解决的问题：,,绘出圆心在原点，半径为整数,R,的圆,x,2,+y,2,==R,2,2.2.1,八分法画圆,八分法画圆,(,y,x),(-,y,x),(-,x,y),(-,x,-y),(-,y,-x),(,y,-x),(,x,-y),解决问题,：,2.2.2,简单方程产生圆弧,算法原理,：利用其函数方程，直接离散计算,圆的函数方程为：,圆的极坐标方程为：,2.2.3,中点,Bresenham,画圆,构造函数,F(x,y)=x,2,-y,2,-R,2,对于圆上的点，有,F(x,y)=0；,,对于圆外的点，,F(x,y)>0；,,而对于圆内的点，,F(x,y)<0算法原理,当,d≤0,时，下一点取,P,u,(x,i,+1,y,i,)；,,当,d>0,时，下一点取,P,d,(x,i,+1,y,i,-1)。
M,的坐标为：,M(x,i,+1,y,i,-0.5),,当,F(x,M,,y,M,)<0,时，取,P,u,(x,i,+1,y,i,),,当,F(x,M,,y,M,)>0,时，取,P,d,(x,i,+1,y,i,-1),,当,F(x,M,,y,M,)=0,时，约定取,P,u,构造判别式,：,误差项的递推,,d≤0：,d>0：,判别式的初始值,算法步骤,：,,1.输入圆的半径,R2.,计算初始值,d=1.25-R、x=0、y=R3.,绘制点(,x,y),及其在八分圆中的另外七个对称点4.判断,d,的符号若,d≤0，,则先将,d,更新为,d+2x+3，,再将(,x,y),更新为(,x+1,y)；,否则先将,d,更新为,d+2(x-y)+5，,再将(,x,y),更新为(,x+1,y-1)5.,当,x
5.,当,x0；,,对于椭圆内的点，,F(x,y)<0解决问题,：,以弧上斜率为－1的点作为分界将第一象限椭圆弧分为上下两部分引理5-1,：若在当前中点，法向量的,y,分量比,x,分量大，即,而在下一个中点，不等号改变方向，则说明椭圆弧从上部分转入下部分法向量,椭圆的中点,Bresenham,算法,算法原理,先推导上半部分的椭圆绘制公式,判别式,若,d,1,≤0，,取,P,u,(x,i,+1,y,i,),,若,d,1,>0，,取,P,d,(x,i,+1,y,i,-1),误差项的递推,,d,1,≤0：,d,1,>0：,判别式的初始值,,再来推导椭圆弧下半部分的绘制公式,,原理,判别式,,若,d,2,>0，,取,P,l,(x,i,,y,i,-1),,若,d,2,≤0，,取,P,r,(x,i,+1,y,i,-1),误差项的递推,,d,2,>0：,d,2,≤0：,注意,：,,上半部分的终止判别,,下半部分误差项的初值,,,,算法步骤,：,,1.输入椭圆的长半轴,a,和短半轴,b。
2.,计算初始值,d=b,2,+a,2,(-b+0.25)、x=0、y=b3.,绘制点(,x,y),及其在四分象限上的另外三个对称点4.判断,d,的符号若,d≤0，,则先将,d,更新为,d+b,2,(2x+3)，,再将(,x,y),更新为(,x+1,y)；,否则先将,d,更新为,d+b,2,(2x+3)+a,2,(-2y+2)，,再将(,x,y),更新为(,x+1,y-1)5.,当,b,2,(x+1)0,时，重复步骤7和8否则结束2.3,多边形的扫描转换与区域填充,多边形的扫描转换,主要是通过确定穿越区域的扫描线的覆盖区间来填充，,,,区域填充,是从给定的位置开始涂描直到指定的边界条件为止。
2.3.1,多边形的扫描转换,多边形有两种重要的表示方法：,顶点,表示和,点阵,表示多边形的扫描转换,:,把多边形的顶点表示转换为点阵表示区域可采用内点表示和边界表示两种表示形式区域填充,:,指先将区域的一点赋予指定的颜色，然后将该颜色扩展到整个区域的过程1. 什么是多边形的扫描转换,,多边形分为凸多边形、凹多边形、含内环的多边形2.,x-,扫描线算法,,基本思想,算法步骤,：,,(1)确定多边形所占有的最大扫描线数，得到多边形顶点的最小和最大,y,值（,y,min,和,y,max,）2),从,y=y,min,到,y=y,max,，,每次用一条扫描线进行填充3)对一条扫描线填充的过程可分为四个步骤：,,,a.,求交,,,b.,排序,,,c.,交点配对,,,d.,区间填色,存在问题：,当扫描线与多边形顶点相交时，交点的取舍问题解决,：,,当扫描线与多边形的顶点相交时，,,若共享顶点的两条边分别落在扫描线的两边，交点只算一个；,,若共享顶点的两条边在扫描线的同一边，这时交点作为零个或两个0,1,1,1,1,0,2,2,2,3. 改进的有效边表算法（,Y,连贯性算法）,改进原理,：,,处理一条扫描线时，仅对有效边求交,,利用扫描线的连贯性,,利用多边形边的连贯性,,有效边（,Active Edge）,：,指与当前扫描线相交的多边形的边，也称为活性边。
有效边表（,Active Edge Table, AET）,：,把有效边按与扫描线交点,x,坐标递增的顺序存放在一个链表中，此链表称为有效边表有效边表的每个结点：,,,x ymax 1/k next,,边表（,Edge Table）,,边表的构造：,,(1)首先构造一个纵向链表，链表的长度为多边形所占有的最大扫描线数，链表的每个结点，称为一个桶，则对应多边形覆盖的每一条扫描线2)将每条边的信息链入与该边最小,y,坐标（,y,min,）,相对应的桶处也就是说，若某边的较低端点为,y,min,，,则该边就放在相应的扫描线桶中3)每条边的数据形成一个结点，内容包括：该扫描线与该边的初始交点,x（,即较低端点的,x,值），1/,k，,以及该边的最大,y,值,y,max,x|,ymin,y,max,1/k NEXT,,(4),同一桶中若干条边按,X|,ymin,由小到大排序，若,X|,ymin,,相等，则按照1/,k,由小到大排序解决顶点交点计为1时的情形,：,算法步骤,：,,(1)初始化：构造边表，,AET,表置空；,,(2)将第一个不空的,ET,表中的边与,AET,表合并；,,(3)由,AET,表中取出交点对进行填充。
填充之后删除,y=y,max,的边；,,(4),y,i+1,=y,i,+1,,根据,x,i+1,=x,i,+1/k,计算并修改,AET,表，同时合并,ET,表中,y=y,i+1,桶中的边，按次序插入到,AET,表中，形成新的,AET,表；,,(5),AET,表不为空则转(3)，否则结束2.3.2,区域填充,区域,是指已经表示成点阵形式的填充图形，它是像素集合4-邻接点,和,8-邻接点,4-连通区域,和,8-连通区域,,,把位于给定区域的边界上的象素一一列举出来的方法称为,边界表示法,边界填充算法,（,Boundary-fill Algorithm）枚举出给定区域内所有象素的表示方法称为,内点表示,泛填充算法（,Flood-fill Algorithm）,1. 边界填充算法,,算法的输入：种子点坐标(,x,y)，,填充色和边界颜色,栈结构实现,4-连通边界填充算法,的,算法步骤,为：,,种子象素入栈；当栈非空时重复执行如下三步操作：,,(1)栈顶象素出栈；,,(2)将出栈象素置成填充色；,,(3)检查出栈象素的4-邻接点，若其中某个象素点不是边界色且未置成多边形色，则把该象素入栈栈结构实现8,-连通边界填充算法,的,算法步骤,为：,,种子象素入栈；当栈非空时重复执行如下三步操作：,,(1)栈顶象素出栈；,,(2)将出栈象素置成填充色；,,(3)检查出栈象素的8-邻接点，若其中某个象素点不是边界色且未置成多边形色，则把该象素入栈。
特点,：,,可以用于填充带有内孔的平面区域把太多的象素压入堆栈,,,改进,,通过沿扫描线填充水平象素段，来代替处理4-邻接点和8-邻接点沿扫描线填充水平象素段的,4-,连通边界填充算法步骤,：,,种子象素入栈；当栈非空时作如下三步操作：,,(1)栈顶象素出栈；,,(2)填充出栈象素所在扫描行的连续象素段，直到遇到边界象素为止，即每出栈一个象素，就对包含该象素的整个扫描线区间进行填充；,,(3)在区间中检查与当前扫描线相邻的上下两条扫描线的有关象素是否全为边界象素或已填充的象素，若存在非边界、未填充边界的象素，则把每一区间的最右象素取作种子象素入栈2. 泛填充算法,,算法的输入：种子点坐标(,x,y)，,填充色和内部点的颜色算法原理,：,,算法从指定的种子(,x,y),开始，用所希望的填充颜色赋给所有当前为给定内部颜色的象素点4-,连通泛填充,算法步骤,如下：,,种子象素入栈；当栈非空时重复执行如下三步操作：,,(1)栈顶象素出栈；,,(2)将出栈象素置成填充色；,,(3)检查出栈象素的,4-,邻接点，若其中某个象素点是给定内部点的颜色且未置成新的填充色，则把该象素入栈内点表示的,4,连通区域的递归填充算法,:,,void FloodFill4(int x,int 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);,,},,},注意,：,,当以边界表示时，4-连通边界填充算法只能填充4-连通区域，8-连通边界填充算法也只能填充8-连通区域。
当以内点表示时，8-连通泛填充算法可以填充8-连通区域也可以填充4-连通区域，当然4-连通泛填充算法还是只能填充4-连通区域2.4,字符处理,ASCII,码：,“美国信息交换用标准代码集”(,American Standard Code for Information Interchange)，,简称,ASCII,码它是用,7,位二进制数进行编码表示,128,个字符；,包括字母、标点、运算符以及一些特殊符号国际码：,“中华人民共和国国家标准信息交换编码，简称为国际码，代号,GB2312－80,，是,汉字编码的国家标准字符集该字符集分为,94,个区，,94,个位，每个符号由一个区码和一个位码共同标识区码和位码各用一个字节表示为了能够区分,ASCII,码与汉字编码，采用字节的最高位来标识：最高位为,0,表示,ASCII,码；最高位为,1,表示表示汉字编码字库,：为了在显示器等输出设备上输出字符，系统中必须装备有相应的字库字库中存储了每个字符的形状信息，字库分为,矢量型,和,点阵型,两种字库中储存了每个字符的图形信息2.4.1,点阵字符,在点阵表示中，每个字符由一个,点阵位图,来表示,,显示时,：,,形成,字符的象素图案,,存储空间庞大，,,可采用轮廓字型法压缩,,黑白段压缩,,点阵字库中的位图表示 矢量轮廓字符,2.4.2,矢量字符,矢量字符采用直线和曲线段来描述字符形状，矢量字符库中记录的是,笔划信息,。
显示时,：解释字符的每个笔划信息,,存储空间小，方便变换,,特点：,,点阵字符：存储量大，易于显示,,矢量字符：存储量小，美观，变换方便,;,但 需要光栅化后才能显示字符属性,字体,宋体,仿宋体,,楷体,,黑体,隶书,,字高,,宋体,,宋体,,宋体,,宋体,,字宽,,字倾斜角,倾斜,倾斜,,对齐,,(,左对齐、中心对齐、右对齐,),,字色,,红色,、,绿色,、,蓝色,,,补充： 属性处理,当前属性值表,1. 线型处理,,实心段和中间空白段的长度（象素数目）可用,象素模板(,pixel mask,，,例如（,16*16,）,),指定存在问题,：如何保持任何方向的划线长度近似地相等,解决,,可根据线的斜率来调整实心段和中间空白段的象素数目2. 线刷子和方刷子处理线宽,,线刷子：垂直刷子、水平刷子,特点,,实现简单、效率高斜线与水平(或垂直)线不一样粗当线宽为偶数个象素时，线的中心将偏移半个象素利用线刷子生成线的始末端总是水平或垂直的，看起来不太自然解决,：添加“线帽（,line cap）”,当比较接近水平的线与比较接近垂直的线汇合时，汇合处外角将有缺口,解决,：斜角连接（,miter join）、,圆连接（,round join）、,斜切连接（,bevel join）,,方刷子,特点,：,,方刷子绘制的线条（斜线）比用线刷子所绘制的线条要粗一些,,方刷子绘制的斜线与水平（或垂直）线不一样粗,,方刷子绘制的线条自然地带有一个“方线帽”,3. 其它线宽处理方式,,区域填充,,改变刷子形状,：,,2.5,裁 剪,裁剪：,确定图形中哪些部分落在显示区之内，哪些落在显示区之外,,,以便只显示落在显示区内的那部分图形。
这个选择过程称为,裁剪,在使用计算机处理图形信息时，计算机内部存储的图形往往比较大，而屏幕显示的只是图的一部分2.5.1,直线段裁剪,Cohen-Sutherland,法（区域编码法）,,,中点分割裁剪算法,,,梁友栋,-Barskey,裁剪算法,Cohen-Sutherland,法（区域编码法）,对每条线段,P,1,P,2,的处理可分为三种情况,,（,1,）,P,1,P,2,完全处于窗口之内，,,则显示该线段,,（,2,）,P,1,P,2,完全处于窗口之外，,,则丢弃该线段,,（,3,）若线段不满足以上两种情况，,,则在交点处把线段分为两段，,,其中一段完全处于窗口外，丢弃之，,,然后对另一段重复上述处理,P,1,P,2,P,3,P,4,,,,为了快速判断直线与窗口的关系，对窗口可采取编码方法，将二维平面分成,9,个区域，每个区域赋予,4,位编码,C,t,C,b,C,r,C,l,1010,,0110,,1000,,0000,,0001,,0101,,0100,,1001,,0010,,则说明该线段完全在窗口外,判断条件：,则说明该线段可能与窗口有交点,中点分割裁剪算法,在区域编码的基础上进行改进，完全在窗口内和完全在窗口外采用之前的处理方法，对不完全在窗口内：,,,寻找距离,P,0,P,1,最近的可见点,P,3,P,4,P,1,P,2,,P,m,,设要裁剪的线段是,P,0,P,1,。
P,0,P,1,和窗口边界交于,A,B,C,D,四点，见图算法的基本思想是从,A,B,和,P,0,三点中找出最靠近的,P,1,点，图中要找的点是,P,0,从,C,D,和,P,1,中找出最靠近,P,0,的点图中要找的点是,C,点那么,P,0,C,就是,P,0,P,1,线段上的可见部分梁友栋,-Barskey,裁剪算法,,线段的,参数表示,,x=x,0,+t,△,x,,y=y,0,+t,△,y 0<=t<=1,,,△,x=x,1,-x,0,,△,y=y,1,-y,0,,窗口边界的四条边分为两类：始边和终边求出,P,0,P,1,与两条始边的交点参数,t,0,, t,1,,,令,t,l,=max(t,0,,t,1,,0),，则,t,L,即为三者中离,p,1,最近的,,点的参数,,求出,p,0,p,1,与两条终边的交点参数,t,2,, t,3,,,令,t,u,=min(t,2,,t,3,,1),，则,t,U,即为三者中离,p,0,最近的,,点的参数,,若,t,u,> t,l,,,则可见线段区间,,,[t,l,, t,u,],,,t,0,t,1,t,2,t,3,0,1,,,始边和终边的确定及交点计算：,,令,Q,L,= - △x D,L,= x,0,-x,L,,Q,R,= △x D,R,= x,R,-x,0,,,Q,B,= - △y D,B,= y,0,-y,B,,Q,T,= △y D,T,= y,T,-y,0,,交点为,t,i,= D,i,/,,Q,i,i=L,R,B,T,,Q,i,<0 t,i,为与始边交点参数,,Q,i,>0 t,i,为与终边交点参数,,Q,i,=0 D,i,<0,时,,,线段不可见,,,D,i,>0,时,,,分析另一,D,,,,E,F,A,B,,当,Q,i,=0,时,,若,D,i,<0,时,,,线段不可见,,（如图中,AB,，有,Q,R,=0,，,D,R,<0,）,,若,D,i,>0,时,,,分析另一,D,,,,（如图中的,EF,就是这种情况，它使,Q,L,=0,，,D,L,>0,和,Q,R,=0,，,D,R,>0,。
这时由于,EF,和,x=x,L,及,x=x,R,平行，故不必去求出,EF,和,x=x,L,及,x=x,R,的交点，而让,EF,和,y=y,T,及,y=y,B,的交点决定直线段上的可见部分E,F,A,B,二 多边形的裁剪,错觉,：直线段裁剪的组合？,,新的问题,：,1,）边界不再封闭，需要用窗口边界的恰当部分来封闭它，如何确定其边界？,,,Sutherland-Hodgman,算法,（,逐边裁剪算法,）,分割处理策略,：将多边形关于矩形窗口的裁剪分解为多边形关于窗口四边所在直线的裁剪流水线过程,(,左上右下,),：,前边的结果是后边的输入,亦称,逐边裁剪算法,Sutherland-Hodgman,算法,基本思想是一次用窗口的一条边裁剪多边形考虑窗口的一条边以及延长线构成的裁剪线该线把平面分成两个部分,:,可见一侧；不可见一侧,,多边形的各条边的两端点,S,、,P,它们与裁剪线的位置关系只有四种,,,Sutherland-Hodgman,算法,,,,,情况（,1,）仅输出顶点,P,；,,情况（,2,）输出,0,个顶点；,,情况（,3,）输出线段,SP,与裁剪线的交点,I,；,,情况（,4,）输出线段,SP,与裁剪线的交点,I,和终点,P,,,,Sutherland-Hodgman,算法,框图,,,,,,,,,,,处理线段,SP,过程子框图,Sutherland-Hodgman,算法,上述算法仅用一条裁剪边对多边形进行裁剪，得到一个顶点序列，作为下一条裁剪边处理过程的输入。
对于每一条裁剪边，算法框图同上，只是判断点在窗口哪一侧以及求线段,SP,与裁剪边的交点算法应随之改变Sutherland-Hodgeman,算法,对凸多边形应用本算法可以得到正确的结果，但是对凹多边形的裁剪将如图所示显示出一条多余的直线这种情况在裁剪后的多边形有两个或者多个分离部分的时候出现因为只有一个输出顶点表，所以表中最后一个顶点总是连着第一个顶点解决这个问题有多种方法，一是把凹多边形分割成若干个凸多边形，然后分别处理各个凸多边形二是修改本算法，沿着任何一个裁剪窗口边检查顶点表，正确的连接顶点对再有就是,Weiler-Atherton,算法2.,双边裁剪法,（,Weiler-Atherton,算法）,裁剪窗口为任意多边形（,凸、凹、带内环）,的情况：,,,,,,,主多边形：被裁剪多边形，记为,Ps,,裁剪多边形：裁剪窗口，记为,Pc,,同时设每一多边形按顺时针方向排列，则右边为多边形的内部（内环相反）,,算法首先沿,Ps,任一点出发，跟踪检测,Ps,的每一条边，当,Ps,与,Pc,相交时：,,1.,若,Ps,的边进入,Pc,，则继续沿,Ps,的边往下处理，同时输出该线段；,,2.,若,Ps,的边是,Pc,出来，则从此点（前交点）开始，沿着窗口边框向右检测,Ps,的边，即用,Pc,的有效边框去裁剪,Ps,的边，找到,Ps,与,Pc,最靠近前交点的新交点，同时输出由前交点到此新交点之间窗边上的线段；,,3.,返回前交点，再沿,Ps,处理各条边，直到处理完所有,Ps,的边，返回起点为止。
起点,,2,,1,,3,,4,,5,,6,,7,,8,,9,,10,,11,,13,,Pc,,Ps,,,,,,P,1,P,6,P,5,P,4,P,3,P,2,Q,1,P,8,P,7,Q,6,Q,5,Q,4,Q,3,Q,2,2.6,反走样,用离散量表示连续量引起的失真，就叫做,走样（,Liasing）,走样现象,：,,一是光栅图形产生的阶梯形,,一是图形中包含相对微小的物体时，这些物体在静态图形中容易被丢弃或忽略，在动画序列中时隐时现，产生闪烁,用于减少或消除这种效果的技术，称为,反走样,（,antialiasing）,常用的反走样方法有：,,提高分辨率、区域采样和加权区域采样,,如：,阶梯程度小一倍，但存储空间大,4,倍，扫描时间大,2,倍,,过取样（,supersampling）,，,或,后滤波,,区域取样（,area sampling）,，,或,前滤波,2.6.1,过取样,简单过取样：,将屏幕看成是比实际所具有的更细的网格来增加取样率，而后沿这种更细网格使用取样点来确定每个屏幕象素的合适亮度等级例：,对于直线段的灰度显示，可以将每个象素分成一定数目的子象素并统计沿线路径的子象素数目，将每个象素的亮度等级设置为正比于这个子象素数目的值。
2.6.2,简单的区域取样,当直线段与像素有交时，求出两者相交区域的面积，,,然后根据相交区域面积的大小确定该像素的灰度值如何计算直线段与象素相交区域的面积,？,,（,d,）,,（,e,）,（,a,）的面积为,D,2,/2k,,（,b,）的面积为,D-k/2,,（,c,）（,d,）（,e,）的面积可由（,a,）（,b,）推出,也可以利用一种求相交区域的近似面积的离散计算方法：,,(1)将屏幕象素分割成,n,个更小的子象素，,,(2)计算中心落在直线段内的子象素的个数,m，,,(3)m/n,为线段与象素相交区域面积的近似值特点,：,,直线段对一个象素亮度的贡献与两者重叠区域的面积成正比,,相同面积的重叠区域对象素的贡献相同,,,非加权区域采样方法有两个,缺,点：,,象素的亮度与相交区域的面积成正比，而与相交区域落在象素内的位置无关，这仍然会导致锯齿效应直线条上沿理想直线方向的相邻两个象素有时会有较大的灰度差2.6.3,加权区域取样,加权区域取样原理,,使相交区域对象素亮度的贡献依赖于该区域与象素中心的距离,,当直线经过该象素时，该象素的亮度,F,是在两者相交区域,A,’,上对滤波器（函数,w,）进行积分的积分值。
可采用离散计算方法,,如：我们将屏幕划分为,n=3,×,3,个子象素，加权表可以取作,,,特点,：,,接近理想直线的象素将被分配更多的灰度值；,,相邻两个象素的滤波器相交，有利于缩小直线条上相邻象素的灰度差2.7,消隐,物体的消隐,或,隐藏线面的消除,：在给定视点和视线方向后，决定场景中哪些物体的表面是可见的，哪些是被遮挡不可见的物体的消隐或隐藏线面的消除经过消隐得到的投影图称为物体的真实图形按消隐对象分类,,线消隐,,消隐对象是物体上的边，消除的是物体上不可见的边面消隐,,消隐对象是物体上的面，消除的是物体上不可见的面深度缓冲器算法、,A,缓冲器算法、区间扫描线算法等BSP,算法、多边形区域排序算法深度排序算法、区域细分算法、光线投射算法等两个基本原则：,排序,、,连贯性,,选择,z,轴的负向为观察方向,1 深度缓存器算法（,Z-buffer,算法）,Z-buffer,算法的原理,：,,例如,：,,,两块缓冲区：,,Z,缓存：,保存屏幕坐标系上各象素点所对应的深度值,,帧缓存：,保存各点的颜色Z-buffer,算法的步骤如下,：,,1．初始化：把,Z,缓存中各(,x,y),单元置为,z,的最小值，而帧缓存各(,x,y),单元置为背景色。
2．在把物体表面相应的多边形扫描转换成帧缓存中的信息时，对于多边形内的每一采样点(,x,y),进行处理：,,(1)计算采样点(,x,y),的深度,z(x,y)；,,(2),如,z(x,y),大于,Z,缓存中在(,x,y),处的值，则把,z(x,y),存入,Z,缓存中的(,x,y),处，再把多边形在,z(x,y),处的颜色值存入帧缓存的(,x,y),地址中问题：,计算采样点(,x,y),的深度,z(x,y),假定多边形的平面方程为：,Ax+By+Cz+D=0利用连贯性加速深度的计算,：,,扫描线上所有后继点的深度值：,当处理下一条扫描线,y=y-1,时，该扫描线上与多边形相交的最左边（,x,最小）交点的,x,值可以利用上一条扫描线上的最左边的,x,值计算：,,扫描线深度缓存器算法,（扫描线,Z-buffer,算法）,,特点分析,：,A,缓冲器算法,2 区间扫描线算法,算法原理,：避免对被遮挡区域的采样是进一步提高扫描线算法计算效率的关键,算法,：,,三张表,：边表、多边形表、有效边表算法的关键,：分割子区间，确定子区间上的唯一可见面特殊情形,：贯穿情形、循环遮挡情形贯穿情形,：,,为了使算法能处理互相贯穿的多边形，扫描线上的分割点不仅应包含各多边形的边与扫描线的交点，而且应包含这些贯穿边界与扫描线的交点,循环遮挡,：,,将多边形进行划分以消除循环遮挡,,例,如：,3 深度排序算法（画家算法）,算法原理,：若场景中任何多边形在深度上均不贯穿或循环遮挡，则各多边形的优先级顺序可完全确定。
深度排序算法,：,,1.将多边形按深度进行排序：距视点近的优先级高，距视点远的优先级低2.由优先级低的多边形开始逐个对多边形进行扫描转换其中的,关键是将多边形按深度进行排序,P,不遮挡,Q,的各种情况,(ab,c,d,e),及互相遮挡,f,4 区域细分算法,算法原理,,一种简单的,细分方式是将区域分割为四块大小相等的矩形,,,算法描述,：,,把物体投影到全屏幕窗口上，然后递归分割窗口，直到窗口内目标足够简单，可以显示为止A.,如果窗口内没有物体，则按背景色显示,,B.,若窗口内只有一个面，则把该面显示出来,,C.,若窗口内含有两个以上的面，则把窗口等分成四个窗口,有下列情况之一，窗口足够简单：,,1.,所有多边形均与窗口分离该窗口置背景色,,2.,只有一个多边形与窗口相交，或该多边形包含窗口，则先将整个窗口置成背景色，然后再对多边形在窗口内的部分用扫描线算法绘制3.,有一个多边形包围了窗口，或窗口与多个多边形相交，但有一个多边形包围窗口，而且在最前面最靠近观察点,可见性测试,,5 光线投射算法,算法原理,：,,算法步骤可简单描述如下,：,,1. 通过视点和投影平面（显示屏幕）上的所有象素点作一入射线，形成投影线。
2. 将任一投影线与场景中的所有多边形求交3. 若有交点，则将所有交点按,z,值的大小进行排序，取出最近交点所属多边形的颜色；若没有交点，则取出背景的颜色4. 将该射线穿过的象素点置为取出的颜色第三章 几何造型技术,在几何造型系统中，有,3,种描述物体的三维模型：,,线框模型：,用顶点和棱边来表示物体，没有面的信息,,曲面模型：,框模型的基础上添。