arrays - 您实际上如何制作八叉树（用于体素）？

Question

我见过创建八叉树、添加和删除数据的代码，但实际上如何构建八叉树呢？是否有 3d 体素软件可以保存到某种数组中，然后可以转换为八叉树？或者你可以直接保存到八叉树吗？

Answer 1

取决于您的实施 -

如果您使用八叉树来细分空间，那么通常您会向它扔一堆 V3，一旦一个节点中有超过一定数量的点，您就会细分并重新分配它们。

如果您正在寻找一种存储我的世界风格体素的方法，那么您将细分直到您的体素大小达到 1:1，并将您的数据存储在叶节点中。

数据来自哪里取决于您——八叉树是一种存储、操作和搜索数据的方式，而不是文件格式本身。

Answer 2

八叉树中的每个节点都有一个点。这些节点被分成（你猜对了）八个子节点。这些节点依次包含一个点。

一般来说，你不会将所有顶点添加到八叉树中，除非你正在做一些不合时宜的碰撞检测，其中每个顶点都很重要……并不是说你不能让它快，但它仍然比近似值慢由较少数量的节点给出。（这几乎适用于所有事情，近似值更快）。

同样，如果您正在以高质量的八叉树进行渲染，则节点数可能与您的点数一样多。

现在开始回答：

1. 创建一个带有从中心包围它的边界框的根节点。

2. 插入每个点。这应该在相关方向细分八叉树。

   1. 当您插入这些点时，数据将进一步向下移动到更紧密地封装您的模型的叶节点中。
   2. 此外，当您细分时，每个后续节点的边界框都会减半。
3. 如果您真的想保存它，您可以保存顶点（编号），然后让您的程序将节点之间的各种连接和顶点记录到磁盘上，它们将能够在大致相同的时间内加载首先需要从头开始构建八叉树。

无论如何，我希望我回答了你的问题。