中农大AutoCAD及计算机图学基础课件04基本图形生成算法

第4讲 基本图形生成算法点：CRT监视器：在指定的屏幕位置上开启（接通）电子束，使该位置上的荧光点辉亮。黑白光栅显示器：将帧缓存中指定坐标位置处的值置1，然后当电子扫视每一条水平扫描线时，一旦遇到缓存中值为1的点，就发射一亮光，即输出一个点。随机扫描显示器：画点的指令保存在显示文件中，该指令把坐标值转换成偏转电压，并在每一个刷新周期内，使电子束偏转到相应位置。直线：通过在应用程序中对每一条直线端点坐标的描述，由输出设备将一对端点间的路径加以描绘来实现。曲线及各种复杂的图素：将其离散成许多小直线段，连接各直线来逼近欲生成的曲线或其它复杂图形。图形的扫描转换：即图形的光栅化。在光栅显示器等数字设备上确定一个最佳逼近于图形的像素集的过程。4.1

直线的扫描转换光栅化直线生成算法的原则：直而光滑端点准确亮度均匀速度快生成算法：逐点比较法、数值微分法、Bresenham算法4.1.1数值微分法

（DDA：DigitalDifferentialAnalyzer）是基于直线微分方程生成直线的算法♣条件：待扫描转换的直线段：P0(x0,y0),P1(x1,y1)∆x=x1-x0,∆y=y1-y0参数方程：x=x0+∆x*ty=y0+∆y*t0≤t≤1♣直接求交算法：划分区间[0,1],dt=1/n计算坐标、

取整.复杂度：乘法+加法+取整♣

DDA增量算法：用增量代替微分k=∆y/∆xxinc=∆x*εyinc=∆y*εxi+1=xi+∆x*ε=xi+xincyi+1=yi+∆y*ε=yi+yinc复杂度：加法+取整一阶导数连续，∆x、∆y成比例 选取ε=1/(max(|∆x|,|∆y|))

在x或y变化大的方向，即计长方向上，步长始终为1，而另一方向上的步长则小于1，其是否走步，视其有无整数部分溢出，即若|k|≤1，则取xinc=1，yinc=k，yi+1=yik若|k|>1，则取yinc=1，xinc=1/k，Xi+1=Xi1/k可用寄存器和加法器来实现：整数部分 小数部分∆x*ε或∆y*ε+<1单位步长初值0.5x或y♣

DDA算法描述:voidDDA_line(intx1,y1,x2,y2){int

deltax,deltay,n,i;floatx,y,xinc,yinc;

deltax=x2-x1;deltay=y2–y1;if(abs(deltax)>abs(deltay)) n=abs(deltax);else n=abs(deltay);

xinc=(float)deltax/n;

yinc=(float)deltay/n;x=x1;y=y1;

putpixel(round(x),round(y));for(i=0;i<n;i++) {x+=xinc;y+=yinc;

putpixel(round(x),round(y));}}♣

DDA算法缺点:

需要进行浮点数运算运行效率低不便于用硬件实现4.1.2Bresenham算法♣目标：消除DDA算法中的浮点运算♣条件：同DDA算法斜率：0≤k≤1♣直线段的隐式方程（(x0,y0)(x1,y1)两端点）F(x,y)=ax+by+c=0a=y0-y1,b=x1-x0,c=x0y1-x1y0♣分析假设线段的端点坐标为(x1,y1)和(x2,y2)，

线段将平面以(x1,y1)为坐标原点划分为八个卦限，首先考虑：线段在第一卦限，即Δx=x2-x1>0，Δy=y2-y1≥0，并且Δx≥Δy此时，xinc=1，yinc=k（0≤k≤1），即每走一步，x坐标增加1，y坐标增加k。♣

Bresenham画线算法示意图

:

假设当前列（x=xi列）中最接近线段的像素已经取为P(xi,yi)，则下一列（x=xi+1列）中最接近线段的像素只能在P的右上方点H(xi+1,yi+1)或正右方点L(xi+1,yi)中选择。选择标准：如果交点A在中点M下方，那么下一点取L；如果A在M上方，那么下一点取H；如果A恰好与M重合，那么下一点可以取L，也可以取H，我们约定取H。

将A点到y=yi行的距离记为di，即di=k*(xi+1)+b-yi，则选择的标准可以表达为：

di<0.5，取L di≥0.5，取H

Bresenham画线算法以H与L的中点M作为选择的标准，因此也被称为中点画线算法。令判别式ei=di-0.5=k*(xi+1)+b-yi-0.5

则有：1.如果ei<0，说明di<0.5，那么下一点取L(xi+1,yi)，即xi+1=xi+1，yi+1=yi，新的判别式ei+1=k*(xi+1+1)+b-yi+1-0.5=k*(xi+1+1)+b-yi-0.5

=ei+k；2.如果ei≥0，说明di≥0.5，那么下一点取H(xi+1,yi+1)，即xi+1=xi+1，yi+1=yi+1，新的判别式ei+1=k*(xi+1+1)+b-yi+1-0.5=k*(xi+1+1)+b-(yi+1)-0.5=ei+k-1。初始时，x=x1，y=y1，e1=k*(x1+1)+b-y1-0.5=(k*x1+b-y1)+k-0.5

=k-0.5。

♣改进的Bresenham算法

注意到斜率k=Δy/Δx，并且Δx>0，引入f=2*Δx*e，因为f与e的符号相同，因此可以代替e作为判别式。初始时，x=x1，y=y1，f1=2*Δy-Δx。假设已知当前列像素位置(xi,yi)和判别式fi，则有：1.如果fi<0，则下一像素：xi+1=xi+1，yi+1=yi，fi+1=fi+2*Δy；2.如果fi≥0，则下一像素：xi+1=xi+1，yi+1=yi+1，fi+1=fi+2*(Δy-Δx)。

♣再改进的Bresenham算法♣算法描述voidBresenham_line(intx1,y1,x2,y2){int

deltax,deltay,x,y,f,i;

deltax=x2–x1;deltay=y2–y1;f=2*deltay–deltax;x=x1;y=y1;

putpixel(x,y);for(i=0;i<deltax;i++){if(f<0)f+=2*deltay;else{f+=2*(deltay-deltax);y++;}x++;

putpixel(x,y);}}♣

Bresenham画线算法的特点：

只包括整数的加法、减法和左移（乘2）操作，效率高适合用硬件实现

适用于第一卦限的Bresenham画线算法可以方便地推广到一般情况：如果Δx<0或Δy<0，只需将x或y的增量变为负数即可；如果|Δy|>|Δx|，只需将x和y的地位对调，即以y方向作为计数方向。

4.2

二次曲线的扫描转换Ax2+Bxy+Cy2+Dx+Ey+F=0圆、椭圆、抛物线、双曲线基本技术：将曲线离散成小直线段，通过连接各直线段来逼近所要的曲线。4.2.1

圆弧的拟合法1、逐点比较法插补圆弧在输出圆弧的过程中，每走完1个单位长度以后，就与应画的圆弧进行比较，根据比较的结果，再决定下一次的走向。约定点处于不同象限时的运动走向：

顺圆走向、逆圆走向（1）圆弧的正负划分

F(x,y)=x2+y2-R2圆弧外的点：F(X，Y)＞0圆弧内的点：F(X，Y)＜0Fm>0 点M在圆外，走-ΔxFm=0 点M在圆上，走-ΔxFm<0 点M在圆内，走+Δy

4

3

2

1

5

6

7

8SEC（2）判别函数圆心：C(xc,yc)起始点：S(xs,ys)任意点：M(xm,ym)判别函数：Fm=Rm-RsM（3）一般运算规律象限Fi≥0Fi<0移动量运算公式移动量运算公式逆Ⅰ逆Ⅲ顺Ⅱ顺Ⅳ–Δx+Δx+Δx–ΔxFi+1=Fi-2Δxxi+Δx2|xi+1|=|xi|–Δx|yi+1|=|yi|+Δy–Δy+Δy–ΔyFi+1=Fi-2Δyyi+Δy2|xi+1|=|xi||yi+1|=|yi|+Δy逆Ⅱ逆Ⅳ顺Ⅰ顺Ⅲ–Δy+Δy–Δy+ΔyFi+1=Fi-2Δyyi+Δy2|xi+1|=|xi||yi+1|=|yi|–Δy–Δx+Δx+Δx–ΔxFi+1=Fi-2Δxxi+Δx2|xi+1|=|xi|+Δx|yi+1|=|yi|（4）终点判断与终点坐标比较条件：|xi-xe|<δ

且|yi-ye|<δ

为避免画大圆弧时起点与终点靠得很近，先连续走几步后，再进行终点判断。voidPN_circle(intradius){intx,y,f;x=0;y=radius;f=0;

putpixel(x,y);while(x<y){if(f<=0){f+=2*x+1;x++;}else{f+=-2*y+1;y--;}

putpixel(x,y);}}（5）算法实现2、简单方程（DDA算法）产生圆弧考虑对象：第一象限的八分之一圆弧圆心(xc,yc)，半径R，起始角ts，终止角te

x=xc+Rcosty=yc+Rsint

对应的微分方程：

dx=-Rsintdt=-ydt

dy=Rcostdt=xdt

用差分方程近似地代替微分方程，得：

∆x=-y∆t

∆y=x∆t圆的对称性

离散化圆弧，求出从ts到te的运动步数n:n=(te-ts)/dt+0.5一般根据半径、速度及精度要求给定dt的经验数据。平面连接3个点的坐标的圆弧可用此算法，计算出圆心坐标、半径、起始角和终止角，然后调用DDA算法。DDA产生椭圆弧算法可用同样思想得到3、中点画圆算法假设当前列（x=xi列）中最接近圆弧的像素已经取为P(xi,yi)根据第二卦限1/8圆的走向，下一列（x=xi+1列）中最接近圆弧的像素只能在P的正右方点H(xi+1,yi)或右下方点L(xi+1,yi-1)中选择

中点画圆算法采用H与L的中点作为选择标准。将H与L的中点记为M，其坐标为(xi+1,yi-0.5)，选择的标准是：如果M在圆内，那么下一点取H；如果M在圆外，那么下一点取L；如果M在圆上，那么下一点可以取L，也可以取H，我们约定取L。令判别式di=F(xi+1,yi-0.5)=(xi+1)2+(yi-0.5)2-R2，则：

1.如果di<0，说明M在圆内，下一点取H(xi+1,yi)，即

xi+1=xi+1,yi+1=yi，新的判别式

di+1=F(xi+1+1,yi+1-0.5)=(xi+1+1)2+(yi-0.5)2-R2

=di+2xi+32.

如果di≥0，说明M在圆外或圆上，下一点取L(xi+1,yi-1)，即xi+1=xi+1,yi+1=yi-1，新的判别式

di+1=F(xi+1+1,yi+1-0.5)=(xi+1+1)2+(yi-1-0.5)2-R2

=di+2xi-2yi+5

初始时，

x0=0，y0=R，

d0=F(x0+1,y0-0.5)=(0+1)2+(R-0.5)2-R2=1.25-R

但这个算法中仍然有浮点数运算！

令f=d-0.25，

初始：x0=0，y0=R，f0=d0-0.25=1-R设已知当前列像素位置(xi,yi)和判别式fi，则有：1）

如果fi<-0.25，那么下一列像素位置

xi+1=xi+1，

yi+1=yi，

fi+1=fi+2xi+3；2）

如果fi≥-0.25，那么下一列像素位置

xi+1=xi+1，

yi+1=yi-1，

fi+1=fi+2xi-2yi+5。

f的初始值1-R为整数，每次迭代f的变化量也是整数，即f保持为整数，因此f<-0.25等价于f<0。voidMidpoint_circle(intradius){intx,y,f;x=0;y=radius;f=1-radius;

putpixel(x,y);while(x<y){if(f<0)f+=2*x+3;else{f+=2*(x-y)+5;y--;}x++;

putpixel(x,y);}}适用于第二卦限的中点画圆程序中点画圆算法的优点

中点画圆算法只用到整数的加法、减法和左移（乘2）运算，效率高并且适合用硬件实现。

当fi<0时，下一点取H(xi+1,yi)，fi的变化量为hi=2xi+3；

当fi≥0时，下一点取L(xi+1,yi-1)，fi的变化量为li=2xi-2yi+5。

hi和li都是x和y的线性函数，而不是常数，但也可以用增量算法计算它们的值，从而提高效率。

（1）fi<0，下一点取H(xi+1,yi)，则

hi+1=2xi+1+3=2(xi+1)+3=hi+2L li+1=2xi+1-2yi+1+5=2(xi+1)-2yi+5=li+2

（2）fi≥0，下一点取L(xi+1,yi-1)，则

hi+1=2xi+1+3=2(xi+1)+3=hi+2 li+1=2xi+1-2yi+1+5=2(xi+1)-2(yi-1)+5=li+4初（3）初始，x0=0，y0=R，h0=3，l0=-2R+5另一个中点画圆程序voidMidpoint_circle1(intradius){intx,y,f,h,l;x=0;y=radius;f=1-radius;h=3;l=5–2*radius;

putpixel(x,y);while(x<y){if(f<0){f+=h;h+=2;l+=2;}else{f+=l;h+=2;l+=4;y--;}x++;

putpixel(x,y);}}4、Bresenham画圆算法

设当前列（x=xi列）中最接近圆弧的像素已经取为

P(xi,yi)，

下一列（x=xi+1列）中最接近圆弧的像素只能在P的

正右方点H(xi+1,yi)或右下方点L(xi+1,yi-1)中选择。

Bresenham画圆算法采用点到圆心的距离平方与半径

平方之差作为选择标准。令D(H)=(xi+1)2+yi2-R2，

D(L)=(xi+1)2+(yi-1)2-R2，则选择的标准是： 若|D(H)|<|D(L)|，则下一点取H；

若|D(H)|>|D(L)|，则下一点取L；

若|D(H)|=|D(L)|，则下一点取L，也可以取H，

约定取L。

Bresenham画圆算法示意图

11.若D(H)>0且D(L)<0，可写成di=D(H)+D(L)22.若D(H)≤0，说明H在圆内或圆上，那么L一定在圆内，即一定有D(L)<0且|D(H)|<|D(L)|，此时di<0。33.若D(L)≥0，说明L在圆外或圆上，那么H一定在圆外，即一定有D(H)>0且|D(H)|>|D(L)|，此时di>0。

改进：

di=D(H)+D(L)=(xi+1)2+yi2-R2+(xi+1)2+(yi-1)2-R2

di+1=(xi+1+1)2+yi+12-R2+(xi+1+1)2+(yi+1-1)2-R2初始时，x0=0，y0=R，

d0=(x0+1)2+y02-R2+(x0+1)2+(y0-1)2-R2=3-2R设已知当前列像素位置(xi,yi)和判别式di，则：1.如果di<0，那么下一列像素位置：

xi+1=xi+1，yi+1=yi，di+1=di+4xi+62.如果di≥0，那么下一列像素位置：

xi+1=xi+1，yi+1=yi-1，di+1=di+4(xi-yi)+10

voidBresenham_circle(intradius){intx,y,d;x=0;y=radius;d=3-2*radius;write_pixel(x,y);while(x<y){if(d<0)d+=4*x+6;else{d+=4*(x-y)+10;y--;}x++;write_pixel(x,y);}}

中点画圆算法的判别式初始值d0M=1.25-R，变化量为

2xi+3或2(xi-yi)+5;

Bresenham画圆算法的判别式初始值d0B=3-2R，变化

量为4xi+6或4(xi-yi)+10，即Bresenham画圆算法的

判别式的变化量是中点画圆算法的2倍。

中点画圆算法与Bresenham画圆算法在整数情况下完

全等价，产生完全相同的像素序列。

4.2.2

椭圆的扫描转换F(x,y)=b2x2+a2y2-a2b2=0椭圆的对称性，只考虑第一象限椭圆弧生成，分上下两部分，以切线斜率为-1的点作为分界点。椭圆上一点处的法向：

N(x,y)=F’x

i+F’y

j =2b2xi+2a2yj在上半部分,法向量的y分量大在下半部分,法向量的x分量大上半部分下半部分法向量两分量相等M1M2若在当前中点处，法向量（2b2(Xp+1)

，2a2(Yp-0.5))的y分量比x分量大,即：b2(Xp+1)<a2(Yp-0.5)；而在下一中点，不等式改变方向，则说明椭圆弧从上部分转入下部分1、椭圆的中点Bresenham画法与圆弧中点算法类似：确定一个象素后，接着在两个候选象素的中点计算一个判别式的值，由判别式的符号确定更近的点先讨论椭圆弧的上部分

(Xp，Yp)中点(Xp+1,Yp-0.5)

d1=F(Xp+1,Yp-0.5)=b2(Xp+1)2+a2(Yp-0.5)2-a2b2根据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)d1的初始条件： 椭圆弧起点为(0，b)，第一个中点为(1,b-0.5)

初始判别式：d0=F(1,b-0.5)=b*b+a*a(-b+0.25)转入下一部分，下一象素可能是一正下方或右下方，此时判别式要初始化。

d2=