計算機圖形學算法基礎作業(yè)

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

2、enham 算法流程圖.5 1.3 中點畫線算法.2 1.3.1 中點畫線算法基本原理.2 1.3.2 中點畫線算法實現步驟.3 1.3.3 中點畫線算法程序（或偽程序）描述.3 1.3.4 中點畫線算法流程圖.3 1.4 生成直線算法的進一步改進.5 1.5 各種直線生成算法的優(yōu)缺點對比分析.6 1.6 直線生成算法的發(fā)展趨勢.7 2 橢圓的 bresenham 生成算法.7 lh 的計算機圖形學作業(yè) ii 2.1 橢圓曲率分析.7 2.2 橢圓方程分析.7 2.3 橢圓生成算法.9 2.3.1 算法實現過程.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 算法實現步驟.11 3.1.3 算法程序（或偽程序）描述.12 3.1.4 算法流程圖.12 3.2 中點分割裁剪算法.12 3.2.1 中點分割算法基本原理與實現步驟.12 3.2.2 算法程序（或偽程序）描述.13 3.2.3 算法流程圖.13 3.3 梁友棟barskey 算法.14 3.3.1 梁友棟barskey 算法基本原理與實現步驟.14 3.3.2 算法程序（或偽程序）描述.15 3.3.3 算法

4、流程圖.15 3.4 快速算法.15 3.5 其余一些改進的直線裁剪算法.16 lh 的計算機圖形學作業(yè) iii 3.6 各種直線裁剪算法的優(yōu)缺點對比分析.16 3.7 直線裁剪算法的發(fā)展趨勢.16 4 圖形求交技術.16 4.1 求交點算法.16 4.1.1 線與線的交點的求法.17 4.2.2 線與面的交點的求法.18 4.2 求交線算法.19 4.3 包含判定算法.21 4.4 重疊判定算法.26 4.5 凸包計算.26 5 自由曲線曲面造型技術.28 5.1 bezier 曲線和曲面.28 5.1.1 bezier 曲線.28 5.1.2 bezier 曲面.31 5.2 b 樣條曲線

5、與曲面.32 5.2.1 b 樣條的遞推定義和性質.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 的計算機圖形學作業(yè) iv 5.4.1 基本概念.40 5.4.2 雙線性 coons 曲面.41 5.4.3 雙三次 coons 曲面.42 6 cagd 中有關曲線曲面、拼接技術.44 n c n g 6.1 基本原理.44 6.2 bezier 曲線的的拼接條件.44 001122 cgcgcg、 6.

6、3 bezier 曲面的的拼接條件.46 0011 cgcg、 7 圖形變換技術.48 7.1 二維圖形幾何變換.49 7.1.1 平移(translation).49 7.1.2 旋轉(rotation).49 7.1.3 變比(scaling).50 7.2 三維圖形幾何變換.51 7.2.1 平移.51 7.2.2 旋轉.51 7.2.3 變比.54 7.3 參數圖形幾何變換.54 7.3.1 圓錐曲線的幾何變換.54 7.3.2 參數曲線、曲面的幾何變換.55 7.4 投影變換.58 7.4.1 平行投影(parallel projection).58 7.4.2 透視投影(persp

7、ective projection).60 lh 的計算機圖形學作業(yè) v 8 圖形消隱算法.61 8.1 掃描線 z-buffer 算法.61 8.2 區(qū)域子分割算法.61 8.3 光線投射算法.62 8.4 平面公式法.62 8.5 徑向預排序法.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 圖形學若干基本算法的實現研究.65 參考文獻.68 附錄.68 lh 計算機圖形學作業(yè)：共九道題 1 圖形學算法基礎作業(yè)

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

9、現步驟 具體方法是： 按照直線從到的方向不同，分為 8 個象限（見圖 1.1） 。對于方向 11 x ,y（） 22 x ,y（） 在第 1a 象限內的直線而言，。對于方向在第 1b 象限內的直線而言， xy d1dm， 取值。各象限中直線生成時的取值列在表 1-1 之中。 yx d1d1/ m， xy d , d 圖 1.1 直線方向的 8 個象限圖 表 1-1 各象限中直線生成時的取值列 xy d , d lh 計算機圖形學作業(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 研究表中的數據，可以發(fā)現兩個規(guī)律： 1、當時；否則：dxdy xy d=1, d= m xy d =1/ m d=1， 2、的符號與的符號相同。這兩條規(guī)律可以導致程序的簡化。由上 xy d , ddx, dy 述方法寫成的程序如附錄 1 所示。其中 steps 變量的設置，以及 等語句，正是利用了上述兩條規(guī)律，使得程序變得簡練。 xy d = dx/steps; d = dy/steps 使用 dda 算法，每生成一條直線做兩次除法，每畫線中一點做兩次加法。因此， 用 dda 法生成直線的速度是相當快的。 1.1.3 dda 算法程序

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

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

13、采用增量計算，提高運算效率。d pp x ,y 若當前象素處于情況，則取正右方象素,要判下一個象素位d0 1pp p (x1,y ) 置，應計算，增量為 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、數，只是初始值包dd 含小數。因此，我們可以用代替來擺脫小數，寫出僅包含整數運算的算2dd 法程序。 1.2.3 中點畫線算法程序（或偽程序）描述 具體程序見附錄 2 1.2.4 中點畫線算法流程圖 （略） 1.3 生成直線的 bresenham 算法 1.3.1 bresenham 算法基本原理 本算法由 bresenham 在 1965 年提出。設直線從起點到終點。直 11 x , y（） 22 x , y（） 線可表示為方程。其中y = kx+b 11 b = yk x 21 21 y - ydy k = x -xdx lh 計算機圖形學作業(yè)：共九道題 4 我們討論先將直線方向限于 1a

15、 象限（圖 1.1）在這種情況下，當直線光柵化時， x 每次都增加 1 個單元，即 。而 y 的相應增加應當小于 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、關鍵在于簡便地求出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 算法實現步驟 綜述上面 1.3.1 的推導，第 1a 象限內的直線 bresenham 算法思想如下： 1、畫點(x1, y2); dxx2x1; dyy2y1； 計算誤差初值 p1=2dy-dx; i=1； lh 計算機圖形學作業(yè)：共九道題 5 2、求直線的下一點位置： xi+1=xi+1； if pi0 則 yi+1=yi+1； 否則 yi+1=yi； 3、畫點（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 生成直線算法的進一步改進 除過前面所講到的 3 種基本直線生成算法外，還有一些其它的方法，由于過多， 這里僅列舉幾種如下： （1）二步法。雖然 bresenham 直線生成算法是一效率很高的算法，但是人們仍 在尋找更有校的算法。1987 年又有人提出了一種二步法。即每循環(huán)一次不是繪制一 個像素，

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

20、：共九道題 6 算法實現： 特殊地，對于水平線()，垂直線()和對角線()，它們都可直y0 x0 xy 接裝人幀緩沖器，而無需進行畫線算法處理。 從以上的描述可以實現優(yōu)于 bresenham 的直線生成算法。其中待生成直線的已知 數據為:為線段起點的橫、縱坐標；為線段終點的橫、縱坐標。 11 (x ,y ) 22 (x ,y ) 算法的輸人數據為: ，。 11 (x ,y ) 22 (x ,y ) （3）基于類最佳逼近的散步直線生成算法。一種新的直線逼近方法類最佳逼 近,基于這種逼近方法,斜率的直線和斜率為的直線具有某種互補性質。k0,0.51 k 利用該性質,設計出一種新的三步直線方法,該算

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

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

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

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

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

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

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

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

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

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

31、棄該線段，簡稱“棄”之。 21p p （3）若線段不滿足“取”或 “棄”的條件，則在交點處把線段分為兩段。其中 一段完全在窗口外，可棄之。然后對另一段重復上述處理。 為快速判斷，采用如下編碼方法： 每個區(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、在窗口內 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)來表示端點的編 碼。具體程序見附錄 6。 3.1.4 算法

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

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

35、lh 計算機圖形學作業(yè)：共九道題 13 如果允許兩個找最近點的過程平行進行，這樣的話可使裁剪速度加快，增加算法 效率。 圖 3.3 中點分割算法 3.2.2 算法程序（或偽程序）描述 具體程序見附錄 7。 3.2.3 算法流程圖 中點分割算法框圖如圖 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 中點分割算法框圖 lh 計算機圖形學作業(yè)：共九道題 14 3.3 梁友棟barskey 算法 3.3

36、.1 梁友棟barskey 算法基本原理與實現步驟 設要裁剪的線段是，的坐標是。和窗口邊界交于 01 p p i p ii x ,y ,i0,1 01 p p a、b、c、d 四點，見圖 3.5。算法基本思想是從 a，b 和三點中找出最靠近的點， 0 p 1 p 圖 3.5 中要找的點是，從 c，d 和三點中找出最靠近的點，圖 3.5 中要找的點 0 p 1 p 0 p 是 c 點。那么就是上的可見部分。 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 具體計算時要把寫成參數方程 01 p p 0 0 xxx t y

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

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

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

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

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

42、.1 求交點算法 求交點可以分兩種情況：求線與線的交點以及求線與面的交點。 4.1.1 線與線的交點的求法 1、直線段與直線段的交點 假設二條直線的端點分別為則它們可以用向量形式表示為：p1p2q1q2， p t = a+bt (0t1) q s = c+ds (0s1) 其中，。ap1bp2p1cq1dq2q1， 構造方程 a+bt = c+ds (4.1.1) 對三維空間中的直線段來說，上述方程實際上是一個二元一次方程組，由三個方 程式組成?？梢詮钠渲袃蓚€解出，再用第三個驗證解的有效性：若第三個方程成s,t 立則說明找到了解，否則說明兩條直線不相交。當所得的解是有效解時，可用 ii t ,

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

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

45、交點的求法 1、直線段與平面的交點（如圖 4.1） 圖 4.1 線段與平面求交 lh 計算機圖形學作業(yè)：共九道題 18 考慮直線段與無界平面的求交問題。把平面上的點表示為，p u,w = a+ub+wc 直線段上的點表示為，二者的交點記為。假設線段不平行于平面，則 q t = d+ter 它們交于，即 r = p u,w = q t a+ub+wc = d+te 等式兩邊點乘，得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ū)域求交點，則要進一步判斷點是否在平面上的有效區(qū)域中， 其算法可參見 4.2 節(jié)。 2、圓錐曲線與平面的交點 圓錐曲線與平面求交時，可以把圓錐曲線表示為參數形式，并把圓錐曲線的參數 形式代入平面方程，即可得到參數的二次方程進行求解。 3、圓錐曲線與二次曲面的交點 圓錐曲線與二次曲面求交時，可把圓錐曲線的參數形式代入二次曲面的隱式方程， 得到參數的四次方程，用求根公式求解。 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 未知數，三個方程式的方程組，只要分別與八條邊界線方程： 聯(lián)立，即可求出線段的兩個端點的參數。u = 0, u =1, w = 0, w =1, s = 0, s =1, t = 0, t =1 在上述方程組中，只要找到兩組解，就可以不再對剩余其它方程組求解。找到的兩組 lh 計算機圖形學作業(yè)：共九道題

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

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

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

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

52、相交的算法如下： plane_sphere_intersect(p, s) plane p; sphere s; d=球面中心到平面的有向距離； if(abs(d)=s.r) 二個面相交于一（切）點 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; 一個平面與一個圓柱面可以無交、交于一條直線（切線） 、二條直線、一個橢圓 或一個圓，可以用兩個面的定義參數求出它們的相對位置關系和相對角度關系，進而 判斷其交屬于何種情況，并求出交

53、線的定義參數。平面與圓錐的交線也可類似求出。 3、平面與參數曲面的交線 最簡單的方法是把參數曲面的表示代入平面方程 x s,t , y s,t , z s,t（） ax+by+cz+d = 0 得到用參數曲面的參數 s、t 表示的交線方程 ax s,t +by s,t +cz s,t +d = 0 另一種方法是用平移和旋轉變換對平面進行坐標變換，使平面成為新坐標系下的 平面。再用相同的變換應用于參數曲面方程得到參數曲面在新坐標系下的方程xoy * x , y , z= xs,t , ys,t , zs,t（）（） 由此得交線在新坐標系下的方程為。 * zs,t0 lh 計算機圖形學作業(yè)：共九道

54、題 21 4.3 包含判定算法 在進行圖形求交時，常常需要判定兩個圖形間是否有包含關系。如點是否包含在 線段、平面區(qū)域、三維形體中，線段是否包含在平面區(qū)域、三維形體中，等等。許多 包含判定問題可轉化為點的包含判定問題，如判斷線段是否在平面上可以轉化為判斷 其兩端點是否在平面上。因此下面主要討論關于點的包含判定算法。 判斷點與線段的包含關系，也就是判斷點與線的最短距離是否位于容差范圍內。 造型中常用的線段有三種： 1、直線段； 2、圓錐曲線段（主要是圓?。?； 3、參數曲線（主要是 bezier，b 樣條與 nurbs 曲線） 。 點與面的包含判定也類似地分為三種情況。下面分別討論。 1、點與直

55、線段的包含判定 假設點坐標為，直線段端點為，則點 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 當時，認為點在線段（或其延長線）上，這時還需進一步判斷點是否落在直線d20 段的有效區(qū)間內。只要對坐標分量進行比較，假設線段兩端點的 x 分量不等（否則所 有分量均相等，那么線段兩端點重合，線段退化為一點） ，那么當與反號 1 xx 2 xx 時，點 p 在線段的有效區(qū)間內。 2、點與圓錐曲線段的包含判定 以圓弧為例

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

57、：共九道題 22 第二步判斷 p 是否在有效的圓弧段內。 3、點與參數曲線的包含判定 設點坐標為，參數曲線為。點也參數曲線的求p x, y, z q t = x t , y t , z t 交計算包括三個步驟： （1）計算參數 值，使到的距離最??；tp q t （2）判斷 是否在有效參數區(qū)間內（通常為） ；t01， （3）判斷與的距離是否小于 。若（2） ， （3）步的判斷均為“是” ，則 q tp 點在曲線上；否則點不在曲線上。 第一步應計算 ，使得最小，即t p q t 2 r t = p-q tp-q t= p-q t 最小 根據微積分知識，在該處即r (t) = 0 q (t) p-q

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

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

60、，如圖 4.3 所示。將點分別與相連， 0 p 12345 pp p p p 0 p i p 構成向量。假設角 。如果，則點在多邊形之外， i0 vpp i0ii pp p1 0 5 1 i i 0 p 如圖 4.3(a)所示。如果，則點在多邊形之內，如圖 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 夾角之和檢驗法 在多邊形邊數不太多（ 0 x,y,z（） 見的或隱的） ； 如果，則觀察點在凸型多面體外部（稱該表面