OpenMesh是一个通用的、高效的数据结构,用来表示和处理多边形网格(polygonal mesh)。它的设计遵循以下几个原则:

  1. 灵活:为不同的算法提供了通用基础,而不需要进行调整。
  2. 高效:在最大程度节省了时间的同时尽可能的降低内存使用。
  3. 易用:为处理复杂的内在结构提供了易用的接口。

特点

  OpenMesh有以下特点:

  • 任意多边形的表示(通常情况)和三角网格表示(更加高效的、专门优化的)。
  • 明了的vertices、halfedges、edges和faces表示。
  • 快速的邻域访问,尤其是One-ring neighborhood。
  • 高度可定制性:

    • 可选择坐标类型(维度和标量类型)。
    • 为网格添加用户自定义的元素或函数。
    • 在运行过程中用动态特性添加数据。

halfedge数据结构

  多边形网格包含几何(vertices)和拓扑结构(edges,faces)。多边形网格数据结构的主要区别在于存储拓扑信息的方式。基于面的结构缺少清晰的边的表示,基于边的结构因为丢失了边的方向导致效率低下,而半边结构克服了这些缺点。半边结构(使得边分成了不同朝向的两个部分)存储主要的连通信息:

这种方法表示出的点边面简单又直观。半边数据结构如上图所示,它将两点之间的边抽象成两条边,首先包含一个点,给定一个向量又能表示出这个点所在的面,同时还存储了指向的下个半边和对面的半边,下个半边可以认为是vertex的跳转,对面的半边则是face的跳转。半边结构还包含可选的前向半边。

重复(2)-(4)可以实现相邻节点的遍历。

实现

  下图为OpenMesh各部分的交互。

  该架构允许用户定义网格 ,用户可以为点边面制定任意的特性,或者为网格kernel选择预先定义的属性。kernel负责网格成员的存储,可以选择使用数组或双链表作为容器类型。因为不同属性的网格需要使用不同的C++类型,OpenMesh使用泛型编程实现网格的算法。类STL的方法有以下优点:

  • 非虚函数表和动态绑定
  • 没有内存和运行时开销
  • 输入数据是模板参数,在编译时