三維對象的表示

三維對象的表示第1頁，共47頁，2023年，2月20日，星期日實體造型（SolidModeling）幾何造型技術第一代：手工繪制工程圖第二代：二維計算機繪圖第三代：三維線架系統(tǒng)第四代：曲面造型第五代：實體造型第2頁，共47頁，2023年，2月20日，星期日實體造型系統(tǒng)的發(fā)展（1/3）60年代初期70年代初期英國劍橋大學的BUILD-1系統(tǒng)德國柏林工業(yè)大學的COMPAC系統(tǒng)日本北海道大學的TIPS-1系統(tǒng)美國羅切斯特大學的PADL-1、PADL-2系統(tǒng)等5年后推出BUILD-2系統(tǒng)第3頁，共47頁，2023年，2月20日，星期日實體造型系統(tǒng)的發(fā)展（2/3）早期系統(tǒng)的特點：用多面體表示形體，不支持精確的曲面表示1978年，英國ShapeData公司，ROMULUS系統(tǒng)，首次引入精確的二次曲面方法用于精確表示幾何形體1980年，Evans&Sutherland開始將ROMULUS投放市場80年代末，NURBS曲線曲面設計方法，不僅能對已有的曲線曲面（如Bezier方法、B樣條方法等）進行統(tǒng)一表示，還能精確表示二次曲線曲面。第4頁，共47頁，2023年，2月20日，星期日實體造型系統(tǒng)的發(fā)展（3/3）國際標準化組織將NURBS作為定義工業(yè)產品形狀的唯一數(shù)學方法。最有代表性的兩個幾何造型系統(tǒng)Parasolid：1985年，ShapeData公司ACIS：1990年，美國SpatialTechnology公司目前，許多流行的商用CAD/CAM軟件，如Unigraphics、Solidedge、Solidwork、MDT等，都在Parasolid或ACIS基礎上開發(fā)。第5頁，共47頁，2023年，2月20日，星期日三維實體的表示（1/7）模型分類第6頁，共47頁，2023年，2月20日，星期日三維實體的表示（2/7）數(shù)據(jù)模型完全以數(shù)據(jù)描述以數(shù)據(jù)文件的形式存在包括----邊界表示、分解表示、構造表示等第7頁，共47頁，2023年，2月20日，星期日線框模型表面模型實體模型三維實體的表示（3/7）----物體的骨架----物體的皮膚----”有血有肉”的物體模型第8頁，共47頁，2023年，2月20日，星期日形體表示成一組輪廓線的集合，只需建立三維線段表數(shù)據(jù)結構簡單、處理速度快所構成的圖形含義不確切，與形體之間不存在一一對應關系，有二義性不便進行光照或消隱處理，不適合真實感顯示和數(shù)控加工線框模型三維實體的表示（4/7）----物體的骨架用線框模型表示的有二義性的物體第9頁，共47頁，2023年，2月20日，星期日表面模型三維實體的表示（5/7）----物體的皮膚將形體表示成一組表面的集合，形體與其表面一一對應，避免了二義性能夠滿足真實感顯示和數(shù)控加工等需求

只有面的信息，形體信息不完整無法計算和分析物體的整體性質（如體積、重心等），限制了在工程分析方面的應用第10頁，共47頁，2023年，2月20日，星期日實體模型三維實體的表示（6/7）----”有血有肉”的物體模型用來描述實體，主要用于CAD/CAM包含了描述一個實體所需的較多信息，如幾何信息、拓撲信息表示完整而無歧義

第11頁，共47頁，2023年，2月20日，星期日過程模型三維實體的表示（7/7）包括----隨機插值模型、迭代函數(shù)系統(tǒng)、L系統(tǒng)、粒子系統(tǒng)、復變函數(shù)迭代等以一個過程和相應的控制參數(shù)描述以一個數(shù)據(jù)文件和一段代碼的形式存在第12頁，共47頁，2023年，2月20日，星期日數(shù)據(jù)模型——邊界表示（1/12）BoundaryRepresentation，也稱BR表示或BRep表示最成熟、無二義性物體的邊界與物體一一對應實體的邊界是表面的并集表面的邊界是邊的并集第13頁，共47頁，2023年，2月20日，星期日數(shù)據(jù)模型——邊界表示（2/12）用于表示物體邊界的有平面多邊形曲面片平面多面體表面由平面多邊形組成的多面體曲面體由曲面片組成的物體第14頁，共47頁，2023年，2月20日，星期日描述形體的信息：GeometryTopology數(shù)據(jù)模型——邊界表示（3/12）描述形體的幾何元素（頂點、邊、面）之間的連接關系，形成物體邊界表示的“骨架”描述形體的幾何元素性質和度量關系，如位置、大小、方向、尺寸、形狀等信息猶如附著在“骨架”上的肌肉第15頁，共47頁，2023年，2月20日，星期日表示形體的基本幾何元素：頂點（Vertex）邊（Edge）面（Face）環(huán)（Loop）體（Body）數(shù)據(jù)模型——邊界表示（4/12）第16頁，共47頁，2023年，2月20日，星期日數(shù)據(jù)模型——邊界表示（5/12）正則形體與非正則形體：要保證幾何造型的可靠性和可加工性，形體上任意一點的足夠小的鄰域在拓撲上必須是一個等價的封閉圓，即該點的鄰域在二維空間中是一個單連通域點至少和三個面（或三條邊）鄰接，不允許存在孤立點邊只有兩個鄰面，不允許存在懸邊面是形體表面的一部分，不允許存在懸面P有懸面有懸邊一條邊有兩個以上的鄰面點P的鄰域非單連通第17頁，共47頁，2023年，2月20日，星期日幾何元素正則形體非正則形體

面

是形體表面的一部分可以是形體表面的一部分，也可以是形體內的一部分，也可以與形體相分離。

邊

只有兩個鄰面可以有多個鄰面、一個鄰面或沒有鄰面。

點

至少和三個面（或三條邊）鄰接可以與多個面（或邊）鄰接，也可以是聚集體、聚集面、聚集邊或孤立點。數(shù)據(jù)模型——邊界表示（6/12）第18頁，共47頁，2023年，2月20日，星期日數(shù)據(jù)模型——邊界表示（7/12）歐拉特征設表面s由一個平面模型給出，且v,e,f分別表示其頂點、邊和小面的個數(shù)，那么v-e+f是一個常數(shù)，它與s劃分形成平面模型的方式無關。該常數(shù)稱為Euler特征。v=8,e=13,f=7v-e+f=2歐拉公式第19頁，共47頁，2023年，2月20日，星期日歐拉物體滿足歐拉公式的物體歐拉運算增加或者刪除面、邊和頂點以生成新的歐拉物體的過程數(shù)據(jù)模型——邊界表示（8/12）第20頁，共47頁，2023年，2月20日，星期日歐拉運算時，必須要保證歐拉公式和下述條件成立，才能夠保證形體的拓撲有效性。面單連通，沒有孔，且被單條邊環(huán)圍?。粚嶓w的補集是單連通，沒有洞穿過它；邊完全與兩個面鄰接，且每端以一個頂點結束；頂點至少是三條邊的匯合點。數(shù)據(jù)模型——邊界表示（9/12）(c)v=9,e=16,f=951234正則形體形體的歐拉運算(a)v=8,e=12,f=6(b)v=9,e=14,f=71251234增加一條邊：v=8,e=13,f=7第21頁，共47頁，2023年，2月20日，星期日數(shù)據(jù)模型——邊界表示(10/12)廣義歐拉公式v-e+f-r=2(s-h)r:多面體表面上內孔數(shù)s:相互分離的多面體數(shù)h:貫穿多面體的孔洞數(shù)v=16,e=32,f=16r=0,s=1,h=1v=24,e=36,f=15r=3,s=1,h=1第22頁，共47頁，2023年，2月20日，星期日數(shù)據(jù)模型——邊界表示(11/12)在邊界表示的數(shù)據(jù)結構中，比較著名的有：半邊數(shù)據(jù)結構輻射邊數(shù)據(jù)結構翼邊數(shù)據(jù)結構1972年由美國斯坦福大學B.G.Baumgart等人提出是以邊為核心來組織數(shù)據(jù)的一種數(shù)據(jù)結構翼邊數(shù)據(jù)結構左上邊右上邊左下邊右下邊左外環(huán)右外環(huán)e

P2

P1第23頁，共47頁，2023年，2月20日，星期日數(shù)據(jù)模型——邊界表示(12/12)缺點數(shù)據(jù)結構及其維護數(shù)據(jù)結構的程序復雜需大量的存儲空間有效性難以保證優(yōu)點精確表示物體表示覆蓋域大，表示能力強容易確定幾何元素間的連接關系，幾何變換容易顯式表示點、邊、面等幾何元素，繪制速度快第24頁，共47頁，2023年，2月20日，星期日數(shù)據(jù)模型——分解表示（1/8）空間位置枚舉表示選擇一個立方體空間，將其均勻劃分用三維數(shù)組C[I][J][K]表示物體，數(shù)組中的元素與單位小立方體一一對應第25頁，共47頁，2023年，2月20日，星期日數(shù)據(jù)模型——分解表示（2/8）優(yōu)點可以表示任何物體容易實現(xiàn)物體間的集合運算容易計算物體的整體性質，如體積等缺點是物體的非精確表示占用大量的存儲空間，如1024*1024*1024=1Gbits沒有邊界信息，不適于圖形顯示對物體進行幾何變換困難，如非90度的旋轉變換第26頁，共47頁，2023年，2月20日，星期日數(shù)據(jù)模型——分解表示（3/8）八叉樹（octrees）表示自適應分割第27頁，共47頁，2023年，2月20日，星期日數(shù)據(jù)模型——分解表示（4/8）(a)(b)zyx55554777FPEEEEEEEEEFEFFEP1023456012345677八叉樹建立過程八叉樹的根節(jié)點對應整個物體空間如果它完全被物體占據(jù)，將該節(jié)點標記為F(Full)，算法結束；如果它內部沒有物體，將該節(jié)點標記為E(Empty)，算法結束；如果它被物體部分占據(jù)，將該節(jié)點標記為P(Partial)，并將它分割成8個子立方體，對每一個子立方體進行同樣的處理第28頁，共47頁，2023年，2月20日，星期日數(shù)據(jù)模型——分解表示（5/8）優(yōu)點可以表示任何物體,數(shù)據(jù)結構簡單容易實現(xiàn)物體間的集合運算容易計算物體的整體性質，如體積等較空間位置枚舉表示占用的存貯空間少缺點是物體的非精確表示沒有邊界信息，不適于圖形顯示對物體進行幾何變換困難第29頁，共47頁，2023年，2月20日，星期日數(shù)據(jù)模型——分解表示（6/8）單元分解（celldecomposition）表示多種體素(a)棱錐體素(b)長方體體素(c)圖(a)和(b)兩種體素的并集第30頁，共47頁，2023年，2月20日，星期日數(shù)據(jù)模型——分解表示（7/8）三種空間分割方法的比較空間位置枚舉表示----同樣大小立方體八叉樹表示----不同大小的立方體單元分解表示----多種體素第31頁，共47頁，2023年，2月20日，星期日數(shù)據(jù)模型——分解表示（8/8）優(yōu)點表示簡單容易實現(xiàn)幾何變換基本體素可以按需選擇，表示范圍較廣可以精確表示物體缺點物體的表示不唯一物體的有效性難以保證第32頁，共47頁，2023年，2月20日，星期日數(shù)據(jù)模型——構造實體幾何表示（1/5）構造實體幾何表示constructivesolidgemetry，簡稱CSG采用單一的“建筑塊”形式的實體造型方法，由兩個物體的正則集合操作生成新的物體并（union）交（intersection）差（difference）第33頁，共47頁，2023年，2月20日，星期日數(shù)據(jù)模型——構造實體幾何表示（2/5）普通的集合運算會產生懸邊、懸面等低于三維的形體

正則集合運算保證集合運算的結果仍是一個正則形體即丟棄懸邊、懸面等

ABAB普通集合的交正則集合的交C懸邊C第34頁，共47頁，2023年，2月20日，星期日數(shù)據(jù)模型——構造實體幾何表示（3/5）將物體表示成一棵二叉樹，稱為CSG樹葉節(jié)點----基本體素，如立方體、圓柱體、圓環(huán)、錐體、球體等中間節(jié)點----并、交、差正則集合運算U*U*—*—*第35頁，共47頁，2023年，2月20日，星期日數(shù)據(jù)模型——構造實體幾何表示（4/5)優(yōu)點表示簡單、直觀，無二義性數(shù)據(jù)量比較小，內部數(shù)據(jù)的管理比較容易形體形狀容易被修改可用作圖形輸入的一種手段容易計算物體的整體性質物體的有效性自動得到保證缺點表示物體的CSG樹不唯一受體素種類和對體素操作種類的限制，CSG方法表示形體的覆蓋域有較大的局限性形體的邊界幾何元素（點、邊、面）隱含地表示在CSG中，因此，顯示與繪制CSG表示的形體需要較長的時間求交計算麻煩第36頁，共47頁，2023年，2月20日，星期日數(shù)據(jù)模型——構造實體幾何表示（5/5）基于正則形體表示的實體造型形體只能表示正則的三維“體”不能表示線架模型中的“線”，表面模型中的“面”但在實際應用中，有時候人們希望在系統(tǒng)中也能處理低于三維的形體于是，產生了非正則造型技術。

要求造型系統(tǒng)的數(shù)據(jù)結構能統(tǒng)一表示線架、表面、實體模型。第37頁，共47頁，2023年，2月20日，星期日數(shù)據(jù)模型——掃描表示(1/6)sweeprepresentations基于一個基體（一般為封閉的二維區(qū)域）沿某一路徑運動而產生形體sweep體

兩個分量被運動的基體基體運動的路徑如果是變截面的掃描，還要給出截面變化規(guī)律

第38頁，共47頁，2023年，2月20日，星期日數(shù)據(jù)模型——掃描表示(2/6)根據(jù)掃描路徑和方式的不同，可將sweep體分為以下幾種類型：平移sweep體

旋轉sweep體

廣義sweep體

第39頁，共47頁，2023年，2月20日，星期日數(shù)據(jù)模型——掃描表示(3/6)平移sweep將一個二維區(qū)域沿著一個矢量方向（線性路徑）推移，拉伸曲面第40頁，共47頁，2023年，2月20日，星期日數(shù)據(jù)模型——掃描表示(4/6)旋轉sweep將一個二維區(qū)域繞旋轉軸旋轉一特定角度（如一周），旋轉曲面旋轉軸旋轉軸旋轉軸第41頁，共47頁，2023年，2月20日，星期日數(shù)據(jù)模型——掃描表示(5/6)廣義sweep任意剖面沿著任意軌跡掃描指定的距離

，掃描路徑可以用曲線函數(shù)來描述可以沿掃描路徑變化剖面的形狀和大小或者當移動該形狀通過某空間時變化剖面相對于掃描路徑的方向也稱掃描曲面

掃描體的掃描路徑為曲線時得到的廣義sweep體基面基面(a)等截面掃描(b)變截面掃描第42頁，共47頁，2023年，2月20日，星期日數(shù)據(jù)模型——掃描表示(6/6)