3.基本图形生成算法.ppt

第3讲基本图形生成及处理算法,华中科技大学机械学院CAD中心吴义忠cad.wyz,主要内容,3.1、光栅显示器工作原理,3.3、直线生成算法,3.4、圆弧生成算法,3.5、字符生成算法,3.6、区域填充算法,3.7、多边形裁减算法,3.8、图形的反走样,3.2、基本几何定义描述,3.1、光栅显示器工作原理,显示器用于显示字符、图形（触摸显示屏还可作为输入设备）。常规光栅显示器上的图形由荧光屏的点阵组成,CRT是通过电子枪发射电子束，经过聚焦系统、加速电极、偏转系统，按行列次序扫描点矩阵，轰击到荧光屏的不同点阵部位，被其内表面的荧光物质吸收，在该点发光产生可见的图形。,阴极射线管显示器（CathodeRadiativeTube）,彩色CRT显示器的每个扫描点（即象素）有三个荧光点（红、绿、蓝三基色），由三支电子枪通过控制各自电子束强度实现不同亮度的颜色。若每支电子枪发出的电子束的强度为256个等级，则显示器能同时显示256*256*256=16M种颜色，称为真彩色系统。,若屏幕尺寸一定，水平和竖直方向上能识别的最大像素个数描述，如800*600，1024*768，1280*1024等。,象素（Pixel）,每个象素都对应于Buffer中的一个存储单元，用来存储象素颜色（灰度）值的存储器，称为帧缓冲存储器，俗称显存。象素的亮度值控制电子束对荧光屏的轰击强度，象素在帧缓存寄存器中的位置编码控制电子束的偏转位置。,分辨率（Resolution）,每秒钟重绘屏幕的次数，CRT产生稳定图像所需要的最小刷新频率：=1秒/荧光物质的持续发光时间（Hz）,刷新频率,荧光屏上画面的每一光点称为一个象素。,与电视工作原理类似，CRT电子束从上到下、从左到右扫描进行，每扫描一遍称为一帧。,帧缓冲存储器,液晶显示器原理不同于CRT，不受刷新频率影响。但是液晶显示有拖尾现象，主要是因为液晶偏转延迟所致，延时越长，拖尾越重。,3.2、基本几何定义描述,对于一个二维CAD系统来说，直线、圆、圆弧、样条曲线是最常见的基本几何要素。对于一个三维CAD系统来说，除了具备上述要素外，还需平面、圆柱面、球面、圆环面及样条曲面。考虑到样条曲线曲面及三维几何建模将在后面章节中详细介绍，在此仅介绍直线、圆、圆弧的定义描述。,直线的定义直线通过点P1(x1,y1)和P2(x2,y2)，直线方程可表示为：二点式方程参数方程,也可表示为标准的直线方程形式：Ax+By+C=0其中：A=y2-y1，B=-(x2-x1)，C=-(Ax1+By1),也可用其它的数学表达方法来定义直线。二点式表达时应注意避免分母为0，不同的表达方法之间可相互转换，以便计算机快速稳定计算。通常直线的数据结构只需记录起点、终点坐标以及直线的属性即可,classLINEdoublex1,y1,x2,y2；intr,g,b;intlintype;intmattype;voiddraw_line();voidcal_length();voidinterpolate();,圆的定义给定圆心（xc,yc）和半径R，圆的方程表示为：一般的代数方程：（xxc)2+(y-yc)2=R2参数方程：x=xc+Rcosy=yc+Rsin,通常圆的数据结构只记录圆心、半径及其属性,classCIRCLEdoublexc,yc,R；intr,g,b;intlintype;voiddraw_circle();voidcircumference();,圆弧的定义圆弧的表示方程和圆的方程完全相同，但是圆弧还需要给出起点和圆弧的角度，通常逆时针方向为正的角度，顺时针方向为负角度。,通常圆弧的数据记录圆心、半径、起点、角度其属性。但为了快速捕捉端点，还可记录终点。,classARCdoublexc,yc,R，x1,y1,；intr,g,b;intlintype;voiddraw_arc();voidarc_length();,思考：为什么直线、圆弧的表示均不记录方程？（几何变换后方程改变）,画直线是CAD中最常用的操作。数学上的直线是没有宽度的点集，显然，光栅显示器只能近地似显示直线。画一条从（x1,y1）到（x2,y2）的直线，实质上是寻找最佳逼近直线的象素序列，并填入色彩数据的过程（如左图），这个过程也称为直线光栅化，也称直线扫描转换。目前常用算法有：直线DDA算法、中点算法、Bresenham算法等。,直线中每一点坐标都可由前一点坐标变化一个增量（x,y）而得到，即表示为递归式：xi+1=xi+x，yi+1=yi+y，并有关系：y=kx，递归式的初值为直线的起点（x1,y1），考虑象素为整数，则算法过程为：,1）直线DDA算法（即微分算法）,xx2x1，yy2y1，ky/xyi+1=kxi+1+b=k(xi+1)+b=yi+k(xi,yi)(xi+1,yi+k),yi=round(yi)=(int)(yi+0.5),算法特点,上述算法简单，易实现；但有浮点数取整运算，不利于硬件实现，效率低；算法仅适用于k1的情形：x每增加1，y最多增加1。当k1时，必须把x，y互换。,3.3、直线生成算法,算法应用举例,直线起点P0（0，0），终点P1（5，2）,DDA算法实现,2）Bresenham算法,Bresenham算法是目前使用最广泛的直线生成算法。,过各行各列象素中心构造一组虚拟网格线。按直线从起点到终点的顺序计算直线与各垂直网格线的交点，然后根据误差项的符号确定该列象素中与此交点最近的象素（如下图所示）。,假设直线方程为：yi+1=yi+k(xi+1xi)，且横坐标象素为xi，其纵坐标为yi，斜率k1；那么下一个象素的横坐标为xi1，而纵坐标要么为yi，要么递增1为yi1，是否增1取决于误差项d的值。误差项d的初值d00，x坐标每增加1，d的值相应递增直线的斜率值k，即ddk。一旦d1，就把它减去1，这样保证d在0、1之间；当d0.5时，直线与垂线x=xi1交点最接近于当前象素(xi，yi)的右上方象素(xi1，yi1)；而当d0.5时，更接近于右方象素(xi1，yi)。为方便计算，令ed0.5，e的初值为0.5，增量为k；当e0时，取当前象素(xi，yi)的右上方象素(xi1，yi1)；而当e0时，取(xi，yi)右方象素(xi1，yi)。,算法举例,用Bresenham方法生成两点P0（0,0）和P1（5,2）的直线段,xye00-0.510-0.1210.331-0.3420.152-0.5,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;,算法程序,算法改进,上述Bresenham算法在计算直线斜率与误差项时用到小数与除法。可以改用整数以避免除法。由于算法中只用到误差项（初值e=dy/dx-0.5）的符号，因此可作替换：e=2*e*dx。,voidInterBresenhamline(intx0,inty0,intx1,inty1,intcolor)intx,y,dx,dy，e;dx=x1-x0;dy=y1-y0;e=2*dy-dx;/e=k-0.5*2*dxx=x0；y=y0;for(i=0;idx;i+)drawpixel(x,y,color);if(e0)y+;e=e-2*dx;/e=e1*2*dxx+;e=e+2*dy;/e=e+k*2*dx,算法避免了除法及浮点运算，且2的整倍数可采用移位操作，便于硬件实现，算法速度快，精度高。,圆也是图形系统中常用的元素。我们将圆定义为所以距离中心位置(xc,yc)为给定值r的点集。圆的方程为：,圆的定义,为叙述方便，仅考虑圆心在原点的圆（其它位置圆可平移到原点位置）。不妨设函数：,显然有：F（x，y）0，则（x,y)位于圆边界外,考虑圆的八对称性，不妨以第二个八分圆进行分析，其它八分圆则可通过镜像实现。,构造判别式,3.4、圆弧生成算法,圆的扫描转换算法有：直接离散法、中点法、Bresenham算法等。,圆的中点算法算法思路如下：根据右图，圆上的点满足判别式：,F(x,y)=x2+y2R2=0中点M：M=(xp+1,yp-0.5)将中点M代入判别式得：,当d0时，M在圆内，P1距离圆弧近，取P1(xp+1,yp)当d0时，M在圆外，P2距离圆弧近，取P2(xp+1,yp-1),若d0,取P2为下一象素，再下一象素的判别式为：,若d0,取P1为下一象素，再下一象素的判别式为：,第一个象素点是（0,R），判别式d的初始值为：,增量,中点算法（续）,为提高算法的效率，将算法中的浮点数改写成整数，用e=d0.25代替d，增量不变，取e0=1R，则算法为：,MidpointCircle(r,color)x=0;y=r;d=1.25-r;drawpixel(x,y,color);while(xy)if(d0)d+=2*x+3;x+;elsed+=2*(x-y)+5;x+;y+;drawpixel(x,y,color);,MidpointCircle_1(r,color)x=0;y=r;e=1-r;drawpixel(x,y,color);while(xy)if(e=ymin)即可。对其它边界也一样。,2）向量叉积法：为简单计，测试点表示为P点。假设窗口边界方向为顺时针，如图中所示，对于其中任一边界向量，从向量起点A向终点B看过去，如果被测试点P在该边界线右边(即内侧)，ABAP的方向与X-Y平面垂直并指向屏幕里面，即右手坐标系中Z轴的负方向。,反过来，如果P在该边界线的左边(即外侧)，这时ABAP的方向与X-Y平面垂直并指向屏幕外面，即右手坐标系中Z轴的正方向。,SutherlandHodgeman多边形裁剪算法具有一般性，被裁剪多边形可以是任意多边形，裁剪窗口不局限于矩形，可以是任意凸多边形。上面的算法是多边形相对窗口的一条边界进行裁剪的实现，对于窗口的每一条边界依次调用该算法程序，并将前一次裁剪的结果多边形作为下一次裁剪时的被裁剪多边形，即可得到完整的多边形裁剪程序。,算法特点：,3）剖面线算法（任意多边形裁减）,剖面线是一组等距的平行线，用填充算法速度慢，直接多边形裁减更快，算法步骤：i)按多边形的初始条件及剖面线的角度和间距，计算剖面线的范围和数量；ii)求剖面线与轮廓边的相交位置；iii）对剖面线上的交点进行排序，并按奇偶规则绘制有效剖面线段。简化技巧：1)跳过顶点处交点判断，避免奇异性判断2)图形变换使剖面线成为水平线（或铅垂线），简化加速求交计算。,在光栅显示器上显示图形时，直线段或图形边界或多或少会呈锯齿状。原因是图形信号是连续的，而在光栅显示系统中，用来表示图形的却是一个个离散的象素。这种用离散量表示连续量引起的失真现象称之为走样(aliasing)；用于减少或消除这种效果的技术称为反走样(antialiasing)。光栅图形的走样现象：阶梯状边界，如图(a)所示，画出的直线边界实际上是阶梯状；图形细节失真（比象素更窄的细节变宽，如图(b)）；狭小图形遗失（如图(c)，在动画序列中将时隐时现，产生闪烁）。,因为计算机屏幕是不连续的离散象素组成，每个象素覆盖一定面积，而每个象素只能显示一种颜色。也就是说，该象素只能显示该覆盖区域某一点处的颜色，不可能反映整个区域颜色，于是出现失真或图形丢失。,常用的反走样方法主要有：提高分辨率、区域采样、加权区域采样等。,图(a),图(b),图(c),反走样基本概念：,3.8、图形的反走样,1）提高分辨率的反走样方法,方法简单，代价大。如显示器水平与竖直分辩率提高1倍，则显示器点距减1倍，帧缓存容量则增加到原来的4倍，扫描转换同样大小的图元却要花4倍时间。,2）区域采样反走样方法,1）将直线段看作具有一定宽度的狭长矩形；2）直线段矩形与某象素正方形有交（或覆盖）时，求相交（或覆盖）区域面积；3）根据相交区域面积，确定该象素的亮度值,直线段对一个像素亮度的贡献与相交区域面积成正比；当直线段和某个像素不相交时，它对该像素的亮度无影响；相同面积的相交区域对像素