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

1、計(jì)算機(jī)圖形學(xué)算法基礎(chǔ)作業(yè)姓名： lh 學(xué)院： 理學(xué)院 專業(yè)： 計(jì)算數(shù)學(xué) 時(shí)間： 2010-12-31 lh 的計(jì)算機(jī)圖形學(xué)作業(yè)i目錄1 直線段生成算法綜述.11.1 生成直線的 dda 方法.11.1.1 dda 算法基本原理.11.1.2 dda 算法實(shí)現(xiàn)步驟.11.1.3 dda 算法程序（或偽程序）描述.21.1.4 dda 算法流程圖.21.2 生成直線的 bresenham 算法.31.2.1 bresenham 算法基本原理.31.2.2 bresenham 算法實(shí)現(xiàn)步驟.51.2.3 bresenham 算法程序（或偽程序）描述.51.2.4 bresenham 算法流程圖.51

2、.3 中點(diǎn)畫(huà)線算法.21.3.1 中點(diǎn)畫(huà)線算法基本原理.21.3.2 中點(diǎn)畫(huà)線算法實(shí)現(xiàn)步驟.31.3.3 中點(diǎn)畫(huà)線算法程序（或偽程序）描述.31.3.4 中點(diǎn)畫(huà)線算法流程圖.31.4 生成直線算法的進(jìn)一步改進(jìn).51.5 各種直線生成算法的優(yōu)缺點(diǎn)對(duì)比分析.61.6 直線生成算法的發(fā)展趨勢(shì).72 橢圓的 bresenham 生成算法.7lh 的計(jì)算機(jī)圖形學(xué)作業(yè)ii2.1 橢圓曲率分析.72.2 橢圓方程分析.72.3 橢圓生成算法.92.3.1 算法實(shí)現(xiàn)過(guò)程.92.3.2 算法流程圖.102.3.3 算法程序描述.113 直線段裁剪算法綜述.113.1 sutherland-cohen 裁剪算法.

3、113.1.1 sutherland-cohen 算法基本原理.113.1.2 sutherland-cohen 算法實(shí)現(xiàn)步驟.113.1.3 算法程序（或偽程序）描述.123.1.4 算法流程圖.123.2 中點(diǎn)分割裁剪算法.123.2.1 中點(diǎn)分割算法基本原理與實(shí)現(xiàn)步驟.123.2.2 算法程序（或偽程序）描述.133.2.3 算法流程圖.133.3 梁友棟barskey 算法.143.3.1 梁友棟barskey 算法基本原理與實(shí)現(xiàn)步驟.143.3.2 算法程序（或偽程序）描述.153.3.3 算法流程圖.153.4 快速算法.153.5 其余一些改進(jìn)的直線裁剪算法.16lh 的計(jì)算機(jī)圖

4、形學(xué)作業(yè)iii3.6 各種直線裁剪算法的優(yōu)缺點(diǎn)對(duì)比分析.163.7 直線裁剪算法的發(fā)展趨勢(shì).164 圖形求交技術(shù).164.1 求交點(diǎn)算法.164.1.1 線與線的交點(diǎn)的求法.174.2.2 線與面的交點(diǎn)的求法.184.2 求交線算法.194.3 包含判定算法.214.4 重疊判定算法.264.5 凸包計(jì)算.265 自由曲線曲面造型技術(shù).285.1 bezier 曲線和曲面.285.1.1 bezier 曲線.285.1.2 bezier 曲面.315.2 b 樣條曲線與曲面.325.2.1 b 樣條的遞推定義和性質(zhì).325.2.2 b 樣條曲線.345.2.5 b 樣條曲面.365.3 nur

5、bs 曲線與曲面.375.3.1 nurbs 曲線.375.3.2 非均勻有理 b 樣條（nurbs）曲面.395.4 coons 曲面.40lh 的計(jì)算機(jī)圖形學(xué)作業(yè)iv5.4.1 基本概念.405.4.2 雙線性 coons 曲面.415.4.3 雙三次 coons 曲面.426 cagd 中有關(guān)曲線曲面、拼接技術(shù).44ncng6.1 基本原理.446.2 bezier 曲線的的拼接條件.44001122cgcgcg、6.3 bezier 曲面的的拼接條件.460011cgcg、7 圖形變換技術(shù).487.1 二維圖形幾何變換.497.1.1 平移(translation).497.1.2 旋

6、轉(zhuǎn)(rotation).497.1.3 變比(scaling).507.2 三維圖形幾何變換.517.2.1 平移.517.2.2 旋轉(zhuǎn).517.2.3 變比.547.3 參數(shù)圖形幾何變換.547.3.1 圓錐曲線的幾何變換.547.3.2 參數(shù)曲線、曲面的幾何變換.557.4 投影變換.587.4.1 平行投影(parallel projection).587.4.2 透視投影(perspective projection).60lh 的計(jì)算機(jī)圖形學(xué)作業(yè)v8 圖形消隱算法.618.1 掃描線 z-buffer 算法.618.2 區(qū)域子分割算法.618.3 光線投射算法.628.4 平面公式法

7、.628.5 徑向預(yù)排序法.638.6 徑向排序法.638.7 隔離平面法.638.8 深度排序法.638.9 光線跟蹤法.638.10 z 緩沖區(qū)法.648.11 極值檢測(cè)法.648.12 深度分類方法.648.13 八叉樹(shù)方法.659 圖形學(xué)若干基本算法的實(shí)現(xiàn)研究.65參考文獻(xiàn).68附錄.68lh 計(jì)算機(jī)圖形學(xué)作業(yè)：共九道題1圖形學(xué)算法基礎(chǔ)作業(yè)圖形學(xué)算法基礎(chǔ)作業(yè)1 直線段生成算法綜述1.1 生成直線的 dda 方法1.1.1 dda 算法基本原理dda 是數(shù)字微分分析式（digital differential analyzer）的縮寫(xiě)。設(shè)直線之起點(diǎn)為，終點(diǎn)為，則斜率為：11x ,y（）2

8、2x ,y（）k2121y -ydyk =x -xdx直線中的每一點(diǎn)坐標(biāo)都可以由前一點(diǎn)坐標(biāo)變化一個(gè)增量而得到，即表示xyd ,d為遞歸式：iixiiyx1xdy1yd 并有關(guān)系：yxd m d遞歸式的初值為直線的起點(diǎn)，這樣，就可以用加法來(lái)生成一條直線。11x ,y（）1.1.2 dda 算法實(shí)現(xiàn)步驟具體方法是：按照直線從到的方向不同，分為 8 個(gè)象限（見(jiàn)圖 1.1） 。對(duì)于方向11x ,y（）22x ,y（）在第 1a 象限內(nèi)的直線而言，。對(duì)于方向在第 1b 象限內(nèi)的直線而言，xyd1dm，取值。各象限中直線生成時(shí)的取值列在表 1-1 之中。yxd1d1/ m，xyd , d圖 1.1 直線方

9、向的 8 個(gè)象限圖表 1-1 各象限中直線生成時(shí)的取值列xyd , dlh 計(jì)算機(jī)圖形學(xué)作業(yè)：共九道題2象限dxdy?xdyd1a1b2a2b3a3b4a4btftftftf11/m-1-1/m-1-1/m11/mm1m1-m-1-m-1研究表中的數(shù)據(jù)，可以發(fā)現(xiàn)兩個(gè)規(guī)律：1、當(dāng)時(shí)；否則：dxdyxyd=1, d= mxyd =1/ m d=1，2、的符號(hào)與的符號(hào)相同。這兩條規(guī)律可以導(dǎo)致程序的簡(jiǎn)化。由上x(chóng)yd , ddx, dy述方法寫(xiě)成的程序如附錄 1 所示。其中 steps 變量的設(shè)置，以及等語(yǔ)句，正是利用了上述兩條規(guī)律，使得程序變得簡(jiǎn)練。xyd = dx/steps; d = dy/ste

10、ps使用 dda 算法，每生成一條直線做兩次除法，每畫(huà)線中一點(diǎn)做兩次加法。因此，用 dda 法生成直線的速度是相當(dāng)快的。1.1.3 dda 算法程序（或偽程序）描述具體程序見(jiàn)附錄 1。1.1.4 dda 算法流程圖（略）1.2 中點(diǎn)畫(huà)線算法1.2.1 中點(diǎn)畫(huà)線算法基本原理假定直線斜率在之間，當(dāng)前象素點(diǎn)為，則下一個(gè)象素點(diǎn)有k01pp(x ,y )兩種可選擇點(diǎn)或。若與的中點(diǎn)稱1ppp (x1,y )2ppp (x1,y1)1p2ppp(x1,y0.5)為 m，q 為理想直線與垂線的交點(diǎn)。當(dāng)m 在 q 的下方時(shí)，則取應(yīng)pxx12p為下一個(gè)象素點(diǎn)；當(dāng)m 在 q 的上方時(shí)，則取為下一個(gè)象素點(diǎn)。這就是中1

11、p點(diǎn)畫(huà)線法的基本原理。lh 計(jì)算機(jī)圖形學(xué)作業(yè)：共九道題31.2.2 中點(diǎn)畫(huà)線算法實(shí)現(xiàn)步驟下面討論中點(diǎn)畫(huà)線法的實(shí)現(xiàn)。過(guò)點(diǎn)、的直線段 l 的方程00(x ,y )11(x ,y )式為，其中，f(x,y)axbyc00101ayy ,bxx0110cx yx y，要 判斷中點(diǎn) m 在 q 點(diǎn)的上方還是下方，只要把m 代入，并判斷它f(x,y)的符號(hào)即可。為此，我們構(gòu)造判別式:ppppdf(m)f(x1,y0.5)a(x1)b(y0.5)c 當(dāng)時(shí)， m 在 l(q 點(diǎn))下方，取為下一個(gè)象素；d02p 當(dāng)時(shí)， m 在 l(q 點(diǎn))上方，取為下一個(gè)象素；d01p 當(dāng)時(shí)，選或均可，約定取為下一個(gè)象素 。d

12、01p2p1p注意到是的線性函數(shù)，可采用增量計(jì)算，提高運(yùn)算效率。dppx ,y若當(dāng)前象素處于情況，則取正右方象素,要判下一個(gè)象素位d01ppp (x1,y )置，應(yīng)計(jì)算，增量為 a。1ppppdf(x2,y0.5)a(x2)b(y0.5)cda 若時(shí)，則取右上方象素。要判斷再下一象素，則要d02ppp (x1,y1)計(jì)算，增量為2ppppdf(x2,y1.5)a(x2)b(y1.5)cdab。畫(huà)線從開(kāi)始，的初值ab00(x , y )d，因，所以。00000df(x1,y0.5)f(x ,y )a0.5b00f(x ,y )00da0.5b 由于我們使用的只是的符號(hào)，而且的增量都是整數(shù)，只是初

13、始值包dd含小數(shù)。因此，我們可以用代替來(lái)擺脫小數(shù)，寫(xiě)出僅包含整數(shù)運(yùn)算的算2dd法程序。1.2.3 中點(diǎn)畫(huà)線算法程序（或偽程序）描述具體程序見(jiàn)附錄 21.2.4 中點(diǎn)畫(huà)線算法流程圖 （略）1.3 生成直線的 bresenham 算法1.3.1 bresenham 算法基本原理本算法由 bresenham 在 1965 年提出。設(shè)直線從起點(diǎn)到終點(diǎn)。直11x , y（）22x , y（）線可表示為方程。其中y = kx+b11b = yk x2121y - ydyk =x -xdxlh 計(jì)算機(jī)圖形學(xué)作業(yè)：共九道題4我們討論先將直線方向限于 1a 象限（圖 1.1）在這種情況下，當(dāng)直線光柵化時(shí)，x 每

14、次都增加 1 個(gè)單元，即 。而 y 的相應(yīng)增加應(yīng)當(dāng)小于 1。為了光柵化，iix1= x +1只可能選擇如圖 1.2 兩種位置之一。iy +1圖 1.2 的位置選擇iy +1圖 1.2 中 的位置選擇 或者 iy +1iiy -1= yiiy +1= y +1選擇的原則是看精確值與及的距離 d1 及 d2 的大小而定。計(jì)算式為：yiyiy +1iiiy = m x +1 +b (1.2.1)d1= y- y (1.2.2)d2 = y +1- y (1.2.3)如果，則，否則。因此算法的關(guān)鍵在于簡(jiǎn)便地求出d1-d2 0iiy +1= y +1iiy +1= y的符號(hào)。將式（1.2.1） 、 （1

15、.2.2） 、 （1.2.3）代入，得d1-d2d1-d2iiidyd1-d2 = 2y-2y -1= 2(x +1)-2y +2b-1dx用乘等式兩邊，并以代入上述等式，得dxip = dx d1-d2iiip = 2x dy-2y dx+2dy+dx 2b-1 (1.2.4)是我們用以判斷符號(hào)的誤差。由于在 1a 象限，總大于 0，所以仍舊可以d1-d2dxip用作判斷符號(hào)的誤差。為：ip1iiiip +1= p +2dy-2dx y +1-y (1.2.5)誤差的初值 p1，可將 x1, y1，和 b 代入式（2.1.4）中的而得到：xi, yi1p = 2dy-dx1.3.2 bres

16、enham 算法實(shí)現(xiàn)步驟綜述上面 1.3.1 的推導(dǎo)，第 1a 象限內(nèi)的直線 bresenham 算法思想如下：1、畫(huà)點(diǎn)(x1, y2); dxx2x1; dyy2y1；計(jì)算誤差初值 p1=2dy-dx; i=1；lh 計(jì)算機(jī)圖形學(xué)作業(yè)：共九道題52、求直線的下一點(diǎn)位置：xi+1=xi+1；if pi0 則 yi+1=yi+1；否則 yi+1=yi；3、畫(huà)點(diǎn)（xi+1, yi-1） ；4、求下一個(gè)誤差 pi+1；if pi0 則 pi+1=pi+2dy-2dx;否則 pi+1=pi+2dy；5、i=i+1; if i dy別將 2a,3a 象限的直線和 3b,4b 象限的直線變換到 1a,4a

17、 和 2b,1b 方向去，以求得程序處理的簡(jiǎn)潔。1.3.4 bresenham 算法流程圖（略）1.4 生成直線算法的進(jìn)一步改進(jìn)除過(guò)前面所講到的 3 種基本直線生成算法外，還有一些其它的方法，由于過(guò)多，這里僅列舉幾種如下：（1）二步法。雖然 bresenham 直線生成算法是一效率很高的算法，但是人們?nèi)栽趯ふ腋行５乃惴ā?987 年又有人提出了一種二步法。即每循環(huán)一次不是繪制一個(gè)像素，而是繪制兩個(gè)像素，這樣無(wú)疑可把生成直線的速度提高一倍。（2）改進(jìn)的 bresenham 算法。對(duì)于對(duì)于傳統(tǒng)的直線生成算法，人們往往把注意力集中在算法本身，卻忽略了算法之外的一些有用信息:畫(huà)線之前，從起點(diǎn)坐標(biāo)和終

18、點(diǎn)坐標(biāo)，我們就可以獲知該線段的斜率，由此可進(jìn)一步得出在主軸方向連續(xù)走 l 個(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)線段的生成。lh 計(jì)算機(jī)圖形學(xué)作業(yè)：共九道題6算法實(shí)現(xiàn)：特殊地，對(duì)于水平線()，垂直線()和對(duì)角線()，它們都可直y0 x0 xy接裝人幀緩沖器，而無(wú)需進(jìn)行畫(huà)線算法處理。從以上的描述可以實(shí)現(xiàn)優(yōu)于 bresenham 的直線生成算法。其中待生成直線的已知數(shù)據(jù)為:

19、為線段起點(diǎn)的橫、縱坐標(biāo)；為線段終點(diǎn)的橫、縱坐標(biāo)。11(x ,y )22(x ,y )算法的輸人數(shù)據(jù)為: ，。11(x ,y )22(x ,y )（3）基于類最佳逼近的散步直線生成算法。一種新的直線逼近方法類最佳逼近,基于這種逼近方法,斜率的直線和斜率為的直線具有某種互補(bǔ)性質(zhì)。k0,0.51 k利用該性質(zhì),設(shè)計(jì)出一種新的三步直線方法,該算法揭示了直線計(jì)算的互補(bǔ)性,理論簡(jiǎn)單,精度達(dá)到最好。這種算法改善了 bresenham 算法和雙步算法的計(jì)算效率。該算法對(duì)于硬件實(shí)現(xiàn)將更有益處。除此之外直線生成算法還有對(duì)稱掃描四步增量畫(huà)線算法、基于 bresenham 的高效直線生成集成算法、基于 bresenh

20、am 算法的四步畫(huà)直線算法、基于直線特性的直線生成集成算法、基于自適應(yīng)步長(zhǎng)的直線生成算法、基于等分像素點(diǎn)的直線生成算法、6步直線生成算法、基于對(duì)角線行程的直線生成算法等等。1.5 各種直線生成算法的優(yōu)缺點(diǎn)對(duì)比分析dda 算法的優(yōu)點(diǎn)是：繪制實(shí)數(shù)直線效果好，誤差??；缺點(diǎn)是：實(shí)現(xiàn)較復(fù)雜，不利于硬件實(shí)現(xiàn)。因?yàn)樵撍惴ㄉ婕暗綄?shí)數(shù)乘除法運(yùn)算，y 與 k 必須用浮點(diǎn)數(shù)表示，而且每一步都要對(duì) y 四舍五入后取整。中點(diǎn)畫(huà)線算法優(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

21、運(yùn)算可以用硬件移位實(shí)現(xiàn)。4、bresenham 算法速度很快，并適于用硬件實(shí)現(xiàn)。1.6 直線生成算法的發(fā)展趨勢(shì)（略）2 橢圓的 bresenham 生成算法2.1 橢圓曲率分析橢圓（為沿軸方向的長(zhǎng)半軸長(zhǎng)度，為沿軸方向的cos , sinrat btaxbylh 計(jì)算機(jī)圖形學(xué)作業(yè)：共九道題7短半軸長(zhǎng)度，且） ，曲率為，在第一象限ab22223/2/(sincos)rkabatbt，將對(duì) 求導(dǎo)數(shù)，有，即曲率為減函數(shù)，在點(diǎn)（即）0,/ 2trktd/d0rkt ( ,0)a0t 處的曲率；在點(diǎn)（即）處的曲率。半徑2(0)/r tka b(0, )b/ 2t2(/2)/r tkb a為的圓的曲率為，半

22、徑為的圓的曲率為，兩圓的曲率關(guān)系為a2/a ab2/b b，則兩圓的曲率在橢圓上點(diǎn)與的曲率之間，四者的22/()b ba aab( ,0)a(0, )b關(guān)系為：。22/1/1/a bbab a2.2 橢圓方程分析根據(jù)橢圓及圓的曲率分析，橢圓弧分別由半徑為和的圓弧逼近生成。為了更ab準(zhǔn)確的由圓弧生成橢圓弧，在橢圓弧上確定一點(diǎn)，將橢圓弧分成曲率較小和曲率較0p大的兩段，橢圓方程為：。222222f x,y0b xa ya b其中為沿軸方向的長(zhǎng)半軸長(zhǎng)度，為沿軸方向的短半軸長(zhǎng)度，且axby。由于橢圓的對(duì)稱性，這里只要討論第一象限橢圓弧的生成。將橢圓弧0ab分為上下兩部分，以弧上曲率為-1 的點(diǎn)（即法向

23、量?jī)蓚€(gè)分量相等的點(diǎn)）作為分界。該橢圓上一點(diǎn)處的法向量為：( , )x y22ffn( , )ij2i 2jx yb xa yxy結(jié)合橢圓方程可計(jì)算出分界點(diǎn)的坐標(biāo)為：0p。222222(/,/)aabbab以點(diǎn)為分界點(diǎn)，將第一象限的圓弧分成曲率較大和較小的兩段弧。如圖 2.1 所0p示，的橢圓弧，與半徑為的圓在點(diǎn)到222/, ybabba1t (0, )a的圓弧上對(duì)應(yīng)。在橢圓弧上任取一點(diǎn)，過(guò)作垂222222t (/,/)aababab1q1qlh 計(jì)算機(jī)圖形學(xué)作業(yè)：共九道題8直線與圓交于點(diǎn)，連接圓心與點(diǎn)，與軸的夾角為。則1p1py橢圓的參數(shù)方程可表示為：sin,cos.xayb圓的參數(shù)方程可表示

24、為：sin,cos.xaya對(duì)于同一 ，橢圓弧上存在唯一的點(diǎn)與圓弧上的點(diǎn)對(duì)應(yīng)，并且對(duì)應(yīng)點(diǎn)的坐標(biāo)存在如下關(guān)系：,( / )y.xxyb a 圖 2.1 圓弧與橢圓弧對(duì)應(yīng)點(diǎn)之一 圖 2.2 圓弧與橢圓弧對(duì)應(yīng)點(diǎn)之一如圖 2.2 所示，半徑為的圓上，從點(diǎn)到b222223t (/,/)aabbbab的圓弧與橢圓上的橢圓弧對(duì)應(yīng)，在橢圓弧上任取一點(diǎn)4t ( ,0)b222(0,/)ybab，過(guò)作垂直線與圓交于點(diǎn)，連接圓心與點(diǎn)，與軸的夾角為。則2q2q2p2py橢圓的參數(shù)方程可表示為：sin,cos.xayb圓的參數(shù)方程可表示為：sin,cos.xbyblh 計(jì)算機(jī)圖形學(xué)作業(yè)：共九道題9對(duì)于同一 ，橢圓弧上存

25、在唯一的點(diǎn)與圓弧上的點(diǎn)對(duì)應(yīng)，并且對(duì)應(yīng)點(diǎn)的坐標(biāo)存在如下關(guān)系：( /b) ,y.xaxy2.3 橢圓生成算法當(dāng)圓弧上的點(diǎn)從沿著圖 2.1、圖 2.2 的對(duì)應(yīng)關(guān)系方向變化到時(shí)，橢圓( ,0)a( ,0)b弧上相對(duì)應(yīng)的點(diǎn)也從該方向變化到。( ,0)a2.3.1 算法實(shí)現(xiàn)過(guò)程1、計(jì)算分界點(diǎn)。000p (x ,y )2、用 bresenham 算法生成兩段圓弧、。半徑為，1c2c1ca；半徑為，。2220,/xaab2cb222y0,/bab3、將圓弧進(jìn)行比例變換：方向的比例系數(shù)為 1，方向的比例系數(shù)為1cxy；將圓弧進(jìn)行比例變換：方向的比例系數(shù)為，方向的比例系數(shù)/b a2cx/a by為 1。4、如圖

26、2.3，已知橢圓上在第一象限的點(diǎn)，則橢圓上另外三個(gè)象限與q(x,y)點(diǎn)對(duì)稱的點(diǎn)分別為，因此只要畫(huà)出在第一象限的q(x,y)( x,y),( x,y),(x,y)圖形，即可得到整個(gè)橢圓的圖形。圖 2.3 橢圓對(duì)稱性2.3.2 算法流程圖橢圓的 bresenham 算法流程圖如下：lh 計(jì)算機(jī)圖形學(xué)作業(yè)：共九道題10計(jì)算分界點(diǎn)000px ,y用 bresenham 算法計(jì)算圓弧xyt ,t計(jì)算對(duì)應(yīng)圓弧上的點(diǎn)結(jié)束用 bresenham 算法計(jì)算圓弧xyt ,tynyn圖 2.4 橢圓的 bresenham 算法流程圖2.3.3 算法程序描述具體程序?qū)崿F(xiàn)見(jiàn)附錄 5。3 直線段裁剪算法綜述裁剪裁剪：確定

27、圖形中哪些部分落在顯示區(qū)之內(nèi)，哪些落在顯示區(qū)之外,以便只顯示落在顯示區(qū)內(nèi)的那部分圖形。這個(gè)選擇過(guò)程稱為裁剪。直線段裁剪算法是復(fù)雜圖元裁剪的基礎(chǔ)。復(fù)雜的曲線可以通過(guò)折線段來(lái)近似，從而裁剪問(wèn)題也可以化為直線段的裁剪問(wèn)題。3.1 sutherland-cohen 裁剪算法3.1.1 sutherland-cohen 算法基本原理sutherlandcohen 算法分成兩步。第一步是判斷直線段是否完全在窗口內(nèi)，若開(kāi)始橢圓上點(diǎn) y 的坐標(biāo)大于0y橢圓上點(diǎn)的 y 坐標(biāo)大于 0lh 計(jì)算機(jī)圖形學(xué)作業(yè)：共九道題11在則該線段稱為完全可見(jiàn)的；或可顯然的決定線段完全在窗口的外邊，稱為完全不可見(jiàn)；對(duì)不能判斷完全可見(jiàn)

28、或完全不可見(jiàn)的線段則要進(jìn)行第二步處理。這時(shí)需要計(jì)算出直線段和窗口邊界的一個(gè)交點(diǎn)，這個(gè)交點(diǎn)把直線分成兩段，把其中一段顯然完全不可見(jiàn)的線段拋棄，對(duì)余下的部分再作第一步判斷，重復(fù)上述過(guò)程，直到直線段最后余下的部分可以用第一步的判斷得出肯定結(jié)論為止。3.1.2 sutherland-cohen 算法實(shí)現(xiàn)步驟基本思想：對(duì)于每條線段分為三種情況處理分為三種情況處理:21pp（1）若完全在窗口內(nèi)，則顯示該線段，簡(jiǎn)稱“取”之。21pp21pp（2）若明顯在窗口外，則丟棄該線段，簡(jiǎn)稱“棄”之。21pp（3）若線段不滿足“取”或 “棄”的條件，則在交點(diǎn)處把線段分為兩段。其中一段完全在窗口外，可棄之。然后對(duì)另一段重

29、復(fù)上述處理。為快速判斷，采用如下編碼方法：每個(gè)區(qū)域賦予 4 位編碼（如圖 3.1 所示）：lrbtcccc其中：otheryycotheryycbt0101minmaxotherxxcotherxxclr0101minmax 100110000001101000000010010001010110 xlxrytyb 圖 3.1 區(qū)域編碼 圖 3.2 線段不能用編碼確定若完全在窗口內(nèi) code1=0,且 code2=0,則“取”21pp若明顯在窗口外 code1&code20，則“棄” 21pp在交點(diǎn)處把線段分為兩段。其中一段完全在窗口外，可棄之。然后對(duì)另一段重復(fù)上述處理。xlh 計(jì)算機(jī)圖形學(xué)作

30、業(yè)：共九道題12計(jì)算線段與窗口邊界的交點(diǎn) 222111,yxpyxpif(left&code !=0)x=xl;y=y1+(y2-y1)*(xl-x1)/(x2-x1);else if(right&code !=0)x=xr;y=y1+(y2-y1)*(xr-x1)/(x2-x1);else if(bottom&code !=0) y=yb;x=x1+(x2-x1)*(yb-y1)/(y2-y1); else if(top & code !=0) y=yt;x=x1+(x2-x1)*(yt-y1)/(y2-y1);3.1.3 算法程序（或偽程序）描述過(guò)程 clip 描述了這一算法。其中用一個(gè)集

31、合(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)行編碼，并把線段與窗口的關(guān)系分為三種情況：完全可見(jiàn)、完全不可見(jiàn)和線段與窗口有交。對(duì)前兩種情況，進(jìn)行一樣的處理。對(duì)于第三種情況，用中點(diǎn)分割的方法求出線段與窗口的交點(diǎn)。求線段與窗口的交點(diǎn)如下：設(shè)要裁剪的線段是。中點(diǎn)分割算法可分成兩個(gè)過(guò)程平行進(jìn)行，即從出發(fā)找01p p0p出離最近的可見(jiàn)點(diǎn)（圖 3.3 中的 a 點(diǎn)） ，和從出發(fā)找出離最近的可見(jiàn)點(diǎn)（圖0p1p

32、1p3.3 中的 b 點(diǎn)） 。這兩個(gè)最近可見(jiàn)點(diǎn)的連線就是原線段的可見(jiàn)部分。從出發(fā)找出最近可見(jiàn)點(diǎn)的辦法是先求的中點(diǎn)，若不能定為顯然不0p01p pmp0mp p可見(jiàn)，則取代替，否則取代替，再對(duì)新的求中點(diǎn)。重復(fù)上述0mp p01p pm1p p01p p01p pmp過(guò)程，直到長(zhǎng)度小于給定的小數(shù) 為止。1mpp圖 3.4 是求的最近可見(jiàn)點(diǎn)的算法框圖。求的最近可見(jiàn)點(diǎn)的算法框圖是一樣0pp1p的，只要把和交換即可。0p1p在顯示時(shí) 可取成一個(gè)像素的寬度，對(duì)分辨率為的顯示器來(lái)說(shuō)，上面講的nn22二分的過(guò)程最多只要做 n 次。由于計(jì)算機(jī)過(guò)程只要做加法和除 2，所以特別適合用硬件來(lái)實(shí)現(xiàn)。lh 計(jì)算機(jī)圖形學(xué)作

33、業(yè)：共九道題13如果允許兩個(gè)找最近點(diǎn)的過(guò)程平行進(jìn)行，這樣的話可使裁剪速度加快，增加算法效率。圖 3.3 中點(diǎn)分割算法3.2.2 算法程序（或偽程序）描述具體程序見(jiàn)附錄 7。3.2.3 算法流程圖中點(diǎn)分割算法框圖如圖 3.4。可見(jiàn)否?0pm01p(pp )/ 21mpp ?顯然不可見(jiàn)01p p顯然不可見(jiàn)?0mp p0mpp1mpp0ppexit原線完全不可見(jiàn)0mppexit否否否否是是是是圖 3.4 中點(diǎn)分割算法框圖lh 計(jì)算機(jī)圖形學(xué)作業(yè)：共九道題143.3 梁友棟barskey 算法3.3.1 梁友棟barskey 算法基本原理與實(shí)現(xiàn)步驟設(shè)要裁剪的線段是，的坐標(biāo)是。和窗口邊界交于01p pip

34、iix ,y ,i0,101p pa、b、c、d 四點(diǎn)，見(jiàn)圖 3.5。算法基本思想是從 a，b 和三點(diǎn)中找出最靠近的點(diǎn)，0p1p圖 3.5 中要找的點(diǎn)是，從 c，d 和三點(diǎn)中找出最靠近的點(diǎn)，圖 3.5 中要找的點(diǎn)0p1p0p是 c 點(diǎn)。那么就是上的可見(jiàn)部分。0p c01p pxyytybxlxrabcd0p1p圖 3.5 是可見(jiàn)部分0p c具體計(jì)算時(shí)要把寫(xiě)成參數(shù)方程01p p00 xxx tyyy t其中。把窗口邊界的四條邊分成兩類，一類稱為始邊，1010 xxx , yyy 另一類稱為終邊。參數(shù)化形式寫(xiě)出裁剪條件:l1rb1txxuxxyyuyy 可以統(tǒng)一表示為形式：kkqup 111221

35、311441pxqxxlpxqxrxpyqyybpyqyty 當(dāng)且，則線段完全在邊界外，則該線段平行于裁剪邊界并0kp0kq0kq且在窗口內(nèi)；當(dāng)?shù)那闆r下：當(dāng),線段從裁剪邊界延長(zhǎng)線的外部延伸到內(nèi)部；當(dāng)0kp0kp,線段從裁剪邊界延長(zhǎng)線的內(nèi)部延伸到外部。kp0對(duì)于每條直線，可以計(jì)算出參數(shù)和，它們定義了在裁剪矩形內(nèi)的線段部分，1u2ulh 計(jì)算機(jī)圖形學(xué)作業(yè)：共九道題15的值由線段從外到內(nèi)遇到的矩形邊界所決定。對(duì)這些邊界計(jì)算。1u0pkkkpqr/取 0 和各個(gè)值之中的最大值。的值由線段從內(nèi)到外遇到的矩形邊界所決定1ukr2u。對(duì)這些邊界計(jì)算。取 1 和各個(gè)值之中的最小值。如果，0pkkkpqr/2u

36、kr21uu 則線段完全落在裁剪窗口之外，被舍棄。否則裁剪線段由參數(shù)的兩個(gè)值，計(jì)算u1u2u出來(lái)。3.3.2 算法程序（或偽程序）描述具體程序見(jiàn)附錄 8。3.3.3 算法流程圖（略）3.4 快速算法 在實(shí)際繪圖時(shí)，常出現(xiàn)大部分線段是可見(jiàn)的，或大部分線段為顯然不可見(jiàn)。因而用最少的操作去判斷被裁剪的線段是否屬于這兩種情況則可以提高裁剪的效率。此外，盡量減少比較和四則運(yùn)算，也是提高效率的重要措施。這樣會(huì)使程序長(zhǎng)一點(diǎn)，但由于效率高，在軟件包中值得采用。用這樣的算法確定一根顯然不可見(jiàn)線段平均只要做3.6 次比較，確定一根完全可見(jiàn)線段要用 8 次比較，而用 sutherland-cohen 算法做同樣工作

37、則分別要做 11 次和 10 次比較?？焖偎惴ㄔ谧羁斓那闆r下要和四條邊求交點(diǎn)，這要用 10 次加減法、5 次乘除法和 13 次比較。采用 sutherland-cohen 算法要做 16次加減法、8 次乘除法和 35 次比較。此外后者還要多次調(diào)用過(guò)程合作集合運(yùn)算，這些都使它比快速算法效率低。3.5 其余一些改進(jìn)的直線裁剪算法除過(guò)前面所講到的 4 種基本直線裁剪算法外，還有一些其它的裁剪方法，由于過(guò)多，這里僅列舉幾種如下：（1）具有最少算術(shù)運(yùn)算量的二維線裁剪算法。見(jiàn)文獻(xiàn)：王駿，梁友棟，彭群生，具有最少算術(shù)運(yùn)算量的二維線裁剪， 計(jì)算機(jī)學(xué)報(bào) ，1991 年第 7 期。（2）一個(gè)有效的多邊形窗口的線裁

38、剪算法。見(jiàn)文獻(xiàn)：劉勇奎等，一個(gè)有效的多邊形窗口的線裁剪， 計(jì)算機(jī)學(xué)報(bào) ，1999 年第 11 期。（3）一種基于幾何變換的高效的線裁剪新算法。見(jiàn)文獻(xiàn)：汪亂，吳銳迅，蔡士杰。一種基于幾何變換的高效的線裁剪新算法。 軟件學(xué)報(bào) ，1998，9(10): 728 一733。（4）任意多邊形窗口的線裁剪算法。見(jiàn)文獻(xiàn)：孫巖，唐棣:任意多邊形窗口的線lh 計(jì)算機(jī)圖形學(xué)作業(yè)：共九道題16裁剪， 2000 年圖形學(xué)會(huì)議?？?。3.6 各種直線裁剪算法的優(yōu)缺點(diǎn)對(duì)比分析sutherland-cohen 直線裁剪算法要計(jì)算直線段與窗口邊界的交點(diǎn)，這不可避免地要進(jìn)行大量的乘除運(yùn)算，必會(huì)降低程序的執(zhí)行效率。而中點(diǎn)分割裁剪

39、算法卻只需用到加法和除 2 運(yùn)算，而除 2 運(yùn)算在計(jì)算機(jī)中可以簡(jiǎn)單地用右移一位來(lái)實(shí)現(xiàn)，從而提高算法的效率。所以特別適合硬件實(shí)現(xiàn)，同時(shí)也適合于并行計(jì)算。3.7 直線裁剪算法的發(fā)展趨勢(shì)（略）4 圖形求交技術(shù)4.1 求交點(diǎn)算法求交點(diǎn)可以分兩種情況：求線與線的交點(diǎn)以及求線與面的交點(diǎn)。4.1.1 線與線的交點(diǎn)的求法1、直線段與直線段的交點(diǎn)假設(shè)二條直線的端點(diǎn)分別為則它們可以用向量形式表示為：p1p2q1q2， p t = a+bt (0t1)q s = c+ds (0s1) 其中，。ap1bp2p1cq1dq2q1，構(gòu)造方程a+bt = c+ds (4.1.1)對(duì)三維空間中的直線段來(lái)說(shuō)，上述方程實(shí)際上是一

40、個(gè)二元一次方程組，由三個(gè)方程式組成。可以從其中兩個(gè)解出，再用第三個(gè)驗(yàn)證解的有效性：若第三個(gè)方程成s,t立則說(shuō)明找到了解，否則說(shuō)明兩條直線不相交。當(dāng)所得的解是有效解時(shí)，可用iit , s（）二個(gè)線段方程之一計(jì)算交點(diǎn)坐標(biāo)，例如。 iip t= a+bt我們還可以根據(jù)向量的基本性質(zhì)，直接計(jì)算 s 與 t：對(duì)（4.1.1）兩邊構(gòu)造點(diǎn)積得c x da+bt = c x dc+ds（）（）（）由于 cxd 同時(shí)垂直于 c 和 d，等式右邊為零。故有(c d) at(c d) b 類似地有l(wèi)h 計(jì)算機(jī)圖形學(xué)作業(yè)：共九道題17(ab) cs(ab) d 完整的算法還應(yīng)判斷無(wú)解與無(wú)窮多解（共線）的情形，以及考慮

41、數(shù)值計(jì)算誤差造成的影響。2、直線段與二次曲線的交點(diǎn)不失一般性，考慮平面上一條直線與同平面的一條二次曲線的交。假設(shè)曲線方程為 ，f x,y = 0直線段方程為 , 11x, y = x +tdx, y +tdy則在交點(diǎn)處有 。11f x +tdx, y +tdy = 0當(dāng)曲線為二次曲線時(shí)，上述方程可寫(xiě)為2atbtc0用二次方程求根公式即可解出 t 值。3、圓錐曲線與圓錐曲線的交點(diǎn)圓錐曲線有代數(shù)法表示、幾何法表示與參數(shù)法表示。在進(jìn)行一對(duì)圓錐曲線的求交時(shí)，把其中一條圓錐曲線用代數(shù)/幾何法表示為隱函數(shù)形式，另一條表示為參數(shù)形式（如二次 nurbs 曲線） 。將參數(shù)形式代入隱函數(shù)形式可得關(guān)于參數(shù)的四次方

42、程，可以使用四次方程的求根公式解出交點(diǎn)參數(shù)。得到交點(diǎn)后可再驗(yàn)證交點(diǎn)是否在有效的圓錐曲線段上。4.2.2 線與面的交點(diǎn)的求法1、直線段與平面的交點(diǎn)（如圖 4.1）圖 4.1 線段與平面求交lh 計(jì)算機(jī)圖形學(xué)作業(yè)：共九道題18考慮直線段與無(wú)界平面的求交問(wèn)題。把平面上的點(diǎn)表示為，p u,w = a+ub+wc直線段上的點(diǎn)表示為，二者的交點(diǎn)記為。假設(shè)線段不平行于平面，則 q t = d+ter它們交于，即 r = p u,w = q ta+ub+wc = d+te等式兩邊點(diǎn)乘，得b x c（）b x ca+ub+wc = b x cd+te（）（）（）（）由于既垂直于 b，又垂直于 c，故有b x c

43、b x ca = b x cd+te（）（）（）可解出(b c) a(b c) dt(b c) e類似求得(c e) d (c e) a(c e) bu(b e) d (b e) a(b e) c如果是直線與平面區(qū)域求交點(diǎn)，則要進(jìn)一步判斷點(diǎn)是否在平面上的有效區(qū)域中，其算法可參見(jiàn) 4.2 節(jié)。2、圓錐曲線與平面的交點(diǎn)圓錐曲線與平面求交時(shí)，可以把圓錐曲線表示為參數(shù)形式，并把圓錐曲線的參數(shù)形式代入平面方程，即可得到參數(shù)的二次方程進(jìn)行求解。3、圓錐曲線與二次曲面的交點(diǎn) 圓錐曲線與二次曲面求交時(shí)，可把圓錐曲線的參數(shù)形式代入二次曲面的隱式方程，得到參數(shù)的四次方程，用求根公式求解。4.2 求交線算法求交線顯

44、然是指求面與面的交線，下面討論幾種常見(jiàn)的情況。1、平面與平面的交線在 cad 中一般使用平面上有界區(qū)域。先考慮最簡(jiǎn)單的情形。兩個(gè)平面區(qū)域分別由定義。如果它們不共面而且不分離，則必交于一直線p u,w , q s,t , u, w, s, t 0, 1段。這條直線必落在所定義的無(wú)限直線上。注意這是個(gè)含有四個(gè)p u,w -q s,t = 0未知數(shù)，三個(gè)方程式的方程組，只要分別與八條邊界線方程：聯(lián)立，即可求出線段的兩個(gè)端點(diǎn)的參數(shù)。u = 0, u =1, w = 0, w =1, s = 0, s =1, t = 0, t =1在上述方程組中，只要找到兩組解，就可以不再對(duì)剩余其它方程組求解。找到的兩

45、組lh 計(jì)算機(jī)圖形學(xué)作業(yè)：共九道題19解就是所求的交線段端點(diǎn)參數(shù)。當(dāng)兩個(gè)一般的多邊形（即既可能是凸的，也可能是凹的，甚至可能帶有內(nèi)孔）相交時(shí)，可能有多段交線。我們可以把兩個(gè)多邊形分別記為 a 和 b，用如下的算法求出它們的交線：（1）把 a 的所有邊與 b 求交，求出所有有效交點(diǎn)；（2）把 b 的所有邊與 a 求交，求出所有有效交點(diǎn)；（3）把所有交點(diǎn)先按 y，再按 x 的大小進(jìn)行排序；（4）把每對(duì)交點(diǎn)的中點(diǎn)與 a 和 b 進(jìn)行包含性檢測(cè)，若該中點(diǎn)即在 a 中又在 b 中，則該對(duì)交點(diǎn)定義了一條交線段。2、平面與二次曲面的交線求平面與二次曲面的交線有兩種方法：代數(shù)法和幾何法。用代數(shù)法考慮平面與二次

46、曲面求交問(wèn)題時(shí)，可以把二次曲面表示為代數(shù)形式：222ax +by +cz +2dxy+2eyz+2fxz+2gx+2hy+2iz+j = 0可以通過(guò)平移與旋轉(zhuǎn)坐標(biāo)變換把平面變?yōu)?xoy 平面，對(duì)二次曲面進(jìn)行同樣的坐標(biāo)變換。由于在新坐標(biāo)系下平面的方程為，所以新坐標(biāo)系下二次曲面方程中，把z0含 z 項(xiàng)都去掉即為平面與二次曲面的交線方程（在新坐標(biāo)系下） 。對(duì)該交線方程進(jìn)行一次逆坐標(biāo)變換即可獲得在原坐標(biāo)系下的交線方程。在具體實(shí)現(xiàn)時(shí)，交線可以用二元二次方程系數(shù)表示（代數(shù)表示） ，輔之以局部坐標(biāo)系到用戶坐標(biāo)系的變換矩陣。這種方法的缺點(diǎn)是，每當(dāng)需要使用這些交線時(shí)，都要進(jìn)行坐標(biāo)變換。例如，判斷一個(gè)空間點(diǎn)是否在

47、交線上，必須先對(duì)它進(jìn)行坐標(biāo)變換，變到平面上，再進(jìn)行檢測(cè)。需要z0繪制該交線時(shí)，也要先在局部坐標(biāo)系下求出點(diǎn)坐標(biāo)，再變換到用戶坐標(biāo)系下的坐標(biāo)。所以交線采用另一種方法（幾何表示）更合理。幾何方法存儲(chǔ)曲線的類型（橢圓、拋物線或雙曲線） ，以及定義參數(shù)（中心點(diǎn)、對(duì)稱軸、半徑等大小尺寸）的數(shù)值信息，使用局部坐標(biāo)系到用戶坐標(biāo)系的變換，把局部坐標(biāo)系下的定義參數(shù)變換到用戶坐標(biāo)系直接使用。這第二種方法使用較少的變換，但需要用計(jì)算來(lái)判斷曲線的種類，及計(jì)算曲線的定義參數(shù)。由于浮點(diǎn)運(yùn)算的不精確性，容易發(fā)生判錯(cuò)類型以及定義參數(shù)誤差過(guò)大的問(wèn)題。當(dāng)平面與二次曲面的交線需要精確表示時(shí)，往往采用幾何法求交。二次曲面采用幾何表示，

48、平面與二次曲面求交時(shí)，根據(jù)它們的相對(duì)位置與角度（根據(jù)定義參數(shù)） ，直接判斷交線類型，其準(zhǔn)確性大大優(yōu)于用代數(shù)法計(jì)算分類的方法。幾何法不需要對(duì)面進(jìn)行變換，所以只要通過(guò)很少的計(jì)算就可以得到交線的精確描述。由于存儲(chǔ)的信息是具有幾何意義的，所以判斷相等性、相對(duì)性等問(wèn)題時(shí)，可以確定有幾何意義的容差。下面以平面一球求交為例，說(shuō)明幾何法求交算法。lh 計(jì)算機(jī)圖形學(xué)作業(yè)：共九道題20平面用一個(gè)記錄 p 表示，p 的兩子域 p.b, p.w 分別代表平面上一點(diǎn)與平面法向量。球面用記錄 s 表示。它的兩個(gè)子域 s.c, s.r 分別代表球面中心和半徑。則可寫(xiě)出平面與球面相交的算法如下：plane_sphere_in

49、tersect(p, s)plane p;sphere s;d=球面中心到平面的有向距離；if(abs(d)=s.r) 二個(gè)面相交于一（切）點(diǎn) s.c-d * p.w;else if (abs(d)s.r) 兩個(gè)面無(wú)交；else 所求交線是圓。其圓半，半徑，圓所在平面法向量為c=s.c-d * p. w;r=sqr t(s.r2-d2);w=p.w;一個(gè)平面與一個(gè)圓柱面可以無(wú)交、交于一條直線（切線） 、二條直線、一個(gè)橢圓或一個(gè)圓，可以用兩個(gè)面的定義參數(shù)求出它們的相對(duì)位置關(guān)系和相對(duì)角度關(guān)系，進(jìn)而判斷其交屬于何種情況，并求出交線的定義參數(shù)。平面與圓錐的交線也可類似求出。3、平面與參數(shù)曲面的交線 最

50、簡(jiǎn)單的方法是把參數(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)變換對(duì)平面進(jìn)行坐標(biāo)變換，使平面成為新坐標(biāo)系下的平面。再用相同的變換應(yīng)用于參數(shù)曲面方程得到參數(shù)曲面在新坐標(biāo)系下的方程xoy*x , y , z= xs,t , ys,t , zs,t（）（）由此得交線在新坐標(biāo)系下的方程為。*zs,t0lh 計(jì)算機(jī)圖形學(xué)作業(yè)：共九道題214.3 包含判定算法在進(jìn)行圖形求交時(shí)，常常需要判定兩個(gè)圖形間是否有包含關(guān)系。如點(diǎn)是否包含在

51、線段、平面區(qū)域、三維形體中，線段是否包含在平面區(qū)域、三維形體中，等等。許多包含判定問(wèn)題可轉(zhuǎn)化為點(diǎn)的包含判定問(wèn)題，如判斷線段是否在平面上可以轉(zhuǎn)化為判斷其兩端點(diǎn)是否在平面上。因此下面主要討論關(guān)于點(diǎn)的包含判定算法。判斷點(diǎn)與線段的包含關(guān)系，也就是判斷點(diǎn)與線的最短距離是否位于容差范圍內(nèi)。造型中常用的線段有三種：1、直線段；2、圓錐曲線段（主要是圓?。?；3、參數(shù)曲線（主要是 bezier，b 樣條與 nurbs 曲線） 。點(diǎn)與面的包含判定也類似地分為三種情況。下面分別討論。1、點(diǎn)與直線段的包含判定假設(shè)點(diǎn)坐標(biāo)為，直線段端點(diǎn)為，則點(diǎn) p 到線p x,y,z1111p x ,y ,z2222px ,y ,z段

52、的距離的平方為12pp 2222211211211111222212121xxxxyyyyzzzzd2xxyyzzxxyyzz當(dāng)時(shí)，認(rèn)為點(diǎn)在線段（或其延長(zhǎng)線）上，這時(shí)還需進(jìn)一步判斷點(diǎn)是否落在直線d20段的有效區(qū)間內(nèi)。只要對(duì)坐標(biāo)分量進(jìn)行比較，假設(shè)線段兩端點(diǎn)的 x 分量不等（否則所有分量均相等，那么線段兩端點(diǎn)重合，線段退化為一點(diǎn)） ，那么當(dāng)與反號(hào)1xx2xx時(shí)，點(diǎn) p 在線段的有效區(qū)間內(nèi)。2、點(diǎn)與圓錐曲線段的包含判定以圓弧為例，假設(shè)點(diǎn)的坐標(biāo)為，圓弧的中心為，半徑為 ，起x, y, z000 x , y , z（）r始角，終止角。這些角度都是相對(duì)于局部坐標(biāo)系 x 軸而言。圓弧所在平面為12 ax+b

53、y+cz+d = 0先判斷點(diǎn)是否在該平面上，若不在，則點(diǎn)不可能被包含。若在，則通過(guò)坐標(biāo)變換，把問(wèn)題轉(zhuǎn)換到二維的問(wèn)題。給定中心為，半徑為 ，起始角，終止角的圓弧，對(duì)平面上一點(diǎn)00 x , y（）r12，判斷 p 是否在圓弧上，可分二步進(jìn)行。p x, y（）第一步判斷 p 是否在圓心為，半徑為 的圓的圓周上，即下式是否成立：00 x , y（）r 2200()()rxxyylh 計(jì)算機(jī)圖形學(xué)作業(yè)：共九道題22第二步判斷 p 是否在有效的圓弧段內(nèi)。3、點(diǎn)與參數(shù)曲線的包含判定設(shè)點(diǎn)坐標(biāo)為，參數(shù)曲線為。點(diǎn)也參數(shù)曲線的求p x, y, z q t = x t , y t , z t交計(jì)算包括三個(gè)步驟：（1）

54、計(jì)算參數(shù) 值，使到的距離最??；tp q t（2）判斷 是否在有效參數(shù)區(qū)間內(nèi)（通常為） ；t01，（3）判斷與的距離是否小于 。若（2） ， （3）步的判斷均為“是” ，則 q tp 點(diǎn)在曲線上；否則點(diǎn)不在曲線上。第一步應(yīng)計(jì)算 ，使得最小，即t p q t 2r t = p-q tp-q t= p-q t最小根據(jù)微積分知識(shí)，在該處即r (t) = 0 q (t) p-q t= 0用數(shù)值方法解出 值，再代入曲線參數(shù)方程可求出曲線上對(duì)應(yīng)點(diǎn)的坐標(biāo)。第（2） 、t（3）步的處理比較簡(jiǎn)單，不再詳述。4、點(diǎn)與平面區(qū)域的包含判定設(shè)點(diǎn)坐標(biāo)為，平面方程為。則點(diǎn)到平面的距離為p x, y, zax+by+cz+d

55、= 0 222ax+by+cz+dr =a +b +c若 ，則認(rèn)為點(diǎn)在平面上，否則認(rèn)為點(diǎn)不在平面上。在造型系統(tǒng)中，通常使r用平面上的有界區(qū)域作為形體的表面。在這種情況下，對(duì)落在平面上的點(diǎn)還應(yīng)進(jìn)一步判別它是否落在有效區(qū)域內(nèi)。若點(diǎn)落在該區(qū)域內(nèi)，則認(rèn)為點(diǎn)與該面相交，否則不相交。下面以平面區(qū)域多邊形為例，介紹有關(guān)算法。判斷平面上一個(gè)點(diǎn)是否包含在同平面的一個(gè)多邊形內(nèi)，有許多種算法，這里僅介紹常用的三種：叉積判斷法、夾角之和檢驗(yàn)法以及交點(diǎn)計(jì)數(shù)檢驗(yàn)法。（1）叉積判斷法假設(shè)判斷點(diǎn)為。多邊形頂點(diǎn)按順序排列為。如圖 4.2 所示。令0p12nppp。那么，在多邊形內(nèi)的充要條件是叉積ii0n1vpp , i1, 2

56、, , n, v1v 0p的符號(hào)相同。叉積判斷法僅適用于凸多邊形。當(dāng)多邊形為iiv x v +1 i1, 2, , n、凹時(shí)，盡管點(diǎn)在多邊形內(nèi)也不能保證上述叉積符號(hào)都相同。這時(shí)可采用后面介紹的兩lh 計(jì)算機(jī)圖形學(xué)作業(yè)：共九道題23種方法。圖 4.2 叉積判斷法（2）夾角之和檢驗(yàn)法假設(shè)某平面上有點(diǎn)和多邊形，如圖 4.3 所示。將點(diǎn)分別與相連，0p12345pp p p p0pip構(gòu)成向量。假設(shè)角 。如果，則點(diǎn)在多邊形之外，i0vppi0iipp p1 051 ii 0p如圖 4.3(a)所示。如果，則點(diǎn)在多邊形之內(nèi)，如圖 4.3(b)所示?？?251 ii0pi通過(guò)下列公式計(jì)算：令, ，則，所以

57、iiisvxv1iiicv v1 iiitgs /c且的符號(hào)即代表角度的方向。iiiarctg s /ci圖 4.3 夾角之和檢驗(yàn)法在多邊形邊數(shù)不太多（ 0 x,y,z（）見(jiàn)的或隱的） ；如果，則觀察點(diǎn)在凸型多面體外部（稱該表面是可見(jiàn)） ，ax+by+cz+d 0，則平面式可見(jiàn)面，應(yīng)被畫(huà)出。d abs(dy) steps=abs(dx);else steps=abs (dy);delta_x=(float)dx / (float)steps;delta_y=(float)dy / (float)steps;x=xa;y=ya;set_pixel(x, y, c);for (k=1; k=ste

58、ps; k+)x+=delta_x;y+=delta_y;set_pixel(x, y, c); 附錄附錄 2 2：中點(diǎn)畫(huà)線算法程序：中點(diǎn)畫(huà)線算法程序void midpoint line (int x0,int y0,int x1, int y1,int color) int a, b, d1, d2, d, x, y； 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 (xx1) if (d=0) /*準(zhǔn)備 x 或 y 的單位遞變值。*/ inc=1;elseinc=-

59、1;if (abs(dx)abs(dy) if(dx0) tmp=x1; /*將 2a, 3a 象限方向*/ x1=x2; /*的直線變換到 1a, 4a*/ x2=tmp; tmp=y1; /*象限方向去*/ y1=y2; dx=-dy; dy=-dy; lh 計(jì)算機(jī)圖形學(xué)作業(yè)：共九道題68 p=2*dy-dx; const1=2*dy; /*注意此時(shí)誤差的*/ const2=2*(dy-dy); /*變化參數(shù)取值. */ x=x1; y=y1; set_pixel(x, y, c); while (xx2) x+; if (p0) p+=const1; else y+=inc; p+=co

60、nst2; set_piexl(x, y, c); else if (dy0) tmp=x1; /* 將 3b, 4b 象限方向的*/ x1=x2; /*直線變換到 2b, 1b */ x2=tmp; /*象限方向去. */ tmp=y1;y1=y2;dx=-dy;dy=-dy;p=2*dx-dy; /*注意此時(shí)誤差的*/const1=2*dx; /*變化參數(shù)取值. */const2=2*(dx-dy);x=x1;y=y1;set_pixel (x, y, c);lh 計(jì)算機(jī)圖形學(xué)作業(yè)：共九道題69 while (yy2) y+; if(p0) p+=const1; elsex+=inc;p+