问题标签 [octree]

我正在尝试实现本文中解释的内容：http: //devblogs.nvidia.com/parallelforall/thinking-parallel-part-iii-tree-construction-gpu/

当我使用提供的示例（0.1010、0.0111、0.1100）尝试 Morton3D 函数时，它返回 1479990 而不是 101011110010。

我错过了这里没有解释的东西吗？

谢谢！-D

我正在尝试使用带有实时光线行进的 revelles 算法在 GLSL（v450）中的计算着色器中遍历我的八叉树。我设法遍历它并获得了图像，但我的 fps 非常低，大约 0-5 fps。由于算法伪代码是递归的，因此我使用堆栈将其转换为循环（因为 GLSL 不允许递归）。问题是，一旦我使这个循环非动态统一，我就会得到大约 30-40 的巨大 fps 下降。

如果我在我的堆栈上使用shared属性，我可以得到这个 fps 备份，仅在全局变量的计算着色器中可用：

使其能够在我的工作组中的所有线程之间共享和使用。问题是我无法将这些与barrier()和/或memoryBarrierShared()函数同步，因为它们似乎需要循环动态统一（参见共享变量 www.opengl.org/wiki/Compute_Shader）。由于我无法同步，图像变得像素化并闪烁。

有没有办法将此算法转换为动态统一循环？当循环变得非动态均匀时，为什么fps会下降？

下面是我的主循环代码。

这是问题所在：我有一个几何网格，其中包含要并行处理的多个多边形（三角形），因此我需要一种有效的方法来获取特定区域的多边形数据，即给定边界框 {(x_min, y_min,z_min),(x_max,y_max,z_max)}，我需要获取一个多边形列表，其中包含位于该立方区域内（或部分位于该立方体区域内）的所有多边形。可能吗？

边界框顶点应位于一组统一的笛卡尔网格上。我不确定我是否说清楚了，整个想法有点像八叉树数据结构，但我需要在八叉树的每个节点中存储一个多边形列表。

因此，如果一个节点有 2*2 个子节点，则称为四叉树（2*2=4）。如果一个节点有 2*2*2 个子节点，则称为八叉树（2*2*2=8）。因此，如果您在 2D 中工作，通常最好使用四叉树，而在 3D 中，最好使用八叉树。

但是在 3D 中是否存在具有任意数量子节点的树？就像一棵有 n n n 个子节点的树。它叫什么，是否已经有任何科学工作？

提前致谢。

在文章Advanced Octrees 2: node representations中指出：

节点的 AABB 可以像以前一样显式存储，也可以从隐式存储在位置代码中的节点树深度计算。为了从节点的位置代码推导出节点的树深度，需要一个标志位来指示位置代码的结束。如果没有这样的标志，就不可能区分例如 001 和 000 001。通过使用 1 位来标记序列的结尾，可以很容易地将 1 001 与 1 000 001 区分开来。使用这样的标志相当于设置八叉树根的位置代码为 1。

位置代码是一个 32 位字。也就是说，如果第一个示例后面的所有位都等于第二个示例的位... 001，则... 000 001可能与作者所说的相同。

标记序列的结尾如何帮助我们找到树中节点的深度？

作者使用示例... 1 001和... 1 000 001. 第一个节点是否有深度 1 和第二个深度 2？如果是这样，我怎么知道？位置代码是一个 32 位的字，因此“结束标志”后面的位可以跟随，因为... 001 001它也是有效节点。

所以我真正不明白的是如何在 32 位字中存储位置代码和树中节点的深度。

我正在使用 WebGL 渲染一个巨大的 3D 体积，并且光线投射算法在着色器（glsl）中实现。该卷是从生物图像堆栈创建的。我想要做的是在渲染这个 3D 体积时保持平滑的放大和缩小。但是图像堆栈是高分辨率的，为了获得实时性能，我需要使用八叉树。您对我如何实施它有什么建议吗？

周期性地，应用程序将接收大量具有纬度和经度的移动物体（每秒大约 100,00,000 [100 万] 个）。要求是检测 400 米距离内的任何物体，检测必须在 400 毫秒（毫秒）内完成。

因此，每当应用程序接收到任何具有纬度和经度的新对象时，我首先需要将其添加到数据结构中，并在 400 毫秒内检查数据结构中的任何其他对象是否在距离新添加对象 400 米的范围内。

根据我的研究，我有以下 2 个选项： 选项 1：如果对象数量较少，Redis GEO 可用于上述要求。但是，对于 100 万个对象，执行 geoadd 和 georadius 查询将花费超过 400 毫秒，这是不可接受的。将来对象可以每秒 200 万个。

选项 2：使用八叉树数据结构，这将提供更好的性能由新对象。

我想了很多关于使用 geohash 对数据进行分区的问题。示例 使用 geohash 前缀，将 redis 实例 1 中的数据和其他 geohas 数据保存在 redis 实例 2 中。但是对于两个对象在 400 m 范围内但在相邻象限中的极端情况，它将失败。

问题 有没有人知道根据纬度和经度划分数据并仍然检测相邻对象？或者减少map-reduce范式中的问题？

考虑到未来物体可以达到每秒 200 万个，任何人都可以提出一种不同的方法吗？

我想使用八叉树作为 OGL 场景表示，并且里面有一些移动的对象。我也想用这个八叉树来加速碰撞检测。是否有任何好的算法可以为您提供移动物体将穿透的八叉树路径（此类路径的所有单元/节点）？

假设我有一个我知道速度的移动物体（所以两个位置，一帧中的运动开始和运动结束）。

我的想法是简单地遍历整个树并对包含移动对象的单元格和其余单元格执行碰撞检测。这会给我所有这些，但它不是矫枉过正吗？谢谢！

我将我的数据集分为两组：

1. transactions.Train（80% 的数据）
2. transactions.test（20% 的数据）

然后我使用派对包中的 ctree 方法构建了决策树，如下所示：

我可以成功地在训练集上应用预测方法并使用表函数输出结果如下：

但是当我尝试根据测试集输出表格时，出现了我的问题，如下所示：

错误如下：

我对类似案例进行了研究，这些案例建议省略我所做的任何 NA 值而不改变错误结果。

任何人都可以通过指出这里的问题来帮助我吗？

我有 3D 体素数据，我想重新打包它以提高内存效率和快速访问。数据以常规八叉树的形式生成，每个单元格一个整数值。不幸的是，数据并不稀疏，但应该连接具有相同值的单元格。

我目前的想法是使用 kD-Tree，最好是左平衡的，但我不确定是否有有效的算法来生成它。我有一些想法，但我希望这是已经建立算法的问题之一，或者至少是我可以在谷歌上搜索的名称。