第2讲-计算机图形学基础-基本图形生成

华中科技大学CAD中心2.1．计算机图形学概述2.2．图形显示原理—CRT显示器工作原理—LCD显示器工作原理2.3．基本图形生成算法—直线生成算法—圆弧生成算法—其它基本图形生成2.4．图形裁减算法2.5．多边形填充算法（选学）2.6．图形反走样算法（选学）2.7．基于OpenGL图形库生成图形（选学）第2讲计算机图形学基础——基本图形生成华中科技大学CAD中心本章目的：(1)介绍显示器显示图形的基本原理；(2)介绍基本图形元素的生成算法。思考问题：1）图形如何在屏幕上显示出来？？2）CAD图形如何生成？？华中科技大学CAD中心2.1．计算机图形学概述计算机图形学主要研究用计算机进行图形信息的表达、输入、存储、显示、输出、检索及图形运算等。具体地说，大致有以下内容：(1)图形的输入：研究如何把要处理的图形输入到计算机内，以便让计算机进行各种处理。(2)产生图形的算法：研究在显示器或其它输出设备上产生图形的算法；(3)图形的数据结构：研究图形在计算机内的表示方法；(4)图形的变换：研究图形的各种几何变换；(5)图形运算：包括图形的分解、组合等；(6)图形语言：各种图形处理功能的语言;(7)图形软件的标准化：图形软件与设备无关及接口兼容性。总的来说，计算机图形学应该解决和研究下列一些问题：(1)图形表示和处理的数学方法及其实现的计算机算法；(2)设计一个好的图形软件支撑系统；(3)设计与实际应用相结合的图形应用系统。华中科技大学CAD中心一类是线条，如工程图、地图、曲线图表等；另一类是明暗图，与照片相似。为了生成图形，首先要有原始数据或数学模型，如工程人员构思的机械零件模型，飞机的总体方案模型，科学数据的可视化等等。这些数字化的输入经过计算机处理后变成图形输出。本课程重点从CAD需求角度来介绍相关研究内容：工程产品设计中的二维工程图、三维实体模型的显示本章主要介绍：基本图形生成原理图形的具体应用范围很广，但是从基本的处理技术看主要有两类：华中科技大学CAD中心2.2、图形显示原理–颜色华中科技大学CAD中心2.2、图形显示原理显示器是计算机上最常用的输出设备，用于显示文本和图形图像。目前显示器多为平板显示器（LCD，LED、PDP，OLED），阴极射线管（CRT）。CRT是通过电子枪发射电子束，经过聚焦系统、加速电极、偏转系统，按行列次序扫描点矩阵，轰击到荧光屏的不同点阵部位，被其内表面的荧光物质吸收，在该点发光产生可见的图形。——阴极射线管显示器（CRT）华中科技大学CAD中心彩色CRT显示器包含数以百万计的磷光点，成阵列排列。每个阵列点（称为象素）有三个荧光点（红、绿、蓝三色），由三支电子枪控制各自电子束强度实现不同亮度颜色，分别为红色、绿色和蓝色（即红、绿、蓝三基色），当通过屏幕的电子束击中它们时，就会发光呈彩色图像。若红（R）、绿（G）、蓝（B）三色每支电子枪发出的电子束强度为256个等级，则显示器能同时显示256*256*256=16M种颜色，称为真彩色系统。象素（Pixel）荧光屏上画面的每一光点称为一个象素。若屏幕尺寸一定，水平和竖直方向上能识别的最大像素个数用分辨率来描述，如800*600，1024*768，1280*1024等。分辨率（Resolution）华中科技大学CAD中心每秒钟重绘屏幕的次数，CRT产生稳定图像所需要的最小刷新频率：=1秒/荧光物质的持续发光时间（Hz）刷新频率（仅CRT）与电视工作原理类似，CRT电子束从上到下、从左到右扫描进行，每扫描一遍称为一帧。注：液晶显示器原理不同于CRT，不受刷新频率影响。但液晶显示有拖尾现象，是因液晶偏转延迟所致，延时越长，拖尾越重。帧扫描华中科技大学CAD中心每个象素都对应于Buffer中的一个存储单元，用来存储象素颜色（灰度）值的存储器，称为帧缓冲存储器。目前，显示器均采用32bit来表示颜色，其中Ｒ、Ｇ、Ｂ各８位，另８位可用于表示色彩透明度，此即颜色的ＲＧＢＡ表示。分辨率1024x1024的一帧图像，其显存所需容量：＝1024x1024x32bit/8＝４Ｍ（byte）帧缓冲存储器简称帧缓存俗称显存象素的亮度值控制电子束对荧光屏的轰击强度，象素在帧缓存寄存器中的位置编码控制电子束的偏转位置。图形系统为灵活控制图形颜色变化，往往不直接将帧缓冲器中的数值作为显示的亮度值，而是先经过颜色查找表（称调色板)产生变换值来控制光点亮度。其工作方式：显存中某位值颜色表地址屏幕上的亮度华中科技大学CAD中心LCD显示系统原理示意图华中科技大学CAD中心——液晶显示器（LCD）液晶是一种介于液体和固体之间的特殊物质，它具有液体的流态性质和固体的光学性质。当液晶受到电压的影响时，就会改变它的物理性质而发生偏转形变，此时通过它的光的折射角度就会发生变化，而产生色彩。当视线与屏幕中心法向成一定角度时，就不能清晰看到屏幕图象，其最大角度称为可视角度。目前CRT显示器被淘汰，LCD显示器是主流。家用电视也以液晶及平板电视为主流。新一代LED显示器正以其超薄、节能和全高清等技术发展迅猛，3D电视是未来发展方向。我国在高端液晶面板技术受制于人(日韩厂商)，LED面板技术不容乐观。华中科技大学CAD中心2.3．基本图形生成算法无论是液晶显示器（LCD），还是阴极射线管显示器（CRT），都是通过改变屏幕上象素点的颜色及亮度来显示图形。对于一个二维CAD系统来说，直线、圆、圆弧、自由曲线是最常见的基本几何要素。对于一个三维CAD系统来说，除了具备上述要素外，还需平面、圆柱面、球面、圆环面及自由曲面。曲线、曲面及三维形体将在后面章节介绍，本章仅介绍直线、圆弧的生成。思考：直线和圆弧如何在生成并显示??华中科技大学CAD中心画直线是CAD中最常用的操作，在光栅显示器上画线只能以点近地似显示。如下图，从（x1,y1）到（x2,y2）画直线实质上是寻找最佳逼近直线的象素序列，并填入色彩数据，该过程称为直线光栅化，也称直线扫描转换。常用算法有：直线DDA算法、中点算法、Bresenham算法等,其中以Bresenham算法效率高，应用最广泛。——直线生成算法华中科技大学CAD中心直线y=kx+b中每一点坐标(xi+1,yi+1)都可由前一点坐标(xi,yi)加一个增量（△x,△y）而得到，即：xi+1=xi+△x，yi+1=yi+△y，且△y=k·△x。设直线的起点（x1,y1）为所画直线的初值，考虑到象素为整数，于是画线算法过程可表述为：1）直线DDA算法（即微分算法）△x＝x2－x1，△y＝y2－y1，k＝△y/△xyi+1=kxi+1+b=k(xi+1)+b=(kxi+b)+k=yi+k(xi,yi)→(xi+1,yi+k)yi=round(yi)=(int)(yi+0.5)上述算法简单，易实现，但有浮点数取整运算，不利于硬件实现，效率低；算法仅适用于k≤1的情形：x每增加1，y最多增加1。当k1时，必须把x，y互换。k≤1k1华中科技大学CAD中心DDA算法实现华中科技大学CAD中心算法应用举例设直线起点P0（0，0），终点P1（5，2）012345321Line:P0(0,0)--P1(5,2)华中科技大学CAD中心2）Bresenham算法原理ddddBresenham算法是使用最广泛的直线生成算法。该算法假设过各行各列象素中心构造一组虚拟网格线，按直线从起点到终点的顺序计算直线与各垂直网格线的交点，然后根据误差项的符号确定该列象素中与此交点最近的象素（如图）。华中科技大学CAD中心算法思想：设直线方程为：yi+1=yi+k(xi+1–xi)，斜率k1，并设初始象素坐标为（xi，yi)，误差初值d0＝0。显然，若下一象素横坐标为xi＋1，则纵坐标yi+1可能为yi，或yi＋1。根据方程可知，x坐标每增加1，d的值相应递增斜率值k，即d＝d＋k；yi+1是否增1，则取决于误差项d的值，具体如下：如果d≥1，就把它减去1，这样保证d在0、1之间；当d≥0.5时，直线与垂线x=xi＋1交点最接近于当前象素(xi，yi)的右上方象素(xi＋1，yi＋1)；而当d0.5时，更接近于右方象素(xi＋1，yi)。为加速计算，令e＝d－0.5，e的初值为－0.5，增量为k，则可转化为下式判断：当e≥0时，取当前象素(xi，yi)的右上方象素(xi＋1，yi＋1)；而当e0时，取(xi，yi)右方象素(xi＋1，yi)。华中科技大学CAD中心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(e≥0){y++；e=e-1;}}}－算法程序华中科技大学CAD中心－算法举例用Bresenham方法生成两点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*dy－dx。voidInterBresenhamline(intx0,inty0,intx1,inty1,intcolor){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(e≥0){y++;e=e-2*dx;}//替换：e=e-1}}－算法特点算法避免了除法及浮点运算，速度加快，精度高。进一步改进：2的倍数可采用移位操作，便于硬件实现，速度更快。Bresenham算法改进：华中科技大学CAD中心圆也是图形系统中常用的元素。我们将圆定义为所以距离中心位置(xc,yc)为给定值r的点集。圆的方程为：222)()(ryyxxcc定义：为叙述方便，仅考虑圆心在原点的圆（其它位置圆可平移到原点位置）。不妨设函数：222),(ryxyxF显然有：F（x，y）0，则（x,y)位于圆边界内F（x，y）＝0，则（x,y)位于圆边界上F（x，y）0，则（x,y)位于圆边界外考虑到圆的八对称性，不妨以第二个八分圆进行分析，其它八分圆则可通过镜像实现。——圆弧生成算法yx(-x,y)(x,y)(-y,x)(y,x)(y,-x)(-y,-x)(-x,-y)(x,-y)oRPP1MP2圆的扫描转换算法有：直接离散法、中点法、Bresenham算法等。华中科技大学CAD中心如右图，圆上的点满足判别式：PP1MP2F(x,y)=x2+y2–R2=0中点M：M=(xp+1,yp-0.5)，将中点M代入上式得：222)5.0()1()5.0,1()(RyxyxFMFdpppp当d＜0时，M在圆内，P1距离圆弧近，取P1(xp+1,yp)当d＞0时，M在圆外，P2距离圆弧近，取P2(xp+1,yp-1)若d0,取P2为下一象素，再下一象素的判别式为：32)5.0()2()5.0,2('222pppppxdRyxyxFd若d≥0,取P1为下一象素，再下一象素的判别式为：5)(2)5.1()2()5.1,2('222ppppppyxdRyxyxFd第一个象素点是（0,R），判别式d的初始值为：RRFd25.1)5.0,1(0增量——圆的中点算法算法华中科技大学CAD中心中点算法（续前）为提高算法的效率，将算法中的浮点数改写成整数，用e=d－0.25代替d，增量不