三角网格的良好数据结构
我正在为三维网格或由三角形组成的面集寻找一种节省内存且方便的数据结构。
目前我正在使用这种“经典”结构：
- 点列表和三角形列表。
- 每个点都有X，Y和Z值。
- 每个三角形有三个索引i0，i1，i2，它们指的是点列表中的一个点。
这是我能想到的最紧凑的布局。 如果我想做的就是绘制网格，并且永远不会修改或过滤它，这是完美的。 但是，它确实使大多数操作修改网格或生成新的部分网格非常麻烦，例如：
- 删除三角形是非常低效的。
- 仅生成少于3个邻居的三角形的新网格
- 查找并删除在给定边界框内具有一个或所有点的所有三角形
- 找到具有一定角度的所有边缘
- 去除短于一定长度的所有边缘
基本上任何需要修改网格，或迭代边缘或找到相邻面/边缘的东西，都需要生成和丢弃几个临时字典和散列集。 没有简单的方法可以迭代单个面的点或边，或单个点周围的边/面。 删除一个点意味着从每个三角形中删除它，然后更改所有三角形中所有其他点的索引值等。
是否有规范的数据结构没有这些缺点，但是内存效率高？
我不是在寻找一个完整的库，只是一个我自己可以实现的结构（尽管了解特定库如何解决这个问题可能很有趣）
有几个开源数据结构可以满足您的需求：
- CGAL https://www.cgal.org/
- OpenMesh http://openmesh.org/
- Surface Mesh http://opensource.cit-ec.de/projects/surface_mesh
我已经将它们从更难以使用到更容易使用。 它们都是半边数据结构
看看比勒费尔德大学（Surface网格的开发者）的这篇论文 ，我认为这是一个很好的起点！