幾何變換集合運算構(gòu)建客觀存在或想象中的形體模型是課件

1、幾何造型就是通過點、線、面和立體等幾何元素的定義、幾何變換、集合運算構(gòu)建客觀存在或想象中的形體模型，是確定形體形狀和其它幾何特征方法的總稱。 第三章 幾何造型2022/8/91提出問題如何在計算機中建立恰當（完整、精確、快速）的幾何造型的模型表示不同圖形對象？如何組織圖形對象的描述數(shù)據(jù)以使存儲這些數(shù)據(jù)所要的空間最省，檢索、處理這些數(shù)據(jù)的速度較快？2022/8/92本章內(nèi)容提要 計算機內(nèi)基本幾何元素和形體的定義 形體的表示模型和數(shù)據(jù)結(jié)構(gòu) 三維形體常用的幾何造型方法 幾何造型的實例 2022/8/93第一節(jié) 形體的計算機表示、表示形體的坐標系2022/8/94 一般采用右手三維笛卡兒坐標系 一般與

2、用戶定義形體和圖素的坐標系一致 用于定義用戶整圖或最高層圖形結(jié)構(gòu) 用戶坐標系分為以下五種:直角坐標系也稱為（笛卡兒坐標系），仿射坐標系，圓柱坐標系，球坐標系，極坐標系。1.用戶坐標系（WCS：World Coordinate System，也稱世界坐標系）2022/8/95 右手三維直角坐標系，用來定義基本形體或圖素 每一個形體和圖素都有各自的坐標原點和長度單位 3.觀察坐標系(VCS：Viewing Coordinate System) 可看作是局部坐標系（Local Coordinates） 左手三維直角坐標系，用來產(chǎn)生形體、圖形的視圖 用于指定裁剪空間 把三維形體的用戶坐標變換成規(guī)格化的

3、設(shè)備坐標 2.造型坐標系(MCS：Modeling Coordinate System)2022/8/965.設(shè)備坐標系（DCS：Device Coordinate System） 使圖形處理過程做到與設(shè)備無關(guān) 設(shè)備坐標規(guī)定為0X1，0Y1 左手三維直角坐標系，用來定義視圖區(qū) 可提高應用程序的可移值性 設(shè)備坐標系是與圖形設(shè)備相關(guān)聯(lián)的坐標系 采用左手三維直角坐標系 通常也是定義象素(Pixel)或位圖(bitmap)的坐標系 4.規(guī)格化的設(shè)備坐標系（NDCS：Normalized Device Coordinate System）2022/8/97各類坐標系之間的關(guān)系 2022/8/98點是0維

4、幾何元素，分端點、交點、切點和孤立點等。在自由曲線面的描述中常用三種類型的點：控制點、型值點、插值點 邊是1維幾何元素，是兩個鄰面（正則形體）或多個鄰面（非正則形體）的交界。直線邊、曲線邊二、基本幾何元素2022/8/99環(huán)是有序、有向邊（真線段或曲線段）組成的面的封閉邊界。環(huán)中的邊不能相交，相鄰兩條邊共享一個端點確定面的最大外邊界的環(huán)稱之為外環(huán)確定面中內(nèi)孔或凸臺邊界的環(huán)稱之為內(nèi)環(huán)在面上沿一個環(huán)前進，其左側(cè)總是面內(nèi)，右側(cè)總是面外。2022/8/910是2維幾何元素，是形體上一個有限、非零的區(qū)域，由一個外環(huán)和若干個內(nèi)環(huán)界定其范圍。 一個面可以無內(nèi)環(huán)，但必須有一個且只有一個外環(huán) 面有方向性面常用的

5、面包括平面、二次面、雙三次參數(shù)曲面等。 2022/8/911體 素是3維幾何元素，由封閉表面圍成空間，也是歐氏空間R3中非空、有界的封閉子集，其邊界是有限面的并集。體素有三種定義形式 單元實體，參數(shù)定義，代數(shù)半空間定義 殼（shell），也稱外殼，是一些點、邊、環(huán)、面的集合。 2022/8/912形體的層次結(jié)構(gòu)2022/8/913三、形體的分類與定義按所構(gòu)造的對象來劃分，可分為規(guī)則形體和不規(guī)則形體。 規(guī)則形體是指可以用歐氏幾何進行描述的三維物體，如點、直線、曲線、平面、曲面或三維立體等及它們的規(guī)則組合。規(guī)則形體的造型是本章描述的重點。1.形體的分類2022/8/914不規(guī)則形體是指不能用歐氏幾

6、何進行描述的物體，如山、樹、草、云、火、波浪等自然界的復雜物體。 不規(guī)則形體大多采用過程式模擬，即用一個簡單模型和少量易于調(diào)節(jié)的參數(shù)來表示一大類形體，不斷改變參數(shù)，遞歸調(diào)用這一模型就能產(chǎn)生數(shù)量很大的形體，這一技術(shù)也稱為數(shù)據(jù)放大技術(shù) 。基于分維數(shù)理論的隨機插值模型、基于文法的模型、粒子系統(tǒng)模型。不規(guī)則形體造型方法主要有：2022/8/9152. 形體的邊界所有實際形體都可看作是由封閉表面圍成的空間，其邊界是有限面的并集，而殼是形體的最大邊界。對于任何區(qū)域都可以用完全在區(qū)域之中（i）和在其邊界上（b）的全部點來定義，表示區(qū)域的點集可以表示成ib。 2022/8/9163. 形體的定義 對于形體表面

7、上任意一點，如果圍繞該點的形體鄰域在二維空間中可以構(gòu)成一個單連通域，且它與封閉圓之間存在著連續(xù)的一一對應關(guān)系，那么我們稱形體表面具有的這種性質(zhì)為二維流形，把表面具有二維流形性質(zhì)的形體稱為正則形體。 (a) 二維流形 (b) 二維流形 (c) 非二維流形 (d) 非二維流形2022/8/9174. 形體的表示模型 在計算機中，形體常用線框模型、表面模型、實體模型來表示。 線框模型應用最早，也是最簡單的一種形體表示方法； 采用三維空間的線段表達三維形體的棱邊。 優(yōu)點：采用線框模型描述形體所需信息最少，數(shù)據(jù)運算簡單，所占的存貯空間也比較?。粚τ布囊笠膊桓?，容易掌握，處理時間較短。2022/8/9

8、18 四棱柱、四棱錐和圓柱的線框模型 局限性：信息表達不完整、不易表達曲面體。 2022/8/919 表面模型是在線框模型的基礎(chǔ)上，增加有關(guān)面、邊信息以及表面特征、棱邊連接方向等內(nèi)容逐步形成的。 早期的Coons、Ferguson、Bezier等方法 80年代后期，非均勻有理B樣條（NURBS）方法用于曲線曲面的描述 表面模型采用有向棱邊圍成的部分來定義形體表面，由面的集合來定義形體。 優(yōu)點：具有很好的顯示特性能夠以消隱、小平面著色、平滑明暗、顏色和紋理等方式顯示形體。 2022/8/920四棱柱和圓柱的表面模型 (a) 模型消隱后的效果 (b) 模型著色后的效果局限性：不能切開形體而展示其內(nèi)

9、部結(jié)構(gòu)；物體的實心部分在邊界的哪一側(cè)是不明確的，使設(shè)計者對物體缺乏整體的概念等等。 2022/8/921 實體模型 在表面模型的基礎(chǔ)上定義了表面的哪側(cè)存在形體，一般采用三種方法來定義： (1)在定義表面時，給出形體存在側(cè)的一點P;(2)直接用表面的外法矢來指明形體存在的一側(cè);(3)采用有向棱邊隱含地表示表面的外法矢方向，有向棱邊按右手法則取向，沿閉合的棱邊所得的方向與表面的外法矢方向一致;2022/8/922 (a)給出一點 (b)采用表面外法矢 (c)采用有向棱邊 (d)形體拓撲檢驗圖無法準確地描述和控制形體的外部形狀；只能產(chǎn)生正則形體；不能描述具有工程語義的實際形體如具有實際工程意義的加工

10、孔、槽等；不能為其后續(xù)系統(tǒng)（CAM/CAPP等）提供非幾何信息如材料、公差等。實體模型的局限性2022/8/923實用的幾何造型系統(tǒng)中，常常綜合使用線框模型，表面模型和實體模型，以相互取長補短。 表示模型優(yōu)點局限性應用范圍線框模型結(jié)構(gòu)簡單、易于理解、運行速度快無觀察參數(shù)的變化；不可能產(chǎn)生有實際意義的形體；圖形會有二義性；畫二維線框圖（工程圖）、三維線框圖表面模型完整定義形體表面，為其他場合提供表面數(shù)據(jù)不能表示形體藝術(shù)圖形；形體表面的顯示；數(shù)控加工實體模型定義了實際形體只能產(chǎn)生正則形體；抽象形體的層次較低物性計算；有限元分析；用集合運算構(gòu)造形體 三種模型的比較2022/8/924第二節(jié) 數(shù)據(jù)結(jié)構(gòu)

11、、幾何信息與拓撲信息圖形對象及構(gòu)成它的點、線、面的位置、相互間關(guān)系和幾何尺寸等都是圖形信息；表示圖形對象的線型、顏色、亮度以及供模擬、分析用的質(zhì)量、比重、體積等數(shù)據(jù)，是有關(guān)對象的非圖形信息。2022/8/925圖形信息又包括：幾何信息：形體在歐氏空間中的位置和大小拓撲信息：形體各分量（點、邊、面）的數(shù)目及其相互間的連接關(guān)系。1. 點、線、面的幾何信息 (1)幾何分量的數(shù)學表示2022/8/926(2)幾何分量之間的相互關(guān)系2022/8/927幾何信息的二義性2. 點、線、面的拓樸信息平面立體的幾何分量之間一共有九種拓撲關(guān)系:2022/8/9282022/8/929剛體運動：不改變圖形上任意兩點

12、間的距離，也不改變圖形的幾何性質(zhì)的運動。拓撲運動：允許形體作彈性運動，即在拓撲關(guān)系中，對圖形可隨意地伸張扭曲。但圖上各個點仍為不同的點，決不允許把不同的點合并成一個點。拓撲等價、拓撲性質(zhì)2022/8/930二、線框模型的數(shù)據(jù)結(jié)構(gòu)將形體的幾何信息和拓撲信息記錄在邊表及頂點表中。 四棱柱的線框模型 四棱柱線框模型中邊與頂點的關(guān)系2022/8/931邊表頂點表邊號邊端點號頂點號XYZe1v1v2v1x1y1z1e2v2v3v2x2y2z2e3v3v4v3x3y3z3e4v4v5v4x4y4z4e5v5v6v5x5y5z5e6v6v7v6x6y6z6e7v7v8v7x7y7z7e8v8v1v8x8y8

13、z8e9v1v5e10v2v6e11v3v7e12v4v82022/8/932三、表面模型的數(shù)據(jù)結(jié)構(gòu) 將形體以三張表的形式表示，即面表、邊表、頂點表，并以單鏈指示它們之間的關(guān)系。 通常把這種結(jié)構(gòu)稱為以面為中心的頂點棱邊面（V-E-F）樹形結(jié)構(gòu)，或單鏈三表結(jié)構(gòu)。 (a) 三棱錐的表面模型 (b) 三棱錐表面模型中點、邊、面的關(guān)系2022/8/933 特點：是結(jié)構(gòu)關(guān)系清楚，節(jié)省存儲空間，檢索比較容易。 缺點：它不宜于頻繁地進行交互地修改。 2022/8/934四、實體模型的數(shù)據(jù)結(jié)構(gòu)1. 翼邊結(jié)構(gòu) 在頂點、棱邊、表面等組成物體的三要素中，翼邊結(jié)構(gòu)以邊為中心來組織數(shù)據(jù)。 2022/8/935 翼邊結(jié)構(gòu)

14、中邊的數(shù)據(jù)結(jié)構(gòu)V1lLeLcc，eLcw，eRcc，eRcwV2lR(a) 棱邊指針結(jié)構(gòu)(b) 頂點指針(c) 環(huán)指針(d) 面環(huán)表2022/8/936 翼邊結(jié)構(gòu)的存儲方式2022/8/937 翼邊結(jié)構(gòu)存在的問題：需要較多的存儲單元，對機器的存儲容量有一定的要求；在邊的構(gòu)造與使用方面還比較復雜。 為此對其進行了改進，提出了半邊數(shù)據(jù)結(jié)構(gòu)。半邊結(jié)構(gòu)已成為邊界表示的主流數(shù)據(jù)結(jié)構(gòu)。 半邊數(shù)據(jù)結(jié)構(gòu)與翼邊數(shù)據(jù)結(jié)構(gòu)的主要區(qū)別在于該結(jié)構(gòu)將一條物理邊拆成兩條邊表示，使其中每條邊只與一個鄰接面相關(guān) 。2022/8/9382. 半邊結(jié)構(gòu) 由于半邊數(shù)據(jù)結(jié)構(gòu)中的邊只表示相應物理邊的一半信息，故稱為半邊。半邊數(shù)據(jù)結(jié)構(gòu)在拓

15、撲上也分為五個層次，即體-面-環(huán)-半邊-頂點。 半邊結(jié)構(gòu)2022/8/939 半邊數(shù)據(jù)結(jié)構(gòu)的層次結(jié)構(gòu)2022/8/9404.以頂點為中心的數(shù)據(jù)結(jié)構(gòu)。 3.以面為中心的數(shù)據(jù)結(jié)構(gòu)面頂點坐標F1(X1Y1Z1，X2Y2Z2，X3Y3Z3，X4Y4Z4)F2(X1Y1Z1，X2Y2Z2，X6Y6Z6，X5Y5Z5).頂點/坐標表面/頂點序列表頂點坐標面頂點序列V1X1Y1Z1F1V1V2V3V4V2X2Y2Z2F2V1V2V6V52022/8/941第三節(jié) 常用的幾何造型方法線框模型、表面模型和實體模型是一種廣義的概念，并不反映形體在計算機內(nèi)部、或?qū)τ脩舳运玫木唧w表示方式。從用戶角度看，形體表示以

16、特征表示和構(gòu)造的實體幾何表示（CSG）較為方便；從計算機對形體的存儲管理和操作運算角度看，以邊界表示（BRep）最為實用。為了適合某些特定的應用要求，形體還有一些輔助表示方式，如單元分解表示和掃描表示?？傮w而言，比較傳統(tǒng)和常用的造型方法有以下幾種：2022/8/942 傳統(tǒng)和常用的造型方法有以下幾種： 掃描表示法（Sweep Representation）構(gòu)造實體幾何法（Constructive Solid Geometry）邊界表示法（Boundary Representation Scheme）基本體素表示法（Pure Primitive Instancing）空間位置枚舉法（Spatia

17、l Occupancy Enumeration）單元分解法（Cell Decomposition）2022/8/943新的表示方法：八叉樹表示法特征造型表示法曲面離散化近似表示法元球造型法2022/8/944 該表示法的覆蓋率形體范圍的大小造型能力的強弱 蘊含信息的完整性數(shù)據(jù)結(jié)構(gòu)是否唯一能否為后續(xù)工作提供信息選擇方法時需考慮以下兩點：2022/8/9451. 邊界表示法（ BR表示或BRep表示）邊界: 形體內(nèi)部點與外部點的分界面將形體的邊界分成有限個“面”（faces）或“片”（patches） (a) (b)2022/8/9462022/8/9472022/8/9482022/8/949利

18、用正則集的概念來定義上述的三維有效物體：點的領(lǐng)域：如果P是點集S的一個元素，那么點P的以R（R0）為半徑的領(lǐng)域指的是圍繞點P的半徑為R的小球（二維情況下為小圓）。內(nèi)點為點集中的這樣一些點，它們具有完全包含于該點集的充分小的領(lǐng)域。邊界點2022/8/950定義點集的正則運算r運算為：正則運算即為先對物體取內(nèi)點再取閉包的運算。rA稱為A的正則集。 2022/8/9512022/8/952二維流形指的是對于實體表面上的任意一點，都可以找到一個圍繞著它的任意小的領(lǐng)域，該領(lǐng)域與平面上的一個圓盤是拓撲等價的。 2022/8/953實體：對于一個占據(jù)有限空間的正則形體，如果其表面是二維流形，則該正則形體為實

19、體。 該定義條件可檢測2022/8/9544.1.6 正則集合運算有效實體的封閉性 把能夠產(chǎn)生正則形體的集合運算稱為正則集合運算2022/8/9552022/8/956有兩種方法實現(xiàn)正則運算間接方式：點的領(lǐng)域，即集合S在點P附近的局部幾何性質(zhì)：當且僅當P的領(lǐng)域為滿時，P在S之內(nèi)；當且僅當P的領(lǐng)域為空時，P在S之外；當且僅當P的領(lǐng)域既不滿也不空時，P在S的邊界上。2022/8/9572022/8/958直接方式：在三維空間中，給定一個正則形體S，空間點集被分為三個子集：S的內(nèi)部點集S的邊界點集S之外的點集2022/8/959分類函數(shù)： 若給定一個正則形體S及一個有界面G，則G相對于S的分類函數(shù)可

20、為： C(S,G)=G in S, G out S, G on S 其中， 2022/8/960用-G表示有界面G的反向面。即，如果有界面G在P點的法向為NP(G)，則有界面-G在P點的法向就是-NP(G)。于是：G on S=G shared (bS), G shared (-bS)其中， 2022/8/961則G相對于S的分類函數(shù)C(S,G)可為：C(S,G)=G in S, G out S, G shared (bS), G shared (-bS)正則集合算子 定義三個正則集合算子關(guān)于邊界面的表達式：2022/8/9622022/8/9634.1.7 平面多面體與歐拉公式平面多面體是表

21、面由平面多邊形構(gòu)成的三維物體。簡單多面體指與球拓撲等價的那些多面體。歐拉公式證明簡單多面體的頂點數(shù)V、邊數(shù)E和面數(shù)F滿足如下關(guān)系：V-E+F=2。2022/8/9642022/8/965令H表示多面體表面上孔的個數(shù)，G表示貫穿多面體的孔的個數(shù)，C表示獨立的、不相連接的多面體數(shù)，則擴展后的歐拉公式為：V-E+F-H=2（C-G）2022/8/966線框模型線框模型存在著幾個缺陷：二義性4.2 三維形體的表示2022/8/967容易構(gòu)造出無效形體2022/8/968不能正確表示曲面信息。2022/8/969無法進行圖形的線面消隱。加重用戶的輸入負擔難以保證數(shù)據(jù)的統(tǒng)一性和有效性。2022/8/970

22、實體模型（實體造型技術(shù)）可以將實體模型的表示大致分為三類：邊界表示（Boundary representation, B-reps）構(gòu)造實體幾何表示空間分割（Space-partitioning）表示2022/8/9714.2.1 多邊形表面模型邊界表示(B-reps)的最普遍方式是多邊形表面模型，它使用一組包圍物體內(nèi)部的平面多邊形，也即平面多面體，來描述實體。2022/8/9721. 多邊形表幾何表屬性表 例如：頂點表、邊表和多邊形表。為圖4-17所示的四面體建立的三張表如下：2022/8/973頂點表邊表面表Ax1,y1,z1ABA,BABCAB,BC,ACBx2,y2,z2BCB,CAB

23、DAB,BD,ADCx3,y3,z3CAC,ABCDBC,CD,BDDx4,y4,z4ADA,DACDAC,CD,ADBCB,CCDC,D2022/8/974表示其拓撲信息例如，翼邊結(jié)構(gòu)表示（Winged Edges Structure）2022/8/9752. 平面方程可以利用平面方程：求得平面的法向量鑒別空間上的點與物體平面的位置關(guān)系。判別點在面的內(nèi)部或外部2022/8/9763. 多邊形網(wǎng)格三維形體的曲面邊界通常用多邊形網(wǎng)格（polygon mesh）的拼接來模擬。三角形帶、四邊形網(wǎng)格2022/8/9774.2.2 掃描表示（sweep representation）掃描表示法（swee

24、p representation）可以利用簡單的運動規(guī)則生成有效實體。包含兩個要素：一是作掃描運動的基本圖形；二是掃描運動的方式。 2022/8/978掃描運動的方式有：旋轉(zhuǎn)掃描非圓形路徑掃描廣義掃描法2022/8/9794.2.3 構(gòu)造實體幾何法構(gòu)造實體幾何法（CSG，Constructive Solid Geometry）由兩個實體間的并、交或差操作生成新的實體。2022/8/980在構(gòu)造實體幾何法中，集合運算的實現(xiàn)過程可以用一棵二叉樹（稱為CSG樹）來描述：樹的葉子樹的非終端結(jié)點二叉樹根結(jié)點2022/8/981構(gòu)造實體幾何法的優(yōu)點：可以構(gòu)造出多種不同的符合需要的實體。問題：求交困難CSG

25、樹不能顯式地表示形體的邊界解決：光線投射（Ray-casting）算法2022/8/982光線投射（Ray-casting）算法核心思想：2022/8/983具體算法是：1)將射線與CSG樹中的所有基本體素求交，求出所有的交點。2)將所有交點相對于CSG樹表示的物體進行分類，確定位于物體邊界上的那部分交點。3)對所有位于物體邊界上的交點計算它們在射線上的參數(shù)值并進行排序，確定距離最近的交點。得到其所在基本體素表面的法矢量。2022/8/9844.2.4 空間位置枚舉表示空間位置枚舉表示法將包含實體的空間分割為大小相同、形狀規(guī)則（正方形或立方體）的體素，然后，以體素的集合來表示圖形對象。二維情況

26、，常用二維數(shù)組存放。三維情況下，常用三維數(shù)組pijk來存放。2022/8/9854.2.5 八叉樹八叉樹（octrees）又稱為分層樹結(jié)構(gòu)，它對空間進行自適應劃分，采用具有層次結(jié)構(gòu)的八叉樹來表示實體。2022/8/986四叉樹2022/8/987八叉樹2022/8/9884.2.6 BSP樹二叉空間分割（binary space partitioning，BSP）方法每次將一實體用任一位置和任一方向的平面分為二部分。2022/8/9894.3 非規(guī)則對象的表示基于分數(shù)維理論的隨機模型基于文法的模型粒子系統(tǒng)模型2022/8/9904.3.1 分形幾何(fractal geometry)分形幾何物

27、體具有一個基本特征：無限的自相似性。無限的自相似性是指物體的整體和局部之間細節(jié)的無限重現(xiàn)。分形物體的描述又包含：分形維數(shù)，又稱分數(shù)維數(shù)生成過程：初始生成元（initiator）、生成元（genenator）2022/8/9914.3.2 形狀語法形狀語法（shape grammars）：給定一組產(chǎn)生式規(guī)則，形狀設(shè)計者可以在從給定初始物體到最終物體結(jié)構(gòu)的每一次變換中應用不同的規(guī)則。2022/8/9924.3.3 微粒系統(tǒng)用于模擬自然景物或模擬其它非規(guī)則形狀物體展示“流體”性質(zhì)的一個方法是微粒系統(tǒng)（particle systems）。這一方法尤其擅長描述隨時間變化的物體。微粒運動的模擬方式：隨機過

28、程模擬、運動路徑模擬、力學模擬2022/8/9934.3.4 基于物理的建?；谖锢淼慕７椒ǎ好枋隽宋矬w在內(nèi)外力相互作用下的行為。通常用一組網(wǎng)格結(jié)點來逼近物體。網(wǎng)格結(jié)點間取為柔性連接，再考慮貫穿物體網(wǎng)格的力傳遞。基于力學方程的動畫描述比基于運動學方程的描述產(chǎn)生的運動更真實。實例2022/8/9944.3.5 數(shù)據(jù)場的可視化科技計算可視化（scientific visualization）指的是運用計算機圖形學和圖象處理技術(shù)，將科學計算過程中及計算結(jié)果的數(shù)據(jù)轉(zhuǎn)換為圖形及圖象在屏幕上顯示出來并進行交互處理的理論、方法和技術(shù)。有三種不同類型的數(shù)據(jù)需要實現(xiàn)可視化：2022/8/995標量：若對每一個

29、直角坐標系oxyz有一個量，它在坐標變換時滿足下式，即保持其值不變，則此量定義了一個標量。 2022/8/996矢量：對于每一個直角坐標系ox1x2x3來說有三個量x1,x2,x3，它們可根據(jù)下式變換到另一個坐標系ox1x2x3，則此時三個量定義了一個矢量。2022/8/997二階張量：如果對每一個直角坐標系ox1x2x3，有9個量Xij(i=1,2,3;j=1,2,3)，它可以按照以張量形式表示的下述公式轉(zhuǎn)換為另一個直角坐標系中的9個量Xij(i=1,2,3;j=1,2,3)，則這9個量定義了一個二階張量。 2022/8/998顯然，二階張量可以表示為一個33矩陣： 2022/8/999二階張量的定義可以推廣到n階張量。當n=0時，張量的分量