第三章 (計算機圖形學基本圖形算法之三)

計算機圖形學基礎

ComputerGraphics

趙東保

華北水利水電學院2011.9第三章基本圖形算法（三）在計算機圖形學中，經(jīng)常需要處理一些共性的問題，如判斷兩條線段是否相交，它們的交點是多少；線段與面之間的位置關系；點是否落在面內(nèi)，點與線段的位置關系等等，這些問題也是計算機圖形學的基本問題。1概述既有大小又有方向的量，也稱向量。其幾何意義一般是指從起點指向終點的有向線段。矢量的加減法矢量的點乘：a·b=|a|·|b|·cos(a,b)矢量的叉乘：∣a×b∣=|a|·|b|·sin(a,b)

矢量的混合積：

(a×b)·c

2矢量3點與線的關系點在線上點在有向線的左側(cè)點在有向線的右側(cè)3點與線的關系利用向量的叉乘可以判斷點與線的各種關系4點與面的關系點在面內(nèi)的包含性檢測空間一點是否在平面上5線與線的關系判斷兩條線段是否相交線段求交5線與線的關系若A，B分別在CD的兩側(cè)；C，D分別在AB的兩側(cè)則二者必相交退化情況5線與線的關系兩線段的參數(shù)方程為：兩線段的交點應滿足：求得代入u,v可得交點坐標5線與線的關系三維空間中，怎樣判斷空間兩線段是否相交，并求出交點參數(shù)方程求交三點構(gòu)成面，判斷另一點是否在面上，再轉(zhuǎn)為二維平面上的判斷線段是否相交向三個平面投影：5線與線的關系三維空間中，假定Z軸是深度方向，如何判斷空間兩線段是否相互遮擋？將兩線段向XOY平面投影利用參數(shù)方程求兩投影線段的交點，并獲得參數(shù)λ，u。將參數(shù)λ，u代入Z方向的參數(shù)方程，獲得深度，比較深度可判知遮擋關系6線與面的關系二維平面內(nèi)，主要有如下關系：線段與面相交線段在面內(nèi)線段與面相離6線與面的關系二維平面內(nèi)，如何判斷線段在面內(nèi)？兩個條件：（1）線段兩端點都在面內(nèi)（2）線段和多邊形邊不相交線段與多邊形的交點如何求?。?線與面的關系三維空間內(nèi)，如何判斷線段與面的遮擋關系設線段的兩端點為P1(x1,y1,z1)，P2(x2,y2,z2)平面方程：Ax+By+Cz+D=0令D1=Ax1+By1+Cz1+DD2=Ax2+By2+Cz2+D當D1(D2)<0

設N1(N2)=-2當D1(D2)=0

設N1(N2)=0當D1(D2)>0

設N1(N2)=1再令N=N1+N26線與面的關系則當N≤-2，線段在面的后面N=0，線段在面上；N=-1，線段貫穿面；N>0，線段在面之前。（N=1和N=2）6線與面的關系一條線段被一平面遮擋的判別原則如下：當N>0時，面不遮擋線段，不用進行比較；當N≤-2時，線段被面遮擋，兩者在投影平面上的公共部份即為線段被面遮擋的部份；6線與面的關系當N=-1時，令λ=│D1│/(│D1│+│D2│)

若N2<0，則線段的[0,λ]間的部份在面的前面；6線與面的關系當N=0時，線段在面之上。此時線段在面的正面或在面的背面。若另兩個端點中有一端點在面的前面，則此線段在

面的正面，可見；若另兩端點均在面之后，此時線段在面的背面，需和此面比較，他們的投影公共部份即為棱的不可見部份。7面與面的關系

二維平面內(nèi)，多邊形的關系主要為多邊形之間相交一個多邊形在另一個多邊形內(nèi)多邊形之間相離7面與面的關系三維空間內(nèi)，如何判斷多邊形之間的遮擋關系？8射線求交射線與直線求交設直線方程為ax+by+c=0，射線方程為x=d1t+x0，y=d2t+y0。(t>0)

把射線方程代入直線方程有：

(ad1+bd2)t+ax0+by0+c=0若ad1+bd2=0，直線與射線平行若ad1+bd2不為零，可求得t=-(ax0+by0+c)/(ad1+bd2)若t<0，則無交點；t=0，直線與射線重合，t>0,則有交點。8射線求交射線與面求交假設面方程為ax+by+cz+d=0，再設射線方程為x=d1t+x0，y=d2t+y0，z=d3t+z0。(t>0)

把射線方程代入直線方程有：

(ad1+bd2+cd3)t+ax0+by0+cz0+d=0若ad1+bd2+cd3=0，射線與面平行若ad1+bd2+cd3不為零，可求得

t=-(ax0+by0+cz0+d)/(ad1+bd2+cd3)。若t<0，則無交點；t=0，射線與面重合，t>0,則有交點。9凸包的生成步1【找內(nèi)點】：找到點集合的一個內(nèi)點G，從內(nèi)點作水平向右的一向量L；步2【排序】：連接內(nèi)點和全部點列，根據(jù)這些連線與L的夾角按遞增次序?qū)c集排序，形成一個雙向鏈接表；步3【求凸包上的起點】：求取點列中的任一個極點P0（X或Y的最小/大者）；9凸包的生成步4【求凸包上的一個頂點】：從P0出發(fā)依次考察連續(xù)的三個頂點，如果是向逆向轉(zhuǎn)（圖中實心圓點），則前進到下一點，否則刪去三個頂點中的中間點（圖中空心圓點），且后退到上一點；步5【求取凸包】：按步4遍歷點表，其結(jié)果即為點集的有向凸包。這樣求得的凸包是一個循環(huán)點列，選取任一個起點均可作為凸包的起點。逆向點順向點10三角網(wǎng)剖分簡單多邊形的三角剖分離散點集的三角網(wǎng)剖分11點到線段的距離11點到線段的距離如何判斷角度是銳角還是鈍角如何計算點到直線的距離（1）構(gòu)建直線方程，利用點到直線的距離公式求取距離。（2）計算向量叉乘，其結(jié)果的一半為三角形的面積，除以邊長的2倍，即得高，就是要求的距離。思考：如何求線段與線段的距離？矩的定義對于二元有界函數(shù)f(x,y)，它的(j+k)階矩為

集合{Mjk}對于函數(shù)f(x，y)是惟一的，也只有f(x，y)才具有這種特定的矩集。12幾何矩1面積參數(shù)j＋k稱為矩的階。特別地，零階矩是多邊形的面積，即對二維離散函數(shù)f(x，y)，零階矩可表示為

所有的一階矩和高階矩除以M00后，與多邊形區(qū)域大小無關。

12幾何矩2質(zhì)心當j=1,k=0時，M10對多邊形區(qū)域來講就是多邊形區(qū)域內(nèi)所有點的x坐標的總和，類似地，M01就是多邊形區(qū)域內(nèi)所有點的y坐標的總和，所以

就是物體的質(zhì)心的坐標。為了獲得矩的不變特征，往往采用中心矩以及歸一化的中心矩。中心矩的定義為3主軸使二階中心矩從μ11變得最小的旋轉(zhuǎn)角θ可以由下式得出：將x、y軸分別旋轉(zhuǎn)θ角得坐標軸x′、y′