圆弧与线宽及属性

1、 扫描转换圆弧扫描转换圆弧A - 直接生成B - 多边形逼近法 C - 正负法D - Bresenham 算法 扫描转换圆弧扫描转换圆弧A - 直接生成直接生成B - 多边形逼近法 C - 正负法D - Bresenham 算法A. 直接采用圆方程直接采用圆方程(离散点离散点) 开根，开根， 计算量大，不可取计算量大，不可取。 扫描转换圆弧扫描转换圆弧A - 直接生成B - 多边形逼近法多边形逼近法 C - 正负法D - Bresenham 算法B- 多边形逼近法多边形逼近法圆的正内接多边形逼近法原理圆的正内接多边形逼近法原理计算多边形各顶点的递推公式计算多边形各顶点的递推公式 Xi+1cos

2、 - sin Xi = Yi +1sin cos Yi因为: 是常数，sin ， cos 只在开始时计算一次。所以，一个顶点只需4次乘法，共4n次乘法，外加直线段的中点算法的计算量。圆边正内接多边形） nn(lim离散点方法取等量的变量但得不到均匀曲线离散角度方法取等量的变量得到均匀曲线 开根，三角函数运算，计算量大，不可取。开根，三角函数运算，计算量大，不可取。 问题：问题：给定最大逼近误差（最大给定最大逼近误差（最大 距离）距离） DELTA ，如何确定多边形的边，如何确定多边形的边数数n或或 ？2n另外，用矢量运算可以简化计算，推出求顶点的逆推公式 d = R Rcos( /2) = (

3、R DELTA)/R =0时，时，Xi+1 = Xi, Yi+1 = yi-1;当当D(Pi) 0时，时，Xi+1 = Xi+1, Yi+1 = yi； 判别式的初值D(P1) = F(P1)= F(1,R) = 1 扫描转换圆弧扫描转换圆弧A - 直接生成B - 多边形逼近法 C - 正负法D - Bresenham 算法算法D-Bresenham法20 8-点对称性),(yx),(yx),(yx ),(yx ),(xy),(xy ),(xy),(xy 21生成一个 ，得到 ),(yx下列8 点:),(),(),(),(yxyxyxyx),(),(),(),(xyxyxyxy只需生成1/8个

4、圆函数是单值的 可以采用Bresenham方法只需考虑 E 或 SE1slope22圆的隐式方程令对于一个圆 有 并且 ryxyxF222),(圆外 0),(yxF圆内 0),(yxF0),(yxF23选择 E 或 SE 函数为 所以 并且 0222ryxSEMF 0)(EMF 0)(中点 MESE当前点),(ppyx),(211ppyx) 1, 1(ppyx),(1ppyx 中点 M中点 M”), 2(23ppyx), 2(21ppyx扫描转换圆弧扫描转换圆弧- Bresenham 方法方法25ESEMSEMF 0)(理想线26ESEM理想线EMF 0)(27决策变量 d令)(MFd 28E

5、SEM理想线情况1: E290oldEd1(1,)22212(1)()2oldpppFyxyxrpd301(2,)22212(2)()2newppppFyxyxrdEdold 031(23)pnewoldxdd由于32) 12() 44() 1(2) 2(2xpxpxpxpxp0oldEd32,23EnewoldEpxddEdold 0其中33ESEM理想线 情况2: SE343(2,)22232(2)()2newppppFyxyxrdSEdold035SEdold 0)522(yxddppoldnew因为361(1,)22212(1)()2oldpppFyxyxrpd3(2,)22232(2

6、)()2newppppFyxyxrd37SEdold 0)522(yxddppoldnew此处38,225SEnewoldSEppddyxSEdold 039用 计算不是常量 sandESEyandxpp40总结 在整个圆上， 不再是常量 与直线算法结构相同 与直线算法的主要差别 需要在每一步计算新 需要实数计算s中点 MESE当前点),(ppyx),(211ppyx) 1, 1(ppyx),(1ppyx 中点 M中点 M”), 2(23ppyx), 2(21ppyx扫描转换圆弧扫描转换圆弧- Bresenham 方法方法42初始条件 令 r 为一个整数. 从 开始计算 下一个中点 M 位于

7、处 所以 ), 0(r), 1 (21rrrrrF2)2(1), 1(4121r45Bresenham直线扫描转换算法的优点如下： 不必计算直线的斜率，因此不做除法。 不用浮点数，只用整数。 只做整数加减运算和乘2运算，而乘2运算可以用 移位操作 实现。 Bresenham算法的运算速度很快， 并适于用硬件实现。 圆的Bresenham算法的程序 circle (xc, yc, radius, c)int xc, yc, radius, c;int x, y, p;x=0;y=radius;p=5-4*radius;while (xy) plot_circle_points(xc, yc, x

8、, y, c); if (p0) p=p+2*x+3; else p=p+2*(x-y)+5; y-=1; x+=1; if (x= =y) plot_circle_points(xc, yc, x, y, c);plot_circle_points(xc, yc, x, y, c)int xc, yc, x, y, c;putpixel(xc+x, yc+y, c);putpixel(xc+x, yc+y, c);putpixel(xc+x, yc-y, c);putpixel(xc-x, yc-y, c);putpixel(xc+y, yc+x, c);putpixel(xc-y, yc+

9、x, c);putpixel(xc+y, yc-x, c);putpixel(xc-y, yc-x, c);Bresenham的圆生成算法 扫描转换椭圆弧扫描转换椭圆弧A 角度微分法B - 中点画法中点画法 Pf1+pf2=Const122 ycxcryyrxxPf1+pf2=ConstA 扫描转换椭圆弧扫描转换椭圆弧A 角度微分法B - 中点画法中点画法 第一象限椭圆区域划分区域1：椭圆切线斜率小于1；区域2：椭圆切线斜率大于1。第一象限椭圆区域划分区域1：椭圆切线斜率小于1；区域2：椭圆切线斜率大于1。在上半部分,法向量的y分量大在下半部分,法向量的x分量大上半部分下半部分法向量两分量相等

10、M1M2候选高像素候选低像素候选像素中点前一像素椭圆弧第一象限区域1内的椭圆弧椭圆的中点画法椭圆的中点画法 与圆弧中点算法类似：确定一个象素后，接着在两个候选象素的中点计算一个判别式的值，由判别式的符号确定更近的点先讨论椭圆弧的上部分当前点: (Xp，Yp), 中点: (Xp+1,Yp-0.5) d1= F(Xp+1,Yp-0.5) = b2(Xp+1)2+a2(Yp-0.5)2-a2b2对区域对区域1， 根据根据d1的符号来决定下一像素是取正右方的那个，还是右下方的那个。的符号来决定下一像素是取正右方的那个，还是右下方的那个。 若d10，中点在椭圆内，取正右方象素，判别式更新为： d1 =

11、F(Xp+2,Yp-0.5) = d1 + b2(2Xp+3) d1的增量为的增量为b2(2Xp+3)当d10，中点在椭圆外，取右下方象素，判别式更新为： d1 = F(Xp+2,Yp-1.5) = d1 + b2(2Xp+3)+a2(-2Yp+2)d1的增量为的增量为b2(2Xp+3)+a2(-2Yp+2) xk xk+1 xk+2 yk-1 yk yk-1处候选像素及其中点 区域2(rx,0) xk xk+1 xk+2 yk-1 yk yk-1处候选像素及其中点 区域2(rx,0) 此时判别式要初始化。 d2 = F(Xp+0.5,Yp-1) = b2(Xp+0.5)2+a2(Yp-1)2

12、-a2b2 若d2=0,则 d2 = F(Xp+0.5,Yp-2) = d2 + a2(-2Yp+3) 下半部分弧的终止条件为下半部分弧的终止条件为 y = 0 d1的初始条件：椭圆弧起点为(0，b)， 第一个中点为(1, b-0.5) 初始判别式初始判别式： d0=F(1,b-0.5) =b*b+a*a(-b+0.25)程序：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*(

13、x+1) a*a*(y-0.5) if (d10) 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); 线宽和线型线宽和线型 生成具有一定宽度的直线，可以沿着生成直线是获得的像素点，通过移动一把具有一定宽度的“刷子”来实现。 假设直线斜率在-1，1之间，可把刷子定成垂直方向，并将刷子中心点对准直线上某一像素点，然后将刷子沿直线运动就刷出了一条具有一定宽度的直线。当直线斜率不在-1，1之间时，只需把刷子运动方向改为水平方向即可。 用刷子来产生直线的算法简单、效率高，但它刷出来的线的末端总是水平或垂直的，因此当线宽较大时，直线的两端就不好看了，而且在两条直线的连接处会产生缺口。 对于绘制具有特殊线形的直线，如虚线、点划线等，也需要编制相应的算法来实现。 3.3 线画图元的属性控