維圖形裁剪ppt課件(2)(編輯修改稿)
2025-05-30 01:52 本頁面
【文章內容簡介】 光標看作小的裁剪窗口。） 編碼算法特點 算法的思路： 采用與前相似的線段端點編碼和相應的檢查方法，先判定完全可見線段和顯然不可見線段。 否則，將 線段分割成相等的兩段 ，然后對每一小段重復上述的檢查， 直至找到每段與窗口邊界的交點或分割小段的長度充分小 ，可以視為一點時為止。 相當于： 對分查找法求交，分割次數(shù)最多不超過線段端點的表示精度 。 中點分割算法 算法過程： 1）輸入線段 AB的兩端點坐標 A（ x0,y0）、 B（ x1,y1），以及裁剪窗口的四條邊界： yt,yb,xl,xr。 2）對 AB編碼， A的編碼 codeA=0001， B的編碼為codeB=0110。 3）線段 AB裁剪的基本過程： 例：中點 算法裁剪過程： y=yT y=yB x=xL x=xR A BB Pm2 Pm1 Pm3 y=yT y=yB x=xL x=xR B AB Pm2 Pm1 ①由于 codeA | codeB≠0，對 AB不能全部保留；又因為 codeA amp。 codeB=0，對 AB不能全部舍棄，因此要對 AB求中點處理； ②求 AB中點。 ③判斷中點 Pm1是否在窗口內，若不在窗口內，則將中點和離窗口最遠點構成的線段去掉，以線段另一端點和該中點再構成線段，求其中點；若中點 Pm1在窗口內，如上頁左圖所示。則以中點和最遠點構成線段 APm1，并求其中點 Pm2，直至中點與窗口邊界的坐標值在規(guī)定的誤差范圍內，則該中點就是線段落在窗口內的一個端點，用原線段端點 A替代每一次保留的中點。 ④若另一端點在窗口內，則經③即可確定該線段在窗口內的部分；若不在窗口內，如右圖，交換兩端點，則該點和所求出的在窗口上的那一點構成一條線段 AB，重復步驟③，即可求出落進窗口的另外一點。并用原線段端點 A替代每一次保留的中點。 最后得到裁剪后的線段為 AB，算法結束。 ? 對分辯率為 2N*2N的顯示器，上述二分過程至多進行 N次。 ? 主要過程只用到加法和除法運算，適合硬件實現(xiàn)， 它可以用左右移位來代替乘除法，這樣就大大加快了速度 。 中點分割裁剪算法特點 設要裁剪的線段是 P0P1。 P0P1和窗口邊界交于 A,B,C,D四點，見圖。算法的基本思想是從 A,B和 P0三點中找出最靠近的 P1點，圖中要找的點是 P0。從 C,D和 P1中找出最靠近 P0的點。圖中要找的點是 C點。那么 P0C就是 P0P1線段上的可見部分。 梁友棟 Barsky算法 線段的 參數(shù)表示 x=x0+t△ x y=y0+t△ y 0=t=1 △ x=x1x0 △ y=y1y0 窗口邊界的四條邊分為兩類：始邊和終邊。 ??????????????????????????為始邊。為終邊，若為終邊。為始邊，若為始邊。為終邊，若為終邊。為始邊，若TBTBRLRLyyyyyyyyyyxxxxxxxxxx0000 P0P1與兩條始邊的交點參數(shù) t0, t1 , 令tl=max(t0 ,t1,0)，則 tL即為三者中離 p1最近的點的參數(shù) p0p1與兩條終邊的交點參數(shù) t2, t3, 令tu=min(t2,t3,1) ，則 tU即為三者中離 p0最近的點的參數(shù) 若 tu tl,則可見線段區(qū)間 [tl , tu] t0 t1 t2 t3 0 1 交點計算 ： 令 QL= △ x DL= x0xL QR= △ x DR= xRx0 QB= △ y DB= y0yB QT= △ y DT= yTy0 交點為 : ti= Di / Qi i=L,R,B,T Qi 0 ti為與始邊交點參數(shù) Qi 0 ti為與終邊交點參數(shù) Qi =0 Di 0 時 ,線段不可見 Di 0 時 , 分析另一 D, E F A B 當 Qi =0時 若 Di 0 時 ,線段不可見 （如圖中 AB，有 QR=0， DR0） 若 Di 0 時 , 分析另一 D, （如圖中的 EF就是這種情況，它使 QL=0， DL0和 QR=0， DR0。這時由于 EF和 x=xL及 x=xR平行，故不必去求出 EF和 x=xL及 x=xR的交點，而讓 EF和 y=yT及 y=yB的交點決定直線段上的可見部分。） E F A B 多邊形裁剪 ? 錯覺 ：直線段裁剪的組合？ ? 關鍵 ： 要 保持窗口內多邊形的邊界部分 ，而且要將窗框的有關部分按一定次序插入多邊形的保留邊界之間，從而 使剪裁后的多邊形的邊仍然保持封閉狀態(tài) 。 ? 新的問題 ： 1）邊界不再封閉，需要用窗口邊界的恰當部分來封閉它，如何確定其邊界？ 多邊形裁剪 2）一個凹多邊形可能被裁剪成幾個小的多邊形，如何 確定這些小多邊形的邊界？ SutherlandHodgman算法 ? 思路 ： 將多邊形邊界作為一個整體，分而治之 。將多邊形的各邊先相對于窗口的某一條邊界進行裁剪，然后將裁剪結果再與另一條邊界進行裁剪，如此重復多次，便可得到最終結果。 ? 流水線過程 (左上右下 )： 左邊的結果是上邊的開始。 亦稱 逐邊裁剪算法 SutherlandHodgman
教學課件相關推薦
鄂ICP備17016276號-1