計(jì)算機(jī)圖形學(xué)C版4的知識(shí)

第3章光柵掃描圖形學(xué)3.1直線生成算法3.2圓與橢圓的生成算法主要教學(xué)內(nèi)容3.3實(shí)區(qū)域的掃描轉(zhuǎn)換3.4區(qū)域填充3.5圖形反走樣基礎(chǔ)

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,當(dāng)x>0時(shí)

0,當(dāng)x=0時(shí)

-1,當(dāng)x<0時(shí)putpixel(30,50,2);在(30,50)處用2號(hào)色顯示一點(diǎn)。它將像素的亮度存儲(chǔ)到幀緩存的對(duì)應(yīng)位置。簡單DDA算法Int(x)：不大于X的最大整數(shù)P132例:起點(diǎn)(0,0),終點(diǎn)(-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算法應(yīng)用舉例(2)對(duì)稱DDA法:取△t=2-

n,

有:2n-1<=max(|△X|,|△Y|)<2n思考題:用對(duì)稱DDA法來處理上例,請(qǐng)寫出各軌跡點(diǎn)的坐標(biāo)。DDA法比直接使用直線方程的方法快，為什么？——沒有浮點(diǎn)乘法，但仍有浮點(diǎn)數(shù)的加法DDA中取整操作和浮點(diǎn)運(yùn)算仍然十分耗時(shí)。3.1.2Bresenham畫線算法類似簡單DDA法,每次在增量最大方向上均走一步,由e的值決定另一方向是否走步。設(shè)直線的起點(diǎn)(xs,ys),終點(diǎn)(xe,ye),斜率m=△y/△x=(ye-ys)/(xe-xs)

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

0<=m<1的第1象限直線,x方向?yàn)樵隽孔畲蠓较騳i,r是當(dāng)前像素P的縱坐標(biāo),yi+1,r是下一個(gè)像素的縱坐標(biāo)，xi+1=xi+1A是C和D的中點(diǎn),當(dāng)前像素P,下一步在C或D中選擇一個(gè)

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

若e(xi+1)<0,表示B在A之下,下一個(gè)將是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,當(dāng)e(xi+1)>=0時(shí)

=yi+1+m-yi,r-0.5=e(xi+1)+m,當(dāng)e(xi+1)<0時(shí)

即e(xi+1)=e(xi)+m-1,當(dāng)e(xi)>=0時(shí),將選D點(diǎn)(xi+1,yi,r+1)

e(xi)+m,當(dāng)e(xi)<0時(shí),將選C點(diǎn)(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)

當(dāng)e(xi)<0時(shí),(即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象限直線的整數(shù)Bresenham算法為便于硬件實(shí)現(xiàn),需去掉除法運(yùn)算:令f=2*e*△x當(dāng)e(xi)>=0時(shí),(即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)有何關(guān)系？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象限直線)整數(shù)Bresenham畫直線算法算法只用到整數(shù)的加法、減法和乘2（算術(shù)移位）運(yùn)算。是一種轉(zhuǎn)換直線的快速增量算法。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線段,起點(diǎn)A(0,0),終點(diǎn)B(-8,-4),請(qǐng)寫出軌跡點(diǎn)的坐標(biāo)。適合各種象限及各種斜率直線的一般Bresenham算法顯示(0,0),(-1,-1)，(-2,-1)，(-3,-2)，(-4,-2)，(-5,-3)，(-6,-3)，(-7,-4)如何生成指定寬度的直線?（1）最簡單的一種方法是利用“線刷子”.若直線斜率|m|<=1,用垂直方向的線刷子;若直線斜率|m|>1,用水平方向的線刷子.直線段的基本屬性有線型、寬度和顏色。線型包括實(shí)線、虛線、點(diǎn)線等。如何生成不同線型的直線？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的直線段采用“線刷子”的優(yōu)點(diǎn):簡單、容易實(shí)現(xiàn)。例：如何用線刷子生成寬度為3的直線？（3）區(qū)域填充（2）正方形刷子也可以用上述方法生成粗曲線。如生成半徑為16，線寬為4的圓，可生成半徑為14和17的兩個(gè)同心圓，然后填充兩個(gè)圓之間的區(qū)域。

Y

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

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

(0,0)X

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

.(-Y,-X).(Y,-X)在生成封閉的圓周時(shí),只要生成第一象限的1/8圓弧,其余部分可利用對(duì)稱點(diǎn)得到。

圓弧的掃描轉(zhuǎn)換：確定最佳逼近于該圓弧的一組象素；按掃描線順序，對(duì)這些象素進(jìn)行寫操作。方法1:利用圓的方程y2=r2-x2,x從0遞增到r/2,利用方程求出y值,效率很低,用到平方、減法、開平方根。x=r.cos?,y=r.sin?,?從0變化到/4,計(jì)算相應(yīng)的x和y值,但計(jì)算正弦和余弦值花時(shí)間比前一種更多。方法2：利用bersenham畫圓算法、中點(diǎn)法、正負(fù)法、逐點(diǎn)插補(bǔ)法，……..設(shè)圓心在原點(diǎn),半徑為R(順時(shí)針畫圓)。只考慮第1象限的1/8圓周的情況,其余部分可根據(jù)對(duì)稱得出。圓的方程為: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在圓內(nèi)

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

若di>0,Ti離圓近,選Ti(從Pi-1的右下角)

di=0,選兩點(diǎn)均可

di<0,Si離圓周近,選Si(Pi-1的正右方)yx.Pi-1.Ti.Si(0,0)RBA現(xiàn)在從A點(diǎn)開始向右下方逐點(diǎn)來尋找弧AB要顯示的點(diǎn)。如圖中點(diǎn)Pi-1是已選中的一個(gè)表示圓弧上的點(diǎn)，根據(jù)弧AB的走向，下個(gè)點(diǎn)應(yīng)該從Si或者Ti中選擇。顯然應(yīng)選Si和Ti中離AB最近的一點(diǎn)。在起點(diǎn)A(0,R)處,S1(1,R),T1(1,R-1)

d1=1+R2-R2+1+(R-1)2-R2=3-2R在起點(diǎn)處，d1的值是多少呢？如何快速的計(jì)算di？

下面推導(dǎo)di+1與di之間的關(guān)系。

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圓弧。同理可以推導(dǎo)出圓心不在原點(diǎn)的第1象限圓弧的di的遞推公式(di+1與di之間的關(guān)系)。圓方程為:(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對(duì)稱點(diǎn)掃描轉(zhuǎn)換一個(gè)橢圓方法1:根據(jù)橢圓方程x2/a2+y2/b2=1,對(duì)于第1象限內(nèi)0<=x<=1的每個(gè)x值,代入方程求出對(duì)應(yīng)的y值x=a.cos?,y=b.sin?,?從0變化到/2,計(jì)算相應(yīng)的x和y值速度慢方法2:采用中點(diǎn)法橢圓方程:

F(x,y)=b2x2+a2y2-a2b2=0橢圓的對(duì)稱性，只考慮第一象限橢圓弧生成，分上下兩部分，以切線斜率為-1的點(diǎn)作為分界點(diǎn)。(0,0)3.2.2橢圓的生成(中點(diǎn)法)橢圓方程:F(X,Y)=b2X2+a2Y2-a2b2=0

y..

.

b.

..順時(shí)針生成橢圓心在原點(diǎn)的1/4橢圓弧(其余部分由對(duì)稱特性求出)

1.上部分橢圓弧,對(duì)Pi,下一步應(yīng)選取Si和Ti中離橢圓近的那個(gè)

通過判斷兩個(gè)候選點(diǎn)的中點(diǎn)在橢圓內(nèi)還是在橢圓外,來確定選哪個(gè)候選點(diǎn).

.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中任何一個(gè);

若di>0,Mi在橢圓外,Ti離橢圓近,取Ti,(從Pi向右下角走一步);

若di<0,Mi在橢圓內(nèi),Si離橢圓近,取Si,(從Pi向正右方走一步).

在起點(diǎn)P0(0,b)處,有d0=F(X0+1,Y0-0.5)=F(1,b-0.5)=b2+a2(b

-0.5)2-a2b2xa中點(diǎn)法生成橢圓di=F(Mi)=F(Xi+1,Yi-0.5)=b2(Xi+1)2+a2(Yi-0.5)2-a2b2

(1)當(dāng)di<0時(shí),取Si,即Xi+1=

Xi+1,Yi+1=Yi,則下一個(gè)中點(diǎn)為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)當(dāng)di>=0時(shí),取Ti,即Xi+1=

Xi+1,Yi+1=Yi-1

,則下一個(gè)中點(diǎn)為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中任何一個(gè);

若di>0,Mi在橢圓外,Bi離橢圓近,取Bi,(從Pi向正下方走一步);

若di<0,Mi在橢圓內(nèi),Ti離橢圓近,取Ti(從Pi向右下角走一步).

下面推導(dǎo)di的遞推公式:中點(diǎn)法生成橢圓di=F(Mi)=F(Xi+0.5,Yi-1)=b2(Xi+0.5)2+a2(Yi-1)2-a2b2

(1)當(dāng)di<0時(shí),取Ti,即Xi+1=

Xi+1,Yi+1=Yi-1

,則下一個(gè)中點(diǎn)為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)當(dāng)di>=0時(shí),取Bi,即Xi+1=

Xi,Yi+1=Yi-1

,下一個(gè)中點(diǎn)為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)大

若在當(dāng)前中點(diǎn)處，法向量（2b2(Xp+1)，2a2(Yp-0.5))的y分量比x分量大,即：b2(Xp+1)<a2(Yp-0.5),若在下一中點(diǎn)，不等式改變方向，則說明橢圓弧從上部分轉(zhuǎn)入下部分。中點(diǎn)法生成橢圓3.橢圓的上下部分如何區(qū)分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; } }/*區(qū)域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;} }}中點(diǎn)法生成橢圓如何實(shí)現(xiàn)弧和扇形弧的掃描轉(zhuǎn)換?利用圓的方程扇形_圓弧加上兩條直線X