计算机图形学(圆弧的扫描转换II)

第3章基本光栅图形算法圆弧的扫描转换正负法中点法Bresenham算法多边形迫近法—圆与椭圆22014-2015-1:CG:SCUECDDA法基本原理设与当前圆周最近的像素点是Pi-1(xi-1,yi-1)下一个与圆周最近的像素点只能是正右方的点Hi(xi-1+1,yi-1)或者是右下方的点Li(xi-1+1,yi-1-1)3生成圆弧之Bresenham算法记D(Hi)=(xi-1+1)2+yi-12-R2,D(Li)=(xi-1+1)2+(yi-1-1)2-R2令判别式Di=|D(Hi)|-|D(Li)|，然后根据Di的正负来判断下一个像素点是取Hi

点还是Li

点若Di<0，表示Hi点更接近圆周，点亮Hi(xi-1+1,yi-1)若Di≥0，表示Li点更接近圆周，点亮Li(xi-1+1,yi-1-1)2014-2015-1:CG:SCUEC4问题：判别式Di=|D(Hi)|-|D(Li)|的计算要用到绝对值运算，能否将绝对值运算去掉呢？判别式的改进如右图所示，可看出D(Hi)>0,D(Li)<0，因此可以考虑把判别式改为di=D(Hi)+D(Li)，在这种情况下di的符号与Di的符号是一致的。问题：是不是任何情况下di的符号与Di的符号都是是一致的呢？如果是，如何证明？2014-2015-1:CG:SCUEC判别式的改进设与当前圆周最近的像素点是P，圆下面可能穿越的区域只能有五种情况：①H点在圆外，L点在圆内R＝7，xp=1,取H点；R＝13，xp=7,取L点；②

H点与L点都在圆内R＝9，xp=3,取H点③

H点与L点都在圆外R＝7，xp=4,取L点④

H点在圆上，L点在圆内⑤H点在圆外，L点在圆上R＝5，xp=2，取L点R＝13，xp=4，取H点52014-2015-1:CG:SCUEC判别式的改进圆穿越①区域时，D(Hi)

>0，D(Li)

<0，有

Di=|D(Hi)

|-|D(Li)

|=D(Hi)

+D(Li)=di考察圆穿越不同区域时di的符号与Di的符号是否一致圆穿越②区域时，D(Hi)

<0，D(Li)

<0，有

Di=|D(Hi)

|-|D(Li)

|<0，di=D(Hi)

+D(Li)<0圆穿越③区域时，D(Hi)

>0，D(Li)

>0，有

Di=|D(Hi)

|-|D(Li)

|>0，di=D(Hi)

+D(Li)>0圆穿越④区域时，D(Hi)

=0，D(Li)

<0，有

Di=|D(Hi)

|-|D(Li)

|=D(Li)=di圆穿越⑤区域时，D(Hi)

>0，D(Li)

=0，有

Di=|D(Hi)

|-|D(Li)

|=D(Hi)=di结论：di的符号与Di的符号是一致的62014-2015-1:CG:SCUEC若di

≤

0，表示Hi点更接近圆周，点亮Hi(xi-1+1,yi-1)，下一个像素是取Hi+1还是Li+1，应计算如下的判别式:7

di=D(Hi)+D(Li)

=[(xi-1+1)2+yi-12-R2]+[(xi-1+1)2+(yi-1-1)2-R2]判别式di的增量计算di+1=D(Hi+1)+D(Li+1)

=[(xi-1+1+1)2+yi-12-R2]+[(xi-1+1+1)2+(yi-1-1)2-R2]=[D(Hi)+2xi-1+3]+[D(Li)+2xi-1+3]=di+4xi-1+62014-2015-1:CG:SCUEC若di>0，表示Li点更接近圆周，点亮Li(xi-1+1,yi-1-1)，下一个像素是取Hi+1还是Li+1，应计算如下的判别式:判别式di的增量计算8

di=D(Hi)+D(Li)

=[(xi-1+1)2+yi-12-R2]+[(xi-1+1)2+(yi-1-1)2-R2]di+1=D(Hi+1)+D(Li+1)

=[(xi-1+1+1)2+(yi-1-1)2-R2]+[(xi-1+1+1)2+(yi-1-1-1)2-R2]=[D(Hi)+2(xi-1-yi-1)+4]+[D(Li)+2(xi-1-yi-1)+6]=di+4(xi-1-yi-1)+102014-2015-1:CG:SCUEC判别式di的初始值=?

9判别式di的增量计算2014-2015-1:CG:SCUECx0=0,y0=R

d1=3–2*R当di≤0时

xi=xi-1+1

di+1=di+4xi-1+6

当di>0时

xi=xi-1+1，yi=yi-1-1di+1=di+4(xi-1-yi-1)+10voidbresenham_arc(intR,intcolor){

intx,y,d;

x=0;

y=R;

d=3-2*R;

while(x<y){

DrawPixel(x,y,color);

if(d<=0)d+=6;

else{

d=d-4*y+10;

y-=1;

}d+=4*x;

x+=1;

}

if(x==y)DrawPixel(x,y,color);}圆弧之Bresenham算法实现102014-2015-1:CG:SCUEC例子：画圆心(0,0)，半径R=5的圆x0=0,y0=5点亮点(x0,y0)=(0,5)d1=3-2R=-7≤0点亮点(x1,y1)=(1,5)d2=d1+4x0＋6=-1≤0点亮点(x2,y2)=(2,5)d3=d2+4x1＋6=9>0点亮点(x3,y3)=(3,4)按45◦线对称翻转按X轴对称翻转按Y轴对称翻转

Bresenham算法画圆举例112014-2015-1:CG:SCUEC正负法与Bresenham算法比较

正负法主要用于笔式绘图仪中，以迎合绘图仪只有水平和垂直方向的运动。每次选出的下一个像素并不一定是离圆弧最近的像素点Bresenham算法在候选的两个像素中，总是选定离圆弧最近的像素为圆弧的一个近似点，因此，Bresenham算法比正负法决定的像素更合理122014-2015-1:CG:SCUEC基本思想按一定方式计算给定圆弧轨迹上的一系列顶点，然后用连接相邻点的一系列直线段来逼近圆弧。用正多边形迫近圆弧法设圆弧所在圆的半径为R，圆弧的起始角和终止角分别为和，把圆弧分割成份，则相邻两个顶点之间的夹角为。设顶点序列的第个点为，为该点的幅角。则下一个顶点的坐标为或表示为矩阵形式圆的多边形迫近法132014-2015-1:CG:SCUEC多边形迫近法的优化已知点Pi，计算点Pi+1需要作四次乘法，再采用画直线方法画PiPi+1为降低计算量，采用cos1,sin或cos1-2/2,sin，取=2-k，则乘法可用移位和加减法实现不能精确求出圆的内接多边形顶点，取得越小，误差越小142014-2015-1:CG:SCUEC多边形迫近法的改进设圆心在坐标原点O(0,0)，内接正多边形的三个相邻点为Pi-1,Pi,Pi+1，如图所示。Pi-1A平行OPi+1，Pi+1A平行OPi-1OPi+1PiPi-1A或：设Pi点的坐标为(xi,yi)，则有：只需两次乘法，但须知道圆上两个相邻内接多边形的顶点152014-2015-1:CG:SCUEC椭圆弧的生成设椭圆的中心在原点，长短轴分别为a和b，且平行于坐标柚，则该椭圆的参数方程为，设顶点序列的第i个顶点为,则下一个顶点的坐标应满足

,

由此可得其中椭圆的多边形迫近法162014-2015-1:CG:SCUEC上半部分，斜率的绝对值<1,单位步长应为X方向下半部分，斜率的绝对值>1,单位步长应为Y方向F(x,y)<0=0>0说明(x，y)在椭圆内说明(x，y)在椭圆上说明(x，y)在椭圆外17生成椭圆之中点法已知椭圆中心在(0,0),长短半轴分别

为a,b,则椭圆方程为：△只需要讨论第一象限椭圆弧的生成,在生成这段椭圆弧时，要分两部分完成2014-2015-1:CG:SCUEC构造判别式：d1i=F(xM,yM)=b2(xi+1)2+a2(yi-0.5)2-a2b2如果d1i

>0,中点在椭圆外，应取右下方像素Pd(xi+1,yi-1)判别式更新为：d1(i+1)=F(xi+2,yi-1.5)=d1i+b2(2xi+3)+2a2(-yi+1)18椭圆上半部分的生成设与当前椭圆弧最近的像素点是P(xi,yi)下一个候选像素点只能是正右方的点Pu(xi+1,yi)或者是右下方的Pd(xi+1,yi-1)

设M(xi+1,yi-0.5)为Pu与Pd的中点P(xi,yi)M(xi+1,yi-0.5)Pu(xi+1,yi)Pd(xi+1,yi-1)如果d1i

≤0,中点在椭圆内，应取正右方像素Pu(xi+1,yi)判别式更新为：d1(i+1)=F(xi+2,yi-0.5)=d1i+b2(2xi+3)判别式初值为：d10=F(1,b-0.5)=b2+a2(-b+0.25)2014-2015-1:CG:SCUECdy/dx=－2b2x/(2a2y)－2b2(xi+1)2/2a2(yi－0.5)

≤－1

19椭圆上半部分的终止条件椭圆上任意一点P(x,y)的切线斜率为：上半部分每一点的切线斜率都大于－1，故上半部分终止的条件为：下一个中点(xi+1,yi-0.5)的切线斜率小于等于－1，即b2(xi+1)

≥

a2(yi－0.5)

2014-2015-1:CG:SCUEC构造判别式：d2i=F(xM,yM)=b2(xi+0.5)2