良好的数据结构三角形网格 [英] good data structure for triangular mesh
问题描述
我要寻找一个内存高效而便捷的数据结构，三维网格或面组构成三角形。
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!
这篇关于良好的数据结构三角形网格的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
