三角網格

三角網格(英語: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).