計(jì)算機(jī)圖形學(xué)3-2課件

第3章基本圖形的生成與計(jì)算2.3區(qū)域填充算法2.1直線的生成算法2.2圓的生成算法2.4字符的生成2.5圖形求交2.6圖形裁剪2.1直線的生成算法畫一條從(x1,y1)到(x2,y2)的直線，實(shí)質(zhì)上是一個(gè)發(fā)現(xiàn)最佳逼近直線的像素序列，并填入色彩數(shù)據(jù)的過程。這過程也稱為直線光柵化。連續(xù)性粗細(xì)、亮度要均勻像素逼近待畫直線速度2.1直線的生成算法2.1.1直線DDA算法

(DigitalDifferentialAnalyser)

假設(shè)直線的起點(diǎn)坐標(biāo)為P1(x1,y1)，終點(diǎn)坐標(biāo)為P2(x2,y2)x方向的增量為△x＝x2－x1

；y方向上增量為△y＝y(tǒng)2－y1

直線的斜率為k＝△y／△x

當(dāng)△x＞△y時(shí)，讓x從x1

到x2變化，每步遞增1，那么，x的變化可以表示為xi+1＝xi＋1y的變化可以表示為yi+1＝y(tǒng)i＋k

用上式可求得圖中直線P1P2和y

向網(wǎng)格線的交點(diǎn)，但顯示時(shí)要用舍入找到最靠近交點(diǎn)處的象素點(diǎn)來表示。當(dāng)△x<△y時(shí)，讓y遞增1，x作相應(yīng)變化。

綜合考慮，按照從(x1,y1)到(x2,y2)方向不同，分8個(gè)象限(圖2.1)。對于方向在第1a象限內(nèi)的直線而言，取增量值Dx=1，Dy=m。對于方向在第1b象限內(nèi)的直線而言，取增量值Dy=1，Dx=1/m。2.1直線的生成算法2.1.1直線DDA算法（續(xù)）圖2.1直線方向的8個(gè)象限

象

限dx>dy?

Dx

Dy1atrue1

m1bfalse1/m12atrue-1m2bfalse-1/m13atrue-1-m3bfalse-1/m-14atrue1-m4bfalse1/m-1表2.18個(gè)象限中的坐標(biāo)增量值

研究表中的數(shù)據(jù)，可以發(fā)現(xiàn)兩個(gè)規(guī)律。⒈

當(dāng)dx>dy時(shí)

Dx=1，Dy=m否則

Dx=1/m，Dy=1⒉Dx、Dy的符號與dx、dy的符號相同。

2.1直線的生成算法2.1.1直線DDA算法（續(xù)）

算法描述如下：dda_line(intxa,intya,intxb,intyb,intc){floatdelta_x,delta_y,x,y;intdx,dy,steps,k;dx=xbxa;dy=ybya;if(abs(dx)>abs(dy)) steps=abs(dx);elsesteps=abs(dy);delta_x=(float)dx/(float)steps;delta_y=(float)dy/(float)steps;2.1直線的生成算法2.1.1直線DDA算法（續(xù)）x=xa;y=ya;set_pixel(x,y,c);for(k=1;k<=steps;k++){x+=delta_x;y+=delta_y;set_pixel((int)(x+0.5),y+0.5,c);}}

使用DDA算法，每生成一條直線做兩次除法，畫線中每一點(diǎn)做兩次加法。因此，用DDA法生成直線的速度是相當(dāng)快的。2.1.1直線的掃描轉(zhuǎn)換——中點(diǎn)畫線算法直線方程：F(x,y)=ax+by+c=0P1:(xp+1,yp)P2:(xp+1,yp+1)M:(xp+1,yp+0.5)若M在直線F之上方，則F(x,y)>0若M在直線F之下方，則F(x,y)<0P=(Xp,Yp)P1P2MQ2.1直線的生成算法2.1直線的生成算法令:d=F(M)=F(xp+1,yp+0.5)=a(xp+1)+b(yp+0.5)+cd<0，則M在直線下方(即在Q下方)，故取P2作為下一個(gè)像素點(diǎn)；而若d>0，則取正右方P1；若d=0，二者一樣合適，可任取一個(gè)，這里約定取P1。為了提高d的運(yùn)算效率，可采用增量方式計(jì)算2.1.1直線的掃描轉(zhuǎn)換——中點(diǎn)畫線算法在d≥0時(shí)，取正右方像素點(diǎn)P1，則下一個(gè)中點(diǎn)M坐標(biāo)：M1(xp+2,yp+0.5)，則下一個(gè)像素點(diǎn)的判別式d1=F(xp+2,yp+0.5)=a(xp+2)+b(yp+0.5)+c=d+a故d的增量為a。而若d<0，則取右上方像素點(diǎn)P2,則下一個(gè)中點(diǎn)M坐標(biāo)：M2(xp+2,yp+1.5)，則下一個(gè)像素點(diǎn)的判別式2.1.1直線的掃描轉(zhuǎn)換——中點(diǎn)畫線算法2.1直線的生成算法d2=F(xp+2,yp+1.5)=a(xp+2)+b(yp+1.5)+c=d+a+b故在后一種的情況下d的增量為a+b。d的初值，顯然第一個(gè)像素應(yīng)取左端點(diǎn)(x0,y0),相應(yīng)的判別式為：d0=F(x0+1,y0+0.5)=a(x0+1)+b(y0+0.5)+c=ax0+by0+c+a+0.5b=F(x0,y0)+a+0.5b2.1.1直線的掃描轉(zhuǎn)換——中點(diǎn)畫線算法2.1直線的生成算法因(x0,y0)在直線上，則F(x0,y0)=0即d0=a+0.5b,由于只用到d的符號，為了減少浮點(diǎn)運(yùn)算，可用2d代替d，則初值為:2d0=2a+b。中點(diǎn)畫線算法的C語言實(shí)現(xiàn)voidMidpoint_line(intx0,inty0,intx1,inty1){ inta,b,delta1,delta2,d,x,y; a=y0-y1,b=x0-x1; d=a+a+b;2.1.1直線的掃描轉(zhuǎn)換——中點(diǎn)畫線算法2.1直線的生成算法 delta1=a+a; delta2=(a+b)+(a+b); x=x0,y=y0; SetPixel(x,y); while(x<x1) { if(d<0) { x++;y++;d+=delta2; }

else { x++;d+=delta1; } SetPixel(x,y); }}2.1.1直線的掃描轉(zhuǎn)換——中點(diǎn)畫線算法2.1直線的生成算法上述算法中，只有整數(shù)的加減法運(yùn)算，沒有乘除，所以適合硬件實(shí)現(xiàn)2.1.1直線的掃描轉(zhuǎn)換——中點(diǎn)畫線算法2.1直線的生成算法2.1.1直線的掃描轉(zhuǎn)換——中點(diǎn)畫線算法2.1直線的生成算法2.1直線的生成算法2.1.3直線Bresenham算法

設(shè)直線從起點(diǎn)(x1,y1)到終點(diǎn)(x2,y2)。直線可表示為方程y=mx+b，其中

b=y1-m*x1,m=（y2-y1)/(x2-x1)=dy/dx;

此處的討論先將直線方向限于1a象限(圖2.2)，在這種情況下，當(dāng)直線光柵化時(shí)，x每次都增加1個(gè)單元，即xi+1=xi

+1而y的相應(yīng)增加值應(yīng)當(dāng)小于1。為了光柵化，yi+1只可能選擇圖2.2中兩種位置之一。圖2.2縱坐標(biāo)的位置選擇

2.1直線的生成算法2.1.3直線Bresenham算法(續(xù)）

yi+1的位置選擇yi+1=yi或者yi+1=yi+1，選擇的原則是看精確值y與yi及yi+1的距離d1及d2的大小而定。計(jì)算公式為

y=m(xi

+1)+b(2.1)

d1=y

yi(2.2)

d2=yi+1

y

(2.3)如果d1d2>0，則yi+1=yi+1，否則yi+1=yi。將式(2.1)、(2.2)、(2.3)代入d1d2，再用dx乘等式兩邊，并以Pi=(d1d2)dx代入上述等式，得

Pi=2xidy2yidx+2dy+(2b1)dx(2.4)d1d2是用以判斷符號的誤差。由于在1a象限，dx總大于0，所以Pi仍舊可以用作判斷符號的誤差。Pi+1為

Pi+1=Pi+2dy2(yi+1yi)dx

(2.5)2.1直線的生成算法2.1.3直線Bresenham算法(續(xù)）

求誤差的初值P1，可將x1、y1和b代入式(2.4)中的xi、yi而得到

P1=2dydx

綜述上面的推導(dǎo)，第1a象限內(nèi)的直線Bresenham算法思想如下：⒈

畫點(diǎn)(x1,y1)，dx=x2x1，dy=y2y1，計(jì)算誤差初值P1=2dy

dx，i=1；⒉

求直線的下一點(diǎn)位置xi+1=xi+1

如果Pi>0，則yi+1=yi+1，否則yi+1=yi；⒊

畫點(diǎn)(xi+1,yi+1)；⒋

求下一個(gè)誤差Pi+1，如果Pi>0，則Pi+1=Pi+2dy2dx，否則

Pi+1=Pi+2dy；⒌

i=i+1；如果i<dx+1則轉(zhuǎn)步驟2；否則結(jié)束操作。VoidLineBre(PDC*pDC,intx0,inty0,intxend,intyend){ intdx=xend-x0; intdy=yend-y0; intp=2*dy-dx; intx,y;x=x0; y=y0; pDC->SetPixel(x,y,c); while(x<xend) { x++; if(p<0) { p=p+2*dy; } else { p=p+2*dy-2*dx; y++; } pDC->SetPixel(x,y,c); }}根據(jù)Bresenham畫線算法，直線端點(diǎn)為(20,10)和（30,18)，請?zhí)顚懴铝斜砀駭?shù)據(jù)。解：根據(jù)Bresenham畫線算法，直線端點(diǎn)為(20,10)和（30,18)Dx＝10，Dy＝8，

k=Dy/Dx=0.8，2Dy＝16，2Dy－2Dx＝－4P0

＝2Dy－Dx＝6畫初始點(diǎn)(20,10),并根據(jù)判別式確定沿線段路徑的后續(xù)像素位置如下表：2.1直線的生成算法2.1.3直線Bresenham算法(續(xù)）

Bresenham算法的優(yōu)點(diǎn)如下：⒈

不必計(jì)算直線的斜率，因此不做除法。⒉

不用浮點(diǎn)數(shù)，只用整數(shù)。⒊

只做整數(shù)加減運(yùn)算和乘2運(yùn)算，而乘2運(yùn)算可以用移位操作實(shí)現(xiàn)。Bresenham算法的運(yùn)算速度很快，并適于用硬件實(shí)現(xiàn)。討論：以上討論的是0＜△y＜△x的情況，對于適用所有8個(gè)方向的直線(圖2.1)的生成算法，則要考慮以判斷條件|dx|>|dy|為分支，并分別將2a、3a象限的直線和3b、4b象限的直線變換到1a、4a和2b、1b象限方向去，以實(shí)現(xiàn)程序處理的簡潔。作業(yè)，編寫程序，比較DDA畫線算法與Bresenhan畫線速度2.2圓的生成算法2.2.1基礎(chǔ)知識

給出圓心坐標(biāo)(xc,yc)和半徑r，逐點(diǎn)畫出一個(gè)圓周的公式有下列兩種：⒈

直角坐標(biāo)法

(xxc)2+(yyc)2=r2由上式導(dǎo)出：

當(dāng)xxc從r到r作加1遞增時(shí)，就可以求出對應(yīng)的圓周點(diǎn)的y坐標(biāo)。但這并非是生成圓的最好方法。這個(gè)方法的一個(gè)問題是每一步包含很大的計(jì)算量。而且，如圖所示，所畫像素位置間的間距是不一致的。我們可以在圓斜率的絕對值大于1后，交換x和y(即步進(jìn)y值并計(jì)算x值)來調(diào)整間距。但是，這種方法增加了算法所需的計(jì)算量和處理過程。2.2圓的生成算法2.2圓的生成算法2.2.1基礎(chǔ)知識(續(xù)）

⒉

極坐標(biāo)法x=xc+r·cosθ，y=yc+r

·sinθ使用上述方法以固定角度為步長生成顯示結(jié)果時(shí)，就可以利用沿圓周的等距點(diǎn)來繪制出圓。為了減少計(jì)算量，我們可以在相鄰點(diǎn)間使用較大的角度間隔并用線段連接相鄰點(diǎn)來逼近圓的路徑。在光柵顯示中設(shè)定角度間隔為1/r可獲得較連續(xù)的邊界。這樣繪出的像素位置大約間隔一個(gè)單位。盡管極坐標(biāo)系統(tǒng)提供了等距點(diǎn)，但三角函數(shù)計(jì)算是十分耗時(shí)的。

2.2圓的生成算法利用圓周坐標(biāo)的對稱性，此算法還可以簡化。將圓周分為8個(gè)象限，只要將第1a象限中的圓周光柵點(diǎn)求出，其余7部分圓周就可以通過對稱法則計(jì)算出來。

中點(diǎn)畫圓法

由于圓的對稱性，下面主要考慮中心在原點(diǎn)半徑為r的圓的第二8分圓。若從圓的正上方開始討論如何確定最佳逼近于該圓弧的像素序列。P=(x,y)P1P2M

假定當(dāng)前已確定了圓弧上的一個(gè)像素點(diǎn)為P(xp,yp)，那么，下一個(gè)像素只能是正右方的P1(xp+1,yp)或右下方的P2(xp+1,yp–1)兩者之一。如圖所示

那么，當(dāng)F(M)>0時(shí)，M在圓外，這說明P2距離圓弧更近，應(yīng)取P2作為下一像素。而當(dāng)F(M)<0時(shí)，P1離圓弧更近，應(yīng)取P1。當(dāng)F(M)=0時(shí)，在P1與P2之中隨便取一個(gè)即可，約定取P2。

對于圓上的點(diǎn)，F(xiàn)(x,y)=0；對于圓外的點(diǎn)，F(xiàn)(x,y)>0；而對于圓內(nèi)的點(diǎn)，F(xiàn)(x,y)<0。與中點(diǎn)畫線法類似，設(shè)M是P1和P2的中點(diǎn)，即M=(xp+1，yp–0.5)。

構(gòu)造函數(shù)：

F(x,y)=x2＋y2–r2(3–5)P=(x,y)P1P2M

若d＜0，則應(yīng)取P1為下一像素，而且再下一個(gè)像素的判別式為

d=F(xp

+2，yp–0.5)=(xp+2)2+(yp

–0.5)2–R2

=d+2xp+3所以，沿正右方向，d的增量為2xp+3。

與中點(diǎn)畫線法一樣，構(gòu)造判別式

d=F(M)=F(xp+1，yp–0.5)=(xp+1)2+(yp–0.5)2–R2

而若d≥0，則P2是下一像素，而且下一像素的判別式為

d'=F(xp+2,yp–1.5)=(xp+2)2

+(yp

–1.5)2–R2=d+(2xp

+3)+(–2yp

+2)所以,沿右下方向,判別式d的增量為2(xp–yp)+5。

初始時(shí)，

x0=0，

y0=R，

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

但這個(gè)算法中仍然有浮點(diǎn)數(shù)運(yùn)算。令f=d-0.25，那么初始時(shí)，x0=0，y0=R，f0=d0-0.25=1-R。假設(shè)已知當(dāng)前列像素位置(xi,yi)和判別式fi，則有：中點(diǎn)畫圓算法

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為整數(shù)，每次迭代f的變化量也是整數(shù)，即f保持為整數(shù)，因此f<-0.25等價(jià)于f<0。

以下是中點(diǎn)畫圓算法的C語言描述：voidMidpointCircle(intxc,intyc,intr,intcolor){intx=0,y=r,d=1–r；

WholeCircle（xc，yc，x，y，color）；

while（x<=y）

{if（d＜0）

{d+=2*x+3；x++；}else{d+=2*（x–y）+5；x++;y––；}WholeCircle（xc，yc，x，y，color）；

}}voidWholeCircle(intxc,intyc,intx,inty,intcolor){CDC*pDC=GetDC（）；

pDC->Setpixel(xc+x，yc+y，color)；

pDC->Setpixel(xc–x，yc+y，color)；

pDC->Setpixel(xc+x，yc–y，color)；

pDC->Setpixel(xc–x，yc–y，color)；

pDC->Setpixel(xc+y，yc+x，color)；

pDC->Setpixel(xc–y，yc+x，color)；

pDC->Setpixel(xc+y，yc–x，color)；

pDC->Setpixel(xc–y，yc–x，color)；ReleaseDC(pDC);}3.2.3Bresenham畫圓算法

考慮圓心在原點(diǎn)，半徑為r的第一個(gè)8分圓。取(0,r)為起點(diǎn)，按順時(shí)針方向生成圓。如圖3.6所示。從這段圓弧的任意一點(diǎn)出發(fā)，按順時(shí)針方向生成圓時(shí)。在這種情況下，x每步增加1，即：yxyiyi-1xixi+1yxi+1=xi+1則相應(yīng)的y有二種選擇：

yi+1=yi

或yi+1=yi-1Bresenham畫圓算法采用一個(gè)決策值來確定到底是選擇yi還是yi-1。在x=xi+1位置上，用d1和d2來標(biāo)識兩個(gè)候選像素的y值與圓弧上理想y值的差值，則：y2=r2-(xi+1)2d1=yi2-y2=yi2-r2+(xi+1)2d2=y2-(yi-1)2=r2-(xi+1)2-(yi-1)2

令di=d1-d2，并代入d1、d2，則有：（方差最?。?/p>

di=2(xi+1)2+yi2+(yi-1)2-2r2這里di就是Bresenham畫圓算法的第i步?jīng)Q策值。如果di<0，則yi+1=yi，否則yi+1=yi-1。若di=0，則可任選一個(gè)，我們約定yi+1=yi-1。

下面來推導(dǎo)di的遞推公式。在i+1步，di+1為：

di+1=2(xi+1+1)2+yi+12+(yi+1-1)2-2r2

若di<0，取右方像素，yi+1=yi，則：

di+1=2(xi+1+1)2+yi2+(yi-1)2-2r2=di+4xi+6而決策值的初值d0由x=0,y=r代入前面公式，得：

d0=2(0+1)2+r2+(r-1)2-2r2=3-2r已知xi+1=xi+1，因而得到：

di+1=2(xi+1+1)2+yi+12+(yi+1-1)2-2r2

若di>=0，取右下方像素，yi+1=yi-1，則：di+1=2(xi+1+1)2+(yi-1)2+(yi-1-1)2-2r2=di+4(xi-yi)+10

由此，可寫出Bresenham畫圓算法的C程序：

2.2圓的生成算法2.2.2圓的Bresenham算法(續(xù)）

根據(jù)上面的推導(dǎo)，圓周生成算法思想如下：⒈求誤差初值，p1=32r，i=1，畫點(diǎn)(0,r)；⒉求下一個(gè)光柵位置，其中xi+1=xi+1，如果pi<0則yi+1=yi，否則yi+1=yi1；⒊畫點(diǎn)(xi+1,yi+1)；⒋計(jì)算下一個(gè)誤差，如果pi<0則pi+1=pi+4xi+6，否則pi+1=pi+4(xiyi)+10；⒌i=i+1，如果x=y則結(jié)束，否則返回步驟2。2.2圓的生成算法2.2.2圓的Bresenham算法(續(xù)）

圓的Bresenham算法的程序?qū)崿F(xiàn)如下：

circle(CDC*pDC,intxc,intyc,intradius,intc)

{

intx,y,p;

x=0;

y=radius;

p=32*radius；

while(x<y) {

plot_circle_points(pDc,xc,yc,x,y,c);

if(p<0)p=p+4*x+6;

else {

p=p+4*(xy)+10;

y=1;

}

x+=1;

}

if(x==y)

plot_circle_points(pDC,xc,yc,x,y,c);

}

2.2圓的生成算法2.2.2圓的Bresenham算法(續(xù)）plot_circle_points(intxc,intyc,intx,inty,intc){pDC->SetPixel(xc+x,yc+y,c);pDC->SetPixel(xcx,yc+y,c);pDC->SetPixel(xc+x,ycy,c);pDC->SetPixel(xcx,ycy,c);pDC->SetPixel(xc+y,yc+x,c);pDC->SetPixelxcy,yc+x,c);pDC->SetPixel(xc+y,ycx,c);pDC->SetPixel(xcy,ycx,c);}2.3區(qū)域填充算法2.3.1基礎(chǔ)知識

區(qū)域填充即給出一個(gè)區(qū)域的邊界，要求對邊界范圍內(nèi)的所有像素單元賦予指定的顏色代碼。區(qū)域填充中最常用的是多邊形填色。

多邊形的表示方法頂點(diǎn)表示點(diǎn)陣表示圖2.5掃描線與多邊形相交

圖2.6光柵化后直線變成離散點(diǎn)

多邊形填色一個(gè)首要的問題，是判斷一個(gè)像素是在多邊形內(nèi)還是多邊形外。數(shù)學(xué)上提供的方法是“掃描交點(diǎn)的奇偶數(shù)判斷法”。

2.3區(qū)域填充算法2.3.1基礎(chǔ)知識(續(xù)）

2.3區(qū)域填充算法2.3.1基礎(chǔ)知識(續(xù)）

填色算法分為兩大類：⒈

掃描線填色(Scan-LineFilling)算法。這類算法建立在多邊形邊界的矢量形式數(shù)據(jù)之上，可用于程序填色，也可用于交互填色。⒉

種子填色(SeedFilling)算法。這類算法建立在多邊形邊界的圖像形式數(shù)據(jù)之上，并還需提供多邊形邊界內(nèi)一點(diǎn)的坐標(biāo)。所以，它一般只能用于人機(jī)交互填色（給出種子點(diǎn)），而難以用于全自動程序填色。2.3區(qū)域填充算法2.3.2掃描線填色算法

算法的基本思想。多邊形以n、x_array、y_array的形式給出，其中，x_array、y_array中存放著多邊形的n個(gè)頂點(diǎn)的x，y坐標(biāo)。用水平掃描線從上到下掃描由點(diǎn)線段構(gòu)成的多段定義成的多邊形。每根掃描線與多邊形各邊產(chǎn)生一系列交點(diǎn)。這些交點(diǎn)按照x坐標(biāo)進(jìn)行分類，將分類后的交點(diǎn)成對取出，作為兩個(gè)端點(diǎn)，以所需要填的色彩畫水平直線。多邊形被掃描完畢后，填色也就完成。例：對右圖的多邊形進(jìn)行填充思路：算出交點(diǎn)；劃分區(qū)間；分配顏色步驟：對每條掃描線分為4步(以掃描線6為例)991234568710001876453211求交點(diǎn)，即計(jì)算該掃描線與多邊形各邊的交點(diǎn)排序，由于交點(diǎn)不一定由左到右求出，因此將求出的交點(diǎn)按x坐標(biāo)值排序交點(diǎn)配對，1與2，3與4，…

…，每對表示一個(gè)區(qū)間區(qū)間填充991234568710001876453211ABCDP1P2P3P4P5P6掃描線2的交點(diǎn)按X排序：2，2，8掃描線7的交點(diǎn)按X排序：2，2，9，11問題：1.掃描線與頂點(diǎn)相交時(shí)，交點(diǎn)的取舍2.邊界像素的取舍991234568710001876453211ABCDP1P2P3P4P5P6991234568710001876453211ABCDP1P2P3P4P5P60次0次2次1次具體方法1：檢查共享該頂點(diǎn)的兩條邊另外兩個(gè)頂點(diǎn)的Y值，按這兩個(gè)Y值中大于共享該頂點(diǎn)Y值的個(gè)數(shù)是0、1、2來決定是取0、1、2個(gè)交點(diǎn)。2.3區(qū)域填充算法2.3.2掃描線填色算法(續(xù)）

上述基本思想中，有幾個(gè)問題需要解決或改進(jìn)：⒈

左、右頂點(diǎn)處理。當(dāng)以1、2、3的次序畫多邊形外框時(shí)，多邊形的左頂點(diǎn)和右頂點(diǎn)如圖2.7中所示的頂點(diǎn)2。它們具有以下性質(zhì)。左頂點(diǎn)2：y1<y2<y3右頂點(diǎn)2：y1>y2>y3

其中y1、y2、y3是3個(gè)相鄰的頂點(diǎn)的y坐標(biāo)。圖2.7多邊形的頂點(diǎn)

當(dāng)掃描線與多邊形的每個(gè)頂點(diǎn)相交時(shí)，會同時(shí)產(chǎn)生2個(gè)交點(diǎn)。這時(shí)，填色就會因掃描交點(diǎn)的奇偶計(jì)數(shù)出錯(cuò)而出現(xiàn)錯(cuò)誤。因此，對所有左、右頂點(diǎn)作如下處理：2.3區(qū)域填充算法2.3.2掃描線填色算法(續(xù)）

左、右頂點(diǎn)的入邊(以該頂點(diǎn)為終點(diǎn)的那條邊，即1–2邊)之終點(diǎn)刪去。對于左頂點(diǎn)，入邊端點(diǎn)(x1,y1)、(x2,y2)修改為(x1,y1)、(

,y21)；對于右頂點(diǎn)，入邊端點(diǎn)(x1,y1)、(x2,y2)修改為(x1,y1)、(

,y2+1)；其中，，即入邊的斜率。對于多邊形的上頂點(diǎn)(y2>y1、y2>y3)或下頂點(diǎn)(y2<y1、y2<y3)，奇偶計(jì)數(shù)保持正確。

⒉

水平邊處理。水平邊(y1=y2)與水平掃描線重合無法求交點(diǎn)。因此，將水平邊畫出后刪去，不參加求交點(diǎn)及求交點(diǎn)以后的操作。

2.3區(qū)域填充算法2.3.2掃描線填色算法(續(xù)）

⒊

掃描線與邊的求交點(diǎn)方法采用遞歸算法。以(x1,y1)、(x2,y2)為端點(diǎn)的邊與第i+1條掃描線的交點(diǎn)為此式表示交點(diǎn)不為(x1,y1)。否則，交點(diǎn)為(x1,y1)。⒋

減少求交計(jì)算量，采用活性邊表。對于一根掃描線而言，與之相交的邊只占多邊形全部邊的一部分,每根掃描線與多邊形所有邊求交的操作是一種浪費(fèi)，需要加以改進(jìn)。

活性邊表(ActiveListofSide)的采用將多邊形的邊分成兩個(gè)子集：與當(dāng)前掃描線相交的邊的集合，以及與當(dāng)前掃描線不相交的邊的集合。對后者不必進(jìn)行求交運(yùn)算，這樣就提高了算法的效率。2.3區(qū)域填充算法2.3.2掃描線填色算法(續(xù)）

圖2.8活性邊表及其指針的表示

掃描線填充算法是一種非常有效的算法，它對于每個(gè)象素只訪問一次，其缺點(diǎn)是對于各種表的維持和排序的耗費(fèi)大?；钚赃叡淼臉?gòu)成方法是：1）將經(jīng)過左、右頂點(diǎn)處理及剔除水平邊后的多邊形之各邊按照maxy值排序，存入一個(gè)線性表中。表中每一個(gè)元素代表一根邊。第一個(gè)元素是maxy值最大的邊，最后一個(gè)元素是maxy值最小的邊。圖2.3.4(a)中的多邊形所形成的線性表如（b）所示。其中F點(diǎn)和B點(diǎn)的y值相等，且為全部多邊形的maxy的最大值。因此FG,FE,AB,BC等四邊排在表之首。而C點(diǎn)的y值>E點(diǎn)的y值，所以CH排在DE前面，余類推。在maxy值相等的邊之間，按任意次序排列。 2)在上述線性表上加入兩個(gè)指針first和last，即形成活性邊表。這兩個(gè)指針之間是與當(dāng)前掃描線相交的邊的集合和已經(jīng)處理完（即掃描完）的邊的集合。這兩者的區(qū)分方法是在處理完的邊上加上記號：△

y=0。在last指針以后的是尚未與當(dāng)前掃描線相交的，在first指針以前的是已經(jīng)處理完了的邊。對于圖2.3.4(a)中掃描線scan1的情況下，圖2.3.4(b)中列出first,last的位置。如果掃描線由上而下移到了scan2的位置，則活性邊表的first應(yīng)指向AB，last應(yīng)指向CH。每根掃描線只須與位于first,last之間的，而且△

y不為0的邊求交即可。這就縮小了求交的范圍。3）活性邊表中每個(gè)元素的內(nèi)容包括：邊的maxy值，記為y_top；與當(dāng)前掃描線相交點(diǎn)的x坐標(biāo)值，記為x_int；邊的y方向當(dāng)前總長。初始值為y2-y1。記為△

y；邊的斜率倒數(shù)：x2-x1/y2-y1

，記為x_change_per_scan。typedefstruct{inty_top;//邊的最大Y值

floatx_int;//與掃描線相交點(diǎn)的X坐標(biāo)

intdelta_y;//直線在Y方向上的總長

floatx_change_per_scan;//直線斜率倒數(shù)}EACH_ENTRY;4）活性邊在每根掃描線掃描之后刷新。刷新的內(nèi)容有2項(xiàng)：調(diào)整first和last指針字間的參加求交的邊元素之值：△

y=△y-1;x_int=x_int-x_change_per_scan;調(diào)整first和last指針，以便讓新邊進(jìn)入激活范圍，處理完的邊退出激活范圍：當(dāng)first所指邊的△

y=0時(shí)，first=first+1；當(dāng)last所指的下一條邊的y_top?下一掃描線的y值時(shí)，last=last+1。二、掃描線填色程序 程序2.3.1示出掃描線填色算法的程序。主程序名為fill_area(count,x,y)，其中參數(shù)x,y是兩個(gè)一維數(shù)組，存放多邊形頂點(diǎn)（共count個(gè)）的x和y坐標(biāo)。它調(diào)用8個(gè)子程序，彼此的調(diào)用關(guān)系如圖2.3.5所示。各子程序的功能為：1、sort_on_bigger_y子程序的主要功能是按照輸入的多邊形，建立起活性邊表。操作步驟是：對每條邊加以判斷：如非水平邊則調(diào)用put_in_side_list子程序放入活性邊來；如是水平邊則直接畫出。2、put_in_sides_list子程序的主要功能是將一條邊存入活性邊表之內(nèi)。操作步驟是：對該邊判別是否左頂點(diǎn)或右頂點(diǎn)，如果將入邊之終點(diǎn)刪去，按照y_top的大小在活性邊表中找到該點(diǎn)的合適位置，在該邊的位置中填入數(shù)據(jù)。3、update_first_and_last子程序的主要功能是刷新活性邊表的first和last兩根指針的所指位置，以保證指針指出激活邊的范圍。4、process_x_intersections子程序的主要功能是對活性邊表中的激活邊（即位于first和last之間的，并且?y?0的邊）按照x_int的大小排序。操作步驟是：從first到last，對每一根?y?0的邊，調(diào)用sort_on_x子程序排入活性邊表中合適位置。5、sort_on_x子程序主要功能是將一條邊side[entry]，在活性邊表的first到entry之間按x_int的大小插入合適位置。操作步驟是：檢查位于entry的邊的x_int是否小于位置entry-1的邊的x_int，如是，調(diào)用swap子程序交換兩條邊的彼此位置。6、swap子程序的主要功能是交換活性邊表中兩條相鄰位置邊的彼此位置。7、draw_lines子程序的主要功能是在一條掃描線位于多邊形內(nèi)的部分，填上指定的色彩。操作步驟是：在活性邊表的激活邊范圍內(nèi)，依次取出Δy10兩邊的x_int，作為兩個(gè)端點(diǎn)（x1,scan），(x2,scan)，畫一條水平線。8、update_sides_list子程序的主要功能是刷新活性邊表內(nèi)激活邊的值：Δy=Dy-1

x_int=x_int_x_chang_per_scan；2.3區(qū)域填充——邊填充算法

1.簡單的邊填充算法每邊與掃描線交點(diǎn)右方的所有像素取“補(bǔ)”,多邊形邊的順序可任意取P1P2P3P4P5P2P3P3P4P4P5P5P12.3區(qū)域填充——邊填充算法

1.簡單的邊填充算法特點(diǎn)：方法簡單每一個(gè)像素被訪問多次，輸入/輸出工作量大2.3區(qū)域填充——邊填充算法

2.柵欄填充算法柵欄：與掃描線垂直的直線，通常過多邊形頂點(diǎn)，且將多邊形分成兩半方法：對每個(gè)掃描線與多邊形的交點(diǎn)，將交點(diǎn)與柵欄間的像素取“補(bǔ)”特點(diǎn)：方法簡單減少了被重復(fù)訪問的像素，特別是有多個(gè)填充對象時(shí)，效果顯著2.3區(qū)域填充——邊填充算法

2.柵欄填充算法P4P5P5P1P1P2P3P4P5P2P3P3P42.3區(qū)域填充——邊填充算法

3.邊標(biāo)志算法基本思想：幀緩沖器中對多邊形的每條邊進(jìn)行直線掃描轉(zhuǎn)換，亦即對多邊形邊界所經(jīng)過的象素打上標(biāo)志。然后再采用和掃描線算法類似的方法將位于多邊形內(nèi)的各個(gè)區(qū)段著上所需顏色。使用一個(gè)布爾量inside來指示當(dāng)前點(diǎn)是否在多邊形內(nèi)的狀態(tài)。2.3區(qū)域填充——邊填充算法

3.邊標(biāo)志算法9912345687100018764532119912345687100018764532112.3區(qū)域填充——邊填充算法

3.邊標(biāo)志算法(算法過程)voidedgemark_fill(polydef,color)多邊形定義polydef；intcolor;{對多邊形polydef每條邊進(jìn)行直線掃描轉(zhuǎn)換；

inside=FALSE;for(每條與多邊形polydef相交的掃描線y)for(掃描線上每個(gè)象素x){if(象素x被打上邊標(biāo)志)inside=!(inside);if(inside！=FALSE)drawpixel(x,y,color);elsedrawpixel(x,y,background); }}2.3區(qū)域填充——邊填充算法

3.邊標(biāo)志算法(算法過程)用軟件實(shí)現(xiàn)時(shí)，掃描線算法與邊界標(biāo)志算法的執(zhí)行速度幾乎相同，但由于邊界標(biāo)志算法不必建立維護(hù)邊表以及對它進(jìn)行排序，所以邊界標(biāo)志算法更適合硬件實(shí)現(xiàn)，這時(shí)它的執(zhí)行速度比有序邊表算法快一至兩個(gè)數(shù)量級。2.4區(qū)域填充——種子填充算法基本原理：假設(shè)在多邊形區(qū)域內(nèi)部有一象素已知，由此出發(fā)找到區(qū)域內(nèi)的所有象素四連通區(qū)域和八連通區(qū)域四連通方向八連通方向種子可以從四個(gè)方向?qū)ふ蚁乱幌袼?，稱為四向算法；允許從八個(gè)方向?qū)ふ蚁乱幌袼?，稱為八向算法。八向算法可以填充八連通區(qū)域和四連通區(qū)域，而四向算法只能填充四連通區(qū)域2.4區(qū)域填充——種子填充算法四連通區(qū)域和八連通區(qū)域991234568710001876453211四連通區(qū)域八連通區(qū)域9912345687100018764532112.4區(qū)域填充——種子填充算法

1.簡單的種子填充算法1.初始化：種子像素入棧，當(dāng)棧非空時(shí)，重復(fù)2～

4的步驟2.棧頂像素出棧3.將出棧像素置為多邊形顏色4.按左、上、右、下順序依次檢查與出棧像素相鄰的四個(gè)像素，若其中某個(gè)像素不在邊界上且未置成多邊形色，則該像素入棧5.當(dāng)堆棧為空時(shí)，算法終止2.4區(qū)域填充——種子填充算法

1.簡單的種子填充算法01234543210S1(2,3)(2,2)(3,3)(2,4)(1,3)(2,2)(3,3)(2,4)(1,2)(1,4)(2,2)(3,3)(2,4)(1,2)(2,4)(2,2)(3,3)(2,4)(1,2)(2,2)(3,3)(2,4)(2,2)(2,2)(3,3)(2,4)(2,1)(3,2)(2,2)(3,3)(2,4)(2,1)(3,3)(2,2)(3,3)(2,4)(2,1)2.4區(qū)域填充——種子填充算法

1.簡單的種子填充算法voidBoundaryFill4(intx,inty,intboundarycolor,intfillcolor){intcurrentcolor; currentcolor=getpoxel(x,y); if(currentcolor!=fillcolor&¤tcolor!=boundarycolor) { setcolor(fillcolor);setpixel(x,y); BoundaryFill4(x,y+1,boundarycolor,newcolor); BoundaryFill4(x,y-1,boundarycolor,newcolor); BoundaryFill4(x-1,y,boundarycolor,newcolor); BoundaryFill4(x+1,y,boundarycolor,newcolor);}}2.4區(qū)域填充——種子填充算法

1.簡單的種子填充算法特點(diǎn)：算法簡單，可以用于填充帶有內(nèi)孔的區(qū)域像素可能重復(fù)入棧，降低了算法效率存儲空間開銷較大2.4區(qū)域填充——種子填充算法

2.掃描線種子填充算法基本思想：首先填充種子點(diǎn)所在掃描線上的位于給定區(qū)域的一個(gè)區(qū)段然后確定與這一區(qū)段相連通的上、下兩條掃描線上位于給定區(qū)域內(nèi)的區(qū)段，并依次保存下來。反復(fù)這個(gè)過程，直到填充結(jié)束。2.4區(qū)域填充——種子填充算法

2.掃描線種子填充算法算法步驟：(1)初始化：堆棧置空。將種子點(diǎn)（x，y）入棧。(2)出棧：若?？談t結(jié)束。否則取棧頂元素（x，y），以y作為當(dāng)前掃描線。(3)填充并確定種子點(diǎn)所在區(qū)段：從種子點(diǎn)（x，y）出發(fā)，沿當(dāng)前掃描線向左、右兩個(gè)方向填充，直到邊界。分別標(biāo)記區(qū)段的左、右端點(diǎn)坐標(biāo)為xl和xr。2.4區(qū)域填充——種子填充算法

2.掃描線種子填充算法(4)并確定新的種子點(diǎn)：在區(qū)間[xl，xr]中檢查與當(dāng)前掃描線y上、下相鄰的兩條掃描線上的象素。若存在非邊界、未填充的象素，則把每一區(qū)間的最右象素作為種子點(diǎn)壓入堆棧。(5)重復(fù)(2)～(4)步。上述算法對于每一個(gè)待填充區(qū)段，只需壓棧一次；因此，掃描線填充算法提高了區(qū)域填充的效率。2.4區(qū)域填充——種子填充算法

2.掃描線種子填充算法sxLxR0123456789101112111098765432108,67,109,96,119,95,119,94,119,93,113,45,49,92,113,45,49,93,45,49,92,45,49,95,49,96,49,97,49,99,92.4區(qū)域填充——種子填充算法

2.掃描線種子填充算法(C語言程序)typedefstruct{//記錄種子點(diǎn)

intx; inty;}Seed;voidScanLineFill(intx,inty,intoldcolor,intnewcolor){intxl,xr,i;boolspanNeedFill;Seedpt;setstackempty();//清空堆棧pt.x=x;pt.y=y;stackpush(pt);//將前面生成的區(qū)段壓入堆棧

2.4區(qū)域填充——種子填充算法

2.掃描線種子填充算法(C語言程序)while(!isstackempty()){ pt=stackpop(); y=pt.y; x=pt.x; while(getpixel(x,y)==oldcolor)//向右填充

{ drawpixel(x,y,newcolor); x++; } xr=x-1; x=pt.x-1; while(getpixel(x,y)==oldcolor)//向左填充

{ drawpixel(x,y,newcolor); x--; }2.4區(qū)域填充——種子填充算法

2.掃描線種子填充算法(C語言程序)

xl=x+1; //處理上面一條掃描線

x=xl; y=y+1; while(x<xr) { spanNeedFill=FALSE; while(getpixel(x,y)==oldcolor) { spanNeedFill=TRUE; x++; } if(spanNeedFill) { pt.x=x-1;pt.y=y; stackpush(pt); spanNeedFill=FALSE; }2.4區(qū)域填充——種子填充算法

2.掃描線種子填充算法(C語言程序)

while(getpixel(x,y)!=oldcolor&&x<xr) x++; }//Endofwhile(i<xr) //處理下面一條掃描線，代碼與處理上面一 //條掃描線類似

x=xl; y=y-2; while(x<xr) { spanNeedFill=FALSE; while(getpixel(x,y)==oldcolor) { spanNeedFill=TRUE; x++; }2.4區(qū)域填充——種子填充算法

2.掃描線種子填充算法(C語言程序)

x++; } if(spanNeedFill) { pt.x=x-1;pt.y=y; stackpush(pt); spanNeedFill=FALSE; } while(getpixel(x,y)!=oldcolor&&x<xr) x++; }//Endofwhile(i<xr)}//Endofwhile(!isstackempty())}2.4區(qū)域填充——圓域的填充算法基本思想：將多邊形區(qū)域的掃描線算法，推廣到圓域的填充。先計(jì)算每條掃描線與圓域的相交區(qū)間；和圓交點(diǎn)的計(jì)算可以改造中點(diǎn)畫圓法來進(jìn)行。再把區(qū)間用指定顏色填充。對于同時(shí)對多個(gè)圓填充時(shí)，可以采用類似活性邊表的方式，即活性圓表法。2.4區(qū)域填充——區(qū)域的圖案填充圖案：一般是用一個(gè)M×N的位圖來表示2.4區(qū)域填充——區(qū)域的圖案填充圖案與區(qū)域的相對位置關(guān)系：(1)圖案與區(qū)域邊界或內(nèi)部對齊(2)圖案與區(qū)域外部對齊設(shè)對齊點(diǎn)為(x0,y0)，則圖案填充：if(pattern((x-x0)%M,(y-y0)%N) drawpixel(x,y,color);else drawpixel(x,y,background);2.4字符的生成2.4.1點(diǎn)陣式字符

點(diǎn)陣式字符將字符形狀表示為一個(gè)矩形點(diǎn)陣，由點(diǎn)陣中點(diǎn)的不同值表達(dá)字符的形狀。

使用點(diǎn)陣式字符時(shí)，需將字庫中的矩形點(diǎn)陣復(fù)制到緩沖器中指定的單元中去。在復(fù)制過程中，可以施加變換，以獲得簡單的變化。圖2.11(b)~(d)列出了以字母P為原型的一些變化例子。圖2.11點(diǎn)陣式字符及其變化

圖（b）變成粗體字。算法是：當(dāng)字符原型中每個(gè)象素被寫入幀緩存寄存器的指定位置xi,yi時(shí)，同時(shí)被寫入xi+1,yi。圖（c）旋轉(zhuǎn)900

。算法是：把字符原型中每個(gè)象素的x,y坐標(biāo)彼此交換，并使y值改變符號后，再寫入幀緩存寄存器的指定位置。圖（d）斜體字。算法是：從底到頂逐行拷貝字符，每隔n行，左移一單元。 此外，還可以對點(diǎn)陣式字符作比例縮放等其他一些簡單的變換。但是對點(diǎn)陣式字符作任意角度的旋轉(zhuǎn)等變換，是比較困難的操作。 由于光柵掃描顯示器的普遍使用，點(diǎn)陣式字符表示已經(jīng)成為一種字符表示的主要形式。從字庫中讀出原字型，經(jīng)過變換拷貝到buffer中去的操作，經(jīng)常制成專門的硬件來完成。這就大大加快了字符生成的速度。2.4字符的生成2.4.2矢量式字符

矢量式字符將字符表達(dá)為點(diǎn)坐標(biāo)的序列，相鄰兩點(diǎn)表示一條矢量，字符的形狀便由矢量序列刻畫。圖2.12示出用矢量式表示的字符“B”?！癇”是由頂點(diǎn)序列{a,b,c,d,e,f,e,g,h,i,j,k,j,

a,l}的坐標(biāo)表達(dá)。圖2.12矢量式表示字符“B”2.4字符的生成2.4.3方向編碼式字符

方向編碼式字符用有限的若干種方向編碼來表達(dá)一個(gè)字符。圖2.13示出8個(gè)方向的編碼為0~7。圖2.14(a)示出字母“B”的方向矢量構(gòu)成。這樣，“B”就表示為8方向編碼{0000123444000123444406666}。方向編碼式字符很容易被填入幀暫存寄存器中予以顯示(圖2.14(b))，方向編碼所占的空間比較小，它也能接受一些特定的變換操作。圖2.13字符的8方向編碼

圖2.14方向編碼式字符的實(shí)例2.4字符的生成2.4.4輪廓字形技術(shù)

直接使用點(diǎn)陣式字符方法將耗費(fèi)巨大的存儲空間。壓縮方法有多種，最簡單的有黑白段壓縮法。另一種方法是部件壓縮法。三是輪廓字形法，這種方法壓縮比大，且能保證字符質(zhì)，是當(dāng)今國際上最流行的一種方法。

輪廓字形法采用直線、或者二次Bezier曲線、三次Bezier曲線的集合來描述一個(gè)字符的輪廓線。輪廓線構(gòu)成一個(gè)或若干個(gè)封閉的平面區(qū)域。輪廓線定義和一些指示橫寬、豎寬、基點(diǎn)、基線等的控制信息，就構(gòu)成了字符的壓縮數(shù)據(jù)。采用適當(dāng)?shù)膮^(qū)域填充算法，可以從字符的輪廓線定義產(chǎn)生的字符位圖點(diǎn)陣，區(qū)域填充算法可以用硬件實(shí)現(xiàn)，也可以用軟件實(shí)現(xiàn)。由美國Apple和Microsoft公司聯(lián)合開發(fā)的TrueType字型技術(shù)就是一種輪廓字型技術(shù)，已被用于為Windows中文版生成漢字字庫。當(dāng)前占領(lǐng)主要的電子印刷市場的我國北大方正和華光電子印刷系統(tǒng)，用的字型技術(shù)是漢字字型輪廓矢量法。這種方法能夠準(zhǔn)確地把字符的信息描述下來，保證了還原的字符質(zhì)量，又對字型數(shù)據(jù)進(jìn)行了大量的壓縮。調(diào)用字符時(shí)，可以任意地放大、縮小或進(jìn)行花樣變化，基本上能滿足電子印刷中字型質(zhì)量的要求。輪廓字型技術(shù)有著廣泛的應(yīng)用。到目前為止在印刷行業(yè)中使用最多。2.5圖形求交

在計(jì)算機(jī)圖形學(xué)中常常會遇到求交計(jì)算。求交運(yùn)算是比較復(fù)雜的，為了減少計(jì)算量，在進(jìn)行真正的求交計(jì)算之前，往往先用凸包等輔助結(jié)構(gòu)進(jìn)行粗略地比較，排除那些顯然不相交的情形。

求交問題可以分為兩類：

求交點(diǎn)求交線

2.5圖形求交2.5.1求交點(diǎn)算法

求交點(diǎn)可以分兩種情況，即求線與線的交點(diǎn)以及求線與面的交點(diǎn)。⒈

直線段與直線段的交點(diǎn)假設(shè)兩條直線的端點(diǎn)分別為P1、P2和Q1、Q2，則直線可以用向量形式表示為P(t)=A+Bt，

0≤t≤1Q(s)=C+Ds，

0≤s≤1其中，A=P1，B=P2P1，C=Q1，D=Q2Q1。構(gòu)造方程

A+Bt=C+Ds(2.9)

對三維空間中的直線段來說，上述方程組實(shí)際上是一個(gè)二元一次方程組，由3個(gè)方程式組成?？梢詮钠渲袃蓚€(gè)解出s、t，再用第三個(gè)驗(yàn)證解的有效性。當(dāng)所得的解(ti,si)是有效解時(shí)，可用兩個(gè)方程之一計(jì)算交點(diǎn)坐標(biāo)，例如P(ti)=A+Bti。

2.5圖形求交2.5.1求交點(diǎn)算法（續(xù)）

根據(jù)向量的基本性質(zhì)，可直接計(jì)算s與t。對方程(2.9)兩邊構(gòu)造點(diǎn)積得

(CD)·(A+Bt)=(CD)·(C+Ds)由于CD同時(shí)垂直于C和D，等式右邊為0。故有類似地有2.5圖形求交2.5.1求交點(diǎn)算法（續(xù)）

⒉

直線段與二次曲線的交點(diǎn)考慮平面上一條直線與同平面的一條二次曲線的交點(diǎn)。假設(shè)曲線方程為f(x,y)=0直線段方程為(x,y)=(x1+tdx,y1+tdy)則在交點(diǎn)處有

f(x1+tdx,y1+tdy)=0當(dāng)曲線為二次曲線時(shí)，上述方程可寫為

at2+bt+c=0用二次方程求根公式即可解出t值。⒊

圓錐曲線與圓錐曲線的交點(diǎn)在進(jìn)行一對圓錐曲線的求交時(shí)，把其中一條圓錐曲線用代數(shù)法或幾何法表示為隱函數(shù)形式，另一條表示為參數(shù)形式(如二次NURBS曲線)。將參數(shù)形式代入隱函數(shù)形式可得到關(guān)于參數(shù)的四次方程。2.5圖形求交2.5.1求交點(diǎn)算法（續(xù)）

下面討論線與面的交點(diǎn)的求法。⒈

直線段與平面的交點(diǎn)圖2.15線段與平面求交

如圖2.15所示。把平面上的點(diǎn)表示為P(u,w)=A+uB+wC，直線段上的點(diǎn)表示為Q(t)=D+tE，二者的交點(diǎn)記為R。假設(shè)線段不平行于平面，則它們交于

R=P(u,w)=Q(t)，即A+uB+wC=D+tE2.5圖形求交2.5.1求交點(diǎn)算法（續(xù)）

等式兩邊點(diǎn)乘(BC)，得

(BC)·(A+uB+wC)=(BC)·(D+tE)由于BC既垂直于B，又垂直于C，故有

(BC)·

A=(BC)·(D+tE)可解出類似求得如果是直線與平面區(qū)域求交點(diǎn)，則要進(jìn)一步判斷交點(diǎn)是否在平面的有效區(qū)域中，其算法可參見2.5.3節(jié)。2.5圖形求交2.5.1求交點(diǎn)算法（續(xù)）

⒉

圓錐曲線與平面的交點(diǎn)圓錐曲線與平面求交點(diǎn)時(shí)，可以把圓錐曲線表示為參數(shù)形式，并把圓錐曲線的參數(shù)形式代入平面方程，即可得到參數(shù)的二次方程，從而進(jìn)行求解。⒊

圓錐曲線與二次曲面的交點(diǎn)圓錐曲線與二次曲面求交點(diǎn)時(shí)，可把圓錐曲線的參數(shù)形式代入二次曲面的隱式方程，得到參數(shù)的四次方程，用四次方程求根公式求解。2.5圖形求交2.5.2

求交線算法

⒈

平面與平面的交線先考慮最簡單的情形。兩個(gè)平面區(qū)域分別由P(u,w)，Q(s,t)，u，w，s，t[0,1]定義。如果它們不共面而且不分離，則必交于一直線段。這條直線必落在P(u,w)Q(s,t)=0所定義的無限直線上。這是個(gè)含有4個(gè)未知數(shù)，3個(gè)方程式的方程組，只要分別與8條邊界線方程：u=0，u=1，w=0，w=1，s=0，s=1，t=0，t=1聯(lián)立，即可求出線段的兩個(gè)端點(diǎn)的參數(shù)。

2.5圖形求交2.5.2

求交線算法

（續(xù)）

⒉

平面與二次曲面的交線

代數(shù)法:

把二次曲面表示為代數(shù)形式

Ax2+By2+Cz2+2Dxy+2Eyz+2Fxz+2Gx+2Hy+2Iz+J=0

通過平移與旋轉(zhuǎn)坐標(biāo)變換把平面變?yōu)閤Oy平面，對二次曲面進(jìn)行同樣的坐標(biāo)變換。由于在新坐標(biāo)系下平面的方程為z=0，所以新坐標(biāo)系下二次曲面方程中，把含z項(xiàng)都去掉即為平面與二次曲面的交線方程。對該交線方程進(jìn)行一次逆坐標(biāo)變換即可獲得在原坐標(biāo)系下的交線方程。

幾何法:幾何法存儲曲線的類型(橢圓、拋物線或雙曲線)，以及定義參數(shù)(中心點(diǎn)、對稱軸、半徑等)的數(shù)值信息，使用局部坐標(biāo)系到用戶坐標(biāo)系的變換，把局部坐標(biāo)系下的定義參數(shù)變換到用戶坐標(biāo)系直接使用。

當(dāng)平面與二次曲面的交線需要精確表示時(shí)，往往采用幾何法求交。2.5圖形求交2.5.2

求交線算法

（續(xù)）

下面以平面—球求交為例，說明幾何法求交算法。平面用一個(gè)記錄p表示，p的兩個(gè)子域p.b、p.w分別代表平面上一點(diǎn)、平面法向量。球面用記錄s表示，它的兩個(gè)子域s.c、s.r分別代表球面中心和半徑。則可寫出平面與球面相交的算法如下：plane_sphere_intersect(p,s)planep;spheres;{d=球面中心到平面的有向距離；if(abs(d)==s.r){2個(gè)面相交于一(切)點(diǎn)s.cd*p.w;}elseif(abs(d)>s.r){兩個(gè)面無交；}2.5圖形求交2.5.2

求交線算法

（續(xù)）

else{所求交線是圓。其圓心、半徑、圓所在平面法向量為c=s.cd*p.w;r=sqrt(s.r2d2);w=p.w;}}

2.5圖形求交2.5.2

求交線算法（續(xù)）

⒊

平面與參數(shù)曲面的交線求平面與參數(shù)曲面的交線，最簡單的方法是把表示參數(shù)曲面的變量(x(s,t),y(s,t),z(s,t))代入平面方程

ax+by+cz+d=0得到用參數(shù)曲面的參數(shù)s、t表示的交線方程

ax(s,t)+by(s,t)+cz(s,t)+d=0

另一種方法是，用平移和旋轉(zhuǎn)對平面進(jìn)行坐標(biāo)變換，使平面成為新坐標(biāo)系下的xOy平面。再將相同的變換應(yīng)用于參數(shù)曲面方程，得到參數(shù)曲面在新坐標(biāo)系下的方程

(x*,y*,z*)=(x*(s,t),y*(s,t),z*(s,t))由此得交線在新坐標(biāo)系下的方程為z*(s,t)=0。2.5圖形求交2.5.3包含判定算法

在進(jìn)行圖形求交時(shí)，常常需要判定兩個(gè)圖形間是否有包含關(guān)系。如點(diǎn)是否包含在線段、平面區(qū)域或三維形體中，線段是否包含在平面區(qū)域或三維形體中，等等。許多包含判定問題可轉(zhuǎn)化為點(diǎn)的包含判定問題，如判斷線段是否在平面上的問題可以轉(zhuǎn)化為判斷線段兩端點(diǎn)是否在平面上。判斷點(diǎn)與線段的包含關(guān)系，也就是判斷點(diǎn)與線的最短距離是否位于容差范圍內(nèi)。造型中常用的線段有3種，即直線段、圓錐曲線段(主要是圓弧)和參數(shù)曲線(主要是Bezier曲線、B樣條與NURBS曲線)。點(diǎn)與面的包含判定也類似地分為3種情況。下面分別予以討論。2.5圖形求交2.5.3包含判定算法（續(xù)）⒈

點(diǎn)與直線段的包含判定假設(shè)點(diǎn)坐標(biāo)為P(x,y,z)，直線段端點(diǎn)為P1(x1,y1,z1)、P2(x2,y2,z2)，則點(diǎn)P到線段P1P2