第五章 二維變換及裁剪

第五章二維變換與裁剪齊次坐標二維幾何變換矩陣Cohen-Sutherland直線段裁剪算法中點分割直線段裁剪算法Liang-Barsky直線段裁剪算法Sutherland-Hodgman多邊形裁剪算法本章學習目標5.1圖形幾何變換基礎5.2二維圖形基本幾何變換矩陣5.3二維復合變換5.4二維圖形裁剪5.5Cohen-Sutherland直線裁剪算法5.6中點分割直線段裁剪算法5.7梁友棟－Barsky直線段裁剪算法5.8多邊形裁剪5.9本章小結習題5本章內(nèi)容5.1圖形幾何變換基礎通過對圖形進行幾何變換，可以由簡單圖形構造復雜圖形。圖形幾何變換是對圖形進行平移變換、比例變換、旋轉(zhuǎn)變換、反射變換和錯切變換。圖形幾何變換可以分為二維圖形幾何變換和三維圖形幾何變換，而二維圖形幾何變換是三維圖形幾何變換的基礎

。

（a）地磚1（b）地磚2圖5-1地板磚類二維場景齊次坐標就是用n＋1維矢量表示n維矢量。例如，在二維平面中，點P(x,y)的齊次坐標表示為(wx,wy,w)。類似地，在三維空間中，點P(x,y,z)的齊次坐標表示為（wx,wy,wz,w）。w＝1就是規(guī)范化的齊次坐標。二維點P(x，y)的規(guī)范化齊次坐標為〔x，y，1〕，三維點P(x，y，z)的規(guī)范化齊次坐標為(x，y，z，1)。定義了規(guī)范化齊次坐標以后，圖形幾何變換可以表示為圖形頂點集合的規(guī)范化齊次坐標矩陣與某一變換矩陣相乘的形式。5.1.1規(guī)范化齊次坐標

對于n×3的矩陣A和3×3的矩陣B，矩陣相乘公式為：5.1.2矩陣相乘（5-1）由線性代數(shù)知道，矩陣乘法不滿足交換律，只有左矩陣的列數(shù)等于右矩陣的行數(shù)時，兩個矩陣才可以相乘。

用規(guī)范化齊次坐標表示的二維基本幾何變換矩陣是一個3×3的方陣，簡稱為二維變換矩陣。從功能上可以把二維變換矩陣T分為4個子矩陣。其中（5-2）5.1.3二維幾何變換矩陣

對圖形進行平移變換；對圖形進行投影變換；對圖形進行整體比例變換。對圖形進行比例、旋轉(zhuǎn)、反射和錯切變換；5.1.4物體變換與坐標變換同一種變換可以看作是物體變換，也可以看作是坐標變換。物體變換是使用同一變換矩陣作用于物體上的所有頂點，但坐標系位置不發(fā)生改變。坐標變換是坐標系發(fā)生變換，但物體位置不發(fā)生改變，然后在新坐標系下表示物體上的所有頂點。這兩種變換緊密聯(lián)系，各有各的優(yōu)點，只是變換矩陣略有差異而已，以下主要介紹物體變換。5.1.5二維幾何變換（5-3）5.2二維圖形基本幾何變換矩陣

二維圖形基本幾何變換是指相對于坐標原點和坐標軸進行的幾何變換，包括平移（Translate）、比例（Scale）、旋轉(zhuǎn)（Rotate）、反射（Reflect）和錯切（shear）5種變換。物體變換物體變換是通過變換物體上每一個頂點實現(xiàn)的，因此以點的二維基本幾何變換為例講解二維圖形基本幾何變換矩陣。5.2.1平移變換矩陣

P’P平移變換（5-4）TyTxTx，Ty為平移參數(shù)5.2.2比例變換矩陣

SxSyPP’比例變換Sx，Sy為比例系數(shù)（5-5）5.2.3旋轉(zhuǎn)變換矩陣

rβPP’旋轉(zhuǎn)變換α為點的起始角，β為點的逆時針方向旋轉(zhuǎn)角（5-6）α5.2.4反射變換矩陣

P’（a）關于原點反射（b）關于x軸反射（c）關于y軸反射反射變換關于原點反射的坐標表示為。相應的齊次坐標矩陣表示為關于原點的二維反射變換矩陣為（5-7）關于x軸的二維反射變換矩陣為（5-8）關于y軸的二維反射變換矩陣為（5-9）5.2.5錯切變換矩陣

（a）正方形（b）沿x正向錯切（c）沿x負向錯切

（d）沿y正向錯切（e）沿y負向錯切（f）沿x和y正向錯切錯切變換沿x，y方向的錯切變換的坐標表示為

。

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

的非對角線上面討論的五種變換給出的都是點變換的公式，對于線框模型，圖形的變換實際上都可以通過點變換來完成。例如直線段的變換可以通過對兩個頂點坐標進行變換，連接新頂點得到變換后的新直線段；多邊形的變換可以通過對每個頂點進行變換，連接新頂點得到變換后的新多邊形。曲線的變換可通過變換控制多邊形的控制點后，重新繪制曲線來實現(xiàn)。

符合下面形式的坐標變換稱為二維仿射變換（AffineTransformation）。（5-11）仿射變換具有平行線變換成平行線，有限點映射到有限點的一般特性。平移、比例、旋轉(zhuǎn)、反射和錯切五種變換都是二維仿射變換的特例，任何一組二維仿射變換總可表示為這5種變換的組合。5.3二維復合變換

5.3.1復合變換原理

5.3.2相對于任一參考點的二維幾何變換相對于任一參考點的比例變換和旋轉(zhuǎn)變換應表達為復合變換形式，變換方法為首先將參考點平移到坐標原點，對坐標原點進行比例變換和旋轉(zhuǎn)變換，然后再進行反平移將參考點平移回原位置。其中，T為復合變換矩陣，為單次基本幾何變換矩陣。例5-1一個由頂點P1（10，10），P2（30，10）和P3（20，25）所定義的三角形，如圖所示，相對于點Q（10，25）逆時針旋轉(zhuǎn)30°，求變換后的三角形頂點坐標。P1P2P3Q原始圖形平移變換QP3P2P1QP3P2P1QP3P2P1P1(17.5,12.01)，P2(34.82,22.01)和P3(18.66,30)5.3.2相對于任意方向的二維幾何變換

相對于任意方向的變換方法是首先對任意方向做旋轉(zhuǎn)變換，使變換方向與坐標軸重合，然后對坐標軸進行二維基本幾何變換，最后做反向旋轉(zhuǎn)變換，將任意方向還原到原來的方向。例5-2將圖示三角形相對于軸線y=kx+b作反射變換，計算每一步的變換矩陣。y=kx+b（0，b）原始圖形平移變換

旋轉(zhuǎn)變換反射變換反旋轉(zhuǎn)變換反平移變換classCTransform//二維幾何變換{public: CTransform(); virtual~CTransform(); voidSetMat(CP2*,int); voidIdentity(); voidTranslate(double,double);//平移變換矩陣

voidScale(double,double);//比例變換矩陣

voidScale(double,double,CP2);//相對于任意點的比例變換矩陣

voidRotate(double);//旋轉(zhuǎn)變換矩陣

voidRotate(double,CP2);//相對于任意點的旋轉(zhuǎn)變換矩陣

voidReflectO();//原點反射變換矩陣

voidReflectX();//X軸反射變換矩陣

voidReflectY();//Y軸反射變換矩陣

voidShear(double,double);//錯切變換矩陣

voidMultiMatrix();//矩陣相乘public: doubleT[3][3]; CP2*POld; intnum;};voidCTransform::Identity()//單位矩陣{ T[0][0]=1.0;T[0][1]=0.0;T[0][2]=0.0; T[1][0]=0.0;T[1][1]=1.0;T[1][2]=0.0; T[2][0]=0.0;T[2][1]=0.0;T[2][2]=1.0;}voidCTransform::Translate(doubletx,doublety)//平移變換矩陣{ Identity(); T[2][0]=tx; T[2][1]=ty; MultiMatrix(); }voidCTransform::Scale(doublesx,doublesy)//比例變換矩陣{ Identity(); T[0][0]=sx; T[1][1]=sy; MultiMatrix(); }voidCTransform::Rotate(doublebeta)//旋轉(zhuǎn)變換矩陣{ Identity(); doublerad=beta*PI/180; T[0][0]=cos(rad);T[0][1]=sin(rad); T[1][0]=-sin(rad);T[1][1]=cos(rad); MultiMatrix(); }voidCTransform::Rotate(doublebeta,CP2p)//相對于任意點的旋轉(zhuǎn)變換矩陣{ Translate(-p.x,-p.y); Rotate(beta); Translate(p.x,p.y); }voidCTransform::ReflectO()//原點反射變換矩陣{ Identity(); T[0][0]=-1; T[1][1]=-1; MultiMatrix(); }voidCTransform::ReflectX()//X軸反射變換矩陣{ Identity(); T[0][0]=1; T[1][1]=-1; MultiMatrix(); }voidCTransform::ReflectY()//Y軸反射變換矩陣{ Identity(); T[0][0]=-1; T[1][1]=1; MultiMatrix(); }voidCTransform::Shear(doubleb,doublec)//錯切變換矩陣{ Identity(); T[0][1]=b; T[1][0]=c; MultiMatrix(); }voidCTransform::MultiMatrix()//矩陣相乘{ CP2*PNew=newCP2[num]; for(inti=0;i<num;i++) { PNew[i]=POld[i]; } for(intj=0;j<num;j++) { POld[j].x=PNew[j].x*T[0][0]+PNew[j].y*T[1][0]+PNew[j].w*T[2][0]; POld[j].y=PNew[j].x*T[0][1]+PNew[j].y*T[1][1]+PNew[j].w*T[2][1]; POld[j].w=PNew[j].x*T[0][2]+PNew[j].y*T[1][2]+PNew[j].w*T[2][2]; } delete[]PNew;}二維幾何變換5.5Cohen-Sutherland直線裁剪算法在二維觀察中，需要在觀察坐標系下根據(jù)窗口大小對二維圖形進行裁剪（clipping），只將位于窗口內(nèi)的圖形變換到視區(qū)輸出。直線段裁剪是二維圖形裁剪的基礎，裁剪的實質(zhì)是判斷直線段是否與窗口相交，如相交則進一步確定直線段上位于窗口內(nèi)的部分。5.5.1編碼原理

Cohen-Sutherland直線段裁剪算法是最早流行的編碼算法。每段直線的端點都被賦予一組四位二進制代碼，稱為區(qū)域編碼(regioncode，RC)，用來標識直線段端點相對于窗口邊界及其延長線的位置。窗口坐標假設窗口是標準矩形，由上、下、左、右4條邊組成，延長窗口的4條邊形成9個區(qū)域。這樣根據(jù)直線段的任一端點P(x，y)所處的窗口區(qū)域位置，可以賦予一組4位二進制區(qū)域碼RC=C3C2C1C0，從右到左依次代表左、右、下、上。為了保證窗口內(nèi)直線段端點的編碼為零，定義規(guī)則如下C0：若端點的x<wxl，則C0=1，否則C0=0。C1：若端點的x>wxr，則C1=1，否則C1=0。C2：若端點的y<wyb，則C2=1，否則C2=0。C3：若端點的y>wyt，則C3=1，否則C3=0。區(qū)域編碼RCwxlwxrwybwyt5.5.2裁剪步驟

（1）若直線段的兩個端點的區(qū)域編碼都為0，即RC0|RC1=0（二者按位相或的結果為零，即RC0=0且RC1=0），說明直線段的兩個端點都在窗口內(nèi)，應“簡取”。（2）若直線段的兩個端點的區(qū)域編碼都不為0，即RC0&RC1≠0（二者按位相與的結果不為零，即RC0≠0且RC1≠0），即直線段位于窗外的同一側，說明直線段的兩個端點都在窗口外，應“簡棄”。（3）若直線段既不滿足“簡取”也不滿足“簡棄”的條件，則需要與窗口進行“求交”判斷。這時，直線段必然與窗口邊界或窗口邊界的延長線相交，分兩種情況處理。P0P1P1P0裁剪直線段時，一般按固定順序左（x=wxl），右（x=wxr）、下（y=wyb）、上（y=wyt）求解窗口邊界與直線段的交點。5.5.3交點計算公式

對于端點坐標為P0（x0，y0)和P1（x1，y1）的直線段，與窗口左邊界（x＝wxl）或右邊界（x＝wxr）交點的y坐標的計算公式為與窗口上邊界（y＝wyt）或下邊界（y＝wyb）交點的x坐標的計算公式為其中，（5-13）（5-14）

Cohen-Sutherland直線段裁剪算法#defineLEFT1//代表:0001#defineRIGHT2//代表:0010#defineBOTTOM4//代表:0100#defineTOP8//代表:1000voidCTestView::EnCode(CP2&pt)//編碼函數(shù){ pt.rc=0; if(pt.x<Wxl) { pt.rc=pt.rc|LEFT; } elseif(pt.x>Wxr) { pt.rc=pt.rc|RIGHT; } if(pt.y<Wyb) { pt.rc=pt.rc|BOTTOM; } elseif(pt.y>Wyt) { pt.rc=pt.rc|TOP; }}voidCTestView::Cohen()//Cohen-Sutherland算法{ CP2p;//交點坐標

EnCode(P[0]);//起點編碼

EnCode(P[1]);//終點編碼

while(P[0].rc!=0||P[1].rc!=0)//處理至少一個頂點在窗口外

{ if((P[0].rc&P[1].rc)!=0)//簡棄之

{ PtCount=0; return; } if(0==P[0].rc)//確保P[0]位于窗口之外

{ CP2Temp; Temp=P[0]; P[0]=P[1]; P[1]=Temp; }UINTRC=P[0].rc; doublek=(P[1].y-P[0].y)/(P[1].x-P[0].x);//斜率

if(RC&LEFT)//P[0]點位于窗口的左側

{ p.x=Wxl;//計算交點y坐標

p.y=k*(p.x-P[0].x)+P[0].y; } elseif(RC&RIGHT)//P[0]點位于窗口的右側

{ p.x=Wxr;//計算交點y坐標

p.y=k*(p.x-P[0].x)+P[0].y; } elseif(RC&BOTTOM)//P[0]點位于窗口的下側

{ p.y=Wyb;//計算交點x坐標

p.x=(p.y-P[0].y)/k+P[0].x; } elseif(RC&TOP)//P[0]點位于窗口的上側

{ p.y=Wyt;//計算交點x坐標

p.x=(p.y-P[0].y)/k+P[0].x; }EnCode(p); P[0]=p;｝｝5.6中點分割直線段裁剪算法5.6.1中點分割算法原理中點分割直線段裁剪算法對Cohen-Sutherland直線裁剪算法的第3種情況做了改進，原理是簡單地把起點為P0，終點為P1的直線段等分為兩段直線P0P和PP1（P為直線段中點），對每一段直線重復“簡取”和“簡棄”的處理，對于不能處理的直線段再繼續(xù)等分下去線，直至每一段直線完全能夠被“簡取”或“簡棄”，也就是說直至每段直線完全位于窗口之內(nèi)或完全位于窗口之外，就完成了直線段的裁剪工作。5.6.2中點計算公式（5-15）P0P1P中點分割算法BOOLCTestView::Cohen()//Cohen－Sutherland算法{ EnCode(P[0]);//起點編碼

EnCode(P[1]);//終點編碼

while(P[0].rc!=0||P[1].rc!=0){//處理至少一個頂點在窗口之外的情況 if((P[0].rc&P[1].rc)!=0)//簡棄之

{ PtCount=0; returnFALSE; } if(0==P[0].rc)//確保P[0]位于窗口之外

{ CP2Temp; Temp=P[0]; P[0]=P[1]; P[1]=Temp; } MidClip(P[0],P[1]); } returnTRUE;}voidCTestView::MidClip(CP2p0,CP2p1)//中點分割算法{ CP2p;//中點坐標

p.x=(p0.x+p1.x)/2;p.y=(p0.y+p1.y)/2;EnCode(p); while(fabs(p.x-p0.x)>1e-6||fabs(p.y-p0.y)>1e-6)//判斷結束

{ if(0==p.rc)//中點也在窗口內(nèi)，則舍棄P0點

p1=p; else//否則舍棄P1點

p0=p; p.x=(p0.x+p1.x)/2;p.y=(p0.y+p1.y)/2;EnCode(p); } P[0]=p;}5.7Liang-Barsky直線段裁剪算法5.7.1Liang-Barsky裁剪算法原理

梁友棟與Barsky提出了比Cohen-Sutherland裁剪算法速度更快的直線段裁剪算法。該算法是以直線的參數(shù)方程為基礎設計的，把判斷直線與窗口邊界求交的二維裁剪問題轉(zhuǎn)化為求解一組不等式，確定直線參數(shù)的一維裁剪問題。設起點為P1（x0，y0)，終點為P1（x1，y1）直線的參數(shù)方程為（5-16）式中，0≤t≤1參數(shù)化算法(Cyrus-Beck)考慮凸多邊形區(qū)域R和直線段P1P2 P(t)=(P2-P1)*t+P1設A是區(qū)域R的邊界上一點，N是區(qū)域邊界在A點的內(nèi)法線向量AP2RNP1參數(shù)化算法(Cyrus-Beck)則對于線段P1P2上任一點P(t)N·(P(t)-A)<0->外側N·(P(t)-A)>0->內(nèi)側N·(P(t)-A)=0->邊界或其延長線上AP2RNP1參數(shù)化算法(Cyrus-Beck)凸多邊形的性質(zhì)：點P(t)在凸多邊形內(nèi)的充要條件是，對于凸多邊形邊界上任意一點A和該點處內(nèi)法向N，都有

N·(P(t)-A)>0參數(shù)化算法(Cyrus-Beck)k條邊的多邊形，可見線段參數(shù)區(qū)間的解:Ni·(p(t)-Ai)>=0,i=0,…,k,0≤t≤1.即：Ni·(P1-Ai)+Ni·(P2-P1)t>=0(1)式可得：

令ti=Ni·(P1-Ai)/[Ni·(P2-P1)]參數(shù)化算法(Cyrus-Beck)Ni·(P2-P1)=0->平行于對應邊。此時判斷Ni·(P1-Ai)若Ni·(P1-Ai)<0->P1P2在多邊形外側->不可見，若Ni·(P1-Ai)>0->P1P2在多邊形內(nèi)側->繼續(xù)其它邊的判斷參數(shù)化算法(Cyrus-Beck)對于t值的選擇：首先，要符合0≤t≤1；其次，對于凸窗口來說，每一個線段與其至多有兩個交點，即有兩個相應的t值。所以我們可以把計算出的t值分成兩組：一組為下限組，是分布在線段起點一側的；一組為上限組，是分布在線段終點一側的。這樣，只要找出下限組中的最大值及上限組中的最小值，就可確定線段了。分組的依據(jù)是：如果Ni·(P2-P1)＜0，則計算出的值屬于上限組如果Ni·(P2-P1)＞0，則計算出的值屬于下限組下限上限P1P2參數(shù)化算法的幾何意義下限組以Ni·(P2-P1)>0為特征，表示在該處沿P1P2方向前進將接近或進入多邊形內(nèi)側。上限組以Ni·(P2-P1)<0為特征，表示在該處沿P1P2方向前進將越來越遠地離開多邊形區(qū)域。參數(shù)化算法(Cyrus-Beck)因此，線段可見的交點參數(shù)：tl=max{0,max{ti:Ni·(P2-P1)>0}}tu=min{1,min{ti:Ni·(P2-P1)<0}}若tl<=tu,[tl

，tu]是可見線段的交點參數(shù)區(qū)間，否則，線段不可見。參數(shù)化算法當凸多邊形是矩形窗口且矩形的邊與坐標軸平行時，該算法退化為Liang-Barsky算法。Liang-Barsky算法所用的量Liang-Barsky放大鏡voidCTestView::LBLineClip()//Liang-Barsky裁剪函數(shù){ doubletmax,tmin,dx,dy; dx=P[1].x-P[0].x;dy=P[1].y-P[0].y;tmax=0.0,tmin=1.0; if(ClipTest(-dx,P[0].x-wxl,tmax,tmin))//窗口邊界的左、右、下、上順序裁剪直線 { if(ClipTest(dx,wxr-P[0].x,tmax,tmin)) { if(ClipTest(-dy,P[0].y-wyb,tmax,tmin)) { if(ClipTest(dy,wyt-P[0].y,tmax,tmin)) { if(tmin<1.0)//判斷直線終點

{

P[1].x=P[0].x+tmin*dx;

P[1].y=P[0].y+tmin*dy

} if(tmax>0.0)//判斷直線的起點

{

P[0].x=P[0].x+tmax*dx;

P[0].y=P[0].y+tmax*dy;

} } } } }}BOOLCTestView::ClipTest(doubleu,doublev,double&tmax,double&tmin)//裁剪測試函數(shù){ doublet; BOOLReturnValue=TRUE; if(u<0.0)//從裁剪窗口的外部到內(nèi)部,計算起點處的tmax { t=v/u; if(t>tmin) ReturnValue=FALSE; elseif(t>tmax) tmax=t; } else { if(u>0.0)//從裁剪窗口的內(nèi)部到外部，計算終點處的tmin { t=v/u; if(t<tmax) ReturnValue=FALSE; elseif(t<tmin) tmin=t; } else//平行于窗口邊界的直線

{ if(v<0.0)//直線在窗口外可直接刪除

ReturnValue=FALSE; } } return(ReturnValue);}5.8多邊形裁剪算法Sutherland-Hodgman裁剪算法又稱為逐邊裁剪算法，基本思想是用裁剪窗口的4條邊依次對多邊形進行裁剪。窗口邊界的裁剪順序無關緊要，這里采用左、右、下、上的順序。多邊形裁剪算法的輸出結果為裁剪后的多邊形頂點序列。錯誤結果正確結果

（a）外→內(nèi)，保存P和P1

（b）內(nèi)→內(nèi)，保存P1

（c）內(nèi)→外，保存P（d）外→外，不保存輸入：P0P1P2P3輸出：S0S1P1P2P3（a）用窗口左邊界裁剪輸入：S0S1P1P2P3輸出：S0S1P1S2S3P3（b）用窗口右邊界裁剪輸入：S5S0S1P1S2S3S4輸出：S5S0S1S6S7S2S3S4

（b）用窗口右邊界裁剪輸入：S0S1P1S2S3P3輸出：S5S0S1P1S2S3S4（c）用窗口下邊界裁剪示例凹多邊形使用Sutherland-Hodgman裁剪算法裁剪后，輸出結果為兩個不連通的三角形，窗口的邊界AB成為了多余線段。為了正確地裁剪凹多邊形，一種方法是先將凹多邊形分割為兩個或更多的凸多邊形，然后分別使用Sutherland-Hodgman裁剪算法裁剪。另一種方法是使用Weiler-Atherton裁剪算法。該算法適用于任何凸的、凹的帶內(nèi)孔的多邊形裁剪，但計算工作量很大。

凹多邊形裁剪錯誤的輸出結果voidCTestView::ClipPolygon(CP2*out,intLength,UINTBoundary){ CP2*pTemp=newCP2[Length]; for(inti=0;i<Length;i++) pTemp[i]=out[i]; CP2p0,p1,p;//p0-起點，p1-終點，p-交點

OutCount=0; p0=pTemp[Length-1]; for(i=0;i<Length;i++) { p1=pTemp[i]; if(Inside(p0,Boundary))//起點在窗口內(nèi)

{ if(Inside(p1,Boundary))//終點在窗口內(nèi),屬于內(nèi)→內(nèi)

{ Out[OutCount]=p1;//終點在窗口內(nèi)

OutCount++; } else//屬于內(nèi)→外

{ p=Intersect