
维基本图形元素生成算法.ppt
65页第三章 二维基本图形元素生成算法1 基本概念基本概念n所谓图元的生成,是指完成图元的参数表示形式(由图形软件包的使用者指定)到点阵表示形式(光栅显示系统刷新时所需的表示形式)的转换通常也称扫描转换图元2课程内容程内容 §3.1 简单的二的二维图形形显示流程示流程 §3.2 直直线段的段的扫描描转换 §3.3 圆弧的弧的扫描描转换 §3.4 易画曲易画曲线的正的正负法法 §3.5 线画画图元的属性控制元的属性控制33.1 简单的二的二维图形形显示流程示流程裁剪和扫描显示图元图3-1-1 二维图形显示流程裁剪和裁剪和扫描描图形显示前需要进行扫描转换+裁剪,这一过程有三种方法:● 裁剪 ---〉扫描转换:最常用,节约计算时间● 扫描转换 ---〉裁剪:算法简单;● 扫描转换到画布 --〉位块拷贝:算法简单,但耗时耗内存常用于字符显示53.2 直直线段的段的扫描描转换n 目目标:求与直:求与直线段充分接近的像素集段充分接近的像素集n 两点假两点假设1.直线段的宽度为12.直线段的斜率: 像素间均匀网格整型坐标系图3-2-16n 描描绘线条条图形的要求形的要求q直线段要显得笔直q线段端点位置要准确q线段的亮度要均匀q转换算法速度要快73.2.1 DDA((digital differential analyzer)算法算法q条件:条件:n待待扫描描转换的直的直线段:段:n斜率:斜率: ,其中,其中n直直线方程:方程:83.2.1 DDA算法算法q直接求交算法:直接求交算法:n划分区划分区间[x , x1]:n计算算纵坐坐标::n取整:取整:n复复杂度:乘法度:乘法+加法加法+取整取整图3-2-293.2.1 DDA算法算法qDDA算法(增量算法)算法(增量算法)n复复杂度:加法度:加法+取整取整n算法算法图3-2-3103.2.1 DDA算法算法nDDA算法程序:void LineDDA ( int x0,int y0,int x1,int y1,int color) /* 假定x0 在这种情况下,x每增加1, y最多增加1当 |k| > 1时,必须把x,y地位互换,y每增加1,x相应增加1/kn特点2 在这个算法中,y与k必须用浮点数表示,而且每一步都要对y进行四舍五入后取整这使得它不利于硬件实现 133.2.1 DDA算法算法改进算法(增量DDA)n优化点: 增加斜率判断并改变循环参数143.2.1DDA算法算法nDDA画线算法程序(改进)void LineDDA ( int x0,int y0,int x1,int y1,int color){ int x,y;float dx, dy,k,l,m; dx= float(x1-x0); dy= float(y1-y0); k=dy/dx; if (abs(k)<1) { for(x=x0; x<= x1, x++) { Putpixel(x, int(y+0.5), color); y+=k; } } else { for(y=y0; y<= y1, y++) { Putpixel(int(x+0.5),y,color); x+=1/k; } }? 如果x0> x1怎么办?153.2.2 画画线中点算法中点算法q目目标:消除:消除DDA算法中的浮点运算算法中的浮点运算(浮点数取整运算,不利于硬件实现; DDA算法,效率低)q条件:条件:n同同DDA算法算法n斜斜 率:率:q直直线段的段的隐式方程式方程((x0,y0)(x1,y1)两端点)F(x,y)=ax+by+c=0 式中 a=y0-y1,b=x1-x0,c=x0y1-x1y016q基本原理基本原理: 画直线段的过程中,当前象素点为(xp, yp),一个象素点有两种可选择点p1(xp+1, yp)或p2(xp+1, yp+1)。 若M=(xp+1, yp+0.5)为p1与p2之中点,Q为理想直线与x=xp+1垂线的交点当M在Q的下方,则P2 应为下一个象素点;M在Q的上方,应取P1 为下一点 图3-2-5173.2.2 画画线中点算法中点算法3.2.2 画画线中点算法中点算法点与直线的关系: on: F(x,y)=0; up: F(x, y)>0; down: F(x, y)<0; 图3-2-6q直直线的正的正负划分性划分性183.2.2 画画线中点算法中点算法 欲判断中M在Q点的上方还是下方,只要把M代F(x,y)并 判断它的符号 构造判别式: d=F(M)=F(xp+1, yp+0.5) =a(xp+1)+b(yp+0.5)+c 当d<0,M在Q点下方,取P2为下一个象素; 当d>0,M在Q点上方,取P1为下一个象素; 当d=0,选P1或P2均可,约定取P1为下一个象素19q问题:判断距直线最近的下一个象素点 构造判别式:d=F(M)=F(xp+1,yp+0.5) 由d>0,d<0可判定下一个象素,PP2P1图3-2-7203.2.2 画画线中点算法中点算法q要判定再下一个象素,分两种情形考虑: 1)若d≥0,取正右方象素P1,再下一个象素判定,由 d1=F(xp+2,yp+0.5)=a(xp+2)+b(yp+0.5)+c=d+a,d的增量 是a 2)若d<0,取右上方象素P2,再下一个象素,由:d2=F(xp+2,yp+1.5)=d+a+b d的增量为a+bP2PP1图3-2-8213.2.2 画画线中点算法中点算法qd的初始值qd0=F(x0+1,y0+0.5)=F(z0,y0)+a+0.5*bq因(x0,y0)在直线上,F(x0,y0)=0,所以, d0=a+0.5*b qd的增量都是整数,只有初始值包含小数,可以用2d代替d, 2a改写成a+a。 q算法中只有整数变量,不含乘除法,可用硬件实现223.2.2 画画线中点算法中点算法q中点算法程序 MidPointLine(x0,y0,x1,y1,color) {int x0,y0,x1,y1,color; int a,b,d1,d2,x,y; a = y0-y1; b = x1 – x0; d = 2 * a +b; d1 = 2*a; d2 = 2*(a+b); x = x0; y = y0; PutPixel(x,y,color); while (x 该方法类似于中点法,由误差项符号决定下一个象素取右边点还是右上点 n算法原理如下:过各行各列象素中心构造一组虚拟网格线按直线从起点到终点的顺序计算直线与各垂直网格线的交点,然后确定该列象素中与此交点最近的象素该算法的巧妙之处在于采用增量计算,使得对于每一列,只要检查一个误差项的符号,就可以确定该列的所求象素 25 如下图所示 设直线方程为 ,其中k=dy/dx 假设x列的象素已经确定为xi,其行坐标为yi那么下一个象素的列坐标为xi+1,而行坐标要么不变为yi,要么递增1为yi+1图3-2-10263.2.3 画画线Bresenham算法算法 是否增1取决于如图所示误差项d的值因为直线的起始点在象素中心,所以误差项d的初值d0=0x下标每增加1,d的值相应递增直线的斜率值k,即d=d+k一旦d≥1,就把它减去1,这样保证d在0和1之间当d≥0.5时,直线与xi+1列垂直网格交点最接近于当前象素( xi ,yi)的右上方象素( xi +1, yi +1 ) ;而当d<0.5时,更接近于右方象素( xi +1,yi ) 图3-2-10273.2.3 画画线Bresenham算法算法为方便计算,令e=d-0.5,e的初值为-0.5,增量为k。 当e≥0时,取当前象素(xi,yi)的右上方象素( xi+1,yi+1 ) ;而当e<0时,更接近于右方象素( xi+1,yi ) 283.2.3 画画线Bresenham算法算法nBresenham画线算法程序 void Bresenhamline (int x0,int y0,int x1, int y1,int color) { int x, y, dx, dy; float k, e; dx = x1-x0; dy = y1- y0; k=dy/dx; e=-0.5; x=x0; y=y0; for (i=0; i<=dx; i++) { Putpixel (x, y, color); x=x+1; e=e+k; if (e>= 0) { y++, e=e-1;} } }293.2.3 画画线Bresenham算法算法n举例:用Bresenham方法扫描转换连接两点P0(0,0)和P1(5,2)的直线段x y e0 0 -0.51 0 -0.1 0.3-12 1 -0.73 1 -0.3 0.1-14 2 -0.95 2 -0.5图3-2-11303.2.3 画画线Bresenham算法算法 上述bresenham算法在计算直线斜率与误差项时用到小数与除法。 可以改用整数以避免除法由于算法中只用到误差项的符号,因此可作如下替换:e=e*2dx n改进的Bresenham画线算法程序:void InterBresenhamline (int x0,int y0,int x1, int y1,int color){ dx = x1-x0; dy = y1- y0; e=-dx; x=x0; y=y0; for (i=0; i<= dx; i++) {Putpixel (x, y, color); x++; e=e+2*dy; if (e>= 0) { y++; e=e-2*dx;} }}313.2.3 画画线Bresenham算法算法3.3圆弧的弧的扫描描转换n处理理对象:象:圆心在原点的心在原点的圆弧弧n圆的八的八对称性称性图3-3-132n两种直接离散方法:两种直接离散方法: 离散点: 离散角度: 缺点:缺点:开根,三角函数运算,计算量大,不可取 333.3圆弧的弧的扫描描转换3.3.1角度角度DDA法法转换圆弧弧 x = x0 + Rcos y = y0 + Rsindx = - Rsin ddy = Rcos dxn+1 = xn + dxyn+1 = yn + dyxn+1 = xn + dx = xn - Rsin d = xn - (yn - y0 )dyn+1 = yn + dy = yn + Rcos d = yn + (xn - x0 )d 显然,确定x,y的初值及d值后,即可以增量方式获得圆周上的坐标,然后取整可得象素坐标。 但要采用浮点运算、乘法运算、取整运算34n圆弧的正弧的正负划分性划分性圆弧外的点:F(x,y)>0圆弧内的点:F(x,y)<03.3.1 角度角度DDA法法转换圆弧弧图3-3-235n生成生成圆弧的中点算法弧的中点算法Ø考考虑对象:象:第二个八分第二个八分圆,, 第一象限的八分之一第一象限的八分之一圆弧弧 PP1P23.3.1 角度角度DDA法法转换圆弧弧图3-3-336Ø问题:与直线情形类似Ø圆弧的隐函数:F(x,y)=x2+y2-R2=0 切线斜率m in [-1,0]Ø中点 M=(xp+1,yp-0.5), 当F(M)<0时,M在圆内,说明P1距离圆弧更近,取P1;当F(M)>0时,P取P2 ;3.3.1 角度角度DDA法法转换圆弧弧37Ø构造判别式 d=F(M)=F(xp+1,yp-0.5)=(xp+1)2+(yp-0.5)2-R2 1)若d<0,取P1,再下一个象素的判别式为: d1=F (xp+2,yp-0.5)=d+2xp+3, 沿正右方向,d的增量为2xp+3; 2)若d≥0,取P2,再下一个象素的判别式为: d2=F (xp+2,yp-1.5)=d+(2xp+3)+(-2yp+2) 沿右下方向,d的增量为2(xp- yp)+5d的初始值(在第一个象素(0,R)处),d0=F(1,R-0.5)=1.25-R,算法中有浮点数, 用e=d-0.25代替3.3.1角度角度DDA法法转换圆弧弧38所以:初始化运算d0 = 1.25 – R 对应于 e 0= 1- R判别式 d < 0 对应于 e < -0.25 又因为:e的初值e0为整数,运算过程中的分量也为整数,故e始终为整数所以: e < -0.25 等价于 e < 0程序如下(完全用整数实现):MidpointCircle(r,color)Int r, color;{ int x,y,d; x = 0; y = r; d = 1-r; putpixcel(x,y,color); while( x < y) { if (d <0){ d += 2*x+3; x++; } else { d += 2*(x-y)+5; x++ ; y--; } putpixcel(x,y,color); }}393.3.2 Bresenham画画圆算法算法 现在从A点开始向右下方逐点来寻找弧AB要用的点。 如图中点Pi-1是已选中的一个表示圆弧上的点,根据弧AB的走向,下一个点应该从Hi或者Li中选择显然应选离AB最近的点作为显示弧AB的点 假设圆的半径为R,显然,当xHi2 + yHi2 -R2 ≥ R2 - (xLi2 + yLi2)时,应该取Li否则取Hi 令di = xHi2 + yHi2 + xli2 + yli2 - 2R2 显然,当di ≥0 时应该取Li否则取HiPi-1HiLi图3-3-440 剩下的问题是如何快速的计算di设图中Pi-1的坐标为(xi-1,yi-1),则Hi和Li的坐标为(xi,yi-1)和(xi,yi-1-1 )di = xi2 + yi-12 + xi2 + (yi-1-1)2 - 2R2 =2xi2 + 2yi-12 - 2yi-1 +1- 2R2 3.3.2 Bresenham画画圆算法算法di+1 = (xi + 1)2 + yi2 + (xi + 1)2 +(yi -1)2 - 2R2 =2xi2 + 4xi + 2yi2 - 2yi - 2R2 + 3Pi-1HiLi图3-3-441当di<0时->取Hi -> yi=yi-1,则 di+1 = di + 4xi-1 + 6当di≥ 0时->取Li -> yi=yi-1-1,则 di+1 = di + 4(xi-1-yi-1) + 10 3.3.2 Bresenham画画圆算法算法Pi-1HiLi图3-3-4 易知 x0=0,y0=R,x1=x0+1 因此 d0+1=12 + y02 + 12 +(y0- 1)2 - 2R2 = 3 - 2y0 = 3 - 2R421、求误差初值,p1=3-2R; i=1;画点(0, r); 2、求下一个光栅位置: x(i+1) = x(i)+1; 如果pi<0则y(i+1) = y(i) ,否则y(i+1) = y(i)-1 ;3、画点(x(i+1),y(i+1)); 4、计算下一个误差: if p(i)<0 则p(i+1) = p(i)+4x(i)+6; 否则 p(i+1)= p(i)+4(x(i)-y(i))+10;5、i=i+1; if x=y 则end;否则返2。 3.3.2 Bresenham画画圆算法算法433.3.2 Bresenham画画圆算法算法443.3.3 椭圆的的扫描描转换nF(x,y)=b2x2+a2y2-a2b=0n椭圆的对称2性,只考虑第一象限椭圆弧生成,分上下两部分,以切线斜率为-1的点作为分界点n椭圆上一点处的法向:N(x,y) = F’ (xi) + F’ (yj) = 2b2 xi + 2a2 yj图3-3-545M2 在当前中点处,法向量(2b2 (xp+1) ,2a2 (yp-0.5))的y分量比x分量大,即:b2 (xp+1) < a2 (yp-0.5), 而在下一中点,不等式改变方向,则说明椭圆弧从上部分转入下部分3.3.3 椭圆的的扫描描转换在上半部分,法向量的y分量大在下半部分,法向量的x分量大上半部分下半部分法向量两分量相等M1图3-3-646n椭圆的中点算法 与圆弧中点算法类似:确定一个象素后,接着在两个候选象素的中点计算一个判别式的值,由判别式的符号确定更近的点 先讨论椭圆弧的上部分(xp,yp)中点(xp+1,yp-0.5)d1=F(xp+1,yp-0.5)= b2(xp+1)2+a2(yp-0.5)2-a2b23.3.3 椭圆的的扫描描转换47根据d1的符号来决定下一像素是取正右方的那个,还是右下方的那个。 n若d1<0,中点在椭圆内,取正右方象素,判别式更新为: d1 '=F(xp+2,yp-0.5)= d1 +b2(2xp+3) d1的增量为b2(2xp+3)n当d1 ≥0,中点在椭圆外,取右下方象素,更新判别式: d1 '=F(xp+2,yp-1.5)= d1 +b2(2xp+3)+a2(-2yp+2) d1的增量为b2(2xp+3)+a2(-2yp+2)3.3.3 椭圆的的扫描描转换48nd1的初始条件:椭圆弧起点为(0,b),第一个中点为(1,b-0.5) 初始判别式: d10=F(1,b-0.5)=b*b+a*a(-b+0.25)转入下一部分,下一象素可能是一正下方或右下方,此时判别式要初始化d2 = F(Xp+0.5,Yp-1) = b2(Xp+0.5)2+a2(Yp-1)2-a2b2 若d2<0,则d2’ = F(Xp+1.5,Yp-2) = d2 + b2(2Xp+2)+a2(-2Yp+3) 若d2>=0,则d2’ = F(Xp+0.5,Yp-2) = d2 + a2(-2Yp+3) 下半部分弧的终止条件为 y = 03.3.3椭圆的扫描转换椭圆的扫描转换49程序:MidpointEllipe(a,b, color)int a,b,color;{ int x,y; float d1,d2; x = 0; y = b; d1 = b*b +a*a*(-b+0.25); putpixel(x,y,color); while( b*b*(x+1) < a*a*(y-0.5)) { { if (d1<0)d1 +=b*b*(2*x+3); x++; } else { d1 +=(b*b*(2*x+3)+a*a*(-2*y+2)) x++; y--; } putpixel(x,y,color); }//上部分 503.3.3 椭圆的的扫描描转换 d2 = sqr(b*(x+0.5)) +sqr(a*(y-1)) – sqr(a*b); while(y >0) { if (d2 <0) { d2 +=b*b*(2*x+2)+a*a*(-2*y+3); x++; y--;} else {d2 += a*a*(-2*y+3); y--; } putpixel(x,y,color); }}513.3.3 椭圆的的扫描描转换3.3.4 生成生成圆弧的多弧的多边形逼近法形逼近法 用正多边形近似代替圆, 显示多边形的边可用扫描转换直线段的中点算法来实现。 Ø圆的正内接多边形迫近法Ø圆的等面积正多边形迫近法52q圆的正内接多边形迫近法圆的正内接多边形迫近法n原理原理n计算多边形各顶点的递推公式计算多边形各顶点的递推公式 Xi+1cos a- sin a Xi = Yi +1sin a cosa Yi因为: a是常数, sin a, cosa只在开始时计算一次所以,一个顶点只需4次乘法,共4n次乘法,外加直线段的中点算法的计算量3.3.4生成圆弧的多边形逼近法生成圆弧的多边形逼近法图3-3-753图3-3-8•问题:: 给定最大逼近定最大逼近误差(最大差(最大 距离)距离) DELTA ,如何确定多,如何确定多边形形的的边数数n或或a?另外,用矢量运算可以简化计算,推出求顶点的逆推公式(p60) d = R – Rcos(a/2) <= DELTA cos(a/2) >= (R – DELTA)/R a <= 2 arc cos (R – DELTA)/Ramax =2 arccos (R – DELTA)/Rn = 360 /a 543.3.4 生成生成圆弧的多弧的多边形逼近法形逼近法图3-3-10n圆的等面积正多边形迫近法步骤:l求多边形径长,从而求所有顶点生标值l由逼近误差值,确定边所对应的圆心角α图3-3-9553.3.4 生成生成圆弧的多弧的多边形逼近法形逼近法扇形ODCE的面积 = 三角形OPiPi+1的面积(P60页)图3-3-10563.3.4 生成生成圆弧的多弧的多边形逼近法形逼近法3.4 易画曲易画曲线的正的正负法法n正正负法法简介介q基本原理基本原理假定初始点假定初始点P0∈∈G0,沿某方,沿某方向向(假定假定为X轴)前)前进△△X时,到,到达达G+或或G-(假定假定为G-)中的中的P1,在在沿另外一方向沿另外一方向(Y轴)前前进△△Y,到到达达P2。 若若P2∈∈G+,,则改改变前前进方向,否方向,否则继续向向G+前前进… …q易画曲易画曲线nF(x,y)具有正具有正负划分性划分性nF(x,y)二二阶连续n曲曲线上各点曲率半径足上各点曲率半径足够大大图3-4-157q初始定向初始定向n确定确定 的符号的符号3.4 易画曲易画曲线的正的正负法法58q前前进规则n取判取判别式式3.4 易画曲易画曲线的正的正负法法59n正正负法生成法生成圆弧弧q考考虑第一像限第一像限圆弧段弧段q圆弧是易画曲弧是易画曲线取初始点P0(x0,y0) = (0,R)初始定向为:D = 4, △X=1, △y = -1则P1为 (x0+1,y0) = (1,R);又因为 D(Pi) = F(Pi)F(P1) = F(Pi)F(1,R)所以由前进规则得前进点递推公式1)当)当D(Pi) >=0时,,xi+1 = xi, yi+1 = yi-1;2)当)当D(Pi) <0时,,xi+1 = xi+1, yi+1 = yi;;判判别式式D(Pi+1)的的递推公式推公式见:: P63判别式的初值D(P1) = F(P1)= F(1,R) = 1 3.4 易画曲易画曲线的正的正负法法图3-4-2603.5 线画画图元的属性控制(元的属性控制(1/5))n线宽控制控制q像素复制方法像素复制方法n优点:点:q实现简单n缺点:缺点:q线段两端要么段两端要么为水平的,水平的, 要么是要么是竖直的直的q折折线顶点点处有缺口有缺口图3-5-1图3-5-261q图元的元的宽度不均匀度不均匀q产生生宽度度为偶数像素的偶数像素的图元效果不好元效果不好图3-5-33.5 线画画图元的属性控制(元的属性控制(2/5))62q移移动刷子刷子3.5 线画画图元的属性控制(元的属性控制(3/5))图3-5-463q利用填充利用填充图元元n优点:点:q生成的生成的图形形质量高量高n缺点缺点q计算量大算量大q有些有些图形的等距形的等距线难以以获得得图3-5-43.5 线画画图元的属性控制(元的属性控制(4/5))64n线型控制型控制1 1 1 1 0 0 1 1 1 1 0 0 1 1 1 1 0 03.5 线画画图元的属性控制(元的属性控制(5/5))图3-5-565。
