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

1、第二個(gè)幾何圖形，定義矢量叉積的強(qiáng)度：| P1P2 |=x1y2-x2y1，結(jié)果為標(biāo)量。|P1P2 | 0時(shí)，P2的逆時(shí)針方向?yàn)镻1 | | p1p 2 | | 0時(shí)，P1的順時(shí)針方向?yàn)閨 | P1P2 | |=0時(shí)，P2與P1共線且為4.1.如果C 0，P1P2將逆時(shí)針旋轉(zhuǎn)P2點(diǎn)，然后得到P2P3。如果C 0，P1P2將順時(shí)針旋轉(zhuǎn)P2點(diǎn)，然后得到P2P3。C=0時(shí)，P1，P2，P3共線，4.1.3凸形輪廓算法，凸形輪廓計(jì)算的基本任務(wù)，其中圖形的凸形輪廓是包含牙齒圖形的面積最小的凸形多邊形，構(gòu)成凸形輪廓的點(diǎn)稱為凸形點(diǎn)，其馀點(diǎn)稱為凸形輪廓內(nèi)部點(diǎn)。，凸多邊形，4.1.3凸殼算法，基本思路，4.1.3

2、凸殼算法Jarris算法，將s設(shè)置為平面內(nèi)的點(diǎn)集，將s中y坐標(biāo)最小的點(diǎn)用作凸殼的第一個(gè)頂點(diǎn)H1，與從H1開始的水平線相交計(jì)算為。命令集的當(dāng)前頂點(diǎn)數(shù)為n0=n-1。While (n0) for I=1至n0向量Pi0Pi計(jì)算；計(jì)算。其馀所有if頂點(diǎn)都位于向量Pi0Pi之上，Pi點(diǎn)添加到凸面包列表中。pi0-Pi；從當(dāng)前點(diǎn)集中刪除交點(diǎn)。n0=n0-1；Endif endfor endwhile，4.1.3凸殼算法Graham算法，4.1.3凸殼算法Graham算法，G1 查找內(nèi)部點(diǎn):查找“點(diǎn)”列中的內(nèi)部點(diǎn)G，從內(nèi)部點(diǎn)水平定位G2 排序:連接內(nèi)部點(diǎn)和所有點(diǎn)列，根據(jù)這些連接和L之間的角度以升序?qū)c(diǎn)列進(jìn)

3、行排序，以形成雙向鏈接表。G3 查找凸面包的起點(diǎn):獲取點(diǎn)行中的所有極P0(x或y的最小/最大值)。Min，4.1.3凸形輪廓算法Graham算法，G4 查找凸形輪廓的頂點(diǎn):從點(diǎn)1開始依次查看連續(xù)的三個(gè)頂點(diǎn)，如果是反向旋轉(zhuǎn)(圖中的實(shí)心點(diǎn))，則將表中的指針加1，否則刪除這三個(gè)，方向點(diǎn)，反向這樣得到的凸包是周期點(diǎn)列，無論選擇哪個(gè)起點(diǎn)，都可以用作凸包的起點(diǎn)。，4.1.4包容性測試，平面上的一點(diǎn)是否位于圖形內(nèi)部，或外部符號判別法角度判別法Griffiths判別法反射線交叉數(shù)判別法，4.1.4包容性測試符號判別法，對于凸面N多邊形，4.1.4凸多邊形，包含4.1.4測試角度確定方法，依次將測試點(diǎn)P連接到多

4、邊形的每個(gè)頂點(diǎn)，然后計(jì)算點(diǎn)P和每個(gè)頂點(diǎn)包圍的角度之和。點(diǎn)位于多邊形外部。、4.1.4包容性測試角度判別法，從凸面多邊形到規(guī)則多邊形角度的適用性能計(jì)算不需要高精度。誤差也可以達(dá)到。必須計(jì)算兩個(gè)矢量之間的角度，而不會(huì)失去判斷的準(zhǔn)確性。與倒三角形函數(shù)計(jì)算有關(guān)。計(jì)算工作量大的計(jì)算量也是O(n)，但需要比符號判別法多做幾倍的工作。4.1.4包容性測試Griffiths判別法，為了避免角度判別法中的倒三角函數(shù)，Griffiths在1981年提出了加快運(yùn)算速度的近似值?；驹瓌t：向量乘積PtPiPtPi 1與Sini成比例，數(shù)量乘積PtPiPtPi 1與cosi成比例，因此tgi或ctgi可以從兩個(gè)乘積的結(jié)

5、果中導(dǎo)出。包含、4.1.4的測試Griffiths判別法，角度I可以通過以下近似線性近似公式得出：arctg x=/4x C，測試反射線交叉判別式點(diǎn)P位于多邊形外部。如果選定的半射線通過多邊形的頂點(diǎn)或與多邊形的邊重合，則根據(jù)矢量交點(diǎn)的特性值、焦點(diǎn)和重邊的處理原則選擇和計(jì)算交點(diǎn)。算法P:反光線交叉包容測試算法，創(chuàng)建從P1 創(chuàng)建光線點(diǎn)Pt(Xt，Yt)到點(diǎn)(X，Yt)的光線向量。其中x是多邊形頂點(diǎn)無法到達(dá)的x的較大值，Yt表示光線與x軸平行。P2 查找交點(diǎn)使牙齒射線矢量與多邊形的每個(gè)角矢量相交。記錄相對于相交幾何圖元參數(shù)和射線的特征值，并在射線方向?qū)R交點(diǎn)。算法P:包含半射線交點(diǎn)數(shù)的測試算法，P3

6、 積分中點(diǎn)確定相鄰交點(diǎn)的幾何參數(shù)(例如中點(diǎn))。求特征值的代數(shù)總和(例如代數(shù)和0)將取消兩個(gè)交點(diǎn)。否則，其中一個(gè)交點(diǎn)將被取消。P4 合并相鄰的相同要素交集標(biāo)識兩個(gè)相鄰交點(diǎn)的要素，如果兩個(gè)相鄰的要素相同，則放棄其中一個(gè)交點(diǎn)。P5 判別計(jì)算交點(diǎn)數(shù)。奇數(shù)是多邊形內(nèi)部的點(diǎn)，否則是多邊形外部的點(diǎn)。4.1.5最大最小判別法，最小最大判別法使用圖形元素的最小外部矩形(或矩形方塊)粗略確定兩個(gè)圖形元素之間的關(guān)系。顯然，牙齒判定條件是充分的條件，在某些情況下，這種替代不正確，但由于比較快的優(yōu)點(diǎn)，彌補(bǔ)了這種不足。a .外部矩形沒有重疊，圖形也沒有重疊。b .外部矩形重疊，但圖形不重疊。外部矩形也重疊，圖形也重疊。、

7、4.1.5最大最小判別法，1)查找多邊形的最小包含矩形。，2)檢查重疊，如果兩個(gè)多邊形的最小包含矩形沒有重疊，則兩個(gè)多邊形不能重疊。以下內(nèi)容之一必須為真：4.1.6直線與面的關(guān)系；D1=ax1 by1 cz1 D2=N-2，直線位于面之后(N=-2) N=0，直線位于面上方(前面或后面)的兩個(gè)牙齒善意頂點(diǎn)作為端點(diǎn)的兩個(gè)相鄰善意如果其他兩個(gè)端點(diǎn)都在面之后，則線位于面的背面N0，線穿過面之前(N=1和n=2)，4.1.6線與面的關(guān)系，N=-1，線穿過面。指令=D1/(D1 D2) N20(P2點(diǎn)在面之后)，則位于棱柱的0，之間的部分(P1P)牙齒面之前。否則，邊的0，之間的部分位于面的后面。4.1

8、.7直線和直線之間的關(guān)系；安裝空間中分別存在P1、P2、Q1、Q2、方程式：4.1.7直線和直線之間的關(guān)系。將4.1.7直線和善意關(guān)系，S和S分別賦值到深度表達(dá)式ZP=zp1(zp2-zp1)szq=zq1(zq2-zq1)S，ZP zq P1P2在Q1Q2之前為ZP=，1，其中：NL是善意方向向量，P0是善意的任意點(diǎn)。4.2距離和面積、4、點(diǎn)到平面的距離。其中Ns是平面的法線向量。注意：1，空間平面方程規(guī)范化時(shí)，點(diǎn)對面距離只需將點(diǎn)的坐標(biāo)直接賦給平面方程。2、點(diǎn)到平面的距離符號指示面上點(diǎn)的方向。4.2距離和面積，5，空間兩條善意距離，L1和L2是空間中的兩條直線，方向矢量分別為Nl1，Nl2，

9、則兩條直線之間的距離為：其中P1和P2分別是L1和L2的隨機(jī)點(diǎn)。范例：尋找線L1和線L2之間的距離。4.2距離和面積，6，直線和平面之間的距離，空間直線l的方向矢量是NL，平面s的法線矢量是NS，NL和Ns的點(diǎn)積不是0牙齒，則直線面相交，距離為0。否則，距離將查找：其中：PP，例如直線和平面s: 2y-z=0之間的距離。4.2距離和面積，7，空間兩個(gè)平面之間的距離，如果兩個(gè)平面平行，則兩個(gè)平面之間的距離為，相交計(jì)算4.3，1，直線面，將空間直線L的方向矢量設(shè)置為NL，將平面S的法線矢量設(shè)置為Ns，以及如果兩個(gè)平面相交，則相交方向?yàn)镹s1Ns2，交點(diǎn)為、4.4圖形填充、4.0S2 計(jì)算填充線實(shí)際

10、范圍取得每個(gè)圖形頂點(diǎn)的坡度比為K的斷面。從所有截?cái)帱c(diǎn)中獲取最大值bmax和最小值bmin。，4.4圖形填充，S3 創(chuàng)建初始圖案填充 b=bmin D，指針經(jīng)過(0，b)，坡率k的直線ax by c=0，直線方向可以是任意的，但是一旦選定取得牙齒無限長直線與所有圖形(包括S4 尋找填充線幾何參數(shù)和圖征)的交點(diǎn)。如果與弧線段的交點(diǎn)相切，則切線點(diǎn)不會(huì)相交，而是以直線方向?qū)R交點(diǎn)。4.4圖形填充，S5 重點(diǎn)處理中點(diǎn)的話，以重點(diǎn)特征值為代數(shù)，如果該代數(shù)等于零，則取消重點(diǎn)。S6 輸出圖案填充依次輸出從負(fù)要素交點(diǎn)到相鄰正要素交點(diǎn)的直線段。S7 下一圖案填充命令b=b D，如果bbmax超出范圍，則退出，否則

11、旋轉(zhuǎn)到S4。練習(xí)題、1、平面幾何投影的以下敘述語句中正確的論述為()A，在平面幾何投影中，如果投影中心從投影面向無限遠(yuǎn)移動(dòng)，則平行投影。b，透視投影比平行投影具有更真實(shí)的視覺效果，真實(shí)地反映對象的精確大小和大小。c，在透視投影變換中，平行線集可以投影到平行的投影面上，從而產(chǎn)生消失點(diǎn)。d，三維空間中的物體可以執(zhí)行透視投影變換，產(chǎn)生三個(gè)或更多的主要消失點(diǎn)。、練習(xí)題、2、包含角和判別點(diǎn)將點(diǎn)P連接到區(qū)域內(nèi)外的多邊形頂點(diǎn)，點(diǎn)P位于區(qū)域外的是_ _ _ _ _ _ _ _ _ _ _。a，點(diǎn)p與每個(gè)頂點(diǎn)包圍的角度之和為0 B，點(diǎn)p與每個(gè)頂點(diǎn)包圍的角度之和為c，點(diǎn)p與每個(gè)頂點(diǎn)包圍的角度之和為2 D，點(diǎn)p與每個(gè)頂點(diǎn)包圍的角度之和為3，練習(xí)中的問題，3，如果多邊形外部的點(diǎn)a與點(diǎn)B和線段連接，則牙齒線段與多邊形邊界相交的