三角形网格的良好数据结构 [英] good data structure for triangular mesh
问题描述
我正在为由三角形组成的 3D 网格或面集寻找一种节省内存且方便的数据结构.
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
我已经将它们从更难使用到更易于使用.它们都是半边数据结构
I've oredered them from the harder to the easier to use. They are all half edge data structures
看看比勒费尔德大学(Surface 开发者)的这篇论文网格)，我认为这对您来说是一个很好的起点！
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屋！
