1、1第十講第十講 三維形體的表示三維形體的表示 表示形體的兩種模型 實體的定義 正則集合運算 特征表示 空間分割表示 推移表示 邊界表示 構造實體幾何表示 不規則形體的建模方法 L系統2表示形體的兩種模型（表示形體的兩種模型（1/4） 數據模型數據模型 完全以數據描述完全以數據描述 例如例如 用以用以8個頂點表示的立方體個頂點表示的立方體 以中心點和半徑表示的球以中心點和半徑表示的球 以數據文件的形式存在以數據文件的形式存在 包括包括-特征表示、空間分割表示、推移表示、邊界特征表示、空間分割表示、推移表示、邊界表示、構造實體幾何表示等表示、構造實體幾何表示等 進一步分為進一步分為 線框模型線框模

2、型 將形體表示成一組輪廓線的集合將形體表示成一組輪廓線的集合 簡單、處理速度快簡單、處理速度快 與形體之間不存在一一對應關系，是真實物體的高度抽象，不適合與形體之間不存在一一對應關系，是真實物體的高度抽象，不適合真實感顯示真實感顯示3表示形體的兩種模型（表示形體的兩種模型（2/4） 表面模型表面模型 將形體表示成一組表面的集合將形體表示成一組表面的集合 形體與其表面一一對應，適合于真實感顯示形體與其表面一一對應，適合于真實感顯示4表示形體的兩種模型（表示形體的兩種模型（3/4） 實體模型實體模型 用來描述實體，主要用于用來描述實體，主要用于CAD/CAM 包含了描述一個實體所需的較多信息，如幾

3、何信包含了描述一個實體所需的較多信息，如幾何信息、拓撲信息息、拓撲信息 過程模型 以一個過程和相應的控制參數描述以一個過程和相應的控制參數描述 例如例如 用一些控制參數和一個生成規則描述的植物用一些控制參數和一個生成規則描述的植物 以一個數據文件和一段代碼的形式存在以一個數據文件和一段代碼的形式存在 包括包括-粒子系統、粒子系統、L系統、迭代函數系統等系統、迭代函數系統等5表示形體的兩種模型（表示形體的兩種模型（4/4） 模型分類模型分類6實體的定義（實體的定義（1/4） 抽象帶來的問題抽象帶來的問題 計算機中表示的物體是無效的計算機中表示的物體是無效的 不能夠客觀存在不能夠客觀存在 為什么要

4、求客觀存在為什么要求客觀存在 CAD/CAM的需求的需求 什么是客觀存在（有效）什么是客觀存在（有效）實體的定義實體的定義 具有一定的形狀具有一定的形狀 具有封閉的邊界（表面具有封閉的邊界（表面) 內部連通內部連通 占據有限的空間占據有限的空間 經過運算后，仍然是有效的物體經過運算后，仍然是有效的物體7實體的定義（實體的定義（2/4） 內點內點 邊界點邊界點 取內點運算取內點運算i 取閉包運算取閉包運算c 正則運算正則運算rAicAr8實體的定義（實體的定義（3/4） 正則點集正則點集 稱為稱為A的正則點集的正則點集 稱稱A為正則點集，如果它滿足為正則點集，如果它滿足 問題：正則點集是實體？問

5、題：正則點集是實體？ArAAr9實體的定義（實體的定義（4/4） 實體的定義實體的定義可計算的條件可計算的條件 正則點集正則點集 表面是二維流形表面是二維流形 二維流形二維流形 其上任意一點存在充分小的領域與圓盤同構其上任意一點存在充分小的領域與圓盤同構（存在連續的一一映射）（存在連續的一一映射）10正則集合運算（正則集合運算（1/2） 為什么需要正則集合運算為什么需要正則集合運算 集合運算式構造復雜物體的有效方法集合運算式構造復雜物體的有效方法 普通的集合運算會產生無效物體普通的集合運算會產生無效物體11正則集合運算（正則集合運算（2/2） 正則集合運算的定義正則集合運算的定義 正則并正則并

6、 正則交正則交 正則差正則差)(*BopArBopA)(*BopArBA)(*BopArBA)(*BopArBA12特征表示特征表示 用一組特征參數表示一組類似的物體用一組特征參數表示一組類似的物體 特征包括形狀特征、材料特征等特征包括形狀特征、材料特征等 適用于工業上標準件的表示適用于工業上標準件的表示13空間分割表示（空間分割表示（1/8） 空間位置枚舉表示空間位置枚舉表示 選擇一個立方體空間，將他均勻劃分選擇一個立方體空間，將他均勻劃分14空間分割表示（空間分割表示（2/8） 用三維數組用三維數組CIJK表示物體，數組中的表示物體，數組中的元素與單位小立方體一一對應元素與單位小立方體一一

7、對應 當當CIjk = 1時，表示對應的小立方體被物體占據時，表示對應的小立方體被物體占據 當當CIjk = 0時，表示對應的小立方體沒有被物體占據時，表示對應的小立方體沒有被物體占據 優點優點 可以表示任何物體可以表示任何物體 容易實現物體間的集合運算容易實現物體間的集合運算 容易計算物體的整體性質，如體積等容易計算物體的整體性質，如體積等 缺點缺點 占用大量的存儲空間，如占用大量的存儲空間，如1024*1024*1024 = 1G bits 沒有邊界信息，不適于圖形顯示沒有邊界信息，不適于圖形顯示 對物體進行幾何變換困難，如非對物體進行幾何變換困難，如非90度的旋轉變換度的旋轉變換 是物體

8、的非精確表示是物體的非精確表示15空間分割表示（空間分割表示（3/8） 八叉樹表示八叉樹表示 對空間位置枚舉表示的空間分割方法作了改進：均對空間位置枚舉表示的空間分割方法作了改進：均勻分割勻分割 自適應分割自適應分割 八叉樹建立過程八叉樹建立過程八叉樹的根節點對應整個物體空間八叉樹的根節點對應整個物體空間如果它完全被物體占據，將該節點標記為如果它完全被物體占據，將該節點標記為F(Full)，算法結束；，算法結束；如果它內部沒有物體，將該節點標記為如果它內部沒有物體，將該節點標記為E(Empty)，算法結束；，算法結束；如果它被物體部分占據，將該節點標記為如果它被物體部分占據，將該節點標記為P(

9、Partial)，并將它分割成，并將它分割成8個子立方體，對每一個子立方體進行同樣的處理個子立方體，對每一個子立方體進行同樣的處理16空間分割表示（空間分割表示（4/8）17空間分割表示（空間分割表示（5/8）18空間分割表示（空間分割表示（6/8） 優點優點 可以表示任何物體可以表示任何物體 容易實現物體建的集合運算容易實現物體建的集合運算 容易計算物體的整體性質，如體積等容易計算物體的整體性質，如體積等 較空間位置枚舉表示占用的存貯空間少較空間位置枚舉表示占用的存貯空間少 缺點缺點 沒有邊界信息，不適于圖形顯示沒有邊界信息，不適于圖形顯示 對物體進行幾何變換困難對物體進行幾何變換困難 是物

10、體的非精確表示是物體的非精確表示19空間分割表示（空間分割表示（7/8） 單元分解表示單元分解表示 對空間位置枚舉表示的空間分割方法作了改進：單對空間位置枚舉表示的空間分割方法作了改進：單一體素一體素 多種體素多種體素 三種空間分割方法的比較三種空間分割方法的比較 空間位置枚舉表示空間位置枚舉表示-同樣大小同樣大小立方體粘合在一起表示物體立方體粘合在一起表示物體 八叉樹表示八叉樹表示-不同大小的立方體不同大小的立方體粘合在一起表示物體粘合在一起表示物體 單元分解表示單元分解表示-多種體素多種體素粘合在一起表示物體粘合在一起表示物體20空間分割表示（空間分割表示（8/8） 優點優點 表示簡單表示

11、簡單 容易實現幾何變換容易實現幾何變換 基本體素可以按需選擇，表示范圍較廣基本體素可以按需選擇，表示范圍較廣 可以精確表示物體可以精確表示物體 缺點缺點 物體的表示不唯一物體的表示不唯一 物體的有效性難以保證物體的有效性難以保證21推移表示推移表示(1/3) 將物體將物體A沿著軌跡沿著軌跡P推移得到物體推移得到物體B，稱，稱B為為sweep體體 平移平移sweep-將一個二維區域沿著一個將一個二維區域沿著一個矢量方向推移矢量方向推移22推移表示推移表示(2/3) 旋轉旋轉sweep-將一個二維區域繞旋轉軸將一個二維區域繞旋轉軸旋轉一周旋轉一周例子例子:3D MAX23推移表示推移表示(3/3)

12、 廣義廣義sweep 任意物體沿著任意軌跡推移任意物體沿著任意軌跡推移 推移過程中物體可以變形推移過程中物體可以變形 優點優點 表示簡單、直觀表示簡單、直觀 適合做圖形輸入手段適合做圖形輸入手段 缺點缺點 作幾何變換困難作幾何變換困難 對幾何運算不封閉對幾何運算不封閉例子：例子：3D MAX24邊界表示（邊界表示（1/5） 物體的邊界與物體一一對應，確定了物物體的邊界與物體一一對應，確定了物體的邊界也就確定了物體本身體的邊界也就確定了物體本身 用于表示物體邊界的有用于表示物體邊界的有-平面多邊形、平面多邊形、曲面片曲面片 什么是多面體？什么是多面體？ 平面多面體平面多面體 表面由平面多邊形組成

13、的多面體表面由平面多邊形組成的多面體 簡單多面體簡單多面體 與球拓撲同構與球拓撲同構25邊界表示（邊界表示（2/5） 歐拉公式歐拉公式 歐拉公式是必要條件歐拉公式是必要條件V-e+f=226邊界表示邊界表示(3/5) 廣義歐拉公式廣義歐拉公式V-e+f-r=2(s-h)r: 多面體表面上孔的個數s: 相互分離的多面體數h: 貫穿多面體的孔洞個數27邊界表示邊界表示(5/5) 優點優點 精確表示物體精確表示物體 表示能力強表示能力強 幾何變換容易幾何變換容易 適于顯示處理適于顯示處理 缺點缺點 表示復雜表示復雜 有效性難以保證有效性難以保證 集合運算復雜集合運算復雜28構造實體幾何表示（構造實體

14、幾何表示（1/2） 將物體表示成一棵二叉樹，稱為將物體表示成一棵二叉樹，稱為CSG樹樹 葉節點葉節點-基本體素，如立方體、圓柱體等基本體素，如立方體、圓柱體等 中間節點中間節點-正則集合運算正則集合運算29構造實體幾何表示（構造實體幾何表示（2/2) 優點優點 表示簡單、直觀表示簡單、直觀 也是物體的構造方法，可用作圖形輸入手段也是物體的構造方法，可用作圖形輸入手段 容易計算物體的整體性質容易計算物體的整體性質 物體的有效性自動得到保證物體的有效性自動得到保證 缺點缺點 表示不唯一表示不唯一 不能直接用于顯示不能直接用于顯示 求交計算麻煩求交計算麻煩30不規則形體的建模方法不規則形體的建模方法

15、 迭代函數系統迭代函數系統 基于文法的模型基于文法的模型 粒子系統粒子系統 動力系統動力系統31L系統（系統（1/4） 由生物學家由生物學家Lindenmayer創立創立 基本思想：基本思想： 用文法表示植物的拓撲結構用文法表示植物的拓撲結構 通過圖形學方法生成逼真的畫面通過圖形學方法生成逼真的畫面 DOL系統（確定的上下文無關的系統（確定的上下文無關的L系統）系統） 定義為三元組定義為三元組，其中，其中V-表示字母集合表示字母集合V*-表示表示V上所有單詞的集合上所有單詞的集合w-是一個非空單詞，稱為公理是一個非空單詞，稱為公理P-產生式集合產生式集合 ，使得，使得如果沒有明顯的產生式，則令如果沒有明顯的產生式，則令*,VxVaxa aa 32L系統（系統（2/4） 例子例子-Koch 雪花曲線雪花曲線 V：F,+,- w：F P：F-F-F+F-F 幾何解釋幾何解釋 F：向前畫一條線