選擇網(wǎng)格數(shù)據(jù)結(jié)構(gòu)的時(shí)候一般考慮下面兩個(gè)因素：
拓?fù)湫枨?Topological Requirements) ：需要表示什么樣的網(wǎng)格？是二維流形旁涤，還是其它更復(fù)雜的網(wǎng)格？是單純的三角形網(wǎng)格搓萧，或者其它任意的多邊形網(wǎng)格毛甲？是需要給當(dāng)前的網(wǎng)格附加上其它的網(wǎng)格？
算法需求(Algorithmic Requirements)：使用什么樣的算法哈扮？是簡單的渲染還是需要頻繁的訪問相鄰的點(diǎn)邊面纬纪？是靜態(tài)網(wǎng)格還是動(dòng)態(tài)網(wǎng)格？對(duì)于網(wǎng)格是否需要附加一些其它的屬性灶泵？對(duì)內(nèi)存的消耗是否特別在意育八？
評(píng)估一個(gè)數(shù)據(jù)結(jié)構(gòu)的好壞有下面幾個(gè)標(biāo)準(zhǔn)：
- 建立數(shù)據(jù)結(jié)構(gòu)所需要預(yù)處理的時(shí)間
- 查詢操作的響應(yīng)時(shí)間
- 執(zhí)行某項(xiàng)具體操作的時(shí)間
- 內(nèi)存消耗和冗余
Faced-Based Data Structures
這種數(shù)據(jù)結(jié)構(gòu)最直觀的優(yōu)點(diǎn)是簡單，這種數(shù)據(jù)結(jié)構(gòu)由網(wǎng)格所有面的集合構(gòu)成赦邻，而對(duì)于每一個(gè)面則使用組成面多邊形的的點(diǎn)來表示髓棋。
以三角形網(wǎng)格為例，假設(shè)使用32位的單精度浮點(diǎn)數(shù)來表示坐標(biāo)則惶洲，那么使用頂點(diǎn)的數(shù)據(jù)來表示一個(gè)三角形則需要36個(gè)字節(jié)(3 vertex * 3 dimension * 4 byte = 36 byte)按声。
通過上一部分的學(xué)習(xí)可以知道頂點(diǎn)的鄰邊的平均數(shù)量為6，即在這種數(shù)據(jù)結(jié)構(gòu)中一個(gè)頂點(diǎn)平均會(huì)被存儲(chǔ)6次恬吕，所以可以估算使用這種數(shù)據(jù)結(jié)構(gòu)平均每一個(gè)頂點(diǎn)要使用72個(gè)字節(jié)(3 dimension * 4 byte * 6 time = 72 byte)
可以發(fā)現(xiàn)签则，一個(gè)頂點(diǎn)的數(shù)據(jù)被多次存儲(chǔ)，一種可以改進(jìn)這種空間冗余的方法是铐料，使用數(shù)組來存儲(chǔ)所有的頂點(diǎn)數(shù)據(jù)渐裂，而對(duì)于每一個(gè)三角形面只需要存儲(chǔ)組成其的三個(gè)頂點(diǎn)的索引號(hào)即可豺旬。
這樣存儲(chǔ)一個(gè)三角形或一個(gè)頂點(diǎn)只需要12個(gè)字節(jié)(3個(gè)4字節(jié)的浮點(diǎn)數(shù)或3個(gè)整數(shù))
這樣平均一個(gè)頂點(diǎn)只需要36個(gè)字節(jié)(3 dimension * 4 byte + 6 time * 4 byte = 36 byte，一份頂點(diǎn)數(shù)據(jù)柒凉，6個(gè)索引號(hào))
但是這種數(shù)據(jù)結(jié)構(gòu)存在一個(gè)問題族阅，它缺陷顯式的連通性信息，在大多數(shù)算法中都會(huì)用到下面的操作：
- 迭代訪問所有的點(diǎn)膝捞、邊和面
- 有方向地遍歷一個(gè)面周圍的邊坦刀，這需要通過一條邊找到它的下一條或者上一條邊，可能還需要順帶的使用到對(duì)應(yīng)頂點(diǎn)的數(shù)據(jù)
- 通過一條邊找到與它相鄰的面或者它的兩個(gè)端點(diǎn)
- 通過一個(gè)頂點(diǎn)迭代訪問它周圍的邊和面(one-ring
neighborhood)
要通過上面的數(shù)據(jù)結(jié)構(gòu)完成這些操作蔬咬，可以把向當(dāng)前的數(shù)據(jù)結(jié)構(gòu)中添加一部分信息鲤遥。
添加了附加信息后，存儲(chǔ)一個(gè)面需要24個(gè)字節(jié)林艘，存儲(chǔ)一個(gè)頂點(diǎn)需要16個(gè)字節(jié)盖奈，平均一個(gè)頂點(diǎn)需要64個(gè)字節(jié)。
Edge-Based Data Structures
這種數(shù)據(jù)結(jié)構(gòu)改進(jìn)Faced-Based Data Structures中沒有顯式存儲(chǔ)邊地問題狐援，并附加存儲(chǔ)了很多其它信息到邊上(兩個(gè)端點(diǎn)卜朗、相鄰地面、邊)咕村。
這種數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)一個(gè)面需要4個(gè)字節(jié)场钉，存儲(chǔ)一個(gè)頂點(diǎn)需要16個(gè)字節(jié)，存儲(chǔ)一條邊需要32個(gè)字節(jié)懈涛，平均一個(gè)頂點(diǎn)需要120個(gè)字節(jié)逛万。
Halfedge-Based Data Structure
在Halfedge-Based Data Structure(半邊數(shù)據(jù)結(jié)構(gòu))中，一個(gè)重要的概念就是Halfedge(半邊)批钠，半邊即一條邊的一半宇植，等于是把一條邊保持長度不變，形式上分為兩條半邊埋心。這兩條半邊組合在一起稱為一條邊指郁，也就是一條邊等于一對(duì)半邊。半邊是有方向的拷呆，并且一條邊的一對(duì)半邊有相反的方向闲坎。
對(duì)于每一條半邊，我們存儲(chǔ)下面的信息：
- 半邊指向的頂點(diǎn)
- 半邊相鄰的面(當(dāng)半邊為網(wǎng)格邊界的時(shí)候沒有相鄰的面)
- 一個(gè)面中的上/下一條半邊
- 與它配對(duì)的另一條半邊
存儲(chǔ)一個(gè)面需要4個(gè)字節(jié)茬斧，存儲(chǔ)一個(gè)頂點(diǎn)需要16個(gè)字節(jié)腰懂，存儲(chǔ)一條半邊需要20個(gè)字節(jié)，平均一個(gè)頂點(diǎn)需要144個(gè)字節(jié)项秉。
這里可以優(yōu)化使用數(shù)組的索引號(hào)而不是指針來存儲(chǔ)具體的信息绣溜，這樣在需要附加額外信息的時(shí)候會(huì)更加方便，同時(shí)由于數(shù)組在內(nèi)存中是連續(xù)排布的娄蔼，在進(jìn)行內(nèi)存管理的時(shí)候也會(huì)更加簡單高效怖喻。
Directed-Edge Data Structure
這種數(shù)據(jù)結(jié)構(gòu)是Halfedge-Based Data Structure(半邊數(shù)據(jù)結(jié)構(gòu))的一種特殊形式底哗，只能夠用于三角形網(wǎng)格。這種數(shù)據(jù)結(jié)構(gòu)將連通性信息隱藏在了數(shù)組索引號(hào)的關(guān)系中锚沸。
假設(shè)f是面的索引號(hào)艘虎，那么這個(gè)面3條半邊的索引號(hào)分別為：
假設(shè)h為半邊的索引，那么其相鄰面的索引以及該半邊在該面中的索引號(hào)為：
假設(shè)要求該半邊指向的下一個(gè)半邊的索引號(hào)咒吐，那么只需要計(jì)算(h + 1) mod 3即可。
每一個(gè)頂點(diǎn)存儲(chǔ)其位置信息和從該點(diǎn)射出的半邊的索引號(hào)属划；每一個(gè)半邊存儲(chǔ)與其配對(duì)的另一條反向的半邊以及該半邊對(duì)應(yīng)的頂點(diǎn)(射出該半邊的)的索引號(hào)恬叹。
這樣存儲(chǔ)一個(gè)頂點(diǎn)需要16個(gè)字節(jié)，存儲(chǔ)一條半邊需要8個(gè)字節(jié)同眯，平均一個(gè)頂點(diǎn)需要64個(gè)字節(jié)绽昼。
該數(shù)據(jù)結(jié)構(gòu)在網(wǎng)格的邊界部分需要特殊處理索引號(hào)。另外該數(shù)據(jù)結(jié)構(gòu)只能單純的表示某種類型的網(wǎng)格须蜗，例如三角形網(wǎng)格或者四邊形網(wǎng)格硅确，而不能表示混合了三角形和四邊形的網(wǎng)格。
