三維實(shí)體的表示

關(guān)于三維實(shí)體的表示第一頁(yè)，共六十二頁(yè)，2022年，8月28日2第七章三維實(shí)體的表示真實(shí)世界存在著千姿百態(tài)的物體，研究如何在建立恰當(dāng)?shù)哪Ｐ捅硎具@些物體的技術(shù)稱為造型技術(shù)——計(jì)算機(jī)圖形學(xué)研究的重要內(nèi)容之一。其中，實(shí)體造型技術(shù)關(guān)注表示實(shí)體的信息的完備性和可操作性，它是由于計(jì)算機(jī)輔助設(shè)計(jì)與制造的需要而發(fā)展起來(lái)的，現(xiàn)在已經(jīng)廣泛應(yīng)用于各種造型系統(tǒng)中。第二頁(yè)，共六十二頁(yè)，2022年，8月28日3三維實(shí)體的表示表示實(shí)體的方法空間分割表示法；由簡(jiǎn)單物體——基本體素，通過(guò)粘合構(gòu)造新的物體。（立方體，長(zhǎng)方體，圓柱體等）單元分解表示，八叉樹(shù)表示，特征表示法構(gòu)造實(shí)體幾何表示法；方法基本同上，將實(shí)體表示稱基本體素的組合，采用更多的運(yùn)算，如并、交、差等。邊界表示法。通過(guò)描述構(gòu)成實(shí)體邊界的點(diǎn)、邊、面來(lái)表示實(shí)體。推移表示法第三頁(yè)，共六十二頁(yè)，2022年，8月28日4實(shí)體的定義實(shí)體造型中必須保證物體的有效性(客觀存在)。真實(shí)世界中物體具有的性質(zhì)具有一定的形狀；具有確定的封閉的邊界；是一個(gè)內(nèi)部連通的三維點(diǎn)集；如果該物體分成了獨(dú)立的幾個(gè)部分，不妨將其看作多個(gè)物體。占據(jù)有限的空間，即體積有限；經(jīng)過(guò)任意的運(yùn)算(切割、粘合)，仍為有效物體；

滿足以上性質(zhì)的物體，稱為有效物體或?qū)嶓w。第四頁(yè)，共六十二頁(yè)，2022年，8月28日5實(shí)體的定義從點(diǎn)集拓?fù)涞慕嵌冉o出實(shí)體的簡(jiǎn)潔定義

將三維物體看作一個(gè)點(diǎn)集，它由內(nèi)點(diǎn)及邊界點(diǎn)共同組成。內(nèi)點(diǎn)：具有完全包含于該點(diǎn)集的充分小鄰域。邊界點(diǎn)：指那些不具有這個(gè)性質(zhì)的點(diǎn)集中的點(diǎn)。第五頁(yè)，共六十二頁(yè)，2022年，8月28日6正則集合運(yùn)算通過(guò)對(duì)簡(jiǎn)單實(shí)體做適當(dāng)?shù)倪\(yùn)算來(lái)構(gòu)造復(fù)雜實(shí)體是一個(gè)有效的方法。實(shí)體可看作點(diǎn)集，對(duì)實(shí)體進(jìn)行的運(yùn)算主要是集合運(yùn)算。但是對(duì)兩個(gè)實(shí)體做普通的集合運(yùn)算并不能保證其結(jié)果仍是實(shí)體。如下，兩個(gè)二維實(shí)體A、B求交：第六頁(yè)，共六十二頁(yè)，2022年，8月28日7正則集合運(yùn)算為了保證運(yùn)算結(jié)果仍為實(shí)體，定義正則集合運(yùn)算op*為：Aop*B=r?(AopB)；其中op=是普通集合運(yùn)算，

r為正則運(yùn)算，op*=正則交、正則并、正則差。(注意定義的含義)定義正則運(yùn)算r如下：r?A=c?i?A。其中，i為取內(nèi)點(diǎn)運(yùn)算，c為取閉包運(yùn)算，A為一個(gè)點(diǎn)集。那么i?A為A的全體內(nèi)點(diǎn)組成的集合，稱作A的內(nèi)部(一個(gè)開(kāi)集)。c?i?A為A的內(nèi)部的閉包，是i?A與其邊界點(diǎn)的并集(一個(gè)閉集)。正則運(yùn)算即為先對(duì)物體取內(nèi)點(diǎn)再取閉包的運(yùn)算。r?A為A的正則點(diǎn)集。但正則點(diǎn)集未必是實(shí)體。第七頁(yè)，共六十二頁(yè)，2022年，8月28日8實(shí)體的定義下圖是帶懸掛邊與孤立點(diǎn)、邊的二維物體，以此為例來(lái)說(shuō)明正則運(yùn)算的過(guò)程。

二維流形：是指這樣一些面，其上任一點(diǎn)都存在一個(gè)充分小的鄰域，該領(lǐng)域與平面上的圓盤是同構(gòu)的，即在該鄰域與圓盤之間存在連續(xù)的一一映射。對(duì)于一個(gè)占據(jù)有限空間的正則點(diǎn)集，如果其表面是二維流形，則該正則點(diǎn)集是實(shí)體(有效物體)。這個(gè)描述中的條件在計(jì)算機(jī)中是可檢測(cè)的。第八頁(yè)，共六十二頁(yè)，2022年，8月28日9正則集合運(yùn)算計(jì)算機(jī)中正則集合運(yùn)算的實(shí)現(xiàn)

任意實(shí)體S可以用它的邊界bS和內(nèi)部iS來(lái)表示：由實(shí)體的定義可知，bS是封閉的，它將整個(gè)三維空間分成了三個(gè)區(qū)域(iS,bS,eS)。邊界bS與實(shí)體S是一一對(duì)應(yīng)的，確定了邊界，也就唯一確定了一個(gè)實(shí)體。為了求實(shí)體A,B的正則運(yùn)算結(jié)果Aop*B，只要求出其邊界b(Aop*B)即可。我們有：第九頁(yè)，共六十二頁(yè)，2022年，8月28日10正則集合運(yùn)算第十頁(yè)，共六十二頁(yè)，2022年，8月28日11下面來(lái)討論A、B兩實(shí)體正則交、正則并、正則差的邊界構(gòu)成。通過(guò)類似的討論，可以得到A，B正則并、正則差的邊界表達(dá)式：正則集合運(yùn)算第十一頁(yè)，共六十二頁(yè)，2022年，8月28日12實(shí)體表示方法空間分割表示邊界表示特征表示推移表示構(gòu)造實(shí)體表示第十二頁(yè)，共六十二頁(yè)，2022年，8月28日13實(shí)體表示方法——空間分割表示空間分割表示

在此表示方法中，實(shí)體被分割表示為互不相交的粘合在一起的更基本的體素?；倔w素的大小、位置、類型可以多種多樣，但它們的一般形狀比較簡(jiǎn)單。空間位置枚舉表示二維平面，為表示圖像，平面分割成大小相同、形狀規(guī)則的像素，然后用像素的集合來(lái)表示圖像，采用的數(shù)據(jù)結(jié)構(gòu)是二維數(shù)組。推廣到三維即是空間位置枚舉表示法。選擇一個(gè)包含物體的立方體作為考慮空間，將立方體劃分成均勻的小立方體，建立一個(gè)三維數(shù)組C[I][J][K]。第十三頁(yè)，共六十二頁(yè)，2022年，8月28日14實(shí)體表示方法——空間分割表示數(shù)組中的元素C[i][j][k]與左下角點(diǎn)坐標(biāo)是(i,j,k)的小立方體對(duì)應(yīng)。當(dāng)該立方體被物體占據(jù)時(shí)，取C[i][j][k]的值為1，否則為0。這樣數(shù)組C就唯一表示了包含于立方體之內(nèi)的所有物體。其中為小立方體的邊長(zhǎng)。數(shù)組的大小取決于空間分辨()的大小和我們感興趣的立方體空間的大小。優(yōu)點(diǎn)：可以表示任何物體(通常情況下是近似表示)，容易實(shí)現(xiàn)物體的集合運(yùn)算以及計(jì)算物體的體積等許多整數(shù)性質(zhì)。缺點(diǎn)：沒(méi)有明確給出物體的邊界信息，不適于圖形顯示；占據(jù)的存儲(chǔ)量非常大。第十四頁(yè)，共六十二頁(yè)，2022年，8月28日15實(shí)體表示方法——空間分割表示八叉樹(shù)表示此法對(duì)空間位置枚舉法中的空間分割方法作了改進(jìn)，即并非統(tǒng)一將物體所在的立方體空間均勻分成邊長(zhǎng)為的小立方體，而是對(duì)空間進(jìn)行自適應(yīng)劃分，采用具有層次結(jié)構(gòu)的八叉樹(shù)表示物體。類似于二維圖形的四叉樹(shù)表示。對(duì)于四叉樹(shù)表示，我們?cè)谝粋€(gè)包含二維圖形區(qū)域的正方形區(qū)域中考慮問(wèn)題，此正方形區(qū)域?yàn)樗牟鏄?shù)的根節(jié)點(diǎn)，它可能處于三種狀態(tài)：完全被圖形覆蓋(F)、部分被覆蓋(P)或完全沒(méi)有被覆蓋(E)。若根節(jié)點(diǎn)處于狀態(tài)F或E，則四叉樹(shù)建立完畢；否則，將其分成四個(gè)小正方形區(qū)域，分別標(biāo)0,1,2,3。第十五頁(yè)，共六十二頁(yè)，2022年，8月28日16FEFFEEEEFFEFFFEE實(shí)體表示方法——空間分割表示這四個(gè)小正方形成為第一層子節(jié)點(diǎn)，對(duì)它們做類似根節(jié)點(diǎn)的處理，如此下去，直到建立圖形的四叉樹(shù)表示。對(duì)狀態(tài)P的節(jié)點(diǎn)的分割層次根據(jù)實(shí)際需要予以指定。如圖，一個(gè)空間自適應(yīng)分割過(guò)程：第十六頁(yè)，共六十二頁(yè)，2022年，8月28日17實(shí)體表示方法——空間分割表示建立物體的八叉樹(shù)表示的過(guò)程與四叉樹(shù)表示大體一樣。此時(shí)，每個(gè)節(jié)點(diǎn)代表的是一個(gè)立方體，對(duì)它分割的結(jié)果產(chǎn)生八個(gè)子節(jié)點(diǎn)。編碼是0到7。用八叉樹(shù)表示實(shí)體，具有許多優(yōu)點(diǎn)：容易實(shí)現(xiàn)實(shí)體之間的正則集合運(yùn)算；容易計(jì)算實(shí)體的整體性質(zhì)；容易實(shí)現(xiàn)隱藏線和隱藏面的消除。缺點(diǎn)：通常不能精確地表示一個(gè)實(shí)體，并且對(duì)八叉樹(shù)表示的實(shí)體做任意的幾何變換比較困難。如旋轉(zhuǎn)角度為非90o倍數(shù)的旋轉(zhuǎn)變換，放縮的比例非2的倍數(shù)的放縮變換。八叉樹(shù)需要較大存儲(chǔ)空間。第十七頁(yè)，共六十二頁(yè)，2022年，8月28日18FEEEEEEEEEEFFEE{5X,74X,75X},X為大于7的整數(shù)實(shí)體表示方法——空間分割表示減少所需存儲(chǔ)空間的方法很多，最簡(jiǎn)單有效的是線性八叉樹(shù)：用一個(gè)線性結(jié)構(gòu)存儲(chǔ)八叉樹(shù)，在數(shù)組中僅僅存放八叉樹(shù)中狀態(tài)為F的節(jié)點(diǎn)。第十八頁(yè)，共六十二頁(yè)，2022年，8月28日19實(shí)體表示方法——單元分解表示單元分解表示從另一角度對(duì)空間位置枚舉表示做了改進(jìn)。它以不同類型的基本體素(不是單一的立方體)通過(guò)粘合運(yùn)算來(lái)構(gòu)造新的實(shí)體。這些基本體素可以是任何簡(jiǎn)單實(shí)體，如圓柱、圓錐、多面體等。粘合運(yùn)算使兩個(gè)實(shí)體在邊界面上相接觸，但它們的內(nèi)部并不相交。只要基本體素的類型足夠多，單元分解表示法能表示范圍相當(dāng)廣泛的物體。單元分解表示法不具有唯一性，即同一實(shí)體可具有多種表示形式。另外，此法所構(gòu)造物體的有效性難以保證第十九頁(yè)，共六十二頁(yè)，2022年，8月28日20實(shí)體表示方法——邊界表示邊界表示即通過(guò)描述實(shí)體的邊界來(lái)表示一個(gè)實(shí)體的方法。邊界與實(shí)體是一一對(duì)應(yīng)的，定義了實(shí)體的邊界，該實(shí)體就被唯一確定。邊界可以是多邊形或曲面片。通常，曲面片被近似地離散成多邊形來(lái)處理。本節(jié)討論多面體的邊界表示。第二十頁(yè)，共六十二頁(yè)，2022年，8月28日21實(shí)體表示方法——邊界表示多面體及歐拉公式：平面多面體是指表面由平面多邊形構(gòu)成的三維體，其表面上的每條邊被偶數(shù)個(gè)多邊形共享。多面體表面具有二維流形的性質(zhì)，即多面體的每條邊只嚴(yán)格屬于兩個(gè)多邊形。第二十一頁(yè)，共六十二頁(yè)，2022年，8月28日22v=8,e=12,f=6v=4,e=6,f=4實(shí)體表示方法——邊界表示簡(jiǎn)單多面體是指與球拓?fù)渫瑯?gòu)的的多面體，可連續(xù)變換成一個(gè)球。它滿足下面的歐拉公式： v-e+f=2

其中v,e,f分別是多面體的頂點(diǎn)數(shù)、邊數(shù)和面數(shù)。歐拉公式是一個(gè)多面體為簡(jiǎn)單多面體的必要但非充分條件。第二十二頁(yè)，共六十二頁(yè)，2022年，8月28日23V=24,e=36,f=15,r=3,s=1,h=1實(shí)體表示方法——邊界表示檢驗(yàn)一個(gè)具有多邊形表面的體是不是簡(jiǎn)單多面體，除了要驗(yàn)證歐拉公式外，還要附加一些條件，如每條邊連接兩個(gè)頂點(diǎn)，每條邊只被兩個(gè)面共享，每個(gè)頂點(diǎn)至少被三條邊共享。如圖所示的非簡(jiǎn)單多面體，滿足廣義歐拉公式：v-e+f-r=2(s-h)。其中r表示多面體表面上孔的個(gè)數(shù)，h為貫穿多面體的孔洞的個(gè)數(shù)，s為相互分離的多面體數(shù)。并且，

廣義歐拉公式仍是檢

查一個(gè)多邊形表面的

體是否為實(shí)體的必要

條件。第二十三頁(yè)，共六十二頁(yè)，2022年，8月28日24實(shí)體表示方法——邊界表示平面方程的計(jì)算構(gòu)成平面多面體邊界的是多邊形。我們討論求多邊形所在平面的方程。平面方程表示為：

其中，N=[Nx,NyNz]取作平面的單位法矢量，空間任意一點(diǎn)V到平面的距離為N?V+d。當(dāng)V落在平面的某一側(cè)時(shí)，它的值為正，另一側(cè)的值為負(fù)，落在平面上時(shí)為0。當(dāng)多邊形是三角形時(shí)，三個(gè)頂點(diǎn)唯一確定一個(gè)平面。其單位法向量為：第二十四頁(yè)，共六十二頁(yè)，2022年，8月28日25實(shí)體表示方法——邊界表示將N和P0(或P1,P2)的坐標(biāo)代入方程，可求出：

這樣，可求出要求的平面方程。當(dāng)多邊形的頂點(diǎn)多于3個(gè)時(shí)，它們不一定共面，此時(shí)，只有以一張與各個(gè)頂點(diǎn)距離之和最小的平面來(lái)近似表示它們。設(shè)多邊形的頂點(diǎn)為Pi(xi,yi,zi)，則所求平面的單位法矢量為：

其中，取Pn+1=P0。展開(kāi)上式得到：第二十五頁(yè)，共六十二頁(yè)，2022年，8月28日26實(shí)體表示方法——邊界表示邊界表示的數(shù)據(jù)結(jié)構(gòu)最簡(jiǎn)單的邊界表示方法

將多面體表示成其邊界的一列多邊形，每個(gè)多邊形又由一列頂點(diǎn)坐標(biāo)來(lái)表示。將頂點(diǎn)統(tǒng)一按一個(gè)方向(如逆時(shí)針或順時(shí)針)排列。

由于每個(gè)頂點(diǎn)屬于多個(gè)多邊形，在多邊形中只保存各頂點(diǎn)的序號(hào)，將多面體的所有頂點(diǎn)存放在一個(gè)數(shù)組中。這里，邊的信息是隱含的，即多邊形頂點(diǎn)序列中相鄰兩個(gè)頂點(diǎn)構(gòu)成一條邊。第二十六頁(yè)，共六十二頁(yè)，2022年，8月28日27實(shí)體表示方法——邊界表示邊界表示的數(shù)據(jù)結(jié)構(gòu)此法數(shù)據(jù)結(jié)構(gòu)簡(jiǎn)單，但效率不高。如查找共享某條邊的兩個(gè)多邊形，則需要遍歷組成該多面體邊界的所有多邊形，才能確定哪兩個(gè)多邊形包含這條邊。(原因：數(shù)據(jù)結(jié)構(gòu)中包含多面體邊界的拓?fù)湫畔⒉煌暾?第二十七頁(yè)，共六十二頁(yè)，2022年，8月28日28實(shí)體表示方法——邊界表示幾何信息指的是頂點(diǎn)、邊、面的位置、大小、形狀等幾何數(shù)據(jù)。拓?fù)湫畔⒅傅氖琼旤c(diǎn)、邊、面之間的連接關(guān)系。多面體的頂點(diǎn)、邊、面之間的拓?fù)潢P(guān)系可用九中不同的形式描述：v{v},v{e},v{f},e{v},e{e},e{f},f{v},f{e},f{f}。每一種關(guān)系都可由其它關(guān)系通過(guò)適當(dāng)?shù)倪\(yùn)算得到。第二十八頁(yè)，共六十二頁(yè)，2022年，8月28日29實(shí)體表示方法——邊界表示在表示法中究竟采用哪種拓?fù)潢P(guān)系或哪幾種關(guān)系的組合取決于邊界表示所支持的各種運(yùn)算以及存儲(chǔ)空間的限制。數(shù)據(jù)結(jié)構(gòu)中保存的拓?fù)潢P(guān)系越多，對(duì)多面體的操作越方便，但占用的存儲(chǔ)空間也越大。拓?fù)潢P(guān)系的選擇要合理折中。第二十九頁(yè)，共六十二頁(yè)，2022年，8月28日30實(shí)體表示方法——邊界表示半邊數(shù)據(jù)結(jié)構(gòu)在構(gòu)成多面體的三要素(頂點(diǎn)、邊、面)中，此法以邊為核心。為了方便表達(dá)拓?fù)潢P(guān)系，將一條邊表示成拓?fù)湟饬x上方向相反的兩條半邊，其結(jié)構(gòu)如圖。第三十頁(yè)，共六十二頁(yè)，2022年，8月28日31多面體面環(huán)半邊頂點(diǎn)實(shí)體表示方法——邊界表示多面體的邊界表示結(jié)構(gòu)如圖：第三十一頁(yè)，共六十二頁(yè)，2022年，8月28日32實(shí)體表示方法——邊界表示半邊數(shù)據(jù)結(jié)構(gòu)類型solid,face,loop,edge,halfedge,vertex將在后面定義。對(duì)每種類型定義一個(gè)同類型的類名，分別分別是Solid,Face,Loop,Edge,Halfedge,Vertex，同時(shí)說(shuō)明一個(gè)浮點(diǎn)數(shù)組vector[4]、一個(gè)短整型Id。后面對(duì)其分別進(jìn)行介紹。第三十二頁(yè)，共六十二頁(yè)，2022年，8月28日33實(shí)體表示方法——邊界表示多面體

structsolid{ Idsolidno;Face*sfaces;Edge*sedges;Vertex*sverts;Solid*nexts;Solid*prves; };多面體是數(shù)據(jù)結(jié)構(gòu)最上層的節(jié)點(diǎn)，任何時(shí)候都可以通過(guò)連接各節(jié)點(diǎn)的雙向指針遍歷多面體邊界的面、邊、頂點(diǎn)等元素。第三十三頁(yè)，共六十二頁(yè)，2022年，8月28日34實(shí)體表示方法——邊界表示面

structface{ Idfaceno;solid*fsolid;Loop*floops;Vertexfeq;Face*nextf;Face*prvef; };

面結(jié)構(gòu)表示多面體表面的一個(gè)平面多邊形，該多邊形所在的平面方程為feq[0]?x+feq[1]?y+feq[2]?z+feq[3]=0邊界由一系列環(huán)構(gòu)成，floops指向其外環(huán)。第三十四頁(yè)，共六十二頁(yè)，2022年，8月28日35實(shí)體表示方法——邊界表示環(huán)

structloop{ HalfEdge*ledge;Face*lface;Loop*prevl;Loop*nextl;};一個(gè)環(huán)由多條半邊組成，環(huán)的走向一定。若規(guī)定外環(huán)逆時(shí)針，則內(nèi)環(huán)順時(shí)針。反之亦然。第三十五頁(yè)，共六十二頁(yè)，2022年，8月28日36實(shí)體表示方法——邊界表示邊

structedge{ Idedgeno;HalfEdge*he1;HalfEdge*he2;Edge*preve;Edge*nexte;};一條邊分為拓?fù)湟饬x上方向相反的兩條半邊。在多面體中保存邊的信息是為了方便對(duì)多面體以線框的形式進(jìn)行顯示處理。第三十六頁(yè)，共六十二頁(yè)，2022年，8月28日37實(shí)體表示方法——邊界表示半邊

structhalfedge{ Edge*edge;Vertex*vtx;Loop*wloop;HalfEdge*prv;HalfEdge*nxt;};

半邊是整個(gè)數(shù)據(jù)結(jié)構(gòu)的核心，一條條首尾相連的半邊組成一個(gè)環(huán)，通過(guò)指針edge，可以訪問(wèn)與該半邊同屬一條邊的另一半邊。第三十七頁(yè)，共六十二頁(yè)，2022年，8月28日38實(shí)體表示方法——邊界表示頂點(diǎn)

structvertex{ Id*vertexno;HalfEdge*vedgeVectorvcoord;Vertex*nextv;Vertex*prevv;};

頂點(diǎn)是構(gòu)成多面體的最基本元素，它包括了多面體的所有幾何信息，即頂點(diǎn)坐標(biāo)vcoord。第三十八頁(yè)，共六十二頁(yè)，2022年，8月28日39實(shí)體表示方法——邊界表示以半邊數(shù)據(jù)結(jié)構(gòu)為基礎(chǔ)的多面體的邊界表示包含了多種拓?fù)潢P(guān)系，如v{e},e{v},e{f},等，可以方便地查找各元素之間的連接關(guān)系。例如，若要查找共享某條邊的兩個(gè)面，首先由指針he1,he2找到兩條半邊，再由半邊的指針wloop找到所屬的環(huán)，最后由環(huán)結(jié)構(gòu)中的指針lface便能確定所求的面。這種表示中存儲(chǔ)的信息量大，需要較多的存儲(chǔ)空間，但卻獲得了較快的處理速度。在邊界表示法中，可以定義一系列運(yùn)算來(lái)構(gòu)造或修改三維實(shí)體，常用的這類運(yùn)算有歐拉運(yùn)算，正則集合運(yùn)算。第三十九頁(yè)，共六十二頁(yè)，2022年，8月28日40實(shí)體表示方法——邊界表示歐拉運(yùn)算將廣義歐拉公式：

v-e+f-r-2s+2h=0

中的v,e,f,r,s,h看成獨(dú)立的坐標(biāo)變量，上式為六維空間的平面(過(guò)原點(diǎn))，坐標(biāo)變量為非負(fù)整數(shù)，對(duì)應(yīng)為一張五維平面的網(wǎng)格，每個(gè)多面體對(duì)應(yīng)一個(gè)網(wǎng)格點(diǎn)(并非每一網(wǎng)格點(diǎn)對(duì)應(yīng)一個(gè)有效的多面體)。如果要構(gòu)造的多面體對(duì)應(yīng)的網(wǎng)格點(diǎn)坐標(biāo)是(v,e,f,r,s,h)，那么構(gòu)造該實(shí)體的過(guò)程就是從原點(diǎn)開(kāi)始沿網(wǎng)格一步一步向這個(gè)坐標(biāo)點(diǎn)前進(jìn)的過(guò)程。由于網(wǎng)格上的每點(diǎn)滿足上式，從而最終得到的多面體也必滿足。這些走法多種多樣。第四十頁(yè)，共六十二頁(yè)，2022年，8月28日41(1)mvfs(s,v,f,x,y,z)：創(chuàng)建一個(gè)序號(hào)為s的多面體，它包含一個(gè)頂點(diǎn)v和一個(gè)面f，頂點(diǎn)v的坐標(biāo)為(x,y,z)。實(shí)體表示方法——邊界表示上式有五個(gè)自由變量，故有五種基本走法。而多種多樣的走法是五種基本走法的合成。最典型的是歐拉運(yùn)算：第四十一頁(yè)，共六十二頁(yè)，2022年，8月28日42(2)mev(s,v1,v2,v3,v4,f1,f2,x,y,z)輸入一個(gè)頂點(diǎn)v4，生成一條新邊v1v4。使得原來(lái)圍繞頂點(diǎn)v1的邊中，v1v2的頂點(diǎn)變成以v4為頂點(diǎn)。當(dāng)v2=v3,f1=f2時(shí)，該運(yùn)算僅僅生成一條新邊。實(shí)體表示方法——邊界表示第四十二頁(yè)，共六十二頁(yè)，2022年，8月28日43(3)mef(s,f1,f2,v1,v2,v3,v4)

連接面f1的兩條邊v1v2與v3v4的頂點(diǎn)v1與v3，生成一條新邊，并將f1分成兩個(gè)面f1和f2。其中，有向邊v1v3所在的面為f2，有向邊v3v1所在的面為f1。實(shí)體表示方法——邊界表示第四十三頁(yè)，共六十二頁(yè)，2022年，8月28日44(4)kemr(s,f,v1,v2)

刪除連接v1與v2的邊，生成一個(gè)新環(huán)。(5)kfmrh(s,f1,f2)合并f1與f2，使得f2變成f1的一個(gè)內(nèi)環(huán)(被刪除)，由此產(chǎn)生一個(gè)新的通孔。實(shí)體表示方法——邊界表示第四十四頁(yè)，共六十二頁(yè)，2022年，8月28日45以構(gòu)造一個(gè)帶孔的立方體為例說(shuō)明歐拉運(yùn)算，由點(diǎn)到邊、由邊到環(huán)、由環(huán)到面、由面到體一步一步來(lái)構(gòu)造三維立體。如圖實(shí)體表示方法——邊界表示第四十五頁(yè)，共六十二頁(yè)，2022年，8月28日46mvfs(s0,v0,f0,x0,y0,z0);mev(s0,v0,v0,v0,v1,f0,f0,x1,y1,z1);mev(s0,v1,v0,v0,v2,f0,f0,x2,y2,z2);mev(s0,v2,v1,v1,v3,f0,f0,x3,y3,z3);mef(s0,f0,f1,v3,v2,v0,v1);實(shí)體表示方法——邊界表示第四十六頁(yè)，共六十二頁(yè)，2022年，8月28日47mev(s0,v0,v3,v3,v4,f1,f1,x4,y4,z4);mev(s0,v4,v0,v0,v5,f1,f1,x5,y5,z5);mef(s0,f1,f2,v5,v4,v1,v2);f1:v1v5v4v0v1f2:v5v1v2v3v0v4v5實(shí)體表示方法——邊界表示第四十七頁(yè)，共六十二頁(yè)，2022年，8月28日48mev(s0,v5,v4,v4,v6,f2,f2,x6,y6,z6);mef(s0,f2,f3,v6,v5,v2,v3);f2:v2v6v5v1v2f3:v6v2v3v0v4v5v6mev(s0,v6,v5,v5,v7,f3,f3,x7,y7,z7);mef(s0,f3,f4,v7,v6,v3,v0);mef(s0,f4,f5,v7,v3,v4,v5);f3:v3v7v6v2v3f4:v7v3v0v4v5v6v7f4:v4v7v3v0v4f5:v7v4v5v6v7實(shí)體表示方法——邊界表示第四十八頁(yè)，共六十二頁(yè)，2022年，8月28日49實(shí)體表示方法——邊界表示正則集合運(yùn)算

通過(guò)對(duì)邊界表示的物體做正則集合運(yùn)算可以構(gòu)造新的邊界表示的物體。

對(duì)具有平面邊界，曲面邊界的物體進(jìn)行集合運(yùn)算的算法有很多，大致步驟如下：(1)預(yù)檢查兩個(gè)物體是否相交：物體表面求交運(yùn)算計(jì)算量大，非常費(fèi)時(shí)。如經(jīng)過(guò)大量計(jì)算，物體表面并不相交。一般，采用包圍盒技術(shù)加速，預(yù)檢查兩個(gè)物體是否相交。所謂包圍盒，指的是包圍物體的最小長(zhǎng)方體(或任何簡(jiǎn)單形體如球、圓柱等)。如二維空間的三角形，其包圍盒是矩形。第四十九頁(yè)，共六十二頁(yè)，2022年，8月28日50實(shí)體表示方法——邊界表示包圍盒在這里的應(yīng)用分為兩個(gè)層次：a.計(jì)算兩個(gè)待求物體的包圍盒，若包圍盒無(wú)交，則物體不相交，正則集合運(yùn)算結(jié)束，否則，進(jìn)入下一層。b.計(jì)算兩物體每一個(gè)表面片的包圍盒，當(dāng)某個(gè)面片的包圍盒與另一物體的包圍盒相交時(shí)，將該面片與另一物體的所有表面片一一求交，否則，該面片與另一物體的所有表面片都無(wú)交。采用此法預(yù)檢查能分離出許多物體與物體或表面片與物體無(wú)交的情況，從而避免了許多不必要的復(fù)雜的求交計(jì)算。第五十頁(yè)，共六十二頁(yè)，2022年，8月28日51實(shí)體表示方法——邊界表示(2)計(jì)算物體表面之間的交線。平面多面體的處理(平面與平面求交)；曲面邊界的處理，涉及到曲面片與曲面片的求交，一般有兩種處理方法：a.解析求交：根據(jù)兩曲面片的解析方程，建立交線的方程。b.離散求交：先將曲面片離散成一塊塊平面多邊形，然后求出這些平面多邊形間的交線，將它們連接起來(lái)近似表示兩曲面間的交線。此算法計(jì)算簡(jiǎn)便，程序處理一致，但存在逼近誤差，解的精度低。(3)對(duì)物體的表面分類。(4)建立結(jié)果物體的邊界表示。第五十一頁(yè)，共六十二頁(yè)，2022年，8月28日52實(shí)體表示方法——特征表示特征表示用一組特征參數(shù)來(lái)定義一族類似的物體。特征從功能上分形狀特征和材料特征。形狀特征如體素、孔、半孔、槽等。材料特征如硬度、密度、熱處理方法等。

如，只考慮形狀特征，一個(gè)圓柱或圓錐可用參數(shù)組(R,H)來(lái)定義，一個(gè)正n棱柱可用參數(shù)組(n,R,H)定義。特征表示適用于表示工業(yè)上定型的標(biāo)準(zhǔn)件。標(biāo)準(zhǔn)件既可以十分簡(jiǎn)單，也可以相當(dāng)復(fù)雜。所有的標(biāo)準(zhǔn)件保存在一個(gè)數(shù)據(jù)庫(kù)中，使用時(shí)，用戶只要指定參數(shù)。特征表示面向用戶，用戶還可根據(jù)需要向數(shù)據(jù)庫(kù)中增加新的體素類型。第五十二頁(yè)，共六十二頁(yè)，2022年，8月28日53實(shí)體表示方法——推移表示推移表示將物體A沿空間一條軌跡P推移時(shí)，A的軌跡定義了一個(gè)新的物體B，則物體B可以由物體A與軌跡P共同表示。這種表示法稱為推移表示法。如A是一個(gè)二維的平面區(qū)域，軌跡是垂直于該平面的直線段，推移的結(jié)果得到一個(gè)柱體，這種簡(jiǎn)單推移表示方法叫平移sweep，由此得到的物體叫平移sweep體。如：正四棱柱、圓柱。如果將平移sweep進(jìn)行推廣：允許二維區(qū)域在推移的過(guò)程中大小可變，軌道可以不垂直于二維區(qū)域所在的平面。正方形區(qū)域沿任一方向推移得到一個(gè)平行六面體。若正方形沿軌跡向前推移時(shí)，其邊長(zhǎng)呈線性遞減，得到的平移sweep體是四棱錐。第五十三頁(yè)，共六十二頁(yè)，2022年，8月28日54實(shí)體表示方法——推移表示旋轉(zhuǎn)sweep通過(guò)將一個(gè)二維區(qū)域繞一個(gè)軸旋轉(zhuǎn)而構(gòu)成新的物體。如直角三角形區(qū)域繞一條直角邊旋轉(zhuǎn)一圈形成的旋轉(zhuǎn)sweep體是一個(gè)圓錐。允許待推移的物體A在推移過(guò)程中任意變化，軌道P為任意曲線，那么所得到的推移方法稱廣義sweep。其中，物體A的尺寸、形狀、朝向在前進(jìn)過(guò)程中都可以改變。故廣義sweep體是非常復(fù)雜的物體，表示能力強(qiáng)于平移sweep與旋轉(zhuǎn)sweep，但需要的計(jì)算復(fù)雜得多。一般，對(duì)sweep體做正則運(yùn)算是困難的，簡(jiǎn)單sweep體在正則運(yùn)算下也不是封閉的。但推移表示簡(jiǎn)單、直觀，是許多造型系統(tǒng)采用的輸入手段。第五十四頁(yè)，共六十二頁(yè)，2022年，8月28日55實(shí)體