第2讲-计算机图形学基础-基本图形生成ppt课件.pptx

《第2讲-计算机图形学基础-基本图形生成ppt课件.pptx》由会员分享，可在线阅读，更多相关《第2讲-计算机图形学基础-基本图形生成ppt课件.pptx（49页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、华中科技大学CAD中心认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目2.1计算机图形学概述2.2图形显示原理 CRT显示器工作原理 LCD显示器工作原理2.3基本图形生成算法 直线生成算法 圆弧生成算法 其它基本图形生成2.4图形裁减算法2.5多边形填充算法（选学）2.6图形反走样算法（选学）2.7基于OpenGL图形库生成图形（选学）第第2讲讲 计算机图形学基础计算机图形学基础基本图形生成基本图形生成基本图形生成基本图形生成华中科技大学CAD中心认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶

2、贫工作高度重视，已经展开了“精准扶贫”项目本章目的：(1)介绍显示器显示图形的基本原理；(2)介绍基本图形元素的生成算法。思考问题：思考问题：1）图形如何在屏幕上显示出来？2）CAD图形如何生成？华中科技大学CAD中心认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目2.12.1计算机图形学概述计算机图形学概述 计算机图形学主要研究用计算机进行图形信息的表达、输入、存储、显示、输出、检索及图形运算等。具体地说，大致有以下内容：(1)图形的输入：研究如何把要处理的图形输入到计算机内，以便让计算机进行各种处理。(2)产生图形的算法

3、：研究在显示器或其它输出设备上产生图形的算法；(3)图形的数据结构：研究图形在计算机内的表示方法；(4)图形的变换：研究图形的各种几何变换；(5)图形运算：包括图形的分解、组合等；(6)图形语言：各种图形处理功能的语言;(7)图形软件的标准化：图形软件与设备无关及接口兼容性。总的来说，计算机图形学应该解决和研究下列一些问题：(1)图形表示和处理的数学方法及其实现的计算机算法；(2)设计一个好的图形软件支撑系统；(3)设计与实际应用相结合的图形应用系统。华中科技大学CAD中心认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目l一

4、类是线条，如工程图、地图、曲线图表等；l另一类是明暗图，与照片相似。为了生成图形，首先要有原始数据或数学模型，如工程人员构思的机械零件模型，飞机的总体方案模型，科学数据的可视化等等。这些数字化的输入经过计算机处理后变成图形输出。本课程重点从CAD需求角度来介绍相关研究内容：工程产品设计中的二维工程图、工程产品设计中的二维工程图、三维实体模型的显示三维实体模型的显示本章主要介绍：本章主要介绍：基本图形生成原理基本图形生成原理图形的具体应用范围很广，但是从基本的处理技术看主要有两类：华中科技大学CAD中心认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已

5、经展开了“精准扶贫”项目2.22.2、图形显示原理、图形显示原理 颜色颜色华中科技大学CAD中心认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目2.22.2、图形显示原理、图形显示原理显示器是计算机上最常用的输出设备，用于显示文本和图形图像。目前显示器多为平板显示器（LCD，LED、PDP，OLED），阴极射线管（CRT）。CRT是通过电子枪发射电子束，经过聚焦系统、加速电极、偏转系统，按行列次序扫描点矩阵，轰击到荧光屏的不同点阵部位，被其内表面的荧光物质吸收，在该点发光产生可见的图形。阴极射线管显示器（CRT）华中科技大学

6、CAD中心认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目彩色CRT显示器包含数以百万计的磷光点，成阵列排列。每个阵列点（称为象素）有三个荧光点（红、绿、蓝三色），由三支电子枪控制各自电子束强度实现不同亮度颜色，分别为红色、绿色和蓝色（即红、绿、蓝三基色），当通过屏幕的电子束击中它们时，就会发光呈彩色图像。若红（R）、绿（G）、蓝（B）三色每支电子枪发出的电子束强度为256个等级，则显示器能同时显示256*256*256=16M种颜色，称为真彩色系统。象素（Pixel）荧光屏上画面的每一光点称为一个象素。若屏幕尺寸一定，水平

7、和竖直方向上能识别的最大像素个数用分辨率来描述，如800*600，1024*768，1280*1024等。分辨率（Resolution）华中科技大学CAD中心认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目每秒钟重绘屏幕的次数，CRT产生稳定图像所需要的最小刷新频率：=1秒 /荧光物质的持续发光时间（Hz）刷新频率（仅CRT）与电视工作原理类似，CRT电子束从上到下、从左到右扫描进行，每扫描一遍称为一帧。注：液晶显示器原理不同于CRT，不受刷新频率影响。但液晶显示有拖尾现象，是因液晶偏转延迟所致，延时越长，拖尾越重。帧扫描华

8、中科技大学CAD中心认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目每个象素都对应于Buffer中的一个存储单元，用来存储象素颜色（灰度）值的存储器，称为帧缓冲存储器。目前，显示器均采用32bit来表示颜色，其中、各位，另位可用于表示色彩透明度，此即颜色的表示。分辨率1024x1024的一帧图像，其显存所需容量：1024x1024x32bit/8（byte）帧缓冲存储器简称帧缓存俗称显存 象素的亮度值控制电子束对荧光屏的轰击强度，象素在帧缓存寄存器中的位置编码控制电子束的偏转位置。图形系统为灵活控制图形颜色变化，往往不直接将

9、帧缓冲器中的数值作为显示的亮度值，而是先经过颜色查找表（称调色板)产生变换值来控制光点亮度。其工作方式：显存中某位值显存中某位值颜色表地址颜色表地址屏幕上的亮度屏幕上的亮度华中科技大学CAD中心认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目LCD显示系统原理示意图华中科技大学CAD中心认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目 液晶显示器（LCD）液晶是一种介于液体和固体之间的特殊物质，它具有液体的流态性质和固体的光学性质。当液晶受到电压的影响时，

10、就会改变它的物理性质而发生偏转形变，此时通过它的光的折射角度就会发生变化，而产生色彩。当视线与屏幕中心法向成一定角度时，就不能清晰看到屏幕图象，其最大角度称为可视角度。目前CRT显示器被淘汰，LCD显示器是主流。家用电视也以液晶及平板电视为主流。新一代LED显示器正以其超薄、节能和全高清等技术发展迅猛，3D电视是未来发展方向。我国在高端液晶面板技术受制于人(日韩厂商)，LED面板技术不容乐观。华中科技大学CAD中心认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目2.32.3基本图形生成算法基本图形生成算法无论是液晶显示器（L

11、CD），还是阴极射线管显示器（CRT），都是通过改变屏幕上象素点的颜色及亮度来显示图形。对于一个二维CAD系统来说，直线、圆、圆弧、自由曲线是最常见的基本几何要素。对于一个三维CAD系统来说，除了具备上述要素外，还需平面、圆柱面、球面、圆环面及自由曲面。曲线、曲面及三维形体将在后面章节介绍，本章仅介绍直线、圆弧的生成。思考：思考：直线和圆弧如何在生成并显示?华中科技大学CAD中心认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目画直线是CAD中最常用的操作，在光栅显示器上画线只能以点近地似显示。如下图，从（x1,y1）到（x2

12、,y2）画直线实质上是寻找最佳逼近直线的象素序列，并填入色彩数据，该过程称为直线光栅化，也称直线扫描转换。常用算法有：直线DDA算法、中点算法、Bresenham算法等,其中以 Bresenham算法效率高，应用最广泛。直线生成算法直线生成算法直线生成算法直线生成算法华中科技大学CAD中心认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目直线y y=kx+b=kx+b中每一点坐标(xi+1,yi+1)都可由前一点坐标(xi,yi)加一个增量（x,y）而得到，即：xi+1=xi+x，yi+1=yi+y，且 y=k x。设直线的起

13、点（x1,y1）为所画直线的初值，考虑到象素为整数，于是画线算法过程可表述为：1）直线DDA算法 （即微分算法）x x x2x2x1x1，y yy2y2y1y1，k k y/y/x xy yi+1i+1=kx=kxi+1i+1+b=k(x+b=k(xi i+1)+b=(kx+1)+b=(kxi i+b)+k=y+b)+k=yi i+k+k(x(xi i,y,yi i)(x)(xi i+1+1,y,yi i+k)+k)yi=round(yi)=(int)(yi+0.5)l 上述算法简单，易实现，但有浮点数取整运算，不利于硬件实现，效率低；l 算法仅适用于k 1的情形：x每增加1，y最多增加1。当

14、 k 1时，必须把x，y互换。k 1k 1华中科技大学CAD中心认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目DDA算法实现华中科技大学CAD中心认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目算法应用举例设直线起点设直线起点P0P0（0 0，0 0），终点），终点P1P1（5 5，2 2）华中科技大学CAD中心认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目2）Bresenham算法

15、原理Bresenham算法是使用最广泛的直线生成算法。该算法假设过各行各列象素中心构造一组虚拟网格线，按直线从起点到终点的顺序计算直线与各垂直网格线的交点，然后根据误差项的符号确定该列象素中与此交点最近的象素（如图）。华中科技大学CAD中心认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目算法思想：设直线方程为：yi+1=yi+k(xi+1 xi)，斜率 k 1，并设初始象素坐标为（xi，yi)，误差初值 d0 0。显然，若下一象素横坐标为 xi1，则纵坐标yi+1可能为yi，或yi1。根据方程可知，x 坐标每增加 1，d 的

16、值相应递增斜率值 k，即 ddk；yi+1是否增1，则取决于误差项d的值，具体如下：如果 d1，就把它减去1，这样保证 d 在 0、1 之间；当 d 0.5 时，直线与垂线 x=xi 1 交点最接近于当前象素 (xi，yi)的右上方象素(xi1，yi1)；而当 d 0.5 时，更接近于右方象素(xi1，yi)。为加速计算，令e d0.5，e 的初值为0.5，增量为 k，则可转化为下式判断：当e 0 时，取当前象素(xi，yi)的右上方象素(xi1，yi1)；而当 e 0 时，取(xi，yi)右方象素(xi1，yi)。华中科技大学CAD中心认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到

17、病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目voidBresenhamline(intx0,inty0,intx1,inty1,intcolor)intx,y,dx,dy；floatk,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;算法程序华中科技大学CAD中心认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目算法举例用Bresenham方法

18、生成两点P0（0,0）和P1（5,2）的直线段 xye00-0.510-0.121-0.731-0.342-0.952-0.5华中科技大学CAD中心认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目上述计算直线斜率与误差项时用到小数与除法。可以改用整数以避免除法。由于算法中只用到误差项 e（e=dy/dx-0.5）的符号，对此误差等式两边同时乘以2*dx，并作替换：e=2*e*dx，则误差判断式变为：e=2*dydx。voidInterBresenhamline(intx0,inty0,intx1,inty1,intcolor

19、)intx,y,dx,dy，e；x=x0；y=y0;dx=x1-x0；dy=y1-y0；e=2*dy-dx;/替换：替换：e=k-0.5for(i=0;idx;i+)drawpixel(x,y,color);x+；e=e+2*dy;/替换：替换：e=e+kif(e0)y+;e=e-2*dx;/替换：替换：e=e-1算法特点算法避免了除法及浮点运算，速度加快，精度高。进一步改进：2 的倍数可采用移位操作，便于硬件实现，速度更快。Bresenham算法改进：华中科技大学CAD中心认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目圆

20、也是图形系统中常用的元素。我们将圆定义为所以距离中心位置(xc,yc)为给定值 r 的点集。圆的方程为：定义：为叙述方便，仅考虑圆心在原点的圆（其它位置圆可平移到原点位置）。不妨设函数：显然有：F（x，y）0，则（x,y)位于圆边界外考虑到圆的八对称性，不妨以第二个八分圆进行分析，其它八分圆则可通过镜像实现。圆弧生成算法圆弧生成算法圆弧生成算法圆弧生成算法yx(-x,y)(x,y)(-y,x)(y,x)(y,-x)(-y,-x)(-x,-y)(x,-y)oRP P1MP2圆的扫描转换算法有：直接离散法、中点法、Bresenham算法等。华中科技大学CAD中心认识到了贫困户贫困的根本原因，才能开

21、始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目如右图，圆上的点满足判别式：P P1M P2 F(x,y)=x 2+y 2 R 2=0中点M：M=(xp+1,yp-0.5)，将中点M代入上式得：当 d 0时，M在圆内，P1 距离圆弧近，取P1(xp+1,yp)当 d 0时，M在圆外，P2 距离圆弧近，取P2(xp+1,yp-1)若 d 0,取P2为下一象素，再下一象素的判别式为：若d 0,取P1为下一象素，再下一象素的判别式为：第一个象素点是（0,R），判别式d的初始值为：增量增量圆的中点算法算法圆的中点算法算法华中科技大学CAD中心认识到了贫困户贫困的根本原

22、因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目中点算法（续前）为提高算法的效率，将算法中的浮点数改写成整数，用 e=d 0.25 代替 d，增量不变，取 e0=1 R，则改进后的中点算法为：MidpointCircle(r,color)x=0;y=r;d=1.25-r;drawpixel(x,y,color);while(xy)if(d0)d+=2*x+3;x+;else d+=2*(x-y)+5;x+;y+;drawpixel(x,y,color);MidpointCircle_1(r,color)x=0;y=r;e=1-r;drawpixel(

23、x,y,color);while(xy)if(e0)e+=2*x+3;x+;else e+=2*(x-y)+5;x+;y-;drawpixel(x,y,color);华中科技大学CAD中心认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目中点算法示例：圆的多边形逼近算法圆的多边形逼近算法 其它画圆算法圆的Bresenham算法 圆的多边形逼近算法 华中科技大学CAD中心认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目自由曲线算法：转化为多直线段逼近，再调用画

24、直线算法。三维线框图：本质上都转化为多直线段组合，直接调用画直线算法。其它基本图形生成算法其它基本图形生成算法其它基本图形生成算法其它基本图形生成算法华中科技大学CAD中心认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目图形基本生成算法小结研究图形的基本生成算法，其宗旨是尽快提高算法的计算速度、精度及可靠性，为各种图形平台提供算法支撑。原则：尽量避免除法、浮点运算，尽可能采用整数加减及移位等运算。(写算法要力争精益求精哦写算法要力争精益求精哦 !)!)思考问题：思考问题：1）如何提高基本图形的生成算法效率2）直线的Brese

25、nham算法比DDA算法、中点算法优势在哪？还 有哪些需要改进。华中科技大学CAD中心认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目通常，直线边和窗口的关系分为如下三类：（a）整条直线在窗口内。不剪裁，全显示。（b）整条直线在窗口外。不剪裁，不显示。（c）部分直线在窗口之内，部分在窗口之外。此时，需要求出直线与窗框之交点，并将窗口外的直线部分剪裁掉，显示窗口内的部分。2.4、图形裁剪算法图形裁剪是CAD系统的基本功能，其作用是确定图形中落在显示区内的那部分图形，这个选择过程称为裁剪。只有窗口内的物体才能显示，窗口之外的物体

26、都是不可见的。1 1）直线的裁减算法）直线的裁减算法算法思路：算法思路：介绍一种 Cohen-Sutherland直线裁剪算法华中科技大学CAD中心认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目 Cohen-Sutherland Cohen-Sutherland直线裁剪算法直线裁剪算法Cohen-Sutherland直线剪裁算法以区域编码为基础，将窗口及其周围以4 bit的二进制数进行编码，4个bit分别代表窗外上、下、右、左空间的编码值。如右图左上区域编码为1001，右上区域编码为1010。窗内编码为0000。将窗口及其

27、邻域分为5个区域：上域：区域（1001，1000，1010）下域：区域（0101，0100，0110）左域：区域（1001，0001，0101）右域：区域（1010，0010，0110）内域：区域（0000）华中科技大学CAD中心认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目1）端点编码。根据直线两端点坐标值相对位置，对直线两端点进行分类编码；2）去除不需剪裁的直线。规则是：如果一条直线的两端在同一区域，则该直线不需剪裁，否则该直线为可能剪裁直线；3）剪裁可能直线。规则是：如果直线的一个端点在上（下、左、右）域，则此直线与

28、上边框求交，然后删去上（下、左、右）边框以上（下、左、右）的部分；对直线的另一端点也按该规则判断。算法思路：算法思路：I.首先将不需剪裁的直线找出，并删去其中在窗外的直线；II.然后对其余直线，逐条与窗框求交点，并将窗外部分删去。算法步骤：算法步骤：华中科技大学CAD中心认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目2 2）多边形裁剪算法）多边形裁剪算法I.每次用窗口的一条边界(包括延长线)对要裁剪的多边形进行裁剪，裁剪时，顺序地测试多边形各顶点，保留边界内侧顶点，删除外侧顶点，同时，适时地插入新顶点，即交点和窗口顶点，从

29、而得到一个新多边形顶点序列。II.然后以此新的顶点序列作为输入，相对第二条窗边界线进行裁剪，又得到一个更新的多边形顶点序列。III.依次下去，相对于第三条、第四条边界线进行裁剪，最后输出的多边形顶点序列即为所求的裁剪好了的多边形，如下图所示。(1)(2)(3)(4)算法思路：算法思路：多边形图形的裁减算法有许多，这里仅介绍Sutherland-Hodgeman算法。华中科技大学CAD中心认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目新的多边形顶点序列产生规则：在用窗口一条边界及其延长线裁剪一个多边形时，该边界线把平面分成两

30、个部分：边界内侧和边界外侧。如下图，依次考虑有序多边形的各边。假设当前处理的边为SP(箭头表示顺序，S为前一点，P为当前点)，边SP与裁剪线的位置关系有四种情况：1）S在外侧，P在内侧。则交点Q与当前点P均保存到新多边形中；2）S、P均在内侧。则当前点P保存到新多边形中；3）S在内侧，P在外侧。则交点Q保存到新多边形中；4）S、P均在外侧。则没有点被保存到新多边形中。算法加速思想：算法加速思想：关键在于提高相交判断速度，尤其图形复杂是更是如此!华中科技大学CAD中心认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目多多边边形形

31、裁裁减减算算法法示示例例cde(f)去除多余悬边去除多余悬边华中科技大学CAD中心认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目区域填充就是在一个闭合区域内填充某种颜色或图案。区域填充一般分两类：多边形填充 和 种子填充。1 1）多边形填充算法）多边形填充算法2.5、区域填充算法（选学）这类算法建立在多边形边边界的矢量形式数据之上，可用于程序填色，也可用交互填色。该算法基于几何求交算法，步骤如下：输入多边形顶点坐标；求多边形顶点中最大和最小y坐标，以确定范围；计算每条扫描线起止点（交点），并扫描填充，直至所有扫描线处理完毕

32、。扫描线多边形填充算法（Scan-Line Filling）多边形填充算法很多，这里主要介绍扫描线多边形填充算法。华中科技大学CAD中心认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目改进的边相关扫描线填充算法相邻扫描线上的交点与多边形的边相关；对同一条边，前一条扫描线yi与该边的交点为xi，而后一条扫描线 y i+1=y i +1与该边的交点则为x i+1=x i +1/m；利用相关性可省去大量求交运算。（具体算法参考图形学教材）关键在于如何快速求扫描线与多边形交点。1）扫描线填充利用画水平直线快速画法 提问题(为什么不用

33、斜线)？2）利用扫描线与多边形交点的连贯性加速求交算法 （下一条扫描线交点可直接计算，不必解方程）算法改进思路：思考：思考：工程图中的剖面线生成算法如何加速?华中科技大学CAD中心认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目这类算法建立在多边形边界的图象数据之上，并需提供多边形界内一点的坐标，一般用于人机交互填色，而难以用于程序自动填色。从多边形内部点出发，沿四连通方向（或八连通方向）扩散搜索区域内所有待填充的象素点，适用于交互绘图。算法思想：用用4连通填充算法的填充结果连通填充算法的填充结果用用8连通填充算法的填充结果

34、连通填充算法的填充结果2 2）种子填色算法（）种子填色算法（Seed FillingSeed Filling）华中科技大学CAD中心认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目给定多边形边界颜色及内部填充颜色；从内部点(x,y)开始，检测该点与边界和填充色是否相同，均不相同则填充该点；检测相邻点与边界和填充色是否相同，均不相同则填充该点；重复第步直至所有象素点被填充。算法步骤：算法特点：该算法直接基于象素，用递归算法，不必求交。但递归太多，存储不够，易造成堆栈溢出。（可用一个大的矩阵记录象素填充的状态来避免递归算法）华中

35、科技大学CAD中心认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目3 3）图案填充算法（选学）图案填充算法（选学）实际应用中，有时需要用图案来填充平面区域，只需将种子填充算法中写象素的那部分代码修改。（种子点颜色改写为定义图案对应点颜色查表即可）定义填充图案：定义一个MN的位图，并用数组存放。M、N常比需要填充区域尺寸小得多（88、1616等），图案设计成周期性的，使之重复使用构成任意尺寸图案。算法思路：算法思路：例：砖墙图案定义例：砖墙图案定义华中科技大学CAD中心认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病

36、除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目图案定位方法图案定位方法相对定位法：相对定位法：把图案原点与填充区域边界或内部的某点对齐；当被填充的多边形移动时，图案也跟着移动，看起来比较自然；对于多边形，可取边界上最左边的顶点，对于圆和椭圆这样具有光滑边界的区域，最好取区域内部某一点，如取中心与图案原点对齐。绝对定位法：绝对定位法：把图案原点与屏幕原点对齐。将整个屏幕看成被要填充的图案布满，只是要填充的区域是透明的，可以让图案显露出来，其它区域对此图案却是不透明的，图案被全部挡住。这种方法比较简单，并且在相邻区域用同一图案填充时，可以达到无缝连接的效果。但它有一个潜在的缺点，即当

37、区域移动时，图案不会跟着移动，其效果是区域内的图案变了。华中科技大学CAD中心认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目2.62.6、图形反走样算法（选学）、图形反走样算法（选学）反走样基本概念：在光栅显示器上显示图形时，直线段或图形边界或多或少会呈锯齿状。原因是图形信号是连续的，而在光栅显示系统中，用来表示图形的却是一个个离散的象素。这种用离散量表示连续量引起的失真现象称之为走样(aliasing)；用于减少或消除这种效果的技术称为反走样(antialiasing)。光栅图形的走样现象：阶梯状边界，如图(a)所示，画

38、出的直线边界实际上是阶梯状；图形细节失真（比象素更窄的细节变宽，如图(b)）；狭小图形遗失（如图(c)，在动画序列中将时隐时现，产生闪烁）。图图(a)图图(b)图图(c)华中科技大学CAD中心认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目因为计算机屏幕是不连续的离散象素组成，每个象素覆盖一定面积，而每个象素只能显示一种颜色。也就是说，该象素只能显示该覆盖区域某一点处的颜色，不可能反映整个区域颜色，于是出现失真或图形丢失。常用的反走样方法主要有：提高分辨率、区域采样、加权区域采样等。常用的反走样方法主要有：提高分辨率、区域采

39、样、加权区域采样等。提高分辨率方法提高分辨率方法 方法简单，代价大。如显示器水平与竖直分辩率提高1倍，则显示器点距减1倍，帧缓存容量则增加到原来的4倍，扫描转换同样大小的图元却要花4倍时间。思考问题：思考问题：数码相机照片也存在走样问题，分析走样的主要因素 有哪些?华中科技大学CAD中心认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目区域采样反走样方法区域采样反走样方法1）将直线段看作具有一定宽度的狭长矩形；2）直线段与某象素有交（或覆盖）时，求相交（或覆盖）区域面积；3）根据相交区域面积，确定该象素的亮度值加权区域采样方法

40、加权区域采样方法A华中科技大学CAD中心认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目 从开发CAD软件角度而言，基本图形生成算法可以自己编程实现，但受编程人员能力的制约。目前许多商业化CAD软件的基本图形生成算法均采用标准的图形库软件。典型的图形库中的基本函数用来描述图元（直线、多边形、球面、立体图形及其他对象）、设定颜色、进行旋转或其他变换等。通用图形程序设计软件包有OpenGL、VRML、DirectX、Java 2D和Java 3D等。由于图形函数库提供了程序设计语言（如C+）和硬件之间的接口，所以这一组图形函数称

41、为计算机图形应用编程接口。如果使用C编写应用程序时，可以使用图形函数进行组织并在输出设备上显示图形。2.7、基于OpenGL图形库生成图形（选学）基于VC+的OpenGL编程 当前，OpenGL是用于开发简捷的交互式二维和三维图形应用程序的最佳环境，任何高性能的图形应用程序，从3D动画、CAD辅助设计到可视化访真，都可以利用OpenGL高质量、高性能的特点。OpenGL自1992年出现以来，逐渐发展成为一个开放的，独立于应用平台的图形标准，OpenGL应用程序可以在任何平台上运行，只需要使用目标系统的OpenGL库重新编译一下。虽然微软有自己的三维编程开发工具DirectX，但它也提供Open

42、GL图形标准，因此，OpenGL可以在微机中广泛应用。OpenGL图形库除了提供基本的点、线、多边形的绘制函数外，还提供了复杂的三维物体，如球、锥、多面体、茶壶以及复杂曲线和曲面。为此，本节简单介绍OpenGL在Visual C+6.0开发环境中的编程实现。华中科技大学CAD中心认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目OpenGL的基本图元 任何复杂的三维模型都是由基本的几何图元：点、线段和多边形组成的，有了这些图元，就可以建立比较复杂的模型。OpenGL图元是抽象的几何概念，不是真实世界中的物体，因此须用相关的数学

43、模型来描述。所有的图元都是由一系列有顺序的顶点集合来描述的。OpenGL中绘制几何图元，必须使用glBegain()和glEnd()这一对函数，传递给glBegain()函数的参数唯一确定了要绘制何种几何图元，同时，在该函数对中给出了几何图元的定义，函数glEnd()标志顶点列表的结束。下面的代码绘制了一个多边形：glBegin(GL_POLYGON);glVertex2f(0.0,0.0);glVertex2f(0.0,3.0);glVertex2f(3.0,3.0);glVertex2f(4.0,1.5);glVertex2f(3.0,0.0);glEnd();GL_POLYGON 为多边

44、形图元类型，其它类型见上表华中科技大学CAD中心认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目OpenGL的基本工作流程 根据这个流程归纳出在OpenGL中渲染绘制出三维图形的基本步骤：1）根据基本图形单元建立景物模型，并且对所建立的模型进行数学描述（OpenGL中把点、线、多边形、图像和位图都作为基本图形单元）；2）把景物模型放在三维空间中的合适的位置，并且设置视点（viewpoint）以观察所感兴趣的景观；3）计算模型中所有物体的色彩，其中的色彩根据应用要求来确定，同时确定光照条件、纹理粘贴方式等；4）把景物模型的数学

45、描述及其色彩信息转换至计算机屏幕上显示。华中科技大学CAD中心认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目例：在黑色的背景下绘制一个彩色的填充三角形#include#include void background(void)glClearColor(0.0,0.0,0.0,0.0);/设置背景颜色为黑色void myDisplay(void)glClear(GL_COLOR_BUFFER_BIT);/buffer设置为颜色可写glBegin(GL_TRIANGLES);/开始画三角形glShadeModel(GL_SMO

46、OTH);/设置为光滑明暗模式 glColor3f(1.0,0.0,0.0);/设置第一个顶点为红色glVertex2f(-1.0,-1.0);/设置第一个顶点的坐标为（-1.0，-1.0）glColor3f(0.0,1.0,0.0);/设置第二个顶点为绿色glVertex2f(0.0,-1.0);/设置第二个顶点的坐标为（0.0，-1.0）glColor3f(0.0,0.0,1.0);/设置第三个顶点为蓝色glVertex2f(-0.5,1.0);/设置第三个顶点的坐标为（-0.5，1.0）glEnd();/三角形结束glFlush();/强制OpenGL函数在有限时间内运行华中科技大学CA

47、D中心认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目（续前）void myReshape(GLsizei w,GLsizei h)glViewport(0,0,w,h);/设置视口glMatrixMode(GL_PROJECTION);/指明当前矩阵为GL_PROJECTIONglLoadIdentity();/将当前矩阵置换为单位阵if(w=h)gluOrtho2D(-1.0,1.5,-1.5,1.5*(GLfloat)h/(GLfloat)w);/二维正视投影矩阵else gluOrtho2D(-1.0,1.5*(GL

48、float)w/(GLfloat)h,-1.5,1.5);glMatrixMode(GL_MODELVIEW);/指明当前矩阵为GL_MODELVIEWint main(int argc,char*argv)glutInit(&argc,argv);/*初始化*/glutInitDisplayMode(GLUT_SINGLE|GLUT_RGB);glutInitWindowSize(400,400);glutInitWindowPosition(200,200);glutCreateWindow(Triangle);/*创建窗口*/background();/*绘制与显示*/glutResha

49、peFunc(myReshape);glutDisplayFunc(myDisplay);glutMainLoop();return(0);华中科技大学CAD中心认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目VC环境下实现过程：1）首先创建工程，创建一个Win32 Console Application。2）链接OpenGL libraries。在Visual C+中先单击Project，再单击Settings，再找到Link单击，最后在Object/library modules 的最前面加上OpenGL32.lib G

50、Lu32.lib GLaux.lib3）单击Project Settings中的C/C+标签，将Preprocessor definitions 中的_CONSOLE改为_WINDOWS。最后单击OK。现在你可以把上面的例子拷贝到工程中去，编译运行。你可以看到一个彩色的三角形。图一：一个彩色的三角形注意：1）直接copy上面的程序进入VC环境时，有可能产生不可见的乱码，导致编译不通过，最好手工重新编辑。2）不同的VC版本，不同的安装路径设置有所不同，咨询有VC编程经验的同学。3）其它知识，参阅附件文档基于VC+的OpenGL编程讲座。华中科技大学CAD中心认识到了贫困户贫困的根本原因，才能开始