Mesh网格数据结构2-半边结构

本文将详细介绍半边结构（Halfedge-based data），以及Face-based data，Edge-based data, Directed-edge data structure.
上一节提到Face-based data，本节续Halfedge-Based Data Structure,Directed-edge data structure继续讨论。

1.Edge-based data Structure

基于边的数据结构如下所示。每一个edge都存储了相邻的两条edge的ref，两个vertex的position，以及相邻的两个face（left and right）。
关于vertex/face就会store position 和 拥有它的一条边的信息。

虽然基于边的数据结构可以表示任意多边形网格，但遍历单环仍然需要区分顶点是边的第一个顶点还是第二个顶点，这个问题最终由半边缘数据结构解决，下一节将对此进行描述。

2.HalfEdge-Based Data Structure

这种数据结构能够表示任意多边形网格，这些网格是可定向流形面（没有复杂的边和顶点）的子集。半边数据结构是以顺时针方向为定位而存储。每个半边指定一个唯一的角（并非共享一个顶点，在一个面上），因此属性如纹理坐标或法向可以存储在每个角。
存储的数据结构包括：
边指向的顶点，邻接的face（nullptr represent boundary halfedge), next Halfedge，previous Halfedge，and opposite halfedge。
半边数据结构使我们能够枚举每个元素，给出一个vertex，enumerate sequence：vertex->outgoing halfedge->opposite halfedge->next halfedge->…。

3. Directed-edge data structure

直接边数据结构是半边数据结构的内存高效变体，专门为三角网格设计。它基于引用网格中每个元素的索引（顶点、面或半边）。索引遵循一定的规则，这些规则隐式地编码三角网格的一些连接信息，类似于hash操作，从face index到halfedge。这个数据结构不是配对Opposite halfedge，而是将属于一个公共triangle的三个halfedge。
直接边可以表示所有可以用一般半边数据结构表示的三角形网格。然而，请注意，边界是由特殊（例如，负）索引处理的，表明相反的半边是无效的。遍历边界循环的开销更大，因为没有原子操作来枚举下一个边界。对于一般的半边结构，这可以被沿边界的下一个半边有效地访问。