計算機輔助制造CAD CAM -04-2

1、第4章 幾何造型系統(tǒng)的數(shù)據(jù)結構 概述數(shù)據(jù)結構的基本知識幾何體在計算機中的表示 三維形體的原理及表達 主要內(nèi)容一、概述 計算機所能處理的對象是數(shù)據(jù)。在計算機內(nèi)部，各種信息都必須經(jīng)過數(shù)字化編碼之后才能被傳送存儲和處理。問題： 何謂計算機造型？何謂幾何造型？ 如何利用計算機對客觀世界中的事物進行造型處理？何謂計算機造型？計算機就是以計算機能夠理解的方式，對實體進行確切的定義，賦予一定的數(shù)學描述，再以一定的數(shù)據(jù)結構形式對所定義的幾何實體加以描述，從而在計算機內(nèi)部構造一個實體的模型。完整性惟一性幾何造型幾何造型是指點線面體等幾何元素通過一系列幾何變換和集合運算生成的物體模型?；編缀卧卦谟嬎銠C內(nèi)的存儲

2、和組織是幾何造型的關鍵技術。幾何造型的任務任務物體+屬性數(shù)字模型幾何信息特性信息設計分析制造仿真裝配管理幾何造型的重要性幾何造型實現(xiàn)產(chǎn)品的計算機輔助設計與制造的基礎和條件。 如何在計算機中表示現(xiàn)實世界？現(xiàn)實世界計算機世界數(shù)據(jù)模型數(shù)據(jù)數(shù)據(jù)結構算法二、數(shù)據(jù)結構知識一、數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)對象、數(shù)據(jù)結構的定義 1、數(shù)據(jù)的定義定義一：數(shù)據(jù)是客觀事物的符號表示。 學號姓名語文數(shù)學C語言6201001張三8554926201002李四928464例：張三的C語言考試成績?yōu)?2分，92就是該同學的成績數(shù)據(jù)。 定義二：能輸入到計算機中并被計算機程序處理的符號的總稱。例：圖像、聲音等。數(shù)據(jù)元素、數(shù)據(jù)項 數(shù)據(jù)元素

3、是數(shù)據(jù)的基本單位，它由不可分割的數(shù)據(jù)項組成數(shù)據(jù)對象是性質相同的數(shù)據(jù)元素的集合。如上例：一個班級的成績表可以看作一個數(shù)據(jù)對象。數(shù)據(jù)結構及其種類 數(shù)據(jù)元素集合（也可稱數(shù)據(jù)對象）中各元素間相互關系。特征示例集合元素間為松散的關系線性結構元素間為嚴格的一對一關系如上面的成績表中各元素特征示例樹形結構元素間為嚴格的一對多關系圖狀結構元素間為多對多關系常用的數(shù)據(jù)結構線性表樹形結構 理解線性表一個線性表是n個數(shù)據(jù)元素的有限序列。線性表是最常用且最簡單的一種數(shù)據(jù)結構。數(shù)據(jù)元素可以是一個數(shù)、一個符號、也可以是一幅圖或更復雜的信息。線性表中的數(shù)據(jù)元素類型多種多樣同一線性表中的元素必定具有相同特性，即屬同一數(shù)據(jù)對象

4、每個數(shù)據(jù)元素有且只有一個直接前趨和直接后繼a1.ai-1aiai+1.anai是ai+1的直接前趨元素，ai+1是ai的直接后繼元素 線性表中元素的個數(shù)n定義為線性表的長度，為0時稱為空表。在非空表中的每個數(shù)據(jù)元素都有一個確定的位置。ai是第i個元素，把i稱為數(shù)據(jù)元素ai在線性中的位序。線性表的存儲結構有兩種：順序存儲結構和鏈式存儲結構順序存儲結構順序存儲就是用一組連續(xù)的存儲單元，按照數(shù)據(jù)元素的邏輯順序依次存放。假定每個數(shù)據(jù)元素占用m個存儲單元，每個數(shù)據(jù)元素第1個單元的存儲位置為該數(shù)據(jù)元素的存儲位置，第1個數(shù)據(jù)元素的存儲位置為b，則第t個數(shù)據(jù)元素的存儲位置為Loc(at)=b+(t-1)m順序

5、存儲結構的特點有序性：各數(shù)據(jù)元素之間的存儲順序與邏輯順序一致。均勻性：每個數(shù)據(jù)元素所占存儲空間的長度相等。因為順序存儲結構的均勻有序性，使得計算機對表內(nèi)數(shù)據(jù)元素進行訪問、修改運算的速度非?？臁?這種結構多用于查找頻繁、很少增刪的場合，比如工程手冊中的數(shù)據(jù)表。鏈式存儲結構線性表中的數(shù)據(jù)元素可以用任意的存儲單元來存儲。線性表中邏輯相鄰的兩元素的存儲空間可以是不連續(xù)的。表的每個數(shù)據(jù)元素除存儲本身的信息之外，還需存儲一個指示其直接后繼的信息。這兩部分信息組成數(shù)據(jù)元素的存儲映象，稱為結點。結點有兩種域：存放數(shù)據(jù)元素本身的數(shù)據(jù)域和存放其直接前趨或直接后繼的指針域。用線性鏈表表示線性表時,數(shù)據(jù)元素之間的邏輯

6、關系是由結點中的指針指示的。鏈式存儲結構又分為單向鏈表和雙向鏈表單向鏈表單向鏈表的指針域只有一個，通常存放直接后繼的地址。第一個元素的地址需要專門存放在指定的指針型變量中，或者設置一個與鏈表結點相同的一個結點，它的數(shù)據(jù)域可以是空的，也可以存放表長等附加信息，指針域存放第一個元素的地址。雙向鏈表單向鏈表的結點只有一個存放直接后繼的指針域，因此某個結點出發(fā)只能向后尋找其他結點。如果結點再增設一個指針域，存放它的直接前趨的地址，就可以方便地從每個結點向前尋找其他結點，這樣的鏈表稱為雙向鏈表。鏈式存儲結構與順序存儲比較刪除或插入運算速度快。不需事先分配存儲空間，以免不能充分利用所用空間。表的容量容易擴

7、充。按邏輯順序查找的速度慢。比相等長度的順序存儲多占用作為指針域的存儲空間。 樹形結構樹形結構的簡稱為樹，它是一種重要的非線性數(shù)據(jù)結構，它為計算機應用中出現(xiàn)的具有層次關系或分支的數(shù)據(jù)提供了一種自然的表示方法。 該樹包含了9個結點，分別為A，B，C.I。其中結點A是樹根，稱為根結點；結點C，E，F(xiàn)，G，H，I是樹葉，也稱為終端結點；結點間的連線稱為邊。 樹形結構的特點除根結點外，每個結點有且只有一個直接前趨；除終端點外，每個結點可以有不只一個直接后繼。結點的直接前趨稱為該結點的雙親，結點的直接后繼稱為該結點的孩子，同一雙親的孩子間稱兄弟。樹是具有層次關系的數(shù)據(jù)結構，層次的數(shù)量稱為樹的高度。結點的

8、孩子數(shù)量稱為度。樹的所有結點中最大的度數(shù)稱為這棵樹的度數(shù)。定長鏈式存儲方式以具有最大度數(shù)的結點的結構作為該樹所有結點的結構。樹的邏輯結構為非線性的，所以其存儲結構形式只能采用鏈式結構。數(shù)據(jù)域子樹1地址子樹2地址子樹n地址特點：每個結點都有相同數(shù)量的子樹域。不定長鏈式存儲方式每個結點增加一個存放度數(shù)的域，結點的長度隨著度數(shù)的增加而增加數(shù)據(jù)域度數(shù)n子樹1地址子樹2地址子樹n地址二叉樹二叉樹是一種不同于樹的數(shù)據(jù)結構，它的特點是每個結點至多只有二棵子樹（即二叉樹中不存在度大于2的結點),并且,二叉樹的子樹有左右之分,其次序不能任意顛倒。由上述定義可以看出，二叉樹和樹是兩個不同的概念樹的每一個結點可以有

9、任意多個后繼，而二叉樹中每個結點的后繼不能超過2；樹的子樹可以不分次序（除有序樹外）；而二叉樹的子樹有左右之分。我們稱二叉樹中結點的左后繼為左兒子，右后繼為右兒子。 二叉樹的五種基本形態(tài)空二叉樹只有一個結點二叉樹只有左子樹的二叉樹只有右子樹的二叉樹左右子樹均有的二叉樹二叉樹的兩個特殊形態(tài)滿二叉樹：如果一棵二叉樹的任何結點，或者是樹葉，或者恰有兩棵非空子樹，則此二叉樹稱作滿二叉樹?？梢则炞C具有n個葉結點的滿二叉樹共有2n-1個結點abcdefghi滿二叉樹完全二叉樹：如果一棵二叉樹最多只有最下面兩層結點度數(shù)可以小于2，并且最下面一層的結點都集中在該層最左邊的若干位置上，則稱此二叉樹為完全二叉樹a

10、bcegdfabcdefghi完全二叉樹jkl特點滿二叉樹是完全二叉樹，完全二叉樹不一定是滿二叉樹。在滿二叉樹的最下一層上，從最右邊開始連續(xù)刪去若干結點后得到的二叉樹仍然是一棵完全二叉樹在完全二叉樹中，若某個結點沒有左孩子，則它一定沒有右孩子，即該結點必是葉結點。 二叉樹的編號編號辦法 在一棵n個結點的完全二叉樹中，從樹根起，自上層到下層，每層從左至右，給所有結點編號，能得到一個反映整個二叉樹結構的線性序列。二叉樹的存儲結構對于滿二叉樹可用順序存儲形式。 對于一般二叉樹，通常采用鏈表結構。每個結點設三個域：存放結點的值域，存放左子樹地址的左子樹域以及存放右子樹地址的右子樹域，如圖所示。順序存儲

11、結構的特點是節(jié)省存儲空間，可利用公式隨機地訪問每個結點和它的雙親及左、右孩子，但不便于刪除或插入操作。鏈表存儲結構的特點是多占一些存儲空間，但運算算法實現(xiàn)比較簡單直觀。 三、幾何體在計算機中的表示常用的五種坐標系(1)用戶坐標系 ( UC)(2) 造型坐標系造 ( MC)(3) 觀察坐標系 ( VC)(4) 規(guī)格化的設備坐標 系 ( NDC)(5) 設備坐標系 ( DC)表示形體的數(shù)據(jù)結構三表結構-包括頂點表、棱邊表、面表對形體進行描述的數(shù)據(jù)結構有：三表結構和八叉樹八叉樹二維圖形用四叉樹表示，三維形體用八叉樹表示，如下圖所示，用八叉樹對形體所占空間作單元分解，首先要定義形體的外接正立方體，并把

12、它分割成八個子立方體，如子立方體為滿或為空，則該子立方體全在或者全不在形體中，該子立方體可以停止分解；而且被形體新分占有的子立方體還要作一分為八的分解、直到所有的子立方體或為滿或為空或已達到規(guī)定或已達到規(guī)定的分解精度，就停止分解。利用八叉樹表示的圓環(huán)用八叉樹結構表示空間體的優(yōu)點可以用統(tǒng)一而簡單的形體（即立方體）來表示空間任意形狀的實體，因而，數(shù)據(jù)結構簡單劃一。容易實現(xiàn)實體之間的交、并、差等集合運算。容易檢查空間實體之間是否碰撞，計算出兩個實體之間的最小距離也相對容易。易于計算物體的性質，如物體的體積、質量、重量等。容易實現(xiàn)消隱及顯示輸出。用八叉樹結構表示空間體的缺點八叉樹表示存儲量較大。在八叉

13、樹表示中難以實現(xiàn)某些幾何變換，如旋轉任意角度，具有任意比例系數(shù)的比例變換等。八叉樹表示中只是空間實體的近似表示，八叉樹表示形體難以轉換成邊界表示或結構實體的幾何表示，從而使得它難以和已有的CADCAM系統(tǒng)有機地結合在一起 四、三維形體的原理及表達幾何造型將對實體的描述和表達建立在幾何信息和拓撲信息處理的基礎上。幾何信息是指物體在空間的形狀、尺寸及位置的描述；拓撲信息是構成物體的各個分量的數(shù)目及相互之間的連接關系。根據(jù)造型空間的不同，可將幾何造型分為 二維造型 三維造型按照對幾何信息與拓撲的描述及存儲方法的不同，三維幾何造型又可分為 三維線框造型 曲面造型 實體造型線框造型指用構成物體的各頂點坐

14、標和連接各頂點所形成的邊來描述物體的造型方法，亦即用一系列的頂點、直線、圓弧和自由曲線來描述物體的輪廓形狀。由此方法所產(chǎn)生的數(shù)字模型為線框模型。線框模型的數(shù)據(jù)結構 線框造型描述的是產(chǎn)品的輪廓外形。線框造型的數(shù)據(jù)結構是表結構，線框造型在計算機內(nèi)部是以邊表和點表來表達和存儲的，實際物體是邊表和點表相應的三維映象，計算機可以自動實現(xiàn)視圖變換和空間尺寸協(xié)調(diào)。下圖為一立方體線框模型的數(shù)據(jù)結構，采用了8個頂點和12條邊來表達。 它由兩張表構成，即點表和邊表。在點表中記錄了各頂點的坐標值，邊表中則記錄了構成邊所需兩個端點和邊號及邊的幾何元素類型代碼，在這里我們以“0”代表直線（若具有弧段，則可以用其它代碼表

15、示）。由此可見三維物體是用它的全部頂點及邊的集合來描述，線框一詞由此而得名。 線框建模的特點采用線框建模的描述方法所需信息最少，數(shù)據(jù)運算簡單，所占的存貯空間也比較小，另外，這種建模方法對硬件的要求不高，容易掌握，處理時間較短。線框建模包含了形體的三維數(shù)據(jù)，可以產(chǎn)生任意視圖，為生成工程圖提供了方便。優(yōu)點：缺點 線框建模所構造的實體模型，只有離散的邊，而沒有邊與邊的關系，即沒有構成面的信息，由于信息表達不完整，在許多情況下，會對物體形狀的判斷產(chǎn)生多義性。曲面（表面）造型曲面造型又叫表面造型，是通過對實體的各個表面或曲面進行描述而構造實體模型的種建模方法；用有向棱邊圍成的部分來定義形體表面，由面的集

16、合來定義形狀而對表面或曲面進行描述而構造形體模型的一種造型方法。 利用曲面建模時，首先是將復雜的外表而分解成若干個組成面，然后定義出一塊塊的基本面素，基本面素可以是平面或二次曲面，例如圓柱面、圓錐面、圓環(huán)面、回轉面等，通過各面素的連接構成了組成面，各組成面的拼接就是所構造的模型。這種方法能夠精確地確定物體表面上任意一個點的X/Y/Z坐標值。 曲面造型實際上是在線框模型的基礎上添加了增加有關面、邊（環(huán)）信息以及表面特征、棱邊的連接向等內(nèi)容而成，利用表面模型，我們就可以對物體進行剖面、消隱、獲得NC加工所需的表面信息等一系列操作。 曲面建模的特點表達了零件表面和邊界定義的數(shù)據(jù)信息，有助于對零件進行

17、渲染等處理，有助于CAM系統(tǒng)直接提取有關面的信息生成數(shù)控機床的加工指令(自動確定刀具的切削路徑)，因此，大多數(shù)CAD/CAM系統(tǒng)中都具備曲面建模的功能； 在物理性能計算上面，表面建模中，面信息的存在有助于對物性方面與面積相關的特征計算，如零件的表面積等，同時對于封閉的零件來說，采用掃描等方法亦可以實現(xiàn)對零件進行與體積等物理性能相關的特征計算，如計算曲面所圍成的容積、重量、形心位置、慣性矩等； 表面建模方式生成的零部件及產(chǎn)品可分割成板、殼形式的有限元網(wǎng)格優(yōu)點產(chǎn)品造型設計的有效性上看，曲面建模在許多場合下效率低。易丟面，精度不高，不宜用作表示機械零件的一般方法。無法表示零件的立體屬性，不便進行質量

18、等特性分析曲面建模的不足： 實體建模實體建模就是計算機利用一些基本體素，如長方體、圓柱體、球體、錐體、圓環(huán)體以及掃描體等通過集合運算(布爾運算)生成復雜形體的一種建模技術。它記錄了實體全部的點、線、面、體的拓撲信息，是當代CAD技術發(fā)展的主流。實體建模主要包括兩部分內(nèi)容：體素的定義及描述和體素之間的布爾運算(并、交、差)。 基本體素：可通過少量參數(shù)進行描述，例如長方體通過長、寬、高定義。為定義基本體素在空間的位置和方向，應首先定義基準點。就長方體而論，它的基準點可位于它的一個頂點，也可位于一個平面的中心；不同的實體建模系統(tǒng)，可提供不同的基本體素類型。常見基本體素平面輪廓掃描體體素：即用平面輪廓掃描法生成的體素。平面輪廓掃描法是一種與二維系統(tǒng)密切結合的、并常用于棱柱體或回轉體生成實體的一種描述方法。掃描的前提條件是要有一個封閉的平面輪廓。當該平面輪廓沿著某一個坐標方向移動或繞某一給定的軸旋轉時，便形成了如右圖所示的兩種掃描變換。整體掃描就是使一個剛體在空間運動以產(chǎn)生新的物體形狀，如右圖所示（銑刀運動中可能生成的形狀 a)平移 b)回轉 ）。這種方法在生產(chǎn)過程的模擬及干涉檢驗方面具有很大的實用價值。特別是在NC加工中刀具軌跡生成和檢驗方面具有重要意義。實體模型與表面模型的不同實