我要寻找一个内存高效而便捷的数据结构，三维网格或面组构成三角形。

I am looking for a memory-efficient yet convenient data structure for a 3D mesh or face-set consisting of triangles.

目前我使用的这个经典的结构：

Currently I am using this 'classical' structure:

点的列表，和三角形的列表。 在每个点都有一个X，Y和Z值。 每个三角形有三个指数I0，I1，I2，是指在点列表的一个点。

这是最紧凑的布局，我能想到的。这是完美的，如果我想要做的就是绘制网格，从不修改或过滤。 然而，它确实使修改网格或生成新的部分网状非常繁琐的大多数操作，例如：

This is the most compact layout I can think of. It is perfect if all I want to do is draw the mesh, and never modify or filter it. However it does make most operations that modify the mesh or generate a new partial mesh very cumbersome, for example:

删除三角形是非常低效的。 生成一个新的网格只用了不到3个三角形的邻居 查找并删除所有具有一个或三角形的所有点在给定的边界框 查找所有边缘有一定的角度 删除超过一定长度较短的所有边缘

基本上任何需要修改的网格，或者遍历边缘或发现相邻的面/边缘，需要产生和丢弃几个临时词典和哈希集。有没有简单的方法来遍历点或个体面的边缘，或边缘/面围绕着一个单独的点。除去一个点意味着从每个三角形删除它，然后在所有的三角形更改索引值，所有其他点等。

Basically anything that requires modifying the mesh, or iterating over the edges or finding neighboring faces/edges, requires generating and discarding several temporary dictionaries and hash sets. There is no easy way to iterate over the points or edges of an individual face, or the edges/faces around an individual point. removing a point means removing it from each triangle, then changing the index values for all other points in all triangles, etc.

有没有办法，没有这些缺点的规范的数据结构，又是内存效率？

Is there a canonical data structure that does not have these drawbacks, yet is memory-efficient?

我不是在寻找一个完整的图书馆，只是一个结构，我可以实现我自己（虽然可能有兴趣知道特别是如何图书馆已经解决了这个问题）

I am not looking for an entire library, just a structure I can implement myself (although it may be interesting to know how particular libraries have solved this problem)

推荐答案

有一对夫妇的开源数据结构，可能会满足您的需要：

There's a couple of open source data structure that may fit your needs:

在CGAL https://www.cgal.org/ OpenMesh http://openmesh.org/ 在表面网格 http://opensource.cit-ec.de/projects/surface_mesh CGAL https://www.cgal.org/ OpenMesh http://openmesh.org/ Surface Mesh http://opensource.cit-ec.de/projects/surface_mesh

我从很难的更容易使用oredered它们。他们都是半边数据结构

I've oredered them from the harder to the easier to use. They are all half edge data structures

看看从比勒费尔德大学本文（开发商目），我认为这是一个很好的起点为您服务！

Take a look at this paper from Bielefeld university (developers of the Surface mesh), I think that it's a good starting point for you!