計(jì)算機(jī)圖形學(xué)各種算法的作業(yè)(偏于理論)

計(jì)算機(jī)圖形學(xué)算法基礎(chǔ)作業(yè)

姓名：________LH__________

學(xué)院：理學(xué)院___________

專業(yè)：計(jì)算數(shù)學(xué)

時(shí)間：2010-12-31

LH的計(jì)算機(jī)圖形學(xué)作業(yè)

目錄

1直線段生成算法綜述....................................................1

1.1生成直線的DDA方法...........................................1

1.1.1DDA算法基本原理..........................................1

1.1.2DDA算法實(shí)現(xiàn)步驟..........................................1

1.1.3DDA算法程序（或偽程序）描述..........................2

1.1.1DDA算法流程圖............................................2

1.2生成直線的Bresenham算法...................................3

1.2.1Bresenham算法基本原理..................................3

1.2.2Bresenham算法實(shí)現(xiàn)步驟..................................5

1.2.3Bresenham算法程序（或偽程序）描述..................5

1.2.4Bresenham算法流程圖.....................................5

1.3中點(diǎn)畫線算法....................................................2

1.3.1中點(diǎn)畫線算法基本原理....................................2

1.3.2中點(diǎn)面線算法實(shí)現(xiàn)步驟....................................3

1.3.3中點(diǎn)畫線算法程序（或偽程序）描述.....................3

1.3.4中點(diǎn)畫線算法流程圖......................................3

1.4生成直線算法的進(jìn)一步改進(jìn)...................................5

1.5各種直線生成算法的優(yōu)缺點(diǎn)對(duì)比分析.......................6

1.6直線生成算法的發(fā)展趨勢(shì)......................................7

2橢圓的Bresenham生成算法...........................................7

LH的計(jì)算機(jī)圖形學(xué)作業(yè)

2.1橢圓曲率分析....................................................7

2.2橢圓方程分析....................................................7

2.3橢圓生成算法...................................................9

2.3.1算法實(shí)現(xiàn)過(guò)程..............................................9

2.3.2算法流程圖...............................................10

2.3.3算法程序描述.............................................11

3直線段裁剪算法綜述..................................................11

3.1Sutherland-Cohen裁剪算法................................11

3.1.1Sutherland-Cohen算法基本原理.......................11

3.1.2Sutherland-Cohen算法實(shí)現(xiàn)步驟.......................11

3.1.3算法程序（或偽程序）描述............................12

3.1.4算法流程圖...............................................12

3.2中點(diǎn)分割裁剪算法............................................12

3.2.1中點(diǎn)分割算法基本原理與實(shí)現(xiàn)步驟......................12

3.2.2算法程序（或偽程序）描述..............................13

3.2.3算法流程圖................................................13

3.3梁友棟一Barskey算法........................................14

3.3.1梁友棟一Barskey算法基本原理與實(shí)現(xiàn)步驟............14

3.3.2算法程序（或偽程序）描述..............................15

3.3.3算法流程圖................................................15

3.4快速算法........................................................15

3.5其余一些改進(jìn)的直線裁剪算法..............................16

II

LH的計(jì)算機(jī)圖形學(xué)作業(yè)

3.6各種直線裁剪算法的優(yōu)缺點(diǎn)對(duì)比分析..................16

3.7直線裁剪算法的發(fā)展趨勢(shì)................................16

4圖形求交技術(shù)....................................................16

4.1求交點(diǎn)算法.................................................16

4.1.1線與線的交點(diǎn)的求法.................................17

4.2.2線與面的交點(diǎn)的求法.................................18

4.2求交線算法................................................19

4.3包含判定算法.............................................21

4.4重疊判定算法.............................................26

4.5凸包計(jì)算..................................................26

5自由曲線曲面造型技術(shù)...........................................28

5.1Bezier曲線和曲面.......................................28

5.1.1Bezier曲線..........................................28

5.1.2Bezier曲面..........................................31

5.2B樣條曲線與曲面........................................32

5.2.1B樣條的遞推定義和性質(zhì).............................32

5.2.2B樣條曲線...........................................34

5.2.5B樣條曲面............................................36

5.3NURBS曲線與曲面........................................37

5.3.1NURBS曲線............................................37

5.3.2非均勻有理B樣條(NURBS)曲面.....................39

5.4Coons曲面.................................................40

in

LH的計(jì)算機(jī)圖形學(xué)作業(yè)

5.4.1基本概念..............................................40

5.4.2雙線性Coons曲面....................................41

5.4.3雙三次Coons曲面....................................42

6CAGD中有關(guān)曲線曲面C“、G”拼接技術(shù)...........................44

6.1基本原理...................................................44

6.2Bezier曲線的C。、G。、CPGPC2>G2的拼接條件........44

6.3Bezier曲面的C。、G。、CpG1的拼接條件..................46

7圖形變換技術(shù).....................................................48

7.1二維圖形幾何變換.........................................49

7.1.1平移(Translation)..................................49

7.1.2旋轉(zhuǎn)(Rotation)......................................49

7.1.3變比(scaling).......................................50

7.2三維圖形幾何變換.........................................51

7.2.1平移..................................................51

7.2.2旋轉(zhuǎn)..................................................51

7.2.3變比..................................................54

7.3參數(shù)圖形幾何變換.........................................54

7.3.1圓錐曲線的幾何變換..................................54

7.3.2參數(shù)曲線、曲面的幾何變換...........................55

7.4投影變換...................................................58

7.4.1平行投影(parallelprojection)....................58

7.4.2透視投影(perspectiveprojection).................60

IV

LH的計(jì)算機(jī)圖形學(xué)作業(yè)

8圖形消隱算法.................................................61

8.1掃描線Z-buffer算法..................................61

8.2區(qū)域子分割算法........................................61

8.3光線投射算法..........................................62

8.4平面公式法.............................................62

8.5徑向預(yù)排序法..........................................63

8.6徑向排序法.............................................63

8.7隔離平面法.............................................63

8.8深度排序法.............................................63

8.9光線跟蹤法.............................................63

8.10Z緩沖區(qū)法............................................64

8.11極值檢測(cè)法............................................64

8.12深度分類方法.........................................64

8.13八叉樹(shù)方法............................................65

9圖形學(xué)若干基本算法的實(shí)現(xiàn)研究.............................65

參考文獻(xiàn)........................................................68

附錄.............................................................68

V

LH計(jì)算機(jī)圖形學(xué)作業(yè)：共九道題

圖形學(xué)算法基礎(chǔ)作業(yè)

1直線段生成算法綜述

1.1生成直線的DDA方法

1.1.1DDA算法基本原理

DDA是數(shù)字微分分析式（DigitalDifferentialAnalyzer）的縮

寫。設(shè)直線之起點(diǎn)為（x”y）,終點(diǎn)為（X242），則斜率k為：

x2-Xjdx

直線中的每一點(diǎn)坐標(biāo)都可以由前一點(diǎn)坐標(biāo)變化一個(gè)增量（D、，Dy）而

得到，即表示為遞歸式：

Xj+l=Xj+Dx

Yi+1=%+D、.

并有關(guān)系：D=mxD

yA

遞歸式的初值為直線的起點(diǎn)（X1,%）,這樣，就可以用加法來(lái)生成一條直

線。

1.1.2DDA算法實(shí)現(xiàn)步驟

具體方法是：

按照直線從（x“％）到（X2，y2）的方向不同，分為8個(gè)象限（見(jiàn)圖1.1）。

對(duì)于方向在第la象限內(nèi)的直線而言，Dx=l,Dy=m。對(duì)于方向在第1b

象限內(nèi)的直線而言，取值Dy=1,D'=l/m。各象限中直線生成時(shí)D,,D,的

取值列在表1T之中。

圖1.1直線方向的8個(gè)象限圖

1

LH計(jì)算機(jī)圖形學(xué)作業(yè)：共九道題

表1-1各象限中直線生成時(shí)D、，D,的取值列

象限|dx|>|dy|9D、D,

laT1m

1bF1/m1

2aT-1m

2bF-1/m1

3aT-1-m

3bF-1/m-1

4aT1-m

4bF1/m-1

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

1、當(dāng)|dx|>|dy|時(shí)|DX|=1,|DJ=HI；否則：Dx=l/m,|Dy|=l

2、Dx，Dy的符號(hào)與dx,dy的符號(hào)相同。這兩條規(guī)律可以導(dǎo)致程序的

簡(jiǎn)化。由上述方法寫成的程序如附錄1所示。其中steps變量的設(shè)置，

以及D*=dx/steps;Dy=dy/steps等語(yǔ)句，正是利用了上述兩條規(guī)律，使得程

序變得簡(jiǎn)練。

使用DDA算法，每生成一條直線做兩次除法，每畫線中一點(diǎn)做兩次

加法。因此，用DDA法生成直線的速度是相當(dāng)快的。

1.1.3DDA算法程序(或偽程序)描述

具體程序見(jiàn)附錄lo

1.1.4DDA算法流程圖

(略)

1.2中點(diǎn)畫線算法

1.2.1中點(diǎn)畫線算法基本原理

假定直線斜率k在。1之間，當(dāng)前象素點(diǎn)為儀酎丫。)，則下一

個(gè)象素點(diǎn)有兩種可選擇點(diǎn)P1(Xp+l*)或P2(xp+l,yp+l)o若R與P2的中

點(diǎn)(Xp+l,yp+0.5)稱為M,Q為理想直線與x=Xp+l垂線的交點(diǎn)。當(dāng)M

2

LH計(jì)算機(jī)圖形學(xué)作業(yè)：共九道題

在Q的下方時(shí)，則取P2應(yīng)為下一個(gè)象素點(diǎn)；當(dāng)M在Q的上方時(shí)，

則取R為下一個(gè)象素點(diǎn)。這就是中點(diǎn)畫線法的基本原理。

1.2.2中點(diǎn)畫線算法實(shí)現(xiàn)步驟

下面討論中點(diǎn)畫線法的實(shí)現(xiàn)。過(guò)點(diǎn)(x°,yo)、&,yj的直線段

L的方程式為F(x,y)=ax+by+c=0,其中a=y0-y|5b=x0-x,,

c=Xoyi-X]yo，要判斷中點(diǎn)M在Q點(diǎn)的上方還是下方，只要把M

代入F(x,y),并判斷它的符號(hào)即可。為此，我們構(gòu)造判別式：

d=F(M)=F(xp+l,yp+0.5)=a(xp+1)+b(yp+0.5)+c

當(dāng)d<0時(shí)，M在L(Q點(diǎn))下方，取P?為下一個(gè)象素；

當(dāng)d>0時(shí)，M在L(Q點(diǎn))上方，取耳為下一個(gè)象素；

當(dāng)d=0時(shí)，選R或P2均可，約定取R為下一個(gè)象素。

注意到d是x”yp的線性函數(shù)，可采用增量計(jì)算，提高運(yùn)算效率。

若當(dāng)前象素處于d>0情況，則取正右方象素P"Xp+l,yp),要判下一

個(gè)象素位置，應(yīng)計(jì)算4=F(xp+2,yp+0.5)=a(xp+2)+b(yp+0.5)+c=d+a,

增量為a。

若d<0時(shí)，則取右上方象素P2(Xp+l*+l)。要判斷再下一象

素，則要計(jì)算d2=F(xp+2,yp+1.5)=a(xp+2)+b(yp+1.5)+c=d+a+b,

增量為a+bo畫線從(x0,y0)開(kāi)始，d的初值

d0=F(x0+l,y0+0.5)=F(x0,y0)+a+0.5b,因F(xo,yo)=O,所以d0=a+0.5b□

由于我們使用的只是d的符號(hào)，而且d的增量都是整數(shù)，只

是初始值包含小數(shù)。因此，我們可以用2d代替d來(lái)擺脫小數(shù)，

寫出僅包含整數(shù)運(yùn)算的算法程序。

1.2.3中點(diǎn)畫線算法程序(或偽程序)描述

具體程序見(jiàn)附錄2

1.2.4中點(diǎn)畫線算法流程圖

(略)

1.3生成直線的Bresenham算法

1.3.1Bresenham算法基本原理

本算法由Bresenham在1965年提出。設(shè)直線從起點(diǎn)(x“y1)到終點(diǎn)

(x2,y2)0直線可表示為方程y=kx+b。其中

3

LH計(jì)算機(jī)圖形學(xué)作業(yè)：共九道題

b=yj-k-x,

k=y^-y._空

X2-x,dX

我們討論先將直線方向限于la象限(圖1.1)在這種情況下，當(dāng)

直線光柵化時(shí)，x每次都增加1個(gè)單元，即x,+l=Xi+l。而y的相應(yīng)增

加應(yīng)當(dāng)小于1。為了光柵化，y+1只可能選擇如圖1.2兩種位置之一。

圖1.2yi+1的位置選擇

圖1.2中yi+1的位置選擇y「l=yi或者Yi+1=Yj+1

選擇的原則是看精確值y與y及y+1的距離dl及d2的大小而定。

計(jì)算式為：

y=m(Xj+l)+b(1.2.1)

dl=y-Yi(1.2.2)

d2=yj+l-y(1.2.3)

如果dl-d2>0,則y+l=yi+l,否則％+1=丫1因此算法的關(guān)鍵在于簡(jiǎn)便

地求出dl-d2的符號(hào)。將式(1.2.1)、(1.2.2)、(1.2.3)代入dl-d2,

得

dl-d2=2y-2y「l=2—(xj+l)-2yi+2b-l

用dx乘等式兩邊，并以R=dx(dl-d2)代入上述等式，得

R=2Xjdy-2Yjdx+2dy+dx(2b-1)(1.2.4)

dl-d2是我們用以判斷符號(hào)的誤差。由于在la象限，dx總大于0,所以

R仍舊可以用作判斷符號(hào)的誤差。耳+1為：

R+l=P,+2dy-2dxg+1-yj(1.2.5)

誤差的初值Pl,可將xl,yl,和b代入式(2.1.4)中的xi,yi而得至h

4

LH計(jì)算機(jī)圖形學(xué)作業(yè)：共九道題

R=2dy-dx

1.3.2Bresenham算法實(shí)現(xiàn)步驟

綜述上面1.3.1的推導(dǎo)，第la象限內(nèi)的直線Bresenham算法思想

如下：

1>畫點(diǎn)（xl,y2）;dx=x2-xl;dy=y2-yl；

計(jì)算誤差初值Pl=2dy-dx;i=l；

2、求直線的下一點(diǎn)位置：

xi+l=xi+l；

ifPi>0則yi+l=yi+l；

否則yi+l=yi；

3、畫點(diǎn)（xi+1,yi-1）；

4、求下一個(gè)誤差Pi+1；

ifPi>0則Pi+l=Pi+2dy-2dx;

否則Pi+l=Pi+2dy；

5、i=i+l;ifi<dx+l則轉(zhuǎn)2；否則end。

1.3.3Bresenham算法程序（或偽程序）描述

由上述算法思想編制的程序見(jiàn)附錄3。這個(gè)程序適用于所有8個(gè)方

向的直線（圖1.1）的生成。程序用色彩C畫出一條端點(diǎn)為（x”力）和

（*2，丫2）的直線。其中變量的含義是：P是誤差；constl和const2,是

誤差的逐點(diǎn)變化量；inc是y的單位遞變量，值為1或-1；tmp是用作

象限變換時(shí)的臨時(shí)變量。程序以判斷|dx|>|dy|為分支，并分別將2a,3a

象限的直線和3b,4b象限的直線變換到la,4a和2b,1b方向去，以求得

程序處理的簡(jiǎn)潔。

1.3.4Bresenham算法流程圖

（略）

1.4生成直線算法的進(jìn)一步改進(jìn)

除過(guò)前面所講到的3種基本直線生成算法外，還有一些其它的方

法，由于過(guò)多，這里僅列舉兒種如下：

（1）二步法。雖然Bresenham直線生成算法是一效率很高的算法，

但是人們?nèi)栽趯ふ腋行５乃惴ā?987年又有人提出了一種二步法。

5

LH計(jì)算機(jī)圖形學(xué)作業(yè)：共九道題

即每循環(huán)一次不是繪制一個(gè)像素，而是繪制兩個(gè)像素，這樣無(wú)疑可把生

成直線的速度提高一倍。

（2）改進(jìn)的Bresenham算法。對(duì)于對(duì)于傳統(tǒng)的直線生成算法，人

們往往把注意力集中在算法本身，卻忽略了算法之外的一些有用信息：

畫線之前，從起點(diǎn)坐標(biāo)和終點(diǎn)坐標(biāo)，我們就可以獲知該線段的斜率，由

此可進(jìn)一步得出在主軸方向連續(xù)走1個(gè)步長(zhǎng)，在副軸方向才走一個(gè)坐標(biāo)

單位，這就是本算法提高Bresenham算法執(zhí)行效率的一個(gè)方面。提高算

法效率的第二個(gè)方面是利用線段本身的對(duì)稱性，則新算法所產(chǎn)生的起點(diǎn)

一側(cè)的半條線段與用Bresenham算法產(chǎn)生的相同。至于終點(diǎn)一側(cè)的半條

線段，可以看成以終點(diǎn)為起點(diǎn)線段的生成。

算法實(shí)現(xiàn)：

特殊地，對(duì)于水平線（Ay=O）,垂直線（Ax=O）和對(duì)角線（岡=卜|）,

它們都可直接裝人幀緩沖器，而無(wú)需進(jìn)行畫線算法處理。

從以上的描述可以實(shí)現(xiàn)優(yōu)于Bresenham的直線生成算法。其中待生

成直線的已知數(shù)據(jù)為：（x“y）為線段起點(diǎn)的橫、縱坐標(biāo)；（X2，y2）為線段終

點(diǎn)的橫、縱坐標(biāo)。

算法的輸人數(shù)據(jù)為：（X|,yj,（x2,y2）o

（3）基于類最佳逼近的散步直線生成算法。一種新的直線逼近方

法一類最佳逼近，基于這種逼近方法，斜率ke[0,0.5）的直線和斜率為l-k

的直線具有某種互補(bǔ)性質(zhì)。利用該性質(zhì)，設(shè)計(jì)出種新的三步直線方法，

該算法揭示了直線計(jì)算的互補(bǔ)性，理論簡(jiǎn)單，精度達(dá)到最好。這種算法改

善了Bresenham算法和雙步算法的計(jì)算效率。該算法對(duì)于硬件實(shí)現(xiàn)將更

有益處。

除此之外直線生成算法還有對(duì)稱掃描四步增量畫線算法、基于

Bresenham的高效直線生成集成算法、基于Bresenham算法的四步畫直

線算法、基于直線特性的直線生成集成算法、基于自適應(yīng)步長(zhǎng)的直線生

成算法、基于等分像素點(diǎn)的直線生成算法、6步直線生成算法、基于對(duì)

角線行程的直線生成算法等等。

1.5各種直線生成算法的優(yōu)缺點(diǎn)對(duì)比分析

DDA算法的優(yōu)點(diǎn)是：繪制實(shí)數(shù)直線效果好，誤差?。蝗秉c(diǎn)是：實(shí)

現(xiàn)較復(fù)雜，不利于硬件實(shí)現(xiàn)。因?yàn)樵撍惴ㄉ婕暗綄?shí)數(shù)乘除法運(yùn)算，y與

k必須用浮點(diǎn)數(shù)表示，而且每一步都要對(duì)y四舍五入后取整。

6

LH計(jì)算機(jī)圖形學(xué)作業(yè)：共九道題

中點(diǎn)畫線算法優(yōu)點(diǎn)是：只有整數(shù)運(yùn)算，不含乘除法；可用硬件實(shí)現(xiàn)。

Bresenham算法的優(yōu)點(diǎn)是：

1、不必計(jì)算直線之斜率，因此不做除法；

2、不用浮點(diǎn)數(shù)，只用整數(shù)；

3、只做整數(shù)加減法和乘2運(yùn)算，而乘2運(yùn)算可以用硬件移位實(shí)現(xiàn)。

4、Bresenham算法速度很快，并適于用硬件實(shí)現(xiàn)。

1.6直線生成算法的發(fā)展趨勢(shì)

（略）

2橢圓的Bresenham生成算法

2.1橢圓曲率分析

橢圓r{acost,bsmt}C。為沿1軸方向的長(zhǎng)半軸長(zhǎng)度，〃為沿丁軸

方向的短半軸長(zhǎng)度，且。〉匕），曲率為/=H/（a2sin21+02cos2/）3/2,在

第一象限fe（0//2）,將勺對(duì)，求導(dǎo)數(shù)，有M,/dr<0,即曲率為減函數(shù)，

在點(diǎn)3,0）（即，=0）處的曲率%,=o）=。//；在點(diǎn)（0力）（即"乃/2）處的

曲率半徑為。的圓的曲率為以//,半徑為匕的圓的曲

率為兩圓的曲率關(guān)系為匕/〃2>。//（“〉0）,則兩圓的曲率在橢

12

圓上點(diǎn)（4,0）與（0/）的曲率之間，四者的關(guān)系為：alb>\/b>\/a>b/a0

2.2橢圓方程分析

根據(jù)橢圓及圓的曲率分析，橢圓弧分別由半徑為以和〃的圓弧逼近

生成。為了更準(zhǔn)確的由圓弧生成橢圓弧，在橢圓弧上確定一點(diǎn)P。，將橢

圓弧分成曲率較小和曲率較大的兩段，橢圓方程為：

F（x,y）=—+a2y2-a2b2=0。

其中4為沿1軸方向的長(zhǎng)半軸長(zhǎng)度，b為沿y軸方向的短半軸長(zhǎng)

度，且a>匕>0。由于橢圓的對(duì)稱性，這里只要討論第一象限橢圓弧

7

LH計(jì)算機(jī)圖形學(xué)作業(yè)：共九道題

的生成。將橢圓弧分為上下兩部分，以弧上曲率為-1的點(diǎn)（即法向量

兩個(gè)分量相等的點(diǎn)）作為分界。該橢圓上一點(diǎn)（x,y）處的法向量為：

、3F.8F22

Nam=菽"百j=2bxi+2ay]

結(jié)合橢圓方程可計(jì)算出分界點(diǎn)Po的坐標(biāo)為：

(a2/yla2+b2,b2/yJa2+/72)。

以P0點(diǎn)為分界點(diǎn)，將第一象限的圓弧分成曲率較大和較小的兩段

弧。如圖2.1所示，ye廳/J"f/向的橢圓弧,與半徑為。的圓在點(diǎn)

22222

T40,a）到T2（a/-Ja+b,ab/y/a+b）的圓弧上對(duì)應(yīng)。在橢圓弧上任取一

點(diǎn)Qi，過(guò)Q/乍垂直線與圓交于R點(diǎn)，連接圓心與R點(diǎn)，與Y軸的夾角為

。。則

橢圓的參數(shù)方程可表示為：

%=asin。,

y,-0cos9.

圓的參數(shù)方程可表示為：

x=asinO,

<

y=QCOSO.

對(duì)于同一0,橢圓弧上存在唯一的點(diǎn)與圓弧上的點(diǎn)對(duì)應(yīng)，并且對(duì)應(yīng)

點(diǎn)的坐標(biāo)存在如下關(guān)系：

X=X,

y'=(b/a)y.

圖2.1圓弧與橢圓弧對(duì)應(yīng)點(diǎn)之-圖2.2圓弧與橢圓弧對(duì)應(yīng)點(diǎn)之一

8

LH計(jì)算機(jī)圖形學(xué)作業(yè)：共九道題

2

如圖2.2所示，半徑為匕的圓上，從點(diǎn)T3（fl/4+/,從/行+/）至

143,0）的圓弧與橢圓上ye（0,Z?2/y/a2+b2）的橢圓弧對(duì)應(yīng)，在橢圓弧上任

取一點(diǎn)Q?，過(guò)Q2作垂直線與圓交于P2點(diǎn)，連接圓心與P2點(diǎn)，與Y軸的夾

角為。。則

橢圓的參數(shù)方程可表示為：

X=asin?,

*

y'=bcosQ.

圓的參數(shù)方程可表示為：

x=/?sin0,

*

y-bcosQ.

對(duì)于同一0,橢圓弧上存在唯一的點(diǎn)與圓弧上的點(diǎn)對(duì)應(yīng)，并且對(duì)應(yīng)

點(diǎn)的坐標(biāo)存在如下關(guān)系：

Ix=（a/b）%,

[y=y.

2.3橢圓生成算法

當(dāng)圓弧上的點(diǎn)從30）沿著圖2.1、圖2.2的對(duì)應(yīng)關(guān)系方向變化到

（。,0）時(shí)，橢圓弧上相對(duì)應(yīng)的點(diǎn)也從該方向變化到（a,0）o

2.3.1算法實(shí)現(xiàn)過(guò)程

1、計(jì)算分界點(diǎn)息制心）。

2、用Bresenham算法生成兩段圓弧和、C20G半徑為a,

xe[0,a2/yla2+b2]；C2半徑為。，ye[0,b2/y/a2+h2]o

3、將圓弧G進(jìn)行比例變換：%方向的比例系數(shù)為1,y方向的比

例系數(shù)為匕/〃；將圓弧C2進(jìn)行比例變換：%方向的比例系數(shù)為。/匕，

y方向的比例系數(shù)為lo

9

LH計(jì)算機(jī)圖形學(xué)作業(yè)：共九道題

4、如圖2.3,已知橢圓上在第一象限的點(diǎn)Q(x,y),則橢圓上另外

三個(gè)象限與Q(x,y)點(diǎn)對(duì)稱的點(diǎn)分別為(-x,y),(-x,-y),(x,-y),因此只

要畫出在第一象限的圖形，即可得到整個(gè)橢圓的圖形。

至（~x.壬y）

（-X,~y）

圖2.3橢圓對(duì)稱性

2.3.2算法流程圖

橢圓的Bresenham算法流程圖如下：

圖2.4橢圓的Bresenham算法流程圖

10

LH計(jì)算機(jī)圖形學(xué)作業(yè)：共九道題

2.3.3算法程序描述

具體程序?qū)崿F(xiàn)見(jiàn)附錄5o

3直線段裁剪算法綜述

裁剪：確定圖形中哪些部分落在顯示區(qū)之內(nèi)，哪些落在顯示區(qū)之外，

以便只顯示落在顯示區(qū)內(nèi)的那部分圖形。這個(gè)選擇過(guò)程稱為裁剪。

直線段裁剪算法是復(fù)雜圖元裁剪的基礎(chǔ)。復(fù)雜的曲線可以通過(guò)折線

段來(lái)近似，從而裁剪問(wèn)題也可以化為直線段的裁剪問(wèn)題。

3.1SutherIand-Cohen裁剪算法

3.1.1SutherIand-Cohen算法基本原理

Sutherland-Cohen算法分成兩步。第一步是判斷直線段是否完全

在窗口內(nèi)，若在則該線段稱為完全可見(jiàn)的；或可顯然的決定線段完全在

窗口的外邊，稱為完全不可見(jiàn)；對(duì)不能判斷完全可見(jiàn)或完全不可見(jiàn)的線

段則要進(jìn)行第二步處理。這時(shí)需要計(jì)算出直線段和窗口邊界的一個(gè)交

點(diǎn)，這個(gè)交點(diǎn)把直線分成兩段，把其中一段顯然完全不可見(jiàn)的線段拋棄，

對(duì)余下的部分再作第一步判斷，重復(fù)上述過(guò)程，直到直線段最后余下的

部分可以用第一步的判斷得出肯定結(jié)論為止。

3.1.2SutherIand-Cohen算法實(shí)現(xiàn)步驟

基本思想：對(duì)于每條線段P〃2分為三種情況處理分為三種情況處

理：

（1）若P0完全在窗口內(nèi)，則顯示該線段P/2，簡(jiǎn)稱“取”之。

（2）若p22明顯在窗口外，則丟棄該線段，簡(jiǎn)稱“棄”之。

（3）若線段不滿足“取”或“棄”的條件，則在交點(diǎn)處把線段分

為兩段。其中--段完全在窗口外，可棄之。然后對(duì)另一段重復(fù)上述處理。

為快速判斷，采用如下編碼方法：

每個(gè)區(qū)域賦予4位編碼（如圖3.1所示）：

GGGG

其中：

「J1）'>>max「I1y<>min

C,=<C=<

0otherh[0other

ll

LH計(jì)算機(jī)圖形學(xué)作業(yè)：共九道題

1X＞工…

C,="max

0other

圖3.1區(qū)域編碼圖3.2線段不能用編碼確定

若pg完全在窗口內(nèi)codel=0,且code2=0,則“取”

若pg明顯在窗口外codel&code2W0,則“棄”

在交點(diǎn)處把線段分為兩段。其中一段完全在窗口外，可棄之。然后

對(duì)另一段重復(fù)上述處理。

計(jì)算線段PIA，M)P2卜,為)與窗口邊界的交點(diǎn)

if(LEFT&code!=0)

{x=XL;y=yl+(y2-yl)*(XL-xl)/(x2-xl);}

elseif(RIGHT&code!=0)

{x=XR;y=yl+(y2-yl)*(XR-xl)/(x2-xl);}

elseif(BOTTOM&code!=0)

{y=YB;x=xl+(x2-xl)*(YB-yl)/(y2-yl);}

elseif(TOP&code!=0)

{y=YT;x=xl+(x2-xl)*(YT-yl)/(y2-yl);}

3.1.3算法程序(或偽程序)描述

過(guò)程clip描述了這一算法。其中用一個(gè)集合(top,bottom,right,left)

來(lái)表示端點(diǎn)的編碼。具體程序見(jiàn)附錄6。

3.1.4算法流程圖

(略)

3.2中點(diǎn)分割裁剪算法

3.2.1中點(diǎn)分割算法基本原理與實(shí)現(xiàn)步驟

與前一種Cohen-Sutherland算法一樣首先對(duì)線段端點(diǎn)進(jìn)行編碼，

12

LH計(jì)算機(jī)圖形學(xué)作業(yè)：共九道題

并把線段與窗口的關(guān)系分為三種情況：完全可見(jiàn)、完全不可見(jiàn)和線段與

窗口有交。對(duì)前兩種情況，進(jìn)行一樣的處理。對(duì)于第三種情況，用中點(diǎn)

分割的方法求出線段與窗口的交點(diǎn)。

求線段與窗口的交點(diǎn)如下：

設(shè)要裁剪的線段是R』。中點(diǎn)分割算法可分成兩個(gè)過(guò)程平行進(jìn)行，

即從P。出發(fā)找出離P。最近的可見(jiàn)點(diǎn)（圖3.3中的A點(diǎn)），和從R出發(fā)找

出離耳最近的可見(jiàn)點(diǎn)（圖3.3中的B點(diǎn)）。這兩個(gè)最近可見(jiàn)點(diǎn)的連線就

是原線段的可見(jiàn)部分。

從P。出發(fā)找出最近可見(jiàn)點(diǎn)的辦法是先求P°R的中點(diǎn)匕，若P°Pm不能

定為顯然不可見(jiàn)，則取P0Pm代替P0P,,否則取Pn,R代替P0P,，再對(duì)新的P°P|

求中點(diǎn)Pm。重復(fù)上述過(guò)程，直到PR"長(zhǎng)度小于給定的小數(shù)￡為止。

圖3.4是求P。的最近可見(jiàn)點(diǎn)P的算法框圖。求R的最近可見(jiàn)點(diǎn)的算

法框圖是一樣的，只要把p0和P1交換即可。

在顯示時(shí)￡可取成一個(gè)像素的寬度，對(duì)分辨率為2Nx2N的顯示器來(lái)

說(shuō)，上面講的二分的過(guò)程最多只要做N次。由于計(jì)