1、哈爾濱工業大學計算機學院唐好選2022年年4月月14日日幾何造型及高級建模技術主要知識點主要知識點 幾何造型的定義幾何造型的定義 形體在計算機內的表示 高級建模技術分數維造型粒子系統基于紋理的造型基于圖像的造型 通過對點、線、面、體等幾何元素，經過平移、旋轉、變比等幾何變換和并交差等集合運算，產生實際的或想象的幾何模型 如何用計算機內的一維存儲空間來存放由0維、1維、2維、3維等幾何元素的集合所定義的形體，無疑是幾何造型中最基本的問題關于幾何造型的定義關于幾何造型的定義 第一代：手工繪制工程圖 第二代：二維計算機繪圖 第三代：三維線框結構 第四代：曲面造型 第五代：實體造型幾何造型技術的發展幾

2、何造型技術的發展模型分類模型分類形體表示形體表示線框模型線框模型表面模型表面模型實體模型實體模型數據模型數據模型過程模型過程模型完全以數據描述規則形體的建模方法以過程和控制參數描述不規則形體的建模方法表現物體的骨架表現物體的皮膚表示“有血有肉”的物體模型主要知識點主要知識點 幾何造型的定義幾何造型的定義 形體在計算機內的表示形體在計算機內的表示 高級建模技術分數維造型粒子系統基于紋理的造型基于圖像的造型 頂點(Vertex)：零維的幾何元素,包括插值點、型值點和控制點 邊(Edge)：一維的幾何元素，可以是直線，也可以是曲線 面(Face)：是形體上一個有限非零的區域，是二維的幾何元素，至少有

3、一個外環和若干個（可以是零個）內環界定其范圍，面的外法線方向是面的方向，可以是平面或曲面 環(Loop)：是有序有向邊組成的面的封閉邊界，在面上沿一個環前進，其左側總在面內，右側總在面外 體(Body)：三維的幾何元素，是由封閉表面圍成的空間，其邊界是有限面的并集表示形體的基本幾何元素表示形體的基本幾何元素 構成形體的幾何元素按六個層次表示：形體、外殼、面、環、邊、點 對于任意形體，如果它是三維歐氏空間中的非空有界的封閉子集，其邊界上任意一點都存在一個充分小的鄰域，該鄰域與平面上的封閉圓是同構的，則該形體為正則形體，否則為非正則形體（如下圖） 點點(V)邊邊(E)面面(F)的個數滿足公式的個數

4、滿足公式V - E + F = 2812345679V-E+F-C=9-20+18-6=1 如果把三維封閉空間分割成如果把三維封閉空間分割成C個多面體，其頂點、邊、面和多個多面體，其頂點、邊、面和多面體個數滿足下列公式：面體個數滿足下列公式：V-E+F-C=1 立方體內立方體內1點與點與8個頂點相個頂點相連可以分割出連可以分割出6個多面體個多面體(C) 頂點數頂點數(V)：8+1 = 9 邊數邊數(E)：12 + 8 = 20 面數面數(F)：6 + 6*4/2 = 18 對于有孔形體，若孔的個數為對于有孔形體，若孔的個數為H,C為形體個數，為形體個數，G為穿透形體為穿透形體的孔洞數，則相應的

5、歐拉公式是的孔洞數，則相應的歐拉公式是:V-E+F-H=2(C-G) 孔個數孔個數(H)：3 形體個數形體個數(C)：1 穿透形體的孔洞數穿透形體的孔洞數(G)：1 頂點數頂點數(V): 3(長方體數長方體數)*8 = 24 邊數邊數(E): 3 (長方體數長方體數)* 12 = 36 面數面數(F)：3(長方體數長方體數)*6-3 = 15V-E+F-H = 24-36+15-3 = 0 = 2(1-1) = 2(C-G) 邊界表示（Boundary Representations） 掃描表示（Sweeps Representations） 空間分解表示（Spatial-Partitioni

6、ng Representations）空間位置枚舉表示（Spatial-Occupancy Enumeration）八叉樹表示（Octrees）單元分解表示（Cell Decomposition） 構造實體幾何表示（Constructive Solid Geometry） 邊界所描述的幾何信息包括： 幾何信息(Geometry)：描述形體幾何元素的性質和度量關系，如位置、大小、方向、尺寸和形狀信息 拓撲信息(Topology)：描述形體幾何元素之間的連接關系、鄰近關系及邊界關系，形成物體邊界表示的骨架 幾何元素間典型的連接關系(即拓撲關系)是指一個形體由哪些面組成,每個面上有幾個環,每個環由哪

7、些邊組成,每條邊又由哪些頂點定義等 幾何造型中最基本的幾何元素是點(V) 、邊(E)、面(F),這三種幾何元素共有9種連接關系邊界表示邊界表示- -形體的邊界及其連接關系形體的邊界及其連接關系1/21/2 VVVVV1V VEEEV1EV1F VFFF EFFE1F EEEEEE1E VVEE1V FFFFFF1F EEEEFF1E VVVVFF1V確定了物體的邊界也就確定了物體本身形體是由幾何元素構成的,每一種形體的邊界每一種形體的邊界都是由與其相對應的較低維的幾何元素組成的。實體邊界通常由面的并集表示,面的邊界是邊的并集,邊由頂點來表示在邊界表示的數據結構中,比較著名的有冀邊數據結構：冀邊

8、數據結構：以邊為核心組織數據結構，用指針記錄每一條邊的兩個鄰面（左右外環）、兩個頂點及兩側各自相鄰的兩個鄰邊（左上/下邊、右上/下邊）半邊數據結構：半邊數據結構：將一條物理邊拆成兩條邊來表示，使其中的每條邊只與一個鄰接面相關 以邊為核心記錄數據（以邊為核心記錄數據（以邊以邊E1為例為例） 記錄記錄E1的兩個鄰面的兩個鄰面 左外環左外環F1和右外環和右外環F2 記錄記錄E1的兩個頂點的兩個頂點 上頂點上頂點V1和下頂點和下頂點V2 記錄記錄E1的四個鄰邊的四個鄰邊 左上邊左上邊E2和左下邊和左下邊E4 右上邊右上邊E3和右下邊和右下邊E5 優點可精確表示物體表示覆蓋域大，表示能力強容易確定幾何元

9、素之間的連接關系，幾何變換容易顯式表示幾何元素，繪制速度快 缺點數據結構復雜，維護不方便需要大量的存儲空間不一定表示一個有效形體，有效性難以保證 也稱為推移表示，是基于一個基體（一般是一個封閉的二維區域）沿某一路徑運動而產生的形體 掃描表示需要兩個分量: 一是被運動的基體 另一個是基體運動的路徑 如果是變截面的掃描，還要給出截面的變化規律 一個二維區域沿某一路徑運動得到的物體稱為Sweep體 平移Sweep體：將一個二維區域沿著一個矢量方向掃描指定的距離，得到的曲面稱為平移Sweep體，或稱為拉伸體(如圓柱、立方體等) 旋轉Sweep體：將一個二維區域繞某一給定的旋轉軸旋轉一個特定的角度得到的

10、曲面稱為旋轉Sweep體，或稱為回轉體（如圓錐） 廣義Sweep體：將任意剖面沿任意軌跡掃描指定的距離，掃描路徑可以用曲線函數來表示，并且可以沿掃描路徑變化剖面的形狀和大小，就可得到廣義的Sweep體 等截面掃描 變截面掃描 優點表示簡單、直觀適合做圖形輸入手段 缺點做幾何變換困難不能直接獲取形體的邊界信息表示形體的覆蓋域非常有限 空間分解表示也稱為空間分割表示，主要分為以下幾種方法：空間位置枚舉表示（ Spatial-Occupancy Enumeration ）八叉樹表示（ Octrees ）單元分解表示（Cell Decomposition）xzy小立方體首先在空間中定義一個能包含所要表

11、示的物體的立方體，立方體的棱邊分別與x,y,z軸平行，然后將其均勻劃分為一些單位小立方體，用三維數組Cxyz表示數組中的元素與單位小立方體是一一對應，當Cxyz=1時，表示對應的小立方體被實體占據，否則，對應的小立方體沒有被實體所占據優點：可以表示任何形狀的物體缺點：是物體的一種非精確表示，占用的存儲空間較大 將物體所在的立方體自適應劃分成一些不同大小的立方體，然后將其表達為一種樹形層次結構 八叉樹表示形體的算法可表示為： 首先對形體定義一個外接的立方體作為八叉樹的根節點，對應整個物體空間，將其分解為8個子立方體，分別對應八叉樹的八個節點 如果立方體單元完全被物體所占據，則該節點標記為F(Fu

12、ll)，停止對該子立方體的分解 如果子立方體單元內沒有物體，則將該節點標記為E(Empty) 如果子立方體單元部分被物體部分占據，則將該節點標記為P(Partial) ,并對該立方體作進一步分解，進一步分割成8個子立方體，對每一個子立方體進行同樣的處理 當分割生成的每一個小立方體均被標記為F或 E以后，算法結束，否則，如果標記為P 的每個小立方體的邊長均為單位長度，這時應將其重新標記為F后結束算法xzyEEEEEFEEEEFFEFPPE棱錐體素 長方體體素 體素并集 將單一體素分解改進為多種體素分解，將多種體素組織在一起表示物體單元分解表示的優點：表示簡單，基本體素可以按需選擇，表示范圍較廣，

13、可以精確表示物體缺點：分解的方法很多，物體的表示不惟一 通過對基本體素定義各種運算而得到新的實體，其運算可以為幾何變換或正則化的并交差集合運算 常用的體素有長方體、立方體、圓柱、圓錐、圓臺、棱錐、棱柱、環和球等 基本步驟首先確定要構造三維實體的初始體素集每次操作時從中選擇兩個體素，按照一定的相對位置關系放置到空間某位置，對其進行體素的并、交、差集合運算，生成一新的實體利用基本體素和每一步新創建的新形體的組合，繼續構造新的形體，直到形成最后所需要的三維實體為止 U* -* -* U*主要知識點主要知識點 幾何造型的定義幾何造型的定義 形體在計算機內的表示形體在計算機內的表示 高級建模技術高級建模

14、技術分數維造型粒子系統基于紋理的造型基于圖像的造型 雪花的形狀是什么樣的?第一步第二步第三步 雪花的每一部分經過放大都可以與它的整體一模一樣(自相似形)自相似形的另一個例子 雪花的形狀 分數維分數維(維數為分數),不同于拓樸維(整數維) 自相似性自相似性:部分與整體以某種形式相似的形 分形集都具有任意小尺度下的比例細節，或者說它具有精細的結構 分形集不能用傳統的幾何語言來描述，它既不是滿足某些條件的點的軌跡，也不是某些簡單方程的解集 分形集具有某種自相似形式，可能是近似的自相似或者統計的自相似 一般，分形集的“分形維數”，嚴格大于它相應的拓撲維數 在大多數令人感興趣的情形下，分形集由非常簡單的

15、方法定義，可能以變換的迭代產生 首先，分形形態是自然界普遍存在的分形形態是自然界普遍存在的，研究分形，是探討自然界的復雜事物的客觀規律及其內在聯系的需要，分形提供了新的概念和方法 其次，分形具有廣闊的應用前景分形具有廣闊的應用前景，在分形的發展過程中，許多傳統的科學難題，由于分形的引入而取得顯著進展。 分形作為一種新的概念和方法，正在許多領域開展應用探索。80年代初國外開始的“分形熱”經久不息。美國著名物理學家惠勒說過：今后誰不熟悉分形，誰就不能被稱為科學上的文化人。 隨機插值模型：可以模擬海岸線和山等自然景象 正規文法模型：用正規文法生成結構性強的植物的拓撲結構，再通過進一步幾何解釋形成逼真的畫面 迭代函數系統模型：選取合適的映射集合、概率集合及初始點，使得生成的無窮點集能模擬某種景物 Koch曲線 隨機L系