第三章 (計(jì)算機(jī)圖形學(xué)基本圖形算法之三)

計(jì)算機(jī)圖形學(xué)基礎(chǔ)

ComputerGraphics

趙東保

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

矢量的混合積：

(a×b)·c

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

設(shè)N1(N2)=-2當(dāng)D1(D2)=0

設(shè)N1(N2)=0當(dāng)D1(D2)>0

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

若N2<0，則線段的[0,λ]間的部份在面的前面；6線與面的關(guān)系當(dāng)N=0時(shí)，線段在面之上。此時(shí)線段在面的正面或在面的背面。若另兩個(gè)端點(diǎn)中有一端點(diǎn)在面的前面，則此線段在

面的正面，可見(jiàn)；若另兩端點(diǎn)均在面之后，此時(shí)線段在面的背面，需和此面比較，他們的投影公共部份即為棱的不可見(jiàn)部份。7面與面的關(guān)系

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

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

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

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

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