多边形网格处理系列第二篇

文章目录

• • @[toc]
• 2. 网格数据结构
• • 基于面的数据结构
  • • 基本情况
    • 优缺点
    • 改进的face-based数据结构
  • 基于边的数据结构
  • 基于半边的数据结构
  • • 基于有向边的数据结构
    • 小结

2. 网格数据结构

• 判断一种数据结构的好坏标准包括（但不限于）：
  • 构建它的时间
  • 响应特定查找的时间
  • 执行特定操作的时间
  • 存储消耗与冗余

基于面的数据结构

基本情况

• 每个面包含3个顶点位置，不能表示网格连接关系
• 也被称为triangle soup或者polygon soup
• 一些数据转换格式，如stereolighography（STL）使用这种这种表示方式
• 假设使用32 bit的单精度数表示顶点坐标，则每个三角形需要3×3×4 bytes。再根据欧拉定理，面的个数大约是顶点的两倍，因此总共可能需要72 bytes/vertex

优缺点

• 不能显式表示连接关系

  • 一些常见的操作不方便：
    • 访问独立的顶点、边和面，使用非特定的顺序
    • 有向遍历一个面的所有边，找到下一条/上一条边
    • 访问边的相邻面，根据朝向有左边的面或右边的面
    • 给定一条边，访问它的两个端点
    • 给定一个顶点，至少一个相邻面或者边是可访问的（one-ring neighborhood，1-邻域）

• 顶点和对应的数据会重复多次

  • 通过建立关于面的索引，可以大幅减少冗余数据，indexed face set 或shared-vertex。

indexed face se被广泛用于OFF，OBJ，VRML；也被用于OpenGL vertex array

改进的face-based数据结构

• 顶点存储坐标之外，还存储一个相邻面（incident face）
• 面存储对应顶点之外，还存储它的相邻三角形（neighboring triangles）

通过增加连通信息，可以访问到顶点的one-ring neighborhood，并执行上述操作

• 这种改进的数据结构被用于CGAL，大约是24 bytes/face × 2 + 16 bytes/vertex = 64 bytes/vertex
• 这种数据结构也有缺陷，不能显式存储边；列举一个中心顶点的one-ring需要区分不同情况

基于边的数据结构

泛用多边形网格大多是基于边的，盖因连接关系主要与边有关。最有名的edge-based data structure有winged-edge和quad-edge

• Winged-edge，每个边存储它的两个端点，它的两个邻接面，它在左边的面和右边的面的下一条和上一条边；每个顶点存储它的相邻边（之一）；每个面存储它的相邻边（之一）。总开销16 bytes/vertex + 32 bytes/edge +4 bytes/face = 120 bytes/vertex
  
• 基于边的表示可以表征任意多边形，但是one-ring遍历依然需要判断不同情形。最终，被半边结构解决掉这个问题

基于半边的数据结构

• 半边数据结构的最大特点就是把原本不带方向的边分离成两个不同方向的半边，这种数据结构可以表征任意有向的（orientable）2-manifolds（没有复杂边和顶点）多边形网格
• 半边数据结构中，半边之中按照逆时针（counterclockwise）顺序环绕每个面和边缘（boundary）。每个boundary可以看成是一个空的面。据此，每条半边有唯一的角点（corner），这个角点可以存储纹理坐标、法向等
  
• 每个半边存储：
  • 它指向的顶点
  • 它的邻接面（逆时针方向）
  • 这个面的下一条半边（逆时针方向）
  • 这个面的上一条半边
  • 以及它的反向边

若半边总是成对出现，可以不存储;

上一条半边也可以省略，盖因用遍历可以找到

• 相应的，每个面存储它的邻接半边；每个顶点存储它的出边
• 总存储量大约是16 bytes/vertex + 20 bytes/halfedge × 6 + 4 bytes/face × 2 = 144 bytes/vertex
• 半边数据结构方便遍历每种元素（顶点、边、半边、面）的相邻元素，尤其方便one-ring enumeration

基于有向边的数据结构

Directed-edge data structure是一种节约存储的半边数据结构的变种，专为三角形网格设计

因为每3条半边组成一个三角形，所以一条半边的邻接面和它在这个邻接面中的序号都是可以固定计算的：
$$\begin{gathered} face(h)=h/3 \\ fac{e}_{i}ndex(h)=h\mathrm{m}\mathrm{o}\mathrm{d}3 \end{gathered}$$
但是处理边缘的时候比较棘手，需要使用特殊标记，如负数来表示反向半边是不存在的

类似的，也可以设置专为四边形网格的有向边数据结构。但是这两者是不能合并的。因此，除了存储优势外，经典半边适用性更广

小结

建议使用已有的数据结构，如CGAL，OpenMesh，MeshLab等

总结

以上是生活随笔为你收集整理的【笔记】Polygon mesh processing读书笔记（2）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。