第11講三維形體顯示技術(shù)-1

1、第11講 三維形體顯示技術(shù) 三角剖分及多面體顯示技術(shù) 11.1、形體表面三角剖分11.2、多邊形模型的幾何壓縮（選學(xué)）11.3、簡單線框顯示11.4、線框消隱顯示 11.4.1、消隱算法概述 11.4.2、凸多面體消隱算法 11.4.3、任意多面體消隱算法11.5、形體濃淡圖簡單繪制 11.5.1、光照效果影響因素 11.5.2、簡單效果的濃淡圖生成本章目的 1、了解三角剖分基本原理2、掌握形體線框顯示技術(shù)3、了解線框消隱顯示技術(shù)4、了解形體濃淡圖簡單繪制原理 CAD系統(tǒng)幾何建模過程形體定義形體定義輸入輸入1形體定義形體定義輸入輸入2形體定義形體定義輸入輸入n內(nèi)部內(nèi)部CSGBREP表達表達布爾

2、布爾運算運算結(jié)果形體結(jié)果形體BREP表達表達三角三角剖分剖分顯示數(shù)顯示數(shù)據(jù)結(jié)構(gòu)據(jù)結(jié)構(gòu)顯示顯示渲染渲染顯示參顯示參數(shù)定義數(shù)定義工程工程應(yīng)用應(yīng)用在CAD系統(tǒng)中，用戶采用參數(shù)化特征建模交互方式建立CAD模型，并以CSGBREP表達存儲模型數(shù)據(jù)。11.1 形體表面的三角剖分1）概述因此，必須將BREP表示轉(zhuǎn)化為基于三角形的顯示格式。在CAD系統(tǒng)中，廣泛采用OpenGL、DirectX等顯示技術(shù)。OpenGL 、DirectX等廣泛支持基于三角形網(wǎng)格的多邊形顯示技術(shù)（其簡單編程介紹見講義第2部分） 。通常在CAD系統(tǒng)中，形體BREP表達面的方程多采用參數(shù)曲面等數(shù)學(xué)描述，面的邊界多采用參數(shù)曲線描述。為實現(xiàn)

3、形體線框消隱，首先需將形體的表面（曲面）進行離散，用平面多邊形逼近的方法近似表示（多采用三角剖分），如下圖所示。2）曲面三角剖分算法曲面三角剖分算法是CAD系統(tǒng)的基礎(chǔ)算法，國內(nèi)外關(guān)于該算法的研究文獻很多（參閱有關(guān)參考文獻）。經(jīng)三角剖分處理后，形體上的所有面用三角形面逼近表示，形體上的邊用三角形邊的兩個端點來定義，最終三維形體表面都生成并記錄了完整的多面體離散數(shù)據(jù)（即顯示數(shù)據(jù)）。CAD系統(tǒng)中的顯示算法（線框圖、線框消隱圖、真實感顯示圖等）大多數(shù)都是基于該多面體離散數(shù)據(jù)的算法處理。在CAD系統(tǒng)中，為滿足顯示需要，通常采用全自動三角剖分算法，避免用戶干預(yù)。則三角化算法主要考慮因素為算法速度、曲面逼近

4、精度，其次考慮算法所生成的三角形數(shù)量（盡量少）。對于有限元分析來說，對網(wǎng)格剖分質(zhì)量要求更高，通常網(wǎng)格剖分時允許用戶進行適當(dāng)交互。則對三角形的形態(tài)進行約束，如避免狹窄三角形、三角形密度變化比較平滑等。根據(jù)網(wǎng)格生成過程的不同，網(wǎng)格剖分主要分為映射網(wǎng)格劃分和自由網(wǎng)格劃分兩類。映射網(wǎng)格劃分是對規(guī)整模型的一種規(guī)整網(wǎng)格劃分方法，對于面是四邊形，網(wǎng)格劃分?jǐn)?shù)需在對邊上保持一致；對于體是六面體，形成的單元全部為六面體。映射網(wǎng)格劃分為多數(shù)商用有限元分析軟件所采用。自由網(wǎng)格劃分又分為節(jié)點連接法、拓?fù)浞纸夥ā缀畏纸夥?、柵格法等。在此僅介紹較為常用的節(jié)點連接法。步驟1：邊界離散節(jié)點連接法該算法實現(xiàn)主要分為以下幾個步驟

5、： 1）邊界離散； 2）參數(shù)域內(nèi)部節(jié)點生成；3）參數(shù)域網(wǎng)格拓?fù)溥B接； 4）曲面上映射；5）按精度自適應(yīng)加密逼近。根據(jù)給定初始精度對曲面的邊界及參數(shù)域邊界進行離散，生成一組邊界節(jié)點，構(gòu)成多邊形邊界。步驟2：參數(shù)域內(nèi)部節(jié)點生成考慮到空間曲面的復(fù)雜性，為使算法簡便，網(wǎng)格生成先在參數(shù)域內(nèi)進行，給定初始密度對參數(shù)域內(nèi)部布置一定數(shù)量節(jié)點。為方便起見，不妨取水平方向或垂直方向按一定間隔掃描布點。如果所布置節(jié)點離邊界節(jié)點或已有的內(nèi)部節(jié)點很近，則取消該節(jié)點和調(diào)整間隔。步驟3：網(wǎng)格拓?fù)溥B接波前法：1985年由Lo.S.H提出。生成過程從外邊界開始（此時前沿邊即為邊界），象波浪一樣向區(qū)域內(nèi)部推進。具體如下：1）每一

6、次操作在所生成的前沿邊中取出一條 邊，然后在所剩的內(nèi)部節(jié)點中選取一個最 合適的點，生成一個三角形；2）隨之前沿邊及剩余內(nèi)部點集接著動態(tài)更 新，直至網(wǎng)格全部生成（此時前沿邊和剩 余內(nèi)部點集為空集）。該方法在選擇內(nèi)部節(jié)點的過程中，設(shè)三角形前沿邊長為a，則所選點應(yīng)使邊b、c滿足（b2c2）為最小即可生成合理的三角形。典型的網(wǎng)格拓?fù)渖伤惴▋煞N：波前法、Delaunay方法。Delaunay方法：目前最為廣泛的方法。其算法思想為：（ Voronoi多邊形生成算法可詳見計算幾何參考書）1）對于已生成的每一個節(jié)點P i（i1,2,N）, 在其鄰域建立一個區(qū)域，一般是凸多邊形，稱Voronoi多邊形；2）該

7、多邊形的邊界由該點與其近旁的節(jié)點連線后并作的中垂線構(gòu)成；3）該多邊形只與那些與p點最鄰近的點有關(guān)，較遠的點不起作用；4）N個節(jié)點得到N個Voronoi多邊形，連接兩相鄰多邊形中的節(jié)點即為所求三角形。步驟4：曲面上映射將參數(shù)域所得的三角形網(wǎng)格一一映射到空間曲面，形成參數(shù)域與空間域一一對應(yīng)的拓?fù)溥B接關(guān)系。步驟5：自適應(yīng)加密對空間曲面網(wǎng)格的每個三角形進行校驗，如果該三角形對曲面的逼近誤差超過所需精度，則對該三角形進一步網(wǎng)格加密。加密方法主要有如右圖所示三種方法，但要注意域鄰近三角形的過渡連接，避免T型節(jié)點。算法說明：對于有退化情況的參數(shù)曲面，其算法應(yīng)作一定修正。對于有限元分析，網(wǎng)格則還應(yīng)增加一個優(yōu)化

8、步驟，避免狹窄三角形出現(xiàn)。11.2、多邊形模型的幾何壓縮（選學(xué)）隨著CG&CAD技術(shù)應(yīng)用范圍日益擴大，對計算機圖形合成質(zhì)量要求也不斷提高，這就需要有足夠精細的幾何模型；三角化越精細，其數(shù)據(jù)容量越大，其存儲、傳輸及顯示越困難；因此，研究新的占用空間小、繪制速度快，適合于計算機網(wǎng)絡(luò)傳輸?shù)娜S幾何數(shù)據(jù)表示方法有著十分重要的意義。僅硬件升級不夠，還需軟件算法支持 。1）幾何壓縮概述幾何壓縮分為：單分辨率模型壓縮、多分辨率模型壓縮單分辨率模型壓縮算法代表： Deering等為代表的三角網(wǎng)格連接關(guān)系實時壓縮算法 Taubin等為代表的基于拓?fù)涫中g(shù)的壓縮算法多分辨率模型壓縮分為： 離散多分辨率模型、連續(xù)多分

9、辨率模型 離散多分辨率模型壓縮是對復(fù)雜的三角形網(wǎng)格通過簡化算法逐步得到不同細節(jié)層次的多個三角網(wǎng)格模型； 連續(xù)多分辨率模型壓縮則是通過一種緊湊的模型表示方法，可生成任意多個不同分辨率的模型。想一想，當(dāng)你觀看遠處風(fēng)景，你能看清細節(jié)嗎？在CG&CAD中，對距離較遠的物體進行顯示時不需細節(jié)，而越來越近時則細節(jié)越清晰。由此提出網(wǎng)格模型簡化壓縮的需求，此即幾何壓縮。2）單分辨率模型的幾何數(shù)據(jù)壓縮指對物體的一種層次細節(jié)的多邊形網(wǎng)格表示形式的幾何數(shù)據(jù)進行壓縮。使之生成：三角形條帶、扇形、網(wǎng)格。目前圖形加速卡均支持三角形條帶、扇形、規(guī)范網(wǎng)格的傳輸和渲染顯示。在計算機內(nèi)部，每個三角形3個頂點（9個坐標(biāo)）需36個字

10、節(jié)來描述（不考慮顏色、法向、紋理等）。如果每個三角形獨立表示并輸出，則每個頂點被重復(fù)多次，浪費顯存，影響傳輸（目前傳輸是瓶頸）。用三角形條帶表示減少頂點傳輸量：相鄰三角形公用一條邊，從第二個三角形開始，每新增一個三角形增加一個點，這使得每個頂點最多只須傳送兩次。V0V2V3V4V5V1V10V9V8V7V6V12V11V14V13V15V0V1V70110111110110000000000000該算法的核心在于產(chǎn)生盡可能長的三角形條帶，提高顯示傳送速度。3）離散多分辨率模型的幾何壓縮離散多分辨率模型是對復(fù)雜的三角形網(wǎng)格經(jīng)過一系列簡化操作，得到了多個不同分辨率的多邊形網(wǎng)格模型。這種簡化算法通過

11、對三角形網(wǎng)格施以局部的變化而逐步得到不同的細節(jié)層次(LOD)。LOD技術(shù)在不影響畫面視覺效果的條件下，通過逐次簡化景物的表面細節(jié)來減少場景的幾何復(fù)雜性，以提高繪制效率。該技術(shù)通常對每一原始多面體模型建立幾個不同逼近精度的幾何模型，每個模型均保留了一定層次的細節(jié)。目前很多造型軟件和VR開發(fā)系統(tǒng)都支持LOD模型表示。 針對多分辨率模型，累進傳輸是有效的措施。首先傳輸LOD層次中一個最低分辨率的模型，然后在繪制操作開始的同時傳送一系列細化操作（類 JPGE 2000思想），減少等待時間。網(wǎng)格簡化的主要目標(biāo)是產(chǎn)生低分辨率近似，這種近似必須能保持原始模型的主要特征及總體外觀。因此，一些特征點（或線）應(yīng)保

12、留。一般來說被簡化的頂點（或邊、面）處曲率半徑較大，即平坦區(qū)域的三角形密度更小一些。目前網(wǎng)格簡化算法可以被簡單地劃分為以下3種方法： （ 1） 頂點去除(vertex decimation)； （2） 邊折疊(edge collapse)； （3）三角形折疊(triangle collapse)。頂點去除頂點去除邊折疊邊折疊三角形折疊三角形折疊11.3、簡單線框顯示線框顯示簡單快捷，適合于CAD實時交互。但有二義性。為了消除二義性及生成工程圖，通常需進行消隱顯示。經(jīng)過三角剖分處理，形成了完整的形體三角網(wǎng)格顯示模型的數(shù)據(jù)結(jié)構(gòu)。為了直觀快速交互顯示形體，通常直接顯示其線框模型。顯示方法：遍歷所有多

13、邊形網(wǎng)格的點表和邊表，依次畫直線。通常兩種顯示狀態(tài)可以任選： a）僅顯示輪廓邊（內(nèi)部邊不顯示）； b）顯示所有離散多邊形。11.4、線框消隱算法多面體消隱結(jié)果與形體幾何有關(guān)，也與視點有關(guān)。從應(yīng)用角度看，消隱問題分為：線消隱（Hidden-line）和面消隱（Hidden-surface）。前者用于線框圖，如凸（凹）多面體隱藏線消隱算法；后者用于填色圖，如Z-Buffer算法、掃描線算法、畫家算法等。11.4.1、消隱算法概述外法矢與視線矢量的夾角將平面分為兩類： （1）若 90，稱后向面； （2）若 90 180, 稱前向面后向面是不可見的；但前向面有可能全部可見，也可能部分可見。11.4.2

14、 凸多面體消隱算法對于凸多面體來說，前向面總可見，如右圖所示。若觀察方向V （從眼睛出發(fā)指向物體）與Z軸一致，則凸多面體消隱，僅需判斷后向面（即VN 0）即可把后向面的棱邊全部消除。Vn想一想，機械制圖課程中怎樣判斷可見性？為加速計算，可將凸多面體變換，使觀察方向 V（從眼睛出發(fā)指向物體）與 Z 軸方向一致，則僅判斷前向面的法矢分量 Nz 0 即可。凸多面體消隱算法如下：/ 假設(shè)已知凸多面體的面邊頂點表Begin 對凸多面體進行變換使V與Z同向； for（所有的面） 計算該面法矢的Z分量N z ； if（N z 0） /為前向面 for(該面所有棱邊） 畫出棱邊； EndVnizxy想一想，有

15、什么更快速的方法判斷后向面？課堂練習(xí)（一）如圖，正六棱柱繞軸線l 旋轉(zhuǎn)45度，試判定旋轉(zhuǎn)后面f的可見性。假設(shè)軸線l 經(jīng)過點（10，20，30），其方向矢為（0.5，-0.3，0.7）。yzof11.4.3、任意多面體消隱算法1）基本算法思路（1）所有后向面的棱邊不可見；（2）為加速運算，對視錐以外的物體進行裁剪，減少不必要的運算；v投影平面投影平面前裁剪面前裁剪面后裁剪面后裁剪面投影平面投影平面前裁剪面前裁剪面后裁剪面后裁剪面vnunu透視投影的視見體透視投影的視見體平行投影的視見體平行投影的視見體對于任意形狀多面體來說，后向面上的所有棱邊仍不可見，前向面則有可能可見，有可能不可見，也可能僅部

16、分可見。算法的重點是判斷前向面的棱邊的可見性。（3）對每一個前向面的所有棱邊判斷可見性，即判斷面對線的遮擋關(guān)系。判斷面與線的遮擋關(guān)系時將反復(fù)進行線線、線面求交，求交速度是關(guān)鍵。線面求交線面求交 線線求交線線求交2）前向面直線段對任意某平面遮擋關(guān)系判斷算法(1) 若線段兩端點及視點在給定平面同側(cè)（圖a），線段可見，轉(zhuǎn)6；(2) 若線段投影與平面投影的包圍盒無交（圖b），線段可見，轉(zhuǎn)6；圖圖 a 視點與線段同側(cè)視點與線段同側(cè) 圖圖 b 包圍盒不交包圍盒不交 (3) 求直線與平面的交點。若無交點轉(zhuǎn)4；否則交點在線段內(nèi)部或外部，則判斷： a）交點在線段內(nèi) ，將線段分兩段（圖c），與視 點同側(cè)的一段可見

17、，轉(zhuǎn)6； 剩余另一段在視點異側(cè)，轉(zhuǎn)4繼續(xù)判斷。 b）若交點在線段外部，轉(zhuǎn)4繼續(xù)判斷。 圖 c 線段與平面求交(5) 求第一段中點，若第一段中點在平面的投影內(nèi)，則相應(yīng)段被遮擋，否則不被遮擋；其他段的遮擋關(guān)系可依次交替取值判斷（如圖e） 。(6) 各可見段分別進入下一個面循環(huán)比較。直至所有面比較完畢，該線段判斷結(jié)束。圖圖 e 分段交替取值分段交替取值 (4) 求線段的投影與平面邊界投影的所有交點（圖d），并求交點在原直線方程的Z值(即深度)，所求得的各交點將線段的投影分成若干段。若無交點，轉(zhuǎn)6。圖 d 線段投影與平面邊界投影的交點（1）上述算法分析一條邊、一個面的情況，對多邊多面通過循環(huán)嵌套實現(xiàn)（

18、可采用GPU并行算法加速）；（2）如果有N條棱消隱，當(dāng)N很大時，用兩兩求交計算量很大O（N2）。為提高算法效率，需要減少求交工作量。常用方法有：加快相交測試；只對可見子線段進行可見性判斷，對不可見線段不予計算；（3）消隱是一項非常耗時計算?，F(xiàn)有商用CAD系統(tǒng)消隱算法正確率難以達到100%，尚不能完全滿足工程圖的特殊要求，且速度有待提高。（4）不同消隱算法的關(guān)鍵在于加速計算的策略和方法不同，重點在于線段可見性的判斷速度和正確性。3）算法分析討論該算法能支持工程圖生成。對CAD圖形來說，常常需要顯示輪廓，而非內(nèi)部三角形邊界，上述算法必須修正：（1）過濾三角形內(nèi)部邊界，可加快速度，但丟失輪廓邊界；（

19、2）若顯示輪廓邊界，只需對邊界和輪廓邊進行消隱計算；（3）工程圖中部分不可見邊用虛線繪出，需單獨標(biāo)識。注意：（1）該算法計算量大，非常耗時，不適合實時交互操作（如拖動）；（2）由于求交量大，因精度誤差導(dǎo)致消隱圖局部有時出現(xiàn)暇次；（3）曲面的輪廓線不夠光滑。11.5.1、光照效果影響因素思考：我們所見物體的顏色是怎樣形成的？ 影響觀察物體顏色的主要因素有哪些？11.5、形體濃淡圖簡單繪制光：當(dāng)光照射到物體表面時，物體對光會發(fā)生反射、透射、吸收、衍射、折射和干涉。 被物體吸收的部分轉(zhuǎn)化為熱，反射光和折射光則遵循反射定律和折射定律。 顏色：是光刺激人眼而產(chǎn)生的主觀感覺，是物理和心理相互作用的一種復(fù)雜

20、生理反映 ，使我們能看見物體的顏色。物體的顏色不僅取決于物體本身（材質(zhì)、粗糙度等），而且還與光源（光的特性）、周圍環(huán)境、以及觀察者的視覺有關(guān)。但人的感覺也會出現(xiàn)錯覺哦（如下圖）！古言：耳聽為虛，眼見為實，對嗎 ？實驗表明：白光經(jīng)棱鏡被分解為紅、橙、黃、綠、青、藍、紫的可見光譜。人對紅、綠、藍三色最敏感，紅色最強，藍色相對較弱。三基色（三原色）原理：大多數(shù)的顏色可以通過紅、綠、藍三色按照不同的比例合成。三基色相互獨立，任何一種基色都不能有其它兩種顏色合成。某一種顏色和這三基色的關(guān)系可用下面的式子來描述：在計算機圖形學(xué)中有兩種三基色系統(tǒng)：紅、綠、藍加色系統(tǒng)(RGB)和青、品紅、黃減色系統(tǒng)(CMY)

21、 ，前者適合顯示系統(tǒng)，后者適合印刷系統(tǒng)。RGB加色系統(tǒng)加色系統(tǒng)CMY減色系統(tǒng)減色系統(tǒng)三基色（或三原色） 顏色C R(紅色百分比) G(綠色百分比) B(藍色百分比)11.5.2 簡單效果的濃淡圖生成1）多邊形填充Flat模型算法思路及步驟：1）顏色計算：以三角形為單位計算顏色，根據(jù)多面體表面的平面法矢決定顏色值，其顏色值根據(jù)法矢與光線的夾角確定（平行于光線最亮）。2）三角形填充：利用第2講基于掃描線的多邊形填充算法（或直接調(diào)用OpenGL的多邊形填充算法）即可。該算法簡單，但所繪制圖形的輪廓分明，各多邊形之間過渡不光滑，沒考慮視線及其它光照環(huán)境因素。例：基于OpenGL進行Flat模型編程實驗

22、。 僅需對第2講中的MyDiisplay（）函數(shù)進行簡單修改即可。void myDisplay(void)glClear(GL_COLOR_BUFFER_BIT);/buffer設(shè)置為顏色可寫glShadeModel(GL_SMOOTH);/設(shè)置為光滑明暗模式 /第1個三角形glBegin(GL_TRIANGLES);/開始畫三角形 glColor3f(1.0,0.0,0.0);/設(shè)置第一個頂點為鮮紅色glVertex2f(-1.0,-1.0);/設(shè)置第一個頂點的坐標(biāo)為（-1.0，-1.0） glColor3f(1.0,0.0,0.0);/設(shè)置第二個頂點為鮮紅色glVertex2f(0.0,-

23、1.0);/設(shè)置第二個頂點的坐標(biāo)為（0.0，-1.0）glColor3f(1.0,0.0,0.0);/設(shè)置第三個頂點為鮮紅色glVertex2f(-0.5,1.0);/設(shè)置第三個頂點的坐標(biāo)為（-0.5，1.0）glEnd();/三角形結(jié)束 /第2個三角形glBegin(GL_TRIANGLES);/開始畫三角形 glColor3f(0.5,0.0,0.0);/設(shè)置第一個頂點為暗紅色glVertex2f(0.5,1.0); /設(shè)置第一個頂點的坐標(biāo)為（-0.5，1.0） glColor3f(0.5,0.0,0.0);/設(shè)置第二個頂點為暗紅色glVertex2f(0.0,-1.0);/設(shè)置第二個頂點的坐標(biāo)