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

1、計算機(jī)圖形學(xué)算法基礎(chǔ)作業(yè) 姓名： lh 學(xué)院： 理學(xué)院 專業(yè)： 計算數(shù)學(xué) 時間： 2010-12-31 lh 的計算機(jī)圖形學(xué)作業(yè) i 目錄 1 直線段生成算法綜述.1 1.1 生成直線的 dda 方法.1 1.1.1 dda 算法基本原理.1 1.1.2 dda 算法實現(xiàn)步驟.1 1.1.3 dda 算法程序（或偽程序）描述.2 1.1.4 dda 算法流程圖.2 1.2 生成直線的 bresenham 算法.3 1.2.1 bresenham 算法基本原理.3 1.2.2 bresenham 算法實現(xiàn)步驟.5 1.2.3 bresenham 算法程序（或偽程序）描述.5 1.2.4 bres

2、enham 算法流程圖.5 1.3 中點(diǎn)畫線算法.2 1.3.1 中點(diǎn)畫線算法基本原理.2 1.3.2 中點(diǎn)畫線算法實現(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)對比分析.6 1.6 直線生成算法的發(fā)展趨勢.7 2 橢圓的 bresenham 生成算法.7 lh 的計算機(jī)圖形學(xué)作業(yè) ii 2.1 橢圓曲率分析.7 2.2 橢圓方程分析.7 2.3 橢圓生成算法.9 2.3.1 算法實現(xiàn)過程.9 2.3.2 算法流程圖.10 2.3.3 算法程序描述.11 3 直線段裁剪算

3、法綜述.11 3.1 sutherland-cohen 裁剪算法.11 3.1.1 sutherland-cohen 算法基本原理.11 3.1.2 sutherland-cohen 算法實現(xiàn)步驟.11 3.1.3 算法程序（或偽程序）描述.12 3.1.4 算法流程圖.12 3.2 中點(diǎn)分割裁剪算法.12 3.2.1 中點(diǎn)分割算法基本原理與實現(xiàn)步驟.12 3.2.2 算法程序（或偽程序）描述.13 3.2.3 算法流程圖.13 3.3 梁友棟barskey 算法.14 3.3.1 梁友棟barskey 算法基本原理與實現(xiàn)步驟.14 3.3.2 算法程序（或偽程序）描述.15 3.3.3 算法

4、流程圖.15 3.4 快速算法.15 3.5 其余一些改進(jìn)的直線裁剪算法.16 lh 的計算機(jī)圖形學(xué)作業(yè) iii 3.6 各種直線裁剪算法的優(yōu)缺點(diǎn)對比分析.16 3.7 直線裁剪算法的發(fā)展趨勢.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 凸包計算.26 5 自由曲線曲面造型技術(shù).28 5.1 bezier 曲線和曲面.28 5.1.1 bezier 曲線.28 5.1.2 bezier 曲面.31 5.2 b 樣條曲線

5、與曲面.32 5.2.1 b 樣條的遞推定義和性質(zhì).32 5.2.2 b 樣條曲線.34 5.2.5 b 樣條曲面.36 5.3 nurbs 曲線與曲面.37 5.3.1 nurbs 曲線.37 5.3.2 非均勻有理 b 樣條（nurbs）曲面.39 5.4 coons 曲面.40 lh 的計算機(jī)圖形學(xué)作業(yè) iv 5.4.1 基本概念.40 5.4.2 雙線性 coons 曲面.41 5.4.3 雙三次 coons 曲面.42 6 cagd 中有關(guān)曲線曲面、拼接技術(shù).44 n c n g 6.1 基本原理.44 6.2 bezier 曲線的的拼接條件.44 001122 cgcgcg、 6.

6、3 bezier 曲面的的拼接條件.46 0011 cgcg、 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 平行投影(parallel projection).58 7.4.2 透視投影(persp

7、ective projection).60 lh 的計算機(jī)圖形學(xué)作業(yè) v 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.10 z 緩沖區(qū)法.64 8.11 極值檢測法.64 8.12 深度分類方法.64 8.13 八叉樹方法.65 9 圖形學(xué)若干基本算法的實現(xiàn)研究.65 參考文獻(xiàn).68 附錄.68 lh 計算機(jī)圖形學(xué)作業(yè)：共九道題 1 圖形學(xué)算法基礎(chǔ)作業(yè)

8、圖形學(xué)算法基礎(chǔ)作業(yè) 1 直線段生成算法綜述 1.1 生成直線的 dda 方法 1.1.1 dda 算法基本原理 dda 是數(shù)字微分分析式（digital differential analyzer）的縮寫。設(shè)直線之 起點(diǎn)為，終點(diǎn)為，則斜率為： 11 x ,y（） 22 x ,y（）k 21 21 y -ydy k = x -xdx 直線中的每一點(diǎn)坐標(biāo)都可以由前一點(diǎn)坐標(biāo)變化一個增量而得到，即表示 xy d ,d 為遞歸式： iix iiy x1xd y1yd 并有關(guān)系： yx d m d 遞歸式的初值為直線的起點(diǎn)，這樣，就可以用加法來生成一條直線。 11 x ,y（） 1.1.2 dda 算法實

9、現(xiàn)步驟 具體方法是： 按照直線從到的方向不同，分為 8 個象限（見圖 1.1） 。對于方向 11 x ,y（） 22 x ,y（） 在第 1a 象限內(nèi)的直線而言，。對于方向在第 1b 象限內(nèi)的直線而言， xy d1dm， 取值。各象限中直線生成時的取值列在表 1-1 之中。 yx d1d1/ m， xy d , d 圖 1.1 直線方向的 8 個象限圖 表 1-1 各象限中直線生成時的取值列 xy d , d lh 計算機(jī)圖形學(xué)作業(yè)：共九道題 2 象限dxdy? x d y d 1a 1b 2a 2b 3a 3b 4a 4b t f t f t f t f 1 1/m -1 -1/m -1 -

10、1/m 1 1/m m 1 m 1 -m -1 -m -1 研究表中的數(shù)據(jù)，可以發(fā)現(xiàn)兩個規(guī)律： 1、當(dāng)時；否則：dxdy xy d=1, d= m xy d =1/ m d=1， 2、的符號與的符號相同。這兩條規(guī)律可以導(dǎo)致程序的簡化。由上 xy d , ddx, dy 述方法寫成的程序如附錄 1 所示。其中 steps 變量的設(shè)置，以及 等語句，正是利用了上述兩條規(guī)律，使得程序變得簡練。 xy d = dx/steps; d = dy/steps 使用 dda 算法，每生成一條直線做兩次除法，每畫線中一點(diǎn)做兩次加法。因此， 用 dda 法生成直線的速度是相當(dāng)快的。 1.1.3 dda 算法程序

11、（或偽程序）描述 具體程序見附錄 1。 1.1.4 dda 算法流程圖 （略） 1.2 中點(diǎn)畫線算法 1.2.1 中點(diǎn)畫線算法基本原理 假定直線斜率在之間，當(dāng)前象素點(diǎn)為，則下一個象素點(diǎn)有k01 pp (x ,y ) 兩種可選擇點(diǎn)或。若與的中點(diǎn)稱 1pp p (x1,y ) 2pp p (x1,y1) 1 p 2 p pp (x1,y0.5) 為 m，q 為理想直線與垂線的交點(diǎn)。當(dāng)m 在 q 的下方時，則取應(yīng) p xx1 2 p 為下一個象素點(diǎn)；當(dāng)m 在 q 的上方時，則取為下一個象素點(diǎn)。這就是中 1 p 點(diǎn)畫線法的基本原理。 lh 計算機(jī)圖形學(xué)作業(yè)：共九道題 3 1.2.2 中點(diǎn)畫線算法實現(xiàn)步

12、驟 下面討論中點(diǎn)畫線法的實現(xiàn)。過點(diǎn)、的直線段 l 的方程 00 (x ,y ) 11 (x ,y ) 式為，其中，f(x,y)axbyc0 0101 ayy ,bxx 0110 cx yx y ，要 判斷中點(diǎn) m 在 q 點(diǎn)的上方還是下方，只要把m 代入，并判斷它f(x,y) 的符號即可。為此，我們構(gòu)造判別式: pppp df(m)f(x1,y0.5)a(x1)b(y0.5)c 當(dāng)時， m 在 l(q 點(diǎn))下方，取為下一個象素；d0 2 p 當(dāng)時， m 在 l(q 點(diǎn))上方，取為下一個象素；d0 1 p 當(dāng)時，選或均可，約定取為下一個象素 。d0 1 p 2 p 1 p 注意到是的線性函數(shù)，可

13、采用增量計算，提高運(yùn)算效率。d pp x ,y 若當(dāng)前象素處于情況，則取正右方象素,要判下一個象素位d0 1pp p (x1,y ) 置，應(yīng)計算，增量為 a。 1pppp df(x2,y0.5)a(x2)b(y0.5)cda 若時，則取右上方象素。要判斷再下一象素，則要d0 2pp p (x1,y1) 計算，增量為 2pppp df(x2,y1.5)a(x2)b(y1.5)cdab 。畫線從開始，的初值ab 00 (x , y )d ，因，所以。 00000 df(x1,y0.5)f(x ,y )a0.5b 00 f(x ,y )0 0 da0.5b 由于我們使用的只是的符號，而且的增量都是整

14、數(shù)，只是初始值包dd 含小數(shù)。因此，我們可以用代替來擺脫小數(shù)，寫出僅包含整數(shù)運(yùn)算的算2dd 法程序。 1.2.3 中點(diǎn)畫線算法程序（或偽程序）描述 具體程序見附錄 2 1.2.4 中點(diǎn)畫線算法流程圖 （略） 1.3 生成直線的 bresenham 算法 1.3.1 bresenham 算法基本原理 本算法由 bresenham 在 1965 年提出。設(shè)直線從起點(diǎn)到終點(diǎn)。直 11 x , y（） 22 x , y（） 線可表示為方程。其中y = kx+b 11 b = yk x 21 21 y - ydy k = x -xdx lh 計算機(jī)圖形學(xué)作業(yè)：共九道題 4 我們討論先將直線方向限于 1a

15、 象限（圖 1.1）在這種情況下，當(dāng)直線光柵化時， x 每次都增加 1 個單元，即 。而 y 的相應(yīng)增加應(yīng)當(dāng)小于 1。為了光柵化， ii x1= x +1 只可能選擇如圖 1.2 兩種位置之一。 i y +1 圖 1.2 的位置選擇 i y +1 圖 1.2 中 的位置選擇 或者 i y +1 ii y -1= y ii y +1= y +1 選擇的原則是看精確值與及的距離 d1 及 d2 的大小而定。計算式為：y i y i y +1 i i i y = m x +1 +b (1.2.1) d1= y- y (1.2.2) d2 = y +1- y (1.2.3) 如果，則，否則。因此算法的

16、關(guān)鍵在于簡便地求出d1-d2 0 ii y +1= y +1 ii y +1= y 的符號。將式（1.2.1） 、 （1.2.2） 、 （1.2.3）代入，得d1-d2d1-d2 iii dy d1-d2 = 2y-2y -1= 2(x +1)-2y +2b-1 dx 用乘等式兩邊，并以代入上述等式，得dx i p = dx d1-d2 iii p = 2x dy-2y dx+2dy+dx 2b-1 (1.2.4) 是我們用以判斷符號的誤差。由于在 1a 象限，總大于 0，所以仍舊可以d1-d2dx i p 用作判斷符號的誤差。為： i p1 iiii p +1= p +2dy-2dx y +

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

18、 if pi0 則 pi+1=pi+2dy-2dx; 否則 pi+1=pi+2dy； 5、i=i+1; if i dy 別將 2a,3a 象限的直線和 3b,4b 象限的直線變換到 1a,4a 和 2b,1b 方向去，以求得程 序處理的簡潔。 1.3.4 bresenham 算法流程圖 （略） 1.4 生成直線算法的進(jìn)一步改進(jìn) 除過前面所講到的 3 種基本直線生成算法外，還有一些其它的方法，由于過多， 這里僅列舉幾種如下： （1）二步法。雖然 bresenham 直線生成算法是一效率很高的算法，但是人們?nèi)?在尋找更有校的算法。1987 年又有人提出了一種二步法。即每循環(huán)一次不是繪制一 個像素，

19、而是繪制兩個像素，這樣無疑可把生成直線的速度提高一倍。 （2）改進(jìn)的 bresenham 算法。對于對于傳統(tǒng)的直線生成算法，人們往往把注意 力集中在算法本身，卻忽略了算法之外的一些有用信息:畫線之前，從起點(diǎn)坐標(biāo)和終 點(diǎn)坐標(biāo)，我們就可以獲知該線段的斜率，由此可進(jìn)一步得出在主軸方向連續(xù)走 l 個步 長，在副軸方向才走一個坐標(biāo)單位，這就是本算法提高 bresenham 算法執(zhí)行效率的一 個方面。提高算法效率的第二個方面是利用線段本身的對稱性，則新算法所產(chǎn)生的起 點(diǎn)一側(cè)的半條線段與用 bresenham 算法產(chǎn)生的相同。至于終點(diǎn)一側(cè)的半條線段，可以 看成以終點(diǎn)為起點(diǎn)線段的生成。 lh 計算機(jī)圖形學(xué)作業(yè)

20、：共九道題 6 算法實現(xiàn)： 特殊地，對于水平線()，垂直線()和對角線()，它們都可直y0 x0 xy 接裝人幀緩沖器，而無需進(jìn)行畫線算法處理。 從以上的描述可以實現(xiàn)優(yōu)于 bresenham 的直線生成算法。其中待生成直線的已知 數(shù)據(jù)為:為線段起點(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è)計出一種新的三步直線方法,該算

21、法揭示了直線計算的互補(bǔ)性,理論簡 單,精度達(dá)到最好。這種算法改善了 bresenham 算法和雙步算法的計算效率。該算法 對于硬件實現(xiàn)將更有益處。 除此之外直線生成算法還有對稱掃描四步增量畫線算法、基于 bresenham 的高效 直線生成集成算法、基于 bresenham 算法的四步畫直線算法、基于直線特性的直線生 成集成算法、基于自適應(yīng)步長的直線生成算法、基于等分像素點(diǎn)的直線生成算法、6 步直線生成算法、基于對角線行程的直線生成算法等等。 1.5 各種直線生成算法的優(yōu)缺點(diǎn)對比分析 dda 算法的優(yōu)點(diǎn)是：繪制實數(shù)直線效果好，誤差??；缺點(diǎn)是：實現(xiàn)較復(fù)雜，不 利于硬件實現(xiàn)。因為該算法涉及到實數(shù)乘

22、除法運(yùn)算，y 與 k 必須用浮點(diǎn)數(shù)表示，而且 每一步都要對 y 四舍五入后取整。 中點(diǎn)畫線算法優(yōu)點(diǎn)是：只有整數(shù)運(yùn)算，不含乘除法；可用硬件實現(xiàn)。 bresenham 算法的優(yōu)點(diǎn)是： 1、不必計算直線之斜率，因此不做除法； 2、不用浮點(diǎn)數(shù)，只用整數(shù)； 3、只做整數(shù)加減法和乘 2 運(yùn)算，而乘 2 運(yùn)算可以用硬件移位實現(xiàn)。 4、bresenham 算法速度很快，并適于用硬件實現(xiàn)。 1.6 直線生成算法的發(fā)展趨勢 （略） 2 橢圓的 bresenham 生成算法 2.1 橢圓曲率分析 橢圓（為沿軸方向的長半軸長度，為沿軸方向的cos , sinrat btaxb y lh 計算機(jī)圖形學(xué)作業(yè)：共九道題 7

23、 短半軸長度，且） ，曲率為，在第一象限ab 22223/2 /(sincos) r kabatbt ，將對 求導(dǎo)數(shù)，有，即曲率為減函數(shù)，在點(diǎn)（即）0,/ 2t r ktd/d0 r kt ( ,0)a0t 處的曲率；在點(diǎn)（即）處的曲率。半徑 2 (0) / r t ka b (0, )b/ 2t 2 (/2) / r t kb a 為的圓的曲率為，半徑為的圓的曲率為，兩圓的曲率關(guān)系為a 2 /a ab 2 /b b ，則兩圓的曲率在橢圓上點(diǎn)與的曲率之間，四者的 22 /()b ba aab( ,0)a(0, )b 關(guān)系為：。 22 /1/1/a bbab a 2.2 橢圓方程分析 根據(jù)橢圓及

24、圓的曲率分析，橢圓弧分別由半徑為和的圓弧逼近生成。為了更ab 準(zhǔn)確的由圓弧生成橢圓弧，在橢圓弧上確定一點(diǎn)，將橢圓弧分成曲率較小和曲率較 0 p 大的兩段，橢圓方程為： 。 222222 f x,y0b xa ya b 其中為沿軸方向的長半軸長度，為沿軸方向的短半軸長度，且axb y 。由于橢圓的對稱性，這里只要討論第一象限橢圓弧的生成。將橢圓弧0ab 分為上下兩部分，以弧上曲率為-1 的點(diǎn)（即法向量兩個分量相等的點(diǎn)）作為分界。 該橢圓上一點(diǎn)處的法向量為：( , )x y 22 ff n( , )ij2i 2jx yb xa y xy 結(jié)合橢圓方程可計算出分界點(diǎn)的坐標(biāo)為： 0 p 。 22222

25、2 (/,/)aabbab 以點(diǎn)為分界點(diǎn)，將第一象限的圓弧分成曲率較大和較小的兩段弧。如圖 2.1 所 0 p 示，的橢圓弧，與半徑為的圓在點(diǎn)到 222 /, ybabba 1 t (0, )a 的圓弧上對應(yīng)。在橢圓弧上任取一點(diǎn)，過作垂 22222 2 t (/,/)aababab 1 q 1 q lh 計算機(jī)圖形學(xué)作業(yè)：共九道題 8 直線與圓交于點(diǎn)，連接圓心與點(diǎn)，與軸的夾角為。則 1 p 1 py 橢圓的參數(shù)方程可表示為： sin, cos. xa yb 圓的參數(shù)方程可表示為： sin, cos. xa ya 對于同一 ，橢圓弧上存在唯一的點(diǎn)與圓弧上的點(diǎn)對應(yīng)，并且對應(yīng)點(diǎn)的坐標(biāo)存在 如下關(guān)系：

26、 , ( / )y. xx yb a 圖 2.1 圓弧與橢圓弧對應(yīng)點(diǎn)之一 圖 2.2 圓弧與橢圓弧對應(yīng)點(diǎn)之一 如圖 2.2 所示，半徑為的圓上，從點(diǎn)到b 22222 3 t (/,/)aabbbab 的圓弧與橢圓上的橢圓弧對應(yīng)，在橢圓弧上任取一點(diǎn) 4 t ( ,0)b 222 (0,/)ybab ，過作垂直線與圓交于點(diǎn)，連接圓心與點(diǎn)，與軸的夾角為。則 2 q 2 q 2 p 2 py 橢圓的參數(shù)方程可表示為： sin, cos. xa yb 圓的參數(shù)方程可表示為： sin, cos. xb yb lh 計算機(jī)圖形學(xué)作業(yè)：共九道題 9 對于同一 ，橢圓弧上存在唯一的點(diǎn)與圓弧上的點(diǎn)對應(yīng)，并且對應(yīng)點(diǎn)

27、的坐標(biāo)存在 如下關(guān)系： ( /b) , y. xax y 2.3 橢圓生成算法 當(dāng)圓弧上的點(diǎn)從沿著圖 2.1、圖 2.2 的對應(yīng)關(guān)系方向變化到時，橢圓( ,0)a( ,0)b 弧上相對應(yīng)的點(diǎn)也從該方向變化到。( ,0)a 2.3.1 算法實現(xiàn)過程 1、計算分界點(diǎn)。 000 p (x ,y ) 2、用 bresenham 算法生成兩段圓弧、。半徑為， 1 c 2 c 1 ca ；半徑為，。 222 0,/xaab 2 cb 222 y0,/bab 3、將圓弧進(jìn)行比例變換：方向的比例系數(shù)為 1，方向的比例系數(shù)為 1 cx y ；將圓弧進(jìn)行比例變換：方向的比例系數(shù)為，方向的比例系數(shù)/b a 2 cx

28、/a b y 為 1。 4、如圖 2.3，已知橢圓上在第一象限的點(diǎn)，則橢圓上另外三個象限與q(x,y) 點(diǎn)對稱的點(diǎn)分別為，因此只要畫出在第一象限的q(x,y)( x,y),( x,y),(x,y) 圖形，即可得到整個橢圓的圖形。 圖 2.3 橢圓對稱性 2.3.2 算法流程圖 橢圓的 bresenham 算法流程圖如下： lh 計算機(jī)圖形學(xué)作業(yè)：共九道題 10 計算分界點(diǎn) 000 px ,y 用 bresenham 算法計算圓弧 xy t ,t 計算對應(yīng)圓弧上的點(diǎn) 結(jié)束 用 bresenham 算法計算圓弧 xy t ,t y n y n 圖 2.4 橢圓的 bresenham 算法流程圖 2

29、.3.3 算法程序描述 具體程序?qū)崿F(xiàn)見附錄 5。 3 直線段裁剪算法綜述 裁剪裁剪：確定圖形中哪些部分落在顯示區(qū)之內(nèi)，哪些落在顯示區(qū)之外,以便只顯示 落在顯示區(qū)內(nèi)的那部分圖形。這個選擇過程稱為裁剪。 直線段裁剪算法是復(fù)雜圖元裁剪的基礎(chǔ)。復(fù)雜的曲線可以通過折線段來近似，從 而裁剪問題也可以化為直線段的裁剪問題。 3.1 sutherland-cohen 裁剪算法 3.1.1 sutherland-cohen 算法基本原理 sutherlandcohen 算法分成兩步。第一步是判斷直線段是否完全在窗口內(nèi)，若 開始 橢圓上點(diǎn) y 的坐標(biāo)大于 0 y 橢圓上點(diǎn)的 y 坐標(biāo)大于 0 lh 計算機(jī)圖形學(xué)作

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

31、棄該線段，簡稱“棄”之。 21p p （3）若線段不滿足“取”或 “棄”的條件，則在交點(diǎn)處把線段分為兩段。其中 一段完全在窗口外，可棄之。然后對另一段重復(fù)上述處理。 為快速判斷，采用如下編碼方法： 每個區(qū)域賦予 4 位編碼（如圖 3.1 所示）： lrbt cccc 其中： other yy c other yy c bt 0 1 0 1 minmax other xx c other xx c lr 0 1 0 1 minmax 10011000 0001 1010 00000010 010001010110 xlxr yt yb 圖 3.1 區(qū)域編碼 圖 3.2 線段不能用編碼確定 若完全

32、在窗口內(nèi) code1=0,且 code2=0,則“取” 21p p 若明顯在窗口外 code1y=y1+(y2-y1)*(xl-x1)/(x2-x1); else if(righty=y1+(y2-y1)*(xr-x1)/(x2-x1); else if(bottomx=x1+(x2-x1)*(yb-y1)/(y2-y1); else if(top x=x1+(x2-x1)*(yt-y1)/(y2-y1); 3.1.3 算法程序（或偽程序）描述 過程 clip 描述了這一算法。其中用一個集合(top,bottom,right,left)來表示端點(diǎn)的編 碼。具體程序見附錄 6。 3.1.4 算法

33、流程圖 （略） 3.2 中點(diǎn)分割裁剪算法 3.2.1 中點(diǎn)分割算法基本原理與實現(xiàn)步驟 與前一種 cohen-sutherland 算法一樣首先對線段端點(diǎn)進(jìn)行編碼，并把線段與窗 口的關(guān)系分為三種情況：完全可見、完全不可見和線段與窗口有交。對前兩種情況， 進(jìn)行一樣的處理。對于第三種情況，用中點(diǎn)分割的方法求出線段與窗口的交點(diǎn)。 求線段與窗口的交點(diǎn)如下： 設(shè)要裁剪的線段是。中點(diǎn)分割算法可分成兩個過程平行進(jìn)行，即從出發(fā)找 01 p p 0 p 出離最近的可見點(diǎn)（圖 3.3 中的 a 點(diǎn)） ，和從出發(fā)找出離最近的可見點(diǎn)（圖 0 p 1 p 1 p 3.3 中的 b 點(diǎn)） 。這兩個最近可見點(diǎn)的連線就是原線段

34、的可見部分。 從出發(fā)找出最近可見點(diǎn)的辦法是先求的中點(diǎn)，若不能定為顯然不 0 p 01 p p m p 0m p p 可見，則取代替，否則取代替，再對新的求中點(diǎn)。重復(fù)上述 0m p p 01 p p m1 p p 01 p p 01 p p m p 過程，直到長度小于給定的小數(shù) 為止。 1m pp 圖 3.4 是求的最近可見點(diǎn)的算法框圖。求的最近可見點(diǎn)的算法框圖是一樣 0 pp 1 p 的，只要把和交換即可。 0 p 1 p 在顯示時 可取成一個像素的寬度，對分辨率為的顯示器來說，上面講的 nn 22 二分的過程最多只要做 n 次。由于計算機(jī)過程只要做加法和除 2，所以特別適合用硬 件來實現(xiàn)。

35、lh 計算機(jī)圖形學(xué)作業(yè)：共九道題 13 如果允許兩個找最近點(diǎn)的過程平行進(jìn)行，這樣的話可使裁剪速度加快，增加算法 效率。 圖 3.3 中點(diǎn)分割算法 3.2.2 算法程序（或偽程序）描述 具體程序見附錄 7。 3.2.3 算法流程圖 中點(diǎn)分割算法框圖如圖 3.4。 可見否? 0 p m01 p(pp )/ 2 1m pp ? 顯然不可見 01 p p 顯然不可見? 0m p p 0m pp 1m pp 0 ppexit 原線完全不可見 0m ppexit 否 否 否 否 是 是 是 是 圖 3.4 中點(diǎn)分割算法框圖 lh 計算機(jī)圖形學(xué)作業(yè)：共九道題 14 3.3 梁友棟barskey 算法 3.3

36、.1 梁友棟barskey 算法基本原理與實現(xiàn)步驟 設(shè)要裁剪的線段是，的坐標(biāo)是。和窗口邊界交于 01 p p i p ii x ,y ,i0,1 01 p p a、b、c、d 四點(diǎn)，見圖 3.5。算法基本思想是從 a，b 和三點(diǎn)中找出最靠近的點(diǎn)， 0 p 1 p 圖 3.5 中要找的點(diǎn)是，從 c，d 和三點(diǎn)中找出最靠近的點(diǎn)，圖 3.5 中要找的點(diǎn) 0 p 1 p 0 p 是 c 點(diǎn)。那么就是上的可見部分。 0 p c 01 p p x y yt yb xl xr a b c d 0 p 1 p 圖 3.5 是可見部分 0 p c 具體計算時要把寫成參數(shù)方程 01 p p 0 0 xxx t y

37、yy t 其中。把窗口邊界的四條邊分成兩類，一類稱為始邊， 1010 xxx , yyy 另一類稱為終邊。 參數(shù)化形式寫出裁剪條件: l1r b1t xxuxx yyuyy 可以統(tǒng)一表示為形式： kk qup 111221 311441 pxqxxlpxqxrx pyqyybpyqyty 當(dāng)且，則線段完全在邊界外，則該線段平行于裁剪邊界并0 k p0 k q0 k q 且在窗口內(nèi)； 當(dāng)?shù)那闆r下：當(dāng),線段從裁剪邊界延長線的外部延伸到內(nèi)部；當(dāng)0 k p0 k p ,線段從裁剪邊界延長線的內(nèi)部延伸到外部。 k p0 對于每條直線，可以計算出參數(shù)和，它們定義了在裁剪矩形內(nèi)的線段部分， 1 u 2 u

38、lh 計算機(jī)圖形學(xué)作業(yè)：共九道題 15 的值由線段從外到內(nèi)遇到的矩形邊界所決定。對這些邊界計算。 1 u0p kkk pqr/ 取 0 和各個值之中的最大值。的值由線段從內(nèi)到外遇到的矩形邊界所決定 1 u k r 2 u 。對這些邊界計算。取 1 和各個值之中的最小值。如果，0p kkk pqr/ 2 u k r 21 uu 則線段完全落在裁剪窗口之外，被舍棄。否則裁剪線段由參數(shù)的兩個值，計算u 1 u 2 u 出來。 3.3.2 算法程序（或偽程序）描述 具體程序見附錄 8。 3.3.3 算法流程圖 （略） 3.4 快速算法 在實際繪圖時，常出現(xiàn)大部分線段是可見的，或大部分線段為顯然不可見。

39、因而 用最少的操作去判斷被裁剪的線段是否屬于這兩種情況則可以提高裁剪的效率。此外， 盡量減少比較和四則運(yùn)算，也是提高效率的重要措施。這樣會使程序長一點(diǎn)，但由于 效率高，在軟件包中值得采用。用這樣的算法確定一根顯然不可見線段平均只要做 3.6 次比較，確定一根完全可見線段要用 8 次比較，而用 sutherland-cohen 算法做同 樣工作則分別要做 11 次和 10 次比較?？焖偎惴ㄔ谧羁斓那闆r下要和四條邊求交點(diǎn)， 這要用 10 次加減法、5 次乘除法和 13 次比較。采用 sutherland-cohen 算法要做 16 次加減法、8 次乘除法和 35 次比較。此外后者還要多次調(diào)用過程合

40、作集合運(yùn)算，這 些都使它比快速算法效率低。 3.5 其余一些改進(jìn)的直線裁剪算法 除過前面所講到的 4 種基本直線裁剪算法外，還有一些其它的裁剪方法，由于過 多，這里僅列舉幾種如下： （1）具有最少算術(shù)運(yùn)算量的二維線裁剪算法。見文獻(xiàn)：王駿，梁友棟，彭群生， 具有最少算術(shù)運(yùn)算量的二維線裁剪， 計算機(jī)學(xué)報 ，1991 年第 7 期。 （2）一個有效的多邊形窗口的線裁剪算法。見文獻(xiàn)：劉勇奎等，一個有效的多 邊形窗口的線裁剪， 計算機(jī)學(xué)報 ，1999 年第 11 期。 （3）一種基于幾何變換的高效的線裁剪新算法。見文獻(xiàn)：汪亂，吳銳迅，蔡士 杰。一種基于幾何變換的高效的線裁剪新算法。 軟件學(xué)報 ，1998

41、，9(10): 728 一 733。 （4）任意多邊形窗口的線裁剪算法。見文獻(xiàn)：孫巖，唐棣:任意多邊形窗口的線 lh 計算機(jī)圖形學(xué)作業(yè)：共九道題 16 裁剪， 2000 年圖形學(xué)會議?？?。 3.6 各種直線裁剪算法的優(yōu)缺點(diǎn)對比分析 sutherland-cohen 直線裁剪算法要計算直線段與窗口邊界的交點(diǎn)，這不可避免 地要進(jìn)行大量的乘除運(yùn)算，必會降低程序的執(zhí)行效率。而中點(diǎn)分割裁剪算法卻只需用 到加法和除 2 運(yùn)算，而除 2 運(yùn)算在計算機(jī)中可以簡單地用右移一位來實現(xiàn)，從而提高 算法的效率。所以特別適合硬件實現(xiàn)，同時也適合于并行計算。 3.7 直線裁剪算法的發(fā)展趨勢 （略） 4 圖形求交技術(shù) 4

42、.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) 對三維空間中的直線段來說，上述方程實際上是一個二元一次方程組，由三個方 程式組成?？梢詮钠渲袃蓚€解出，再用第三個驗證解的有效性：若第三個方程成s,t 立則說明找到了解，否則說明兩條直線不相交。當(dāng)所得的解是有效解時，可用 ii t ,

43、 s（） 二個線段方程之一計算交點(diǎn)坐標(biāo)，例如。 ii p t= a+bt 我們還可以根據(jù)向量的基本性質(zhì)，直接計算 s 與 t：對（4.1.1）兩邊構(gòu)造點(diǎn)積 得 c x da+bt = c x dc+ds（）（）（） 由于 cxd 同時垂直于 c 和 d，等式右邊為零。故有 (c d) a t (c d) b 類似地有 lh 計算機(jī)圖形學(xué)作業(yè)：共九道題 17 (ab) c s (ab) d 完整的算法還應(yīng)判斷無解與無窮多解（共線）的情形，以及考慮數(shù)值計算誤差造 成的影響。 2、直線段與二次曲線的交點(diǎn) 不失一般性，考慮平面上一條直線與同平面的一條二次曲線的交。 假設(shè)曲線方程為 ，f x,y = 0

44、 直線段方程為 , 11 x, y = x +tdx, y +tdy 則在交點(diǎn)處有 。 11 f x +tdx, y +tdy = 0 當(dāng)曲線為二次曲線時，上述方程可寫為 2 atbtc0 用二次方程求根公式即可解出 t 值。 3、圓錐曲線與圓錐曲線的交點(diǎn) 圓錐曲線有代數(shù)法表示、幾何法表示與參數(shù)法表示。在進(jìn)行一對圓錐曲線的求交 時，把其中一條圓錐曲線用代數(shù)/幾何法表示為隱函數(shù)形式，另一條表示為參數(shù)形式 （如二次 nurbs 曲線） 。將參數(shù)形式代入隱函數(shù)形式可得關(guān)于參數(shù)的四次方程，可以 使用四次方程的求根公式解出交點(diǎn)參數(shù)。得到交點(diǎn)后可再驗證交點(diǎn)是否在有效的圓錐 曲線段上。 4.2.2 線與面的

45、交點(diǎn)的求法 1、直線段與平面的交點(diǎn)（如圖 4.1） 圖 4.1 線段與平面求交 lh 計算機(jī)圖形學(xué)作業(yè)：共九道題 18 考慮直線段與無界平面的求交問題。把平面上的點(diǎn)表示為，p u,w = a+ub+wc 直線段上的點(diǎn)表示為，二者的交點(diǎn)記為。假設(shè)線段不平行于平面，則 q t = d+ter 它們交于，即 r = p u,w = q t a+ub+wc = d+te 等式兩邊點(diǎn)乘，得b x c（） b x ca+ub+wc = b x cd+te（）（）（）（） 由于既垂直于 b，又垂直于 c，故有b x c b x ca = b x cd+te（）（）（） 可解出 (b c) a(b c) d

46、t (b c) e 類似求得 (c e) d (c e) a (c e) b u (b e) d (b e) a (b e) c 如果是直線與平面區(qū)域求交點(diǎn)，則要進(jìn)一步判斷點(diǎn)是否在平面上的有效區(qū)域中， 其算法可參見 4.2 節(jié)。 2、圓錐曲線與平面的交點(diǎn) 圓錐曲線與平面求交時，可以把圓錐曲線表示為參數(shù)形式，并把圓錐曲線的參數(shù) 形式代入平面方程，即可得到參數(shù)的二次方程進(jìn)行求解。 3、圓錐曲線與二次曲面的交點(diǎn) 圓錐曲線與二次曲面求交時，可把圓錐曲線的參數(shù)形式代入二次曲面的隱式方程， 得到參數(shù)的四次方程，用求根公式求解。 4.2 求交線算法 求交線顯然是指求面與面的交線，下面討論幾種常見的情況。 1

47、、平面與平面的交線 在 cad 中一般使用平面上有界區(qū)域。先考慮最簡單的情形。兩個平面區(qū)域分別由 定義。如果它們不共面而且不分離，則必交于一直線p u,w , q s,t , u, w, s, t 0, 1 段。這條直線必落在所定義的無限直線上。注意這是個含有四個p u,w -q s,t = 0 未知數(shù)，三個方程式的方程組，只要分別與八條邊界線方程： 聯(lián)立，即可求出線段的兩個端點(diǎn)的參數(shù)。u = 0, u =1, w = 0, w =1, s = 0, s =1, t = 0, t =1 在上述方程組中，只要找到兩組解，就可以不再對剩余其它方程組求解。找到的兩組 lh 計算機(jī)圖形學(xué)作業(yè)：共九道題

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

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

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

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

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

53、線的定義參數(shù)。平面與圓錐的交線也可類似求出。 3、平面與參數(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)系下的 平面。再用相同的變換應(yīng)用于參數(shù)曲面方程得到參數(shù)曲面在新坐標(biāo)系下的方程xoy * x , y , z= xs,t , ys,t , zs,t（）（） 由此得交線在新坐標(biāo)系下的方程為。 * zs,t0 lh 計算機(jī)圖形學(xué)作業(yè)：共九道

54、題 21 4.3 包含判定算法 在進(jìn)行圖形求交時，常常需要判定兩個圖形間是否有包含關(guān)系。如點(diǎn)是否包含在 線段、平面區(qū)域、三維形體中，線段是否包含在平面區(qū)域、三維形體中，等等。許多 包含判定問題可轉(zhuǎn)化為點(diǎ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)與直

55、線段的包含判定 假設(shè)點(diǎn)坐標(biāo)為，直線段端點(diǎn)為，則點(diǎn) p 到線p x,y,z 1111 p x ,y ,z 2222 px ,y ,z 段的距離的平方為 12 pp 2 222 211211211 111 222 212121 xxxxyyyyzzzz d2xxyyzz xxyyzz 當(dāng)時，認(rèn)為點(diǎn)在線段（或其延長線）上，這時還需進(jìn)一步判斷點(diǎn)是否落在直線d20 段的有效區(qū)間內(nèi)。只要對坐標(biāo)分量進(jìn)行比較，假設(shè)線段兩端點(diǎn)的 x 分量不等（否則所 有分量均相等，那么線段兩端點(diǎn)重合，線段退化為一點(diǎn)） ，那么當(dāng)與反號 1 xx 2 xx 時，點(diǎn) p 在線段的有效區(qū)間內(nèi)。 2、點(diǎn)與圓錐曲線段的包含判定 以圓弧為例

56、，假設(shè)點(diǎn)的坐標(biāo)為，圓弧的中心為，半徑為 ，起x, y, z 000 x , y , z（）r 始角，終止角。這些角度都是相對于局部坐標(biāo)系 x 軸而言。圓弧所在平面為 1 2 ax+by+cz+d = 0 先判斷點(diǎn)是否在該平面上，若不在，則點(diǎn)不可能被包含。若在，則通過坐標(biāo)變換， 把問題轉(zhuǎn)換到二維的問題。 給定中心為，半徑為 ，起始角，終止角的圓弧，對平面上一點(diǎn) 00 x , y（）r 1 2 ，判斷 p 是否在圓弧上，可分二步進(jìn)行。p x, y（） 第一步判斷 p 是否在圓心為，半徑為 的圓的圓周上，即下式是否成立： 00 x , y（）r 22 00 ()()rxxyy lh 計算機(jī)圖形學(xué)作業(yè)

57、：共九道題 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 交計算包括三個步驟： （1）計算參數(shù) 值，使到的距離最??；tp q t （2）判斷 是否在有效參數(shù)區(qū)間內(nèi)（通常為） ；t01， （3）判斷與的距離是否小于 。若（2） ， （3）步的判斷均為“是” ，則 q tp 點(diǎn)在曲線上；否則點(diǎn)不在曲線上。 第一步應(yīng)計算 ，使得最小，即t p q t 2 r t = p-q tp-q t= p-q t 最小 根據(jù)微積分知識，在該處即r (t) = 0 q (t) p-q

58、 t= 0 用數(shù)值方法解出 值，再代入曲線參數(shù)方程可求出曲線上對應(yīng)點(diǎn)的坐標(biāo)。第（2） 、t （3）步的處理比較簡單，不再詳述。 4、點(diǎn)與平面區(qū)域的包含判定 設(shè)點(diǎn)坐標(biāo)為，平面方程為。則點(diǎn)到平面的距離為p x, y, zax+by+cz+d = 0 222 ax+by+cz+d r = a +b +c 若 ，則認(rèn)為點(diǎn)在平面上，否則認(rèn)為點(diǎn)不在平面上。在造型系統(tǒng)中，通常使r 用平面上的有界區(qū)域作為形體的表面。在這種情況下，對落在平面上的點(diǎn)還應(yīng)進(jìn)一步 判別它是否落在有效區(qū)域內(nèi)。若點(diǎn)落在該區(qū)域內(nèi)，則認(rèn)為點(diǎn)與該面相交，否則不相交。 下面以平面區(qū)域多邊形為例，介紹有關(guān)算法。判斷平面上一個點(diǎn)是否包含在同平面的

59、一個多邊形內(nèi)，有許多種算法，這里僅介紹常用的三種：叉積判斷法、夾角之和檢驗 法以及交點(diǎn)計數(shù)檢驗法。 （1）叉積判斷法 假設(shè)判斷點(diǎn)為。多邊形頂點(diǎn)按順序排列為。如圖 4.2 所示。令 0 p 12n ppp 。那么，在多邊形內(nèi)的充要條件是叉積 ii0n1 vpp , i1, 2, , n, v1v 0 p 的符號相同。叉積判斷法僅適用于凸多邊形。當(dāng)多邊形為 ii v x v +1 i1, 2, , n、 凹時，盡管點(diǎn)在多邊形內(nèi)也不能保證上述叉積符號都相同。這時可采用后面介紹的兩 lh 計算機(jī)圖形學(xué)作業(yè)：共九道題 23 種方法。 圖 4.2 叉積判斷法 （2）夾角之和檢驗法 假設(shè)某平面上有點(diǎn)和多邊形

60、，如圖 4.3 所示。將點(diǎn)分別與相連， 0 p 12345 pp p p p 0 p i p 構(gòu)成向量。假設(shè)角 。如果，則點(diǎn)在多邊形之外， i0 vpp i0ii pp p1 0 5 1 i i 0 p 如圖 4.3(a)所示。如果，則點(diǎn)在多邊形之內(nèi)，如圖 4.3(b)所示?？?2 5 1 i i 0 p i 通過下列公式計算：令, ，則，所以 iii svxv1 iii cv v1 iii tgs /c 且的符號即代表角度的方向。 iii arctg s /c i 圖 4.3 夾角之和檢驗法 在多邊形邊數(shù)不太多（ 0 x,y,z（） 見的或隱的） ； 如果，則觀察點(diǎn)在凸型多面體外部（稱該表面