關(guān)于二維圖形的裁剪第1頁，講稿共93頁，2023年5月2日，星期三2023/6/27計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院2二維裁剪識別圖形在指定區(qū)域內(nèi)和區(qū)域外的部分的過程稱為裁剪算法，簡稱裁剪（clipping）二維窗口是投影平面上的一個矩形。一般來說，這個矩形的邊和投影平面上的坐標(biāo)軸平行，圖形在窗口內(nèi)的部分被顯示出來，窗口外的部分被裁剪掉了。平面上的圖形受該矩形的裁剪稱為二維裁剪。第2頁，講稿共93頁，2023年5月2日，星期三2023/6/27計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院3裁剪的應(yīng)用從定義的場景中抽取用于觀察的部分在三維視圖中識別出可見面防止線段或?qū)ο蟮倪吔缁煜脤?shí)體造型來創(chuàng)建對象顯示多窗口的環(huán)境允許選擇圖形的一部分來進(jìn)行拷貝、移動或刪除等繪圖操作裁剪算法類型圖形裁剪與窗口——視圖變換的先后窗口邊界裁剪視區(qū)邊界裁剪圖形生成與裁剪先后先生成后裁剪先裁剪后生成第3頁，講稿共93頁，2023年5月2日，星期三2023/6/27計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院4點(diǎn)的裁剪圖形裁剪中的最基本的問題。假設(shè)裁剪窗口為一個在標(biāo)準(zhǔn)位置的矩形，即邊與坐標(biāo)軸平行的矩形，由上（y=ymin）、下（y=ymax）、左（x=xmin）、右（x=xmax）四條邊描述。點(diǎn)(x,y)在窗口內(nèi)的充分必要條件是：裁剪窗口（Xmin，Xmax，Ymin，Ymax）是世界坐標(biāo)系的窗口邊界或視區(qū)邊界應(yīng)用舉例爆炸場景或海面泡沫的顯示問題：對于任何多邊形窗口，如何判別？(xmin,ymin)(xmax,ymax)第4頁，講稿共93頁，2023年5月2日，星期三2023/6/27計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院5直線段裁剪直線段裁剪算法是復(fù)雜圖形裁剪的基礎(chǔ)。復(fù)雜的曲線可以通過折線段來近似，從而裁剪問題也可以化為直線段的裁剪問題。裁剪的目的判斷圖形元素是否落在裁剪窗口之內(nèi)并找出其位于內(nèi)部的部分裁剪處理的基礎(chǔ)圖元關(guān)于窗口內(nèi)外關(guān)系的判別圖元與窗口的求交假定條件矩形裁剪窗口：[xmin,xmax]X[ymin,ymax]待裁剪線段：第5頁，講稿共93頁，2023年5月2日，星期三2023/6/27計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院6直線段裁剪待裁剪線段和窗口的關(guān)系

（1）完全落在窗口內(nèi)，線段完全可見（2）完全落在窗口外，顯然不可見（3）與窗口邊界相交，線段至少有一端點(diǎn)在窗口之外，但非顯然不可見

第6頁，講稿共93頁，2023年5月2日，星期三2023/6/27計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院7 要確定一條直線段上位于窗口內(nèi)的可見段，只須求出它的兩個位于窗口內(nèi)的可見端點(diǎn)即可。算法的基本思想 把所有的直線按照它和窗口的關(guān)系分類，不同的直線使用不同的處理方法確定其可見部分。第7頁，講稿共93頁，2023年5月2日，星期三2023/6/27計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院8為提高效率，算法設(shè)計(jì)時(shí)應(yīng)考慮：(一）快速判斷情形(1)(2)；(二)設(shè)法減少情形(3)求交次數(shù)和每次求交時(shí)所需的計(jì)算量。直線裁剪算法的主要步驟：首先將不需要裁剪的直線挑出，并刪去其中在窗外的直線；其次，對其余直線，逐條與窗框求交點(diǎn)，并將窗外部分刪去第8頁，講稿共93頁，2023年5月2日，星期三2023/6/27計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院9實(shí)交點(diǎn)是直線段與窗口矩形邊界的交點(diǎn)。虛交點(diǎn)則是直線段與窗口矩形邊界延長線或直線段的延長線與窗口矩形邊界的交點(diǎn)。

第9頁，講稿共93頁，2023年5月2日，星期三2023/6/27計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院10直線的剪裁算法直接求交算法矢量裁剪法Cohen-Sutherland算法中點(diǎn)分割算法梁友棟－Barsky算法Nicholl-Lee-Nicholl算法第10頁，講稿共93頁，2023年5月2日，星期三2023/6/27計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院11直接求交算法直線與窗口邊都寫成參數(shù)形式，求參數(shù)值。第11頁，講稿共93頁，2023年5月2日，星期三2023/6/27計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院12矢量裁剪法算法思想先從線段的一個端點(diǎn)出發(fā)進(jìn)行判斷或進(jìn)行求交運(yùn)算，所得交點(diǎn)坐標(biāo)保存在（xs，ys）中，然后再從線段的另一個端點(diǎn)出發(fā)用前面的判斷及其求交運(yùn)算求得交點(diǎn)坐標(biāo)（x，y），最后只輸出兩個交點(diǎn)間的線段。用窗口的四條邊界的直線將窗口分為9個區(qū)。012345678(x2,y2)ybytxlxr(x1,y1)第12頁，講稿共93頁，2023年5月2日，星期三2023/6/27計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院13排斥性測試若線段滿足下述四個條件之一時(shí)：max(x1,x2)≤xlmin(x1,x2)≥xrmax(y1,y2)≤ybmin(y1,y2)≥yt則線段必定位于窗口之外，無輸出線段。包含性測試若線段滿足：xl≤x1≤xr,yb≤y1≤yt,則線段的始點(diǎn)在0區(qū)，也即線段可見段的起點(diǎn)為：

xs=x1,

ys=y1第13頁，講稿共93頁，2023年5月2日，星期三2023/6/27計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院14求交點(diǎn)，并判斷I.若x1＜xl,則：線段的起點(diǎn)坐標(biāo)可能位于3區(qū)、4區(qū)、5區(qū)。而新起點(diǎn)的坐標(biāo)可能在直線y=yb和線段的交點(diǎn)上直線y=yt和線段的交點(diǎn)上直線x=xl和線段的交點(diǎn)上012345678(x1,y1)(x2,y2)ybytxlxr第14頁，講稿共93頁，2023年5月2日，星期三2023/6/27計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院15第一種情況：此時(shí)，若xl≤xs≤xr則(xsys)為有效新起點(diǎn)。第二種情況：此時(shí)，若xl≤xs≤xr則(xsys)為有效新起點(diǎn)。第三種情況：此時(shí)，若yb≤ys≤yt則(xsys)為有效新起點(diǎn)。三種情況都不滿足，則此線段不在窗口區(qū)內(nèi)。第15頁，講稿共93頁，2023年5月2日，星期三2023/6/27計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院16II.若x1>xr

線段的起點(diǎn)坐標(biāo)可能位于6區(qū)、7區(qū)、8區(qū)。而新起點(diǎn)的坐標(biāo)可能在直線y=yb和線段的交點(diǎn)上直線y=yt和線段的交點(diǎn)上直線x=xr和線段的交點(diǎn)上012345678(x1,y1)ybytxlxr第16頁，講稿共93頁，2023年5月2日，星期三2023/6/27計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院17第一種情況：此時(shí)，若xl≤xs≤xr則(xsys)為有效新起點(diǎn)。第二種情況：此時(shí)，若xl≤xs≤xr則(xsys)為有效新起點(diǎn)。第三種情況： 此時(shí)，若yb≤ys≤yt則(xsys)為有效新起點(diǎn)。若此三種情況都不滿足，則此線段不在窗口區(qū)內(nèi)。第17頁，講稿共93頁，2023年5月2日，星期三2023/6/27計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院18III若Xl<=X<=Xr線段的起點(diǎn)坐標(biāo)可能位于1區(qū)和2區(qū)。而新起點(diǎn)的坐標(biāo)可能在直線y=yb和線段的交點(diǎn)上直線y=yt和線段的交點(diǎn)上012345678(x1,y1)ybytxlxr第18頁，講稿共93頁，2023年5月2日，星期三2023/6/27計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院19第一種情況：此時(shí)，若xl≤xs≤xr則(xsys)為有效新起點(diǎn)。第二種情況：

此時(shí)，若xl≤xs≤xr則(xsys)為有效新起點(diǎn)。若此二種情況都不滿足，則此線段不在窗口區(qū)內(nèi)。使用同樣的方法，可得到直線在窗口的另一個可見端點(diǎn)。第19頁，講稿共93頁，2023年5月2日，星期三2023/6/27計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院20Cohen-Sutherland算法(編碼算法)基本思想：Cohen-Sutherland直線剪裁算法以區(qū)域編碼為基礎(chǔ)，將窗口及其周圍的八個方向以4bit的二進(jìn)制數(shù)進(jìn)行編碼。對每條直線段p0(x0,y0)p1(x1,y1)分三種情況處理：(1)直線段完全可見，“簡取”之。(2)直線段完全不可見，“簡棄”之。(3)直線段既不滿足“簡取”的條件，也不滿足“簡棄”的條件，需要對直線段按交點(diǎn)進(jìn)行分段，分段后重復(fù)上述處理。

第20頁，講稿共93頁，2023年5月2日，星期三2023/6/27計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院21算法步驟：第一步判別線段兩端點(diǎn)是否都落在窗口內(nèi)，如果是，則線段完全可見；否則進(jìn)入第二步；第二步判別線段是否為顯然不可見，如果是，則裁剪結(jié)束；否則進(jìn)行第三步；第三步求線段與窗口邊延長線的交點(diǎn)，這個交點(diǎn)將線段分為兩段，其中一段顯然不可見，丟棄。對余下的另一段重新進(jìn)行第一步，第二步判斷，直至結(jié)束

裁剪過程是遞歸的。第21頁，講稿共93頁，2023年5月2日，星期三2023/6/27計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院22第22頁，講稿共93頁，2023年5月2日，星期三2023/6/27計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院23Cohen-SutherLand算法(編碼算法)特點(diǎn)：對顯然不可見線段的快速判別編碼方法：延長窗口的四條邊線，由窗口四條邊所在直線把二維平面分成9個區(qū)域，每個區(qū)域賦予一個四位編碼，CtCbCrCl，上下右左；左域右域上域下域內(nèi)域第23頁，講稿共93頁，2023年5月2日，星期三2023/6/27計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院24第一位1：點(diǎn)處于上邊框線的上邊；第二位1：點(diǎn)處于下邊框線的下邊；第三位1：點(diǎn)處于右邊框線的右邊；第四位1：點(diǎn)處于左邊框線的左邊；顯然：如果某線段的兩端點(diǎn)的兩個四位代碼全為零時(shí)那么該線段完全位于窗口內(nèi)，即全為“0000”，可直接保留；如果兩端點(diǎn)的標(biāo)識碼的邏輯與（按位乘）運(yùn)算，結(jié)果不為零，那么該線段必位于窗口外，可直接舍棄。否則，這一線段可能與窗口相交。此時(shí)，需要對線段進(jìn)行再分割，即找到與窗口邊線的一個交點(diǎn)，根據(jù)交點(diǎn)位置，賦予四位二進(jìn)制編碼，然后再進(jìn)行上述測試，測試結(jié)果是必有一段在窗口之外，可被排除，另一段再重復(fù)上述處理過程。直到全部線段均被舍棄或被保留為止。第24頁，講稿共93頁，2023年5月2日，星期三2023/6/27計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院25Cohen-SutherLand算法(編碼算法)端點(diǎn)編碼：定義為它所在區(qū)域的編碼結(jié)論：當(dāng)線段的兩個端點(diǎn)的編碼的邏輯“與”非零時(shí)，線段為顯然不可見的第25頁，講稿共93頁，2023年5月2日，星期三2023/6/27計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院26求交測試順序固定(左上右下）最壞情形，線段求交四次。Cohen-SutherLand算法(編碼算法)對于那些非完全可見、又非顯然不可見的線段，需要求交（如，線段AD)，求交前先測試與窗口哪條邊所在直線有交？(按序判斷端點(diǎn)編碼中各位的值ClCtCrCb）第26頁，講稿共93頁，2023年5月2日，星期三2023/6/27計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院27

1）特點(diǎn)：容易將不需要裁剪的直線挑出。規(guī)則是：如果一條直線的兩端在同一區(qū)域，則該直線不需要裁剪，否則該直線為可能裁剪直線。對可能裁剪的直線縮小了與之求交的邊框范圍。規(guī)則是：如果直線的一個端點(diǎn)在上（下、左、右）域，則此直線與上邊框求交，然后刪去上邊框以上的部分。該規(guī)則對直線的另一端點(diǎn)也適用。一條直線至多只需要與兩條邊框求交。用編碼方法可快速判斷線段--完全可見和顯然不可見。

2）特別適用二種場合：大窗口場合；窗口特別小的場合，如光標(biāo)拾取圖形時(shí),光標(biāo)看作小的裁剪窗口。第27頁，講稿共93頁，2023年5月2日，星期三2023/6/27計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院28例題：P1P2P1：(-3/2,1/6)；編碼(0001)P2：(1/2,3/2)；編碼(1000)(2)求右邊交點(diǎn)，得P’’1(1,11/6)P2(-1,1/2)；并編碼，判別之不可見求左邊交點(diǎn)，得P’1P2;P’1:(-1,1/2);編碼(0000)

判別知非完全可見，且P’1在窗口內(nèi)，因此交換P’1P2得新線段P1P2；

P1：(1/2,3/2)；編碼(1000) P2：(-1,1/2)；編碼(0000)(3)求上邊交點(diǎn)，得P’’’1(-1/4,1)P2(-1,1/2)；并編碼，兩端點(diǎn)編碼全部為0，線段完全可見，程序結(jié)束P1’P1’’P’’’1第28頁，講稿共93頁，2023年5月2日，星期三2023/6/27計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院29Cohen-SutherLand算法(編碼算法)如何判定該與窗口的哪條邊求交呢？ 編碼中對應(yīng)位為1的邊。2）if(ai=bi=ci=di=0)則顯示整條直線，取出下一條直線，返回1）；否則if((a1&a2)or(b1&b2)or(c1&c2)or(d1&b2)=1)則取出下一條直線，返回1）；否則例子：依次對每條直線P1P2作如下處理1）對直線兩端點(diǎn)P1、P2按各自所在的區(qū)域編碼，P1、P2的編碼分別記為：C1(P1)={a1,b1,c1,d1}，C2(P2)={a2,b2,c2,d2}其中ai，bi，ci，di取值域?yàn)閧0，1}，i={1,2}第29頁，講稿共93頁，2023年5月2日，星期三2023/6/27計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院303）if(a1&a2=1)，則求直線與窗上邊（y＝y(tǒng)w_max)之交點(diǎn)，并刪去交點(diǎn)以上部分；

if(b1&b2=1)，則求直線與窗下邊（y＝y(tǒng)w_min)之交點(diǎn)，并刪去交點(diǎn)以下部分；if(c1&c2=1)，則求直線與窗右邊（x＝xw_max)之交點(diǎn)，并刪去交點(diǎn)以右部分；if(d1&d2=1)，則求直線與窗左邊（x＝xw_max)之交點(diǎn)，并刪去交點(diǎn)以左部分；4）返回1）。第30頁，講稿共93頁，2023年5月2日，星期三2023/6/27計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院31第31頁，講稿共93頁，2023年5月2日，星期三2023/6/27計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院32中點(diǎn)分割算法基本思想：

從P0點(diǎn)出發(fā)找出離P0最近的可見點(diǎn)，和從P1點(diǎn)出發(fā)找出離P1最近的可見點(diǎn)。這兩個可見點(diǎn)的連線就是原線段的可見部分。定義：

線段端點(diǎn)的最近可見點(diǎn)是指任一線段被窗口裁剪后所得兩個新端點(diǎn)中離該端點(diǎn)較近的一個點(diǎn)。從P0點(diǎn)出發(fā)找出距P0最近的可見點(diǎn)（圖中為A點(diǎn)），從P1點(diǎn)出發(fā)找出距P1最近的可見點(diǎn)（圖中為B）。取中點(diǎn)Pm=(P1+P2)/2。第32頁，講稿共93頁，2023年5月2日，星期三2023/6/27計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院33中點(diǎn)分割法與前一種Cohen-Sutherland算法一樣首先對線段端點(diǎn)進(jìn)行編碼，并把線段與窗口的關(guān)系分為三種情況:全在、完全不在和線段與窗口有交。

對前兩種情況，進(jìn)行一樣的處理。對第三類線段的處理

當(dāng)對直線段不能簡取也不能簡棄時(shí)，不斷地用對分方法，舍去線段的不可見部分，用中點(diǎn)去逼近線段與窗口邊界的交點(diǎn)。 簡單地用中點(diǎn)分割的方法求出線段與 窗口的交點(diǎn)，把線段等分為二段，對 兩段重復(fù)上述測試處理，直至每條線 段完全在窗口內(nèi)或完全在窗口外。第33頁，講稿共93頁，2023年5月2日，星期三2023/6/27計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院34實(shí)現(xiàn)算法：（以P0點(diǎn)為例說明）

1)排斥性測試 測試線段是否完全被排斥在窗口之外，若是，則無線段輸出，算法結(jié)束。否則執(zhí)行下一步；

2)包含性測試 測試P1點(diǎn)是否包含在窗口內(nèi)，如果是，則P1點(diǎn)即為P0的最遠(yuǎn)可選點(diǎn)，算法結(jié)束，否則，執(zhí)行下一步；

3)將直線段P0P1于中點(diǎn)Pm處分割，則分如下幾種情況處理：第34頁，講稿共93頁，2023年5月2日，星期三2023/6/27計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院35線段MP1完全在窗口之外，那么便以線段P0M為新的線段P0P1，然后返回算法的第一步重新開始測試；如果線段MP1沒有被完全排斥在窗口之外，那么便以線段MP1作為新線段P0P1，然后返回算法的第一步。P0P1MP0P1MP0P1MP0P1M第35頁，講稿共93頁，2023年5月2日，星期三2023/6/27計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院36中點(diǎn)分割算法-求線段與窗口的交點(diǎn)從P0出發(fā)找距離P0最近可見點(diǎn)采用中點(diǎn)分割方法先求出P0P1的中點(diǎn)Pm,若P0Pm不是顯然不可見的， 并且P0P1在窗口中有可見部分， 則距P0最近的可見點(diǎn)一定落在

P0Pm上，所以用P0Pm代替P0P1；否則取PmP1代替P0P1。再對新的P0P1求中點(diǎn)Pm。重復(fù)上述過程，直到PmP1長度小于給定的控制常數(shù)為止，此時(shí)Pm收斂于交點(diǎn)。從P1出發(fā)找距離P1最近可見點(diǎn)采用上面類似方法。第36頁，講稿共93頁，2023年5月2日，星期三2023/6/27計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院37中點(diǎn)分割算法框圖第37頁，講稿共93頁，2023年5月2日，星期三2023/6/27計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院38算法步驟：(1)輸入直線段的兩端點(diǎn)坐標(biāo)：p0(x0,y0)、p1(x1,y1)，以及窗口的四條邊界坐標(biāo)：ymin、ymax、xmin和xmax。(2)對p0、p1進(jìn)行編碼：點(diǎn)p0的編碼為code1，點(diǎn)p1的編碼為code2。(3)若code1|code2=0，對直線段應(yīng)簡取之，保留當(dāng)前直線段的端點(diǎn)坐標(biāo)，轉(zhuǎn)(5)；否則，若code1&code2≠0，對直線段可簡棄之，轉(zhuǎn)(5)；當(dāng)上述兩條均不滿足時(shí)，進(jìn)行步驟(4)。(4)求出直線段的中點(diǎn)M，將p1M、p2M入棧。(5)當(dāng)棧不空時(shí)，從棧中彈出一條直線段，取為p0p1，轉(zhuǎn)(2)進(jìn)行處理。否則，繼續(xù)(6)。(6)當(dāng)棧為空時(shí)，合并保留的直線段端點(diǎn)，得到窗口內(nèi)的直線段p0p1。用直線掃描轉(zhuǎn)換算法畫出當(dāng)前的直線段p0p1，算法結(jié)束。第38頁，講稿共93頁，2023年5月2日，星期三2023/6/27計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院39 中點(diǎn)分割算法的核心思想是通過二分逼近來確定直線段與窗口的交點(diǎn)。第39頁，講稿共93頁，2023年5月2日，星期三2023/6/27計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院40第40頁，講稿共93頁，2023年5月2日，星期三2023/6/27計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院41重新構(gòu)造算法步驟：(1)若code1|code2=0，對直線段應(yīng)簡取之，結(jié)束；否則，若code1&code2≠0，對直線段可簡棄之，結(jié)束；當(dāng)這兩條均不滿足時(shí)，進(jìn)行步驟(2)。(2)找出該直線段離窗口邊界最遠(yuǎn)的點(diǎn)和該直線段的中點(diǎn)。判中點(diǎn)是否在窗口內(nèi)：若中點(diǎn)不在窗口內(nèi)，則把中點(diǎn)和離窗口邊界最遠(yuǎn)點(diǎn)構(gòu)成的線段丟掉，以線段上的另一點(diǎn)和該中點(diǎn)再構(gòu)成線段求其中點(diǎn)；如中點(diǎn)在窗口內(nèi)，則又以中點(diǎn)和最遠(yuǎn)點(diǎn)構(gòu)成線段，并求其中點(diǎn)，直到中點(diǎn)與窗口邊界的坐標(biāo)值在規(guī)定的誤差范圍內(nèi)相等，則該中點(diǎn)就是該線段落在窗口內(nèi)的一個端點(diǎn)坐標(biāo)。(3)如另一點(diǎn)在窗口內(nèi)，則經(jīng)(2)即確定了該線段在窗口內(nèi)的部分。如另一點(diǎn)不在窗口內(nèi)，則該點(diǎn)和所求出的在窗口上的那一點(diǎn)構(gòu)成一條線段，重復(fù)步驟(2)，即可求出落在窗口內(nèi)的另一點(diǎn)。第41頁，講稿共93頁，2023年5月2日，星期三2023/6/27計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院42第42頁，講稿共93頁，2023年5月2日，星期三2023/6/27計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院43

#defineTRUE1#defineFALSE0intmid_trim(p1,p2,xmin,ymin,xmax,ymax,a)floatp1[3],p2[3],xmin,ymin,xmax,ymax,a[3];{floatA[3],B[3],M[3];set_point(p1,A);set_point(p2,B);while(TRUE){if(Identify_line_out(A,B,xmin,ymin,xmax,ymax)==TRUE)retuenFALSE;if(Identify_pt_in(B,xmin,ymin,xmax,ymax)==TRUE){set_point(B,a);returnTRUE;}第43頁，講稿共93頁，2023年5月2日，星期三2023/6/27計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院44

else{get_midpoint(A,B,M);if(Identify_line_out(M,B,xmin,ymin,xmax,ymax)==TRUE){set_point(M,B);}else{set_point(M,A);}}}第44頁，講稿共93頁，2023年5月2日，星期三2023/6/27計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院45第45頁，講稿共93頁，2023年5月2日，星期三2023/6/27計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院46對分辯率為2N*2N的顯示器，上述二分過程至多進(jìn)行N次。主要過程只用到加法和除法運(yùn)算，適合硬件實(shí)現(xiàn)，它可以用左右移位來代替乘除法，這樣就大大加快了速度。中點(diǎn)分割裁剪算法第46頁，講稿共93頁，2023年5月2日，星期三2023/6/27計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院47梁友棟－Barsky算法算法基本思想：設(shè)要裁剪的線段為P0P1

，和窗口邊界交于A,B,C,D四點(diǎn)。首先從D、A和P0三點(diǎn)中找出最靠近P1的點(diǎn)。圖中顯然為A其次從C、B和P1中找出最靠近P0的點(diǎn)，圖中顯然為B那么AB就是P0P1線段上的可見部分第47頁，講稿共93頁，2023年5月2日，星期三2023/6/27計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院48梁友棟－Barsky算法具體計(jì)算時(shí)將P0P1寫成參數(shù)方程其中：0<=t<=1第48頁，講稿共93頁，2023年5月2日，星期三2023/6/27計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院49梁友棟－Barsky算法窗口邊界分類：始邊和終邊第49頁，講稿共93頁，2023年5月2日，星期三2023/6/27計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院50梁友棟－Barsky算法——交點(diǎn)計(jì)算xyyTyBxLxBABCDP1P0第50頁，講稿共93頁，2023年5月2日，星期三2023/6/27計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院51梁友棟－Barsky算法為了確定始邊和終邊，以及求P0P1與它們的交點(diǎn)，令易知交點(diǎn)的參數(shù)為第51頁，講稿共93頁，2023年5月2日，星期三2023/6/27計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院52梁友棟－Barsky算法EFAB分析另外一個D第52頁，講稿共93頁，2023年5月2日，星期三2023/6/27計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院53梁友棟-Barsky算法當(dāng)Qi=0時(shí)若Di<0時(shí)，線段不可見（如圖中AB，有QR=0，DR<0）若Di>0時(shí),分析另一D,

（如圖中的EF就是這種情況，它使QL=0，DL>0和QR=0，DR>0。這時(shí)由于EF和x=xL及x=xR平行，故不必去求出EF和x=xL及x=xR的交點(diǎn)，而讓EF和y=yT及y=yB的交點(diǎn)決定直線段上的可見部分。）EFAB第53頁，講稿共93頁，2023年5月2日，星期三2023/6/27計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院54P1yxyTyBxLxBABCDP0t0’t0’’t1’t1’’lP0lP1第54頁，講稿共93頁，2023年5月2日，星期三2023/6/27計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院55第55頁，講稿共93頁，2023年5月2日，星期三2023/6/27計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院56Nicholl-Lee-Nicholl算法NLN算法在求交計(jì)算前進(jìn)行更多的區(qū)域測試來減少求交計(jì)算，消除C-S算法中多次求交的情況。基本想法：通過在裁剪窗口周圍創(chuàng)立多個區(qū)域來對一條直線段的多次裁剪。也即對2D平面的更細(xì)的劃分。第56頁，講稿共93頁，2023年5月2日，星期三2023/6/27計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院57Nicholl-Lee-Nicholl算法假定待裁剪線段P0P1為非完全可見且非顯然不可見。步驟：第一步，窗口四邊所在的直線將二維平面劃分成9個區(qū)域，假定落在區(qū)域0、4、5

第57頁，講稿共93頁，2023年5月2日，星期三2023/6/27計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院58Nicholl-Lee-Nicholl算法第二步：從P0點(diǎn)向窗口的四個角點(diǎn)發(fā)出射線，這四條射線和窗口的四條邊所在的直線一起將二維平面劃分為更多的小區(qū)域。此時(shí)P1的位置決定了P0P1和窗口邊的相交關(guān)系。第58頁，講稿共93頁，2023年5月2日，星期三2023/6/27計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院59Nicholl-Lee-Nicholl算法第三步，確定P1所在的區(qū)域（判斷P1所在區(qū)域位置，可判定P0、P1與窗口哪條邊求交)。 根據(jù)窗口四邊的坐標(biāo)值及P0P1和各射線的斜率可確定P1所在的區(qū)域。第四步，求交點(diǎn)，確定P0P1的可見部分特點(diǎn)：效率較高，但僅適合二維矩形窗口。第59頁，講稿共93頁，2023年5月2日，星期三2023/6/27計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院60非矩形窗口的線段裁剪思考：凹多邊形窗口的線段裁剪圓和曲線窗口的線段裁剪第60頁，講稿共93頁，2023年5月2日，星期三2023/6/27計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院61多邊形裁剪幾個概念凸多邊形如果多邊形任意兩個內(nèi)點(diǎn)的連線都在多邊形里，則該多邊形稱為凸多邊形；凹多邊形一個非凸多邊形稱為凹多邊形多邊形正方向頂點(diǎn)為P1,…,PN（并且邊為Pi-1Pi，PNP1）的多邊形，如果按照這種順序遍歷產(chǎn)生一個逆時(shí)針回路，則該多邊形被認(rèn)為是正方向的。第61頁，講稿共93頁，2023年5月2日，星期三2023/6/27計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院62多邊形裁剪錯覺：直線段裁剪的組合？新的問題：1）邊界不再封閉，需要用窗口邊界的恰當(dāng)部分來封閉它，如何確定其邊界？第62頁，講稿共93頁，2023年5月2日，星期三2023/6/27計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院63多邊形裁剪2）一個凹多邊形可能被裁剪成幾個小的多邊形，如何確定這些小多邊形的邊界？第63頁，講稿共93頁，2023年5月2日，星期三2023/6/27計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院64多邊形的剪裁算法Sutlerland－Hodgman算法Weiler－Athenton算法第64頁，講稿共93頁，2023年5月2日，星期三2023/6/27計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院65Sutherland-Hodgman算法對多邊形裁剪的Sutherland-Hodgman算法是一種簡便的方法，只要對多邊形用窗口的四條邊依次裁剪四次，便可得到裁剪后的多邊形。分割處理策略：將多邊形關(guān)于矩形窗口的裁剪分解為多邊形關(guān)于窗口四邊所在直線的裁剪。第65頁，講稿共93頁，2023年5月2日，星期三2023/6/27計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院66基本思想：1）令多邊形的頂點(diǎn)按邊線逆時(shí)針走向排序。各邊先與左窗邊求交。求交后刪去多邊形在窗之左的部分，并插入左窗邊及其延長線的交點(diǎn)之間的部分，從而形成一個新的多邊形。然后，新的多邊形按相同的方法與上窗邊相裁剪。如此重復(fù)，直至與各窗邊都裁剪完畢。2）多邊形與每一條窗邊相交，生成新的多邊形頂點(diǎn)序列的過程，是一個對多邊形各頂點(diǎn)依次處理的過程。第66頁，講稿共93頁，2023年5月2日，星期三2023/6/27計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院67第67頁，講稿共93頁，2023年5月2日，星期三2023/6/27計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院68第68頁，講稿共93頁，2023年5月2日，星期三2023/6/27計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院69第69頁，講稿共93頁，2023年5月2日，星期三2023/6/27計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院70Sutherland-Hodgman算法流水線過程(左上右下)：左邊的結(jié)果是上邊的開始。亦稱逐邊裁剪算法第70頁，講稿共93頁，2023年5月2日，星期三2023/6/27計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院71算法實(shí)施策略：為窗口各邊界裁剪的多邊形存儲輸入與輸出頂點(diǎn)表。在窗口的一條裁剪邊界處理完所有頂點(diǎn)后，其輸出頂點(diǎn)表將用窗口的下一條邊界繼續(xù)裁剪。窗口的一條邊以及延長線構(gòu)成的裁剪線把平面分為兩個區(qū)域，包含有窗口區(qū)域的一個域稱為可見側(cè)；不包含窗口區(qū)域的域?yàn)椴豢梢妭?cè)。第71頁，講稿共93頁，2023年5月2日，星期三2023/6/27計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院72沿著多邊形依次處理頂點(diǎn)會遇到四種情況：第72頁，講稿共93頁，2023年5月2日，星期三2023/6/27計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院73第73頁，講稿共93頁，2023年5月2日，星期三2023/6/27計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院74Sutherland-Hodgman算法框圖是否第一點(diǎn)?取點(diǎn)PSPFPS在e的可見側(cè)退出輸出SSP和e相交？計(jì)算SP和e的交點(diǎn)I輸出I(a)(b)是是是否是否否否開始處理線段SP頂點(diǎn)輸入完畢？退出第74頁，講稿共93頁，2023年5月2日，星期三2023/6/27計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院75設(shè)封閉多邊形的頂點(diǎn)為P1,P2,…Pn，框圖中e是表示窗口的四條邊中正在裁剪的一條邊，每次裁剪時(shí)第一個點(diǎn)存放在F中，以便對最后一條邊裁剪時(shí)使用。用圖（a）中的算法對邊P1P2,P2P3,…Pn-1Pn作裁剪，用圖（b）中的算法對最后一條邊PnP1作裁剪。裁剪好一條邊便輸出一條邊。上述算法僅用一條裁剪邊對多邊形進(jìn)行裁剪，得到一個頂點(diǎn)序列，作為下一條裁剪邊處理過程的輸入。第75頁，講稿共93頁，2023年5月2日，星期三2023/6/27計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院76Sutherland-Hodgman算法裁剪結(jié)果的頂點(diǎn)構(gòu)成：裁剪邊內(nèi)側(cè)的原頂點(diǎn)；多邊形的邊與裁剪邊的交點(diǎn)。順序連接。幾點(diǎn)說明：裁剪算法采用流水線方式，適合硬件實(shí)現(xiàn)?？赏茝V到任意凸多邊形裁剪窗口第76頁，講稿共93頁，2023年5月2日，星期三2023/6/27計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院77Weiler-Athenton算法裁剪窗口為任意多邊形（凸、凹、帶內(nèi)環(huán)）的情況：主多邊形：被裁剪多邊形，記為A裁剪多邊形：裁剪窗口，記為B第77頁，講稿共93頁，2023年5月2日，星期三2023/6/27計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院78主多邊形和裁剪多邊形把二維平面分成兩部分。內(nèi)裁剪：A∩B外裁剪：A-BWeiler-Athenton算法裁剪結(jié)果區(qū)域的邊界由A的部分邊界和B的部分邊界兩部分構(gòu)成，并且在交點(diǎn)處邊界發(fā)生交替，即由A的邊界轉(zhuǎn)至B的邊界，或由B的邊界轉(zhuǎn)至A的邊界

第78頁，講稿共93頁，2023年5月2日，星期三2023/6/27計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院79Weiler-Athenton算法如果主多邊形與裁剪多邊形有交點(diǎn)，則交點(diǎn)成對出現(xiàn)，它們被分為如下兩類：進(jìn)點(diǎn)：主多邊形邊界由此進(jìn)入裁剪多邊形內(nèi)如，I1,I3,I5,I7,I9,I11出點(diǎn)：主多邊形邊界由此離開裁剪多邊形區(qū)域.

如，I0,I2,I4,I6,I8,I10第79頁，講稿共93頁，2023年5月2日，星期三2023/6/27計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院80Weiler-Athenton算法1）建頂點(diǎn)表；2）求交點(diǎn)；3）裁剪……Weiler_Athenton裁剪算法（內(nèi)裁剪）步驟：1、建立主多邊形和裁剪多邊的頂點(diǎn)表．2、求主多邊形和裁剪多邊形的交點(diǎn)，并將這些交點(diǎn)按順序插入兩多邊形的頂點(diǎn)表中。在兩多邊表形頂點(diǎn)表中的相同交點(diǎn)間建立雙向指針。3、裁剪如果存在沒有被跟蹤過的交點(diǎn)，執(zhí)行以下步驟：

第80頁，講稿共93頁，2023年5月2日，星期三2023/6/27計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院81

(1)建立裁剪結(jié)果多邊形的頂點(diǎn)表．

(2)選取任一沒有被跟蹤過的交點(diǎn)為始點(diǎn)，將其輸出到結(jié)果多邊形頂點(diǎn)表中．

(3)如果該交點(diǎn)為進(jìn)點(diǎn)，跟蹤主多邊形邊界；否則跟蹤裁剪多邊形邊界．

(4)跟蹤多邊形邊界，每遇到多邊形頂點(diǎn)，將其輸出到結(jié)果多邊形頂點(diǎn)表中，直至遇到新的交點(diǎn)．

(5)將該交點(diǎn)輸出到結(jié)果多邊形頂點(diǎn)表中，并通過連接該交點(diǎn)的雙向指針改變跟蹤方向（如果上一步跟蹤的是主多邊形邊界，現(xiàn)在改為跟蹤裁剪多邊形邊界；如果上一步跟蹤裁剪