圆弧与线宽及属性

扫描转换圆弧A

-直接生成B-多边形逼近法

C-正负法D-Bresenham算法

扫描转换圆弧A

-直接生成B-多边形逼近法

C-正负法D-Bresenham算法A.直接采用圆方程(离散点)

(x-xc)2+(y-yc)2=r2沿x轴从xc-r到xc+r以单位步长计算对应的y值来得到圆周每点的位置。每一步包含很大的计算量，而且，所画像素位置间的间距是不一致的。圆斜率绝对值大于1后，交换x和y来调整间距。但增加计算量和处理过程。开根，计算量大，不可取。

扫描转换圆弧A

-直接生成B-多边形逼近法

C-正负法D-Bresenham算法B-多边形逼近法圆的正内接多边形逼近法原理计算多边形各顶点的递推公式

Xi+1 cosα -sinα

Xi =

Yi+1 sinα cosα

Yi因为:α是常数，sinα

，cosα只在开始时计算一次。所以，一个顶点只需4次乘法，共4n次乘法，外加直线段的中点算法的计算量。离散点方法取等量的变量但得不到均匀曲线离散角度方法取等量的变量得到均匀曲线以固定角度为步长生成显示时，圆就可沿圆周等距点绘制出来。沿圆周使用较大的角度分步时，可用直线段连接逼近圆的路径。为在光栅系统上得到更连续的边界，可将步长设为1/r，绘制的像素位置约为一个单位间隔。消除了不等间距现象开根，三角函数运算，计算量大，不可取。

问题：给定最大逼近误差（最大距离）DELTA

，如何确定多边形的边数n或α

？另外，用矢量运算可以简化计算，推出求顶点的逆推公式d=R–Rcos(α

/2)<=DELTAcos(α

/2)>=(R–DELTA)/R

α

<=2arccos(R–DELTA)/Rα

max=2arccos(R–DELTA)/Rn=360/α

扫描转换圆弧A

-直接生成B-多边形逼近法

C-正负法D-Bresenham算法C-正负法(1/5)基本原理假定初始点P0∈G0，沿某方向(假定为X轴）前进△X时，到达G+或G-(假定为G-)中的P1,再沿另外一方向(Y轴)前进△Y,到达P2。若P2∈G+，则改变前进方向，否则继续向G+前进。……易画曲线F(x,y)具有正负划分性F(x,y)二阶连续曲线上各点曲率半径足够大C-正负法(2/5)初始定向确定的符号C-正负法(3/5)前进规则取判别式C-正负法(4/5)正负法生成圆弧考虑第一像限圆弧段（圆弧是易画曲线）

取初始点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)C-正负法(5/5)所以由前进规则得前进点递推公式1）当D(Pi)>=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法208-点对称性21生成一个，得到

下列8点:只需生成1/8个圆函数是单值的

可以采用Bresenham方法只需考虑E

或

SE22圆的隐式方程令对于一个圆有并且

23选择

E或SE函数为所以并且

中点

MESE当前点中点

M’中点

M”扫描转换圆弧-Bresenham

方法25理想线26理想线27决策变量

令28理想线情况1:E293031由于32其中33理想线

情况2:SE3435因为3637此处3839用

计算不是常量

40总结在整个圆上，不再是常量与直线算法结构相同与直线算法的主要差别

需要在每一步计算新

需要实数计算中点

MESE当前点中点

M’中点

M”扫描转换圆弧-Bresenham

方法42初始条件令

r

为一个整数.从开始计算下一个中点M

位于处所以

Bresenham直线扫描转换算法的优点如下：⒈

不必计算直线的斜率，因此不做除法。⒉

不用浮点数，只用整数。⒊

只做整数加减运算和乘2运算，而乘2运算可以用

移位操作实现。

Bresenham算法的运算速度很快，

并适于用硬件实现。

圆的Bresenham算法的程序circle(xc,yc,radius,c)intxc,yc,radius,c;{intx,y,p;x=0;y=radius;p=5-4*radius;while(x<y){

plot_circle_points(xc,yc,x,y,c);

if(p<0)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)intxc,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+x,c);putpixel(xc+y,yc-x,c);putpixel(xc-y,yc-x,c);}

Bresenham的圆生成算法

扫描转换椭圆弧A

–角度微分法B-中点画法

椭圆生成方法可通过椭圆长轴和短轴尺寸不同而修改画圆程序实现。椭圆为到两定点(焦点)距离之和等于常数点的集合。假如短轴和长轴与坐标轴方向平行，可简化椭圆方程。“标准位置”椭圆是指其长轴和短轴平行于x和y轴，参数rx和ry标出长、短半轴。椭圆方程可借助于椭圆中心坐标和参数rx和ry写为：Pf1+pf2=Const标准位置椭圆的参数方程：

x=xc+rxcosθ，

y=yc+rysinθ。考虑对称性可用来进一步减少计算量。标准位置椭圆在四分像限中是对称的，必须计算一个整四分像限中椭圆曲线的像素位置，再由对称性得到其它三个像限中的像素位置。椭圆生成方法Pf1+pf2=ConstA

扫描转换椭圆弧A

–角度微分法B-中点画法

中点椭圆生成基本思想给定长短轴参数rx、ry(假设ry≤rx)和椭圆中心位置(xc,yc)。先确定中心在原点的标准位置的椭圆点(x,y)，即：取(xc,yc)=(0,0)，然后，将点变换为圆心在(xc,yc)的点。定义椭圆隐函数形式为：

fellipse(x,y)=ry2x2+rx2y2-rx2ry2=0中点椭圆生成基本思想

该函数具有下列特性：fellipse(x,y)＜0，假如(x,y)位于椭圆边界内；fellipse(x,y)＝0，假如(x,y)在椭圆边界上；fellipse(x,y)＞0，假如(x,y)位于椭圆边界外。将椭圆函数fellipse(x,y)作为中点算法的决策参数。在每个取样位置，按照椭圆函数在沿椭圆轨迹两个候选像素间中点求值的符号选择下一个像素。中点椭圆生成区域划分中点法依据椭圆斜率将第一像限的椭圆(ry≤rx)分成两部分。根据斜率变化确定步长方向：斜率绝对值小于1的区域1内x方向取单位步长；斜率绝对值大于1的区域2内y方向取单位步长。第一象限椭圆区域划分区域1：椭圆切线斜率小于1；区域2：椭圆切线斜率大于1。中点椭圆生成区域划分

第一象限椭圆区域划分区域1：椭圆切线斜率小于1；区域2：椭圆切线斜率大于1。区域分割条件在每一步中，需检测曲线的斜率值。椭圆的斜率：

dy/dx=-2ry2x/2rx2y在两区域交界处：dy/dx=-1，即：2ry2x=2rx2y。因此，区域1和区域2的交替条件是：

2ry2x≥2rx2y在上半部分,法向量的y分量大在下半部分,法向量的x分量大上半部分下半部分法向量两分量相等M1M2中点椭圆生成路径选择区域1和区域2可以多种方法来处理：从(0,ry)开始，先沿椭圆路径顺时针x方向步进(△x=1，△y≤0)；斜率绝对值大于1时，变为y方向步进(△y=-1，△x≥0)

；从(rx,0)开始，先沿椭圆路径逆时针y方向步进(△y=1，△x≤0)；当斜率绝对值小于1时，变为x方向步进(△x=-1，△y≥0)

；利用并行处理器可同时计算两区域内的像素位置。(rx

,0)(0,ry)候选高像素候选低像素候选像素中点前一像素椭圆弧第一象限区域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的符号来决定下一像素是取正右方的那个，还是右下方的那个。

若d1＜0，中点在椭圆内，取正右方象素，判别式更新为：

d1'=F(Xp+2,Yp-0.5)=d1+b2(2Xp+3)

d1的增量为b2(2Xp+3)当d1≥0，中点在椭圆外，取右下方象素，判别式更新为：

d1'=F(Xp+2,Yp-1.5)=d1+b2(2Xp+3)+a2(-2Yp+2)

d1的增量为b2(2Xp+3)+a2(-2Yp+2)区域2中点椭圆生成算法

区域2(|切线斜率|＞1)

其初始点取区域1中选择的最后位置。在负y方向以单位步长取样，在每一步中取水平像素间的中点对决策参数求值为：

d2k=fellipse(xk+1/2,yk-1)=ry2(xk+1/2)2+rx2(yk-1)2-rx2ry2区域2(rx,0)区域2中点椭圆生成算法

区域2中(|切线斜率|＞1)

假如d2k＞0，中点位于椭圆边界之外，

选择xk处像素；假如d2k≤0，中点位于椭圆边界之内或上，

选择xk+1处像素。区域2(rx,0)此时判别式要初始化。

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=0d1的初始条件：

椭圆弧起点为(0，b)，第一个中点为(1,b-0.5)

初始判别式：

d0=F(1,b-0.5)=b*b+a*a(-b+0.25)程序：MidpointEllipe(a,b,color) inta,b,color; {intx,y;floatd1,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); }//上部分

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);}}其它曲线生成算法常见曲线包括圆锥曲线、三角和指数函数、概率分布、通用多项式和样条函数。这些曲线的显示可采用类似于圆和椭圆函数来生成直接从显式表示y=f(x)或参数方程中得到；用中点法绘制隐式函数f(x,y)=0曲线。直接逼近：直接方法是用直线段来逼近曲线－

“以直代曲”。沿曲线轨迹等距的线端点位置可使用参数表示；按曲线的斜率选择独立变量从显式表示中生成等距位置。其它曲线生成算法直线拟合：可将曲线离散成坐标点数据集，用直线段来将离散点连结在一起，或采用线性或非线性回归来拟合数据组。利用对称：利用函数对称性来减少曲线轨迹坐标位置的计算量。中点法：根据隐式函数f(x,y)=0

确定合适的决策参数。线宽和线型

生成具有一定宽度的直线，可以沿着生成直线是获得的像素点，通过移动一把具有一定宽度的“刷子”来实现。

假设直线斜率在[-1，1]之间，可把刷子定成垂直方向，并将刷子中心点对准直线上某一像素点，然后将刷子沿直线运动就刷出了一条具有一定宽度的直线。当直线斜率不在[-1，1]之间时，只需把刷子运动方向改为水平方向即可。

用刷子来产生直线的算法简单、效率高，但它刷出来的线的末端总是水平或垂直的，因此当线宽较大时，直线的两端就不好看了，而且在两条直线的连接处会产生缺口。

对于绘制具有特殊线形的直线，如虚线、点划线等，也需要编制相应的算法来实现。3.3线画图元的属性控制线型线型属性包括实线、虚线和点线等。通过设置沿线路径显示的实线段的长度和间距来修改画线算法以生成各种类型的线。虚线：在实线段之间插入与实线段等长的空白段；划线：长度和空白段长度常作为用户的选项来指定。点线：很短的划线和等于或大于划线大小的空白段。

线型段长度和中间空白段的像素数目可用像素掩模指定。像素掩模是包含数字0和1的串，指定沿线路径哪些位置要画。用固定数目像素来画划线会因斜率变化而产生在不同线方向生成不等长的划线的现象。保持划线等长的方法：按照线斜率来调整实心段和中间空白段的像素数目。将划线看作单独的线段，将每条划线的端点坐标定位后，调用沿划线路径计算像素位置的画线程序。线宽标准线宽

用在每个放样位置处用一个像素来生成。其它线宽

作为标准