第8章 幾何造型

1、計(jì)算機(jī)圖形學(xué)計(jì)算機(jī)圖形學(xué)武漢大學(xué)國際軟件學(xué)院武漢大學(xué)國際軟件學(xué)院 涂建光涂建光幾何造型2022年5月16日1時(shí)37分1Computer GraphicsComputer Graphics計(jì)計(jì) 算算 機(jī)機(jī) 圖圖 形形 學(xué)學(xué)概概 述述n幾何造型幾何造型:l利用點(diǎn)、線、面、體等利用點(diǎn)、線、面、體等幾何元素幾何元素，經(jīng)過平移、，經(jīng)過平移、旋轉(zhuǎn)、比例等旋轉(zhuǎn)、比例等幾何變換幾何變換和交、叉、并等和交、叉、并等集合運(yùn)集合運(yùn)算算，產(chǎn)生實(shí)際或想象的物體模型；，產(chǎn)生實(shí)際或想象的物體模型；l應(yīng)用：飛機(jī)外形設(shè)計(jì)，機(jī)械零件的計(jì)算機(jī)輔助應(yīng)用：飛機(jī)外形設(shè)計(jì)，機(jī)械零件的計(jì)算機(jī)輔助設(shè)計(jì)與制造，刀具、機(jī)器人運(yùn)動(dòng)的模擬等等。設(shè)計(jì)與

2、制造，刀具、機(jī)器人運(yùn)動(dòng)的模擬等等。n三維幾何造型的兩個(gè)主要分支：三維幾何造型的兩個(gè)主要分支：l曲面造型：曲面造型：研究在計(jì)算機(jī)內(nèi)如何描述一張曲面研究在計(jì)算機(jī)內(nèi)如何描述一張曲面,如何對(duì)它的形狀進(jìn)行交互式的顯示與控制；如何對(duì)它的形狀進(jìn)行交互式的顯示與控制；l實(shí)體造型：實(shí)體造型：研究如何在計(jì)算機(jī)內(nèi)定義、表示一研究如何在計(jì)算機(jī)內(nèi)定義、表示一個(gè)三維物體。個(gè)三維物體。2022年5月16日星期一2Computer GraphicsComputer Graphics計(jì)計(jì) 算算 機(jī)機(jī) 圖圖 形形 學(xué)學(xué)n 造型技術(shù)的發(fā)展造型技術(shù)的發(fā)展l6070年代初：早期的實(shí)體造型技術(shù)，共同的特點(diǎn)是年代初：早期的實(shí)體造型技術(shù)，共

3、同的特點(diǎn)是不支持精確的曲面表示，用多面體表示形體不支持精確的曲面表示，用多面體表示形體 l70年代：雕塑曲面技術(shù)的發(fā)展，出現(xiàn)了年代：雕塑曲面技術(shù)的發(fā)展，出現(xiàn)了Coons曲面、曲面、Bezier曲線和曲面、曲線和曲面、B樣條曲線和曲面等設(shè)計(jì)方法，在樣條曲線和曲面等設(shè)計(jì)方法，在汽車、航空和造船等行業(yè)得到了廣泛的應(yīng)用。汽車、航空和造船等行業(yè)得到了廣泛的應(yīng)用。l80年代末：出現(xiàn)了年代末：出現(xiàn)了NURBS曲線曲面設(shè)計(jì)方法，已有的曲線曲面設(shè)計(jì)方法，已有的曲線曲面表示方法，如曲線曲面表示方法，如Bezier方法、方法、B樣條方法等，可樣條方法等，可以用以用NURBS方法統(tǒng)一表示，且能精確表示二次曲線曲方法統(tǒng)

4、一表示，且能精確表示二次曲線曲面。由于面。由于NURBS的強(qiáng)大的表示能力，能夠精確表示形的強(qiáng)大的表示能力，能夠精確表示形體的幾何造型系統(tǒng)，紛紛采用了體的幾何造型系統(tǒng)，紛紛采用了NURBS方法，國際標(biāo)方法，國際標(biāo)準(zhǔn)化組織也已將準(zhǔn)化組織也已將NURBS作為定義工業(yè)產(chǎn)品形狀的唯一作為定義工業(yè)產(chǎn)品形狀的唯一數(shù)學(xué)方法。數(shù)學(xué)方法。 2022年5月16日星期一3Computer GraphicsComputer Graphics計(jì)計(jì) 算算 機(jī)機(jī) 圖圖 形形 學(xué)學(xué)n 正則形體正則形體l早期的幾何造型系統(tǒng)只支持正則的形體早期的幾何造型系統(tǒng)只支持正則的形體造型造型 l對(duì)于任一形體，如果它是對(duì)于任一形體，如果它是3

5、維歐氏空間維歐氏空間R3中非空、有界的封閉子集，且其表面任中非空、有界的封閉子集，且其表面任意一點(diǎn)的足夠小的鄰域在拓?fù)渖蠎?yīng)該是意一點(diǎn)的足夠小的鄰域在拓?fù)渖蠎?yīng)該是一個(gè)等價(jià)的封閉圓，我們稱該形體為正一個(gè)等價(jià)的封閉圓，我們稱該形體為正則形體，否則稱為非正則形體。則形體，否則稱為非正則形體。2022年5月16日星期一4Computer GraphicsComputer Graphics計(jì)計(jì) 算算 機(jī)機(jī) 圖圖 形形 學(xué)學(xué)l基于正則形體表示的實(shí)體造型形體只能基于正則形體表示的實(shí)體造型形體只能表示正則的三維表示正則的三維“體體”，低于三維的形，低于三維的形體是不能存在的。這樣，線框模型中的體是不能存在的。這

6、樣，線框模型中的“線線”，表面模型中的，表面模型中的“面面”，都是實(shí)，都是實(shí)體造型系統(tǒng)中所不能表示的。體造型系統(tǒng)中所不能表示的。l實(shí)際應(yīng)用中，有時(shí)候人們希望在系統(tǒng)中實(shí)際應(yīng)用中，有時(shí)候人們希望在系統(tǒng)中也能處理象形體中心軸、剖切平面這樣也能處理象形體中心軸、剖切平面這樣低于三維的形體，這就要求造型系統(tǒng)的低于三維的形體，這就要求造型系統(tǒng)的數(shù)據(jù)結(jié)構(gòu)能統(tǒng)一表示線框、表面、實(shí)體數(shù)據(jù)結(jié)構(gòu)能統(tǒng)一表示線框、表面、實(shí)體模型。模型。2022年5月16日星期一5Computer GraphicsComputer Graphics計(jì)計(jì) 算算 機(jī)機(jī) 圖圖 形形 學(xué)學(xué)l形體的集合運(yùn)算（并、交、差）是構(gòu)造形體的形體的集合運(yùn)算

7、（并、交、差）是構(gòu)造形體的基本方法基本方法l正則造型和非正則造型（非正則造型是主流）正則造型和非正則造型（非正則造型是主流）2022年5月16日星期一6Computer GraphicsComputer Graphics計(jì)計(jì) 算算 機(jī)機(jī) 圖圖 形形 學(xué)學(xué)坐坐 標(biāo)標(biāo) 系系n 造型坐標(biāo)系（局部坐標(biāo)系）造型坐標(biāo)系（局部坐標(biāo)系）n 用戶坐標(biāo)系用戶坐標(biāo)系l直角坐標(biāo)系（左手系，右手系）直角坐標(biāo)系（左手系，右手系）l仿射坐標(biāo)系仿射坐標(biāo)系l圓柱坐標(biāo)系圓柱坐標(biāo)系l球坐標(biāo)系球坐標(biāo)系l極坐標(biāo)系極坐標(biāo)系n 觀察坐標(biāo)系觀察坐標(biāo)系n 規(guī)格化的設(shè)備坐標(biāo)系規(guī)格化的設(shè)備坐標(biāo)系n 設(shè)備坐標(biāo)系設(shè)備坐標(biāo)系2022年5月16日星期一7

8、Computer GraphicsComputer Graphics計(jì)計(jì) 算算 機(jī)機(jī) 圖圖 形形 學(xué)學(xué)幾何元素幾何元素n點(diǎn)（點(diǎn)（Vertex）l控制點(diǎn)，型值點(diǎn)，插值點(diǎn)控制點(diǎn)，型值點(diǎn)，插值點(diǎn)l點(diǎn)通過它在空間中的位置來表示。一維空間的點(diǎn)通過它在空間中的位置來表示。一維空間的點(diǎn)用一元組（點(diǎn)用一元組（t）表示；二維空間中的的點(diǎn)用二）表示；二維空間中的的點(diǎn)用二元組（元組（x,y）表示；三維空間中的點(diǎn)用三元組）表示；三維空間中的點(diǎn)用三元組（x,y,z）表示。）表示。n維空間中的點(diǎn)在齊次坐標(biāo)下維空間中的點(diǎn)在齊次坐標(biāo)下用（用（n+1）元組（）元組（x1， x2，xn，w）表示。）表示。l點(diǎn)是幾何造型中的最基本

9、的元素，許多其它形點(diǎn)是幾何造型中的最基本的元素，許多其它形體都可以用有序的點(diǎn)集表示。體都可以用有序的點(diǎn)集表示。l在正則形體定義中，不允許孤立的點(diǎn)存在。在正則形體定義中，不允許孤立的點(diǎn)存在。 2022年5月16日星期一8Computer GraphicsComputer Graphics計(jì)計(jì) 算算 機(jī)機(jī) 圖圖 形形 學(xué)學(xué)n邊（邊（Edge）l面的邊界或者幾個(gè)面（包括平面和曲面）的交面的邊界或者幾個(gè)面（包括平面和曲面）的交l正則形體：一條邊只能是兩個(gè)面的交集正則形體：一條邊只能是兩個(gè)面的交集l非正則形體：既可以是多個(gè)面的交集，也可以非正則形體：既可以是多個(gè)面的交集，也可以是一張孤立的平面或曲面的邊

10、界是一張孤立的平面或曲面的邊界l邊可以是直線或曲線，它的形狀由邊的幾何信邊可以是直線或曲線，它的形狀由邊的幾何信息來表示息來表示l邊有方向，它由起點(diǎn)和終點(diǎn)來界定邊有方向，它由起點(diǎn)和終點(diǎn)來界定l在正則形體定義中，不允許孤立的邊存在在正則形體定義中，不允許孤立的邊存在 2022年5月16日星期一9Computer GraphicsComputer Graphics計(jì)計(jì) 算算 機(jī)機(jī) 圖圖 形形 學(xué)學(xué)n環(huán)（環(huán)（Loop）l由一系列首尾相連的有向邊組成的封閉邊界由一系列首尾相連的有向邊組成的封閉邊界l環(huán)中的邊不能相交，并且相鄰的兩條邊共享一環(huán)中的邊不能相交，并且相鄰的兩條邊共享一個(gè)端點(diǎn)個(gè)端點(diǎn)l環(huán)有方向、

11、內(nèi)外之分。外環(huán)邊通常按逆時(shí)針方環(huán)有方向、內(nèi)外之分。外環(huán)邊通常按逆時(shí)針方向排序，內(nèi)環(huán)邊通常按順時(shí)針方向排序，這樣，向排序，內(nèi)環(huán)邊通常按順時(shí)針方向排序，這樣，使得環(huán)的使得環(huán)的“內(nèi)部內(nèi)部”始終位于環(huán)的左側(cè)始終位于環(huán)的左側(cè)l環(huán)主要用于定義面，包括帶一個(gè)或多個(gè)孔的面環(huán)主要用于定義面，包括帶一個(gè)或多個(gè)孔的面 2022年5月16日星期一10Computer GraphicsComputer Graphics計(jì)計(jì) 算算 機(jī)機(jī) 圖圖 形形 學(xué)學(xué)n面（面（Face）l由一個(gè)外環(huán)和由一個(gè)外環(huán)和n（n0）個(gè)內(nèi)環(huán)來表示）個(gè)內(nèi)環(huán)來表示l內(nèi)環(huán)完全在外環(huán)之內(nèi)內(nèi)環(huán)完全在外環(huán)之內(nèi)l每個(gè)環(huán)既不能自相交，也不能與其它環(huán)相交每個(gè)環(huán)既不

12、能自相交，也不能與其它環(huán)相交l根據(jù)環(huán)的定義，在面上沿環(huán)的方向前進(jìn)，左側(cè)根據(jù)環(huán)的定義，在面上沿環(huán)的方向前進(jìn)，左側(cè)總在面內(nèi)，右側(cè)總在面外總在面內(nèi)，右側(cè)總在面外l面有方向性，一般用其外法矢方向作為該面的面有方向性，一般用其外法矢方向作為該面的正向正向l面的形狀由它的幾何信息來表示，可以是平面面的形狀由它的幾何信息來表示，可以是平面或曲面或曲面l在正則形體定義中，也不允許孤立的面存在。在正則形體定義中，也不允許孤立的面存在。 2022年5月16日星期一11Computer GraphicsComputer Graphics計(jì)計(jì) 算算 機(jī)機(jī) 圖圖 形形 學(xué)學(xué)n體（體（Body）l是用面的并集來表示的是用

13、面的并集來表示的l用于定義體的面形成一個(gè)封閉的邊界用于定義體的面形成一個(gè)封閉的邊界l在正則幾何造型系統(tǒng)中，要求體必須是正則的。在正則幾何造型系統(tǒng)中，要求體必須是正則的。n體素（體素（voxel ）l來源：從實(shí)際形體中選擇、參數(shù)輪廓線掃描產(chǎn)來源：從實(shí)際形體中選擇、參數(shù)輪廓線掃描產(chǎn)生、代數(shù)半空間定義生、代數(shù)半空間定義2022年5月16日星期一12Computer GraphicsComputer Graphics計(jì)計(jì) 算算 機(jī)機(jī) 圖圖 形形 學(xué)學(xué)表示形體的兩種模型表示形體的兩種模型2022年5月16日星期一13Computer GraphicsComputer Graphics計(jì)計(jì) 算算 機(jī)機(jī) 圖

14、圖 形形 學(xué)學(xué)表示形體的數(shù)據(jù)模型表示形體的數(shù)據(jù)模型n線框模型線框模型l用頂點(diǎn)和棱邊來表示形體用頂點(diǎn)和棱邊來表示形體2022年5月16日星期一14V8V1V2V8V7V6V5V4V3e1e2e4e3e12e11e10e9e5e6e7e8長方體V7V4e1e2e11e12V3V1V2(a)(b)Computer GraphicsComputer Graphics計(jì)計(jì) 算算 機(jī)機(jī) 圖圖 形形 學(xué)學(xué)l線框模型缺點(diǎn)線框模型缺點(diǎn)u數(shù)據(jù)結(jié)構(gòu)包含的信息有限，無法實(shí)現(xiàn)圖形數(shù)據(jù)結(jié)構(gòu)包含的信息有限，無法實(shí)現(xiàn)圖形的自動(dòng)消隱；的自動(dòng)消隱； u同一數(shù)據(jù)結(jié)構(gòu)可能對(duì)應(yīng)多個(gè)物體，產(chǎn)生二同一數(shù)據(jù)結(jié)構(gòu)可能對(duì)應(yīng)多個(gè)物體，產(chǎn)生二義性；

15、義性； u無法表達(dá)連續(xù)的幾何信息，不能明確的定無法表達(dá)連續(xù)的幾何信息，不能明確的定義點(diǎn)和幾何物體之間的關(guān)系；義點(diǎn)和幾何物體之間的關(guān)系； u在生成復(fù)雜物體的圖形時(shí)，采用線框式的在生成復(fù)雜物體的圖形時(shí)，采用線框式的數(shù)據(jù)結(jié)構(gòu)要求輸入大量的初等數(shù)據(jù)，這不數(shù)據(jù)結(jié)構(gòu)要求輸入大量的初等數(shù)據(jù)，這不僅加重了用戶的負(fù)擔(dān)，而且很難保證數(shù)據(jù)僅加重了用戶的負(fù)擔(dān)，而且很難保證數(shù)據(jù)的有效性和統(tǒng)一性。的有效性和統(tǒng)一性。 2022年5月16日星期一15Computer GraphicsComputer Graphics計(jì)計(jì) 算算 機(jī)機(jī) 圖圖 形形 學(xué)學(xué)n表面模型表面模型l用有向棱邊圍成的部分來定義物體表面，由面用有向棱邊圍成的

16、部分來定義物體表面，由面的集合來定義物體。的集合來定義物體。l表面模型是在線框模型的基礎(chǔ)上，增加了有關(guān)表面模型是在線框模型的基礎(chǔ)上，增加了有關(guān)生成三維物體各表面的數(shù)據(jù)信息，這些信息包生成三維物體各表面的數(shù)據(jù)信息，這些信息包括定義表面的環(huán)、表面特征、棱邊連接方向等括定義表面的環(huán)、表面特征、棱邊連接方向等內(nèi)容；內(nèi)容；l可以滿足面和面的求交、線面消隱、明暗色彩可以滿足面和面的求交、線面消隱、明暗色彩圖、數(shù)控加工等應(yīng)用問題的需要；圖、數(shù)控加工等應(yīng)用問題的需要；l缺點(diǎn)：沒有說明形體究竟在面的哪一側(cè)。缺點(diǎn)：沒有說明形體究竟在面的哪一側(cè)。2022年5月16日星期一16Computer GraphicsCom

17、puter Graphics計(jì)計(jì) 算算 機(jī)機(jī) 圖圖 形形 學(xué)學(xué)n實(shí)體模型實(shí)體模型l明確定義了表面的哪一側(cè)存在實(shí)體；明確定義了表面的哪一側(cè)存在實(shí)體；l在表面模型的基礎(chǔ)上可用三種方法來定義：在表面模型的基礎(chǔ)上可用三種方法來定義：（a）在定義表面的同時(shí)，給出實(shí)體存在側(cè)的一點(diǎn)）在定義表面的同時(shí)，給出實(shí)體存在側(cè)的一點(diǎn)P；（b）直接用表面的外法矢來指明實(shí)體存在的一側(cè)；）直接用表面的外法矢來指明實(shí)體存在的一側(cè)；（c）是用有向棱邊的方向表示表面的外法矢方向，）是用有向棱邊的方向表示表面的外法矢方向，右手法則確定外法矢量，圖（右手法則確定外法矢量，圖（d）所示。）所示。 2022年5月16日星期一17(a)(c

18、)(b)(d)PComputer GraphicsComputer Graphics計(jì)計(jì) 算算 機(jī)機(jī) 圖圖 形形 學(xué)學(xué)常用的形體表示方式常用的形體表示方式 n 前面三種表示模型是一種廣義的概念，不反映實(shí)前面三種表示模型是一種廣義的概念，不反映實(shí)體在計(jì)算機(jī)內(nèi)部，或?qū)ψ罱K用戶而言所用的具體體在計(jì)算機(jī)內(nèi)部，或?qū)ψ罱K用戶而言所用的具體表示方式。針對(duì)不同的表示方式，幾何造型系統(tǒng)表示方式。針對(duì)不同的表示方式，幾何造型系統(tǒng)采用的數(shù)據(jù)結(jié)構(gòu)也有所不同，常用的有：采用的數(shù)據(jù)結(jié)構(gòu)也有所不同，常用的有：l構(gòu)造實(shí)體幾何表示：以一組簡單的物體通過正則集合構(gòu)造實(shí)體幾何表示：以一組簡單的物體通過正則集合運(yùn)算來構(gòu)造新的物體，這

19、些簡單的物體稱為基本體素，運(yùn)算來構(gòu)造新的物體，這些簡單的物體稱為基本體素，可以是立方體、長方體、圓柱體、圓錐體等?？梢允橇⒎襟w、長方體、圓柱體、圓錐體等。l邊界表示：通過描述構(gòu)成實(shí)體邊界的點(diǎn)、邊、面而達(dá)邊界表示：通過描述構(gòu)成實(shí)體邊界的點(diǎn)、邊、面而達(dá)到表示實(shí)體的目的，實(shí)體與其邊界一一對(duì)應(yīng)。到表示實(shí)體的目的，實(shí)體與其邊界一一對(duì)應(yīng)。l空間分割表示：將基本體素通過空間分割表示：將基本體素通過“粘合粘合”構(gòu)造新的物構(gòu)造新的物體。單元分解表示、八叉樹表示等屬于這種表示方法，體。單元分解表示、八叉樹表示等屬于這種表示方法，特征表示法也可看作這種表示方法的特例。特征表示法也可看作這種表示方法的特例。2022年

20、5月16日星期一18Computer GraphicsComputer Graphics計(jì)計(jì) 算算 機(jī)機(jī) 圖圖 形形 學(xué)學(xué)構(gòu)造實(shí)體幾何表示構(gòu)造實(shí)體幾何表示n 構(gòu)造實(shí)體幾何（構(gòu)造實(shí)體幾何（Construction Solid Geometry）表示，或稱）表示，或稱CSG樹表示樹表示n 是一種應(yīng)用廣泛的物體表示與構(gòu)造方法，它的是一種應(yīng)用廣泛的物體表示與構(gòu)造方法，它的基本思想是將一些簡單的基本體素通過正則集基本思想是將一些簡單的基本體素通過正則集合運(yùn)算來構(gòu)造、表示新的物體。合運(yùn)算來構(gòu)造、表示新的物體。2022年5月16日星期一19（b）CSG樹（a）實(shí)體模型*Computer GraphicsCo

21、mputer Graphics計(jì)計(jì) 算算 機(jī)機(jī) 圖圖 形形 學(xué)學(xué)2022年5月16日星期一20Computer GraphicsComputer Graphics計(jì)計(jì) 算算 機(jī)機(jī) 圖圖 形形 學(xué)學(xué)2022年5月16日星期一21Computer GraphicsComputer Graphics計(jì)計(jì) 算算 機(jī)機(jī) 圖圖 形形 學(xué)學(xué)lCSG樹表示的優(yōu)點(diǎn)：樹表示的優(yōu)點(diǎn)：u數(shù)據(jù)結(jié)構(gòu)簡單，數(shù)據(jù)量小，內(nèi)部數(shù)據(jù)管理容易；數(shù)據(jù)結(jié)構(gòu)簡單，數(shù)據(jù)量小，內(nèi)部數(shù)據(jù)管理容易；u每個(gè)每個(gè)CSG樹都能表達(dá)有效的形體，無二義性；樹都能表達(dá)有效的形體，無二義性；u可方便的轉(zhuǎn)換成可方便的轉(zhuǎn)換成BRep表示，從而支持更廣泛的表示，從而

22、支持更廣泛的應(yīng)用；應(yīng)用；u容易編輯。容易編輯。lCSG樹表示的缺點(diǎn)：樹表示的缺點(diǎn)：u產(chǎn)生、修改形體的操作種類有限，集合運(yùn)算對(duì)形產(chǎn)生、修改形體的操作種類有限，集合運(yùn)算對(duì)形體的局部操作不易實(shí)現(xiàn)；體的局部操作不易實(shí)現(xiàn)；u繪制困難。繪制困難。2022年5月16日星期一22Computer GraphicsComputer Graphics計(jì)計(jì) 算算 機(jī)機(jī) 圖圖 形形 學(xué)學(xué)邊界表示法邊界表示法n邊界表示法邊界表示法(Boundary Representation，BRep):n邊界就是物體內(nèi)部點(diǎn)與外部點(diǎn)的分界面。邊界就是物體內(nèi)部點(diǎn)與外部點(diǎn)的分界面。 2022年5月16日星期一23(a)實(shí)體模型(b)模型

23、的邊界Computer GraphicsComputer Graphics計(jì)計(jì) 算算 機(jī)機(jī) 圖圖 形形 學(xué)學(xué)p邊界表示法與傳統(tǒng)的工程繪圖有密切的聯(lián)系。邊界表示法與傳統(tǒng)的工程繪圖有密切的聯(lián)系。u輸入兩個(gè)點(diǎn)，即可以通過兩個(gè)給定點(diǎn)連接一條線。輸入兩個(gè)點(diǎn)，即可以通過兩個(gè)給定點(diǎn)連接一條線。u若干條首尾相接的線段若干條首尾相接的線段(即棱邊，在計(jì)算機(jī)圖形學(xué)中即棱邊，在計(jì)算機(jī)圖形學(xué)中它們被定義成物體的相鄰表面的交線它們被定義成物體的相鄰表面的交線)可形成一個(gè)閉可形成一個(gè)閉合環(huán)，一個(gè)或多個(gè)環(huán)給出一個(gè)面的邊界。合環(huán)，一個(gè)或多個(gè)環(huán)給出一個(gè)面的邊界。u最后，若干個(gè)表面閉合后圍成一個(gè)最后，若干個(gè)表面閉合后圍成一個(gè)“體

24、體”。p 邊界表示法的一個(gè)很重要的特點(diǎn)是在該表示法中，邊界表示法的一個(gè)很重要的特點(diǎn)是在該表示法中，描述物體的信息包括幾何信息與拓?fù)湫畔蓚€(gè)方描述物體的信息包括幾何信息與拓?fù)湫畔蓚€(gè)方面。面。 2022年5月16日星期一24Computer GraphicsComputer Graphics計(jì)計(jì) 算算 機(jī)機(jī) 圖圖 形形 學(xué)學(xué)p拓?fù)湫畔⑼負(fù)湫畔?u物體的拓?fù)湫畔⑹侵肝矬w上所有的頂點(diǎn)、物體的拓?fù)湫畔⑹侵肝矬w上所有的頂點(diǎn)、棱邊、表面間是怎樣連接的。棱邊、表面間是怎樣連接的。p幾何信息幾何信息 u物體的幾何信息指的是頂點(diǎn)、邊、面的物體的幾何信息指的是頂點(diǎn)、邊、面的位置、大小、形狀等幾何數(shù)據(jù)。位置、大小、

25、形狀等幾何數(shù)據(jù)。2022年5月16日星期一25Computer GraphicsComputer Graphics計(jì)計(jì) 算算 機(jī)機(jī) 圖圖 形形 學(xué)學(xué)n拓?fù)湫畔⑴c幾何信息分開表示有下述優(yōu)點(diǎn)：拓?fù)湫畔⑴c幾何信息分開表示有下述優(yōu)點(diǎn)：p便于具體查詢物體中各元素，獲取它們便于具體查詢物體中各元素，獲取它們的相關(guān)信息。的相關(guān)信息。 p容易支持對(duì)物體的各種局部操作。容易支持對(duì)物體的各種局部操作。 p對(duì)于具有相同拓?fù)浣Y(jié)構(gòu)而只是大小、尺對(duì)于具有相同拓?fù)浣Y(jié)構(gòu)而只是大小、尺寸不同的一類物體可以用統(tǒng)一的數(shù)據(jù)結(jié)寸不同的一類物體可以用統(tǒng)一的數(shù)據(jù)結(jié)構(gòu)加以表示構(gòu)加以表示 。 p便于在數(shù)據(jù)結(jié)構(gòu)上附加各種非幾何信息便于在數(shù)據(jù)結(jié)構(gòu)

26、上附加各種非幾何信息 。2022年5月16日星期一26Computer GraphicsComputer Graphics計(jì)計(jì) 算算 機(jī)機(jī) 圖圖 形形 學(xué)學(xué)nBrep表示的優(yōu)點(diǎn)：表示的優(yōu)點(diǎn)：l表示形體的點(diǎn)、邊、面等幾何元素是顯式表示表示形體的點(diǎn)、邊、面等幾何元素是顯式表示的，使得繪制形體的速度較快，而且比較容易的，使得繪制形體的速度較快，而且比較容易確定幾何元素間的連接關(guān)系；確定幾何元素間的連接關(guān)系；l容易支持對(duì)物體的各種局部操作；容易支持對(duì)物體的各種局部操作；l便于在數(shù)據(jù)結(jié)構(gòu)上附加各種非幾何信息，如精便于在數(shù)據(jù)結(jié)構(gòu)上附加各種非幾何信息，如精度、表面粗糙度等。度、表面粗糙度等。nBrep表示的

27、缺點(diǎn)：表示的缺點(diǎn)：l數(shù)據(jù)結(jié)構(gòu)復(fù)雜，需要大量的存儲(chǔ)空間，維護(hù)內(nèi)數(shù)據(jù)結(jié)構(gòu)復(fù)雜，需要大量的存儲(chǔ)空間，維護(hù)內(nèi)部數(shù)據(jù)結(jié)構(gòu)的程序比較復(fù)雜；部數(shù)據(jù)結(jié)構(gòu)的程序比較復(fù)雜；l不一定對(duì)應(yīng)一個(gè)有效形體，通常運(yùn)用歐拉操作不一定對(duì)應(yīng)一個(gè)有效形體，通常運(yùn)用歐拉操作來保證來保證Brep表示形體的有效性、正則性等。表示形體的有效性、正則性等。2022年5月16日星期一27Computer GraphicsComputer Graphics計(jì)計(jì) 算算 機(jī)機(jī) 圖圖 形形 學(xué)學(xué) 歐拉運(yùn)算歐拉運(yùn)算 n 歐拉運(yùn)算是三維物體邊界表示數(shù)歐拉運(yùn)算是三維物體邊界表示數(shù)據(jù)結(jié)構(gòu)的生成操作，它的每一種據(jù)結(jié)構(gòu)的生成操作，它的每一種運(yùn)算所構(gòu)運(yùn)算所構(gòu) 建的

28、拓?fù)湓睾屯負(fù)潢P(guān)建的拓?fù)湓睾屯負(fù)潢P(guān)系均要求滿足系均要求滿足 歐拉公式：歐拉公式：n 以保證所建邊界表示的有效性。以保證所建邊界表示的有效性。式中式中v、e、f分別表示物體上的頂分別表示物體上的頂點(diǎn)、棱邊和表面的數(shù)目，而點(diǎn)、棱邊和表面的數(shù)目，而r、s、h分別表示物體表面的內(nèi)環(huán)數(shù)，分別表示物體表面的內(nèi)環(huán)數(shù)，不相連接的物體個(gè)數(shù)以及物體的不相連接的物體個(gè)數(shù)以及物體的通孔數(shù)目。通孔數(shù)目。2022年5月16日星期一282()vefshr v=24, e=36f=15, r=3s=1, h=1Computer GraphicsComputer Graphics計(jì)計(jì) 算算 機(jī)機(jī) 圖圖 形形 學(xué)學(xué)n滿足歐拉公

29、式的歐拉運(yùn)算多種多樣，下滿足歐拉公式的歐拉運(yùn)算多種多樣，下表列出了五個(gè)具有鮮明幾何意義的基本表列出了五個(gè)具有鮮明幾何意義的基本歐拉操作歐拉操作2022年5月16日星期一29Computer GraphicsComputer Graphics計(jì)計(jì) 算算 機(jī)機(jī) 圖圖 形形 學(xué)學(xué)nBRep的半邊數(shù)據(jù)結(jié)構(gòu)：的半邊數(shù)據(jù)結(jié)構(gòu)：l在構(gòu)成多面體的三要素在構(gòu)成多面體的三要素(頂點(diǎn)、邊、面頂點(diǎn)、邊、面)中，中，半邊數(shù)據(jù)結(jié)構(gòu)以邊為核心。半邊數(shù)據(jù)結(jié)構(gòu)以邊為核心。l為了方便表達(dá)拓?fù)潢P(guān)系，它將一條邊表為了方便表達(dá)拓?fù)潢P(guān)系，它將一條邊表示成拓?fù)湟饬x上方向相反的兩條示成拓?fù)湟饬x上方向相反的兩條“半半邊邊”，所以稱為半邊數(shù)據(jù)結(jié)

30、構(gòu)。，所以稱為半邊數(shù)據(jù)結(jié)構(gòu)。l半邊數(shù)據(jù)結(jié)構(gòu)在拓?fù)渖戏譃槲鍌€(gè)層次，半邊數(shù)據(jù)結(jié)構(gòu)在拓?fù)渖戏譃槲鍌€(gè)層次，即體即體-面面-環(huán)環(huán)-半邊半邊-頂點(diǎn)。頂點(diǎn)。2022年5月16日星期一30Computer GraphicsComputer Graphics計(jì)計(jì) 算算 機(jī)機(jī) 圖圖 形形 學(xué)學(xué)2022年5月16日星期一31多面體面 頂點(diǎn) 環(huán)半邊prevsnextsprevfprevlnextfnextlprevvnextprvfloopsfsolidsfacesnextvwloopledgelfacevedge vtx邊sedgesprevenexte右環(huán)邊左半邊左環(huán)右半邊左指針右指針v2v2v1v1Comput

31、er GraphicsComputer Graphics計(jì)計(jì) 算算 機(jī)機(jī) 圖圖 形形 學(xué)學(xué)基于空間分割的八叉樹表示基于空間分割的八叉樹表示n一種層次數(shù)據(jù)結(jié)構(gòu)一種層次數(shù)據(jù)結(jié)構(gòu)n表達(dá)方法：表達(dá)方法：l首先在空間中定義一個(gè)能夠包含所表示物體的首先在空間中定義一個(gè)能夠包含所表示物體的立方體，立方體的三條棱邊分別與立方體，立方體的三條棱邊分別與x, y, z軸平軸平行，邊長為行，邊長為2n；2022年5月16日星期一32zx4051673yp若立方體內(nèi)空間完全由所表若立方體內(nèi)空間完全由所表示的物體占據(jù)，則物體可用示的物體占據(jù)，則物體可用這個(gè)立方體予以表示，否則這個(gè)立方體予以表示，否則將立方體等分為八個(gè)小

32、塊，將立方體等分為八個(gè)小塊，每塊仍為一個(gè)小立方體，其每塊仍為一個(gè)小立方體，其邊長為原立方體邊長的邊長為原立方體邊長的1/2，并依次編號(hào)為并依次編號(hào)為0,1,2,7； Computer GraphicsComputer Graphics計(jì)計(jì) 算算 機(jī)機(jī) 圖圖 形形 學(xué)學(xué)l若某一小立方體的體內(nèi)空間全部被所表示物體若某一小立方體的體內(nèi)空間全部被所表示物體占據(jù)，則將此立方體標(biāo)識(shí)為占據(jù)，則將此立方體標(biāo)識(shí)為“FULL” ;l若它與所表示物體無交，則該立方體被標(biāo)志為若它與所表示物體無交，則該立方體被標(biāo)志為“EMPTY” ;l否則將它標(biāo)識(shí)為否則將它標(biāo)識(shí)為“PARTIAL”，并繼續(xù)分割下，并繼續(xù)分割下去；去；l

33、依此方式，物體在計(jì)算機(jī)內(nèi)可表示為一棵八叉依此方式，物體在計(jì)算機(jī)內(nèi)可表示為一棵八叉樹。凡是標(biāo)識(shí)為樹。凡是標(biāo)識(shí)為“FULL”或或“EMPTY”的立方的立方體均為終端節(jié)點(diǎn)，而標(biāo)識(shí)為體均為終端節(jié)點(diǎn)，而標(biāo)識(shí)為“PARTIAL”的立的立方體為非終端節(jié)點(diǎn)；方體為非終端節(jié)點(diǎn)；l當(dāng)分割生成的每一小立方體的邊長為單位長時(shí)當(dāng)分割生成的每一小立方體的邊長為單位長時(shí)，分割即告終止。此時(shí)，應(yīng)將每一標(biāo)識(shí)為，分割即告終止。此時(shí)，應(yīng)將每一標(biāo)識(shí)為“PARTIAL”的小立方體重新標(biāo)識(shí)為的小立方體重新標(biāo)識(shí)為“FULL”或或“EMPTY”。 2022年5月16日星期一33Computer GraphicsComputer Graphi

34、cs計(jì)計(jì) 算算 機(jī)機(jī) 圖圖 形形 學(xué)學(xué)2022年5月16日星期一34Computer GraphicsComputer Graphics計(jì)計(jì) 算算 機(jī)機(jī) 圖圖 形形 學(xué)學(xué)2022年5月16日星期一35Computer GraphicsComputer Graphics計(jì)計(jì) 算算 機(jī)機(jī) 圖圖 形形 學(xué)學(xué)l八叉樹表示的優(yōu)點(diǎn)：八叉樹表示的優(yōu)點(diǎn)：u容易實(shí)現(xiàn)物體之間的正則集合運(yùn)算。由于物容易實(shí)現(xiàn)物體之間的正則集合運(yùn)算。由于物體的八叉樹表示就是由它內(nèi)部含有的大大小體的八叉樹表示就是由它內(nèi)部含有的大大小小的立方體（稱體元）組成，因此對(duì)物體執(zhí)小的立方體（稱體元）組成，因此對(duì)物體執(zhí)行并、交、叉運(yùn)算時(shí)，只需同時(shí)遍

35、歷參加集行并、交、叉運(yùn)算時(shí)，只需同時(shí)遍歷參加集合運(yùn)算的兩物體相應(yīng)的八叉樹，就可以獲得合運(yùn)算的兩物體相應(yīng)的八叉樹，就可以獲得拼合的八叉樹，而無需進(jìn)行復(fù)雜的求交運(yùn)算；拼合的八叉樹，而無需進(jìn)行復(fù)雜的求交運(yùn)算；u容易實(shí)現(xiàn)隱藏線和隱藏面的消除。消除隱藏容易實(shí)現(xiàn)隱藏線和隱藏面的消除。消除隱藏線和隱藏面的關(guān)鍵是對(duì)物體（及其不同部分）線和隱藏面的關(guān)鍵是對(duì)物體（及其不同部分）按其距視點(diǎn)的遠(yuǎn)近排序，而在八叉樹表示中，按其距視點(diǎn)的遠(yuǎn)近排序，而在八叉樹表示中，各結(jié)點(diǎn)之間的序的關(guān)系是簡單且固定的，使各結(jié)點(diǎn)之間的序的關(guān)系是簡單且固定的，使得計(jì)算比較容易；得計(jì)算比較容易；2022年5月16日星期一36Computer Gr

36、aphicsComputer Graphics計(jì)計(jì) 算算 機(jī)機(jī) 圖圖 形形 學(xué)學(xué)u易計(jì)算物體的整體性質(zhì)，如體積、質(zhì)量等。易計(jì)算物體的整體性質(zhì)，如體積、質(zhì)量等。在計(jì)算物體的體積或質(zhì)量時(shí)，只需從物體的在計(jì)算物體的體積或質(zhì)量時(shí)，只需從物體的八叉樹的根節(jié)點(diǎn)開始，逐層計(jì)算所表示物體八叉樹的根節(jié)點(diǎn)開始，逐層計(jì)算所表示物體的最大和最小體積（質(zhì)量）。當(dāng)標(biāo)識(shí)為的最大和最小體積（質(zhì)量）。當(dāng)標(biāo)識(shí)為“PARTIAL”的體元以的體元以“FULL”計(jì)時(shí)得最大計(jì)時(shí)得最大體積（質(zhì)量），若不計(jì)入時(shí)得最小體積（質(zhì)體積（質(zhì)量），若不計(jì)入時(shí)得最小體積（質(zhì)量）。由于樹的每一層都是在一定精度下對(duì)量）。由于樹的每一層都是在一定精度下對(duì)所表

37、示物體的一種近似，因此若所得的最大所表示物體的一種近似，因此若所得的最大最小體積（質(zhì)量）之差小于給定的允差，計(jì)最小體積（質(zhì)量）之差小于給定的允差，計(jì)算即結(jié)束。算即結(jié)束。 2022年5月16日星期一37Computer GraphicsComputer Graphics計(jì)計(jì) 算算 機(jī)機(jī) 圖圖 形形 學(xué)學(xué)l八叉樹表示的缺點(diǎn)：八叉樹表示的缺點(diǎn)：u不能精確地表示一個(gè)物體，并且對(duì)八叉樹表不能精確地表示一個(gè)物體，并且對(duì)八叉樹表示的物體做任意的幾何變換也比較困難；示的物體做任意的幾何變換也比較困難；u它占用的存儲(chǔ)空間很多，這是因?yàn)槊恳惑w元它占用的存儲(chǔ)空間很多，這是因?yàn)槊恳惑w元都是立方體，且體元各表面分別與三

38、個(gè)坐標(biāo)都是立方體，且體元各表面分別與三個(gè)坐標(biāo)平面平行。只有當(dāng)所表示的物體具有相似的平面平行。只有當(dāng)所表示的物體具有相似的形狀和位置時(shí)，才會(huì)獲得簡潔的八叉樹表示。形狀和位置時(shí)，才會(huì)獲得簡潔的八叉樹表示。在每一個(gè)八叉樹結(jié)點(diǎn)中，除去一個(gè)描述該結(jié)在每一個(gè)八叉樹結(jié)點(diǎn)中，除去一個(gè)描述該結(jié)點(diǎn)性質(zhì)（點(diǎn)性質(zhì)（FULL或或EMPTY等）的域外，還存等）的域外，還存儲(chǔ)它指向父結(jié)點(diǎn)及八個(gè)子結(jié)點(diǎn)地址的指針，儲(chǔ)它指向父結(jié)點(diǎn)及八個(gè)子結(jié)點(diǎn)地址的指針，從而使物體的八叉樹表示在空間花費(fèi)上十分從而使物體的八叉樹表示在空間花費(fèi)上十分昂貴。實(shí)際上，八叉樹表示是以存儲(chǔ)空間換昂貴。實(shí)際上，八叉樹表示是以存儲(chǔ)空間換取了算法的效率。取了算法的效率。 2022年5月16日星期一38Computer GraphicsComputer Graphics計(jì)計(jì) 算算 機(jī)機(jī) 圖圖 形形 學(xué)學(xué)構(gòu)造形體的構(gòu)造形體的SweepSweep運(yùn)算運(yùn)算n一個(gè)在空間移動(dòng)的幾何集合，可掃描出一一個(gè)在空間移動(dòng)的幾何集合，可掃描出一個(gè)實(shí)體。它是以沿著某種軌跡移動(dòng)點(diǎn)、曲個(gè)實(shí)體。它是以沿著某種軌跡移動(dòng)點(diǎn)、曲線或曲面為基礎(chǔ)的，這一過程所產(chǎn)生的軌線或曲面為基礎(chǔ)的，這一過程所產(chǎn)生的軌跡定義為一維、二維或三維物體。跡定義為一維、二維或三維物體。n