chp三維形體的實(shí)體表示

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

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

3、何信包含了描述一個(gè)實(shí)體所需的較多信息，如幾何信息、拓?fù)湫畔⑾ⅰ⑼負(fù)湫畔?過程模型 以一個(gè)過程和相應(yīng)的控制參數(shù)描述以一個(gè)過程和相應(yīng)的控制參數(shù)描述 例如例如 用一些控制參數(shù)和一個(gè)生成規(guī)則描述的植物用一些控制參數(shù)和一個(gè)生成規(guī)則描述的植物 以一個(gè)數(shù)據(jù)文件和一段代碼的形式存在以一個(gè)數(shù)據(jù)文件和一段代碼的形式存在 包括包括-粒子系統(tǒng)、粒子系統(tǒng)、L系統(tǒng)、迭代函數(shù)系統(tǒng)等系統(tǒng)、迭代函數(shù)系統(tǒng)等5表示形體的兩種模型（表示形體的兩種模型（4/4） 模型分類模型分類6實(shí)體的定義（實(shí)體的定義（1/4） 抽象帶來的問題抽象帶來的問題 計(jì)算機(jī)中表示的物體是無(wú)效的計(jì)算機(jī)中表示的物體是無(wú)效的 不能夠客觀存在不能夠客觀存在 為什么要

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

5、題：正則點(diǎn)集是實(shí)體？ArAAr9實(shí)體的定義（實(shí)體的定義（4/4） 實(shí)體的定義實(shí)體的定義可計(jì)算的條件可計(jì)算的條件 正則點(diǎn)集正則點(diǎn)集 表面是二維流形表面是二維流形 二維流形二維流形 其上任意一點(diǎn)存在充分小的領(lǐng)域與圓盤同構(gòu)其上任意一點(diǎn)存在充分小的領(lǐng)域與圓盤同構(gòu)（存在連續(xù)的一一映射）（存在連續(xù)的一一映射）10正則集合運(yùn)算（正則集合運(yùn)算（1/2） 為什么需要正則集合運(yùn)算為什么需要正則集合運(yùn)算 集合運(yùn)算式構(gòu)造復(fù)雜物體的有效方法集合運(yùn)算式構(gòu)造復(fù)雜物體的有效方法 普通的集合運(yùn)算會(huì)產(chǎn)生無(wú)效物體普通的集合運(yùn)算會(huì)產(chǎn)生無(wú)效物體11正則集合運(yùn)算（正則集合運(yùn)算（2/2） 正則集合運(yùn)算的定義正則集合運(yùn)算的定義 正則并正則并

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

7、對(duì)應(yīng) 當(dāng)當(dāng)CIjk = 1時(shí)，表示對(duì)應(yīng)的小立方體被物體占據(jù)時(shí)，表示對(duì)應(yīng)的小立方體被物體占據(jù) 當(dāng)當(dāng)CIjk = 0時(shí)，表示對(duì)應(yīng)的小立方體沒有被物體占據(jù)時(shí)，表示對(duì)應(yīng)的小立方體沒有被物體占據(jù) 優(yōu)點(diǎn)優(yōu)點(diǎn) 可以表示任何物體可以表示任何物體 容易實(shí)現(xiàn)物體間的集合運(yùn)算容易實(shí)現(xiàn)物體間的集合運(yùn)算 容易計(jì)算物體的整體性質(zhì)，如體積等容易計(jì)算物體的整體性質(zhì)，如體積等 缺點(diǎn)缺點(diǎn) 占用大量的存儲(chǔ)空間，如占用大量的存儲(chǔ)空間，如1024*1024*1024 = 1G bits 沒有邊界信息，不適于圖形顯示沒有邊界信息，不適于圖形顯示 對(duì)物體進(jìn)行幾何變換困難，如非對(duì)物體進(jìn)行幾何變換困難，如非90度的旋轉(zhuǎn)變換度的旋轉(zhuǎn)變換 是物體

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

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

10、體的非精確表示是物體的非精確表示19空間分割表示（空間分割表示（7/8） 單元分解表示單元分解表示 對(duì)空間位置枚舉表示的空間分割方法作了改進(jìn)：?jiǎn)螌?duì)空間位置枚舉表示的空間分割方法作了改進(jìn)：?jiǎn)我惑w素一體素 多種體素多種體素 三種空間分割方法的比較三種空間分割方法的比較 空間位置枚舉表示空間位置枚舉表示-同樣大小同樣大小立方體粘合在一起表示物體立方體粘合在一起表示物體 八叉樹表示八叉樹表示-不同大小的立方體不同大小的立方體粘合在一起表示物體粘合在一起表示物體 單元分解表示單元分解表示-多種體素多種體素粘合在一起表示物體粘合在一起表示物體20空間分割表示（空間分割表示（8/8） 優(yōu)點(diǎn)優(yōu)點(diǎn) 表示簡(jiǎn)單表示

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

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

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

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

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