第三章 二维图形的生成-直线和圆

2023/2/5西安工程大学计算机图形学1第四章、二维图形的生成和变换4.1、直线段的扫描转换算法

4.1.1、DDA算法

4.1.2、中点画线法

4.1.3、Bresenham画线算法4.2、圆弧扫描转换算法

4.2.1、中点算法

4.2.2、Bresenham画圆算法

4.2.3、生成圆弧的正负法4.3、椭圆弧生成算法

2023/2/5西安工程大学计算机图形学2对一维图形，不考虑线宽，则用一个像素宽的直线来显示图形。二维图形的光栅化，即区域的填充：确定像素集，填色或图案。任何图形的光栅化，必须显示在一个窗口内，否则不予显示。即确定一个图形的哪些部分在窗口内，哪些在窗口外，即裁剪。 图形的扫描转换（光栅化）：确定一个像素集合，用于显示一个图形的过程。步骤如下：1、确定有关像素2、用图形的颜色或其它属性，对像素进行写操作2023/2/5西安工程大学计算机图形学3图形显示前需要：扫描转换+裁剪裁剪---〉扫描转换：最常用，节约计算时间。扫描转换---〉裁剪：算法简单；2023/2/5西安工程大学计算机图形学4图形显示器是由一个个排列有序的像素构成，划分的像素点越多分辨率就越高。例如640X480的显示器，分成640X480个网格，网格单元视为像素，一条线段就是由一些连续可见的像素所组成，如下图所示：4.1直线段的扫描转换算法在数学上，理想的直线是没有宽度的，是由无数个在它上面的点构成的集合。直线可以向一个方向及其相反的方向无限延长。在图形学中研究的对象是直线段，它是一条具有一个Pixel或多个Pixel宽的直线段。2023/2/5西安工程大学计算机图形学5由上图可知：画一条直线实际上就是根据一系列计算出来并与该直线靠近的像素绘制的。Line:P0(0,0)——P1(5,2)0143215234各行各列像素中心构成的一组虚拟网格线像素单元4.1直线段的扫描转换算法0123456701234562023/2/5西安工程大学计算机图形学6直线的扫描转换:确定最佳逼近于该直线的一组象素，并且按扫描线顺序，对这些象素进行写操作。直线段是最基本的图形，因此直线段生成的质量好坏与速度快慢将直接影响整个图形生成的质量和速度。三个常用算法：数值微分法（DDA）中点画线法Bresenham算法。4.1直线段的扫描转换算法2023/2/5西安工程大学计算机图形学74.1.1、数值微分法（ＤＤＡ）

假定直线的起点、终点分别为:(x0,y0),(x1,y1)，且都为整数。

栅格交点表示象素点位置(Xi+1,Yi+k)(Xi,Yi)●4.1直线段的扫描转换算法●●●●●2023/2/5西安工程大学计算机图形学8基本思想

已知直线L两端点位P0(x0,y0),P1(x1,y1)4.1直线段的扫描转换算法即可以通过x方向的增量Δx，计算y的增量Δy来生成直线。当得4.1.1、数值微分法（ＤＤＡ）2023/2/5西安工程大学计算机图形学9即：当x方向每递增1像素，y方向递增k(即直线斜率)；每次通过上式计算出（xi，yi）取整后输出显示器。注意上述分析的算法仅适用于k≤1的情形。在这种情况下，x每增加1,y最多增加1。4.1直线段的扫描转换算法当得4.1.1、数值微分法（ＤＤＡ）2023/2/5西安工程大学计算机图形学10注：当时，必须把x,y位置互换，即利用递推式，y每增加1，x相应增加。所以取和中较大者为步进方向，如下图x为步进方向y为步进方向4.1直线段的扫描转换算法2023/2/5西安工程大学计算机图形学11012345321Line:P0(0,0)--P1(5,2)例：画直线段P0(0,0)--P1(5,2)k=0.4

xy+k四舍五入int（y+0.5)0 0 01 0.4 02 0.8 1 3 1.2 14 1.6 25 2 24.1直线段的扫描转换算法4.1.1、数值微分法（ＤＤＡ）2023/2/5西安工程大学计算机图形学12voidDDALine(intx0,inty0,intx1,inty1,intcolor)

intx；

floatdx,dy,y,k; dx=x1-x0,dy=y1-y0; k=dy/dx,y=y0; for(x=x0;xx1,x++)

putpixel(x,int(y+0.5),color); y=y+k;

4.1直线段的扫描转换算法4.1.1、数值微分法（ＤＤＡ）2023/2/5西安工程大学计算机图形学13增量算法：在一个迭代算法中，如果每一步的x、y值是用前一步的值加上一个增量来获得，则称为增量算法。DDA算法就是一个增量算法。4.1直线段的扫描转换算法该算法的优点是绘制实数直线效果好，误差小。缺点是实现较复杂，不利于硬件实现。该算法涉及到实数乘除法运算，y与k必须用浮点数表示，而且每一步都要对y进行四舍五入后取整。4.1.1、数值微分法（ＤＤＡ）2023/2/5西安工程大学计算机图形学144.1.2、中点画线法原理：假定直线斜率0<K<1，且已确定点亮象素点P（Xp,Yp

）,则下一个与直线最接近的像素只能是P1点或P2点。设M为中点，Q为交点现需确定下一个点亮的象素是P1还是P2。P=(xp,yp)QP2P14.1直线段的扫描转换算法M2023/2/5西安工程大学计算机图形学15我们以M和Q的关系来判断取P1还是P2当M在Q的下方->P2离直线更近更近->取P2。M在Q的上方->P1离直线更近更近->取P1M与Q重合，P1、P2任取一点。问题：如何判断M与Q点的关系？P=(xp,yp)QP2P1M4.1直线段的扫描转换算法4.1.2、中点画线法2023/2/5西安工程大学计算机图形学16∴欲判断中点M点是在Q点上方还是在Q点下方，只需把M代入F(x,y),并检查它的符号。P=(xp,yp)QP2P1M4.1直线段的扫描转换算法4.1.2、中点画线法

假设直线方程为：ax+by+c=0其中a=y0-y1,b=x1-x0,

c=x0y1-x1y02023/2/5西安工程大学计算机图形学17当d=0，选P1或P2均可，约定取P1；P=(xp,yp)QP2P14.1直线段的扫描转换算法4.1.2、中点画线法构造判别式：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；能否采用增量算法呢？M2023/2/5西安工程大学计算机图形学18情形1.若d0->M在直线上方->取P1;

此时再下一个象素的判别式为

d1=F(xp+2,yp+0.5)=a(xp+2)+b(yp+0.5)+c=a(xp

+1)+b(yp

+0.5)+c+a=d+a；

即d的增量为a,QP2P14.1直线段的扫描转换算法P=(xp,yp)M4.1.2、中点画线法2023/2/5西安工程大学计算机图形学19情形2.若d<0->M在直线下方->取P2;

此时再下一个象素的判别式为

d2=F(xp+2,yp+1.5)=a(xp+2)+b(yp+1.5)+c=a(xp

+1)+b(yp+0.5)+c+a+b=d+a+b

；即d的增量为a＋bP=(xp,yp)QP2P14.1直线段的扫描转换算法M4.1.2、中点画线法2023/2/5西安工程大学计算机图形学20

画线从(x0,y0)开始，d的初值

d0=F(x0+1,y0+0.5)=a(x0

+1)+b(y0+0.5)+c=F(x0,y0)+a+0.5b=a+0.5b

由于只用d

的符号作判断，为了只包含整数运算,可以用2d代替d来摆脱小数，提高效率。4.1直线段的扫描转换算法即d0＝2*a+b

若d0

增量为2*a

若d<0

增量为2*(a+b)4.1.2、中点画线法2023/2/5西安工程大学计算机图形学21012345321例：用中点画线法P0(0,0)

P1(5,2)

a=y0-y1=-2b=x1-x0=5

d0=2a+b=1

d1=2a=-4d2=2(a+b)=6

i

xi

yi

d

1 0 0 1 2 1 0 -3 3 2 1 3 4 3 1 -1 5 4 2 5

4.1直线段的扫描转换算法4.1.2、中点画线法2023/2/5西安工程大学计算机图形学22中点画线法voidMidpointLine(intx0,inty0,intx1,inty1,intcolor){inta,b,d1,d2,d,x,y;a=y0-y1,b=x1-x0,d=2*a+b;d1=2*a,d2=2*(a+b);x=x0,y=y0;drawpixel(x,y,color);while(x<x1){if(d<0){x++;y++;d+=d2;}else{x++;d+=d1;}drawpixel(x,y,color);}/*while*/}/*midPointLine*/4.1直线段的扫描转换算法2023/2/5西安工程大学计算机图形学234.1.3、直线的Bresenham算法4.1直线段的扫描转换算法

算法原理：过各行各列象素中心构造一组虚拟网格线。按直线从起点到终点的顺序计算直线与各垂直网格线的交点，然后确定该列象素中与此交点最近的象素。该算法的巧妙之处在于采用增量计算，使得对于每一列，只要检查一个误差项的符号，就可以确定该列的所求象素。2023/2/5西安工程大学计算机图形学24

为了讨论方便，我们假定直线的斜率在0~1之间，其它情况类似处理如右图所示，设直线方程为其中k=dy/dx。

假设当前象素已经确定为(xi,yi)那么下一个象素的列坐标为xi＋1，而行坐标要么不变为yi，要么递增1为yi＋1。

yx4.1直线段的扫描转换算法4.1.3、直线的Bresenham算法则有2023/2/5西安工程大学计算机图形学25

是否增1取决于如图所示误差项

d的值。因为直线的起始点在象素中心，所以误差项

d的初值d0＝0

因为x每增加1，d的值相应递增直线的斜率值

k，即d＝d＋k。1、当d≥0.5时，直线与xi＋1列垂直网格交点最接近的象素为右上方象素（xi+1，yi＋1）；2、当d<0.5时，更接近直线的为正右方象素（xi＋1，yi）。

4.1直线段的扫描转换算法注：一旦y方向上走一步，d=d-1。2023/2/5西安工程大学计算机图形学26为方便计算，令e＝d－0.5，e的初值为－0.5，增量为

k。结论：1.

d的初值d0＝0，d＝d＋k；2.当

d≥0.5时，下一个像素取为，右上方象素（xi+1，yi＋1）；3.当

d<0.5时，下一个像素取为

正右方象素（xi＋1，yi）。

2.当e<0时，更接近于正右方像素点（xi＋1，yi）。

图-1

Bresenham算法误差项的几何含义}dy}d}d

x}d4.1直线段的扫描转换算法

1.当e≥0时，取当前像素（xi，yi）的右上方像素点（xi＋1，yi＋1）；注：同前面一样，y方向上走一步，e=e-1。

算法步骤：1.输入直线的两端点P0(x0,y0)和P1(x1,y1)。2.计算初始值△x、△y、e=-0.5、x=x0、y=y0。3.绘制点(x,y)。4.e更新为e+k，判断e的符号。若e>0，则(x,y)更新为(x+1,y+1)，同时将e更新为e-1；否则(x,y)更新为(x+1,y)。5.当直线没有画完时，重复步骤3和4。否则结束。2023/2/5西安工程大学计算机图形学28

举例1:用Bresenham方法扫描转换连接两点P0（0,0）和P1（5,2）的直线段。斜率K=2/5=0.4e0=-0.5e=d-0.5,d=d+k,k=dy/dx当e≥0时，取当前像素的右上方像素为下一个像素当e<0时，取当前像素的正右方像素为下一个像素4.1直线段的扫描转换算法0143215234x e ye-10－0.5 0 1－0.1 0 20.3 1－0.73－0.3 1 40.1 2－0.95－0.5 2 2023/2/5西安工程大学计算机图形学29Bresenham画线算法参考程序

(0<k<1)：voidBresenhamline(intx0,inty0,intx1,inty1,intcolor){intx,y,i;floatdx,dy,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;}

}

}4.1直线段的扫描转换算法因为一旦y方向上走一步，就减去1。没有摆脱浮点数计算2023/2/5西安工程大学计算机图形学30

上述bresenham算法在计算误差项与直线斜率时用到小数与除法。可以改用整数以避免除法。由于算法中只用到误差项的符号，因此可作如下替换：

改进的Bresenham画线算法程序：4.1直线段的扫描转换算法递增量初始量原先即2023/2/5西安工程大学计算机图形学31voidBresenhamline(intx0,inty0,intx1,inty1,intcolor){intx,y,dx,dy,e;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;}

}}2023/2/5西安工程大学计算机图形学32Bresenham算法的优点是：1、不必计算直线之斜率，因此不做除法；2、不用浮点数，只用整数；3、只做整数加减法和乘2运算，而乘2运算可以用硬件移位实现。Bresenham算法速度很快，并适于用硬件实现。4.1直线段的扫描转换算法4.1.3、直线的Bresenham算法2023/2/5西安工程大学计算机图形学33(1)上述算法只对斜率在0~1之间的直线段生成适合，

当直线的斜率大于1时，算法应该如何改进?MaxxMaxy(0,0)(50,20)MaxyMaxx(0,0)(50,20)}d

}d

}d

}d

注意：此时d或e的增量为几点讨论和思考4.1直线段的扫描转换算法2023/2/5西安工程大学计算机图形学34for(i=0;i<=dy;i++){putpixel(x,y,color);y=y+1;e=e+k1;if(e>=0){x=x+1;e=e-1;}}}(2)Bresenham画线算法参考程序

(k>1)：Bresenham_line(intx0,inty0,intx1,inty1,intcolor){intx,i,y;floatdx,dy,k,k1,e;dx=x1-x0;dy=y1-y0;k=dy/dx;k1=1/k;e=-0.5;x=x0;y=y0;4.1直线段的扫描转换算法2023/2/5西安工程大学计算机图形学35(3)根据上述的思想，我们如何将算法扩展到，任一八分圆坐标空间图，从而形成一般Bresenham算法？

如下图：4.1直线段的扫描转换算法(4)适用于任意斜率的Bresenham直线生成算法程序示例2023/2/5西安工程大学计算机图形学364.2圆的扫描转换算法

下面仅以圆心在原点、半径R为整数的圆为例，讨论圆的生成算法。假设圆的方程为：

X2+Y2=R2

若圆心不在原点可以通过坐标变换画出任意位置的圆。2023/2/5西安工程大学计算机图形学374.2.1圆弧扫描算法

X2+Y2=R2

Y=Sqrt(R2-X2)在一定范围内，每给定一X值，可得一Y值。当X取整数时，Y须取整。缺点：浮点运算，开方，取整，不均匀。yx2023/2/5西安工程大学计算机图形学384.2.2角度DDA法

xn+1=x

n+dx=x

n－

Rsind=x

n－

(y

n－y0)d

y

n+1=y

n+dy=y

n+Rcosd=y

n+(xn－x0)d

给定圆上的初始值x1，y1及d值后，即可以增量方式获得圆周上的坐标，然后取整可得象素坐标。但要采用浮点运算、乘法运算、取整运算。圆的极坐标方程x=x0+Rcos

y=y0+Rsin求微分dx=－

Rsind

dy=Rcosd记

xn+1－xn

＝dx

yn+1－yn

＝dy2023/2/5西安工程大学计算机图形学394.2.3中点画圆法第二个8分圆P为当前点亮象素，那么，下一个点亮的象素可能是P1(Xp+1，Yp)或P2(Xp+1，Yp

－1)。MP1P2P（Xp

，Yp

）利用圆的对称性，只须讨论1/8圆。XYY=XY=-X2023/2/5西安工程大学计算机图形学40构造判别函数：

F（X，Y）=X2+Y2-R2

；若

F（X，Y）=0

则（X，Y）在圆上；

F（X，Y）<0

则（X，Y）在圆内；

F（X，Y）>0

则（X，Y）在圆外。设M为P1、P2间的中点，M=(Xp+1,Yp-0.5)MP1P24.2.3中点画圆法2023/2/5西安工程大学计算机图形学41有如下结论：

F(M)<0

M在圆内

取P1

F(M)>=0M在圆外

取P2为此，可采用如下判别式：

MP1P2P(xp,yp)4.2.3中点画圆法2023/2/5西安工程大学计算机图形学42

d=F(M)=F(xp+1,yp-0.5)=(xp+1)2+(yp-0.5)2-R2

若d<0,则P1

为下一个象素，那么再下一个象素的判别式为

d1=F(xp+2,yp-0.5)=(xp+2)2+(yp-0.5)2-R2

=d+2xp+3

即d

的增量为2xp+3.MP1P2P(xp,yp)4.2.3中点画圆法2023/2/5西安工程大学计算机图形学43

若d>=0,则P2

为下一个象素，那么再下一个象素的判别式为：d1=F(xp+2,yp-1.5)=(xp+2)2+(yp-1.5)2-R2

=d+（2xp+3）+（-2yp+2）即d

的增量为2(xp-yp)+5.

d的初值:d0=F(1,R-0.5)=1+(R-0.5)2-R2

即：d0=1.25-RMP1P2P2P(xp,yp)4.2.3中点画圆法2023/2/5西安工程大学计算机图形学44MidpointCircle(intr,intcolor){intx,y;floatd;x=0;y=r;d=1.25-r;putpixel(x,y,color);

while(x<y)

{

if(d<0){d+=2*x+3;x++；}else{d+=2*(x-y)+5;x++;y--;}putpixel(x,y,color);}}4.2.3中点画圆法2023/2/5西安工程大学计算机图形学45为了进一步提高算法的效率，可以将上面的算法中的浮点数改写成整数，将乘法运算改成加法运算，即仅用整数实现中点画圆法。使用e=d-0.25代替de0=1-R4.2.3中点画圆法2023/2/5西安工程大学计算机图形学46上述算法能否再改进呢？注意到d

的增量是x,y的线性函数，每当x递增1，则d的增量递增Δx=2每当y递减1，则d的增量递增Δy=2Δx初始值=3；Δy初始值=-2R+24.2.3中点画圆法2023/2/5西安工程大学计算机图形学47

本节介绍另一种常用的画圆算法Bresenham算法.不失一般性，考虑圆心在原点，半径为R的四分之一圆。取（0，R）为起点，按顺时针方向生成圆。如下图所示：（0，R）YXOR第一个4分圆

4.2.4Bresenham画圆算法2023/2/5西安工程大学计算机图形学48从这段圆弧的任意一点出发，按顺时针方向生成圆时，为了最佳逼近该圆，下一个像素的取法只有三种可能的选择：正右方像素，右下方像素和正下方像素。分别记为H、D和V。如下图所示：(x,y)H(x+1,y)V(x,y-1)D(x+1,y-1)第一个4分圆下一像素的三个候选者（0，R）YXOR第一个4分圆

4.2.4Bresenham画圆算法2023/2/5西安工程大学计算机图形学49

这三个像素中，与理想圆弧最近者为所求像素。理想圆弧与这三个候选点之间的关系只有下列五种情形：1.H、D、V全在圆内；

2.H在圆外,D、V在圆内；

3.D在圆上,H在圆外,V在圆内;4.H、D、在圆外，V在圆内；

5.H、D、V全在圆外；

(x,y)H(x+1,y)D(x+1,y-1)V(x,y-1)123542023/2/5西安工程大学计算机图形学50

上述三点到圆心的距离平方与圆弧上一点到圆心的距离平方之差分别为：

与Bresenham直线扫描算法一样，在选最佳逼近该圆的像素时，我们希望只判别误差项的符号。

我们以△D的符号分为三种情况讨论。DVOH△H△D△V几何解释如右图，它们可以表示H，D，V离圆弧的远近。2023/2/5西安工程大学计算机图形学51情况（一）：

为了确定H和D哪个更接近于圆弧,令如果

,那么右下方像素D在圆内，圆弧与候选点的关系只可能是1或2的情形。则这时最佳逼近圆弧的像素只能是H或D两个像素之一。(x,y)H(x+1,y)D(x+1,y-1)V(x,y-1)123542023/2/5西安工程大学计算机图形学521.若,则圆到正右方像素H的距离小于圆到右下方像素D的距离,此时应取H为下一个像素。2.若,则圆到右下方像素D的距离较小,故应取D为下一个像素。3.若,两者均可取，约定取正右方像素H。下面来计算的值，此时只会出现情形1或2。(x,y)H(x+1,y)D(x+1,y-1)V(x,y-1)12354故可根据的符号，判断应取H还是D对于情形2，H在圆外，D在圆内，因此所以可以简化为：2023/2/5西安工程大学计算机图形学53(x,y)H(x+1,y)D(x+1,y-1)V(x,y-1)123542023/2/5西安工程大学计算机图形学54(x,y)H(x+1,y)D(x+1,y-1)V(x,y-1)12354对于情形1，H、D都在圆内，而在这段圆弧上，y是x的单调递减函数，所以只能取H为下一个像素。且这时，因此有

：

与情形2的判别条件一致。可见在的情况下，若，则应取H为下一像素，否则应取D为下一像素由上述讨论可知：

当时，若，即,则取H，否则取D

如果,那么右下方像素D在圆外，圆弧与候选点的关系只可能是4或5的情形。则这时最佳逼近圆弧的像素只能是V或D两个像素之一。2023/2/5西安工程大学计算机图形学55情况（二）：

为了确定V和D哪个更接近于圆弧,令(x,y)H(x+1,y)D(x+1,y-1)V(x,y-1)123542023/2/5西安工程大学计算机图形学561，当

，即时，应取右下方像素D；2，当，即时，应取正下方像素V；3，当时，二者均可取，我们约定取右下方像素D下面来计算的值，此时只会出现情形4或5。(x,y)H(x+1,y)D(x+1,y-1)V(x,y-1)123542023/2/5西安工程大学计算机图形学57(x,y)H(x+1,y)D(x+1,y-1)V(x,y-1)12354先考虑情形4：由于D在圆外，V在圆内,所以则可以简化为故在时可以根据

的符号，判断取D或V

时,取D;当时取V2023/2/5西安工程大学计算机图形学58(x,y)H(x+1,y)D(x+1,y-1)V(x,y-1)12354对于情形5，D、V都在圆外，显然取V为下一个像素。此时

，所以

可见,在

时，当时,取D为下一像素，否则应取V为下一像素。由上述讨论可知：2023/2/5西安工程大学计算机图形学59情况（三）：此时

D恰好在圆上，故应取

D作为下一像素。(x,y)H(x+1,y)D(x+1,y-1)V(x,y-1)123542023/2/5西安工程大学计算机图形学60

归纳上述3种情况的讨论，可得计算下一个像素的算法：1、当

时，若，则取D，否则取V；2、当

时，若，则取H，否则取D；3、当时，取D。2023/2/5西安工程大学计算机图形学61(x,y)(x+2,y-1)(x＋1,y-1)(x+2,y)

下面讨论的增量算法。1、若下一像素取的是HH坐标为：其误差项H(x+1,y)2023/2/5西安工程大学计算机图形学62(x,y)(x+2,y-1)(x＋1,y-2)(x+2,y－2)2、若下一像素取的是DD坐标为：D(x+1,y－1)其误差项2023/2/5西安工程大学计算机图形学63(x,y)(x+1,y-1)(x,y-2)(x+1,y－2)3、若下一像素取的是VV坐标为：V(x,y－1)其误差项2023/2/5西安工程大学计算机图形学64Bresenham_Ciecle(intr,intcolor){intx,y,deltaD,deltaHD,delta2,direction;x=0;y=R;deltaD=2*(1-R);//△D初始值while(y>=0){putpixel(x,y,color);if(deltaD<0){deltaHD=2*(deltaD+y)－1;if(deltaHD<=0)direction=1;//即选H

elsedirection=2;//即选D}Bresenham画圆算法参考程序2023/2/5西安工程大学计算机图形学65elseif(deltaD>0){deltaDV=2*(deltaD-x)-1;if(deltaDV<=0)direction=2;elsedirection=3;}elsedirection=2;switch(direction){case1:x++;deltaD+=2*x+1;break;case2:x++;y--;deltaD+=2*(x-y+1);break;case3:y--;deltaD+=(-2*y+1);break;}/*switch*/}/*while*/}/*Bresenham_Ciecle*/2023/2/5西安工程大学计算机图形学66Bresenham画圆算法

现在从(0,R)点开始向右下方逐点来寻找圆弧上的点。如图中点Pi是已选中的一个表示圆弧上的点，根据圆弧的走向，下一个点应该从Hi或者Li中选择。显然应选离圆弧最近的点作为显示圆弧的点。PiHiLi假设圆的半径为R，显然，当

xhi2+yhi2-R2≥R2-(xli2+yli2)时应该取Li。否则取Hi。令di=xhi2+yhi2+xli2+yli2–2R2

显然，

当di≥0时应该取Li。否则，取Hi。2023/2/5西安工程大学计算机图形学67di=(xi+1)2+yi2+(xi+1)2+(yi-1)2-2R2=2(xi+1)2+2yi2-2yi

+1-2R2当di<0时->取Hi(xi+1,yi)

，则PiHiLi

下步就是如何快速的计算di。设图中Pi的坐标(xi,yi)则Hi和Li的坐标为(xi+1,yi)和(xi＋1,yi-1)di+1=(xi+1+1)2+yi2+(xi+1+1)2+(yi-1)2-2R2=2(xi+1)2+2yi2-2yi+1-2R2+4xi+6=di+4xi+6Bresenham画圆算法2023/2/5西安工程大学计算机图形学68当di≥0时->取Li(xi＋1,yi-1)

，则

di+1=(xi

+1+1)2+(yi-1)2+(xi+1+1)2+(yi-1-1)2-2R2=di+4(xi-yi)+10PiHiLi

易知x0=0，y0=R,x1=x0+1

因此d0=12+y02+12+(y0-1)2-2R2

=3-2y0=3-2RBresenham画圆算法2023/2/5西安工程大学计算机图形学69生成圆弧的正负法

原理：

设圆的方程为F(x,y)=X2+Y2-R2=0;

假设求得Pi的坐标为(xi,yi)；则当Pi在圆内时->F(xi,yi)<0->向右->向圆外当Pi在圆外时->F(xi,yi)>0->向下->向圆内2023/2/5西安工程大学计算机图形学70即求得Pi点后选择下一个象素点Pi+1的规则为：当F(xi,yi)≤0取xi+1=xi+1，yi+1=yi;

当F(xi,yi)＞0取xi+1=xi，yi+1=yi-1;

这样用于表示圆弧的点均在圆弧附近，且使F(xi,yi)时正时负，故称正负法。快速计算的关键是F(xi,yi)的计算，能否采用增量算法？生成圆弧的正负法2023/2/5西安工程大学计算机图形学71若F(xi,yi)已知，计算F(xi+1,yi+1)可分两种情况：1、F(xi,yi)≤0->xi+1=xi+1，yi+1=yi;->F(xi+1,yi+1)=(xi+1)2+(yi+1)2-R2

->=(xi+1)2+yi2

-R2=F(xi,yi)+2xi

+12、F(xi,yi)＞0->xi+1=xi，yi+1=yi-1;->F(xi+1,yi+1)=(xi+1)2+(yi+1)2-R2

->=xi2+(yi–1)2-R2=F(xi,yi)-2yi

+13、初始值：略生成圆弧的正负法2023/2/5西安工程大学计算机图形学724.3椭圆的扫描转换F(x,y)=b2x2+a2y2-a2b2=0椭圆的对称性，只考虑第一象限椭圆弧生成，分上下两部分，以切线斜率为-1的点作为分界点.也就是法向量中x和y分量相等的点.椭圆上一点处的法向：

N(x,y)=Fx'i+Fy'

j =2b2

x

i+2a2

y

j上半部分下半部分2023/2/5西安工程大学计算机图形学73上半部分,法向量的y分量大。法向量两分量相等在当前中点处，法向量（2b2(Xp+1)，2a2(Yp-0.5))的y分量比x分量大,即：b2(Xp+1)<a2(Yp-0.5),而在下一中点，不等式改变方向，则说明椭圆弧从上部分转入下部分上半部分下半部分M1M2下半部分,法向量的x分量大4.3椭圆的扫描转换2023/2/5西安工程大学计算机图形学74先讨论椭圆弧的上部分

设(Xp，Yp)已确定，则下一像素为:(Xp+1，Yp)或(Xp+1，Yp-1).为了选取下一像素将候选像素中点(Xp+1,Yp-0.5)带入椭圆隐式方程判定符号.

d1=F(Xp+1,Yp-0.5)=b2(Xp+1)2+a2(Yp-0.5)2-a2b2

与圆弧中点算法类似：确定一个象素后，接着在两个候选象素的中点计算一个判别式的值，由判别式的符号确定距离椭圆弧更近的点4.3椭圆的扫描转换2023/2/5西安工程大学计算机图形学75

根据d1的符号来决定是取正右方的(Xp+1，Yp)还是右下方(Xp+1，Yp-1).。

若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)4.3椭圆的扫描转换再讨论椭圆弧的下部分

设(Xp，Yp)已确定，则下一像素为:(Xp，Yp-1)或(Xp+1，Yp-1).为了选取下一像素将候选像素中点(Xp+0.5,Yp-1)带入椭圆隐式方程判定符号.

d2=F(Xp+0.5,Yp-1)=b2(Xp+0.5)2+a2(Yp-1)2-a2b24.3椭圆的扫描转换若d2＜0，中点在椭圆内，取右下方象素，判别式更新为：

d2’=F(Xp+1.5,Yp-2)=d2+b2(2Xp+2)+a2(3-2Yp)d2的增量为b2(2Xp+2)+a2(3-2Yp).若d2>=0，中点在椭圆外，取正下方象素，判别式更新为：

d2’=F(Xp+0.5,Yp-2)=d2+a2(3-2Yp)d2的增量为a2(3-2Yp).4.3椭圆的扫描转换d1的初始值：椭圆弧起点为(0，b)；第一个中点为(1,b-0.5).初始判别式：d10=F(1,b-0.5)=b*b+a*a(-b+0.25)转入下部分，下一象素可能是正下方或右下方，此时判别式要初始化。假定上半部分最后一