圖形學(xué)知識點(diǎn)

1、常見的直線有三種掃描算法：DDA算法，中點(diǎn)畫線法，Bresenham算法。下面來看看中點(diǎn)劃線算法。中點(diǎn)畫線算法中點(diǎn)畫線算法其實(shí)是基于判斷點(diǎn)在直線的上方還是下方。 基本思想：當(dāng)前象素點(diǎn)為(xp, yp) 。下一個象素點(diǎn)為P1 或P2 。設(shè)M=(xp+1,yp+0.5)，為p1與p2之中點(diǎn)，Q為理想直線   x=xp+1垂線的交點(diǎn)。將Q與M的y坐標(biāo)進(jìn)行比較。當(dāng)M在Q的下方，則P2  應(yīng)為下一個象素點(diǎn)；M在Q的上方，應(yīng)取P1為下一點(diǎn)。構(gòu)造判別式:d=F(M)=F(xp+1,yp+0.5) =a(xp+1)+b(yp+0.5)+c其中a=y0-y1, b=x1-

2、x0, c=x0y1-x1y0當(dāng)d<0，M在L(Q點(diǎn))下方，取右上方P2為下一個象素；當(dāng)d>0，M在L(Q點(diǎn))上方，取右方P1為下一個象素；當(dāng)d=0，選P1或P2均可， 約定取P1為下一個象素；若當(dāng)前象素處于d>=0情況，則取正右方象素P1 (xp+1, yp), 要判下一個象素位置，應(yīng)計(jì)算     d1 = F(xp+2, yp+0.5)=a(xp+2)+b(yp+0.5)=d+a； 增量為a若d<0時，則取右上方象素P2 (xp+1, yp+1)。要判斷再下一象素，則要計(jì)算     d2

3、 = F(xp+2, yp+1.5)=a(xp+2)+b(yp+1.5)+c=d+a+b ；增量為ab畫線從(x0, y0)開始，d的初值 d0 = F(x0+1, y0+0.5)=F(x0, y0)+a+0.5b =a+0.5b。可以用2d代替d來擺脫小數(shù)，提高效率。令 d0=2a+b, d1=2a, d2=2a+2b,我們有如下算法 。算法代碼：void Midpoint Line (int x0,int y0,int x1, int y1,int color)     int a, b, d1, d2, d, x, y;

4、0;  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; &

5、#160;    else              x+, d+=d1;    drawpixel (x, y, color);  2.2.2 中點(diǎn)算法生成圓中點(diǎn)畫圓算法在一個方向上取單位間隔，在另一個方向的取值由兩種可能取值的中點(diǎn)離圓的遠(yuǎn)近而定。實(shí)際處理中，用決策變量的符號來確定象素點(diǎn)的選擇，因此算法效率較高。一、中點(diǎn)畫圓算法描述設(shè)要顯示圓的圓心在原點(diǎn)(0，0)，半徑為R，起點(diǎn)在(0

6、，R)處，終點(diǎn)在(，)處，順時針生成八分之一圓，利用對稱性掃描轉(zhuǎn)換全部圓。為了應(yīng)用中點(diǎn)畫圓法，我們定義一個圓函數(shù)F(x，y)=x2+y2-R2(219)任何點(diǎn)(x，y)的相對位置可由圓函數(shù)的符號來檢測：F(x，y)<0點(diǎn)(x，y)位于數(shù)學(xué)圓內(nèi)=0點(diǎn)(x，y)位于數(shù)學(xué)圓上>0點(diǎn)(x，y)位于數(shù)學(xué)圓外(220) 如下圖所示，圖中有兩條圓弧A和B，假定當(dāng)前取點(diǎn)為Pi(xi，yi)，如果順時針生成圓，那么下一點(diǎn)只能取正右方的點(diǎn)E(xi+1，yi)或右下方的點(diǎn)SE(xi+1，yi-1)兩者之一。中點(diǎn)畫線算法假設(shè)M是E和SE的中點(diǎn)，即 ，則：1、當(dāng)F(M)<0時，M在圓內(nèi)(圓弧

7、A)，這說明點(diǎn)E距離圓更近，應(yīng)取點(diǎn)E作為下一象素點(diǎn)；2、當(dāng)F(M)>0時，M在圓外(圓弧B)，表明SE點(diǎn)離圓更近，應(yīng)取SE點(diǎn)；3、當(dāng)F(M)=0時，在E點(diǎn)與SE點(diǎn)之中隨便取一個即可，我們約定取SE點(diǎn)。 二、中點(diǎn)畫圓算法思想因此，我們用中點(diǎn)M的圓函數(shù)作為決策變量di，同時用增量法來迭代計(jì)算下一個中點(diǎn)M的決策變量di+1。(221)下面分兩種情況來討論在迭代計(jì)算中決策變量di+1的推導(dǎo)。1、見圖（a），若di<0，則選擇E點(diǎn)，接著下一個中點(diǎn)就是，這時新的決策變量為：(222)（a）(di<0) 中點(diǎn)畫線算法式(222)減去(221)得：di+1=di+2xi+3(223)2、見圖

8、（b），若di0，則選擇SE點(diǎn)，接著下一個中點(diǎn)就是 ，這時新的決策變量為：(224)（b）(di0) 中點(diǎn)畫線算法式(224)減去(221)得：di+1=di+2(xi-yi)+5(225)我們利用遞推迭代計(jì)算這八分之一圓弧上的每個點(diǎn)，每次迭代需要兩步處理：（1）用前一次迭代算出的決策變量的符號來決定本次選擇的點(diǎn)。（2）對本次選擇的點(diǎn)，重新遞推計(jì)算得出新的決策變量的值。剩下的問題是計(jì)算初始決策變量d0，如下圖所示。對于初始點(diǎn)(0，R)，順時針生成八分之一圓，下一個中點(diǎn)M的坐標(biāo)是 ，所以：(226)生成圓的初始條件和圓的生成方向三、中點(diǎn)畫圓算法實(shí)現(xiàn)1、輸入：圓半徑r、圓心(x0，y0)；2、確定

9、初值：x=0，y=r、d=5/4-r；3、While(x<=y)·利用八分對稱性，用規(guī)定的顏色color畫八個象素點(diǎn)(x，y)；· 若d0y=y-1；d=d+2(x-y)+5)；否則d=d+2x+3；·x=x+1；1、輸入：圓半徑r、圓心(x0，y0)；2、確定初值：x=0，y=r、d=5/4-r；3、While(x<=y)·利用八分對稱性，用規(guī)定的顏色color畫八個象素點(diǎn)(x，y)；· 若d0y=y-1；d=d+2(x-y)+5)；否則d=d+2x+3；·x=x+1；五、中點(diǎn)畫圓算法完善在上述算法中，使用了浮點(diǎn)數(shù)來表示

10、決策變量d。為了簡化算法，擺脫浮點(diǎn)數(shù)，在算法中全部使用整數(shù)，我們使用e=d-1/4代替d。顯然，初值d=5/4-r對應(yīng)于e=1-r。決策變量d<0對應(yīng)于e<-1/4。算法中其它與d有關(guān)的式子可把d直接換成e。又由于e的初值為整數(shù)，且在運(yùn)算過程中的迭代值也是整數(shù)，故e始終是整數(shù)，所以e<-1/4等價(jià)于e<0。因此，可以寫出完全用整數(shù)實(shí)現(xiàn)的中點(diǎn)畫圓算法。要求：寫出用整數(shù)實(shí)現(xiàn)的中點(diǎn)畫圓算法程序，并上機(jī)調(diào)試，觀看運(yùn)行結(jié)果。六、中點(diǎn)畫圓算法程序void MidpointCircle(int x0,int y0,int r,int color)int x,y;float d;x=0

11、;y=r;d=5.0/4-r;while(x<=y)putdot(x0,y0,x,y,color);if(d<0)d+=x*2.0+3;elsed+=2.0*(x-y)+5;y-; x+;putdot(x0,y0,x,y,color)putpixel(x0+x,y0+y,color);putpixel(x0+x,y0-y,color);putpixel(x0-x,y0+y,color);putpixel(x0-x,y0-y,color);putpixel(x0+y,y0+x,color);putpixel(x0+y,y0-x,color);putpixel(x0-y,y0+x,co

12、lor);putpixel(x0-y,y0-x,color);bezier曲線 一、原理： 貝塞爾曲線于1962年，由法國工程師皮埃爾·貝塞爾（Pierre Bézier）所廣泛發(fā)表，他運(yùn)用貝塞爾曲線來為汽車的主體進(jìn)行設(shè)計(jì)。貝塞爾曲線最初由 Paul de Casteljau 于1959年運(yùn)用 de Casteljau 算法開發(fā)，以穩(wěn)定數(shù)值的方法求出貝塞爾曲線。線性貝塞爾曲線給定點(diǎn) P0、P1，線性貝塞爾曲線只是一條兩點(diǎn)之間的直線。這條線由下式給出：且其等同于線性插值。二次方貝塞爾曲線的路徑由給定點(diǎn) P0、P1、P2 的函數(shù) B(t) 追蹤：。 TrueType

13、字型就運(yùn)用了以貝塞爾樣條組成的二次貝塞爾曲線。P0、P1、P2、P3 四個點(diǎn)在平面或在三維空間中定義了三次方貝塞爾曲線。曲線起始于 P0 走向 P1，并從 P2 的方向來到 P3。一般不會經(jīng)過 P1 或 P2；這兩個點(diǎn)只是在那里提供方向資訊。 P0 和 P1 之間的間距，決定了曲線在轉(zhuǎn)而趨進(jìn) P3 之前，走向 P2 方向的“長度有多長”。曲線的參數(shù)形式為：。 現(xiàn)代的成象系統(tǒng)，如 PostScript、Asymptote 和 Metafont，運(yùn)用了以貝塞爾樣條組成的三次貝塞爾曲線，用來描繪曲線輪廓。一般化P0、P1、Pn，其貝塞爾曲線即例如 ：如上公式可如下遞歸表達(dá)： 用 表示由點(diǎn) P0、P1

14、、Pn 所決定的貝塞爾曲線。則用平常話來說， 階貝塞爾曲線之間的插值。一些關(guān)于參數(shù)曲線的術(shù)語，有即多項(xiàng)式又稱作 n 階的伯恩斯坦基底多項(xiàng)式，定義 00 = 1。點(diǎn) Pi 稱作貝塞爾曲線的控制點(diǎn)。多邊形以帶有線的貝塞爾點(diǎn)連接而成，起始于 P0并以 Pn 終止，稱作貝塞爾多邊形（或控制多邊形）。貝塞爾多邊形的凸包（convex hull）包含有貝塞爾曲線。線性貝塞爾曲線函數(shù)中的 t 會經(jīng)過由 P0 至P1 的 B(t) 所描述的曲線。例如當(dāng) t=0.25時，B(t) 即一條由點(diǎn) P0 至 P1 路徑的四分之一處。就像由 0 至 1 的連續(xù) t，B(t) 描述一條由 P0 至 P1 的直線。為建構(gòu)二

15、次貝塞爾曲線，可以中介點(diǎn) Q0 和 Q1 作為由 0 至 1 的 t：· 由 P0 至 P1 的連續(xù)點(diǎn) Q0，描述一條線性貝塞爾曲線。 · 由 P1 至 P2 的連續(xù)點(diǎn) Q1，描述一條線性貝塞爾曲線。 · 由 Q0 至 Q1 的連續(xù)點(diǎn) B(t)，描述一條二次貝塞爾曲線。 為建構(gòu)高階曲線，便需要相應(yīng)更多的中介點(diǎn)。對于三次曲線，可由線性貝塞爾曲線描述的中介點(diǎn) Q0、Q1、Q2，和由二次曲線描述的點(diǎn) R0、R1 所建構(gòu)：對于四次曲線，可由線性貝塞爾曲線描述的中介點(diǎn) Q0、Q1、Q2、Q3，由二次貝塞爾曲線描述的點(diǎn) R0、R1、R2，和由三次貝塞爾曲線描述的點(diǎn) S0、S1

16、 所建構(gòu)：P(t)=(1-t)P0+tP1下面是4個點(diǎn)的遞推公式，可是使用遞歸實(shí)現(xiàn)的de Casteljau算法。  本文轉(zhuǎn)自：凸包（Convex Hull）是一個計(jì)算幾何（圖形學(xué)）中的概念。用不嚴(yán)謹(jǐn)?shù)脑拋碇v，給定二維平面上的點(diǎn)集，凸包就是將最外層的點(diǎn)連接起來構(gòu)成的凸多邊型，它能包含點(diǎn)集中所有點(diǎn)的。bezier曲線定義：n次多項(xiàng)式曲線P(t)稱為n次Bezier曲線Pt=i=0nPi.BEZi,n(t) 0,1其控制頂點(diǎn)、控制多邊形。性質(zhì)：(1)端點(diǎn)位置 p(t)|t=0=P0、p(t)|t=1=Pn (2) 端點(diǎn)切矢量；（3）對稱性：不是形狀對稱，保持貝塞爾曲線全部控制點(diǎn)Pi的坐標(biāo)

17、位置不變，只是將控制點(diǎn)Pi的排序顛倒 ，曲線形狀保持不變。（3）凸包性：a：點(diǎn)集的凸包：包含這些點(diǎn)的最小凸集；b：Bezier曲線位于其控制頂點(diǎn)的凸包之內(nèi)。（4）多值性。（5）幾何不變性（6）平面曲線的變差縮減性優(yōu)點(diǎn)： 形狀控制直觀、設(shè)計(jì)靈活缺點(diǎn)： （1）所生成的曲線與特征多邊形的外形相距較遠(yuǎn)（2）局部控制能力弱，因?yàn)榍€上任意一點(diǎn)都是所有給定頂點(diǎn)值的加權(quán)平均（3）控制頂點(diǎn)數(shù)增多時，生成曲線的階數(shù)也增高（4）控制頂點(diǎn)數(shù)較多時，多邊形對曲線的控制能力減弱（5）曲線拼接需要附加條件，不太靈活缺陷：以Bernstein基函數(shù)構(gòu)造的Bezier曲線或曲面有許多優(yōu)越性，但有兩點(diǎn)不足：其一是Bezier曲

18、線或曲面不能作局部修改，控制多邊形的一個頂點(diǎn)發(fā)生了變化，整條Bezier曲線的形狀便發(fā)生變化；其二是Bezier曲線或曲面的拼接比較復(fù)雜。因此，產(chǎn)生B樣條。B樣條曲線優(yōu)于Bezier曲線之處：（1）與控制多邊形的外形更接近；（2）局部修改能力；（3）任意形狀，包括尖點(diǎn)、直線的曲線；（4）易于拼接（5）階次低，與型值點(diǎn)數(shù)目無關(guān)，計(jì)算簡便。B樣條缺點(diǎn)：不能精確地表示圓。B樣條：定義：給定m+n+1個空間向量 Bk ，(k=0,1,m+n)，稱n次參數(shù)曲線。Pi,nt=i=0nBi+1Fl,n(t) 0t1,為B樣條曲線的第i段曲線。它的全體稱n次B樣條曲線，它具有Cn-1連續(xù)性。二次B樣條: n=

19、2， 拋物線。（三角中線的四分之一處。）三次B樣條：n=3，三角中線的三分之一處。三次B樣條的C2連續(xù)性B樣條的基函數(shù)具有如下性質(zhì)：具有如下性質(zhì)： 1）有界正性； 2）權(quán)性； 3）對稱性； 4）遞推性；B 樣條曲線的性質(zhì)：1. 局部性：根據(jù)定義式可知，第 k 段n次B樣條曲線只與 n+1 個頂點(diǎn)Pi(i=0，1，n)有關(guān)，因此，當(dāng)改動其中一個控制頂點(diǎn)時，只會對相鄰的n+1段產(chǎn)生影響，不會對整條曲線(當(dāng) m n)產(chǎn)生影響。這就為設(shè)計(jì)曲線時修改某一局部的形狀帶來了很大的方便。2.幾何不變性：由于定義式所表示的B樣條曲線是參數(shù)形式，因此，和Bezier曲線一樣，B樣條曲線的形狀和位置與坐標(biāo)系選擇無關(guān)

20、。3. 連續(xù)性：當(dāng)給定的m+n+1個控制頂點(diǎn)Pi (i=0，1，m+n)互不相重，則所控制的整條B樣條曲線具有n-1階幾何連續(xù) (Gn-1)。當(dāng)給定的控制頂點(diǎn)相鄰最大重頂點(diǎn)數(shù)為h（即h 個控制頂點(diǎn)重合在一起），則整條B樣條曲線具有n-h-1階幾何連續(xù)(Gn-h-1)。4. 對稱性：根據(jù)B樣條曲線的基函數(shù)的對稱性可推導(dǎo)，它表明了B樣條曲線段的起點(diǎn)和終點(diǎn)的幾何性質(zhì)完全相同。 5.遞推性；6. 保凸性: B樣條曲線和Bezier曲線一樣，也具有保凸性。即當(dāng)所有的控制頂點(diǎn)形成一個平面凸的閉多邊形時， Pk,n(t) 是一條平面凸曲線。7. 凸包性: 當(dāng)t0，1時，有0Gi,n(t)1 (i=0，1，n

21、)和i=0nGi,n(t)，因此，根據(jù)凸包定義可知，對任何t0，1，Pk,n(t) 必定在控制頂點(diǎn)構(gòu)成的凸包之中。如左圖所示，六個控制頂點(diǎn)控制的三次B樣條曲線由三段B樣條曲線段組成。其中，每一條曲線段由四個頂點(diǎn)控制且包含在四個頂點(diǎn)構(gòu)成的凸包之中。8.變差縮減性:二次B樣條曲線:二次B樣條曲線段是一段拋物線。二次B樣曲線的性質(zhì)：1. 端點(diǎn)位置：2. 端點(diǎn)切矢：如左圖所示，六個控制頂點(diǎn)控制的二次B樣條曲線由四段B樣條曲線段組成。其中，每一條曲線段由相鄰的三個頂點(diǎn)控制。曲線段的起點(diǎn)和終點(diǎn)同控制頂點(diǎn)的連接邊相切于連接邊的終點(diǎn)位置。3.當(dāng)P0，P1，P2三頂點(diǎn)共線時，P0,2(t)(t0，1)即蛻化為一

22、段直線。4. 當(dāng)給定一組頂點(diǎn)P0，P1，Pm(m2)，若存在Pi=Pi+1(0im-2)，則二次B樣條曲線經(jīng)過頂點(diǎn)Pi，且在此處是尖點(diǎn)。三次B樣條曲線：三次B樣條性質(zhì)：1：端點(diǎn)位置2：端點(diǎn)切矢及二階導(dǎo)數(shù)三次B樣條曲線的頂點(diǎn)位置和頂點(diǎn)切矢二、三次B樣條曲線的應(yīng)用：在曲線擬合設(shè)計(jì)中，B樣條曲線主要可用于實(shí)驗(yàn)數(shù)據(jù)平滑和要求局部交互式修改的自由曲線設(shè)計(jì)。當(dāng)然，二、三次B樣條曲線及其變型，幾乎可以應(yīng)用到所有的要求具有一次或二次幾何連續(xù)的曲線造型場合。(1)要求過插值端點(diǎn)；(2)封閉的二、三次B樣條曲線； (3)插值二、三次B樣條曲線；非均勻B樣條曲線同樣具有局部性，幾何不變性，連續(xù)性，對稱性，遞推性，凸

23、包性和變差縮減性等性質(zhì)。二 直線段裁剪算法1編碼裁剪算法（Cohen-Sutherland裁減算法）1 編碼裁剪算法的基本思想： （1）將窗口分成9個區(qū)并編碼。(XXXX 為上下右左的順序） （2）對線段的兩個端點(diǎn)進(jìn)行編碼。 （3）對編碼進(jìn)行運(yùn)算，進(jìn)行裁剪的判斷， 找出窗口內(nèi)線段的兩個端點(diǎn)。 (下圖中紅色的AB點(diǎn)）編碼裁剪算法的步驟：step1: 將窗口分成9個區(qū)并對9個區(qū)進(jìn)行編碼。每個區(qū)用4位二進(jìn)制代碼表示，代碼的含義：第一位：點(diǎn)處于左邊框線的左面，則為1，否則為0，表左邊界；第二位：點(diǎn)處于右邊框線的右面，則為1，否則為0，表右邊界；第三位：點(diǎn)處于下邊框線的下面，則為1，否則為0，表下邊界；

24、第四位：點(diǎn)處于上邊框線的上面，則為1，否則為0，表上邊界。例：0110 表示右下，0000 表示正中，0010 表示右中。step2: 對線段的兩個端點(diǎn)進(jìn)行編碼對線段的端點(diǎn)進(jìn)行編碼的方法：1 若XA<XL: XA的編碼=0001 否則若XA>XR: XA的編碼=0010 否則若XA=XL: XA的編碼=0000 否則若XA=XR: XA的編碼=00002 若YA>YT: YA的編碼=1000 否則若YA<YB: YA的編碼=0100 否則若YA=YT: YA的編碼=0000 否則若YA=YB: YA的編碼=00003 點(diǎn)A的編碼=XA|YA （求XA與YA的或運(yùn)算） 例

25、：XA=0001,YA=0100,則點(diǎn)A的編碼0101Step3: 進(jìn)行裁剪的判斷根據(jù)線段與窗口的位置關(guān)系分三種情況處理： 1 如果線段的兩個端點(diǎn)的編碼都為0000（計(jì)算方法見下頁）證明該線段的兩個端點(diǎn)都在窗口內(nèi)，則輸出并顯示。兩端點(diǎn)全在窗口內(nèi)的判斷式：x1(3) + x1(2) + x1(1) + x1(0) = 0x2(3) + x2(2) + x2(1) + x2(0) = 0“是”的例子：線段a(a1=0000,a2=0000)a1(3) + a1(2) + a1(1) + a1(0) = 0 + 0 + 0 + 0 = 0a2(3) + a2(2) + a2(1) + a2(0) =

26、 0 + 0 + 0 + 0 = 0結(jié)果：兩端點(diǎn)的代碼的各個位均為0，符合保留條件，線段在窗口內(nèi)，a應(yīng)保留“否”的例子：線段d(d1=0001,d2=0000)d1(3) + d1(2) + d1(1) + d1(0) = 0 + 0 + 0 + 1 = 1d2(3) + d2(2) + d2(1) + d2(0) = 0 + 0 + 0 + 0 = 0結(jié)果：兩端點(diǎn)的代碼的各個位不都為0，不符合保留條件 d是否保留應(yīng)進(jìn)一步判斷。2 如果線段的兩個端點(diǎn)的與運(yùn)算不等于0，兩個端點(diǎn)一定在窗口外的同一側(cè)，可以裁掉。例：codeA=0100, codeB=0110, codeA & codeB

27、= 0100 不等于0，故應(yīng)該裁剪。兩端點(diǎn)全在窗口外的判斷式：x1(3)*x2(3) + x1(2)*x2(2) + x1(1)*x2(1) + x1(0)*x2(0) 0“是”的例子：線段b（b1=0101,b2=0110）b1(3)*b2(3) + b1(2)*b2(2)+b1(1)*b2(1)+b1(0)*b2(0)=0*0+ 1*1+ 0*1 + 1*0 =1 0注：1*1 說明直線的兩個端點(diǎn)都在窗口之下，該直線必在窗口之下，該裁減。結(jié)果：兩端點(diǎn)的代碼的邏輯乘為非0，符合裁減條件，線段b在窗口外，b應(yīng)裁減“否”的例子：線段c（c1=1000,c2=0010）c1(3)*c2(3) +

28、c1(2)*c2(2) + c1(1)*c2(1) + c1(0)*c2(0) =1*0 + 0*0+ 0*1 + 0*0 =0結(jié)果：兩端點(diǎn)的代碼的邏輯乘為0，不符合裁減條件，c是否裁減應(yīng)進(jìn)一步判斷。3 如果線段不能由上述兩種測試，必須把線段再分割： 有下列幾種情形： (1)一個端點(diǎn)在窗口外，一個端點(diǎn)在窗口內(nèi)，如圖A，圖B (2)兩個端點(diǎn)都在窗口外，中間部分在窗口內(nèi)，如圖C (3)兩個端點(diǎn)都在窗口外，中間部分在窗口外，如圖D方法：1、先找出窗口的邊界XL,XR,YT,YB2、讓端點(diǎn)A分別與XL,XR,YT,YB進(jìn)行比較。按照上下右左或（左右下上）的順序去比較。若YA>YT，則舍掉A點(diǎn)，求

29、新交點(diǎn)C：XC=XA+ （XB-XA） /（YB-YA） * （YC-YA） YC=YT3 再求點(diǎn)C的編碼。(1)此時已裁掉AC，剩下BC，由裁剪AB的問題變?yōu)椴眉鬊C的問題。(2)裁剪BC時，返回step1,直到兩個端點(diǎn)的編碼都為0，才畫線。(3) 若一個線段被分成幾部分，每一部分的兩個端點(diǎn)的編碼與運(yùn)算都不等于0，證明每一部分都在窗口外的同一側(cè)，刪掉。 如 ：線段EF編碼裁剪算法的優(yōu)缺點(diǎn)：優(yōu)點(diǎn)： 方便直觀，速度快缺點(diǎn)：(1) 由于采用位邏輯乘的運(yùn)算，在有些高級語言中不便進(jìn)行；(2) 對于跨越三個區(qū)域的線段，不能一次作出判斷而裁剪，仍需分成幾段去判斷，最終全部刪掉。多邊形的裁剪算法:逐邊裁剪算

30、法（Sutherland-Hodgman算法）；邊界裁剪算法逐邊裁剪算法（Sutherland-Hodgman算法）直線與多邊形裁剪的不同點(diǎn)：1 直線的裁剪：裁掉窗口外的部分即可2 多邊形的裁剪：裁掉窗口外的部分后，窗口內(nèi)的部分仍然要求是封閉圖形?；舅枷耄阂来斡么翱诘乃臈l邊框直線對多邊形進(jìn)行分步裁剪。沿著多邊形依次處理頂點(diǎn)會遇到四種情況：逐邊裁剪算法的步驟：(1)生成頂點(diǎn)序列：把待裁剪多邊形的各個頂點(diǎn)按照一定的方向有次序地組成頂點(diǎn)序列。(2)對頂點(diǎn)序列進(jìn)行處理： 用裁剪邊依次檢驗(yàn)每個頂點(diǎn)：處于裁剪邊可見側(cè)的頂點(diǎn)，被列入新頂點(diǎn)序列，例如A；處于裁剪邊不可見側(cè)的頂點(diǎn)，則被刪除；例如B；同時，檢驗(yàn)

31、此點(diǎn)與其后繼頂點(diǎn)，是否在裁剪邊的兩側(cè)，若“是”，則求出與邊的交點(diǎn)，存入新頂點(diǎn)序列。新的頂點(diǎn)序列組成了新的多邊形。(3)把輸出的頂點(diǎn)序列作為新的輸入序列，再去執(zhí)行(2), 重復(fù)3次。邊界裁剪算法:(也稱雙邊裁剪法，但不是用窗口的兩個邊來裁剪)邊界裁剪算法:(也稱雙邊裁剪法，但不是用窗口的兩個邊來裁剪)1 基本思想：(1)在裁剪的過程中,把用戶多邊形和窗口多邊形的邊交互使用。(2)先用多邊形的邊裁剪多邊形，找出位于窗口內(nèi)的頂點(diǎn)。（a）遇到某種條件時，轉(zhuǎn)而用窗口的邊去裁剪多邊形；（b）遇到一定條件又轉(zhuǎn)回用多邊形去裁剪多邊形。(3)如此反復(fù)，直到起點(diǎn)。裁剪前需將多邊形和窗口的頂點(diǎn)，都按相同方向，排列有

32、序。邊界裁剪算法的步驟：Step1: 生成兩個環(huán)(1) 把多邊形的頂點(diǎn)按逆(順)時針的方向排成一個環(huán)；同時把窗口的四個頂點(diǎn)也按逆(順)時針方向排成一個環(huán)。(2) 目的：確定搜索方向。即按照環(huán)的方向搜索位于窗口內(nèi)的頂點(diǎn)。(3) 例：多邊形按照P1P2, P2P3, P3P4, P4P1的方向搜索窗口按照W1W2, W2W3, W3W4, W4W1的方向搜索。Step2: 搜索位于窗口內(nèi)的頂點(diǎn)1 從多邊形的任一點(diǎn)出發(fā)，順環(huán)的方向搜索窗口內(nèi)的頂點(diǎn)， 以及多邊形與窗口的交點(diǎn)。2 遇到交點(diǎn)時分兩種情況處理：(1)交點(diǎn)為入點(diǎn):繼續(xù)按原來的方向搜索(2)交點(diǎn)為出點(diǎn):（a）改變搜索方向，從交點(diǎn)出轉(zhuǎn)彎，轉(zhuǎn)入窗口

33、有效邊；（b）順窗口環(huán)的方向 搜索窗口與多邊形的交點(diǎn)；（c）當(dāng)遇到新的交點(diǎn)時，返回到前交點(diǎn)，重新按多邊形的環(huán)搜索。 Step3 : 反復(fù)執(zhí)行step2，直到回到起點(diǎn)結(jié)束。3 如果按照順時針方向生成兩個環(huán)并按順時針方向搜索的實(shí)例柵欄填充算法柵欄:此算法是為了減少邊緣算法訪問像素的次數(shù)而提出的柵欄填充的基本思想: 對于每個掃描線與多邊形邊的交點(diǎn),就將交點(diǎn)與柵欄之間的像素取補(bǔ).若交點(diǎn)位于柵欄左邊,則將交點(diǎn)之右,柵欄之左的所有像素取補(bǔ)若交點(diǎn)位于柵欄右邊,則將交點(diǎn)之左,柵欄之右的所有像素取補(bǔ)逐點(diǎn)判斷填充算法：區(qū)域填充的基本(初級)方法:逐點(diǎn)判斷填充算法（a）逐點(diǎn)判斷繪圖窗口內(nèi)的每一個像素；（b）若在區(qū)域

34、的內(nèi)部：用指定的屬性設(shè)置該點(diǎn)；否則不予處理；取矩形R(x1xx2,y1yy2)，使R包圍D，則逐點(diǎn)判斷填充算法如下：for(y=y1;y<=y2;y+) for(x=x1;x<=x2;x+) if(inside(D,x,y) drawpixel(x,y,color);上述算法原理簡單、實(shí)用，但效率低。如何判斷點(diǎn)在多邊形的內(nèi)或外？1）射線法；2）累計(jì)角度法；3）編碼法這里以射線法為例進(jìn)行說明：過被檢測點(diǎn)任作一條射線,求其與邊界的交點(diǎn),若交點(diǎn)數(shù)為偶數(shù),則該點(diǎn)在邊界之外,否則在邊界之內(nèi)。AEL（活性邊法）：消隱算法圖像空間消隱：描述for(圖像中每一個像素) 確定由投影點(diǎn)與像素連線穿過的

35、距離觀察點(diǎn)最近的物體；用適當(dāng)?shù)念伾L制該像素； 特點(diǎn)：在屏幕坐標(biāo)系中進(jìn)行的，生成的圖像一般受限于顯示器的分辨率 ；算法復(fù)雜度為O(nN)：場景中每一個物體要和屏幕中每一個像素進(jìn)行排序比較， n為物體個數(shù)，N為像素個數(shù)代表方法：z緩沖器算法，掃描線算法等景物空間消隱: 描述for(世界坐標(biāo)系中的每一個物體) 確定未被遮擋的物體或者部分物體；用恰當(dāng)?shù)念伾L制出可見部分；特點(diǎn)：算法精度高，與顯示器的分辨率無關(guān)，適合于精密的CAD工程領(lǐng)域 算法復(fù)雜度為O(n2)：場景中每一個物體都要和場景中其他的物體進(jìn)行排序比較，n為物體個數(shù)代表方法：背面剔除、表優(yōu)先級算法等z緩沖器算法:基本知識：（1）z緩沖器是幀

36、緩沖器的推廣；（2）幀緩沖器：存儲的是像素的顏色屬性；（3）z緩沖器：存儲的是對應(yīng)像素的z值；（4）假設(shè)在視點(diǎn)坐標(biāo)系(oxyz)中，投影平面為z=0，視線方向沿(-z)軸方向，投影為平行投影；（5）深度值就是物體沿著視線(-z)方向、與視點(diǎn)的距離 ；（6）離視點(diǎn)近的物體遮擋離視點(diǎn)遠(yuǎn)的物體：z值越大，離視點(diǎn)越近。z緩沖器算法描述（1）幀緩沖器中的顏色置為背景顏色（2）z緩沖器中的z值置成最小值(離視點(diǎn)最遠(yuǎn))（4） 以任意順序掃描各多邊形 a) 對于多邊形中的每一像素，計(jì)算其深度值z(x,y) b) 比較z(x, y)與z緩沖器中已有的值zbuffer(x,y) 如果z(x, y) > zb

37、uffer(x, y)，那么 計(jì)算該像素(x, y)的光亮值屬性并寫入幀緩沖器 更新z緩沖器 zbuffer(x, y)z(x, y)繞任意軸的三維旋轉(zhuǎn)變換：針對任意方向軸的變換可用五個步驟來完成： (1)使任意方向軸的起點(diǎn)與坐標(biāo)原點(diǎn)重合，此時進(jìn)行平移變換。 (2)使方向軸與某一坐標(biāo)軸重合，此時需進(jìn)行旋轉(zhuǎn)變換，且旋轉(zhuǎn)變換可能不止一次。 (3)針對該坐標(biāo)軸完成變換。 (4)用逆旋轉(zhuǎn)變換使方向軸回到其原始方向。(5)用逆平移變換使方向軸回到其原始位置。二維變換基本知識：1.比例變換（scale）（指相對于原點(diǎn)的比例變換）Sx平行于x軸的方向上的縮放量；Sy平行于y軸的方向上的縮放量；2.旋轉(zhuǎn)變換（

38、rotation）點(diǎn)P繞原點(diǎn)逆時針轉(zhuǎn)度角（設(shè)逆時針旋轉(zhuǎn)方向?yàn)檎较颍?.平移變換（translation）5.基本幾何變換的齊次坐標(biāo)表示常用的二維幾何變換1.對稱變換（symmetry）（反射變換或鏡像變換） （1）相對于y軸對稱（2）相對于x軸對稱（3）相對于原點(diǎn)對稱（即中心對稱）（4）相對于直線y=x對稱（5）相對于直線y=-x對稱2.錯切變換（shear）（1）沿 x 軸方向關(guān)于 y 軸錯切將圖形上關(guān)于y軸的平行線沿x方向推成角的傾斜線，而保持y坐標(biāo)不變。（2）沿 y 軸方向關(guān)于 x 軸錯切將圖形上關(guān)于x軸的平行線沿y方向推成角的傾斜線，而保持x坐標(biāo)不變。二維組合變換1.相對于任意點(diǎn)（x

39、0 , y0）的比例變換 對任意點(diǎn)比例變換的步驟： （1）平移變換 （2）相對于原點(diǎn)的比例變換 （3）平移變換2.繞任意點(diǎn)（x0 , y0）的旋轉(zhuǎn)變換 繞任意點(diǎn)旋轉(zhuǎn)變換的步驟： （1）平移變換 （2）對圖形繞原點(diǎn)進(jìn)行旋轉(zhuǎn)變換 （3）平移變換相對于任意方向的二維幾何變換如：對某人乙以直線段的坐反射變換，其變換的過程為（1）平移變換；（2）旋轉(zhuǎn)變換；（3）針對坐標(biāo)軸進(jìn)行二維幾何變換；（4）反向旋轉(zhuǎn)； （5）逆向平移。三維齊次坐標(biāo)變換矩陣三維基本幾何變換平移變換三維基本幾何變換比例變換三維基本幾何變換比例變換三維基本幾何變換旋轉(zhuǎn)變換繞Z軸旋轉(zhuǎn)三維空間立體繞z軸正向旋轉(zhuǎn)時, 立體上各頂點(diǎn)的x, y坐標(biāo)

40、改變, 而z坐標(biāo)不變。繞X軸旋轉(zhuǎn)三維空間立體繞x軸旋轉(zhuǎn)時, 立體上各頂點(diǎn)的y, z坐標(biāo)改變, 而x坐標(biāo)不變。繞Y軸旋轉(zhuǎn)三維空間立體繞y軸正向旋轉(zhuǎn)時, 立體上各頂點(diǎn)的x, z坐標(biāo)改變, 而y坐標(biāo)不變。三維基本幾何變換對稱變換關(guān)于坐標(biāo)平面對稱關(guān)于XOY平面進(jìn)行對稱變換的矩陣計(jì)算形式為：關(guān)于YOZ平面進(jìn)行對稱變換的矩陣計(jì)算形式為關(guān)于ZOX平面進(jìn)行對稱變換的矩陣計(jì)算形式為關(guān)于坐標(biāo)軸對稱變換關(guān)于x軸進(jìn)行對稱變換的矩陣計(jì)算形式為關(guān)于Y軸進(jìn)行對稱變換的矩陣計(jì)算形式為關(guān)于Z軸進(jìn)行對稱變換的矩陣計(jì)算形式為關(guān)于原點(diǎn)對稱三維基本幾何變換錯切變換三維錯切變換是指三維立體在空間沿x、 y、 z三個方向?qū)崿F(xiàn)錯切變形, 三

41、維錯切是二維錯切變換的一個擴(kuò)充。 三維錯切變換矩陣為沿z方向錯切：沿x方向錯切沿y方向錯切以z軸為依賴軸(z值不變)的三維錯切變換矩陣：三維復(fù)合變換是指圖形作一次以上的變換，變換結(jié)果是每次變換矩陣的乘積。投影變換就是把三維立體（或物體）投射到投影面上得到二維平面圖形的過程。平面幾何投影主要指平行投影、透視投影以及通過這些投影變換而得到的三維立體的常用平面圖形：三視圖、軸測圖和透視圖等。觀察投影是指在觀察空間下進(jìn)行的圖形投影變換。中心投影法（燈光）透視投影平行投影法（陽光） 斜投影法、正投影法透視投影最接近于視覺效果；正投影法是繪制工程圖樣的基礎(chǔ)。 根據(jù)投影面與坐標(biāo)軸的夾角，正投影又可分為：三視

42、圖和正軸測。三視圖：投影面與某一坐標(biāo)軸垂直，正軸測：投影面與所有坐標(biāo)軸不垂直三視圖投影面分別與X軸、Y軸和Z軸垂直，分為：正視圖V（主視圖）：投影線平行與y軸，XOZ坐標(biāo)面俯視圖H（水平投影面）：投影線平行與z軸，XOY坐標(biāo)面?zhèn)纫晥DW（左視圖）：投影線平行與x軸，YOZ坐標(biāo)面正投影的圖形，在長寬高三個方向上的比例與實(shí)物保持一致，因此，常用于工程制圖。三視圖規(guī)律正視圖反映長、高；俯視圖反映長、寬；側(cè)視圖反映高、寬。主、俯視圖長對正；主、側(cè)視圖高平齊；側(cè)、俯視圖寬相等。確定三維形體上各點(diǎn)的位置坐標(biāo)；引入齊次坐標(biāo)，求出所作變換相應(yīng)的變換矩陣；將所作變換用矩陣表示，通過運(yùn)算求得三維形體上各點(diǎn)(x,y,z)經(jīng)變換后的相應(yīng)點(diǎn)(x,y)或(y,z) ；由變換后的所有二維點(diǎn)繪出三維形體投影后的三視圖。簡單的畫我直接畫了一張，P主點(diǎn)、S視點(diǎn)、V1V2左右余點(diǎn)、M1M2右左測點(diǎn)，PS垂直于視平線，V1S垂直于V2S,V1M1=V1S,V2M2=V2S。平面可以比較的標(biāo)準(zhǔn)長度，我在左上位標(biāo)了。圖內(nèi)的紅線就是標(biāo)準(zhǔn)平面長度，通過測點(diǎn)轉(zhuǎn)換成消失變線。視平線下的是高2、左寬1、右寬3的長方體，視平線上的是邊長為2的正方體。成角透視所有條件和