第五章二維變換與裁剪

孔令德

二維變換與裁剪第五章齊次坐標(biāo)二維幾何變換矩陣Cohen-Sutherland直線段裁剪算法中點(diǎn)分割直線段裁剪算法Liang-Barsky直線段裁剪算法Sutherland-Hodgman多邊形裁剪算法本章學(xué)習(xí)目標(biāo)5.1圖形幾何變換基礎(chǔ)5.2二維圖形基本幾何變換矩陣5.3二維復(fù)合變換5.4二維圖形裁剪5.5Cohen-Sutherland直線裁剪算法5.6中點(diǎn)分割直線段裁剪算法5.7Liang－Barsky直線段裁剪算法5.8多邊形裁剪算法5.9本章小結(jié)本章內(nèi)容5.1圖形幾何變換基礎(chǔ)

圖形的幾何變換是對(duì)圖形進(jìn)行平移、比例、旋轉(zhuǎn)、反射和錯(cuò)切5種變換。圖5-1是使用二維變換的平移與旋轉(zhuǎn)，將一塊地板磚鋪設(shè)在九宮格內(nèi)的效果圖。圖形幾何變換可以分為二維圖形幾何變換和三維圖形幾何變換，而二維圖形幾何變換是三維圖形幾何變換的基礎(chǔ)

。

5-1九宮格內(nèi)鋪設(shè)地板磚

（a）單塊地板磚圖案（b）地板磚圖案九宮格內(nèi)鋪設(shè)效果圖二維幾何變換示例5.1.1二維變換矩陣二維幾何變換矩陣T是一個(gè)3×3的方陣，簡(jiǎn)稱為二維變換矩陣。（5-1）從功能上可以把二維變換矩陣T分為4個(gè)子矩陣。其中是對(duì)圖形進(jìn)行比例變換、旋轉(zhuǎn)變換、反射變換是對(duì)圖形進(jìn)行平移變換；

和錯(cuò)切變換；是對(duì)圖形進(jìn)行投影變換；是對(duì)圖形進(jìn)行整體比例變換。齊次坐標(biāo)就是用n＋1維矢量表示n維矢量。例如，在二維平面中，點(diǎn)P(x,y)的齊次坐標(biāo)表示為(wx,wy,w)。類似地，在三維空間中，點(diǎn)P(x,y,z)的齊次坐標(biāo)表示為（wx,wy,wz,w）。w＝1就是規(guī)范化的齊次坐標(biāo)。二維點(diǎn)P(x，y)的規(guī)范化齊次坐標(biāo)為〔x，y，1〕，三維點(diǎn)P(x，y，z)的規(guī)范化齊次坐標(biāo)為(x，y，z，1)。定義了規(guī)范化齊次坐標(biāo)以后，圖形幾何變換可以表示為圖形頂點(diǎn)集合的規(guī)范化齊次坐標(biāo)矩陣與某一變換矩陣相乘的形式。5.1.2規(guī)范化齊次坐標(biāo)

假設(shè)變換前的二維點(diǎn)為變換后的該點(diǎn)為問(wèn)題是1×2的行矩陣無(wú)法，二維點(diǎn)可以使用行矢量矩陣表示。與3×3的二維變換矩陣相乘。為此引入規(guī)范化齊次坐標(biāo)。無(wú)法對(duì)于n×3的矩陣P和3×3的矩陣T，令m=n-1則矩陣相乘公式如下：

5.1.3矩陣相乘（5-2）由線性代數(shù)知道，矩陣乘法不滿足交換律，只有左矩陣的列數(shù)等于右矩陣的行數(shù)時(shí)，兩個(gè)矩陣才可以相乘。對(duì)于二維變換的兩個(gè)3×3的方陣P和T，如對(duì)三角形實(shí)施二維幾何變換，矩陣相乘公式為5.1.4二維幾何變換

二維幾何變換的基本方法是把變換矩陣作為一個(gè)算子，作用到變換前的圖形頂點(diǎn)集合的規(guī)范化齊次坐標(biāo)矩陣上，得到變換后新的圖形頂點(diǎn)集合的規(guī)范化齊次坐標(biāo)矩陣。設(shè)變換前圖形頂點(diǎn)集合的規(guī)范化齊次坐標(biāo)矩陣為變換后圖形頂點(diǎn)集合的規(guī)范化齊次坐標(biāo)矩陣為二維變換矩陣為二維幾何變換公式為

（5-3）5.2二維基本幾何變換矩陣二維基本幾何變換是指相對(duì)于坐標(biāo)原點(diǎn)和坐標(biāo)軸進(jìn)行的幾何變換，包括平移、比例、旋轉(zhuǎn)、反射和錯(cuò)切五種變換。本節(jié)以點(diǎn)的二維基本幾何變換為例進(jìn)行講解。二維坐標(biāo)點(diǎn)的基本幾何變換可以表示為的形式，為變換前的二維坐標(biāo)點(diǎn)，的二維坐標(biāo)坐標(biāo)點(diǎn)，T為3×3的變換矩陣。其中，為變換后5.2.1平移變換矩陣

平移變換是指將坐標(biāo)點(diǎn)從位置移動(dòng)到位置的過(guò)程，如圖5-2所示。平移變換的坐標(biāo)表示為。圖5-2平移變換相應(yīng)的齊次坐標(biāo)矩陣表示為二維平移變換矩陣（5-4）式中，Tx，Ty為平移參數(shù)。5.2.2比例變換矩陣

比例變換是指坐標(biāo)點(diǎn)相對(duì)于坐標(biāo)原點(diǎn)O，沿x比例變換的坐標(biāo)表示為相應(yīng)的齊次坐標(biāo)矩陣表示為方向縮放Sx倍，沿y方向縮放Sy倍，得到，如圖5-3所示。點(diǎn)的過(guò)程。二維比例變換矩陣（5-5）式中，Sx，Sy為比例系數(shù)。變換矩陣的子矩陣是對(duì)圖形作整體比例變換，關(guān)于這一點(diǎn)，讀者可以令Sx＝Sy＝S導(dǎo)出，請(qǐng)注意這里s＝1/S，即s>1時(shí)，圖形整體縮小；0<s<1時(shí)，圖形整體放大。

圖5-3比例變換當(dāng)Sx＝Sy且Sx、Sy大于1時(shí)，圖形等比放大；當(dāng)Sx＝Sy且Sx、Sy小于1大于0時(shí)，圖形等比縮??；當(dāng)Sx≠Sy時(shí)，圖形發(fā)生形變。5.2.3旋轉(zhuǎn)變換矩陣

rβPP’圖5-4旋轉(zhuǎn)變換α為點(diǎn)的起始角，β為點(diǎn)的逆時(shí)針?lè)较蛐D(zhuǎn)角（5-6）α點(diǎn)的坐標(biāo)表示為r點(diǎn)的坐標(biāo)表示為5.2.4反射變換矩陣

P’（a）關(guān)于原點(diǎn)反射（b）關(guān)于x軸反射（c）關(guān)于y軸反射圖5-5反射變換關(guān)于原點(diǎn)反射的坐標(biāo)表示為。相應(yīng)的齊次坐標(biāo)矩陣表示為關(guān)于原點(diǎn)的二維反射變換矩陣為（5-7）關(guān)于x軸的二維反射變換矩陣為（5-8）關(guān)于y軸的二維反射變換矩陣為（5-9）5.2.5錯(cuò)切變換矩陣

（a）正方形（b）沿x正向錯(cuò)切（c）沿x負(fù)向錯(cuò)切

（d）沿y正向錯(cuò)切（e）沿y負(fù)向錯(cuò)切（f）沿x和y正向錯(cuò)切圖5-6錯(cuò)切變換沿x，y方向的錯(cuò)切變換的坐標(biāo)表示為相應(yīng)的齊次坐標(biāo)矩陣表示為沿x，y兩個(gè)方向的二維錯(cuò)切變換矩陣為其中b、c為錯(cuò)切參數(shù)（5-10）元素大多為零，如果c和b不為零，則意味著對(duì)圖形進(jìn)行錯(cuò)切變換。令b＝0可以得到沿x方向的錯(cuò)切變換，c>0是沿x正向的錯(cuò)切變換，c<0是沿x負(fù)向的錯(cuò)切變換。令c＝0可以得到沿y方向的錯(cuò)切變換，b>0是沿y正向的錯(cuò)切變換，b<0是沿y負(fù)向的錯(cuò)切變換。在前面的變換中，子矩陣

的非對(duì)角線上面討論的五種變換給出的都是點(diǎn)變換的公式，圖形的變換實(shí)際上都可以通過(guò)點(diǎn)變換來(lái)完成。

例如直線段的變換可以通過(guò)對(duì)兩個(gè)頂點(diǎn)坐標(biāo)進(jìn)行變換，連接新頂點(diǎn)得到變換后的新直線段；

多邊形的變換可以通過(guò)對(duì)每個(gè)頂點(diǎn)進(jìn)行變換，連接新頂點(diǎn)得到變換后的新多邊形。

曲線的變換可通過(guò)變換控制多邊形的控制點(diǎn)后，重新繪制曲線來(lái)實(shí)現(xiàn)。

符合下面形式的坐標(biāo)變換稱為二維仿射變換（5-11）矩陣表示為（5-12）齊次矩陣表示為（5-13）變換后的坐標(biāo)x’和y’都是變換前的坐標(biāo)x和y的線性函數(shù)。參數(shù)aij是由變換類型確定的常數(shù)。仿射變換具有平行線變換成平行線，有限點(diǎn)映射為有限點(diǎn)的一般特性。

平移、比例、旋轉(zhuǎn)、反射和錯(cuò)切五種變換都是二維仿射變換的特例，任何一組二維仿射變換總可以表示為這五種變換的組合。仿射變換保持變換前后兩段直線間的角度、平行關(guān)系和長(zhǎng)度之比不改變。5.3二維復(fù)合變換

5.3.1復(fù)合變換原理

其中，T為復(fù)合變換矩陣，復(fù)合變換是指圖形做了一次以上的基本幾何變換，是基本幾何變換的組合形式，復(fù)合變換矩陣是基本幾何變換的組合矩陣。為n個(gè)單次基本幾何變換矩陣。通常。在復(fù)合變換中，矩陣相乘再計(jì)算。的順序不可交換。通常先計(jì)算出，5.3.2相對(duì)于任一參考點(diǎn)的二維幾何變換相對(duì)于任意一個(gè)參考點(diǎn)的變換方法為首先將參考點(diǎn)平移到坐標(biāo)原點(diǎn)，對(duì)坐標(biāo)原點(diǎn)進(jìn)行二維基本幾何變換，然后再將參考點(diǎn)平移回原位置。在5種變換中，比例變換和旋轉(zhuǎn)變換就是與參考點(diǎn)相關(guān)的變換。

例5-1一個(gè)由頂點(diǎn)P0（10，10），P1（30，10）和P2（20，25）定義的三角形，如圖5-7所示，相對(duì)于參考點(diǎn)Q（10，25）逆時(shí)針旋轉(zhuǎn)30o，求變換后的三角形頂點(diǎn)坐標(biāo)。P0P1P3QQP2P1P0（1）將Q點(diǎn)平移至坐標(biāo)原點(diǎn)，如圖5-8所示。圖5-7示例圖圖5-8平移變換變換矩陣變換后3個(gè)頂點(diǎn)的齊次坐標(biāo)為（2）三角形相對(duì)于坐標(biāo)原點(diǎn)逆時(shí)針?lè)较蛐D(zhuǎn)30°，如圖5-9所示。變換矩陣QP2P1P0圖5-9旋轉(zhuǎn)變換（3）將參考點(diǎn)Q平移回原位置，如圖5-10所示。QP2P1P0圖5-10反平移變換變換后三個(gè)頂點(diǎn)的齊次坐標(biāo)為變換矩陣變換后3個(gè)頂點(diǎn)的齊次坐標(biāo)為這樣三角形變換后的頂點(diǎn)坐標(biāo)為P0（17.5，12.01），P1（34.82，22.01）和P2（18.66，30）。這里，三角形是將Q點(diǎn)作為旋轉(zhuǎn)中心，而不是將坐標(biāo)系原點(diǎn)作為旋轉(zhuǎn)中心。圖形的旋轉(zhuǎn)變換是相對(duì)于某一參考點(diǎn)進(jìn)行的，這一結(jié)論讀者一般都比較清楚。同樣圖形的比例變換也是相對(duì)于某一參考點(diǎn)進(jìn)行的，在應(yīng)用中如果不注意將會(huì)導(dǎo)致錯(cuò)誤的結(jié)果?；拘D(zhuǎn)變換復(fù)合旋轉(zhuǎn)變換習(xí)題35.3.2相對(duì)于任意方向的二維幾何變換

相對(duì)于任意方向的變換方法是首先對(duì)任意方向做旋轉(zhuǎn)變換，使變換方向與坐標(biāo)軸重合，然后對(duì)坐標(biāo)軸進(jìn)行二維基本幾何變換，最后做反向旋轉(zhuǎn)變換，將任意方向還原到原來(lái)的方向。例5-3圖5-14所示三角形相對(duì)于軸線y=kx+b進(jìn)行反射變換，求每一步相應(yīng)的變換矩陣。y=kx+b（0，b）圖5-14原始圖形圖5-15平移變換（1）將點(diǎn)（0，b）平移至坐標(biāo)原點(diǎn)，如圖5-15所示。變換矩陣（2）將軸線y=kx繞坐標(biāo)系原點(diǎn)順時(shí)針旋轉(zhuǎn)β角(β=arctank)，落于x軸上，如圖5-16所示。變換矩陣為圖5-16旋轉(zhuǎn)變換（3）三角形相對(duì)x軸作反射變換，如圖5-17所示。變換矩陣為圖5-17反射變換（4）將軸線y=kx逆時(shí)針旋轉(zhuǎn)β角(β=arctank)，如圖5-18所示。變換矩陣圖5-18反旋轉(zhuǎn)變換（5）將軸線平移回原來(lái)的位置，如圖5-19所示。變換矩陣為總變換矩陣為反平移變換二維幾何變換5.4二維圖形裁剪5.4.1圖形學(xué)中常用的坐標(biāo)系

計(jì)算機(jī)圖形學(xué)中常用的坐標(biāo)系有世界坐標(biāo)系用戶坐標(biāo)系觀察坐標(biāo)系屏幕坐標(biāo)系設(shè)備坐標(biāo)系規(guī)格化設(shè)備坐標(biāo)系等

圖5-20二維直角坐標(biāo)系圖5-21三維右手直角坐標(biāo)系描述現(xiàn)實(shí)世界中場(chǎng)景的固定坐標(biāo)系稱為世界坐標(biāo)系，世界坐標(biāo)系是實(shí)數(shù)域坐標(biāo)系，根據(jù)應(yīng)用的需要可以選擇直角坐標(biāo)系、圓柱坐標(biāo)系、球坐標(biāo)系以及極坐標(biāo)系等。圖5-20所示為二維直角坐標(biāo)系。三維直角世界坐標(biāo)系可分為右手坐標(biāo)系與左手坐標(biāo)系兩種，如圖5-21所示，zw軸的指向按照右手螺旋法則或左手螺旋法則從xw軸轉(zhuǎn)向yw軸確定。1.世界坐標(biāo)系描述物體數(shù)學(xué)模型的坐標(biāo)系稱為用戶坐標(biāo)系，有時(shí)也稱為局部坐標(biāo)系。用戶坐標(biāo)系也是實(shí)數(shù)域坐標(biāo)系。用戶坐標(biāo)系是可移動(dòng)坐標(biāo)系，用戶坐標(biāo)系的原點(diǎn)可以放在物體的任意位置上，坐標(biāo)系也可以旋轉(zhuǎn)任意角度。對(duì)于立方體，可以將用戶坐標(biāo)系原點(diǎn)放置在立方體中心；對(duì)于圓柱，可以將用戶坐標(biāo)系的y軸作為旋轉(zhuǎn)軸。2.用戶坐標(biāo)系3.觀察坐標(biāo)系觀察坐標(biāo)系是在世界坐標(biāo)系中定義的直角坐標(biāo)系。二維觀察坐標(biāo)系主要用于指定圖形的輸出范圍，如圖5-22所示。三維觀察坐標(biāo)系是左手系，原點(diǎn)位于視點(diǎn)Ov，zv軸垂直于屏幕，zv軸正向?yàn)橐暰€方向，如圖5-23所示。觀察坐標(biāo)系世界坐標(biāo)系輸出結(jié)果圖5-22二維觀察坐標(biāo)系觀察坐標(biāo)系屏幕坐標(biāo)系世界坐標(biāo)系圖5-23三維觀察坐標(biāo)系4.屏幕坐標(biāo)系屏幕坐標(biāo)系為實(shí)數(shù)域二維或三維直角坐標(biāo)系。

二維屏幕坐標(biāo)系，原點(diǎn)位于屏幕中心，xs軸水平向右為正，ys軸垂直向上為正。如圖5-24所示。

三維屏幕坐標(biāo)系為左手系，原點(diǎn)位于屏幕中心，zs軸方向沿著視線方向，ys軸垂直向上為正，xs軸與ys軸和zs軸成左手系，如圖5-25所示。

從視點(diǎn)Ov沿著zs方向的視線觀察，P點(diǎn)和Q點(diǎn)在屏幕上的投影點(diǎn)都為P’點(diǎn)，但P、Q點(diǎn)與視點(diǎn)的距離不同，P點(diǎn)位于Q點(diǎn)之前，離視點(diǎn)近，應(yīng)該遮擋Q點(diǎn)。

顯然，只有采用三維屏幕坐標(biāo)系才能正確反映投影時(shí)物體上點(diǎn)的深度信息。圖5-24二維屏幕坐標(biāo)系圖5-25三維屏幕坐標(biāo)系5.設(shè)備坐標(biāo)系光柵掃描顯示器等圖形輸出設(shè)備自身都帶有一個(gè)二維直角坐標(biāo)系稱為設(shè)備坐標(biāo)系。設(shè)備坐標(biāo)系是整數(shù)域二維坐標(biāo)系，如圖5-26所示，原點(diǎn)位于屏幕左上角，x軸水平向右為正，y軸垂直向下為正，基本單位為像素。格化到[0，1]的范圍內(nèi)的設(shè)備坐標(biāo)系稱為規(guī)格化設(shè)備坐標(biāo)系，如圖5-27所示。

圖5-26設(shè)備坐標(biāo)系圖5-27規(guī)格化設(shè)備坐標(biāo)系

規(guī)格化設(shè)備坐標(biāo)系獨(dú)立于具體輸出設(shè)備。一旦圖形變換到規(guī)格化設(shè)備坐標(biāo)系中，只要作一個(gè)簡(jiǎn)單的乘法運(yùn)算即可映射到具體的物理設(shè)備坐標(biāo)系中。由于規(guī)格化設(shè)備坐標(biāo)系能統(tǒng)一用戶各種圖形的顯示范圍，故把用戶圖形變換為規(guī)格化設(shè)備坐標(biāo)系中的統(tǒng)一大小標(biāo)準(zhǔn)圖形的過(guò)程叫做圖形的邏輯輸出。把規(guī)格化設(shè)備坐標(biāo)系中的標(biāo)準(zhǔn)圖形送到物理顯示設(shè)備上輸出的過(guò)程叫做圖形的物理輸出。有了規(guī)格化設(shè)備坐標(biāo)系后，圖形的輸出可以在抽象的顯示設(shè)備上進(jìn)行討論，因而這種圖形學(xué)又稱為與具體設(shè)備無(wú)關(guān)的圖形學(xué)。5.4.2窗口與視區(qū)及窗視變換

在觀察坐標(biāo)系中定義的確定圖形顯示內(nèi)容的區(qū)域稱為窗口。此時(shí)窗口內(nèi)的圖形是用戶希望在屏幕上看到的，窗口是裁剪圖形的標(biāo)準(zhǔn)參照物。

在設(shè)備坐標(biāo)系中定義的輸出圖形的區(qū)域稱為視區(qū)。視區(qū)和窗口常為矩形，大小可以不相同。一般情況下，用戶把窗口內(nèi)感興趣的圖形輸出到屏幕上相應(yīng)的視區(qū)內(nèi)。

圖5-28定義了3個(gè)窗口內(nèi)容用于輸出。圖5-28定義3個(gè)窗口

圖5-29的屏幕被劃分為三個(gè)視區(qū)，對(duì)三個(gè)窗口的輸出內(nèi)容進(jìn)行了重組。圖5-30使用4個(gè)視區(qū)分別輸出房屋的立體圖及其三視圖的線框模型。圖5-29顯示3個(gè)視區(qū)圖5-30多視區(qū)輸出圖形輸出需要進(jìn)行從窗口到視區(qū)的變換，只有窗口內(nèi)的圖形才能在視區(qū)中輸出，并且輸出的形狀要根據(jù)視區(qū)的大小進(jìn)行調(diào)整，這稱為窗視變換。

在二維圖形觀察中，可以這樣理解，窗口相當(dāng)于一扇窗戶。窗口內(nèi)的圖形是用戶希望看到的，就在視區(qū)中輸出；窗口外的圖形用戶不希望看到，不在視區(qū)中輸出。因此需要對(duì)窗口中輸出的二維圖形進(jìn)行裁剪。在計(jì)算機(jī)圖形學(xué)術(shù)語(yǔ)中，窗口最初是指要觀察的圖形區(qū)域。但是隨著Windows的出現(xiàn)，窗口的概念已廣泛用于圖形系統(tǒng)中，泛指任何可以移動(dòng)，改變大小、激活或變?yōu)闊o(wú)效的屏幕上的矩形區(qū)域。在本章中，窗口回歸到其原始定義，是在觀察坐標(biāo)系中確定輸出圖形范圍的矩形區(qū)域。多視區(qū)輸出5.4.3窗視變換矩陣

實(shí)際的窗口與視區(qū)的大小往往不一致，要在視區(qū)中正確地顯示窗口中的物體，必須將物體從窗口變換到視區(qū)。窗口與視區(qū)的邊界定義如圖5-31所示，假定把窗口內(nèi)的一點(diǎn)P（xw，yw)變換為視區(qū)中的一點(diǎn)P’（xv，yv）。這屬于相對(duì)于任一參考點(diǎn)的二維幾何變換，

（a）窗口（b）視區(qū)圖5-31窗口與視區(qū)的定義變換步驟如下（1）將窗口左下角點(diǎn)（wxl，wyb）平移到觀察坐標(biāo)系原點(diǎn)。平移參數(shù)為（－wxl，－wyb）。（2）對(duì)原點(diǎn)進(jìn)行比例變換，使窗口與視區(qū)大小相等，即將窗口變換為視區(qū)。，其中，（3）進(jìn)行反平移，將視區(qū)的左下角點(diǎn)平移到設(shè)備坐標(biāo)系的（vxl，vyb）點(diǎn)。窗視變換矩陣窗視變換寫成方程令

（5-12）則窗視變換的展開(kāi)式為5.5Cohen-Sutherland直線裁剪算法在二維觀察中，需要在觀察坐標(biāo)系下根據(jù)窗口大小對(duì)二維圖形進(jìn)行裁剪（clipping），只將位于窗口內(nèi)的圖形變換到視區(qū)輸出。直線段裁剪是二維圖形裁剪的基礎(chǔ)，裁剪的實(shí)質(zhì)是判斷直線段是否與窗口相交，如相交則進(jìn)一步確定直線段上位于窗口內(nèi)的部分。5.5.1編碼原理

Cohen-Sutherland直線段裁剪算法是最早流行的編碼算法。每段直線的端點(diǎn)都被賦予一組四位二進(jìn)制代碼，稱為區(qū)域編碼(regioncode，RC)，用來(lái)標(biāo)識(shí)直線段端點(diǎn)相對(duì)于窗口邊界及其延長(zhǎng)線的位置。假設(shè)窗口是標(biāo)準(zhǔn)矩形，由上（y=wyt）、下（y=wyb）、左（x=wxl）、右（x=wxr）4條邊組成，如圖5-32所示。

圖5-32窗口坐標(biāo)延長(zhǎng)窗口的4條邊形成9個(gè)區(qū)域，如圖5-33所示。

圖5-33區(qū)域編碼RC這樣根據(jù)直線段的任一端點(diǎn)相對(duì)于窗口的位置，可以賦予一組4位二進(jìn)制區(qū)域編碼RC=C4C3C2C1。

為保證窗口內(nèi)直線段端點(diǎn)的編碼為零，編碼規(guī)則定義如下C1：若端點(diǎn)的x<wxl，

則C1=1，否則C1=0。C2：若端點(diǎn)的x>wxr，

則C2=1，否則C2=0。C3：若端點(diǎn)的y<wyb，

則C3=1，否則C3=0。C4：若端點(diǎn)的y>wyt，

則C4=1，否則C4=0。5.5.2裁剪步驟

（1）若直線段的兩個(gè)端點(diǎn)的區(qū)域編碼都為0，即RC0|RC1=0（二者按位相或的結(jié)果為零，即RC0=0且RC1=0），說(shuō)明直線段的兩個(gè)端點(diǎn)都在窗口內(nèi)，應(yīng)“簡(jiǎn)取”。（2）若直線段的兩個(gè)端點(diǎn)的區(qū)域編碼都不為0，即RC0&RC1≠0（二者按位相與的結(jié)果不為零，即RC0≠0且RC1≠0），即直線段位于窗外的同一側(cè)，說(shuō)明直線段的兩個(gè)端點(diǎn)都在窗口外，應(yīng)“簡(jiǎn)棄”。（3）若直線段既不滿足“簡(jiǎn)取”也不滿足“簡(jiǎn)棄”的條件，則需要與窗口進(jìn)行“求交”判斷。這時(shí)，直線段必然與窗口邊界或窗口邊界的延長(zhǎng)線相交，分兩種情況處理。

一種情況是直線段與窗口邊界相交，如圖5-34所示直線段P0P1。此時(shí)RC0=0010≠0，RC1=0100≠0，但RC0&RC1=0，按左右下上順序計(jì)算窗口邊界與直線段的交點(diǎn)。右邊界與P0P1的交點(diǎn)為P，P0P直線段位于窗口之右，“簡(jiǎn)棄”之。將P點(diǎn)的坐標(biāo)與編碼替換為P0點(diǎn)，并交換P0P1點(diǎn)的坐標(biāo)及其編碼，使P0點(diǎn)總處于窗口之外，如圖5-35所示。下邊界與P0P1的交點(diǎn)為P，P0P直線段位于窗口之下，“簡(jiǎn)棄”之，將P點(diǎn)的坐標(biāo)與編碼替換為P0點(diǎn)，如圖5-36所示。此時(shí)，直線段P0P1被“簡(jiǎn)取”。圖5-34直線段與窗口邊界相交圖5-35P0點(diǎn)位于裁剪窗口之外

圖5-36裁剪后的直線段PP0PP0P0P1P1P1另一種情況是直線段與窗口邊界的延長(zhǎng)線相交，直線段完全位于窗口之外，且不在窗口同一側(cè)，所以RC0=0010≠0，RC1=0100≠0，但RC0&RC1=0，如圖5-37所示。P1P0按左右下上順序計(jì)算窗口邊界延長(zhǎng)線與直線段的交點(diǎn)。右邊界延長(zhǎng)線與P0P1的交點(diǎn)為P，P0P段直線位于窗口的右側(cè)，“簡(jiǎn)棄”之，將P點(diǎn)的坐標(biāo)和編碼替換為P0點(diǎn)，如圖5-38所示。此時(shí)，直線段P0P1位于窗口外的下側(cè)，“簡(jiǎn)棄”之。圖5-37直線段與窗口邊界的延長(zhǎng)線相交圖5-38窗口右邊界的延長(zhǎng)線裁剪后的直線段P0P15.5.3交點(diǎn)計(jì)算公式

對(duì)于端點(diǎn)坐標(biāo)為P0（x0，y0)和P1（x1，y1）的直線段，與窗口左邊界（x＝wxl）或右邊界（x＝wxr）交點(diǎn)的y坐標(biāo)的計(jì)算公式為與窗口上邊界（y＝wyt）或下邊界（y＝wyb）交點(diǎn)的x坐標(biāo)的計(jì)算公式為其中，（5-15）（5-16）在直線段裁剪過(guò)程中，一般按固定順序左（x=wxl），右（x=wxr）、下（y=wyb）、上（y=wyt）求解窗口邊界與直線段的交點(diǎn)。基于Cohen-Sutherland直線段裁剪算法使用綠色矩形窗口對(duì)任意繪制的直線段進(jìn)行裁剪，如圖5-39（a）所示。裁剪結(jié)果如圖5-39（b）所示。圖5-39Cohen-Sutherland裁剪算法的應(yīng)用（a）裁剪前（b）裁剪后

Cohen-Sutherland直線段裁剪算法5.6中點(diǎn)分割直線段裁剪算法5.6.1中點(diǎn)分割算法原理中點(diǎn)分割直線段裁剪算法對(duì)Cohen-Sutherland直線裁剪算法的第3種情況做了改進(jìn)，原理是簡(jiǎn)單地把起點(diǎn)為P0，終點(diǎn)為P1的直線段等分為兩段直線P0P和PP1（P為直線段中點(diǎn)），對(duì)每一段直線重復(fù)“簡(jiǎn)取”和“簡(jiǎn)棄”的處理，對(duì)于不能處理的直線段再繼續(xù)等分下去，直至每一段直線完全能夠被“簡(jiǎn)取”或“簡(jiǎn)棄”，也就是說(shuō)直至每段直線完全位于窗口之內(nèi)或完全位于窗口之外，就完成了直線段的裁剪工作。5.6.2中點(diǎn)計(jì)算公式對(duì)于端點(diǎn)坐標(biāo)為P0（x0，y0)和P1（x1，y1）的直線段，中點(diǎn)坐標(biāo)的計(jì)算公式為：（5-17）展開(kāi)形式為P0P1P中點(diǎn)分割算法使用中點(diǎn)分割直線段裁剪算法對(duì)圖5-40（a）所示的金剛石圖案進(jìn)行裁剪，裁剪結(jié)果如圖5-40（b）所示。（a）裁剪前（b）裁剪后圖5-40中點(diǎn)分割直線段裁剪算法的應(yīng)用中點(diǎn)分割算法裁剪金剛石圖案5.7Liang-Barsky直線段裁剪算法5.7.1Liang-Barsky裁剪算法原理

梁友棟和Barsky提出了比Cohen-Sutherland裁剪算法速度更快的直線段裁剪算法。該算法是以直線的參數(shù)方程為基礎(chǔ)設(shè)計(jì)的，把直線與窗口邊界求交的二維裁剪問(wèn)題轉(zhuǎn)化為通過(guò)求解一組不等式來(lái)確定直線段參數(shù)的一維裁剪問(wèn)題。Liang-Barsky算法將直線段與窗口的相互位置關(guān)系劃分為兩種情況：平行于窗口邊界的直線段與不平行于窗口邊界的直線段。設(shè)起點(diǎn)為P1（x0，y0)，終點(diǎn)為P1（x1，y1）直線的參數(shù)方程為（5-18）式中，0≤t≤1展開(kāi)式為對(duì)于對(duì)角點(diǎn)為（wxl，wyt）、（wxr，wyb）的矩形裁剪窗口，直線段裁剪條件如下（5-19）分解后有：（5-20）代入上式得到將（5-21）令：，，，，則（5-21）統(tǒng)一表示為：（5-22）n＝1，2，3，4。

n代表直線段裁剪時(shí)，窗口的邊界順序，n＝1表示左邊界；n＝2表示右邊界；n＝3表示下邊界；n＝4表示上邊界。公式（5-22）給出了直線段的參數(shù)方程裁剪條件。5.7.2算法分析Liang-Barsky裁剪算法主要考察直線方程參數(shù)t的變化情況。為此，先討論直線段與窗口邊界不平行的情況。令：

，且n＝1，2，3，4。（5-23），從式（5-21）可以知道，x0≠x1而且y0≠y1，這意味著直線段不與窗口的任何邊界平行，直線段及其延長(zhǎng)線與窗口邊界及其延長(zhǎng)線必定相交，可以采用參數(shù)t對(duì)直線段進(jìn)行裁剪。表示在該處直線段從裁剪窗口及其邊界延長(zhǎng)線的內(nèi)部延伸到窗口外部，直線段和窗口邊界的交點(diǎn)位于直線段的終點(diǎn)一側(cè)。表示在該處直線段從裁剪窗口及其邊界延長(zhǎng)線的外部延伸到窗口內(nèi)部，直線段與窗口邊界的交點(diǎn)位于直線段的起點(diǎn)一側(cè)；5.7.3算法的幾何意義

假定，直線段L1的起點(diǎn)坐標(biāo)為（x0，y0），終點(diǎn)坐標(biāo)為（x1，y1）。Liang-Barsky裁剪算法的幾何意義如圖5-41所示。圖5-41直線段與裁剪窗口的相對(duì)位置注意圖中參數(shù)t是或x或y的坐標(biāo)值，t1、t2、t3、t4代表了直線段與窗口4條邊界交點(diǎn)處的參數(shù)值。圖中將綠色區(qū)域定義為內(nèi)部，白色區(qū)域定義為外部。

，并不是時(shí)，表示y1>y0，直線段從窗口上邊界的內(nèi)部延伸到窗口外部，和窗口上邊界及其延長(zhǎng)線相交于參數(shù)t等于t4處。時(shí)，表示y0<y1，直線段從窗口下邊界的外部延伸到窗口內(nèi)部，和窗口下邊界及其延長(zhǎng)線相交于參數(shù)t等于t3處時(shí)，表示x1>x0，直線段從窗口右邊界的內(nèi)部延伸到窗口外部，與窗口右邊界及其延長(zhǎng)線相交于參數(shù)t等于t2處；時(shí)，表示x0<x1，直線段從窗口左邊界的外部延伸到窗口內(nèi)部，與窗口左邊界及其延長(zhǎng)線相交于參數(shù)t等于t1處；時(shí)，tmin應(yīng)該小于1。時(shí)，tmax應(yīng)該大于0；對(duì)于直線段的終點(diǎn)一側(cè)，直線段L1與裁剪窗口的交點(diǎn)參數(shù)是t1和t4。對(duì)于直線段的起點(diǎn)一側(cè)，，所以當(dāng)時(shí)，起點(diǎn)取t的最大值tmax＝t1；

時(shí)，終點(diǎn)取t的最小值tmin＝t4；

，所以當(dāng)如果tmax≤tmin，被裁剪的直線段位于窗口內(nèi)。顯然（5-24）即可見(jiàn)，對(duì)于直線段的起點(diǎn)，使用參數(shù)t1和t3判斷，取其最大值；對(duì)于直線段的終點(diǎn)，使用參數(shù)t2和t4判斷，取其最小值。直線段位于窗口內(nèi)的參數(shù)條件是：tmax≤tmin

將tmax和tmin代入式（5-18），可以計(jì)算直線段L1與窗口左邊界與上邊界的交點(diǎn)。時(shí)，表示y1>y0，直線段從窗口上邊界的內(nèi)部延伸到窗口外部，與窗口上邊界及其延長(zhǎng)線相交于參數(shù)t等于t4處。時(shí)，表示y0<y1，直線段從窗口下邊界的外部延伸到窗口內(nèi)部，與窗口下邊界及其延長(zhǎng)線相交于參數(shù)t等于t3處；時(shí)，表示x1>x0，直線段從窗口右邊界的內(nèi)部延伸到窗口外部，與窗口右邊界及其延長(zhǎng)線相交于參數(shù)t等于t2處；時(shí)，表示x0<x1，直線段從窗口左邊界的外部延伸到窗口內(nèi)部，與窗口左邊界及其延長(zhǎng)線相交于參數(shù)t等于t1處

假定直線段L2起點(diǎn)坐標(biāo)為（x0，y0），終點(diǎn)坐標(biāo)為（x1，y1）。因?yàn)閠max>tmin，所以直線段L2位于窗口外，可刪除。

起點(diǎn)一側(cè)，時(shí)，tmax＝t3；終點(diǎn)一側(cè)，時(shí)，tmin＝t2；如果u1=0，u2=0，u3≠0，u4≠0，表示x0＝x1

。是平行于窗口左右邊界的垂線。如圖5-42所示。

圖5-42垂直直線段且n=3，4

（5-25）如果v1<0或v2<0，相應(yīng)有x0<wxl或x0≥wxr

。直線段位于窗口左右邊界之外，可刪除；

如果v1≥0且v2≥0，相應(yīng)有x0≥wxl或x0≤wxr。在水平方向上直線段位于窗口左右邊界或其內(nèi)部，僅需要判斷該直線段在垂直方向是否位于窗口上下邊界之內(nèi)。使用式（5-24）計(jì)算tmax和tmin。如果tmax>tmin，則直線段完全位于窗口外，刪除該直線段。如果tmax≤tmin，則直線段部分位于窗口之內(nèi)，將tmax和tmin代入式（5-18），算出直線段與窗口上下邊界的交點(diǎn)。同理，如果u3=0，u4=0，u1≠0，u2≠0，表示y0＝y(tǒng)1

。是平行于窗口上下邊界的水平線，如圖5-43所示。

5-43水平直線段如果滿足v3<0或v4<0，則相應(yīng)有y0<wyb或y0≥wyt

。直線段位于窗口上下邊界之外，可刪除；如果v3≥0且v4≥0。則相應(yīng)有y0≥wyb或y0≤wyt

。這意味著在垂直方向上直線段位于窗口上下邊界之內(nèi)，僅需要判斷該直線段在水平方向是否位于窗口左右邊界之內(nèi)。且n=1，2

（5-26）使用式（5-24）計(jì)算tmax和tmin。如果tmax>tmin，則直線段完全位于窗口外，刪除之。如果tmax≤tmin，將tmax和tmin代入式（5-18），可以計(jì)算出直線段與窗口的左右邊界的交點(diǎn)。算法應(yīng)用：在屏幕客戶區(qū)中心繪制“金剛石”圖案。以鼠標(biāo)指針為中心，顯示一個(gè)正方形作為“放大鏡”，如圖5-44所示。移動(dòng)放大鏡顯示金剛石圖案的放大部分。要求使用Liang-Barsky直線段裁剪算法在放大鏡中顯示裁剪后的金剛石圖案，如圖5-45所示。

圖5-44金剛石圖案與放大鏡5-45放大鏡裁剪金剛石圖案Liang-Barsky放大鏡5.8多邊形裁剪算法多邊形是由3條或3