三角網格

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

海豚的三角網格例子。

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

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

表示方式

使用OpenGLDirectX 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,而無需任何中間處理。

參考資料

  1. ^ 董洪偉. 三角网格分割综述. 中國圖象圖形學報: 181–193. [2018-05-25]. doi:10.11834/jig.20100201. (原始內容存檔於2018-05-26). 
  2. ^ Colin Smith, On Vertex-Vertex Meshes and Their Use in Geometric and Biological Modeling頁面存檔備份,存於網際網路檔案館), (PDF)
  3. ^ http://staff.ustc.edu.cn/~lgliu/Courses/GAMES102_2020/PPT/GAMES102-13_TriangularMeshes.pdf
  4. ^ Amit Patel. Data structure for triangle meshes. Red Blob Games. [2022-09-24]. (原始內容存檔於2022-09-28).