我正在寻找一种内存占用小但方便的数据结构,用于表示由三角形组成的三维网格或面集。
目前我正在使用这种“经典”的结构:
- 一个点列表和一个三角形列表。 - 每个点都有X、Y和Z值。 - 每个三角形都有三个索引i0、i1、i2,这些索引指向点列表中的一个点。
这是我能想到的最紧凑的布局。如果我只想画网格而不是修改或筛选它,那么它是完美的。然而,它使得大多数修改网格或生成新的部分网格的操作非常麻烦,例如:
- 删除三角形非常低效。 - 仅生成具有少于3个邻居的三角形的新网格 - 找到并删除所有在给定边界框内的点或全部点所在的三角形 - 找到所有具有特定角度的边缘 - 删除所有短于一定长度的边缘
基本上,任何需要修改网格或迭代边缘或查找相邻面/边缘的操作都需要生成并丢弃多个临时字典和哈希集合。没有简单的方法可以遍历单个面的点或边缘,或者围绕单个点的边缘/面。删除一个点意味着将其从每个三角形中删除,然后更改所有其他点在所有三角形中的索引值等等。
有没有一种经典的数据结构可以不具备这些缺点,但是内存占用小?
我不是在寻找整个库,只是一种我可以自己实现的结构(尽管了解特定库是如何解决此问题可能很有趣)。
目前我正在使用这种“经典”的结构:
- 一个点列表和一个三角形列表。 - 每个点都有X、Y和Z值。 - 每个三角形都有三个索引i0、i1、i2,这些索引指向点列表中的一个点。
这是我能想到的最紧凑的布局。如果我只想画网格而不是修改或筛选它,那么它是完美的。然而,它使得大多数修改网格或生成新的部分网格的操作非常麻烦,例如:
- 删除三角形非常低效。 - 仅生成具有少于3个邻居的三角形的新网格 - 找到并删除所有在给定边界框内的点或全部点所在的三角形 - 找到所有具有特定角度的边缘 - 删除所有短于一定长度的边缘
基本上,任何需要修改网格或迭代边缘或查找相邻面/边缘的操作都需要生成并丢弃多个临时字典和哈希集合。没有简单的方法可以遍历单个面的点或边缘,或者围绕单个点的边缘/面。删除一个点意味着将其从每个三角形中删除,然后更改所有其他点在所有三角形中的索引值等等。
有没有一种经典的数据结构可以不具备这些缺点,但是内存占用小?
我不是在寻找整个库,只是一种我可以自己实现的结构(尽管了解特定库是如何解决此问题可能很有趣)。