计算机图形学C版4的知识

第3章光栅扫描图形学3.1直线生成算法3.2圆与椭圆的生成算法主要教学内容3.3实区域的扫描转换3.4区域填充3.5图形反走样基础

DD-line(x1,y1,x2,y2,color)

intx1,y1,x2,y2,color;

{intlength;floatx,y,x,y;

length=abs(x2-x1);

if(abs(y2-y1)>length)length=abs(y2-y1);

x=(x2-x1)/length;y=(y2-y1)/length;

x=x1+0.5*sign(x);y=y1+0.5*sign(y);

for(i=1;i<=length;i++)

{putpixel(Int(x),Int(y),color);

x=x+x;

y=y+y;

}

}sign(x)=

1,当x>0时

0,当x=0时

-1,当x<0时putpixel(30,50,2);在(30,50)处用2号色显示一点。它将像素的亮度存储到帧缓存的对应位置。简单DDA算法Int(x)：不大于X的最大整数P132例:起点(0,0),终点(-8,-4)

显示(-1,-1)，(-2,-1)，(-3,-2)，(-4,-2)，(-5,-3)，(-6,-3)，(-7,-4)，(-8,-4)

-1-2-3-4-8-7-6-5-4-3-2-1简单DDA算法应用举例(2)对称DDA法:取△t=2-

n,

有:2n-1<=max(|△X|,|△Y|)<2n思考题:用对称DDA法来处理上例,请写出各轨迹点的坐标。DDA法比直接使用直线方程的方法快，为什么？——没有浮点乘法，但仍有浮点数的加法DDA中取整操作和浮点运算仍然十分耗时。3.1.2Bresenham画线算法类似简单DDA法,每次在增量最大方向上均走一步,由e的值决定另一方向是否走步。设直线的起点(xs,ys),终点(xe,ye),斜率m=△y/△x=(ye-ys)/(xe-xs)

判断e(xi+1)=yi+1-yi,r-0.5

0<=m<1的第1象限直线,x方向为增量最大方向yi,r是当前像素P的纵坐标,yi+1,r是下一个像素的纵坐标，xi+1=xi+1A是C和D的中点,当前像素P,下一步在C或D中选择一个

若e(xi+1)>=0,表示B在A之上,下一个将是D,yi+1,r=yi,r+1

若e(xi+1)<0,表示B在A之下,下一个将是C,yi+1,r=yi,ryi,r+1DB(xi+1,yi+1)ACXYP(xi,yi)O(0,0)yi,re(xi+1)=yi+1-yi,r-0.5

e(x2)=y2-y1,r-0.5=y2-y1-0.5=y1+m-y1-0.5=m-0.5e(xi+2

)=yi+2–yi+1,r-0.5yi+1+m-yi,r-1-0.5=e(xi+1)+m-1,当e(xi+1)>=0时

=yi+1+m-yi,r-0.5=e(xi+1)+m,当e(xi+1)<0时

即e(xi+1)=e(xi)+m-1,当e(xi)>=0时,将选D点(xi+1,yi,r+1)

e(xi)+m,当e(xi)<0时,将选C点(xi+1,yi,r)

e的初值？Bresenham-line(x1,y1,x2,y2,color)

intx1,y1,x2,y2,color;

{intx,y,△x,△y;

floate,m;

x=x1;y=y1;

△x=x2-x1;△y=y2-y1;m=△y/△x;e=m-0.5;

for(i=1;i<=△x;i++)

{putpixel(x,y,color);

ife>=0

{y=y+1;e=e-1;}

x=x+1;e=e+m;

}

}适合0<=m<1的第1象限直线的Bresenham算法P134例:用Bresenham画直线算法生成(0,0)到(8,3)的直线段。

显示(0,0),(1,0),(2,1),(3,1),(4,2),(5,2),(6,2),(7,3)

当e(xi)<0时,(即f(xi)<0)

f(xi+1)=2*e(xi+1)*△x=2*(e(xi)+△y/△x))*△x

=f(xi)+2△y适合0<=m<1的第1象限直线的整数Bresenham算法为便于硬件实现,需去掉除法运算:令f=2*e*△x当e(xi)>=0时,(即f(xi)>=0)f(xi+1)=2*e(xi+1)*△x=2*(e(xi)+△y/△x-1)*△x

=f(xi)+2△y-2△xf(x2)=2*e(x2)*△x=2*(△y/△x-0.5)*△x=2△y-△x则f(xi+1)与f(xi)有何关系？f的初值？Inter.bresenham-Line(x1,y1,x2,y2,color)

intx1,y1,x2,y2,color;

{intx,y,△x,△y,e;x=x1;y=y1;

△x=x2-x1;△y=y2-y1;e=2*△y-△x;

for(i=1;i<=△x;i++)

{putpixel(x,y,color);

if(e>=0){y=y+1;e=e-2*△x;}

x=x+1;e=e+2*△y;

}}

(适合0<=m<1的第1象限直线)整数Bresenham画直线算法算法只用到整数的加法、减法和乘2（算术移位）运算。是一种转换直线的快速增量算法。Generalized-Integer-Bresenham-Line(x1,y1,x2,y2,color);

intx1,y1,x2,y2,color;

{intx,y,△x,△y,s1,s2,temp,interchange;

x=x1;y=y1;△x=abs(x2-x1);△y=abs(y2-y1);

s1=sign(x2-x1);s2=sign(y2-y1);

if(△y>△x){temp=△x;△x=△y;△y=temp;interchange=1;}

elseinterchange=0;

e=2*△y-△x;

for(i=1;i<=△x;i++)

{putpixel(x,y,color);

if(e>=0)

{if(interchange=1)x=x+s1;

elsey=y+s2;

e=e-2*△x;}

if(interchange=1)y=y+s2;

elsex=x+s1;

e=e+2*△y;}}适合各种象限及各种斜率直线的一般Bresenham算法P136例:用一般Bresenham画线算法生成AB线段,起点A(0,0),终点B(-8,-4),请写出轨迹点的坐标。适合各种象限及各种斜率直线的一般Bresenham算法显示(0,0),(-1,-1)，(-2,-1)，(-3,-2)，(-4,-2)，(-5,-3)，(-6,-3)，(-7,-4)如何生成指定宽度的直线?（1）最简单的一种方法是利用“线刷子”.若直线斜率|m|<=1,用垂直方向的线刷子;若直线斜率|m|>1,用水平方向的线刷子.直线段的基本属性有线型、宽度和颜色。线型包括实线、虚线、点线等。如何生成不同线型的直线？putpixel(x,y-1,RED);putpixel(x,y,RED);putpixel(x,y+1,RED);用垂直刷子生成宽度为3的直线段

putpixel(x-1,y,RED);putpixel(x,y,RED);putpixel(x+1,y,RED);

用水平刷子生成宽度为3的直线段采用“线刷子”的优点:简单、容易实现。例：如何用线刷子生成宽度为3的直线？（3）区域填充（2）正方形刷子也可以用上述方法生成粗曲线。如生成半径为16，线宽为4的圆，可生成半径为14和17的两个同心圆，然后填充两个圆之间的区域。

Y

.(-Y,X).(Y,X)

.(-X,Y).(X,Y)

(0,0)X

.(-X,-Y).(X,-Y)

.(-Y,-X).(Y,-X)在生成封闭的圆周时,只要生成第一象限的1/8圆弧,其余部分可利用对称点得到。

圆弧的扫描转换：确定最佳逼近于该圆弧的一组象素；按扫描线顺序，对这些象素进行写操作。方法1:利用圆的方程y2=r2-x2,x从0递增到r/2,利用方程求出y值,效率很低,用到平方、减法、开平方根。x=r.cosØ,y=r.sinØ,Ø从0变化到/4,计算相应的x和y值,但计算正弦和余弦值花时间比前一种更多。方法2：利用bersenham画圆算法、中点法、正负法、逐点插补法，……..设圆心在原点,半径为R(顺时针画圆)。只考虑第1象限的1/8圆周的情况,其余部分可根据对称得出。圆的方程为:X2+Y2-R2=0

yx.Pi-1.Li.Hi(0,0)RBA3.2.1圆弧的bresenham算法P1373.2圆与椭圆的生成算法若D(Si)=XSi2+YSi2-R2>0,Si在圆外；

D(Ti)=XTi2+YTi2-R2<0,Ti在圆内

令di=D(Si)+D(Ti)

若di>0,Ti离圆近,选Ti(从Pi-1的右下角)

di=0,选两点均可

di<0,Si离圆周近,选Si(Pi-1的正右方)yx.Pi-1.Ti.Si(0,0)RBA现在从A点开始向右下方逐点来寻找弧AB要显示的点。如图中点Pi-1是已选中的一个表示圆弧上的点，根据弧AB的走向，下个点应该从Si或者Ti中选择。显然应选Si和Ti中离AB最近的一点。在起点A(0,R)处,S1(1,R),T1(1,R-1)

d1=1+R2-R2+1+(R-1)2-R2=3-2R在起点处，d1的值是多少呢？如何快速的计算di？

下面推导di+1与di之间的关系。

di=D(Si)+D(Ti)=(Xi-1+1)2+Yi-12-R2+(Xi-1+1)2+(Yi-1-1)2-R2(1)若di<0,选Si,Xi+1=Xi-1+1,Yi+1=Yi-1

.Pi-1(Xi-1,Yi-1).Si(Xi-1+1,Yi-1).Si+1(Xi-1+2,Yi-1).Ti(Xi-1+1,Yi-1-1).Ti+1(Xi-1+2,Yi-1-1)di+1=D(Si+1)+D(Ti+1)=(Xi-1+2)2+Yi-12-R2+(Xi-1+2)2+(Yi-1-1)2-R2

=di+4Xi-1+6P138

(2)若di>=0,选Ti,Xi+1=Xi-1+1,Yi+1=Yi-1-1

.Pi-1(Xi-1,Yi-1).Si(Xi-1+1,Yi-1).Ti(Xi-1+1,Yi-1-1).Si+1(Xi-1+2,Yi-1-1).Ti+1(Xi-1+2,Yi-1-2)

di+1=D(Si+1)+D(Ti+1)=(Xi-1+2)2+(Yi-1-1)2-R2+(Xi-1+2)2+(Yi-1-2)2-R2

=di+4(Xi-1-Yi-1)+10BresenhamCircle(r,color)

intr,color;

{intx,y,d;

x=0;y=r;d=3-2*r;

while(x<y)

{putpixel(x,y,color);

if(d>=0)

{d=d+4*(x-y)+10;y=y-1;}

elsed=d+4*x+6;

x=x+1;

}

}圆弧的bresenham算法XY01234567899876543210P139例子：用Bresenham画圆算法生成X

2+Y2-64

=0第1象限的1/4圆弧。同理可以推导出圆心不在原点的第1象限圆弧的di的递推公式(di+1与di之间的关系)。圆方程为:(X

–Xc)

2+(Y–Yc)2-R2=0BresenhamCircle(xc,yc,r,color)

intxc,yc,r,color;

{intx,y,d;

x=0;y=r;d=3-2*r;

while(x<y)

{circle-pointS(x,y,color);

if(d>=0)

{d=d+4*(x-y)+10;y=y-1;}

elsed=d+4*x+6;

x=x+1;

}

if(x=y)circle-pointS(x,y,color);}适合圆心在（xc,yc)的Bresenham画圆周算法其中circle-pointS(x,y,color)

{putpixel(x+xc,y+yc,color);

putpixel(y+xc,x+yc,color);

putpixel(y+xc,-x+yc,color);

putpixel(x+xc,-y+yc,color);

putpixel(-x+xc,-y+yc,color);

putpixel(-y+xc,-x+yc,color);

putpixel(-y+xc,x+yc,color);

putpixel(-x+xc,y+yc,color);

}(xc,yc)yx对称点扫描转换一个椭圆方法1:根据椭圆方程x2/a2+y2/b2=1,对于第1象限内0<=x<=1的每个x值,代入方程求出对应的y值x=a.cosØ,y=b.sinØ,Ø从0变化到/2,计算相应的x和y值速度慢方法2:采用中点法椭圆方程:

F(x,y)=b2x2+a2y2-a2b2=0椭圆的对称性，只考虑第一象限椭圆弧生成，分上下两部分，以切线斜率为-1的点作为分界点。(0,0)3.2.2椭圆的生成(中点法)椭圆方程:F(X,Y)=b2X2+a2Y2-a2b2=0

y..

.

b.

..顺时针生成椭圆心在原点的1/4椭圆弧(其余部分由对称特性求出)

1.上部分椭圆弧,对Pi,下一步应选取Si和Ti中离椭圆近的那个

通过判断两个候选点的中点在椭圆内还是在椭圆外,来确定选哪个候选点.

.Pi(Xi,Yi).Si(Xi+1,Yi).Mi(Xi+1,Yi–0.5).Ti(Xi+1,Yi-1)

令di=F(Mi)=F(Xi+1,Yi-0.5),若di=0,下一步选取Si,Ti中任何一个;

若di>0,Mi在椭圆外,Ti离椭圆近,取Ti,(从Pi向右下角走一步);

若di<0,Mi在椭圆内,Si离椭圆近,取Si,(从Pi向正右方走一步).

在起点P0(0,b)处,有d0=F(X0+1,Y0-0.5)=F(1,b-0.5)=b2+a2(b

-0.5)2-a2b2xa中点法生成椭圆di=F(Mi)=F(Xi+1,Yi-0.5)=b2(Xi+1)2+a2(Yi-0.5)2-a2b2

(1)当di<0时,取Si,即Xi+1=

Xi+1,Yi+1=Yi,则下一个中点为Mi+1(Xi+2,Yi–0.5)

.Pi(Xi,Yi).Si(Xi+1,Yi).(Xi+2,Yi)

.Mi(Xi+1,Yi–0.5)

.Mi+1(Xi+2,Yi–0.5).Ti(Xi+1,Yi-1).(Xi+2,Yi-1)

di+1=F(Mi+1)=F(Xi+2,Yi-0.5)=b2(Xi+2)2+a2(Yi-0.5)2-a2b2

=b2(Xi+1+1)2+a2(Yi-0.5)2-a2b2=b2(Xi+1)2+2b2(Xi+1)+b2+a2(Yi-0.5)2-a2b2

=di+b2(2Xi+3)di的递推公式(2)当di>=0时,取Ti,即Xi+1=

Xi+1,Yi+1=Yi-1

,则下一个中点为Mi+1(Xi+2,Yi–1.5)

.Pi(Xi,Yi).Si(Xi+1,Yi)

.Mi(Xi+1,Yi–0.5)

.Ti(Xi+1,Yi-1).(Xi+2,Yi-1)

.Mi+1(Xi+2,Yi–1.5)

.(Xi+2,Yi-2)

di+1=F(Mi+1)=F(Xi+2,Yi-1.5)=b2(Xi+2)2+a2(Yi-1.5)2-a2b2

=b2(Xi+1+1)2+a2(Yi-0.5-1)2-a2b2=di+b2(2Xi+3)+a2(-2Yi+2)2.下部分椭圆弧

.Pi(Xi,Yi)

.Bi(Xi,Yi-1).Mi

.Ti(Xi+1,Yi-1)其中Mi(Xi+0.5,Yi–1)令di=F(Mi)=F(Xi+0.5,Yi-1),若di=0,取Ti,Bi中任何一个;

若di>0,Mi在椭圆外,Bi离椭圆近,取Bi,(从Pi向正下方走一步);

若di<0,Mi在椭圆内,Ti离椭圆近,取Ti(从Pi向右下角走一步).

下面推导di的递推公式:中点法生成椭圆di=F(Mi)=F(Xi+0.5,Yi-1)=b2(Xi+0.5)2+a2(Yi-1)2-a2b2

(1)当di<0时,取Ti,即Xi+1=

Xi+1,Yi+1=Yi-1

,则下一个中点为Mi+1(Xi+1.5,Yi–2)

.Pi(Xi,Yi).Bi(Xi,Yi-1)

.Mi

.Ti(Xi+1,Yi-1)

其中Mi(Xi+0.5,Yi–1)

.(Xi+1,Yi-2)

.Mi+1.

(Xi+2,Yi-2)其中Mi+1(Xi+1.5,Yi–2)

di+1=F(Mi+1)=F(Xi+1.5,Yi-2)=b2(Xi+1.5)2+a2(Yi-2)2-a2b2

=di+b2(2Xi+2)+a2(-2Yi+3)(2)当di>=0时,取Bi,即Xi+1=

Xi,Yi+1=Yi-1

,下一个中点为Mi+1(Xi+0.5,Yi–2)

.Pi(Xi,Yi).Bi(Xi,Yi-1)

.Mi

.Ti(Xi+1,Yi-1)

其中Mi(Xi+0.5,Yi–1).(Xi,Yi-2)

.Mi+1.(Xi+1,Yi-2)其中Mi+1(Xi+0.5,Yi–2)

di+1=F(Mi+1)=F(Xi+0.5,Yi-2)=b2(Xi+0.5)2+a2(Yi-2)2-a2b2

=di+a2(-2Yi+3)

下部分椭圆弧上半部分d的初值:

d1=F(1,b-0.5)=1*b2+a2*(b-0.5)2-a2*b2

=b*b+a*a*(-b+0.25)

下半部分d的初值:d2=F(x+0.5,y-1)=b2*(x+0.5)2+a2*(y-1)2-a2*b2

上半部分d的初值和下半部分d的初值各为多少？F(X,Y)=b2X2+a2Y2-a2b2=0

(X,Y)处的法向量:N(X,Y)=2b2Xi+2a2Yj

在上半部分中,法向量的y分量(dF/dY=2a2Y)大

在下半部分中,法向量的x分量(dF/dX=2b2X)大

若在当前中点处，法向量（2b2(Xp+1)，2a2(Yp-0.5))的y分量比x分量大,即：b2(Xp+1)<a2(Yp-0.5),若在下一中点，不等式改变方向，则说明椭圆弧从上部分转入下部分。中点法生成椭圆3.椭圆的上下部分如何区分Midpointellipse(a,b,color)(见P142) inta,b,color; {intx,y;floatd1,d2; x=0;y=b; d1=b*b+a*a*(-b+0.25); while(b*b*(x+1)<a*a*(y-0.5)) {putpixel(x,y,color);

{if(d1<0) d1=d1+b*b*(2*x+3);x=x+1;} else{d1=d1+b*b*(2*x+3)+a*a*(-2*y+2); x=x+1;y=y-1; } }/*区域1*/ d2=sqr(b*(x+0.5))+sqr(a*(y-1))–sqr(a*b); while(y>0) {putpixel(x,y,color);

if(d2<0){d2=d2+b*b*(2*x+2)+a*a*(-2*y+3); x=x+1;y=y-1；} else{d2=d2+a*a*(-2*y+3);y=y-1;} }}中点法生成椭圆如何实现弧和扇形弧的扫描转换?利用圆的方程扇形_圆弧加上两条直线X