計算機圖形學-第4章 幾何計算.ppt

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

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

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

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

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

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

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

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

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

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

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

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

13、數(shù)s和s 若s0,1且 s0,1， 則這兩條線在空間存在遮擋關系,4.1.7 線與線的關系,將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 距離和面積,將點的坐標代入直線方程即可。,1、點到平面上直線的距離,2、點到空間直線的垂足,設nL是直線L的單位方向向量，P0是L上的任意一點，P是空間中的任意一點，則P在L上的垂足Pv為：,例：已知點P0(0,0,0),PL(1,1,1)，直線L由P0、PL決定，求點P(0

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

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