一种基于数组的网格数据结构

本文介绍一种在网格引擎开发中有效的网格数据结构，非原创。

---

在三维几何内核中，提到了长方体有很多种表示方式，其中一种是以原点，长，宽，高四个double型参数表达，一种是以Brep边界表达，包含了自顶向下的复杂拓扑和几何信息。其实这两种表达方式的数据信息可以相互转换，也就是由原点长宽高可以建出Brep结构，由Brep信息也可以计算出原点长宽高。

这两种数据结构，不考虑应用场景，从研发角度看，是一个时间和空间平衡问题。如果程序中不需要高频取数据结构，频繁利用参数构建数据结构，参数型表达可以省下很多内存和硬盘开销，相反，利用Brep结构数据，可以省下可观的计算开销。

---

有限元计算中的网格数据一般分为两部分

1. 节点信息

2. 单元信息

其中，节点信息是包含3个double型表示空间xyz的实际坐标信息。单元则是由节点索引构成的，下图中右边表示了三角形的网格结构。这种数据结构用来表示网格没有问题，但是在网格划分生成过程中，需要大量的查询和修改操作，这种数据结构是无法满足要求的。

在网格生成过程中，需要进行如下大量查找：

1. 哪些面使用了某个顶点
   

2. 哪些边使用了某个顶点
   

3. 哪些面使用了某条边
   

4. 哪些边构成了某个面
   

5. 哪些面和某个面相邻

网格引擎常用的数据结构是半边结构HEDS(Half-Edge-Data-Structure)，其中每条边上由两个方向相反的边组成，每条半边包含所在的面和下一条半边以及末端顶点信息，在非边界上可以很好表达相邻面的信息。

以上数据结构定义了一个半边结构，图片来自于

https://www.flipcode.com/archives/The_Half-Edge_Data_Structure.shtml

半边数据结构虽然可以很好的表达网格，也满足查询，但是存储的数据还是偏多。

---

新提出的数据结构，根据点，边面的索引顺序构造了如下新的数据结构：

1. 每个半边对应一对索引，该索引由两个数据构成，一个是由包含该点的面索引，一个是面包含的一条边索引；创建边界上的点到一个边界半边的映射(map)
   

2. 创建非边界半边到对应方向相反的半边的索引映射(map)

3. 创建边界半边到对应方向相反的非边界半边的索引映射(map)

   
   
   

该数据结构有效利用数组顺序结构特性，压缩了数据，降低了内存使用量，也是很多商用网格引擎使用的基本数据结构。

本文仅提供了该数据结构的基础信息，更多详细设计参考如下原文：