1、2.5二、三維邊界表示法1、方法原理首先考慮一個簡單的四面體應如何表示。它是一個平面多面體，即它的每個表面均可以看成是一個平面多邊形。為了做到無歧義地、有效地表示，需指出它的頂點位置以及由哪些點構成邊，哪些邊圍成一個面等一些幾何與拓撲的信息。頂點表V1面表圖2-5-4三維邊界表示法比較常用的表示一個平面多面體的方法是采用三張表來提供這些信息（如圖5-，4這）三張表就是：1）頂點表：用來表示多面體各頂點的坐標；2）邊表：指出構成多面體某邊的兩個頂點；3）面表：給出圍成多面體某個面的各條邊。對于后兩個表一般使用指針的方法指出有關的邊、點存放的位置。為了更快地獲得所需信息，更充分地表達點、線、面之間

2、的拓撲關系，可以把其它一些有關的內(nèi)容結合到所使用的表中。圖25-中4的擴充后的邊表就是將邊所屬的多邊形信息結合進邊表中以后的形式。這樣利用這種擴充后的表，可知某條邊是否為兩個多邊形的公共邊，如果是，相應的兩個多邊形也立即知道。這是一種用空間換取時間的方法。是否要這樣做，應視具體的應用而定，同樣也可根據(jù)需要適當?shù)財U充其它兩張表來提高處理的效率。除了描述它的幾何結構，還要指出該多面體的一些其它特性。例如每個面的顏色、紋理等等。這些屬性可以用另一個表獨立存放。當有若干個多面體時，還必須有一個對象表。每個多面體在這個表中列出圍成它的諸面，同樣也可用指針的方式實現(xiàn)，這時面表中的內(nèi)容，已不再是只和一個多面

3、體有關。2、特點采用這種分列的表來表示多面體，可以避免重復地表示某些點、邊、面，因此一般來說存貯量比較節(jié)省，對圖形顯示更有好處。例如，由于使用了邊表，可以立即顯示出該多面體的線條畫，也不會使同一條邊重復地畫上兩次。可以想象，如果表中僅有多邊形表而省卻了邊表，兩個多邊形的公共邊不僅在表示上要重復，而且很可能會畫上兩次。類似地，如果省略了頂點表，那么作為一些邊的公共頂點的坐標值就可能反復地寫出好多次。3、拓撲檢查對于比較復雜的多面體要輸入大量的數(shù)據(jù)。檢查輸入的數(shù)據(jù)是否一致、是否完全，是一項必不可少的工作，這就是通常所說的拓撲檢查。一般來說，在數(shù)據(jù)表中包含的信息越多，輸入時有錯的可能性也越大，但是可

4、用來檢查是否有錯的手段也會隨之增加。對上面提及的數(shù)據(jù)結構，至少可以檢查以下諸項：1）頂點表中的每個頂點至少是兩條邊的端點；2每）條邊至少是一個多邊形的邊；3每）個多邊形是封閉的；4每）個多邊形至少有一條邊是和另一個多邊形共用的；5若）邊表中包含了指向它所屬多邊形的指針，那么指向該邊的指針必在相應的多邊形中出現(xiàn)。這些檢查對于維護表示多面體的數(shù)據(jù)庫的全體一致性是有效的，而復雜的情況應當有專門的程序來檢查。4、應用以上討論的只是簡單的平面多面體的三維邊界表示，但是研究的對象是自然實體，其三維形狀的復雜程度難以描述。例如巖石的外表不規(guī)則，組成的平面可有成千上萬，如何用三維邊界表示法表示呢?從理論上講，

5、對任意的三維形體只要它滿足一定的條件，總可找到一個適合的平面多面體來近似地表示這個三維形體，且使誤差保持在一定的范圍之內(nèi)。但是在實際上，這種逼近受到多方面因素的制約，解決這個問題的方法也不一而足。通常，這個問題可以敘述成：要表示某個三維形體，又僅知道從這個形體的外表面上測得的一組點P1Pn的坐標。為了解決這個問題，首先要為這些點建立起某種關系。這種關系被稱為這些點代表的形體結構。可以由一個圖來表示，圖的頂點就是這里給定的那組點P1Pn，而圖的邊的給定方式則恰好反映了所設想的結構。不同的圖，有不同的邊（也就是連接這些頂點的方法不同相應地，這個圖對應的平面多面體也不同，這可由圖25-來5示意。圖2-5-5相同的點，不同的形體結構在眾多的結構中，每個面均是三角形的平面多面體起著很重要的作用（這跟不規(guī)則三角網(wǎng)很類似。即使對結構加上了這種限制，同一組點仍可得到不同的平面多面體。因此，人們自然會想到，在這類多面體中，