三角網格

三角網格（英語：Triangle mesh）是數字建模處理的一個重要的概念。^[1]一個3D建模由多個三角形以不同角度(共用邊或角)組合的3D模型，而外圍的每個三角形構成三角網格。

海豚的三角網格例子。

許多圖形軟體包和硬體設備操作網格里的三角形，比操作相似數量的單獨的三角形更加有效率。這是因為一般情況下，計算機圖形對三角形的頂點進行處理。如果對於單獨的三角形，則每個頂點都要處理。但在大型網格中，一個頂點可能被許多三角形共用，如果每個頂點僅做一次操作，則時間會減少很多，但效果保持不變。

在許多計算機圖形應用中，都會用到三角網格。網格由頂點，邊，和三角形組成。應用可能需要了解網格部分間的各種連接。這些連接可以獨立維護，獨立於實際的頂點位置。許多種資料結構都可以用來處理三角網格，並支持對網格內容的查詢。^[2]

表示方式

使用OpenGL和DirectX API，主要有兩種方式將三角網格傳給圖形硬體，分別是三角形帶（英語：Triangle strip）和索引數組。

三角形帶

三角形帶是一種在三角形之間共享節點數據的方法。三角形帶中，每個三角形和一個相鄰的三角形共用一條邊，而和下一個三角形共用另一條。另一種方式是三角形扇（英語：Triangle fan），它是共用一個中心節點的相連三角形集合。使用這些方法，節點的處理很有效率，只需要處理N+2個節點，來繪製N個三角形。^[3]

三角形帶很有效，然而缺點是對於任意三角網格而言，將其轉換成三角形帶的方式可能並不明顯或便捷。

資料結構

對於這種簡單的資料結構，其抽象表示是

Vertex = <integer>; // v
Edge = <integer, integer>; // v0, v1
Triangle <integer,integer,integer>; // v0, v1, v2
VData = <application-specific vertex data>;
EData = <application-specific edge data>;
TData = <application-specific triangle data>;
VAttribute = <VData, set<Edge>,set<Triangle>>; // data, eset, tset
EAttribute = <EData, set<Triangle>>; // data, tset
TAttribute = <TData>; // data
VPair = pair<Vertex,VAttribute>;
EPair = pair<Edge,EAttribute>;
TPair = pair<Triangle,TAttribute>;
VMap = map<VPair>;
EMap = map<EPair>;
TMap = map<TPair>;
Mesh = <VMap,EMap,TMap>; // vmap, emap, tmap

這些映射支持哈希表的標準插入和刪除函數。僅當該項目尚不存在時，才會插入。僅當該項目確實存在時，才會刪除。^[4]

邊坍縮

此操作涉及確定邊 hvk，vti，其中 vk 稱為保留頂點，vt 稱為丟棄頂點。共用此邊的三角形將被從網格中移除。頂點 vt 也會被從網格中移除。任何共用 vt 的三角形都將該頂點替換為 vk。

索引數組

對於索引數組，網格由兩個單獨的數組表示，一個數組保存頂點，另一個數組則是三角形對應的三個頂點的索引集合。圖形系統首先處理頂點，然後使用轉換後數據的索引，渲染三角形。在 OpenGL 中，當使用頂點緩衝區對象（英語：Vertex Buffer Object）（VBO） 時，glDrawElements() 基元用於實現此功能。

使用此方法，可以存儲和操作共用任意數量頂點的任何三角形集，並將其傳遞到圖形 API，而無需任何中間處理。