可编辑网格的存储方式

  渲染时使用的数据结构往往是数组,因为它节约存储空间而且方便索引进行随机访问。但是在模型编辑软件如 Blender、MAYA 中就不能使用数组,取而代之的是类似于链表的数据结构。
  为了方便修改,网格信息时一般不只存储顶点信息,往往还会保存连接信息(mesh connectivity)。


邻接三角形结构


  这次要讨论的是邻接三角形结构(The Triangle-Neighbor Structure)。

  邻接三角形一般采用如下形式:

  • 定义一个三角形,三角形里存储指向相邻三个三角形的指针,和指向三个顶点的指针。
  • 定义顶点,顶点里存储属性信息和一个指向任意邻接三角形的指针。

顶点引用图

  如图所示:Triangle.nbr中第k个元素,指向和该三角形共享k和k+1顶点的相邻三角形。

  一个网格(mesh)包含许许多多这样的信息,在邻接三角形结构下,网格可以用如下方式组织:

  网格中除了必须的顶点索引外,还包含两个附加的数组:一个用来存储每个三角形的三个邻接三角形,一个用来存储每个顶点的任意一个邻接三角形。如下图所示:

网格存储示例

  在邻接三角形结构的网格中,不仅可以以常数时间找到指定的任何编号好的顶点或者三角形,同时也保持了顶点网格的连续性(connectivity)。

  如果顶点 v 是三角形 t 的第 k 个顶点,则 t.nbr[k] 是延顺时针方向围绕着顶点 v 的下一个三角形。如以下伪代码:

  以上算法可以在常数时间内找到所有围绕着顶点 v 的三角形。但是这个算法有一个缺点,由于定义的是 v 指向任意一个三角形(实际也难以规定指向哪一个三角形)。搜索时就会发现必须遍历三角形的顶点来确认自己的位置,产生了许多无意义的搜索。

  为了解决这个问题,可以存储指针指向该三角形的特定边缘,而非指向整个邻接三角形。

  对于这种结构,每个 vertex 存储四个索引(三个顶点和一条边),每个三角形存储六个索引(三个顶点和三条边)。统计中三角形个数大概是顶点数的两倍,所以所以每个顶点存储占用 4nv + 6nt = 16nv。(nv是顶点个数,每个顶点占用4个基本元素的大小,基本元素大小一般为vec4)。

  在这种结构下可以保存进入三角形的信息:

  也就可以遍历以顶点为中心的三角形:

  对于非完备的三角形网格,则可以对边界三角形没有邻接三角形的边 e,使 e 指向的三角形序号为哨兵即可。


翼边结构


  接下来是翼边结构(The Winged-Edge Structure),这种数据结构将边作为最主要的存储单元。

  在翼边网格中,每个 edge 存储指向它连接的两个 vertex (头和尾顶点)的指针,它是两个 face (左右面)的一部分,还有四个指针指向左侧和右侧的 lprev,rprev,lnext,rnext,相对中心边,指向边的排序采用逆时针方式,如下所示:

翼边示例

  相对 e0 而言,e2 为 lprev,e1 为 lnext,e3 为 rnext,e4 为 rprev。

四边形示例

  翼边结构可以以常数时间访问当前当前 vertex 或 face 的所有相邻边。

  与邻接三角形结构不同的是:翼边结构在多边形也同样适用。

  翼边结构也可以去掉 prev 分量,但是如此的话,想要获取 prev 边就必须循环遍历整个 face 来获取它。具体选择要根据空间与时间的平衡。


半边结构(The Half-Edge Structure)


  翼边结构相当优雅,但是它仍有一个可以改进的地方——它需要在移动到下一个边缘之前该 edge 的方向。采用半边结构可以解决这个问题。

  数据存储在每个 edge 分割而成的两个 half-edges 上。每一个 half-edge 会包含四个指针,一个指向它的面元 face,一个指向该 half-edge 的头顶点(head vertex),一个指向另一个相反的 half-edges ,一个指向逆时针旋转的下一条 half-edge。和翼边结构类似,半边结构也可以不保存指向同直线 half-edge 的指针。结构代码如下所示:

  图例如下所示:
半边结构图例

  遍历半边结构也与遍历翼边结构类似,除了——不在需要检查方向。

  这次遍历 vertex 的方向是顺时针的,因为省略了指向 prev 的指针。

  半边结构的存储示例:
半边结构

  在没有边界的网格中,半边通常成对存在,所以很多实现都可以去掉 pair 指针。通过布置阵列,是的偶数边缘 i 总是和 i + 1 配对,奇数边缘 j 总是和 j – 1 配对。


  所有这三种网格拓扑结构都可以支持各种类型的网格进行修改,例如分割或折叠顶点,交换边缘,添加或删除三角形等。具体取用哪一个都需要进行分析后选择。


转载可带上本文永久固定链接:http://www.gleam.graphics/editer_mesh_structure.html

About the Author

说点什么

您将是第一位评论人!

avatar