計(jì)算機(jī)圖形學(xué)-第4章 幾何計(jì)算.ppt

1、第二篇 幾 何,第4章 幾何計(jì)算,判斷計(jì)算 拐向判斷 凸包算法 包容性測(cè)試 距離和面積 點(diǎn)到平面上一直線的距離 點(diǎn)到一空間直線的垂足 點(diǎn)到平面的距離 相交計(jì)算 直線與平面相交 平面與平面相交 曲線與曲線相交 ,主要內(nèi)容,4.1判斷計(jì)算,決定幾何間的位置和方向的計(jì)算 點(diǎn)、線段在線段、圓、折線、多邊形上、內(nèi)和外的判斷計(jì)算。 幾何位置關(guān)系判斷計(jì)算：切、交、離、含 等 。,向量叉積的模的定義： | P1P2 |= =x1y2 - x2y1，其結(jié)果是一個(gè)標(biāo)量。 若|P1P2 | 0，則P2在P1的逆時(shí)針方向 若| P1P2 | 0，則P2在P1的順時(shí)針方向 若| P1P2 | = 0，則P2與P1共線,

2、4.1.1 折線段的拐向判斷_原理,4.1.2折線段的拐向判斷,對(duì)于有公共端點(diǎn)P2的線段P1P2和P2P3 ，通過計(jì)算|(P2 - P1)(P3- P2) |的符號(hào)，即 C= 便可以確定折線段的拐向。 若C 0，則P1P2在P2點(diǎn)逆時(shí)針旋轉(zhuǎn)后得到P2P3 若C 0，則P1P2在P2點(diǎn)順時(shí)針旋轉(zhuǎn)后得到P2P3 若C = 0，則P1 、 P2 、P3共線,4.1.3 凸包算法,凸包計(jì)算的基本任務(wù)就是確定兩個(gè)或多個(gè)物體彼此之間是否發(fā)生接觸或穿透。 一個(gè)圖形的凸包就是包含這個(gè)圖形的一個(gè)面積最小的凸多邊形，構(gòu)成凸包的點(diǎn)稱為凸包點(diǎn)，其余點(diǎn)稱為凸包內(nèi)點(diǎn)。,在一個(gè)多邊形上（包括在多邊形的邊界上及邊界包圍的范圍

3、）任意取兩點(diǎn)并以一條線段連接，如果線段上的每一點(diǎn)均在該多邊形內(nèi)，則這個(gè)多邊形是凸多邊形。 如三角形、正方形、平行四邊形、正五邊形等。,凸多邊形,4.1.3 凸包算法,基本思想：用形狀簡(jiǎn)單的幾何體（凸包）將形狀復(fù)雜的物體包圍起來，由物體的凸包進(jìn)行粗略檢測(cè)，當(dāng)兩凸包不相交時(shí)，其相應(yīng)的兩原物體間一定不相交，從而快速排除那些不可能相交的物體。,4.1.3 凸包算法Jarris算法,設(shè)S為平面內(nèi)的點(diǎn)的集合, 從S中將y坐標(biāo)最小的點(diǎn)作為凸包的第一個(gè)頂點(diǎn)H1, 找到與以H1為起點(diǎn)的水平線的叉積為正且夾角最小的點(diǎn),作為凸包的第二個(gè)頂點(diǎn)H2 , 再求與線段H1H2叉積為正且夾角最小的點(diǎn),作為凸包的第三個(gè)頂點(diǎn)，直

4、到返回第一個(gè)頂點(diǎn)。,4.1.3 凸包算法Jarris步進(jìn)法,令點(diǎn)集中最右（左/上/下）點(diǎn)為凸包頂點(diǎn)的起點(diǎn)，計(jì)作Pi0； 令點(diǎn)集中的當(dāng)前頂點(diǎn)數(shù)為N0=N-1； While（N0） For i=1 To N0 計(jì)算向量Pi0Pi； if 其余頂點(diǎn)全部在向量Pi0Pi的左側(cè)（右側(cè)），則 Pi點(diǎn)加入凸包列表； Pi0 - Pi； 從當(dāng)前點(diǎn)集中刪除Pi； N0=N0-1； endif endfor endwhile,4.1.3 凸包算法Graham算法,對(duì)于一個(gè)有序點(diǎn)集，如果所有點(diǎn)都在凸包上，則每三個(gè)相繼的點(diǎn)會(huì)組成一個(gè)左拐，若三個(gè)相繼的點(diǎn)組成一個(gè)右拐，即中間點(diǎn)位于三點(diǎn)組成的三角形內(nèi)，可以直接去除該點(diǎn)。,

5、4.1.3 凸包算法Graham算法,G1【找內(nèi)點(diǎn)】：找到點(diǎn)列的一個(gè)內(nèi)點(diǎn)G，從內(nèi)點(diǎn)作水平向右的一向量L； G2【排序】：連接內(nèi)點(diǎn)和全部點(diǎn)列，根據(jù)這些連線與L的夾角按遞增次序?qū)c(diǎn)列排序，形成一個(gè)雙向鏈接表； G3【求凸包上的起點(diǎn)】：求取點(diǎn)列中的任一個(gè)極點(diǎn)P0（x或y的最小/最大者）；,Min,4.1.3 凸包算法Graham算法,G4【求凸包上的一個(gè)頂點(diǎn)】：從點(diǎn)1出發(fā)依次考察連續(xù)的三個(gè)頂點(diǎn)，如果是向逆向轉(zhuǎn)（圖中實(shí)心圓點(diǎn)），則表的指針加1，否則刪去三個(gè)頂點(diǎn)中的中間點(diǎn)（圖中空心圓點(diǎn)），且指針減1；,順向點(diǎn),逆向點(diǎn),G5【求取凸包】：按G4遍歷點(diǎn)表，其結(jié)果即為點(diǎn)列的有向凸包。這樣求得的凸包是一個(gè)循環(huán)點(diǎn)

6、列，選取任一個(gè)起點(diǎn)均可作為凸包的起點(diǎn)。,4.1.4 包容性測(cè)試,決定平面上的一個(gè)點(diǎn)是在圖形的內(nèi)部還是在它的外部 符號(hào)判別法 角度判別法 Griffiths判別法 半射線交點(diǎn)計(jì)數(shù)判別法,4.1.4包容性測(cè)試符號(hào)判別法,對(duì)于一個(gè)凸n多邊形，按照同一方向（保證邊向量的左側(cè)為多邊形的內(nèi)部）計(jì)算通過各邊向量的直線的方程系數(shù) (Ai , Bi , Ci) (i=1,2,n) 設(shè)被測(cè)試點(diǎn)為T(Xt，Yt)，計(jì)算 Di=Aixt+Biyt+Ci (i=1,2,n) 若Di0(或Di=0)，則被測(cè)試點(diǎn)在多邊形的外部(或在邊界上)，判斷結(jié)束。 否則，所有的Di0 (i=1,2,n)，表示被測(cè)試點(diǎn)在圖形的內(nèi)部。,4

7、.1.4包容性測(cè)試符號(hào)判別法,在此判別法中，多邊形為凸的條件不能少 雖然有 A45xt +B45yt + C45 0 而T卻在多邊形的內(nèi)部。,4.1.4包容性測(cè)試角度判別法,依次將測(cè)試點(diǎn)P與多邊形各頂點(diǎn)相連,然后計(jì)算點(diǎn)P與各頂點(diǎn)圍成的角度之和,點(diǎn)在多邊形之外,點(diǎn)在多邊形之內(nèi),4.1.4包容性測(cè)試角度判別法,大?。豪糜嘞叶ɡ?方向：令,夾角如何計(jì)算？,4.1.4包容性測(cè)試角度判別法,這種角度的計(jì)算不需要很高的精度，其誤差甚至可以達(dá)到也不失判別的正確性 但是必須計(jì)算兩向量間的夾角而涉及到反三角函數(shù)的計(jì)算，計(jì)算工作量較大 計(jì)算量雖也是O(n)，但要比符號(hào)判別法的工作增加幾倍 其適用性能從凸多邊形擴(kuò)

8、展到一般多邊形,4.1.4包容性測(cè)試Griffiths判別法,為了在角度判別法中避免求取反三角函數(shù)，Griffiths在1981年提出了一種近似的方法以加快運(yùn)算速度。 基本原理： 矢量積PtPiPtPi+1與sini成正比，而數(shù)量積PtPiPtPi+1與cosi成正比,于是tgi或ctgi可由這兩個(gè)積的結(jié)果導(dǎo)出。,4.1.4包容性測(cè)試Griffiths判別法,角度i可由下列近似的線性逼近公式求得： arctg x=/4x+C 其中,4.1.4包容性測(cè)試半射線交點(diǎn)判別法,令R是一條以P為起點(diǎn)任何方向的半射線 當(dāng)R和多角形的交點(diǎn)個(gè)數(shù)為奇數(shù)個(gè)時(shí)，點(diǎn)P在多角形的內(nèi)部 當(dāng)交點(diǎn)個(gè)數(shù)為偶數(shù)或?yàn)榱銜r(shí)，點(diǎn)P在多

9、角形的外部,若選擇的半射線通過多角形的頂點(diǎn)，或與多角形的邊重合時(shí)，根據(jù)向量交點(diǎn)的特征值、重點(diǎn)和重邊的處理原則進(jìn)行交點(diǎn)的取舍，然后計(jì)數(shù)。,算法P：半射線交點(diǎn)計(jì)數(shù)包容性測(cè)試算法,P1【建立射線】由點(diǎn)Pt(Xt，Yt)向點(diǎn)(X，Yt)建立一射線向量。其中X是一個(gè)多角形頂點(diǎn)不可能達(dá)到的X大值，Yt意味著射線和X軸平行； P2【求交點(diǎn)】將此射線向量和多角形的各邊向量求交。并記錄交點(diǎn)幾何參數(shù)和相對(duì)于射線的特征值，并將交點(diǎn)按其射線方向排隊(duì)；,算法P：半射線交點(diǎn)計(jì)數(shù)包容性測(cè)試算法,P3【合并重點(diǎn)】判別相鄰交點(diǎn)的幾何參數(shù)，如為重點(diǎn)，則求其特征值的代數(shù)和，如代數(shù)和為零，則取消兩個(gè)交點(diǎn)，否則取消其中一個(gè)交點(diǎn)； P4

10、【合并相鄰?fù)卣鹘稽c(diǎn)】判別相鄰兩個(gè)交點(diǎn)的特征，如果相鄰兩個(gè)特征相同，則取消其中一個(gè)交點(diǎn)； P5【判別】計(jì)算交點(diǎn)個(gè)數(shù)，如為奇數(shù)，則點(diǎn)在多角形內(nèi)部，否則在多角形外部。,4.1.5最大最小判別法,如果兩個(gè)圖形元素的最小矩形包圍盒子不相重迭，則這 兩個(gè)圖形元素不可能相交。 最小最大判定法提供了這樣一種快速拒絕判定法，這個(gè) 判定法是用圖形元素的最小外接矩形(或矩形盒子)來 替代，用以粗略地判定兩個(gè)圖形元素之間的某種關(guān)系。 雖然，這種判定條件是一種充分條件，在某些情況下， 這種替代是不正確的，但由于其比較速度很快的優(yōu)點(diǎn) 彌點(diǎn)補(bǔ)了這種不足。,4.1.5最大最小判別法,a.外接矩形不相迭，圖形也不相迭 b.外

11、接矩形相迭，但圖形并不相迭 c.外接矩形相迭，圖形也相迭,4.1.5最大最小判別法,1）找出多邊形的最小包含矩形,該矩形的4條邊分別平行于兩坐標(biāo)軸，矩形的位置和大小可以用Xmax、Xmin、Ymax、Ymin來定義，而這4個(gè)參數(shù)就是多邊形頂點(diǎn)坐標(biāo)中的極值。,2）重疊性檢驗(yàn),如果兩個(gè)多邊形的最小包含矩形不發(fā)生重疊，則這兩個(gè)多邊形必定不會(huì)重疊，則下式必有一個(gè)成立：,4.1.6 線與面的關(guān)系,令： D1= Ax1+By1+Cz1+D D2= Ax2+By2+Cz2+D D1(D2)0 1 且令：N=N1+N2,4.1.6 線與面的關(guān)系,則當(dāng)N-2，線在面的后面（ N=-2 ） N=0， 線在面上（正

12、面或背面） 以此線兩頂點(diǎn)為端點(diǎn)的兩相鄰線的另兩個(gè)端點(diǎn)的狀態(tài)決定 若另兩個(gè)端點(diǎn)中有一端點(diǎn)在面的前面，則此線棱在面的正面； 若另兩端點(diǎn)均在面之后，此時(shí)線在面的背面 N0，線在面之前（ N=1 和 N=2 ）,4.1.6線與面的關(guān)系,N=-1， 線貫穿面； 令=D1/ (D1+D2) 若N20（P2點(diǎn)在面后）， 則棱的0,間的部份（P1P）在面的前面； 否則，棱的0,間的部份在面的后面。,4.1.7 線與線的關(guān)系,設(shè)空間有兩條線，其端點(diǎn)分別為P1、P2和Q1、Q2，方程分別為：,4.1.7 線與線的關(guān)系,求得它們?cè)赬OY投影面上的交點(diǎn)S（P1P2上的P點(diǎn)和Q1Q2上的Q點(diǎn)在XOY上的重合投影點(diǎn)）的參

13、數(shù)s和s 若s0,1且 s0,1， 則這兩條線在空間存在遮擋關(guān)系,4.1.7 線與線的關(guān)系,將s和s分別代入深度方程 zp=zp1+(zp2-zp1)s zq=zq1+(zq2-zq1)s 若 zp zq P1P2在Q1Q2的前面 zp = zq P1P2與Q1Q2在同一平面上 zp zq P1P2在Q1Q2后面,4.2 距離和面積,將點(diǎn)的坐標(biāo)代入直線方程即可。,1、點(diǎn)到平面上直線的距離,2、點(diǎn)到空間直線的垂足,設(shè)nL是直線L的單位方向向量，P0是L上的任意一點(diǎn)，P是空間中的任意一點(diǎn)，則P在L上的垂足Pv為：,例：已知點(diǎn)P0(0,0,0),PL(1,1,1)，直線L由P0、PL決定，求點(diǎn)P(0

14、.5,1,0)到直線L的垂足PV。,4.2 距離與面積,3、點(diǎn)到空間直線的距離,例：求點(diǎn)P（2，-1，1）到直線L的距離D。,其中：NL是直線的方向向量，P0是直線上任意點(diǎn)。,4.2 距離與面積,4、點(diǎn)到平面的距離,其中：Ns為平面的法向量。,注意： 1、若空間平面方程是規(guī)格化的，則點(diǎn)到面的距離直接把點(diǎn) 的坐標(biāo)代入平面方程即可。 2、點(diǎn)到平面的距離符號(hào)標(biāo)示點(diǎn)在面的方位。,4.2 距離與面積,5、空間兩直線的距離,L1與L2是空間任意兩條直線，方向向量分別為Nl1，Nl2，則兩直線之間的距離為：,其中P1和P2分別為L(zhǎng)1和L2上的任意點(diǎn)。,例：求直線L1與直線L2之間的距離。,4.2 距離與面積

15、,6、直線與平面的距離,空間直線L的方向向量為NL，平面S的法向量為Ns，若NL與NS的點(diǎn)積不為0，則線面相交，距離為0，否則，距離為：,其中：PL與Ps分別為直線和平面上的任意點(diǎn)。,例：求直線 與平面S：2y-z=0之間的距離。,4.2 距離與面積,7、空間兩平面的距離,若兩平面平行，則兩者之間的距離為：,4.3 相交計(jì)算,1、線面相交,設(shè)空間直線L的方向向量為NL，平面S的法向量為Ns，若NLNs不為0，則線面相交，交點(diǎn)為：,其中：PL與Ps分別為直線和平面上的任意點(diǎn)。,4.3 相交計(jì)算,2、面面相交,設(shè)空間任意平面S1、S2，法向量分別為Ns1、Ns2，Ps1和Ps2分別是兩平面上的任意點(diǎn)。若兩平面相交，交線方向?yàn)镹s1Ns2，交點(diǎn)為：,4.4 圖形填充,對(duì)圖形有界區(qū)域的矢量化填充 直線段和圖形公共部份的求取是區(qū)域填充算法的基礎(chǔ)； 在隱藏線消除中，則是對(duì)畫面上的線段作相反的判斷，公共部份是被隱藏的，而非公共部份則是需要繪制的。,4.4 圖形填充,S1【建立方程】根據(jù)圖形描述(圓弧曲線XYR)，對(duì)直線連接的，是根據(jù)二點(diǎn)式建立過二點(diǎn)的有向法線式系數(shù)，對(duì)圓弧連接的則求取圓心位置。 S2【求取填充線范圍】對(duì)各圖形頂點(diǎn)求取斜率為K的截距；并在所有截距中求取最大值bmax和最小值bmin。,4.4 圖形填充,S3【建立初始填充線】令b=bmin+D，過點(diǎn)(0，b)，斜