版權(quán)說(shuō)明:本文檔由用戶(hù)提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
1、計(jì)算機(jī)圖形學(xué),武漢大學(xué)電子信息學(xué)院 王泉德qdwang@sohu.com,第六章 幾何造型,一、引言二、形體在計(jì)算機(jī)內(nèi)的表示三、常用的形體表示方法,一、引言,三維圖形在科學(xué)研究和工程技術(shù)中有著廣泛的應(yīng)用。在CAD中,需要對(duì)所設(shè)計(jì)的作品從不同的角度進(jìn)行審視。計(jì)算機(jī)幾何造型就是用計(jì)算機(jī)系統(tǒng)來(lái)表示、控制、分析和輸出三維形體。是通過(guò)對(duì)點(diǎn)、線、面、體等圖形元素進(jìn)行幾何變換和并、交、差等集合運(yùn)算,在計(jì)算機(jī)內(nèi)表示、構(gòu)造三維形體的技術(shù),即為幾何
2、造型技術(shù)。 。所以幾何造型是計(jì)算機(jī)圖形學(xué)中一個(gè)十分重要的應(yīng)用領(lǐng)域,它是CAD/CAM和CIMS(計(jì)算機(jī)集成制造系統(tǒng))的核心技術(shù),也是用來(lái)實(shí)現(xiàn)計(jì)算機(jī)輔助設(shè)計(jì)的基本手段。幾何造型的功能:形體輸入,即把形體從用戶(hù)格式轉(zhuǎn)換成計(jì)算機(jī)內(nèi)部格式;圖形數(shù)據(jù)的存儲(chǔ)和管理;圖形控制,如對(duì)形體進(jìn)行平移、縮放、旋轉(zhuǎn)等幾何變換;圖形修改,如應(yīng)用集合運(yùn)算、歐拉運(yùn)算、有理B樣條操作及其交互手段實(shí)現(xiàn)對(duì)形體局部或整體修改;圖形分析,如形體的容差分析,物質(zhì)特性
3、分析等;圖形顯示輸出,如消隱、光照、顏色的控制等;查詢(xún)形體的屬性及其有關(guān)參數(shù),三維幾何造型分為兩個(gè)分支:三維曲面造型(surface modeling)和三維實(shí)體造型(solid Modeling);曲面造型技術(shù)研究在計(jì)算機(jī)內(nèi)如何描述一張曲面,如何對(duì)它的形狀進(jìn)行交互式的顯式和控制;實(shí)體造型技術(shù)著重研究如何在計(jì)算機(jī)內(nèi)定義、表示一個(gè)三維物體。實(shí)體造型技術(shù)是隨著CAD、CAM的需要而發(fā)展起來(lái)的,其核心內(nèi)容是三維物體的數(shù)學(xué)模型和計(jì)算機(jī)表
4、示方法;曲面造型和實(shí)體造型是相互支持、相互補(bǔ)充的,在發(fā)展上也是相互獨(dú)立,平行發(fā)展的。光有曲面造型,我們的目光就只能停留在組成物體的一張張表面上,無(wú)法分析物體的整體性質(zhì);反之,光有實(shí)體造型,我們將無(wú)法準(zhǔn)確描述和控制物體的外部形狀;曲面造形所涉及到的基礎(chǔ)內(nèi)容諸如自由曲線和曲面的表示已經(jīng)討論過(guò)。下面將介紹有關(guān)實(shí)體造型的基礎(chǔ)知識(shí)。,清華大學(xué)GEMS系統(tǒng)的數(shù)據(jù)結(jié)構(gòu),,,體組,特征表示,單體(零件),面組,面,線框,環(huán),環(huán)邊,邊,頂點(diǎn),曲 面
5、,曲 線,點(diǎn),,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,實(shí)體幾何數(shù)據(jù),實(shí)體拓?fù)鋽?shù)據(jù),,參數(shù)域曲線,,,Parasolid的模型結(jié)構(gòu),Parasolid是一個(gè)嚴(yán)格的邊界表示的實(shí)體建模內(nèi)核;Parasolid被設(shè)計(jì)用于機(jī)械CAD/CAM/CAE、建筑工程和結(jié)構(gòu)(AEC)、虛擬現(xiàn)實(shí)中;Parasolid可以被C等編程語(yǔ)言調(diào)用;Parasolid是由Unigraphics Solutions Inc 在
6、Cambridge, England開(kāi)發(fā)的, 用于它的Unigraphics和Solid Edge 產(chǎn)品中;,二、形體在計(jì)算機(jī)內(nèi)的表示,1、表示形體的坐標(biāo)系,2、幾何元素的定義,在計(jì)算機(jī)中,形體主要由幾何信息和拓?fù)湫畔⒍x,通常采用六層結(jié)構(gòu),如右所示:,形體-體體是三維幾何元素,由封閉表面圍成的空間, 其邊界是有限面的并集。定義:由封閉表面圍成的有效空間稱(chēng)為體;一個(gè)形體Q是R3空間中非空、有界的封閉子集。其邊界(記為?Q)
7、 是有限個(gè)面的并集,而外殼是形體的最大邊界。一個(gè)單位立方體可定義為:{(x,y,z)∈R3|0≤x≤1,0≤y≤1,0≤z≤1}其中一個(gè)表面可表示為:{(1,y,z)∈R3|0≤y≤1,0≤z≤1} 注意:這里沒(méi)有規(guī)定形體必須是一個(gè)連續(xù)的封閉集合,目的是用這樣的定義來(lái)擴(kuò)大幾何造型的域,使得形體可以由不連續(xù)的體素,或是僅由某些相交的形體組成。,為了保證幾何造型的可靠性和可加工性,要求形體上任何一點(diǎn)的足
8、夠小的領(lǐng)域在拓?fù)渖蠎?yīng)是一個(gè)等價(jià)的封閉圈,即圍繞該點(diǎn)的形體鄰域在二維空間中可構(gòu)成一個(gè)單連通域,我們把滿足這個(gè)定義的形體成為正則形體。,形體-面 面是二維幾何元素 ,是形體上一個(gè)有限、非空的區(qū)域,由一個(gè)外環(huán)和若干個(gè)內(nèi)環(huán)界定其范圍。一個(gè)面可以無(wú)內(nèi)環(huán),但必須有一個(gè)且只有一個(gè)外環(huán)。面有方向性,一般用其外法向量方向作為該面的正向。 面F的邊界(記為?F)是有限條線段的并集,P(F)表示含有F的唯一平面。,形體-環(huán) 由有序、有向邊組成的面的封閉
9、邊界稱(chēng)為環(huán),環(huán)中任意邊都不能自交,相鄰兩條邊共享一個(gè)端點(diǎn) 環(huán)又分為內(nèi)環(huán)和外環(huán)。內(nèi)環(huán)是在已知面中的內(nèi)孔或凸臺(tái)面邊界的環(huán),其邊按順時(shí)針?lè)较颉M猸h(huán)是已知面的最大外邊界的環(huán),其邊按逆時(shí)針?lè)较虬瓷鲜龇绞蕉x,在面上沿著邊的方向前進(jìn),面的內(nèi)部始終在走向的左側(cè)。,單環(huán)在R3中具有下列性質(zhì)的共面線段{e1,e2,…,en}的集合:兩條不同線段ei,ej的交,或是空集,或是一個(gè)點(diǎn),該點(diǎn)即為兩條線段的端點(diǎn);環(huán)中每個(gè)端點(diǎn)的度都是非負(fù)偶數(shù),即為偶數(shù)條線
10、段的交點(diǎn)。,假設(shè)F是一個(gè)面,其中包含有單環(huán){c0,c1,…,cn}(n≥0),且c0是外環(huán),則具有下列性質(zhì):F的邊界:?F=c0∪c1∪…∪cn;單環(huán)ci(0≤i≤n)均不相交; F是由在c0內(nèi)部的點(diǎn),在c1(i≥1)外部的點(diǎn)和∪ci(0≤i≤n)邊界上的點(diǎn)所組成。,形體-邊形體內(nèi)兩個(gè)相鄰面的交界稱(chēng)為邊,一條邊有且僅有兩個(gè)相鄰面。兩個(gè)端點(diǎn)確定一條邊,這兩個(gè)端點(diǎn)分別稱(chēng)為該邊的起點(diǎn)和終點(diǎn)。假設(shè)Q是一個(gè)形體,E(Q)是形
11、體邊的集合,則在?Q中E(Q)是滿足下列條件的所有線段的集合:邊e的兩個(gè)端點(diǎn)屬于V(Q)(形體頂點(diǎn)的集合);邊e中沒(méi)有一個(gè)內(nèi)部點(diǎn)屬于V(Q)邊e上每個(gè)點(diǎn),都有兩個(gè)不同的面,即存在兩個(gè)面fi,fj ∈ ?Q使得邊e∈fi∩fj;形體Q的邊框線WF(Q)是由有序?qū)?V(Q),E(Q))所組成。,形體-點(diǎn)邊的端點(diǎn)稱(chēng)為點(diǎn)點(diǎn)不能出現(xiàn)在邊的內(nèi)部,也不能孤立地位于物體內(nèi)、物體外或面內(nèi)頂點(diǎn)又是?F中兩條不共線的線段的交點(diǎn)。假設(shè)Q是一個(gè)形
12、體,V(Q)是所有頂點(diǎn)P的集合,P(f)是含面f的唯一平面,則存在3個(gè)面f1,f2,f3 ∈ ?Q,一點(diǎn)P∈V(Q),使得P=f1∩f2∩f3=P(f1)∩P(f2)∩P(f3),形體-體素、半空間體素 簡(jiǎn)單的連續(xù)封閉的形體,可以用有限個(gè)尺寸參數(shù)定位和定形體素,如長(zhǎng)方體、圓柱體、圓錐、球、環(huán)等;也可以用半空間定義;半空間集合{P|F(P)≤0}成為半空間,其中P為R3中的一點(diǎn),F(xiàn)為一個(gè)平面,當(dāng)F=0時(shí),表示一個(gè)平面,這
13、個(gè)平面的半空間可以由F(P)=ax+by+cz+d定義的平面加上在平面某一側(cè)的所有點(diǎn)組成。顯然一個(gè)長(zhǎng)方體可以看成是6個(gè)平面半空間的交;,,形體-幾何信息和拓?fù)湫畔缀涡畔ⅲ簬缀涡畔⒚枋鑫矬w的大小、尺寸、位置、形狀等;拓?fù)湫畔ⅲ好枋鰩缀卧刂g的連接關(guān)系,指物體上所有的頂點(diǎn)、棱邊、表面間的連接關(guān)系;拓?fù)湫畔⒑蛶缀涡畔⒎珠_(kāi)表示有下述優(yōu)點(diǎn);便于具體查詢(xún)物體中各元素,獲取它們的有關(guān)信息;容易提取物體的局部信息,方便的進(jìn)行物體的各種局
14、部操作;對(duì)于具有相同拓?fù)浣Y(jié)構(gòu)而只是大小、尺寸不同的一類(lèi)物體,可用統(tǒng)一的數(shù)據(jù)結(jié)構(gòu)加以表示;便于在數(shù)據(jù)結(jié)構(gòu)上附加各種非幾何信息,如物體某表面的光潔度等等;,形體-頂點(diǎn)、棱邊、表面之間的拓?fù)潢P(guān)系,,,,,,,,,,f,f,f,f,f,v,v,v,v,f,e,e,e,e,f,f,f,f,v,v,v,v,v,e,e,e,v,f,f,e,v,v,e,e,e,e,e,e,3、三維形體表示的三種模型:線框、表面、實(shí)體,1) 線框模型線框模型是最早
15、用來(lái)表示形體的模型,并且至今仍在廣泛地應(yīng)用。線框模型由頂點(diǎn)表示幾何位置,相鄰頂點(diǎn)連接構(gòu)成棱邊表示幾何形狀特征。下圖是一個(gè)長(zhǎng)方體的例子,8個(gè)頂點(diǎn)和12條棱邊表示出這一形體。,線框模型是表面模型和實(shí)體模型的基礎(chǔ)。它具有結(jié)構(gòu)簡(jiǎn)單、易于理解、數(shù)據(jù)量少的特點(diǎn),因此計(jì)算機(jī)處理速度快。,線框模型的局限性:,線框模型包含的信息有限,無(wú)法實(shí)現(xiàn)圖形的自動(dòng)消隱;同一數(shù)據(jù)結(jié)構(gòu)可能對(duì)應(yīng)多個(gè)圖形,產(chǎn)生不定性;線框數(shù)據(jù)結(jié)構(gòu)無(wú)法處理曲面物體的側(cè)影輪廓線;當(dāng)生
16、成復(fù)雜的圖形時(shí),處理的數(shù)據(jù)量過(guò)于龐大;,,,圖形的不定性,曲面物體的側(cè)影輪廓線,,,,,2)表面模型表面模型是用有向棱邊圍成的部分來(lái)定義形體表面,由面的集合來(lái)定義形體。表面模型是在線框模型的基礎(chǔ)上,通過(guò)增加由哪些棱邊按何種順序連接等內(nèi)容定義出表面,從而可以滿足面面求交、線面消隱、明暗處理、數(shù)控加工等應(yīng)用需要。表面模型通常用于構(gòu)造復(fù)雜的曲面形體。表面模型完整地定義了形體的邊界,但是形體的實(shí)心部分在邊界哪一側(cè)并不明確。,3) 實(shí)體模
17、型如果要處理完整的三維形體,最終必須使用實(shí)體模型,實(shí)體模型明確定義了表面的哪一側(cè)存在實(shí)體。以下是實(shí)體在表面某一側(cè)的4種定義方法:,1:除了定義一個(gè)表面外,還定義實(shí)體存在于表面一側(cè)的一點(diǎn)P;2:以法線指向定義實(shí)體存在的一側(cè);3:定義表面邊界線為有限邊界,并設(shè)右螺旋前進(jìn)的方向指向?qū)嶓w外側(cè);4:將形體分割成幾個(gè)區(qū)域,由于每一條邊界線兩側(cè)的箭頭方向相反,則表明表面一側(cè)存在實(shí)體。,實(shí)體模型在表面模型的基礎(chǔ)上,使用表面的外法線矢量方向來(lái)指明
18、實(shí)體存在的一側(cè),例如規(guī)定正向指向體外。通常用有向棱邊隱含地表示表面的外法線矢量方向。在定義表面時(shí),有向棱邊按右手法則取向,沿著閉合的棱邊所得的方向與表面外法線矢量方向一致。,下圖是在表面模型的基礎(chǔ)上增加定義了表面外環(huán)的棱邊方向。據(jù)此還可檢查形體的拓?fù)湟恢滦?,拓樸合法的形體在相鄰兩個(gè)面的公共邊界上,棱邊的方向正好相反。,4) 三種模型的數(shù)據(jù)結(jié)構(gòu)線框模型的數(shù)據(jù)結(jié)構(gòu):線框模型的數(shù)據(jù)信息是頂點(diǎn)和棱邊,其數(shù)據(jù)結(jié)構(gòu)一般使用兩組數(shù)據(jù),或稱(chēng)兩表結(jié)
19、構(gòu)。一張表表示頂點(diǎn),一張表表示棱邊。以下圖為例,假定長(zhǎng)方體的長(zhǎng)是2,寬是1,高是1,則數(shù)據(jù)組織如表1和表2所示。,,,表面模型的數(shù)據(jù)結(jié)構(gòu):表面模型是在線框模型的基礎(chǔ)上增加定義表面信息,所以其數(shù)據(jù)結(jié)構(gòu)也是在線框模型兩表結(jié)構(gòu)的基礎(chǔ)上增加面表,如表3所示。,實(shí)體模型是在表面模型的基礎(chǔ)上定義了表面的哪一側(cè)存在實(shí)體,即按右手法則取向安排組成表面的邊順序。表3中邊的順序已經(jīng)符合這一要求,也可以作為實(shí)體模型的面表。三個(gè)表中除了所列的基本幾何數(shù)據(jù)外,
20、還可以擴(kuò)充增加屬性信息。比如邊表和面表中可以包括顏色屬性,面表中還可包括透明度、紋理特征等。對(duì)上述三表還可以進(jìn)行數(shù)據(jù)的一致性和完整性檢驗(yàn),內(nèi)容諸如每個(gè)頂點(diǎn)至少是二條邊的端點(diǎn);每條邊至少是一個(gè)面的組成部分;每個(gè)面的邊界都是封閉的;每個(gè)面至少有一條同其它面的公共邊等。,二、常用的形體表示方法,前面介紹的形體表示的線框模型、表面模型和實(shí)體模型是一種廣義的概念,并不反映形體在計(jì)算機(jī)內(nèi)部、或?qū)ψ罱K用戶(hù)而言所用的具體的表示方式。從用戶(hù)的角度看,
21、形體表示以特征表示法和體素構(gòu)造表示法(CSG樹(shù))較為方便從計(jì)算機(jī)對(duì)形體的存儲(chǔ)管理和操作運(yùn)算角度看,以邊界表示法(BRep)最為實(shí)用為了適合某些特定的要求,還有一些輔助的形體表示方式,如單元分解表示法、掃描表示法和基于參數(shù)的實(shí)體造型法;,對(duì)于一個(gè)幾何造型系統(tǒng),一般根據(jù)應(yīng)用的要求,采用混合的造型表示方法:70年代初,美國(guó)Rochester大學(xué)推出了以CSG表示為基礎(chǔ)的PADL-1系統(tǒng);日本北海道大學(xué)推出了以Coons曲面為邊界的TIPS
22、系統(tǒng);美國(guó)MIT推出了以線框邊界為基礎(chǔ)的ADAM系統(tǒng);美國(guó)Stanford大學(xué)推出了以歐拉操作為基礎(chǔ)的Geomod系統(tǒng);英國(guó)劍橋大學(xué)推出了以邊界表示為基礎(chǔ)的Build-1系統(tǒng)。,1、體素構(gòu)造表示(CSG樹(shù)表示),1) 物體的正則集合運(yùn)算物體之間的并、交、差運(yùn)算是幾何造型系統(tǒng)中構(gòu)造物體的最基本的手段之一。在現(xiàn)實(shí)生活中,它們也并非陌生。在機(jī)械加工中,將兩個(gè)零件焊接在一起可以看作是物體的“求并”過(guò)程;在物體上鉆開(kāi)一個(gè)孔,實(shí)際上是從這個(gè)物
23、體上移去了相應(yīng)于孔的那部分材料。物體間的求交過(guò)程在動(dòng)態(tài)干涉問(wèn)題中經(jīng)常應(yīng)用到。,物體間的正則集合運(yùn)算,形體:可定義為一個(gè)具有邊界子集和內(nèi)部子集的封閉點(diǎn)集,因而執(zhí)行幾何運(yùn)算的結(jié)果也應(yīng)為具有邊界子集和內(nèi)部子集的封閉點(diǎn)集,且保持形狀的初始維數(shù)。按照常規(guī)的集合運(yùn)算,不能保持點(diǎn)集的正則性質(zhì),如:通常的兩個(gè)立方體的交集運(yùn)算可能產(chǎn)生的結(jié)構(gòu)有:,為了保持維數(shù)上的一致,引入正則集和正則集合運(yùn)算的概念。正則集: 是定義在三維空間中的有界,封閉,半解析的區(qū)域
24、。有界:集合的占有空間是有限的封閉:集合的邊界元素也屬于集合中的元素半解析:由有限個(gè)解析半空間經(jīng)集合運(yùn)算所得的集合。解析半空間定義為{(x,y,z)|F(x,y,z)≥0}由正則集合組成的形體稱(chēng)為正則形體,由非正則集合組成的形體稱(chēng)為非正則形體。判斷正則形體的方法:假設(shè)Q是三維空間R3中一幾何形體, 則Q={Qb,Qi},其中Qb為Q的邊界或表面,為Qi為Q的內(nèi)部, Qc為Q的外部. 若Q的邊界滿足下列性質(zhì),則稱(chēng)形體為正則形體:
25、Qb將Qi和Qc分割成兩個(gè)不連通的子空間;去掉Qb上的任意一點(diǎn),Qi和Qc變成為連通的空間;對(duì)于任意一點(diǎn)P∈Qb,如果在P處存在切平面, 則其法向量Np指向Qc子空間。,下列圖均不是正則體該圖表示一個(gè)邊界有 懸邊和懸面的集合。該圖表示一個(gè)非解析 半空間的集合該圖表示一個(gè)立方體中減去一個(gè)直徑與立方體邊長(zhǎng)相等的圓柱體其結(jié)果是一個(gè)非
26、正則集合。,根據(jù)正則集合的性質(zhì),將傳統(tǒng)的點(diǎn)集運(yùn)算進(jìn)行修改,得到點(diǎn)集的正則集合運(yùn)算如下所示:,A ∪* B = r ( A ∪ B) A ∩* B = r ( A ∩ B) A -* B = r ( A - B),,其中, ∪* ∩* -* 分別表示正則化的點(diǎn)集并、交、差運(yùn)算,而∪,∩, - 則表示傳統(tǒng)的點(diǎn)的集合運(yùn)算,r表示點(diǎn)集正則化算子;,
27、在許多情況下,一個(gè)復(fù)雜物體可以由一些比較簡(jiǎn)單、規(guī)則的物體經(jīng)過(guò)集合運(yùn)算而得到。因此,這個(gè)復(fù)雜的物體可描述為一棵樹(shù)。這棵樹(shù)的終端結(jié)點(diǎn)為基本體素(如立方體、圓柱、圓錐),而中間結(jié)點(diǎn)為正則集合的運(yùn)算結(jié)點(diǎn)。這棵樹(shù)叫做CSG (Constructive Solid Geometry)樹(shù);,,,,,U*,,,,,,_*,,,CSG樹(shù)造型過(guò)程示例,CSG樹(shù)結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu),左圖是CSG樹(shù)結(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)的一種組織方式。每一結(jié)點(diǎn)由操作碼、坐標(biāo)變換域、基本體素指
28、針、左子樹(shù)、右子樹(shù)等五個(gè)域組成。操作碼按照約定方式取值。當(dāng)操作碼為零時(shí)表示該結(jié)點(diǎn)為一基本體素結(jié)點(diǎn)。,,,,,,Op_Code 操作碼,transform坐標(biāo)變換,Left_subtree 左子樹(shù),right_subtree 右子樹(shù),primitive 基本體,從CSG樹(shù)結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)可以看出,CSG樹(shù)只定義了它所表示的物體的構(gòu)造方式,它既不存儲(chǔ)頂點(diǎn),棱邊,表面等邊界信息,也不顯式定義三維點(diǎn)集與所表示物體在空間的一一對(duì)應(yīng)
29、的關(guān)系。因此,用CSG樹(shù)表示又稱(chēng)為物體的隱式模型或算法模型;用CSG樹(shù)表示一個(gè)復(fù)雜形體十分簡(jiǎn)潔,同時(shí)提供了足夠的信息,支持對(duì)物體的一切幾何性質(zhì)的計(jì)算;,CSG樹(shù)表示的分治算法,CSG樹(shù)的表示方法最適合采用分治算法(divide-and-conquer);設(shè)F是關(guān)于一個(gè)CSG樹(shù)所定義物體的幾何性質(zhì)的函數(shù),則計(jì)算F的分治算法的大致輪廓如下: F(tree, data) = if (tree is a leaf)
30、 then PRIM-F(tree, data); else COMBINE(F(left-subtree, data), F(right-subtree,data),
31、 node(tree)); 其中,PRIM-F為計(jì)算基本體素的幾何性質(zhì)F的函數(shù),COMBINE為依 據(jù)CSG樹(shù)非終結(jié)點(diǎn)處所實(shí)施的集合運(yùn)算對(duì)左、右子樹(shù)的F進(jìn)行合成的函數(shù),算法的效率取決于合成函數(shù);,CSG樹(shù)光線投射算法,問(wèn)題的提出:由于CSG樹(shù)不顯示表示物體的邊界,因此無(wú)法直接顯示CSG樹(shù)表示的物體,而如果要通過(guò)求出CSG樹(shù)表示物體的精確邊
32、界進(jìn)行物體顯示,則代價(jià)太大,效率不高。對(duì)于這個(gè)問(wèn)題,光線投射算法提供了圓滿的解決方案。,左圖為光線投射示意圖,算法的核心思想是從視點(diǎn)出發(fā)向顯示屏幕的每一象素投射光線,求出光線與距離視點(diǎn)最近的可見(jiàn)表面的交點(diǎn)和交點(diǎn)處的表面法向量,然后根據(jù)光照模型計(jì)算出該點(diǎn)的色彩和亮度;,CSG樹(shù)表示法是三維物體的最有效的表示方法之一,它有以下幾個(gè)方面的優(yōu)點(diǎn);記錄了物體的構(gòu)造過(guò)程;表示的有效性由基本體素的有效性和集合運(yùn)算的正則性而自動(dòng)得到保證;表示十分
33、簡(jiǎn)潔;,CSG樹(shù)表示法并非適用于一切場(chǎng)合,在生成工程設(shè)計(jì)中常用的線畫(huà)圖形時(shí)效率較低,這時(shí),需要將物體的CSG樹(shù)表示轉(zhuǎn)換成為邊界表示,以便獲取邊界信息;,2 、邊界表示法,邊界表示模型是一種采用描述形體邊界的方法來(lái)描述的幾何表示模型。所謂邊界就是物體內(nèi)部點(diǎn)和外部點(diǎn)的分界面。顯然,定義了物體的邊界,該物體也就被唯一的定義了;邊界可以拆分成一些有界的“面”和“小片”,而每一個(gè)面都可以通過(guò)其邊界的邊和頂點(diǎn)來(lái)表示;,v1,四棱柱,面節(jié)點(diǎn),邊節(jié)點(diǎn),
34、頂點(diǎn)坐標(biāo),f1,f2,f3,….,e1,e2,e3,e4,….,v1,v2,v3,….,(x1,y1,z1),,,組合結(jié)構(gòu),坐標(biāo)信息,,,,,,,,,,,,,,,,,,,,….,邊界表示法示例,,,U,,,,,,邊界表示法中的數(shù)據(jù)存儲(chǔ)結(jié)構(gòu) — 翼邊結(jié)構(gòu),翼邊結(jié)構(gòu)是邊界表示法中典型的一種數(shù)據(jù)結(jié)構(gòu),是1972年由B.G. Baumgart作為多面體的表示模式最先提出來(lái)的。在頂點(diǎn)、棱邊、表面等組成物體的三要素當(dāng)中,翼邊結(jié)構(gòu)以邊為中心來(lái)組織
35、數(shù)據(jù);,P2,P1,Loop 左,Loop 右,elcc,elcw,ercw,ercc,e,翼邊結(jié)構(gòu)如左圖,棱邊e的數(shù)據(jù)結(jié)構(gòu)中包含兩個(gè)指針,指向頂點(diǎn)P1和P2(P1為起點(diǎn),P2為終點(diǎn));同時(shí),e中還設(shè)置兩個(gè)環(huán)指針,分別指向棱邊e所鄰接的兩表面上的環(huán)Loop左和Loop右。這樣就確定了棱邊和相鄰表面之間的拓?fù)潢P(guān)系。同時(shí),為了能從棱邊e出發(fā)找到任一閉合環(huán)上的其它棱邊,在e中增設(shè)了四個(gè)指針Ercc,Ercw,Elcw,Elcc ;,邊e的翼邊
36、數(shù)據(jù)結(jié)構(gòu)如下所示:,(1) 邊界表示中的歐拉運(yùn)算,歐拉運(yùn)算是三維物體邊界表示數(shù)據(jù)結(jié)構(gòu)的生成操作,運(yùn)用歐拉運(yùn)算,可以正確、有效的構(gòu)建三維物體邊界表示中的所有拓?fù)湓睾屯負(fù)潢P(guān)系;,歐拉公式: V-E+F=2(V為頂點(diǎn)數(shù),E為棱線數(shù),F(xiàn)為面數(shù));凡是滿足歐拉公式的形體均稱(chēng)為歐拉形體;,,擴(kuò)展的歐拉公式,擴(kuò)展的歐拉公式:V-E+F-H=2(B-P) 其中,H為物體表面邊界的內(nèi)環(huán)數(shù);B為不相連接的物體個(gè)數(shù);P為
37、物體上的通孔數(shù)目;,V=16,E=24,F=11,H=1,B=1,P=0,V=16,E=24,F=10,H=2,B=1,P=1,,,,歐拉運(yùn)算,滿足歐拉公式的歐拉運(yùn)算多種多樣,但存在著5個(gè)基本的歐拉運(yùn)算,它們能夠有效的構(gòu)造出任意物體的拓?fù)浣Y(jié)構(gòu);Mvsf(v,f): 輸入一初始點(diǎn)v作為構(gòu)造物體的開(kāi)始;Mev(v1,v2,e):輸入一點(diǎn)v2,并構(gòu)造一條連接v1,v2的新邊e;Mef(v1,v2,e,f1,f2):構(gòu)造一條連接v1,
38、v2的新邊e,同時(shí)構(gòu)造一張新面f2,f2和f1通過(guò)e鄰接;Kemr(v1,v2,e):刪除v1,v2之間的橋邊e,同時(shí)構(gòu)造一個(gè)新的內(nèi)環(huán);Kfmrh(f1,f2):將表面f1的內(nèi)環(huán)面f2刪除,同時(shí)構(gòu)造f1的一個(gè)新內(nèi)環(huán),生成物體的一個(gè)通孔;,歐拉運(yùn)算一般不作為直接面向用戶(hù)的高級(jí)操作,而是放在系統(tǒng)的低層為集合操作、Sweep操作、局部操作等高級(jí)操作服務(wù),作為生成邊界表示數(shù)據(jù)結(jié)構(gòu)的工具;,(2)邊界表示中的Sweep運(yùn)算,Sweep運(yùn)算將一
39、個(gè)二維的平面區(qū)域轉(zhuǎn)化為三維立體。常用的Sweep運(yùn)算有平移式、旋轉(zhuǎn)式和廣義式三種。,,平移式Sweep,旋轉(zhuǎn)式Sweep,(3) 邊界表示中的集合運(yùn)算,當(dāng)物體采用邊界表示法時(shí),它們之間的集合運(yùn)算可分為以下四個(gè)步驟:采用包圍盒技術(shù),檢查兩物體是否相交;計(jì)算兩物體各表面之間的交線,該步驟是整個(gè)集合運(yùn)算的核心,直接影響到集合運(yùn)算的效率和速度;對(duì)兩物體表面進(jìn)行判定分類(lèi):兩物體之間的交線將它們的表面分割成兩部分,其中一部分落在拼合體的表面上
40、,形成新的邊界,另一部分落在拼合體內(nèi)或拼合體外,則在集合運(yùn)算的最后給予刪除;在集合運(yùn)算的過(guò)程中,不斷的建立新的拼合體的數(shù)據(jù)結(jié)構(gòu);,3 、單位分解表示法,集合運(yùn)算是十分有效的造型手段,但在邊界表示法中,物體各個(gè)面之間的巨大的求交運(yùn)算量影響了集合運(yùn)算的效率和可靠性;解決問(wèn)題的兩個(gè)途徑:改進(jìn)已有的邊界表示法中的集合運(yùn)算算法( 特別是其中的求交算法);探索物體在計(jì)算機(jī)內(nèi)的新的表示模式;單位分解表示法便是這種新的探索的結(jié)果;,單位分解表示
41、法 — 八叉樹(shù)表示,物體的單元分解表示法是一種層次數(shù)據(jù)結(jié)構(gòu),首先在空間中定義一個(gè)能夠包含所表示物體的立方體。立方體的棱和坐標(biāo)軸平行。若立方體內(nèi)的空間完全由所表示的物體占據(jù),則物體可用這個(gè)立方體予以表示,否則,將立方體等分成八個(gè)小塊,每塊仍為一個(gè)小立方體。若某一小立方體的體內(nèi)空間完全被所表示的物體占據(jù),則將此立方體標(biāo)志為“FULL”,若它與所表示的物體無(wú)交,則該立方體被標(biāo)記為“EMPTY”,否則將它標(biāo)志為“PARTIAL”,并繼續(xù)分
42、割下去,依此方式,物體在計(jì)算機(jī)內(nèi)可表示成為一棵八叉樹(shù),凡是標(biāo)記為“FULL”和“EMPTY”的立方體均為終端結(jié)點(diǎn),而標(biāo)記為“PARTIAL”的立方體為非終端結(jié)點(diǎn)。最后,當(dāng)分割生成的小立方體為單位長(zhǎng)時(shí),分割即告終止。,,三維物體的八叉樹(shù)表示,,,,,,,,2,3,6,7,2,0,1,3,1,3,7,5,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,具有子孫的節(jié)點(diǎn),空節(jié)點(diǎn),實(shí)節(jié)點(diǎn),
43、八叉樹(shù)表示法的性能分析,物體之間的集合運(yùn)算在八叉樹(shù)表示中具有十分簡(jiǎn)單的形式,可轉(zhuǎn)換為對(duì)參加集合運(yùn)算的兩物體的相應(yīng)八叉樹(shù)的遍歷問(wèn)題;八叉數(shù)的數(shù)據(jù)結(jié)構(gòu)大大簡(jiǎn)化了隱藏線和隱藏面的消除問(wèn)題;在八叉樹(shù)表示中,物體上的各元素已按空間位置排列成一定的順序,降低了消隱過(guò)程中排序的時(shí)間復(fù)雜度;物體的整體性能的計(jì)算(體積、質(zhì)量等)更為簡(jiǎn)單;采用八叉樹(shù)表示物體的最大缺點(diǎn)是占用過(guò)多的存儲(chǔ)空間。線性八叉樹(shù)方法是對(duì)傳統(tǒng)的八叉樹(shù)方法的改進(jìn),可降低對(duì)存儲(chǔ)的要求;
44、,4 、 ACIS三維造型系統(tǒng),ACIS是由美國(guó)Spatial Technology于1990年首次推出。ACIS的重要特點(diǎn)是支持線框、曲面、實(shí)體統(tǒng)一表示的非正則形體造型技術(shù),能夠處理非流形形體。ACIS產(chǎn)品采用了組件技術(shù),其核心是幾何造型器(Geometric Modeler),還包括一些可與核心集成的組件,稱(chēng)為外殼(Husk)。,ACIS的結(jié)構(gòu),ACIS的結(jié)構(gòu),核心只提供一些基本的幾何造型功能,其它高級(jí)功能在外殼中提供。外殼
45、可以是Spatial Technology公司提供的,如高級(jí)渲染(Advanced Rendering)外殼、三維工具箱(3D Toolkit)外殼等,也可以是用戶(hù)開(kāi)發(fā)的。,ACIS的模型表示,ACIS模型表示由各種屬性(Attributes)、幾何(Geometries)和拓?fù)洌═opologies)成。幾何是指模型的物理描述,如點(diǎn)、曲線、曲面、直線、橢圓等;拓?fù)涫侵父鞣N幾何實(shí)體在空間的關(guān)聯(lián),如體、殼、面、環(huán)、邊和頂點(diǎn)等;屬性依
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶(hù)所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 眾賞文庫(kù)僅提供信息存儲(chǔ)空間,僅對(duì)用戶(hù)上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶(hù)上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶(hù)因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 油畫(huà)幾何化造型語(yǔ)言芻議
- 語(yǔ)音輔助幾何造型系統(tǒng)的研究.pdf
- 造型系統(tǒng)中的幾何約束求解.pdf
- 曲面造型中幾何逼近與幾何插值的算法研究.pdf
- 基于NURBS的風(fēng)機(jī)葉片的幾何造型.pdf
- 幾何分割方式在動(dòng)畫(huà)造型中的應(yīng)用
- 動(dòng)物角色造型的幾何形態(tài)表現(xiàn)研究.pdf
- 基于點(diǎn)元的幾何造型與繪制.pdf
- 油畫(huà)幾何化造型語(yǔ)言芻議_21042.pdf
- 廣義Ball曲線曲面的幾何造型研究.pdf
- 區(qū)間算法在幾何造型中的應(yīng)用.pdf
- 卡通角色造型中的幾何元素研究.pdf
- 幾何學(xué)與產(chǎn)品造型設(shè)計(jì)研究.pdf
- 離散細(xì)分方法在幾何造型中的應(yīng)用.pdf
- 基于點(diǎn)表示幾何體的造型技術(shù).pdf
- 基于曲線曲面上的幾何造型方法研究.pdf
- Toric曲面幾何造型與半代數(shù)樣條研究.pdf
- 曲線曲面的幾何約束造型與近似合并.pdf
- 帶多幾何參數(shù)的細(xì)分造型方法研究.pdf
- 數(shù)字幾何造型中的若干問(wèn)題研究.pdf
評(píng)論
0/150
提交評(píng)論