问题标签 [octree]

I am working with structured 2.5D and unstructured 3D data, which generally is available in (X,Y,Z) coordinates, i.e. point clouds. Now I want to impose a regular voxel grid onto the data. This is not meant for visualization purposes, but rather for "cleaning" or fusing the data. I imagine cases, where e.g. 3 points fall within the volume of one voxel. Then I would aim at either just setting this voxel to "activated" and discarding the 3 original points or alternatively I would like to calculate the euclidian mean of the points and return the thus "cleaned" point cloud as an irregularly structured one again.

I hope I could make my intentions clear enough: It's not about visualization and not necessarily about using volumetric cubes instead of points. It's only about manipulating possibily irregular point clouds in a structured way.

I was thinking about kd-tree or octree based solutions in this context, but can anybody point me in the proper direction? Hinting at existing MATLAB implementations would be most appreciated.

我目前正在执行一项任务，其中我必须为球体数据集实现一个仅 CPU 的光栅化器。数据集是静态的，因此在运行时不会发生变化，即使整个数据集可以在摄像机前旋转。

现在的想法是实现一些遮挡剔除方法，以便从相机的角度来看被其他球体遮挡的球体不会进入光栅化器的下一个阶段，（针对 z 缓冲区和像素着色进行测试）浪费CPU时间。

我一直在寻找实现这一目标的可能方法。首先，我想到了一个在八叉树中维护场景模型的分层 Z 缓冲实现。然而，由于数据集旋转，我需要重新计算每一帧的八叉树，这可能非常昂贵。我对吗？

我不确定在这种情况下，空间散列或一些更便宜的计算球体数据集的分层组织是否会更有益。对此有什么想法吗？请注意，这必须在 CPU 上完全实现。

我目前正在实施 Revelles、Urena 和 Lastra 的论文“An Efficient Parametric Algorithm for Octtree Traversal”。在Ray - Octree 交叉算法中，有人实现了它并粘贴了他的代码。我的实现应该是相同的，只是我使用了一些向量进行计算。然而，使用这个八叉树只会渲染图像的右上角，对于图像的其余部分，八叉树不会被遍历。检查是否遍历发生在以下方法中：

[编辑]上述方法实现功能

从纸上。正如 C. Urena 指出的那样，论文中有一个错误导致遍历不正确。不幸的是，在此错误起作用之前跳过了遍历。在 C. Urena 的链接之后可以找到的 Google 组中，似乎八叉树节点的大小的计算方式不同。我做了：

相对

在谷歌组。我将对其进行测试并发布另一个更新。[/编辑]

[编辑 2]应用 Carlos 提到的修复程序并将大小减少一半给我带来了这么多：

球体应该被完全渲染，但至少不是左上角的所有光线都被拒绝。[/编辑 2]

[编辑 3]使用不同的数据集我得到了看似更好的结果，看起来我必须调查代码的其他部分。

[/编辑 3]

我有一个八叉树，它存储基于体素的流体。当我模拟流体时，我需要访问当前节点周围的叶子，我该如何实现这样的搜索？

您可以假设节点存储指向其父节点的指针。（也许需要其他数据？）

我正在用 C++ 实现一个八叉树，它稍后应该包含一个用于渲染的网格。但目前我正在努力构建八叉树。更准确地说，导致问题的是 addNode() 函数。我想到了一个类似于二叉树的递归实现： Binary Tree implementation C++

但是，在八叉树中，每个节点都有 8 个儿子，而不仅仅是 2 个。此外，因此我不能像在二叉树中那样使用简单的开关（左/右）来决定在哪里添加节点。我需要检查 8 个儿子之一是否为空（指针为 NULL），如果没有指针为空，我需要使用其中一个儿子作为参数调用 add 函数。然而，这将导致一个八叉树，其中第一个儿子总是包含所有后续的子八叉树。这个 add 函数通常是如何实现的并避免了这个问题？

到目前为止，关于设计决策的一些背景知识......我开发了一个可以存储点的八叉树结构。我选择根据某个基本体素大小来限制“世代”的递归。仅当将点添加到该节点时才会创建子节点。这不是一个动态的图形应用程序——这个八叉树和其中的对象是静态的，因此无需担心提高性能的预处理。

现在，我想在我的八叉树中添加“形状”——特别是由三角形组成的表面网格。这些三角形的顶点与八叉树中存储的点不对应。如何将这些形状存储在八叉树中？我看到两个选项...

灰色节点是“空的”，因为它们没有形状。在备选方案 1 中，形状存储在它们相交的每个节点中 - 即，节点 1a 包含 shape1，而 4c 和 4d 共享 shape2。在备选方案 2 中，形状仅存储在它们相交的最小节点中 - 即，节点 1a 包含 shape1，节点 4 包含 shape2。

我见过的大多数关于八叉树的帖子都假设 Alt1，但他们从未解释过原因。Alt2 对我来说更有意义，只会为那些位于节点边界上的形状创建额外的工作。为什么 Alt1 更可取？

编辑：为了澄清，我使用的实现语言是 C++，所以我更喜欢该语言的示例实现，但问题与语言无关。对不起，如果这是不正确的标签使用。

Edit2：虽然与形状存储问题没有直接关系，但此链接对问题背后的八叉树遍历进行了很好的讨论。我认为它可能会帮助任何有兴趣研究这个问题的人。

更新：四年后，Alt2 最终变得更容易实现，但速度很慢，因为存储在更高八叉树级别的大三角形在每次遍历八叉树时都要进行测试——在我的例子中，这意味着成百上千次不必要的测试。我最终修改了我的代码以使用R*-Tree 变体，这很容易实现并且速度大大加快。

我发现很难在 Java 中使用位图图像的颜色。java - 如何使用八叉树颜色量化算法或任何其他更好的算法在java编程中获得最常用的图像颜色？

我正在构建一个空间八叉树。为了确定某个点 (x,y,z) 应该放置在哪个分支/八分圆中，我使用了这个函数：

它为每个八分圆返回一个唯一的 0 到 7 之间的数字。事实证明，这个片段被多次调用。建造大树时会非常耗时。

有什么简单的方法可以加快这个过程吗？

这已经提供了 30% 的加速：

还有其他提示吗？

问题陈述：使用八叉树找到每个粒子最近的 GRID ID。

图。1]：

图[2]：

我有一个粒子系统（~6k，可移动），我需要检查哪个网格点（刚性；在图片中）最接近。有人建议我选择 Octree，因为它对于 3D 网格来说速度很快。

这是递归八叉树获取网格最近网格点的正确算法吗？

1. 获取一个输入作为点 P 起始坐标 C（第一次是 [0,0,0]）
2. 起始尺寸 = [Sx, Sy, Sz]
3. 得到所有 8 个中点 Mi = {M1,..,M8} 得到 Mi 和 P 的最小距离

4. 假设 M 得到 M 的起始位置为 Cn 设置大小 Sn = [Sx/8, Sy/8, Sz/8]

5. 如果 M 和 P 的距离小于 2 *（网格空间 G）：

   5.1。迭代从 Cn 到 Sn 的所有网格点

   5.2. 打印最少作为结果

6. 别的

   6.1。设置起始坐标为 Cn

   6.2. 将大小设置为 Sn

   6.3. 转到 1

问题：如果粒子在边界外或接近边界，最后一次迭代会耗尽所有速度，因为它检查所有 A x B x C。

请建议您是否有更好的方法来解决此问题。

我目前正在一个高效的计算引擎中工作，用于 CPU 和 GPU 中的粒子模拟。我最近一直在研究八叉树，我设法为空间中的粒子编写了一个八叉树的工作版本，并且还有效地处理了它们的碰撞。现在我必须在我的八叉树中插入三角形网格（STL 对象），以便我也可以处理粒子和对象三角形之间的碰撞。我很困惑如何以有效的方式将三角形插入到我已经创建的八叉树中？请提出实现这一目标的方法。如果这有帮助，我正在使用 C++。已经谢谢了。